[ЗАСТАВКА] В прошлом уроке мы с вами узнали, что такое решающие деревья, и выяснили, что они могут восстанавливать очень сложные закономерности, из-за чего они склонны к переобучению. Решающее дерево слишком легко подгоняется под обучающую выборку и получается непригодным для построения прогнозов. Бороться с переобучением довольно сложно. Надо либо использовать критерии остановок, которые слишком простые и не всегда помогают, либо делать стрижку деревьев, которая, наоборот, слишком сложная. Зачем же мы тогда тратили на них время? Оказывается решающие деревья очень хорошо подходят для объединения в композиции, для построения одного непереобученного алгоритма на основе большого количества решающих деревьев. В этом и следующем уроке мы будем говорить, как именно объединять их в такие композиции, а пока давайте еще раз вспомним проблемы решающих деревьев. Представьте, что у нас есть вот такая выборка, и мы обучили на ней решающее дерево до конца, то есть до тех пор, пока в каждом листе не оказалось по одному объекту. Разделяющая поверхность будет очень плохой. Она очень разрезанная. Даже если есть объект, который попадает в гущу другого класса, например синяя точка внизу, разделяющая поверхность пытается уловить этот объект, выдать на нем правильный синий ответ. Из-за этого поверхность получается очень переобученная. Если мы немного изменим обучающую выборку, например выкинем пару объектов и обучим решающее дерево на том, что осталось, разделяющая поверхность будет все еще очень изрезанной и переобученной, но совершенно другой. Она очень неустойчива к изменениям в выборке. Итак, у решающих деревьев есть два недостатка. Первый — они очень сильно переобучаются, а второй — они очень неустойчивы, они очень сильно меняются даже при небольших изменениях в выборке. И на самом деле второй пункт можно обратить в их достоинство с помощью композиции, но об этом чуть позже. А пока давайте поговорим в целом о том, что такое композиция алгоритмов. Итак, композиция — это объединение n алгоритмов в один. Представьте, что мы каким-то образом нашли N большое алгоритмов b1, ..., bn. Пока не важно, откуда мы их взяли. Просто представьте, что мы их как-то обучили. Чтобы объединить их в композицию, мы усредняем их ответы, то есть суммируем ответы всех этих алгоритмов b1, ..., bn на объекте x, и делим на N большое, то есть на количество этих алгоритмов. Если мы решаем задачу классификации, то далее мы берем знак от этого среднего; если регрессии, то просто возвращаем это среднее как ответ. Алгоритм a(x), который возвращает знак среднего или просто среднее и называется композицией n алгоритмов. А алгоритмы b1, ..., bn, которые мы объединяем в композицию, называются базовыми алгоритмами. Рассмотрим простой пример. Представьте, что в нашей композиции 6 базовых алгоритмов, и есть некоторый объект x, на котором наши базовые алгоритмы выдали вот такие ответы: −1, −1, 1, −1, 1 и −1. Это задача классификации с двумя классами. Какие-то алгоритмы отнесли наш объект к классу +1, какие-то — к классу −1. Усредним ответы. Получим при этом −2/6 или −1/3. Знак этой дроби — это −1, значит ответ композиции — это −1. Мы отнесли объект к классу −1, поскольку именно за этот вариант проголосовало большинство базовых алгоритмов. Итак, для того чтобы строить композицию, нужно обучить n базовых алгоритмов. При этом понятно, что нельзя их обучать на всей обучающей выборке. Они получатся одинаковыми, и в их усреднении не будет никакого смысла. Нужно делать их немного различными. Как этого достичь? Например, с помощью рандомизации, то есть обучать их по разным подвыборкам обучающей выборки. Поскольку решающие деревья очень сильно меняются даже при небольших изменениях обучающей выборки, такая рандомизация с помощью подвыборок будет очень хорошо влиять на их различность. Один из популярных подходов по построению подвыборок — это бутстрап. В чем он заключается? Представьте, что у нас есть полная обучающая выборка, состоящая из l объектов. Мы генерируем из нее l объектов с возвращением, то есть мы берем из нее некоторый случайный объект, записываем его в новую выборку и возвращаем обратно. То есть в какой-то момент мы можем снова его вытянуть и снова поместить в обучающую выборку. При этом новая выборка будет тоже иметь размер l, но при этом какие-то объекты будут в ней повторяться, а какие-то объекты исходной обучающей выборки не встретятся ни разу. Можно показать, что количество различных объектов в бутстрапированной выборке будет равняться 0,632 * l, то есть примерно 63 % объектов исходной выборки будет содержаться в бутстрапированной. Есть и другой подход к рандомизации. Это просто генерация случайного подмножества обучающей выборки. Например, мы берем случайные 50 % объектов и на них обучаем базовый алгоритм. Этот подход чуть хуже, потому что в нем появляется гиперпараметр — размер подвыборки. В нашем примере это было 50 %. В случае же с бутстрапом никаких параметром нет. Он без какой-либо настройки выдает нам подвыборку, что гораздо удобнее. Если мы построим с помощью бутстрапа 100 базовых решающих деревьев и объединим их в композицию, то мы получим вот такую разделяющую поверхность в нашем примере, который мы разбирали в начале. Видно, что поверхность все еще довольно сложная, но при этом гораздо менее переобученная. Она уже не пытается подгоняться под большинство объектов, которые залезают в гущу другого класса. Она более или менее угадывает разделяющую поверхность между двумя классами. Да, все еще есть некоторые погрешности, но и их можно было бы устранить, если построить еще больше базовых алгоритмов. Итак, мы с вами вспомнили, что решающие деревья являются очень сильно переобученными алгоритмами и так же неустойчивы к любым изменениям в обучающей выборке. При этом усреднение ответов нескольких базовых алгоритмов, базовых решающих деревьев повышает качество композиции, дает более высокое качество и менее переобученную разделяющую поверхность, чем отдельные базовые алгоритмы. При этом строить отдельные базовые решающие деревья или базовые алгоритмы можно разными способами, например с помощью бутстрапа или генерации случайных подвыборок. В следующем видео мы продолжим разговор о композициях и разберемся, почему же усреднение улучшает качество базовых алгоритмов.