В этом видео мы поговорим о том, как строить решающие деревья, как обучать их на конкретную выборку. Как мы выяснили в прошлый раз, решающие деревья очень легко переобучаются. Легко построить дерево, у которого каждый лист будет соответствовать одному объекту обучающей выборки. Это дерево будет строить вот такую разделяющую поверхность, очень-очень сложную, которая будет давать идеальное качество, но при этом явно будет переобученной. Поскольку дерево может достичь нулевой ошибки на обучающей выборке, нам не подходит любое дерево. В принципе, скорее всего, каждую задачу можно решить деревом, которое будет иметь нулевую ошибку и при этом не быть переобученным, и, скорее всего, это будет минимальное дерево из всех, у которых нулевая ошибка. Минимальным оно может быть, например, в смысле количества листьев, то есть можно поставить задачу построить такое решающее дерево, которое не ошибается на данной выборке и при этом имеет меньше всего листьев. К сожалению, эта задача NP-полная, то есть ее невозможно решить за разумное время, поэтому в машинном обучении пользуются гораздо более простым подходом: строят дерево жадно, последовательно, от корня к листьям, а именно мы начинаем с пустого дерева, дальше выбираем каким-то образом корень, который разбивает нашу выборку на две, дальше разбиваем потомков этого корня и так далее. Ветвим дерево до тех пор, пока не решим, что этого достаточно. Давайте выясним, как именно можно разбивать конкретную вершину на две, на два потомка. Итак, как мы с вами договаривались, мы будем использовать в качестве условия для разбиения очень простую штуку: будем брать один из признаков, j-тый, и сравнивать его с порогом t. Если значение j-того признака меньше порога, отправляем объект в одну сторону, например, влево, если больше порога, то вправо. Допустим, мы сейчас находимся в вершине m, и в нее попало некоторое количество объектов обучающей выборки, например, xm, будем так обозначать это подмножество объектов. Мы будем использовать некоторый критерий ошибки Q, который зависит от того, какие объекты попали в данную вершину, то есть xm, и от параметров разбиения j и t, то есть на основе какого признака мы разбиваем и с каким порогом мы сравниваем значение этого признака. Будем выбирать параметры j и t-разбиения так, чтобы они минимизировали данный критерий ошибки Q. Подбирать параметр j можно перебором, поскольку признаков у нас конечное число, а из всех возможных значений параметра t, порога, можно рассматривать только те, при которых получаются различные разбиения. Можно показать, что этих значений t столько, сколько различных значений признака j на обучающей выборке. Например, можно отсортировать все значения j-того признака и брать пороги между этими значениями. После того как мы выбрали конкретное разбиение, выбрали оптимальные значения параметров j и t, мы разбиваем нашу вершину на две: левую и правую. При этом часть объектов, а именно те, на которых j-тый признак меньше или равен порогу t, отправляются влево, и будем обозначать это подмножество как xl, а часть объектов из xm, те, у которых значение j-того признака больше порога t, отправляются вправо, и это подмножество обозначается как xr. Эту процедуру можно повторить дальше для двух дочерних вершин, тем самым углубляя наше дерево. В какой-то момент нам все же придется остановиться. Как понять, что данную вершину уже разбивать не нужно, что ее можно объявить листом и выдавать прогноз для того объекта, который в нее попал? Критериев останова очень много. Например, можно смотреть, сколько объектов находится в данной вершине. Если там всего один объект обучающей выборки, понятно, что дальше разбивать не имеет смысла; если же больше, можно разбивать дальше. Или, например, можно смотреть, какие объекты попали в эту вершину: если они все относятся к одному классу в задаче классификации, можно прекратить разбиение; если же есть несколько классов, можно разбивать дальше. Или, например, можно следить за глубиной дерева и останавливать разбиение, если глубина превышает некоторый порог, например, 10. Мы будем подробнее говорить о критериях останова в следующих видео этого урока, а сейчас давайте обсудим, как выбирать ответ в листе, если мы решили вершину объявить листом. Итак, в данный лист попала некоторая подвыборка xm, некоторое подмножество объектов обучающей выборки, и нужно выбрать какой-то один прогноз, который будет оптимален для данной подвыборки. В случае с регрессией мы знаем, что если функционал – среднеквадратичная ошибка, то оптимально выдавать средний ответ по этой подвыборке, то есть мы суммируем ответы по всем объектам i, которые попали в данную вершину, и делим на количество объектов в этой вершине. Это и будет оптимальным прогнозом в случае с задачей регрессии среднеквадратичного функционала. Если мы решаем задачу классификации, то наиболее логичным выбором будет возвращать тот класс, который наиболее популярен в выборке xm. То есть мы для каждого класса y считаем, сколько объектов этого класса попало в данную вершину, и возвращаем тот, который максимален, которого больше всего. Если же мы хотим возвращать вероятности классов в данной вершине, это тоже очень легко сделать. Вероятность k-того класса оценивается как доля объектов k-того класса в данной вершине среди всех объектов, впавших в эту вершину, то есть среди всех объектов из xm. У нас остались открытыми два вопроса: как именно разбивать, как задавать критерии разбиения, как оценивать ошибку разбиения в данной вершине и как выбирать критерий останова? О них мы будем говорить в следующих видео этого урока. Мы обсудили, что решающие деревья удобно строить жадно – от корня к листьям, при этом конкретное разбиение в каждой вершине выбирается, исходя из некого критерия ошибки, о котором будем говорить позже. Также нужно задать некоторый критерий останова, который определяет, следует ли данную вершину разбивать дальше или же уже можно сделать ее листом. Также мы обсудили, как именно выбирать прогнозы в листьях, в задачах классификации и регрессии. В следующем видео мы продолжим разговор и поговорим о том, как задавать критерии ошибки.
