Бустинг — ещё один способ машинного обучения

Мы уже гово­ри­ли об общем прин­ци­пе рабо­ты ней­ро­се­тей для машин­но­го обу­че­ния. Раз­бе­рём дру­гой — бустинг. Кто кого бустит и зачем?

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

Дерево решений

Что­бы понять бустинг, нуж­но сна­ча­ла понять дере­во реше­ний. Вот это — очень про­стое дере­во:

Сей­час это дере­во реше­ний, но может быть дере­вом пред­ска­за­ний. Пред­ставь­те, что в заго­лов­ке дере­ва напи­са­но «Вый­дет ли Юзер­нейм гулять?» — и вы полу­чи­те маши­ну пред­ска­за­ний, кото­рая на осно­ве дан­ных о Юзер­ней­ме и пого­де будет стро­ить точ­ные пред­ска­за­ния о Юзер­ней­ме — при усло­вии, что мы зада­ём пра­виль­ные вопро­сы.

Машина предсказания

Теперь при­мер слож­нее. Допу­стим, у нас есть дан­ные по мил­ли­о­ну музы­каль­ных кли­пов на Юту­бе. По каж­до­му есть 100 кри­те­ри­ев, напри­мер:

  • Длит­ся ли клип доль­ше трёх минут.
  • Есть ли там пря­мая боч­ка.
  • Этот трек в жан­ре «хип-хоп» или нет.
  • Выпу­стил ли клип попу­ляр­ный лей­бл.
  • Запи­сан ли клип во дво­ре на мобиль­ный теле­фон.

Так­же у нас есть дан­ные о том, набрал ли клип боль­ше мил­ли­о­на про­смот­ров. Мы хотим научить­ся пред­ска­зы­вать этот кри­те­рий — назо­вём его попу­ляр­но­стью. То есть мы хотим полу­чить некий алго­ритм, кото­ро­му на вход пода­ёшь 100 кри­те­ри­ев кли­па в фор­ма­те да/нет, а на выхо­де он тебе гово­рит: «Это­му кли­пу суж­де­но стать попу­ляр­ным».


Мил­ли­он кли­пов, сто кри­те­ри­ев — обу­ча­ю­щая выбор­ка для алго­рит­ма

Первая проблема

Если мы захо­тим постро­ить дере­во пред­ска­за­ний для этой зада­чи, мы столк­нём­ся с про­бле­мой: мы не зна­ем, какие кри­те­рии ста­вить в нача­ло, а какие в конец, какие запи­хи­вать в какие вет­ки, а какие вооб­ще не нуж­ны и пото­му не вли­я­ют.

Первый шаг решения

Что­бы постро­ить дере­во для такой зада­чи, мы долж­ны будем сна­ча­ла посчи­тать, насколь­ко каж­дый кри­те­рий свя­зан с жела­е­мым резуль­та­том:


Сре­ди мил­ли­о­на кли­пов в обу­ча­ю­щей выбор­ке 300 000 выпу­сти­ли извест­ные лейб­лы. 120 000 из них ста­ли попу­ляр­ны. Этот кри­те­рий луч­ше дру­гих пред­ска­зы­ва­ет попу­ляр­ность

В ито­ге мы видим, что самая силь­ная связь с ито­го­вой попу­ляр­но­стью у кри­те­рия «Выпу­стил ли клип попу­ляр­ный лей­бл». Полу­ча­ет­ся, если клип выпу­стил лей­бл, это вли­я­ет на успех силь­нее, чем боч­ка или авто­тюн. Этот кри­те­рий вста­ёт на вер­ши­ну дере­ва.

Затем мы смот­рим, какой кри­те­рий поста­вить сле­ду­ю­щим. Берём те 300 000 кли­пов, кото­рые выпу­сти­ли лейб­лы, и про­го­ня­ем их по осталь­ным кри­те­ри­ям. Ищем тот, кото­рый даёт самую высо­кую ито­го­вую точ­ность пред­ска­за­ния.


Сре­ди 300 000 кли­пов, кото­рые выпу­сти­ли лейб­лы, 250 000 кли­пов идут доль­ше 3 минут и 90 000 из них набра­ли боль­ше мил­ли­о­на про­смот­ров. Этот кри­те­рий луч­ше дру­гих пред­ска­зы­ва­ет попу­ляр­ность кли­пов лей­б­ла

Ста­вим его на вто­рое место.

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

Оп, у нас появи­лось дере­во реше­ний:


Боль­шин­ство кли­пов не взле­тит, но какие-то ста­нут попу­ляр­ны­ми

Случайный лес

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

Возь­мём слу­чай­ную выбор­ку из наших исход­ных дан­ных. Не мил­ли­он кли­пов, а 10 000. К ним — слу­чай­ный набор кри­те­ри­ев, не все 100, а 5:

И постро­им дере­во попро­ще:


Было мно­го уров­ней, ста­ло мень­ше

Так постро­им ещё несколь­ко дере­вьев, каж­дое — на сво­ём набо­ре дан­ных и сво­ём набо­ре кри­те­ри­ев:


Лес алго­рит­мов

У нас появил­ся слу­чай­ный лес. Слу­чай­ный — пото­му что мы каж­дый раз бра­ли ран­дом­ный набор дан­ных и кри­те­ри­ев. Лес — пото­му что мно­го дере­вьев.

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


Три за, один про­тив — клип ждёт успех. Навер­ное

Неслучайный лес — бустинг

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


Пер­вое дере­во может давать мно­го оши­бок

Теперь дела­ем сле­ду­ю­щее дере­во. Обра­тим вни­ма­ние на места, где пер­вое дере­во ошиб­лось. Дадим этим ошиб­кам боль­ший вес при под­бо­ре дан­ных и кри­те­ри­ев для обу­че­ния. Зада­ча — сде­лать дере­во, кото­рое испра­вит ошиб­ки преды­ду­ще­го.


Учим дере­во исправ­лять ошиб­ки пред­ше­ствен­ни­ка

Но вто­рое дере­во наде­ла­ет сво­их оши­бок. Дела­ем тре­тье, кото­рое их испра­вит. Потом чет­вёр­тое. Потом пятое. Вы поня­ли прин­цип.

Дела­ем такие дере­вья, пока не достиг­нем жела­е­мой точ­но­сти или пока точ­ность не нач­нёт падать из-за пере­обу­че­ния. Полу­ча­ет­ся, у нас мно­го дере­вьев, каж­дое из кото­рых не очень силь­ное. Но вме­сте они скла­ды­ва­ют­ся в лес, кото­рый даёт хоро­шую точ­ность. Бустинг!

И где это используют?

Бустинг часто исполь­зу­ют в зада­чах, когда ней­рон­ные сети не очень под­хо­дят.

Ней­ро­се­ти хоро­шо справ­ля­ют­ся с одно­род­ны­ми дан­ны­ми, напри­мер изоб­ра­же­ни­я­ми или голо­сом. А вот если дан­ные раз­но­го харак­те­ра и с раз­ной струк­ту­рой, то бустинг справ­ля­ет­ся луч­ше. Напри­мер, что­бы пред­ска­зать пого­ду, надо учесть тем­пе­ра­ту­ру и влаж­ность, дан­ные с рада­ров, наблю­де­ния поль­зо­ва­те­лей и дру­гие пара­мет­ры. Бустинг с этим справ­ля­ет­ся отлич­но.

Вот что про бустинг рас­ска­зы­ва­ет Роман Хал­ке­чев, руко­во­ди­тель отде­ла ана­ли­ти­ки в Яндекс.Еде:

«В Яндек­се повсе­мест­но исполь­зу­ем биб­лио­те­ку CatBoost. Это внут­рен­няя раз­ра­бот­ка, кото­рую в 2017 году выло­жи­ли в open source. Она помо­га­ет решать мно­го задач, напри­мер, ран­жи­ро­ва­ние в Поис­ке, пред­ска­за­ние в Пого­де, реко­мен­да­ции в Музы­ке.

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

С одной сто­ро­ны, мы не хотим терять заказ. С дру­гой — не хотим разо­ча­ро­вы­вать поль­зо­ва­те­ля, кото­рый начал поиск так­си, но так и не смог уехать, пото­му что нико­гда не нашлось.

С помо­щью CatBoost мы реши­ли научить­ся пред­ска­зы­вать, смо­жем ли най­ти для кон­крет­но­го поль­зо­ва­те­ля маши­ну после вызо­ва. Это зада­ча клас­си­фи­ка­ции — нуж­но отне­сти поль­зо­ва­те­ля к одной из двух групп: «Смо­жем най­ти маши­ну» или «Не смо­жем най­ти маши­ну». Мы ори­ен­ти­ро­ва­лись на мет­ри­ки precision и recall. Они поз­во­ля­ют най­ти баланс надёж­но­сти: не наобе­щать лиш­не­го, но и не поте­рять зака­зы.

В ито­ге бла­го­да­ря ново­му меха­низ­му совер­ша­ет­ся око­ло 1% от всех поез­док, а в неко­то­рых горо­дах и рай­о­нах — до 15%».

Почи­тай­те пол­ное интер­вью с Рома­ном, там мно­го про ана­ли­ти­ку и машин­ное обу­че­ние на прак­ти­ке →

Текст:
Вяче­слав Уфим­цев
Сове­ты:
Роман Хал­ке­чев
Редак­тор:
Мак­сим Илья­хов
Кор­рек­тор:
Ири­на Михе­е­ва
Вёрст­ка:
Мария Дро­но­ва
Худож­ник:
Дани­ил Бер­ков­ский
Раз­нёс весть:
Вита­лий Вебер
Во сла­ву:
пла­не­тар­но­го дре­ва дан­ных