Funções que não são eficientemente computáveis, mas que podem ser aprendidas

28

Sabemos que (ver, por exemplo, Teoremas 1 e 3 de [1]), grosso modo, sob condições adequadas, funções que podem ser computadas eficientemente pela máquina de Turing em tempo polinomial ("computável eficientemente") podem ser expressas por redes neurais polinomiais com tamanhos razoáveis ​​e, portanto, pode ser aprendido com a complexidade da amostra polinomial ("aprendível") em qualquer distribuição de entrada.

Aqui, "aprendível" refere-se apenas à complexidade da amostra, independentemente da complexidade computacional.

Estou me perguntando sobre um problema muito próximo: existe uma função que não pode ser computada eficientemente pela máquina de Turing em tempo polinomial ("não computável com eficiência"), mas, enquanto isso, pode ser aprendida com a complexidade da amostra polinomial ("aprendível") sob alguma distribuição de entrada?

Minkov
fonte
4
Eu discordo de "e, portanto, posso ser aprendido". Existem funções computáveis ​​com muita eficiência (por exemplo, DFAs) que são MUITO difíceis de aprender, mesmo aproximadamente.
Areyh #
3
Provavelmente isso está faltando, mas e a classe de (digamos) funções booleanas com polarização n ? (Ou seja, mais ou menos, uma função aleatória com cada valor sendo independentemente1com probabilidade2-2n1 ) Para qualquerε>2-2n , o aprendizado do PAC sob a distribuição uniforme é trivial (é necessária uma amostra de 0, a função constante0é uma boa hipótese), mas parece que qualquer algoritmo de avaliação precisaria gastar tempo superpolinomial (como não há estrutura para a função). Provavelmente estou entendendo mal a pergunta. ε>2n0
Clement C.
3
Sua terminologia é um pouco confusa. Quando dizemos "eficientemente aprendível", geralmente nos referimos à eficiência computacional. Apenas dizer "aprendível" é suficiente para implicar na eficiência da amostra.
Lev Reyzin
1
@Minkov Para o PAC aprender, você deve aprender com relação a qualquer distribuição. Caso contrário, a questão não é interessante (como Clement aponta).
Lev Reyzin
2
Por que as pessoas estão votando para fechar? Eu acho que essa é uma pergunta profunda e sutil!
Areyh #

Respostas:

11

Formalizarei uma variante desta questão em que "eficiência" é substituída por "computabilidade".

Seja Cn a classe conceitual de todos os idiomas LΣ reconhecíveis pelas máquinas de Turing em n estados ou menos. Em geral, para xΣ e fCn , o problema da avaliação f(x) é indecidible.

No entanto, suponha que tenhamos acesso a um oráculo A (apropriado, realizável) de aprendizado do PAC A para Cn . Ou seja, para qualquer ϵ,δ>0 , o oráculo solicita uma amostra rotulada de tamanho m0(n,ϵ,δ) modo que, assumindo que tal amostra foi extraída de uma distribuição desconhecida D , o oráculo A gera uma hipótese fC n , que, com uma probabilidade de, pelo menos, 1 - δ , tem Df^Cn1δDerro de generalização não superior a ϵ . Mostraremos que esse oráculo não é computável por Turing.

Na verdade, iremos mostrar que um problema mais simples é indecidible: Uma de determinação, dado uma amostra marcada S , se existe uma fCn consistente com S . Suponha (para obter uma contradição) que K é uma máquina de Turing que decide o problema de consistência.

Fazemos as seguintes convenções notacionais. Identificar Σ com N={0,1,2,} através da ordenação lexicográfica de costume. Para x{0,1} , dizemos que uma TM M "S-imprime" x se ele aceita todas as cadeias em Σ correspondente aos índices i st xi=1 e não aceita (possivelmente por não interrompendo) qualquer uma das strings correspondentes aos índices xi=0 . Uma vez que (por hipótese)K é determinável, segue-se que a funçãoK~:xk , definido como sendo a menork tal que alguns TM emCk S-imprimex , é Turing-calculável. Segue-se ainda que a função g:kx , que mapeia umkN para a menor string (lexicograficamente)x{0,1} tal queK~(x)>k , também é computável.

Agora definir o TM M como se segue: M S-imprime g(|M|) , onde M é a codificação de M , |x|denota o comprimento da string e o teorema da recursão está sendo invocado para afirmar a existência de um M desse tipo . Então M tem algum comprimento de codificação, =|M|e S-imprime alguma sequência, xM{0,1}. Por construção, K~(xM)> , e assim xM pode não ser S-impresso por qualquer TM com a descrição comprimento ou mais curto. E, no entanto, é definido como a saída S-print de uma TM com o comprimento da descrição --- uma contradição.

Aryeh
fonte
2
Desafio: converter meu argumento "infinito" via computabilidade em um argumento finitário via eficiência. Penso que a resposta à pergunta de @ minkov é negativa: você não pode aprender eficientemente uma classe de função que não pode avaliar com eficiência. Eu acho que isso continuará a ser verdade se você ultrapassar o PAC adequado ou realizável.
Aryeh #