[БЕЗ_ЗВУКА] В этом видео мы поговорим о критериях информативности, с помощью которых можно выбирать оптимальное разбиение при построении решающего дерева. Как мы с вами договорились, решающее дерево будем строить простое, у которого в каждой вершине записано условие, которое берет значение j-го признака, сравнивает его с порогом t, и если значение признака меньше порога t, то объект идет в левое поддерево, если больше, то в правое поддерево. Допустим, у нас есть некоторая вершина с номером m, в которую попала подвыборка обучающей выборки X с индексом m, и мы хотим разбить эту вершину на два поддерева. Мы уже говорили, что будем делать это с помощью критерия ошибки, который показывает, насколько качественно данное условие, данная пара (признак j и порог t) разбивает объект, попавший в эту выборку, на две подвыборки. Этот критерий обозначается буквой Q. После того, как конкретный критерий выбран, мы разбиваем выборку Xm на две части. Xl — это те объекты, у которых значения j-го признака меньше или равно порога t, и Xr — это те объекты, у которого значения j-го признака больше порога t. Выборка Xl отправляется в левое поддерево, выборка Xr отправляется в правое поддерево. После этого можно повторить процедуру для левого и правого листа, который мы породили из данной вершины. Критерий ошибки будем записывать вот в таком сложном виде. Давайте разберемся, что означают его части. Он состоит из двух слагаемых. В первом слагаемом используется функция H, которой на вход передается выборка Xl, то есть та часть объектов, которая пойдет в левое поддерево. Функция H должна измерять качество этого подмножества, то есть насколько сильный разброс ответов имеет место при попадании выборки Xl в левое поддерево. Аналогично второе слагаемое измеряет то же самое для правого поддерева, в нем функцию H передает выборка Xr, и она должна измерить, насколько силен разброс ответов в подмножестве Xr. Обратите внимание, что значение функции H на Xl и Xr нормируется, они домножаются на коэффициенты, которые равны доли объектов, которая идет влево, и доли объектов, которая идет вправо. Зачем это нужно? Представьте, что у нас в вершине m находится 1000 объектов, и из них 990 идут в левое поддерево, и 10 — в правое поддерево. При этом 990 объектов, которые идут влево, оказываются одного класса, то есть это очень хорошее поддерево, а 10 объектов, которые идут вправо, относятся ко всем возможным классам. Распределение классов там равномерное, то есть эта подвыборка получается плохой, но при этом в ней всего 10 объектов, и нам не так страшно, что она получилась плохой, при том, что 990 попали в правильную вершину. Поэтому нам важно домножать значение качества подмножества на размер этого подмножества. Итак, функция H(X) называется критерием информативности, и она должна измерять, насколько силен разброс ответов в выборке X. По сути, эта функция зависит от того, какие ответы имеют объекты из множества X. Ее значение должно быть тем меньше, чем меньше разброс этих ответов. Давайте разберем несколько примеров критерия информативности для задач регрессии и классификации. Начнем с регрессии. Понятно, что в случае с регрессией измерить разброс довольно просто — это просто дисперсия ответов этой выборки. Чтобы ее измерить, сначала вычислим средний ответ выборки X, который обозначается буквой y с верхней чертой. Он вычисляется просто, как среднее значение. А затем вычислим дисперсию выборки, которая вычисляется как среднее значение квадрата отклонения ответа на объекте от среднего ответа по выборке. Перейдем к классификации. В случае с классификацией все немного сложнее. Нам понадобится вспомогательная величина, которая показывает для k-го класса, какова доля объектов класса k в выборке X. Будем обозначать эту величину как pk-тое. И она, собственно, вычисляется по этой формуле, смысл которой как раз таки доля объектов класса k в выборке X. На основе этих чисел pk вводятся критерии информативности для классификации, и первый из них — это критерий Джини. Он вычисляется по такой формуле. В нем стоит суммирование по всем классам, от первого до K, и для каждого класса вычисляется произведение pk на (1 − pk), где pk — это доля объектов k-го класса в вершине. Обратите внимание, что все числа в этой сумме положительные, поэтому критерий Джини всегда не отрицательный, он не меньше нуля. При этом, если в нашей выборке X все объекты относятся к какому-то одному классу, например к первому, то все слагаемые в этой сумме будут нулевыми, значит и сам критерий Джини будет равен 0. Это означает, что его оптимум достигается в том случае, если все объекты в подвыборке относятся к одному классу. У него есть много интерпретаций. И одна из них следующая: критерий Джини равен вероятности ошибки случайного классификатора, где случайный классификатор устроен так, что он выдает случайный класс от 1 до K, при этом вероятность выдать класс (какое-то k) равна pk, то есть равна пропорции этого класса в общей подвыборке X. Еще один пример критерия информативности для классификации, это энтропийный критерий. Он вычисляется по такой формуле. В нем суммируются следующие слагаемые: берется вероятность pk и домножается на логарифм этой вероятности, и все это берется со знаком минус. При этом мы считаем, что если вероятность равна 0, то ноль умножить на логарифм нуля — это то же ноль. Причем это можно доказать по непрерывности, если взять просто предел функции X In X. Для этого критерия выполнено то же самое свойство: если в выборке X находятся объекты ровно одного класса, например первого, то значение энтропийного критерия будет равно 0. И какое бы не было распределение на классах, значение энтропийного критерия не отрицательное. У него так же есть очень интересный физический смысл. По сути, энтропийный критерий — это мера отличия распределения классов от вырожденного. Если распределение вырожденное, то энтропия равна 0, в этом распределении нет ничего неожиданного, мы всегда знаем, что мы будем получать из него. Если же это распределение равномерное, то есть вероятность получить каждый класс в этой выборке одинаковая, то энтропия будет максимальна. У этого распределения максимальный уровень неожиданности. Мы не можем предсказать, что мы получим. Итак, мы выяснили, что критерий ошибки должен минимизировать разброс ответов в обоих поддеревьях после разбиения по какому-то условию. И выражается он через критерий информативности, который измеряет разброс ответов в одном из поддеревьев. В регрессии это просто среднеквадратичная ошибка или дисперсия. В классификации это может быть критерий Джини или энтропийный критерий. В следующем видео мы поговорим о том, как выбирать критерий останова и что такое стрижка деревьев.