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

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

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

Напомним базовую постановку задачи «обучения с учителем». Есть пара случайных величин , принимает значения в (чаще всего , где — число признаков), принимает значения в , где чаще всего либо (и тогда говорят о задаче регрессии), либо конечное множество (и тогда говорят о задаче классификации). Мы сегодня будем говорить о задаче регрессии. Наша цель — установить связь между и , то есть научиться предсказывать значение по значению . Пусть также задана функция потерь , которая показывает цену ошибки, если при правильном ответе был предсказан . Мы сейчас будем рассматривать квадратичную функцию потерь .

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

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

Эта оценка имеет смысл, если предположить, что функция является непрерывной. При большом количестве данных и большом , при этом малым по сравнению с , ближайшие соседи к точке будут достаточно близки к ней и, в силу непрерывности, значения функции в точках будет достаточно близко к . Если велико, выборочное среднее будет достаточно близко к истинному матожиданию, а следовательно функция , заданная (4.1), будет близка к .

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

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

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

Действительно, рассмотрим такой пример. Пусть распределено равномерно на множестве . Допустим для простоты, что мы используем метод одного ближайшего соседа, и предполагаем, что и связаны детерминистически, то есть — это какое-то число (не случайное для заданного ). Для получения предсказания в точке с точности потребуется, чтобы ближайший сосед находился на расстоянии порядка от . Чтобы для каждой точки нашёлся такой ближайший сосед, требуется, чтобы всего точек было порядка . (Разрежем каждую сторону -мерного единичного куба на кусочков, всего получим маленьких кубиков, в каждом нужно иметь по точке.) Эта штука экспоненциально растёт по и уже при может стать фантастически большой даже для не слишком маленьких . Этот эффект называется проклятием размерности (одним из его проявлений).

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

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

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

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

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

Пусть теперь зафиксированы, а являются случайными величинами. Мы предполагаем, что истинная связь между и является линейной, плюс некоторая случайная ошибка. А именно, существует такой вектор (вектор весов), что
где — стандартное скалярное произведение (), а все независимы в совокупности, имеют нулевое матожидание для всех и одинаковую конечную дисперсию .

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

Если бы модель была на 100% верна и ошибки отсутствовали ( для всех ), то уравнение (4.2) было бы линейным уравнением на , из которого можно было бы найти последний. В реальности же приходится использовать другие методы — в частности, метод максимального правдоподобия.

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

Сделаем небольшое отступление и рассмотрим более простую задачу. Пусть у нас есть — выборка из нормального распредления с неизвестными параметрами и . Рассмотрим функцию правдоподобия (likelihood): Она показывает, какова плотность вероятности получить тот набор данных, который мы получили, то есть насколько правдоподобно было получить эти данные из распределения с указанными параметрами. Переход к произведению в первой строчке связан с тем, что мы предполагаем независимыми. Для фиксированных данных , правдоподобие — это функция от и .
import matplotlib.pyplot as plt
import numpy as np
import qqmbr.odebook as ob
# see https://github.com/ischurov/qqmbr/blob/master/qqmbr/odebook.py

from scipy.stats import norm
np.random.seed(42)
x = np.random.normal(1, 5, 20)
plt.plot(x, np.zeros_like(x), 'o')
X = np.linspace(-10, 10, 200)
plt.plot(X, norm(loc=-5, scale=5).pdf(X))
plt.plot(X, norm(loc=1, scale=2).pdf(X))
plt.plot(X, norm(1, 5).pdf(X))
Рис. 4.1: Выборка, отмеченная синими точками, получена из одного из нормальных распределений, чьи плотности нарисованы. Из какого?
Оценка наибольшего правдоподоия (maximum likelihood estimate, MLE) — это такое значение параметров распределения, при которых правдоподобие максимально.

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

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

Вопрос 1. Найдите теперь MLE-оценку для дисперсии .

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

Чтобы воспользоваться методом максимизации правдоподобия для линейной регрессии необходимо уточнить постановку задачи (4.2). А именно, предположим, что все распределены в соответствии с нормальным законом (и как обычно независимы):
Найдём правдоподобие . (Мы по-прежнему считаем набор фиксированным.) Поскольку , имеем: Из последнего соотношения видно, что для максимизации логарифма правдоподобия необходимо минимизировать величину
называемую суммой квадратов остатков (residual sum of squares). Данный метод называется методом наименьших квадратов, а оптимальное значение называют МНК-оценкой для истинных весов .

Заметим, что задачу минимизации , которую мы получили методом наибольшего правдоподобия, предположив нормальность остатков, можно интерпретировать иначе. В самом начале лекции мы говорили о том, что в задаче машинного обучения обычно задана некоторая функция потерь .

Определение 1. Сумма значений функции потерь на всех объектах обучающей выборки называется эмпирическим риском.

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

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

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

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

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

Вопрос 2. Сколько строк и столбцов в матрице ?
  строк и столбцов, конечно!

Верно, строк столько, сколько объектов

  строк и столбцов, разумеется!

А вот и нет!

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

Вектор — вектор правильных ответов. Теперь можно представить в виде:

где — стандартная евклидова норма в пространстве , векторы и являются вектор-столбцами. Действительно, каждая компонента вектора — это скалярное произведение , вектор состоит из остатков, квадрат его нормы — сумма квадратов остатков.

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

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

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

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

Градиент также часто обозначается для векторного аргумента .

Утверждение 1. Пусть — матрица с строками и столбцами, и . Тогда
где — транспонированная матрица .

Доказательство. Будем использовать матричную форму записи стандартного скалярного произведения:
где и — некоторые векторы одинаковой размерности, записанные как вектор-столбцы. Имеем:
скалярное произведение является числом, поэтому оно не изменится в результате транспонирования:

Утверждение 2. Для фиксирвоанного вектора ,

Доказательство. Это утверждение, как и следующее, можно мгновенно доказать в координатах, но можно действовать по-высоконаучному:
Очевидно, производная — это , а градиент (в соответствии с определением) — вектор .

Утверждение 3. Для фиксированной матрицы ,

Доказательство. Будем действовать по-высоконаучному:
Последнее слагаемое есть , а производная — это функция . Остаётся записать производную в виде скалярного произведения на фиксированный вектор — он и будет вектором градиента. Первое слагаемое уже записано в этом виде. Разберёмся со вторым слагаемым:
по предложению 1. Таким образом, производная принимает вид:
откуда и следует, что градиент равен .

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

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

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

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

Вопрос 3. Почему нельзя написать так:
  Узнать ответ

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

Вопрос 4. Мы нашли ноль градиента. Почему это действительно минимум?