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

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

Обозначения и модель обучения Valiant

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

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

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

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

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

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

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

Обучение статистическим запросам

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

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

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

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

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

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

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

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

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

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

Ошибки такого типа могут непоправимо нарушить работу алгоритма; фактически справедлива следующая теорема:

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

См. также

Ссылки

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

[1] Валиант, LG (август 1985 г.). Обучение расчленению союзов . В IJCAI (стр. 560–566).

[2] Валиант, Лесли Г. «Теория обучаемого». Сообщения ACM 27.11 (1984): 1134–1142.

[3] Лэрд, PD (1988). Обучение на хороших и плохих данных . Академическое издательство Клювер.

[4] Кернс, Майкл. « Эффективное устойчивое к шуму обучение на основе статистических запросов. Архивировано 3 мая 2013 г. в Wayback Machine ». Журнал ACM 45.6 (1998): 983–1006.

[5] Бранк, Клиффорд А. и Майкл Дж. Паццани. « Исследование шумоустойчивых алгоритмов обучения реляционных концепций ». Материалы 8-го международного семинара по машинному обучению. 1991.

[kv-6] Кернс, М.Дж., и Вазирани, У.Ф. (1994). Введение в теорию компьютерного обучения , глава 5. MIT Press.

[7] Англуин Д. и Лэрд П. (1988). Обучение на шумных примерах . Машинное обучение, 2(4), 343–370.

[kearns-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). Теория вычислительного обучения: Новые модели и алгоритмы (Докторская диссертация, Массачусетский технологический институт).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]