Машинное обучение в «Яндексе»

О проблеме Больших Данных начинают говорить, когда объемы данных переходят разумные пределы и с их обработкой перестают, например, справляться имеющиеся компьютерные мощности. Вместе с тем, если отбросить шумиху вокруг Больших Данных, видно, что ничего страшного не происходит. Конечно, данных стало больше и с ними уже сложно справляться, но это в истории уже неоднократно случалось: при исчерпании своих возможностей человек изобретает средства их усиления — так появились, например, паровозы и экскаваторы. Мало того, если у человека возникает проблема, то обычно оказывается, что у него уже есть все необходимые ресурсы для ее решения — сегодня имеется масса идей и исследований в области работы с Большими Данными как в научной области (статистика, наука о данных), так и в сфере технологий: MapReduce, машинное обучение, data mining, deep learning (направление машинного обучения, позволяющее изучать законы перехода от одного описания к другому с помощью некоторых обобщений, — например, если распознавать картинки, самое простое описание заключается в наборе цветов пикселей, но если предположить, что на картинке изображены лица людей, то описание станет менее подробным, но более содержательным, и т. п.). Не стали исключением и задачи, решаемые компанией «Яндекс», через серверы которой ежедневно проходят огромные потоки данных.

Качество работы любой поисковой системы зависит от объемов данных и способов их обработки — для обработки объемов, с которыми имеет дело «Яндекс», использование алгоритмов, написанных вручную, невозможно. Как технологии, которые изначально были нацелены на решение одного класса задач, сделать полезными для решения задач из других предметных областей? Каким образом научить алгоритм улучшаться по мере работы с учетом накопленного опыта и помогать зарабатывать дополнительные деньги?

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

• рекомендательные системы: кластеризация товаров и пользователей для выявления наиболее интересного подмножества товаров для индивидуального потребителя;
• автоматический перевод текста: эта задача сдвинулась с места лишь в начале этого века благодаря комбинированию подходов традиционного перевода на базе правил и использованию статистик встречающихся слов в корпусах параллельных текстов — то есть пар «оригинальный текст на одном языке — перевод на другой язык» (cейчас качество перевода растет за счет получения обратной связи от пользователя, которую можно использовать в алгоритмах обучения с подкреплением);
• распознавание лиц: у распознаваемых изображений выделяется набор вычислимых признаков, по которым накоплена определенная статистика, позволяющая отнести рассматриваемый объект к одному из заданных классов (известных лиц);
• автоматизация отбора персонала: определение того, какие признаки в образовании, опыте или личных качествах человека лучше всего коррелируют с успешной работой в той или иной роли в конкретной компании;
• определение лояльности и платежеспособности клиента: предсказание вероятности его ухода (например, к другому оператору) на основе его поведения.

Машинное обучение

Машинное обучение — технологическое направление на стыке математики, статистики и программирования. Статистика анализирует данные с целью выявления моделей, которые лучше помогают человеку понять или объяснить происходящее, а машинное обучение направлено на создание алгоритмов, для которых четко определяются критерии качества их работы и задается требование роста этого качества с ростом объема доступных данных. Таким образом, машинное обучение нацелено на получение практической пользы (повышения качества) от работы с доступными данными. Примечательно, что работа алгоритма далеко не всегда предусматривает объяснение происходящего — в отличие от статистики.

Алгоритмы машинного обучения принято делить на два класса: обучение с учителем и без него. В первом случае подразумевается, что имеется некий источник знаний, который позволяет пометить все объекты входных данных определенным образом, причем эти метки считаются истинными. Например, задача бинарной классификации — для каждого объекта обучающей выборки задан класс, которому этот объект принадлежит. Для второго случая система должна сама найти оптимальный способ работы с данными исходя из неких общих критериев. Например, задача разбиения множества на кластеры при решении алгоритмом k-средних кроме входных данных получает параметр k, задающий количество кластеров, на которые алгоритм должен разбить объекты. И в первом, и во втором случае подразумевается, что у данных есть некоторое представление, доступное для машины (чаще всего это таблицы, где строки — объекты, а колонки — набор признаков этих объектов), и можно задать некоторую вычислимую целевую функцию, которая при работе алгоритма соответствует качеству его работы.

Рис. 1. Задача классификации

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

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

Затем весь набор точек (данных) случайным образом делят на две части: обучающая (или «тренировочная») выборка и тестовая выборка (в отношении 60 к 40), а потом задается критерий качества классификации. В таких задачах принято говорить не о максимизации пользы, а об уменьшении ошибки распознавания, которая может быть задана как общее число неправильно распознанных точек. Алгоритм решения стремится минимизировать значение функции ошибки. Затем мы выбираем один из известных алгоритмов бинарной классификации (decision trees — дерево принятия решений, gradient boosted decision trees — деревья решений, построенные методом градиентного роста, neural networks — нейросети, logistic regression — логистическая регрессия и т. п.) и обучаем его на тренировочной выборке.

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

Качество решения

Рис. 2. Результат работы классификатора. Матрица неточностей

Чрезвычайно важно адекватным образом определить функцию качества (или функцию ошибки) классификатора и проконтролировать, чтобы выбранный классификатор правильно справился с поставленной задачей. Под качеством классификатора имеют в виду ошибки, которые он допускает. Базовый подход к оценке этих ошибок состоит в разделении их на ошибки первого (ложная тревога, False Negative) и второго рода (ложный пропуск, False Positive) и подсчет количества этих ошибок по отношению к общему числу положительных или отрицательных событий. Общее представление о работе классификатора может дать матрица неточностей (confusion matrix), которая содержит правильно распознанные хорошие примеры (True Positive), правильно распознанные плохие примеры (True Negative) и ошибки (рис. 2).

Рис. 3. Диаграмма множеств положительных и отрицательных примеров

Для разных задач стоимость ошибки первого или второго рода может быть различной. Например, в ситуации с распознаванием постоянного покупателя по отпечатку пальцев лучше настроить классификатор на минимизацию ошибок пропуска события (FP), а для распознавания отпечатка пальца сейфовым биометрическим замком — на минимизацию ошибок ложного срабатывания (FN). На рис. 3 приведена связь множества положительных и отрицательных событий и результаты работы классификатора в виде диаграмм множеств.

Чтобы не зависеть от абсолютного количества событий для измерения качества классификаторов, придуманы различные относительные меры качества — например, чувствительность (sensitivity, полнота recall), определенность (specificity) и точность (precision): Sensitivity = TP / (TP + FN) — вероятность того, что тест скажет, что пациент болен, если пациент действительно болен; Specificity = TN / (TN + FP) — вероятность того, что тест скажет, что пациент здоров, если он здоров; Precision = TP / (TP + FP) — доля правильно отобранных больных к общему числу отобранных алгоритмом больных.

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

Контроль

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

Рис. 4. Ошибки обучения классификатора

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

Опыт компании «Яндекс»

Первым примером использования машинного обучения в «Яндексе» стала задача ранжирования — показ в результатах поиска самых релевантных сайтов. Изначально эта задача решалась путем подбора функции ранжирования вручную, однако ее размер рос экспоненциально, поэтому была создана технология машинного обучения MatrixNet, которая не только решила проблему стремительного усложнения функции, но и позволила поставить на поток разработку факторов — признаков, позволяющих экстраполировать оценки релевантности, вручную подготовленные экспертами для небольшого числа сайтов, на весь Интернет. Постепенно подбор почти всех функций ранжирования в поисковых задачах «Яндекса» был переведен на машинное обучение: специальные функции подбираются и для разных регионов, для разных видов контента (веб-сайты, картинки, видео и т. п.), для пользователей с разными интересами. После того как технология машинного обучения зарекомендовала себя в ранжировании, началось ее использование в ряде других задач в поисковой системе, а затем и в других предметных областях.

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

Сейчас серверные мощности, задействованные в задачах машинного обучения, весьма значительны — только для задач ранжирования в «Яндекс.Поиске» задействован кластер из нескольких тысяч серверов на GPU производительностью 80 TFLOPS с перспективой расширения до 300 TFLOPS. О месте технологий машинного обучения «Яндекса» можно косвенно судить по результатам международных соревнований по машинному обучению, на которых специалисты компании не только занимали высокие места в таких состязаниях по ранжированию, как Yahoo Learning to Rank и Facebook Recruiting, но и показывали хорошие результаты на конкурсах по машинному обучению в других областях.

Решение хорошо показало себя на внутренних задачах компании, после чего оно было предоставлено как готовая технология внешним клиентам. Первым партнером стал ЦЕРН, в котором машинное обучение применяется для обнаружения очень редких (единицы на миллиард) событий в больших объемах экспериментальных данных.

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

Поисковый таргетинг

Одним из первых бизнесов «Яндекса» было размещение рекламы в результатах поиска — рекламодатель выбирал, по каким ключевым словам (фразам) нужно показывать его объявления, и назначал ставку (цену клика) по каждой фразе. Когда пользователь задавал запрос, в котором присутствовала нужная фраза, поисковая машина выбирала объявление с наибольшей ценой и его показывала. Дополнительно учитывалась «кликабельность» объявления, для того чтобы за объявления, вызывающие повышенный интерес у пользователя, рекламодатель платил меньше. Тем самым у рекламодателя формировался стимул самому заботиться о релевантности объявлений выбранным фразам, чтобы не раздражать пользователей рекламой, слишком далекой от их интересов. Все это хорошо работало, пока в компании не осознали, что имеется много данных и факторов, которые остаются вне рассмотрения. Тогда было решено воспользоваться технологией машинного обучения MatrixNet, чтобы поставить на поток поиск и отбор новых факторов, и в результате уже после первого внедрения был получен рост доходов на 5%. Теперь любая новая идея уже через месяц может быть проверена практикой и в случае успеха начинает работать для всех пользователей.

Поведенческий таргетинг

Через несколько лет в компании перестали ограничиваться результатами поиска и предложили владельцам сайтов возможность показывать объявления от рекламодателей «Яндекса» — так родилась Рекламная Сеть «Яндекса». Первое время реклама в ней показывалась по тому же принципу, что и в результатах поиска — по совпадению фраз в заголовке страницы с указанными рекламодателем. Но скоро стало понятно, что на огромной части сайтов с некоммерческой тематикой рекламу совсем не размещают либо размещают за бесценок. Тогда было решено использовать информацию о задаваемых пользователями поисковых запросах и их переходах на сайты — общий объем этой информации составляет десятки терабайт в день. На их основе был составлен профиль интересов каждого пользователя, чтобы среди этих интересов находить хорошо монетизируемые, показывая рекламу на плохо монетизируемых сайтах только по этим темам.

В задаче с поведенческим таргетингом есть одна важная особенность — здесь приходится иметь дело с несколькими сторонами, у каждой из которых свои интересы: рекламодатель, рекламная площадка, пользователь и компания «Яндекс». Рекламодатель заинтересован в привлечении как можно большего числа клиентов и в предельном случае хотел бы, чтобы пользователи видели только его рекламу. При этом рекламодатель заинтересован платить за рекламу как можно меньше. Рекламная площадка (сайт — участник рекламной сети) заинтересована показывать как можно меньше рекламы, но получать от рекламодателя как можно больше денег. Пользователи хотели бы видеть меньше рекламы, а если уж она показывается, то должна быть адресной. Для учета интересов всех сторон все это сводится в целевую функцию, а потом производится ее оптимизация.

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

Интересной задачей оказывается учет индивидуальных особенностей пользователей. В частности, опыт «Яндекса» показывает, что скорость угасания интересов у различных людей к различным темам сильно варьируется. Чтобы учесть эти особенности, требуется персонализованная формула. Механизм для создания таких формул сейчас находится в разработке.

Аналогично поисковому таргетингу, в результате внедрения машинного обучения в компании наладили автоматический подбор формулы. Сегодня 60% доходов «Яндекса» от рекламной сети приносит именно поведенческий таргетинг.

«Крипта»

Для социально-демографического таргетинга «Яндекс» использует собственную технологию — «Крипта», позволяющую группировать пользователей по их поведению в Сети. Всем, кто знаком с работой рекламы, хорошо известно, что ее нужно показывать только тому сегменту аудитории, на который она рассчитана. Одним из главных способов выбора такого сегмента является социодемографический портрет покупателя товара или услуги: уровень дохода, возраст, пол, регион. Для контекстной рекламы это не очень критично — совпадение по поисковой фразе уже дает хорошую уверенность в уместности рекламы, а медийная показывается широковещательно и обычно не привязана к сиюминутным интересам пользователя, поэтому для нее очень важна возможность сегментирования аудитории. Как известно, огромный процент пользователей Сети предпочитает скрывать свой истинный возраст, дату рождения и уровень дохода — либо не указывая их при регистрации, либо приводя заведомо недостоверные данные. В результате пользователю показывается реклама, адресованная совсем другой аудитории, что приносит раздражение, приводит к потерям средств рекламодателя и доверия к поисковой машине.

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

Телезрители в Интернете

Многие рекламодатели размещают рекламу одновременно и на телеканалах, и в Сети. Несмотря на то что телевизор ежемесячно смотрит 99% россиян, 30% из них проводят у экранов не более часа в день. По этому признаку все телезрители делятся на две группы. Рекламодатели хотят работать с этими группами по-разному. Например, в самом простом случае не показывать в Интернете рекламу тем, кто и так видит ее на телеэкране.

Специалисты «Яндекса» выявили несколько тысяч пользователей, о которых было достоверно известно, что они смотрят телевизор, и использовали их поисковую историю в качестве обучающей выборки. Так были обнаружены признаки, отличающие телезрителей от остальной аудитории Интернета. В качестве пилота эта технология использовалась в рекламной кампании Snickers — в сегменте редко смотрящей телевизор аудитории кликабельность баннеров увеличилась вдвое по сравнению с аудиторией постоянных телезрителей, при сопоставимом количестве показов тем и другим.

***

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

Андрей Устюжанин (anaderi@yandex-team.ru), Денис Юркин (yurkennis@yandex-team.ru) — сотрудники компании «Яндекс» (Москва).