4Линейная регрессия

4.1Проклятие размерности

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

Напомним базовую постановку задачи «обучения с учителем». Есть пара случайных величин $(X,Y)$, $X$ принимает значения в $X$ (чаще всего $X=R^d$, где $d$ — число признаков), $Y$ принимает значения в $Y$, где $Y$ чаще всего либо $R$ (и тогда говорят о задаче регрессии), либо конечное множество (и тогда говорят о задаче классификации). Мы сегодня будем говорить о задаче регрессии. Наша цель — установить связь между $X$ и $Y$, то есть научиться предсказывать значение $Y$ по значению $X$. Пусть также задана функция потерь $L(y,\hat{y}):Y\times Y\to R$, которая показывает цену ошибки, если при правильном ответе $y$ был предсказан $\hat{y}$. Мы сейчас будем рассматривать квадратичную функцию потерь $L(y,\hat{y})=(y-\hat{y}{)}^2$.

4.1.2Метод $k$ ближайших соседей (k-NN)

На прошлых лекциях (см. раздел 2.2) мы выяснили, что наилучшим предсказанием в случае квадратичной функции потерь является матожидание условного распределения: Поскольку на практие совместное распределение случайных величин $X$ и $Y$ неизвестно, мы оцениваем $f_{best}$ с помощью данных $D=\left\{\right(x_1,y_1),\dots ,(x_n,y_n\left)\right\}$, являющихся выборкой из $(X,Y)$. Пусть мы хотим предсказать значение $y$ для данного значения $x$. Если бы у нас было много объектов с одним и тем же $x$, в качестве предсказания $\hat{y}=f\left(x\right)$ логично было бы выбрать выборочное среднее для всех значений $y$ этих объектов:Если случайная величина $X$ является непрерывной (или по крайней мере содержит непрерывные компоненты), наличие нескольких объектов с одинаковыми значениями $x$, в точности равными данному, имеет нулевую вероятность. Поэтому вместо множества $\{i\mid x_i=x\}$ используется множество $k$ ближайших соседей к $x$. Обозначим множество индексов $\{i_m{\}}_{m=1}^k$ ближайших соседей $x_{i_1},\dots ,x_{i_k}$ к точке $x$ через $N_k\left(x\right)$ и положим:Так мы получаем оценку метода $k$ ближайших соседей.

Эта оценка имеет смысл, если предположить, что функция $f_{best}$ является непрерывной. При большом количестве данных $n$ и большом $k$, при этом малым по сравнению с $n$, ближайшие соседи к точке $x$ будут достаточно близки к ней и, в силу непрерывности, значения функции $f_{best}$ в точках $x_{i_m}\in S_k\left(x\right)$ будет достаточно близко к $f_{best}\left(x\right)$. Если $k$ велико, выборочное среднее будет достаточно близко к истинному матожиданию, а следовательно функция $f$, заданная (4.1), будет близка к $f_{best}$.

4.1.3Зачем нужно что-то ещё?

Казалось бы, что тут может пойти не так? Метод $k$ ближайших соседей выглядит универсальным и в высшей степени теоретически обоснованным — зачем нужны какие-то ещё методы?

Проблема в том, что для получения хорошей оценки в методе $k$ ближайших соседей нужно иметь много данных — мы хотим, чтобы $k$ было большим (чтобы взятие выборочного среднего уничтожило шум и позволило получить хорошую оценку для истинного матождиания), но при этом маленьким по сравнению с $n$ (чтобы $x$-координаты ближайших соседей были близки к точке $x$, для которой мы делаем предсказание — иначе от непрерывности мало толку). Эта проблема усугубляется, если $d$ оказывается большим.

Действительно, рассмотрим такой пример. Пусть $X$ распределено равномерно на множестве $[0,1{]}^d$. Допустим для простоты, что мы используем метод одного ближайшего соседа, и предполагаем, что $X$ и $Y$ связаны детерминистически, то есть $Y\mid X=x$ — это какое-то число (не случайное для заданного $x$). Для получения предсказания в точке $x$ с точности $\epsilon$ потребуется, чтобы ближайший сосед находился на расстоянии порядка $O\left(\epsilon \right)$ от $x$. Чтобы для каждой точки $x\in [0,1{]}^d$ нашёлся такой ближайший сосед, требуется, чтобы всего точек было порядка $O\left(1/{\epsilon }^d\right)$. (Разрежем каждую сторону $d$-мерного единичного куба на $O\left(1/\epsilon \right)$ кусочков, всего получим $O\left(1/{\epsilon }^d\right)$ маленьких кубиков, в каждом нужно иметь по точке.) Эта штука экспоненциально растёт по $d$ и уже при $d=10$ может стать фантастически большой даже для не слишком маленьких $\epsilon$. Этот эффект называется проклятием размерности (одним из его проявлений).

4.1.4Предположения о характере истинной зависимости

Что же делать? Если не требовать от $f_{best}$ ничего сверх непрерывности, у нас мало шансов сделать что-то лучше. К счастью, часто мы можем предположить, что $f_{best}$ обладает какими-то дополнительными хорошими свойствами, и в этом предположении справиться с проклятием размерности.

Непрерывность выглядит самым слабым из разумных предположений о виде истинной зависимости между $X$ и $Y$. Самым сильным предположением является утверждение о независимости $X$ и $Y$ — в этом случае, в частности, $f_{best}$ является константой и наш алгоритм должен выдавать предсказание, вообще не глядя на $x$. Это предположение кажется черезчур сильным, оно делает задачу бессмысленной. Чуть менее сильным и при этом достаточно разумным предположением является линейность фукции $f_{best}$. Накладывая это ограничение на $f_{best}$ мы попадаем в мир линейных моделей, которому будут посвящены эта и следующие несколько лекций.

4.2Задача линейной регрессии

4.2.1Общая постановка задачи

Пусть теперь $x_1,\dots ,x_n\in R^d$ зафиксированы, а $y_1,\dots ,y_n$ являются случайными величинами. Мы предполагаем, что истинная связь между $y_i$ и $x_i$ является линейной, плюс некоторая случайная ошибка. А именно, существует такой вектор $w\in R^d$ (вектор весов), чтогде $⟨x_i,w⟩$ — стандартное скалярное произведение ($x_{i1}{w}_1+\dots +x_{id}{w}_d$), а все ${\epsilon }_i$ независимы в совокупности, имеют нулевое матожидание $E\left[{\epsilon }_i\right]=0$ для всех $i=1,\dots ,n$ и одинаковую конечную дисперсию $D\left[{\epsilon }_i\right]={\sigma }^2<\infty$.

В этом случае процесс обучения линейной модели состоит в нахождении вектора $\hat{w}$ по имеющимся данным. Как это сделать?

Если бы модель была на 100% верна и ошибки отсутствовали (${\epsilon }_i=0$ для всех $i=1,\dots ,d$), то уравнение (4.2) было бы линейным уравнением на $w$, из которого можно было бы найти последний. В реальности же приходится использовать другие методы — в частности, метод максимального правдоподобия.

4.2.2Оценка параметров распределения с помощью максимизации правдоподобия

Сделаем небольшое отступление и рассмотрим более простую задачу. Пусть у нас есть $z_1,\dots ,z_n$ — выборка из нормального распредления $N(\mu ,{\sigma }^2)$ с неизвестными параметрами $\mu$ и ${\sigma }^2$. Рассмотрим функцию правдоподобия (likelihood): $$\begin{array}{}p(z_1,\dots ,z_n\mid \mu ,\sigma )=\prod _{i=1}^{n}p(z_i\mid \mu ,\sigma )=& =\prod _{i=1}^n\frac{1}{\sqrt{2\pi {\sigma }^2}}\exp \left[-\frac{(z_i-\mu {)}^2}{2{\sigma }^2}\right].& \text{(4.3)}& \text{(4.4)}\end{array}$$ Она показывает, какова плотность вероятности получить тот набор данных, который мы получили, то есть насколько правдоподобно было получить эти данные из распределения с указанными параметрами. Переход к произведению в первой строчке связан с тем, что мы предполагаем $y_i$ независимыми. Для фиксированных данных $z_1,\dots ,z_n$, правдоподобие — это функция от $\mu$ и $\sigma$. Оценка наибольшего правдоподоия (maximum likelihood estimate, MLE) — это такое значение параметров распределения, при которых правдоподобие максимально.

Найдём MLE-оценку для нашего примера. Обычно вместо того, чтобы максимизировать само правдоподобие, максимизируют его логарифм (log-likelihood).

В данном случае оптимизационная задача особенно проста: MLE-оценка для $\mu$ не зависит от выбора $\sigma$. Найдём её. Достаточно минимизировать выражениеЭто функция одной переменной ($\mu$). Находя производную и приравнивая её к нулю, мгновенно получаем:Таким образом, MLE-оценка для матожидания нормального распределения является выборочным средним.

4.2.3Линейная регрессия с гауссовыми ошибками

Чтобы воспользоваться методом максимизации правдоподобия для линейной регрессии необходимо уточнить постановку задачи (4.2). А именно, предположим, что все ${\epsilon }_i$ распределены в соответствии с нормальным законом (и как обычно независимы):Найдём правдоподобие $y_1,\dots ,y_n$. (Мы по-прежнему считаем набор $x_1,\dots ,x_n$ фиксированным.) Поскольку ${\epsilon }_i=y_i-⟨x_i,w⟩$, имеем: $$\begin{array}{}p(y_1,\dots ,y_n\mid w,\sigma )& =\prod _{i=1}^n\frac{1}{\sqrt{2\pi {\sigma }^2}}\exp \left[-\frac{(y_i-⟨x_i,w⟩{)}^2}{2{\sigma }^2}\right];& \ln p(y_1,\dots ,y_n\mid w,\sigma )& =-n\ln \sqrt{2\pi {\sigma }^2}-\frac{1}{2{\sigma }^2}\sum _{i=1}^n(y_i-⟨x_i,w⟩{)}^2.& \text{(4.5)}& \text{(4.6)}\end{array}$$ Из последнего соотношения видно, что для максимизации логарифма правдоподобия необходимо минимизировать величинуназываемую суммой квадратов остатков (residual sum of squares). Данный метод называется методом наименьших квадратов, а оптимальное значение $\hat{w}$ называют МНК-оценкой для истинных весов $w$.

Заметим, что задачу минимизации $RSS$, которую мы получили методом наибольшего правдоподобия, предположив нормальность остатков, можно интерпретировать иначе. В самом начале лекции мы говорили о том, что в задаче машинного обучения обычно задана некоторая функция потерь $L(y,\hat{y})$.

Если функция потерь является квадратичной, то эмпирическим риском и оказывается $RSS$. Таким образом, метод наименьших квадратов оказывается частным случаем метода минимизации эмпирического риска, выходящего далеко за рамки линейных моделей.

Такая интерпретация, лишенная связи с теории вероятностей, даёт большую свободу. Теперь мы можем выбирать любую функцию потерь и находить оценку для $w$, полученную минимизацией эмпирического риска, создавая таким образом разнообразные алгоритмы машинного обучения, обладающие разными свойствами (связанными со свойствами функции потерь). Об этом мы поговорим позже.

4.3Явный вид МНК-оценки

4.3.1МНК в матричной форме

Запишем обучающую выборку в матричном виде. Пусть $X$ — матрица объект-признак, по строкам которой записаны векторы $x_i$.

Нам приходится внести небольшую путаницу — раньше буквой $X$ обозначалась случайная величина, а теперь (и до конца этой лекции) — фиксированная матрица.

Вектор $y=(y_1,\dots ,y_n)\in R^n$ — вектор правильных ответов. Теперь $RSS\left(w\right)$ можно представить в виде:

где $\parallel \cdot \parallel$ — стандартная евклидова норма в пространстве $R^n$, векторы $y$ и $w$ являются вектор-столбцами. Действительно, каждая компонента вектора $Xw$ — это скалярное произведение $⟨x_i,w⟩$, вектор $Xw-y$ состоит из остатков, квадрат его нормы — сумма квадратов остатков.

Для фиксированных $X$ и $y$, функция $RSS$ является отображением из $R^d$ в $R$. У него есть градиент и необходимым условием экстремума является равенство этого градиента нулю.

4.3.2Немного о градиентах

Чтобы найти градиент нам необходимо напомнить определения и доказать несколько вспомогательных утверждений.

Градиент также часто обозначается $\frac{\partial \phi }{\partial x}$ для векторного аргумента $x$.

4.3.3Вывод МНК-оценки

Теперь всё готово к тому, чтобы найти градиент $RSS$. Запишем (4.7) в следующем виде:Последнее слагаемое не зависит от $w$, его градиент равен нулю. Разберёмся с двумя другими:Здесь мы воспользовались предложением 1, предложением 3 и тем фактом, что $X^{T}X$ — симметричная матрица и при транспонировании не меняется.Здесь мы воспользовались предложением 1 и предложением 2.

Таким образом:

Предположим, что $X^{T}X$ является невырожденной матрицей. (Она состоит из скалярных произведений столбцов матрицы $X$, её невыожденность эквивалентна тому, что все столбцы $X$ линейно независимы.) Тогда оптимальное значение $\hat{w}$ находится из условия равенства градиента нулю по формуле:Её можно обвести в рамочку — она того стоит.

---