Участник:Vokov/Скользящий контроль

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

Перейти к: навигация, поиск

Кросс-валида́ция (перекрёстная прове́рка, скользя́щий контро́ль, англ. cross-validation) — метод оценки предсказательной способности моделей машинного обучения и статистических моделей, основанный на многократном разбиении исходной выборки на обучающую и проверочную (тестовую) подвыборки. Основная цель кросс-валидации — получить несмещённую (или слабо смещённую) оценку ожидаемой ошибки модели на новых данных, не участвовавших в обучении, и тем самым избежать переобучения при выборе модели или настройке её гиперпараметров.

В современной практике анализа данных и машинного обучения кросс-валидация является одним из основных инструментов сравнения алгоритмов, отбора признаков и оптимизации гиперпараметров. Её систематическое применение позволяет разделить этапы обучения, выбора модели и итоговой оценки качества, что критически важно для получения надёжных и воспроизводимых результатов.

Содержание

Мотивировка и основные идеи

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

Простейший способ — отложить часть данных, однократно обучить модель на оставшейся части и вычислить ошибку на отложенной выборке (англ. hold-out validation). Однако такая оценка сильно зависит от конкретного случайного разбиения и неэффективно использует данные, особенно когда выборка мала. Кросс-валидация преодолевает эти недостатки, усредняя ошибку по нескольким разбиениям.

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

Историческая справка

Идейным предшественником кросс-валидации является метод складного ножа (англ. jackknife), предложенный Морисом Кенуем (Quenouille, 1949) для оценивания смещения статистических оценок и развитый Джоном Тьюки (Tukey, 1958), который дал методу его название[1][2]. Тьюки сравнивал его с универсальным ножом бойскаута, который можно приспособить для самых разных задач, хотя он и уступает специализированным инструментам в каждой конкретной ситуации.

Современная кросс-валидация возникла в 1970-х годах в работах Мервина Стоуна (Stone, 1974), который ввёл термин «cross-validation», и Сеймура Гейссера (Geisser, 1975), предложившего метод «прогнозирующего повторного использования выборки» (predictive sample reuse)[3][4]. Практически одновременно Аллен (Allen, 1974) предложил критерий PRESS (Prediction Sum of Squares) для линейной регрессии, математически эквивалентный скользящему контролю с последовательным исключением одного наблюдения[5]. С 1990-х годов, с ростом популярности методов машинного обучения, кросс-валидация стала стандартным инструментом оценки и сравнения алгоритмов, а исследования Кохави (Kohavi, 1995) закрепили многие современные практические рекомендации[6].

Основные разновидности кросс-валидации

Всюду далее будем считать, что имеется выборка \mathcal{D} = \{(\mathbf{x}_i, y_i)\}_{i=1}^{n}, где \mathbf{x}_i — вектор признаков, y_i — целевая переменная (числовая в задачах регрессии или категориальная в задачах классификации). Модель, обученная на подмножестве \mathcal{T} \subset \mathcal{D}, обозначается \hat{f}_{\mathcal{T}}. Функция потерь L(y, \hat{y}) измеряет ошибку прогноза (например, квадратичная ошибка, абсолютная ошибка, индикатор несовпадения классов).

k-блочная кросс-валидация (k-fold)

Выборка случайным образом разбивается на k непересекающихся блоков (англ. folds) примерно равного размера: \mathcal{D} = \mathcal{F}_1 \cup \dots \cup \mathcal{F}_k. Для каждого блока \mathcal{F}_j выполняются следующие шаги:

  1. модель обучается на объединении всех блоков, кроме \mathcal{F}_j (обучающая подвыборка \mathcal{D} \setminus \mathcal{F}_j);
  2. вычисляется средняя ошибка на отложенном блоке \mathcal{F}_j: \text{Err}_j = \frac{1}{|\mathcal{F}_j|} \sum_{i \in \mathcal{F}_j} L(y_i, \hat{f}_{\mathcal{D} \setminus \mathcal{F}_j}(\mathbf{x}_i)).

Итоговая оценка кросс-валидации есть среднее арифметическое по всем k блокам:

\text{CV}_{(k)} = \frac{1}{k} \sum_{j=1}^{k} \text{Err}_j.

На практике наиболее распространён выбор k = 5 или k = 10. Такие значения обеспечивают компромисс между смещением и дисперсией оценки (см. ниже). При k = n метод переходит в скользящий контроль с исключением по одному наблюдению.

Скользящий контроль с исключением по одному (LOOCV)

Частный случай k-блочной валидации, когда каждый блок состоит ровно из одного наблюдения: k = n. Обозначается LOOCV (leave-one-out cross-validation). Модель обучается n раз, каждый раз на всех точках, кроме одной, а ошибка вычисляется на исключённой точке. Оценка:

\text{CV}_{\text{LOO}} = \frac{1}{n} \sum_{i=1}^{n} L(y_i, \hat{f}_{-i}(\mathbf{x}_i)),

где \hat{f}_{-i} — модель, обученная без i-го наблюдения.

LOOCV обладает минимальным смещением, так как для обучения используется почти вся выборка, но может иметь высокую дисперсию, особенно для нестабильных моделей. Кроме того, он вычислительно затратен при больших n, хотя для линейных моделей существуют эффективные аналитические формулы (PRESS-статистика).

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

Полный, или исчерпывающий скользящий контроль (англ. complete cross-validation, exhaustive cross-validation) обобщает LOOCV на случай, когда из выборки исключается не одно, а p наблюдений, и перебираются все возможные комбинации тестовых подвыборок такого размера. Эта процедура также известна как скользящий контроль с исключением p наблюдений (leave-p-out cross-validation, LPOCV). Оценка вычисляется по формуле:

\text{CV}_{\text{LPOCV}} = \frac1{C_n^p} \sum_{\mathcal{S}: |\mathcal{S}|=p} \frac{1}{p} \sum_{i \in \mathcal{S}} L(y_i, \hat{f}_{\mathcal{D}\setminus\mathcal{S}}(\mathbf{x}_i)),

где сумма берётся по всем C_n^p подмножествам \mathcal{S} размера p.

Теоретически LPOCV позволяет тонко управлять компромиссом между смещением и дисперсией, варьируя p, однако его практическое применение ограничено экспоненциальным ростом числа обучений. Полный перебор осуществим лишь для очень малых выборок. Шао (Shao, 1993) показал, что для состоятельного выбора модели в линейной регрессии доля исключаемых наблюдений должна расти с объёмом выборки, что стимулировало интерес к LPOCV в теоретических исследованиях[7].

Стратифицированная кросс-валидация

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

Стратификация, как правило, снижает дисперсию оценки кросс-валидации и рекомендуется в большинстве практических руководств, в том числе в работе Кохави (1995)[6]. Она особенно важна при малом объёме данных и в задачах медицинской диагностики, обнаружения мошенничества и других областях с несбалансированными классами.

Повторная кросс-валидация (repeated CV)

Оценка, полученная однократным разбиением на k блоков, может обладать заметной дисперсией из-за случайности разбиения. Для её уменьшения процедуру повторяют несколько раз с разными случайными разбиениями, после чего усредняют результаты. Например, 10-кратная кросс-валидация, повторённая 5 раз, даёт более стабильную оценку, чем однократная 10-кратная. Ценой является пропорциональное увеличение времени вычислений.

Вложенная кросс-валидация (nested CV)

Когда кросс-валидация одновременно применяется для выбора модели (настройки гиперпараметров) и для итоговой оценки её качества, возникает опасность оптимистического смещения: модель «подглядывает» в тестовые блоки внешнего цикла через выбор гиперпараметров. Для строгого разделения этих этапов используют вложенную (двойную) кросс-валидацию, состоящую из двух вложенных циклов:

  • Внешний цикл разбивает все данные на K блоков. Каждый внешний блок поочерёдно играет роль независимого тестового набора.
  • Внутренний цикл на оставшихся K-1 блоках выполняет кросс-валидацию (например, 5-кратную) для настройки гиперпараметров или отбора модели-кандидата. Выбранная таким образом модель обучается на полном внутреннем наборе и оценивается на внешнем тестовом блоке.

Результатом внешнего цикла является несмещённая оценка производительности всей процедуры обучения вместе с выбором гиперпараметров. Вложенная кросс-валидация — золотой стандарт оценки моделей, когда одновременно решаются задачи настройки и сравнения.

Другие варианты

  • Скользящий контроль с исключением p наблюдений (leave-p-out) — всевозможные подмножества размера p используются как тестовые. Число обучений C_n^p обычно слишком велико, поэтому на практике применяется редко.
  • Случайные подвыборки (Monte Carlo CV) — заданное количество случайных разбиений на обучающую и тестовую подвыборки фиксированного размера без требования охватить все данные. Позволяет гибко варьировать долю тестовых данных.

Статистические свойства

Качество оценки ошибки методом кросс-валидации характеризуется смещением и дисперсией.

  • Смещение. k-блочная кросс-валидация оценивает ожидаемую ошибку модели, обученной на подвыборках размера n - n/k. Поскольку ошибка, как правило, убывает с ростом объёма обучающей выборки, оценка CV даёт слегка завышенное значение по сравнению с ошибкой модели, обученной на всех n наблюдениях. Для LOOCV это смещение минимально, для малых k (например, k=2) — максимально.
  • Дисперсия. Дисперсия оценки зависит от стабильности алгоритма обучения. LOOCV может иметь высокую дисперсию, потому что обучающие подвыборки почти одинаковы и предсказания на разных исключаемых точках сильно коррелированы. Эмпирические исследования показывают, что 5- и 10-кратная кросс-валидация часто обеспечивают лучший баланс смещения и дисперсии[6].
  • Асимптотические свойства. При n \to \infty и фиксированном k оценка CV является состоятельной для ожидаемой ошибки прогноза.

В задачах классификации дополнительную роль играет выбор метрики: доли правильных ответов (accuracy), средней абсолютной ошибки вероятностей (Brier score), логарифмической функции потерь и т. д. Одна и та же процедура кросс-валидации позволяет оценивать любую из них, однако свойства (смещение/дисперсия) могут различаться.

Доверительные интервалы в кросс-валидации

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

Простейший подход — вычислить выборочное стандартное отклонение ошибок на k блоках s и построить интервал в виде \text{CV}_{(k)} \pm t_{k-1,\alpha/2} \, s / \sqrt{k}. Такой интервал часто оказывается слишком оптимистичным (заужен), потому что не учитывает положительную корреляцию между блоками: модель обучена на сильно перекрывающихся данных. Более корректная оценка дисперсии среднего значения должна явно включать ковариации между ошибками блоков.

Повторная кросс-валидация

Надо и Бенжио (Nadeau & Bengio, 2003) предложили формулу, модифицирующую наивную оценку дисперсии путём учёта отношения числа тестовых наблюдений к общему числу[8]. Если \text{CV}_i — средняя ошибка в i-м повторении k-блочной валидации, а \bar{\text{CV}} = \frac{1}{R}\sum_{i=1}^{R} \text{CV}_i, то скорректированная дисперсия среднего оценивается как

\widehat{\text{Var}}(\bar{\text{CV}}) = \left(\frac{1}{R} + \frac{1}{k-1}\right) \frac{1}{R-1} \sum_{i=1}^{R} (\text{CV}_i - \bar{\text{CV}})^2.

На основе неё можно построить приближённый доверительный интервал, используя квантили распределения Стьюдента.

Другой популярный метод — бутстреп (англ. bootstrap) по результатам повторений: из множества из R значений \text{CV}_i генерируются бутстреп-выборки, и интервал строится по процентилям. Бутстреп не требует вывода аналитических формул дисперсии, однако ему всё равно необходимо достаточно большое R (обычно десятки–сотни повторений).

Следует помнить, что никакой несмещённой оценки дисперсии ошибки k-блочной кросс-валидации, не зависящей от неизвестных характеристик распределения данных, в общем случае не существует (Bengio & Grandvalet, 2004)[9]. Поэтому на практике доверительные интервалы для ошибки CV носят приближённый характер и должны интерпретироваться с осторожностью.

Непараметрическое доверительное оценивание

Рассмотрим вариационный ряд значений Q_j = \text{Err}_j, полученных на разбиениях j=1,\ldots,N:

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

Если бы случайные величины Q_j были независимы, то значение случайной величины Q_j не выходило бы за границы доверительного интервала \bigl[ Q^{(t)},Q^{(N-t+1)} \bigr] с вероятностью \eta= \frac{2t}{N+1}. В частности, для интервальной оценки \bigl[ Q^{(1)},Q^{(N)} \bigr] с надёжностью 95% достаточно взять N=40 разбиений. Для получения верхней оценки с надёжностью 95% достаточно взять N=20 разбиений.

Проблема в том, что величины Q_j не являются независимыми, и к таким простым оценкам следует относиться с осторожностью, как к эвристическим.

Параметрическое доверительное оценивание

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

Кросс-валидация в задачах прогнозирования и связь с A/B тестированием

В прогностических задачах различают валидацию вне выборки (англ. out-of-sample validation) и валидацию вне времени (англ. out-of-time validation). Первая предполагает, что наблюдения из обучающей и тестовой выборок получены из одного и того же стационарного распределения, и случайное разбиение не нарушает структуру данных. Стандартная кросс-валидация как раз реализует эту идею.

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

  • Валидация на будущих периодах (out-of-time): разбиение производится с учётом хронологии — все тренировочные наблюдения предшествуют тестовым. Кросс-валидация временных рядов (time series cross-validation) использует «скользящее окно» или «расширяющееся окно»: модель последовательно обучается на всё более длинных исторических интервалах и проверяется на непосредственно следующем периоде.
  • Такой подход гарантирует, что мы оцениваем именно прогнозную силу во времени, а не умение модели интерполировать пропуски.

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

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

  • Кросс-валидация опирается на предположение о стационарности и независимости наблюдений, в то время как A/B тест может учитывать временные эффекты, новизну и взаимодействие между пользователями.
  • Кросс-валидация не может заменить A/B тест для измерения причинно-следственных эффектов, потому что не подразумевает активного рандомизированного вмешательства.
  • На практике кросс-валидацию часто используют для офлайн-отбора лучшей модели-кандидата перед запуском A/B теста, чтобы снизить риски и затраты, связанные с тестированием заведомо слабых вариантов.

Таким образом, кросс-валидация и A/B тестирование являются взаимодополняющими инструментами: первая позволяет быстро и дёшево сравнивать модели на исторических данных, второе — подтверждать эффект в реальных условиях эксплуатации.

Кросс-валидация в отборе модели и настройке гиперпараметров

Кросс-валидация широко применяется для выбора модели среди семейства кандидатов (например, выбор степени полинома в регрессии, числа соседей в k-NN, коэффициента регуляризации в гребневой регрессии или LASSO). Стандартный протокол состоит в том, чтобы для каждого значения гиперпараметра вычислить среднюю ошибку кросс-валидации и выбрать то значение, которое её минимизирует.

Для дополнительной устойчивости часто применяют «правило одной стандартной ошибки» (one standard error rule): выбирается наиболее простая (экономная) модель, чья ошибка не превышает минимальную более чем на одно стандартное отклонение ошибки CV[10].

Критически важно помнить: если кросс-валидация используется и для выбора гиперпараметров, и для финальной оценки, то итоговую ошибку необходимо измерять на независимом тестовом наборе, не участвовавшем ни в одном из предыдущих этапов. В противном случае оценка будет чрезмерно оптимистичной. Вложенная кросс-валидация, описанная выше, позволяет получить практически несмещённую оценку без откладывания отдельного тестового набора.

Распространённые ошибки и практические рекомендации

  • Утечка данных (data leakage). Любая предобработка, опирающаяся на статистики всей выборки (центрирование, масштабирование, отбор признаков, заполнение пропусков), должна выполняться отдельно внутри каждого блока кросс-валидации на основе только обучающей подвыборки. Игнорирование этого правила завышает кажущуюся обобщающую способность.
  • Несбалансированные классы. Всегда следует использовать стратифицированное разбиение; простой случайный k-fold может привести к блокам без представителей минорного класса и полностью исказить оценку.
  • Выбор числа блоков k. Для малых выборок (n < 100) часто используют LOOCV или k=n. Для средних и больших выборок стандартом де-факто является k=10; k=5 даёт меньшую дисперсию, но чуть большее смещение. При значительном дисбалансе число блоков можно увеличить.
  • Повторная кросс-валидация и статистические тесты. При сравнении нескольких алгоритмов многократно повторённая кросс-валидация позволяет применить парные статистические тесты (например, тест Уилкоксона или скорректированный t-тест) для формальной проверки гипотез о превосходстве одного метода над другим[11].
  • Детерминированные модели. Для некоторых алгоритмов (например, линейная регрессия с фиксированными предикторами) кросс-валидация даёт детерминированный результат; для методов, зависящих от случайной инициализации (нейронные сети, случайный лес), необходимо фиксировать начальное состояние генератора случайных чисел, чтобы обеспечить воспроизводимость.

См. также

Примечания

  1. Quenouille M. H. Approximate tests of correlation in time-series // Journal of the Royal Statistical Society, Series B. — 1949. — Т. 11. — № 1. — С. 68–84.
  2. Tukey J. W. Bias and confidence in not quite large samples (abstract) // The Annals of Mathematical Statistics. — 1958. — Т. 29. — № 2. — С. 614.
  3. Stone M. Cross-validatory choice and assessment of statistical predictions // Journal of the Royal Statistical Society, Series B. — 1974. — Т. 36. — № 2. — С. 111–147.
  4. Geisser S. The predictive sample reuse method with applications // Journal of the American Statistical Association. — 1975. — Т. 70. — № 350. — С. 320–328.
  5. Allen D. M. The relationship between variable selection and data augmentation and a method for prediction // Technometrics. — 1974. — Т. 16. — № 1. — С. 125–127.
  6. 6,0 6,1 6,2 Kohavi R. A study of cross-validation and bootstrap for accuracy estimation and model selection // Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI). — 1995. — С. 1137–1143.
  7. Shao J. Linear model selection by cross-validation // Journal of the American Statistical Association. — 1993. — Т. 88. — № 422. — С. 486–494.
  8. Nadeau C., Bengio Y. Inference for the generalization error // Machine Learning. — 2003. — Т. 52. — № 3. — С. 239–281.
  9. Bengio Y., Grandvalet Y. No unbiased estimator of the variance of K-fold cross-validation // Journal of Machine Learning Research. — 2004. — Т. 5. — С. 1089–1105.
  10. Hastie T., Tibshirani R., Friedman J. 7.10.1 K-Fold Cross-Validation // The Elements of Statistical Learning. — 2nd ed.. — New York: Springer, 2009. — С. 241–245. — ISBN 978-0-387-84857-0
  11. Dietterich T. G. Approximate statistical tests for comparing supervised classification learning algorithms // Neural Computation. — 1998. — Т. 10. — № 7. — С. 1895–1923.

Литература

  • Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. — 2nd ed.. — New York: Springer, 2009. — ISBN 978-0-387-84857-0 — Глава 7 «Model Assessment and Selection».
  • James G., Witten D., Hastie T., Tibshirani R. An Introduction to Statistical Learning: with Applications in R. — New York: Springer, 2013. — ISBN 978-1-4614-7137-0 — Глава 5 «Resampling Methods».
  • Kohavi R. A study of cross-validation and bootstrap for accuracy estimation and model selection // Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI). — 1995. — С. 1137–1143.
  • Stone M. Cross-validatory choice and assessment of statistical predictions // Journal of the Royal Statistical Society, Series B. — 1974. — Т. 36. — № 2. — С. 111–147.
  • Geisser S. The predictive sample reuse method with applications // Journal of the American Statistical Association. — 1975. — Т. 70. — № 350. — С. 320–328.
  • Arlot S., Celisse A. A survey of cross-validation procedures for model selection // Statistics Surveys. — 2010. — Т. 4. — С. 40–79.
  • Shao J. Linear model selection by cross-validation // Journal of the American Statistical Association. — 1993. — Т. 88. — № 422. — С. 486–494.
  • Nadeau C., Bengio Y. Inference for the generalization error // Machine Learning. — 2003. — Т. 52. — № 3. — С. 239–281.
  • Bengio Y., Grandvalet Y. No unbiased estimator of the variance of K-fold cross-validation // Journal of Machine Learning Research. — 2004. — Т. 5. — С. 1089–1105.