[ЗАСТАВКА] В машинном обучении нередки ситуации, когда мы строим классификатор, он не удовлетворяет нас по качеству, мы пытаемся строить другой, второй, третий — все они оказываются не очень удачными. Возникает вопрос: можем ли мы из большого числа слабых классификаторов каким-то образом получить один агрегированный классификатор, который будет работать лучше? Рассмотрим такую постановку задачи: у нас имеется, как обычно, обучающая выборка. Объекты и соответствующие им ответы — это метки классов (+/−1). И мы построили некоторое количество базовых классификаторов — T. Простым голосованием называется такой классификатор, который относит объект x к тому классу, к которому его отнесли большинство базовых классификаторов. Это, наверное, самый простой способ агрегирования, и он, конечно же, имеет прямую аналогию в измерении физических величин, когда мы одну и ту же величину измеряем многократно. Если эти измерения независимы, то точность усредненного измерения будет повышаться с увеличением числа измерений. Что-то похожее происходит и в данном случае, только мы не можем, конечно же, говорить, что базовые алгоритмы являются независимыми случайными величинами, поскольку все они настраиваются на решение одной и той же задачи. Но все же у нас есть немало инструментов для повышения различности базовых алгоритмов. Вот чтобы у нас простое голосование работало и улучшало качество, базовые алгоритмы должны быть, с одной стороны, не слишком плохие, хотя бы немножко лучше, чем случайное гадание, и они должны быть различны. Повышать различность можно путем обучения базовых алгоритмов по разным случайным подвыборкам, можно обучать их по одной и той же выборке, но случайным образом менять веса обучающих объектов, можно обучать их по случайным подмножествам признаков, можно использовать различные модели классификации, различные начальные приближения, или рандомизировать сам процесс обучения базовых алгоритмов. Рассмотрим один из самых известных методов повышения различности базовых алгоритмов. В этом методе базовые алгоритмы обучаются независимо друг от друга по случайным подвыборкам. Метод называется бэггинг — это искусственное слово, образованное от слов bootstrap aggregation. А bootsrap в статистике — это такой способ формирования выборки, когда выбирается ровно столько же объектов, сколько их исходно было, но объекты выбираются с повторениями. То есть, как только вы выбрали случайный объект, вы его возвращаете обратно и можете выбрать его повторно. И при этом число объектов, которое вы выберете в выборку, оно будет составлять примерно 63 % от исходной выборки, и оставшаяся доля объектов ни разу не попадет в такую сэмплированную выборку. И вот по таким случайным подвыборкам, в которых некоторые объекты будут по несколько раз, но объем этой выборки равен объему исходной выборки, и предлагается обучать базовые алгоритмы. Они будут обучаться совершенно независимо друг от друга — это некое преимущество, которое позволяет легко распараллеливать этот метод. Есть другой подход, который называется метод случайных подпространств. Вы выбираете некоторое число n' — сколько признаков вы будете отбирать из числа исходных n признаков, и по полученным случайным подпространствам опять-таки можете строить базовый классификатор, причем нет никаких ограничений на использование тех или иных моделей классификаций в качестве базовых классификаторов. Эти два подхода можно совместить в одном алгоритме. Допустим, у нас имеется n признаков и некий метод обучения, который способен обучиться по подвыборке, используя только подмножество признаков. То есть J — это подмножество признаков, а U — это подвыборка. Алгоритм очень простой, он заключается в том, что вы, задавшись длиной обучающих подвыборок, длиной признаковых подописаний и двумя порогами ε1 и ε2, делаете следующую работу: вы T раз обучаете базовый алгоритм по выбранному случайному подмножеству заданной длины l' на выбранном случайном подмножестве признаков из n' штук и получаете алгоритм bt. Но беда в том, что этот алгоритм может оказаться и неудачным, и вы используете как раз 2 порога, для того чтобы оценить, достаточно ли хорош этот алгоритм получился на обучающей выборке — за это отвечает порог ε1. Но если вы обучение делали лишь по части обучающих объектов, как это происходит в бэггинге, то тогда на оставшейся части объектов вы можете посмотреть, обладает ли построенный базовый алгоритм обобщающей способностью. Если она недостаточно высока, то вы не будете брать этот базовый алгоритм в композицию, вы его просто выкинете и будете строить следующий. То есть, таким образом получается, что у нас есть 4 параметра в этом алгоритме, с помощью которых можно управлять качеством базовых алгоритмов. Ну и как только вы их построили, вы их объединяете с помощью простого голосования в композицию. Развитием этой идеи стал метод, который получил название случайного леса. Это специальный случай бэггинга, когда в качестве базового семейства используются решающие деревья, при этом, в отличие от обычных способов построения решающих деревьев, вы здесь не используете усечение (или pruning). Вообще, метод настроен на то, чтобы построить композицию как можно быстрее, чтобы можно было строить композиции по большим выборкам данных. Дальше построение дерева тоже производится весьма специфическим образом. Когда вы выбираете признак для каждого внутреннего узла в этом решающем дереве, вы его выбираете не из всего множества n признаков, а из какого-то случайного подмножества, состоящего из k признаков. Причем, если дерево строится для классификаций, то рекомендуется брать k, равном корню квадратному из числа признаков, а если для регрессии — то число признаков делить на 3. Это эмпирические рекомендации. Вот, оказывается, что если таким образом строить бэггинг над решающими деревьями, мы получим большое количество решающих деревьев, их простое голосование как раз и называется случайным лесом. Оказалось, что этот алгоритм чрезвычайно эффективен, и он очень быстро обучается и очень хорошо решает практические задачи — вот как ни странно, несмотря на то, что столько было внесено случайности в процесс построения решающего леса, тем не менее, вот оказывается, что простое голосование делает из этих неточных, не очень хорошо построенных деревьев очень хороший агрегированный алгоритм классификации. Есть еще несколько моментов, которые хотелось бы уточнить про этот алгоритм. Как понять, что мы должны остановиться, что нам достаточно данного числа деревьев? Вот обычно за оптимизацию такого рода структурных параметров отвечают критерии типа скользящего контроля. Что хорошо в случайном лесе? То, что мы можем для каждого объекта оставить те алгоритмы из числа базовых классификаторов, которые не обучались на этом объекте, этот объект не входил в состав обучающей выборки для них. И вот такая оценка, которая произведена... для каждого объекта произведена только по тем базовым алгоритмам, которые на нем не обучались, она обладает очень хорошими статистическими свойствами. Она является несмещенной оценкой обобщающей способности полученной композиции и называется out-of-bag, то есть использование тех объектов, которые не входили в состав обучающей выборки для каждого базового алгоритма. И вот эта вот оценка, поскольку она характеризует обобщающую способность, она очень удобна для того, чтобы выбирать число деревьев, и не только для этого — разные параметры можно оптимизировать по этой оценке, ну вот, в частности, параметр k можно оптимизировать и подобрать лучший под данную задачу. Также эта оценка может быть использована для того, чтобы оценивать важности признаков. Есть разные методики, одна из них заключается в том, чтобы по построенному дереву определить, какой признак самый полезный. Если вы перемешиваете случайным образом значения признаков на объектах обучающей выборки и видите, что это сильно ухудшает оценку out-of-bag, значит, этот признак полезный. Итак, резюмируем. Random Forest или «случайный лес» — это один из самых сильных методов машинного обучения. Он основан на бэггинге — на способе построения композиций классификаторов, при котором классификаторы обучаются независимо друг от друга. Это позволяет легко распараллеливать этот метод, и далее используется простое голосование. Бэггинг хорош еще и тем, что он позволяет вычислять оценки обобщающей способности (out-of-bag), использовать их для того, чтобы оптимизировать число базовых алгоритмов, оценивать степени важности признаков, подбирать параметры модели. Но, тем не менее, Random Forest все же при решении практических задач обычно немного уступает другому композиционному методу, который называется градиентный бустинг и который мы рассмотрим в следующий раз. [ЗАСТАВКА]
