Курс "Информационный поиск"

Курс поддержан грантом фонда "Династия".

Архив курса в ИТМО

Лектор: Павел Браславский

Контакты:
электронная почта: pbras [эт] яндекс [точка] ру, тема [ir_spb]
рассылка: http://bit.ly/iir2014

Курс состоит из лекций, практических занятий и семинаров. Четыре блока лекций: февраль 20-21, март 13-14, апрель 10-11, май 22-23. По две пары в день, начало: пт. 13.40, сб. 9.30. Лекции проходят на матмехе СПбГУ (Петергоф, Университетский проспект, 28), ауд. 405.

Критерии оценки

5 (отлично) -- выполнены и зачтены ВСЕ практические задания, контрольные, итоговая контрольная работа, активная работа на семинарах.
4 (хорошо) -- аналогично 5, но есть замечания к выполнению практических заданий, отчетам, контрольным работам и работе на семинаре.
3 (удовлетворительно) -- сделаны все практические задачи, по ним предоставлены отчеты. На основании отчетов, результатов контрольных работ и участия/неучастия в семинарах можно сделать вывод, что нет хорошего понимания содержания выполненных заданий и лекционного материала.

Ведомость.

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

Как улучшить оценку? Принимать активное участие в решение задач на семинарах, писать контрольные, делать доклады по результатам выполнения практических заданий, участвовать в обсуждении вопросов, возникающих у коллег по курсу в процессе выполнения практик (можно отмечаться в списке вопросов к семинару).

Расписание

Программа курса

Блок 1 (20-21 февраля)
  1. Cовременный информационный поиск: краткое введение. Прямой поиск и поиск по индексу. Матрица "термин-документ" и инвертированный индекс . Словарь и списки словопозиций. Булев поиск, обработка булевых запросов. Фразовые запросы, запросы с расстояниями. Биграммный индекс, координатный индекс.
  2. Основные этапы построения индекса. Выделение лексем, стоп-слова, нормализация терминов. Лингвистическая обработка. Распределенное построение индекса: MapReduce.
  3. Русская морфология для задач информационного поиска. Стемминг и лемматизация. Нормализация терминов на основе правил и статистики; данные для морфологического анализа. Существующие библиотеки морфологического анализа для русского языка.
  4. Законы Хипса и Ципфа. Модель векторного пространства. Частота по коллекции и документная частота. Подход tf*idf и его варианты. Обратная связь по релевантности.
ВИП: Гл. 1, Гл. 2, 3.1, 4.1, 4.2, 4.4, 5.1
Слайды авторов ВИП: 1, 2, 3, 4, 5.
Cлайды Джеффа Дина про MapReduce (2004)
Слайды ПБ: введение, морфология
Блок 2 (13-14 марта)
  1. Поиск с ранжированием. Взвешенное зонное ранжирование.
  2. Вероятностная модель информационного поиска. Приницп вероятностного ранжировнаия. Бинарная модель независимости. Okapi BM25.
  3. Языковые модели в информационном поиске. Сглаживание. Варианты сопоставления документа и запроса. Модели перевода.
  4. Оценка информационного поиска. Лабораторная парадигма. Релевантность. Коллекция, задания, метрики. Метрики на множестве документов: точность, полнота, F-мера. Метрики на ранжированном списке результатов: precision@k, MAP, 11-точечный график, R-precision, MRR, DCG, nDCG. Организация оценки. Согласованность оценок. Краудсорсинг.
  5. Согласие асессоров, каппа-статистика. Недостатки "лабораторной парадигмы" оценки информационного поиска. Использование кликов для оценки качества поиска ("переплетение" ранжированных списков, A/B тестирование).
ВИП: Гл. 6, 9, 11, 12, 8.
Слайды авторов ВИП: 1, 4, 5, 6.
Слайды про РОМИП
Блок 3 (10-11 апреля)
  1. Эффективный поиск. Сжатие словаря и индекса. Эффективное вычисление соответствия документа запросу: экономия на сортировке результатов; экономия на вычислении соответствия документа запросу (сортировка списков словопозиций, двухуровневые индексы, подход WAND и др.). Сокращение индекса (index pruning).
  2. Особенности веб-поиска, экономическая модель веб-поиска. Использование ссылочной структуры веба. Компактное представление веб-графа. Алгоритм PageRank.
  3. Машинное обучение ранжированию. Подходы и методы, доступные данные и библиотеки.
  4. Интерфейс информационно-поисковых систем. Представление результатов поиска: список результатов, сниппеты. Методы автоматического реферирования и другие подходы к генерации сниппетов, оценка качества сниппетов.
ВИП: 5, 7.1, 19.1-19.4, 20.4, 21.1, 21.2, 8.7.
Слайды авторов ВИП: 1, 2, 3, 4, 5, 6 (раздел "Results presentation").
Автоматическое реферирование и сниппеты, Search snippets evaluation @ Yandex
Слайды Игоря Кураленка
+см. ссылки внизу
Блок 4 (22-23 мая)
  1. Логи поисковых запросов: особенности данных, доступные коллекции. Обработка поисковых запросов: сегментация запросов, тематическая классификация запросов, нахождение близких запросов. Исправление опечаток в запросах. Запросы-вопросы.
  2. Жанры и другие нетематические признаки в задачах информационного поиска. Жанровая классификация, показатели удобочитаемости, применение в поиске. Определение автора документа, определение пола автора документа.
  3. (*)Тезаурусы в задачах информационного поиска и автоматической обработки текста.
ВИП: 15.3
Анализ запросов
Genres in IR

 

Практические задания

Задание 1. Морфологический анализ

Ознакомьтесь с морфологическими анализаторами (настройки, параметры, форматы входных и выходных данных):

Поэкспериментируйте с документами разных жанров: художественная литература, научные статьи, сообщения на форумах. Обратите внимание, как обрабатываются редкие слова, слова с опечатками, иностранные слова, имена собственные. Предложите методику оценки морфологического анализатора, сравните по этой методике любые два анализатора.

Результаты оформите в виде отчета (1-2 страницы PDF).

Задание 2. Анализ коллекции. Частотный словарь. Законы Хипса и Ципфа.

1) Постройте по данным BY.WEB таблицу, аналогичную таблицам 4.2 и 5.1 книги "Введение в информационный поиск". Обработанная коллекция: bit.ly/by_web

Данные, которые должны быть представлены в таблице:

  1. Количество документов
  2. Средний размер документа в байтах
  3. Средний размер документа в байтах после удаления разметки
  4. Средняя длина документа в словах
  5. Средняя длина слова в буквах
  6. Размер коллекции в словах
  7. Размер словаря коллекции (в т.ч. без чисел/после свертывания регистра/только слова из русских букв/после лемматизации)
  8. Словопозиции (в т.ч. без чисел/без стоп-слов/только слова из русских букв)

Стоп-слова раньше можно быть взять из дистрибутива Я.Сервера (stopword.lst), сейчас можно просто найти в сети, например здесь.

2) Постройте зависимость размера словаря от размера коллекции. Аппроксимируйте прямой в log-log координатах. Нарисуйте график. Постройте частотный словарь коллекции, зависимость частоты от ранга в словаре. Аппроксимируйте прямой в log-log координатах. Нарисуйте график. Проанализируйте результаты.

3) постройте граф гиперссылок между доменами, приведите список доменов с максимальным количеством входящих ссылок.

Задание 3. Индексирование коллекции BY.WEB

Проиндексировать коллекцию By.Web (см. описание формата) одним из поисковых "движков":

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

Задание 4. Оценка качества стандартного решения

  1. Получите результаты поиска по созданному индексу для запросов из списка (см. описание формата).
  2. На основе таблиц релевантности (бинарные оценки) для коллекции By.Web 2008 и 2009 годов рассчитайте метрики качества: p@10, MAP, R-precision, 11-точечный график, MRR.

Сравните оценки для

Для рассчета метрик можно перевести данные в формат TREC и воспользоваться скриптом trec_eval, см. описание.

Задание 5. Машинное обучение ранжированию на данных "Интернет-математики 2009"

Ознакомьтесь с задачей и форматом данных конкурса "Интернет-математика 2009". Постройте функцию ранжирования (см. ссылки на библиотеки ниже) на основе обучающего множества, примените ее к тестовым данным, загрузите решение. В отчете опишите методы, приведите ваши результаты со страницы рейтинга.

Задание 6. Машинное обучение ранжированию на данных РОМИП By.Web

Реализуйте вычисление и сохранение значений признаков (features) в индексе для пар "запрос-документ", которые могут быть полезным сигналом для ранжирования (в качестве примера см. список стандартных признаков коллекции LETOR). Используйте оценки релевантности пар "запрос-документ" для коллекции By.Web 2008 года для обучения функции ранжирования; оценки 2009 года -- для тестирования. Вычислите значений метрик качества поиска (см. задание 5), сравните со стандартным решением. (См. ссылки на библиотеки ранжирования ниже.)

 

Литература

Основная книжка:

Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schutze, Introduction to Information Retrieval, Cambridge University Press. 2008. http://nlp.stanford.edu/IR-book/; курс авторов (вкл. слайды и ссылки)

Русский перевод: http://www.williamspublishing.com/Books/978-5-8459-1623-5.html

Дополнительно:

Ian H. Witten, Alistair Moffat, and Timothy C. Bell Managing Gigabytes: Compressing and Indexing Documents and Images, Morgan Kaufmann Publishing, 1999. http://www.cs.mu.oz.au/mg/

Ricardo Baeza-Yates, Berthier Ribeiro-Neto Modern Information Retrieval: The Concepts and Technology behind Search, 2/E Addison-Wesley, 2011 [на амазоне]

W. Bruce Croft, Donald Metzler, Trevor Strohman. Search Engines: Information Retrieval in Practice, 2009. http://www.search-engines-book.com/

Ссылки

 

Адрес этого документа: http://www.kansas.ru/ir_spb/index.html

Последнее изменение 11.06.2015