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

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

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

Версия 22:10, 7 апреля 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)}.$

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

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

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

Обычно интерес представляет односторонняя верхняя оценка; в таком случае достаточно взять $N=20$ разбиений.

Параметрические оценки доверительного интервала основаны на априорном предположении о виде распределения случайной величины $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 непересекающихся блоков. Преимущество этого способа в том, что увеличивается число разбиений.