ACMES

• Membres : Sadok Ben Yahia (HDR, depuis le 1/1/2012), Amel Bouzeghoub (HDR), Bruno Defude (HDR), Alda Gancarski, Daqing Zhang ;
• Doctorants : 12 dont 3 soutenues
• Post-doctorants : Pablo Samuel Castro Rivadeneira (2011-12), Bin Guo (2009-11), Vaskar Raychoudhury (2011), Zhiyong Yu (2012-13), Daqiang Zhang (2011-12)

La construction d’applications personnalisées ou adaptées aux utilisateurs est devenue incontournable ces dernières années. Cela passe par la prise en compte de ce que l’on appelle généralement le contexte. L’essor des réseaux sociaux et la multiplication des sources d’acquisition d’informations (capteurs de tout type) ont élargi le contexte et permettent d’acquérir de l’information sur l’utilisateur beaucoup plus riche et plus dynamique. Les travaux que nous menons dans cet axe se situent dans la modélisation, l’apprentissage et le raisonnement en vue de faire de la prédiction basée sur ce contexte élargi au monde physique (capteurs) et aux interactions sociales, ce que nous nommons l’intelligence collective et sociale (ICS). C’est un domaine de recherche à l’intersection de plusieurs disciplines (réseau de capteurs, informatique mobile et ubiquitaire, apprentissage automatique, fouille de données et sciences sociales) visant à révéler les modèles d’individus, de groupe et des comportements sociaux. Cela permet de construire des services complètement novateurs dans des domaines comme la santé, le transport, la sécurité, la gestion des ressources de la ville ou l’environnement.

L’architecture générale d’un tel système s’articule autour de 4 couches : La couche physique (application internet et web social, dispositifs mobiles, capteurs physiques ou logiques, réseau ambiant, Internet des objets,...), la couche données (passage du monde physique à des données brutes, avec des opérations éventuelles d’échantillonnage, de lissage, de fusion,...), la couche sémantique (transforme les données brutes en connaissances exploitables par les applications) et la couche application (inclut notamment des fonctions assistance aux utilisateurs construites à partir des résultats de la couche sémantique). Cette décomposition est complétée par une dimension transversale qui est la distribution. Nos travaux couvrent essentiellement les couches sémantique et application. Les points clés de ces propositions portent sur la nature des données modélisées et analysées (données spatiales, temporelles, avec dépendances causales, sociales), l’hétérogénéité (diversité des sources, fusion,...), l’échelle et le caractère centralisé ou distribué de tout ou partie du processus de transformation des données (couche sémantique) ou des fonctions d’assistance (couche application).

Reconnaissance d’activités humaines

Une première catégorie de nos travaux porte sur la reconnaissance d’activités humaines à partir d’informations élémentaires (données d’accéléromètres par exemple). Cela concerne d’une part la reconnaissance d’activités simples telles que marcher, courir, monter ou descendre des marches d’escalier, être à l’arrêt, à vélo, en voiture, etc. Nous avons pour cela utilisé un algorithme de classification pour exploiter les données issues d’une source de données unique, des téléphones portables dotés d’un accéléromètre que les utilisateurs gardent dans leur poche. Ces travaux concernent d’autre part l’extraction de patrons d’association intra et inter activités. Nous avons utilisé des règles d’association pour extraire des motifs fréquents à partir de traces spatio-temporelles d’activités quotidiennes de personnes âgées. Ces patrons d’associations sont ensuite utilisés pour générer un modèle d’activité humaine [158, 35]. Ces travaux ont été supportés par les projets du pôle Systematic et FEDER AQUEDUC (Améliorer la Qualité DU service à la personne et au Citadin) et le projet européen FP7 Societies (Self-orchestrating Community ambient Intelligence Spaces).

Une variante de ce problème est l’identification de situations. L’un des défis pour un grand nombre d’applications est d’identifier en temps réel la situation de l’utilisateur pour des actions d’adaptation ou d’assistance et des notifications de recommandation. Nos travaux ont dans un premier temps consisté à proposer un modèle formel basé sur les ontologies pour représenter le contexte et les situations. Nous utilisons des règles logiques et un mécanisme de raisonnement à partir de cas pour la reconnaissance de situations [231]. Cette modélisation formelle offre une spécification commune partagée des données de contexte facilitant l’interopérabilité, la réutilisabilité et la portabilité des modèles entre différents systèmes et domaines d’application. Elle permet en outre de vérifier l’intégrité et la cohérence des situations et fournit un haut niveau d’abstraction et un formalisme pour la spécification des situations. Cependant, elle requièrt l’intervention humaine pour la spécification des situations et des règles d’inférence. Pour réduire cette limite, nous avons proposé des modèles hybrides soit en combinant cette approche avec une approche de fouille de données (règles d’association) pour de la recherche d’information contextuelle basée sur la prédiction des intérêts des utilisateurs et leurs relations sociales [51], soit en la combinant avec une approche orientée processus qui apporte un gain notamment en terme de temps de réponse car les processeurs de contexte COSMOS fournissent la donnée de contexte la plus récente sans avoir besoin d’interroger les sources de données [186].

Systèmes de recommandation sensibles au contexte

Nous avons également travaillé sur les systèmes de recommandation sensibles au contexte. Ces systèmes doivent recommander aux utilisateurs des actions en tenant compte d’une part du contexte spatio-temporel et d’autre part du modèle de l’utilisateur (incluant les situations dans lesquelles il se trouve). Pour cela, deux problèmes doivent être abordés, l’acquisition automatique d’un profil riche d’un utilisateur et d’autre part la définition d’algorithmes de recommandation adaptés. L’identification de situation est ici réalisée directement à partir de données brutes issues des capteurs, en utilisant des techniques d’apprentissage permettant de découvrir directement des associations entre les données. Pour définir notre système de recommandation, nous avons choisi une méthode d’apprentissage par renforcement qui permet de gérer au mieux le compromis à trouver entre exploration et exploitation.
On doit exploiter ce que l’on connaît déjà pour obtenir une récompense, mais on doit aussi explorer
pour faire de meilleures actions dans le futur. Le dilemme est que ni l’exploration ni l’exploitation ne peuvent être poursuivies exclusivement sans faillir à la tâche. Nous proposons de modéliser un système de recommandation sensible au contexte comme un problème de bandit où le système doit choisir entre maximiser ses récompenses en tenant compte de la connaissance courante (exploitation) et en apprendre plus sur les préférences non connues de l’utilisateur (exploration). Nous introduisons de plus la notion de niveau de risque associé à chaque situation courante de l’utilisateur. Il peut en effet être dangereux ou inapproprié de recommander des items non désirés dans certaines situations dont le niveau de risque est élevé. Ce travail a été réalisé dans le cadre de la thèse CIFRE avec Nomalys (http://www.nomalys.com/). Nous avons mené des expérimentations en-ligne (avec de vrais utilisateurs de Nomalys) et hors-ligne et avons utilisé des données spatio-temporelles et sociales. Ces évaluations ont montré la pertinence de nos choix pour augmenter de façon significative les performances du système de recommandation [107, 109].

Fusion de données multi-sources

Une autre catégorie de travaux fusionne des données de différentes natures (spatio-temporelles, sociales) en utilisant des techniques de clustering et de classification. Il s’agit de l’extraction et l’analyse des traces GPS de taxis à grande échelle, des fichiers logs de téléphones portables et des données sociales émanant du réseau social Twitter et du réseau spatio-temporel Foursquare. Avec les traces GPS de 7800 taxis sur plus d’une année à Hangzhou, en Chine, nous pouvons comprendre où et quand les passagers montent ou descendent d’un taxi, quelle route un taxi prend pour une course donnée, quelle est la vitesse et la direction dans chaque réseau routier, etc.. Avec ce grand volume de données GPS, nous avons étudié des questions de recherche comme la compréhension de stratégies de service de taxi efficaces et inefficaces (pour guider des chauffeurs de taxi pour augmenter leur chiffre d’affaires ou pour consommer moins de carburant), la détection des trajectoires de conduite anormales (pour éviter de faire des détours), la prévision des conditions de trafic de chaque réseau routier en temps réel, la planification des bus de nuit afin de fournir des chemins plus économiques et écologiques. Ces travaux ont été publiés dans [180, 111, 112, 23, 78].

Confiance dans les réseaux sociaux

Nous avons également mené des travaux sur les données issues des réseaux sociaux et notamment sur la notion de confiance. L’idée de base est de pouvoir inférer une relation de confiance permettant d’attribuer une note de confiance à des pairs qui ne figurent pas dans la liste directe d’amis. Nos principales contributions ont porté sur l’inférence des relations de confiance directes et indirectes dans les réseaux sociaux. Les valeurs de confiance directe sont calculées à partir des interactions directes entre utilisateurs, leurs types de relations et la similarité de leurs intérêts. Les valeurs de confiance indirectes sont inférées en propageant les valeurs directes du noeud source vers le noeud cible. Les expérimentations ont été menées sur les données du réseau social Advogato avec 14000 utilisateurs et 55000 relations. Les résultats ont montré l’efficacité des algorithmes proposés en termes de précision et rappel et que notre approche passait à l’échelle [117, 80].

Acquisition et exploitation distribuées

Les travaux précédemment cités supposent tous que (i) on dispose de toutes les données brutes dans une base unique et centralisée et (ii) que l’interprétation de ces données se fait également de manière centralisée. Dans de nombreux contextes, cette hypothèse de centralisation est irréaliste puisque les données brutes vont être produites de manière distribuée. La centralisation est alors impossible soit pour des raisons de coût (cela nécessiterait trop de communications pour échanger les données), soit pour respecter l’autonomie des sources, soit pour des raisons de respect de la vie privée. Nous avons donc mené des travaux s’intéressant d’une part à la construction décentralisée des modèles utilisateurs et d’autre part à l’exploitation décentralisée de ces modèles.

Nos premiers travaux ont porté sur la gestion d’événements dans les réseaux inter-véhiculaires. Le but ici est d’aider les conducteurs dans leurs choix en utilisant une information de nature statistique sur des observations d’événements de nature spatio-temporelle (libération d’une place de parking, accidents, passage d’un véhicule d’urgence,...), sachant que nous supposons que l’observation de ces événements est faite au niveau des véhicules sans recours à une infrastructure centralisée. Pour cela, nous avons proposé (i) une structure de données compacte permettant à chaque véhicule de stocker des fréquences d’occurrences d’un événement dans une zone spatio-temporelle donnée ; (ii) un mécanisme d’échange entre véhicules basé sur des communications opportunistes ainsi qu’un processus de fusion des structures de données échangées en détectant les doublons ; (iii) des algorithmes d’aide à la décision basés sur ces fréquences. Ces propositions ont été validées par simulations effectuées sur un simulateur développé en collaboration avec le LAMIH [42, 144].

Nous nous sommes également intéressés aux systèmes de recherche d’informations en pair-à-pair non structuré (de type Gnutella), en cherchant à améliorer d’une part le routage des requêtes (choisir les meilleurs pairs pour une requête donnée) et d’autre part l’interclassement des résultats fournis par les différents pairs contributeurs. De nombreuses méthodes proposent d’utiliser l’historique des requêtes pour améliorer l’efficacité (rappel/précision) et la performance de recherche (diminuer le nombre de messages échangés) des méthodes classiques de routage. Cependant, elles souffrent de trois principaux inconvénients, à savoir : la représentation du profil utilisateur ; le problème du démarrage à froid ; le problème d’échec de sélection. En réponse à ces problèmes, nous avons proposé (i) un modèle de routage sémantique basé sur l’historique des requêtes. Le profil de l’utilisateur est représenté par un ensemble d’intérêts et est construit automatiquement en utilisant l’analyse formelle de concept (FCA). Chaque intérêt représente des relations sémantiques entre les requêtes passées, leurs termes et les pairs positifs. Ensuite, ce modèle est utilisé pour définir notre propre méthode de routage par apprentissage. Pour palier le problème de démarrage à froid, (ii) nous proposons une méthode prédictive de l’intention de l’utilisateur qui construit une base de connaissances initiale pour chaque pair. Cette base de connaissances initiale est construite au démarrage du système. Enfin, (iii) nous proposons une méthode de routage hybride pour traiter le problème d’échec de sélection [61, 52]. L’interclassement de résultats est le processus symétrique du routage qui consiste à fusionner n listes de résultats (retournés par les n pairs répondant à une requête donnée) en une liste unique. Si l’on suppose que les systèmes de recherche d’informations sous jacents sont hétérogènes (tant en collection, qu’en modèle de recherche d’information), le problème est complexe. Nous avons proposé une solution basée sur l’exploitation de profils utilisateurs construits sur le même principe que dans le cas du routage. Le but est d’estimer l’importance d’un pair relativement à une requête et l’importance d’une requête relativement à un pair. Un mécanisme de rafraichissement des profils a été également proposé permettant de recalculer de manière incrémentale et distribuée les seuls profils nécessaires. Ces propositions ont été validées par simulation dans des contextes réalistes.

Modifié le 9 avril 2015