Перейти к основному содержимому

Учёт пользовательской функции потерь

Функции неопределённости как минимальные значения потерь​

Все представленные ранее функции неопределённости решающих деревьев получаются в результате расчёта средних потерь при оптимальном константном прогнозе для этих потерь.

Пусть ItI_t - индексы объектов, попавших в узел tt, а ∣It∣|I_t| - количество таких объектов.

Тогда дисперсия откликов представляет собой минимально возможные среднеквадратичные потери при константном прогнозе y^∈R\hat{y}\in\mathbb{R}. Оптимальной константой, минимизирующей средний квадрат ошибки, будет выборочное среднее (докажите!):

ϕ(t)=min⁡y^1∣It∣∑i∈It(yi−y^)2=1∣It∣∑i∈It(yi−meani∈It(yi))2\begin{aligned} \phi(t)&=\min_{\widehat{y}}\frac{1}{\left|I_{t}\right|}\sum_{i\in I_{t}}\left(y_{i}-\widehat{y}\right)^{2}\\ &=\frac{1}{\left|I_{t}\right|}\sum_{i\in I_{t}}\left(y_{i}-\text{mean}_{i\in I_{t}}(y_{i})\right)^{2} \end{aligned}

Среднее абсолютное отклонение от медианы минимизирует модуль отклонений от оптимальной константы y^∈R\hat{y}\in\mathbb{R}, в качестве которой выступает медиана (докажите!):

ϕ(t)=min⁡y^1∣It∣∑i∈It∣yi−y^∣=1∣It∣∑i∈It∣yi−mediani∈It(yi)∣\begin{aligned} \phi(t)&=\min_{\widehat{y}}\frac{1}{\left|I_{t}\right|}\sum_{i\in I_{t}}\vert y_{i}-\widehat{y}\vert\\ &=\frac{1}{\left|I_{t}\right|}\sum_{i\in I_{t}}\vert y_{i}-\text{median}_{i\in I_{t}}(y_{i})\vert \end{aligned}

Классификационная ошибка минимизирует частоту ошибок классификации, когда класс всегда предсказывается также оптимальной константой. В качестве таковой выступает самый часто встречающийся класс (докажите!):

ϕ(t)=min⁡y^1∣It∣∑i∈ItI[yi≠y^]=1∣It∣∑i∈ItI[yi≠yсамый частый]=1−p^max\begin{aligned} \phi(t)&=\min_{\widehat{y}}\frac{1}{\left|I_{t}\right|}\sum_{i\in I_{t}}\mathbb{I}[y_{i}\ne\widehat{y}]\\ &=\frac{1}{\left|I_{t}\right|}\sum_{i\in I_{t}}\mathbb{I}[y_{i}\ne y_{\text{самый частый}}]\\ &=1-\hat{p}_{max} \end{aligned}

Энтропия представляет собой наилучшее значение кросс-энропийных потерь (cross-entropy loss между фактическими вероятностями классов и их предсказанными значениями для всех объектов узла tt. Оптимальными вероятностями оказываются при этом фактические частоты классов в узле p^1,p^2,...p^C\widehat{p}_1,\widehat{p}_2,...\widehat{p}_C (докажите!):

ϕ(t)=min⁡p:∑cpc=1−1∣It∣(∑i∈It∑c=1Cln⁡pcI[yi=c])=min⁡p:∑cpc=1−1∣It∣(∑i∈It∑c=1CI[yi=c]ln⁡pc)=−∑i=1Cp^iln⁡p^i\begin{aligned} \phi(t)&=\min_{p:\sum_{c}p_{c}=1}-\frac{1}{\left|I_{t}\right|}\left(\sum_{i\in I_{t}}\sum_{c=1}^{C}\ln p_{c}^{\mathbb{I}[y_{i}=c]}\right)\\ &=\min_{p:\sum_{c}p_{c}=1}-\frac{1}{\left|I_{t}\right|}\left(\sum_{i\in I_{t}}\sum_{c=1}^{C}\mathbb{I}[y_{i}=c]\ln p_{c}\right)\\ &=-\sum_{i=1}^{C}\widehat{p}_{i}\ln\widehat{p}_{i} \end{aligned}

Критерий Джини выступает в качестве оптимального значения функции потерь Бриера между фактическими и предсказываемыми вероятностями. Наилучшими вероятностями также выступают фактические частоты каждого класса среди объектов узла (докажите!):

ϕ(t)=min⁡p:∑cpc=11∣It∣∑i∈It∥p−pitrue∥2=min⁡p:∑cpc=11∣It∣∑i∈It∑c=1C(pc−I[yi=c])2=∑i=1Cp^i(1−p^i)=1−∑i=1Cp^i2\begin{aligned} \phi(t)&=\min_{p:\sum_{c}p_{c}=1}\frac{1}{\left|I_{t}\right|}\sum_{i\in I_{t}}\left\lVert \mathbf{p}-\mathbf{p}_{i}^{true}\right\rVert ^{2}\\ &=\min_{p:\sum_{c}p_{c}=1}\frac{1}{\left|I_{t}\right|}\sum_{i\in I_{t}}\sum_{c=1}^{C}\left(p_{c}-\mathbb{I}[y_{i}=c]\right)^{2}\\ &=\sum_{i=1}^{C}\widehat{p}_{i}(1-\widehat{p}_{i})=1-\sum_{i=1}^{C}\widehat{p}_{i}^{2}& \end{aligned}
Задача

Докажите, что энтропия и критерий Джини минимизируют соответствующие функции потерь. Для этого необходимо воспользоваться методом множителей Лагранжа [1], поскольку оптимизация по вектору p\mathbf{p} будет производиться при условии, что ∑c=1Cpc=1\sum_{c=1}^C p_c=1.

Функции неопределённости для пользовательской функции потерь​

При минимизации нестандартной функции потерь L(y^,y)\mathcal{L}(\hat{y},y) оптимальной функцией неопределённости ϕ(t)\phi(t) будет минимальное среднее значение значение этой функции потерь при константном прогнозе y^\hat{y}:

ϕopt(t)=min⁡y^1∣It∣∑i∈ItL(y^,yi)\phi_{\text{opt}}(t) = \min_{\hat{y}}\frac{1}{|I_t|}\sum_{i\in I_t}\mathcal{L}(\hat{y},y_i)

Именно такая функция неопределённости будет оптимальна для минимизации потерь L(y^,y)\mathcal{L}(\hat{y},y).

Такой подход, несмотря на его оптимальность, не реализован в большинстве библиотек машинного обучения в связи с тем, что для стандартных функций потерь оптимальный y^\hat{y} вычислим аналитически и известен заранее, что позволяет рассчитать функцию неопределённости за O(∣It∣)O(|I_t|), в то время как для произвольной функции потерь необходимо производить каждый раз переборную оптимизацию y^\hat{y}, из-за чего сложность вычисления ϕ(t)\phi(t) возрастает до O(∣It∣2)O(|I_t|^2).

Стоит отметить, что сложность возрастает до квадратичной от числа объектов в узле только во время настройки дерева. Сложность построения прогнозов при этом не меняется, поскольку решающие правила узлов уже фиксированы.

Листовые прогнозы для пользовательской функции потерь​

При использовании пользовательской функции потерь L(y^,y)\mathcal{L}(\hat{y},y) прогнозы в листах также оптимально назначать как минимизаторы именно этой функции:

y^=arg⁡min⁡y1∣It∣∑i∈ItL(y,yi)\hat{y} = \arg\min_{y}\frac{1}{|I_t|}\sum_{i\in I_t}\mathcal{L}(y,y_i)

В частном случае задачи регрессии с L(y^,y)=(y^−y)2\mathcal{L}(\hat{y},y)=(\hat{y}-y)^2 оптимально назначать прогнозом листа выборочное среднее, а при L(y^,y)=∣y^−y∣\mathcal{L}(\hat{y},y)=|\hat{y}-y| медиану (докажите!).

В задаче классификации оптимально назначать прогнозом самый часто встречающийся класс среди объектов листа только для функции потерь L(y^,y)=I{y^≠y}\mathcal{L}(\hat{y},y)=\mathbb{I}\{\hat{y}\ne y\} (докажите!). Для другой функции потерь это правило уже перестаёт быть оптимальным.

Литература​

  1. Wikipedia: метод множителей Лагранжа.