Информационный поиск Лидия Михайловна Пивоварова Системы понимания текста

Введение Информационный поиск – поиск в большой коллекции документов, удовлетворяющих потребности пользователя, сформулированной в виде короткого запроса на естественном языке. Информационный поиск – поиск в большой коллекции документов, удовлетворяющих потребности пользователя, сформулированной в виде короткого запроса на естественном языке. Стремительный рост Интернета и успешное развитие информационно-поисковых систем привели к тому, что современный информационный поиск как дисциплина включает широкий круг вопросов, связанных со сбором, хранением, поиском и представлением самой разнообразной информации; сюда же естественным образом относятся многие задачи автоматической обработки текста. Стремительный рост Интернета и успешное развитие информационно-поисковых систем привели к тому, что современный информационный поиск как дисциплина включает широкий круг вопросов, связанных со сбором, хранением, поиском и представлением самой разнообразной информации; сюда же естественным образом относятся многие задачи автоматической обработки текста.

Содержание 1. Индексирование 2. Модели информационного поиска 3. Оценка информационного поиска 4. Роль автоматической обработки текста в информационном поиске

Индексирование Поиск по большим коллекциям не может осуществляться в режиме реального времени. Поиск по большим коллекциям не может осуществляться в режиме реального времени. Для быстрого поиска коллекция предварительно обрабатывается и по ней строится индекс(ы) – набор атрибутов, которые упорядочены в удобном для поиска порядке. Для быстрого поиска коллекция предварительно обрабатывается и по ней строится индекс(ы) – набор атрибутов, которые упорядочены в удобном для поиска порядке. В случае полнотекстового поиска такими атрибутами являются слова (словосочетания), приведенные к нормальной форме. В случае полнотекстового поиска такими атрибутами являются слова (словосочетания), приведенные к нормальной форме.

Структура индекса

Процесс индексирования 1. Анализ структуры – выделение заголовков, абзацев и т.п.; удаление html-разметки и т.д; 2. Токенизация – разбиение текста на слова, удаление знаков препинания; 3. Удаление стоп-слов - высокочастотных служебных слов (предлогов, союзов и т.п.); 4. Лемматизация – приведение слов к нормальной (например, словарной) форме; 5. Взвешивание

Взвешивание В индексе хочется учитывать не только сам факт вхождения слова в документ, но и «вес», т.е. информацию о частоте данного слова в документе. В индексе хочется учитывать не только сам факт вхождения слова в документ, но и «вес», т.е. информацию о частоте данного слова в документе. Однако саму по себе частоту использовать плохо, поскольку слова распределены в языке неравномерно: некоторые встречаются гораздо чаще других Однако саму по себе частоту использовать плохо, поскольку слова распределены в языке неравномерно: некоторые встречаются гораздо чаще других

Закон Ципфа (Zipf) Произведение частоты термина f на его ранг r остается примерно постоянной величиной f = C/r, C N/10

Принцип Луна (Luhn) Самые часто встречающиеся слова – не самые значимые!

Классический метод взвешивания: tf-idf tf – относительная частота слова в документе tf – относительная частота слова в документе idf – обратная документальная частота (чем меньше в коллекции документов, в которые входит это слово, тем idf больше) idf – обратная документальная частота (чем меньше в коллекции документов, в которые входит это слово, тем idf больше) Вес слова в документе: В современных поисковых системах используются более сложные варианты взвешивания.

Содержание 1. Индексирование 2. Модели информационного поиска 3. Оценка информационного поиска 4. Роль автоматической обработки текста в информационном поиске

Булева модель Запрос: булево выражение: Запрос: булево выражение: Ответ: Ответ: Плюс: простота; минус: отсутствие ранжирование Плюс: простота; минус: отсутствие ранжирование

Векторная модель Коллекция из n документов и m различных терминов представляется в виде матрицы mxn, где каждый документ – вектор в m-мерном пространстве. Коллекция из n документов и m различных терминов представляется в виде матрицы mxn, где каждый документ – вектор в m-мерном пространстве. Веса терминов можно считать по разному: частота, бинарная частота (входит – не входит), tf*idf… Веса терминов можно считать по разному: частота, бинарная частота (входит – не входит), tf*idf… Порядок слов не учитывается (bag of words) Порядок слов не учитывается (bag of words) Матрица очень большая (большое число различных терминов в гетерогенной коллекции). Матрица очень большая (большое число различных терминов в гетерогенной коллекции). В матрице много нулей В матрице много нулей

Векторная модель Близость запроса к документу: косинусная мера близости Близость запроса к документу: косинусная мера близости

Вероятность вычисляется на основе теоремы Байеса: Вероятность вычисляется на основе теоремы Байеса: P(R) – вероятность того, что случайно выбранный из коллекции документ D является релевантным P(R) – вероятность того, что случайно выбранный из коллекции документ D является релевантным P(d|R) – вероятность случайного выбора документа d из множества релевантных документов P(d|R) – вероятность случайного выбора документа d из множества релевантных документов P(d) – вероятность случайного выбора документа d из коллекции D P(d) – вероятность случайного выбора документа d из коллекции D Вероятностные модели

Решающее правило заключается в максимизации следующей функции: Решающее правило заключается в максимизации следующей функции:

Содержание 1. Индексирование 2. Модели информационного поиска 3. Оценка информационного поиска 4. Роль автоматической обработки текста в информационном поиске

Оценка информационного поиска Полнота (recall): R = tp / (tp+fn) Точность (presicion): P = tp / (tp+fp) F-мера: Аккуратность (accuracy): A = (tp + tn) / (tp + tn +fp +fn) Релевантные Нерелевантные Найденныеtpfp Ненайденныеfntn Оценка требует большой коллекции размеченных документов, т.е. огромного труда асессоров. Большое продвижение дают конференции-соревнования: TREC, РОМИП и т.д.

Содержание 1. Индексирование 2. Модели информационного поиска 3. Оценка информационного поиска 4. Роль автоматической обработки текста в информационном поиске

Уровни анализа языка Морфологический анализ Морфологический анализ – признан необходимым для информационного поиска, особенно для флективных языков (например, русского); сюда же относится предсказательная морфология (для незнакомых слов), а также исправление опечаток. Синтаксический анализ Синтаксический анализ – уже из самого понятия bag of words следует, что синтаксис здесь практически не используется; исключения: линейный порядок слов, именные группы, сборка терминологических словосочетаний. Семантический анализ Семантический анализ – в классическом информационном поиске как правило не используется; некоторые элементы лексической семантики применяются при расширении запросов, индексировании документов и составлении каталогов.

Источники 1. J. Savoy, E. Gaussier Information Retrieval // Handbook of natural language processing, Second Edition Editor(s): Nitin Indurkhya; Fred J. Damerau, Goshen, Connecticut, USA – 2010 – pp К. Д. Маннинг, П. Рагхаван, Х. Шютце Введение в информационный поиск – Вильямс, А.В. Сычев Информационно-поисковые системы -