|
Пользователь приходит на сайт поисковой системы, задает свой запрос и задача поисковой системы состоит в том, чтобы выдать по запросу топ самых релевантных документов. Документов, подходящих под данный запрос, в индексе – миллиарды, и даже после первых фильтраций их – миллионы. Эти миллионы нужно как-то упорядочить. На помощь в составлении формулы ранжирования приходит машинное обучение, а именно – Матрикснет, собственный алгоритм градиентного бустинга Яндекса.
Матрикснет – это градиентный бустинг на деревьях решений, который поддерживает все основные режимы: классификации, мультиклассификации, регрессии, ранжирования и др. Есть еще более сложные режимы – комбинации вышеперечисленных. Наш отдел разрабатывает новые режимы для нужд смежных отделов, а также внутренние пользователи Яндекса сейчас тоже могут добавлять свои собственные режимы.
Матрикснет умеет работать с пропущенными значениями – если значение какого-то фактора не указано, это не будет проблемой. Кроме того, обучение Матрикснета может быть запущено на кластере — это распределенный алгоритм. Это важно потому, что в поиске обучающие выборки сейчас такого размера, что в оперативную память одного сервера они просто не помещаются, вот почему нужно делать распределенное обучение.
Применения Матрикснета в Яндексе
Матрикснет в Яндексе применяется повсеместно. Во-первых, в поиске. Матрикснет изначально писался именно для поиска. Во-вторых, он используется в рекламе для того, чтобы показывать пользователям самые интересные для них объявления, предсказывая количество кликов по рекламе. В-третьих, прогноз погоды в Яндексе строится по формуле Матрикснета. Также алгоритм применяется во внешних проектах Яндекса – YDF, в системе рекомендаций Яндекс.Дзен, в обнаружении ботов, разрешении омонимии, сегментации пользователей и многих других.
Особенности Матрикснета
Сейчас в открытом доступе есть сразу несколько алгоритмов градиентного бустинга, поэтому я расскажу, чем от них отличается Матрикснет. Важной его особенностью является то, что для него почти не нужен подбор параметров. Почему?
Когда писался Матрикснет, его тестировали на наборе разных обучающих выборок (пулов) так, чтобы он на всех давал хорошее качество, поэтому на новых дата-сетах мы тоже получаем хорошее качество. Матрикснет легко использовать не только потому, что почти не нужен подбор параметров, но еще и потому, что в Яндексе есть инфраструктура, позволяющая запускать обучение буквально в один клик (об этом подробнее ниже). Матрикснет выигрывает по качеству у других алгоритмов градиентного бустинга на деревьях решений в режиме регрессии.
У Матрикснета сильно оптимизированное обучение. Это важно для всех задач Яндекса, но в большей степени для поиска. Хотя у нас и большие обучающие выборки, мы не можем себе позволить, чтобы формула обучалась месяц, потому что от этого будет страдать качество. Поэтому применяются всякие оптимизации, как алгоритмические, так и низкоуровневые, а также оптимизация нагрузки на сеть. Применение формулы Матрикснета тоже сильно заоптимизировано (за 1 сек. в одном потоке формула может быть применена к 100000 документов).
Градиентный бустинг на деревьях решений
Деревья решений – это такая структура данных — бинарное дерево – где во всех узлах данных, кроме листовых, находится разбиение по какому-то фактору или числу, а в листовых вершинах находятся числа. Вот таким образом дерево можно применить к документу:
Градиентный бустинг – это сумма простых моделей (в данном случае деревьев решений), каждая из которых улучшает результат предыдущей комбинации.
Матрикснет – это не произвольные деревья решений, а так называемые «oblivious деревья решений», где на каждом уровне находится разбиение по одному и тому же признаку и одному и тому же числу. У такого способа построения дерева есть набор особенностей:
• получение очень простых моделей, устойчивых к переобучению
• разбиение пространства при помощи гиперплоскости, а значит, что для вычисления значения в листе, нужно вычислить значение всех разбиений, а значит, не важно в каком порядке это делать
• регуляризация. Нужно гарантировать отсутствие листьев, в которых почти не бывает объектов, поэтому приходится придумывать различные регуляризации, чтобы штрафовать такие ситуации
Обучение на кластере
Есть несколько способов, как градиентные бустинги на деревьях решений параллелят на несколько серверов:
1. по признакам
2. по документам
Если мы параллелим обучение по признакам (когда различные признаки лежат на нескольких серверах), то тогда количество информации, которую нужно будет пересылать по сети, будет прямо пропорционально числу документов. Так как число документов у нас очень большое и постоянно растет, ы не можем себе такое позволить и параллелим обучение по документам.
Узким местом в обучении всех градиентных бустингов на деревьях решений является выбор структуры дерева, т.е. набор признаков, из которых будет состоять наше следующее дерево. Выбор делается из двух способов:
1. master-slave режим, когда есть один ведущий узел и набор слейвов, каждый из которых считает какие-то статистики по признакам и отправляет их мастеру, который их агрегирует и выбирает лучший признак
2. all radius режим, где нет выделенного мастера, а каждый узел считает все статистики и агрегирует у себя сам
У каждого из этих подходов есть серьезные недостатки. В режиме master-slave мастер становится узким местом по сети, в режиме all radius идет очень много трафика, потому что каждый узел должен получить много информации. Например, XGBoost работает в режиме all radius, поэтому не так хорошо параллелится. В Матрикснете обе эти проблемы решены следующим способом: при выборе очередного дерева, для каждого признака выбирается случайный узел, который объявляется виртуальным мастером, и все остальные слейвы общаются уже с этим узлом. Он агрегирует нужную информацию, обсчитывает этот признак и отправляет мастеру результат. |
|
|
|
|
