ИНФОРМАЦИОННЫЙ ПОИСК
Информационный поиск — это задача поиска документов, отвечающих потребностям пользователя в информации. Наиболее широко известными примерами систем информационного поиска являются поисковые машины World Wide Web. Пользователь Web может ввести в приглашении поисковой машины такой запрос, как [ AI book], и получить список подходящих страниц. В данном разделе показано, как создаются подобные системы. Для систем информационного поиска (называемых сокращенно системами ИП) применяются перечисленные ниже характеристики.
1. Определение коллекции документов. В каждой системе должно быть принято определенное решение о том, что рассматривается в ней как документ — отдельный абзац, страница или многостраничный текст.
2. Способ формулировки запроса на языке запросов. Запрос указывает, какая информация требуется пользователю*. Язык запросов может предусматривать лишь возможность составления списка слов, такого как [AI book], или может позволять задавать сочетание слов, которые должны быть расположены близко друг от друга, как в запросе [ "AI book" ]; он может содержать логические операторы, как в запросе [AI AND book]; а также включать операторы, отличные от логических, как в запросе [AI NEAR book] или [AI book SITEiwww.aaai.org].
3. Результирующий набор. Таковым является подмножество документов, которые система информационного поиска определяет как релевантные данному запросу. Под словом релевантный подразумевается вероятно полезный (согласно конкретным информационным потребностям, сформулированным в запросе) для того лица, которое сформулировало запрос.
4. Способ представления результирующего набора. Он может быть настолько простым, как ранжированный список названий документов, или настолько сложным, как вращающаяся цветная карта результирующего набора, спроектированная на трехмерное пространство.
После чтения предыдущей главы могло сложиться впечатление, что систему информационного поиска возможно создать, преобразовав с помощью синтаксического анализа коллекцию документов в базу знаний, состоящую из логических высказываний, после чего в ней будет выполняться синтаксический анализ каждого запроса и поиск ответа в базе знаний с помощью предиката Ask. Но, к сожалению, еще никому не удалось создать крупномасштабную систему информационного поиска таким образом. Дело в том, что составить словарь и грамматику, которые охватывают большую коллекцию документов, слишком сложно, поэтому во всех системах информационного поиска используются более простые языковые модели.
Самые ранние системы информационного поиска действовали на основе булевой модели ключевых слов. Каждое слово в коллекции документов рассматривалось как булева характеристика, которая является истинной применительно к данному документу, если соответствующее слово встречается в документе, и ложной в противном случае. Поэтому характеристика "поиск" является истинной для текущей главы, но ложной для главы 15. В таком случае язык запросов представляет собой язык булевых выражений, заданных на характеристиках. Документ считается релевантным, только если соответствующее выражение принимает истинное значение. Например, запрос [информация AND поиск] принимает истинное значение для текущей главы и ложное для главы 15.
Преимуществом такой модели является то, что ее несложно описать и реализовать. Но она имеет некоторые недостатки. Во-первых, степень релевантности документа измеряется одним битом, поэтому отсутствуют руководящие данные, на основании которых можно было бы упорядочить релевантные документы для презентации. Во-вторых, булевы выражения могут оказаться непривычными для пользователей, не являющихся программистами или логиками. В-третьих, задача формулировки подходящего запроса может оказаться сложной даже для квалифицированного пользователя. Предположим, что предпринимается попытка выполнить запрос [информация AND поиск AND модели AND оптимизация], что приводит к получению пустого результирующего набора. После этого осуществляется попытка выполнить запрос [информация OR поиск OR модели OR оптимизация], но если он возвращает слишком большой объем результатов, то нелегко определить, какую попытку следует предпринять после этого.
В большинстве систем информационного поиска используются модели, основанные на статистических сведениях о количестве слов (а иногда и другие характеристики низкого уровня). В этой главе будет описана вероятностная инфраструктура, которая хорошо согласуется с описанными ранее языковыми моделями. Основная идея состоит в том, что после формулировки некоторого запроса требуется найти документы, которые с наибольшей вероятностью будут релевантными по отношению к нему. Иными словами, необходимо вычислить следующее значение вероятности:
P(R=true\D, Q)
где D— документ; Q— запрос; R — булева случайная переменная, обозначающая релевантность. После получения этого значения можно применить принцип ранжирования вероятностей, который указывает, что если результирующий набор должен быть представлен в виде упорядоченного списка, это следует сделать в порядке уменьшения вероятности релевантности.
Существует несколько способов декомпозиции совместного распределения Р (R= true I D, Q). В настоящей главе будет описан подход, известный под названием языкового моделирования, в котором предусматривается получение оценки языковой модели для каждого документа, а затем вычисление для каждого запроса вероятности этого запроса с учетом языковой модели документа. Используя г для обозначения выражения R=true, можно перезаписать приведенное выше определение вероятности следующим образом:
P{r\D,Q) - P{D, Q\r)P(r)/P(D,Q) (согласно правилу Байеса)
= P{Q\D,r)P(D\r)P(r)/P(D,Q) (согласно цепному правилу)
= OLP{Q\D, r) P(r I D)/P(D, Q) (согласно правилу Байеса,
для фиксированного D)
Как уже было сказано, может быть предпринята попытка максимизировать значение P{r\D, Q), но равным образом можно максимизировать отношение вероятностей Р{г | D, Q) / P(-i г | D, Q). Это означает, что ранжирование документов может осуществляться на основе следующей оценки:
P{r\D, Q) _ P{Q\D,r) P(r\D) P(-ir\D,Q) " P(Ј|D,-nr) P(-nr|D)
Преимущество такого подхода состоит в том, что из процедуры вычисления устраняется терм P{D,Q). Теперь примем предположение, что в случае нерелевантных документов каждый документ является независимым по отношению к запросу. Иными словами, если какой-то документ нерелевантен по отношению к запросу, то получение информации о существовании этого документа не позволит определить, в чем состоит сам запрос. Это предположение может быть выражено с помощью такой формулы:
P(D,Q\-,r) = P(D|ir) P(Q\-ir)
На основании этого предположения получим следующее:
P{r\D,Q) P(r\D)
pbr|D,c) = PiQlD'r)x7I
Коэффициент P{r\D) /Р(-«г | D) измеряет независимую от запроса вероятность того, что документ является релевантным. Таким образом, этот коэффициент представляет собой меру качества документа; некоторые документы с большей вероятностью будут релевантными по отношению к любому запросу, поскольку сами эти документы имеют изначально высокое качество. Применительно к статьям для академических журналов качество можно оценить на основании количества упоминаний об этих статьях в других источниках, а для оценки Web-страниц можно использовать количество гиперссылок на ту или иную страницу. В каждом из этих случаев можно присвоить больший вес адресатам ссылок, характеризующимся высоким качеством. Одним из факторов оценки релевантности документа, независимой от запроса, может также служить продолжительность существования этого документа.
Первый коэффициент, P{Q\D,r), представляет собой вероятность запроса с учетом релевантного документа. Для оценки этой вероятности необходимо выбрать языковую модель, описывающую то, как связаны запросы с релевантными документами. Один из широко распространенных подходов состоит в том, что документы представляются с помощью модели однословных сочетаний. В проблематике информационного поиска она известна также под названием модели мультимножества слов, поскольку в ней учитывается только частота появления каждого слова в документе, а не их порядок. При использовании такой модели следующие (очень короткие) примеры документов рассматриваются как идентичные: "man bites dog" (человек кусает собаку) и "dog bites man" (собака кусает человека). Очевидно, что эти документы имеют разный смысл, но верно также то, что оба они являются релевантными по отношению к запросам о собаках и укусах. Теперь, чтобы рассчитать вероятность запроса при наличии релевантного документа, достаточно просто перемножить вероятности слов в запросе, руководствуясь моделью однословных сочетаний данного документа. В этом и состоит наивная байесовская модель данного запроса. Используя для обозначения j-ro слова в запросе, получим следующее:
Наконец, мы получили возможность применить эти математические модели к некоторому примеру. В табл. 23.1 приведены статистические данные по количеству однословных сочетаний применительно к словам в запросе [Bayes information retrieval model], выполняемом на коллекции документов, состоящей из пяти отдельных глав оригинала настоящей книги. Предполагается, что эти главы имеют одинаковое качество, поэтому требуется лишь вычислить вероятность запроса применительно к данному документу, для каждого документа. Такая процедура выполнена дважды, причем в первый раз использовалось выражение оценки несглажен-ного максимального правдоподобия Di5 а во второй раз — модель DL' со сглаживанием путем добавления единицы. Можно было бы предположить, что текущая глава должна получить наивысший ранг применительно к этому запросу, и в действительности были получены такие данные при использовании в каждой модели.
Преимуществом сглаженной модели является то, что она менее восприимчива к шуму и позволяет присвоить ненулевую вероятность релевантности документу, не содержащему все слова запроса. А преимуществом несглаженной модели является то, что она позволяет проще выполнить вычисления применительно к коллекциям с многочисленными документами, поскольку после создания индекса, где указано, в каких документах упоминается каждое слово, появляется возможность быстро формировать результирующий набор путем применения операции пересечения к этим спискам, после чего остается вычислить Р(о|Д) только для документов, входящих в полученное пересечение, а не для каждого документа.
Таблица 23.1. Вероятностная модель информационного поиска для запроса [Bayes information retrieval model], применяемого к коллекции документов, состоящей из пяти глав оригинала настоящей книги. В этой таблице указано количество слов, относящееся к каждой паре "документ-слово", и общее количество слов ЛГдля каждого документа. Используются две модели документа (Dj. — это несглаженная модель однословных сочетаний для i-ro документа; D±' — та же модель со сглаживанием путем добавления единицы) и вычисляется вероятность запроса применительно к каждому документу для обеих моделей. Очевидно, что текущая глава (глава 23) имеет наивысшие показатели при использовании любой модели, поскольку в ней появление искомых слов имеет в 200 раз более высокую вероятность по сравнению с любой другой главой.