Границы правильного обучения в VC

11

Хорошо известно, что для концептуального класса с размерностью VC достаточно получить помеченные примеры для PAC learn . Мне не ясно, является ли алгоритм обучения PAC (который использует эти многочисленные образцы) правильным или неправильным? В учебниках Кернса и Вазирани, а также Энтони и Биггса кажется, что алгоритм обучения PAC неправильный (т. Е. Выходная гипотеза не лежит в ) d O ( дCdCCO(dεlog1ε)CC

  1. Может ли кто-нибудь уточнить, имеет ли место аналогичная верхняя граница для правильной настройки обучения PAC? Если да, не могли бы вы дать мне ссылку, в которой это явно упоминается, а также содержит автономное доказательство?

  2. Недавно Ханнеке улучшил эту границу, избавившись от фактора . Может ли кто-нибудь уточнить, известно ли, что является съемным для правильной настройки обучения PAC? Или это все еще открытый вопрос?log ( 1 / ε )log(1/ε)log(1/ε)

Annonymous
источник
Что это за бумага Ханнеке, на которую вы ссылаетесь?
gradstudent
1
@gradstudent arxiv.org/abs/1507.00473
Клемент С.

Ответы:

9

Я благодарю Арье за то, что он привлек этот вопрос к моему вниманию.

Как уже упоминалось, ответом на (1) является « Да» , и простой метод минимизации эмпирического риска в позволяет достичь сложности образца ( см. Vapnik and Chervonenkis, 1974; Blumer, Ehrenfeucht, Haussler and Warmuth, 1989).CO((d/ε)log(1/ε))

Что касается (2), на самом деле известно, что существуют пробелы где ни один правильный алгоритм обучения не достигает лучшего, чем образец сложности , и следовательно, правильное обучение не может достичь оптимальной сложности выборки . Насколько мне известно, этот факт фактически никогда не публиковался, но коренится в связанном аргументе Даниели и Шалева-Шварца (COLT 2014) (первоначально сформулирован для другого, но связанного вопроса в мультиклассовом обучении).C Ω ( ( d / ε ) log ( 1 / ε ) ) O ( d / ε )Ω((d/ε)log(1/ε))O(d/ε)

Рассмотрим простой случай и обозначим пространство как , а - синглетоны : то есть, каждый классификатор в классифицирует ровно одна точка из , как , а остальные как . Для нижней границы возьмем целевую функцию как случайный синглтон , где , а - предельное распределение , является одинаковым наd=1X{1,2,...,1/ε}Cfz(x):=I[x=z],zXCX10fxxUniform(X)PXX{x}, Теперь ученик никогда не видит примеров с меткой , но он должен выбрать точку чтобы угадать метку (важно, чтобы функция `` все ноль ') не была в , поэтому любой ученик должен угадать некоторую ) и до тех пор, пока он не увидит каждую точку в него будет как минимум вероятности неверного угадывания (т. е. задняя вероятность того, что имеет составляет не менее ). Аргумент сборщика купонов подразумевает, что это потребует1z1CzX{x}1/2fzzx1/2Ω((1/ε)log(1/ε))Образцы чтобы увидеть каждую точку вX{x} . Таким образом, это доказывает нижнюю оценкуΩ((1/ε)log(1/ε)) для всех учеников.

Для общего d>1 , мы возьмем X как {1,2,...,d/(4ε)} , возьмите C качестве классификатора IA для множеств AX размера d точно , выберите целевую функцию случайным образом из C и снова возьмите P качестве равномерного только для тех точек, которые целевая функция классифицирует 0 ( поэтому ученик никогда не видит точку с надписью 1). Тогда обобщение аргумента купон-коллектор подразумевает, что нам нужно Ω((d/ε)log(1/ε)) выборок, чтобы увидеть хотя бы |X|2d различных точек из X , и не видя это много различных точек любой собственный ученик имеет по крайней мере 1/3 шанс получить больше , чем d/4 его догадка A из d точек неправильно в его выбрали гипотезы hAЭто означает, что частота ошибок превышает ε . Таким образом, в этом случае не существует надлежащего учащегося со сложностью выборки, меньшей Ω((d/ε)log(1/ε)) , что означает, что ни один учащийся не достигает оптимальной сложности выборки O(d/ε) .

Обратите внимание , что результат вполне специфичен для пространства C построено. Существуют пространства C которых учащиеся могут достичь оптимальной сложности выборки O(d/ε) и даже точного полного выражения O((d/ε)+(1/ε)log(1/δ)) из ( Ханнеке, 2016a). Некоторые верхние и нижние оценки для общих учащихся ERM были разработаны в (Hanneke, 2016b), количественно определенными в терминах свойств пространства C, а также обсуждение некоторых более специализированных случаев, когда конкретные ученики могут иногда достигать оптимальной сложности выборки.

Ссылки:

Вапник и Червоненкис (1974). Теория распознавания образов. Наука, Москва, 1974.

Blumer, Ehrenfeucht, Haussler и Warmuth (1989). Обучаемость и измерение Вапника-Червоненки. Журнал Ассоциации вычислительной техники, 36 (4): 929–965.

Даниели и Шалев-Шварц (2014). Оптимальные ученики для многоклассовых задач. В материалах 27-й конференции по теории обучения.

Ханнеке (2016a). Оптимальная выборочная сложность обучения PAC. Журнал исследований машинного обучения, Vol. 17 (38), стр. 1-15.

Ханнеке (2016b). Уточненные границы ошибок для нескольких алгоритмов обучения. Журнал исследований машинного обучения, Vol. 17 (135), стр. 1-55.

С. Ханнеке
источник
Интересно ... Существует ли комбинаторная характеристика классов для которой правильное обучение PAC является оптимальным для выборки? Или хотя бы достаточные условия (замыкание на пересечении, объединение?)C
Клемент С.
2
@ClementC. Не известно ни одной полной характеристики того, какие классы имеют оптимальные показатели, достижимые обычными учениками в целом. Ссылочная статья «Уточненные границы ошибок ...» дает комбинаторную характеристику того, какие классы допускают оптимальные показатели для всех учащихся ERM (следствие 14). Соответствующим количеством является «звездное число»: наибольшее количество точек, так что можно перевернуть метку любой отдельной точки, не изменяя другие (определение 9). Классы, замкнутые на пересечении, имеют оптимального ученика: «закрытие» (теорема 5 в статье, а также доказанная Дарнштадтом, 2015).
С. Ханнеке
Спасибо!
Климент С.
6

Ваши вопросы (1) и (2) связаны между собой. Во-первых, давайте поговорим о правильном обучении PAC. Известно, что есть соответствующие ученики PAC, которые достигают нулевой ошибки выборки, и все же требуют примеры. Для простого доказательстваезависимости, рассмотрим класс концепции интервалов[,Ь][0,1]при равномерном распределении. Если мы выберемнаименьшийсогласованный интервал, мы действительно получим выборочную сложностьO(1/ϵ). Предположим, однако, что мы выбираемнаибольшийсогласованный интервал, и целевой концепцией является точечный интервал, такой как[0,0]Ω(dϵlog1ϵ)ϵ[a,b][0,1]O(1/ϵ)[0,0], Тогда простой аргумент купон-сборщик показывает, что если мы не получим примерно примеры, нас одурачит промежуток между отрицательными примерами (единственный вид, который мы увидим), который имеет характерное поведение1/[размер выборки] при равномерном распределении. Более общие нижние оценки этого типа приведены в1ϵlog1ϵ1/

П. Ауэр, Р. Ортнер. Новая оценка PAC для концептуально-замкнутых классов. Машинное обучение 66 (2-3): 151-163 (2007) http://personal.unileoben.ac.at/rortner/Pubs/PAC-intclosed.pdf

Сущность правильного PAC заключается в том, что для положительных результатов в абстрактном случае нельзя указать алгоритм, выходящий за рамки ERM, который гласит: «найдите концепцию, соответствующую помеченному образцу». Когда у вас есть дополнительная структура, такая как интервалы, вы можете исследовать два разных алгоритма ERM, как указано выше: минимальный и максимальный согласованный сегмент. И они имеют разные сложности образца!

Сила неправильного PAC заключается в том, что вы можете разрабатывать различные схемы голосования (такой результат у Ханнеке) - и эта дополнительная структура позволяет вам доказать улучшенные показатели. (Эта история проще для независимого PAC, где ERM дает вам наилучшую возможную частоту наихудших случаев, вплоть до констант.)

Редактировать. Теперь мне пришло в голову, что стратегия предсказания 1-включения графа Д. Хауслера, Н. Литтлстоуна, М. Д. Вармута. Предсказание {0,1} -функций для случайно нарисованных точек. Inf. Вычи. 115 (2): 248-292 (1994) может быть естественным кандидатом для универсального надлежащего ученика PAC.O(d/ϵ)

Арье
источник
Спасибо! Итак, если я правильно вас понимаю, примерная сложность неправильного обучения PAC составляет а для правильного обучения PAC это Θ ( d / ϵ log ( 1 / ϵ ) ) , нижняя граница для последнего достигается за пример, который вы даете. Это правильно? Θ(d/ϵ)Θ(d/ϵlog(1/ϵ))
Аноним
Да, с небольшой оговоркой, что для неправильного PAC вам нужно использовать определенный алгоритм (Ханнеке), а не просто какой-либо старый ERM. Не стесняйтесь принять ответ :)
Aryeh
Я опаздываю на вечеринку, но разве вышеупомянутая нижняя граница Proper-PAC не является нижней границей сложности образца только для конкретного алгоритма обучения (или его ограниченного класса)? Я имею в виду, что без такого ограничения теоретически не существует разделения между правильным и неправильным PAC, верно? (И, следовательно, нет разделения без вычислительных допущений, таких как или аналогичных)?)NPRP
Клемент С.
1
Обычное определение обучаемости PAC требует алгоритмов много времени. Моя точка зрения заключается в том, что (i) смягчение того, что правильное и неправильное имеет одинаковую сложность образца; (ii) с этим требованием мы не можем доказать безусловное разделение между правильным и ненадлежащим (поскольку это, по сути, доказывает что-то вроде NP, не равное RP). ( Тем не менее, мы можем доказать нижнюю границу сложности примера конкретных правильных алгоритмов обучения, что, насколько я понимаю, является тем, что делает ссылка Арье.)
Клемент С.
1
@ClementC. В одном из ваших предыдущих комментариев, которые вы упомянули после запуска неправильного алгоритма PAC, учащийся получает, возможно, неправильную гипотезу, и затем учащийся может найти ближайшую правильную гипотезу из концептуального класса (без каких-либо дополнительных примеров). Но как учащийся может сделать это, не зная распределения, при котором ему дают образцы? Разве самое близкое измеряется в соответствии с неизвестным распределением?
Аноним
5

Чтобы добавить к принятому в настоящее время ответу:

  1. Да. верхняя граница сложности образца сохраняется и для правильного обучения PAC(хотя важно отметить, что он может не привести к вычислительно эффективному алгоритму обучения. Это нормально, поскольку, если толькоNP=RPне известно, что некоторые классы неэффективно изучаемый PAC (см., например, теорему 1.3 в книге Кернса-Вазирани, которую вы упоминаете). На самом деле это показано в книге Кирнса-Вазирани (теорема 3.3), такLсуществует постоянная гипотеза искателя с классом гипотезыH=C. Смотрите также [1].

    O(dεlog1ε)
    NP=RPLH=C
  2. Неизвестный. Алгоритм Ханнеке [2] является неправильным алгоритмом обучения. Вопрос о том, можно ли убрать этот дополнительный фактор сложности выборки для надлежащего обучения PAC (теоретически, т.е. откладывая в сторону любые требования к вычислительной эффективности) , остается открытым вопросом. Ср открытые вопросы в конце [3]:log(1/ε)

    Классически, все еще остается открытым вопрос, необходим ли -фактор в верхней границе [1] для ( ε , δ ) -собственного обучения PAC.log(1/ε)(ε,δ)

    (Сноска 1 в том же документе также актуальна)


[1] A. Blumer, A. Ehrenfeucht, D. Haussler и MK Warmuth. Обучаемость и измерение Вапника-Червоненки. Журнал ACM, 36 (4): 929–965, 1989.

[2] С. Ханнеке. Оптимальная выборочная сложность обучения PAC. J. Mach. Учить. Местожительство 17, 1, 1319-1333, 2016.

[3] С. Аруначалам и Р. де Вольф. Оптимальная квантовая выборка сложности алгоритмов обучения. В материалах 32-й конференции по вычислительной сложности (CCC), 2017.

Климент С.
источник
Предполагается ли, что граф 1-включения Haussler et al. такой оптимальный ученик PAC?
Арье,
@ Арье, я не уверен. Из того, что я смог найти, Уормхут предположил это в 2004 году. Я не знаю больше, чем это.
Клемент С.