Решающие деревья

Структура модели

Решающее дерево — бинарное дерево, где каждая внутренняя вершина \(v\) содержит предикат \(\beta_v: \mathbb{X} \to \{0, 1\}\), а каждый лист содержит прогноз \(c_v \in \mathbb{Y}\).

Типичные предикаты:

\(\beta_v(x) = [x_j \geq t]\) — самый простой и часто используемый.
\(\beta_v(x) = [\langle w, x \rangle \geq t]\) — линейный предикат.
\(\beta_v(x) = [\rho(x, x_0) \geq t]\) — предикат по расстоянию.

Multi-way деревья (более 2 ветвей из одной вершины) существуют, но сложнее в обучении и чаще переобучаются.

Как обучать деревья

Если в выборке нет двух одинаковых объектов с разными ответами, существует дерево с нулевой ошибкой на обучении. Найти наименьшее такое дерево — NP-трудная задача, поэтому используют жадные алгоритмы.

Алгоритм построения (псевдокод):

SplitNode(m, Rm):
    если выполнен критерий останова:
        c_m = средний ответ / самый частый класс
        выход
    иначе:
        j, t = argmax Q(Rm, j, t)
        Rl = {(x,y) in Rm | x_j < t}
        Rr = {(x,y) in Rm | x_j >= t}
        SplitNode(l, Rl)
        SplitNode(r, Rr)

Критерии останова:

Ограничение на максимальную глубину.
Минимальное число объектов в листе.
Допустимая доля ошибок в листе.

Критерии качества предиката (impurity)

\(H(R)\) — impurity, показывает разнородность ответов в регионе \(R\). Общий подход:

\[H(R) = \min_{c \in \mathbb{R}} \frac{1}{|R|} \sum_{(x,y) \in R} L(y_i, c)\]

Примеры для регрессии:

\[H(R_m) = \frac{1}{|R_m|} \sum_{(x,y) \in R_m} (y_i - \bar{y}_m)^2\]

Примеры для классификации (доля класса \(k\): \(p_k = \frac{1}{|R_m|} \sum [y_i = k]\)):

Энтропия: \(H(R) = -\sum_k p_k \log p_k\)
Критерий Джини: \(H(R) = \sum_k p_k(1 - p_k)\)

Функционал качества разбиения:

\[Q(R_m, j, t) = H(R_m) - \frac{|R_l|}{|R_m|} H(R_l) - \frac{|R_r|}{|R_m|} H(R_r)\]

Обработка пропусков

Вариант 1 — штраф за пропуски

Штрафуем предикат по признаку \(j\) пропорционально доле объектов без пропусков:

\[Q(R, j, t) = \frac{|R \setminus V_j|}{|R|}\ Q(R \setminus V_j(R),\ j, t)\]

Объекты с пропуском отправляем и влево, и вправо с весами \(\frac{|R_l|}{|R|}\) и \(\frac{|R_r|}{|R|}\).

Вариант 2 — суррогатный предикат

Выбираем лучший предикат \(\beta(x)\), затем ищем суррогатные \(\beta'(x), \beta''(x), \dots\), дающие похожее разбиение. На инференсе используем первый доступный предикат:

\[x \xrightarrow{\beta(x)\ \text{н/д}} \beta'(x) \xrightarrow{\text{н/д}} \beta''(x) \xrightarrow{\text{н/д}} \dots\]

Категориальные признаки

Для признака \(x_j \in \{u_1, \dots, u_q\}\) ищем оптимальное разбиение \(Q = Q_1 \sqcup Q_2\) и используем предикат \(\beta(x) = [x_j \in Q_1]\). Перебор всех \(2^{|Q|}\) разбиений заменяется линейным алгоритмом: сортируем категории по доле положительных объектов, затем перебираем префиксы.

Линейный алгоритм поиска оптимального разбиения работает только для бинарной классификации и регрессии.

Связь деревьев и линейных моделей

Дерево делит пространство на регионы \(\mathbb{X} = J_1 \sqcup \dots \sqcup J_n\) и выдаёт прогноз:

\[a(x) = \sum_{j=1}^n w_j [x \in J_j]\]

Индикаторы регионов — нелинейные признаки, а \(w_j\) — веса. То есть дерево само строит нелинейные признаки, а затем применяет к ним линейную модель. На этой идее основан метод PmXTree.

← Назад к списку тем

НейроЦелитель

Темы