Перегляд вихідного коду сторінки Похибка узагальнення

У застосуваннях [[Кероване навчання|керованого навчання]] в [[Машинне навчання|машинному навчанні]] та [[Теорія статистичного навчання|теорії статистичного навчання]], '''по́хибка узага́льнення''' ({{lang-en|generalization error}}, відома також як '''по́хибка за ме́жами ви́бірки''', {{lang-en|out-of-sample error}}<ref>Y S. Abu-Mostafa, M.Magdon-Ismail, and H.-T. Lin (2012) Learning from Data, AMLBook Press. ISBN 978-1600490064 {{ref-en}}</ref>)&nbsp;— це міра того, наскільки точно алгоритм здатен передбачувати значення виходів для не бачених раніше даних. Оскільки навчальні алгоритми обчислюються на скінченних вибірках, обчислення навчальних алгоритмів може бути чутливим до {{нп|Похибка вибірки|похибки вибірки||Sampling error}}. В результаті, вимірювання похибки передбачування на поточних даних може не давати достатньо інформації про передбачувальну здатність на даних нових. Похибку узагальнення може бути мінімізовано униканням [[перенавчання]] в навчальних алгоритмах. Продуктивність [[алгоритм]]у [[Машинне навчання|машинного навчання]] вимірюється шляхом відкладання на графіку значень похибки узагальнення протягом процесу навчання, що називається [[Крива здатності навчатися|кривими навчання]].

== Визначення == 
{{Див. також|Теорія статистичного навчання}}

В задачі навчання метою є розробка функції <math>f(x)</math>, яка передбачує вихідні значення <math>y</math> на основі деяких вхідних даних <math>x</math>. Очікуваною похибкою <math>I[f_n]</math> певної функції <math>f_n</math> над усіма можливими  значеннями <math>x</math> та <math>y</math> є

: <math> I[f_n] = \int_{X \times Y} V(f_n(x),y) \rho(x,y) dx dy, </math>

де <math>V</math> позначає [[Функція втрат|функцію втрат]], а <math>\rho(x,y)</math> є невідомим [[Спільний розподіл|спільним розподілом імовірності]] для <math>x</math> та <math>y</math>.

Не знаючи цей спільний розподіл імовірності, неможливо обчислити <math>I[f]</math>. Натомість, ми можемо обчислювати емпіричну похибку на даних вибірки. Для заданих <math>n</math> точок даних емпіричною похибкою є

: <math> I_S[f_n] = \frac{1}{n} \sum_{i=1}^n V(f_n(x_i),y_i) </math>

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

: <math> G = I[f_n] - I_S[f_n] </math>

Про алгоритм кажуть, що він узагальнюється, якщо

: <math> \lim_{n \rightarrow \infty} I[f_n] - I_S[f_n] = 0</math>

Оскільки <math>I[f_n]</math> для невідомого розподілу ймовірності обчислено бути не може, то не може бути обчислено й '''похибку узагальнення'''. Натомість, метою багатьох задач у теорії статистичного навчання є обмежити або схарактеризувати похибку узагальнення в імовірності:

: <math>
P_G = P(I[f_n] - I_S[f_n] \leq \epsilon) \geq 1 - \delta_n 
</math>

Тобто, метою є схарактеризувати ймовірність <math>1 - \delta_n</math> того, що похибка узагальнення є меншою за деяку межу похибки <math>\epsilon</math> (відому як ''темп навчання'', {{lang-en|learning rate}}, і в цілому залежну від <math>\delta</math> та <math>n</math>).

== Стосунок до стійкості ==

Для багатьох типів алгоритмів було показано, що алгоритм має межі узагальнення, якщо він відповідає певним критеріям {{нп|Стійкість (теорія навчання)|стійкості||Stability (learning theory)}}. Зокрема, якщо алгоритм є симетричним (послідовність входів не впливає на результат), має обмежені втрати та відповідає двом умовам стійкості, то він узагальнюватиметься. Перша умова стійкості, стійкість [[Перехресне затверджування з виключенням по одному|перехресного затверджування з виключенням по одному]] ({{lang-en|leave-one-out cross-validation stability}}), каже, що для стійкості похибка передбачення для кожної точки даних при застосуванні перехресного затверджування з виключенням по одному мусить збігатися до нуля при <math>n\rightarrow \infty</math>. Друга умова, стійкість похибки очікування до виключення по одному ({{lang-en|expected-to-leave-one-out error stability}}, відома також як стійкість гіпотези при дії в [[Норма L1|нормі <math>L_1</math>]]), виконується тоді, коли передбачення для не включеної точки не змінюється при усуненні однієї точки з тренувального набору.<ref name="MukherjeeEtAl">{{cite journal|first1=S.|last1=Mukherjee|first2=P.|last2=Niyogi|first3=T.|last3=Poggio|first4=R. M.|last4=Rifkin.|title=Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization.|journal=Adv. Comput. Math.|volume=25|issue=1-3|pages=161–193|year=2006|url=http://cbcl.mit.edu/publications/ps/mukherjee-ACM-06.pdf}} {{ref-en}}</ref>

Ці умови може бути формалізовано наступним чином:

=== Стійкість перехресного затверджування з виключенням по одному ===

Алгоритм <math>L</math> має стійкість <math>CVloo</math>, якщо для кожного <math>n</math> існують такі <math>\beta_{CV}^{(n)}</math> та <math>\delta_{CV}^{(n)}</math>, що

: <math>\forall i\in\{1,...,n\}, \mathbb{P}_S\{|V(f_{S^i},z_i)-V(f_S,z_i)|\leq\beta_{CV}^{(n)}\}\geq1-\delta_{CV}^{(n)}</math>

і <math>\beta_{CV}^{(n)}</math> та <math>\delta_{CV}^{(n)}</math> прямують до нуля при прямуванні <math>n</math> до нескінченності.<ref name="MukherjeeEtAl"/>

=== Стійкість похибки очікування до виключення по одному ===

Алгоритм <math>L</math> має стійкість <math>Eloo_{err}</math>, якщо для кожного <math>n</math> існують такі <math>\beta_{EL}^m</math> та <math>\delta_{EL}^m</math>, що

: <math>\forall i\in\{1,...,n\}, \mathbb{P}_S\{|I[f_S]-\frac{1}{n}\sum_{i=1}^N V(f_{S^{i}},z_i)|\leq\beta_{EL}^{(n)}\}\geq1-\delta_{EL}^{(n)}</math>

де <math>\beta_{EL}^{(n)}</math> та <math>\delta_{EL}^{(n)}</math> прямують до нуля при <math>n\rightarrow\infty</math>.

Для стійкості виключення по одному в нормі <math>L_1</math> це є тим самим, що й стійкість гіпотези

:<math> \mathbb{E}_{S,z}[|V(f_S,z) - V(f_{S^i},z)|] \leq \beta_H^{(n)} </math>

де <math>\beta_H^{(n)}</math> прямує до нуля при прямуванні <math>n</math> до нескінченності.<ref name="MukherjeeEtAl"/>

=== Алгоритми з доведеною стійкістю ===

Стосовно ряду алгоритмів було доведено, що вони є стійкими, і, в результаті, мають межі на своїх похибках узагальнення. Перелік цих алгоритмів та праць, що довели стійкість, є {{нп|Стійкі алгоритми|тут||Stability (learning theory)#Algorithms that are stable}}.

== Стосунок до перенавчання == 
{{See also|Перенавчання}}

[[Файл:RegressionOverfitting.png|thumb|Цей малюнок показує взаємозв'язок між перенавчанням та похибкою узагальнення ''I''[''f<sub>n</sub>''] - ''I<sub>S</sub>''[''f<sub>n</sub>'']. Точки даних було породжено зі співвідношення ''y'' = ''x'' із білим шумом, доданим до значень ''y''. В лівому стовпчику синім кольором показано тренувальні точки. До тренувальних даних було допасовано функцію&nbsp;— [[многочлен]] сьомого порядку. В правому стовпчику цю функцію перевіряють на даних, вибраних зі спільного розподілу ''y'' та ''x'', що лежить в основі.
У верхньому рядку функцію допасовано до вибіркового набору з 10 точок даних. У нижньому рядку функцію допасовано до вибіркового набору зі 100 точок даних. Як можна бачити, для малих розмірів вибірки та складних функцій похибка на тренувальному наборі є малою, але похибка на розподілі, що лежить в основі даних, є великою, і ми маємо перенавчання даних. В результаті похибка узагальнення є великою. Зі збільшенням числа вибіркових точок похибка передбачення на тренувальних та перевірних даних збігаються, і похибка узагальнення прямує до 0.
]]
Поняття похибки узагальнення та перенавчання тісно пов'язані. Перенавчання стається тоді, коли навчена функція <math>f_S</math> стає чутливою до шуму в вибірці. В результаті ця функція працюватиме добре на тренувальному наборі, але не працюватиме добре на інших даних зі спільного розподілу ймовірності <math>x</math> та <math>y</math>. Таким чином, що більше перенавчання стається, то більшою є похибка узагальнення.

Величину перенавчання може бути перевірено застосуванням методів [[Перехресне затверджування|перехресного затверджування]], які розділюють вибірку на імітовані тренувальні та випробувальні вибірки. Потім модель тренують на тренувальній вибірці, й оцінюють на випробувальній. Випробувальна вибірка є не баченою алгоритмом заздалегідь, і тому являє собою випадкову вибірку зі спільного розподілу ймовірності <math>x</math> та <math>y</math>. Ця випробувальна вибірка дозволяє отримувати наближення очікуваної похибки, і, як результат, отримувати наближення конкретного вигляду похибки узагальнення.

Існує багато алгоритмів для запобігання перенавчанню. Алгоритм мінімізації може штрафувати складніші функції (він відомий як [[Регуляризація (математика)|регуляризація]] Тихонова), або простір гіпотез може бути обмежено, або явно виглядом функцій, або додаванням обмежень до функції мінімізації (регуляризація Іванова).

Підхід, що полягає в пошуку функції, яка не перенавчається, суперечить меті пошуку функції, яка є достатньо складною, щоби схоплювати особливі характеристики даних. Це відоме як [[компроміс зсуву та дисперсії]]. Збереження функції простою для запобігання перенавчанню може вносити зсув в отримувані в результаті передбачування, в той час як надання їй можливості ставати складнішою веде до перенавчання й вищої дисперсії в передбаченнях. Мінімізовувати й те, і друге одночасно — неможливо.

== Примітки ==
{{Примітки}}

== Література ==
* Bousquet, O., S. Boucheron and G. Lugosi. Introduction to Statistical Learning Theory. Advanced Lectures on Machine Learning Lecture Notes in Artificial Intelligence 3176, 169-207. (Eds.) Bousquet, O., U. von Luxburg and G. Ratsch, Springer, Heidelberg, Germany (2004) {{ref-en}}
* Bousquet, O. and A. Elisseef (2002), Stability and Generalization, Journal of Machine Learning Research, 499-526. {{ref-en}}
* Devroye L. , L. Gyorfi, and G. Lugosi (1996). A Probabilistic Theory of Pattern Recognition. Springer-Verlag. ISBN  978-0387946184. {{ref-en}}
* Poggio T. and S. Smale. The Mathematics of Learning: Dealing with Data. Notices of the AMS, 2003 {{ref-en}}
* Vapnik, V. (2000). The Nature of Statistical Learning Theory. Information Science and Statistics. Springer-Verlag. ISBN 978-0-387-98780-4. {{ref-en}}
* Bishop, C.M. (1995), ''Neural Networks for Pattern Recognition'', Oxford: Oxford University Press, especially section 6.4.  {{ref-en}}
* Finke, M., and Müller, K.-R. (1994), "Estimating a-posteriori probabilities using stochastic network models," in Mozer, Smolensky, Touretzky, Elman, & Weigend, eds., ''Proceedings of the 1993 Connectionist Models Summer School'', Hillsdale, NJ: Lawrence Erlbaum Associates, pp.&nbsp;324–331.  {{ref-en}}
* Geman, S., Bienenstock, E. and Doursat, R. (1992), "Neural Networks and the Bias/Variance Dilemma", ''Neural Computation'', 4, 1-58. {{ref-en}}
* Husmeier, D. (1999), ''Neural Networks for Conditional Probability Estimation: Forecasting Beyond Point Predictions'', Berlin: Springer Verlag, ISBN 1-85233-095-3. {{ref-en}}
* McCullagh, P. and Nelder, J.A. (1989) ''Generalized Linear Models'', 2nd ed., London: Chapman & Hall. {{ref-en}}
* 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. {{ref-en}}
* Ripley, B.D. (1996) ''Pattern Recognition and Neural Networks'', Cambridge: Cambridge University Press. {{ref-en}}
* Rohwer, R., and van der Rest, J.C. (1996), "Minimum description length, regularization, and multimodal data," ''Neural Computation'', 8, 595-609. {{ref-en}}
* Rojas, R. (1996), "A short proof of the posterior probability property of classifier neural networks," ''Neural Computation'', 8, 41-43. {{ref-en}}
* White, H. (1990), "Connectionist Nonparametric Regression: Multilayer Feedforward Networks Can Learn Arbitrary Mappings," ''Neural Networks'', 3, 535-550. Reprinted in White (1992). {{ref-en}}
* White, H. (1992a), "Nonparametric Estimation of Conditional Quantiles Using Neural Networks," in Page, C. and Le Page, R. (eds.), ''Proceedings of the 23rd Sympsium on the Interface: Computing Science and Statistics'', Alexandria, VA: American Statistical Association, pp.&nbsp;190–199. Reprinted in White (1992b). {{ref-en}}
* White, H. (1992b), ''Artificial Neural Networks: Approximation and Learning Theory'', Blackwell. {{ref-en}}

{{Диференційовні обчислення}}

[[Категорія:Алгоритми класифікації]]