Похибка узагальнення

У застосуваннях керованого навчання в машинному навчанні та теорії статистичного навчання, по́хибка узага́льнення (англ. generalization error, відома також як по́хибка за ме́жами ви́бірки, англ. out-of-sample error^[1]) — це міра того, наскільки точно алгоритм здатен передбачувати значення виходів для не бачених раніше даних. Оскільки навчальні алгоритми обчислюються на скінченних вибірках, обчислення навчальних алгоритмів може бути чутливим до похибки вибірки^[en]. В результаті, вимірювання похибки передбачування на поточних даних може не давати достатньо інформації про передбачувальну здатність на даних нових. Похибку узагальнення може бути мінімізовано униканням перенавчання в навчальних алгоритмах. Продуктивність алгоритму машинного навчання вимірюється шляхом відкладання на графіку значень похибки узагальнення протягом процесу навчання, що називається кривими навчання.

Визначення

Див. також: Теорія статистичного навчання

В задачі навчання метою є розробка функції ${\displaystyle f(x)}$, яка передбачує вихідні значення ${\displaystyle y}$ на основі деяких вхідних даних ${\displaystyle x}$. Очікуваною похибкою ${\displaystyle I[f_{n}]}$ певної функції ${\displaystyle f_{n}}$ над усіма можливими значеннями ${\displaystyle x}$ та ${\displaystyle y}$ є

${\displaystyle I[f_{n}]=\int _{X\times Y}V(f_{n}(x),y)\rho (x,y)dxdy,}$

де ${\displaystyle V}$ позначає функцію втрат, а ${\displaystyle \rho (x,y)}$ є невідомим спільним розподілом імовірності для ${\displaystyle x}$ та ${\displaystyle y}$.

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

${\displaystyle I_{S}[f_{n}]={\frac {1}{n}}\sum _{i=1}^{n}V(f_{n}(x_{i}),y_{i})}$

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

${\displaystyle G=I[f_{n}]-I_{S}[f_{n}]}$

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

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

Оскільки ${\displaystyle I[f_{n}]}$ для невідомого розподілу ймовірності обчислено бути не може, то не може бути обчислено й похибку узагальнення. Натомість, метою багатьох задач у теорії статистичного навчання є обмежити або схарактеризувати похибку узагальнення в імовірності:

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

Тобто, метою є схарактеризувати ймовірність ${\displaystyle 1-\delta _{n}}$ того, що похибка узагальнення є меншою за деяку межу похибки ${\displaystyle \epsilon }$ (відому як темп навчання, англ. learning rate, і в цілому залежну від ${\displaystyle \delta }$ та ${\displaystyle n}$).

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

Для багатьох типів алгоритмів було показано, що алгоритм має межі узагальнення, якщо він відповідає певним критеріям стійкості^[en]. Зокрема, якщо алгоритм є симетричним (послідовність входів не впливає на результат), має обмежені втрати та відповідає двом умовам стійкості, то він узагальнюватиметься. Перша умова стійкості, стійкість перехресного затверджування з виключенням по одному (англ. leave-one-out cross-validation stability), каже, що для стійкості похибка передбачення для кожної точки даних при застосуванні перехресного затверджування з виключенням по одному мусить збігатися до нуля при ${\displaystyle n\rightarrow \infty }$. Друга умова, стійкість похибки очікування до виключення по одному (англ. expected-to-leave-one-out error stability, відома також як стійкість гіпотези при дії в нормі ${\displaystyle L_{1}}$), виконується тоді, коли передбачення для не включеної точки не змінюється при усуненні однієї точки з тренувального набору.^[2]

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

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

Алгоритм ${\displaystyle L}$ має стійкість ${\displaystyle CVloo}$, якщо для кожного ${\displaystyle n}$ існують такі ${\displaystyle \beta _{CV}^{(n)}}$ та ${\displaystyle \delta _{CV}^{(n)}}$, що

${\displaystyle \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)}}$

і ${\displaystyle \beta _{CV}^{(n)}}$ та ${\displaystyle \delta _{CV}^{(n)}}$ прямують до нуля при прямуванні ${\displaystyle n}$ до нескінченності.^[2]

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

Алгоритм ${\displaystyle L}$ має стійкість ${\displaystyle Eloo_{err}}$, якщо для кожного ${\displaystyle n}$ існують такі ${\displaystyle \beta _{EL}^{m}}$ та ${\displaystyle \delta _{EL}^{m}}$, що

${\displaystyle \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)}\}\geq 1-\delta _{EL}^{(n)}}$

де ${\displaystyle \beta _{EL}^{(n)}}$ та ${\displaystyle \delta _{EL}^{(n)}}$ прямують до нуля при ${\displaystyle n\rightarrow \infty }$.

Для стійкості виключення по одному в нормі ${\displaystyle L_{1}}$ це є тим самим, що й стійкість гіпотези

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

де ${\displaystyle \beta _{H}^{(n)}}$ прямує до нуля при прямуванні ${\displaystyle n}$ до нескінченності.^[2]

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

Стосовно ряду алгоритмів було доведено, що вони є стійкими, і, в результаті, мають межі на своїх похибках узагальнення. Перелік цих алгоритмів та праць, що довели стійкість, є тут^[en].

Стосунок до перенавчання

Див. також: Перенавчання

Цей малюнок показує взаємозв'язок між перенавчанням та похибкою узагальнення I[f_n] - I_S[f_n]. Точки даних було породжено зі співвідношення y = x із білим шумом, доданим до значень y. В лівому стовпчику синім кольором показано тренувальні точки. До тренувальних даних було допасовано функцію — многочлен сьомого порядку. В правому стовпчику цю функцію перевіряють на даних, вибраних зі спільного розподілу y та x, що лежить в основі. У верхньому рядку функцію допасовано до вибіркового набору з 10 точок даних. У нижньому рядку функцію допасовано до вибіркового набору зі 100 точок даних. Як можна бачити, для малих розмірів вибірки та складних функцій похибка на тренувальному наборі є малою, але похибка на розподілі, що лежить в основі даних, є великою, і ми маємо перенавчання даних. В результаті похибка узагальнення є великою. Зі збільшенням числа вибіркових точок похибка передбачення на тренувальних та перевірних даних збігаються, і похибка узагальнення прямує до 0.

Поняття похибки узагальнення та перенавчання тісно пов'язані. Перенавчання стається тоді, коли навчена функція ${\displaystyle f_{S}}$ стає чутливою до шуму в вибірці. В результаті ця функція працюватиме добре на тренувальному наборі, але не працюватиме добре на інших даних зі спільного розподілу ймовірності ${\displaystyle x}$ та ${\displaystyle y}$. Таким чином, що більше перенавчання стається, то більшою є похибка узагальнення.

Величину перенавчання може бути перевірено застосуванням методів перехресного затверджування, які розділюють вибірку на імітовані тренувальні та випробувальні вибірки. Потім модель тренують на тренувальній вибірці, й оцінюють на випробувальній. Випробувальна вибірка є не баченою алгоритмом заздалегідь, і тому являє собою випадкову вибірку зі спільного розподілу ймовірності ${\displaystyle x}$ та ${\displaystyle y}$. Ця випробувальна вибірка дозволяє отримувати наближення очікуваної похибки, і, як результат, отримувати наближення конкретного вигляду похибки узагальнення.

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

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