← На сайт курсаВсе главы

Неделя 03 · От локальных решений к ансамблям

English Русский

Рисунки, изображения, анимации и их элементы управления сохранены с исходными английскими надписями. Переведены текст главы, таблицы и внешние подписи; формулы и код сохранены.

Главный вопрос. Почему объединение неустойчивых деревьев может дать полезную модель и какие данные обоснуют её выбор вместо другого классификатора?

Содержание. Сохраняем две части недели: основы деревьев из лекции и ансамбли с выбором модели из практикума. Самостоятельная тема SVM и ядер недели 02 применяется в общем сравнении, а не переносится в неделю 03.

Результаты обучения и необходимые знания

• проводить наблюдение по дереву и вычислять предсказание листа;
• сравнивать взвешенные критерии разбиения классификации и регрессии;
• объяснять жадный рост, обрезку, управление сложностью и неустойчивость;
• различать бутстрэп/бэггинг, OOB-оценку, лес и аддитивный бустинг;
• вычислять шаг бустинга по остаткам/антиградиенту с уменьшением шага;
• сравнивать современные инструменты, включая обработку пропусков и категорий;
• строить CV и поиск гиперпараметров без утечек и переобучения на leaderboard.

Нужны роли данных и квадратичная ошибка недели 01; скоры, вероятности, метрики и основы SVM недели 02. Нужные для усреднения ожидания и ковариации вводятся здесь. Энтропия пока служит критерием разбиения; теория информации относится к неделе 07.

Сопутствующие материалы: лекция о деревьях, практикум об ансамблях, Hidden Pairs, программа. Лабораторный baseline не является отдельным учебным ноутбуком.

Соглашения об обозначениях

Символ	Значение и соглашение
\(x_i\in\mathbb R^{d\times1}\), \(y_i\)	Входной столбец и наблюдаемая цель; бинарные метки 0/1
\(S_R\), \(K\)	Индексы обучающих строк в области \(R\); число классов с номерами \(0,\ldots,K-1\)
\(R\), \(n_R\), \(p_{R,c}\)	Область узла, число обучающих наблюдений, доля класса
\((j,s)\); \(R_L,R_R\)	Признак/порог разбиения; левая и правая дочерние области
\(I(R)\)	Заданная неоднородность; дочерние узлы взвешиваются \(n_{R_L}/n_R\) и \(n_{R_R}/n_R\)
\(q_{R,c}\), \(\widehat c_R\)	Доля класса в листе как оценка вероятности и отдельное решение большинства
\(a_R\), \(\bar y_R\)	Константа регрессионного листа и среднее целей при квадратичной потере
\(N\), \(\mathcal L(T)\)	Общее число обучающих строк и множество листовых областей дерева \(T\)
\(\mathcal R_G(T)\), \(\alpha\)	Взвешенная по наблюдениям Gini всего дерева и штраф листа; отличается от \(L_i\)
\(T(x)\); \(T_m(x)\), \(M\)	Одно дерево; базовое дерево \(m\) и число деревьев
\(\mathcal D\), \(\omega\), \(f_*(x)\), \(\mu(x)\)	Случайная обучающая выборка, случайность обучения, условное среднее популяции и среднее регрессионное предсказание по fit
\(\overline T_M(x)\), \(\sigma_T^2\), \(\rho\)	Усреднённый выход, дисперсия отдельного предсказания и общая парная корреляция при заданных предположениях
\(\mathcal O_i\), \(\mathcal C\)	Деревья без строки \(i\); строки с хотя бы одним OOB-предсказанием
\(F_m(x)\), \(\eta\)	Аддитивный предиктор после \(m\) шагов и shrinkage/размер шага
\(r_{mi}\), \(q_m(x)\), \(\pi\)	Псевдоостаток шага \(m\), бинарная вероятность после шага и обучающая доля единиц
\(L_i\), \(\bar L\)	Потеря примера и явно усреднённая цель

Входы — столбцы, наблюдения — строки \(X\), как в неделях 01–02. Используем полные численные координаты, переход влево при \(x_j\leq s\) и невзвешенные наблюдения. Разбиение лекции \(\Theta=(j,t_m)\) обозначаем \((j,s)\), неоднородность \(H\) — \(I\), оставляя \(I_H\) для энтропии. Индекс класса \(c\) не путаем с индексом наблюдения \(i\). Логарифмы натуральные.

Статистическое смещение (bias) не равно свободному члену \(b\). Регрессионный бустинг предсказывает действительное значение, бинарный обновляет скор/логит, не неконтролируемую сумму вероятностей. Лес и бустинг используют разные обучение и объединение, хотя оба содержат деревья.

Последовательность вопросов разбивает пространство входов

От цены квартиры к локальному предсказанию

Пусть цену квартиры предсказывают по площади, комнатам и этажу. Линейная модель объединяет измерения в скор; дерево задаёт вопросы вроде «площадь не больше 60 м²?» и направляет квартиру к следующему вопросу или предсказанию. Эта мотивация взята из лекции; её пороги и цены иллюстративны, не рыночные оценки или результаты fit.

Решающее дерево (decision tree) состоит из корня, внутренних узлов решений и конечных узлов — листьев. Каждое численное правило здесь сравнивает одну координату с порогом. Лист хранит постоянное предсказание. Полученная модель кусочно-постоянна: предсказание может меняться при пересечении границы, оставаясь постоянным внутри области каждого листа. В небольшом дереве легко проследить путь отдельного предсказания, но такой разбор не доказывает ни правильности предсказания, ни причинного характера правила.

Для области узла \(R\) и разбиения \((j,s)\) определим:

\[ \begin{aligned} R_L&=\{x\in R:x_j\leq s\},\\ R_R&=\{x\in R:x_j>s\}. \end{aligned} \]

Влево идём при истинном неравенстве, включая равенство. Разбивается только текущая родительская область: горизонтальная линия потомка заканчивается у вертикальной границы родителя, не рассекая всю плоскость. В двух измерениях осевые разбиения дают прямоугольные листья, возможно неограниченные вне окна рисунка. Другие варианты используют иные правила; здесь численные бинарные разбиения CART — classification and regression trees, деревьев классификации и регрессии.

Зафиксируем маленький пример классификации

Возьмём синтетическую обучающую выборку с безразмерными координатами. ID означает одно наблюдение; веса строк равны. Валидации, теста и оценки качества нет. Область нулевого класса намеренно мала: постоянная единица уже верна для 14 из 16 строк, но пропускает оба нулевых наблюдения.

ID	\(x_1\)	\(x_2\)	\(y\)
A	1	1	0
B	1	2	0
C	1	3	1
D	1	4	1
E	2	1	1
F	2	2	1
G	2	3	1
H	2	4	1
I	3	1	1
J	3	2	1
K	3	3	1
L	3	4	1
M	4	1	1
N	4	2	1
O	4	3	1
P	4	4	1

CSV содержит те же строки. Регрессия цен и бинарная задача — разные примеры: цена не является меткой класса.

Рассмотрим фиксированное дерево на Рисунок 1. В корне проверяется \(x_1\leq1.5\). Правый потомок уже является листом с наблюдениями E–P. Левый содержит A–D и проверяет \(x_2\leq2.5\), отделяя A–B от C–D. В следующем разделе проверим, почему именно эти правила уменьшают заданный обучающий критерий; сначала прочитайте рисунок как процедуру предсказания.

Рисунок 1: Одно дерево показано областями и правилами. Счётчики упорядочены (класс ноль, класс один), \(n\) — число обучающих строк. Фиолетовый путь направляет неразмеченный запрос \(U=(1.5,3.25)^\top\) в \(R_{LR}\). Фон — класс листа, не независимо проверенная уверенность. Оси, ID и имена листьев согласованы; на телефоне панели располагаются вертикально.

Для U первый ответ — да, включая равенство 1.5, второй — нет, поскольку \(3.25>2.5\). Путь \(R\to R_L\to R_{LR}\) приходит к двум единичным меткам. Запрос не меняет пороги и обучающие количества. Метки U нет, поэтому предсказанная единица не является измеренным правильным ответом.

Что хранит классификационный лист

В непустом листе вероятность оценивается обучающей долей \(q_{R,c}=p_{R,c}\). Один класс выбирают большинством, \(\widehat c_R=\arg\max_c p_{R,c}\); равенство разрешается меньшим индексом. Счётчики (2,0), (0,2), (0,12) дают доли единицы 0, 1, 1. Чистота обучения не устанавливает калибровку или достоверность новых ответов; вспомните контрпример уверенности недели 02.

До второго правила \(R_L\) содержит (2,2). Будь он листом, имел бы \(q_{R_L,1}=0.5\) и класс ноль по большинству с нашим равенством. Включающее равенство правило недели 02 \(q\geq0.5\) выбрало бы единицу. Различаются правила решений, не доли классов. Указывайте, какое правило породило предсказания.

СоветПодумайте: какая область владеет запросом?

Куда попадёт \((1.5,2.5)^\top\)? Что изменится для \((1.50001,2.5)^\top\)? Используйте неравенства, не визуальное положение относительно толстой линии.

Выбор разбиения по объявленному критерию

Перед выбором подсчитайте смесь классов

Пусть \(S_R=\{i:x_i\in R\}\) индексирует обучающие наблюдения узла. Для \(K\) классов с номерами \(0,\ldots,K-1\):

\[ \begin{aligned} n_R&=|S_R|,\\ p_{R,c}&=\frac{1}{n_R}\sum_{i\in S_R}\mathbf1[y_i=c]. \end{aligned} \]

Индикатор \(\mathbf1[\cdot]\) равен единице при истинном условии, иначе нулю. Чистый узел имеет одну долю класса, равную единице. В нашем корне \(p_{R,0}=2/16\) и \(p_{R,1}=14/16\). Используем неоднородность Джини (Gini impurity):

\[ \begin{aligned} I_G(R)&=\sum_{c=0}^{K-1}p_{R,c}(1-p_{R,c})\\ &=1-\sum_{c=0}^{K-1}p_{R,c}^2. \end{aligned} \]

Одна интерпретация — выбрать метку из эмпирических частот классов узла и независимо выбрать случайную догадку из тех же частот. Вероятность их несовпадения равна \(I_G(R)\). Это интерпретация смеси классов, а не частота ошибок предсказателя, выбирающего большинство. В бинарном случае обозначение \(p=p_{R,1}\) даёт \(I_G=2p(1-p)\): ноль для чистого узла и \(1/2\) для равномерной смеси. В нашем корне \(I_G(R)=7/32=0.21875\).

Другой локальный критерий смеси — энтропия:

\[ I_H(R)=-\sum_{c=0}^{K-1}p_{R,c}\log p_{R,c}. \]

Натуральные логарифмы дают единицы нат. Нулевой член определим как \(\lim_{p\downarrow0}p\log p=0\). Энтропия чистого узла нулевая, равной бинарной смеси — \(\log2\). Другая фиксированная база логарифма одинаково положительно масштабирует оценки и сохраняет порядок. Gini и энтропия различны и не обязаны всегда выбирать одинаково. Более широкая теория информации остаётся неделе 07.

Для сравнения: лист большинства верно размечает долю \(\max_c p_{R,c}\), поэтому обучающая доля ошибок классификации равна:

\[ I_E(R)=1-\max_c p_{R,c}. \]

В корне это \(1/8\), а не Gini \(7/32\). Максимум следует из подсчёта верных решений большинства; этим проверяют сводку критериев лекции. Это не \(1-\min_c p_{R,c}\).

Взвешивайте дочерние узлы числом наблюдений

Для правила \((j,s)\) определим взвешенную дочернюю неоднородность и её уменьшение:

\[ \begin{aligned} Q_I(R;j,s)&=\frac{n_{R_L}}{n_R}I(R_L)\\ &\quad+\frac{n_{R_R}}{n_R}I(R_R),\\ \Delta I&=I(R)-Q_I(R;j,s). \end{aligned} \]

У всех вариантов один родительский критерий, поэтому минимум \(Q_I\) эквивалентен максимуму \(\Delta I\). Веса дают единицу: усредняются наблюдения, а не два узла разного размера поровну. Эти веса не означают перевзвешивание классов.

При \(x_1\leq1.5\) слева (2,2) и неоднородность \(1/2\), справа (0,12) и нулевая. Следовательно:

\[ \begin{aligned} Q_G&=\frac4{16}\frac12+\frac{12}{16}0=\frac18,\\ \Delta I_G&=\frac7{32}-\frac18=\frac3{32}. \end{aligned} \]

Теперь рассмотрим \(x_1\leq2.5\). Левый потомок содержит восемь наблюдений с численностями классов (2,6), поэтому неоднородность Gini равна \(3/8\); правый потомок чистый. Взвешенный критерий равен \((8/16)(3/8)=3/16\), что хуже \(1/8\). Невзвешенное среднее дало бы \(1/4\) для первого правила и \(3/16\) для второго, поменяв предпочтение на противоположное. Ошибка возникает, если считать, что потомок с четырьмя строками представляет половину обучающих наблюдений.

Перебирайте варианты, не угадывайте красивую линию

Для полных численных признаков берут середины промежутков между соседними различными значениями активного узла. Все пороги одного промежутка дают одинаковое обучающее разбиение. Равные значения остаются вместе, пустые дети исключаются. У каждого признака здесь 1, 2, 3, 4, значит пороги 1.5, 2.5, 3.5.

Правило	L / R	\(Q_G\)	\(Q_H\)
\(x_1\leq1.5\)	4 / 12	0.12500	0.17329
\(x_1\leq2.5\)	8 / 8	0.18750	0.28117
\(x_1\leq3.5\)	12 / 4	0.20833	0.33792
\(x_2\leq1.5\)	4 / 12	0.20833	0.35571
\(x_2\leq2.5\)	8 / 8	0.18750	0.28117
\(x_2\leq3.5\)	12 / 4	0.20833	0.33792

L / R — количества \(n_{R_L}\) и \(n_{R_R}\), разделённые чертой; сумма 16. \(Q_G\) использует Gini, \(Q_H\) — энтропию в натах. Оба выбирают \(x_1\leq1.5\) именно для этих данных. До округления сравнивают точные Gini; равенство разрешают меньшим индексом признака, затем меньшим порогом. Это объявленные правила примера, не предполагаемые defaults библиотеки.

Внутри \(R_L\) первая координата всегда единица, варианты даёт только \(x_2\). Порог 2.5 разделяет A–B и C–D на чистые узлы, снижая Gini с \(1/2\) до нуля. Критерий ошибок большинства не улучшился бы в корне: постоянная единица ошибается дважды, как и равносмешанный левый лист первого разбиения. Неизменное число ошибок может скрывать полезное изменение смеси. Полное дерево совпадает со всеми 16 обучающими метками; это соответствие обучению, не обобщение.

Таблица расчётов сохраняет шесть корневых и три левых варианта, ID, счётчики, оба критерия, дерево и путь запроса. Глава справочника обсуждает разбиения подробнее. Раздел роста продолжает тот же пример остановкой и обрезкой.

Регрессионный лист минимизирует квадрат ошибки средним

Для регрессии вернёмся к ценам, не переосмысляя бинарные метки. Непустой лист с целями \(y_i\) и константой \(a\) минимизирует:

\[ \begin{aligned} \mathrm{SSE}_R(a)&=\sum_{i\in S_R}(y_i-a)^2,\\ \frac{d\mathrm{SSE}_R}{da}&=2\sum_{i\in S_R}(a-y_i)=0,\\ a_R&=\bar y_R=\frac1{n_R}\sum_{i\in S_R}y_i. \end{aligned} \]

Вторая производная \(2n_R>0\), поэтому среднее — единственный минимум. Сумма и среднее квадратов дают ту же константу. Неоднородность регрессии определим как средний квадрат отклонений узла:

\[ I_{\mathrm{MSE}}(R)=\frac1{n_R}\sum_{i\in S_R}(y_i-\bar y_R)^2. \]

Знаменатель эмпирической дисперсии — \(n_R\), не \(n_R-1\), используемый для несмещённой оценки дисперсии популяции. Взвешенная дочерняя MSE равна общей сумме квадратов обоих детей, делённой на размер родителя. Невзвешенное сравнение снова меняет цель.

Четыре синтетические цены 4, 6, 8, 10 миллионов условных единиц дают среднее 7, сумму квадратов 20, MSE 5. Группы (4,6) и (8,10) имеют средние 5 и 9, каждая сумму квадратов 2 и MSE 1. Взвешенная MSE равна 1, уменьшение — 4. Единицы квадратичные ценовые. Реальных цен, обученного жилищного порога или валидации здесь нет; расчёт сохранён в ledger.

Классификационный лист описывает распределение классов, регрессионный — численную цель под выбранной потерей. Оба связывают область с константой, но цели, значения листьев и критерии различаются.

Жадный рост, обрезка и неустойчивость

Локальное решение повторяется рекурсивно

Разбиение выбирается в активном узле по непосредственным детям, без перебора всех продолжений. Это жадная (greedy) процедура. Локально лучший выбор не обязан дать лучшее полное дерево при бюджете глубины или листьев.

Для примера используем Gini, глубину не больше двух и минимум два наблюдения в листе. Глубина корня нулевая. В каждом узле:

1. Остановитесь при чистых метках или предельной глубине.
2. Переберите пороги между различными значениями, оставляя минимум допустимого числа строк в каждом ребёнке.
3. Выберите минимум взвешенной Gini; при равенстве — меньший признак, затем порог. Остановитесь без допустимого разбиения или строго положительного локального улучшения.
4. Примите правило и повторите в детях. Записанный порядок — в глубину, сначала влево.

Порядок указывает, как мы обрабатываем узлы; он не означает, что все правила одного уровня оптимизируются совместно. Такой обычный поиск порога не обучает дерево градиентным спуском. Приняв правило в ходе роста, мы сохраняем его при построении потомков. Последующая обрезка удаляет ветви, а не переоптимизирует все их пороги.

В \(R\) лучший порог \(x_1\leq1.5\) даёт размеры 4 и 12. В \(R_L\) три порога второй координаты дают 1/3, 2/2, 3/1. Только 2.5 обеспечивает минимум два. Дети A–B и C–D чистые. Посещаем и останавливаем \(R_{LL}\), \(R_{LR}\), затем уже чистый \(R_R\). Листьев три, хотя глубина два допускает четыре. Остановка по чистоте исключает лишние правила.

Области и правила растут вместе

Рисунок 2 воспроизводит 12 записанных событий за 32 секунды. Точки и оси фиксированы; область меняется только при принятии правила. Пунктир — варианты, не дополнительные границы готового дерева. Для корня показаны три представительных варианта из шести в ledger; для левого ребёнка — все три с двумя недопустимыми по размеру. Плеер управляется вручную, без звука и автозапуска.

Рисунок 2: Одно событие управляет обеими панелями. Фиолетовый выделяет активный узел/область, выбранный пунктирный вариант или путь запроса. Синие круги — нули, оранжевые треугольники — единицы, фон — текущие решения листьев. G сокращает Gini, p1 — наблюдаемую долю единиц; это не калиброванная уверенность. Постер показывает принятие второго правила. Линия потомка заканчивается у родителя; запрос U идёт влево при равенстве, затем вправо.

Последовательность начинается одним листом, сравнивает и принимает корневое правило, затем левое дочернее. Явно останавливается в трёх чистых листьях и проводит \(U=(1.5,3.25)^\top\) через фиксированное дерево. Сравнение вариантов не меняет предсказаний, принятие меняет; запрос не меняет правил и счётчиков. Кадры удерживают дискретные состояния без интерполированных порогов или вымышленных деревьев.

Основные принятые состояния доступны без движения на Рисунок 3. Полный журнал хранит ID узлов/строк, количества, доли, допустимость вариантов, правила, остановки и точное время воспроизведения.

Рисунок 3: Один лист, принятое корневое и принятое левое разбиение. В соответствующих строках одинаковы оси и наблюдения; дерево и области описывают одно состояние. Смешанный левый лист первоначально выбирает ноль по правилу равенства. Второе разбиение отделяет A–B от C–D. Это и печатная замена видео.

Пусть \(N=16\) — общее число обучающих строк, \(\mathcal L(T)\) — листья дерева \(T\). Определим риск всего дерева:

\[ \mathcal R_G(T)=\sum_{R'\in\mathcal L(T)}\frac{n_{R'}}{N}I_G(R'). \]

Каждая \(R'\) — листовая область. Разбиение узла \(R\) меняет риск на \((n_R/N)\Delta I_G\). Корень уменьшает его на \(3/32\), четырёхстрочный левый ребёнок — на \((4/16)(1/2)=1/8\). Риск последовательно \(7/32\), \(1/8\), ноль; ошибок классификации — две, две, ноль. Снижение Gini и уменьшение ошибок различаются. Ни одна последовательность не даёт валидации или теста.

Остановить рост до подстройки ко всем деталям

Глубина, число листьев, минимальный размер листа и требуемое уменьшение неоднородности ограничивают множество деревьев, которые можно построить. Предел глубины ограничивает число вопросов на пути. Минимальное число наблюдений в листе исключает вариант, если любой потомок окажется слишком малым; это может менять выбор разбиения, а не только момент остановки. Минимальное улучшение исключает слишком малый выигрыш при заданной нормировке. В нашей иллюстрации требуется строго положительный локальный выигрыш Gini; пороги в программных реализациях нужно читать с учётом их собственной нормировки.

При тех же данных и равенствах глубина один оставляет пень с двумя листьями. Глубина два с минимумом три даёт тот же пень: левый узел из четырёх строк не разделить на два по три. Доли листьев \(0.5\) и \(1\), обучающих ошибок две. Это проверенные эффекты ограничений, не рекомендации реальным данным.

Больше листьев позволяет подстроиться к малым областям, ошибкам меток и особенностям выборки. Чистый обучающий лист может ошибаться в будущем. Но малый лист не обязательно шум: A–B — весь редкий класс примера. Сложность выбирают по валидации или подходящей CV с учётом метрики и зависимости данных. Обучающая таблица одна не определяет обобщение.

СоветПодумайте: что остановит узел?

Почему в \(R_L\) минимум три блокирует все разбиения при смешанных метках? Почему чистый узел из 12 строк останавливается, хотя численные пороги ещё есть?

Обрезать выросшее дерево по заданной цене

Предварительная обрезка (pre-pruning) ограничивает рост. Последующая обрезка (post-pruning) заменяет выбранные ветви выросшего дерева листьями. Области потомков объединяются, константа пересчитывается по всем строкам узла; наблюдения не удаляются.

Для классификационного примера зададим цель «риск–сложность»:

\[ \begin{aligned} J_\alpha(T)&=\mathcal R_G(T)+\alpha|\mathcal L(T)|,\\ \alpha&\geq0. \end{aligned} \]

Первый член — взвешенная Gini, нормированная одинаковым общим \(N\). Второй взимает \(\alpha\) за лист. Замена на долю ошибок или ненормированную сумму меняет смысл и масштаб \(\alpha\). Официальное руководство использует взвешенную неоднородность; другие изложения могут определять риск иначе.

Обрезкой нашего дерева можно получить ровно три поддерева:

Вариант	Листья	\(\mathcal R_G\)	\(J_\alpha\)
Полное дерево	3	\(0\)	\(3\alpha\)
Только корневое разбиение	2	\(1/8\)	\(1/8+2\alpha\)
Корень-лист	1	\(7/32\)	\(7/32+\alpha\)

Полное дерево и один лист равны по цене при \(\alpha=7/64\). Пень с двумя листьями никогда не минимизирует цель: для победы над полным нужно \(\alpha\geq1/8\), над одним листом — \(\alpha\leq3/32\); интервалы не пересекаются. При предпочтении меньшего дерева в равенстве ниже \(7/64\) выбираются три листа, на границе и выше — один. При \(\alpha=1/8\) цены \(3/8\), \(3/8\), \(11/32\); минимум у корня-листа, который всюду предсказывает единицу и ошибается на A–B.

Перебор явно отличает обрезку от прямого роста анимации. Ограничение глубины один даёт пень, который эта цель не выбирает: pre/post-pruning не обязаны совпадать. Ранжируются поддеревья этого дерева, не все возможные структуры. Полезное для новых данных \(\alpha\) тоже не найдено: альтернативы сравнивает валидация. Её результата и теста пример не сообщает.

Малое изменение данных сдвигает границу

Сохраним координаты, ограничения и равенства. В отдельной проверке чувствительности изменим только обучающую метку E с единицы на ноль. Это гипотетическое возмущение, не рекомендация перемечать данные ради улучшения модели.

Лучший корневой порог сдвигается с 1.5 к 2.5. В новой таблице \(x_1\leq2.5\) и \(x_2\leq2.5\) равны по Gini \(15/64\); меньший индекс выбирает \(x_1\). Слева снова \(x_2\leq2.5\), область нуля расширяется. У F в \((2,2)^\top\) метка остаётся единицей, предсказание меняется на ноль.

Рисунок 4: Проверка одной изменённой метки при одинаковых осях и правилах. Формы показывают метки, фон — решения. Только E меняет метку; F меняет лишь предсказание. Это зависимость от обучающей выборки, не сравнение точности на общей ненаблюдаемой популяции.

Жадный выбор может измениться при смене ранжирования вариантов или разрешении равенства, повлияв на предсказания для наблюдений, отличных от изменённой строки. Пример показывает возможность такой чувствительности; он не оценивает её типичную частоту и не доказывает неустойчивости каждого дерева. Усреднение предсказаний по-разному обученных деревьев может снизить часть вариативности, если их ошибки не слишком похожи. В следующем разделе рассмотрим предположения, необходимые для этого аргумента.

Усреднению нужно разнообразие

Изменённая метка в предыдущем примере сдвинула границу для других строк. Предположим, мы могли бы собрать другую обучающую выборку из той же популяции и обучить модель заново. Изменится ли предсказание при фиксированном входе? Этот вопрос касается дисперсии предсказаний между обучениями. Она отличается и от разброса целевых значений внутри листа, и от ошибки на одной фиксированной тестовой выборке.

Ансамбль объединяет несколько fit. Среднее может ослабить влияние особенностей выборки, но копии одинакового предсказания ничего не добавляют. Важны и вариация предсказаний, и её общая часть.

Разделить систематическую ошибку, вариацию обучения и новый шум

Только для этого вывода рассмотрим регрессию при фиксированном \(x\). Пусть \(f_*(x)=\mathbb E[Y\mid x]\) — условное среднее популяции, новая цель \(Y=f_*(x)+\epsilon\). Предполагаем конечные вторые моменты, \(\mathbb E[\epsilon\mid x]=0\) и независимость нового шума от выборки и случайности обучения при этом входе. Его дисперсия \(\sigma_\epsilon^2(x)\); гауссовость не нужна.

Пусть \(\mathcal D\) — случайная обучающая выборка, \(\omega\) — случайность процедуры, \(\widehat f(x;\mathcal D,\omega)\) — предсказание. Среднее по обучениям \(\mu(x)=\mathbb E_{\mathcal D,\omega}[\widehat f(x;\mathcal D,\omega)]\). Прибавим и вычтем его:

\[ Y-\widehat f =\epsilon+\bigl(f_*-\mu\bigr)+\bigl(\mu-\widehat f\bigr). \]

После возведения в квадрат и усреднения остаются три члена. Центрированная вариация fit и шум имеют нулевые средние; смешанный член исчезает по независимости. Все функции вычислены при фиксированном \(x\), ожидание берётся по выборкам, случайности обучения и новому шуму:

\[ \begin{aligned} \mathbb E[(Y-\widehat f)^2] &=\underbrace{(\mu-f_*)^2}_{\text{squared bias}}\\ &\quad+\underbrace{\mathbb E[(\widehat f-\mu)^2]}_{\text{prediction variance}}\\ &\quad+\underbrace{\sigma_\epsilon^2(x)}_{\text{fresh noise}}. \end{aligned} \]

Численная проверка. Пусть \(f_*(x)=1\), равновероятные fit дают 1 или 3, независимый новый шум — \(-1\) или \(+1\). Средний fit 2, квадрат смещения 1, дисперсии предсказания и шума по 1. Четыре равновероятные пары дают MSE 3. Это не средние по строкам одной обучающей выборки; точный перебор проверен генератором.

Bias здесь — систематическое смещение предсказания, не intercept. Это разложение квадратичной ошибки, не accuracy классификации на те же слагаемые. Оно не доказывает, что сложность всегда снижает смещение или бэггинг сохраняет смещение дерева исходной выборки.

Ковариация определяет пользу усреднения

При фиксированном \(x\) положим \(Z_m=T_m(x)\) и \(\overline T_M(x)=M^{-1}\sum_{m=1}^M Z_m\). Здесь \(Z_m\) — действительные регрессионные предсказания либо вероятности одного заданного класса. Все дисперсии и ковариации относятся к одному эксперименту повторного выбора данных и случайности обучения. Раскрывая квадрат суммы:

\[ \begin{aligned} \operatorname{Var}(\overline T_M) &=\frac{1}{M^2}\sum_{m=1}^M\operatorname{Var}(Z_m)\\ &\quad+\frac{2}{M^2}\sum_{m<k}\operatorname{Cov}(Z_m,Z_k). \end{aligned} \]

В простом частном случае каждое \(Z_m\) имеет дисперсию \(\sigma_T^2>0\), каждая различная пара — корреляцию \(\rho\). Пар \(M(M-1)/2\), ковариация каждой \(\rho\sigma_T^2\), поэтому:

\[ \operatorname{Var}(\overline T_M) =\sigma_T^2\left[\rho+\frac{1-\rho}{M}\right]. \]

При \(M=10\) относительная дисперсия равна \(0.1\) для \(\rho=0\), \(0.325\) для \(\rho=0.25\), \(0.775\) для \(\rho=0.75\). При \(\rho=1\) остаётся вся вариация. На рисунке индивидуальная дисперсия и корреляция фиксированы при росте \(M\): это алгебраическая иллюстрация, не измеренная кривая леса.

Рисунок 5: Относительная дисперсия среднего равнодисперсных предсказаний при трёх заданных корреляциях. Общая вариация создаёт ненулевой предел при положительной корреляции.

Если у деревьев общее ожидаемое предсказание \(\mu(x)\), линейность даёт \(\mathbb E[\overline T_M(x)]=\mu(x)\): усреднение не удаляет общее смещение. Бутстрэп может менять распределение дерева, поэтому сравниваются среднее и его собственные составляющие, не автоматически дерево исходной выборки.

Почему отдельные fit всё ещё коррелированы. Независимые bootstrap-выборки и seed могут давать независимость условно при фиксированных данных. При повторном сборе данных деревья разделяют одну исходную выборку. Общее условное среднее одинаково строящихся деревьев может меняться с \(\mathcal D\), создавая ковариацию. Разные seed не доказывают \(\rho=0\) в формуле.

СоветПредскажите перед продолжением

Даст ли десятикратное число сильно коррелированных деревьев десятикратное снижение дисперсии? Объясните ковариационным членом, а не числом файлов моделей.

Бутстрэп, OOB-оценка и случайные леса

Перевыбирать строки вместе с целями

Обычно есть одна выборка, не запас независимых наборов. Бутстрэп (bootstrap) независимо и равномерно выбирает с возвращением \(N\) индексов из \(N\) тренировочных строк. Вход и цель остаются парой. Строки повторяются или отсутствуют; есть \(N\) извлечений, не обязательно \(N\) различных наблюдений. Повторы влияют на счётчики, средние и критерии; удаление повторов меняет метод.

Бэггинг (bagging, bootstrap aggregating) обучает базовую модель на каждом бутстрэпе и объединяет ответы. Дерево не исправляет остатки предыдущего. Fit вычисляются отдельно, но общие исходные данные сохраняют статистическую зависимость.

Для явных повторов и пропусков используем отдельную синтетическую однопризнаковую регрессию, не перемеченные 16 классификационных точек.

Строка	\(r_1\)	\(r_2\)	\(r_3\)	\(r_4\)	\(r_5\)	\(r_6\)
\(x_1\)	1	2	3	4	5	6
\(y\)	0	0	2	2	4	4

Три возможные упорядоченные bootstrap-последовательности зафиксированы для проверки, не для демонстрации типичного качества. Каждой подберём регрессионный пень: корень глубины ноль, максимум один, минимум два извлечения на ребёнка; минимум суммарной квадратичной ошибки по серединам различных значений, меньший порог при равенстве, влево при \(\leq\). Средние учитывают повторы.

Дерево	Шесть извлечённых индексов	Правило	Среднее слева	Среднее справа
\(T_1\)	1, 1, 2, 4, 5, 6	\(x_1\leq3\)	\(0\)	\(10/3\)
\(T_2\)	1, 2, 3, 3, 6, 6	\(x_1\leq2.5\)	\(0\)	\(3\)
\(T_3\)	2, 2, 4, 5, 6, 6	\(x_1\leq4.5\)	\(2/3\)	\(4\)

У \(T_1\) цели \(0,0,0\) слева и \(2,4,4\) справа. Ledger перечисляет все допустимые пороги и проверяет минимум. Это обученные пни, не придуманные ответы.

Рисунок 6: Кратности строк и допустимость OOB для трёх пней. Читайте столбец сверху вниз: так находятся деревья, которым разрешено OOB-предсказание этой строки.

Почему пропускается около 37 процентов

Вероятность пропустить конкретную строку за одно извлечение — \(1-1/N\). За все \(N\) независимых извлечений:

\[ \begin{aligned} P(\text{row }i\text{ omitted}) &=\left(1-\frac1N\right)^N\\ &\longrightarrow e^{-1}\approx0.368. \end{aligned} \]

Линейность ожидания даёт число пропущенных \(N(1-1/N)^N\) и различных включённых \(N[1-(1-1/N)^N]\). Независимость событий пропуска разных строк не требуется. При \(N=6\) вероятность \((5/6)^6\approx0.335\), ожидаемое число различных включённых около \(3.99\). Ни 37%, ни среднее число не обязательны для каждого запуска. При замене \(N\) извлечений на \(B\) вероятность становится \((1-1/N)^B\).

Сначала OOB-предсказание каждого наблюдения

Для строки \(i\) обозначим \(\mathcal O_i\) индексы деревьев, чьи бутстрэпы полностью исключили строку. При \(|\mathcal O_i|>0\) её вневыборочное предсказание (out-of-bag, OOB) равно:

\[ \widehat y_i^{\mathrm{OOB}} =\frac{1}{|\mathcal O_i|}\sum_{m\in\mathcal O_i}T_m(x_i). \]

Набор меняется с \(i\). Для \(r_3\) допустимы деревья 1 и 3; дерево 2 видело \(r_3\) дважды. Ответы 0 и \(2/3\) дают \(\widehat y_3^{\mathrm{OOB}}=1/3\). Цель 2, квадрат ошибки \((2-1/3)^2=25/9\). Включение дерева 2 нарушило бы OOB, хотя оно входит в ансамбль.

Строка	Допустимые деревья	OOB-предсказание	Квадрат ошибки
\(r_1\)	3	\(2/3\)	\(4/9\)
\(r_2\)	нет	не определено	не оценивается
\(r_3\)	1, 3	\(1/3\)	\(25/9\)
\(r_4\)	2	\(3\)	\(1\)
\(r_5\)	2	\(3\)	\(1\)
\(r_6\)	нет	не определено	не оценивается

Пусть \(\mathcal C=\{i:|\mathcal O_i|>0\}\) — покрытые строки. Иллюстративная OOB MSE:

\[ \frac{1}{|\mathcal C|}\sum_{i\in\mathcal C} (y_i-\widehat y_i^{\mathrm{OOB}})^2 =\frac{47}{36}\approx1.306. \]

Покрытие \(|\mathcal C|/N=4/6\). Три дерева оставили два наблюдения без ответа. Не заменяйте неопределённость нулём и не сообщайте полное покрытие молча. Указывайте покрытие и число участников; больше деревьев обычно улучшает покрытие. При независимых бутстрэпах вероятность отсутствия OOB-участников среди \(M\) деревьев для фиксированной строки равна \([1-(1-1/N)^N]^M\).

Среднее собственных OOB MSE деревьев даёт \(55/27\approx2.037\), другую величину: наборы OOB различны, потеря среднего не равна среднему потерь. Для нового внешнего входа бэггинг использует все деревья; OOB исключает разные деревья ради оценки строк, которых они не видели.

OOB — полезная внутренняя оценка при подходящем сборе, не окончательный независимый тест. Многократный выбор настроек по OOB адаптируется к этим строкам. Обычный бутстрэп строк не защищает от связанных пациентов, повторных субъектов и временных утечек. Предобработка всех строк тоже даёт OOB-строке влияние: обучайте преобразования внутри каждого перевыбора либо используйте корректно вложенный pipeline валидации. Протокол должен соответствовать популяции и структуре зависимостей.

Укажите, что объединяется в ансамбле

Регрессия усредняет действительные ответы. Для классификации отдельно выбирают объединение:

• Жёсткое голосование (hard voting): каждое дерево выбирает класс, побеждает большинство голосов.
• Усреднение вероятностей: для каждого класса вычисляют \(\overline q_c(x)=M^{-1}\sum_m q_{m,c}(x)\) и выбирают наибольшее среднее; \(q_{m,c}(x)\) — доля класса в листе дерева \(m\), куда попал вход.

Для OOB-вероятностей и голосов действует то же ограничение допустимых деревьев. Разрешение равенства объявляют; здесь меньший класс. Среднее корректных вероятностных векторов сохраняет единичную сумму, но не доказывает калибровку.

Решения могут различаться: вероятности единицы \(0.49,0.49,1\) дают голоса \(0,0,1\) и нулевой класс, а средняя \(0.66\) выбирает единицу. Руководство леса scikit-learn задаёт усреднение вероятностей; нельзя молча подменять им пример большинства из практикума.

Случайный лес меняет кандидаты разбиения

Если один признак постоянно лучший, bootstrap-деревья всё ещё похожи. Стандартный случайный лес (random forest) добавляет выбор: в каждом узле случайно выделить подмножество признаков, затем найти среди них лучшее допустимое разбиение. В следующем узле подмножество может быть другим; это не однократное ограничение всех признаков дерева.

Вернёмся к 16 исходным строкам классификации. Поиск по обоим признакам даёт корневое правило \(x_1\leq1.5\) со взвешенным Gini \(1/8\). Если подмножество кандидатов этого узла содержит только \(x_2\), лучшее правило — \(x_2\leq2.5\) со взвешенным Gini \(3/16\). Поэтому случайное ограничение признаков может вынудить выбрать локально худшее разбиение. Его цель — уменьшить сходство обученных деревьев; любое снижение общей вариации нужно сопоставлять с ослаблением отдельных предсказаний. Точное сравнение корневых разбиений не является эмпирическим доказательством лучшего качества полученного леса. Руководство по лесам описывает перевыбор строк и выбор признаков в узлах как разные источники случайности.

Построение bootstrap-леса можно прочитать в четыре шага:

1. Для каждого дерева выберите бутстрэп парных обучающих строк.
2. В каждом подходящем узле выберите признаки и допустимое разбиение по заданным критерию и остановкам.
3. Сохраните листья и объединяйте ответы объявленным правилом.
4. Для OOB используйте только деревья без предсказываемой строки; перед оценкой сообщайте покрытие.

Размер подмножества — выбор модели, не универсальная доля \(d\). Глубина и размер листа управляют отдельными деревьями; число деревьев — стабильностью усреднения, хранением и ценой предсказания. Оно не восстанавливает отсутствующий сигнал, не убирает общее смещение и не гарантирует отложенную accuracy.

Что обоснует выбор леса?

Обучение на выборке и приведённая арифметика OOB не доказывают превосходства над одиночным деревом. Обоснованное сравнение использует одинаковые отложенные фолды и метрику для обеих моделей, обучает предобработку внутри обучающих фолдов и задаёт для каждого метода поиск по валидации среди параметров сложности. При необходимости разбиения должны учитывать группы или время. Сравнивайте предсказания на отложенных данных, вариацию между подходящими фолдами и стоимость обучения и предсказания; OOB используйте как дополнительную диагностику леса, а не сравнивайте его OOB-оценку непосредственно с обучающим качеством дерева. После фиксации настроек нетронутая тестовая выборка даёт отдельную итоговую оценку. Раздел о выборе модели разовьёт этот протокол вместе с базовой SVM недели 02.

СоветПроверьте механизм

Какая случайность меняет кратности строк, а какая — доступные узлу признаки? Какие деревья могут участвовать в OOB-предсказании конкретного наблюдения?

Бустинг обучает поправки

Бэггинг усредняет ответы нескольких моделей. Бустинг (boosting) строит последовательность: новое дерево зависит от текущего ансамбля и добавляет поправку. Малое дерево полезно, даже если плохо предсказывает исходные цели само по себе. Практикум развивает переход от отдельных fit к последовательным поправкам.

Начать с лучшей константы и найти остаток

Для регрессии используем половину квадрата ошибки примера и её среднее:

\[ \begin{aligned} L_i(F)&=\frac12\bigl(y_i-F(x_i)\bigr)^2,\\ \bar L(F)&=\frac1N\sum_i L_i(F). \end{aligned} \]

Лучшая константа — обучающее среднее \(F_0(x)=\bar y\). На шаге \(m\) вычисляем остаток по текущему предсказанию:

\[ r_{mi}=y_i-F_{m-1}(x_i). \]

По парам \((x_i,r_{mi})\) подбираем малое регрессионное дерево \(T_m\), минимизируя квадраты отклонения от остатков с заданными ограничениями. Лист хранит средний остаток строк. Добавляем масштабированную поправку:

\[ F_m(x)=F_{m-1}(x)+\eta T_m(x). \]

Здесь \(\eta>0\) — shrinkage, уменьшение шага. Используем фиксированное \(\eta\) и средние остатков без дополнительного поиска шага или пересчёта листьев. Начальная константа и прежние деревья фиксируются при добавлении нового: это поэтапное обучение (stage-wise). Дерево учит функцию \(x\), поэтому поправка определена и для новых входов, не только обучающих строк.

Полная поправка для шести строк

Используем таблицу W03-C, но теперь все шесть строк без бутстрэпа: \(x_1=1,\ldots,6\), \(y=(0,0,2,2,4,4)\). Глубина один, минимум две строки в листе, минимум квадратов по серединам соседних значений, меньший порог при равенстве, \(\leq\) влево. Берём \(\eta=0.4\). Это учебные настройки, не рекомендации.

Начальное среднее равно \(F_0=2\), поэтому первый вектор остатков — \((-2,-2,0,0,2,2)\). Условию размера листа удовлетворяют только пороги 2.5, 3.5 и 4.5. Квадратичные ошибки подбора этих остатков равны соответственно 4, \(16/3\) и 4. Правило разрешения равенства выбирает \(x_1\leq2.5\). Средние остатков равны \(-2\) слева и 1 справа. Поэтому добавляемая поправка равна \(-0.8\) или \(+0.4\), а не всему предсказанию обученного дерева.

\(x_1\)	\(y\)	\(F_0\)	\(r_{1i}=y-F_0\)
1	0	2	−2
2	0	2	−2
3	2	2	0
4	2	2	0
5	4	2	2
6	4	2	2

Используйте остатки как цели дерева, затем обновите предиктор:

\(x_1\)	\(T_1(x_i)\)	\(0.4T_1(x_i)\)	\(F_1(x_i)\)
1	−2	−0.8	1.2
2	−2	−0.8	1.2
3	1	0.4	2.4
4	1	0.4	2.4
5	1	0.4	2.4
6	1	0.4	2.4

Строки 3 и 4 имели нулевой остаток, но сдвигаются вверх из-за общего листа со строками 5 и 6. Дерево кусочно-постоянно приближает вектор остатков, не задаёт шесть независимых обновлений. Для обучения важна общая цель, а не улучшение каждой строки на каждом шаге.

Рисунок 7: Поправка изменяет предиктор. Панели используют общие порог и записанные значения, но разный смысл вертикальных осей. Пунктирное дерево масштабируют до сложения. Это проверенный обучающий расчёт, не подтверждение качества новых данных.

Обучающая MSE уменьшается с \(8/3\approx2.667\) до \(104/75\approx1.387\); средняя половинная цель — с \(4/3\) до \(52/75\). Масштаб отчёта не меняет минимизирующее предсказание, но меняет множители производных.

На следующем шаге пересчитаем \(r_{2i}=y_i-F_1(x_i)\): \((-1.2,-1.2,-0.4,-0.4,1.6,1.6)\). Повторное использование первых остатков обучало бы устаревшую поправку. Точный генератор хранит три шага:

Шаг	Порог	Обучающая MSE после обновления
Начальная константа	нет	\(8/3\approx2.667\)
1	2.5	\(104/75\approx1.387\)
2	4.5	\(1064/1875\approx0.567\)
3	4.5	\(12776/46875\approx0.273\)

При постоянном shrinkage итог \(F_M(x)=F_0(x)+\eta\sum_{m=1}^M T_m(x)\). Это сумма поправок, не среднее деревьев, независимо обученных на \(y\).

Почему подбор остатков — градиентный шаг предсказаний

Для дифференцируемой потери примера определим псевдоостаток (pseudo-residual):

\[ r_{mi}=-\left. \frac{\partial L_i(F)}{\partial F(x_i)} \right|_{F=F_{m-1}}. \]

Для половины квадрата производная \(F(x_i)-y_i\), антиградиент — обычный остаток. Для полного квадрата он \(2(y_i-F(x_i))\), для MSE по каждому предсказанию — \(2(y_i-F(x_i))/N\), для нашей половинной средней — \(r_{mi}/N\). Общий положительный множитель меняет масштаб шага. Псевдоцели определяем производными отдельных примеров, усреднение указываем отдельно, не пряча множитель в \(\eta\).

Представьте вектор текущих предсказаний на всех обучающих входах. Его антиградиент задаёт желаемое изменение каждой координаты. Регрессионное дерево с ограниченной сложностью приближает это направление, обучаясь на псевдоостатках. Оно также распространяет поправку на входы за пределами обучающей таблицы. В этом полезный смысл функционального градиентного спуска (functional gradient descent); пороги разбиений по-прежнему выбираются жадным поиском, а не дифференцированием по ним.

Для половинной квадратичной потери и средних остатков выполняется \(\sum_i r_{mi}T_m(x_i)=\sum_i T_m(x_i)^2\). Раскрывая новую ошибку:

\[ \begin{aligned} &\mathrm{MSE}(F_{m-1})-\mathrm{MSE}(F_m)\\ &\qquad=\eta(2-\eta)\,\frac1N\sum_i T_m(x_i)^2. \end{aligned} \]

Это обновление уменьшает обучающую MSE при \(0<\eta<2\) и ненулевой поправке. Генератор проверяет тождество каждого шага. Вывод зависит от потери и средних листьев, не гарантирует улучшение произвольной цели, приближённого шага или новых данных.

Некоторые алгоритмы сначала выбирают области по псевдоостаткам, затем оптимизируют листья по исходной потере либо используют ньютоновское приближение со вторыми производными. Дополнительный поиск шага может задавать множитель. Это разные решения, не скрытые части примера. См. официальную формулировку.

Бинарный бустинг складывает логиты, затем вычисляет вероятности

Вернёмся к различию недели 02: \(F(x)\) — бинарный логит, \(q(x)=\sigma(F(x))\) — оценка вероятности единицы. При метках \(y_i\in\{0,1\}\):

\[ q(x)=\frac{1}{1+\exp(-F(x))}. \]

BCE как функция скора:

\[ \begin{aligned} L_i(F)&=\log(1+\exp(F(x_i)))\\ &\quad-y_iF(x_i). \end{aligned} \]

Устойчивая форма \(\max(F,0)+\log(1+\exp(-|F|))-y_iF\) вычисляется для каждой строки. Дифференцируйте по логиту, не по вероятности:

\[ \begin{aligned} \frac{\partial L_i}{\partial F(x_i)}&=q(x_i)-y_i,\\ r_{mi}&=y_i-q_{m-1}(x_i). \end{aligned} \]

Положительный псевдоостаток требует увеличить логит, отрицательный — уменьшить. Обучите регрессионное дерево на этих действительных псевдоостатках и добавьте его выход к \(F\). Это регрессионное дерево внутри классификатора: ему не требуется выдавать класс или вероятность.

Для начальной доли единиц \(\pi\in(0,1)\) лучшая константа BCE удовлетворяет \(\sigma(F_0)=\pi\), откуда:

\[ F_0=\log\frac{\pi}{1-\pi}. \]

При одном обучающем классе конечного нерегуляризованного оптимума константы нет. Явно используйте подходящую постоянную классовую модель либо объявленные сглаживание/регуляризацию; не вычисляйте бесконечный логит и не называйте незаметное обрезание тем же решением.

Бинарный шаг со всеми названными величинами

Возьмём отдельные синтетические бинарные цели \(y=(0,0,1,0,1,1)\) на тех же шести координатах, не прежние регрессионные значения. Здесь \(\pi=1/2\), значит \(F_0=0\), все начальные вероятности \(1/2\). Псевдоостатки \((-1/2,-1/2,1/2,-1/2,1/2,1/2)\).

Сохраним ограничения пня и \(\eta=0.4\). Псевдоостатки выбирают 2.5, равный по оценке 4.5, но меньший. Среднее слева \(-1/2\), справа \(1/4\). Явное обновление первого порядка даёт:

Строки	\(T_1\)	Логит \(F_1\)	Вероятность \(q_1\)
1, 2	\(-0.5\)	\(-0.2\)	\(0.450166\)
3–6	\(0.25\)	\(0.1\)	\(0.524979\)

Средняя BCE падает с \(0.693147\) до \(0.645644\). Вероятности получены сигмоидой обновлённых логитов. Прямое добавление \(0.4T_1\) к старым вероятностям дало бы другие числа \(0.3\) и \(0.6\), не это обновление. Дальнейшие бесконтрольные прибавления могли бы выйти из \([0,1]\).

Рисунок 8: Добавьте действительную поправку к скору, затем примените сигмоиду. Панели представляют одно состояние в разных вертикальных единицах. Метки бинарны, цели поправки действительны.

Решение класса — отдельный шаг. При нашем меньшем классе в равенстве единица требует \(q>1/2\). В неделе 02 использовалось \(q\geq\tau\), поэтому при точном \(\tau=1/2\) решение другое. После шага ни одна вероятность не равна \(1/2\). Смена порога меняет решения без изменения логитов или BCE.

В показанном шаге выходы листьев равны средним псевдоостатков. Это не численное воспроизведение библиотечного GradientBoostingClassifier, который может уточнять эти значения. Например, ньютоновская поправка листа в начальном состоянии использует сумму \(y_i-q_i\), делённую на сумму \(q_i(1-q_i)\), и в тех же областях до уменьшения шага даёт \(-2\) и \(1\) вместо \(-1/2\) и \(1/4\). Прежде чем сравнивать числа, явно задайте алгоритм.

Shrinkage ограничивает добавление; валидация — обучение

Меньшее \(\eta\) ослабляет поправку и обычно требует больше стадий для сравнимого fit. Оно не делает произвольное шумное направление полезным. Глубина/размер листа, число стадий и shrinkage взаимодействуют и выбираются по валидации. Early stopping следит за подходящей валидационной целью по заданному правилу и сохраняет лучшую стадию, не ожидая остановки обучающей потери. Тест стадию не выбирает.

Бустинг может менять и смещение, и дисперсию. Лозунг «бэггинг снижает дисперсию, бустинг — смещение» мотивирует, но не гарантирует. Оба подхода ошибаются при утечке, сдвиге, слабых признаках и неподходящей сложности. Снижение MSE/BCE таблиц доказывает только улучшение заданных обучающих целей конкретными шагами.

СоветПредскажите следующую поправку

У положительного примера малая вероятность. Каков знак \(y-q\)? Что меняют до пересчёта вероятности? Почему следующий регрессионный остаток использует \(F_1\), не \(F_0\)?

Современные инструменты и корректный выбор модели

Библиотека способна обучить сложный ансамбль, пока эксперимент отвечает не на тот вопрос. До выбора пакета определите наблюдение, доступную при предсказании информацию и полезный результат новых данных. Оцениваемую модель совместно задают алгоритм, предобработка и процедура выбора.

XGBoost, LightGBM и CatBoost

Пакеты реализуют бустинг деревьев с разными инженерными и модельными решениями. Это не три новые потери, и их числа не обязаны совпадать с примерами первого порядка. Ниже — вопросы к инструментам, не рейтинг скорости или точности.

Библиотека	Особенность построения
XGBoost	Бустинг с явной регуляризованной целью, градиентами и кривизной в обновлениях. См. вывод.
LightGBM	Гистограммный поиск, рост leaf-wise: расширяется лист максимального улучшения. Ограничение глубины не превращает рост в level-wise. См. особенности.
CatBoost	Бустинг со встроенными категориальными преобразованиями, в том числе статистиками по порядку перестановки и one-hot в заданных случаях. См. преобразования.

«Поддерживает пропуски и категории» недостаточно без соглашений о входе:

Библиотека	Пропуски и категориальные входы
XGBoost	Деревья обучают направление ветви для пропусков (FAQ). Нативные категории требуют объявленного типа и включённого поддерживаемого метода; пример Python использует category, enable_categorical=True, hist. При сериализации сохраняйте категориальные сведения (руководство).
LightGBM	Поддерживаются численные пропуски; ноль не обязательно пропуск. Категории объявляют явно, целые коды соблюдают правила, включая отрицательные значения (подробнее).
CatBoost	Численные пропуски обрабатываются заданным режимом (руководство). Категориальные столбцы обозначают, пропущенным категориям задают постоянное представление вроде строкового токена; категориальные float/NaN не взаимозаменяемы с численными NaN (FAQ).

Целые коды категорий — идентификаторы, не обязательно упорядоченные измерения. Передача как обычных чисел может навязать порядок. Сохраняйте значения категорий между обучением и предсказанием. Новая категория, пропуск и записанный ноль — разные события с явными представлениями. Нативная обработка не защищает от утечки цели или смены сбора данных.

Библиотека	Настройки и ограничения
XGBoost	Shrinkage, число раундов, глубина, ограничения детей и штрафы листьев; смысл зависит от booster и метода дерева (параметры).
LightGBM	num_leaves, min_data_in_leaf, глубина, скорость и раунды; leaf-wise требует контроля сложности, особенно на малых данных (настройка).
CatBoost	Глубина, скорость, итерации, регуляризация листьев; CPU/GPU и политики роста имеют документированные ограничения (параметры).

Источники проверены 22 октября 2026: документация обозначена XGBoost 3.4.2, LightGBM 4.7.0; онлайн-руководство CatBoost без версии, рядом зафиксирован выпуск 1.2.10. Это срез документации, не проверка исполнения трёх выпусков. Для воспроизведения записывайте установленные версии, API/backend. Нет универсально самого быстрого, точного или свободного от предобработки пакета.

Кросс-валидация оценивает процедуру обучения

Гиперпараметр, например глубина, shrinkage или SVM \(C\), выбирают вне обычного подбора параметров. Направлять выбор может отложенная валидация. При малом объёме данных кросс-валидация (CV) переиспользует выборку разработки в нескольких разбиениях: обучение на тренировочной части фолда, предсказание отложенной, сводка выбранной метрики по фолдам.

Отложенный фолд исключается из всех обучаемых шагов его предиктора. Для численной SVM — заполнение пропусков при необходимости, масштабирование, fit, всё по тренировочной части. Словари категорий обучают внутри фолда с правилом неизвестных категорий. Target encoding требует особой осторожности: значение тренировочной строки не должно выдавать её собственную метку; внутри обучения тоже нужна подходящая cross-fitting или ordered-схема.

Scaler всей выборки разработки до CV позволяет отложенным строкам влиять на статистики. Отбор признаков, снижение размерности и кодирование целей дают более прямые утечки. Pipeline явно задаёт границу: всю цепочку клонируют и обучают отдельно внутри фолда, затем применяют к его отложенным строкам. См. типичные ошибки.

Разбиение должно соответствовать задаче. Стратификация сохраняет пропорции приблизительно независимых бинарных наблюдений, но не делает повторных пациентов, связанные записи или соседние моменты независимыми. Для новых групп используйте разделение групп, для будущего — временное forward-разбиение. Исключайте признаки, недоступные в момент предсказания. Руководство CV различает эти случаи.

Ранняя остановка (early stopping) тоже использует информацию данных. Если она выбирает стадию бустинга внутри обучения по CV, используйте внутреннее разбиение на обучение и валидацию, а не выбирайте стадию по внешнему фолду, оценку которого предполагается считать независимым свидетельством качества. Итоговая тестовая выборка не должна выбирать предобработку, порог, стадию остановки или бюджет поиска.

Искать в объявленном пространстве, а не среди бесконечных оценок

Сетка перебирает перечисленные конфигурации. Случайный поиск (random search) выбирает их из объявленных распределений и может попробовать больше значений важных параметров, чем малая декартова сетка. Логарифмический масштаб полезен для различий \(C\) или скорости на порядки величины, но диапазон остаётся модельным выбором. См. руководство поиска.

Бюджет имеет конкретный эффект. Если независимый вариант с вероятностью 0.1 попадает в заданную полезную область, десять попыток попадут туда с вероятностью \(1-0.9^{10}\approx0.651\). Расчёт предполагает фиксированную область и независимость; это не вероятность успеха настоящей настройки, где полезная область неизвестна.

Байесовская оптимизация по прежним конфигурациям и валидационным результатам строит суррогат поверхности отклика. Acquisition rule предлагает новый вариант, сочетая обещанное качество и неопределённость. Его оценивают по тому же протоколу и обновляют суррогат. Snoek, Larochelle, Adams рассматривают гауссовский процесс. Суррогат не обязан быть самим классификатором; поиск всё равно расходует валидационные сведения, не исправляет разбиение и не гарантирует глобальный оптимум малого бюджета.

Записывайте пространство, число вариантов или лимит времени, метрику, фолды, seed и равенства. Равные числа попыток не равны вычислениям или полноте охвата. Вместе с выбранным качеством изучайте train/validation-разрыв, число OOB-участников, хранение и цену предсказания. Вариация фолдов описательна, но пересечение тренировочных частей не превращает её автоматически в доверительный интервал.

Разделяйте выбор и итоговую оценку

Максимум многих шумных валидационных оценок предпочитает положительный шум наряду с полезной настройкой. Средняя CV для выбора победителя — оценка отбора, не независимая оценка выбранной процедуры.

Два обоснованных варианта:

1. Отложить итоговый тест. Все сравнения и настройки — на данных разработки; затем зафиксировать процедуру, переобучить на разработке и оценить тест без новых решений по результату.
2. Вложенная CV: каждая внешняя тренировочная часть содержит свой внутренний поиск вместе с предобработкой и выбором семейства. Победитель оценивается на нетронутом внешнем фолде. Внешние результаты оценивают весь отбор, не конфигурацию, заранее выбранную по всем фолдам.

Если тест вызвал новую настройку, он стал частью разработки; дальнейшим утверждениям нужны новые независимые данные. Leaderboard соревнования создаёт ту же обратную связь: повторные отправки и ручные решения адаптируются даже без видимых меток. Малый прирост не устанавливает улучшение популяции. Следуйте инструкции лабораторной; ниже нет её данных или решения.

Сравнение с масштабированной SVM: воспроизводимый мини-эксперимент

Гладкая ядровая граница и осевые области дерева имеют разные индуктивные предположения. Для расстояний ядра важны масштабы. В разделе SVM недели 02 \(C\) управляет штрафом мягкого зазора, \(\gamma\) — масштабом расстояния RBF. Протокол должен быть общим. Сообщение преподавателя о сильных SVM в лабораторной относится к той задаче, не является универсальным рейтингом, который нужно встроить в пример.

Для отдельной иллюстрации генерируем 240 наблюдений двух лун, шум 0.22, seed 2026; вторую координату умножаем на 100 как разные единицы. Стратифицированный тест из 60 строк откладываем с seed 2026. Остальные 180 делим на общие три стратифицированных фолда для всех вариантов, shuffle seed 2027. Каждый fit обучает 120 и предсказывает 60; тест ни один фолд не использует.

До оценки объявим три варианта каждого семейства:

Семейство	Поиск и фиксированные настройки
Одно дерево	Глубина 2, 4 или без ограничения; минимум листа 2.
Лес	Минимум листа 1, 3 или 6; 100 bootstrap-деревьев, квадратный корень числа признаков на узел.
Гистограммный бустинг	Максимум листьев 3, 7 или 15; 80 стадий, shrinkage 0.1, минимум листа 10, early stopping выключен.
RBF SVM	\(C=1,\gamma=0.1\); \(C=1,\gamma=1\); либо \(C=10,\gamma=1\). StandardScaler внутри тренировочной части каждого фолда; без калибровки вероятностей.

Это малое сравнение оценивателей scikit-learn, не XGBoost/LightGBM/CatBoost. Запуск: Python 3.9.6, NumPy 1.26.4, scikit-learn 1.6.1, один поток. Случайность деревьев использует seed 2026. По три варианта дают одинаковое число объявленных попыток, не одинаковую вычислительную цену или исчерпывающую оптимизацию.

Главная метрика — бинарная ROC-AUC, положительный класс один. Деревья/ансамбли используют непрерывные вероятности единицы, SVM — signed decision scores. Ранжированию не нужна калиброванная вероятность; пороговые классы теряют информацию порядка. API SVC различает скоры и необязательное оценивание вероятностей.

Внутри семейства выбирают максимум средней AUC фолдов, затем тем же правилом общего победителя; точные равенства разрешаются первым записанным вариантом. Скрипт хранит все варианты, ID фолдов, отложенные скоры и независимо проверяет AUC сравнением положительных/отрицательных пар с половиной балла за равенство.

Семейство	Выбранные настройки	Средний AUC по CV
Дерево	depth=None	0.8739
Случайный лес	leaf=1	0.9680
Гистограммный бустинг	leaves=7	0.9613
RBF SVM с масштабированием	C=1, gamma=1	0.9863

Заранее заданное правило выбора по CV выбирает RBF SVM с масштабированием (C=1, gamma=1). После повторного обучения на всех 180 примерах выборки разработки его единственный итоговый тестовый ROC-AUC равен 0.9989 на 60 примерах. Остальные семейства не оцениваются на тесте для дальнейшего выбора.

Значения CV выше использованы для выбора, не являются независимым тестовым сравнением четырёх методов. Тест — один малый результат. Гладкая геометрия лун благоприятна криволинейным границам; смена данных, шума, разбиения и пространства поиска может изменить порядок. Выводов о лабораторном соревновании нет. Seed и настройки не менялись ради воспроизведения сообщённого преподавателем рейтинга.

Синтетические строки и полный журнал позволяют проверить расчёт. Скрипт проверяет, что среднее каждого SVM scaler использует только свои тренировочные строки. Seed воспроизводит запуск, но не заменяет сведения по подходящим выборкам, разбиениям и задачам.

Итоги, расширения и упражнения

Три способа изменить предсказание

Дерево обучается разбиению пространства и задаёт локальные константы. Его полезность связана с нелинейными правилами, которые легко проследить; чувствительность отчасти возникает из дискретного выбора разбиений. Бэггинг усредняет предсказания моделей, обученных на перевыбранных данных. Его преимущество зависит от общей части вариативности этих предсказаний. Случайный лес меняет наборы признаков-кандидатов наряду с кратностями строк, разнообразя полученные модели. Бустинг вместо этого последовательно добавляет поправки, определённые функцией потерь. Его классификатор объединяет скоры до преобразования в вероятности.

Механизм	Что обучают и объединяют
Дерево	Жадные правила и значения листьев; один путь даёт ответ.
Бэггинг/лес	Отдельные fit перевыбранных строк; в данном лесе ещё случайные признаки узлов; средние значений/вероятностей либо заданные голоса.
Бустинг	Последовательные деревья текущих псевдоостатков, возможно с оптимизацией листьев; масштабированные поправки добавляются предиктору.

Ни одна конструкция сама не определяет обобщение. Нужны правильная граница данных, метрика задачи и сведения, не потраченные на выбор метода.

Частые смешения понятий

Различие	Следствие
Неоднородность и отложенная потеря	Обучающее улучшение разбиения не доказывает обобщение.
Локальное разбиение и оптимум дерева	Жадность не оптимизирует все будущие правила совместно.
Раздельные fit и независимые ответы	Общие данные могут сохранять большую ковариацию.
OOB-предсказание и ошибка дерева	Сначала объединяют допустимые ответы строки, затем оценивают.
Средние вероятностей и голоса	Решения могут различаться; калибровка не следует ниоткуда автоматически.
Остаток и псевдоостаток	Совпадают при половине квадрата на примере, не при любой потере/редукции.
Бинарный скор и вероятность	Поправку добавляют логиту, затем применяют сигмоиду.
Выбранная CV и итоговая оценка	Повторная настройка расходует валидационные сведения, включая leaderboard.

Связь с последующими методами

Листья обученного дерева задают фиксированные области. В неделе 04 сети обучают промежуточные представления производными. Общи модели, цели и границы оценки; различается поиск полезных функций. Неделя 07 возвращает вероятностные модели и обоснования потерь и неопределённости.

Дополнительно: табличные фундаментальные модели (tabular foundation models). TabPFN и TabICL используют предобучение и in-context learning по предоставленной таблице. Значительная часть обучения переносится до текущей задачи, но роли данных, применимость, вычислительные ограничения и настройки остаются важны. Это дополнительное чтение, не обязательный вывод или выполненный бенчмарк. Версию оценивают по общему отложенному протоколу, не по названию «foundation model».

Дополнительные упражнения

Это новые тренировочные задачи, не решения оцениваемой лабораторной. Покажите вычисление и толкование; ответов здесь нет.

1. Путь и решение. По исходному дереву проведите \((1.5,2.5)^\top\) и \((1.5001,2.5)^\top\). Дайте долю листа и класс, укажите важное соглашение равенства.
2. Взвешивание разбиения. У родителя счётчики \((3,5)\). A даёт \((3,1)\) и \((0,4)\), B — \((1,3)\) и \((2,2)\). Найдите взвешенную Gini и объясните необходимость размеров детей.
3. Остановка или обрезка. Для трёх поддеревьев при \(\alpha=0.10\) и \(0.12\) найдите все штрафованные цели и выбор. Почему ограничение глубины не обязано повторить его?
4. Усреднение коррелированных fit. При индивидуальной дисперсии 4, корреляции 0.3, \(M=5\) найдите дисперсию среднего и предел при росте \(M\). Задайте предположения и вывод об общем смещении.
5. OOB-участники. Добавьте четвёртый бутстрэп \((1,1,3,4,5,5)\). Найдите его OOB и новые наборы участников всех строк. Какие предсказания ещё нужны перед новой OOB MSE? Одного списка пропусков недостаточно.
6. Следующая поправка. Из регрессионного \(F_1\) обучите допустимый пень с \(\eta=0.4\). Найдите MSE и объясните строки с выросшей потерей, если они есть. Отдельно найдите знак бинарного псевдоостатка при \(y=1,q=0.2\) и величину, к которой добавляют поправку.
7. Аудит поиска. Команда кодирует цели по всем строкам, делает случайную CV, пробует 100 настроек, выбирает максимум и настраивает после каждой отправки leaderboard. Исправьте предобработку, зависимое разбиение при необходимости и итоговую оценку.
8. Корректное сравнение. Для повторных клиентов и пропущенных категорий задайте сравнение дерева/леса/бустинга/масштабированной SVM: вопрос, метрику, роли, входы, бюджет, early stopping, измерения ресурсов. Что обоснует и чего не обоснует выбор метода?

Источники и дальнейшее чтение

• Справочник Яндекса: деревья.
• Справочник Яндекса: ансамбли.
• Самостоятельная тема SVM недели 02 и официальная документация реализации.
• Презентации деревьев и ансамблей доступны выше. Официальные документы и первичные статьи процитированы в месте соответствующих утверждений; дата среза инструментов указана в тексте.