Как работают поисковые системы |
||||
МЕНЮ Главная страница Поиск Регистрация на сайте Помощь проекту Архив новостей ТЕМЫ Новости ИИ Голосовой помощник Разработка ИИГородские сумасшедшие ИИ в медицине ИИ проекты Искусственные нейросети Искусственный интеллект Слежка за людьми Угроза ИИ ИИ теория Внедрение ИИКомпьютерные науки Машинное обуч. (Ошибки) Машинное обучение Машинный перевод Нейронные сети начинающим Психология ИИ Реализация ИИ Реализация нейросетей Создание беспилотных авто Трезво про ИИ Философия ИИ Big data Работа разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика
Генетические алгоритмы Капсульные нейросети Основы нейронных сетей Распознавание лиц Распознавание образов Распознавание речи Творчество ИИ Техническое зрение Чат-боты Авторизация |
2022-01-23 12:35 Мы разбирали старые письма и наткнулись на статью, которую писал Илья Сегалович iseg для журнала «Мир Internet» в далёком 2002 году. В ней он сравнивает интернет и поисковые системы с чудесами света, размышляет о поисковых технологиях и вспоминает их историю. Несмотря на загруженность по работе, Илья написал статью в рекордные сроки и даже снабдил достаточно подробным словарём терминов, который особенно интересно читать в наши дни. Нам не удалось найти электронную версию журнала со статьей, поэтому сегодня мы публикуем её в нашем блоге, первым автором которого, к слову, был Илья. В мире написаны сотни поисковых систем, а если считать функции поиска, реализованные в самых разных программах, то счет надо вести на тысячи. И как бы ни был реализован процесс поиска, на какой бы математической модели он ни основывался, идеи и программы, реализующие поиск, достаточно просты. Хотя эта простота, относится, по-видимому, к той категории, про которую говорят «просто, но работает». Так или иначе, но именно поисковые системы стали одним из двух новых чудес света, предоставив Homo Sapiens неограниченный и мгновенный доступ к информации. Первым чудом, очевидно, можно считать Интернет как таковой, с его возможностями всеобщей коммуникации. Поисковые системы в исторической перспективе Существует распространенное убеждение, что каждое новое поколение программ совершенней предыдущего. Дескать, раньше все было несовершенно, зато теперь повсюду царит чуть ли не искусственный интеллект. Иная крайняя точка зрения состоит в том, что «все новое – это хорошо забытое старое». Думаю, что применительно к поисковым системам истина лежит где-то посередине. Алгоритм + Структура данных = Поисковая система Как и любая программа, поисковая система оперирует со структурами данных и исполняет алгоритм. Разнообразие алгоритмов не очень велико, но оно есть. Не считая квантовых компьютеров, которые обещают нам волшебный прорыв в «алгоритмической сложности» поиска, и про которые автору почти ничего не известно, есть четыре класса поисковых алгоритмов. Три алгоритма из четырех требуют «индексирования», предварительной обработки документов, при котором создается вспомогательный файл, сиречь «индекс», призванный упростить и ускорить сам поиск. Это алгоритмы инвертированных файлов, суффиксных деревьев, сигнатур. В вырожденном случае предварительный этап индексирования отсутствует, а поиск происходит при помощи последовательного просмотра документов. Такой поиск называется прямым. Прямой поиск Простейшая его версия знакома многим, и нет программиста, который бы не написал хотя бы раз в своей жизни подобный код:
Кроме того, есть масса программ, комбинирующих индексный поиск для нахождения блока текста с дальнейшим прямым поиском внутри блока. Например, весьма популярный, в том числе и в Рунете, glimpse. Вообще, у прямых алгоритмов есть принципиально беспроигрышные отличительные черты. Например, неограниченные возможности по приближенному и нечеткому поиску. Ведь любое индексирование всегда сопряжено с упрощением и нормализацией терминов, а, следовательно, с потерей информации. Прямой же поиск работает непосредственно по оригинальным документам безо всяких искажений. Инвертированный файл Эта простейшая структура данных, несмотря на свое загадочное иностранное название, интуитивно знакома как любому грамотному человеку, так и любому программисту баз данных, даже не имевшему дело с полнотекстовым поиском. Первая категория людей знает, что это такое, по «конкордансам» – алфавитно упорядоченным исчерпывающим спискам слов из одного текста или принадлежащих одному автору (например «Конкорданс к стихам А. С. Пушкина», «Словарь-конкорданс публицистики Ф. М. Достоевского»). Вторые имеют дело с той или иной формой инвертированного списка всякий раз, когда строят или используют «индекс БД по ключевому полю». Чтобы сэкономить на дисковом пространстве и ускорить поиск, обычно прибегают к двум приемам. Во-первых, можно сэкономить на подробности самой позиции. Ведь чем подробнее задана такая позиция, например, в случае с «Симофонией» это «книга+глава+стих», тем больше места потребуется для хранения инвертированного файла. В наиподробнейшем варианте в инвертированном файле можно хранить и номер слова, и смещение в байтах от начала текста, и цвет и размер шрифта, да много чего еще. Чаще же просто указывают только номер документа, скажем, книгу Библии, и число употреблений этого слова в нем. Именно такая упрощенная структура считается основной в классической теории информационного поиска – Information Retrieval (IR). Второй (никак не связанный с первым) способ сжатия: упорядочить позиции для каждого слова по возрастанию адресов и для каждой позиции хранить не полный ее адрес, а разницу от предыдущего. Вот как будет выглядеть такой список для нашей странички в предположении, что мы запоминаем позицию вплоть до номера главы: ЖЕНЩИНА: [Быт.1],[+11],[0],[+2],[+4],[+2],[+4],.. Дополнительно на разностный способ хранения адресов накладывают какой-нибудь простенький способ упаковки: зачем отводить небольшому целому числу фиксированное «огромное» количество байт, ведь можно отвести ему почти столько байт, сколько оно заслуживает. Здесь уместно упомянуть коды Голомба или встроенную функцию популярного языка Perl: pack(“w”) .В литературе встречается и более тяжелая артиллерия упаковочных алгоритмов самого широкого спектра: арифметический, Хафман, LZW и т. д. Прогресс в этой области идет непрерывно. На практике в поисковых системах они используются редко: выигрыш невелик, а мощности процессора расходуются неэффективно. В результате всех описанных ухищрений размер инвертированного файла, как правило, составляет от 7 до 30 процентов от размера исходного текста, в зависимости от подробности адресации. Занесены в «Красную книгу» Неоднократно предлагались другие, отличные от инвертированного и прямого поиска алгоритмы и структуры данных. Это, прежде всего, суффиксные деревья (см. книги Манбера и Гоннета), а также сигнатуры. Математические модели Приблизительно 3 из 5 поисковых систем и модулей функционируют безо всяких математических моделей. Точнее сказать, их разработчики не ставят перед собой задачу реализовывать абстрактную модель и/или не подозревают о существовании оной. Принцип здесь прост: лишь бы программа хоть что-нибудь находила. Абы как. А дальше сам пользователь разберется. * Gerard Salton (Sahlman) 1927-1995. Он же Селтон, он же Залтон и даже Залман, он же Жерар, Герард, Жерард или даже Джеральд в зависимости от вкуса переводчика и допущенных опечаток. http://www.cs.cornell.edu/Info/Department/Annual95/Faculty/Salton.html http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/s/Salton:Gerald.html http://www.cs.virginia.edu/~clv2m/salton.txt Обозначение IDF ввела Karen Sparck-Jones (Карен Спарк-Джоунз) в 1972 в статье про различительную силу (term specificity). С этого момента обозначение TF*IDF широко используется как синоним векторной модели. Наконец, в 1977 году Robertson и Sparck-Jones (Робертсон и Спарк-Джоунз) обосновали и реализовали вероятностную модель (предложенную еще в 1960-м), также положившую начало целому семейству. Релевантность в этой модели рассматривается как вероятность того, что данный документ может оказаться интересным пользователю. При этом подразумевается наличие уже существующего первоначального набора релевантных документов, выбранных пользователем или полученных автоматически при каком-нибудь упрощенном предположении. Вероятность оказаться релевантным для каждого следующего документа рассчитывается на основании соотношения встречаемости терминов в релевантном наборе и в остальной, «нерелевантной» части коллекции. Хотя вероятностные модели обладают некоторым теоретическим преимуществом, ведь они располагают документы в порядке убывания «вероятности оказаться релевантным», на практике они так и не получили большого распространения. Я не собираюсь вдаваться в подробности и выписывать громоздкие формулы для каждой модели. Их сводка вместе с обсуждением занимает в сжатом виде 35 страниц в книжке «Современный информационный поиск». Важно только заметить, что в каждом из семейств простейшая модель исходит из предположения о взаимонезависимости слов и обладает простым условием фильтрации: документы, не содержащие слова запроса, никогда не бывают найденными. Продвинутые («альтернативные») модели каждого из семейств не считают слова запроса взаимонезависимыми, а, кроме того, позволяют находить документы, не содержащие ни одного слова из запроса. Поиск «по смыслу» Способность находить и ранжировать документы, не содержащие слов из запроса, часто считают признаком искусственного интеллекта или поиска по смыслу и относят априори к преимуществам модели. Вопрос о том, так ли это или нет, мы оставим за рамками данной статьи. Сингулярным разложением действительной матрицы A размеров m*n называется всякое ее разложение вида A = USV, где U – ортогональная матрица размеров m*m, V – ортогональная матрица размеров n*n, S – диагональная матрица размеров m*n, элементы которой sij= 0, если i не равно j, и sii = si >= 0. Величины si называются сингулярными числами матрицы и равны арифметическим значениям квадратных корней из соответствующих собственных значений матрицы AAT. В англоязычной литературе сингулярное разложение принято называть SVD-разложением. Давным-давно доказано, что если оставить в рассмотрении первые k сингулярных чисел (остальные приравнять нулю), мы получим ближайшую из всех возможных аппроксимацию исходной матрицы ранга k (в некотором смысле ее «ближайшую семантическую интерпретацию ранга k»). Уменьшая ранг, мы отфильтровываем нерелевантные детали; увеличивая, пытаемся отразить все нюансы структуры реальных данных. Операции поиска или нахождения похожих документов резко упрощаются, так как каждому слову и каждому документу сопоставляется относительно короткий вектор из k смыслов (строки и столбцы соответствующих матриц). Однако по причине малой ли осмысленности «смыслов», или по какой иной, но использование LSI в лоб для поиска так и не получило распространения. Хотя во вспомогательных целях (автоматическая фильтрация, классификация, разделение коллекций, предварительное понижение размерности для других моделей) этот метод, по-видимому, находит применение. Оценка качества 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% … Какова бы ни была модель, поисковая система нуждается в «тюнинге» – оценке качества поиска и настройке параметров. Оценка качества – идея, фундаментальная для теории поиска. Ибо именно благодаря оценке качества можно говорить о применимости или неприменимости той или иной модели и даже обсуждать их теоретичеcкие аспекты. В частности, одним из естественных ограничений качества поиска служит наблюдение, вынесенное в эпиграф: мнения двух «асессоров» (специалистов, выносящих вердикт о релевантности) в среднем не совпадают друг с другом в очень большой степени! Отсюда вытекает и естественная верхняя граница качества поиска, ведь качество измеряется по итогам сопоставления с мнением асессора. Обычно для оценки качества поиска меряют два параметра:
Именно эти параметры использовались и используются на регулярной основе для выбора моделей и их параметров в рамках созданной Американским Институтом Стандартов (NIST) конференции по оценке систем текстового поиска (TREC – text retrival evaluation conference)*. Начавшаяся в 1992 году консорциумом из 25 групп, к 12 году своего существования конференция накопила значительный материал, на котором до сих пор оттачиваются поисковые системы. К каждой очередной конференции готовится новый материал (так называемая «дорожка») по каждому из интересующих направлений. «Дорожка» включает коллекцию документов и запросов. Приведу примеры: — Дорожка произвольных запросов (ad hoc) – присутствует на всех конференциях — Многоязычный поиск — Маршрутизация и фильтрации — Высокоточный поиск (с единственным ответом, выполняемый на время) — Взаимодействие с пользователем — Естестственно-языковая «дорожка» — Ответы на «вопросы» — Поиск в «грязных» (только что отсканированных) текстах — Голосовой поиск — Поиск в очень большом корпусе (20GB, 100GB и т. д.) — WEB корпус (на последних конференциях он представлен выборкой по домену .gov) — Распределенный поиск и слияние результатов поиска из разных систем * Материалы конференции публично доступны по адресу trec.nist.gov/pubs.html. Не только поиск Как видно из «дорожек» TREC, к самому поиску тесно примыкает ряд задач, либо разделяющих с ним общую идеологию (классификация, маршрутизация, фильтрация, аннотирование), либо являющихся неотъемлемой частью поискового процесса (кластеризация результатов, расширение и сужение запросов, обратная связь, «запросо-зависимое» аннотирование, поисковый интерфейс и языки запросов). Нет ни одной поисковой системы, которой бы не приходилось решать на практике хотя бы одну из этих задач. Лингвистика Немного в стороне от статистических моделей и структур данных стоит класс алгоритмов, традиционно относимых к лингвистическим. Точно границы между статистическими и лингвистическими методами провести трудно. Условно можно считать лингвистическими методы, опирающиеся на словари (морфологические, синтаксические, семантические), созданные человеком. Хотя считается доказанным, что для некоторых языков (например, для английского) лингвистические алгоритмы не вносят существенного прироста точности и полноты, все же основная масса языков требует хотя бы минимального уровня лингвистической обработки. Не вдаваясь в подробности, приведу только список задач, решаемых лингвистическими или окололингвистическими приемами: Поиск в вебе “Things that work well on TREC often do not produce good results on the web… Some argue that on the web, users should specify more accurately what they want and add more words to their query. We disagree vehemently with this position. If a user issues a query like «Bill Clinton» they should get reasonable results since there is a enormous amount of high quality information available on this topic” Пора вернуться к теме, с которой началась эта статья: что же изменилось в поисковых системах за последнее время? Прежде всего, стало очевидно, что поиск в вебе, не может быть сколько-нибудь корректно выполнен, будучи основан на анализе (пусть даже сколь угодно глубоком, семантическом и т. п.) одного лишь текста документа. Ведь внетекстовые (off-page) факторы играют не меньшую, а порой и бо?льшую роль, чем текст самой страницы. Положение на сайте, посещаемость, авторитетность источника, частота обновления, цитируемость страницы и ее авторов – все эти факторы невозможно сбрасывать со счета. Cтав основным источником получения справочной информации для человеческого вида, поисковые системы стали основным источником трафика для интернет-сайтов. Как следствие, они немедленно подверглись «атакам» недобросовестных авторов, желающих любой ценой оказаться в первых страницах результатов поиска. Искусственная генерация входных страниц, насыщенных популярными словами, техника клоакинга, «слепого текста» и многие другие приемы, предназначенные для обмана поисковых систем, мгновенно заполонили Интернет. Кроме проблемы корректного ранжирования, создателям поисковых систем в Интернете пришлось решать задачу обновления и синхронизации колоссальной по размеру коллекции с гетерогенными форматами, способами доставки, языками, кодировками, массой бессодержательных и дублирующихся текстов. Необходимо поддерживать базу в состоянии максимальной свежести (на самом деле достаточно создавать иллюзию свежести – но это тема отдельного разговора), может быть учитывать индивидуальные и коллективные предпочтения пользователей. Многие из этих задач никогда прежде не рассматривались в традиционной науке информационного поиска. Для примера рассмотрим пару таких задач и практических способов их решения в поисковых системах для интернета. Качество ранжирования Не все внетекстовые критерии полезны в равной мере. Именно ссылочная популярность и производные от нее оказались решающим фактором, поменявшим в 1999-2000 годах мир поисковых систем и вернувшим им преданность пользователей. Так как именно с ее помощью поисковые системы научились прилично и самостоятельно (без подпорок из вручную отредактированных результатов) ранжировать ответы на короткие частотные запросы, составляющие значительную часть поискового потока. Качество индекса Хотя размер базы в интернете на поверхностный взгляд не кажется критическим фактором, это не так. Недаром рост посещаемости таких машин, как Google и Fast, хорошо коррелирует именно с ростом их баз. Основная причина: «редкие» запросы, то есть те, по которым находится менее 100 документов, составляют в сумме около 30% от всей массы поисков – весьма значительную часть. Этот факт делает размер базы одним из самых критичных параметров системы. Очевидно, что так можно определять процент перекрытия текстов, выявлять все его источники и т.п. Этот изящный алгоритм воплотил давнюю мечту доцентов: отныне мучительный вопрос «у кого студент списывал этот курсовик» можно считать решенным! Легко оценить долю плагиата в любой статье. (В том числе и в данной; надеюсь, что 0%; можете проверить.) Чтобы у читателя не создалось впечатление, что информационный поиск исключительно западная наука, упомяну про альтернативный алгоритм определения почти-дубликатов, придуманный и воплощенный у нас в Яндексе. В нем используется тот факт, что большинство поисковых систем уже обладают индексом в виде инвертированного файла (или инвертированным индексом), и этот факт удобно использовать в процедуре нахождения почти-дубликатов. Цена одного процента Архитектурно современные поисковые системы представляют собой сложные многокомпьютерные комплексы. Начиная с некоторого момента по мере роста системы основная нагрузка ложится вовсе не на робота, а на поиск. Ведь в течение секунды приходят десятки и сотни запросов. Список литературы Modern Information Retrieval Источник: habr.com Комментарии: |
|||