[ЗАСТАВКА] Мы начинаем урок, посвященный решающим деревьям. Это семейство алгоритмов, которое очень сильно отличается от линейных моделей и в то же время занимает крайне важную роль в машинном обучении. Итак, пока что мы с вами проходили линейные модели. Они легко обучаются. В случае со среднеквадратичной ошибкой для вектора весов даже есть аналитическое решение. Также очень легко применять к линейным моделям градиентный спуск, который быстро сходится, если с признаками все хорошо, и дает нам точное решение. При этом линейные модели могут восстанавливать только очень простые зависимости из-за того, что у них очень мало степеней свободы, очень мало параметров. Их столько, сколько признаков. В то же время линейные модели можно использовать для восстановления нелинейных зависимостей за счет перехода в спрямляющие пространства, что может оказаться довольно сложной операцией. В то же время линейные модели не очень хорошо отражают то, как люди принимают решения. На самом деле, когда человек хочет понять ту или иную вещь, он будет задавать последовательность из простых вопросов, которые в итоге приведут его к какому-то ответу. Давайте разберем простой пример, который слабо относится к жизни, и поэтому не стоит повторять его дома. Итак, медицинская диагностика. Представьте, что пациент приходит к врачу и спрашивает, что с ним случилось. В это время врач очень простой и он может диагностировать только два заболевания: ангину и грипп. Сначала врач спрашивает, какая температура у пациента. Если она меньше 37 градусов, он говорит, что пациент здоров, если больше 37 градусов, он переходит к следующему вопросу, а именно спрашивает, болит ли у пациента горло. Если оно болит, то врач ставит диагноз «ангина», если не болит, врач говорит, что это грипп. В итоге, задав максимум два вопроса, врач приходит к тому или иному ответу. Другой вопрос о том, насколько качественны эти ответы, но в целом они отражают структуру мышления. Или другой пример для известной задачи определения выживет или нет тот или иной пассажир Титаника. Задача очень неплохо решается вот таким решающим деревом. Давайте разберем его. В первую очередь мы смотрим, какой пол у данного пассажира. Если это женщина, то мы сразу говорим, что она выживет, и этот ответ будет правильным в 73 % случаев. Если это мужчина, то мы смотрим, сколько ему лет. Если девять или меньше, то мы перейдем в следующую ветку, а если больше девяти, то сразу говорим, что пассажир погиб. Если меньше девяти лет, то мы смотрим, сколько родственников у этого пассажира было на борту. Если три или больше, то говорим, что он погиб. Если меньше, то говорим, что он выжил. Итак, мы рассмотрели два примера решающих деревьев. В общем случае это некоторое бинарное дерево, у которого в каждой внутренней вершине записано простое условие. В зависимости от того, верное оно или нет, мы будем идти либо вправо, либо влево от этой вершины. В каждом листе решающего дерева записан некоторый прогноз. Таким образом, мы берем некий объект, стартуем из корня и движемся по дереву, проверяя условие в текущей вершине. В зависимости от его выполнения идем либо влево, либо вправо. В конце концов мы попадаем в лист, в котором записан прогноз, который и выдается в качестве ответа модели. Отмечу, что можно строить и более сложные небинарные деревья, но, как правило, используются именно бинарные. Этого достаточно, чтобы решать большинство задач. Условия во внутренних вершинах также используются крайне простые. Наиболее частый вариант — вот такой. Мы проверяем, находится ли значение j-того признака левее, чем некоторый порог. То есть мы берем у объекта j-тый признак, сравниваем с порогом t, и если оно меньше порога, мы идем влево, если больше порога, мы идем вправо. Это опять же очень простое условие, которое зависит всего от одного признака, но его достаточно, чтобы решать многие сложные задачи. Прогноз в листе будет вещественным, если это регрессия, и он будет пытаться как можно лучше приблизить истинный ответ. Если это классификация, то есть два варианта. Дерево может выдавать либо номер класса (тогда в каждом листе будет записан просто тот или иной класс), либо распределение вероятности на классах. В этом случае в каждом листе будет записан некоторый вектор длины k, если k — это число классов, который будет говорить, насколько вероятно, что объект относится к тому или иному классу. Давайте посмотрим, как выглядят зависимости, которые восстанавливают решающие деревья. Рассмотрим задачу классификации с двумя признаками. В ней три класса, и видно, что решающее дерево может очень неплохо отделить каждый класс от всех остальных. Видно, что разделяющая поверхность каждого класса кусочно-постоянная, и при этом каждая сторона разделяющей поверхности параллельна одной из осей координат из-за того, как именно мы выбрали условия. Каждое условие сравнивает значение ровно одного признака, ровно одной координаты с порогом. В то же время решающее дерево может легко переобучиться. Его можно сделать настолько глубоким, что каждый лист решающего дерева будет соответствовать ровно одному объекту обучающей выборки. В этом случае, если мы запишем в каждом листе ответ соответствующего объекта, мы получим нулевую ошибку на обучающей выборке, но в то же время дерево будет явно переобученным. Вот пример такого дерева. Оно идеально отделило синий от красного класса. Но при этом разделяющая поверхность получилась безумно сложной. Видно, что этот алгоритм переобучился, от него не будет никакого толка на тестовой выборке. Посмотрим теперь на задачу регрессии. Пусть у нас есть всего один признак x, и нужно по его значению восстановить значение целевой переменной y. Если построить не очень глубокое дерево, то оно восстановит зависимость примерно так. Опять же, видно, что восстановленная зависимость будет кусочно-постоянной, но в целом качество довольно неплохое. Если же мы увеличим глубину дерева, то получим вот такую функцию. Видно, что дерево подогналось под выбросы, и его качество будет уже не таким хорошим. Дерево переобучилось из-за того, что его глубина слишком большая. Итак, мы с вами узнали, что такое решающее дерево, и поговорили о том, что оно последовательно проверяет простые условия и приходит в тот или иной лист, где записан прогноз. Деревья интерпретируемы, но при этом позволяют восстанавливать очень сложные зависимости. Из-за этого они довольно легко переобучаются под обучающую выборку. В следующем видео мы продолжим разговор о решающих деревьях и обсудим, как именно можно их обучать.