Дисперсия кратных оценок перекрестной проверки как : какова роль «устойчивости»?

37

TL, DR: кажется, что, вопреки часто повторяемым советам, перекрестная проверка «один-один-один» (LOO-CV), то естькратное CV, где(количество сгибов) равно(число обучающих наблюдений) - дает оценки ошибки обобщения, которые являются наименьшей переменной для любого, а не самой переменной, предполагая определенноеусловие устойчивости либо для модели / алгоритма, либо для набора данных, либо для обоих (я не уверен, какой правильно, так как я не очень понимаю это условие стабильности).KKNK

  • Может кто-то ясно объяснить, что именно это условие стабильности?
  • Правда ли, что линейная регрессия является одним из таких «стабильных» алгоритмов, подразумевая, что в этом контексте LOO-CV является строго лучшим выбором CV, если учитывать смещение и дисперсию оценок ошибки обобщения?

Общепринятое мнение, что выбор в кратном CV следует за компромиссом дисперсии смещения, такие более низкие значения (приближающиеся к 2) приводят к оценкам ошибки обобщения, которые имеют более пессимистическое смещение, но более низкую дисперсию, в то время как более высокие значения из (приближается ) приводят к оценкам, которые менее смещены, но с большей дисперсией. Традиционное объяснение этого явления дисперсии, увеличивающейся с , дается, пожалуй, наиболее заметно в «Элементах статистического обучения» (раздел 7.10.1):KKKKNK

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

Подразумевается, что ошибок валидации более сильно коррелированы, так что их сумма является более переменной. Эта линия рассуждений повторялась во многих ответах на этом сайте (например, здесь , здесь , здесь , здесь , здесь , здесь , здесь и здесь ), а также в различных блогах и т. Д. Однако подробный анализ практически никогда не приводится, вместо этого только интуиция или краткий набросок того, как может выглядеть анализ.N

Однако можно найти противоречивые утверждения, обычно ссылающиеся на определенное условие «стабильности», которое я на самом деле не понимаю. Например, в этом противоречивом ответе цитируются пара абзацев из статьи 2015 года, в которой, среди прочего, говорится: «Для моделей / процедур моделирования с низкой нестабильностью LOO часто имеет наименьшую изменчивость» (выделение добавлено). Эта статья (раздел 5.2), похоже, согласна с тем, что LOO представляет наименее переменный выбор если модель / алгоритм «стабильны». Принимая даже другую позицию по этому вопросу, есть и эта статья (следствие 2), который говорит , что «Дисперсия кратной кросс проверки [...] не зависит отKkk, снова ссылаясь на определенное условие «стабильности».

Объяснение того, почему LOO может быть самой переменной кратным CV, достаточно интуитивно понятно , но есть обратная интуиция. Окончательная оценка CV средней квадратической ошибки (MSE) является средним значением оценок MSE в каждой кратности. Таким образом, когда увеличивается до , оценка CV является средним для возрастающего числа случайных величин. И мы знаем, что дисперсия среднего уменьшается с числом усредняемых переменных. Таким образом, для того, чтобы LOO была самой переменной кратной CV, должно быть верно, что увеличение дисперсии из-за повышенной корреляции между оценками MSE перевешивает уменьшение дисперсии из-за того, что большее число сгибов усредняется поKKNK, И совсем не очевидно, что это правда.

Задумавшись обо всем этом, я решил провести небольшую симуляцию для случая линейной регрессии. Я имитируемый 10000 наборов данных с = 50 и 3 некоррелированных предикторами, каждый раз оценкой ошибки обобщения с использованием -кратного резюме с = 2, 5, 10, или 50 = . Код R здесь. Вот результирующие средние и отклонения оценок CV по всем 10000 наборов данных (в единицах MSE):NKKN

         k = 2 k = 5 k = 10 k = n = 50
mean     1.187 1.108  1.094      1.087
variance 0.094 0.058  0.053      0.051

Эти результаты показывают ожидаемую закономерность того, что более высокие значения приводят к менее пессимистическому смещению, но также, по-видимому, подтверждают, что дисперсия оценок CV самая низкая, а не самая высокая, в случае LOO.K

Таким образом, представляется, что линейная регрессия является одним из «стабильных» случаев, упомянутых в вышеприведенных работах, где увеличение связано с уменьшением, а не с увеличением дисперсии в оценках CV. Но я до сих пор не понимаю:K

  • Что именно это условие "стабильности"? Применимо ли это к моделям / алгоритмам, наборам данных или к обоим в некоторой степени?
  • Есть ли интуитивный способ думать об этой стабильности?
  • Каковы другие примеры стабильных и нестабильных моделей / алгоритмов или наборов данных?
  • Достаточно ли безопасно предположить, что большинство моделей / алгоритмов или наборов данных являются «стабильными» и, следовательно, что обычно следует выбирать настолько высоким, насколько это возможно в вычислительном отношении?K
Джейк Уэстфолл
источник
1
+1. Что именно означает «среднее» в ваших результатах моделирования? Средняя оценка CV ошибки обобщения (средняя по 10000 наборам данных)? Но с чем мы должны это сравнить? Было бы более целесообразно показать смещение, то есть среднеквадратичное отклонение от истинной ошибки обобщения. Кроме того, что является «истинной ошибкой обобщения» в этом случае? Истинная ошибка обобщения оценки для данного набора данных N = 100? Или ожидаемое значение истинной ошибки обобщения (ожидаемое значение для всех N = 100 наборов данных)? Или что-то другое?
говорит амеба: восстанови Монику
3
+1. После короткого взгляда на en.wikipedia.org/wiki/… кажется, что в этом контексте стабильность означает, что алгоритм дает аналогичные результаты в обучающем наборе с и N - 1 примерами. Где подобное означает разницу между некоторой функцией потерь, ограниченной каким-то низким значениемNN1
Лукаш Град
1
Кроме того, я недавно говорил об этом с @DikranMarsupial (который, вероятно, является одним из наших главных экспертов по перекрестной проверке здесь, в резюме) здесь, в комментариях - он предложил прочитать статью Кохави 1995 года . Дикран также говорил о стабильности. К сожалению, я не следил за этим с тех пор.
говорит амеба: восстанови Монику
2
Я так не думаю, @ Джейк. То, что я написал, лишает законной силы вашу «контр-интуицию», но основная «интуиция» (в которой модели из разных сгибов сильно зависят) все еще может сохраняться.
говорит амеба, восстанови Монику
1
Еще одно моделирование, подтверждающее ваши выводы о том, что дисперсия уменьшается с помощью : stats.stackexchange.com/a/357749/28666 . K
говорит амеба: восстанови Монику

Ответы:

15

Этот ответ дополняет мой ответ в предвзятости и дисперсии в перекрестной проверке с пропуском по сравнению с K-кратным, в которой обсуждается, почему LOOCV не всегда приводит к более высокой дисперсии. Следуя аналогичному подходу, я попытаюсь выделить случай, когда LOOCV действительно приводит к более высокой дисперсии в присутствии выбросов и "нестабильной модели".

Алгоритмическая устойчивость (теория обучения)

Тема алгоритмической стабильности является недавней, и за последние 20 лет были доказаны несколько классических, влиятельных результатов. Вот несколько статей, которые часто цитируются

Лучшая страница для понимания - это страница википедии, которая дает отличное резюме, написанное, предположительно, очень хорошо осведомленным пользователем.

Интуитивное определение стабильности

Интуитивно понятно, что стабильный алгоритм - это алгоритм, для которого предсказание не сильно меняется, когда данные обучения немного изменены.

Формально существует полдюжины версий стабильности, связанных между собой техническими условиями и иерархиями, см. Этот график, например, здесь :

enter image description here

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

нотация

Следующее примечание взято из статьи в Википедии, которая сама копирует статью Буске и Элиссеефа:

  • Обучающее множество взят из неизвестного распределения DS={z1=(x1,y1),...,zm=(xm,ym)}
  • Функция потерь гипотезы f относительно примера z определяется как V ( f , z )VfzV(f,z)
  • Мы модифицируем тренировочный набор, удаляя элемент: S | я = { г 1 , . , , , Г я - 1 , г я + 1 , . , , , z m }iS|i={z1,...,zi1,zi+1,...,zm}
  • Или путем замены на -й элемент: S я = { г 1 , . , , , z i - 1 , ziSi={z1,...,zi1,zi,zi+1,...,zm}

Формальные определения

Возможно, самым сильным понятием стабильности, которому может следовать интересный алгоритм обучения, является равномерная стабильность :

Равномерная устойчивость Алгоритм имеет равномерную устойчивость отношению к функции потерь V, если выполняется следующее:βV

SZm  i{1,...,m},  sup|V(fs,z)V(fS|i,z)|  β

Рассматриваемый как функция , термин β можно записать как β m . Мы говорим, что алгоритм стабилен, когда β m уменьшается как 1mββmβm . Несколько более слабая форма стабильности:1m

Гипотеза стабильности

i{1,...,m},  E[ |V(fs,z)V(fS|i,z)| ] β

Если одна точка удалена, разница в результатах алгоритма обучения измеряется усредненной абсолютной разницей потерь ( норма ). Интуитивно понятно: небольшие изменения в выборке могут привести только к тому, что алгоритм перейдет к близким гипотезам.L1

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

Некоторые примеры устойчивых алгоритмов

Следующие алгоритмы были показаны как стабильные и доказали границы обобщения:

  • Регуляризованная регрессия наименьших квадратов (с соответствующей предварительной)
  • Классификатор КНН с функцией потерь 0-1
  • SVM с ограниченным ядром и большой константой регуляризации
  • Мягкая маржа SVM
  • Алгоритм минимальной относительной энтропии для классификации
  • A version of bagging regularizers

An experimental simulation

Repeating the experiment from the previous thread (see here), we now introduce a certain ratio of outliers in the data set. In particular:

  • 97% of the data has [.5,.5] uniform noise
  • 3% of the data with [20,20] uniform noise

As the 3 order polynomial model is not regularized, it will be heavily influenced by the presence of a few outliers for small data sets. For larger datasets, or when there are more outliers, their effect is smaller as they tend to cancel out. See below for two models for 60 and 200 data points.

enter image description here

Выполнение симуляции, как и ранее, и построение графика среднего MSE и дисперсии MSE дает результаты, очень похожие на эксперимент 2 из статьи Bengio & Grandvalet 2004 .

Левая сторона : нет выбросов. Правая сторона : 3% выбросов.

enter image description here

enter image description here

(см. связанный документ для объяснения последнего рисунка)

Пояснения

Цитирование ответа Ив Grandvalet в другой теме:

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

In practice it is quite difficult to simulate an increase in variance due to LOOCV. It requires a particular combination of instability, some outliers but not too many, and a large number of iterations. Perhaps this is expected since linear regression has been shown to be quite stable. An interesting experiment would be to repeat this for higher dimensional data and a more unstable algorithm (e.g. decision tree)

Xavier Bourret Sicotte
источник
+1 but I'd hope this thread can eventually be closed as the duplicate of the linked one (I'd wait until the bounty period is over and the discussions subdue, and see what answer ends up being accepted). I'll comment more later.
amoeba says Reinstate Monica
I'm not really convinced the question is a duplicate. My question uses the variance of LOO issue primarily as a way to frame the main questions, which are about trying to get an approachable explanation of what "stability" means -- see the bullet-pointed questions at the top and bottom of the OP. Speaking of which, while this answer is useful (+1), I can't see that you attempted to answer the stability questions... you do use the term a couple of times, but you seem to do so in a way that assumes the reader already knows what it means. Not sure I can accept the answer in its current form.
Jake Westfall
1
@JakeWestfall When I wrote that I "hope" that this thread can eventually be closed as a duplicate, I meant that I hope that an accepted answer in that thread will eventually be great enough that it will cover the things that you asked about :) Take a look at the Bengio&Grandvalet paper, Experiment 2. They show that using linear regression and Gaussian data they get minimum variance for LOOCV (that's your result too), but if the data contain some fraction of outliers then LOOCV has higher variance than 10-fold or so. I think this hints to what the relevant "stability" is about.
amoeba says Reinstate Monica
3
I love it @XavierBourretSicotte. Thanks for doing such great work on this answer.
Jake Westfall
1
Yes, quoting this paper: pdfs.semanticscholar.org/bf83/…: "A stable algorithm has the property that replacing one element in its learning set does not change much its outcome. As a consequence, the empirical error, if thought as a random variable, should have a small variance. Stable algorithms can then be good candidates for their empirical error to be close to their generalization error.
Xavier Bourret Sicotte
2

I will give my answer in context of the paragraph you cite:

With K=N, the cross-validation estimator is approximately unbiased for the true (expected) prediction error, but can have high variance because the N "training sets" are so similar to one another.

The CV estimator of the true (expected) prediction error is based on a training set example, so here, the expectation is over training set samples, when I understand that correctly.

So, what this paragraph regarding "high variance" then says is that there is a "high" difference between expected error and the error estimated by CV (which is here, the average over folds).

This makes sense because the model is fit to a particular training set and because all training folds are so similar within leave-one-out. However, while the training folds are very similar within a CV round, the estimate probably differs by a lot if we swap training samples for CV. In k-fold CV, since we "diversify" the training folds, we have some averaging affect, and across k-folds, the estimates then vary less.

Or in other words, the leave-one-out CV estimator is basically almost like a holdout method were you don't rotate folds and base your error estimate on one validation set. Again, over training examples, there will be a high variance compared to estimates from k-fold, where you average over folds by already training somewhat diverse models within k-fold round (in other words, if you swap training sets, the estimates of the error via k-fold probably won't vary that much).

EDIT:

When I read some answers here on cross-validated and the internet in general, I think there seems some confusion to which estimator we are referring. I think some people refer to a model having high variance (with is ML talk for the loss having a dominating variance component) vs high variance of the k-fold CV estimator. And, another set of answers refer to variance as the sample variance regarding the folds when someone says "k-fold has high variance". So, I suggest to be specific, because the answers are different in either case.


источник
When discussing variance my assumption is that we are talking about the variance of the CV estimator on training set D as defined here: stats.stackexchange.com/questions/365224/… and here: stats.stackexchange.com/questions/325123/…. Yves Grandvalet and Bengio argue in their 2004 paper that the CV estimates the expected prediction error. You can see his response here: stats.stackexchange.com/a/358138/192854
Xavier Bourret Sicotte
If you are to base your answer on different definitions of variance, I think it would be helpful to add the formal definitions and formulas. Perhaps I should do so in my answers as well..
Xavier Bourret Sicotte
Yes, I need to review the literature a bit and should add some formulas to the answer. The quote from the The Elements of Statistical Learning is still intuitive to me though, that LOOCV has a high variance if the model has a high variance, because it is an average over the folds. If a model has high bias, both LOOCV and any k-fold estimators should have low variance (independent of bias) because the predictions will not vary so much. But the point in the paragraph was prob. that LOOCV in comparison to k-fold for most cases
The quote has been shown to be incorrect - at least as a generalization - see the multiple papers quoted in my answers
Xavier Bourret Sicotte
1

We've been through this before -- you're getting too mathematical about a dead horse. See Ron Kohavi's (Stanford-Univ) classic paper on CV and the bias-variance dilemma here. When you're done reading this, you won't want to perform LOOCV, and will likely be attracted to 10-fold CV and/or bootstrap-bias CV.

You also have to think about large datasets, for which LOOCV is way too computationally expensive. At present, LOOCV is not really an option in most groups' workflows/pipelines.

What precisely is this "stability" condition? Does it apply to models/algorithms, datasets, or both to some extent?

In the universe of all cost functions and in the universe of all feature sets, I would not assume there is an overall "stability" index, because it would not be inadmissible, and would be too prone to breaking down under an infinitely large set of conditions. Fundamentally, k=n is appropriate when the d.f. and/or # parameters is so large that more training data are needed. Bias will also be greater for k=n, since more data are used, and variance would be artificially zero, since the training datasets are too similar to one another. You would also be learning more noise in the data when k=n.

LREG as a classifier would work when the data are linearly separable, but on average its bias would be too high, since many datasets are not linearly separable.

Is there an intuitive way to think about this stability?

Not in my view -- since there is no general rule on stability.

What are other examples of stable and unstable models/algorithms or datasets?

This is open-ended and too broad, since an infinitely large number of responses can be contrived, which would not be helpful.

Is it relatively safe to assume that most models/algorithms or datasets are "stable" and therefore that K should generally be chosen as high as is computationally feasible?

No. No. Relying only on k assumes that you believe the data. An example is Random Forests, for which there really is no k. While roughly 37% of the data will be used for testing (on average, 37% of objects are not selected when sampling with replacement), there are e.g. 5,000 different datasets (bootstraps) each of which are split into training/testing differently. Your example pulled from papers assumed that each dataset used was a true realization of the data -- which is an erroneous assumption.

Given bootstrapping, the rule of stability surrounding k is admissible, since the data sample used for a straightforward CV approach involving k is not a true realization of the universe of all data from which the sample was obtained.

JoleT
источник
Thanks for your comments, but this does not seem to answer the question.
Jake Westfall
See the appended answer to the OP.
JoleT
3
Only skimmed the article, but they really seem to make their claim about 10x being best on extremely shaky ground. I can't believe that has 7k citations. With that said, there seems good reason to believe there's much benefit to more than 10x. Will give a more thorough reading when I have a chance.
Cliff AB