Caracterização combinatória do aprendizado exato com consultas de associação

15

Edit: Como não recebo nenhuma resposta / comentário há uma semana, gostaria de acrescentar que estou feliz em saber algo sobre o problema. Eu não trabalho na área, portanto, mesmo que seja uma observação simples, talvez eu não saiba. Mesmo um comentário como "Eu trabalho na área, mas não vi uma caracterização como essa" seria útil!

Fundo:

Existem vários modelos de aprendizagem bem estudados na teoria da aprendizagem (por exemplo, aprendizagem do PAC, aprendizado on-line, aprendizado exato com consultas de associação / equivalência).

Por exemplo, no aprendizado do PAC, a complexidade da amostra de uma classe de conceito tem uma boa caracterização combinatória em termos da dimensão VC da classe. Portanto, se queremos aprender uma classe com precisão e confiança constantes, isso pode ser feito com amostras, em que é a dimensão VC. (Observe que estamos falando de complexidade da amostra, não da complexidade do tempo.) Também há uma caracterização mais refinada em termos de precisão e confiança. Da mesma forma, o modelo de aprendizado on-line com erros tem uma boa caracterização combinatória.Θ(d)d

Questão:

Quero saber se um resultado semelhante é conhecido para o modelo de aprendizado exato com consultas de associação. O modelo é definido da seguinte forma: Temos acesso a uma caixa preta que na entrada fornece . Sabemos vem de algum conceito de classe . Queremos determinar com o mínimo de consultas possível.f ( x ) f C fxf(x)fCf

Existe um parâmetro combinatório de uma classe de conceito que caracteriza o número de consultas necessárias para aprender um conceito no modelo de aprendizado exato com consultas de associação?C

O que eu sei:

A melhor caracterização que encontrei é neste artigo de Servedio e Gortler , usando um parâmetro que eles atribuem a Bshouty, Cleve, Gavaldà, Kannan e Tamon . Eles definem um parâmetro combinatório chamado , em que é a classe de conceito, que possui as seguintes propriedades. (Seja o número ideal de consultas necessárias para aprender neste modelo.) C Q C CγCCQCC

QC=Ω(1/γC)QC=Ω(registro|C|)QC=O(registro|C|/γC)

Essa caracterização é quase estreita. No entanto, pode haver um espaço quadrático entre os limites superior e inferior. Por exemplo, se , o limite inferior é , mas o limite superior éΩ ( k ) O ( k 2 ) Ω ( k ) O ( k 2 )1/γC=registro|C|=kΩ(k)O(k2) . (Eu também acho que essa lacuna é possível, ou seja, existe uma classe de conceito para a qual os limites inferiores são , mas o limite superior é .)Ω(k)O(k2)

Robin Kothari
fonte
1
"Dimensão do palheiro" caracteriza a complexidade da consulta para otimizar uma função: cis.upenn.edu/~mkearns/papers/haystack.pdf , é diferente do que você deseja, mas você pode aproveitar o trabalho relacionado que discute o que se sabe sobre caracterizar a complexidade da consulta do aprendizado exato.
Aaron Roth

Respostas:

6

Para mostrar o exemplo do exemplo de alce anônimo, considere a classe de conceito que consiste em funções que produzem 1 em apenas um ponto em {0,1} ^ n. A classe é do tamanho 2 ^ n, e 2 ^ n consultas são necessárias no pior dos casos. Dê uma olhada na pior dimensão de ensino (Goldman & Schapire), que fornece algo semelhante ao que você está procurando.

ganso anônimo
fonte
1
Obrigado! A pesquisa da dimensão de ensino levou-me à dimensão de ensino estendida, que é semelhante ao parâmetro combinatório mencionado na pergunta, que me levou a muitos outros artigos interessantes sobre o tema.
precisa
4

Não conheço essa caracterização. No entanto, vale a pena notar que, para quase qualquer classe de conceito, é necessário consultar todos os pontos. Para ver isso, considere a classe conceitual que consiste em todos os vetores booleanos n-dimensionais com peso de Hamming 1. Essa classe conceitual obviamente requer n consultas para aprender, o que é igual à sua cardinalidade. Provavelmente, você pode generalizar essa observação para obter que quase qualquer classe de conceito também exija a execução de todas as consultas.

Eu suspeitaria que, dada uma classe de conceito C como entrada, é difícil para o NP determinar a complexidade de exatamente aprender a classe de conceito com consultas de associação, ou mesmo aproximar-se para dizer uma constante. Isso daria alguma indicação de que não existe uma caracterização combinatória "boa". Se você deseja provar um resultado de dureza NP, mas tente e falhe, sinta-se à vontade para postar aqui e vou ver se consigo descobrir (tenho algumas idéias).

alce anônimo
fonte
1
Obrigado pela resposta. Mesmo que seja verdade que quase todas as classes de conceitos (com uma distribuição razoável sobre as classes) são difíceis de aprender, algumas são fáceis de aprender e seria interessante ter um parâmetro combinatório que a caracterize. Não me importo se o parâmetro é difícil de calcular. Nem mesmo a dimensão VC é computável com eficiência.
precisa
1

Embora outros tenham apontado a resposta. Eu pensei que poderia torná-lo independente e mostrar por que a dimensão do ensino é a resposta.

CXSXffCS

T(f)f(f,C)=mEun{ |S| | ST(f)}fmEun(f)T(f)(C)=fC(f,C)C

f(f,C)mEun(f)(C)f

seteropere
fonte
fff
O limite mínimo do @RobinKothari TD limita o número mínimo de consultas em qualquer algoritmo MQ. Na prática, pode não haver algoritmo que atinja cegamente esse limite sem trapaça ou truques de código. No artigo "Consultas revisitadas" de Angluin, ela discutiu um parâmetro chamado MQ que representa o número de consultas necessárias pelo melhor algoritmo MQ no pior caso. Não me lembro de seus detalhes, mas certamente TD <= MQ.
Seteropere 28/11/2015
1
O que me interessou (quando fiz essa pergunta) foi um parâmetro que caracteriza o aprendizado exato com as consultas de associação. Deve ser um limite superior e inferior. Forneci um exemplo de um parâmetro que consegue isso (até um fator de log | C |) na pergunta. Minha pergunta era se algo melhor é conhecido.
precisa