Sabemos que (véanse, por ejemplo, los Teoremas 1 y 3 de [1]), en términos generales, en condiciones adecuadas, las funciones que pueden calcularse eficientemente por la máquina de Turing en tiempo polinómico ("eficientemente computable") pueden expresarse mediante redes neuronales polinómicas con tamaños razonables, y por lo tanto se puede aprender con la complejidad de la muestra polinómica ("aprendible") bajo cualquier distribución de entrada.
Aquí "aprendible" solo se refiere a la complejidad de la muestra, independientemente de la complejidad computacional.
Me pregunto acerca de un problema muy relacionado: ¿existe una función que la máquina de Turing no pueda calcular de manera eficiente en tiempo polinómico ("no eficientemente computable"), pero mientras tanto, se puede aprender con la complejidad de la muestra polinómica ("aprendible") bajo cualquier distribución de entrada?
- [1] Roi Livni, Shai Shalev-Shwartz, Ohad Shamir, " Sobre la eficiencia computacional del entrenamiento de redes neuronales ", 2014
Respuestas:
Formalizaré una variante de esta pregunta donde "eficiencia" se reemplaza por "computabilidad".
Sea la clase de concepto de todos los lenguajes reconocible por las máquinas de Turing en estados o menos. En general, para y , el problema de evaluar es indecidible.donorte L ⊆ Σ∗ norte x ∈ Σ∗ F∈ Cnorte F(x)
Sin embargo, supongamos que tenemos acceso a un oráculo de aprendizaje PAC (adecuado, realizable) para . Es decir, para cualquier , el oráculo solicita una muestra etiquetada de tamaño modo que, suponiendo que dicha muestra se extraiga de una distribución desconocida , el oráculo genera una hipótesis que, con una probabilidad de al menos , tiene un error de generalización no mayor que . Mostraremos que este oráculo no es computable por Turing.A Cn ϵ,δ>0 m0(n,ϵ,δ) D A f ∈ C n 1 - δ D εf^∈Cn 1−δ D ϵ
En realidad, vamos a demostrar que un problema más sencillo es indecidible: Uno de determinar, dada una muestra marcada , si existe un consonancia con . Supongamos (para contradecir) que es una máquina de Turing que decide el problema de consistencia.S f∈Cn S K
Hacemos las siguientes convenciones de notación. Identifique con mediante el ordenamiento lexicográfico habitual. Para , decimos que un TM "S-imprime" si acepta todas las cadenas en correspondientes a los índices st y no acepte (posiblemente no deteniendo) ninguna de las cadenas correspondientes a los índices . Dado que (por supuesto) es decidible, se deduce que la función , definida como la más pequeña, de modo que alguna TM enΣ∗ N={0,1,2,…} x∈{0,1}∗ M x Σ∗ i xi=1 xi=0 K K~:x↦k k Ck
S-imprime , es computable por Turing. Además, se deduce que la función
, que asigna una
a la cadena menor (lexicográficamente)
tal que , también es computable.x g:k↦x k∈N x∈{0,1}∗ K~(x)>k
Ahora defina la TM siguiente manera: S-imprime , donde es la codificación de , denota longitud de la cadena, y la recursión teorema se invoca para afirmar la existencia de un tal . Entonces tiene alguna longitud de codificación,, y S-imprime alguna cadena, . Por construcción, , por lo que no puede ser impreso en S por ninguna TM con una longitud de descripciónM M g(|⟨M⟩|) ⟨M⟩ M El |x| M M ℓ =|⟨M⟩ | XMETRO∈ { 0 , 1 }∗ K~( xMETRO) > ℓ XMETRO ℓ ℓo más corto Y, sin embargo, se define como la salida de impresión S de una TM con una longitud de descripción --- una contradicción.ℓ
fuente