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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определения)
(Разновидности кросс-валидации)
 
(не показаны 34 промежуточные версии 6 участников)
Строка 1: Строка 1:
'''Кросс-валидация''' или '''скользящий контроль''' это процедура оценивания обобщающей способности алгоритмов.  
+
'''Кросс-валидация''' или '''скользящий контроль''' {{---}} процедура эмпирического оценивания обобщающей способности алгоритмов.  
 
С помощью кросс-валидации эмулируется наличие тестовой выборки, которая не участвует в обучении, но для которой известны правильные ответы.  
 
С помощью кросс-валидации эмулируется наличие тестовой выборки, которая не участвует в обучении, но для которой известны правильные ответы.  
  
=== Определения ===  
+
=== Определения и обозначения ===  
<tex>T^l = {(x_i, y_i)}_{i=1}^{l}</tex> - обучающая выборка.
+
Пусть <tex> X </tex> {{---}} множество [[Общие понятия | признаков]], описывающих объекты, а <tex> Y </tex> {{---}} конечное множество меток.
  
<tex>Q</tex> - мера качества.
+
<tex>T^l = {(x_i, y_i)}_{i=1}^{l}, x_i \in X, y_i \in Y</tex> {{---}} обучающая выборка,
  
<tex>\mu(T^l) = argmin_{a \in A}Q(a, T^l)</tex> - метод минимизации [[Общие понятия | эмпирического риска]].
+
<tex>Q</tex> {{---}} мера качества,
  
== Разновидности Кросс-валидации ==
+
<tex>A</tex> {{---}} [[Модель алгоритма и ее выбор | модель]],
 +
 
 +
<tex>\mu: (X \times Y)^l \to A, </tex> {{---}} алгоритм обучения.
 +
 
 +
== Разновидности кросс-валидации ==
  
 
=== Валидация на отложенных данных (Hold-Out Validation) ===
 
=== Валидация на отложенных данных (Hold-Out Validation) ===
  
 
Обучающая выборка один раз случайным образом разбивается на две части <tex> T^l = T^t \cup T^{l-t} </tex>
 
Обучающая выборка один раз случайным образом разбивается на две части <tex> T^l = T^t \cup T^{l-t} </tex>
 +
 +
[[Файл:Hold-out.png|500px]]
 +
  
 
После чего решается задача оптимизации:  
 
После чего решается задача оптимизации:  
  
<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 применяется в случаях больших датасетов, т.к. требует меньше вычислительных мощностей по сравнению с другими методами кросс-валидации.  
 
Недостатком метода является то, что оценка существенно зависит от разбиения, тогда как желательно, чтобы она характеризовала только алгоритм обучения.
 
Недостатком метода является то, что оценка существенно зависит от разбиения, тогда как желательно, чтобы она характеризовала только алгоритм обучения.
+
 
 
=== Полная кросс-валидация (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]]
  
 
<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, что затрудняет практическое применение данного метода.
  
 
=== 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 = 10</tex> (5 в случае малого размера выборки).
  
<tex>T^l = F_1 \cup \dots \cup F_k, |F_i| \approx \frac{l}{k}
+
[[Файл:K-fold-validation.png|500px]]
\\ CV_k = \frac{1}{k} \sum_{i=1}^{k} Q(\mu(T^l \setminus F_i),F_i) \to min </tex>
 
  
Каждая из <tex>k</tex> частей единожды используется для тестирования.
+
<tex>T^l = F_1 \cup \dots \cup F_k, |F_i| \approx \frac{l}{k},
Как правило <tex>k = 10</tex> (5 в случае малого размера выборки)
+
\\ CV_k = \frac{1}{k} \sum_{i=1}^{k} Q(\mu(T^l \setminus F_i),F_i) \to min </tex>.
  
В результате можно посчитать различные метрики, показывающие, насколько модель удачная, например, среднюю ошибку на частях, которые не участвовали в обучающей выборке.
+
  <font color="green"># Пример кода для k-fold кросс-валидации:
 +
  '''# Пример классификатора, cпособного проводить различие между всего лишь двумя
 +
  '''# классами, "пятерка" и "не пятерка" из набор данных MNIST</font>
 +
  '''import''' numpy '''as''' np
 +
  '''from''' sklearn.model_selection '''import''' StratifiedKFold
 +
  '''from''' sklearn.datasets '''import''' fetch_openml
 +
  '''from''' sklearn.base '''import''' clone
 +
  '''from''' sklearn.linear_model '''import''' SGDClassifier
 +
 
 +
  mnist = fetch_openml('mnist_784', version=1)
 +
  X, y = mnist["data"], mnist["target"]
 +
  y = y.astype(np.uint8)
 +
  X_train, X_test, y_train, y_test = X[:60000], X[60000:], y[:60000], y[60000:]
 +
  y_train_5 = (y_train == 5) <font color="green"> # True для всех пятерок, False для в сех остальных цифр. Задача опознать пятерки</font>
 +
  y_test_5 = (y_test == 5)
 +
  sgd_clf = SGDClassifier(random_state=42)<font color="green"> # классификатор на основе метода стохастического градиентного спуска (Stochastic Gradient Descent SGD)</font>
 +
  <font color="green"># Разбиваем обучающий набора на 3 блока</font>
 +
  # выработку прогнозов и их оценку осуществляем на каждом блоке с использованием модели, обученной на остальных блоках</font>
 +
  skfolds = StratifiedKFold(n_splits=3, random_state=42)
 +
  for train_index, test_index in skfolds.split(X_train, y_train_5):
 +
      clone_clf = clone(sgd_clf)
 +
      X_train_folds = X_train[train_index]
 +
      y_train_folds = y_train_5[train_index]
 +
      X_test_fold = X_train[test_index]
 +
      y_test_fold = y_train_5[test_index]
 +
      clone_clf.fit(X_train_folds, y_train_folds)
 +
      y_pred = clone_clf.predict(X_test_fold)
 +
      n_correct = sum(y_pred == y_test_fold)
 +
      print(n_correct / len(y_pred))
 +
  <font color="green"># print 0.95035
 +
  #      0.96035
 +
  #      0.9604</font>
  
 
=== 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) ===  
 
Выборка разбивается на <tex>l-1</tex> и 1 объект <tex>l</tex> раз.
 
Выборка разбивается на <tex>l-1</tex> и 1 объект <tex>l</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>
+
[[Файл: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>.
 +
 
 +
Преимущества LOO в том, что каждый объект ровно один раз участвует в контроле, а длина обучающих подвыборок лишь на единицу меньше длины полной выборки.
 +
 
 +
Недостатком LOO является большая ресурсоёмкость, так как обучаться приходится <tex>L</tex> раз. Некоторые методы обучения позволяют достаточно быстро перенастраивать внутренние параметры алгоритма при замене одного обучающего объекта другим. В этих случаях вычисление LOO удаётся заметно ускорить.
  
 
=== Случайные разбиения (Random subsampling) ===  
 
=== Случайные разбиения (Random subsampling) ===  
Выборка разбивается в случайной пропорции. Процедура повторяется несколько раз.  
+
Выборка разбивается в случайной пропорции. Процедура повторяется несколько раз.
 +
 
 +
[[Файл:CompleteCrossValidation.png|500px]]
  
 
=== Критерий целостности модели (Model consistency criterion) ===  
 
=== Критерий целостности модели (Model consistency criterion) ===  
Не переобученый алгоритм должен показывать одинаковую эффективность на каждой части
+
Не переобученый алгоритм должен показывать одинаковую эффективность на каждой части.
 +
 
 +
[[Файл: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>.
  
 
== См. также ==
 
== См. также ==
* [[Общие понятия]]<sup>[на 17.01.19 не создан]</sup>
+
* [[Общие понятия]]
 
* [[Модель алгоритма и ее выбор]]
 
* [[Модель алгоритма и ее выбор]]
* [[Мета-обучение]]<sup>[на 17.01.19 не создан]</sup>
+
* [[Мета-обучение]]
  
 
== Примечания ==
 
== Примечания ==
 
# [https://en.wikipedia.org/wiki/Cross-validation_(statistics) Кросс-валидация]
 
# [https://en.wikipedia.org/wiki/Cross-validation_(statistics) Кросс-валидация]
# [https://www.ml4aad.org/wp-content/uploads/2018/07/automl_book_draft_auto-weka.pdf Автоматизированный выбор модели в библиотеке WEKA для Java]
+
 
# [https://epistasislab.github.io/tpot/ Автоматизированный выбор модели в библиотеке TPOT для Python]
 
# [https://automl.github.io/auto-sklearn/stable/ Автоматизированный выбор модели в библиотеке sklearn для Python]
 
 
== Источники информации ==
 
== Источники информации ==
 
# [http://www.machinelearning.ru/wiki/index.php?title=%D0%A1%D0%BA%D0%BE%D0%BB%D1%8C%D0%B7%D1%8F%D1%89%D0%B8%D0%B9_%D0%BA%D0%BE%D0%BD%D1%82%D1%80%D0%BE%D0%BB%D1%8C Скользящий контроль] -  статья на MachineLearning.ru
 
# [http://www.machinelearning.ru/wiki/index.php?title=%D0%A1%D0%BA%D0%BE%D0%BB%D1%8C%D0%B7%D1%8F%D1%89%D0%B8%D0%B9_%D0%BA%D0%BE%D0%BD%D1%82%D1%80%D0%BE%D0%BB%D1%8C Скользящий контроль] -  статья на MachineLearning.ru

Текущая версия на 03:58, 27 июля 2020

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

Определения и обозначения[править]

Пусть [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].

 # Пример кода для k-fold кросс-валидации:
 # Пример классификатора, cпособного проводить различие между всего лишь двумя
 # классами, "пятерка" и "не пятерка" из набор данных MNIST
 import numpy as np
 from sklearn.model_selection import StratifiedKFold
 from sklearn.datasets import fetch_openml
 from sklearn.base import clone
 from sklearn.linear_model import SGDClassifier
 
 mnist = fetch_openml('mnist_784', version=1)
 X, y = mnist["data"], mnist["target"]
 y = y.astype(np.uint8)
 X_train, X_test, y_train, y_test = X[:60000], X[60000:], y[:60000], y[60000:]
 y_train_5 = (y_train == 5)  # True для всех пятерок, False для в сех остальных цифр. Задача опознать пятерки
 y_test_5 = (y_test == 5)
 sgd_clf = SGDClassifier(random_state=42) # классификатор на основе метода стохастического градиентного спуска (Stochastic Gradient Descent SGD)
 # Разбиваем обучающий набора на 3 блока
 # выработку прогнозов и их оценку осуществляем на каждом блоке с использованием модели, обученной на остальных блоках</font>
 skfolds = StratifiedKFold(n_splits=3, random_state=42)
 for train_index, test_index in skfolds.split(X_train, y_train_5):
     clone_clf = clone(sgd_clf)
     X_train_folds = X_train[train_index]
     y_train_folds = y_train_5[train_index]
     X_test_fold = X_train[test_index]
     y_test_fold = y_train_5[test_index]
     clone_clf.fit(X_train_folds, y_train_folds)
     y_pred = clone_clf.predict(X_test_fold)
     n_correct = sum(y_pred == y_test_fold)
     print(n_correct / len(y_pred))
 # print 0.95035 
 #       0.96035 
 #       0.9604

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