Ошибка внутри и вне выборки машинное обучение - Решение и исправление самых разных ошибок на TopOshibok.ru

From Wikipedia, the free encyclopedia

For supervised learning applications in machine learning and statistical learning theory, generalization error^[1] (also known as the out-of-sample error^[2] or the risk) is a measure of how accurately an algorithm is able to predict outcome values for previously unseen data. Because learning algorithms are evaluated on finite samples, the evaluation of a learning algorithm may be sensitive to sampling error. As a result, measurements of prediction error on the current data may not provide much information about predictive ability on new data. Generalization error can be minimized by avoiding overfitting in the learning algorithm. The performance of a machine learning algorithm is visualized by plots that show values of estimates of the generalization error through the learning process, which are called learning curves.

Definition[edit]

In a learning problem, the goal is to develop a function $f_{n}({\vec {x}})$ that predicts output values for each input datum ${\vec {x}}$ . The subscript indicates that the function $f_{n}$ is developed based on a data set of data points. The generalization error or expected loss or risk I[f] of a particular function over all possible values of ${\vec {x}}$ and is the expected value of the loss function $V(f)$ :^[1]

$I[f]=\int _{X\times Y}V(f({\vec {x}}),y)\rho ({\vec {x}},y)d{\vec {x}}dy,$

where $\rho ({\vec {x}},y)$ is the unknown joint probability distribution for ${\vec {x}}$ and .

Without knowing the joint probability distribution $\rho$ , it is impossible to compute I[f] . Instead, we can compute the error on sample data, which is called empirical error (or empirical risk). Given data points, the empirical error of a candidate function is:

$I_{n}[f]={\frac {1}{n}}\sum _{i=1}^{n}V(f({\vec {x}}_{i}),y_{i})$

An algorithm is said to generalize if:

$\lim _{n\rightarrow \infty }I[f]-I_{n}[f]=0$

Of particular importance is the generalization error $I[f_{n}]$ of the data-dependent function $f_{n}$ that is found by a learning algorithm based on the sample. Again, for an unknown probability distribution, $I[f_{n}]$ cannot be computed. Instead, the aim of many problems in statistical learning theory is to bound or characterize the difference of the generalization error and the empirical error in probability:

$P_{G}=P(I[f_{n}]-I_{n}[f_{n}]\leq \epsilon )\geq 1-\delta _{n}$

That is, the goal is to characterize the probability $1-\delta _{n}$ that the generalization error is less than the empirical error plus some error bound $\epsilon$ (generally dependent on $\delta$ and ).
For many types of algorithms, it has been shown that an algorithm has generalization bounds if it meets certain stability criteria. Specifically, if an algorithm is symmetric (the order of inputs does not affect the result), has bounded loss and meets two stability conditions, it will generalize. The first stability condition, leave-one-out cross-validation stability, says that to be stable, the prediction error for each data point when leave-one-out cross validation is used must converge to zero as $n\rightarrow \infty$ . The second condition, expected-to-leave-one-out error stability (also known as hypothesis stability if operating in the $L_{1}$ norm) is met if the prediction on a left-out datapoint does not change when a single data point is removed from the training dataset.^[3]

These conditions can be formalized as:

Leave-one-out cross-validation Stability[edit]

An algorithm has $CVloo$ stability if for each , there exists a $\beta _{CV}^{(n)}$ and $\delta _{CV}^{(n)}$ such that:

$\forall i\in \{1,...,n\},\mathbb {P} _{S}\{|V(f_{S^{i}},z_{i})-V(f_{S},z_{i})|\leq \beta _{CV}^{(n)}\}\geq 1-\delta _{CV}^{(n)}$

and $\beta _{CV}^{(n)}$ and $\delta _{CV}^{(n)}$ go to zero as goes to infinity.^[3]

Expected-leave-one-out error Stability[edit]

An algorithm has $Eloo_{err}$ stability if for each there exists a $\beta_{EL}^m$ and a $\delta_{EL}^m$ such that:

$\forall i\in \{1,...,n\},\mathbb {P} _{S}\left\{\left|I[f_{S}]-{\frac {1}{n}}\sum _{i=1}^{N}V\left(f_{S^{i}},z_{i}\right)\right|\leq \beta _{EL}^{(n)}\right\}\geq 1-\delta _{EL}^{(n)}$

with $\beta _{EL}^{(n)}$ and $\delta _{EL}^{(n)}$ going to zero for $n\rightarrow \infty$ .

For leave-one-out stability in the $L_{1}$ norm, this is the same as hypothesis stability:

$\mathbb {E} _{S,z}[|V(f_{S},z)-V(f_{S^{i}},z)|]\leq \beta _{H}^{(n)}$

with $\beta _{H}^{(n)}$ going to zero as goes to infinity.^[3]

Algorithms with proven stability[edit]

A number of algorithms have been proven to be stable and as a result have bounds on their generalization error. A list of these algorithms and the papers that proved stability is available here.

Relation to overfitting[edit]

This figure illustrates the relationship between overfitting and the generalization error I[f_n] — I_S[f_n]. Data points were generated from the relationship y = x with white noise added to the y values. In the left column, a set of training points is shown in blue. A seventh order polynomial function was fit to the training data. In the right column, the function is tested on data sampled from the underlying joint probability distribution of x and y. In the top row, the function is fit on a sample dataset of 10 datapoints. In the bottom row, the function is fit on a sample dataset of 100 datapoints. As we can see, for small sample sizes and complex functions, the error on the training set is small but error on the underlying distribution of data is large and we have overfit the data. As a result, generalization error is large. As the number of sample points increases, the prediction error on training and test data converges and generalization error goes to 0.

The concepts of generalization error and overfitting are closely related. Overfitting occurs when the learned function f_S becomes sensitive to the noise in the sample. As a result, the function will perform well on the training set but not perform well on other data from the joint probability distribution of and . Thus, the more overfitting occurs, the larger the generalization error.

The amount of overfitting can be tested using cross-validation methods, that split the sample into simulated training samples and testing samples. The model is then trained on a training sample and evaluated on the testing sample. The testing sample is previously unseen by the algorithm and so represents a random sample from the joint probability distribution of and . This test sample allows us to approximate the expected error and as a result approximate a particular form of the generalization error.

Many algorithms exist to prevent overfitting. The minimization algorithm can penalize more complex functions (known as Tikhonov regularization), or the hypothesis space can be constrained, either explicitly in the form of the functions or by adding constraints to the minimization function (Ivanov regularization).

The approach to finding a function that does not overfit is at odds with the goal of finding a function that is sufficiently complex to capture the particular characteristics of the data. This is known as the bias–variance tradeoff. Keeping a function simple to avoid overfitting may introduce a bias in the resulting predictions, while allowing it to be more complex leads to overfitting and a higher variance in the predictions. It is impossible to minimize both simultaneously.

References[edit]

^ ^a ^b Mohri, M., Rostamizadeh A., Talwakar A., (2018) Foundations of Machine learning, 2nd ed., Boston: MIT Press
^ Y S. Abu-Mostafa, M.Magdon-Ismail, and H.-T. Lin (2012) Learning from Data, AMLBook Press. ISBN 978-1600490064
^ ^a ^b ^c Mukherjee, S.; Niyogi, P.; Poggio, T.; Rifkin., R. M. (2006). «Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization» (PDF). Adv. Comput. Math. 25 (1–3): 161–193. doi:10.1007/s10444-004-7634-z. S2CID 2240256.

Further reading[edit]

Olivier, Bousquet; Luxburg, Ulrike; Rätsch, Gunnar, eds. (2004). Advanced Lectures on Machine Learning. Lecture Notes in Computer Science. Vol. 3176. pp. 169–207. doi:10.1007/b100712. ISBN 978-3-540-23122-6. S2CID 431437. Retrieved 10 December 2022.
Bousquet, Olivier; Elisseeff, Andr´e (1 March 2002). «Stability and Generalization». The Journal of Machine Learning Research. 2: 499–526. doi:10.1162/153244302760200704. S2CID 1157797. Retrieved 10 December 2022.
Mohri, M., Rostamizadeh A., Talwakar A., (2018) Foundations of Machine learning, 2nd ed., Boston: MIT Press.
Moody, J.E. (1992), «The Effective Number of Parameters: An Analysis of Generalization and Regularization in Nonlinear Learning Systems», in Moody, J.E., Hanson, S.J., and Lippmann, R.P., Advances in Neural Information Processing Systems 4, 847–854.
White, H. (1992b), Artificial Neural Networks: Approximation and Learning Theory, Blackwell.

Источник

В первых двух статьях мы говорили соответственно о неравенстве Хёффдинга и о том, как его можно использовать в постановке проблемы обучения. Мы увидели, что неравенство Хёффдинга нельзя было напрямую применить к проблеме обучения, иначе это было бы просто проверкой гипотезы, а не изучением и выбором лучшей гипотезы из набора гипотез. В этой статье мы получим несколько практических примеров того, как использовать две границы, прежде чем в следующей статье серии будет рассказано, как улучшить границу. В последней статье, касающейся ошибки обобщения, было разъяснено, что границу необходимо ослабить, чтобы она стала применимой к ситуациям обучения — ровно в M раз слабее, причем M — это размер набора гипотез. Это будет проиллюстрировано в этой статье на двух приведенных примерах. Начнем с неравенства, касающегося единственной гипотезы.

Проверка гипотезы

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

Это неравенство было напрямую переведено из неравенства Хёффдинга в соответствие с гипотезой. В случае, если об этом забыли, мы быстро повторим, что означают различные переменные в неравенстве:

E_in (h): выборка h, Ein (h).
E_out (h): вне выборки — это ошибка обобщения.
ε: это наша допустимая величина отклонения E_in от E_out.
N: это размер нашей выборки.
δ: это наш уровень достоверности, например, δ = 0,05 дает уровень достоверности 0,95.

Нам нужно будет переставить некоторые термины, прежде чем мы сможем использовать неравенство в нашем примере — вместо этого мы получим следующую формулу:

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

Пример единственной гипотезы

Представьте, что у вас есть данные D, которые вы разбили на две части — одну для обучения, D_train, и одну для тестирования, D_test. Каждый сплит имеет размер n_train и n_test соответственно. У вас также есть (единственная) гипотеза h, которую вы тренируете на D_train.

После этого вы вычисляете тестовые потери E_in (h, D_test) (также можно просто записать E_in (h), но мы хотим обозначить, что это именно ошибка в выборке тестового набора). Затем вы хотите проверить, насколько хорошо гипотеза будет обобщать невидимые данные, поэтому вы будете использовать тестовые потери для оценки границы потерь при обучении. Другими словами, вы получите оценку E_out (h, D_train) с учетом E_in (h, D_test) и n_test. Опять же, мы указываем, что E_out (h) относится к D_train. Наконец, мы можем вставить в формулу:

Затем мы можем представить, что у нас есть ошибка выборки 0,1, размер выборки 1000 и уровень достоверности 0,05. Мы можем вставить это в нашу формулу, а затем получить оценку:

Пример конечных гипотез

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

Изменилось только то, что теперь у нас есть набор гипотез, а не одна. E_in вычисляется для всех гипотез в наборе, и выбирается гипотеза с наименьшей ошибкой в выборке. Эта гипотеза является последней гипотезой g, которая затем будет использоваться для ограничения E_out.

Теперь мы можем взять конкретный пример. Как и раньше, у вас есть данные D, которые вы разделите на две части: одну для обучения, D_train, и одну для тестирования, D_test. Каждый сплит имеет размер n_train и n_test соответственно. Вы также нашли свою окончательную гипотезу g на основе набора гипотез H, который имеет размер M. Вы тренируете найденную гипотезу на D_train. Опять же, мы хотим вывести границу того, насколько хорошо он будет обобщен на неизвестные данные, поэтому вы будете использовать тестовые потери, чтобы оценить границу потерь при обучении. Другими словами, вы получите оценку E_out (h, D_train) с учетом Ein (h, D_test) и n_test. Мы можем вставить в формулу:

Мы снова можем вставить конкретные значения и вычислить границу — мы предполагаем, что у нас есть ошибка в выборке 0,1, размер выборки 1000 и уровень достоверности 0,05. На этот раз у нас также есть набор гипотез размером 2000.

Заключение

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

Источник

Часть 1 в основном посвящена основам машинного обучения и нескольким простым моделям.

Во второй части я объяснил следующие 3 лекции курса Обучение на основе данных. Эти 3 лекции в основном теоретические и являются самыми тяжелыми лекциями курса с точки зрения математических абстракций. Но математические результаты дают фундаментальное представление об обучении на основе данных. Даже после того, как я реализовал множество программ машинного обучения, временами я ощущаю алгоритмы машинного обучения как волшебные черные ящики, которые при загрузке данных дают потрясающие прогнозы. Но эти лекции прекрасно объясняют волшебство, происходящее внутри черных ящиков, с некоторыми ошеломляющими математическими результатами!

Лекция 6: Теория обобщения

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

Лекция 7: Измерение ВК

Проще говоря, размерность VC множества гипотез H — это наибольшее количество точек, которые H может разрушить. Поскольку в этой лекции хорошо объясняется множество математических результатов, повторять их в этой истории бессмысленно. Но в этой лекции объясняется простое использование измерения VC и неравенства VC для получения тесной границы между ошибкой внутри выборки и ошибкой вне выборки. Посмотрите эту лекцию для подробного объяснения.

Лекция 8: Компромисс смещения и дисперсии

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

Что такое предвзятость?

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

Что такое дисперсия?

Дисперсия — это изменчивость прогноза модели для данной точки данных или значения, которое говорит нам о разбросе наших данных. Модель с высокой дисперсией уделяет много внимания обучающим данным и не обобщает данные, которых она не видела раньше (переобучение).

Я проанализировал компромисс смещения и дисперсии для модели K-ближайших соседей, которую я использовал для прогнозирования Индии / не Индии по (x, y) местоположению пикселя в этом изображении, загруженном из Википедии. В качестве набора данных я использовал файл india_map.npy, созданный из вышеупомянутого изображения. Подробное объяснение и реализацию Python можно найти на этой вики-странице моего репозитория.

Как и ожидалось, с увеличением сложности модели (т.е. с увеличением k) смещение уменьшается, а дисперсия увеличивается.

Надеюсь, вам понравилась эта тяжелая математика часть машинного обучения. Скоро опубликую Часть 3. Часть 3 будет очень интересной, так как она больше фокусируется на практических реализациях. Быть в курсе!

Источник

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

Что такое переоснащение

Прежде всего, мы должны определить, что означает переоснащение в контексте моделей машинного обучения. Проще говоря, переоснащение — это когда ваша модель слишком идеально подходит для ваших данных. Как это вообще возможно? Когда мы рассматриваем наш набор данных, нам нужно помнить, что он часто не является полностью верным представлением целевой функции, стоящей за ним. Часто присутствует некоторый шум, который размывает структуру фактической целевой функции. Итак, если мы слишком хорошо подгоняем данные выборки, то вы подбираете шум так же, как истинную модель! Если это кажется немного абстрактным, мы можем объяснить это на интуитивном примере:

У нас есть 5 точек данных с низким уровнем шума, поэтому мы можем видеть, что две точки немного отклоняются от фактической целевой функции. Подбор, который мы нашли, идеально соответствует всем 5 пунктам, но он явно далек от фактической целевой функции. Что тогда будет, когда у нас появятся новые точки? Мы явно получим огромную ошибку! Другими словами, переобучение — это когда вы выбираете гипотезу с наименьшей ошибкой ввода, E_in, и это приводит к более высокой ошибке вывода, E_out, чем ожидалось. Вопрос в том, как избежать переобучения наших данных? Есть два способа избавиться от переобучения; регуляризация или использование набора для проверки. В этой статье мы рассмотрим только то, как это делается с помощью набора для проверки. Набор проверки используется для оценки E_out для модели. Посмотрим, как мы будем принимать решения на основе этой оценки.

Набор для проверки

Прежде чем мы это сделаем, мы должны сначала определить, что такое набор проверки. Если у нас есть набор данных D, мы можем разделить его на две части — обучающий набор, D_train, и набор проверки, D_val. Затем мы используем это подмножество данных для оценки ошибки вне выборки, что возможно, поскольку оно не участвовало напрямую в процессе обучения. Это может показаться обычным набором тестов, но есть одно важное отличие — он будет использоваться для принятия определенных решений в процессе обучения. Прежде чем мы поговорим об этих вариантах, поговорим немного подробнее о создании набора проверки.

Как мы уже заявляли, допустим, у нас есть набор данных D с N образцами. Мы можем разделить набор данных на две части:

D_train: обучающий набор размером (N — K).
D_val: набор для проверки с размером K. Обратите внимание, что нам не нужно брать конкретное подмножество данных, мы можем просто выбрать K случайных точек.

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

Все хорошо, что это объективная оценка ошибки вне выборки, но насколько она надежна? Мы можем представить, что это зависит от размера нашего набора для проверки, K. Давайте рассмотрим два примера, чтобы показать идею того, почему размер K так важен для надежности оценки ошибки. Давайте сначала представим, что наш набор для проверки очень мал.

Представьте, что у нас есть набор данных с размером выборки 10. Затем мы разделяем наш набор данных на две части, где наш обучающий набор будет иметь размер 9. Это означает, что набор проверки будет состоять только из одной точки. Мы не можем сказать, что одна точка даст нам хорошее представление об общей производительности нашей модели! Либо он оценивает нашу ошибку в 0% или 100%. Ясно, что маленький K — это плохо. Что же тогда произойдет, если наш K будет большим?

Представим себе противоположный сценарий: наш обучающий набор представляет собой одну точку, а набор проверки состоит из 9 точек. Набор для проверки даст хорошее представление о том, насколько хорошо работает наша гипотеза. Но поскольку у нас не так много данных для обучения, наша гипотеза, вероятно, будет хуже и приведет к ухудшению производительности вне выборки. С другой стороны, наш набор для проверки очень надежен, когда говорит нам, что производительность будет ужасной! Быстро становится ясно, что перед нами парадокс: мы хотим, чтобы K был достаточно маленьким, чтобы давать нам достаточно обучающих данных, но мы также хотим, чтобы он был достаточно большим, чтобы быть надежным.

Хорошо, что нам вообще не нужно чем-то жертвовать. Целью проверки является оценка производительности вне выборки, а E_val является хорошей оценкой E_out (g-). Хотя это хорошая оценка, это не означает, что мы должны вывести g- в качестве окончательной гипотезы. Основная цель — получить наилучшую возможную гипотезу, чтобы мы могли тренировать гипотезу для всего набора данных после оценки g- на данных проверки.

И на практике реальная ошибка вне выборки, вероятно, будет меньше расчетной, поскольку наша модель будет обучаться на большем обучающем наборе.

Выбор модели

Теперь мы поняли, как создается набор проверки — но чем он отличается от обычного набора тестов? До сих пор мы говорили только о том, как его можно использовать для оценки выбранной нами гипотезы, но его можно использовать для чего-то гораздо более захватывающего! Мы можем использовать набор проверки для выбора модели.

Представьте, что у нас есть M наборов гипотез, отсюда:

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

Затем мы можем оценить каждую из этих окончательных гипотез в нашем наборе для проверки, а затем мы хотим выбрать ту с минимальной ошибкой, E_m *. Нам нужно помнить, что это больше не беспристрастная оценка E_out, поскольку мы выбираем модель с наименьшей ошибкой — следовательно, она имеет положительное смещение. Кроме того, как и раньше, нам не нужно выводить g_m * -, но мы затем повторно обучаем его для всех данных и выводим g_m *.

Перекрестная проверка

Теперь мы поняли, как создается набор для проверки и как его можно использовать для принятия решений о том, какую гипотезу выбрать. Мы можем вернуться к дилемме относительно размера K — он должен быть маленьким или большим? Но вместо того, чтобы пытаться найти идеальное значение, мы можем выполнить перекрестную проверку. Мы сосредоточимся на конкретном случае перекрестной проверки — исключить по одному. Это частный случай K-кратной проверки, но идея та же, и ее легко визуализировать.

Перекрестная проверка без исключения

Представьте, что у нас есть набор данных D, который имеет размер выборки N. Мы хотим выполнить перекрестную проверку с исключением одного исключения для набора данных, чтобы оценить нашу окончательную гипотезу g. Есть N способов разделить данные на обучающий набор размером N — 1 и проверочный набор размером 1. В частности, мы можем сказать, что у нас есть набор данных:

после исключения точки данных (x_n, y_n), каждый раз мы тренируемся на N — 1 точке, что дает нам окончательную гипотезу g_n, и затем мы можем оценить ошибку этой гипотезы на нашем наборе проверки. Если набор для проверки представляет собой только одну точку, мы получаем оценку ошибки:

Это делается N раз, пока у нас не будет N мер ошибок, и затем мы сможем взять среднюю ошибку по всем этим оценкам ошибок:

Мы можем проиллюстрировать это следующим образом:

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

Как оказалось, наша оценка представляет собой несмещенную оценку E_out (N — 1), и мы можем ожидать, что реальный результат будет немного ниже, поскольку мы тренируем еще одну точку. Следовательно, мы имеем:

Перекрестная проверка с исключением по одному — это конкретный случай k-кратной перекрестной проверки, где k — количество точек, выбранных для исключения для проверки. Вопрос снова в том, насколько большим должно быть K? Если K слишком велико, то у нас будет большее расхождение между E_out (g) и E_out (g-). На практике часто выбирают 10-кратную перекрестную проверку.

Заключение

В этой статье мы определили, что такое переобучение — когда мы выбираем модель, которая слишком хорошо соответствует нашим данным и, таким образом, соответствует шуму в данных. Тогда это даст большую, чем ожидалось, ошибку вне выборки. Это можно исправить, используя набор для проверки, в котором мы непосредственно оцениваем ошибку вне выборки и можем сделать выбор в отношении нашей окончательной гипотезы на основе этой оцененной ошибки. Эффективным методом является использование перекрестной проверки, поскольку это объективная оценка E_out, но нам нужно подумать о том, сколько точек мы хотим сохранить для проверки — в противном случае у нас будет большее расхождение между E_out (g) и E_out ( грамм-).

Источник

В предыдущих статьях мы определили, что такое ошибка обобщения в контексте машинного обучения и как ограничить ее с помощью различных неравенств. Мы также определили переобучение и то, как его можно исправить с помощью набора для проверки. Мы могли бы избежать парадокса выбора размера для нашего набора проверки, используя перекрестную проверку, которая оказалась несмещенной оценкой для E_out (N — 1). В этой статье мы дадим несколько практических примеров того, какие неравенства использовать в случае набора проверки и перекрестной проверки.

Пример — набор для проверки

Представьте, что у нас есть набор данных D с размером выборки N = 100. Мы разбиваем наш набор данных на две части; обучающий набор размером 75 и проверочный набор размером 25. Мы хотим оценить 100 моделей, что означает, что у нас есть 100 наборов гипотез и найти модель с наилучшей производительностью на нашем проверочном наборе. Мы скажем, что все модели имеют d_VC = 10. Затем мы хотим дать верхнюю границу нашей ошибки вне выборки. Давайте сначала проиллюстрируем процесс, который нам предстоит пройти:

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

Теперь мы знаем размеры нашей новой гипотезы, которая составляет M = 100. Мы оцениваем наши гипотезы на проверочном наборе и выбираем ту с минимальной ошибкой, E_val (g_m * -). Это наша оценка E_out (g_m *) в выборке. Мы помним, что после того, как мы нашли gm *, мы тренируем гипотезу на всех данных и возвращаем модель. Поскольку мы знаем размер нашего набора гипотез, мы можем дать верхнюю границу нашей ошибки вне выборки с помощью:

Мы помним, что наша ошибка в выборке в данном случае — E_val (g_m * -), которую мы используем для привязки E_out (g_m * -). Мы выводим не gm * -, а gm *. Однако мы можем представить, что E_out (g_m *) меньше или равно E_out (g_m * -), поскольку мы будем тренировать нашу окончательную гипотезу на всем нашем наборе данных. В целом можно сказать, что у нас есть:

Важно отметить, что в этом случае N равно размеру нашего набора для проверки! Представим, что мы выбираем уровень достоверности 95%, т. Е. Δ = 0,05, и ошибку выборки 0,20. Тогда имеем следующую оценку:

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

В этом случае наш набор гипотез представляет собой объединение всех наших 100 наборов гипотез — мы не знаем, сколько их в каждом, поэтому мы не знаем М. Мы также не используем набор проверки — вместо этого мы делаем то, что каждый Модель Hm в нашем наборе гипотез дает окончательную гипотезу, и мы выбираем ту, которая имеет минимальную ошибку. Это то же самое, что выбрать окончательную гипотезу из объединения всех наших наборов гипотез — следовательно, мы не можем сказать, что это простой конечный набор гипотез. Вместо этого нам нужно найти размерность VC объединения нашей гипотезы. В итоге мы получим следующую оценку:

Мы помним, что каждый набор гипотез имеет d_VC = 10. Следовательно, нам нужно сначала вычислить границу VC для нашего набора гипотез, что можно сделать с помощью:

Допустим, наша окончательная гипотеза все еще имеет ошибку выборки 0,20. Тогда мы получим следующую оценку:

Мы ясно видим, что в первом случае граница более жесткая.

Пример — перекрестная проверка

Представьте, что у нас есть набор данных с N образцами. Вы отдаете его двум своим друзьям. Один из них применяет 5-кратное перекрестное тестирование: данные разделяются на 5 частей, а затем каждый раз, когда одна из складок резервируется для тестирования, а остальные четыре используются для обучения модели прогнозирования. Каждая из 5 складок используется для тестирования только один раз. Таким образом, ваш друг получает 5 моделей прогнозов и дает вам ту, которая имеет наименьшую ошибку теста. Другой друг применяет 10-кратное перекрестное тестирование таким же образом и возвращает вам модель с наименьшей ошибкой теста. Два друга работают независимо друг от друга. Пусть h_1 ∗ будет моделью, созданной первым другом, и E_in (h_1 *) его тестовой потерей, и пусть h_2 * будет моделью, созданной вторым другом, а E_in (h_2 *) его тестовой потерей. Мы хотим ограничить ошибку вне выборки для каждой гипотезы, выдвинутой вашими друзьями.

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

Мы помним, что E_cv — это несмещенная оценка E_out (N — K). Можно сказать, что:

Мы используем неравенство для конечного набора гипотез, где M = 5, поскольку наш первый друг выдвигает всего 5 гипотез. Наша ошибка в выборке равна E_cv. N по-прежнему равно N, поскольку все данные были использованы в сумме. Следовательно, мы имеем следующее:

Давайте теперь сделаем то же самое для друга, который реализует 10-кратную перекрестную проверку. Тогда у нас было бы:

Теперь у нас есть 10 моделей, поэтому мы получим следующую оценку:

Заключение

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

Источник