Информационный поиск осень 2019

Материал из CSC Wiki
Перейти к:навигация, поиск

Важные ссылки

Преподаватель: Павел Браславский pbras@yandex.ru

Почта для отчетов по практическим заданиям: ir2019assignments@googlegroups.com

Таблица с результатами

Рассылка

Чат в телеграме

Класс на Stepik

Полезные ссылки

CS 276 / LING 286: Information Retrieval and Web Search @ Stanford

Ноутбук для второй домашки

Python base64-decoder

Beautiful Soup for Python

mystem for Python

Лекции

  1. Современный информационный поиск: краткое введение. слайды, SIGIR2019 keynote by W. Bruce Croft
  2. Основы поиска. Прямой поиск и поиск по индексу. Матрица "термин-документ" и инвертированный индекс. Словарь и списки словопозиций. Булев поиск, обработка булевых запросов. Фразовые запросы, запросы с расстояниями. Биграммный индекс, координатный индекс. CS276 slides
  3. Первые этапы построения индекса. Выделение лексем, стоп-слова, нормализация терминов. Морфологическая обработка: стемминг и лемматизация. Законы Хипса и Ципфа. слайды
  4. Поиск с ранжированием. Взвешенное зонное ранжирование. Модель векторного пространства. Частота по коллекции и документная частота. Подход tf*idf и его варианты. Обратная связь по релевантности. CS276 slides
  5. Вероятностная модель информационного поиска. Принцип вероятностного ранжирования. Бинарная модель независимости. BM25. SEIRiP slides
  6. Языковые модели в информационном поиске. Сглаживание. Варианты сопоставления документа и запроса. SEIRiP slides
  7. Использование ссылочной структуры веба в поиске. Алгоритм PageRank. CS276 slides
  8. Оценка информационного поиска. Лабораторная парадигма. Релевантность. Коллекция, задания, метрики. Метрики на множестве документов: точность, полнота, F-мера. Метрики на ранжированном списке результатов: precision@k, MAP, 11-точечный график, R-precision, MRR, DCG, nDCG. Организация оценки. Согласованность оценок. Краудсорсинг. Согласие асессоров, каппа-статистика. Использование кликов для оценки качества поиска ("переплетение" ранжированных списков, A/B тестирование).
  9. Машинное обучение ранжированию. Подходы и методы, доступные данные и библиотеки.
  10. Эффективное индексирование и поиск. Распределенное построение индекса: MapReduce. Сжатие словаря и индекса. Эффективное вычисление соответствия документа запросу: экономия на сортировке результатов; экономия на вычислении соответствия документа запросу (сортировка списков словопозиций, двухуровневые индексы, подход WAND и др.). Сокращение индекса (index pruning).
  1. Вопросно-ответный поиск.
  2. Интерфейсы информационно-поисковых систем. Представление результатов поиска: список результатов, сниппеты. Методы генерации сниппетов, оценка качества сниппетов. Эксперименты с участием пользователей.

Тесты

Морфология: 1, 2, 3, 4

Булев поиск и координатный индекс (тест на бумаге)

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

Правила

Задания можно выполнять группами до 3 человек. Оценка ставится всей группе (размер группы не влияет на оценку). Каждый участник группы должен хотя бы раз выступить на семинаре с рассказом о результатах. В отчетах может указываться коэффициент участия членов группы для перераспределения баллов. Например, задание выполнено группой из трех человек и оценено в 80 баллов; при равном вкладе все участники группы получают по 80 баллов, если указан вклад 2:1:1, то первый участник получает 120 баллов, второй и третий -- по 60. Сдача в течение одной недели после дедлайна -- засчитывается половина баллов, позже -- баллы не засчитываются.


Для сдачи домашки необходимо:

  1. Прислать читаемый отчет о результатах в pdf.
  2. Прислать ссылку на репозиторий на github'е с кодом, с помощью которого вы выполняли задания. Код не будет вносить вклада в оценку, однако будет просматриваться, и без него домашка не будет засчитываться.
  3. Выступить с докладом на любом из семинаров, предшествующих дате дедлайна по данной домашке - таким образом вы получаете фидбэк и сможете успеть скорректировать что-либо до написания отчета. Доклад нужно сопроводить слайдами.

1. Обработка коллекции BY.WEB

Максимальный балл: 100

Дедлайн -- 15 сентября

By.Web -- коллекция страниц в домене первого уровня BY (Беларусь). Коллекция была подготовлена компанией Яндекс в рамках мероприятий по оценке методов информационного поиска РОМИП. Использование коллекции регулируется соглашением. Коллекция предназначена исключительно для выполнения учебных заданий, распространять коллекцию или использовать ее в коммерческих целях запрещается.

  1. Первичная обработка данных (30 баллов)
    • Извлеките документы. Коллекция документов состоит из 10 xml-файлов, содержание и URL закодированы в base64 + cp1251.
    • Удалите HTML-разметку (например, с помощью Beautiful Soup) (!!! Если вы планируете выполнить подзадание 3, специальным образом обработайте гиперссылки <a href=”URL”>)
    • Посчитайте общее количество документов, постройте распределение длин документов в словах и байтах, определите средний размер документа в словах и байтах, соотношение объема текста и исходного HTML-документа. Какие еще характеристики могут быть полезны для анализа коллекции?
  2. Морфологическая обработка данных, построение частотного словаря (30 баллов)
    • Приведите слова документов к нижнему регистру и леммам (словарным формам) с помощью mystem или pymorphy2.
    • Какую долю коллекции составляют стоп-слова (их можно взять, например здесь)? Посчитайте среднюю длину слова в коллекции и словаре, долю слов латиницей. Для слов из словаря коллекции посчитайте частоту в коллекции (collection frequency, cf) и инвертированную документную частоту (inverse document frequency, idf), приведите “верхушки” списков. Постройте график зависимости ранга слова от частоты в логарифмических координатах.
  3. Постройте граф гиперссылок между страницами коллекции, визуализируйте (например, с помощью gephi). (20 баллов)
  4. Подготовьте отчет и сделайте доклад на семинаре (20 баллов)

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

Баллы -- 100 (+20 дополнительных)

Дедлайн -- 29 сентября

  1. Проиндексируйте коллекцию с помощью Elasticsearch. Обратите внимание на настройки и последовательность обработки. Так, вы можете индексировать plain text, полученный в результате выполнения задания 1, или использовать фильтр Elasticsearch. Замерьте скорость индексирования и размер полученного индекса. (20 баллов)
  2. Оцените качество поиска по формуле BM25, используя “слабую” (OR) оценку релевантности РОМИП 2009 года, посчитайте метрики: p@20, r@20, MAP@20, R-precision. Оцените скорость выполнения запросов. (20 баллов) Текст запросов Оценки релевантности
  3. Проиндексируйте коллекцию с морфологической обработкой. Варианты: 1) использовать фильтр Snowball в Elasticsearch или 2) индексирование предварительно лемматизированных документов (см. Задание 1). Сравните качество поиска с вариантом без морфологии (не забывайте, что запрос надо тоже привести к основам/леммам). (20 баллов) +10 баллов за сравнение качества поиска со стеммингом/лемматизацией: привести значения метрик и проанализировать несколько примеров запросов, где расхождения максимальны.
  4. Рассчитайте PageRank страниц. Предложите другие статические показатели информативности страниц. Скомбинируйте BM25 и статический показатель, оцените качество поиска. (20 баллов)
  5. Постройте индекс с использованием поля для заголовка документа. Сравните качество поиска с использованием этого поля и без. (+10 доп. баллов)
  6. Подготовьте отчет и сделайте доклад на семинаре. (20 баллов)

Материалы для подготовки

3. Машинное обучение ранжированию (LETOR)

Баллы -- 100 (+20 дополнительных)

Дедлайн -- 13 октября

Задача -- обучить функции ранжирования 1) на “готовых” векторах для пар “запрос-документ” и оценках релевантности и 2) на “сырых” документах и запросах и оценках релевантности.

  1. Обучить модель ранжирования на данных “Интернет-математика 2009”. Данные для обучения -- X 245-размерных векторов признаков для пар “запрос-документ” (Y уникальных запросов). Для обучения функции ранжирования используйте библиотеку ranklib или другую библиотеку. Сравнить три метода -- пототечный (pointwise), попарный (pairwise), списочный (listwise); метрика -- NDCG. (20 баллов) +10 баллов за лучший результат на курсе.
  2. By.Web (60 баллов)
    • Обучение. Используйте оценки РОМИП 2008 года для обучения (обратите внимание, что в данном случае оценки релевантности бинарные). Ознакомьтесь с признаками, которые реализованы в наборе данных LETOR. Реализуйте извлечение нескольких дополнительных признаков (помимо базового значения BM25) для пар “документ-запрос”, например:
      • Совпадение для полей документа (заголовок/тело документа)
      • Коэффициент, основанный на минимальной длине окна, включающего все слова запроса (меньше длина -- предположительно более релевантный документ)
      • Признаки запроса (длина)
      • Признаки документа (длина, pagerank, длина URL)
        Проанализируйте важность признаков.
    • Тестирование. Используйте оценки 2009 года для тестирования. С помощью Elasticsearch получите 100 документов на каждый запрос, получите векторы для пар “запрос-документ” и ранжируйте с помощью модели, полученной на оценках 2008 года. +10 баллов за лучший результат на курсе.
  3. Подготовьте отчет и сделайте доклад на семинаре. (20 баллов)