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

Устойчивость к ошибкам (обучение 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}}(x)}$ быть оракулом, который при каждом вызове возвращает пример ${\displaystyle x}$ и его правильная этикетка ${\displaystyle f(x)}$.

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

Определение:Мы говорим что ${\displaystyle f}$ эффективно обучается с помощью ${\displaystyle {\mathcal {H}}}$ в Доблестный установка, если существует алгоритм обучения ${\displaystyle {\mathcal {A}}}$ который имеет доступ к ${\displaystyle {\text{Oracle}}(x)}$ и многочлен ${\displaystyle p(\cdot ,\cdot ,\cdot ,\cdot )}$ такой, что для любого ${\displaystyle 0<\varepsilon \leq 1}$ и ${\displaystyle 0<\delta \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(x,\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(x,\eta )}$ и многочлен ${\displaystyle p(\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,size(f)\right)}$ , функция ${\displaystyle h\in {\mathcal {H}}}$ который с вероятностью удовлетворяет по крайней мере ${\displaystyle 1-\delta }$ условие ${\displaystyle error(h)\leq \varepsilon }$.

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

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

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

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

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

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

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

В модели вредоносной классификации^[9] злоумышленник генерирует ошибки, чтобы помешать алгоритму обучения. Этот параметр описывает ситуации пакет ошибок, что может произойти, если в течение ограниченного времени передающее оборудование неоднократно выходит из строя. Формально алгоритм ${\displaystyle {\mathcal {A}}}$ вызывает оракула ${\displaystyle Oracle(x,\beta )}$ который возвращает правильно помеченный пример ${\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(x,\beta )}$ и многочлен ${\displaystyle p(\cdot ,\cdot ,\cdot ,\cdot ,\cdot )}$ такой, что для любого ${\displaystyle 0<\varepsilon \leq 1}$, ${\displaystyle 0<\delta \leq 1}$ он выводит в ряде вызовов оракула, ограниченном ${\displaystyle p\left({\frac {1}{1/2-\beta _{B}}},{\frac {1}{\varepsilon }},{\frac {1}{\delta }},n,size(f)\right)}$ , функция ${\displaystyle h\in {\mathcal {H}}}$ который с вероятностью удовлетворяет по крайней мере ${\displaystyle 1-\delta }$ условие ${\displaystyle error(h)\leq \varepsilon }$.

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

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

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

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

Смотрите также

• Машинное обучение
• Сбор данных
• Наверное, примерно правильное обучение
• Состязательное машинное обучение

Рекомендации

1. Валиант, Л. Г. (август 1985 г.). Изучение дизъюнкции союзов. В IJCAI (стр. 560–566).
2. Валиант, Лесли Г. "Теория обучаемого". Сообщения ACM 27.11 (1984): 1134–1142.
3. Лэрд, П. Д. (1988). Учимся на хороших и плохих данных. Kluwer Academic Publishers.
4. Кирнс, Майкл. «Эффективное устойчивое к шуму обучение на основе статистических запросов». Журнал ACM 45.6 (1998): 983–1006.
5. Бранк, Клиффорд А. и Майкл Дж. Паццани. «Исследование устойчивых к шуму реляционных алгоритмов обучения концепции». Материалы 8-го международного семинара по машинному обучению. 1991 г.
6. Кирнс, М. Дж., И Вазирани, У. В. (1994). Введение в теорию вычислительного обучения, глава 5. MIT press.
7. Англуин Д. и Лэрд П. (1988). Учимся на шумных примерах. Машинное обучение, 2 (4), 343–370.
8. Кернс, М. (1998). [www.cis.upenn.edu/~mkearns/papers/sq-journal.pdf Эффективное устойчивое к шуму обучение на основе статистических запросов]. Журнал ACM, 45 (6), 983–1006.
9. Кирнс, М., и Ли, М. (1993). [www.cis.upenn.edu/~mkearns/papers/malicious.pdf Обучение при наличии вредоносных ошибок]. SIAM Journal on Computing, 22 (4), 807–837.
10. Гольдман, С.А., и Роберт, Х. (1991). Слоан. Сложность случайного атрибута шума. Технический отчет WUCS 91 29, Вашингтонский университет, факультет компьютерных наук.
11. Слоан, Р. Х. (1989). Теория вычислительного обучения: новые модели и алгоритмы (Докторская диссертация, Массачусетский технологический институт).