Uma questão de aprendizado de paridade

10

Vamos definir uma classe de funções sobre um conjunto de bits. Corrija duas distribuições p , q que são "razoavelmente" diferentes uma da outra (se desejar, a distância variacional é pelo menos ϵ ou algo semelhante).np,qϵ

Agora, cada função nesta classe é definida por um conjunto de k índices de S , e é avaliado da seguinte maneira: Se a paridade dos bits seleccionados é 0, retornar uma amostra aleatória a partir de p , mais retornar uma amostra aleatória de q .fkSpq

Problema : Suponha que eu sou dado acesso oráculo para alguns a partir desta classe, e enquanto eu sei ε (ou alguma outra medida de distância), eu não sei p e q .fϵpq

Existe algum limite no número de chamadas que preciso fazer para o PAC-learn ? Presumivelmente, a minha resposta vai ser em termos de n , k e ε .fn,kϵ

Nota : não especifiquei o domínio de saída. Novamente, eu sou flexível, mas por agora vamos dizer que e q são definidos sobre um domínio finito [ 1 .. M ] . Em geral, eu também estaria interessado no caso em que eles são definidos sobre R (por exemplo, se forem gaussianos)pq[1..M]R

Suresh Venkat
fonte
Não sei se entendi o modelo. O que você especifica em uma chamada da Oracle? Os exemplos são sempre retirados da distribuição especificada pelo destino?
Lev Reyzin
11
Em uma chamada oracle, você invoca f () e ele retorna um valor.
quer tocar hoje
Então, dependendo da função de destino , p ou q é sempre usado para gerar exemplos? (Presumo que você esteja aprendendo um pouco sobre a classe F. )fFpqF
Lev Reyzin
Sim, está correto. o problema é saber quais um (ou aprender o bit de paridade sendo usado)
Suresh Venkat
2
Não tenho certeza de como você adapta o modelo PAC a esse modelo. Mas parece que é suficiente ser capaz de distinguir de q com probabilidade 1 - 1 / ( 2 k ) e, em seguida, você pode obter os valores de f ( x ) para k linearmente independentes x e usar a eliminação gaussiana para encontrar f (desde que f é linear). distinguir dois gaussianos bem separados será fácil, por exemplo. pq11/(2k)f(x)kxff
Sasho Nikolov

Respostas:

6

A discussão nos comentários abaixo indica que eu entendi mal a pergunta. Minha resposta tem como premissa o Oráculo tomar nenhuma entrada e retorno , onde x ~ p ou x ~ q , dependendo f F . Aparentemente, não é isso que está sendo perguntado.(x,f(x))xpxqfF


Uma vez que a distribuição alvo é fixada para cada alvo , o PAC-amostra limite superior aplica-se (o que decorre do facto de que a distribuição alvo para esta ligado pode depender mesmo completamente em f * ). Assim, m ~ O ( 1fFf exemplos devem ser suficientes para encontrar uma hipótese de erroϵwp1-δ. Nota - depois de ver esses exemplos, é preciso encontrar uma hipótese consistente deF, e isso pode não ser tratável.

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

p=q=UmΩ(VC(F))

pqk

Lev Reyzin
fonte
(f,D)xD(x,f(x))fn) Lev, sua resposta assume um oráculo do primeiro tipo ou do segundo tipo? Se o segundo tipo, ainda estamos falando sobre a aprendizagem do PAC?
Keki Burjorjee
11
(x,f(x))xDfpqp=q
pq
11
fxf(x)pqx
p=N(+0.25,1)q=N(0.25,1)def fitness() ...random_number_generator.set_seed(x)