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

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

Версия от 16:13, 7 апреля 2008; Vokov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

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

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

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

Содержание

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

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

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

Пусть $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). </p>$

Доверительный интервал

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

$Q^{(1)} \leq Q^{(2)} \leq \cdots \leq Q^{(N)}. </p>$

Утверждение. Если разбиения осуществлялись случайно, независимо и равновероятно, то с вероятностью $\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=39$ разбиений.

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

Статья в настоящий момент дорабатывается.
{{{1}}}

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