Тезаурусы в задачах информационного поиска. Лукашевич (2010) (1185451), страница 41
Текст из файла (страница 41)
Каждому атому формулысопоставляется множество документов, для которых значение атома истинно. Если атомявляется термином, то ему сопоставляется множество документов, в которых терминвстречается. Затем над множествами выполняются элементарные операции —155объединения, пересечения и дополнения, соответствующие логическим связкам междуатомами.Современные булевские модели информационного поиска включают такжеоператоры близости элементов запроса, которая измеряется либо в количествепромежуточных слов между элементами запроса в документе, либо задается указаниемструктурной единицы документа (предложение, абзац), в которой должны упоминатьсяэлементы запроса.Булевская модель обработки запроса имеет ряд недостатков:- на заданный запрос поисковая машина может вернуть очень много документов(или даже все документы коллекции). В этом случае пользователь вынужденпоследовательно добавлять условия в запрос, чтобы уменьшитьрезультирующую выборку.
Поиск производится методом проб и ошибок. Врезультате также часто возникает ситуация, когда условия булевского запросаоказываются противоречивы, и пользователь не получает ни одного документа;- как правило, полезную выборку обозримого размера можно получить, задавсложную логическую формулу. При этом от пользователя требуется не толькознание правил построения формул, но и достаточно хорошее знакомство с«языком» предметной области;- вследствие того, что существует только два значения релевантности:«релевантен» (true) и «нерелевантен» (false), результирующая выборка неможет быть упорядочена по релевантности.
Все документы одинаковорелевантны;- все атомы формулы имеют одинаковую важность (вес), хотя некоторые из нихмогут быть «ключевыми», другие — вспомогательными.В то же время Булевская модель имеет и положительные достоинства. Результатыее работы хорошо предсказуемы и понятны. В булевском запросе могут быть объединенызначения разных характеристик документов, включая как слова, содержащиеся вдокументе, так и такие характеристики как автор документа, время создания документа ит.д.Несмотря на недостатки булевской модели, имеются ситуации, когда булевскийпоиск является предпочтительным, поэтому такая возможность поиска предоставляетсямногими поисковыми системами как интернет-поисковиками, так и различнымикоммерческими службами по поиску документов, библиотечными службами.11.1.2. Векторная модель информационного поискаДля упорядочения выдачи поисковой системы по мере соответствия ее запросу,необходимо ввести веса соответствия документов запросу, которые должны вычислятьсяна основе входящих в запрос слов (Buckley и др., 1993).Простым способом определения значимости слова запроса в документе являетсячастота употребления слова в документе (tf): чем чаще встречается слово запроса вдокументе, чем выше его вес.
Такой способ вычисления веса слов запроса в документепредполагает, что все слова документа имеют одинаковую значимость. Однако словадокумента могут иметь большую или меньшую различительную силу. Так, в базе«Законодательство России» практически каждый документ содержит слова закон,законодательство, Россия, Российский, поэтому данные слова в данной коллекции имеютнизкую значимость для определения релевантности документов. Таким образом, можнопредположить, что чем чаще в коллекции документов употребляется некоторое слово, темменьше его значимость при нахождении релевантных документов.Частотность употребления слова в коллекции может быть учтена посредствомвычисления количества документов в коллекции, в которых содержится это слово, - df.При возрастании df, вес слова в документе должен снижаться.
Это можно учесть, умножаячастоту употребления слова в документе tf на обратную величину df – idf. Таким образом,156вес слова в документе может быть вычисляться по формуле tf*idf. Idf часто вычисляетсяпо следующей формулеNIdftj= log n , j(11.1)где N — число документов в коллекции, n j — число документов, в которыхвстретился t j .dN — множество документов коллекции,Таким образом, пусть Dd1,..,Tt1,..,tM — множество слов-элементов запроса.
Для каждого фиксированного iдокумент d i представляется вектором весовwji tfjiidfji,j 1..M ,(11.2)где tf ji — частота встречаемости слова t j в документе d i , idf ji — величина,обратная частоте встречаемости слова t j по всем документам коллекции.После вычисления весов всех слов в документе документ может быть представленкак вектор, в котором каждый компонент соответствует отдельному слову документа.Представление документов и запросов в виде векторов, входящих в них слов, и составляетсуть векторной модели информационного поиска.Запрос также может быть представлен как вектор весов слов. Для определениясходства между векторами запроса и документа используется так называемая косинуснаямера.Sim (q, di)= ( wqti*wdti) /( wqti2* wdti2)(11.3)Таким образом, теперь соответствие запроса документу измеряется конкретнымчислом, и все документы могут быть упорядочены в выдаче поисковой системы по этомучислу.К преимуществам векторной модели информационного поиска относится то, чтомодель предоставляет простую модель для создания упорядоченной выдачиинформационной системы.
При этом конкретный способ вычисления весов слов вдокументе может меняться в зависимости от решаемой задачи и рабочей коллекции.Недостатком подхода является предположение о независимости слов в тексте, чтопротиворечит тому, что в тексте используется множество связанных по смыслу слов.11.1.3. Вероятностные модели информационного поискаОдним из эффективных типов моделей информационного поиска являютсявероятностные модели.Вероятностные модели базируются на принципе ранжирования на основевероятности, провозглашенном ван Ризбергеном в 1979 году, который заключается вследующем (Croft и др., 2009):Если поисковая система в ответ на каждый запрос ранжирует документы вколлекции в соответствии с уменьшающейся вероятностью релевантностидокумента пользователю, который задал запрос,где вероятности оценены максимально точно на базе тех данных, которыедоступны системе для этой цели,то общая эффективность системы по отношению к данному пользователю будетмаксимальной эффективностью, которая может быть получена на имеющихсяданных.157Мы не будем подробно приводить рассмотрения, которые проводятся в рамкахданного класс моделей, поскольку это выходит за рамки данной книги.
Мы укажем лишьнаиболее известную модель оценки релевантностидокумента запросу, котораясформировалась в рамках этого подхода, а именно так называемую модель BM25, такженазываемую OKAPI по названию системы, в которой впервые такая схема взвешиваниябыла применена (Robertson и др., 1994).где f(qi,D) это частотность терма qi в документе D, |D| - это длина документа D всловах, avgdl – средняя длина документов в коллекции, k1 и b – это параметры формулы,обычно принимающие значения k1=2.0, b = 0.75.
. IDF(qi) - это обратная частота поколлекции, которая обычно вычисляется как:(11.5)где N – это общее число документов в коллекции и n(qi) – это число документов,содержащих qi.11.1.4. Языковые статистические модели (language modelling)Языковые статистические модели являются моделями информационного поиска,относительно недавно адаптированные к этой задаче из других сфер автоматическойобработки текста и речи.«Языковые статистические модели» - это группа статистических методов, которыеоценивают вероятность появления последовательности из m словпосредством вычисления вероятностного распределения.
Такие модели используются всамых различных сферах автоматической обработки текстов в таких как распознаваниеречи, машинный перевод, морфологический и синтаксический анализ текста.В информационном поиске языковые модели используются для установленияотношений между запросом Q и документами коллекции, в том смысле, что упорядочениедокументов при выдаче ответов на запрос определяется на основе оценки вероятноститого, что языковая модель, построенная по документу, породит совокупность слов запросаP(Q|Md) (Ponte, Croft, 1998; Song, Croft, 1999).Равенство (11.6) представляет собой основную формулу языковой моделиинформационного поиска для так называемой униграммной модели, то есть в том случае,если все слова запроса рассматриваются как независимые друг от друга сущности:(*) P (q1, q2, ….qn | d)= P(qi|d)(11.6)Данная формула означает, что вероятность порождения запроса из документа вуниграммной модели оценивается как произведение вероятности порождения отдельногоэлемента запроса из документа.
Наиболее естественным способом оценки P(qi|d) являетсяоценка вероятности встречаемости терма qi в документе d посредством так называемойоценки максимального правдоподобия (maximal likelihood estimate – MLE), то естьP (qi|d)=freq (qi,d)/length(d)(11.7)Оценка вероятности последовательностей слов может оказаться достаточносложной для текстовых коллекций, поскольку некоторые возможные последовательностислов могли никогда не встречаться в базовой коллекции, и не могли использоваться для158качественной настройки языковой модели (training of language model), то есть возникает так называемая проблема нехватки данных (data sparceness).По этой причине важным элементом языковых моделей является процедурасглаживания (smoothing) (Chen, Goodman, 1998). Большинство формул сглаживанияпредложено в рамках моделей, созданных для распознавания речи.В сфере языковых моделей для информационного поиска ситуация нехваткиданных проявляется в том, что если элемент запроса не содержится в документе, то привыбранном способе оценки вероятности получаем P(qi|d)=0 и, следовательно, P (q1, q2,….qn | d) =0.Все процедуры сглаживания основаны на некотором снижении оценки вероятностина основе уже встреченных событий (то есть на основе появления термина в документе) иза счет этого появляется возможность дополнительно оценить вероятность событий,которые в конкретном документе не встретились.Одной из распространенных техник сглаживания является учет вероятностипоявления слова в коллекции P(qi|C), и тогда обобщенная формула сглаживания выглядитследующим образом:P (w|d)=Ps(w|d), если слово запроса встречалось в документе,d P (w|C), если слово не встречалось в документе.(11.8)где Ps(w|d ) – это сглаженная вероятность P(w|d),P(wi|C) – это вероятность появления слова в коллекции,d - - коэффициент учета каждой из моделей, в общем случае может зависеть отдокумента.Один из простейших вариантов формулы, так называемое сглаживание JelinekMercer, выглядит следующим образом:P (qi|M)= λP(qi|d)+(1-λ)P(qi|C)(11.9)Другим примером формулы сглаживания является так называемая формулаабсолютного дисконтирования (absolute discounting).
Идея метода заключается впонижении вероятности встреченных слов путем вычитания констант вместо умноженияих на коэффициенты λ и (1-λ):P (qi|M)=(max(с(qi,d)-δ,0)/Σwc (w,d)) + σ P(qi|C)(11.10)где δ – сглаживающая константа величиной от 0 до 1; σ = δ |d|u/|d|; |d|u – числоуникальных слов в документе; |d| - общее количество слов в документе, то есть|d| = Σwc (w,d))(11.11)Учет P(qi|C) в языковых моделях играет роль, сходную с учетом обратнойчастотности (idf) в векторной модели информационного поиска (Zhai, Lafferty, 2001)Эксперименты в рамках конференции TREC (Ponte, Croft, 1998; Manning и др.,2008) показали эффективность языковых моделей для информационного поиска, однакосущественным для эффективной работы методов является процедура подбора подходящейпроцедуры сглаживания.В работе (Zhai, Lafferty, 2001) исследовались различные виды сглаживания.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
