Машинное обучение в поиске Яндекса или Как устроен Матрикснет

1

Пользователь приходит на сайт поисковой системы, задает собственный запрос и задача поисковой системы состоит в том, чтобы выдать по запросу топ самых релевантных документов. Документов, подходящих под этот запрос, в индексе – миллиарды, и даже после первых фильтраций их – миллионы. Эти миллионы нужно как-то упорядочить. На поддержка в составлении формулы ранжирования приходит машинное обучение, а именно – Матрикснет, собственный алгоритм градиентного бустинга Яндекса.

Матрикснет – это градиентный бустинг на деревьях решений, какой поддерживает все основные режимы: классификации, мультиклассификации, регрессии, ранжирования и др. Есть еще более сложные режимы – комбинации вышеперечисленных. Наш отдел разрабатывает новоиспеченные режимы для нужд смежных отделов, а также внутренние пользователи Яндекса сейчас тоже могут добавлять свои собственные порядки.

Матрикснет умеет работать с пропущенными значениями – если значение какого-то фактора не указано, это не будет проблемой. Кроме того, обучение Матрикснета может быть запущено на кластере — это распределенный алгоритм. Это значительно потому, что в поиске обучающие выборки сейчас такого размера, что в оперативную память одного сервера они просто не помещаются, вот отчего нужно делать распределенное обучение.

Применения Матрикснета в Яндексе

Матрикснет в Яндексе применяется повсеместно. Во-первых, в розыске. Матрикснет изначально писался именно для поиска. Во-вторых, он используется в рекламе для того, чтобы показывать пользователям самые увлекательные для них объявления, предсказывая количество кликов по рекламе. В-третьих, прогноз погоды в Яндексе строится по формуле Матрикснета. Также алгоритм применяется во внешних проектах Яндекса – YDF, в системе рекомендаций Яндекс.Дзен, в обнаружении ботов, позволенье омонимии, сегментации пользователей и многих других.

Особенности Матрикснета

Сейчас в открытом доступе есть сразу несколько алгоритмов градиентного бустинга, потому я расскажу, чем от них отличается Матрикснет. Важной его особенностью является то, что для него почти не нужен подбор параметров. Почему?

Когда писался Матрикснет, его тестировали на комплекте разных обучающих выборок (пулов) так, чтобы он на всех давал хорошее качество, поэтому на новых дата-сетах мы тоже получаем неплохое качество. Матрикснет легко использовать не только потому, что почти не нужен подбор параметров, но еще и потому, что в Яндексе кушать инфраструктура, позволяющая запускать обучение буквально в один клик (об этом подробнее ниже). Матрикснет выигрывает по качеству у иных алгоритмов градиентного бустинга на деревьях решений в режиме регрессии.

У Матрикснета сильно оптимизированное обучение. Это важно для всех задач Яндекса, но в вящей степени для поиска. Хотя у нас и большие обучающие выборки, мы не можем себе позволить, чтобы формула обучалась месяц, потому что от этого будет мучиться качество. Поэтому применяются всякие оптимизации, как алгоритмические, так и низкоуровневые, а также оптимизация нагрузки на сеть. Применение формулы Матрикснета тоже мощно заоптимизировано (за 1 сек. в одном потоке формула может быть применена к 100000 документов).

Градиентный бустинг на деревьях решений

Деревья решений – это такая структура этих — бинарное дерево – где во всех узлах данных, кроме листовых, находится разбиение по какому-то фактору или числу, а в листовых верхушках находятся числа. Вот таким образом дерево можно применить к документу:

Градиентный бустинг – это сумма простых моделей (в этом случае деревьев решений), каждая из которых улучшает результат предыдущей комбинации.

Матрикснет – это не произвольные деревья решений, а так именуемые «oblivious деревья решений», где на каждом уровне находится разбиение по одному и тому же признаку и одному и тому же числу. У такого способа построения дерева кушать набор особенностей:

• получение очень простых моделей, устойчивых к переобучению
• разбиение пространства при помощи гиперплоскости, а значит, что для вычисления смыслы в листе, нужно вычислить значение всех разбиений, а значит, не важно в каком порядке это делать
• регуляризация. Необходимо гарантировать отсутствие листьев, в которых почти не бывает объектов, поэтому приходится придумывать различные регуляризации, чтобы штрафовать такие ситуации

Обучение на кластере

Кушать несколько способов, как градиентные бустинги на деревьях решений параллелят на несколько серверов:

1. по признакам
2. по документам

Если мы параллелим обучение по приметам (когда различные признаки лежат на нескольких серверах), то тогда количество информации, которую нужно будет пересылать по сети, будет ровно пропорционально числу документов. Так как число документов у нас очень большое и постоянно растет, ы не можем себе такое позволить и параллелим обучение по документам.

Узким пунктом в обучении всех градиентных бустингов на деревьях решений является выбор структуры дерева, т.е. набор признаков, из каких будет состоять наше следующее дерево. Выбор делается из двух способов:

1. master-slave режим, когда кушать один ведущий узел и набор слейвов, каждый из которых считает какие-то статистики по признакам и отправляет их искуснику, который их агрегирует и выбирает лучший признак
2. all radius режим, где нет выделенного мастера, а каждый узел считает все статистики и агрегирует у себя сам

У любого из этих подходов есть серьезные недостатки. В режиме master-slave мастер становится узким местом по сети, в порядке all radius идет очень много трафика, потому что каждый узел должен получить много информации. Так, XGBoost работает в режиме all radius, поэтому не так хорошо параллелится. В Матрикснете обе эти проблемы решены следующим способом: при выборе очередного дерева, для любого признака выбирается случайный узел, который объявляется виртуальным мастером, и все остальные слейвы общаются уже с этим узлом. Он агрегирует необходимую информацию, обсчитывает этот признак и отправляет мастеру результат.

Мы также стараемся минимизировать трафик разными способами. Так, при выборе лучшего разбиения, мы на каждом слейве выбираем набор кандидатов для лучших признаков, и виртуальным мастерам скидываем информацию лишь по нескольким признакам. Не вообще по всем имеющимся, а только по топу самых лучших.

Матрикснет в ранжировании

График того, как со порой менялся размер формулы ранжирования, где число итераций – это число деревьев в модели, а килобайты – это размер модели.

Как видим, необходимо постоянно ускорять как обучение, так и применение модели, чтобы соответствовать вот такому росту.

Как же применяется машинное обучение для розыска? Для начала нужно собрать обучающую выборку, в которой будет набор пар (документ, запрос). Каждой такой чете асессоры ставят оценку – насколько этот документ подходит к запросу. Кроме того, в этой строке – документ, запрос, оценка – еще будут приметы (запросные, документные, документно-запросные). Если признак запросный, то мы его просто продублируем для всех документов запроса.

По полученной обучающей выборке и будет обучаться модель. Порядки обучения, используемые в поиске Яндекса:

• Регрессия (поточечный режим): Отличный = 1, Хороший = 0.8, Плохой = 0 => Минимизация MSE
• Попарный порядок – генерируем набор пар документов с разными оценками. Формула оптимизирует правильное ранжирование внутри пар.
• Оптимизация ранжирующей функции nDCG (не гладкая, не выйдет сделать шаг по градиенту). Дифференцируемое приближение функции.

Задачи в Матрикснете

• Автогенерация фичей, умный выбор фичей
• Ускорение обучения (CPU, GPU)
• Оптимизации для разреженных этих
• Обучение на кластере с неравномерным распределением ресурсов
• Новые регуляризации и функции ошибок
• Инструменты для анализа обученной формулы
• Пророчество времени обучения и требуемых ресурсов

Что нужно сделать исследователю в Яндексе, если ему нужно обучить формулу? Необходимо решить ряд очень сложных и первоочередных задач:

1. Найти последнюю версию алгоритма
2. Собрать данные для обучения в необходимом формате
3. Найти себе вычислительные ресурсы (кластер)
4. Запустить распределенное обучение

В Яндексе есть специальная инфраструктура, какая решает все эти задачи и делает жизнь исследователей лучше – это Нирвана.

Принципы Нирваны

Нирвана – это платформа для запуска произвольных процессов. Основной ее особенностью является то, что все процессы в ней конфигурируются в облике графов.

Если взять, например, обучение формулы Матрикснета, то пользователь создает граф, оперируя определенными блоками, вяжа их между собой, и запускает. Каждый блок – это операция, принимающая и генерирующая какие-то данные, через которые и осуществляется между ними связь. Пользователь запускает граф с обучением и вся история его запуска сохраняется, после этого он может посмотреть любой собственный предыдущий граф, склонировать его, запустить еще раз и гарантированно получить такой же результат.

В Нирване специально уделено отдельное внимание воспроизводимости. Любые эксперименты с машинным обучением в Яндексе – воспроизводимы. Кроме того, Нирвана позволяет посмотреть историю экспериментов любых иных пользователей в Яндексе, склонировать их эксперимент, как-то его изменить и перезапустить. Например, можно взять обучение нашей поисковой продакш-формулы, посмотреть этот граф, склонировать, изменить там какой-либо параметр и получить свою поисковую формулу, которая может быть лучше существующей.

В Нирване реализовано масса операций, сейчас их порядка 10 тысяч. Реализованы различные утилиты, есть удобный поиск по операциями. Если необходимая операция не находится, то есть возможность создания своей операции. Нирвана поддерживает так называемое визуальное программирование, что гораздо облегчает создание функций и композитных операций. И разумеется, в Нирване реализованы наиболее часто используемые в Яндексе алгоритмы машинного обучения – и Матрикснет, и обучение нейросетей. В Нирване весьма просто обучить свою нейросеть, ничего сложного в этом нет, и даже не требуется никаких дополнительных специальных знаний.

Нирвана – будет новая система, ее альфа-версия была запущена в 2015 году. Но у нее уже очень много пользователей – на сегодняшний день их немало 2 тыс. (треть от всего Яндека), в неделю Нирваной активно пользуется около 500 человек, которые запускают по 50 тыс. графов еженедельно.

Ключ: searchengines.ru