the fonction de parité est une fonction d'un vecteur de n bits et de sorties 1 si la somme est étrange et 0 sinon. Ceci peut être considéré comme une tâche de classification où la n entrée est les caractéristiques.
Y a-t-il un algorithme d'apprentissage de la machine qui serait capable d'apprendre cette fonction? Des forêts de décision clairement aléatoires ne réussiraient pas, puisque tout sous-ensemble strict de fonctionnalités n'a aucun pouvoir prédictif. De plus, je pense qu'aucun réseau de neurones d'une profondeur fixe ne réussirait, car le calcul de la fonction de parité n'est pas dans la classe de complexité AC0 .
3 Réponses :
Qu'en est-il de la classification des processus gaussiens? Vous pouvez former votre modèle par le vecteur d'entrée N-dimensionnel et la sortie de bit de parité à 1 dimensions. Ensuite, pour toute entrée de test, vous pouvez demander une prédiction. Vous pouvez vérifier ce livre en ligne.
http://www.gaussianprocess.org/gpml/chapters/
Le chapitre 3 aborde le problème de la classification.
SVM polynomial peut faire cela. Encodez les zéros comme 1 et ceux que -1. Pour n variables (bits), vous avez besoin d'un noyau polynomial de degré n. Lorsque le noyau est calculé, il calcule également implicitement la valeur X1 * x2 * ... * xn (où XI est la version de la version I-ème). Si le résultat est -1, vous avez un nombre impair de celles, sinon vous en avez un nombre pair.
Si je ne me trompe pas, les réseaux de neurones devraient également être capables de le calculer. Autant que je me souvienne, les réseaux de neurones avec 2 couches cachées et des unités sigmoïdes sont capables d'apprendre toute fonction arbitraire.
Bon point sur le SVM polynomial! Un NN avec une couche cachée est de trivialement capable de calculer toute fonction booléenne, mais les couches cachées devraient alors se développer de manière exponentielle en n.
Je suppose que j'étais sous la fausse impression que NNS était en quelque sorte équivalente à des circuits booléens.
Les réseaux neuronaux peuvent représenter et apprendre la fonction de parité avec une seule couche cachée avec le même nombre de neurones que les intrants. Le fait que la fonction de parité ne soit pas dans AC0 est un fait sur les circuits de portes booléennes, mais les percepteurs multicouches (comme couramment utilisé) peuvent avoir des poids à valeur réelle, ce qui fait toute la différence.
Un exemple de solution explicite serait les suivants, en supposant des entrées qui résout le problème de la parité.
Vos demandaient, cependant, sur les algorithmes d'apprentissage de la machine qui peuvent apprendre cette fonction. Selon la section "parité" dans [2], la réponse est qu'au moins pour le petit [1] Franco, Leonardo et Sergio A. Cannas. "Propriétés de généralisation des réseaux modulaires: mise en œuvre de la fonction de parité." IEEE transactions sur les réseaux de neurones 12.6 (2001): 1306-1313.
[2] Rumelhart, David E., Geoffrey E. Hinton, et Ronald J. Williams. Apprendre les représentations internes par propagation d'erreur. N ° ICS-8506. Californie Univ San Diego La Jolla Inst pour la science cognitive, 1985. N , n des unités cachées et une fonction d'activation de signe (décrite par exemple dans [1]): < / p>
k 1s dans l'entrée, les premiers unités masquées k enverront un 1 à la sortie, le reste un zéro.
N , la propagation arrière sur un réseau de neurones à une couche peut apprendre la fonction et, en fait, Apprendre un réseau très similaire à celui décrit ci-dessus.
Pour fixe n , ne serait-il pas un perceptron à deux couches avec une couche cachée suffisamment grande suffisamment?
Eh bien, oui ça le ferait. Si l'on possède un nœud dans la couche cachée pour chaque combinaison 00011110101 des bits d'entrée, il est trivialement possible. Le nombre de nœuds cachés augmentera alors de manière exponentielle avec n.
Habituellement, vous devez utiliser environ 2 * N nœuds cachés dans votre MLP avec une couche cachée et cela devrait fonctionner. BackPropagation standard est un algorithme d'optimisation obsolète pour Anns. Je suggérerais que Levenberg-marquardt, le gradient de conjugué, le quickprop ou le rprop à la place.
Alfa: À droite, mais dans ce cas, je ne pense pas que de nombreux nœuds de couches cachées fonctionneront.