Информационный поиск Андрей Федоровский, Mail.Ru

Что будем искать? Поиск по формальным параметрам Структурированная, связанная синтетическая коллекция Точные однозначные запросы Реляционная алгебра, SQL. Результат однозначно определяем. Скучно.

Что будем искать? - 2 Полнотекстовый поиск Коллекция текстовых документов на естественном языке Запросы в виде короткой строки на естественном языке Результат – документы, релевантнные запросу. Релевантность у каждого своя. Интересно.

Используем Графематика Морфология Постморфология, снятие омонимии Text mining, фактографический поиск Размеченные корпуса для обучения

Используем - 2 Определение тематики документов Фильтрация нежелательной информации Нечеткие дубликаты Авторитет источника Кластеризация результатов Машинное обучение, методы оптимизации

Как будем искать? Прямой поиск (Кнут-Моррис-Пратт, Бойер-Мур) Документ длиной n, образец длиной m. Предвычисления за O(m) Поиск за O(n) Гибок. Легко задать сложные критерии совпадения: нечеткий поиск (Bitap), regexp.

Как будем искать? - 2 Суффиксные деревья (Укконен), суффиксные массивы (Salson) Документ длиной n, образец длиной m. Предвычисления за O(n) Размер индекса O(n) Скорость поиска O(m) При хорошей скорости индексации и поиска позволяет искать любую подстроку.

Векторная модель документа Документ и запрос как наборы слов. Графематический и морфологический разбор. Строим вектора в пространстве слов: Минус – теряем взаимное расположение слов. Обычно контекст слов ценен, его жаль выбрасывать.

Обратный индекс Набор лемм со списком включающих ее документов ПИТЬ : (d12, d821, d4421) ПИЛА : (d821) Словопозиции, морф. параметры словоформы ПИТЬ : (… d821 (pos22, "Г пр.в.,ж.р.,ед.ч. ")…) ПИЛА: (… d821 (pos22, "С ж.р.,им.п.")…) Хорошо, если совпадают словоформы в документе и запросе. И если слова находятся рядом.

Запрос Превращаем строку в дерево: [Рыба пила] Рыба & (пить | пила) Получаем списки документов из обратного индекса, объединяем или пересекаем их: РЫБА: (d12, d56, d821, d970) ПИТЬ : (d12, d821, d4421) ПИЛА : (d821, d970) Результат – (d12, d821, d970)

Запрос - 2 Удаление стоп-слов: [быть или не быть] Расширение запросов [МГУ адрес] => [(МГУ | Московский Государственный Университет) адрес] Сужение запросов. Например, исходя из геолокации пользователя [купить телефон] => [купить телефон Рязань] Ускорение различными эвристиками в раз.

Релевантность TF – вес слова в документе IDF – насколько слово редкое в коллекции

Релевантность BM25 Здесь учитывается длина документа. В действительности таких влияющих факторов множество.

Что еще влияет Разметка документа. Графематический модуль совмещен с парсером html и сохраняет информацию о зонах документа. Пассажи – компактно расположенные в документе группы слов запроса. Они же помогают формировать сниппеты и являются аннотацией документа в выдаче. Кворум слов запроса. С учетом IDF.

Что еще влияет 2 Соответствие словоформ в запросе и документе Совместная встречаемость слов запроса в документе недалеко друг от друга Согласованность тематик запроса и документа

Определение дубликатов Точные – контрольная сумма Нечеткие – шинглы (Broder) Я к Вам пишу, чего же боле Я к Вам пишу, чего же боле –> CRC Выбор нескольких – множеством способов:

Авторитетность. PageRank Вероятность пользователя случайно перейти на документ Вероятность перейти или случайно, или по ссылке из другого документа. Он очень быстро итеративно сходится. Через итераций имеем устойчивое решение.

Измерение качества Точность Полнота Точность на N Можно одновременно поднять и точность, и полноту?

Измерение качества - 2 F-мера Обобщение Пока мы не учитываем позиции в результатах.

Измерение качества - 3 Средняя точность Полнота в формулу не входит. Почему же AvP считается интегральной мерой?

Измерение качества - 4 DCG – оцениваем еще и позицию в выдаче. NDCG – нормируем на идеальную выдачу.

11-точечный график TREC

Тестирование качества Асессоры вручную просматривают результаты. Несколько систем образуют общий набор результатов. Документы не из этого набора считаются нерелевантными. Это – метод «общего котла» (TREC, РОМИП) Точность системы можно понять и по одному набору. Для полноты – нужен общий.

Оптимизация параметров TFIDF веса для слов и для устойчивых словосочетаний слова запроса в заголовке документа, в начале документа пар слов запроса в документе с сохранением смежности и порядка пассаж в документе, плотно содержащий все слова запроса авторитетность документа тематика документа наличие ссылок на документ, содержащие слова запроса et cetera, et cetera…

Оптимизация параметров Набор параметров Критерий качества Подбор оптимального набора Метод имитации отжига (Simulated annealing) Генетические алгоритмы Деревья решений См. «Numerical recipes in C» или Jason Brownlee «Clever Algorithms»

Переобучение С ростом m ошибка падает. Нужно ли брать m=n-1?

Переобучение – 2 Переобученный поиск хорошо ищет только по тестовому набору данных. Нужно ли идти в оптимизации параметров до конца? И где остановиться?

Переобучение – 3 Первое правило недопереобучения: брать несмещенный набор данных. Training set – набор данных для обучения Test set – набор данных для проверки качества

Early stopping У нас есть training set T, размеченный асессорами на соответствие набору запросов Q. Разобьем T на T и validation set V. Обучаемся на T. На каждой итерации проверяем качество на V. Останавливаемся, когда качество перестало улучшаться не на T, а на V. Как будет дальше изменяться качество на T? А на V?

Cross-validation У нас есть training set T, размеченный асессорами на соответствие набору запросов Q. Разобьем T на T1…Tk. Обучаемся на всех, кроме T1. Проверяем качество на T1. Обучаемся на всех, кроме T2. Проверяем качество на T2… По окончании получаем k решений. Что с ними делаем? Чем этот метод лучше early stopping? А чем хуже?

Регуляризация Штраф за сложность модели. Обычно это большие значения параметров.

Семплинг данных, обучение на семпле. Многократный семплинг, потом – агрегация. Bagging

Задача бинарной классификации Начальные веса Есть набор слабых алгоритмов Выберем из них тот, который классифицирует лучше всех. Здесь ошибка Boosting, AdaBoost

Теперь увеличим веса тем объектам, на которых первый больше ошибался. И рассчитаем α – вес классификатора, зависящий от выданной им ошибки. Теперь повторим выбор наилучшего классификатора, уже с новыми весами. Получим последовательность классификаторов с весами. Построим из них итоговый: Boosting, AdaBoost – 2

Словарь в большом массиве текстов неограниченно велик. Закон Хиппса: Выбор слов: частые стоп-слова, редкий мусор. Выбор по Information Gain – все равно остаются тысячи слов. A – term-document martix. Нужно ее приближение ранга k. SVD: U,V – ортонормированы. - диагональна. LSI