[ЗАСТАВКА] В этом видео мы поговорим о случайных лесах, которые являются одним из лучших способов объединения деревьев в композиции. В прошлый раз мы выяснили, что ошибка любого алгоритма на контрольной выборке складывается из шума смещения и разброса, при этом на шум мы никак повлиять не можем. Усреднение базовых алгоритмов не меняет смещение, то есть если базовые алгоритмы были сильные, то и композиция будет довольно сильной, способной восстанавливать сложные закономерности, а вот разброс усреднение уменьшает, и при этом чем менее коррелированы базовые алгоритмы, тем сильнее будет уменьшение разброса при усреднении. Мы обсудили два способа понижения корреляции между базовыми алгоритмами, а именно бэггинг, когда мы обучаем каждый базовый алгоритм в случайном подмножестве объектов, и метод случайных подпространств, когда мы обучаем каждый базовый алгоритм на случайном подмножестве признаков. Их можно объединять, использовать одновременно и тот, и другой. Но их оказывается мало, и чтобы добиться еще более маленькой корреляции между базовыми алгоритмами, имеет смысл сделать более случайным процесс построения этих базовых алгоритмов. Давайте подумаем, как можно сделать рандомизированным процесс построения решающих деревьев. Для этого вспомним, как он устроен. Итак, решающее дерево строится жадно. Мы начинаем с одной вершины, разбиваем ее на две и далее производим ветвление уже этих двух поддеревьев, этих двух вершин до тех пор, пока не будет выполнен некоторый критерий останова. При этом разбиение мы осуществляем следующим образом. Нам нужно найти такое условие разбиения, а условия у нас очень простые, они проверяют j-тый признак и сравнивают его значение с некоторым порогом t. Если значение j-того признака меньше или равно этого порога, то объект идет в левое поддерево, если больше порога, то в правое поддерево. И нам нужно выбрать такие признак j и порог t, при которых будет достигаться минимум некоторого критерия ошибки, который характеризует, насколько хорошо разбивать данную вершину именно по такому условию, именно таким способом. И мы искали лучший признак j и порог t просто перебором, поскольку их – конечное число. Рандомизировать процесс можно следующим образом: будем искать лучший признак j для разбиения не из всех возможных признаков выборки, а из некоторого случайного подмножества признаков, и размер этого подмножества будет равен некоторой константе q. Оказывается, что этот подход действительно позволяет сделать деревья менее коррелированными. На этом графике по оси x отложено q, то есть то, из скольки случайно выбранных признаков мы выбираем лучшие при конкретном разбиении, а по оси y отложена корреляция между двумя базовыми решающими деревьями. Видно, что чем меньше q, чем меньше простор при выборе лучшего разбиения, тем меньше корреляция между решающими деревьями. Разница в корреляции при выборе абсолютно случайного признака, если q = 1, и при выборе из всего множества признаков, достигает несколько раз. Корреляция уменьшается в несколько раз при уменьшении q. Для q есть некоторые рекомендации, которые неплохо работают на практике. Если мы решаем задачу регрессии, то имеет смысл брать q = d/3, то есть 1/3 от общего числа признаков. Если мы решаем задачу классификации, то имеет смысл брать q = √d, корню из числа признаков. Итак, давайте полностью проговорим, как устроен алгоритм построения случайного леса. Мы хотим построить композицию из N решающих деревьев. Что мы делаем для построения каждого из них? Сначала мы генерируем случайную подвыборку X с волной с помощью бутстрапа. После этого мы обучаем на этой выборке X с волной очередное решающее дерево bn(x). И построение обладает двумя особенностями: во-первых, мы строим дерево до тех пор, пока в каждом листе окажется не более некоторого числа объектов n минимальное. Очень часто эту константу берут равной 1, то есть строят деревья до конца, до тех пор, пока в каждом листе не окажется по одному объекту обучающей выборки. В результате мы получим очень сложные, очень переобученные решающие деревья с низким смещением, но это нам и нужно при построении композиции. Также при выборе оптимального разбиения при построении дерева мы ищем лучший признак не из всех признаков выборки, а из случайного подмножества признаков размера q. Обратите внимание, что случайное подмножество размера q выбирается заново при каждом новом разбиении вершины. Этим подход отличается от метода случайных подпространств, где мы выбираем случайное подмножество один раз перед построением базового алгоритма, здесь же оно будет свое в каждой вершине. Далее мы объединяем построенные деревья в композицию. Если это регрессия, то мы просто усредняем их, если это классификация, то мы берем знак от среднего ответа. Одна из особенностей случайных лесов состоит в том, что они не переобучаются при росте числа базовых алгоритмов. На этом графике изображена зависимость качества случайных лесов при разном значении параметра q в зависимости от числа базовых алгоритмов. Видно, что при росте числа базовых алгоритмов ошибка на тесте уменьшается, в какой-то момент выходит на асимптоту и остается на этом уровне, не происходит роста ошибки при росте числа базовых алгоритмов. Итак, мы разобрались, что такое случайный лес. Это композиция решающих деревьев, в которой эти решающие деревья строятся довольно случайно: при каждом разбиении оптимальный признак выбирается из случайного подмножества признаков. За счет этого сильно уменьшается корреляция между деревьями, и поэтому разброс композиции получается довольно низким. Особенность случайного леса состоит в том, что он не переобучается при росте числа базовых алгоритмов. За счет этого случайный лес считается одним из самых универсальных алгоритмов. У него практически нет гиперпараметров. Мы можем брать просто довольно большое число базовых деревьев и при этом будем получать хороший, не переобученный алгоритм. В следующем видео мы поговорим о различных трюках, которые можно делать со случайными лесами.
