Information Retrieval

Страница курса по информационному поиску в Высшей школе ИТИС КФУ

Основы информационного поиска (Весна 2016)

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

Преподаватели

Никита Жильцов - лекции
Владислав Бойко - практика

Слайды

  1. Лекция 1: Основы информационного поиска, структура инвертированного индекса [Слайды]
  2. Лекция 2: Алгоритмы индексирования, сжатие индекса [Слайды]
  3. Лекция 3: Ранжирование в векторной модели документа [Слайды]
  4. Лекция 4: Вероятностные модели поиска и языковое моделирование [Слайды]
  5. Лекция 5: Оценивание результатов поиска [Слайды]
  6. Лекция 6: Машинное обучение ранжированию [Слайды]
  7. Лекция 7: Ранжирование структурированных документов [Слайды]

  1. Практика 1: Знакомство с Elastic Search [Слайды]
  2. Практика 2: Поисковые команды [Слайды]

Программа экзамена

  1. Основные компоненты инвертированного индекса
  2. Алгоритмы пересечения словопозиций: основной, общий, с пропусками
  3. Координатный индекс: структура, алгоритм пересечения словопозиций
  4. Блочное индексирование, основанное на сортировке
  5. Однопроходное индексирование в оперативной памяти
  6. Распределенное индексирование с MapReduce
  7. Законы Хипса и Ципфа
  8. Способы хранения словаря без сжатия: массив, строка, блок
  9. Сжатие словаря фронтальным кодированием
  10. Сжатие словопозиций кодированием переменной длины
  11. Сжатие словопозиций: гамма коды
  12. Векторная модель документа: взвешивание по TF-IDF
  13. Ранжирование в векторной модели документа (формула косинуса, базовый алгоритм)
  14. Опорная нормировка по длине документа
  15. Бинарная модель независимости: вывод функции ранжирования
  16. Бинарная модель независимости: оценки по методу максимального правдоподобия
  17. Бинарная модель независимости: оценивание через обратную связь по релевантности
  18. BM25: смесь пуассоновских распределений, формула ранжирования
  19. Языковые модели: определение, пример, применение для поиска
  20. Языковые модели: оценка по методу максимального правдоподобия, сглаживание Елинека-Мерсера, сглаживание Дирихле
  21. Меры оценивания качества без ранжирования. Кривая точность-полнота
  22. Средняя точность по 11 точкам. Макроусредненная средняя точность (mean average precision, MAP)
  23. Нормированная дисконтированная совокупная выгода (normalized discounted cumulative gain, NDCG)
  24. Постановка задачи машинного обучения ранжированию. Три подхода: поточечный, попарный, списочный
  25. Метод опорных векторов: линейная разделимость классов, опорные векторы, линейный классификатор
  26. Метод опорных векторов: геометрический зазор, задача оптимизации
  27. Метод опорных векторов: классификация с мягким зазором
  28. Метод опорных векторов для ранжирования (Ranking SVM)
  29. BM25F: некорректная и корректная комбинация весов полей
  30. MLM: смесь вероятностных языковых моделей
  31. PRMS (Probabilistic retrieval model for semi-structured data)

Тестовые коллекции

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

  1. Необходимо составить списки стоп-слов на основе статистики терминов в коллекции по трем разным коллекциям документов. Стоп-словами будут считаться 5% самых частотных и 5% наименее частотных (по документной частоте, document frequency=df) терминов из индекса. Предобработка коллекции должна включать основные операции, такие как перевод в нижний регистр и стемминг.
  2. Для данной коллекции построить графики распределений, иллюстрирующие законы Ципфа и Хипса. Графики должны содержать кривые, построенные по коллекции, и прямые, параметризуемые этими законами и построенными с помощью метода наименьших квадратов.
  3. Реализовать сжатие словаря фронтальным кодированием. В реализуемой структуре данных для каждого термина должны храниться значения документной частоты, указатели на списки словопозиций, указатели терминов. Необходимо реализовать поиск термина (term lookup): по данному термину найти его документную частоту. Апробировать на тестовой коллекции.
  4. Реализовать сжатие файла словопозиций кодированием переменной длины (variable byte encoding). Апробировать на тестовой коллекции.
  5. Реализовать вариант функции ранжирования tf-idf - модель с опорной нормировкой (pivoted document length normalization). модель с опорной нормировкой, где D - документ, Q - запрос, tf(t,D) - частота термина t в документе D, |D| - длина документа D, avdl - средняя длина документа, tf(t,Q) - частота термина t в запросе, N - количество документов в коллекции, df(t) - документная частота термина t, s - параметр в диапазоне [0,1]. Апробировать на тестовой коллекции.
  6. Реализовать варианты функции ранжирования tf-idf с разным масштабированием документной частоты. См. рис.
    масштабирование документной частотности
    Апробировать на тестовой коллекции.
  7. Реализовать языковую модель, основанную на линейной интерполяции (сглаживание Елинека-Мерсера), при которой вероятность сгенерировать термин t из документа d оценивается как смесь (линейная комбинация) распределений вероятностей термина по документу и по коллекции. См. формулу.
    языковая модель, основанная на линейной интерполяции
    Апробировать на тестовой коллекции.
  8. Реализовать подсчет основных мер оценивания: точность на уровне k (P@k), макроусредненная средняя точность на уровне k (MAP@k), mean reciprocal rank (MRR). Протестировать результаты можно с помощью коллекции CACM или DBpedia (см. п. "Тестовые коллекции") и оценок релевантности (relevance judgments), генерируя поисковую выдачу случайным образом смешивая релевантные и неоцененные результаты (эмуляция некоторой другой функции ранжирования). Сравнить полученные оценки с результатами инструмента оценивания от TREC: trec_eval.
  9. Провести оптимизацию параметра регуляризации (C) линейной модели обучения ранжированию SVM-rank (linear kernel) в схеме пятиблочного скользящего контроля (5-fold cross validation). В качестве тестовой коллекции можно взять DBpedia (см. п. "Тестовые коллекции") с оценками релевантности. В качестве целевой меры - усредненную среднюю точность (MAP@k). Привести оценки качества поиска для разных параметров с макроусреднением по 5 блокам. Меры оценивания можно считать с помощью инструмента trec_eval. Признаки - на свое усмотрение (примеры: косинусная мера, длина документа в лексемах, длина запроса, значение BM25 и т.п.)

Оценка

Части курса Баллы Дата сдачи
Практические задания 30% 2 апреля
Проект 20% 6 апреля (группы 201, 202, 203) и
9 апреля (группы 204, 205, 207)
Экзамен 50% 16 апреля в 10.00, ауд. 1310 (группы 201, 202); 20 апреля в 15.20, ауд. 108 (группы 203, 204); 23 апреля в 10.00, ауд. 1310 (группы 205, 207)
Студенты, получившие не менее 45 баллов за практические задания и проект, получают экзамен (50 баллов) автоматом.

Рекомендованная литература

  1. К. Маннинг, П. Рагхаван, Х.Шютце. Введение в информационный поиск. Пер. с англ. - М.: ООО "И.Д. Вильямс", 2011. - 528 с. (Основной учебник).
  2. Tie-Yan Liu. Learning to Rank for Information Retrieval. Springer, 2011.
  3. S. Amit, C. Buckley, M. Mitra. Pivoted document length normalization // In Proc. SIGIR, pp. 21–29. ACM Press. (1996) URL: http://dspace.library.cornell.edu/bitstream/1813/7217/1/95-1560.pdf.
  4. J. Zobel, A. Moffat. Exploring the similarity space // ACM SIGIR Forum. Vol. 32. No. 1. ACM, 1998. URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.18.6193&rep=rep1&type=pdf
  5. S. Robertson, S. Walker. Some simple effective approximations to the 2-poisson model for probabilistic weighted retrieval // Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval. Springer-Verlag. New York, Inc., 1994. URL: http://nclt.computing.dcu.ie/~gjones/Teaching/CA437/p232.pdf
  6. M. Smucker, J. Allan, and B. Carterette. A Comparison of Statistical Significance Tests for Information Retrieval Evaluation // In Proceedings of the 16th ACM CIKM, pages 623–632, 2007. URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.366.7734&rep=rep1&type=pdf
  7. Robertson, S., Zaragoza, H., Taylor, M. Simple BM25 extension to multiple weighted fields. Proceedings of the thirteenth ACM international conference on Information and knowledge management. - ACM.- 2004.
  8. Ogilvie, P., J. Callan. Combining document representations for known-item search. Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval.- ACM.- 2003.
  9. J. Kim, X. Xue, and W. B. Croft. A probabilistic retrieval model for semistructured data. Advances in Information Retrieval. Springer Berlin Heidelberg.- 2009.- P.228-239.

    10. Идеи для проектов

    Приложения

    1. Вертикальный поиск по сайту нашего университета: подразделение (см. список), сотрудники (пример страницы), конкурсы/программы/гранты (см. страницу). Система должна автоматически определять тип запрашиваемой страницы в запросе по ключевым словам. Пример эвристики - если в запросе упоминается имя, возвращать релевантные страницы о сотруднике (а не произвольные страницы, на которых упоминается данное имя).
    2. Отслеживание товара (задается ключевыми словами, например, "телевизор большая диагональ") в агрегаторе Яндекс.Маркет. Индекс периодически обновляется. Учесть свежесть результатов при ранжировании.
    3. Поиск по пабликам КФУ и ИТИСа ВКонтакте: по упоминаниям людей в сообщениях, авторам сообщений и тексту сообщения (например, "петя иванов студвесна"). Можно использовать API ВКонтакте. Выделять термины в запросе, обозначающие имя, и придать им больший вес в ранжирующей функции.
    4. Поиск твитов (см. Twitter API). Придумать новую ранжирующую функцию, которая бы учитывала: появление ключевого слова как обычного слова, упоминания пользователя и в виде хэштэга; нормализацию по длине. Кроме того, обратить внимание на предобработку - разбиение на лексемы.
    5. Поиск упоминаний компаний в новостях. Можно взять RSS ленту с пресс-релизами о компаниях, например, Firrma. На стадии индексирования компании можно выделять из некоторого готового словаря (возможно, с алиасами - эквивалентными наименованиями, например, "Российские технологии"="Ростех"). В поисковом интерфейсе вводятся ключевые слова, обозначающие компанию, и, возможно, уточняющие термины (например, "ростех выручка"). Система возвращает релевантные новости. Учесть различное взвешивание терминов в запросе.

    Темы исследований

    1. Провести сравнительную экспериментальную оценку различных ранжирующих функций на основе разных вариантов взвешивания TF-IDF для некоторых тестовых коллекций (как минимум две). Взять в качестве основы (baseline) - классическую схему взвешивания TF-IDF. Привести значения основных мер оценивания (MAP@100, P@10, P@20, MRR, NDCG@100) и процент относительного улучшения по сравнению с основой. Посчитать статистическую значимость по тесту Фишера. Сделать выводы.
    2. Провести аналогичное исследование (см. 1). Сравнить только BM25 и query likelihood language model (Dirichlet smoothing). Оптимизировать параметры модели BM25 в схеме пятиблочного скользящего контроля. Сделать выводы.
    3. Придумать статические и динамические характеристики документов (см. Лекция 3). Исследовать их значимость (в смысле качества поисковых результатов) по схеме leave-one-out для модели обучения ранжированию SVM-rank. Привести результаты, как минимум, на двух тестовых коллекциях. Сделать выводы.

    Баллы

    NB. Для студентов, набравших 100 баллов и заинтересованных в летней стажировке в проектах Quest.ai или Textocat: отправляйте свои запросы на собеседование вместе с резюме по адресу nzhiltsov {at} textocat {dot} com.