Сегодня мы завершаем серию публикаций о фреймворке FML, в которых рассказываем о том, как и для чего автоматизировали в Яндексе применение технологий машинного обучения. В сегодняшнем посте мы расскажем:
В предыдущем посте мы остановились на том, что с помощью FML нам удалось поставить на поток разработку новых факторов для формулы ранжирования и первоначальную оценку их полезности. Однако следить, что фактор остаётся ценным и не впустую расходует вычислительные ресурсы, необходимо и после его внедрения.
Для этого была создана специальная регулярная автоматическая проверка — так называемый мониторинг качества факторов. Вычислительно он очень сложный, но позволяет решить целый ряд проблем.
Первая – это выявление претендентов на «удаление». Убедившись однажды, что фактор вносит большой вклад и его цена приемлема, и приняв после этого решение о его внедрении, важно следить за тем, чтобы со временем он оставался полезным, несмотря на появление всё новых и новых факторов. Ведь новый может запросто оказаться более общим и сильным, чем старый, и не только создавать новую ценность, но и дублировать его. Например, когда мы сначала внедрили фактор «вхождение слов запроса в URL, записанный латиницей», а спустя какое-то время сделали новый, поддерживающий вхождение в URL-ы, записанные и латиницей, и кириллицей, первый потерял всякую ценность. Старую версию следует удалять как минимум по двум причинам: 1) экономия на времени вычисления старого фактора; 2) уменьшение размерности признаков при обучении.
Иногда возникает другая ситуация. Фактор раньше приносил «много пользы», а теперь он, хотя и остаётся полезным, уже не проходит порог качество / затраты. Такое может случиться, если он потерял свою актуальность, или стал частично дублироваться более новыми факторами. Поэтому нужно создавать здоровую эволюцию — чтобы слабые факторы погибали и уступали место сильным. Но здесь недостаточно одних данных от FML, и окончательное решение об удалении фактора принимается экспертами.
Есть ещё одна проблема, которую решает мониторинг качества. Отслеживая то, что полезность однажды внедрённого фактора не снизилась, он обеспечивает регрессионное тестирование. Качество фактора может упасть, например, из-за случайной модификации или системного изменения в свойствах интернета, на которые он первоначально полагался. В таком случае система уведомит разработчика, что данный фактор нужно «починить» (исправить ошибку или модифицировать его так, чтобы он отвечал новым реалиям).
Третья задача мониторинга, которую он вскоре начнёт решать — избавление от избыточности факторов. До определённого момента мы не проверяли, дублирует ли новый фактор какой-то из уже внедрённых. В результате вполне могло оказаться, что, например, есть два фактора, которые повторяют друг друга. Но если измерить, какой вклад каждый из них в одиночку даёт по отношению ко всем остальным, — окажется, что он равен нулю. А если исключить оба фактора, то качество упадёт. И задача именно в том, чтобы выбрать, какие из дублирующихся факторов эффективнее всего оставить, с точки зрения того же соотношения роста качества к цене вычислений. Вычислительно это на много порядков сложнее, чем оценка нового фактора. Именно для решения этой задачи мы и планируем задействовать расширенный кластер на 300 Tflops.
Ситуация, в которой каждый из двух факторов, I и J,
дают нулевой вклад — (J, K, L) и (I, K, L),
но удаление их обоих приводит к ухудшению качества — (K, L).
Можно исключить любой один (I либо J).
Выгоднее исключить J, как более ресурсоёмкий.
В этом и предыдущих постах говорилось о конкретных применениях для FML в контексте регулярного машинного обучения. Но в итоге фреймворк вышел за рамки этих прикладных задач и стал полноценной платформой для распределённых вычислений над поисковым индексом.
Посвященные читатели наверняка заметили, что везде, где используется FML, речь идёт о примерно одном и том же массиве данных: скаченных документах, сохранённых запросах, асессорских оценках, результатах расчёта факторов. Мы в своё время тоже это заметили, а ещё посмотрели на количество других задач, которые уже решаются в Поиске и так или иначе полагаются на эти данные; и решили извлечь из этого дополнительную пользу. А именно — сделали из FML полноценный конвейер для произвольных распределённых вычислений над этим набором данных, которые выполняются на вычислительном кластере, насчитывающем несколько тысяч серверов.
Мы добились того, что FML облегчает выполнение распределённых расчётов над поисковым индексом и дополнительными данными, специфичными для конкретной задачи. Поисковый индекс обновляется несколько раз в неделю, и с каждым обновлением существенная его часть переезжает между серверами для более оптимального использования ресурсов. FML полностью избавляет разработчика от забот о поиске нужного фрагмента индекса и предоставляет ему полный и консистентный доступ к нему. Фреймворк диагностирует целостность индекса и запускает вычисления именно на тех серверах кластера, где лежат нужные разработчику данные.
В отличие от поискового индекса, специфичные для текущей задачи данные FML сам раскладывает по серверам. Также он берёт на себя управление распределённым выполнением конкурирующих пользовательских задач. Как только вычисления запущены, FML начинает следить за ходом выполнения расчётов и когда какая-то из задач на конкретном сервере становится недоступной, даёт сигнал администраторам. Получив его, они приступают к диагностике конкретной ситуации с этой задачей на этом сервере, будь то поломка диска, неисправности сети или полный выход сервера из строя. В наших дальнейших планах — помогать администраторам как можно более детальной диагностикой и упростить поиск причин тех или иных сбоев. Последние в условиях нескольких тысяч серверов — совершенно заурядное дело, и происходят много раз в день. Поэтому мы сильно сэкономим ручной труд администраторов, если хоть немного его автоматизируем.
На первый взгляд, всё это очень похоже на задачи YAMR — то же распределение вычислений, сбор результатов и обеспечение надёжности. Но есть два кардинальных отличия. Во-первых, FML имеет дело с поисковым индексом, а не с классической структурой «ключ-значение», принятой в YAMR. Поисковый индекс подразумевает, что все выборки происходят по комбинации сразу большого количества ключей (в простейшем случае — нескольких слов запроса). Работа с такими выборками в парадигме «ключ-значение» принципиально затруднена. А во-вторых, если YAMR сам решает, как разложить данные по серверам, то FML умеет работать с любым распределением данных, заранее заданным внешней системой по её собственным законам.
Решение оказалось настолько удачным, что большинство команд разработки Поиска по собственной инициативе перешло на использование FML, и, по нашим оценкам, сегодня около 70% (в смысле количества процессорного времени) вычислений в разработке Яндекс.Поиска находится под управлением FML.
Как мы уже говорили, FML и Матрикснет являются частями технологии машинного обучения Яндекса. И используется она у нас не только в веб-поиске. Например, с её помощью подбираются формулы для так называемых «вертикальных» поисков (по изображениям, видео и т.п.) и для предварительного отсева совсем нерелевантных документов в веб-поиске. Она помогает обучать алгоритм классификации товаров по категориям в Яндекс.Маркете. Кроме того, машинное обучение подбирает формулы для поискового робота (например, для стратегии, которая определяет, в каком порядке обходить сайты). И во всех этих случаях решает одну и ту же задачу — строит функцию, которая наилучшим образом соответствует экспертным данным, поданным на вход. Думаем, в ближайшее время мы найдём для него ещё множество применений в Яндексе. Например, используем в обучении классификаторов, которых у нас очень много.
FML в паре с библиотекой машинного обучения Матрикснет может быть полезен не только в разработке поисковых систем, но и в других областях, где требуется обработка данных. С некоторыми коллективами мы уже опробовали их для построения поиска по специализированным видам данных с учётом специфических факторов. Например, CERN (Европейский Центр ядерных исследований) использует Матрикснет для обнаружения редких событий в больших объёмах данных (единицы на миллиард). Традиционно там использовался пакет TMVA, основанный на Gradient Boosted Decision Trees (GBDT). Поскольку Матрикснет на наших задачах и наших метриках давно стал точнее, чем простой GBDT, мы расчитываем, что и физики ЦЕРНа смогут использовать его для повышений точности своих исследований.
Глядя более широко на то, что умеет наша технология, мы уверены, что она может быть полезна и во многих сферах, в которых встречаются типовые задачи машинного обучения — тем более, если они имеют дело с большим массивом данных, меняющимся во времени. Например, в крупных интернет-магазинах, онлайн-аукционах, социальных сетях.
Сейчас нам известно только одно промышленное решение для близкой задачи, помимо нашего собственного, — Google Prediction API. Есть и несколько стартапов, таких как BigML. К сожалению, мы не смогли найти сведений об их эффективности для тех или иных применений. В качестве конвейера для вычислительных задач может ещё служить Amazon Cloud Service, но его пристальное рассмотрение показало, что это очень общее решение, для совершенно произвольных задач. В то время как наше создано именно для поисковых и максимально раскрывается в них. Аналоги же FML в решении задач «Оценка эффективностипо нового фактора» и «Мониторинг качества факторов» нам и вовсе неизвестны.
Внешний наблюдатель может косвенно судить об эффективности нашей технологии, опираясь на результаты международных соревнований по машинному обучению. Например, специалисты Яндекса занимали высокие места в состязаниях по ранжированию Yahoo Learning to Rank и Facebook Recruiting, в которых борьба за точность ранжирующей функции идёт в терминах тысячных долей ERR/NDCG. Хорошие результаты они показывали на конкурсах по машинному обучению и в других областях.
Чтобы быть уверенными в том, что наши технологии остаются лучшими в своей области, мы регулярно проводим и собственные конкурсы по машинному обучению — в рамках серии «Интернет-математика». Среди тем: машинное обучение ранжированию, предсказание пробок на дорогах, классификация панорамных фото. Два года назад наши соревнования стали международными, и завершающий этап конкурса по пресказанию релевантности по поведению пользователей прошёл в рамках конференции WSDM 2012 в Сиэттле (США). Совсем недавно завершился конкурс, посвящённый прогнозированию переключения поисковой системы.
Несмотря на то, что фреймворк FML, о котором мы рассказали вам в этой серии постов, изначально создавался для работы с Матрикснетом, он может быть адаптирован к любой другой известной библиотеке машинного обучения (например, Apache Mahout, Weka, scikit-learn).
В последнее время появилось несколько хороших онлайн-курсов по машинному обучению. На английском можно порекомендовать курс Стенфордского университета, на русском — курс Константина Воронцова, который читается в Школе Анализа Данных.
Из «бумажных» изданий отметим два издания: The Elements of Statistical Learning: Data Mining, Inference, and Prediction (Trevor Hastie, Robert Tibshirani, Jerome Friedman) (доступна и в электронном виде) и Pattern Recognition and Machine Learning (Christopher M. Bishop).
Кроме этого, будет полезной обширная подборка курсов и учебников, собранная на Kaggle.
- почему нужно следить за качеством факторов и как мы это делаем;
- как FML помогает в задачах распределённых вычислений над поисковым индексом;
- каким образом и для чего наши технологии машинного обучения уже применяются и могут быть применены как в Яндексе, так и вне его;
- какую литературу можно посоветовать для более глубокого погружения в затронутую проблематику.
Мониторинг качества уже внедрённых факторов
В предыдущем посте мы остановились на том, что с помощью FML нам удалось поставить на поток разработку новых факторов для формулы ранжирования и первоначальную оценку их полезности. Однако следить, что фактор остаётся ценным и не впустую расходует вычислительные ресурсы, необходимо и после его внедрения.
Для этого была создана специальная регулярная автоматическая проверка — так называемый мониторинг качества факторов. Вычислительно он очень сложный, но позволяет решить целый ряд проблем.
Первая – это выявление претендентов на «удаление». Убедившись однажды, что фактор вносит большой вклад и его цена приемлема, и приняв после этого решение о его внедрении, важно следить за тем, чтобы со временем он оставался полезным, несмотря на появление всё новых и новых факторов. Ведь новый может запросто оказаться более общим и сильным, чем старый, и не только создавать новую ценность, но и дублировать его. Например, когда мы сначала внедрили фактор «вхождение слов запроса в URL, записанный латиницей», а спустя какое-то время сделали новый, поддерживающий вхождение в URL-ы, записанные и латиницей, и кириллицей, первый потерял всякую ценность. Старую версию следует удалять как минимум по двум причинам: 1) экономия на времени вычисления старого фактора; 2) уменьшение размерности признаков при обучении.
Иногда возникает другая ситуация. Фактор раньше приносил «много пользы», а теперь он, хотя и остаётся полезным, уже не проходит порог качество / затраты. Такое может случиться, если он потерял свою актуальность, или стал частично дублироваться более новыми факторами. Поэтому нужно создавать здоровую эволюцию — чтобы слабые факторы погибали и уступали место сильным. Но здесь недостаточно одних данных от FML, и окончательное решение об удалении фактора принимается экспертами.
Есть ещё одна проблема, которую решает мониторинг качества. Отслеживая то, что полезность однажды внедрённого фактора не снизилась, он обеспечивает регрессионное тестирование. Качество фактора может упасть, например, из-за случайной модификации или системного изменения в свойствах интернета, на которые он первоначально полагался. В таком случае система уведомит разработчика, что данный фактор нужно «починить» (исправить ошибку или модифицировать его так, чтобы он отвечал новым реалиям).
Третья задача мониторинга, которую он вскоре начнёт решать — избавление от избыточности факторов. До определённого момента мы не проверяли, дублирует ли новый фактор какой-то из уже внедрённых. В результате вполне могло оказаться, что, например, есть два фактора, которые повторяют друг друга. Но если измерить, какой вклад каждый из них в одиночку даёт по отношению ко всем остальным, — окажется, что он равен нулю. А если исключить оба фактора, то качество упадёт. И задача именно в том, чтобы выбрать, какие из дублирующихся факторов эффективнее всего оставить, с точки зрения того же соотношения роста качества к цене вычислений. Вычислительно это на много порядков сложнее, чем оценка нового фактора. Именно для решения этой задачи мы и планируем задействовать расширенный кластер на 300 Tflops.
Ситуация, в которой каждый из двух факторов, I и J,
дают нулевой вклад — (J, K, L) и (I, K, L),
но удаление их обоих приводит к ухудшению качества — (K, L).
Можно исключить любой один (I либо J).
Выгоднее исключить J, как более ресурсоёмкий.
Конвейер распределённых вычислений
В этом и предыдущих постах говорилось о конкретных применениях для FML в контексте регулярного машинного обучения. Но в итоге фреймворк вышел за рамки этих прикладных задач и стал полноценной платформой для распределённых вычислений над поисковым индексом.
Посвященные читатели наверняка заметили, что везде, где используется FML, речь идёт о примерно одном и том же массиве данных: скаченных документах, сохранённых запросах, асессорских оценках, результатах расчёта факторов. Мы в своё время тоже это заметили, а ещё посмотрели на количество других задач, которые уже решаются в Поиске и так или иначе полагаются на эти данные; и решили извлечь из этого дополнительную пользу. А именно — сделали из FML полноценный конвейер для произвольных распределённых вычислений над этим набором данных, которые выполняются на вычислительном кластере, насчитывающем несколько тысяч серверов.
Мы добились того, что FML облегчает выполнение распределённых расчётов над поисковым индексом и дополнительными данными, специфичными для конкретной задачи. Поисковый индекс обновляется несколько раз в неделю, и с каждым обновлением существенная его часть переезжает между серверами для более оптимального использования ресурсов. FML полностью избавляет разработчика от забот о поиске нужного фрагмента индекса и предоставляет ему полный и консистентный доступ к нему. Фреймворк диагностирует целостность индекса и запускает вычисления именно на тех серверах кластера, где лежат нужные разработчику данные.
В отличие от поискового индекса, специфичные для текущей задачи данные FML сам раскладывает по серверам. Также он берёт на себя управление распределённым выполнением конкурирующих пользовательских задач. Как только вычисления запущены, FML начинает следить за ходом выполнения расчётов и когда какая-то из задач на конкретном сервере становится недоступной, даёт сигнал администраторам. Получив его, они приступают к диагностике конкретной ситуации с этой задачей на этом сервере, будь то поломка диска, неисправности сети или полный выход сервера из строя. В наших дальнейших планах — помогать администраторам как можно более детальной диагностикой и упростить поиск причин тех или иных сбоев. Последние в условиях нескольких тысяч серверов — совершенно заурядное дело, и происходят много раз в день. Поэтому мы сильно сэкономим ручной труд администраторов, если хоть немного его автоматизируем.
На первый взгляд, всё это очень похоже на задачи YAMR — то же распределение вычислений, сбор результатов и обеспечение надёжности. Но есть два кардинальных отличия. Во-первых, FML имеет дело с поисковым индексом, а не с классической структурой «ключ-значение», принятой в YAMR. Поисковый индекс подразумевает, что все выборки происходят по комбинации сразу большого количества ключей (в простейшем случае — нескольких слов запроса). Работа с такими выборками в парадигме «ключ-значение» принципиально затруднена. А во-вторых, если YAMR сам решает, как разложить данные по серверам, то FML умеет работать с любым распределением данных, заранее заданным внешней системой по её собственным законам.
Решение оказалось настолько удачным, что большинство команд разработки Поиска по собственной инициативе перешло на использование FML, и, по нашим оценкам, сегодня около 70% (в смысле количества процессорного времени) вычислений в разработке Яндекс.Поиска находится под управлением FML.
Области применения и сравнение с аналогами
Как мы уже говорили, FML и Матрикснет являются частями технологии машинного обучения Яндекса. И используется она у нас не только в веб-поиске. Например, с её помощью подбираются формулы для так называемых «вертикальных» поисков (по изображениям, видео и т.п.) и для предварительного отсева совсем нерелевантных документов в веб-поиске. Она помогает обучать алгоритм классификации товаров по категориям в Яндекс.Маркете. Кроме того, машинное обучение подбирает формулы для поискового робота (например, для стратегии, которая определяет, в каком порядке обходить сайты). И во всех этих случаях решает одну и ту же задачу — строит функцию, которая наилучшим образом соответствует экспертным данным, поданным на вход. Думаем, в ближайшее время мы найдём для него ещё множество применений в Яндексе. Например, используем в обучении классификаторов, которых у нас очень много.
FML в паре с библиотекой машинного обучения Матрикснет может быть полезен не только в разработке поисковых систем, но и в других областях, где требуется обработка данных. С некоторыми коллективами мы уже опробовали их для построения поиска по специализированным видам данных с учётом специфических факторов. Например, CERN (Европейский Центр ядерных исследований) использует Матрикснет для обнаружения редких событий в больших объёмах данных (единицы на миллиард). Традиционно там использовался пакет TMVA, основанный на Gradient Boosted Decision Trees (GBDT). Поскольку Матрикснет на наших задачах и наших метриках давно стал точнее, чем простой GBDT, мы расчитываем, что и физики ЦЕРНа смогут использовать его для повышений точности своих исследований.
Почему Матрикснет может открыть дорогу Нобелевской премии
Один из видов событий, к подсчёту которых может быть применен FML/Матрикснет — это случаи распада странного B-мезона на мюон-антимюонную пару. Физически реальные показания одного из детекторов Большого Андронного Коллайдера после столкновения пучков протонов сравниваются с эталонными значениями, полученными в симуляторе событий.
Стандартная модель считает такие распады очень редким событием (примерно 3 события на миллиард столкновений). И если в результате анализа экспериментальных данных Матрикснет достоверно покажет, что таких событий больше и их количество совпадает с предсказаниями одной из новых физик, это будет означать справедливость этих теорий и может стать первым долгожданным поводом для вручения Нобелевской премии их авторам.
Стандартная модель считает такие распады очень редким событием (примерно 3 события на миллиард столкновений). И если в результате анализа экспериментальных данных Матрикснет достоверно покажет, что таких событий больше и их количество совпадает с предсказаниями одной из новых физик, это будет означать справедливость этих теорий и может стать первым долгожданным поводом для вручения Нобелевской премии их авторам.
Глядя более широко на то, что умеет наша технология, мы уверены, что она может быть полезна и во многих сферах, в которых встречаются типовые задачи машинного обучения — тем более, если они имеют дело с большим массивом данных, меняющимся во времени. Например, в крупных интернет-магазинах, онлайн-аукционах, социальных сетях.
Сейчас нам известно только одно промышленное решение для близкой задачи, помимо нашего собственного, — Google Prediction API. Есть и несколько стартапов, таких как BigML. К сожалению, мы не смогли найти сведений об их эффективности для тех или иных применений. В качестве конвейера для вычислительных задач может ещё служить Amazon Cloud Service, но его пристальное рассмотрение показало, что это очень общее решение, для совершенно произвольных задач. В то время как наше создано именно для поисковых и максимально раскрывается в них. Аналоги же FML в решении задач «Оценка эффективностипо нового фактора» и «Мониторинг качества факторов» нам и вовсе неизвестны.
Внешний наблюдатель может косвенно судить об эффективности нашей технологии, опираясь на результаты международных соревнований по машинному обучению. Например, специалисты Яндекса занимали высокие места в состязаниях по ранжированию Yahoo Learning to Rank и Facebook Recruiting, в которых борьба за точность ранжирующей функции идёт в терминах тысячных долей ERR/NDCG. Хорошие результаты они показывали на конкурсах по машинному обучению и в других областях.
Чтобы быть уверенными в том, что наши технологии остаются лучшими в своей области, мы регулярно проводим и собственные конкурсы по машинному обучению — в рамках серии «Интернет-математика». Среди тем: машинное обучение ранжированию, предсказание пробок на дорогах, классификация панорамных фото. Два года назад наши соревнования стали международными, и завершающий этап конкурса по пресказанию релевантности по поведению пользователей прошёл в рамках конференции WSDM 2012 в Сиэттле (США). Совсем недавно завершился конкурс, посвящённый прогнозированию переключения поисковой системы.
Несмотря на то, что фреймворк FML, о котором мы рассказали вам в этой серии постов, изначально создавался для работы с Матрикснетом, он может быть адаптирован к любой другой известной библиотеке машинного обучения (например, Apache Mahout, Weka, scikit-learn).Рекомендуемая литература
В последнее время появилось несколько хороших онлайн-курсов по машинному обучению. На английском можно порекомендовать курс Стенфордского университета, на русском — курс Константина Воронцова, который читается в Школе Анализа Данных.
Из «бумажных» изданий отметим два издания: The Elements of Statistical Learning: Data Mining, Inference, and Prediction (Trevor Hastie, Robert Tibshirani, Jerome Friedman) (доступна и в электронном виде) и Pattern Recognition and Machine Learning (Christopher M. Bishop).
Кроме этого, будет полезной обширная подборка курсов и учебников, собранная на Kaggle.