Скользящий контроль

Материал из MachineLearning.

(Различия между версиями)

Версия 22:23, 10 апреля 2008

Скользящий контроль или кросс-проверка или кросс-валидация (cross-validation, CV) — процедура эмпирического оценивания обобщающей способности алгоритмов, обучаемых по прецедентам.

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

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

Скользящий контроль является стандартной методикой тестирования и сравнения алгоритмов классификации, регрессии и прогнозирования.

Содержание

1 Определения и обозначения
- 1.1 Процедура скользящего контроля
- 1.2 Доверительное оценивание
2 Разновидности скользящего контроля
3 Скользящий контроль в задачах прогнозирования
4 Недостатки скользящего контроля
5 Применения скользящего контроля
6 Теоретические оценки
7 Ссылки
8 Литература

Определения и обозначения

Рассматривается задача обучения с учителем.

Пусть $X$ — множество описаний объектов, $Y$ — множество допустимых ответов.

Задана конечная выборка прецедентов $X^L = (x_i,y_i)_{i=1}^L \subset X\times Y$ .

Задан алгоритм обучения — отображение $\mu$ , которое произвольной конечной выборке $X^m$ ставит в соответствие функцию (алгоритм) $a:\:X\to Y$ , аппроксимирующую неизвестную целевую зависимость.

Задан функционал $Q(a,X^m)$ , оценивающий качество алгоритма $a$ по конечной выборке прецедентов $X^m$ .

Процедура скользящего контроля

Выборка $X^L$ разбивается $N$ различными способами на две непересекающиеся подвыборки: $X^L = X^m_n \cup X^k_n$ , где $X^m_n$ — обучающая подвыборка длины m, $X^k_n$ — контрольная подвыборка длины $k=L-m$ , $n=1,\ldots,N$ — номер разбиения.

Для каждого разбиения n строится алгоритм $a_n = \mu(X^m_n)$ и вычисляется значение функционала качества $Q_n = Q (a_n, X^k_n)$ . Среднее арифметическое значений $Q_n$ по всем разбиениям называется оценкой скользящего контроля:

$CV(\mu,X^L)=\frac1N \sum_{n=1}^N Q (\mu(X^m_n), X^k_n).$

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

Доверительное оценивание

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

Непараметрическая оценка доверительного интервала. Строится вариационный ряд значений $Q_n = Q (a_n, X^k_n)$ , $n=1,\ldots,N$ :

$Q^{(1)} \leq Q^{(2)} \leq \cdots \leq Q^{(N)}.$

Утверждение 1. Если разбиения осуществлялись случайно, независимо и равновероятно, то с вероятностью $\eta= \frac{t}{N+1}$ значение случайной величины $Q(a(X^m),X^k)$ не превосходит $Q^{(N-t+1)}$ .

Следствие 1. Значение случайной величины $Q(a(X^m),X^k)$ не превосходит $Q^{(N)}$ с вероятностью $\eta= \frac{1}{N+1}$ .

В частности, для получения верхней оценки с надёжностью 95% достаточно взять $N=20$ разбиений.

Утверждение 2. Если разбиения осуществлялись случайно, независимо и равновероятно, то с вероятностью $\eta= \frac{2t}{N+1}$ значение случайной величины $Q(a(X^m),X^k)$ не выходит за границы доверительного интервала $\bigl[ Q^{(t)},Q^{(N-t+1)} \bigr]$ .

Следствие 2. Значение случайной величины $Q(a(X^m),X^k)$ не выходит за границы вариационного ряда $\bigl[ Q^{(1)},Q^{(N)} \bigr]$ с вероятностью $\eta= \frac{2}{N+1}$ .

В частности, для получения двусторонней оценки с надёжностью 95% достаточно взять $N=40$ разбиений.

Параметрические оценки доверительного интервала основаны на априорном предположении о виде распределения случайной величины $Q(a(X^m),X^k)$ . Если априорные предположения не выполняются, доверительный интервал может оказаться сильно смещённым. В частности, если предположения о нормальности распределения не выполнены, то нельзя пользоваться стандартным «правилом двух сигм» или «трёх сигм». Джон Лангфорд в своей диссертации (2002) указывает на распространённую ошибку, когда правило двух сигм применяется к функционалу частоты ошибок, имеющему на самом деле биномиальное распределение. Однако биномиальным распределением в общем случае тоже пользоваться нельзя, поскольку в результате обучения по случайным подвыборкам $X^m$ вероятность ошибки алгоритма $a(X^m)$ оказывается случайной величиной. Следовательно, случайная величина $Q(a(X^m),X^k)$ описывается не биномиальным распределеним, а (неизвестной) смесью биномиальных распределений. Аппроксимация смеси биномиальным распределением может приводить к ошибочному сужению доверительного интервала.

Разновидности скользящего контроля

Возможны различные варианты скользящего контроля, отличающиеся способами разбиения выборки.

Полный скользящий контроль (complete CV)

Оценка скользящего контроля строится по всем $N=C_L^k$ разбиениям. Это число становится слишком большим уже при $k>2$ , поэтому полный скользящий контроль используется либо в теоретических исследованиях, либо в тех редких случаях, когда для него удаётся вывести эффективную вычислительную формулу. Например, такая формула известна для метода k ближайших соседей, что позволяет эффективно выбирать параметр k. На практике чаще применяются другие разновидности скользящего контроля.

Случайные разбиения

Разбиения $n=1,\ldots,N$ выбираются случайно, независимо и равновероятно из множества всех $C_L^k$ разбиений. Именно для этого случая справедливы приведённые выше оценки доверительных интервалов. На практике эти оценки, как правило, без изменений переносится и на другие способы разбиения выборки.

Контроль на отложенных данных (hold-out CV)

Оценка скользящего контроля строится по одному случайному разбиению.

Этот способ имеет существенные недостатки:

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

Контроль по отдельным объектам (leave-one-out CV)

Является частным случаем полного скользящего контроля при $k=1$ .

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

Недостатком LOO является большая ресурсоёмкость, так как обучаться приходится $L$ раз. Некоторые методы обучения позволяют достаточно быстро перенастраивать внутренние параметры алгоритма при замене одного обучающего объекта другим. В этих случаях вычисление LOO удаётся заметно ускорить.

Контроль по q блокам (q-fold CV)

Выборка случайным образом разбивается на q непересекающихся блоков одинаковой (или почти одинаковой) длины $k_1,\ldots,k_q$ :

$X^L = X^{k_1}_1 \cup\cdots\cup X^{k_q}_q,$ $k_1+\dots+k_q = L.$

Каждый блок по очереди становится контрольной подвыборкой, при этом обучение производится по остальным $q-1$ блокам. Критерий определяется как средняя ошибка на контрольной подвыборке:

$CV(\mu,X^L)=CV(\mu,X^L)=\frac1q \sum_{n=1}^q Q \bigl( \mu(X^L\setminus X^{k_n}_n), X^{k_n}_n \bigr).$

Это компромисс между LOO, hold-out и случайными разбиениями. С одной стороны, обучение производится только q раз вместо L. С другой стороны, длина обучающих подвыборок, равная $L\frac{q-1}q$ с точностью до округления, не сильно отличается от длины полной выборки L. Обычно выборку разбивают случайным образом на 10 или 20 блоков.

Контроль по T×q блокам (T×q-fold CV)

Контроль по q блокам (q-fold CV) повторяется T раз. Каждый раз выборка случайным образом разбивается на q непересекающихся блоков. Преимущество этого способа в том, что увеличивается число разбиений.

Стратификация

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

Стратификация заключается в том, чтобы заранее поделить выборку на части (страты), и при разбиении на обучение длины m и контроль длины k гарантировать, что каждая страта будет поделена между обучением и контролем в той же пропорции $m:k$ .

Стратификация классов в задачах классификации означает, что каждый класс делится между обучением и контролем в пропорции $m:k$ .

Стратификация по вещественному признаку. Объекты выборки сортируются согласно некоторому критерию (например, по одному из признаков), и контрольная выборка составляется из объектов с номерами $\bigl\lfloor \tfrac{(i-1)L}{k-1}+1 \bigr\rfloor,\; i=1,\ltots,k$ .