Approches sémantiques pour la prédiction de présence d’amiante dans les bâtiments

 Raisonneurs

La possibilité de réaliser des inférences à partir d’un graphe de connaissances est essentielle et représente l’un des avantages majeurs de l’utilisation des ontologies et des règles SWRL qui peuvent leur être associées. Les raisonneurs sont des moteurs d’inférence qui rendent cette tâche possible. Il existe différents raisonneurs qui ont chacun leurs propriétés 9 . Ils se différencient par les environnements dans lesquels ils peuvent être intégrés, par les services de raisonnement supportés et par les méthodologies . Certains raisonneurs peuvent être utilisés à partir de l’environnement “Protégé” 10 qui permet de créer et manipuler des bases ontologiques simples ou complexes. C’est le cas de ELK, FaCT++, HermiT, jcel, ontop et Pellet. D’autres sont aussi supportés par la bibliothèque owlready2 11 de python qui permet la gestion des ontologies (Pellet et HermiT). Pellet, HermiT et FaCT++ sont des raisonneurs qui prennent en charge les spécifications de OWL 2. Cependant, seul Pellet peut utiliser les prédicats intégrés de SWRL tels que greaterThan, lessThan, ou encore lessThanOrEqual, permettant de comparer des données numériques ou de type date. La table 2.1 montre les services de raisonnement supportés par chacun de ces raisonneurs. Dans cette thèse, nous avons choisi d’utiliser Pellet pour sa compatibilité avec OWL (voir section 2.5) et pour sa capacité à intégrer les règles SWRL dans le moteur d’inférences OWL-DL fondé sur les algorithmes des tableaux sémantiques. Pellet permet d’utiliser les prédicats intégrés de SWRL qui permettent de comparer des constantes de divers types tels que les entiers, les dates, etc. De plus, son intégration dans un prototype développé en python est facile (c.-à-d. il est disponible dans la bibliothèque “owlready2” 12 de python).

 Hypothèse du monde ouvert

Les graphes de connaissances sont de plus en plus nombreux et volumineux, mais les données ne sont pas nécessairement complètes. L’hypothèse du monde ouvert (Open World Assumption – OWA) [20] indique que ce qui n’est pas connu pour être vrai n’est pas nécessairement faux. En pratique, cela signifie que des conclusions ne peuvent être tirées qu’à partir de faits et d’axiomes explicitement énoncés. C’est le contraire de l’hypothèse du monde fermé (Closed World Assumption – CWA), qui indique que tout fait vrai est connu pour être vrai. L’hypothèse du monde fermé permet à une application de déduire, de son manque de connaissance d’un fait, que ce fait est faux et d’inférer ce que qui découle de ce fait considéré comme faux. Les langages du Web sémantique tels que OWL font l’hypothèse du monde ouvert. Un raisonneur ne peut pas déduire qu’un fait est faux parce qu’il est absent. Cette hypothèse a également des conséquences sur les approches de découvertes de connaissances telles que l’apprentissage de règles à partir de graphes de connaissances. Ces graphes ne contiennent pas toujours d’exemples négatifs et certaines approches utilisent des hypothèses particulières sur les données. L’approche de [20] a montré comment découvrir des règles à partir de GC malgré l’absence de contre-exemples explicites. L’hypothèse clé est l’hypothèse de complétude partielle (Partial Completeness Assumption – PCA). Cela permet à [20] de considérer des contre-exemples de règles, même dans le cadre de l’OWA. 23 24 Chapitre 3 Revue de l’état de l’art 3.1 Introduction Dans ce chapitre, nous présentons un état de l’art correspondant aux travaux que nous avons réalisés. Nos travaux se basent sur des données du CSTB décrivant des bâtiments et des diagnostics pour construire un graphe de connaissances et utiliser ces données pour prédire la présence d’amiante dans les produits utilisés dans des parties de bâtiments non diagnostiqués. Cette prédiction peut soit se baser sur des connaissances externes décrivant les listes de références de produits amiantés, soit sur des règles de classification induites à partir des diagnostics déjà décrits dans le graphe. Aussi, nous nous focalisons dans ce chapitre sur les approches de liage de données et sur les approches de découvertes de règles. Les approches de liage de données peuvent permettre, en créant des liens d’identités, de compléter un graphe de connaissance pour lequel certains faits sont manquants. Ces approches se basent sur la comparaison des descriptions RDF de deux objets pour décider si ces descriptions réfèrent bien au même objet du monde réel. Dans le contexte des graphes de connaissances (GC), la fouille de règles peut également être utilisée pour enrichir les graphes et permettre de prédire de nouveaux liens ou types, ou permettre de détecter des triplets RDF erronés. Motivées par le besoin de passage à l’échelle, la plupart des approches récentes de prédiction de liens ou de types sont basées sur des méthodes d’apprentissage profond et de plongement de graphes (graph embeddings) qui permettent de traduire des vecteurs de grande dimension en espaces de dimension relativement faible [44]. Néanmoins, d’autres applications pour lesquelles des règles interprétables sont nécessaires pour comprendre et maintenir une certaine connaissance du domaine sont toujours intéressées par la découverte de règles logiques. Dans cet état de l’art, nous allons tout d’abord présenter les stratégies de liage de données basées sur des règles. Nous présenterons ensuite les différentes stratégies d’induction de règles définies en Programmation Logique Inductive (PLI) (Section 3.3) avant de présenter les stratégies d’induction de règles logiques définies pour les 25 graphes de connaissance, et terminerons par la définition des biais de langage qui a une grande importance pour limiter l’espace de recherches et ainsi permettre son exploration en un temps raisonnable, et pour obtenir des résultats qui soient d’intérêts pour les utilisateurs. Puis nous allons discuter l’évolution des approches qui s’intéressent à l’apprentissage de règles, en expliquant les procédures et les types de données traitées par ces approches (Section 3.3.2). Nous présentons également dans cette partie, les mesures de qualités utilisées par ces approches pour évaluer les règles découvertes et les caractéristiques des règles à trouver. 

Approches de liage de données

Le liage de donnée consiste à déterminer si deux descriptions réfèrent au même objet du monde réel. Il est souvent utilisé dans le Web sémantique pour établir des liens entre les données. LinkingOpenData 1 est un des projets de liage de données des graphes RDF où les liens entre les données sont explicitement déclarés en utilisant le constructeur owl :sameAs. Différents types de méthodes permettent de lier les données. Certaines plateformes se basent sur des règles de liage déclarées par un expert du domaine [56]. Cependant, il n’est pas toujours facile pour un expert de spécifier toutes les propriétés ou combinaisons de propriétés qui peuvent être discriminantes pour un ensemble d’individus. Le numéro de sécurité sociale est une propriété clairement discriminante pour des personnes, mais il est plus difficile de spécifier que le nom,la date et le lieu de naissance suffisent à s’assurer qu’il s’agit bien de la même personne. Aussi, certaines approches sont supervisées et se basent sur des échantillons de données liées et de données distinctes. D’autres approches se basent des sur des jeux de données RDF [53, 41] pour lesquelles on peut supposer que l’Unique Name Assumption est respectée. Dans ce cadre, il s’agit de déterminer toutes les propriétés qui suffisent à distinguer un individu d’un autre individu sans avoir besoin d’exemples positifs. Les règles apprises peuvent être plus ou moins expressives. Les approches telles que [52, 53] s’intéressent uniquement à des éléments de descriptions de longueur 1, qui peuvent comporter des constantes. Ainsi [53] permet de découvrir la règle de liage conditionnelle suivante : V ille(X) ∧ V ille(Y ) ∧ Dpartement(X, #Aisne) ∧ Dpartement(Y, #Aisne) ∧ Nom(X, N) ∧ Nom(Y, N) → sameAS(X, Y ) Cette règle signifie que deux villes qui partagent le même nom sont identiques si elles sont situées dans le département de l’Aisne. D’autres approches se basent sur la recherche de motifs de graphes plus complexes qui représentent des expressions référentielles. Une telle approche permet de découvrir par exemple que Mozart est la seule personne qui est un musicien reconnu et qui est né à Salzbourg en 1756. Pour limiter l’espace de recherche, [41] ne s’intéresse qu’aux combinaisons de propriétés instanciées apparaissant dans des non-clefs. Quelle que soit l’approche de liage proposée, il est nécessaire de disposer d’informations communes dans les deux jeux de données qui soient suffisamment discriminantes pour décider que les deux IRI correspondent à deux 1.

Stratégies d’induction de règles

L’induction de règle peut être effectuée en suivant différents types de stratégie et en choisissant celle qui convient le mieux aux besoins de l’ontologue, à la composition et aux différents types des prédicats qui apparaissent dans la règle. Dans cette section, nous présentons les principes de la programmation logique inductive (PLI) suivis par les différents types de stratégies. Par la suite, nous décrirons les différentes approches d’induction de règles. Enfin, nous aborderons les différentes contraintes posées par le biais de langage qui guident les stratégies et bornent l’espace de recherche.

Programmation

Logique Inductive PLI Les approches existantes de découverte de règles de la logique du premier ordre dans les graphes de connaissances sont généralement inspirées des méthodes développées en PLI (Programmation Logique Inductive) [38]. L’objectif de la PLI est d’apprendre d’une hypothèse, c.-à-d. un ensemble de règles de la forme “IF prémisse ALORS conclusion”, à partir d’un ensemble de données appelées exemples. Les exemples fournis pour un apprentissage supervisé correspondent à des couples constitués de la description relationnelle d’un exemple et d’une étiquette correspondant à l’une des classes à apprendre. Lorsque l’on ne dispose que de deux classes (ensemble E+ et E− d’exemples et de contre-exemples des instances de classe), il s’agit d’un problème d’apprentissage de concept. Le problème peut alors être défini comme suit : “L’apprentissage de concepts est la construction d’une description générale d’une classe d’objets à partir d’un ensemble d’exemples positifs et d’exemples négatifs.” [36] Une autre définition formelle est donnée par [10], à partir d’un langage de concepts LC , un langage d’exemples Le, les couvertures ou relations d’appartenance ∈C qui spécifie comment LC se rapporte à Le, et un ensemble d’exemples E d’un concept cible inconnu t ∈ LC . Chaque exemple est de la forme (e, Classe) où e ∈ Le, et Classe est vrai ou f aux. Les exemples (e, vrai) sont des exemples positifs, tandis que les exemples (e, f aux) sont négatifs. L’objectif de l’apprentissage des concepts est alors de trouver une hypothèse H ∈ LC qui couvre tous les exemples positifs (dans ce cas H est complet) et aucun des exemples négatifs (dans ce cas H est cohérent). L’espace de recherche correspond à un ensemble d’hypothèses, pour lequel on doit définir un langage d’hypothèses permettant de délimiter la représentation des concepts à apprendre pour réduire l’espace de recherche et garantir une certaine qualité des résultats en évitant au système de considérer des hypothèses inutiles ou difficiles à interpréter. Il s’agit des biais de langage. Il en est de même pour le langage des exemples et celui de la théorie 27 du domaine. Le parcours de l’espace de recherche est effectué grâce à des opérations de généralisation et/ou de spécialisation basées sur une relation de subsomption. A priori, une hypothèse devrait classifier correctement tous les exemples positifs (complétude) et aucun exemple négatif (correction). Cependant, les exemples d’apprentissage comportent souvent des données erronées ou des exceptions, il est donc parfois difficile de trouver une hypothèse qui soit à la fois complète et correcte. Aussi, la plupart des approches relaxent cette contrainte et essaient de trouver une hypothèse qui couvre de nombreux exemples positifs en couvrant aussi peu d’exemples négatifs que possible. Les algorithmes développés sont soit ascendants ou descendants. Les algorithmes ascendants tels que [40, 50] partent d’un exemple positif et le généralise tant que l’hypothèse ne couvre pas ou peu de négatifs tandis que les algorithmes descendants tels que [2, 47, 40, 25] considèrent une prémisse de règle vide ou correspondant aux hypothèses les plus générales que l’on peut examiner (i.e top(s) de l’espace de recherche) et spécialisent ces hypothèses. L’apprentissage des règles logiques de prédiction est considéré comme un problème de recherche qui est souvent NP-difficile, il faut donc chercher la solution en optimisant l’espace de recherche sachant que la complexité de l’espace de recherche dépend de la complexité des solutions. Stratégies de type Separate-and-conquer Separate-and-Conquer (SAC) et Divide-and-Conquer (DAC) sont des stratégies très populaires pour l’induction de règles logiques. Ces deux stratégies de base sont suivies par différentes approches d’induction des règles sur les graphes de connaissances. Separate-and-Conquer (SAC) (appelé aussi covering algorithms [18]) démarre par la production d’un ensemble de règles en spécialisant à plusieurs reprises une règle plus générale, en exploitant que les exemples positifs, c.- à-d. ces règles découvertes ne couvrent que des exemples positifs. À chaque itération, SAC sélectionne une règle plus spécialisée que si elle couvre un sous-ensemble des exemples positifs et exclut les exemples négatifs. Ceci est répété jusqu’à ce que tous les exemples positifs soient couverts par l’ensemble de règles. Stratégies de type Divide-and-Conquer Par ailleurs, Divide-and-Conquer (DAC) [4] produit une hypothèse en divisant une règle trop générale en un ensemble de règles spécialisées qui couvrent des sous-ensembles disjoints d’exemples. Les règles qui couvrent uniquement les exemples positifs sont conservées, tandis que les règles qui couvrent à la fois les exemples positifs et négatifs sont traitées récursivement de la même manière que la première règle générale. Plus précisément, si DAC trouve une règle qui couvre que des exemples positifs, elle l’ajoute au résultat. Si une règle couvre que des exemples négatifs elle l’exclue du résultat. Cependant, si elle trouve une règle R qui couvre des exemples positifs et négatifs, elle la divise en R1, …Rn telle que R1 ∪ … ∪ Rn ⇔ R, puis elle fait la même chose pour chaque règle Ri 28 avec i ∈ [1, n]. Ces deux stratégies présentent des coûts de calcul différents. Pour SAC, le coût de calcul mesuré en termes de nombre de vérifications pour voir si une règle couvre ou non un exemple augmente de manière quadratique avec la taille de l’ensemble d’exemples, alors qu’il augmente linéairement pour DAC. Cela découle du fait que SAC recherche un espace d’hypothèse plus grand que DAC. Parmi les approches de type DAC nous trouvons celles qui utilisent les arbres de décision logique du premier ordre FOLDT (First-Order Logical Decision Tree) telles que TDIDT (Top-down induction of decision trees) [46] et son successeur TILDE (Top-down induction of logical decision trees) [2]. Ces dernières se basent sur des arbres de décision dans lesquels les noeuds peuvent partager des variables et impliquer des prédicats numériques comportant des valeurs seuils. Cependant, TDIDT et TILDE n’utilisent pas la sémantique de l’ontologie dans l’exploration de l’espace de recherche. TILDE (Top-down induction of logical decision trees) [2] se base sur le système de l’induction descendante des arbres de décision TDIDT [46] qui suit la stratégie de DAC. TDIDT utilise les arbres de décision logique du premier ordre FOLDT pour découvrir des hypothèses H (ou des règles) à partir d’un ensemble de classes C, un ensemble d’exemples E et un ensemble de connaissances B, tel que pour tout e ∈ E, H ∧ e ∧ B  c et e ∈ E, H ∧ e ∧ B 2 c 0 , avec c est la classe de l’exemple e et c 0 ∈ C − {c}. L’hypothèse H est composée de prédicats et de classes qui sont représentés dans les nœuds de FOLDT. Ces nœuds peuvent se retrouvés dans l’arbre T comme des feuilles avec une classe k et dans ce cas ils sont notés T = leaf(k), ou des nœuds internes avec un prédicat pred et deux branches gauche l et droite r, et dans ce cas le nœud est noté T = inode(pred, l, r). Au fur et à mesure que l’exploration de l’arbre avance dans les branches, TILDE enrichit l’hypothèse H par les prédicats trouvés dans les nœuds de la branche en cours d’exploration et qui se termine par la classe localisée dans la feuille (le nœud final de la branche). L’exploration des branches est guidée par un biais de langage déclaratif (voir Section 3.3.1) pour limiter l’espace de recherche. Comme cité précédemment, TILDE est fondé sur les mêmes techniques que TDIDT et calcule en plus le nombre de tests à considérer à un nœud. Ce nombre est trouvé par l’opérateur de raffinement θ−subsomption, c.-à-d. étant donné deux clauses 2 c1 et c2, on dit que c1 θ−subsume c2 ssi ∃θ : c1θ ∈ c2 avec θ est appelé une substitution de variable.