Image de couverture du post

2019-11-14 01:02 - Technique

J’ai utilisé du Machine Learning pour me recommander des bons jeux

Cet article est destiné autant aux connaisseurs qu’à une audience non initiée qui n’a jamais entendu parler de Machine Learning. Je présente mon approche pour me faire un système de recommandation de jeux personnalisé.

Pourquoi ?

Steam a son propre système de recommandations qui utilise probablement des technologies d’apprentissage automatique (Machine learning) également, mais leur système a plusieurs défauts qui le rendent généralement peu pertinent:

  • Steam n’a pas une quantification précise de mon appréciation des jeux: recommander un jeu après y avoir joué est facultatif et c’est un choix binaire: soit j’ai aimé, soit pas (alors que la réalité est beaucoup plus nuancée).
  • Steam doit utiliser un modèle générique pour fonctionner avec une grande variété d’utilisateurs, et un tel système a du mal à apprendre quels critères sont pertinents pour chaque utilisateur.
  • Steam est une entreprise et son but est le profit: leur système de recommandation est certainement biasé pour maximiser leurs revenus.

Une des approches de Steam pour faire des recommandations est le clustering, c’est-à-dire regouper des jeux similaires, et ensuite me proposer des jeux similaires à ceux auxquels j’ai joué. Par exemple sur la capture d’écran suivante de ma liste de recommandations, Steam a estimé que Secret Neighbor était similaire à Portal 2 et que je pourrais donc être intéressé. Sauf que les jeux multijoueurs et l’horreur ne sont pas trop mon truc, donc… bah… loupé, désolé Steam.

Secret Neighbor

Mon idée est donc de faire mon propre système de recommandations, qui marchera mieux que celui de Steam (car personnalisé pour moi en particulier).

Mais en fait, c’est quoi le Machine Learning?

Bon, en français ça se dit apprentissage automatique, mais je n’utilise pas ce mot parce que j’ai l’habitude de parler d’informatique en anglais. En gros c’est un méli-mélo de techniques informatiques qui partagent une idée commune: permettre à des machines de trouver des résultats sans avoir été explicitement programmées pour ces tâches, grâce à une phase d’apprentissage.

Mon approche utilise de l’apprentissage supervisé, c’est-à-dire que j’entraîne mon modèle sur un certain nombre de jeux que je connais déjà, en lui donnant des données annotées, i.e contenant non seulement des caractéristiques sur le jeu mais aussi une quantité entre 0 et 1 qui exprime combien j’ai aimé le jeu. Lors de l’entraînement, l’algorithme essaie de comprendre le lien entre les caractéristiques des jeux et leur note, et dans la phase de prédiction (ou inférence), je donne à l’algorithme des jeux que je ne connais pas et lui demande quelle note il leur mettrait. Je peux lui demander de faire ça pour tous les jeux du magasin Steam et de me lister ceux auxquels il a attribué le plus haut score.

Construire l’ensemble de données

La première étape d’un système de recommandations est de récolter des données sur un large ensemble de jeux, dans mon cas tous ceux du magasin Steam.

Pour cela j’ai construit un algorithme de scraping, c’est-à-dire un programme qui collecte des données. Plutôt que d’utiliser le magasin en ligne de Steam comme un humain, mon algorithme a utilisé des APIs (Application Programming Interfaces), c’est-à-dire en gros des protocoles de communication qui permettent à des programmes d’interroger un site ou service.

J’ai croisé les données de plusieurs APIs: celles officielles de Steam (api.steampowered.com et store.steampowered.com/api) et une API non officielle du site SteamSpy (steamspy.com/api.php). La raison est que dans tout le bazar des interfaces officielles de Steam, je n’ai pas trouvé toutes les données que je voulais.

Parmi les informations que j’ai récoltées, on trouve par exemple pour chaque jeu:

  • Son score Metacritic.
  • Son score Steam (ratio de recommandations positives/négatives)
  • Date de sortie.
  • Tags que j’estime pertinents (par exemple “Story Rich”, “Great Soundtrack”)
  • Support de la manette (je n’aime pas jouer au clavier)
  • etc…

Ensuite, j’ai donné une note aux jeux. D’abord une note à ceux auxquels j’ai joués, ce qui est assez évident. Mais ce n’est pas suffisant. En effet:

  • Les jeux auxquels j’ai joués ne sont pas représentatifs de l’ensemble des jeux du magasin Steam.
  • La grande majorité des notes que j’ai mises étaient très positives. Mon modèle doit connaître non seulement ce que j’aime, mais aussi ce que je n’aime pas, pour faire la différence.

J’ai donc doublé le nombre de jeux annotés en tirant des jeux au hasard, et si je tombais sur des jeux dont j’étais certain qu’ils ne m’intéressaient pas, je les ajoutais avec une note de zéro.

Sur les plus de 37000 jeux que comptent Steam, mon ensemble de données n’a gardé que les 3070 jeux qui apparaissent sur Metacritic, et parmi ceux-ci 115 ont un score, dont une moitié a un bon score (jeux auxquels j’ai joués), et l’autre moitié a un score nul.

Analyse des caractéristiques pertinentes

On pourrait penser à tort que le score Metacritic ou le score Steam d’un jeu suffiraient à trouver quels jeux j’apprécie ou non, mais c’est sans compter que chaque individu a des goûts différents. L’image ci-dessous illustre ceci en mettant en relation le score que j’ai attribué aux jeux auxquels j’ai joués, et leur note Metacritic ou note Steam:

Features vs score

On remarque que les jeux qui m’ont plu ont tous un relativement bon score Metacritic/Steam, mais l’inverse n’est pas vrai: beaucoup de jeux qui ont un bon score Metacritic/Steam ne m’ont pas beaucoup plu.

Ces caractéristiques ne suffisent donc pas à expliquer pourquoi un jeu me plait ou non. Comme mentionné plus haut, mon intuition a été d’utiliser le système de tags Steam pour ajouter des informations pertinentes sur chaque jeu qui permettront au modèle de mieux apprendre mon comportement. Ces tags peuvent être:

  • Des tags positifs, c’est-à-dire qui vont en général augmenter le score d’un jeu.
  • Des tags négatifs, c’est-à-dire qui vont pénaliser un jeu.

Je ne peux pas utiliser tous les tags disponibles pour des raisons que j’évoquerai dans la section suivante. Je dois trouver un nombre limité de tags. Trouver les bons tags a été un processus de tâtonnement en évaluant comment différents tags influençaient mon modèle.

Entraîner la machine

Cette section devient moins triviale mais je vais faire en sorte de la rendre à peu près compréhensible quand-même. Le modèle dont je me suis servi est appelé neural network ou réseau de neurones. L’idée est de simuler grossièrement le fonctionnement du cerveau humain.

Lors de la construction de mon ensemble de données, j’ai transformé toutes les caractéristiques en valeurs numériques. Le réseau de neurones est une suite de couches où les neurones de chaque couche réagissent aux valeurs de la couche précédente pour générer une valeur à leur tour: les valeurs de la couche de gauche sont les caractéristiques de chaque jeu et la valeur de la couche de droite est le score que j’ai attribué au jeu. Le réseau apprend en modifiant la manière donc chaque neurone génère une valeur, grâce à un procédé magique appelé backpropagation. En fait c’est pas magique du tout mais bon c’est un chouilla trop long à expliquer pour cet article, donc si vous êtes intéressé, euh… bah suivez ce cours de Stanford, c’est gratuit, en ligne et c’est comme ça que j’ai appris. Si vous voulez expérimenter rapidement les réseaux de neurones de manière interactive, vous pouvez aussi utiliser le playground Tensorflow.

Un réseau de neurones très simple pour notre problème serait:

réseau de neurones simple

Le vrai réseau de neurones que j’ai utilisé a 11 caractéristiques en entrée, et deux couches intermédiaires de 16 neurones chacune.

Un problème auquel on se heurte vite est appelé overfitting: en raison du faible nombre d’exemples annotés utilisés pour entraîner le réseau de neurones, il s’adapte trop aux exemples annotés et performe moins bien sur des jeux qui n’ont pas été utilisés pour l’entraîner. C’est un problème important parce que cela signifie que la qualité des prédictions sera moindre. Un moyen de mesurer ça est de diviser l’ensemble d’entraînement en deux: une partie (par exemple 70%) est utilisée pour entraîner le modèle. L’autre partie (ici 30%) est utilisée seulement pour évaluer la performance du modèle (ces jeux sont inconnus du modèle puisqu’ils ne sont pas utilisés pour l’entraîner). Si on évalue les erreurs de prédictions au fur et à mesure de l’entraînement, sur chacuns des deux ensembles, on observe (moyenne des carrés des erreurs):

overfitting

Ici, l’erreur sur l’ensemble d’entraînement diminue, c’est-à-dire que l’algorithme progresse sur les exemples qu’il connaît. Mais au bout d’un moment, ses prédictions sur les exemples inconnus s’empirent parce que l’algorithme se spécifie trop aux exemples connus.

J’ai donc appliqué un procédé appelé régularisation, qui consiste, en gros, à entraîner l’algorithme en pénalisant une importance trop inégale des différentes caractéristiques. La courbe d’apprentissage ressemble maintenant à ça:

regularized

On a divisé l’erreur presque par deux sur l’ensemble de validation, tandis qu’elle a légèrement augmenté sur l’ensemble d’entraînement (le modèle est moins spécifique aux exemples connus). Le modèle est prêt à faire des prédictions.

Résultats

Mon algorithme m’a calculé pour chaque jeu du magasin Steam auquel je n’ai pas donné un score, quel score il pense que je lui donnerais. Les 5 jeux à obtenir le meilleur score selon l’algorithme sont:

rang nom du jeu
1 Return of the Obra Dinn
2 Mutazione
3 The Wolf Among Us
4 Dark Souls III
5 SOMA

Je dois dire que je suis impressionné par la qualité des résultats. Les deux premiers jeux sont déjà dans ma liste de souhaits (ce que l’algo ne savait pas!), et The Wolf Among Us et SOMA sont également très susceptibles de m’intéresser. Dark Souls III pas trop parce que c’est trop sombre et difficile.

Bilan

Je débute en Machine Learning donc ne prenez pas trop mon mot à la lettre (c’est ce que je fais professionnellement mais je suis plutôt du côté optimisation sur GPU).

Je suis très satisfait des résultats, et ça a été un exercice formateur.

Vous pouvez trouver le code source sur GitHub.

Image de couverture tirée de NieR Automata.

nyri0 (2019-11-14 20:13)

Additional details: the following table contains the Pearson correlation coefficients of various features wrt the score.

feature correlation with the score
Metacritic 0.395986129743881
Reviews 0.280593754607957
story rich 0.24654041479133
great soundtrack -0.130778359562621
atmospheric 0.441390265757566
date 0.150532820912653

The tag “atmospheric” has the highest correlation, so it is very likely to define whether I liked a game or not. Surprisingly the tag “great soundtrack” has a negative correlation. It means that it is correlated to the score that I gave to the games, but it has the tendancy to go against it. It’s weird but we have to keep in mind that this is calculated among a set of games that I mostly liked, and this tag doesn’t appear much, so one or two games that I didn’t like with this tag can influence the correlation a lot.

nyri0 (2019-11-15 21:45)

Update: had a look further down the list and made interesting discoveries such as Pinstripe and The Gardens Between! :)

nyri0 (2019-11-15 23:22)

Another update: I used random forests and achieved the same quality of results as neural networks with no effort whatsoever!! Most of the top games are pretty similar with both approaches. The code is also on GitHub.

Log in to post a comment.