Data Driven Concept Refinement to Support Avionics Maintenance Luis Palacios Medinacelli1,2 Yue Ma2 Gaëlle Lortal1 Claire Laudy1 Chantal Reynaud2 1 LRASC, Thales Research & Technology, Palaiseau, France 2 LRI, Univ. Paris-Sud, CNRS, Université Paris-Saclay, France {gaelle.lortal,claire.laudy}@thalesgroup.com, {palacios,ma,cr}@lri.fr to be run to find out the exact part(s) of the equip- ment which is faulty and causes failures. Once the Abstract tests are run, it is up to mechanic experts to determine the possible components of the equipment involved in Description Logic Ontologies are one of the the failure, and the repairs/replacements to be done. most important knowledge representation for- For a maintenance process it is difficult to establish a malisms nowadays which, broadly speaking, priori what are the actions to be taken to return the consist of classes of objects and their rela- equipment to a fully functional state. Establishing the tions. Given a set of objects as samples and most probable actions is useful to shorten the exami- a class expression describing them, we present nation and repair time, thus gaining in efficiency and ongoing work that formalizes which properties lowering the costs. In this paper, we aim to model this of these objects are the most relevant for the problem and propose a primitive method. The idea is given class expression to capture them. More- based on the fact that we know by a large amount of over, we provide guidance on how to refine the historical shop repair reports the test results and re- given expression to better describe the set of pair decisions made accordingly. We can consider the objects. The approach is used to characterize closed incidents as positive samples of a repair action, test results that lead to a specific maintenance the incidents that do not require this repair action as corrective action, and in this paper is illus- negative ones, and use tests as features of each sample. trated to define sub-classes of aviation reports Then identifying important tests results equals identi- related to specific aircraft equipment. fying key features that distinguish positives from neg- atives. Finally we use these key features to provide 1 Introduction a description for the sub-set of tests that lead to a Given a DL-Ontology we might find that some con- specific maintenance action. Our approach thus can cepts definitions are too generic, in the sense that they be used to obtain formal patterns to capture a set of are not rich enough to capture only the intended ob- samples; properties that distinguish positive from neg- jects, or that the definition does not describe them ative samples; guide to refine a concept expression and properly. In order to have more control on what is enrich patterns that can be served as features for clus- expressed, having sub-types of such concepts is use- tering or classifying samples. ful, since we can make distinctions between the ob- jects that could not be made before. Our motiva- 2 Positioning tion comes from the avionics maintenance domain Mining formal patterns from data has been identified [Palacios et al.2016] , where we find several levels of as an important task in many di↵erent research com- maintenance. One of them involves shop repair, where munities. Depending on the target language used for an equipment found faulty on an aircraft is to be re- representing a pattern, we can divide the existing work paired or replaced. In this scenario, several tests need into di↵erent categories. Copyright c by the paper’s authors. Copying permitted for Concept Learning Similar to our paper, DL-Learner private and academic purposes. [Lehmann2009], a state-of-the art tool for concept In: Proceedings In: Proceedings ofofIJCAI Workshop the SML on Semantic Workshop, Machine Australia, Melbourne, Learning learning, is based on description logic. It provides a (SMLpublished 20-08-2017, 2017), Aug at19-25 2017, Melbourne, Australia. http://ceur-ws.org framework for supervised machine learning using sev- eral algorithms which are highly parameterizable. It is work raised in the subgraph isomorphism issue. Sub- based on refinement operators like CELOE for OWL graph isomorphism is an NP-complete problem. Thus, expressions and ELTL for the EL family of DLs. De- mining subgraphs of a graph means studying an expo- pending on the desired properties of the operator and nential number of subgraphs. In [Yan and Han2003], the DL-constructors allowed, the operator traverses the authors propose an algorithm, CloseGraph to mine the space of possible concept expression in a top-down closed frequent graphs. The algorithm uses pruning or bottom-up way. Then these concept expressions are methods in order to reduce the exploration space. A evaluated, using heuristics, to find the most suitable closed graph in a set of graphs is a graph, for which it ones. Shorter and more simple expressions are pre- exists no proper subgraph that has the same support. ferred by these algorithms. Therefore, closed graph patterns will be the largest A useful list of approaches for concept learning and patterns that can be found in a graph database for a their characteristics can be found in [Tran et al.2012] given problem. where they position their approach based on bisimu- [Motoda2007], [Inokuchi et al.2000] and lations with respect to other techniques. [Yoshida et al.1994] present two approaches for In [Divroodi and Nguyen2015], they study how to extracting frequent subgraphs: AGM and GBI. establish whether the signature of an ontology (the AGM relies on the representation of the graphs by concepts, roles and individuals along with the DL- adjacency matrices and GBI relies on the chunking of family chosen) is sufficient to distinguish between two adjacent nodes in order to generate subgraphs and the objects. Broadly speaking, if two objects belong to rewriting of the graphs given the selected subgraphs the same equivalence class, they are indistinguishable. as new nodes. On the other hand, given a set of samples, if there Using graph mining, the most relevant structures exists an expression in the underlying language that of a set of graphs can be found. It can be used to can capture this set of samples, then it must be the find patterns that discriminate positive and negative union of some equivalence classes. They use this no- examples. This is very similar to our problem of learn- tion to provide an algorithm that learns a concept ex- ing a concept from examples as patterns describe the pression, by partitioning the domain with respect to common parts of the examples. However, no direct the equivalence classes. One interesting feature of their control over the signature is given, neither the pos- approach, is that it o↵ers a formal way of defining ap- sibilities to extend a concept are taken into account. proximations to a concept expression based on rough Graph mining techniques can be used as initial step sets [Nguyen and Szalas2013] by using the similarity for our approach to find a first substructure that dis- classes and the underlying language. criminate partially positives and negatives examples. In the above mentioned approaches, the goal is to find Our feature extraction algorithm may then be applied a concept expression that best describes a set of sam- in order to not remain at a structure level but to con- ples, by refining the concept. In a specialization sce- sider the semantics, focusing on the relevant proper- nario, if a false positive, can be left out of the extension ties. Furthermore the associated signature provides of the concept by adding a restriction to the the objects theoretical limits to what can be expressed. that belong to it, we know that the selected property The rest of the paper is organized as follows: in separates the false positive from the rest of the sam- section 3 we introduce the approach and the necessary ples. Pointing out these properties and objects, is the definitions. Then, in section 4 we show a use case di↵erence and contribution of this paper with respect based on aviation reports, where we refine a concept to the above mentioned approaches. based on expert knowledge. Finally, in section 5 the Graph mining Graph structures are used within a conclusions and further works are presented. variety of applications in order to represent structured information. The issue of mining interesting patterns 3 Defining the most relevant features in these graphs structures has thus emerged and a large amount of researches focus on algorithms en- We define ontologies based on [Baader2003], where an abling graph mining. Regarding our application, in- ontology is a tuple O = hT , Ai with T being the T- teresting patterns mean for instance recurring or fre- Box and A the A-Box. The T-Box contains the set of quent patterns that can be found either in a big graph concept and role definitions, while the A-Box contains or in a set of (smaller) graphs. It may also mean find- assertions about the definitions in the T-Box. The sig- ing significant patterns, either semantically or statisti- nature ⌃O of an ontology O is the set of all concept cally representative for the instance. From a Machine names, role names and individuals in O. For details Learning point of view, interesting patterns are those refer to [Divroodi and Nguyen2015]. To make the ap- that well discriminate positive vs. negative samples. proach simpler, in the following we consider T = ; One of the main problems addressed by the di↵erent and the assertions in the A-Box are of the form A(x) or r(x, y), where A and r are atomic. they provide all the properties that we can consider Given an ontology O, a set of samples X = Pos [ to further specialize C and still capture x, and there- Neg (where Pos is a set of positive samples and Neg fore represent the relevant properties to capture the a set of negative samples) and a concept C describing set of positive instances. In order to provide a formal X up to certain degree , we are interested in finding definition for these objects, let us first introduce some a DL-expression C 0 with a better degree 0 to describe necessary notions. X , if it exists. The value of is to be defined in ac- cordance to the problem by the user (for example the Definition 1 Given an ontology O with signature recall, the accuracy, f-measure, etc.). Thus, the prob- ⌃O , two objects x, y and an A-Box A, we say that lem consists in that: a) C captures some unintended there exists a binary relation closure between x and y, objects (false positives),b) it does not capture some denoted by r "(x, y), if x = y or if there exists a path intended objects (false negatives) or c) both. of the form: We take the case of false positives to illustrate the ap- proach, where C captures some negative samples. In {r1 (x, z1 ), r2 (z1 , z2 ), . . . , rm (zn 1 , zn )} ✓ A this scenario, we would like to make C more specific, that is to add restrictions to the objects that belong with n 1, zn = y, and rj 2 ⌃O (1  j  m). to this concept, in such a way that a) some (or all) Next, we want to establish which of the edges of the false positives are not considered anymore and b) we graph representing the object are necessary for a given preserve all (or most) of the positive samples. Given a concept to capture the object. This is formalized by concept C and a positive instance x 2 Pos, we want to the following definition: know what are the properties to consider, if we want to specialize C. Intuitively the process is as follows: Definition 2 Given an object x, a concept C, an A- Any instance and its relation to other objects can be Box A and a binary relation r(y, z) 2 A, we say that represented as a directed (acyclic) graph, with the r(y, z) is necessary for C to capture x i↵: nodes representing the objects and the edges repre- senting the relations between them, as stated by the C(x) = > w.r.t A, r "(x, y), r(y, z) 2 A but A-Box. For example consider the A-Box : C(x) = ? w.r.t A \ r(y, z) A : {r1 (x, y), r2 (y, w), r3 (y, z)} Likewise, we say that r(y, z) is unnecessary if we obtain: Since a concept expression C is given as part r2 C(x) = > w.r.t A \ r(y, z) r1 w x y r3 still holds. Additionally, we say that an object o is z necessary if o = x or: Figure 1: The graph representation of object x 9z | r(z, o) 2 A s.t. r(z, o) is necessary. of the input, we can determine which are the proper- ties of object x that are necessary for C to capture it. Note that depending on the concept C and the con- Assume C ⌘ 9r1 .9r2 .>, then the assertion r3 (y, z) is tent of the A-Box, a unnecessary binary relation might not relevant for deciding whether C(x) = > holds, and become necessary, therefore several possible answers a simpler representation of x can be obtained: This might exist. For example take the concept C ⌘ 9r.> and the A-Box: A = {r(x, y), r(x, z)}, then we have: r2 r1 w x y C(x) = > w.r.t A \ r(x, y) Concluding that r(x, y) is not necessary, but only as Figure 2: The graph representation of object x, w.r.t. long as r(x, z) 2 A (and vice-versa). Given a definition A \ r3 (y, z) for the properties and objects necessary for an object representation allows us to establish up to which point x to belong to a concept C, we can also obtain those the structure of the object x is relevant for C. From that are not necessary. These (unnecessary) proper- the original A-Box, we know that some of the objects ties are linked to the object x but are not required by to which x is connected, are themselves connected to C. As such they can be seen as candidate properties other objects by relations not considered by C. In our for specializing C and still capture x. These are the example object y is connected to object z through re- properties of special objects hereafter called leafs of x, lation r3 . We are interested in these objects, since defined by: Definition 3 Given an object x, a concept C and an Algorithm 1 Minimal set of necessary role assertions A-Box A the set of leafs of x w.r.t C is given by: 1: input: (x, C(x) = >, A) 2: Rx = {r(y, z) | r " (x, y), r(y, z) 2 A} Leafs x,C = {y | r(y, z) 2 A 3: CopyR = Rx 4: CandR = {r(y, z) 2 Rx |6 9w s.t. r(z, w) 2 Rx } where y is necessary for C to capture x 5: Cx = {D(z) 2 A | z = x or 9y s.t. r(y, z) 2 Rx } but r(y, z) is not necessary for C to capture x} 6: while CandR 6= ; do 7: for r(y, z) 2 CandR do 8: if C(x) = > w.r.t. {Rx \ r(y, z)} [ Cx then Intuitively the set Leafs x,C represents all those objects 9: remove r(y, z) from Rx y in the frontier of x w.r.t. C, in the sense that no fur- 10: end if ther edges of the graph representing x are considered 11: remove r(y, z) from CopyR by C to decide whether the object x belongs to it. 12: end for 13: CandR = {r(y, z) 2 CopyR |6 9w s.t. r(z, w) 2 Definition 4 Given an object x, a concept C and the CopyR } set Leafs x,C w.r.t. an A-Box A, the set of extensions 14: end while Extx,C to specialize C w.r.t. x is defined by: 15: return: Rx Extx,C = {r(y, z) 2 A | y 2 Leafs x,C those role assertions that do not have further outgoing edges (that is, the last elements of a path): and r(y, z) is not necessary for C to capture x } CandR = {r(y, w), r(x, z)} Intuitively Extx,C provides all those role names through which C can be specialized and still capture (5) creates the set of all concept assertions about all x. The set of leafs and their properties are the answer the objects that take part in a relation in Rx . In our to our problem (they provide the ways in which we example is empty. Then we start the while loop to test can specialize C, from where we can derive the con- all assertions for necessity until no more candidates are flictive properties and the conflicting objects). Be- found. (7) takes one candidate at the time, and (8) fore we present an algorithm to obtain the neces- tests if its necessary. The unnecessary assertions are sary properties, let us show that the definitions are removed from Rx (9). Any assertion already tested is not sufficient alone. Consider now C ⌘ 9r.> and removed from CopyR by (11) in order not to test them A = {r(x, y), r(y, w), r(x, z)}, we have Leafs x,C = twice. First we test r(y, w): {x} and Extx,C = {r(x, y), r(x, z)}. We can indeed specialize C using these properties, but nothing in C(x) = >w.r.t.{Rx \ r(y, w)} [ Cx , remove r(y, w) the above answer gives us the information that either Rx = {r(x, y), r(x, z)} , CopyR = {r(x, y), r(x, z)} r(x, y) or r(x, z) is required for C(x) = > to hold (we just know they are not necessary). To obtain this infor- Then, r(x, z) is tested: mation, we take the unnecessary relations and remove C(x) = >w.r.t.{Rx \ r(x, z)} [ Cx , remove r(x, z) them one by one from the A Box until a minimal set of necessary role assertions is reached. We now Rx = {r(x, y)} , CopyR = {r(x, y)} introduce an algorithm to compute a minimal set of Once all identified candidates are tested, the set necessary role assertions, from which we can extract CandidatesR is re-computed (13) considering only Leafs x,C and Extx,C : those assertions remaining in CopyR , In Algorithm 1 we first compute Rx (2), which is the subset of the A-Box A containing all those role asser- CandR = {r(x, y)} tions in a path from x: A second run of the while loop tests r(x, y) yielding: r(x, y) 2 Rx since r " (x, x) and r(x, y) 2 A C(x) = ?w.r.t.{Rx \ r(x, y)} [ Cx , keep r(x, y) r(y, w) 2 Rx since r " (x, y) and r(y, w) 2 A Rx = {r(x, y)} , CopyR = {} r(x, z) 2 Rx since r " (x, x) and r(x, z) 2 A Since there are no more candidates to test, the out- put of the algorithm is the modified set Rx which is a We have : Rx = CopyR = {r(x, y), r(y, w), r(x, z)} minimal set of necessary role assertions for C(x) = > 1 : (3) makes a copy CopyR of Rx from which we will Rx = {r(x, y)} sequentially remove the last elements of each path. (4) establishes as the candidates CandR to be tested all 1 The proof for this property remains as further work. From this set we can easily construct Leafs x,C and involves usesN av Extx,C , following their definitions: 1336 A1 GP S AviationIssue Aircraft NavInUse Leaf sx,C = {x, y} , Extx,C = {r(y, w), r(x, z)} hasN arrative repP roblem ..GP S.. Mf Where the possible extensions to consider to specialize C are r(y, w), r(x, z), which is the intended answer. Narrative CompProb 4 Use case Figure 3: The graph representation of object 1336, instance of AviationIssue concept. Concepts are rep- Since the data specific to aviation maintenance is re- resented in bold, values as nodes, and relations as stricted for disclosure, we provide an example based edges. on aviation incidents. Similarly as in aviation main- tenance, where we want to find sub-types of failures It is easy to see that the AviationIssue 1336 is an based on their features, here we want to obtain in- instance of C, but the problem is that we also find teresting sub-concepts of aviation issues. We count C(1361) = >, thus C does not classify the objects in with an ontology OASRS representing the reported avi- the intended way. To establish how to improve C, we ation incidents from the ASRS 2 database, and a set use algorithm 1 to obtain Rx , and from this set of of equipment used in aviation, from which we selected necessary role assertions we obtain its leafs and the GPS. In this scenario, we are interested on which prop- possible properties to specialize it: erties to take into account to obtain those ”GPS re- Rx = {involves(1336, A1)} lated aviation issues” and those ”aviation issues where the GPS presented a problem”. We proceed as follows: Leafs x = {1336, A1} in the ASRS website, a classification of some reports Extx,C = {hasN arrative(1336, ”...GP S...”), made by experts is given, one of such sets is ”GP S related reports”. This provides us with the set of posi- usesN av(A1, GP S), repP rob(A1, M f )} tive instances Pos 3 . As the set of negative instances It is out of the scope of this paper how to construct Neg, we have selected reports related to other types of a concept expression using the identified properties, incidents disjoint with Pos: nevertheless we provide some examples to illustrate the approach. If we first consider hasN arrative to Pos = {1336, 1347, 1359} , Neg = {1361} specialize C, we can add a restriction in the following way: The A-Box A is composed of the following concepts and roles: C 0 ⌘ 9involves.> ^ 9hasN arrative.{”...GP S...”} AviationIssue = {1336, 1347, 1359, 1361} The concept C 0 expects that any report mentioning Aircraf t = {A1, A2, A3, A4} GPS in its narrative is indeed a ”GPS related report”. N avInU se = {GP S, F M S} But even though report 1361 mentions GPS, it is not CompP rob = {M f, IO} classified as ”GPS related reports” by the experts (set involves = {(1336, A1), (1347, A2), (1359, A3), Pos). Thus, we learn that hasN arrative is not the (1361, A4)} property that allows us to distinguish them. We pro- usesN av = {(A1, GP S), (A2, GP S), (A3, GP S), ceed now with the property usesN av. We can special- (A3, F M S)} repP roblem = {(A1, M f ), (A2, M f ), (A3, IO), ize C by: (A4, M f )} C 00 ⌘ 9Involves.9usesN av.> hasN arrative = {(1336, ”..GP S..”), (1347, ”..GP S..”), Then C 00 correctly classifies Pos and Neg (since (1359, ”..GP S..”), (1361, ”..GP S..”)} 00 (where: Mf=Malfunctioning,CompProb=ComponentProblem, C (1361) = ?). We learn that usesN av is the most IO=Improperly operated,repProblem=reportedProblem, relevant property to specialize C that allows us to NavInUse=Navigation system in use) make the desired distinction, and that the specializa- tion should be made in the position of the leaf A1 in the Assume as input we are given a concept expression of graph. Finally, assume we want to obtain a more inter- the form: esting concept expression, representing those ”Avia- C ⌘ 9involves.> tion Issues that involve a problem with GPS devices”. The sets of positive and negative samples become: 2 Aviation Safety Report System (https://asrs.arc.nasa.gov) 3 The samples have been simplified for this paper. Pos = {1336, 1347} , Neg = {1359, 1361} Considering again object 1336 and C 00 as part of the References input, the graph representation of its necessary prop- [Baader2003] Franz Baader. The description logic erties is: handbook: Theory, implementation and applica- involves usesN av tions. Cambridge university press, 2003. 1336 A1 GP S [Divroodi and Nguyen2015] Ali Rezaei Divroodi and AviationIssue Aircraft NavInUse Linh Anh Nguyen. On bisimulations for description logics. Information Sciences, 295:465–493, 2015. Figure 4: The graph representation of object x, where only the necessary properties for C 00 to capture it are [Inokuchi et al.2000] Akihiro Inokuchi, Takashi shown. Washio, and Hiroshi Motoda. An apriori-based algorithm for mining frequent substructures from Where: graph data. In Proceedings of the 4th European Leafs x,C 00 = {1336, A1} Conference on Principles of Data Mining and Extx,C 00 = {hasN arrative, repP rob} Knowledge Discovery, PKDD ’00, pages 13–23, London, UK, UK, 2000. Springer-Verlag. If we select repP rob we can construct a concept ex- pression of the form: [Lehmann2009] Jens Lehmann. Dl-learner: learning concepts in description logics. Journal of Machine C 000 ⌘ 9Involves.(9usesN av.> u 9repP rob.{M f }) Learning Research, 10(Nov):2639–2642, 2009. We can see that C 000 properly distinguishes between [Motoda2007] Hiroshi Motoda. Pattern Discovery Pos and Neg, and we learn that the most important from Graph-Structured Data - A Data Mining Per- property to make this distinction w.r.t. C 00 is repP rob, spective, pages 12–22. Springer Berlin Heidelberg, where the most relevant objects (leafs) and their prop- Berlin, Heidelberg, 2007. erties provide the key to construct such expressions. [Nguyen and Szalas2013] Linh Anh Nguyen and An- drzej Szalas. Logic-based roughification. Rough Sets Aviation Issues and Intelligent Systems-Professor Zdzislaw Pawlak in Memoriam, pages 517–543, 2013. A.I. mention GPS [Palacios et al.2016] Luis Palacios, Galle Lortal, A.I. related to GPS Claire Laudy, Christian Sannino, Ludovic Simon, A.I. present Giuseppe Fusco, Yue Ma, and Chantal Reynaud. GPS problems Avionics maintenance ontology building for fail- ure diagnosis support. In Proceedings of the 8th International Joint Conference on Knowledge Figure 5: Specialization of concept ”Aviation Issue”. Discovery, Knowledge Engineering and Knowledge Management (IC3K 2016), pages 204–209, 2016. 5 Conclusions and further works [Tran et al.2012] Thanh-Luong Tran, Quang-Thuy Ha, Linh Anh Nguyen, Hung Son Nguyen, Andrzej We consider that the most simple case (without a T- Szalas, et al. Concept learning for description logic- Box) is the most appropriate way to introduce our based information systems. In Knowledge and Sys- work and show how it can be used to obtain those tems Engineering (KSE), 2012 Fourth International properties relevant for a concept to capture an object. Conference on, pages 65–73. IEEE, 2012. This information can be used to guide the refinement process or generalizing a concept, since we know ex- [Yan and Han2003] Xifeng Yan and Jiawei Han. actly up to which point the properties of the object are Closegraph: Mining closed frequent graph patterns. taken into account by the concept expression in the in- In Proceedings of the Ninth ACM SIGKDD Inter- put. The approach can also be useful for optimizing national Conference on Knowledge Discovery and concept learning techniques, given that the scenario Data Mining, KDD ’03, pages 286–295, New York, is restricted to our specifications. A constructive way NY, USA, 2003. ACM. for obtaining the refined concept can be given, which [Yoshida et al.1994] Kenichi Yoshida, Hiroshi Mo- is dependent of the DL-family chosen for the ontology. toda, and Nitin Indurkhya. Graph-based induction Finally, we will study the method for generating rich as a unified learning framework. Applied Intelli- features for action prediction in the avionics mainte- gence, 4(3):297–316, 1994. nance domain.