BIF7002 Séminaire interdisciplinaire de bio-informatique	Travail présenté à MAKARENKOV, Vladimir & BANIRÉ DIALLO, Abdoulaye
L’apprentissage machine par renforcement et les processus de décision markoviens Rapport à la suite de la présentation de Bogdan Mazoure du 10 mars intitulée « Introduction to Reinforcement Learning or how to track cell movements in an automated way »
Par : Mathieu Lemieux (LEMM23037808) & Pascal Tremblay-Dauphinais (TREP02128309)
Département d'informatique Université du Québec à Montréal 15 avril 2020

Introduction

L’apprentissage machine permet de construire et d’optimiser des modèles à partir de données empiriques et d’appliquer ensuite ceux-ci à divers processus prévisionnels et de prise de décision. C’est aujourd’hui un maillon central de ce que l’on nomme l’intelligence artificielle, cette capacité qu’ont certains systèmes ordinés (ordinateurs) à implémenter des fonctions que l’on associe généralement à l’intelligence humaine et animale, telle la résolution de problèmes et l’apprentissage. (Jordan & Mitchel, 2015)

L’apprentissage machine est en train de changer de façon importante plusieurs domaines scientifiques, des secteurs complets de l’économie ainsi que nos vies quotidiennes avec le nombre croissant de produits et services qui en intègrent la technologie ou en sont issus. Il existe différentes approches en apprentissage machine et l’une d’entre-elle, l’apprentissage par renforcement, consiste à optimiser un modèle mathématique prédictif à l’aide d’un système de punitions/récompenses (Mazoure, 2020). Particulièrement bien inséré dans le domaine du jeu, nous allons voir que l’apprentissage par renforcement trouve aussi des applications en biologie ou elle pourrait entre autres permettre de modéliser la dynamique d’évolution cellulaire à partir d’images de cellules en développement (Wang et al., 2018).

Apprentissage machine

Le but de l’apprentissage machine (Machine learning) est la création d’un modèle mathématique permettant de prédire, à partir d’un certain nombre de variables à l’entrée, la valeur d’une variable dépendante. Cette variable peut être catégorique lorsqu’il s’agit d’un algorithme de classification, ou continue lorsqu’il s’agit d’un algorithme de régression (Mazoure, 2020).

Si l’humain est bien sûr impliqué dans la programmation et la configuration de l’algorithme d’apprentissage, c’est l’ordinateur qui, par la suite, va utiliser les données qui lui sont soumises pour construire et optimiser un modèle mathématique permettant de prédire un résultat de façon probabiliste (en vue de prendre une décision sur une tâche à accomplir). L’ordinateur acquiert donc, d’une certaine façon, la faculté d’apprendre de manière empirique par rapport à une situation précise. (Jordan & Mitchel, 2015)

Dans un premier temps, tous les algorithmes d’apprentissage machine passent par une phase d’apprentissage. L’apprentissage est un processus itératif par lequel un jeu de données est soumis à maintes reprises au modèle. À chaque itération, une fonction mathématique évalue la performance du modèle dans son ensemble, puis les paramètres du modèle sont modifiés afin d’améliorer sa performance au prochain tour (Mazoure, 2020). L’optimisation fait souvent intervenir une série d’équations différentielles (comme c’est le cas pour les réseaux de neurones lors de la back-propagation) et consiste généralement par en un processus de Gradient-descent.

Par la suite, le modèle peut être testé sur un ensemble indépendant de données et sa performance peut ainsi servir de benchmark pour une comparaison avec d’autres modèles. Dans un cas classique, le jeu de données servant au test est isolé des données servant à l’entraînement dès le début (i.e. Holdout cross-validation). Cette méthode prive cependant le modèle de données pour son entraînement. Pour atténuer cet effet, il est possible de recommencer de façon répétée le processus d’apprentissage avec une nouvelle division des données à chaque fois, puis de sélectionner le meilleur modèle (i.e. k-fold cross-validation).

Finalement, le modèle peut être utilisé en situation réelle afin d’accomplir certaines tâches et être ainsi confronté à de nouvelles données. Il est parfois possible d’utiliser les nouvelles données pour poursuivre l’apprentissage en continu, bien qu’une solution externe n’existe pas toujours pour évaluer l’efficacité du modèle à ce stade.

Aujourd’hui, les algorithmes développés à l’aide de l’apprentissage machine se retrouvent embarqués à bord de véhicules autonomes pour l’estimation des paramètres optimums de conduite, intégrés à des appareils électroniques pour la reconnaissance de patterns dans les signaux d’électrocardiogrammes, dans des logiciels pour la traduction automatisée, la reconnaissance des caractères manuscrits ou la détection de transactions bancaires frauduleuses pour n’en nommer que quelques usages (Jordan & Mitchell, 2015).

Types d’apprentissages

On dit qu’un apprentissage est supervisé si le jeu de données soumis lors de la phase d’entraînement contient des étiquettes, c’est-à-dire la valeur du résultat attendu du modèle pour chacun des enregistrements. Cette valeur sert à mesurer la performance du modèle à chaque itération et les paramètres peuvent ainsi être optimisés de façon à réduire l’écart entre la valeur obtenue et la valeur réelle (l’étiquette).

Dans le cas d’un apprentissage non-supervisé, où aucune indication n’existe quant au résultat attendu, il s’agit généralement de découvrir les structures internes aux données et d’en déduire les catégories sous-jacentes. On parle alors de clustering, c’est-à-dire de regroupement des données en catégories (ici non-prédéterminées) et, selon l’implémentation, l’utilisateur peut spécifier le nombre de clusters final à atteindre (e.g. k-mean clustering). (Mazoure, 2020)

Finalement, il existe un cas intermédiaire entre apprentissage supervisé et non-supervisé, où le but à atteindre est connu mais la valeur intrinsèque de chaque action n’est pas étiquetée. Cet apprentissage dit par renforcement est basé sur un système de punitions/récompenses, reçues à la suite d’une série de décisions prises par l’ordinateur en fonction du modèle en cours; ce modèle étant ensuite ajusté de façon à maximiser la récompense (Kaelbling, 1996). Ce type d’apprentissage est souvent utilisé dans les jeux mais nous verrons qu’il peut aussi être appliqué à d’autres situations. (Van Otterlo & Wiering, 2012)

Apprentissage par renforcement

L’apprentissage par renforcement est le problème rencontré par un agent qui apprend par essais et erreurs ses interactions avec un environnement dynamique (Kaelbling et al., 1996). Dans un modèle d’apprentissage par renforcement, les notions d’agent, d’environnement, d’état et d’action sont donc centrales. Un agent évolue dans un environnement et il agit et se déplace de façon discrète selon un répertoire précis d’actions permises. Après chaque action, son état est modifié par les contraintes internes de l’environnement (voir Figure 1).

Ultimement, l’agent termine le jeu avec un certain score. L’apprentissage consiste à modifier les paramètres du modèle de prise de décision de l’agent itérativement à chaque partie pour maximiser sa performance à long terme. Contrairement aux autres types d’apprentissage machine, il n’y a pas de jeux de données initial en apprentissage par renforcement; il est créé au fur et à mesure que la partie se déroule. (Mazoure, 2020)

Chaîne de Markov, Probabilité de transition et stationarité

            Les chaînes de Markov sont utilisées pour modéliser les probabilité qu’un système passe d’un état donné à un autre lorsque cette probabilité ne dépend que de l’état du système au temps précédent. Chaque état transitionne immédiatement dans un autre état basé sur une certaine distribution de probabilités. Une matrice de transition représente l’ensemble des probabilités de transition d’un état à un autre. À chaque itération, ces valeurs peuvent être modifiées pour tenir compte des transitions réellement observées; la matrice de transition évolue donc dans le temps. Cette évolution peut cependant se stabiliser vers un état stationnaire représentant son comportement à long terme, et cet état est indépendant des conditions initiales. (Mazoure, 2020)

Processus de décision markovien et interactions entre agent et environnement

Figure 1. Interactions entre agent et environnement (sourece : Mazoure, 2020)

Les processus de décision markoviens sont similaires aux chaines de Markov mais font intervenir la notion d’action conditionnelle. Ils permettent de représenter les différents états dans lesquels un agent peut se retrouver, les différentes actions qu’il peut prendre, ainsi que les différentes récompenses/punitions associées aux différentes actions. (Mazoure, 2020)

Un MDP a les composantes suivantes (v. Figure 1) :

-           Un ensemble d’états initiaux

-           Un ensemble d’actions possibles

-           Un modèle de transition

-           Une fonction permettant de calculer la récompense

Le chemin précis emprunté (ou la suite/combinaison des actions entreprises) n’est pas prise en compte et représente généralement un ensemble combinatoire trop grand pour être testé de façon systématique. Seul l’état de l’agent au temps t est pris en compte lors de la prise d’action au temps t+1. (Jaakkola et al., 1995)

Policy function, Value function et équation de Bellman

La Policy function (π) est une fonction de densité qui représente la probabilité qu’une action particulière prise au temps t (parmi la liste des actions possibles) soit optimale sachant l’état de l’agent (la valeur à l’ensemble des variables décrivant l’agent) au temps t-1. C’est la fonction que l’on tente d’optimiser. (Mazoure, 2020)

La fonction de valeur (value function) permet quant à elle de calculer la somme attendue de récompenses sachant l’état au moment t et pour une Policy function donnée. Afin de calculer une fonction de valeur, on fait d’abord la somme des récompenses cumulées afin de mesurer la performance de l’agent, puis on introduit un facteur de récompense (reward factor) (γ) et on utilise l’équation de Bellman. (Mazoure, 2020)

On peut minimiser cette dernière de la façon suivante :

Apprentissage profond et Deep Q-Network (DQN)

Les algorithmes d’apprentissage par renforcement, tout comme ceux d’apprentissage supervisés, peuvent être implémentés à l’aide de réseaux neuronaux. Ces algorithmes d’apprentissage sont qualifiés de profonds lorsqu’il existe plus d’une couche de neurones cachés interconnectés ensemble. Une fonction loss permet de quantifier la performance et sert à l’optimisateur pour ajuster les paramètres du modèle. Il existe plusieurs optimisateurs (tels Adam et RMSProp) mais tous ne permettent pas au système de converger de façon aussi efficace selon le type de données en jeu. (Mazoure, 2020)

En 2015, une équipe a démontré l’efficacité de Deep Q-Network (DQN), un algorithme d’apprentissage profond par renforcement, pour jouer (et remporter!) des parties des populaires jeux d’Atari. (Mnih et al. 2013; Mnih et al. 2015; Mazoure, 2020)

Minima et maxima locaux et le compromis exploitation-exploration

            L’optimisation par gradient-descent ne mène pas toujours au résultat optimal. Par exemple, un robot dont l’objectif consiste à rejoindre l’issus d’un labyrinthe ne passera pas nécessairement par le chemin le plus court si chacune de ses déplacements a un coût unitaire inférieur (ou une récompense supérieure) à une série d’actions alternatives dont le coût total est inférieur mais dont l’une des actions individuelles a un coût supérieur. De façon à augmenter les chances d’atteindre le minimum/maximum global, l’agent doit donc prendre à l’occasion des décisions désavantageuses à court terme dans l’espoir qu’elles puissent mener à une stratégie optimale à plus long terme. La capacité à performer des actions non-avantageuse (exploration) doit être mitigée par celle à performer l’action ayant le meilleur potentiel à court terme (exploitation). (Mazoure, 2020)

(Mazoure, 2020)

Figure 2. Minimum local et exploration (sourece : Mazoure, 2020)

Overfitting

            On parle de overfitting lorsque le modèle, qui est optimisé à l’aide des données d’entraînement, échoue ou performe moins bien lorsque confronté aux données tests et en situation réelle. Cela se produit lorsque l’optimisation a été poussé trop loin sur des données d’entraînement ne reflétant pas suffisamment la diversité des données possibles en situation réelle.

Matériel et méthode

L’objectif de la partie expérimentale de ce rapport est de mesurer l’effet de certains paramètres sur l’efficience d’un algorithme de Q-learning à trouver une solution à un problème simple. Le code utilisé est tiré d’un tutoriel de reinforcement learning (https://pythonprogramming.net/q-learning-reinforcement-learning-python-tutorial/).

Environnement

L’environnement a été généré à l’aide du package OpenAI Gym. Ce package offre un ensemble d’environnements virtuels permettant de tester différents algorithmes de reinforcement learning. L’environnement sélectionné se nomme MountainCar-v0. Le but de ce jeu est d’amener une voiture au sommet d’une colline (voir figure 3). Le défi est que la colline est trop à pic pour être gravi directement et nécessite de prendre de la vitesse en effectuant un mouvement de balancier entre les 2 collines. L’interaction avec l’environnement se fait en utilisant la méthode .step(action). Les 3 actions possibles sont aller vers la droite, aller vers la gauche et ne rien faire. Un épisode de jeu se termine après 200 actions ou lorsque le drapeau est atteint. Chaque action renvoie un reward de -1 et atteindre le drapeau donne un reward de 0.

Figure 3 Représentation graphique de l’environnement “MountainCar-v0”du package OpenAI Gym.

Table-Q

L’algorithme de Q-learning nécessite la construction d’une table-Q, qui est un dictionnaire contenant les valeurs Q de toutes les actions possibles pour chaque état possible du jeu. Pour chaque utilisation de la méthode .step(), les valeurs de la position et de la vitesse de la voiture sont renvoyées. Un tuple contenant ces 2 valeurs est utilisé pour représenter l’état et sert de clé pour le dictionnaire. Les valeurs du dictionnaire sont les 3 valeurs Q des 3 actions possibles. Les valeurs Q sont initialisées aléatoirement.

Mise à jour des valeurs Q

Les valeurs Q de la table-Q sont mises à jour chaque fois que l’algorithme décide d’une action. Les mises à jour se font à l’aide de l’équation de Bellman (figure 4). Les paramètres d’intérêts sont le learning rate qui détermine l’importance du changement de la valeur Q à chaque fois qu’une action est exécutée et le discount factor qui détermine l’impact qu’aura la prochaine action sur la valeur Q modifiée.

Figure 4 Équation de Bellman.

Epsilon

L’algorithme de base est un algorithme glouton, car la plus grande valeur de Q détermine quelle sera la prochaine action. Cette approche limite grandement l’exploration du problème, car une fois un maximum local atteint l’algorithme n'essaiera plus aucune nouvelle solution. La solution à ce problème est de prendre une partie des décisions aléatoirement plutôt qu’à l’aide de la table Q. La proportion de décisions aléatoire est nommée epsilon et peut avoir une valeur allant de 0 à 1.

Paramètres expérimentaux et suivi des apprentissages

Les paramètres expérimentaux testés sont le learning rate, le discount factor, epsilon et le taux de diminution d’epsilon. Les conditions de base se retrouvent à la figure 5. Un seul paramètre sera changé à la fois.

Learning rate	0,1
Discount factor	0,95
Nombre d’épisodes par apprentissage	25000
Epsilon	1
Diminution d’epsilon	diminue linéairement de 1 à 0 pour les 12500 premiers épisodes

Figure 5 Paramètres expérimentaux de base.

Différentes informations sur les épisodes récents seront enregistrées tous les 100 épisodes. Ces informations sont le reward maximal et minimal ainsi que la moyenne des reward. La totalité des informations sera présentée sous forme de graphique afin de comparer les différentes conditions expérimentales.

Résultats

Variabilité entre apprentissages identiques

La première expérience vise à comparer 3 apprentissages différents ayant des paramètres identiques (figure 6). Dans les 3 cas, le premier succès apparaît légèrement après le 6000e épisode et les reward maximaux convergent vers des valeurs de -120 à -115. Les résultats sont relativement semblables même si certaines différences peuvent être observées comme le meilleur reward atteint pour tout l’apprentissage ou la courbe du reward minimal. Ces différences peuvent s’expliquer par le fait que la table-Q initiale est générée aléatoirement et que l’exploration du problème se fait aléatoirement.

Figure 6 Trois apprentissages ayant des paramètres identiques.

Discount factor

Cette expérience vise à déterminer l’effet du discount factor (figure 7). Des discount factor de 0,95 et de 0,9 semblent ne pas changer les résultats d’apprentissage. Des discount factor de 0,8 et 0,5 semblent empêcher l’apprentissage de converger vers des valeurs stables. De plus, un discount factor de 0,5 semble amener une plus grande variation des résultats et détériorer leur qualité.

Figure 7 Quatre apprentissages ayant des discount factor différents. Discount factor: haut gauche = 0,95, haut droite = 0,9, bas gauche = 0,8 et bas droite = 0,5.

Learning rate

Cette expérience vise à déterminer l’effet du Learning rate (figure 8). Le learning rate semble avoir un impact important sur la vitesse de découverte de la première solution car pour un learning rate de 0,05 celle-ci prend moins de 1000 épisodes, pour un learning rate de 0,1 et 0,2 celle-ci prend environ 6000 épisodes et pour un learning rate de 0,5 celle-ci prend environ 8000 épisodes. Un learning rate de 0,05 semble également améliorer la qualité générale des solutions trouvées.

Figure 8 Quatre apprentissages ayant des learning rate différents. Learning rate : haut gauche = 0,05 , haut droite = 0,1 , bas gauche = 0,2 et bas droite = 0,5.

Epsilon

Cette expérience vise à déterminer l’effet de l’epsilon (figure 9). Une valeur d’epsilon de 0,5 semble accélérer la découverte de la première solution à moins de 1000 épisodes plutôt que les 6000 épisodes d’un epsilon de 1. Ralentir la diminution de l’epsilon retarde l’apparition d’une solution à 10000 épisodes et empêche les résultats de converger.

Figure 9 Trois apprentissages ayant un epsilon ou une diminution d’epsilon différent. Epsilon: haut gauche = 1, haut droite = 0,5 , bas gauche = 1 avec diminution d’epsilon sur tous les épisodes plutôt que la première moitié des épisodes.

Discussion

Le résultat le plus clairement influencé par les paramètres testés est le temps qu’un apprentissage prend à trouver une solution pour la première fois. Ce temps peut être divisé par 6 en utilisant un epsilon de 0,5 ou un learning rate de 0,05 par rapport aux conditions de base. Cela suggère que des décisions trop souvent aléatoires ou une table-Q qui se modifie trop rapidement nuisent à la découverte de solution.

 Il est plus difficile de se prononcer sur l’impact des paramètres testés sur les valeurs maximales, minimales et moyennes de reward. Si l’on considère la variabilité des 3 apprentissages avec paramètres identiques, les différences de valeurs de reward des apprentissages avec des paramètres différents ne semblent pas significatives sauf dans un cas (pour une valeur de discount factor de 0,5). Une solution possible serait de générer encore plus d’apprentissages pour chacune des conditions expérimentales. Par contre, cette solution nécessiterait des modifications de notre approche du problème étant donné qu’avec le matériel informatique et le code utilisé chaque apprentissage de 25000 épisodes est géré manuellement et prend 15 minutes à exécuter.

Conclusion

Le Q-learning est une approche intéressante pour des problèmes simples et permet de se familiariser avec l’application des concepts de reinforcement learning. Cette approche devient rapidement très lourde si le système exploré contient trop d’états ou permet trop d’actions. Le Q-learning ne peut être appliquer à des problèmes plus complexes. D’autres approches devraient être privilégiées pour résoudre des problèmes se rapprochant plus de la complexité du monde réel.

Références

Documentation de OpenAI Gym. https://github.com/openai/gym/blob/master/README.rst

Jaakkola, T., Singh, S. P., & Jordan, M. I. (1995). Reinforcement learning algorithm for partially observable Markov decision problems. In Advances in neural information processing systems (pp. 345-352).

Jordan, M. I., & Mitchell, T. M. (2015). Machine learning: Trends, perspectives, and prospects. Science, 349(6245), 255-260.

Kaelbling, L. P., Littman, M. L., & Moore, A. W. (1996). Reinforcement learning: A survey. Journal of artificial intelligence research, 4, 237-285.

Mazoure, B. (2020). Introduction to Reinforcement Learning or how to track cell movements in an automated way. Conférence donnée à Montréal, Qc. le 10 mars 2020

Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., & Riedmiller, M. (2013). Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602.

Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., ... & Petersen, S. (2015). Human-level control through deep reinforcement learning. Nature, 518(7540), 529-533.

Van Otterlo, M., & Wiering, M. (2012). Reinforcement learning and markov decision processes. In Reinforcement Learning (pp. 3-42). Springer, Berlin, Heidelberg.

Wang, Z., Wang, D., Li, C., Xu, Y., Li, H., & Bao, Z. (2018). Deep reinforcement learning of cell movement in the early stage of C. elegans embryogenesis. Bioinformatics, 34(18), 3169-3177.