Cambridge University Press, 2008. — 504 p. — ISBN 978-0-521-86571-5.Язык: EnglishВведение в информационный поиск — это первый учебник, в котором наряду с классическим поиском рассматриваются веб-поиск, а также классификация и кластеризация текстов. Учебник написан с точки зрения информатики и содержит современное изложение всех аспектов проектирования и реализации систем сбора, индексирования и поиска документов, методов оценки таких систем, а также введение в методы машинного обучения на базе коллекций текстов.
Несмотря на то что учебник задуман как вводный курс по информационному поиску, он будет интересен исследователям и профессионалам.Об авторах
Кристофер Д. Маннинг (Christofer D. Manning) — профессор компьютерных наук в Станфордском университете (Stanford University).
Прабхакар Рагхаван (Prabhakar Raghavan) — директор департамента Yahoo! Research и профессор-консультант по компьютерным наукам Станфордского университета.
Хайнрих Шютце (Hinrich Schutze) — заведующий кафедрой теоретической вычислительной лингвистики Института обработки текстов на естественных языках (Университет Штутгарта).Class-tested and coherent, this groundbreaking new textbook teaches web-era information retrieval, including web search and the related areas of text classification and text clustering from basic concepts. Written from a computer science perspective by three leading experts in the field, it gives an up-to-date treatment of all aspects of the design and implementation of systems for gathering, indexing, and searching documents; methods for evaluating systems; and an introduction to the use of machine learning methods on text collections. All the important ideas are explained using examples and figures, making it perfect for introductory courses in information retrieval for advanced undergraduates and graduate students in computer science. Based on feedback from extensive classroom experience, the book has been carefully structured in order to make teaching more natural and effective. Although originally designed as the primary text for a graduate or advanced undergraduate course in information retrieval, the book will also create a buzz for researchers and professionals alike.Introduction to Information Retrieval: Table of ContentsFront matter (incl. table of notations)Boolean retrieval - слайды Булев поиск - /file/334693/The term vocabulary & postings lists - слайды Лексикон и списки словопозиций - /file/334715/Dictionaries and tolerant retrieval - слайды Словари и нечеткий поиск - /file/334725/
Index construction - слайды Построение индекса - /file/334735/Index compression - слайды Сжатие индекса - /file/334744/Scoring, term weighting & the vector space modelComputing scores in a complete search system
Evaluation in information retrievalRelevance feedback & query expansionXML retrievalProbabilistic information retrievalLanguage models for information retrieval
Text classification & Naive BayesVector space classificationSupport vector machines & machine learning on documentsFlat clusteringHierarchical clusteringMatrix decompositions & latent semantic indexingWeb search basicsWeb crawling and indexesLink analysisBibliography & IndexПредисловие авторов книги к русскому изданию
Мы рады предоставленной возможности написать краткое предисловие к русскому изданию книги Introduction to Information Retrieval. Поскольку оригинальное издание вышло в 2008 году, важность поиска по текстовым и другим неструктурированным информационным источникам к текущему моменту еще больше возросла. Этот поиск важен и как техническая задача, и как главная часть социального и делового взаимодействия людей в современном информационном мире. Прошедший период представляет собой захватывающий период широкого распространения блогов, микроблогов и социальных сетей, а также все более широкого применения инструментов, использующих методы машинного обучения и более глубокую интерпретацию текстов.В частности, в России это было восхитительное и, вероятно, поворотное время появления успешных компаний, занимающихся веб-поиском, оптическим распознаванием символов и автоматической обработкой текста. Кроме того, за прошедшее время активизировалась организационная и академическая деятельность. Мы хотели бы отметить, в частности, семинар РОМИП, упомянутый в главе 8, который организовал форум по оценке методов информационного поиска в русскоязычных источниках (http://romip.ru/), аналогичный конференциям TREC, а также недавно организованную Российскую летнюю школу по информационному поиску. Мы надеемся, что публикация этой книги будет способствовать дальнейшему развитию методов информационного и веб-поиска в русскоязычном мире.Предисловие редакторов перевода
Информационный поиск, родившись на стыке библиотечного дела и информатики
в середине XX века, некоторое время оставался скромной научной и прикладной областью, в которой работало небольшое количество ученых. Бурный рост интернета в конце прошлого — начале нынешнего века стал мощнейшим стимулом развития дисциплины.
Современный информационный поиск — это миллионы пользователей, огромные объемы данных, мощные вычислительные системы, изощренные алгоритмы. Для решения
изначальной задачи — поиска информации, соответствующей потребности пользователя, — привлекаются методы машинного обучения, анализа мультимедийной информации, компьютерная лингвистика, геоинформационные сервисы, исследуется психология
пользователей и их социальные связи, удобство интерфейсов и т. д.
Создание учебника для такой динамичной и разносторонней дисциплины становится
очень сложной задачей. Кристофер Маннинг, Прабхакар Рагхаван и Хайнрих Шютце с
этой задачей прекрасно справились. Книга представляет собой сбалансированное, последовательное и основательное введение в предметную область. До книги Введение в информационный поиск, оригинальное издание которой вышло в 2008 году, основными
учебниками по информационному поиску были книги 1999 года: Witten et al. , Managing
Gigabytes и Baeza-Yates и Ribeiro-Neto, Modern Information Retrieval (см библиографию).
С русскоязычной учебной и профессиональной литературой по информационному поиску дело обстояло намного хуже. За исключением отдельных вузовских учебных пособий
и переводных изданий узкоприкладного характера, основательных книг по информаци-
онному поиску на русском языке не выходило с начала 80-х годов прошлого века.
Благодаря интернет-магазинам не составляет большого труда стать обладателем
оригинального английского издания, к тому же электронная версия книги свободно доступна по адресу http://www.informationretrieval.org/. Несмотря на это, мы
считаем, что издание книги на русском языке — важное и полезное дело. Русская версия
призвана упросить знакомство с информационным поиском всем заинтересованным —
студентам, аспирантам, исследователям и инженерам-практикам. Профессионалам, работающим в этой области, книга поможет структурировать их знания и послужит аннотированным библиографическим указателем. Еще одна важная задача книги — зафиксировать (а иногда и ввести в оборот) русскую терминологию по информационному поиску.
Отсутствие профессиональной литературы по информационному поиску в течение долгого времени обусловило сложности, с которыми мы столкнулись в процессе перевода.
При переводе терминологии мы старались по возможности использовать устоявшиеся математические термины, термины, принятые в отечественной информатике (computer
science), и те, что стали общепринятыми в практике разработки поисковой системы Яндекс, а также в рамках Российского семинара по оценке методов информационного поиска (РОМИП, http://romip.ru). При переводе мы искали не просто понятные, но и
по возможности однозначные и непротиворечивые варианты терминов. Поэтому, например, в книге везде, где только можно, dictionary (структура данных) переводится как словарь, а vocabulary — как лексикон, proximity — близость, а similarity — сходство. Также мы старались использовать устоявшуюся терминологию из других наук, например из
биологии, в тех случаях, когда она существует (например, capture-recapture — метод повторного захвата). Многие члены сообщества ru_ir в Живом Журнале откликнулись на наш призыв поучаствовать в коллективном переводе предметного указателя книги на
сайте translated.by, за что мы им очень благодарны.
Мы не стали переводить примеры на русский язык, для этого их пришлось бы слишком сильно переработать. Мы надеемся, что читатель сможет воспользоваться пояснениями в тексте, да и точного понимания текста примеров для понимания работы алгоритмов и методов, как правило, не требуется.
Наконец, мы взяли на себя смелость снабдить текст комментариями не только для
указания эквивалентных русских источников, если они имеются, и комментариев по выбору терминологии, но и в случаях, когда наш опыт разработчиков веб-поиска и исследователей позволял дополнить оригинальный текст (в некоторых случаях это происходило из-за специфики русскоязычного поиска).
Мы хотим поблагодарить тех, кто принял участие в переводе терминологии и прислал свои предложения и замечания по тексту: Андрей Белов, Леонид Бойцов, Константин Воронцов, Максим Захаров, Юрий Зеленков, Евгений Кирпичев, Константин Коломеец, Наташа Лауфер, Лидия Пивоварова, Денис Расковалов, Григорий Сапунов, Александр Сигачёв, Павел Уваров, Евгений Харитонов.
Мы рады отметить, что интерес к информационному поиску в России растет. В качестве точек кристаллизации такого интереса можно назвать семинар РОМИП, серию
летних школ RuSSIR (http://romip.ru/russir2010/), Школу анализа данных
Яндекса (http://shad.yandex.ru/), сообщество Информационный поиск (http: //
community.livejournal.com/ru_ir/). Вопросы информационного поиска обсуждаются на конференциях Электронные библиотеки (http://rcdl.ru/) и Диалог
(http://www.dialog-21.ru/). Надеемся, что эта книга поможет развитию информационного поиска — научной и прикладной дисциплины — в России и ближнем зарубежье.
Мы благодарим ООО Яндекс за поддержку русского издания книги.
Павел Браславский
Дмитрий Клюшин
Илья СегаловичПредисловие
Еще в 1990-х годах результаты социологических исследований свидетельствовали о
том, что большинство людей предпочитают получать информацию от других людей, а не
с помощью информационно-поисковых (Information Retrieval — IR) систем. Например,
в то время для бронирования билетов и гостиниц люди чаще обращались к сотрудникам
туристических агентств. Однако за последние десять лет благодаря постоянному совершенствованию методов информационного поиска поисковые системы в вебе поднялись на новый качественный уровень, позволяющий лучше удовлетворять потребности все большего количества людей, а веб-поиск стал стандартным и часто предпочтительным механизмом поиска информации. Например, в 2004 году опрос Pew Internet Survey (Fallows, 2004) показал, что 92% пользователей сети Интернет считают ее удобной для получения повседневной информации. К удивлению многих, информационный поиск из преимущественно академической дисциплины стал базисом для средств доступа к информации, на который полагается большинство людей. В книге изложены научные основы этой дисциплины на уровне, доступном как студентам старших курсов университетов, так и способным студентам младших курсов.
Информационный поиск возник раньше веба. Его эволюция стимулировалась разнообразными проблемами, связанными с обеспечением поиска и доступа к информационным источникам. Сначала информационный поиск касался научных публикаций и библиотечных каталогов, однако вскоре он распространился и на другие сферы, в которых важна роль информации, — на журналистику, право и медицину. Многие исследования в области информационного поиска проводились именно в этом контексте, и до сих пор большая доля практических приложений этой дисциплины связана с обеспечением доступа к неструктурированной информации, хранящейся в многочисленных корпоративных и правительственных базах данных. Именно этим методам посвящена большая часть книги.
Тем не менее в последние годы основным двигателем прогресса является веб, открывший возможность публиковать информацию десяткам миллионов пользователей.
Эта лавина публикаций осталась бы недоступной, если бы информацию было невозможно найти, сопроводить аннотацией и проанализировать так, чтобы каждый пользователь
мог быстро найти необходимые ему релевантные и исчерпывающие сведения. В конце
1990-х годов многие люди поняли, что дальнейшая индексация всего веба вскоре станет
невозможной из-за его экспоненциального роста. Однако значительные научные инновации и превосходные инженерные решения, быстро снижающаяся стоимость компьютерного аппаратного обеспечения и появление коммерческой заинтересованности в веб-поиске в совокупности способствовали возникновению крупных поисковых систем, способных с высоким качеством и за доли секунды выполнить сотни миллионов запросов в день по базе, состоящей из миллиардов веб-страниц.Структура книги и учебного курса
Книга является результатом объединения нескольких учебных курсов, прочитанных в Стэнфордском университете (Stanford University) и Штутгартском университете
(University of Stuttgart) в разных вариантах: на протяжении одной четверти, одного семестра и двух четвертей. Эти курсы предназначались для старшекурсников, изучавших
компьютерные науки, но оказались полезными и для студентов младших курсов, а также
для студентов, осваивавших юриспруденцию, медицинскую информатику, статистику,
лингвистику и разнообразные технические дисциплины. Книга организована так, чтобы
осветить то, что мы считаем важным для студентов, изучающих информационный поиск
на протяжении одного семестра. Кроме того, каждая глава содержит материал одной
лекции продолжительностью 75–90 минут.
Главы 1–8 посвящены основам информационного поиска и, в частности, сущности
поисковых систем; мы считаем, что этот материал является ядром любого курса по ин-
формационному поиску. В главе 1 введены инвертированные индексы (inverted indexes)
и показано, как с их помощью можно обработать простые булевы запросы (Boolean
queries). В главе 2 детально описываются способы предварительной обработки докумен-
тов перед индексированием и методы усовершенствования индексов для расширения
функциональных возможностей и повышения скорости поиска. В главе 3 рассматриваются
поисковые структуры для словарей и методы обработки запросов, содержащих орфографические ошибки и другие неточности. В главе 4 описывается несколько алгоритмов построения инвертированного индекса по коллекции текстов с особым акцентом на масштабируемые и распределенные алгоритмы, допускающие применение к очень большим коллекциям. В главе 5 излагаются методы сжатия словарей и инвертированных индексов. Эти
методы очень важны для обеспечения быстрой (за доли секунды) обработки пользовательских запросов в больших поисковых системах. Индексы и запросы, изучаемые в главах 1–5, касаются лишь булева поиска (Boolean retrieval), при котором документ либо соответствует запросу, либо нет. Желание измерить степень соответствия документа запросу, или релевантность (score) документа, стимулировало разработку методов взвешивания терминов (term weighting) и ранжирования (computation of scores), описанных в главах 6 и 7, и далее, к концепции списка документов, упорядоченных по степени соответствия запросу.
Глава 8 посвящена оценке информационно-поисковых систем на основании экспертных
оценок релевантности найденных документов, что позволяет сравнивать относительное качество систем на стандартных коллекциях документов и запросов.
Главы 9–21 основаны на материале, изложенном в главах 1–8, и охватывают широкий
спектр более сложных тем. В главе 9 обсуждаются методы повышения эффективности
поиска с помощью таких приемов, как обратная связь по релевантности (relevance
feedback) и расширение запросов (query expansion), предназначенных для увеличения вероятности нахождения релевантных документов. В главе 10 рассматриваются методы
информационного поиска по документам, структурированным с помощью языков раз-
метки, таких как XML и HTML. Мы сводим поиск по структурированным документам к
применению методов ранжирования на основе векторной модели (vector space scoring),
изложенных в главе
6. В главах 11 и 12 для ранжирования документа по отношению к
запросу используется теория вероятностей. Глава 11 посвящена традиционному вероятностному информационному поиску, позволяющему вычислить вероятность релевантности документа при заданном наборе слов запроса. Впоследствии эту вероятность можно использовать как показатель релевантности при ранжировании. В главе 12 иллюстрируется альтернатива, в рамках которой для каждого документа в коллекции создается языковая модель, позволяющая оценить вероятность того, что она порождает заданный запрос. Эта вероятность является еще одним количественным показателем, с помощью которого осуществляется ранжирование документов.
В главах 13–18 излагаются методы машинного обучения и численные методы информационного поиска. Главы 13–15 посвящены проблеме классификации документов
по известным категориям на основе набора документов и классов, которым они принадлежат. В главе 13 представлены доказательства того, что классификация на основе статистики представляет собой одну из ключевых технологий, необходимых для успешного функционирования поисковой системы. В ней излагается наивный байесовский подход (Naive Bayes), представляющий собой концептуально простой и эффективный метод классификации текстов, а также основы стандартной методологии оценки текстовых классификаторов. В главе 14 описано применение модели векторного пространства, введенной в главе 6, а также изложены два метода классификации: метод Роккио (Rocchio method) и метод k ближайших соседей (k nearest neighbor — kNN), применяемые к векторам документов. В ней также рассматривается компромисс между смещением и разбросом (дисперсией), представляющий собой важную характеристику задач обучения и позволяющий установить критерии для выбора подходящего метода классификации текстов. В главе 15 вводится метод опорных векторов (support vector machine), который многие исследователи в настоящее время считают наиболее эффективным методом классификации текстов. Кроме того, в данной главе исследуются связи между задачей классификации и, на первый взгляд, совершенно посторонними темами, таким как вывод функций ранжирования по набору обучающих примеров.
Главы 16–18 посвящены идентификации кластеров близких документов в коллекции.
В главе 16 сначала приводится обзор нескольких важных приложений кластеризации в
области информационного поиска,
