Стратегия поиска в автоматизированных информационных системах

Примечание	от автора: Список литературы не совсем соответствует истине
	Загрузить архив:
	Файл: ref-19638.zip (350kb [zip], Скачиваний: 31) скачать

КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ КУЛЬТУРЫ И ИСКУССТВ

Кафедра информатики

Вступительный реферат по теме:

Стратегия поиска в Автоматизированных информационно-поисковых системах

Выполнил:

Султанов Ильнур Ильдусович

Казань, 2004
Содержание

TOC o "1-3" h z u Введение. PAGEREF _Toc84433917 h 3

Проблемы поиска информации. PAGEREF _Toc84433918 h 5

Поисковые алгоритмы.. PAGEREF _Toc84433919 h 7

Оценка качества. PAGEREF _Toc84433920 h 16

Дополнительные возможности предоставляемые поисковыми машинами. PAGEREF _Toc84433921 h 18

Лингвистика. PAGEREF _Toc84433922 h 20

Заключение. PAGEREF _Toc84433923 h 22

Список литературы.. PAGEREF _Toc84433924 h 23

Глоссарий: PAGEREF _Toc84433925 h 24

[1][1] (векторная, обобщенная векторная, латентно-семантическая, нейросетевая) и вероятностные.

Булевское семейство моделей самое известное, реализующие полнотекстовый поиск. Есть слово - документ считается найденным, нет – не найденным. Собственно, классическая булевская модель – это мостик, связывающий теорию информационного поиска с теорией поиска и манипулирования данными.

Критика булевской модели, вполне справедливая, состоит в ее крайней жесткости и непригодности для ранжирования. Поэтому еще в 1957 году Joyce и Needham (Джойс и Нидхэм) предложили учитывать частотные характеристики слов, чтобы «... операция сравнения была бы отношением расстояния между векторами...».

Векторная модель и была с успехом реализована в 1968 году отцом-основателем науки об информационном поиске Джерардом Солтоном (Gerard Salton)[2][2] в поисковой системе SMART (Salton's Magical Automatic Retriever of Text). Ранжирование в этой модели основано на естественном статистическом наблюдении, что чем больше локальная частота термина в документе (TF) и больше «редкость» (т.е. обратная встречаемость в документах) термина в коллекции (IDF), тем выше вес данного документа по отношению к термину. Обозначение IDF ввела Karen Sparck-Jones(Карен Спарк-Джоунз) в 1972 в статье про различительную силу (term specificity). С этого момента обозначение TF*IDF широко используется как синоним векторной модели.

Наконец, в 1977 году Robertson и Sparck-Jones  (Робертсон и Спарк-Джоунз) обосновали и реализовали вероятностную модель (предложенную еще в 1960), также положившую начало целому семейству. Релевантность в этой модели рассматривается как вероятность того, что данный документ может оказаться интересным пользователю. При этом подразумевается наличие уже существующего первоначального набора релевантных документов, выбранных пользователем или полученных автоматически при каком-нибудь упрощенном предположении. Вероятность оказаться релевантным для каждого следующего документа рассчитывается на основании соотношения встречаемости терминов в релевантном наборе и в остальной, «нерелевантной» части коллекции. Хотя вероятностные модели обладают некоторым теоретическим преимуществом, ведь они располагают документы в порядке убывания "вероятности оказаться релевантным", на практике они так и не получили большого распространения.

Важно заметить, что в каждом из семейств простейшая модель исходит из предположения о взаимонезависимости слов и обладает условием фильтрации: документы, не содержащие слова запроса, никогда не бывают найденными. Продвинутые («альтернативные») модели каждого из семейств не считают слова запроса взаимонезависимыми, а, кроме того, позволяют находить документы, не содержащие ни одного слова из запроса.[3][3], соответствующих первым главным компонентам ее сингулярного разложения.

Доказано, что если оставить в рассмотрении первые k сингулярных чисел (остальные приравнять нулю), мы получим ближайшую из всех возможных аппроксимацию исходной матрицы ранга k (в некотором смысле ее «ближайшую семантическую интерпретацию ранга k»). Уменьшая ранг, мы отфильтровываем нерелевантные детали; увеличивая, пытаемся отразить все нюансы структуры реальных данных.

Операции поиска или нахождения похожих документов резко упрощаются, так как каждому слову и каждому документу сопоставляется относительно короткий вектор из k смыслов (строки и столбцы соответствующих матриц). Однако по причине малой ли осмысленности «смыслов», или по какой иной[4][4], но использование LSI в лоб для поиска так и не получило распространения. Хотя во вспомогательных целях (автоматическая фильтрация, классификация, разделение коллекций, предварительное понижение размерности для других моделей) этот метод, по-видимому, находит применение.

[5][5] для оценки качества поиска меряют два параметра:

· точность (precision) – доля релевантного материала в ответе поисковой системы

· полнота (recall) – доля найденных релевантных документов в общем числе релевантных документов коллекции

Именно эти параметры использовались и используются на регулярной основе для выбора моделей и их параметров в рамках созданной Американским Интститутом Стандартов (NIST) конференции по оценке систем текстового поиска (TREC - text retrival evaluation conference)[6][6]. Начавшаяся в 1992 году консорциумом из 25 групп, к 12-му году своего существования конференция накопила значительный материал, на котором до сих пор оттачиваются поисковые системы. К каждой очередной конференции готовится новый материал (т.н. «дорожка») по каждому из интересующих направлений. «Дорожка» включает коллекцию документов и запросов. Приведу примеры:

· Дорожка произвольных запросов (ad hoc) – присутствует на всех конференциях

· Многоязычный поиск

· Маршрутизация и фильтрации

· Высокоточный поиск (с единственным ответом, выполняемый на время)

· Взаимодействие с пользователем

· Естестственно-языковая «дорожка»

· Ответы на «вопросы»

· Поиск в «грязных» (только что отсканированных) текстах

· Голосовой поиск

· Поиск в очень большом корпусе (20GB, 100GB и т.д.)

· WEB корпус (на последних конференциях он представлен выборкой по домену .gov)

· Распределенный поиск и слияние результатов поиска из разных систем

[1] В отечественной литературе алгебраические модели часто называют линейными

[2]GerardSalton (Sahlman) 1927-1995. Он же Селтон, он же Залтон и даже Залман, он же Жерар, Герард, Жерард или даже Джеральд в зависимости от вкуса переводчика и допущенных опечаток

http://www.cs.virginia.edu/~clv2m/salton.txt

[3]для больших коллекций число «смыслов» увеличивают до 300

[4]После наших экспериментов с LSI получилось, что «смысл номер 1» в Рунете - все англоязычные документы, «смысл номер 3» – все форумы и т.п.

[5] но не обязательно – есть и «альтернативные» метрики!

[6] материалы конференции публично доступны по адресу trec.nist.gov/pubs.html