Статистические языковые модели в информационном поиске Никита Спирин, PhD candidate University of Illinois at Urbana-Champaign, Department of Computer Science Московский Физико-Технический Институт, Факультет Управления и Прикладной Математики Skype: spirinus

Что есть информационный поиск (IR)? information retrieval is a field concerned with the structure, analysis, organization, storage, searching, and retrieval of information [Salton,68] –Information в большинстве случаев есть текст, но может быть и изображением, видео. –Retrieval в основном есть поиск по запросу, но может быть и классификация, фильтрация, резюмирование,..

Зачем поиск? Twitter генерирует сообщений в день фотографий в месяц загружается на Facebook. Более профессиональных фотографий загружается в год на Flickr. Размер индекса Google (нижняя оценка на размер Интернета) в 2008 году достиг страниц.

Ключевые компоненты поисковой системы? Интернет Краулер Поисковый Индекс Ранжирующая функция

План доклада Базовые понятия – Обзор моделей ранжирования – Введение в статистические языковые модели Базовая модель ранжирования на основе статистических языковых моделей Продвинутые модели ранжирования на основе статистических языковых моделей Модель ранжирования на основе вероятностного расстояния статистических языковых моделей Заключение

План доклада Базовые понятия – Обзор моделей ранжирования – Введение в статистические языковые модели Базовая модель ранжирования на основе статистических языковых моделей Продвинутые модели ранжирования на основе статистических языковых моделей Модель ранжирования на основе вероятностного расстояния статистических языковых моделей Заключение

Обзор моделей ранжирования 1950 – 1960: зарождение данного научного направления –Гипотеза об автоматической индексируемости коллекций (Luhn) –Первые эксперименты и выработка принципов оценки работы поисковых систем (Cleverdons Cranfield 1 и Cranfield 2) –Ранние эксперименты по разработке векторной модели ранжирования (Saltons прототип-система SMART) 1970 – 1980: бурное развитие информационного поиска –Становление векторной модели ранжирования –Модели ранжирования на основе вероятностного подхода (PRP) 1990: дальнейшее развитие информационного поиска (новые приложения и теоретизирование подходов и моделей) –Статистические языковые модели –Разработка коллекций для объективного сравнения поисковых систем : Веб поиск, масштабируемость поисковых систем, антиспам –Машинное обучение ранжированию –MapReduce, Hadoop, GFS, …

Постановка задачи ранжирования Дано: –Словарь для данного языка ; –Множество запросов обучения, где каждое слово из запроса содержится в словаре; –Коллекция документов, где каждый документ есть упорядоченное множество слов из словаря; –Для обучающего множества пар запрос/документ задана оценка релевантности Найти: –Для нового запроса множество релевантных документов (возможно упорядоченное) из коллекции.

Вычисление релевантности: упорядоченное множество или нет? Стратегия 1 (фильтрация документов) –R(q) = { d C | f(d,q)=1 }, где f(d,q) {0,1} есть классификатор, индикаторная функция –Алгоритм должен предсказать абсолютную оценку о релевантности документа запросу. Стратегия 2 (ранжирование документов) –R(q) = { d C | f(d,q)> }, где f(d,q) есть ранжирующая функция; порог фильтрации –Алгоритм должен предсказать относительную релевантность документов и подобрать оптимальный порог фильтрации.

Классификация f(d,q)=? Ранжирование f(d,q)=? d d d d d d d d d 9 - R(q) Реальная релевантность R(q) Вычисление релевантности: упорядоченное множество или нет?

Стратегия 1 (фильтрация документов) –R(q) = { d C | f(d,q)=1 }, где f(d,q) {0,1} есть классификатор, индикаторная функция –Алгоритм должен предсказать абсолютную оценку о релевантности документа запросу. Стратегия 2 (ранжирование документов) –R(q) = { d C | f(d,q)> }, где f(d,q) есть ранжирующая функция; порог фильтрации –Алгоритм должен предсказать относительную релевантность документов и подобрать оптимальный порог фильтрации.

Модели на основе текстовой близости (1) Принцип: – Релевантность документа запросу коррелирует с текстовой близостью запроса и документа Векторная модель ранжирования (VSM) – Документ и запрос представляются, как векторы в пространстве терминов ( компонент); – Каждому термину присвоен вес, характеризующий его информативность, уникальность; – Релевантность оценивается как некоторая мера близости векторов;

Модели на основе текстовой близости – формально (2) Документ есть ; Запрос есть ; Вес термина определяется на основе TFIDF, которая учитывает – Частоту слова в документе TF; – Встречаемость слова в коллекции IDF; – Длину документа; Близость определяется на основе нормированного скалярного произведения (косинусная мера).

Модели на основе текстовой близости (3) Преимущества векторной модели ранжирования (VSM): – Дает наилучшие результаты по сравнению с другими классическими моделями; – Очень проста и понятна в реализации; – Существует множество кейсов применения, коллекций и benchmarkов для сравнения и экспериментов; Недостатки: – Основана на эвристиках, допускает независимость терминов в запросе и документе; – Сложно расширяема для добавления предметного знания; – Требует тщательной настройки параметров экспертом; – Не объясняет как представлять документы и запросы.

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

Выпишем функцию распределения финального ответа для нового прецедента Определим функцию потерь при и при, а также байесовский риск, тогда Вероятностный Принцип Ранжирования, PRP (2)

Модели на основе вероятностных соображений (1) Принцип: – Какова вероятность того, что данный документ релевантен данному запросу? Вероятностная модель ранжирования (PRM): – Рассматриваются три случайные величины (запрос, документ, релевантность R {0,1}); – Цель: упорядочить документы коллекции по убыванию вероятности соответствия документов запросу, P(R=1|Q,D); – Возможны различные способы оценки вероятности в формуле P(R=1|Q,D).

Модели на основе вероятностных соображений (2) Дискриминативный подход (оценить вероятность напрямую, построить отображение): – Определить признаки на парах Q x D, например, # совпавших слов, длина документа, величина IDF самого популярного слова на странице, предсказания базовых ранжирующих функций baseR(Q,D),… – Используя обучающее множество (запросы, документы, и известные оценки релевантности на парах), оценить параметры модели ранжирования – Для нового документа породить признаки и применить обученную модель

Генеративный подход (факторизация вероятности в произведение случайных величин, оценка релевантности не напрямую) –Вычислить O(R=1|Q,D) по правилу Байеса –Определить порождающую модель P(Q,D|R) Возможные случаи –Генерация документов: P(Q,D|R)=P(D|Q,R)P(Q|R) –Генерация запросов: P(Q,D|R)=P(Q|D,R)P(D|R) Не влияет на ранжирование Модели на основе вероятностных соображений (3)

Модель релевантных документов для Q Модель нерелевантных документов для Q Допустим независимость величин A 1 … A k Пусть D=d 1 …d k, где d k {0,1} есть значение величины A k (тоже самое для Q=q 1 …q m ) Модели на основе вероятностных соображений – генерация документа

Необходимо оценить по 2 параметра для каждого термина A i : p i = P(A i =1|Q,R=1): вероятность, что A i ассоциирован с релевантным классом документов; q i = P(A i =1|Q,R=0): вероятность, что A i ассоциирован с нерелевантным классом документов. (RSJ модель) Как оценить данные параметры? Модели на основе вероятностных соображений – генерация документа

Модели на основе вероятностных соображений – генерация запроса При допущении о равномерной априорной вероятности получим Вероятность запроса p(q| d ) Априорная релевантность документа Следовательно, вопрос заключается в том как оценить вероятность запроса по документу? Процесс состоит из 2 ключевых стадий: оценить лингвистическую модель для каждого документа D вычислить релевантности документов запросу на основе этих моделей.

Другие модели ранжирования Подход на основе графических моделей – Принцип: вывести по-байесовски, что запрос релевантен документу Подход на основе генетических алгоритмов и символьной регрессии – Принцип: порождение моделей и отбор наиболее перспективных Подход на основе оптимизации эмпирического риска Эвристический подход на основе структурных свойств функции ранжирования

План доклада Базовые понятия – Обзор моделей ранжирования – Введение в статистические языковые модели Базовая модель ранжирования на основе статистических языковых моделей Продвинутые модели ранжирования на основе статистических языковых моделей Модель ранжирования на основе вероятностного расстояния статистических языковых моделей Заключение

Статистические языковые модели - SLM (определение) Вероятностное распределение на множестве словарных последовательностей: – p(Мама мыла раму) 0.001; – p(Рама мыла маму) ; – p(Матрица Грамма в унитарном пространстве эрмитова) Может быть использована для порождения текста, если рассматривать как случайный процесс семплирования слов из данного вероятностного распределения. Поэтому также можно встретить термин генеративная модель языка. Зависит от коллекции, тематики, типа модели.

Статистические языковые модели (примеры применения) Позволяет вероятностно описывать естественный язык в рамках теоретически обоснованной гибкой модели. С помощью SLM можно отвечать на вопросы: – Для словосочетания Мама мыла, какова вероятность того, что следующим словом будет раму? А машину? А танк? (распознавание речи) – Если слово Евро встретилось 1 раз и футбол 4 раза в статье, какова вероятность, что данная статья про спорт по сравнению с финансами? (информационный поиск, категоризация текста) – Если пользователь любит футбол, какова вероятность того, что он употребит слово гол в запросе?(информационный поиск на основе SLM)

Текст генерируется последовательно посредством выбора с возвращением так, что слова в последовательности независимы. То есть p(w 1 w 2... w n )=p(w 1 )p(w 2 )…p(w n ). Параметры модели: {p(w i )} таковы, что p(w 1 )+…+p(w N )=1, где (N размер словаря V) Формально, ULM есть мультиномиальное распределение на множестве слов. Простейшая статистическая языковая модель – Unigram Language Model (ULM)

Text Generation with Unigram LM ULM с вектором параметров p(w| ) … вектор 0.1 базис 0.05 матрица 0.1 след 0.02 … мяч … Тема 1: Математика … базис игра 0.25 мяч 0.1 тренировка 0.2 … Тема 2: Спорт Документ d Учебник по аналитической геометрии Новость по футболу Простейшая статистическая языковая модель – Unigram Language Model (ULM) Семплирование с возвращением

ULM с вектором параметров p(w| ) Документ d Простейшая статистическая языковая модель – Unigram Language Model (ULM) Подсчет встречаемости, обучение … базис 1 игра 50 мяч 20 тренировка 10 гонка 0 … футбол 100 … Всего # слов = / / / / /1000 … базис игра 0.05 мяч 0.02 тренировка 0.01 … футбол 0.1 Как оценить качество модели? Является ли данная модель хорошей? Модель восстановленная по данному документу присваивает наибольшую вероятность данному документу, но обобщающая способность такой модели низкая => сглаживание (рассмотрим далее)

Evaluation of SLMs Прямая оценка качества: Как хорошо модель предсказывает данные, по которым она была обучена? – Примеры: правдоподобие, perplexity, кросс энтропия, KL-divergence (в общем и в целом все эквивалентны) Косвенная оценка качества: Способствует ли данная модель повышению качества конечной задачи (перевод, поиск,..)? – Конкретная метрика проблемно-зависимая – В случае IR мы смотрим на то, как данная модель повышает качество поиска, что в свою очередь оценивается эвристическими метриками типа (DCG, MRR, MAP,..) – Предпосылка данного подхода: более качественная лингвистическая модель приводит к повышению качества решения конечной задачи, но не факт! Оценка статистических языковых моделей

N-gram модель – Имеет вид, p(w 1 w 2... w n )=p(w 1 )p(w 2 |w 1 )…p(w n |w 1 …w n-1 ); – n-gram означает, что модель генерации зависит от предыдущих n-1 слов; – Например, модель на основе биграмм имеет вид p(w 1... w n )=p(w 1 )p(w 2 |w 1 ) p(w 3 |w 2 ) …p(w n |w n-1 ). Модели, учитывающие удаленные взаимодействия терминов (Maximum Entropy Language Model, etc.). Структурные языковые модели (probabilistic context- free grammar, PCFG). В случае информационного поиска используются в большинстве случаев только Unigram Language Model. Более сложные статистические языковые модели

Почему используются только языковые модели нулевого порядка (ULM)? Сложность перехода к более мощным языковым моделям: – Требуется настраивать больше параметров => требуется больше данных для качественной настройки (Модель, восстановленная по 100 документам, ужасна). – Приводят к значительным вычислительным проблемам по времени отклика при запросе и по затратам на хранение. Учет структуры текста/предложений не нужен/малоэффективен для выявления тематической релевантности. Однако, используется активно в IE. Но применение более сложных моделей может и должно привести в общем случае к повышению качества конечных приложений, в частности поиска!

План доклада Базовые понятия – Обзор моделей ранжирования – Введение в статистические языковые модели Базовая модель ранжирования на основе статистических языковых моделей Продвинутые модели ранжирования на основе статистических языковых моделей Модель ранжирования на основе вероятностного расстояния статистических языковых моделей Заключение

Документ Статья по Байесовским сетям Статья-обзор о чемпионате Европы 2012 Лингвистическая модель … text ? mining ? inference ? Bayes ? … спорт ? … сегодня? матч ? продуктивно ? гол ? … Запрос Q = машинное обучение ? Какая модель наиболее вероятно породила данный запрос? Базовая модель ранжирования с использованием ULM, правдоподобие запроса (1)

d1d1 d2d2 dNdN q d 1 d 2 d N LMs документов p(q| d 1 ) p(q| d 2 ) p(q| d N ) Правдоподобие запроса Базовая модель ранжирования с использованием ULM, правдоподобие запроса (2) … 2 ключевых вопроса: Какую вероятностную модель следует использовать? Как эффективно вычислить d i ?

Multi-Bernoulli: моделирует наличие/отсутствие слов – q= (x 1, …, x |V| ), x i =1 если слово w i есть в документе; x i =0 если нет; – Параметры: { p(w i =1|d), p(w i =0|d)}, так что p(w i =1|d)+ p(w i =0|d) = 1. Мультиномиальное (ULM): моделирует частоту слов – Q = q 1,…q m, где q j есть слово из запроса – c(w i,q) есть частота слова w i в запросе Q – Parameters: {p(w i |d)} таковы, что p(w 1 |d)+… p(w |v| |d) = 1. Большинство работ используют мультиномиальное распределение, что показывает наилучшие результаты согласно вычислительным экспериментам. Различные языковые модели генерации текста

Ключевой принцип/задача в SLM-IR Задача поиска => Задача оценки лингвистической модели документа p(w i |d) В лингвистических моделях сглаживание играет ключевую роль, что в свою очередь является ключевым фактором в различии соответствующих ранжирующих функций.

Все методы сглаживания основаны на идее: – Дисконтировать вероятность слов, существующих в документе; – Перераспределить отобранную вероятность среди слов, несуществующих в документе. Лапласовское сглаживание (additive smoothing) предлагает прибавлять единицу к частоте каждого слова и нормализовывать. Лапласов фактор Размер словаря Частота w в d Длина документа d (общее число слов) Методы сглаживания

P(w) Word w Оценка по ММП Сглаженная LM Иллюстрация идеи сглаживания LM

Правильно ли рассматривать все слова одинаково? – Нет. Мы можем использовать языковую модель, построенную на основе коллекции для персонифицированной обработки слов. Дисконтированная ММП оценка Языковая модель коллекции Развитие идеи: Сглаживание на основе коллекции документов (Jelinek-Mercer)

Развитие идеи: Сглаживание на основе коллекции документов c априорным распределением (Dirichlet) Формально распределение Дирихле есть Примечательным свойством распределения Дирихле является его связь с мультиномиальным: А следовательно,, где. согласно Байесовскому выводу, имеем:

Сравнение простых моделей ранжирования на основе статистических языковых моделей

Дисконтированная оценка ММП ULM коллекции Принцип ранжирования со сглаживанием в общей форме Общая формула сглаживания Почему сглаживание особенно важно в случае информационного поиска?

Не важно для ранжирования IDF-дисконтирование TF вес Нормализация длины документа (длинные документы дисконтируются меньше) Сглаживание коллекцией p(w|C) есть TFIDF + норм. длины, а следовательно сглаживание есть реализация классических эвристик информационного поиска. SLM-IR с простым сглаживанием может быть также эффективно вычислена, как и классические модели ранжирования. Суммирование по словам из запроса и документа Сравнение с классическими эвристиками информационного поиска

Стадия 1 Сглаживание пропущенных слов по-байесовски Стадия 2 Моделирование шума в запросе Двустадийное сглаживание (Dirichlet + Jelinek-Mercer) LM коллекции Языковая модель пользователя (аппроксимация по коллекции p(w|C))

План доклада Базовые понятия – Обзор моделей ранжирования – Введение в статистические языковые модели Базовая модель ранжирования на основе статистических языковых моделей Продвинутые модели ранжирования на основе статистических языковых моделей Модель ранжирования на основе вероятностного расстояния статистических языковых моделей Заключение

Перечень продвинутых моделей ранжирования на основе SLM Языковые модели, учитывающие интеракции терминов и структуру запросов (n-gram, PCFG) Кластерное сглаживание (cosine, LDA, PLSI) Транслитерационная модель (семантическое сглаживание, кросс-языковое сглаживание) Модель на основе полного Байесовского вывода Модель, моделирующая шум в запросе на основе смеси распределений (определение информативных и неинформативных терминов в запросе)

Перечень продвинутых моделей ранжирования на основе SLM Языковые модели, учитывающие интеракции терминов и структуру запросов (n-gram, PCFG) Кластерное сглаживание (cosine, LDA, PLSI) Транслитерационная модель (семантическое сглаживание, кросс-языковое сглаживание) Модель на основе полного Байесовского вывода Модель, моделирующая шум в запросе на основе смеси распределений (определение информативных и неинформативных терминов в запросе)

Языковые модели с длинным горизонтом Учитывают последовательные интеракции терминов в запросе: Учитывают структуру запроса и документа: Данные модели не приводят к значительному повышению качества поиска, так как: – Требуется настройка колоссального числа параметров; – Эффект от моделирования последовательности слов в запросе не значителен и учитывается косвенно в ULM.

Кластерное сглаживание (1) Идея: – Кластеризовать документы и сгладить языковую модель документа на основе языковой модели соответствующего кластера документов. Согласно экспериментам данный подход не приводит к значимому увеличению качества. Причина: жесткая кластеризация и неудачная настройка параметров приводят к тому, что модель дисконтирует ключевые слова из данного кластера.

Кластерное сглаживание - Dirichlet (2) Предпосылка: – Коллекция документов состоит из k тем. – Каждый кластер представляется как нечеткое распределение на множестве тем. По результатам экспериментов данный подход явно показывает положительный эффект от кластерного сглаживания. Однако, данный подход не используется на практике для больших коллекций из-за трудоемкости построения LDA для больших коллекций.

Кластерное сглаживание – центрирование на документах (3) Что делать если документ находится на границе кластеров? Осуществляем сглаживание на основе соседей.

Мотивация: – Все рассмотренные модели осуществляют поиск на основе слов непосредственно указанных в запросе. Теряем ли мы часть важных документов при этом? – Да. Транслитерационная модель учитывает семантические связи между словами в запросе и документах Позволяет увеличить качество поиска значительно (полнота), но в свою очередь возникают новые вопросы, связанные с обучением транслитерационной модели и эффективностью исполнения запросов. Транслитерационная модель Обычная LM Транслитерационная языковая модель ранжирования

План доклада Базовые понятия – Обзор моделей ранжирования – Введение в статистические языковые модели Базовая модель ранжирования на основе статистических языковых моделей Продвинутые модели ранжирования на основе статистических языковых моделей Модель ранжирования на основе вероятностного расстояния статистических языковых моделей Заключение

Мотивация: – Модели ранжирования на основе близости документов и вероятностных методов генерации документов легко позволяют учитывать обратную связь по предпочтениям пользователей. – Модели на основе правдоподобия запроса (на основе статистических языковых моделей) не позволяют легко учитывать данную информацию. Подход: – Аналогично векторной модели ранжирования мы представим документ и запрос в одном пространстве (теперь вероятностном) и определим меру близости для оценки релевантности. Модель ранжирования на основе вероятностного расстояния статистических языковых моделей

Обратная связь в классической векторной модели ранжирования Исходный запрос + q q Нерелевантные документы Новый запрос Релевантные документы

Генерация документов: Правдоподобие запроса (языковая модель): Релевантные док. Нерелевантные док. Модель релевантных запросов P(D|Q,R=1) P(D|Q,R=0) P(Q|D,R=1) (q 1,d 1,1) (q 1,d 2,1) (q 1,d 3,1) (q 1,d 4,0) (q 1,d 5,0) (q 3,d 1,1) (q 4,d 1,1) (q 5,d 1,1) (q 6,d 2,1) (q 6,d 3,0) Прямой запрос: - P(Q|D,R=1) языковая модель достигает лучшего качества. Обратная связь: - P(D|Q,R=1) улучшаема для данного запроса и новых документов - P(Q|D,R=1) улучшаема, но для новых запросов и данного документа. Обратная связь в моделях на основе вероятностного принципа ранжирования

Компоненты: – Модель представления: статистическая языковая модель; – Функция близости: KL-расстояние. Модель ранжирования на основе вероятностного расстояния статистических языковых моделей Не важно для ранжирования

ММП оценка языковой модели запроса имеет вид: Выпишем формулу ранжирования документов на основе KL-расстояния: Связь с базовой моделью на основе правдоподобия запроса

Запрос Q Документ D Поисковая выдача Обратная связь F={d 1, d 2, …, d n } Алгоритм разделения смеси Модель обратной связи Модель учета обратной связи

План доклада Базовые понятия – Обзор моделей ранжирования – Введение в статистические языковые модели Базовая модель ранжирования на основе статистических языковых моделей Продвинутые модели ранжирования на основе статистических языковых моделей Модель ранжирования на основе вероятностного расстояния статистических языковых моделей Заключение

Преимущества: – Теоретическое обоснование (понятная настройка параметров, обоснованные вероятностные предположения, обобщает существующие подходы). – Расширяема для специальных задач (тематики, поиск отзывов..). – Масса исследований в смежных областях (NLP, сигналы,..). – Достигает превосходного качества ранжирования и сравнима, либо доминирует классические модели ранжирования. – Позволяет учитывать обратную связь о релевантности документов. Недостатки: – Требует задание генеративного подхода (трудно оценить). – Вычислительно более дорогостоящая для достижения схожего качества ранжирования. Сравнение классических моделей ранжирования и на основе статистических языковых моделей

Теоретическое обоснование применения языковых моделей в поиске. Эмпирически модели данного семейства показывают превосходное качество в задаче ранжирования: – Базовая модель ранжирования с сглаживанием по Дирихле – Базовая модель ранжирования + предметные априорные оценки релевантности документов (URL, PageRank,..). – Транслитерационная модель учитывает семантические связи между словами одного и разных языков. – Модель с KL-расстоянием – наилучший способ учесть обратную связь о релевантности документов. – Продвинутые модели (смеси распределений, байесовский вывод) демонстрируют как можно расширять модель. Полностью автоматическая настройка параметров. Статистические языковые модели в информационном поиске – status quo

Спасибо за внимание! Никита Спирин, PhD candidate University of Illinois at Urbana-Champaign, Department of Computer Science Московский Физико-Технический Институт, Факультет Управления и Прикладной Математики Skype: spirinus