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

3.1Элементы статистики

3.1.1Выборки

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

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

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

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

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

3.1.2Статистические оценки и их свойства

3.1.2.1Выборочное среднее

Вернёмся к примеру с монеткой. Пусть — случайная величина, равная 1 при выпадении орла и 0 при выпадении решки, — вероятность выпадения орла. Её матожидание равно . Пусть мы получили такую выборку из :
Что мы можем сказать про ?

Рассмотрим функцию от выборки, называемую выборочным средним. Это просто среднее арифметическое:

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

Соотношение (3.1) является частным случаем утверждения о состоятельности оценки. Общее определение выглядит так.

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

Таким образом, соотношение (3.1) утверждает, что является состоятельной оценкой для матожидания .

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

Помимо состоятельности нас будет интересовать ещё одно свойство: несмещённость. Напомним, что мы считаем случайными величинами. Зафиксируем и рассмотрим матожидание :

где в последней сумме одинаковых слагаемых.

Иными словами, это означает следующее. Зафиксируем некоторое и сгенерируем много-много выборок длины . Для каждой посчитаем выборочное среднее. Затем посчитаем среднее этих средних. Полученное среднее будет близко к истинному матожиданию .

Общее определение звучит так:

Определение 2. Функция от выборки называется несмещённой оценкой для параметра , если

Вопрос 1. В качестве оценки для матожидания можно использовать не только выборочное среднее. Пусть . Являетя ли состоятельной оценкой для матожидания? Несмещённой оценкой?

Вопрос 2. Рассмотрим функцию , где — некоторые константы. При каких эта функция будет несмещённой оценкой для матожидания?

3.1.2.2Выборочная дисперсия

Определение 3. Дисперсией случайной величины называется матождание квадрата её отклонения от своего матожидания:

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

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

Оказывается, что нет.

Вопрос 3. Докажите это.

Оказывается, несмещнной оценкой для дисперсии является так называемая исправленная выборочная дисперсия, отличающаяся от обычной тем, что деление происходит на , а не на :

3.1.3Дисперсия оценок

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

Найдём дисперсию . Для этого напомним свойства дисперсии: где — константа (неслучайная величина), и независимы.

Итак, имеем: То есть дисперсия оценки среднего уменьшается линейно с ростом размера выборки .

Вопрос 4. Рассмотрим функцию . При каких эта функция является несмещённой оценкой для матожидания, имеющей наименьшую дисперсию?

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

Пусть есть пара случайных величин и данные , являющиеся выборкой из . Иными словами, мы считаем, что каждая из пар распределена в соответствии с распределением и все пары независимы в совокупности. (При этом конечно не является независимым с .) Будем обозначать распределение через (распределение действительно является декартовой степенью распределения в силу независимости).

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

Алгоритм машинного обучения принимает на вход данные и возвращает функцию , которая предсказывает значение по данному набору признаков . Функция называется обученным алгоритмом. Формально:

Для оценки качества предсказаний задана некоторая функция потерь
Величина измеряет, насколько нам плохо от того, что при правильном ответе мы предсказали . Сегодня на протяжении всей лекции мы будем рассматривать квадратичную функцию потерь:
На прошлой лекции мы показали, что для квадратичной функции потерь самое лучшее предсказание — это матожидание условного распределения:
Проблема состоит в том, что на практике мы никогда не знаем истинное распределение и таким образом не можем найти матожидание (3.4). Вместо этого мы используем данные для нахождения некоторого приближения .

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

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

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

где и независимы. Последнее следует из того факта, что мы считаем независимым от . Иными словами, то, какие данные мы имеем, само по себе никак не влияет на процесс генерирования нового объекта — это выглядит вполне реалистичным предположением.

Теперь мы будем оценивать внутреннее матожидание в (3.8) для фиксированного .

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

Теорема 1. Ожидаемая квадратичная ошибка представляется следующим образом:
где , , и независимы. Первое слагаемое в сумме называется смещением (bias), оно показывает систематическую ошибку алгоритма — отклонение усредненного предсказания от идеального предсказания . Второе слагаемое называется шумом (noise), оно не зависит от алгоритма, а зависит только от истинного распределения . Шум равен ожидаемой ошибке идеального предсказывающего алгоритма. Наконец, третье слагаемое назыается разбросом (variance), оно показывает, насколько разными могут получаться предсказания если обучать алгоритм на разных обучающих выборках. Иными словами, оно показывает чувствительность алгоритма по отношению к данным.

Доказательство. Начнём с алгебраических преобразований: Выражение является просто числом, не случайной величиной, поэтому его матожидание равно ему самому и его можно выносить за знак матожидания. Поэтому (3.10) совпадает с искомым разложением. (Напомним, что по определению дисперсия .) Остаётся доказать, что оставшиеся слагаемые нулевые.

В (3.11) вынесем за матожидание и заметим, что , т.к. матожидание матожидания равно матожиданию. Таким образом, слагаемое (3.11) равно нулю. Аналогично доказывается, что слагаемое (3.13) равно нулю. В слагаемом (3.12) записана (с точностью до знака) ковариация случайных величин и . Она равна нулю при условии, что случайные велиины независимы.

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

Метод k ближайших соседей (k nearest neighbors, k-NN) — простейший метод машинного обучения. Для задачи регрессии он основан на непосредственной оценке идеального предсказания по выборке:
где — множество индексов элементов , являющихся ближайшими соседями к .

Для примера, рассмотрим распределение , заданное следующим образом: Что можно сказать о смещении и разбросе для kNN при различных ? Рассмотрим экстремальные случаи — и . При предсказание равно одному из значений и разброс предсказания примерно равен разбросу условного распределения , то есть . При , предсказание в любой точке есть среднее от всех , ( — общий размер выборки). Разброс предсказаний теперь равен (см. параграф 3.1.3).

Что происходит со смещением? При предсказание не зависит от и его матожидание равно Таким образом, смещене в точках, далёких от , будет большим.

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

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

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