Интуиция, стоящая за наиболее распространенными методами поиска на основе терминов, такими как BM25, TF-IDF, модель правдоподобия запроса.
1. Что такое поиск информации?
Значение термина информационного поиска (IR) может быть очень широким. Например, достать свой идентификатор из кармана, чтобы вы могли напечатать его в документе, — это простая форма поиска информации. Хотя существует несколько определений IR, многие согласны с тем, что IR — это технология, позволяющая людям получать информацию. Сюда входят поисковые системы, рекомендательные системы, диалоговые системы и т. д. С академической точки зрения поиск информацииможет быть определен как:
Информационно-поисковый поиск (ИП) — это поиск материалов (обычно документов) неструктурированного характера (обычно текстовых), которые удовлетворяют потребность в информации, из больших коллекций (обычно хранящихся на компьютерах).
Мэннинг и др., «Введение в поиск информации».
2. Методы поиска на основе терминов
Методы поиска на основе терминов представляют собой математические основы для определения соответствия запроса и документа на основе точного синтаксического соответствия между документом и запросом для оценки релевантности документов заданному поисковому запросу. Идея состоит в том, что пара документа и поискового запроса представлена содержащимися в них терминами. В этой статье объясняется интуиция, стоящая за наиболее распространенными методами поиска на основе терминов, такими как BM25, TF-IDF, модель правдоподобия запроса.
Получите ответы 💬 на основе GPT на любой вопрос по науке о данных или программированию. Создавайте сводки и учебные заметки для тысяч 📚 учебных ресурсов всего одним щелчком мыши. 👉
2.1. TF-IDF
TF-IDF занимается поиском информации на основе модели Bag of Words (BOW), которая, вероятно, является самой простой моделью IR. TF-IDF состоит из двух частей: TF (частота терминов) и IDF (обратная частота документа).
TF – Частота термина
Частота термина, как следует из названия, — это частота термина t в документе d. Идея состоит в том, что мы присваиваем вес каждому термину в документе в зависимости от количества вхождений этого термина в документе. Таким образом, оценка документа равна частоте термина, которая предназначена для отражения того, насколько важно слово для документа.
В литературе мы находим две часто используемые формулы для частоты терминов: необработанная частота терминов, которая подсчитывает, как часто термин t появляется в документе d, и log частота терминов, заданная по приведенной ниже формуле. Лог имеет демпфирующий эффект при больших значениях частот терминов. Если мы посмотрим на приведенную выше таблицу на наличие термина «Антоний», то увидим, что он встречается в два раза чаще в Антонии и Клеопатре, чем в Юлии Цезаре. Исходя из частоты необработанных терминов, это будет означать, что Антоний и Клеопатра в два раза релевантнее, чем Юлий Цезарь.
IDF – обратная частота документа
Частота терминов страдает от критической проблемы: все термины считаются одинаково важными, когда дело доходит до оценки релевантности документа по запросу, хотя это не всегда так. На самом деле, некоторые термины имеют мало или вообще не имеют различительной способности при определении релевантности (например, «the» может встречаться в одном документе много раз, но не вносить никакого вклада в релевантность). С этой целью мы вводим механизм для снижения влияния терминов, которые слишком часто встречаются в коллекции, чтобы иметь смысл для определения релевантности. Чтобы определить только важные термины, мы можем указать частоту документов (DF) этого термина, которая представляет собой количество документов, в которых термин встречается. Это что-то говорит об уникальности терминов в сборнике. Чем меньше DF, тем больше уникальность заданных терминов.
Значит, нам лучше. А в чем проблема с ДФ? Один только DF, к сожалению, ничего нам не говорит. Например, если DF термина «компьютер» равен 100, это редкий или распространенный термин? Мы просто не знаем. Вот почему DF необходимо помещать в контекст, который соответствует размеру корпуса/коллекции. Если корпус содержит 100 документов, то термин встречается очень часто, если он содержит 1 млн документов, то термин встречается редко. Итак, давайте добавим размер корпуса, называемый N, и разделим, чтобы документировать частоту термина.
Звучит хорошо, верно? Но допустим, что размер корпуса равен 1000, а количество документов, содержащих термин, равно 1, тогда N/DF будет равно 1000. Если количество документов, содержащих термин, равно 2, то N/DF будет равно 500. Очевидно, небольшое изменение в DF может иметь очень большое влияние на N/DF и показатель IDF. Важно иметь в виду, что нас в основном волнует, когда DF находится в низком диапазоне по сравнению с размером корпуса. Это связано с тем, что если DF очень большой, термин используется во всех документах и, вероятно, не очень актуален для конкретной темы. В этом случае мы хотим сгладить изменение N/DF, и один из простых способов сделать это — взять логарифм N/DF. Кроме того, применение журнала может помочь сбалансировать влияние как TF, так и N/DF на окончательный результат. Таким образом, если термин появляется во всех документах коллекции, DF будет равен N. Log(N/DF) = log1 = 0, что означает, что термин не имеет никакой силы в определении релевантности.
Вместе мы можем определить оценку TF-IDF следующим образом:
2.2 BM25
BM25 — это вероятностная структура поиска, которая расширяет идею TF-IDF и устраняет некоторые недостатки TF-IDF, связанные с насыщением терминов и длиной документа. Полная формула BM25 выглядит немного пугающе, но вы могли заметить, что IDF является частью формулы BM25. Давайте разобьем оставшуюся часть на более мелкие компоненты, чтобы понять, почему это имеет смысл.
Насыщение сроков и убывающая отдача
Если в документе 100 употреблений термина "компьютер", действительно ли он вдвое более релевантен, чем документ, содержащий 50 употреблений? Мы могли бы утверждать, что если термин «компьютер» встречается достаточно много раз, документ почти наверняка релевантен, и любые другие упоминания не увеличивают вероятность релевантности. Итак, мы хотим контролировать вклад TF, когда срок, вероятно, будет насыщен. BM25 решает эту проблему, вводя параметр k1, который управляет формой этой кривой насыщения. Это позволяет нам экспериментировать с различными значениями k1 и смотреть, какое значение работает лучше всего.
Вместо использования TF мы будем использовать следующее: (k1+1)* TF / (TF + k1)
Итак, что это делает для нас? Он говорит, что если k1 = 0, то (k1+1)*TF/TF+ k1 = 1. В этом случае BM25 теперь оказывается IDF. Если k стремится к бесконечности, BM25 будет таким же, как TF-IDF. Параметр k1 можно настроить таким образом, что если при увеличении TF в какой-то момент показатель BM25 достигнет насыщения, как показано на рисунке ниже, это означает, что увеличение TF больше не влияет на результат.
Нормализация длины документа
Еще одна проблема, которая не учитывается в TF-IDF, — это длина документа. Если документ очень короткий и однажды содержит слово «компьютер», это уже может быть хорошим индикатором релевантности. Но если документ действительно длинный и термин «компьютер» встречается только один раз, вполне вероятно, что документ не о компьютерах. Мы хотим дать вознаграждение за совпадение терминов с короткими документами и оштрафовать за длинные. Тем не менее, вы не хотите чрезмерно наказывать, потому что иногда документ длинный, потому что он содержит много релевантной информации, а не просто много слов. Итак, как мы можем этого добиться? Введем еще один параметр b, который используется для построения нормализатора: (1-b) +b*dl/dlavg в формуле BM25. Чтобы он работал, значение параметра b должно быть между 0 и 1. Теперь оценка BM25 будет следующей:
Во-первых, давайте разберемся, что означает, что документ может быть коротким или длинным. Опять же, документ считается длинным или коротким в зависимости от контекста корпуса. Один из способов принять решение — использовать среднюю длину корпуса в качестве точки отсчета. Длинный документ — это просто документ, который длиннее средней длины корпуса, а короткий короче средней длины корпуса. Что этот нормализатор делает для нас? Как видно из формулы, когда b равно 1, нормализатор превратится в (1–1 + 1*dl/dlavg). С другой стороны, если b равно 0, все становится равным 1, и влияние длины документа вообще не учитывается.
Когда длина документа (dl) больше средней длины документа, этот документ получает штраф и получает более низкую оценку. Параметр b определяет, насколько сильными будут штрафы для этих документов: чем выше значение b, тем выше штраф для больших документов, потому что влияние длины документа по сравнению со средней длиной корпуса сильнее. С другой стороны, документы размером меньше среднего вознаграждаются и дают более высокий балл.
Таким образом, TF-IDF вознаграждает за частоту терминов и наказывает за частоту документов. BM25 выходит за рамки этого, чтобы учитывать длину документа и частоту встречаемости терминов.
2.3. Языковые модели
Одна из центральных идей языкового моделирования заключается в том, что когда пользователь пытается создать хороший поисковый запрос, он или она выдает термины, которые, вероятно, появятся в соответствующем документе. Другими словами, релевантный документ — это документ, который может содержать термины запроса. Что отличает языковое моделирование от других вероятностных моделей, так это то, что оно создает языковую модель для каждого документа, из которого генерируются вероятности, соответствующие вероятности того, что запрос может быть найден. в этом документе. Эта вероятность определяется как P(q|M_d).
Определение языковой модели — это функция, которая вычисляет вероятности для слова или набора слов (например, (части) предложения) с учетом словарного запаса. Давайте рассмотрим пример модели, которая производит вероятности для отдельных слов:
Вероятность предложения "кошка любит рыбу" составляет 0,3 x 0,2 x 0,2 = 0,012, а вероятность предложения "собака любит кошку" – 0,1 x 0,2 x 0,3 = 0,006. Это означает, что термин «кошка любит рыбу» чаще встречается в документе, чем «собака любит кошку». Если мы хотим сравнить разные документы с одним и тем же поисковым запросом, мы производим вероятность для каждого документа отдельно. Помните, что каждый документ имеет свою языковую модель с разными вероятностями.
Другой способ интерпретировать эти вероятности — спросить, насколько вероятно, что эта модель генерирует предложение «кошка любит рыбу» или «собака любит кошку». С технической точки зрения вы также должны включить вероятности того, насколько вероятно, что предложение продолжится или остановится после каждого слова. Эти предложения не обязательно должны существовать в документе и не должны иметь смысла. В этой языковой модели, например, предложения «кошка любит рыбу» и «сом-рыба-рыба» имеют одинаковую вероятность, другими словами, они с одинаковой вероятностью будут генерироваться.
Языковая модель из приведенного выше примера называется моделью языка униграмм. Это модель, которая оценивает каждый термин независимо и игнорирует контекст. Одной из языковых моделей, которая включает контекст, является модель языка биграмм. Эта модель включает условные вероятности для терминов при условии, что им предшествует другой термин. Вероятность того, что «кошка любит рыбу», будет равна P(кошка) x P(лайки|кошка) x P(рыба|лайки). Это, конечно, требует существования всех условных вероятностей.
Существуют более сложные модели, но они реже используются. Каждый документ создает новую языковую модель, но обучающих данных в одном документе часто недостаточно для точного обучения более сложной модели. Это напоминает компромисс между смещением и дисперсией. Сложные модели имеют высокую дисперсию и склонны к переобучению на небольших обучающих данных.
Сопоставление с использованием модели вероятности запроса
При ранжировании документов по степени их релевантности запросу нас интересует условная вероятность P(d|q). В модели вероятности запроса эта вероятность так называемого рангового эквивалента P(q|d), поэтому нам нужно использовать только вероятности, описанные выше. Чтобы понять, почему они эквивалентны по рангу, обратимся к правилу Байеса:
P(d|q) = P(q|d) P(d) / P(q)
Поскольку P(q) имеет одинаковое значение для каждого документа, это никак не повлияет на ранжирование. P(d), с другой стороны, рассматривается как однородный для простоты и поэтому также не влияет на ранжирование (например, в более сложных моделях P(d) можно сделать зависимым от длины документа). Итак, вероятность P(d|q) эквивалентна P(q|d). Другими словами, в модели вероятности запроса следующие два эквивалентны по рангу:
- Вероятность того, что документ d соответствует запросу q.
- Вероятность того, что запрос q сгенерирован языком документа d.
Когда пользователь создает запрос, у него уже есть представление о том, как может выглядеть соответствующий документ. Термины, используемые в запросе, с большей вероятностью появятся в релевантных документах, чем в нерелевантных документах. Одним из способов оценки вероятности P(q|d) для модели униграмм является использование оценки максимального правдоподобия:
где tf_t,d — частота термина t в документе d, а L_d — размер документа d. Другими словами, подсчитайте долю частоты появления каждого слова запроса в документе d по сравнению со всеми словами в этом документе, а затем перемножьте все эти доли друг с другом.
Есть две небольшие проблемы с приведенной выше формулой. Во-первых, если одно из условий запроса не встречается в документе, вся вероятность P(q|d) будет равна нулю. Другими словами, единственный способ получить ненулевую вероятность — это если каждый термин в запросе появляется в документе. Вторая проблема заключается в том, что вероятность терминов, встречающихся в документе реже, может быть завышена.
Методы сглаживания
Решение упомянутых выше проблем заключается во внедрении методов сглаживания, которые помогают путем создания ненулевых вероятностей для терминов, не фигурирующих в документе, и путем создания эффективных весов для частых терминов. Существуют различные методы сглаживания, такие как сглаживание Елинека-Мерсера, в котором используется линейная комбинация оценок максимального правдоподобия для конкретного документа и коллекции:
Или сглаживание Дирихле:
Но это тема для другого поста в блоге.
Таким образом, традиционные методы поиска на основе терминов просты в реализации, а такой метод, как BM25, является одной из наиболее широко используемых функций поиска информации благодаря неизменно высокой точности поиска. Однако они решают проблему, основанную на представлении Bag-of-Words (BoW), поэтому они сосредоточены только на точном синтаксическом сопоставлении и, следовательно, не учитывают семантически связанные слова.
