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

Вместе с Анной Вероникой Дорогуш, руководителем группы разработчиков СatBoost, Александром Крайновым, руководителем группы компьютерного зрения, и Михаилом Биленко, руководителем управления искусственного интеллекта и исследований Яндекса, мы поговорили о разнообразии методов машинного обучения, особой роли градиентного бустинга и специфике алгоритма СatBoost, который в ближайшее время заменит хорошо известный Матрикснет в качестве основного инструмента Яндекса.

N+1: Как так вышло, что искусственные нейросети на сегодняшний день затмили все прочие методы машинного обучения, которых на самом деле, даже судя по Википедии, очень и очень много?

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

N+1: То есть сочетание нескольких факторов и удачные иллюстрации в виде публичных проектов, вроде AlphaGo, DeepDream, — в этом все дело?

Михаил: И это тоже, но они скорее были следствием. Просто у больших лабораторий, которые занимались сетями, сразу же появились еще бóльшие бюджеты, то есть появился некий маховик, и на этом маховике возник DeepMind, который на свой отдельный бюджет от Google сумел сделать AlphaGo. Не то чтобы все эти вещи были революционными, просто они с разных сторон выстреливают, поэтому создается впечатление, что происходит какой-то фейерверк.

Михаил Биленко, руководитель управления искусственного интеллекта и исследований Яндекса

Александр: У каждого метода машинного обучения есть свои преимущества. Нейронная сеть показывает свое преимущество в end-to-end обучении, то есть когда мы берем сырые данные и нам не нужно, что называется, feature-инжинирить (Специально готовить признаки для модели, основываясь на хорошем понимании задачи и свойств исходных данных. — Прим. N+1). А значит, не нужно быть специалистом в предметной области. Для того чтобы обучить нейронную сеть играть в го, вообще-то даже не обязательно знать правила го. Поэтому можно очень быстро что-то сделать в той области, которой раньше рука машинного обучения даже не касалась, не будучи в ней специалистом. Поэтому мы видим очень много ярких, красивых проектов, какие-то стартапы, какие-то неожиданные свершения, все это выглядит фантастически и эффектно. Например, нейронная сеть пишет музыку, а люди, которые написали эту нейронную сеть, не разбираются в нотах, но им это нисколько не мешает.

N+1: А какие бы вы выделили методы машинного обучения, которые на сегодняшний день «живы» и не оказались «задвинуты» бурно развивающимися нейросетями?

Хором: Они все живы.

Анна Вероника: Если мы говорим об обучении с учителем, есть, во-первых, линейные модели. Они нужны, например, если вам важно получить интерпретируемый результат после обучения. Скажем, в медицине очень важно понимать, что же именно модель строит. В таком случае линейную модель очень удобно использовать, потому что веса очень легко интерпретировать, понимать, насколько значим тот или иной фактор, а в зависимости от знака, с плюсом или с минусом, — в какую сторону он значим.

N+1: Кажется, что линейные модели — это самый простой, самый примитивный подход. Грубо говоря, если человек в Excel строит по десяти точкам линейную регрессию, формально он тоже использует линейные модели, хотя тут каким-то серьезным машинным обучением даже не пахнет.

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

Анна Вероника Дорогуш, руководитель группы разработчиков СatBoost

Анна Вероника: У нас в Яндексе линейные модели тоже очень активно используются, в рекламе, например, это вполне живые методы. Есть и другие подходы, конечно. Скажем, есть группа методов ближайших соседей. Тоже, казалось бы, очень простые методы, но широко используются. Кстати, часто в сочетании с нейросетями.

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

Анна Вероника: В большинстве случаев имеет смысл использовать какие-то комбинации методов. Эти вещи можно часто встретить на Kaggle (kaggle.com, один из крупнейших порталов, посвященных обработке данных и машинному обучению, на нем проводятся крупные соревнования разработчиков. — Прим. N+1). Там есть такое понятие как «стакинг», когда ты обучаешь много разных сложных методов и для уменьшения ошибки суммируешь их, получая лучший результат.

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

N+1: Если почитать, что пишут про Яндекс в контексте машинного обучения, то чаще всего речь идет об алгоритме Матрикснет, который используется в большинстве сервисов Яндекса и представляет собой градиентный бустинг на решающих деревьях. Почему вы используете именно этот метод? Если все прочие методы живы и все в каком-то смысле хороши?

##

Давайте сделаем отступление и разберемся, что такое решающие деревья и зачем им еще какой-то бустинг. Как вы помните, любой метод машинного обучения с учителем можно представить как функцию f(X) = A, где Х — ваши входные данные, а А — ответ. Например, Х — кредитная история клиента, А — решение по кредиту, или Х — картинка, А — вероятность того, что на ней изображен кот.

Есть очень простой метод, с помощью которого можно получать ответы А. Давайте построим решающее дерево, которое будет принимать решение о выдаче кредита. С виду оно будет напоминать типичный онлайн-тест вроде «Кто ты из супергероев?» Сначала спросим «Зарплата в месяц больше или меньше 50000 рублей?» Если больше — пойдем в правую ветку дерева, если меньше — в левую. Например, если наш банк осторожный и в левой ветке сразу поставит отказ в выдаче кредита, то на этом вопросы закончатся и ветку объявят листом (потому что она дальше не растет). А правая ветвь продолжится вопросом: «Есть ли непогашенные кредиты?» Если есть — идем налево, в еще один лист с отказом, если нет — идем вправо, в лист с положительным решением.

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

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

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

Давайте для начала построим очень, очень простое дерево, почти такое, как мы описали выше, всего из нескольких вопросов. Очевидно, что оно даст огромную ошибку на реальных данных и использовать его нельзя. Но теперь давайте построим новое дерево и учить его будем с учетом ошибки, которую выдало первое дерево. Поскольку дерево у нас опять будет очень простым, полностью мы ошибку не погасим, но новая ошибка, если все правильно сделать, будет уже меньше. Построим третье дерево, которое будет стараться скомпенсировать вторую ошибку, и так далее. Слово «градиент» в названии означает, что каждое наше новое дерево будет построено так, чтобы «спускаться» в направлении уменьшения ошибки. Тогда, построив достаточное количество деревьев, мы сможем получить неплохой результат. Здесь уже нужно будет не усреднять, а суммировать результаты всех деревьев, чтобы получить ответ для каких-то новых данных.

Анна Вероника: У градиентного бустинга есть важные достоинства. Прежде всего, он дает очень хорошие результаты. Если у вас есть большая выборка, можно обучить модель и получить ответ с лучшей точностью в сравнении с такими методами, как «случайный лес» или AdaBoost. К тому же у градиентного бустинга есть свои особенности обучения и применения. Например, нам принципиально важно, особенно в поиске, чтобы применение модели работало быстро, чтобы пользователь быстро получал ответ. Вот градиентный бустинг как раз можно быстро применить, а тот же самый метод ближайших соседей, например, нет.

Михаил: Ведь эта модель — это просто ансамбль деревьев, и неважно, сделан он при помощи случайного леса или бустинга, это просто куча правил, ответов на простые вопросы. И это хорошо тем, что это параллелится (Распределяется по нескольким процессорам. — Прим. N+1). Кстати, есть одна вещь, которая уникальна для Матрикснета, это то, что исторически называется oblivious trees, или симметричные деревья.

##

Особенность симметричных деревьев в том, что после каждого разветвления вопросы дублируются. В нашем примере с кредитной историей после вопроса «Зарплата больше или меньше 50000 рублей» в симметричном дереве дальше в обоих ветках последовал бы вопрос «Есть ли непогашенные кредиты?», и так далее. Такая структура приводит к тому, что симметричное дерево на самом деле можно заменить простой таблицей, а таблицу, очевидно, применять гораздо быстрее. Представьте сами, где проще искать ответ: в дереве, водя пальцем от вершины к вершине, или в таблице, где нужно найти только столбец и строку?

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

Михаил: Да, бустинговые деревья на самом деле везде доминируют. Точно так же и больше половины кагглеров (Участников соревнований на kaggle.com. — Прим. N+1) перешли на XGBoost (Популярная открытая реализация градиентного бустинга. — Прим. N+1).

Анна Вероника: Кстати, если говорить про нейросети, то они у нас используются для подготовки признаков для градиентного бустинга. И не только у нас.

N+1: Получается, что Матрикснет — это в итоге тоже какая-то комбинация?

Михаил: На большой рабочей сцене всегда присутствуют многие компоненты: линейные, сетевые, какие угодно, какие-то старые подходы к деревьям. Но обычно основные «сливатели» всего — это градиентные бустинги.

N+1: Кстати, на февральской лекции, посвященной Матрикснет, вы показывали табличку, где ваши результаты сравнивались с тем же XGBoost и другими методами. И везде Матрикснет выигрывал, кроме, кажется, одного показателя. За счет чего так получилось? Ведь XGBoost же сравнительно молодой, а у Матрикснета десятилетний юбилей не за горами.

Михаил: (смеется)

Ну, это скорее из разряда «Почему в этом году Audi выиграла у BMW на Нюрбургринге? (Легендарная гоночная трасса в Германии. — Прим. N+1)

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

Сравнение результатов CatBoost с близкими аналогами на стандартных наборах данных. Yandex

N+1: Если Матрикснет жил-жил, улучшался, всех побеждал, тогда зачем вы разработали новый алгоритм — CatBoost? Это совсем новый релиз или очередная итерация Матрикснета, которую вы решили выделить в отдельный проект?

Анна Вероника: Матрикснет — это огромный проект, очень сильно оптимизированный, с десятилетним прошлым, он есть на CPU, GPU, в нем есть распределенное обучение с очень сложной схемой пересылки данных… Это большой и сложный проект. А CatBoost начинался как экспериментальный проект, который родился из определенного вопроса: вот есть числовые признаки, а есть категориальные — что с ними делать?

##

Категориальные признаки — это хорошо известный камень преткновения для многих методов машинного обучения. Это те признаки, в которых нет чисел. То есть в той же самой истории про кредит у вас может быть признак «зарплата», он числовой, так как ему соответствует какое-то число. А может быть признак «профессия», которому будет соответствовать какое-то слово, которое вычислительной модели ни о чем не говорит. И сложность в работе с категориальными признаками заключается как раз в необходимости их оцифровать и «вписать» в модель.

N+1: Ага, то есть CatBoost — это полноценный преемник Матрикснета? И он делает все то же самое, плюс еще с категориальными переменными лучше справляется?

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

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

Александр: Да, у нас очень много автоматических процессов настроено на Матрикснет, и люди даже не до конца понимают, что там под капотом — ведь все налажено. Заменить все это аккуратно в большой, сложной, годами настраиваемой системе, чтобы это все не развалилось, конечно, очень сложно.

N+1: Но в итоге цель именно такая?

Михаил: Да.

N+1: А что же такого придумано в CatBoost, что он хорошо справляется с категориальными признаками?

##

Возможно, вам уже пришла в голову идея, как быть с категориальными переменными: давайте ветвить дерево не на два пути, а на столько, сколько значений имеется у нашего категориального признака. Например, если признак — это порода собак, и пород этих в ваших данных будет всего девять, то давайте сразу поделим выборку на девять ветвей и дальше будем с ними работать. Такой подход существует и называется N-way-split, то есть деление на N ветвей. И он в целом был бы неплох, если бы не приводил к быстрому переобучению, так как деревья в таком подходе получаются ну очень ветвистые. Представьте себе, что одним из ваших категориальных признаков является «ID пользователя», которых в наборе данных могут быть сотни тысяч. Делить дерево на сотни тысяч ветвей — плохая идея. Конечно, не все так ужасно, и для N-way-split придуманы многие способы, которые снижают риск переобучения и заставляют этот метод работать, но это отдельная история.

Кардинально другой способ — это заменить значения категориальных переменных на какое-то число. Тогда ваша модель подумает, что категориальных признаков вообще не бывает и все признаки — числовые, заморачиваться не надо. Как придумать это число? Самый простой метод — это пронумеровать все значения для каждого признака. То есть в примере с породой собак вы получите не список «спаниель», «пудель», «дворняга» и так далее, а числа 0, 1, 2 и так до 8. Но, как вы понимаете, такой подход никаким образом не отражает роль или значимость данного признака в вашей выборке. Хотя на самом деле порода может сильно повлиять на ответ, который вас интересует, например, оценку стоимости щенка. Вряд ли дворняга будет стоить столько же, сколько и тибетский мастиф.

Еще один способ — вместо одного признака «порода собак» ввести девять новых признаков. Да-да, ввести признаки «дворняга», «спаниель» и далее по списку. И для каждого примера в вашей выборке вы будете ставить «1» в колонку с соответствующей породой и «0» во все остальные. Теперь модель сможет отличать одну породу от другой и, например, дворняге присвоить меньший вес, чем мастифу. Этот метод называется one-hot-encoding, и он неплохо работает.

Наконец, самый продвинутый метод — это использование так называемых «счетчиков». Например, вам нужно классифицировать всех собак в вашей выборке по двум группам — класс «0» и класс «1», скажем, для оценки вероятности победы каждой собаки в конкурсе («1» — победит, «0» — нет). Тогда для каждой конкретной породы вы можете посчитать, сколько собак из вашей выборки побеждало прежде, то есть входит в класс «1» (пусть таких будет m), и поделить это на число всех собак данной породы, N. Фактически, вы получите вероятность m/N, которая показывает, насколько велик шанс, что данная порода принадлежит к первому классу и, следовательно, может рассчитывать на победу в следующий раз. Для вашей модели это ценная информация, она несет какой-то смысл, в отличие от простых названий пород, поэтому заменив ваши категориальные значения на соответствующие вероятности, вы эффективно переведете этот признак в разряд числовых. Этот метод обработки категориальных признаков в последние годы особенно популярен.

Анна: Представим себе категориальную переменную, например, тип облаков, которые могут быть кучевые, перистые и так далее. Каждый из этих типов мы хотим каким-то образом заменить на число. Как это можно сделать? Мы можем использовать простые счетчики, но на самом деле они не очень хорошо работают, потому что приводят к переобучению: происходит утечка данных и модель «запоминает» свою обучающую выборку, свой пример. Давайте не будем его ей показывать! Сделаем leave-one-out: для расчета счетчика на каждом объекте обучающей выборки не будем использовать его самого, будем смотреть только на все остальные примеры. Так утечка информации будет меньше, но в конце концов это тоже не работает: рано или поздно модель все равно запомнит свою обучающую выборку и переобучится. Еще, конечно, можно делать leave-bucket-out. Это такое обобщение leave-one-out, когда мы смотрим на все, кроме некоторой группы. К сожалению, это тоже работает не лучшим образом, и опять по тем же причинам.

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

***N+1**: Что же тогда остается для пользователя?

Анна: Для пользователя при желании все еще остается подбор гиперпараметров (Параметры, которые не подстраиваются автоматически в ходе обучения, а задаются извне. — Прим. N+1). Все открытые реализации градиентного бустинга требуют аккуратной настройки параметров. Если запустить многие популярные алгоритмы с исходными параметрами, а потом подобрать их поточнее и посмотреть, что получилось, то разница будет огромной. А вот у Матрикснет и CatBoost такой проблемы нет, в них дефолтные параметры подобраны так, что с ними уже получается очень хороший результат. Но на некоторые параметры смотреть все еще нужно. Обязательно нужно выбирать правильное число деревьев, для этого надо использовать тестовые данные и выбирать итерацию, на которой на них перестает падать ошибка. В CatBoost для этого есть детектор переобучения — он сам за тебя поймет, что ты переобучился, и сохранит тебе модель на лучшей итерации. Что касается дефолтных параметров, то у нас есть несколько «волшебных» значений, которые работают лучше всего, это learning rate 0,03 (Шаг обучения — с какой скоростью алгоритм будет уменьшать ошибку на каждой итерации. — Прим. N+1) и глубина дерева 6. Бывает и так, что на каких-то наборах данных нужно менять значения этих параметров, например, на некоторых физических данных нужно увеличивать глубину.

N+1: Я правильно понимаю, что CatBoost будет открытый?

Анна Вероника: Да. Мы, кстати, недавно выложили на arXiv статью с описанием еще одной особенности алгоритма — схемы обучения, благодаря которой уменьшается утечка.

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

N+1: Понятно. Получается, будет совсем открытая имплементация, как у того же XGBoost, когда можно скачать питоновскую библиотеку?

Михаил: Прямо так и будет, в момент релиза. Можно будет брать и играться.

Беседовал Тарас Молотилин

P.S. Запуск проекта прошел сегодня, 18 июля, так что все библиотеки уже можно скачать на странице CatBoost на GitHub. Там же вы найдете официальную документацию, обучающие примеры и программу для визуального анализа результатов CatBoost-Viewer.