Transformation de programmes logiques

Systèmes de recommandation

   Les systèmes de recommandation ont pour l’objectif principal de recommander des items à des utilisateurs. Nous présentons ici quelques-unes des approches de la recommandation.
— Les approches basées sur le contenu [Lan95, PB07] recommandent à l’utilisateur des items proches de ceux qu’il a appréciés. Cela requiert une description de chaque item et un moyen d’établir la proximité de deux items, par exemple en cherchant des points communs dans des mots-clefs décrivant les items. Il existe également des approches sémantiques [BFPAGS+08], dans lesquelles les items ne sont pas décrits par des mots-clefs, mais au sein des ontologies : plutôt que de recommander les items maximisant une mesure de similarité, ces approches cherchent les liens sémantiques entre les items appréciés par l’utilisateur et des candidats à la recommandation.
— Les approches collaboratives utilisent les notes attribuées, explicitement ou implicitement, par tous les utilisateurs aux items pour recommander des items. Il en existe deux variantes. Le filtrage basé sur les utilisateurs [RIS+94] cherche à rapprocher l’utilisateur d’autres utilisateurs ayant noté les mêmes items de manière similaire et à recommander les items appréciés par ces utilisateurs. Le filtrage basé sur les items [SKKR01] cherche à exploiter les notations des items pour établir des similarités entre items et proposer à l’utilisateur des items similaires à ceux qu’il a appréciés.
— Les approches démographiques [Paz99] cherchent à catégoriser les utilisateurs dans des classes à partir d’informations démographiques telles que leur âge, intérêts ou lieu d’habitation, puis à recommander des items à l’utilisateur en fonction de la classe dont il fait partie.
— Les approches basées sur la connaissance [Bur99] reposent sur un ensemble de règles qui, définies par un expert, sont utilisées pour déterminer les items à recommander en fonction de critères fournis par l’utilisateur. Le système peut éventuellement interroger l’utilisateur pour avoir des critères plus précis et affiner la recommandation.
— Il existe enfin diverses approches hybrides [MJZ03] qui réunissent différentes approches.
— L’hybridation pondérée consiste à utiliser la somme pondérée des scores d’un item dans plusieurs approches pour déterminer le score d’un item, et garder les items ayant le plus grand score.
— L’hybridation à bascule consiste à utiliser une approche ou une autre en fonction d’un critère.
— L’hybridation mixée consiste à présenter ensemble les résultats de différentes approches.
— L’hybridation par combinaison de caractéristiques consiste à utiliser les caractéristiques d’une approche dans une autre approche.
— L’hybridation en cascade consiste à utiliser une approche pour filtrer un ensemble d’items recommandés par une autre approche.
— L’hybridation par ajout de caractéristiques consiste à utiliser le résultat d’une approche comme paramètre dans une autre approche.
— L’hybridation métaniveau consiste à utiliser une approche de personnalisation pour générer un modèle, et à utiliser une autre approche dans ce modèle plutôt qu’avec les données originales. Le choix de l’approche de recommandation est une tâche complexe qui dépend de nombreux paramètres, tels que le domaine et le nombre d’utilisateurs et d’items que le système devra gérer. Un système donné suit une seule approche (éventuellement hybride) et résout un problème de recommandation, sans chercher la généralité. La majorité des systèmes de recommandation ont des approches numériques et n’utilisent pas de techniques de raisonnement. Seuls les systèmes basés sur le contenu utilisant une approche sémantique peuvent faire appel à des techniques de raisonnement dans la manipulation des informations sémantiques.

Comment exprimer l’adaptation ?

   Le plus souvent, l’adaptation dans les systèmes d’hypermédias adaptatifs est exprimée à l’aide de règles de la forme condition-action ou évènement-condition-action [WHDB98]. Ces règles peuvent aussi être des formules de logique du premier ordre, utilisant alors un raisonnement pour l’adaptation [HDN04]. GLAM [Jac06] propose l’utilisation de règles en logique du premier ordre reliées à différents stéréotypes de profils, avec des métarègles pour déterminer quelles règles utiliser en cas de conflit entre règles. L’expression de l’adaptation par règles étant fastidieuse et difficile pour des intervenants non techniciens, des techniques d’aide à l’écriture des règles ont été mises au point. Des éditeurs graphiques de règles [DBSS05] permettent l’application de patrons prédéfinis d’adaptation à un modèle donné. Des systèmes de patrons d’adaptation permettent au concepteur d’application de spécialiser des modèles génériques d’adaptation à ses propres modèles [ZBR+09]. Des langages d’adaptations tels que LAG [CV04] ou GAL [VDSHLH09] offrent une alternative de plus haut niveau à l’écriture de règles,en offrant des constructions permettant d’exprimer directement certaines techniques d’adaptation. Cependant, ces techniques d’expression de l’adaptation ne permettent qu’une adaptation ad hoc, c’est à dire spécifique à un modèle du domaine et de l’utilisateur donné. Ces outils sont le plus souvent des langages facilitant l’expression de l’adaptation, mais demandent toujours au concepteur d’application de coder l’intégralité de la logique d’adaptation de l’application.

Le problème du sensing

   Un agent interagissant avec un environnement peut ne pas tout savoir de l’environnement et des conséquences de ses actions, et donc ne pas pouvoir faire de plans sans prendre en compte des éléments extérieurs : ce problème est appelé problème du sensing. Il est commun à de nombreuses théories d’agents. L’interaction avec des humains pose le problème du sensing : en interagissant avec un utilisateur, l’agent ne peut prévoir sa réponse, et doit donc agir avec une certaine incertitude (il ne peut choisir avec certitude une marche à suivre pour l’intégralité de son exécution). Ici, nous présentons rapidement le problème et quelques-unes de ses solutions. Ces solutions seront présentées plus en détail dans les descriptions des formalismes dans les sections  suivantes. Les formalismes d’actions sont des formalismes permettant de modéliser un univers en définissant des actions, leurs préconditions et leurs effets . Dans ces formalismes, l’univers évolue uniquement par les actions : une action fait passer l’univers d’un état à un autre, et un état peut être défini comme la séquence d’actions qui y a mené à partir d’un état initial. Dans la plupart des formalismes, les définitions des effets des actions sont déterministes : l’application d’une action dans un état précis a toujours les mêmes effets. De fait, de tels formalismes ne peuvent pas exprimer des agents ne connaissant pas les effets de leurs actions, ou ne connaissant qu’une partie de leur environnement. Une des solutions à ce problème implique la notion de connaissance [Moo79] : il s’agit de faire la différence entre ce qui est vrai dans l’environnement et ce que l’agent sait : il peut y avoir des faits vrais que l’agent ne sait pas encore. Une des formalisations de cette solution est donnée en 2.2.3. La connaissance de l’agent y est définie dans les mêmes termes que l’environnement, sous la forme d’un fluent 10 spécial nommé fluent épistémique. De même, l’influence des actions sur la connaissance est définie de la même manière que l’influence des actions sur l’environnement. Selon les formalismes, deux formes de modifications de la connaissance sont possibles : la mise à jour de la connaissance (knowledge update) et l’extension de la connaissance (knowledge extension). La mise à jour de la connaissance se produit dans le cas où un fait est oublié au profit d’un autre qui le remplace (par exemple : «la porte est maintenant ouverte, alors qu’elle était fermée auparavant»). L’extension de la connaissance se produit quand un nouveau fait est connu sans en invalider un autre (par exemple : «je découvre que la porte est ouverte, sans connaître son état précédent»). Certains formalismes ne permettent que l’extension de la connaissance, tandis que d’autres permettent les deux formes.

Interaction avec un environnement incertain

   Il existe de nombreuses manières de modéliser des changements de l’environnement qui ne sont pas directement dus à l’agent, ou qui lui échappent d’une manière ou d’une autre. L’utilisation d’actions exogènes [GLL00], introduites dans Golog avec ConGolog, consiste à définir des actions qui ne sont pas présentes dans le programme de l’agent, mais qui peuvent être exécutées à n’importe quel moment pendant le déroulement du programme. Formellement, un programme ConGolog δ est remplacé par δ || δE XO, où δE XO = (πa E xo(a)?;a)∗ et E XO(a) indique que a est une action exogène. Cette approche présente deux problèmes. D’une part, le lancement des actions exogènes est mélangé au programme, et rien ne distingue les actions exogènes des autres. D’autre part, l’interaction avec l’utilisateur sur le Web se fait de manière très contrainte : une page est envoyée à l’utilisateur, qui envoie une réponse ; rien ne peut se passer en dehors du moment précis où l’application attend la réponse de l’utilisateur. [BF+95] propose une variante du calcul des situations comprenant des actions non-déterministes, qui ont plusieurs issues possibles, ainsi qu’une solution au problème du cadre prenant en compte ces actions non-déterministes. De telles actions pourraient être utiles pour représenter les interactions avec l’utilisateur (on demande à l’utilisateur, à un moment donné, de faire un choix), mais il n’existe pas de langage similaire à Golog basé sur ce formalisme ni de système de planification. Ce formalisme est donc moins adapté à l’écriture d’un agent que Golog. Pour gérer les actions de sensing, dont le résultat n’est pas connu à l’avance et qui empêchent donc la planification classique, sGolog [Lak99] cherche une exécution d’un programme qui n’est pas une séquence d’actions, mais un arbre d’actions : chaque action de sensing cause un branchement de l’arbre, et une planification est lancée pour chaque résultat possible du sensing. Il est ainsi possible de générer hors-ligne un plan conditionnel qui pourra être exécuté quel que soit le résultat des actions de sensing. Il existe également des approches s’intéressant à la quantification de l’incertitude. [BHL98] introduit la notion d’effecteurs bruités, qui sont des actions ayant un argument numérique dont l’argument effectif peut être différent de l’argument demandé (par exemple, un robot décide d’avancer de 10cm, mais l’imprécision de ses moteurs le fait avancer en fait de 10.2cm, et l’imprécision de ces capteurs le fait mesurer une avancée de 9.9cm). L’article s’intéresse à la limitation de l’imprécision dans ce contexte. [BP03] traite le résultat des actions d’un point de vue probabiliste, en donnant à chaque action des résultats probables, et en définissant un mode de planification qui permet d’obtenir un plan qui marche avec une certaine probabilité, compte tenu d’actions qui peuvent échouer ou avoir différents résultats. De la même manière, [GL00] introduit pGolog, une variante de Golog dont les actions primitives peuvent être probabilistes ; les actions de mesure de valeurs incertaines sont alors considérées comme des actions probabilistes. [GL01] s’intéresse à la mise à jour des croyances dans pGolog, c’est-à-dire à comment gérer les situations où les résultats de nouvelles mesures sont en contradiction avec ce que l’agent croit. DTGolog [BRS+00] est une variante de Golog intégrant des processus de décision de Markov dans Golog, permettant de chercher des plans optimaux dans le cadre d’actions non déterministes. Un interpréteur en ligne de DTGolog a été proposé [Sou01], mais celui-ci ne peut calculer une exécution optimale que jusqu’à l’action de sensing suivante. Ce problème peut être résolu par le remplacement des actions de sensing explicites par des capteurs passifs actualisant continuellement le modèle de l’environnement de l’agent [FFL04]. Cette solution n’est cependant disponible que quand de tels capteurs existent, comme c’est le cas pour des robots évoluant dans le monde réel.

Table des matières

Table des figures
I Introduction 
1 Contexte et problématique 
1.1 Problématique
1.2 Approche
1.3 Contributions
2 État de l’art 
2.1 Personnalisation et personnification
2.1.1 Systèmes de recommandation
2.1.2 Hypermédias adaptatifs
2.1.3 Personnalisation et Web sémantique
2.1.4 Personnification
2.1.5 Conclusion
2.2 Expression logique des agents interagissant avec des humains
2.2.1 Le problème du sensing
2.2.2 Agents en Golog
2.2.3 Gestion de l’interlocuteur humain
2.2.4 Logiques modales
2.2.5 Conclusion
2.3 Altération d’agents
2.3.1 Préférences globales sur l’exécution d’agents
2.3.2 Choix des buts dans le modèle BDI
2.3.3 Personnification d’agents
2.3.4 Conclusion
2.4 Conclusion de l’état de l’art
II Contributions 
3 Contributions préliminaires 
3.1 Personnalisation faible et forte
3.1.1 Définitions
3.1.2 Illustrations
3.1.3 Conclusion
3.2 Modélisation d’applications Web sous forme d’agents logiques
3.2.1 Choix d’IndiGolog
3.2.2 Structure de l’agent interagissant sur le Web
3.2.3 Théorie de l’action d’une application Web
3.2.4 Illustration : bonjour, monde
3.2.5 Illustration : agent gérant un hypertexte
3.2.6 Conclusion
4 Choix d’un agent et altération des choix 
4.1 Extension nécessaire de Golog
4.2 Transformations
4.2.1 Transformations simples
4.2.2 Transformations destructrices
4.2.3 Report du choix à l’exécution
4.2.4 Validité des transformations
4.2.5 Conclusion
4.3 Ajout de choix
4.3.1 Transformation d’actions
4.3.2 Caractérisation des familles d’actions
4.3.3 Généralisation aux procédures
4.3.4 Conclusion
5 Affinités et critères de choix 
5.1 Profils et attributs
5.2 Affinités d’actions
5.2.1 Attributs d’une action
5.2.2 Actions à attributs fixes
5.2.3 Actions à attributs variables
5.2.4 Attributs d’une action dans un programme
5.2.5 Calcul de l’affinité
5.2.6 Classe d’affinité
5.3 Comparaison de programmes
5.3.1 Comparaison de multi-ensembles
5.3.2 Comparaison d’actions
5.3.3 Résolution des conditions
5.3.4 Comparaison de séquences
5.3.5 Comparaison des choix
5.3.6 Éléments transparents à la comparaison
5.4 Programmes requis et programmes bannis
5.5 Conclusion
6 Processus automatique de transformation 
6.1 Actions
6.2 Choix de programmes
6.3 Choix d’arguments
6.4 Conclusion
III Applications des transformations 
7 Personnalisation 
7.1 Système de recommandation
7.1.1 Description
7.1.2 Personnalisation selon les sujets
7.1.3 Renforcement et découverte
7.1.4 Combinaison des transformations
7.2 Hypermédia adaptatif pédagogique
7.2.1 Description
7.2.2 Programme de base
7.2.3 Personnalisation
7.3 Conclusion
8 Personnification 
8.1 Agent conversationnel
8.2 Représentation du domaine
8.3 Architecture de l’agent
8.4 Altération de l’agent
8.4.1 Sélection du type d’information à partager
8.4.2 Acceptation des interprétations
8.4.3 Combinaison des transformations
8.5 Conclusion
IV Conclusion 
9 Conclusion 
10 Perspectives 
10.1 Prolongements
10.1.1 Outillage
10.1.2 Expérimentation
10.1.3 Preuve
10.2 Choix
10.2.1 Profil sur deux axes
10.2.2 Profil discret
10.3 Ajouts
10.3.1 Introduction d’aléatoire dans le programme
10.3.2 Transformation à l’exécution
V Annexes 
A Exemples
A.1 Un agent-robot visitant une maison
B Preuves
B.1 Possibilité d’exécution du choix préférentiel
B.2 Restrictions
C Sémantique de IndiGolog
C.1 Programme vide
C.2 Action primitive
C.3 Test ou attente
C.4 Séquence
C.5 Branchement non-déterministe
C.6 Choix non-déterministe d’argument
C.7 Itération non-déterministe
C.8 Conditionnelle synchronisée
C.9 Boucle synchronisée
C.10 Exécution concurrente
C.11 Concurrence priorisée
C.12 Itération concurrente
Bibliographie

Télécharger le rapport complet