ВВЕДЕНИЕ 3
1. Обзор существующих алгоритмов машинного обучения для задачи ранжирования 5
1.1. Поточечный подход 5
1.2. Попарный подход 6
1.3. Посписочные методы 7
2. Теоретические основы алгоритмов ранжирования текстов 8
2.1. Предобработка входных данных 8
2.2. Нейронные сети 11
2.3. Метод опорных векторов 19
3. Практическая реализация 24
3.1. Обработка текста 24
3.2. Нейронные сети 29
3.3. Метод опорных векторов 37
ЗАКЛЮЧЕНИЕ 41
СПИСОК ЛИТЕРАТУРЫ 42
ПРИЛОЖЕНИЕ 45
Каждый человек в своей жизни сталкивался с тем или иным ранжированием, так как многие пользуются различными онлайн- кинотеатрами, социальными сетями, крупными интернет-магазинами и уж точно поисковыми системами. Во всех перечисленных интернет-площадках можно столкнуться с ранжированием: будь то поисковая выдача на запрос или индивидуально подобранная для каждого пользователя лента рекомендаций в онлайн-кинотеатре Netflix и видеохостинге Youtube или таргетированная реклама в соцсетях, как Вконтакте и Инстаграм. К тому же, помимо очевидных примеров, ранжирование встречается в таких сферах, как машинный перевод[1] и даже в вычислительной биологии. Для такой распространенной задачи существуют разные алгоритмы решения, и одними из основных являются алгоритмы обучения ранжированию.
Обучение ранжированию - один из классов задач машинного обучения, обычно обучения с учителем, обучения с частичным учителем и обучения с подкреплением, которое направлено на решение проблем ранжирования информации. Данная задача выделяется на фоне других задач машинного обучения, так как обычно конечным результатом, например, классификации или регрессии является предсказывание одного или нескольких значений к одному элементу выборки, то есть класса в случае классификации и вектора значений в случае регрессии. Однако обучение ранжированию - это анализ сразу целого списка элементов выборки одновременно, так как стоит задача отсортировать этот список так, чтобы получить релевантную выдачу на какой-либо запрос.
Однако анализ сразу корпуса элементов - задача непростая, и существует несколько подходов обучения ранжированию для решения данной задачи: поточечный, попарный и списочный. У каждого есть свои преимущества и свои проблемы, и существует огромное количество различных алгоритмов в каждом подходе.
Целью работы является решение задачи подбора новостей по заданной теме и ранжирование найденных новостей по степени их релевантности. Основным инструментом решения задачи должны являться методы машинного обучения. Для этого будут проанализированы и реализованы два алгоритма: нейронная сеть и метод опорных векторов. Оба они реализованы с попарным подходом решения задач ранжирования. Попарный подход был выбран, так как он показывает лучшие результаты на практике, чем, например, поточечный подход, да и предсказывание порядка двух документов по отношению друг к другу ближе к природе ранжирования, чем предсказывание оценки релевантности в отрыве от других документов в списке. И многие популярные алгоритмы, например, RankNet, LambdaRank и LambdaMART [2] [3] относятся к попарному подходу.
Для данной работы поставлены задачи:
- Сбор и изучение материалов по существующим алгоритмам машинного обучения для задачи ранжирования:
- поточечные методы;
- попарные методы;
- списочные методы.
- Разбор полученной информации по ранжированию:
- способы реализации;
- различия;
- преимущества и недостатки.
- Реализация двух алгоритмов машинного обучения для задачи ранжирования:
- нейронная сеть;
- метод опорных векторов.
- Тестирование.
- Анализ результатов работы отобранных алгоритмов и выбор оптимального алгоритма.
В рамках данной выпускной квалификационной работы для решения задачи подбора новостей по заданной теме и ранжирование найденных новостей по степени их релевантности были разработаны два алгоритма попарного подхода обучения ранжированию: нейронные сети и метод опорных векторов. В ходе разработки были решены следующие поставленные задачи:
- Сбор и изучение материалов по существующим алгоритмам машинного обучения для задачи ранжирования.
- Реализация двух алгоритмов машинного обучения для задачи ранжирования на языке программирования Python:
- нейронная сеть;
- метод опорных векторов.
- Анализ результатов работы отобранных алгоритмов.
Рассмотрены алгоритмы были с различными параметрами. Нейронная
сеть была реализована в трёх моделях: с одним скрытым слоем, с двумя и тремя, а также обучена при помощи двух алгоритмов оптимизации целевой функции. Точнее всего результат был при обучении градиентовским спуском, а увеличение количества слоёв на результат повлияло незначительно. Для метода опорных векторов рассматривались различные ядра. Их результаты тоже отличались незначительно. Как итог, были выбраны параметры для алгоритмов, которые дают лучшее время - нейронная сеть с одним скрытым слоем и градиентовским спуском в обучении и метод опорных векторов с полиномиальным ядром.
По результатам дальнейших экспериментов можно отметить, что с задачей ранжирования справляются оба отобранных алгоритма одинаково хорошо, однако по времени выигрывает нейронная сеть (17,5 с. против 166,9 с. у метода опорных векторов).
