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

В частности, одним из естественных ограничений качества поиска служит

наблюдение, вынесенное в эпиграф: мнения двух «асессоров» (специалистов,

выносящих вердикт о релевантности) в среднем не совпадают друг с другом в

очень большой степени! Отсюда вытекает и естественная верхняя граница

качества поиска, ведь качество измеряется по итогам сопоставления с мнением

асессора.

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

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

системы

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

релевантных документов коллекции

Именно эти параметры использовались и используются на регулярной основе

для выбора моделей и их параметров в рамках созданной Американским

Интститутом Стандартов (NIST) конференции по оценке систем текстового

поиска (TREC - text retrival evaluation conference)[6][6]. Начавшаяся в

1992 году консорциумом из 25 групп, к 12-му году своего существования

конференция накопила значительный материал, на котором до сих пор

оттачиваются поисковые системы. К каждой очередной конференции готовится

новый материал (т.н. «дорожка») по каждому из интересующих направлений.

«Дорожка» включает коллекцию документов и запросов. Приведу примеры:

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

конференциях

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

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

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

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

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

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

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

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

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

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

домену .gov)

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

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

Как видно из «дорожек» TREC, к самому поиску тесно примыкает ряд задач,

либо разделяющих с ним общую идеологию (классификация, маршрутизация,

фильтрация, аннотирование), либо являющихся неотъемлемой частью поискового

процесса (кластеризация результатов, расширение и сужение запросов,

обратная связь, «запросо-зависимое» аннотирование, поисковый интерфейс и

языки запросов). Нет ни одной поисковой системы, которой бы не приходилось

решать на практике хотя бы одну из этих задач.

Зачастую наличие того или иного дополнительного свойства является

решающим доводом в конкурентной борьбе поисковых систем. Например, краткие

аннотации состоящие из информативных цитат документа, которыми некоторые

поисковые системы сопровождают результаты соей работы, помогают им

оставаться на полступеньки впереди конкурентов.

Обо всех задачах и способах их решения рассказать невозможно. Для

примера рассмотрим «расширение запроса», которое обычно производится через

привлечение к поиску ассоциированных терминов. Решение этой задачи возможно

в двух видах – локальном (динамическом) и глобальном (статическом).

Локальные техники опираются на текст запроса и анализируют только

документы, найденные по нему. Глобальные же «расширения» могут оперировать

тезаурусами, как априорными (лингвистическими), так и построенными

автоматически по всей коллекции документов. По общепринятому мнению,

глобальные модификации запросов через тезаурусы работают неэффективно,

понижая точность поиска. Более успешный глобальный подход основан на

построенных вручную статических классификациях, например, ВЕБ-директориях.

Этот подход широко использутся в интернет-поисковиках в операциях сужения

или расширения запроса.

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

или очень похожих принципах и моделях, что и сам поиск. Сравните, например,

нейросетевую поисковую модель, в которой используется идея передачи

затухающих колебаний от слов к документам и обратно к словам (амплитуда

первого колебания – все тот же TF*IDF), с техникой локального расширения

запроса. Последняя основанна на обратной связи (relevance feedback), в

которой берутся наиболее смыслоразличительные (контрастные) слова из

документов, принадлежащих верхушке списка найденного.

К сожалению, локальные методы расширения запроса, несмотря на эффектные

технические идеи типа «Term Vector Database» и очевидную пользу, все еще

остаются крайне дорогими.

Лингвистика

Немного в стороне от статистических моделей и структур данных стоит

класс алгоритмов, традиционно относимых к лингвистическим. Точно границы

между статистическим и лингвистическими методами провести трудно. Условно

можно считать лингвистическими методы, опирающиеся на словари

(морфологические, синтаксические, семантические), созданные человеком. Хотя

считается доказанным, что для некоторых языков лингвистические алгоритмы не

вносят существенного прироста точности и полноты (например, английский),

все же основная масса языков требует хотя бы минимального уровня

лингвистической обработки. Приведу только список задач, решаемый

лингвистическими или окололингвистическими приемами:

. автоматическое определение языка документа

. токенизация (графематический анализ): выделение слов, границ

предложений

. исключение неинформативных слов (стоп-слов)

. лемматизация (нормализация, стемминг): приведение словоизменительных

форм к «словарной». В том числе и для слов, не входящих в словарь

системы

. разделение сложных слов (компаундов) для некоторых языков (например,

немецкого)

. дизамбигуация: полное или частичное снятие омонимии

. выделение именных групп

Еще реже в исследованиях и на практике можно встретить алгоритмы

словообразовательного, синтаксического и даже семантического анализа. При

этом под семантическим анализом чаще подразумевают какой-нибудь

статистический алгоритм (LSI, нейронные сети), а если толково-комбинаторные

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

областях.

Заключение

Прежде всего, очевидно, что поиск в большом информационном массиве, не

может быть сколько-нибудь корректно выполнен, будучи основан на анализе

одного лишь текста документа. Ведь внетекстовые (off-page) факторы играют

порой и большую роль, чем текст самой страницы. Положение на сайте,

посещаемость, авторитетность источника, частота обновления, цитируемость

страницы и ее авторов – все эти факторы играют важную роль.

Cтав основным источником получения справочной информации для человека,

поисковые системы стали основным источником трафика для интернет -сайтов.

Как следствие, они немедленно подверглись «атакам» недобросовестных

авторов, желающих оказаться в первых страницах результатов поиска.

Искусственная генерация входных страниц, насыщенных популярными словами,

техника клоакинга, «слепого текста» и многие другие приемы, предназначенные

для обмана поисковых систем.

Кроме проблемы корректного ранжирования, создателям поисковых систем

пришлось решать задачу обновления и синхронизации колоссальной по размеру

коллекции с гетерогенными форматами, способами доставки, языками,

кодировками, массой бессодержательных и дублирующихся текстов. Необходимо

поддерживать базу в состоянии максимальной свежести, может быть учитывать

индивидуальные и коллективные предпочтения пользователей. Многие из этих

задач никогда прежде не рассматривались в традицонной науке информационного

поиска.

Список литературы

1. Ашманов И. С. Национальные особенности поисковых систем // Журнал

"Компьютер в школе", № 01, 2000 год // Издательство "Открытые системы"

(www.osp.ru)

2. Антонов А.В., Мешков В.С. Аналитические проблемы поисковых систем и

«лингвистические анализаторы» // НТИ.Сер.1.- 2000.- №6.-С.1-5

3. Войскунский В.Г. Оценка функциональной эффективности документального

поиска: и размытые шкалы оценка пертинентности // НТИ. Сер. 2.- 1992.-

№5.-С.19-27

4. Кноп К. Поиск в Интернете как хроническое заболевание // Мир Internet.

- 2002. - N 10. - С. 33-35

5. Конжаев А. Стратегия информационного поиска // http://www.msiu.ru.

6. Попов С. Поиск информации и принятие решения // НТИ. Сер.2.-2001.-№1.-

С.1-4

7. Степанов В.К Русскоязычные поисковые механизмы в Интернет //

ComputerWorld Россия.-1997.-N11.-C.37-40.

8. Сегалович И. Как работают поисковые системы // Мир Internet. - 2002. -

N 10. - С. 24-32

Глоссарий:

++ асессор (assesor, эксперт) – специалист в предметной области,

выносящий заключение о релевантности документа, найденного поисковой

системой

++ булевская модель (boolean, булева, булевая, двоичная) – модель

поиска, опирающаяся на операции пересечения, объединения и вычитания

множеств

++ векторная модель – модель информационного поиска, рассматривающая

документы и запросы как векторы в пространстве слов, а релевантность как

расстояние между ними

++ вероятностная модель – модель информационного поиска,

рассматривающая релевантность как вероятность соответствия данного

документа запросу на основании вероятностей соответствия слов данного

документа идеальному ответу

++ внетекстовые критерии (off-page, вне-страничные) – критерии

ранжирования документов в поисковых системах, учитыващие факторы, не

содержащиеся в тексте самого документа и не извлекаемые оттуда никаким

образом

++ входные страницы (doorways, hallways) – страницы, созданные для

искусственного повышения ранга в поисковых системах (поискового спама). При

попадании на них пользователя перенаправляют на целевую страницу

++ дизамбигуация (tagging, part of speech disambiguation, таггинг) –

выбор одного из нескольких омонимов c помощью контекста; в английском языке

часто сводится к автоматическому назначению грамматической категории «часть

речи»

++ дубликаты (duplicates) – разные документы с идентичным, с точки

зрения пользователя, содержанием; приблизительные дубликаты (near

duplicates, почти-дубликаты), в отличие от точных дубликатов, содержат

незначительные отличия

++ иллюзия свежести – эффект кажущейся свежести, достигаемый поисковыми

системами в интернете за счет более регулярного обхода тех документов,

которые чаще находятся пользователями

++ инвертированный файл (inverted file, инверсный файл, инвертированный

индекс, инвертированный список) – индекс поисковой системы, в котором

перечислены слова коллекции документов, а для каждого слова перечислены все

места, в которых оно встретилось

++ индекс (index, указатель) – см. индексирование

++ индекс цитирования (citation index) – число упоминаний (цитирований)

научной статьи, в традиционной библиографической науке рассчитывается за

промежуток времени, например, за год

++ индексирование (indexing, индексация) – процесс составления или

приписывания указателя (индекса) – служебной структуры данных, необходимой

для последующего поиска

++ информационный поиск (Information Retrieval, IR) – поиск

неструктурированной информации, единицой представления которой является

документ произвольных форматов. Предметом поиска выступает информационная

потребность пользователя, неформально выраженная в поисковом запросе. И

критерий поиска, и его результаты недетермированы. Этими признаками

информационный поиск отличается от «поиска данных», который оперирует

набором формально заданных предикатов, имеет дело со структурированной

информацией и чей результат всегда детерминирован. Теория информационного

поиска изучает все составляющие процесса поиска, а именно, предварительную

обработку текста (индексирование), обработку и исполнение запроса,

ранжирование, пользовательский интерфейс и обратную связь.

++ клоакинг (cloaking) – техника поискового спама, состоящая в

распознании авторами документов робота (индексирующего агента) поисковой

системы и генерации для него специального содержания, принципиально

отличающегося от содержания, выдаваемого пользователю

++ контрастность термина – см. различительная сила

++ латентно-семантическое индексирование – запатентованный алгоритм

поиска по смыслу, идентичный факторному анализу. Основан на сингулярном

разложении матрицы связи слов с документами

++ лемматизация (lemmatization, нормализация) – приведение формы слова

к словарному виду, то есть лемме

++ накрутка поисковых систем – см. спам поисковых систем

++ непотизм – вид спама поисковых систем, установка авторами документов

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

++ обратная встречаемость в документах (inverted document frequency,

IDF, обратная частота в документах, обратная документная частота) –

показатель поисковой ценности слова (его различительной силы); обратная

говорят, потому что при вычислении этого показателя в знаменателе дроби

обычно стоит число документов, содержащих данное слово

++ обратная связь – отклик пользователей на результат поиска, их

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

системой и использующиеся, например, для итеративной модификации запроса.

Следует отличать от псевдо-обратной связи – техники модификации запроса, в

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

релевантными

++ омонимия – см. полисемия

++ основа – часть слова, общая для набора его словообразовательных и

словоизменительных (чаще) форм

++ поиск по смыслу – алгоритм информационного поиска, способный

находить документы, не содержащие слов запроса

++ поиск похожих документов (similar document search) – задача

информационного поиска, в которой в качестве запроса выступает сам документ

и необходимо найти документы, максимально напоминающие данный

++ поисковая система (search engine, SE, информационно-поисковая

система, ИПС, поисковая машина, машина поиска, «поисковик», «искалка») –

программа, предназначенная для поиска информации, обычно текстовых

документов

++ поисковое предписание (query, запрос) – обычно строчка текста

++ полисемия (polysemy, homography, многозначность, омография,

омонимия) - наличие нескольких значений у одного и того же слова

++ полнота (recall, охват) – доля релевантного материала, заключенного

в ответе поисковой системы, по отношению ко всему релевантному материалу в

коллекции

++ почти-дубликаты (near-duplicates, приблизительные дубликаты) – см.

дубликаты

++ прюнинг (pruning) – отсечение заведомо нерелевантных документов при

поиске с целью ускорения выполнения запроса

++ прямой поиск – поиск непосредственно по тексту документов, без

предварительной обработки (без индексирования)

++ псевдо-обратная связь – см. обратная связь

++ различительная сила слова (term specificity, term discriminating

power, контрастность, различительная сила) – степень ширины или узости

слова. Слишком широкие термины в поиске приносят слишком много информации,

при это существенная часть ее бесполезна. Слишком узкие термины помогают

найти слишком мало документов, хотя и более точных.

++ регулярное выражение (regualr expression, pattern, «шаблон», реже

«трафарет», «маска») – способ записи поискового предписания, позволяющий

определять пожелания к искомому слову, его возможные написания, ошибки и

т.д. В широком смысле – язык, позволяющий задавать запросы неограниченной

сложности

++ релевантность (relevance, relevancy) – соответствие документа

запросу

++ сигнатура (signature, подпись) – множество хеш-значений слов

некоторого блока текста. При поиске по методу сигнатур все сигнатуры всех

блоков коллекции просматриваются последовательно в поисках совпадений с хеш-

значениями слов запроса

++ словоизменение (inflection) – образование формы определенного

грамматического значения, обычно обязательного в данном грамматическом

контексте, принадлежащей к фиксированному набору форм (парадигме),

характерного для слов данного типа. В отличие от словообразования никогда

не приводит к смене типа и порождает предсказуемое значение. Словоизменение

имен называют склонением (declension), а глаголов – спряжением

(conjugation)

++ словообразование (derivation) – образование слова или основы из

другого слова или основы. Чаще приводит к смене типа и к образованию слов,

имеющих идеосинкразическое значение

++ смыслоразличительный – см. различительная сила

++ спам поисковых систем (spam, спамдексинг, накрутка поисковых систем)

– попытка воздействовать на результат информационного поиска со стороны

авторов документов

++ статическая популярность – см. PageRank

++ стемминг – поцесс выделения основы слова

++ стоп-слова (stop-words) – те союзы, предлоги и другие частотные

слова, которые данная поисковая система исключила из процесса

индексирования и поиска для повышения своей производительности и/или

точности поиска

++ суффиксные деревья, суффиксные массивы (suffix trees, suffix arrays,

PAT-arrays) – индекс, основанный на представлении всех значимых суффиксов

текста в структуре данных, известной как бор (trie). Суффиксом в этом

индексе называю любую «подстроку», начинающуюся с некоторой позиции текста

(текст рассматривается как одна непрерывная строка) и продолжающуюся до его

конца. В реальных приложениях длина суффиксов ограничена, а индексируются

только значимые позиции – например, начала слов. Этот индекс позволяет

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

файлах

++ токенизация (tokenization, lexical analysis, графематический анализ,

лексический анализ) – выделение в тексте слов, чисел, и иных токенов, в том

числе, например, нахождение границ предложений

++ точность (precision) - доля релевантного материала в ответе

поисковой системы

++ хеш-значение (hash-value) – значение хеш-функции (hash-function),

преобразующей данные произвольной длины (обычно, строчку) в число

фиксированного порядка

++ частота (слова) в документах (document frequency, встречаемость в

документах, документная частота) – число документов в коллекции, содержащих

данное слово

++ частота термина (term frequency, TF) – частота употреблений слова в

документе

++ шингл – (shingle) – хеш-значение непрерывной последовательности слов

текста фиксированной длины

++ PageRank – алгоритм расчета статической (глобальной) популярности

страницы в интернете, назван в честь одного из авторов - Лоуренса Пейджа.

Соответствует вероятности попадания пользователя на страницу в модели

случайного блуждания

++ TF*IDF – численная мера соответствия слова и документа в векторной

модели; тем больше, чем относительно чаще слово встретилось в документе и

относительно реже в коллекции

-----------------------

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

линейными

[2] Gerard Salton (Sahlman) 1927-1995. Он же Селтон, он же Залтон и даже

Залман, он же Жерар, Герард, Жерард или даже Джеральд в зависимости от

вкуса переводчика и допущенных опечаток

http://www.cs.cornell.edu/Info/Department/Annual95/Faculty/Salton.html

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

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

[4] После наших экспериментов с LSI получилось, что «смысл номер 1» в

Рунете - все англоязычные документы, «смысл номер 3» – все форумы и т.п.

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

[6] материалы конференции публично доступны по адресу

trec.nist.gov/pubs.html

-----------------------

|Consistency checking has shown that the |

|overlap of relevant documents between any|

|two assesors is on the order of 40% on |

|average…cross-assesor recall and |

|precision of about 65% …This implies a |

|practical upper bound on retrieval system|

|performance of 65% …[7][1] |

|Donna Harman |

|What we have learned, and not learned, |

|from TREC [harman] |

| |

|Сингулярным разложением действительной|

|матрицы A размеров m*n называется |

|всякое ее разложение вида A = USV, где|

|U - ортогональная матрица размеров |

|m*m, V - ортогональная матрица |

|размеров n*n, S - диагональная матрица|

|размеров m*n, элементы которой sij= 0,|

|если i не равно j, и sii = si >= 0. |

|Величины si называются сингулярными |

|числами матрицы и равны арифметическим|

|значениям квадратных корней из |

|соответствующих собственных значений |

|матрицы AAT. В англоязычной литературе|

|сингулярное разложение принято |

|называть SVD-разложением. |

[pic]

Страницы: 1, 2