Вопрос паритетного обучения

10

Определим класс функций для набора из битов. Исправьте два распределения , которые «разумно» отличаются друг от друга (если хотите, их вариационное расстояние составляет не менее , или что-то подобное).p , q ϵnp,qϵ

Теперь каждая функция в этом классе определяется набором из индексов и оценивается следующим образом: если четность выбранных битов равна 0, вернуть случайную выборку из , иначе вернуть случайную выборку из .k S p qfkSpq

Проблема : Предположим, у меня есть доступ оракула к некоторому из этого класса, и хотя я знаю (или некоторую другую меру расстояния), я не знаю и .ϵ p qfϵpq

Есть ли какие-либо ограничения на количество вызовов, которые мне нужно сделать для PAC-learn ? Предположительно мой ответ будет в терминах и .n , k ϵfn,kϵ

Примечание : я не указал выходной домен. Опять же, я гибок, но сейчас давайте скажем, что и определены над конечной областью . В общем, меня также интересует случай, когда они определены над (например, если они гауссианы)q [ 1 .. M ] Rpq[1..M]R

Суреш Венкат
источник
Я не уверен, что понимаю модель. Что вы указываете в оракула? Всегда ли примеры взяты из дистрибутива, указанного целью?
Лев Рейзин
1
В вызове оракула вы вызываете f (), и он возвращает значение.
Суреш Венкат
Таким образом, в зависимости от целевой функции , либо p, либо q всегда используются для генерации примеров? (Я предполагаю, что вы fFpqF
учитесь в
Да, это правильно. проблема в том, чтобы узнать, какой из них (или узнать, какой бит четности используется)
Суреш Венкат
2
Я не уверен, как вы адаптируете модель PAC к этой модели. Но кажется, что этого достаточно, чтобы иметь возможность отличить от q с вероятностью 1 - 1 / ( 2 k ), а затем вы можете получить значения f ( x ) для k, линейно независимых x, и использовать исключение Гаусса, чтобы найти f (так как f является линейным). например, будет легко отличить двух хорошо разделенных гауссов. pq11/(2k)f(x)kxff
Сашо Николов

Ответы:

6

Обсуждение в комментариях ниже указывает на то, что я неправильно понял вопрос. Мой ответ основывается на Oracle не принимает никакого ввода и возврата , где х ~ р или х ~ д , в зависимости от F F . Это явно не то, что просят.(x,f(x))xpxqfF


Поскольку распределение цели является фиксированным для каждой цели , применяется верхняя граница образца PAC (это следует из того факта, что распределение цели для этой границы может даже полностью зависеть от f ). Следовательно, m ˜ O ( 1fFf примеров должно быть достаточно, чтобы найти гипотезу ошибкиϵwp1-δ. Обратите внимание - после просмотра этих примеров нужно найти непротиворечивую гипотезу отF, и это может не соответствовать.

mO~(1ϵ(VC(F)+log(1/δ)))
ϵ1δF

С другой стороны, можно получить почти совпадающую нижнюю границу даже для случая , равномерное распределение, где m Ω ( V C ( F ) ), примеры все еще требуются (это можно немного улучшить) ,пзнак равноQзнак равноUмΩ(ВС(F))

Вариационное расстояние между и q , а также k может играть роль в небольшом зазоре между этими границами, но я сомневаюсь в этом.пQК

Лев Рейзин
источник
Типичная настройка обучения PAC имеет оракула который берет образец x из распределения D и возвращает ( x , f ( x ) ) . Это не параметр, описанный в вопросе Суреша или посте в блоге, который вдохновил его: bit.ly/YtwdST . В обоих случаях оракул является функцией f , и учащийся может предоставить любой элемент из набора экземпляров (цепочки битов длины n(е,D)ИксD(Икс,е(Икс))еN). Лев, твой ответ предполагает оракула первого типа или второго типа? Если второй тип, мы все еще говорим о PAC-обучении?
Кеки Бурджорджи
1
Понимаю. В PAC, то «оракулом» обычно понимается как кнопка , которая возвращает где х ~ D . Оракул, который вы описываете, называется «запросом на членство» для f . Мой ответ относится только к первому. Если вы только запрашиваете членство, как вы узнаете какую-либо информацию о p или q, используя платформу Suresh? Допустим, p = q для простоты. (Икс,е(Икс))Икс~DепQпзнак равноQ
Лев Рейзин
Спасибо за это разъяснение. Таким образом, в случае, описанном Сурешем, оракул «запроса членства» работает следующим образом (я предполагаю, что вы поместили эту сущность в кавычки, потому что оракул может возвращать реальное значение, а не просто логическое значение is-a-member / not-a- ответ члена): если соотношение действующих атрибутов равно 1, то возвращаемый результат извлекается из распределения . В противном случае результат получается из распределения q . Есть дополнительная морщина. Оракул запоминает все свои предыдущие ответы и возвращает их, если запрашивается с тем же вводом. Другими словами, это детерминистично. пQ
Кеки Бурджорджи
1
Я не понимаю Если оракул - это просто функция и вы запрашиваете его, давая ему x , разве он не возвращает f ( x ) ? Как играть p или q, если учащийся сам генерирует x ? Я думаю, что я все время не мог понять этого основного положения ...еИксе(Икс)пQИкс
Лев Рейзин
Для и q = N ( - 0,25 , 1 ) псевдокод оракула для проблемы с «морщинкой» приведен в нижней части этого комментария reddit: bit.ly/XvVMC4 ( ). Я не могу встроить код, потому что SE не позволяет переводы строк в комментариях. Чтобы получить «не морщинистую» версию проблемы, просто удалите строку . пзнак равноN(+0,25,1)Qзнак равноN(-0,25,1)def fitness() ...random_number_generator.set_seed(x)
Кеки Бурджорджи