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

Часть серии по
Машинное обучение и интеллектуальный анализ данных
Проблемы Классификация Кластеризация Регресс Обнаружение аномалий AutoML Правила ассоциации Обучение с подкреплением Структурированный прогноз Функциональная инженерия Особенности обучения Онлайн обучение Полу-контролируемое обучение Обучение без учителя Учимся ранжировать Введение в грамматику
Обучение с учителем ( классификация  • регрессия ) Деревья решений Ансамбли Упаковка Повышение Случайный лес k -NN Линейная регрессия Наивный байесовский Искусственные нейронные сети Логистическая регрессия Перцептрон Вектор релевантности (RVM) Машина опорных векторов (SVM)
Кластеризация БЕРЕЗА ИЗЛЕЧИВАТЬ Иерархический k -средство Ожидание – максимизация (EM) DBSCAN ОПТИКА Средний сдвиг
Снижение размерности Факторный анализ CCA ICA LDA NMF PCA PGD t-SNE
Структурированный прогноз Графические модели Сеть Байеса Условное случайное поле Скрытый Марков
Обнаружение аномалий k -NN Фактор местного выброса
Искусственная нейронная сеть Автоэнкодер Когнитивные вычисления Глубокое обучение DeepDream Многослойный перцептрон RNN LSTM ГРУ ESN Ограниченная машина Больцмана GAN SOM Сверточная нейронная сеть U-Net Трансформатор Пиковая нейронная сеть Мемтранзистор Электрохимическая RAM (ECRAM)
Обучение с подкреплением Q-обучение SARSA Временная разница (TD)
Теория Компромисс смещения и дисперсии Теория вычислительного обучения Минимизация эмпирического риска Обучение Оккама PAC обучение Статистическое обучение Теория ВК
Площадки для машинного обучения NeurIPS ICML ML JMLR ArXiv: cs.LG
Статьи по Теме Глоссарий искусственного интеллекта Список наборов данных для исследований в области машинного обучения Краткое описание машинного обучения
v т е

Устойчивость к ошибкам (обучение 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]}

Определение: мы говорим, что это можно эффективно изучить, используя в настройке Valiant, если существует алгоритм обучения, который имеет доступ, и многочлен такой, что для любого и он выводит в ряде вызовов оракула, ограниченного , функцию, которая удовлетворяет с вероятность хотя бы условие .${\ 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 }$

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

Классификационный шум [ править ]

В модели шума классификации ^[6] вводится коэффициент шума . Тогда вместо того, чтобы всегда возвращать правильную метку примера , алгоритм может вызвать только неисправный оракул , который с вероятностью перевернет метку . Как и в случае с Valiant, цель алгоритма обучения - выбрать лучшую функцию , минимизирующую ее . В приложениях трудно получить доступ к реальному значению , но мы предполагаем, что у нас есть доступ к его верхней границе . ^[7] Обратите внимание, что если мы допустим уровень шума${\displaystyle 0\leq \eta <{\frac {1}{2}}}$${\displaystyle Oracle(x)}$${\displaystyle x}$${\displaystyle {\mathcal {A}}}$${\displaystyle Oracle(x,\eta )}$${\displaystyle x}$${\displaystyle \eta }$${\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}}$${\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}}}$

Определение: Учитывая связанный для , мы говорим , что это эффективно изучаемым с использованием в злонамеренной модели классификации, если существует алгоритм обучения , который имеет доступ к и полиному такого , что для любого , он выводит, в ряде обращений к оракулу ограничено by , функция, которая с вероятностью удовлетворяет, по крайней мере, условию .${\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 }$

См. Также [ править ]

Ссылки [ править ]