Хорошо известно, что для концептуального класса с размерностью VC достаточно получить помеченные примеры для PAC learn . Мне не ясно, является ли алгоритм обучения PAC (который использует эти многочисленные образцы) правильным или неправильным? В учебниках Кернса и Вазирани, а также Энтони и Биггса кажется, что алгоритм обучения PAC неправильный (т. Е. Выходная гипотеза не лежит в ) d O ( дCC
Может ли кто-нибудь уточнить, имеет ли место аналогичная верхняя граница для правильной настройки обучения PAC? Если да, не могли бы вы дать мне ссылку, в которой это явно упоминается, а также содержит автономное доказательство?
Недавно Ханнеке улучшил эту границу, избавившись от фактора . Может ли кто-нибудь уточнить, известно ли, что является съемным для правильной настройки обучения PAC? Или это все еще открытый вопрос?log ( 1 / ε )
Ответы:
Я благодарю Арье за то, что он привлек этот вопрос к моему вниманию.
Как уже упоминалось, ответом на (1) является « Да» , и простой метод минимизации эмпирического риска в позволяет достичь сложности образца ( см. Vapnik and Chervonenkis, 1974; Blumer, Ehrenfeucht, Haussler and Warmuth, 1989).С O((d/ε)log(1/ε))
Что касается (2), на самом деле известно, что существуют пробелы где ни один правильный алгоритм обучения не достигает лучшего, чем образец сложности , и следовательно, правильное обучение не может достичь оптимальной сложности выборки . Насколько мне известно, этот факт фактически никогда не публиковался, но коренится в связанном аргументе Даниели и Шалева-Шварца (COLT 2014) (первоначально сформулирован для другого, но связанного вопроса в мультиклассовом обучении).C Ω ( ( d / ε ) log ( 1 / ε ) ) O ( d / ε )Ω((d/ε)log(1/ε)) O(d/ε)
Рассмотрим простой случай и обозначим пространство как , а - синглетоны : то есть, каждый классификатор в классифицирует ровно одна точка из , как , а остальные как . Для нижней границы возьмем целевую функцию как случайный синглтон , где , а - предельное распределение , является одинаковым наd=1 X {1,2,...,1/ε} C fz(x):=I[x=z],z∈X C X 1 0 fx∗ x∗∼Uniform(X) P X X∖{x∗} , Теперь ученик никогда не видит примеров с меткой , но он должен выбрать точку чтобы угадать метку (важно, чтобы функция `` все ноль ') не была в , поэтому любой ученик должен угадать некоторую ) и до тех пор, пока он не увидит каждую точку в него будет как минимум вероятности неверного угадывания (т. е. задняя вероятность того, что имеет составляет не менее ). Аргумент сборщика купонов подразумевает, что это потребует1 z 1 C z X∖{x∗} 1/2 fz z≠x∗ 1/2 Ω((1/ε)log(1/ε)) Образцы чтобы увидеть каждую точку вX∖{x∗} . Таким образом, это доказывает нижнюю оценкуΩ((1/ε)log(1/ε)) для всех учеников.
Для общегоd>1 , мы возьмем X как {1,2,...,d/(4ε)} , возьмите C качестве классификатора IA для множеств A⊂X размера 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.
источник
Ваши вопросы (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(хотя важно отметить, что он может не привести к вычислительно эффективному алгоритму обучения. Это нормально, поскольку, если толькоNP=RPне известно, что некоторые классы неэффективно изучаемый PAC (см., например, теорему 1.3 в книге Кернса-Вазирани, которую вы упоминаете). На самом деле это показано в книге Кирнса-Вазирани (теорема 3.3), такLсуществует постоянная гипотеза искателя с классом гипотезыH=C. Смотрите также [1].
Неизвестный. Алгоритм Ханнеке [2] является неправильным алгоритмом обучения. Вопрос о том, можно ли убрать этот дополнительный фактор сложности выборки для надлежащего обучения PAC (теоретически, т.е. откладывая в сторону любые требования к вычислительной эффективности) , остается открытым вопросом. Ср открытые вопросы в конце [3]: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.
источник