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?
- [1] Roi Livni, Shai Shalev-Shwartz, Ohad Shamir, " Sobre a eficiência computacional do treinamento de redes neurais ", 2014
Respostas:
Formalizarei uma variante desta questão em que "eficiência" é substituída por "computabilidade".
SejaCn 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 f∈Cn , o problema da avaliação
f(x) é indecidible.
No entanto, suponha que tenhamos acesso a um oráculoA (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 f ∈ C n
, que, com uma probabilidade de, pelo menos, 1 - δ , tem Df^∈Cn 1−δ D erro 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 marcadaS , se existe uma f∈Cn 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~:x↦k , definido como sendo a menork tal que alguns TM emCk
S-imprimex , é Turing-calculável. Segue-se ainda que a função
g:k↦x , que mapeia umk∈N
para a menor string (lexicograficamente)x∈{0,1}∗
tal queK~(x)>k , também é computável.
Agora definir o TMM 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.
fonte