Fonctions qui ne sont pas efficacement calculables mais qui peuvent être apprises

Nous savons que (voir, par exemple, les théorèmes 1 et 3 de [1]), en gros, dans des conditions appropriées, des fonctions qui peuvent être efficacement calculées par la machine de Turing en temps polynomial ("efficacement calculable") peuvent être exprimées par des réseaux de neurones polynomiaux avec des tailles raisonnables, et peut donc être appris avec une complexité d'échantillon polynomiale ("apprenable") sous toutes les distributions d'entrée.

Ici "apprenable" ne concerne que la complexité de l'échantillon, quelle que soit la complexité de calcul.

Je m'interroge sur un problème très proche: existe-t-il une fonction qui ne peut pas être calculée efficacement par la machine de Turing en temps polynomial ("pas efficacement calculable"), mais qui peut être apprise avec la complexité d'un échantillon polynomial ("apprenable") sous toutes les distributions d'entrée?

[1] Roi Livni, Shai Shalev-Shwartz, Ohad Shamir, " Sur l'efficacité informatique de la formation des réseaux de neurones ", 2014

cc.complexity-theory np-hardness machine-learning turing-machines lg.learning Minkov
la source

Je m'oppose à "et donc je peux apprendre". Il existe des fonctions calculables très efficacement (par exemple, les DFA) qui sont TRÈS difficiles à apprendre, même approximativement.

Aryeh

Cela manque probablement le but, mais qu'en est-il de la classe des fonctions booléennes biaisées par ? (C'est-à-dire, plus ou moins, une fonction aléatoire avec chaque valeur étant indépendamment avec une probabilité ). Pour tout , l'apprentissage PAC sous la distribution uniforme est trivial (0 échantillon nécessaire, la fonction constante est une bonne hypothèse), mais il semble que tout algorithme d'évaluation devrait passer du temps superpolynomial (car il n'y a pas de structure à la fonction). Je suis très probablement mal compris la question, cependant.

2^{- \sqrt{n}}

$2^{-\sqrt{n}}$

1

$1$

2^{- \sqrt{n}}

$2^{-\sqrt{n}}$

ε > 2^{- \sqrt{n}}

$\varepsilon > 2^{-\sqrt{n}}$

0

$0$

Clement C.

Votre terminologie est un peu déroutante. Lorsque nous disons «apprenant efficacement», nous faisons généralement référence à l'efficacité de calcul. Le simple fait de dire «apprenable» suffit pour impliquer l'efficacité de l'échantillon.

Lev Reyzin

@Minkov Pour apprendre PAC, vous devez apprendre en ce qui concerne toute distribution. Sinon, la question n'est pas intéressante (comme le souligne Clément).

Lev Reyzin

Pourquoi les gens votent-ils pour fermer? Je pense que c'est une question profonde et subtile!

Aryeh

Réponses:

Je vais formaliser une variante de cette question où "efficacité" est remplacée par "calculabilité".

Soit $C_n$ la classe conceptuelle de tous les langages $L\subseteq\Sigma^*$ reconnaissable par les machines de Turing sur $n$ états ou moins. En général, pour $x\in\Sigma^*$ et $f\in C_n$ , le problème de l'évaluation de $f(x)$ est indécidable.

Cependant, supposons que nous ayons accès à un (bon, réalisation) oracle PAC-apprentissage $A$ pour $C_n$ . Autrement dit, pour tout , l'oracle demande un échantillon étiqueté de taille telle sorte que, en supposant qu'un tel échantillon a été tiré iid d'une distribution inconnue , l'oracle génère une hypothèse qui, avec une probabilité d'au moins , a une erreur de généralisation pas plus de . Nous montrerons que cet oracle n'est pas calculable par Turing. $\epsilon,\delta>0$ $m_0(n,\epsilon,\delta)$ $D$ $A$ $\hat f\in C_n$ $1-\delta$ $D$ $\epsilon$

En fait, nous allons montrer qu'il ya un problème plus simple est indécidable: L' un de déterminer, étant donné un échantillon étiqueté , s'il existe un compatible avec . Supposons (pour obtenir une contradiction) que est une machine de Turing qui décide du problème de cohérence. $S$ $f\in C_n$ $S$ $K$

Nous faisons les conventions de notation suivantes. Identifiez avec via l'ordre lexicographique habituel. Pour , on dit qu'un TM "S-imprime" s'il accepte toutes les chaînes de correspondant aux indices st et ne le fait pas accepter (éventuellement en ne s'arrêtant) aucune des chaînes correspondant aux indices . Puisque (par hypothèse) est décidable, il s'ensuit que la fonction , définie comme étant la plus petite telle que certains TM dans $\Sigma^*$ $\mathbb{N}=\{0,1,2,\ldots\}$ $x\in\{0,1\}^*$ $M$ $x$ $\Sigma^*$ $i$ $x_i=1$ $x_i=0$ $K$ $\tilde K:x\mapsto k$ $k$ $C_k$ S-imprime , est calculable par Turing. Il s'ensuit en outre que la fonction , qui mappe un à la plus petite chaîne (lexicographiquement) telle que , est également calculable. $x$ $g:k\mapsto x$ $k\in\mathbb{N}$ $x\in\{0,1\}^*$ $\tilde K(x)>k$

Définissez maintenant le TM comme suit: S-imprime , où est l'encodage de , indique la longueur de chaîne, et le théorème récursion est invoqué pour affirmer l'existence d'un tel . Alors a une certaine longueur d'encodage,, et il S-imprime une chaîne, . Par construction, , et donc ne peut être imprimé en S par aucune MT avec la longueur de description $M$ $M$ $g(|\langle M\rangle|)$ $\langle M\rangle$ $M$ $|x|$ $M$ $M$ $\ell=|\langle M\rangle|$ $x_M\in\{0,1\}^*$ $\tilde K(x_M)>\ell$ $x_M$ $\ell$ ou plus court. Et pourtant, il est défini comme la sortie S-print d'une MT avec une longueur de description --- une contradiction. $\ell$

Aryeh
la source

Défi: convertir mon argument "infinitaire" via la calculabilité en argument finitaire via l'efficacité. Je pense que la réponse à la question de @ minkov est négative: vous ne pouvez pas apprendre efficacement une classe de fonction que vous ne pouvez pas évaluer efficacement. Je pense que cela continuera d'être vrai si vous allez au-delà du PAC approprié ou réalisable.

Aryeh