Агностическое обучение по произвольным распределениям

$D$ $\{0,1\}^d\times \{0,1\}$ $C$ $f:\{0,1\}^d\rightarrow\{0,1\}$ $f \in C$

e r r (f, D) = \underset{(x, y) \sim D}{Pr} [f (x) \neq y]

$err(f,D) = \Pr_{(x,y) \sim D}[f(x) \neq y]$

O P T (C, D) = min_{f \in C} e r r (f, D)

$OPT(C,D) = \min_{f \in C}\ err(f,D)$ Скажем, что алгоритм независимо изучает по любому распределению, если для любого он может с вероятностью найти функцию такую, что , с учетом времени и число выборок из , ограниченное полиномом от и .

A

$A$

C

$C$

D

$D$

2 / 3

$2/3$

f

$f$

e r r (f, D) \leq O P T (C, D) + ϵ

$err(f,D) \leq OPT(C,D) + \epsilon$

D

$D$

d

$d$

1 / ϵ

$1/\epsilon$

Вопрос: Какие классы функций как известно, являются агностически обучаемыми по произвольным распределениям? $C$

Ни один класс не слишком прост! Я знаю, что даже монотонные соединения, как известно, не могут быть изучены агностически в произвольных распределениях, поэтому я просто ищу нетривиальные классы функций.

reference-request machine-learning lg.learning Аарон Рот
источник

Стоит отметить для непосвященных, что агностическое обучение сосредоточено на том случае, когда OPT (C, D)> 0 (т.е. у вас неправильный класс гипотез

Суреш Венкат

Хорошая точка зрения. В особом случае, когда OPT (C, D) = 0, это обучение PAC, и это намного проще. Для агностического обучения гарантия должна действовать независимо от того, что такое OPT (C, D).

Аарон Рот

Есть также случай «PAC w / Classification Noise», где OPT (C, D)> 0, и хотя у вас есть правильный класс гипотез (реализуемый параметр), есть некоторая ошибка, потому что метки случайно меняются из-за шума ... I хотелось бы, чтобы названия разных настроек были менее запутанными.

Лев Рейзин

это звучит как агностическое обучение с верхней границей OPT (C, D)

Суреш Венкат

Не совсем, потому что шум не может быть произвольным в модели классификации шума. Таким образом, если бы существовала какая-то враждебная картина шума, которая усложняла обучение (или находило эмпирический минимизатор риска) в агностической модели, это не могло бы часто происходить в модели классификации шума (то есть попадание в дельта-параметр PAC).

Лев Рейзин

Ответы:

Если ни один класс не является слишком простым, то вот некоторые классы, которые можно изучать PAC. В ответ на комментарии вычеркнуты классы с полиномиальным количеством гипотез:

~~деревья решений с постоянной глубиной (и другие классы, имеющие только много гипотез)~~
~~гиперплоскости в (только гипотезы, дающие различные маркировки) $R^2$ $O(n^2)$~~
объединения интервалов (динамическое программирование)
четность некоторых из первых из битов (см. это и это ) $\log(k)\log\log(k)$ $n$
~~другие классы гипотез в низкоразмерных условиях.~~

Практически все остальное - NP-Hard, чтобы (по крайней мере, правильно) агностически изучать PAC.

Учебник Адама Калаи по агностическому обучению также может вас заинтересовать.

Лев Рейзин
источник

Спасибо. Таким образом, деревья решений с постоянной глубиной, двумерные гиперплоскости (я полагаю, другие низкоразмерные настройки, на которые вы ссылаетесь) все попадают в категорию наличия только полиномиально большого количества функций, которые могут быть изучены путем исчерпания. Четности на log (k) loglog (k) битах и объединениях интервалов интересны тем, что они содержат суперполиномиально много функций. Есть ли такие, как эти?

Аарон Рот

Правильно, хотя в R ^ 2 существует бесконечно много гиперплоскостей, просто O (n ^ 2) по-разному классифицирует точки данных. Я не знаю никаких других интересных классов на макушке, но если я подумаю / найду какие-нибудь, я отредактирую свой ответ.

Лев Рейзин

так вы хотите неограниченные классы VC-измерения?

Суреш Венкат

неограниченная размерность VC, безусловно, была бы интересна, но большие конечные (для фиксированных d) классы уже чрезвычайно интересны (и кажутся редкими)

Аарон Рот

@LevReyzin Ссылка на лекции Калаи не работает. Не могли бы вы исправить это? Я искал в сети, но не мог найти это либо.

Anirbit