3Шум, смещение и разброс

3.1Напоминание: постановка задачи

Пусть есть пара случайных величин $(X,Y)$ и данные $D=\left\{\right(x_1,y_1),\dots ,(x_n,y_n\left)\right\}$, являющиеся выборкой из $(X,Y)$. Иными словами, мы считаем, что каждая из пар $(x_1,y_1),\dots ,(x_n,y_n)$ распределена в соответствии с распределением $(X,Y)$ и все пары независимы в совокупности. (При этом $x_j$ конечно не является независимым с $y_j$.) Будем обозначать распределение $D$ через $(X,Y{)}^n$ (распределение $D$ действительно является декартовой степенью распределения $(X,Y)$ в силу независимости).

Пусть $x_j\in X$, $y_j\in Y$. Чаще всего $X=R^d$, где $d$ — количество признаков. Мы также сейчас будем считать, что $Y=R$, то есть мы рассматриваем задачу регрессии (предсказания числовой переменной).

Алгоритм $a$ машинного обучения принимает на вход данные $D$ и возвращает функцию $f:X\to Y$, которая предсказывает значение $y$ по данному набору признаков $x$. Функция $f$ называется обученным алгоритмом. Формально:

Для оценки качества предсказаний задана некоторая функция потерьВеличина $L(y,\hat{y})$ измеряет, насколько нам плохо от того, что при правильном ответе $y$ мы предсказали $\hat{y}$. Сегодня на протяжении всей лекции мы будем рассматривать квадратичную функцию потерь:На прошлой лекции мы показали, что для квадратичной функции потерь самое лучшее предсказание — это матожидание условного распределения:Проблема состоит в том, что на практике мы никогда не знаем истинное распределение $(X,Y)$ и таким образом не можем найти матожидание (3.1). Вместо этого мы используем данные $D$ для нахождения некоторого приближения $f_{best}$.

3.2Ожидаемая ошибка

Пусть мы получили некоторые данные $D$, обучили на них алгоритм $a$ и получили предсказывающую функцию $f=a\left(D\right)$. Мы хотим минимизировать ожидаемую ошибку предсказания на новом объекте $(x_{new},y_{new})$, полученном из того же распределения $(X,Y)$. Однако, теперь нам необходимо учесть, что не только новый объект является случайной величиной, но и данные $D$ мы рассматриваем как случайную величину — разные обучающие выборки будут приводить к разным функциям $f$, которые будут давать разные предсказания. Таким образом, нас интересует следующая ожидаемая ошибка:где $D$ распределено как $(X,Y{)}^n$, $(x_{new},y_{new})$ распределено как $(X,Y)$ и независимо от $D$. Введём обозначения: $$\begin{array}{}f\left(x\right)& =a\left(D\right),& \hat{y}& =f\left(x_{new}\right).& \text{(3.3)}& \text{(3.4)}\end{array}$$ Для фиксированного $x_{new}$, $\hat{y}$ — это некоторая случайная величина (т.к. она зависит от $D$, которая также случайная величина). Обозначим распределение $\hat{y}$ для фиксированного $x_{new}$ через $\hat{Y}\left(x_{new}\right)$.

С помощью леммы 1 из предыдущей лекции можно переписать (3.2) следующим образом:

где $y_{new}$ и $\hat{y}$ независимы. Последнее следует из того факта, что мы считаем $(x_{new},y_{new})$ независимым от $D$. Иными словами, то, какие данные мы имеем, само по себе никак не влияет на процесс генерирования нового объекта $(x_{new},y_{new})$ — это выглядит вполне реалистичным предположением.

Теперь мы будем оценивать внутреннее матожидание в (3.5) для фиксированного $x_{new}$.

3.3Разложение ожидаемой ошибки

3.4Пример: метод k ближайших соседей (k-NN)

Метод k ближайших соседей (k nearest neighbors, k-NN) — простейший метод машинного обучения. Для задачи регрессии он основан на непосредственной оценке идеального предсказания $E[Y\mid X=x]$ по выборке: где $N_k\left(x\right)$ — множество индексов элементов $x_i$, являющихся $k$ ближайшими соседями к $x$.

Для примера, рассмотрим распределение $(X,Y)$, заданное следующим образом: $$\begin{array}{cc}X\sim & Uniform(-1,1);\\ \epsilon \sim & N(0,{\epsilon }_0);\\ Y=& X^2+\epsilon .\end{array}$$ Что можно сказать о смещении и разбросе для kNN при различных $k$? Рассмотрим экстремальные случаи — $k=1$ и $k=n$. При $k=1$ предсказание равно одному из значений $y_j$ и разброс предсказания примерно равен разбросу условного распределения $Y\mid X=x$, то есть ${\epsilon }_0^2$. При $k=n$, предсказание в любой точке есть среднее от всех $y_j$, $j=1,\dots ,n$ ($n$ — общий размер выборки). Разброс предсказаний теперь равен ${\epsilon }_0^2/n$ (см. параграф 1.4.3).

Что происходит со смещением? При $n=k$ предсказание $f\left(x\right)$ не зависит от $x$ и его матожидание равно $$\begin{array}{cc}E\left[f\right(x\left)\right]=& E\frac{y_1+\dots +y_n}{n}=E\left[Y\right]=E_{X}E[Y\mid X]=\\ =& E_X{X}^2=\frac{1}{2}{\int }_{-1}^1{x}^{2}dx=\frac{1}{3}.\end{array}$$ Таким образом, смещене в точках, далёких от $\sqrt{1/3}$, будет большим.

Наоборот, при $k=1$, $f\left(x\right)=y_j$, где $j$ таково, что $x_j$ является ближайшим соседом $x$. Матожидание предсказания в этом случае равно $x_j^2$, а расстояние от $x$ до $x_j$ составляет примерно $2/n$ (т.к. точки $\left\{x_k\right\}$ распределены равномерно). Таким образом, смещение примерно равно $x_j^2-x^2=O\left(1/n\right)$ и становится сколь угодно маленьким при больших $n$.

В целом, увеличение $k$ приводит к тому, что при вычислении $f\left(x\right)$ в оценку для среднего попадает больше более далёких точек. Это приводит к уменьшению разброса (потому что точек больше), но увеличению смещения (потому что участвуют более далёкие точки). Это означает, что ни слишком маленькие, ни слишком большие значения $k$ скорее всего не будут оптимальными. На практике $k$ находится путём подбора с помощью кросс-валидации (об этом подробнее на семинаре).

Это пример так называемого bias—variance tradeoff: модель может быть либо очень гибкой, но при этом слишком чувствительной к данным (маленькое смещение, большой разброс), либо слишком грубой, но зато устойчивой (большое смещение, маленький разброс).

---