Кросс-валидация — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(См. также)
Строка 1: Строка 1:
'''Кросс-валидация''' или '''скользящий контроль''' это процедура эмпирического оценивания обобщающей способности алгоритмов.  
+
'''Кросс-валидация''' или '''скользящий контроль''' {{---}} процедура эмпирического оценивания обобщающей способности алгоритмов.  
 
С помощью кросс-валидации эмулируется наличие тестовой выборки, которая не участвует в обучении, но для которой известны правильные ответы.  
 
С помощью кросс-валидации эмулируется наличие тестовой выборки, которая не участвует в обучении, но для которой известны правильные ответы.  
  
Строка 5: Строка 5:
 
Пусть <tex> X </tex> {{---}} множество [[Общие понятия | признаков]], описывающих объекты, а <tex> Y </tex> {{---}} конечное множество меток.
 
Пусть <tex> X </tex> {{---}} множество [[Общие понятия | признаков]], описывающих объекты, а <tex> Y </tex> {{---}} конечное множество меток.
  
<tex>T^l = {(x_i, y_i)}_{i=1}^{l}, x_i \in X, y_i \in Y</tex> {{---}} обучающая выборка.
+
<tex>T^l = {(x_i, y_i)}_{i=1}^{l}, x_i \in X, y_i \in Y</tex> {{---}} обучающая выборка,
  
<tex>Q</tex> {{---}} мера качества.
+
<tex>Q</tex> {{---}} мера качества,
  
<tex>A</tex> {{---}} [[Модель алгоритма и ее выбор | модель]].
+
<tex>A</tex> {{---}} [[Модель алгоритма и ее выбор | модель]],
  
 
<tex>\mu: (X \times Y)^l \to A, </tex> {{---}} алгоритм обучения.
 
<tex>\mu: (X \times Y)^l \to A, </tex> {{---}} алгоритм обучения.
  
== Разновидности Кросс-валидации ==
+
== Разновидности кросс-валидации ==
  
 
=== Валидация на отложенных данных (Hold-Out Validation) ===
 
=== Валидация на отложенных данных (Hold-Out Validation) ===
Строка 24: Строка 24:
 
После чего решается задача оптимизации:  
 
После чего решается задача оптимизации:  
  
<tex>HO(\mu, T^t, T^{l-t}) = Q(\mu(T^t), T^{l-t}) \to min </tex>
+
<tex>HO(\mu, T^t, T^{l-t}) = Q(\mu(T^t), T^{l-t}) \to min </tex>,
  
 
Метод Hold-out применяется в случаях больших датасетов, т.к. требует меньше вычислительных мощностей по сравнению с другими методами кросс-валидации.  
 
Метод Hold-out применяется в случаях больших датасетов, т.к. требует меньше вычислительных мощностей по сравнению с другими методами кросс-валидации.  
Строка 30: Строка 30:
  
 
=== Полная кросс-валидация (Complete cross-validation) ===
 
=== Полная кросс-валидация (Complete cross-validation) ===
# Выбирается значение <tex>t</tex>
+
# Выбирается значение <tex>t</tex>;
# Выборка разбивается всеми возможными способами на две части <tex> T^l = T^t \cup T^{l-t} </tex>
+
# Выборка разбивается всеми возможными способами на две части <tex> T^l = T^t \cup T^{l-t} </tex>.
  
 
[[Файл:CompleteCrossValidation.png|500px]]
 
[[Файл:CompleteCrossValidation.png|500px]]
  
 
<tex>CVV_t = \frac{1}{C_l^{l-t}}  
 
<tex>CVV_t = \frac{1}{C_l^{l-t}}  
\displaystyle\sum_{T^l = T^t \cup T^{l-t}} Q(\mu(T^t), T^{l-t}) \to min </tex>
+
\displaystyle\sum_{T^l = T^t \cup T^{l-t}} Q(\mu(T^t), T^{l-t}) \to min </tex>,
  
 
Здесь число разбиений <tex>C_l^{l-t}</tex> становится слишком большим даже при сравнительно малых значениях t, что затрудняет практическое применение данного метода.
 
Здесь число разбиений <tex>C_l^{l-t}</tex> становится слишком большим даже при сравнительно малых значениях t, что затрудняет практическое применение данного метода.
Строка 42: Строка 42:
 
=== k-fold кросс-валидация ===
 
=== k-fold кросс-валидация ===
  
# Обучающая выборка разбивается на <tex> k </tex> непересекающихся одинаковых по объему частей
+
# Обучающая выборка разбивается на <tex> k </tex> непересекающихся одинаковых по объему частей;
 
# Производится <tex> k </tex> итераций. На каждой итерации происходит следующее:
 
# Производится <tex> k </tex> итераций. На каждой итерации происходит следующее:
 
## Модель обучается на <tex> k - 1 </tex> части обучающей выборки;
 
## Модель обучается на <tex> k - 1 </tex> части обучающей выборки;
## Модель тестируется на части обучающей выборки, которая не участвовала в обучении;
+
## Модель тестируется на части обучающей выборки, которая не участвовала в обучении.
 
Каждая из <tex>k</tex> частей единожды используется для тестирования.  
 
Каждая из <tex>k</tex> частей единожды используется для тестирования.  
Как правило <tex>k = 10</tex> (5 в случае малого размера выборки)
+
Как правило, <tex>k = 10</tex> (5 в случае малого размера выборки).
  
 
[[Файл:K-fold-validation.png|500px]]
 
[[Файл:K-fold-validation.png|500px]]
  
<tex>T^l = F_1 \cup \dots \cup F_k, |F_i| \approx \frac{l}{k}  
+
<tex>T^l = F_1 \cup \dots \cup F_k, |F_i| \approx \frac{l}{k},
\\ CV_k = \frac{1}{k} \sum_{i=1}^{k} Q(\mu(T^l \setminus F_i),F_i) \to min </tex>
+
\\ CV_k = \frac{1}{k} \sum_{i=1}^{k} Q(\mu(T^l \setminus F_i),F_i) \to min </tex>.
  
 
=== t×k-fold кросс-валидация ===  
 
=== t×k-fold кросс-валидация ===  
 
# Процедура выполняется <tex>t</tex> раз:  
 
# Процедура выполняется <tex>t</tex> раз:  
## Обучающая выборка случайным образом разбивается на <tex>k</tex> непересекающихся одинаковых по объему частей
+
## Обучающая выборка случайным образом разбивается на <tex>k</tex> непересекающихся одинаковых по объему частей;
 
## Производится <tex> k </tex> итераций. На каждой итерации происходит следующее:
 
## Производится <tex> k </tex> итераций. На каждой итерации происходит следующее:
 
### Модель обучается на <tex> k - 1 </tex> части обучающей выборки;
 
### Модель обучается на <tex> k - 1 </tex> части обучающей выборки;
### Модель тестируется на части обучающей выборки, которая не участвовала в обучении;
+
### Модель тестируется на части обучающей выборки, которая не участвовала в обучении.
  
  
<tex>T^l = F_{(1,1)} \cup \dots \cup F_{(k,1)} = \dots = F_{(1,t)} \cup \dots \cup F_{(k,t)}, |F_{(i,j)}| \approx \frac{l}{k}  </tex>  
+
<tex>T^l = F_{(1,1)} \cup \dots \cup F_{(k,1)} = \dots = F_{(1,t)} \cup \dots \cup F_{(k,t)}, |F_{(i,j)}| \approx \frac{l}{k}  </tex>,
  
<tex> CV_{t \times k} = \frac{1}{tk} \sum_{j=1}^t \sum_{i=1}^{k} Q(\mu(T^l \setminus F_{(i,j)}),F_{(i,j)}) \to min </tex>
+
<tex> CV_{t \times k} = \frac{1}{tk} \sum_{j=1}^t \sum_{i=1}^{k} Q(\mu(T^l \setminus F_{(i,j)}),F_{(i,j)}) \to min </tex>.
  
 
=== Кросс-валидация по отдельным объектам (Leave-One-Out) ===  
 
=== Кросс-валидация по отдельным объектам (Leave-One-Out) ===  
Строка 71: Строка 71:
 
[[Файл:LeaveOneOut.png|500px]]
 
[[Файл:LeaveOneOut.png|500px]]
  
<tex>LOO = \frac{1}{l} \sum_{i=1}^{l} Q(\mu(T^l \setminus p_i),p_i) \to min </tex>, где <tex>p_i = (x_i, y_i)</tex>
+
<tex>LOO = \frac{1}{l} \sum_{i=1}^{l} Q(\mu(T^l \setminus p_i),p_i) \to min </tex>, где <tex>p_i = (x_i, y_i)</tex>.
  
 
Преимущества LOO в том, что каждый объект ровно один раз участвует в контроле, а длина обучающих подвыборок лишь на единицу меньше длины полной выборки.
 
Преимущества LOO в том, что каждый объект ровно один раз участвует в контроле, а длина обучающих подвыборок лишь на единицу меньше длины полной выборки.
Строка 83: Строка 83:
  
 
=== Критерий целостности модели (Model consistency criterion) ===  
 
=== Критерий целостности модели (Model consistency criterion) ===  
Не переобученый алгоритм должен показывать одинаковую эффективность на каждой части
+
Не переобученый алгоритм должен показывать одинаковую эффективность на каждой части.
  
 
[[Файл:ModelConsistencyCriterion.png|500px]]
 
[[Файл:ModelConsistencyCriterion.png|500px]]
  
<tex> D_1 = (\mu, T^{l-t}) = \frac{1}{l} \sum_{i=1}^l (\mu(T^t)(x_i)-\mu(T^{l-t})(x_i)) </tex>
+
<tex> D_1 = (\mu, T^{l-t}) = \frac{1}{l} \sum_{i=1}^l (\mu(T^t)(x_i)-\mu(T^{l-t})(x_i)) </tex>,
  
 
Метод может быть обобщен как аналог <tex> CV_{t \times 2} </tex>.
 
Метод может быть обобщен как аналог <tex> CV_{t \times 2} </tex>.

Версия 02:53, 30 января 2019

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

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

Пусть [math] X [/math] — множество признаков, описывающих объекты, а [math] Y [/math] — конечное множество меток.

[math]T^l = {(x_i, y_i)}_{i=1}^{l}, x_i \in X, y_i \in Y[/math] — обучающая выборка,

[math]Q[/math] — мера качества,

[math]A[/math] модель,

[math]\mu: (X \times Y)^l \to A, [/math] — алгоритм обучения.

Разновидности кросс-валидации

Валидация на отложенных данных (Hold-Out Validation)

Обучающая выборка один раз случайным образом разбивается на две части [math] T^l = T^t \cup T^{l-t} [/math]

Hold-out.png


После чего решается задача оптимизации:

[math]HO(\mu, T^t, T^{l-t}) = Q(\mu(T^t), T^{l-t}) \to min [/math],

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

Полная кросс-валидация (Complete cross-validation)

  1. Выбирается значение [math]t[/math];
  2. Выборка разбивается всеми возможными способами на две части [math] T^l = T^t \cup T^{l-t} [/math].

CompleteCrossValidation.png

[math]CVV_t = \frac{1}{C_l^{l-t}} \displaystyle\sum_{T^l = T^t \cup T^{l-t}} Q(\mu(T^t), T^{l-t}) \to min [/math],

Здесь число разбиений [math]C_l^{l-t}[/math] становится слишком большим даже при сравнительно малых значениях t, что затрудняет практическое применение данного метода.

k-fold кросс-валидация

  1. Обучающая выборка разбивается на [math] k [/math] непересекающихся одинаковых по объему частей;
  2. Производится [math] k [/math] итераций. На каждой итерации происходит следующее:
    1. Модель обучается на [math] k - 1 [/math] части обучающей выборки;
    2. Модель тестируется на части обучающей выборки, которая не участвовала в обучении.

Каждая из [math]k[/math] частей единожды используется для тестирования. Как правило, [math]k = 10[/math] (5 в случае малого размера выборки).

K-fold-validation.png

[math]T^l = F_1 \cup \dots \cup F_k, |F_i| \approx \frac{l}{k}, \\ CV_k = \frac{1}{k} \sum_{i=1}^{k} Q(\mu(T^l \setminus F_i),F_i) \to min [/math].

t×k-fold кросс-валидация

  1. Процедура выполняется [math]t[/math] раз:
    1. Обучающая выборка случайным образом разбивается на [math]k[/math] непересекающихся одинаковых по объему частей;
    2. Производится [math] k [/math] итераций. На каждой итерации происходит следующее:
      1. Модель обучается на [math] k - 1 [/math] части обучающей выборки;
      2. Модель тестируется на части обучающей выборки, которая не участвовала в обучении.


[math]T^l = F_{(1,1)} \cup \dots \cup F_{(k,1)} = \dots = F_{(1,t)} \cup \dots \cup F_{(k,t)}, |F_{(i,j)}| \approx \frac{l}{k} [/math],

[math] CV_{t \times k} = \frac{1}{tk} \sum_{j=1}^t \sum_{i=1}^{k} Q(\mu(T^l \setminus F_{(i,j)}),F_{(i,j)}) \to min [/math].

Кросс-валидация по отдельным объектам (Leave-One-Out)

Выборка разбивается на [math]l-1[/math] и 1 объект [math]l[/math] раз.

LeaveOneOut.png

[math]LOO = \frac{1}{l} \sum_{i=1}^{l} Q(\mu(T^l \setminus p_i),p_i) \to min [/math], где [math]p_i = (x_i, y_i)[/math].

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

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

Случайные разбиения (Random subsampling)

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

CompleteCrossValidation.png

Критерий целостности модели (Model consistency criterion)

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

ModelConsistencyCriterion.png

[math] D_1 = (\mu, T^{l-t}) = \frac{1}{l} \sum_{i=1}^l (\mu(T^t)(x_i)-\mu(T^{l-t})(x_i)) [/math],

Метод может быть обобщен как аналог [math] CV_{t \times 2} [/math].

См. также

Примечания

  1. Кросс-валидация

Источники информации

  1. Скользящий контроль - статья на MachineLearning.ru
  2. Model assessment and selection