Réseau de neurones et apprentissage

[Uhrond]

Bonjour à vous,

J'ai développé un algo de réseau de neurones, initialement prévu pour faire de la reconnaissance d'écriture (en utilisant la base de donnée de chiffres manuscrit MNIST) et j'ai obtenu de bon résultat (97% de reconnaissance sur 10000 chiffres inconnus)
J'ai utilisé la méthode normal : je soumet l'image d'un chiffre, le réseau me donne une sortie et je "rétro-propage" l'erreur par rapport à ce qui est attendu.

Jusque là, tout fonctionne à merveille.
Aujourd'hui, je souhaite apprendre à un réseau à jouer à un jeu (je commence par du morpion, c'est plutôt basique). Mais voila je ne sais pas trop comment m'y prendre :
A quel moment lui rétro-propager une erreur ? Un coup au moment d'être joué n'est pas forcement bon ou mauvais, seul l'issue de la partie nous le dira.
Mais si il perds on ne peux pas non-plus lui dire que toutes les positions de la partie étaient mauvaises.... Je sèche un peu.

Avez-vous des idées ou des liens vers de la documentations la-dessus ?

Je vous remercie,
-----

[goaoute]

Comment veux-tu faire apprendre si tu n'a pas de cycle essai/erreur
Mais par contre tu peux mettre en place une stratégie quand le pion est menacé, car là tu retrouve de l'essai/erreur

[Juju41]

Salut,

tu peux chercher "tic tac toe machine learning" dans ton moteur de recherche préféré, il y a pas mal d'exemples.

[Tryss2]

Une bonne méthode, c'est d'entrainer le réseau sur un "paquet" de parties.

Si tu génères 500 parties au hasard, tu va avoir un % de victoire pour chaque position, et tu entraines ton réseau la dessus.

C'est ce que fait Alpha Zero : il va jouer x parties avec le réseau a, entrainer un réseau b sur les n*x parties les plus récentes, faire jouer a contre b, et si b est plus fort que a, b devient le nouveau réseau, et on recommence.

Tu peux regarder le code de LeelaZero, un programme open source basé sur ce principe :

https://github.com/gcp/leela-zero

[A voir en vidéo sur Futura]

[invite73192618]

A quel moment lui rétro-propager une erreur ? Un coup au moment d'être joué n'est pas forcement bon ou mauvais, seul l'issue de la partie nous le dira.
Mais si il perds on ne peux pas non-plus lui dire que toutes les positions de la partie étaient mauvaises.... Je sèche un peu.

Avez-vous des idées ou des liens vers de la documentations la-dessus ?

+1 Tryss2 la meilleure approche connue est effectivement celle d'Alpha Zéro, où le coeur de l'idée est d'alterner entre des phases de self-play et des phases d'entrainement classiques. Par contre on pourrait simplifier un peu les choses plutôt que d'essayer de reproduire tout l'arsenal algorithmique utilisé (ne serait-ce que pour comprendre comment chaque élément s'ajoute aux autres).

Une façon simple d'implémenter cela est de se limiter à un policy network, i.e. un réseau de neurone (initialement au hasard) qui prend un plateau en entrée et sort une distribution de probabilité de jouer chaque case au prochain coup. Cette distribution de probabilité est utilisée pour déterminer quels coups sont joués pendant une partie en self-play. A la fin de chaque partie le résultat détermine si les coups étaient mauvais ou bon (oui oui, l'ensemble des coups). A la fin de chaque paquet de partie on lance un apprentissage classique pour améliorer le réseau en vue de la prochaine phase de self-play. Au bout d'un certain nombre d'alternance le niveau plafonne, idéalement sur un niveau de jeu parfait (ou surhumain, selon le jeu).

Évidement c'est une approche qui semble à priori catastrophique pour la raison que tu mentionnes (certains coups étaient peut-être bons même si la partie était perdue au final) mais aussi parce que le réseau peut facilement se bloquer dans un optimum local (cesser d'explorer des coups potentiellement bons, surapprendre une stratégie qui ne marche que contre un réseau très mauvais -celui en cours d'évaluation). Il y a donc un certain nombre de précautions à prendre pour que cela marche:
-le choix devrait être faire suivant une normalisation sur les coups autorisés (les autres cases sont ignorées, et auront une erreur de 0 par définition)
-plutôt que de choisir les coups systématiquement selon la distribution de probabilité donné par le réseau, certains coups seront choisis au hasard avec une probabilité T, avec T un hyperparamètre (température) qui peut par ailleurs diminuer avec le temps (de manière à ce que les premiers coups soient plus variables) ou être indexé sur le niveau de performance
-plutôt que de prendre l'ensemble des coups joués à chaque partie pour la base d'entrainement, il est possible de ne choisir que un ou quelques coups par parties.
-A l'inverse c'est probablement une bonne idée d'augmenter cette base de donnée par des positions équivalentes (symétries du plateau)
-et d'être plutôt rapide à stopper l'entrainement tôt

A mon avis ceci devrait être suffisant pour arriver à un joueur parfait au morpion. Si je trouve le temps je l'essaierais moi aussi.

Alternativement une autre approche serait d'utiliser un evaluation network, i.e. un réseau de neurone qui prend un plateau en entrée et sort une probabilité de gagner. Dans ce cas l'apprentissage est moins douteux, par contre la décision des coups est alors plus compliquée: il faut construire un arbre des possibles avec à chaque noeud une probabilité de gagner qui est remonté depuis les noeuds terminaux selon l'algorithme minimax. Dans le cas du morpion je ne le recommanderais pas car la profondeur du jeu est tellement limitée que le minimax est très suffisant pour trouver la solution tout seul...

Si toutefois tu vas sur un jeu plus demandant (morpion 3D?) alors l'une ou l'autre approches sont possibles, et les deux en combinaison c'est presque alphazero (i.e. nonobstant quelques trucs supplémentaires...)

[Bounoume]

ton intervention me mène à deux réflexions très différentes:
la première:
je saisis mal l'initialisation puis l'enchaînement des groupes de parties!
Peux-tu rectifier ce que je crois avoir retenu?


le début:
la partie n° 1: qui manipule les noirs, qu manipule les blancs? le réseau (initialisé au hasard)? en face, le hasard ?


pour le réseau (initialisé au hasard) la variable d'entrée, c'est l'état initial du goban? donc un tableau de 19*19 positions des noirs/blancs ?
en sortie, dans la matrice (ij) des coups possibles, on a la probabilités de chaque coup possible (ij) donnée par le réseau?

alors le joueur (réseau') joue quoi?
le coup trouvé le + 'probable'?

...... ou alors on continue sur ..... plusieurs parties: autant que de coups joués comme qualifiés de 'très probables'par la sortie du réseau?
Ce qui ferait une croissance exponentielle du nombre de parties en fonction du nombre de coups????


Après, je pense avoir compris : dans ce nombre de parties, estimation du résultat de chacune, choix des 'meilleures', fourniture en entrée des états successifs du goban, lecture de chaque réponse du réseau.... calcul de l'erreur et rétropropagation (?)... / modifiaction des poids des connexions

ceci pour chaque état successif du goban dans chacune des parties retenues...
Mais alors, quid des 'probabilités'? Comment comparer UN coup réel, et une distribution de probabilités? Le coup joué est affecté de p=1, tous les autres possibles de zéro?

Voila pour combler mon peu de connaissances du sujet.....

Ma deuxième réflexion:
dans ce jeu de go, les humains on dû définir des concepts, des classifications, des raisonnements et des stratégies basées sur ces clasifications et ces concepts.
Basiquement ces stratégies et séquences conditionnelles, qui sont le fruit de l'analyse de nombreuses partie, est-ce que AlphaGo en crée, en utilise, et en explicite de façon intelligible?
Si ce n'est pas fait, est-ce que ça serait envisageable, et comment?
cordialement

[pm42]

dans ce jeu de go, les humains on dû définir des concepts, des classifications, des raisonnements et des stratégies basées sur ces clasifications et ces concepts.

Plein. Mais on a du mal à transmettre ces concepts à un ordinateur aujourd'hui que ce soit par programmation classique ou par apprentissage.

Basiquement ces stratégies et séquences conditionnelles, qui sont le fruit de l'analyse de nombreuses partie, est-ce que AlphaGo en crée, en utilise, et en explicite de façon intelligible?

La 1ère version, implicitement puisqu'elle a appris à partir de dizaines de milliers de parties humaines de haut niveau.
Les versions suivantes, absolument pas.

Si ce n'est pas fait, est-ce que ça serait envisageable, et comment?

Tout dépend de ce que tu entends par là mais vu que sans jamais voir une partie humaine ou connaitre les concepts en questions, AlphaGo Zero explose tout ce qui existe, l'intérêt est limité en performance pure.

[invite73192618]

la partie n° 1: qui manipule les noirs, qu manipule les blancs? le réseau (initialisé au hasard)? en face, le hasard ?

Les détails varient selon les configurations (sans qu'on sache vraiment laquelle est la meilleure). Pour alphazero il y a un réseau champion statique (initialement au hasard) contre des réseaux challengers qui partent de ce même réseau et tentent d'apprendre à partir des nouvelles parties (conceptuellement il pourrait y avoir un seul challenger, mais comme le calcul se distribue bien il y en a généralement plusieurs en attente d'affronter le champion et plusieurs en mode apprentissage). Si un challenger bat le réseau champion de manière reproductible (i.e. disons au-dessus de 60% du temps) alors il devient le nouveau champion.

pour le réseau (initialisé au hasard) la variable d'entrée, c'est l'état initial du goban? donc un tableau de 19*19 positions des noirs/blancs ?

Oui. En fait alphazero utilise non pas le plateau courant mais une série de quelques plateaux (le courant + le dernier avant lui + l'avant-dernier, etc. sur 9 coups (de mémoire le 9)). Ici encore je ne pense pas que personne ne sache si c'est la meilleure idée (perso cela me semble douteux).

en sortie, dans la matrice (ij) des coups possibles, on a la probabilités de chaque coup possible (ij) donnée par le réseau?

Oui (j'assume que tu parles du policy network).

alors le joueur (réseau') joue quoi?
le coup trouvé le + 'probable'?

Un coup au hasard, mais avec un hasard biaisé par le policy network: si le réseau sort une probabilité de 90% de chances pour un coup x, alors il a 90% de chances de jouer ce coup. (nonobstant l'histoire de la température)

Ce qui ferait une croissance exponentielle du nombre de parties en fonction du nombre de coups????

Donc non, il prend un seul chemin par partie, au "hasard biaisé".

Après, je pense avoir compris : dans ce nombre de parties, estimation du résultat de chacune, choix des 'meilleures', fourniture en entrée des états successifs du goban, lecture de chaque réponse du réseau.... calcul de l'erreur et rétropropagation (?)... / modifiaction des poids des connexions

Yep

ceci pour chaque état successif du goban dans chacune des parties retenues...

Pas nécessairement, il peut être utile de sous-échantillonner les états.

Mais alors, quid des 'probabilités'? Comment comparer UN coup réel, et une distribution de probabilités? Le coup joué est affecté de p=1, tous les autres possibles de zéro?

Yep, c'est une façon. Une autre façon serait de faire jouer disons 100 parties par état sélectionné et de calculer des probabilités plutôt que d'avoir des oui/non. Ultimement la convergence après un grand nombre de partie rend ces méthodes en théorie équivalentes (la seconde est toutefois plus couteuse mais rend l'apprentissage plus smooth, ce qui peut être le meilleur choix).

Mais on a du mal à transmettre ces concepts à un ordinateur aujourd'hui que ce soit par programmation classique ou par apprentissage.

A vrai dire il n'est pas du tout évident que ces concepts soient utiles pour jouer. S'ils l'étaient, on devrait être capable de faire un système expert avec un niveau de jeu intéressant, non? Au mieux ils sont utiles pour sélectionner quelles parties il faut apprendre, au pire ils sont carrément inutiles -des rationnalisations plutôt que des raisons.

La 1ère version, implicitement puisqu'elle a appris à partir de dizaines de milliers de parties humaines de haut niveau.

En fait on ne peut pas exclure, mais vu que la majorité des coups étaient ensuite en self-play il n'est pas évident de savoir s'il restait vraiment du savoir humain ou s'il a été complêtement effacé au bout d'un certain temps. A l'inverse on pourrait argumenter que certains choix (en particulier le nombre de tableaux en entrée) continuent de reflèter un savoir humain empirique même dans alphazero.

Si ce n'est pas fait, est-ce que ça serait envisageable, et comment?

Question intéressante. Une façon simple serait de faire surreprésenter les situations/parties pour lesquelles on pense que le savoir humain apporterait quelque chose, en biaisant les chances que le réseau suive les coups recommandés. Tout le reste de la machinerie peut alors rester tel quel et le résultat sera un réseau qui sera biaisé (pas nécessairement en bien!) selon les conseils humains.

[Bounoume]

A vrai dire il n'est pas du tout évident que ces concepts soient utiles pour jouer. S'ils l'étaient, on devrait être capable de faire un système expert avec un niveau de jeu intéressant, non? Au mieux ils sont utiles pour sélectionner quelles parties il faut apprendre, au pire ils sont carrément inutiles -des rationalisations plutôt que des raisons.

Dans le cas particulier du jeu de go, très possible.
par contre il y a des domaines relevant du monde réel (je penserais à des manipulations génétiques, à du codage informatique, à de l'ingénierie industrielle....) , où il y a bien des 'formes' à traiter, mais aussi des règles supérieures simples, de nature logique, qui régissent les classes d'objets caractérisables par ces 'formes' .

Je ne suis pas sûr que l'apprentissage direct par des "exemples" présentés suffise pour que le réseau intègre implicitement les lois qui régissent le modèle, et apprenne un comportement conforme aux objectifs (par exemple, en génétique, optimiser la séquence, le site, les risques...)

Pour moi, il faudrait parfois l' application de règles -une fois reconnues les cibles concernées (par les formes de certains de leurs attributs). Ceci en référence avec des connaissances formalisées pré-établies par la science ou la technique.

[invite73192618]

Pour moi, il faudrait parfois l' application de règles -une fois reconnues les cibles concernées (par les formes de certains de leurs attributs). Ceci en référence avec des connaissances formalisées pré-établies par la science ou la technique.

D'accord, donc tu pensais à des rêgles rigides plutôt qu'à des "conseils à adapter selon le cas" (ce qui est le cas le plus courant au jeu de go). Pour ajouter cela une façon naturelle serait 1) d'utiliser ces rêgles pour déterminer que certains coups sont interdits et 2) annuler l'exploration de ces coups. Cette dernière étape existe déjà ("-le choix devrait être faire suivant une normalisation sur les coups autorisés (les autres cases sont ignorées, et auront une erreur de 0 par définition)"), il suffit de l'adapter pour ajouter n'importe quelle rêgle souhaitée.

[Uhrond]

Bonjour à tous et merci pour toutes vos réponses très utiles.

J'ai réussi à obtenir un joueur parfait au morpion de la façon suivante :
- 9 neurones en entré et 1 en sortie
- le reseau est initialisé aleatoirement et joue contre lui-même (avec un peu de hasard dans le choix des coups)
- je prends une certaine position de jeu et je calcul une centaines de parties differentes à partir de cette position
- je calcul le pourcentage de parties gagné + 0.5 fois les parties nulle
- je retropropage cette valeur dans le réseau.
- à chaque tour de jeu, je propose tous les coups possible au réseau et je garde celui qui a la meilleur valeur.

Après 3-4 heures d'apprentissage il devient imbattable (c'est peut etre pas super optimisé)

Maintenant que ce problème est resolu je vais allé plus loin (toujours plus) en essayant cette même technique pour l'apprentissage du puissance 4, qui a nettement plus de possibilités de jeu...
On verra pour passer aux échec ensuite

[invite73192618]

Cela me rappelle une heuristique qui était utilisée dans alphago première version, où un mini policy net était utilisé sur quelques dizaines de parties en self-play pour obtenir un % de victoire (c'était utilisé en queue d'arbre). Autrement dit c'était une reconstruction fonctionnelle d'un value net à partir d'un policy net. Ici tu proposes une approche miroir: construire l'équivalent fonctionnel d'un policy net à partir d'un value net. J'aime beaucoup

Par contre je suspecte que l'apprentissage serait meilleur si tu remplaçais ta dernière commande (garde celui qui a la meilleure valeur) par un coup au "hasard biaisé" (au hasard selon une distribution de probabilité proportionnelle à la probabilité de gagner). Cela ne fera (probablement) pas (une grande) différence au morpion qui est trop simple pour être exigeant, mais au puissance 4 tu devrais commencer à voir les bénéfices. Par ailleurs c'est assez simple de prévoir que cette heuristique soit turné on ou off selon que le réseau est en mode apprentissage ou en mode compétition.

[pm42]

10 neurones pour gagner au morpion ? Je trouve ça impressionnant quelque part.

[Uhrond]

Merci pour le conseil Jiav, je me pencherai sur la question.
pm42, j'ai au total beaucoup plus de neurones :
9 en entrées, deux couches de 100 neurones chacune et 1 en sortie
(la valeur des couches a été prises complètement au hasard, je ferai des tests pour voir avec quel "minimum" de neurones ça fonctionne)

[pm42]

Oui, je me disais que 10 en tout ce n’était pas beaucoup. Tu as essayé avec moins dans les couches intermédiaires ?

[Uhrond]

Pour le moment non mais je vais le tester

Bounoume parle de "concept" à apprendre pour jouer au jeu. J'ai été surpris de voir à quelle vitesse (quelques minutes d'apprentissage) mon réseau à compris qu'il fallait toujours jouer en premier sur la case du milieu au morpion et sur la colonne du milieu au puissance 4.

[invite73192618]

je vais le tester

Perso je serais surpris que tu ai besoin de plus de neurones (au total dans les couches cachées, i.e. excluant les entrées et sorties) qu'il n'y a de coups successifs possibles dans une partie de morpion. Donc 9 max.

[Uhrond]

En effet, avec seulement 9 neurones (9-9-1) ça fonctionne toujours. Cest beaucoup plus rapide (20-30mn d'apprentissage) et olus léger... je l'aurai pas cru

[invite73192618]

En fait c'était prédictible en remarquant que la tâche est presque linéaire: une grosse activation centrale, une moyenne sur les coins, une faible sur les 4 restants, et déjà on a une rêgle qui tient presque la route. Après chaque neurone dans les couches cachées amène l'équivalent d'un "if then ", et comme la tâche comportementale ne nécessite que quelques ajouts de ce type alors un petit nombre de neurone devrait suffire. Ce n'est pas un raisonnement 100% waterproof parce qu'il ne suffit pas de montrer qu'un faible nombre de neurone est suffisant -il faut aussi que la rétropropagation soit capable de les paramétrer. Mais dans un cas aussi simple cela restait un pari raisonnable.