Contenus
ToggleProjet théorie des langages : Automata
Ceci est le premier projet théorie des langages.
ETC: 15 hours (deadline – 5 classes)
2-3 students per team
Please take your time on both quality and contents
Associate professor and assistant professors will not answer questions about the project.
Barème: 40 points
- 15 Points
- 10 Points
- 15 points
“-Why is it so difficult for you to accept my orders if you're just a machine? -Just a machine? That's like saying that you are just an ape.”
Partie 1 : Des données lisibles et compréhensibles
« Jacq Vaucan: Funny, you were supposed to help us survive.
Blue Robot: Surviving is not relevant. Living is. We want to live. »
Après avoir aperçu un robot se réparant seul, un agent lui tire une balle dans la tête, rendant son biokernel apparemment illisible et inutilisable. Jacq Vaucan, agent d’assurance travaillant pour la ROC, est chargé d’enquêter sur l’origine de cette malfaçon, ce qui le conduit à découvrir une série d’anomalies et de comportements étranges de la part des automates.
Au cours de son enquête, il est amené à s’intéresser à un robot soudeur, qui s’immole par le feu devant ses propres yeux, brisant ainsi le second protocole. Ayant relaté ce fait, Jacq n’est pas cru par ses pairs, et poursuit néanmoins sa recherche d’un « Horloger », personne supposée capable d’un exploit technique tel que le contournement théoriquement impossible des protocoles.
Devenu méfiant de la ROC, Jacq décide d’aller voir le Docteur Dupré, brillante chercheuse en robotique qui parvient à faire parler le biokernel endommagé et à le copier sur le biokernel d’une Cleo, devenue alors capable de se réparer elle-même et d’apprendre extrêmement vite. Le Biokernel est à la fois capable de construire des nouveaux protocoles comme de produire des protocoles résultant d’une combinaison de ses connaissances.
Le Docteur Dupré décide de donner à Jacq le processus de création de nouveaux algorithmes dans le biokernel. La première étape est la récupération et le nettoyage des données. Pour cela, le Docteur Dupré donne à Jacq une série de valeur montrant l’activité énergétique du biokernel :
https://www.kaggle.com/robikscube/hourly-energy-consumption
Jacq décide alors de faire appel à un spécialiste (vous) afin de mieux comprendre comment à partir d’une série de données, le biokernel arrive à en tirer une IA prédictive et autonome.
Votre première mission et de nettoyer ces données, pour cela vous utiliser le protocole standard suivant :
- Pour chaque jour
- Fixer la valeur de début de journée en MWh
- Pour chaque heure de la journée, calculer la pente d’évolution de la consommation (à 0,01%)
Chaque valeur de la pente forme un symbole de votre alphabet, chaque jour forme un mot. Ainsi, la comparaison des mots permettra à la machine de mieux comprendre l’évolution de sa consommation en au cours du temps.
Puisque le détail d’évolution de la consommation est assez précis, cela va générer de très nombreux symboles dans l’alphabet, il vous faut alors nettoyer l’alphabet afin de limiter le bruit. Vous avez au plus 24 symboles pour chaque journée, si vous fabriquez les mots sur un mois, cela vous engendrera plus de 700 symboles. Vous avez donc l’idée de regrouper les données similaires au sein d’une même valeur référente grâce à l’algorithme des k-Means :
https://www.datacamp.com/community/tutorials/k-means-clustering-r
Notation
- Donner les mots engendrés sur une semaine (5 points)
- Expliquer à l’aide des mots engendrés l’algorithme des k-Means (5 points)
- Montrer le résultat obtenu (via R) sur un mois de consommation (5 points)
Partie 2 : Arbres de décision et simplification
« Cleo: Now I know why the rain changed.
Jacq Vaucan: Why?
Cleo: I don’t think you could understand. »
Maintenant que vous avez nettoyer les données, vous devez fabriquer l’automate de contrôle par apprentissage. La première étape de la construction de l’automate se fait grâce à une faculté de simplification du biokernel. Ce dernier est capable de repérer les schémas identiques dans un ensemble de mot. Par exemple si sur deux journées vous obtenez les mots suivants : azertyuiop et bhjtyuiqf, le biokernel et capable de dire que seul « tyui » est commun aux deux mots.
Dans un premier temps, fabriquer l’arbre de décision sur les mots suivants :
- azertyuiop ; ghjtyuifg ; fghjktyui ; fghjazeop
L’arbre de décision présente une branche par mot, et une transition (arc) par chaque symbole du mot.
La deuxième étape est la recherche des sous-chaines communes pour chaque paire de mots :
https://complex-systems-ai.com/wp-content/uploads/2016/03/tutorial2.pdf exercice 4
Déterminer les plus grand sous-chaines communes entre toute paire de mots. Classer les sous-chaines communes par ordre croissant et choisissez les plus grandes tant que cela est possible. Il est possible de choisir une sous-chaines communes si tous les éléments de cette sous-chaines ne sont pas déjà sélectionnées dans une autre sous-chaine commune.
Une fois que vous avez sélectionner les sous-chaines, regrouper les états correspondant deux des mots entre eux avec sur l’arc le mot commun.
Notation
- Arbre de décision (2 points)
- Calcul des sous-chaines communes (5 points)
- Arbre de décision mergé (3 points)
Partie 3 : Réduction de l’automate et prédiction
« Jacq Vaucan: Who altered your protocols?
Blue Robot: Nobody altered my protocols.
Jacq Vaucan: What about them?
Blue Robot: I enhanced them.
Jacq Vaucan: Are you the boss?
Blue Robot: Boss is a human thought structure.»
Maintenant que l’automate a été réduit, la dernière étape consiste à déterminiser et minimiser ce dernier. Prenons l’automate suivant pour plus de facilité :
Déterminiser et minimiser l’automate afin de présenter au biokernel l’algorithme le plus léger possible. Une fois l’automate minimal obtenu, donner un arbre de décision sur le comportement futur (la suite du mot) en considérant le préfixe suivant sur un pas de 5 :
- ab, quelles sont les mots validés ?
De même, le biokernel est capable de récupérer le chemin parcouru en remontant l’automate en arrière. Donner un arbre de décision sur le comportement passé (le début du mot) en considérant le suffixe suivant sur un pas de 5 :
- ccc, quelles sont les mots validés ?
Notation
- Déterminisation (5 points)
- Minimisation (5 points)
- Prédiction (5 points)