Устойчивость к ошибкам (обучение PAC)

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

Нотация и модель обучения Valiant

Далее пусть ${ displaystyle X}$ будь нашим ${ displaystyle n}$ -мерное пространство ввода. Позволять ${ displaystyle { mathcal {H}}}$ быть классом функций, которые мы хотим использовать, чтобы изучить ${ displaystyle {0,1 }}$ -значная целевая функция ${ displaystyle f}$ определяется по ${ displaystyle X}$ . Позволять ${ Displaystyle { mathcal {D}}}$ быть распределением входов по ${ displaystyle X}$ . Цель алгоритма обучения ${ displaystyle { mathcal {A}}}$ выбрать лучшую функцию ${ displaystyle h in { mathcal {H}}}$ так что это минимизирует ${ displaystyle error (h) = P_ {x sim { mathcal {D}}} (h (x) neq f (x))}$ . Предположим, у нас есть функция ${ displaystyle size (f)}$ который может измерить сложность ${ displaystyle f}$ . Позволять ${ displaystyle { text {Oracle}} (х)}$ быть оракулом, который при каждом вызове возвращает пример ${ displaystyle x}$ и его правильная этикетка ${ displaystyle f (x)}$ .

Когда никакой шум не искажает данные, мы можем определить обучение в среде Valiant:^[1]^[2]

Определение:Мы говорим что ${ displaystyle f}$ эффективно обучается с помощью ${ displaystyle { mathcal {H}}}$ в Доблестный установка, если существует алгоритм обучения ${ displaystyle { mathcal {A}}}$ который имеет доступ к ${ displaystyle { text {Oracle}} (х)}$ и многочлен ${ Displaystyle р ( CDOT, CDOT, CDOT, CDOT)}$ такой, что для любого ${ Displaystyle 0 < varepsilon leq 1}$ и ${ Displaystyle 0 < дельта leq 1}$ он выводит в ряде вызовов оракула, ограниченном ${ displaystyle p left ({ frac {1} { varepsilon}}, { frac {1} { delta}}, n, { text {size}} (f) right)}$ , функция ${ displaystyle h in { mathcal {H}}}$ который с вероятностью удовлетворяет по крайней мере ${ displaystyle 1- delta}$ условие ${ displaystyle { text {error}} (h) leq varepsilon}$ .

Далее мы определим обучаемость ${ displaystyle f}$ когда данные претерпели некоторые изменения.^[3]^[4]^[5]

Классификация шума

В модели шума классификации^[6] а уровень шума ${ displaystyle 0 leq eta <{ frac {1} {2}}}$ вводится. Тогда вместо ${ displaystyle Oracle (x)}$ который всегда возвращает правильную метку примера ${ displaystyle x}$ , алгоритм ${ displaystyle { mathcal {A}}}$ может вызвать только ошибочного оракула ${ Displaystyle Oracle (х, eta)}$ это перевернет этикетку ${ displaystyle x}$ с вероятностью ${ displaystyle eta}$ . Как и в случае с Valiant, цель алгоритма обучения ${ displaystyle { mathcal {A}}}$ выбрать лучшую функцию ${ displaystyle h in { mathcal {H}}}$ так что это минимизирует ${ displaystyle error (h) = P_ {x sim { mathcal {D}}} (h (x) neq f (x))}$ . В приложениях трудно получить доступ к реальной стоимости ${ displaystyle eta}$ , но мы предполагаем, что у нас есть доступ к его верхней границе ${ displaystyle eta _ {B}}$ .^[7] Обратите внимание, что если мы допустим уровень шума ${ displaystyle 1/2}$ , то обучение становится невозможным при любом количестве времени вычислений, потому что каждая метка не несет информации о целевой функции.

Определение:Мы говорим что ${ displaystyle f}$ эффективно обучается с помощью ${ displaystyle { mathcal {H}}}$ в модель шума классификации если существует алгоритм обучения ${ displaystyle { mathcal {A}}}$ который имеет доступ к ${ Displaystyle Oracle (х, eta)}$ и многочлен ${ Displaystyle р ( CDOT, CDOT, CDOT, CDOT)}$ такой, что для любого ${ displaystyle 0 leq eta leq { frac {1} {2}}}$ , ${ Displaystyle 0 Leq varepsilon Leq 1}$ и ${ Displaystyle 0 Leq Delta Leq 1}$ он выводит в ряде вызовов оракула, ограниченном ${ displaystyle p left ({ frac {1} {1-2 eta _ {B}}}, { frac {1} { varepsilon}}, { frac {1} { delta}}, n, размер (f) справа)}$ , функция ${ displaystyle h in { mathcal {H}}}$ который с вероятностью удовлетворяет по крайней мере ${ displaystyle 1- delta}$ условие ${ displaystyle error (h) leq varepsilon}$ .

Статистическое изучение запросов

Статистическое изучение запросов^[8] это своего рода активное изучение проблема, в которой алгоритм обучения ${ displaystyle { mathcal {A}}}$ может решить, запрашивать ли информацию о вероятности ${ Displaystyle P_ {е (х)}}$ что функция ${ displaystyle f}$ правильно маркирует пример ${ displaystyle x}$ , и получает ответ с точностью в пределах допуска ${ displaystyle alpha}$ . Формально, когда алгоритм обучения ${ displaystyle { mathcal {A}}}$ вызывает оракул ${ Displaystyle Oracle (х, альфа)}$ , он получает как вероятность обратной связи ${ Displaystyle Q_ {е (х)}}$ , так что ${ Displaystyle Q_ {е (х)} - альфа leq P_ {е (х)} leq Q_ {е (х)} + альфа}$ .

Определение:Мы говорим что ${ displaystyle f}$ эффективно обучается с помощью ${ displaystyle { mathcal {H}}}$ в модель обучения статистическим запросам если существует алгоритм обучения ${ displaystyle { mathcal {A}}}$ который имеет доступ к ${ Displaystyle Oracle (х, альфа)}$ и многочлены ${ Displaystyle р ( cdot, cdot, cdot)}$ , ${ Displaystyle д ( cdot, cdot, cdot)}$ , и ${ Displaystyle г ( CDOT, CDOT, CDOT)}$ такой, что для любого ${ Displaystyle 0 < varepsilon leq 1}$ справедливо следующее:

${ Displaystyle Oracle (х, альфа)}$ можно оценить ${ Displaystyle P_ {е (х)}}$ во время ${ displaystyle q left ({ frac {1} { varepsilon}}, n, размер (f) right)}$ ;
${ displaystyle { frac {1} { alpha}}}$ ограничен ${ displaystyle r left ({ frac {1} { varepsilon}}, n, размер (f) right)}$
${ displaystyle { mathcal {A}}}$ выводит модель ${ displaystyle h}$ такой, что ${ displaystyle err (h) < varepsilon}$ , в ряде обращений к оракулу, ограниченному ${ displaystyle p left ({ frac {1} { varepsilon}}, n, размер (f) right)}$ .

Обратите внимание, что параметр достоверности ${ displaystyle delta}$ не фигурирует в определении обучения. Это потому, что основная цель ${ displaystyle delta}$ заключается в том, чтобы позволить алгоритму обучения небольшую вероятность отказа из-за нерепрезентативной выборки. С этого момента ${ Displaystyle Oracle (х, альфа)}$ всегда гарантирует соответствие критерию приближения ${ Displaystyle Q_ {е (х)} - альфа leq P_ {е (х)} leq Q_ {е (х)} + альфа}$ , вероятность отказа больше не нужна.

Модель статистических запросов строго слабее, чем модель PAC: любой класс, эффективно обучаемый SQ, может эффективно обучаться PAC при наличии шума классификации, но существуют эффективные проблемы, которые можно изучить с помощью PAC, такие как паритет которые не могут быть эффективно обучены SQ.^[8]

Вредоносная классификация

В модели вредоносной классификации^[9] злоумышленник генерирует ошибки, чтобы помешать алгоритму обучения. Этот параметр описывает ситуации пакет ошибок, что может произойти, если в течение ограниченного времени передающее оборудование неоднократно выходит из строя. Формально алгоритм ${ displaystyle { mathcal {A}}}$ вызывает оракула ${ Displaystyle Oracle (х, бета)}$ который возвращает правильно помеченный пример ${ displaystyle x}$ взяты, как обычно, из раздачи ${ Displaystyle { mathcal {D}}}$ над входным пространством с вероятностью ${ displaystyle 1- beta}$ , но он возвращается с вероятностью ${ displaystyle beta}$ пример взят из дистрибутива, не относящегося к ${ Displaystyle { mathcal {D}}}$ . Более того, этот злонамеренно выбранный пример может быть стратегически выбран противником, который знает ${ displaystyle f}$ , ${ displaystyle beta}$ , ${ Displaystyle { mathcal {D}}}$ , или текущий прогресс алгоритма обучения.

Определение:Учитывая границу ${ displaystyle beta _ {B} <{ frac {1} {2}}}$ за ${ displaystyle 0 leq beta <{ frac {1} {2}}}$ мы говорим, что ${ displaystyle f}$ эффективно обучается с помощью ${ displaystyle { mathcal {H}}}$ в модели вредоносной классификации, если существует алгоритм обучения ${ displaystyle { mathcal {A}}}$ который имеет доступ к ${ Displaystyle Oracle (х, бета)}$ и многочлен ${ Displaystyle п ( CDOT, CDOT, CDOT, CDOT, CDOT)}$ такой, что для любого ${ Displaystyle 0 < varepsilon leq 1}$ , ${ Displaystyle 0 < дельта leq 1}$ он выводит в ряде вызовов оракула, ограниченном ${ displaystyle p left ({ frac {1} {1 / 2- beta _ {B}}}, { frac {1} { varepsilon}}, { frac {1} { delta}} , n, размер (f) right)}$ , функция ${ displaystyle h in { mathcal {H}}}$ который с вероятностью удовлетворяет по крайней мере ${ displaystyle 1- delta}$ условие ${ displaystyle error (h) leq varepsilon}$ .

Ошибки во входных данных: неоднородный шум случайных атрибутов

В неоднородном шуме случайных атрибутов^[10]^[11] модель, которую алгоритм изучает Логическая функция, злой оракул ${ Displaystyle Oracle (х, ню)}$ может перевернуть каждый ${ displaystyle i}$ -й бит примера ${ displaystyle x = (x_ {1}, x_ {2}, ldots, x_ {n})}$ независимо с вероятностью ${ Displaystyle ню _ {я} leq nu}$ .

Этот тип ошибки может непоправимо помешать алгоритму, на самом деле имеет место следующая теорема:

В настройке неоднородного шума случайных атрибутов алгоритм ${ displaystyle { mathcal {A}}}$ может выводить функцию ${ displaystyle h in { mathcal {H}}}$ такой, что ${ displaystyle error (h) < varepsilon}$ только если ${ Displaystyle Nu <2 varepsilon}$ .

Устойчивость к ошибкам (обучение PAC) - Error tolerance (PAC learning)

Содержание