Снова в эфире наша образовательная рубрика. На этот раз предлагаем ознакомиться с очередным курсом Техносферы, посвящённым информационному поиску. Цель курса — рассказать об основных методах, применяемых при создании поисковых систем. Некоторые из них представляют собой хороший пример смекалки, некоторые показывают, где и как может применяться современный математический аппарат. Преподаватели курса: Алексей Воропаев, Владимир Гулин, Дмитрий Соловьев, Игорь Андреев, Алексей Романенко, Ян Кисель.

Лекция 1. Введение в информационный поиск. Обзор архитектуры поисковых систем

Определение задачи информационного поиска. Примеры поисковых систем. Задачи, связанные с поиском информации. История развития поисковых систем. Логическая модель информационного поиска, его задачи. Принципы булева поиска. Матрица «термин-документ». Обратный индекс. Словарь и координатные блоки. Создание обратного индекса. Разбиение на токены и сортировка. Словари и координатные блоки.

Лекция 2. Лингвистика

Что такое лингвистика, каковы её задачи. История зарождения и развития лингвистики как науки. Задачи, решаемые лингвистикой, её разновидности. Общая лингвистика: фонетика, фонология, морфология, синтаксис, семантика, прагматика. Историческая лингвистика. Лингвистическая типология. Социолингвистика. Диалектология. Лексикография. Психолингвистика. Математическая лингвистика. Статистическая лингвистика. Подходы к языку: рационалистический и эмпирический. Морфология. Корпусная лингвистика. Конкорданс, законы Ципфа, поправки и формула Мандельброта.

Лекция 3. Основы обработки текста

Критерии документа, кодировки. Уровни лингвистического анализа. Токены и термины. Детекция языка: графематический, N-граммный и лексический подходы. Нормализация. Проблемы токенизации. Наличие и отсутствие пробелов. Китайский, японский, арабский языки. Ударение и диакритика. Классы эквивалентности. Понижение регистра. Стоп-слова. Лемматизация. Стемминг. Предиктор. Виды языков. Статистическое снятие омонимии. Разбиение текста на предложения. Расширение поискового запроса.

Лекция 4. Коллокации

Методы подсчёта вероятности: параметрический и непараметрический подходы, стандартные и биноминальные распределения, мультиноминальное и нормальное распределения, аппроксимирование. Байесовский подход к статистике. Определение коллокаций, их признаки. Частотность биграмм. Фильтр по частям речи. Отклонения, гистограммы отклонений. Поиск коллокаций, примеры применения t-критерия. Поиск отличий в словоупотреблении. Критерий Пирсона. x²-критерий. Критерий отношения правдоподобия. Относительные частоты. Взаимная информация. Разреженность данных. F-мера.

Лекция 5. Языковые модели. N-граммы. Цепи Маркова

Цели распознавания языка. Языковые модели. Поиск с использованием языковых моделей. Фундаментальная проблема нехватки данных. Построение N-грамм. Метод максимального правдоподобия. Сглаживание. Валидация моделей. Линейное смешение моделей. Цепь Маркова. Матрица переходов. Последовательность состояний. Скрытые марковские модели. Три задачи HMM. Алгоритмы вперёд и назад. Алгоритмы Витерби, Баума-Уэлша. Применение НММ Таггер. Анализ поведения пользователя.

Лекция 6. Машинный перевод

Определение и задачи машинного перевода. История развития машинного перевода. Подходы к машинному переводу: rule-based, corpora-based, hybrid. Три основные методологии. RBMT, его сравнение с SMT, их преимущества и недостатки. Параллельный корпус. Выравнивание по предложениям. Word-based модели. Модели IBM Model, их ограничения. Фразовые модели: фразовый статистический перевод, вычисление вероятности перевода, модель языка, модель перевода, построение фразовой таблицы. Декодирование. Оценка машинного перевода. BLEU (Bilingual evaluation understudy). Эволюция машинного перевода.

Лекция 7. Индексация

Общая схема базы поиска. Назначение обратного индекса. Технические ограничения и дисковая подсистема. Cостав обратного индекса и варианты его построения. Оптимизация пересечения блоков. Сжатие координатных блоков: сравнение побитовых и побайтовых подходов: код Фибоначчи, VarByte, гамма-коды, Simple9. Практические советы по уменьшению объема индекса. Структуры данных, используемые для построения словаря. Подходы к хранению стоп-слов. Проблемы индексации больших объемов. Распределение документов и балансировка баз. Архитектура индексатора.

Лекция 8. Архитектура web-поиска. Текстовое ранжирование

Логическая схема поисковой машины. Поисковый кластер. Индексация. Булев поиск. Вычисление веса. Коэффициент Жаккара. Частотная матрица. Модель «мешка слов». Частота термина. Логарифмическое взвешивание. Документная частота. IDF. Документы как векторы. Методы оптимизации текстового ранжирования. Термины с большим IDF. Документы с большим количеством терминов из запроса. Статические веса, общий вес. Эшелоны. Кластеризация индекса. Параметрические индексы и зоны. Поля (числовые зоны). Индексы для зон. Компактность вхождения. Вероятностный поиск. Использование языковых моделей при поиске. Варианты сравнения моделей. Правдоподобие запроса и документа. Сравнение моделей. Обратная связь по релевантности. Бинарная вероятностная модель. Байесовы сети в задаче ранжирования.

Лекция 9. Дизайн поисковой выдачи. Сниппеты. Оценка качества поиска

Примеры дизайнов страниц поисковых выдач разных ресурсов. Компоненты SERP. Органические результаты. Выделение параграфов. Разбиение на предложения. Формирование сниппета, общий алгоритм формирования. Обогащение сниппетов. Метрики сниппетов. Оценка асессорами. Метрики качества поисковой системы. Качество поиска. Стандартные коллекции. TREC. Точность/полнота. Критика чистой релевантности. Маркерные тесты. Поиск периферийных сайтов. Региональная навигация. Тематический поиск. Общее качество поиска. Асессорская служба. Оценка релевантности документа. Кросс-валидация. SOM-карты. Автопоиск ошибок. Онлайн-метрики. Оценка гипотез. Кликовые метрики. Корреляция с асессорами.

Лекция 10. Особенности web-поиска. Спайдер

Популярность пользования поиском. История поисковых систем. Основы web-поиска. Потребности пользователей. Эмпирическая оценка поисковых результатов пользователем. Коллекция web-документов. Поисковая реклама, как она ранжируется, каковы её плюсы и минусы. Спайдер, его задачи. Очередь URL’ов. Поисковые роботы. Основная архитектура спайдера. Парсинг: нормализация URL. Распределённый спайдер. Взаимодействие серверов. Схема Mercator. Front queues, back queues. Свежесть базы. Deep Web (труднодоступные сайты). Карты сайтов. Хранение документов. Удаление шума.

Лекция 11. Поиск дубликатов в Web

Сравнение документов: точные и неточные дубликаты, почти дубликаты, версии для печати. Три этапа определения похожих документов. Шинглы (shingles), опция сжатия. Множественная модель, матричная модель. Поиск похожих колонок. Сигнатуры. Выявление похожего множества (minhashing). Поиск похожих пар. Отбор кандидатов из сигнатур Minhash. Locality-sensitive hashing. Распределение по частям и по корзинам. LSH-компромиссы. Поиск дубликатов в Web.

Лекция 12. Применение самоорганизующихся карт в поисковой машине

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

Лекция 13. Выявление спам-сайтов на основе анализа контента страниц

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

Лекция 14. Поведенческое и ссылочное ранжирование

Вычисление поведенческой релевантности. Индексация анкорного текста. Алгоритм HITS, Page Rank. Метод блочной структуры. Системы для обработки графов.

Лекция 15. Ранжирование с машинным обучением

Классическое ранжирование. Факторы ранжирования. Ранжирование на основе машинного обучения. Специфика задачи машинного обучения ранжированию. Формальная постановка задачи. Градиентный спуск. Деревья решений. «Невнимательные» деревья решений. Алгоритмические композиции над деревьями решений (bagging, boosting). Стакинг. Алгоритм BagBoo. Вопросы построения обучающих данных. Активное обучение. Сэмплирование неопределённости. Комитетные методы активного обучения. Применение самоорганизующихся карт для сэмплирования обучающих данных. Алгоритм SOM+QBag для активного обучения ранжированию.

Предыдущие выпуски

Технопарк:

• 1 семестр. Web-технологии
• 1 семестр. Алгоритмы и структуры данных
• 1 семестр. С/С++
• 2 семестр. Базы данных
• 3 семестр. Проектирование высоконагруженных систем

Техносфера:

• 1 семестр. Алгоритмы интеллектуальной обработки больших объемов данных
• 1 семестр. Методы использования СУБД в интернет-приложениях

Подписывайтесь на youtube-канал Технопарка и Техносферы!