\chapter{\'Etat de l'art (Raisonnement à Partir de Cas)}

\section{Raisonnement à partir de cas (RàPC)}

Le raisonnement à partir de cas est une approche fondé sur la connaissance, est une technique d'intelligence artificielle dont l'idée est de résoudre un nouveau problème donné en utilisant l'analogie avec les connaissances déjà acquises par le système. Le RàPC est apparue comme une alternative pour améliorer les systèmes experts. Initialement en 1977 les travaux de Shank et Abelson \cite{schank+abelson77} sur l'organisation hiérarchique de la mémoire pour imiter le raisonnement humain ont permis d'implémenter un système a Kolodner \cite{KOLODNER1983281} en l'année 1983 pour arriver au terme RàPC en 1989 dans le travail de Riesbeck et Shank \cite{Riesbeck1989}.

Le raisonnement à partir de cas a été utilisé dans différents domaines comme : médecine, conception de produits, sports, systèmes de recommandation, etc. En médecine a été appliqué pour explorer et aider la prise de décisions des médecins dans les traitements qui requièrent administration de doses précises selon les cas et les patients, \cite{PETROVIC201617} propose un algorithme de raisonnement à partir de cas qui indique quel est la dose correcte de radiation pour le traitement du cancer. Pour administrer une dose de radiothérapie il est nécessaire de connaître avec précision deux paramètres: le nombre de faisceaux et l'angle de chacun d'eux. L'algorithme proposé essaie de trouver la valeur optimal pour la combinaison des deux paramètres en utilisant les réseaux de neurones et l'adaptation des cas connus pour changer le nombre de faisceaux et adapter le angle de chaque faisceau. La validation de l'algorithme est évaluée avec une base de 80 cas réels de cancer du cerveau extraits de l'hôpital de Nottingham City, le nombre de neurones et couches a été changé de façon empirique. Les résultats montrent que l'utilisation des cas historiques et la construction des solutions à partir des solutions déjà connues atteint une amélioration de 12\% dans les cas du nombre de faisceaux et 29\% dans les cas de l'angle des faisceaux.

Plusieurs travaux ont obtenu de bons résultats en appliquant le RàPC avec des modifications dans chacune des phases ou en combinant différents algorithmes au design de produits. \cite{ROLDANREYES20151} propose comme le montre la figure \figref{figMCBR1} un algorithme pour produire propylène glycol dans un réacteur chimique, dans ce cas la phase de réutilisation du RàPC est mélangée avec la recherche des états qui satisfassent le nouveau problème (Constraint satisfaction problems CSP) en utilisant l'information des cas de base déjà résolus. Les solutions trouvées sont évaluées selon le nombre de changements faits aux solutions déjà connues (Parcimonie), le nombre de possibles solutions trouvées (Accuracy), l'évaluation de commentaires faits par des experts et la complexité des transformations réalisées. Il n'est pas obligatoire de modifier tout le cycle du RàPC pour l'adapter à une problématique spécifique, comme \cite{JUNG20095695} qui développe un système basé sur l'hybridation du RàPC avec des réseaux de neurones pour concevoir des produits, le système se focalise uniquement dans les phases de rechercher et réutiliser du RàPC où sont exécutes les algorithmes implémentés. Le système détermine de façon automatique les valeurs pour les paramètres nécessaires à la conception de un produit particulier en suivant le cycle traditionnel du RàPC. Avec l'algorithme de k-moyennes est extrait un cas représentatif de la base de cas et l'adaptation des solutions des voisins trouvées est faite avec le réseau de neurones RBFN. Avec 830 test, les nouveaux cas très similaires aux cas de la base initiale est obtenu un bon design en 99.4\% des cas, pour les cas dissemblables le pourcentage est de 94.8\%. Le RàPC peut être utilisé aussi comme outil secondaire pour aider d'autres algorithmes à trouver la bonne configuration, dans \cite{10.1007/978-3-642-15973-2_50} est implémenté un réseau de neurones classique pour designer la géométrie d'une matrice pour l'extrusion de l'aluminium, car actuellement c'est un processus qui se fait manuellement par essai et erreur. Le RàPC ici est utilisé pour aider à déterminer les valeurs optimales des paramètres du réseau.

\mfigure[!ht]{width=\textwidth}{./Figures/ModCBR1.png}{Cycle du RàPC modifié. (Traduit de \cite{ROLDANREYES20151})}{figMCBR1}

%\begin{figure}
%\centering
%\includegraphics[scale=0.4]{./Figures/ModCBR1.png}
%\caption{Cycle du RàPC modifié. (\cite{ROLDANREYES20151})}
%\label{figMCBR1}
%\end{figure}

L'une des problématiques la plus représentative et la plus fondamentale de l'utilisation du RàPC est la création de recettes de cuisine à partir de une base de ingrédients et d'un ensemble de recettes déjà connues, mais malgré l'apparente simplicité du problème il y a beaucoup de variations et modèles, dans \cite{10.1007/978-3-319-47096-2_11} est abordée cette problématique, mais en additionnant un nouveau cycle au cycle traditionnel du RàPC. Le premier cycle génère des descriptions abstraites du problème avec un réseau de neurones et algorithmes génétiques; le seconde cycle prend les descriptions abstraites comme nouveaux cas, cherche les cas similaires et adapte les solutions rencontrées. L'exécution des deux cycles considère certains critères prédéfinis par l'utilisateur. En comparant le même problème avec le cycle traditionnel du RàPC il y a effectivement une amélioration de la qualité des recettes proposées et qui vont plus en accord avec les critères définis. Sur la même problématique, mais plus focalisé sur la génération des recettes novatrices, \cite{10.1007/978-3-319-61030-6_1}, utilise un modèle probabiliste qui considère les préférences des utilisateurs, un indicateur de curiosité et un composant qui synthétise tout le design; une fois que toutes les exigences sont remplies, la recette est créée en combinant les ingrédients avec un réseau d'apprentissage profond. Les changements dans la représentation des cas est aussi une source d'amélioration des résultats parce que parfois d'un côté il y a plus d'information et de l'autre certain techniques ou algorithmes fonctionnent mieux, c'est le cas que montre \cite{Muller} où les recettes sont codées comme un processus de transformation et mélange des ingrédients en suivant une suite de pas ordonnés, pour créer innovation dans les recettes une mesure de distance est employée entre les ingrédients avec laquelle il est possible de trouver une recette et changer les ingrédients pour les plus proches, de la même façon il est possible de créer recettes plus proches des exigences des utilisateurs, les étapes de transformation appelées aussi opérateurs sont stockes et catégorisées les unes avec les autres avec une métrique qui permet de les échanger pour obtenir une nouvelle recette.

Une autre type d'application du RàPC très notable est le génération, analyse et correction du texte écrit; pour la réalisation de ces tâches parfois il est nécessaire de transformer le texte en représentation numérique ou établir une fonction ou mesure qui va indiquer quels mots ont une proximité sémantique. Le travail de \cite{10.1007/978-3-319-24586-7_20} utilise le RàPC pour générer des histoires en utilisant le texte d'autres histoires, en explorant les possibles transformations de forme que la nouvelle histoire ne soit pas très similaire aux histoire déjà connues mais que elle soit cohérent. Le travail est plus focalisé sur la phase de révision, car les résultats de la révision déterminent si la histoire générée corresponde avec les critères spécifiés ou si le cycle d'adaptation doit recommencer; l'adaptation se fait en cherchant dans la base des cas, les personnages, les contextes, les objets et en unifiant tout avec des actions; la plus part des histoires générées sont cohérents mais sont des paragraphes très courts. Dans \cite{10.1007/978-3-030-58342-2_20} les phrases écrites en langue française sont corrigées, ce travail n'utilise pas la transformation numérique des phrases, ni connaissances linguistiques, mais seulement retrouve les phrases similaires en utilisant l'algorithme LCS (Longest Common Subsequence) et en calculant la distance parmi toutes les phrases pour savoir si elle est bien écrite ou pas, sinon le système peut proposer une correction en changeant certains mots selon le contexte et calculer à nouveau les distances qui déterminent la cohérence et pertinence de la phrase.

Le sport fait partie aussi des domaines explorés avec le RàPC, qui est généralement employé pour suggérer des routines d'entraînement, prédire des temps de course, ainsi comme évaluer et améliorer la performance des athlètes. La prédiction du temps de course pour un athlète est l'objectif du travail de \cite{10.1007/978-3-030-01081-2_25} où les coureurs ont été suivis et analysés pour la prédictions des temps de finalisation de une course, ici est implémenté un algorithme pour ceux qui font de la marathon en utilisant l'algorithme KNN pour rechercher les cas similaires et en faisant la prédiction avec la moyenne pondérée des meilleurs temps d'arrivée des cas similaires retrouvés dans la première étape du RàPC. Tandis que \cite{10.1007/978-3-030-58342-2_8} essaie de prédire le meilleur temps personnel pour des patineurs en se basant sur l'analogie de que les patineur avec des caractéristiques et histoire de course similaires auront des temps similaires aussi, mais parfois calculer une moyenne des temps similaires trouvés, ne suffit pas, car il y a des variables qui peuvent changer beaucoup la performance du patineur comme: le type de course, une piste spécifique, la distance de course, etc; l'algorithme a été testé avec une base de données qui contiens l'information de 21 courses de 500m, 700m, 1000m, 1500m, 3km, 5km and 10km entre Septembre 2015 et Janvier 2020. Un système multi-fonctionnel apparait dans \cite{10.1007/978-3-030-58342-2_5} car il permet de obtenir une prédiction du temps de course, suggérer un plan du rythme de la course et il recommande aussi un plan d'entraînement pour une course donnée; les trois fonctionnalités sont implémentées avec RàPC et en utilisant 'information des coureurs qui présentent un parcours historique et des caractéristiques physiques similaires, les plans d'entraînement ont été définis génériquement sur 16 semaines avant le début de la marathon parce que c'est le temps usuel pour la préparation de tous les coureurs. Le système a été évalué avec une base de données de 21000 coureurs dans la période de 2014 à 2017 qui ont couru les marathons de Dublin, Londres ou New-York.

Les systèmes de recommandation et le RàPC peuvent aussi être combinés comme le fait \cite{Obeid}, dont le objectif est d'arriver à minimiser les limitations des systèmes traditionnels ainsi comme avoir la capacité d'analyser des données hétérogènes et dans des grands espaces dimensionnels, dans ce travail est recommandé aux élèves du secondaire le parcours de carrière et les universités/collèges qui correspondent à leurs intérêts, ce travail montre aussi une taxonomie des techniques algorithmiques généralement utilisées dans les systèmes de recommandation pour les EIAH (figure \figref{figTax}). La utilisation du RàPC dans les environnements informatiques pour l'apprentissage humain (EIAH) et la personnalisation montrent des résultats positifs comme l'indique le travail de \cite{8495930} dont le modèle suit le cycle traditionnel du RàPC en combinant les modèles d'apprentissage traditionnel et digital, les principales contributions sont: la représentation des cas et la recommandation des parcours d'apprentissage personnalisés selon l'information des autres apprenants. Pour démontrer l'effectivité du modèle est crée une base de cas initiales avec laquelle est recommandé le parcours à 120 apprenants, les résultats ont été obtenus avec l'aide des examens avant et après avoir suivi le parcours recommandé par le modèle.

\mfigure[!ht]{width=\textwidth}{./Figures/taxonomieEIAH.png}{Taxonomie des techniques algorithmiques employées pour des modules de recommandation dans les EIAH (Traduit de \cite{Obeid})}{figTax}

%\begin{figure}
%\centering
%\includegraphics[scale=21]{./Figures/taxonomieEIAH.png}
%\caption{Taxonomie des techniques algorithmiques employées pour des modules de recommandation dans les EIAH (\cite{Obeid})}
%\label{figTax}
%\end{figure}

Certains travaux ont appliqué le raisonnement à partir de cas à un problème spécifique en proposant des représentations des cas et des solutions différents et d'autres ont modifié le cycle conceptuel comme est montré dans la figure \figref{figMCBR2} extraite de \cite{10.1007/978-3-319-47096-2_11} où est additionné un autre cycle complémentaire avec l'idée d'améliorer le résultat du processus du RàPC en utilisant le \textit{Deep Learning}; dans \cite{10.1007/978-3-642-15973-2_50} la phase de stockage est modifiée en retenant les cas dont les résultats n'ont pas eu de succès, pour guider le processus dans la fabrications de nouvelles pièces; \cite{Robertson2014ARO} additionne pour chaque cas, une valeur d'utilité espérée selon chaque possible action avec laquelle est possible d'obtenir une prédiction probabiliste de l'application des actions à un état initiale donné.

\mfigure[!ht]{width=\textwidth}{./Figures/ModCBR2.png}{Addition d'un cycle complémentaire avec \textit{Deep Learning} au RàPC (Traduit de \cite{10.1007/978-3-319-47096-2_11})}{figMCBR2}

Le tableau \ref{tabArts2} montre un récapitulatif des articles analysés dans l'état de l'art du RàPC.

\begin{table}
\footnotesize
\begin{tabular}{p{4.2cm}p{9cm}}
Ref&Limites et faiblesses\\
\hline

\cite{PETROVIC201617}&Grand quantité de données pour que l'algorithme marche bien. Recommandation limitée à un problème très spécifique\\

\cite{ROLDANREYES20151}&Un seul méthode d'adaptation est utilisé. Le modèle n'exploite pas les cas qui présentent une erreur\\

\cite{JUNG20095695}&Le modèle d'adaptation proposé marche bien seulement avec des cas très proches. L'apprentissage dans le RàCP se limite à stocker les nouveaux cas\\

\cite{10.1007/978-3-642-15973-2_50}&Le RàPC n'est pas modifié ou amélioré. La révision dans le RàPC n'est pas automatique\\

\cite{10.1007/978-3-319-47096-2_11}&Beaucoup de données nécessaires pour entrainer le modèle de 'Deep Learning'. Les solution générées n'ont pas été validées\\

\cite{10.1007/978-3-319-61030-6_1}&L'évaluation des solution générées n'est pas automatique. Les solutions sont produites avec un seul point de vue\\

\cite{Muller}&Un seul approche pour adapter les cas dans le RàPC. La révision dans le RàPC n'est pas automatique\\

\cite{10.1007/978-3-319-24586-7_20}&Les solutions générées peuvent présenter des incohérences. Il n y a pas une métrique objective pour mesurer la qualité des réponses\\

\cite{10.1007/978-3-030-58342-2_20}&Les résultats ne sont pas très bonnes. Le modèle n'a pas de connaissances linguistiques\\

\cite{10.1007/978-3-030-01081-2_25}&Les prédictions n'ont pas été testées dans le monde réel. Les données sont très spécifiques et peu variées\\

\cite{10.1007/978-3-030-58342-2_8}&Les prédictions sont pour des cas limités. Le modèle est entrainé pour un type d'utilisateur spécifique\\

\cite{10.1007/978-3-030-58342-2_5}&Seulement une technique de sélection de solutions. Les données nécessaires pour le modèle sont complexes\\

\cite{Obeid}&L'ontologie peut être limitée pour évaluer plusieurs cas inconnus ou imprévus. Il est nécessaire d'avoir une forte connaissance dans le domaine\\

\cite{8495930}&Le modèle a été validé avec peu de données. Les recommandation se basent seulement dans l'information des autres apprenants\\

\end{tabular}
\caption{Tableau de synthèse des articles analysés dans l’état de l’art du RàPC}
\label{tabArts2}
\end{table}

%\begin{figure}
%\centering
%\includegraphics[scale=0.4]{./Figures/ModCBR2.png} 
%\caption{Addition d'un cycle complémentaire avec \textit{Deep Learning} au RàPC (\cite{10.1007/978-3-319-47096-2_11})}
%\label{figMCBR2}
%\end{figure}

Deux problèmes très communes des systèmes de recommandation sont : le \textit{cold-start} qui occurs au début d'une recommandation lorsque il n'y a pas suffisamment de données pour calculer ou inférer une recommandation appropriée et le {gray-sheep} que se produit lorsque un utilisateur présente un comportement très différent des utilisateurs qui sont stockés dans la base de données et le système ne peut pas générer des recommandations en se basant sur l'information disponible.