Aprendizagem adequada do PAC de 2-DNF sob distribuição uniforme

Qual é o resultado do estado da arte sobre a complexidade das consultas de fórmulas 2-DNF apropriadas para o aprendizado do PAC com consultas de amostra e com distribuição uniforme ? Ou algum limite não trivial?

Como não estou familiarizado com a teoria da aprendizagem e essa pergunta é motivada por um campo diferente, a resposta pode ser óbvia. Eu verifiquei o livro de Kearns e Vazirani, mas eles não parecem considerar essa configuração explicitamente.

upd. Embora o principal parâmetro de interesse seja a complexidade da consulta, o tempo de execução também é importante. Se possível, o tempo de execução deve ser, aproximadamente, o mesmo que a complexidade da consulta ou, no máximo, polinomial.

upd. O Apêndice B (parte superior da página 18) do documento "Learning Submodular Functions", de Balcan e Harvey, menciona que "É bem sabido que os 2-DNFs são eficientemente aprendidos pelo PAC". No entanto, eles não mencionam se esse resultado é para aprendizado adequado ou fornece alguma referência.

Não sei se você considerará o seguinte um limite não trivial, mas aqui vou eu.

Primeiro, para ficar claro, para que não confundamos -DNF com k- termo DNF (o que costumo fazer), uma fórmula c -DNF sobre as variáveis x 1 , … , x n tem a forma ∨ k i = 1 ( ℓ i , 1 ∧ ℓ i , 2 . . . ℓ i , c ) onde ∀ 1 ≤ i ≤ k e 1 ≤ j ≤ $c$$k$$c$$x_1, \ldots, x_n$$\vee_{i=1}^{k}(\ell_{i,1} \wedge \ell_{i,2} ... \ell_{i,c})$$\forall 1 \le i \le k$$1 \le j \le c$, .$\ell_{i,j} \in \{x_1, \ldots, x_n, \bar{x}_1, \ldots, \bar{x}_n \}$

Podemos primeiro perguntar quantos termos distintos podem existir em um -DNF. Cada termo terá c das n variáveis, cada uma negada ou não - resultando em 2 c ($c$$c$$n$ termos possíveis diferentes. Em uma instância 2-DNF, cada termo aparecerá ou não, resultando em| H| =22c ($2^c\binom{n}{c}$ possíveis "alvos", ondeHé o espaço de hipóteses.$|\mathcal{H}| = 2^{2^c\binom{n}{c}}$$\mathcal{H}$

Imagine um algoritmo que tire amostras e tente todas as | H | hipóteses até encontrar uma que prediz perfeitamente as amostras. O teorema da navalha de Occam diz que você só precisa tomar m = O ( $m$$|\mathcal{H}|$amostras para este algoritmo para encontrar um alvo com erro≤ϵcom probabilidade≥1-δ.$m = O(\frac{1}{\epsilon}|(\mathcal{H}|+\frac{1}{\delta})$$\le \epsilon$$\ge 1-\delta$

No nosso caso, para , lg | H | = O ( n 2 ) , o que significa que você precisará de n 2 amostras para fazer o aprendizado (adequado).$c=2$$\lg|\mathcal{H}| = O(n^2)$$n^2$

Mas o jogo inteiro no aprendizado não é realmente uma amostra de complexidade (embora isso faça parte do jogo, especialmente no aprendizado eficiente de atributos), mas na tentativa de projetar algoritmos de tempo polinomial. Se você não se importa com eficiência, então é a resposta mais simples para a complexidade da amostra de PAC.$n^2$

UPDATE (dada a pergunta alterada) :

Como você declarou explicitamente que se importava apenas com a complexidade da amostra, apresentei o algoritmo de Occam de força bruta, que é provavelmente o argumento mais simples. No entanto, minha resposta foi um pouco tímida. -DNF são realmente aprendíveis em tempo polinomial! Este é um resultado do artigo original de Valiant, " Uma teoria do aprendiz ". De fato, c -DNF pode ser aprendido para qualquer c = O ( 1 ) .$2$$c$$c = O(1)$

O argumento é o seguinte. Você pode ver um -DNF como uma disjunção de ≈ n c "meta-variáveis" e tentar aprender a disjunção, eliminando os meta-variáveis inconsistente com os exemplos. Essa solução pode ser facilmente traduzida de volta para uma solução "adequada" e leva tempo O ( n c ) . Como observação lateral, ainda está em aberto se existe um algoritmo de tempo polinomial para c = ω ( 1 ) .$c$$\approx n^c$$O(n^c)$$c = \omega(1)$

Quanto à complexidade da amostra também ser um limite inferior, a resposta é praticamente sim. Este artigo de Ehrenfeucht et al. mostra que o limite do Occam está quase apertado.$n^2$