Функции неопределённости как минимальные значения потерь
Все представленные ранее функции неопределённости решающих деревьев получаются в результате расчёта средних потерь при оптимальном константном прогнозе для этих потерь.
Пусть It - индексы объектов, попавших в узел t, а ∣It∣ - количество таких объектов.
Тогда дисперсия откликов представляет собой минимально возможные среднеквадратичные потери при константном прогнозе y^∈R. Оптимальной константой, минимизирующей средний квадрат ошибки, будет выборочное среднее (докажите!):
Среднее абсолютное отклонение от медианы минимизирует модуль отклонений от оптимальной константы y^∈R, в качестве которой выступает медиана (докажите!):
Классификационная ошибка минимизирует частоту ошибок классификации, когда класс всегда предсказывается также оптимальной константой. В качестве таковой выступает самый часто встречающийся класс (докажите!):
Энтропия представляет собой наилучшее значение кросс-энропийных потерь (cross-entropy loss между фактическими вероятностями классов и их предсказанными значениями для всех объектов узла t. Оптимальными вероятностями оказываются при этом фактические частоты классов в узле p1,p2,...pC (докажите!):
Критерий Джини выступает в качестве оптимального значения функции потерь Бриера между фактическими и предсказываемыми вероятностями. Наилучшими вероятностями также выступают фактические частоты каждого класса среди объектов узла (докажите!):
Докажите, что энтропия и критерий Джини минимизируют соответствующие функции потерь. Для этого необходимо воспользоваться методом множителей Лагранжа [1], поскольку оптимизация по вектору p будет производиться при условии, что ∑c=1Cpc=1.
Функции неопределённости для пользовательской функции потерь
При минимизации нестандартной функции потерь L(y^,y) оптимальной функцией неопределённости ϕ(t) будет минимальное среднее значение значение этой функции потерь при константном прогнозе y^:
ϕopt(t)=y^min∣It∣1i∈It∑L(y^,yi)
Именно такая функция неопределённости будет оптимальна для минимизации потерь L(y^,y).
Такой подход, несмотря на его оптимальность, не реализован в большинстве библиотек машинного обучения в связи с тем, что для стандартных функций потерь оптимальный y^ вычислим аналитически и известен заранее, что позволяет рассчитать функцию неопределённости за O(∣It∣), в то время как для произвольной функции потерь необходимо производить каждый раз переборную оптимизацию y^, из-за чего сложность вычисления ϕ(t) возрастает до O(∣It∣2).
Стоит отметить, что сложность возрастает до квадратичной от числа объектов в узле только во время настройки дерева. Сложность построения прогнозов при этом не меняется, поскольку решающие правила узлов уже фиксированы.
Листовые прогнозы для пользовательской функции потерь
При использовании пользовательской функции потерь L(y^,y) прогнозы в листах также оптимально назначать как минимизаторы именно этой функции:
y^=argymin∣It∣1i∈It∑L(y,yi)
В частном случае задачи регрессии с L(y^,y)=(y^−y)2 оптимально назначать прогнозом листа выборочное среднее, а при L(y^,y)=∣y^−y∣ медиану (докажите!).
В задаче классификации оптимально назначать прогнозом самый часто встречающийся класс среди объектов листа только для функции потерь L(y^,y)=I{y^=y} (докажите!). Для другой функции потерь это правило уже перестаёт быть оптимальны м.