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

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.$\Theta(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 $x$$f(x)$$f$$C$$f$

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$\gamma^C$$C$$Q_C$$C$

$Q_C = \Omega(1/\gamma^C)\qquad Q_C = \Omega(\log |C|) \qquad Q_C = O(\log |C|/\gamma^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/\gamma^C = \log |C| = k$$\Omega(k)$$O(k^2)$ . (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 é .)$\Omega(k)$$O(k^2)$

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.

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).

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

$C$$X$$S\subseteq X$$f$$f$$C$$S$

$\mathcal{T}(f)$$f$$(f,C)=min\{\ |S|\ | \ S\in \mathcal{T}(f) \}$$f$$_{min}(f)$$\mathcal{T}(f)$$(C)=$$_{f\in C}$$(f,C)$$C$

$f$$(f,C)$$_{min}(f)$$(C)$$f$