5Ещё о линейной регрессии

5.1Напоминание: постановка задачи и метод наименьших квадратов

Наша модель выглядит следующим образом. Есть набор

x_{1}, \dots, x_{n} \in R^{d}

. Мы их считаем фиксированными (неслучайными). Также есть некоторый фиксированный вектор весов

w \in R^{d}

. Значения

y_{i}

определяются следующим образом:

\begin{matrix} y_{i} = ⟨ w, x_{i} ⟩ + ε_{i}, \\ (5.1) \end{matrix}

где

ε_{i}

— случайные величины со следующими свойствами:

$E [ε_{i}] = 0$ ;
$D [ε_{i}] = σ^{2} < \infty$ ;
$c o v (ε_{i}, ε_{j}) = 0$ для $i \neq j$ .

Напомним, что ковариацией случайных величин

ξ

η

называется число

c o v (ξ, η) = E [(ξ - E [ξ]) (η - E [η])] .

Если случайные величины независимы, их ковариация равна нулю.

Обозначим через $X$ матрицу, в которой по строкам записаны векторы $x_{i}$ . Это матрица с $n$ строками и $d$ столбцами. Пусть $y = (y_{1}, \dots, y_{n})$ — вектор правильных ответов и $ε = (ε_{1}, \dots, ε_{n})$ — вектор ошибок. Уравнение (5.1) можно записать в матричной форме:

y = X w + ε

МНК-оценкой для

w

называется вектор

^w \in R^{d}

, который является решением оптимизационной задачи

\begin{matrix} ∥ X^w - y ∥^{2} \to min^w . \\ (5.2) \end{matrix}

Если столбцы матрицы

X

линейно независимы, то решение этой задачи является единственным и его можно найти с помощью формулы

\begin{matrix} ^w = (X^{T} X)^{- 1} X^{T} y . \\ (5.3) \end{matrix}

Замечание 1. В предыдущей лекции мы нашли МНК-оценку как оценку наибольшего правдоподобия в предположении, что остатки

ε_{i}

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

5.1.1Геометрическая интерпретация

Рассмотрим пространство

R^{n}

. Обозначим столбцы матрицы

X

через

x^{(1)}, \dots, x^{(d)}

, они являются элементами

R^{n}

. Рассмотрим множество

L = {X w ∣ w \in R^{d}}

. Оно задаёт

d

-мерное линейное подпространство в пространстве

R^{n}

, натянутое на столбцы матрицы

X

. Оптимизационная задача (5.2) состоит в нахождении точки

^y = X^w

, ближайшей к точке

y

. Чтобы найти такую точку, достаточно спроектировать

y

на

L

ортогонально. Чтобы найти

^w

, нужно разложить

^y

по базису в

L

, составленному из столбцов матрицы

X

Эта интерпретация часто бывает полезна, но про некоторые вещи с её помощью невозможно думать: например, невозможно себе представить, что значит «найти предсказание для нового $x$ (отличного от тех, что есть в обучающей выборке)».

5.2Несмещённость МНК-оценки

Утверждение 1. МНК-оценка является несмещённой, то есть

E [^w] = w .

Доказательство. Для доказательства нам потребуются две вспомогательные леммы (очень простые).

Лемма 1. Матожидание коммутирует со скалярным произведением на фиксированный вектор, то есть для любого случайного вектора

z \in R^{k}

и постоянного вектора

u \in R^{k}

E [⟨ u, z ⟩] = ⟨ u, E [z] ⟩

Доказательство леммы. Это переформулировка линейности матожидания. Пусть

u = (u_{1}, \dots, u_{k})

z = (z_{1}, \dots, z_{k})

. Тогда

E [⟨ u, z ⟩] = E [u_{1} z_{1} + \dots + u_{k} z_{k}] = u_{1} E [z_{1}] + \dots + u_{k} E [z_{k}] = ⟨ u, E [z] ⟩ .

∎

Лемма 2. Матожидание коммутирует с умножением на фиксированную матрицу, то есть для любого случайного вектора

z \in R^{k}

и постоянной матрицы

A

k

столбцами справедливо:

E [A z] = A E [z]

Доказательство леммы. Каждая компонента вектора

A z

является скалярным произведением строки матрицы

A

на вектор

z

. Дальше применяем лемму 1 покомпонентно и получаем требуемое.∎

Вернёмся к доказательству утверждения. Имеем: $\begin{matrix} E [^w] = & E [(X^{T} X)^{- 1} X^{T} y] = E [(X^{T} X)^{- 1} X^{T} (X w + ε)] = = & E [(X^{T} X)^{- 1} (X^{T} X) w] + E [(X^{T} X)^{- 1} X^{T} ε] = = & E [w] + (X^{T} X)^{- 1} X^{T} E [ε] = E [w] . \end{matrix}$ В предпоследнем переходе мы воспользовались леммой 2, в последнем — предположением о том, что матожидание $ε$ равно нулю.∎

5.3Дисперсии и ковариации МНК-оценки

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

x

есть скалярное произведение

⟨ x,^w ⟩

.) Что с разбросом, то есть дисперсией предсказаний?

5.3.1Ковариационная матрица

Чтобы сказать что-то про разброс предсказаний необходимо сначала разобраться с разбросом вектора весов

^w

. У числовой случайной величины есть дисперсия. Разброс векторной случайной величины характеризует более сложный объект — ковариационная матрица.

Определение 1. Ковариационной матрицей векторной случайной величины

z

, принимающей значения в

R^{k}

, называется матрица, имеющая вид:

V a r (z) = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ \begin{matrix} c o v (z_{1}, z_{1}) & c o v (z_{1}, z_{2}) & \dots & c o v (z_{1}, z_{k}) c o v (z_{2}, z_{1}) & c o v (z_{2}, z_{2}) & \dots & c o v (z_{2}, z_{k}) ⋮ & ⋮ & ⋱ & ⋮ c o v (z_{k}, z_{1}) & c o v (z_{k}, z_{2}) & \dots & c o v (z_{k}, z_{k}) \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ .

Эта матрица является симметричной. Поскольку ковариация случайной величины с самой собой является её дисперсией, на диагонали ковариационной матрицы стоят как раз дисперсии компонент

z

Гм-гм, симметричная матрица? Наверняка она задаёт какую-нибудь симметричную билинейную или квадратичную форму! И правда.

Утверждение 2. Ковариационная матрица задаёт билинейную форму. Для любых фиксированных векторов

u, v \in R^{k}

⟨ V a r (z) u, v ⟩ = u^{T} V a r (z) v = E [⟨ u, z - E [z] ⟩ ⟨ v, z - E [z] ⟩] .

Доказательство. В силу линейности, достаточно проверить это утверждение, выбирая в качестве

u

v

базисные векторы. Для таких векторов оно проверяется методом пристального вглядывания в формулы.∎

Следствие 1. Ковариационная матрица задаёт квадратичную форму, значение которой на векторе

u

равно дисперсии скалярного произведения

⟨ u, z ⟩

⟨ V a r (z) u, u ⟩ = u^{T} V a r (z) u = D [⟨ u, z ⟩] .

5.3.2Пример и геометрическая интерпретация

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

Рис. 5.1: Две выборки из двумерного нормального распределения с различными матрицами ковариации

Для левой картинки ковариационная матрица является единичной:

(\begin{matrix} 1 & 0 0 & 1 \end{matrix}) .

Поскольку на внедиагональном элементе матрицы стоит 0, компоненты вектора оказываются нескоррелированными, что мы и видим по картинке: увеличение горизнтальной компоненты не приводит к систематическому увеличению или уменьшению вертикальной, линейная зависимость отсутствует.

Для правой картинки матрица ковариации равна

(\begin{matrix} 1 & 0, 8 0, 8 & 1 \end{matrix}) .

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

0, 8

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

Следствие 1 имеет следующую геометрическую интерпретацию. Зафиксируем какой-нибудь вектор $u$ , имеющий единичную длину. Тогда $u^{T} V a r (z) u$ показывает, какова дисперсия скалярного произведения $⟨ u, z ⟩$ . Для единичного вектора $u$ указанное скалярное произведение — это длина проекции $z$ на $u$ . То есть мы измеряем разброс проекции случайного вектора на заданное направление. Например, на правой картинке колебания вдоль направления вектора $(\sqrt{2} / 2, \sqrt{2} / 2)$ будет гораздо больше, чем вдоль направления вектора $(- \sqrt{2} / 2, \sqrt{2} / 2)$ . На левой картинке колебания в любом направлении одинаковы.

5.3.3Ковариационная матрица и линейные операторы

Утверждение 3. Для случайного вектора

z

со значениями в

R^{k}

и фиксированной матрицы

A

k

столбцами справедливо следующее:

V a r (A z) = A V a r (z) A^{T} .

Доказательство. Возьмём произвольный фиксированный вектор

u \in R^{k}

. Имеем:

u^{T} V a r (A z) u = D [⟨ u, A z ⟩] = D [⟨ z, A^{T} u ⟩] = (A^{T} u)^{T} V a r (z) A^{T} u = u^{T} (A V a r (z) A^{T}) u .

Поскольку равенство выполняется для любого вектора

u

, матрицы между

u^{T}

u

в левой и правой части цепочки равенств обязаны совпадать.∎

5.3.4Ковариационная матрица МНК-оценки

Теперь всё готово к тому, чтобы найти ковариационную матрицу для оценки вектора весов

^w

. Подставим в формулу (5.3) модель (5.1) и посчитаем ковариационную матрицу:

V a r (^w) = V a r ((X^{T} X)^{- 1} X^{T} (X w + ε)) = V a r (w + (X^{T} X)^{- 1} X^{T} ε) = \dots

Сдвиг на постоянный вектор

w

не влияет на ковариации (из каждой компоненты всё равно вычитается её матожидание).

\dots = V a r ((X^{T} X)^{- 1} X^{T} ε) = (X^{T} X)^{- 1} X^{T} V a r (ε) ((X^{T} X)^{- 1} X^{T})^{T} = \dots

Здесь мы воспользовались утверждением 3. Ковариационная матрица

ε

является скалярной (по предположениям модели — все дисперсии равны одному и тому же числу, все ковариации равны нулю) и равна

σ^{2} I

\dots = σ^{2} (X^{T} X)^{- 1} X^{T} X (X^{T} X)^{- 1} = σ^{2} (X^{T} X)^{- 1} .

Ура! Итак,

\begin{matrix} V a r (^w) = σ^{2} (X^{T} X)^{- 1} . \\ (5.4) \end{matrix}

Таким образом, зная матрицу

X

мы можем явно найти ковариационную матрицу для

^w

(по крайней мере, если верим в предположения нашей модели).

5.3.5Теорема Гаусса — Маркова

Хороша ли МНК-оценка? Теорема Гаусса — Маркова говорит: ой как хороша! По крайней мере, если сравнивать её с другими несмещенными линейными оценками.

Теорема 1. (Гаусса — Маркова) Пусть выполняются условия модели (5.1), матрица

X

имеет независимые столбцы и пусть

¯ w

— какая-то несмещённая линейная оценка для

w

, то есть

¯ w

записывается в виде

¯ w = C y,

где

C

— некоторая фиксированная матрица и

E [¯ w] = w .

Рассмотрим произвольный фиксированный вектор

x \in R^{d}

. Тогда

D [⟨ x, ¯ w ⟩] \geq D [⟨ x,^w ⟩],

где

^w

, как и прежде, МНК-оценка для

w

Иными словами, теорема Гаусса — Маркова говорит, что дисперсия (разброс) любого предсказания для любой линейной несмещённой оценки $w$ будет не меньше, чем дисперсия того же предсказания для МНК-оценки.

Заключение теоремы можно также переформулировать таким образом: матрица

V a r (¯ w) - V a r (^w)

всегда неотрицательно определена.

Доказывать эту теорему мы сейчас не будем.

5.3.6Когда смещённая оценка лучше

Казалось бы, мы победили: нашли несмещённую оценку, которая даёт предсказания с минимальной дисперсией. Чего ещё можно хотеть?

Теорема Гаусса — Маркова рассматривает только довольно узкий класс альтернатив — исключительно линейные несмещённые оценки, и показывает, что МНК-оценка оптимальна именно в этом классе. Но это не означает, что она оптимальна с практической точки зрения.

Напомним (второй раз за сегодня), что ожидаемая ошибка на новом наблюдении (то, что мы хотим сделать как можно менше) складывается из шума, смещения и разброса. Мы показали, что МНК-оценка имеет нулевое смещение и минимальный разброс среди оценок с нулевым смещением. Однако, может быть, есть оценка с ненулевым смещением, которая имеет существенно более низкий разброс, и таким образом по сумме выигрывает у МНК-оценки? Оказывается, что так как раз часто и бывает (более того, почти всегда).

Давайте покажем, как это возможно, на простом примере.

Пример 1. Пусть матрица

X

задана следующим образом:

X = ⎛ ⎜ ⎜ ⎜ ⎝ \begin{matrix} 10 & 0 - 10 & 0 0 & 1 0 & - 1 \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎠ .

Иными словами, у нас есть всего четыре наблюдения: в точках

(10, 0)

(- 10, 0)

(0, 1)

(0, - 1)

Пусть также истинный вектор весов $w = (1, 1)$ , то есть истинная зависимость имеет вид:

y_{i} = x_{i}^{(1)} + x_{i}^{(2)} + ε_{i}

Ковариационная матрица МНК-оценки имеет вид:

V a r (^w) = σ^{2} (X^{T} X)^{- 1} = ⎛ ⎜ ⎝ \begin{matrix} \frac{σ^{2}}{200} & 0 0 & \frac{σ^{2}}{2} \end{matrix} ⎞ ⎟ ⎠ .

Предсказания в точках

(10, 0)

(- 10, 0)

равны

⟨ (\pm 10, 0), w ⟩ = \pm 10 w_{1} .

Их разброс равен

D [\pm 10 w_{1}] = 10^{2} D [w_{1}] = 10^{2} \frac{σ^{2}}{200} = \frac{σ^{2}}{2} .

Аналогично разброс предсказаний в точках

(\pm 1, 0)

также равен

\frac{σ^{2}}{2}

Как мы видим, если $σ^{2}$ очень большое, разброс предсказаний МНК-модели может быть также очень большим.

Давайте вместе с МНК-оценкой для исходной модели рассмотрим также МНК-оцеки для упрощённых моделей, которые игнорируют один из или оба признака. Иными словами, мы рассматриваем четыре модели.

Наша исходная модель.
Модель построена по матрице $X$ , из которой убрали первый столбец и оставили только второй, зависимость предсказания от первого признака в модели отсутствует. Иными словами, в формуле
$^y = {^w}_{1} x^{(1)} + {^w}_{2} x^{(2)}$
принудительно положили, что ${^w}_{1} = 0$ .
Модель построена по матрице $X$ , из которой убрали второй столбец и оставили только первый. Иными словами, принудительно положили ${^w}_{2} = 0$ .
Модель вообще игнорирует матрицу $X$ и во всех точках $x$ делает предсказание $^y = 0$ . Иными словами, ${^w}_{1} = {^w}_{2} = 0$ .

Нетрудно показать, что для нашей матрицы

X

необнулённые веса в моделях 2 и 3 совпадают с соответствующими весами исходной модели.

Давайте посчитаем ожидаемую ошибку для всех четырёх моделей. Для этого нужно найти смещение и разброс для каждой модели.

У исходной (первой) модели нулевой смещение предсказаний, а разброс в каждой из четырёх точек равен $\frac{σ^{2}}{2}$ . Общий разброс равен $2 σ^{2}$ .

У второй модели в точках $(0, \pm 1)$ смещение остаётся нулевым, а в точках $(\pm 10, 0)$ модель предсказывает значение $0$ (поскольку мы обнулили ${^w}_{1}$ ), в то время как правильное значение равно $\pm 10$ . Значит, смещение (вернее, его квадрат, именно он входит в формулу для ожидаемой ошибки) в каждой из этих точек равно $(0 \mp 10)^{2} = 100$ , общее смещение модели $200$ . Разброс в точках $(0, \pm 1)$ остаётся равен $\frac{σ^{2}}{2}$ , а в точках $(\pm 10, 0)$ разброс равен нулю, поскольку в этих точках модель предсказывает постоянное число (0). Общий разброс равен $σ^{2}$ .

У третьей модели всё наоборот — в точках $(0, \pm 1)$ смещение равно по 1 (там истинное значение равно 1, а предсказание будет 0), общее смещение равно 2. Общий разброс, как и второй модели, оказывается равен $σ^{2}$ .

Наконец, у четвертой модели смещение равно $202$ , а разброс нулевой.

Сведём наши результаты в табличку.

\begin{matrix} m o d e l & b i a s & v a r i a n c e 1 & 0 & 4 σ^{2} 2 & 200 & 2 σ^{2} 3 & 2 & 2 σ^{2} 4 & 202 & 0 \end{matrix}

Если

σ^{2}

, то есть шум в наших данных, маленький (например, равен 0), то самой лучшей моделью будет первая. Однако, если

σ^{2} > 1

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

σ^{2}

, в какой-то момент будет выгоднее вообще перейти на четвертую модель, которая верит в то, что

y

всегда равен нулю. (При каком

σ^{2}

это наступит?)

Итак, на нашем примере мы видим, что бывают ситуации, когда лучше выбрать смещённую модель, которая даёт меньший разброс предсказаний, чем несмещённую модель. Это ещё один пример так называемого bias-variance tradeoff.

Заметим, что в данном случае оптимальной могла стать третья модель, но никак не вторая: её ожидаемая ошибка при любом $σ^{2}$ больше ожидаемой ошибки третьей. Это можно интерпретировать так. В нашей истинной зависимости коэффициенты при обоих признаках были равны между собой. В то же время дисперсии самих признаков существенно различались — дисперсия первого признака была гораздо больше дисперсии второго. При равных дисперсиях шумов в каждой точке, это привело к тому, что дисперсия второй компоненты вектора признаков оказалась гораздо выше дисперсии первой. Поэтому именно ей нам пришлось «пожертвовать», чтобы уменьшить разброс предсказаний. На этой идее основан один из методов отбора признаков — удаление незначимых признаков, то есть таких, у которых слишком большое значение разброса по сравнению со значением самого признака.

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

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

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

← Предыдущая глава

Машинное обучение для факультета математики Записки лекций