Description Logic Ontologies are one of the most important knowledge representation formalisms nowadays which, broadly speaking, consist of classes of objects and their relations. Given a set of objects as samples and a class expression describing them, we present ongoing work that formalizes which properties of these objects are the most relevant for the given class expression to capture them. Moreover, we provide guidance on how to refine the given expression to better describe the set of objects. The approach is used to characterize test results that lead to a specific maintenance corrective action, and in this paper is illustrated to define sub-classes of aviation reports related to specific aircraft equipment.
Given a DL-Ontology we might find that some concepts definitions are too generic, in the sense that they are not rich enough to capture only the intended objects, or that the definition does not describe them properly. In order to have more control on what is expressed, having sub-types of such concepts is useful, since we can make distinctions between the objects that could not be made before. Our motivation comes from the avionics maintenance domain [Palacios et al.2016] , where we find several levels of maintenance. One of them involves shop repair, where an equipment found faulty on an aircraft is to be repaired or replaced. In this scenario, several tests need to be run to find out the exact part(s) of the equipment which is faulty and causes failures. Once the tests are run, it is up to mechanic experts to determine the possible components of the equipment involved in the failure, and the repairs/replacements to be done. For a maintenance process it is dicult to establish a priori what are the actions to be taken to return the equipment to a fully functional state. Establishing the most probable actions is useful to shorten the examination and repair time, thus gaining in eciency and lowering the costs. In this paper, we aim to model this problem and propose a primitive method. The idea is based on the fact that we know by a large amount of historical shop repair reports the test results and repair decisions made accordingly. We can consider the closed incidents as positive samples of a repair action, the incidents that do not require this repair action as negative ones, and use tests as features of each sample. Then identifying important tests results equals identifying key features that distinguish positives from negatives. Finally we use these key features to provide a description for the sub-set of tests that lead to a specific maintenance action. Our approach thus can be used to obtain formal patterns to capture a set of samples; properties that distinguish positive from negative samples; guide to refine a concept expression and enrich patterns that can be served as features for clustering or classifying samples. 2
Mining formal patterns from data has been identified as an important task in many di↵erent research communities. Depending on the target language used for representing a pattern, we can divide the existing work into di↵erent categories.
Concept Learning Similar to our paper, DL-Learner [Lehmann2009], a state-of-the art tool for concept learning, is based on description logic. It provides a framework for supervised machine learning using several algorithms which are highly parameterizable. It is based on refinement operators like CELOE for OWL expressions and ELTL for the EL family of DLs. Depending on the desired properties of the operator and the DL-constructors allowed, the operator traverses the space of possible concept expression in a top-down or bottom-up way. Then these concept expressions are evaluated, using heuristics, to find the most suitable ones. Shorter and more simple expressions are preferred by these algorithms.
A useful list of approaches for concept learning and their characteristics can be found in [Tran et al.2012] where they position their approach based on bisimulations with respect to other techniques.
In [Divroodi and Nguyen2015], they study how to establish whether the signature of an ontology (the concepts, roles and individuals along with the DLfamily chosen) is sucient to distinguish between two objects. Broadly speaking, if two objects belong to the same equivalence class, they are indistinguishable. On the other hand, given a set of samples, if there exists an expression in the underlying language that can capture this set of samples, then it must be the union of some equivalence classes. They use this notion to provide an algorithm that learns a concept expression, by partitioning the domain with respect to the equivalence classes. One interesting feature of their approach, is that it o↵ers a formal way of defining approximations to a concept expression based on rough sets [Nguyen and Szalas2013] by using the similarity classes and the underlying language.
In the above mentioned approaches, the goal is to find a concept expression that best describes a set of samples, by refining the concept. In a specialization scenario, if a false positive, can be left out of the extension of the concept by adding a restriction to the the objects that belong to it, we know that the selected property separates the false positive from the rest of the samples. Pointing out these properties and objects, is the di↵erence and contribution of this paper with respect to the above mentioned approaches.
Graph mining Graph structures are used within a variety of applications in order to represent structured information. The issue of mining interesting patterns in these graphs structures has thus emerged and a large amount of researches focus on algorithms enabling graph mining. Regarding our application, interesting patterns mean for instance recurring or frequent patterns that can be found either in a big graph or in a set of (smaller) graphs. It may also mean finding significant patterns, either semantically or statistically representative for the instance. From a Machine Learning point of view, interesting patterns are those that well discriminate positive vs. negative samples.
One of the main problems addressed by the di↵erent work raised in the subgraph isomorphism issue. Subgraph isomorphism is an NP-complete problem. Thus, mining subgraphs of a graph means studying an exponential number of subgraphs. In [Yan and Han2003], the authors propose an algorithm, CloseGraph to mine closed frequent graphs. The algorithm uses pruning methods in order to reduce the exploration space. A closed graph in a set of graphs is a graph, for which it exists no proper subgraph that has the same support. Therefore, closed graph patterns will be the largest patterns that can be found in a graph database for a given problem.
[Motoda2007], [Inokuchi et al.2000] and [Yoshida et al.1994] present two approaches for extracting frequent subgraphs: AGM and GBI. AGM relies on the representation of the graphs by adjacency matrices and GBI relies on the chunking of adjacent nodes in order to generate subgraphs and the rewriting of the graphs given the selected subgraphs as new nodes.
Using graph mining, the most relevant structures of a set of graphs can be found. It can be used to find patterns that discriminate positive and negative examples. This is very similar to our problem of learning a concept from examples as patterns describe the common parts of the examples. However, no direct control over the signature is given, neither the possibilities to extend a concept are taken into account. Graph mining techniques can be used as initial step for our approach to find a first substructure that discriminate partially positives and negatives examples. Our feature extraction algorithm may then be applied in order to not remain at a structure level but to consider the semantics, focusing on the relevant properties. Furthermore the associated signature provides theoretical limits to what can be expressed.
The rest of the paper is organized as follows: in section 3 we introduce the approach and the necessary definitions. Then, in section 4 we show a use case based on aviation reports, where we refine a concept based on expert knowledge. Finally, in section 5 the conclusions and further works are presented. 3
We define ontologies based on [Baader2003], where an ontology is a tuple O = hT , Ai with T being the TBox and A the A-Box. The T-Box contains the set of concept and role definitions, while the A-Box contains assertions about the definitions in the T-Box. The signature ⌃ O of an ontology O is the set of all concept names, role names and individuals in O. For details refer to [Divroodi and Nguyen2015]. To make the approach simpler, in the following we consider T = ; and the assertions in the A-Box are of the form A(x) or r(x, y), where A and r are atomic.
Given an ontology O, a set of samples X = Pos [ Neg (where Pos is a set of positive samples and Neg a set of negative samples) and a concept C describing X up to certain degree , we are interested in finding a DL-expression C0 with a better degree 0 to describe X , if it exists. The value of is to be defined in accordance to the problem by the user (for example the recall, the accuracy, f-measure, etc.). Thus, the problem consists in that: a) C captures some unintended objects (false positives),b) it does not capture some intended objects (false negatives) or c) both. We take the case of false positives to illustrate the approach, where C captures some negative samples. In this scenario, we would like to make C more specific, that is to add restrictions to the objects that belong to this concept, in such a way that a) some (or all) false positives are not considered anymore and b) we preserve all (or most) of the positive samples. Given a concept C and a positive instance x 2 Pos, we want to know what are the properties to consider, if we want to specialize C. Intuitively the process is as follows: Any instance and its relation to other objects can be represented as a directed (acyclic) graph, with the nodes representing the objects and the edges representing the relations between them, as stated by the A-Box. For example consider the A-Box :
A : {r1(x, y), r2(y, w), r3(y, z)} we obtain: Since a concept expression C is given as part y y of the input, we can determine which are the properties of object x that are necessary for C to capture it. Assume C ⌘ 9 r1.9 r2.>, then the assertion r3(y, z) is not relevant for deciding whether C(x) = > holds, and a simpler representation of x can be obtained: This representation allows us to establish up to which point the structure of the object x is relevant for C. From the original A-Box, we know that some of the objects to which x is connected, are themselves connected to other objects by relations not considered by C. In our example object y is connected to object z through relation r3. We are interested in these objects, since x x r1 r1 r2 r3 r2 w z w they provide all the properties that we can consider to further specialize C and still capture x, and therefore represent the relevant properties to capture the set of positive instances. In order to provide a formal definition for these objects, let us first introduce some necessary notions.
Definition 1 Given an ontology O with signature ⌃ O, two objects x, y and an A-Box A, we say that there exists a binary relation closure between x and y, denoted by r " (x, y), if x = y or if there exists a path of the form: {r1(x, z1), r2(z1, z2), . . . , rm(zn 1, zn)} ✓ A with n 1, zn = y, and rj 2 ⌃ O(1 j m).
Next, we want to establish which of the edges of the graph representing the object are necessary for a given concept to capture the object. This is formalized by the following definition: Definition 2 Given an object x, a concept C, an ABox A and a binary relation r(y, z) 2 A , we say that r(y, z) is necessary for C to capture x i↵:
C(x) = > w.r.t A, r " (x, y), r(y, z) 2 A but Likewise, we say that r(y, z) is unnecessary if C(x) = ? w.r.t A \ r(y, z)
C(x) = > w.r.t A \ r(y, z) still holds. Additionally, we say that an object o is necessary if o = x or: 9 z | r(z, o) 2 A
s.t. r(z, o) is necessary.
Note that depending on the concept C and the content of the A-Box, a unnecessary binary relation might become necessary, therefore several possible answers might exist. For example take the concept C ⌘ 9 r.> and the A-Box: A = {r(x, y), r(x, z)}, then we have:
C(x) = > w.r.t A \ r(x, y) Concluding that r(x, y) is not necessary, but only as long as r(x, z) 2 A (and vice-versa). Given a definition for the properties and objects necessary for an object x to belong to a concept C, we can also obtain those that are not necessary. These (unnecessary) properties are linked to the object x but are not required by C. As such they can be seen as candidate properties for specializing C and still capture x. These are the properties of special objects hereafter called leafs of x, defined by: Definition 3 Given an object x, a concept C and an A-Box A the set of leafs of x w.r.t C is given by:
Leafsx,C = {y | r(y, z) 2 A where y is necessary for C to capture x but r(y, z) is not necessary for C to capture x} Intuitively the set Leafsx,C represents all those objects y in the frontier of x w.r.t. C, in the sense that no further edges of the graph representing x are considered by C to decide whether the object x belongs to it. Definition 4 Given an object x, a concept C and the set Leafsx,C w.r.t. an A-Box A, the set of extensions Extx,C to specialize C w.r.t. x is defined by:
Extx,C = {r(y, z) 2 A | y 2 Leafsx,C and r(y, z) is not necessary for C to capture x } Intuitively Extx,C provides all those role names through which C can be specialized and still capture x. The set of leafs and their properties are the answer to our problem (they provide the ways in which we can specialize C, from where we can derive the conflictive properties and the conflicting objects). Before we present an algorithm to obtain the necessary properties, let us show that the definitions are not sucient alone. Consider now C ⌘ 9 r.> and A = {r(x, y), r(y, w), r(x, z)}, we have Leafsx,C = {x} and Extx,C = {r(x, y), r(x, z)}. We can indeed specialize C using these properties, but nothing in the above answer gives us the information that either r(x, y) or r(x, z) is required for C(x) = > to hold (we just know they are not necessary). To obtain this information, we take the unnecessary relations and remove them one by one from the A Box until a minimal set of necessary role assertions is reached. We now introduce an algorithm to compute a minimal set of necessary role assertions, from which we can extract Leafsx,C and Extx,C: In Algorithm 1 we first compute Rx (2), which is the subset of the A-Box A containing all those role assertions in a path from x: r(x, y) 2 Rx since r " (x, x) and r(x, y) 2 A r(y, w) 2 Rx since r " (x, y) and r(y, w) 2 A r(x, z) 2 Rx since r " (x, x) and r(x, z) 2 A
We have : Rx = CopyR = {r(x, y), r(y, w), r(x, z)} (3) makes a copy CopyR of Rx from which we will sequentially remove the last elements of each path. (4) establishes as the candidates CandR to be tested all Algorithm 1 Minimal set of necessary role assertions 1: input: (x, C(x) = >, A) 2: Rx = {r(y, z) | r " (x, y), r(y, z) 2 A} 3: CopyR = Rx 4: CandR = {r(y, z) 2 Rx |6 9 w s.t. r(z, w) 2 Rx} 5: Cx = {D(z) 2 A | z = x or 9 y s.t. r(y, z) 2 Rx} 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 9: remove r(y, z) from Rx 10: end if 11: remove r(y, z) from CopyR 12: end for 13: CandR = {r(y, z) 2 CopyR |6 9 w s.t. r(z, w) 2
CopyR} 14: end while 15: return: Rx those role assertions that do not have further outgoing edges (that is, the last elements of a path):
CandR = {r(y, w), r(x, z)} (5) creates the set of all concept assertions about all the objects that take part in a relation in Rx. In our example is empty. Then we start the while loop to test all assertions for necessity until no more candidates are found. (7) takes one candidate at the time, and (8) tests if its necessary. The unnecessary assertions are removed from Rx (9). Any assertion already tested is removed from CopyR by (11) in order not to test them twice. First we test r(y, w):
C(x) = >w.r.t.{Rx \ r(y, w)} [ Cx , remove r(y, w) Rx = {r(x, y), r(x, z)} , CopyR = {r(x, y), r(x, z)}
C(x) = >w.r.t.{Rx \ r(x, z)} [ Cx , remove r(x, z)
Rx = {r(x, y)} , CopyR = {r(x, y)} Once all identified candidates are tested, the set CandidatesR is re-computed (13) considering only those assertions remaining in CopyR,
CandR = {r(x, y)} A second run of the while loop tests r(x, y) yielding: C(x) = ? w.r.t.{Rx \ r(x, y)} [ Cx , keep r(x, y)
Rx = {r(x, y)} , CopyR = {} Since there are no more candidates to test, the output of the algorithm is the modified set Rx which is a minimal set of necessary role assertions for C(x) = > 1:
Rx = {r(x, y)} 1The proof for this property remains as further work. From this set we can easily construct Leafsx,C and Extx,C, following their definitions:
Leaf sx,C = {x, y} , Extx,C = {r(y, w), r(x, z)} Where the possible extensions to consider to specialize C are r(y, w), r(x, z), which is the intended answer. 4
Since the data specific to aviation maintenance is restricted for disclosure, we provide an example based on aviation incidents. Similarly as in aviation maintenance, where we want to find sub-types of failures based on their features, here we want to obtain interesting sub-concepts of aviation issues. We count with an ontology OASRS representing the reported aviation incidents from the ASRS 2 database, and a set of equipment used in aviation, from which we selected GPS. In this scenario, we are interested on which properties to take into account to obtain those ”GPS related aviation issues” and those ”aviation issues where the GPS presented a problem”. We proceed as follows: in the ASRS website, a classification of some reports made by experts is given, one of such sets is ”GP S related reports”. This provides us with the set of positive instances Pos 3. As the set of negative instances Neg, we have selected reports related to other types of incidents disjoint with Pos:
Pos = {1336, 1347, 1359} , Neg = {1361} The A-Box A is composed of the following concepts and roles: AviationIssue =
Aircraf t = N avInU se = CompP rob = involves = usesN av repP roblem = = hasN arrative = {1336, 1347, 1359, 1361} {A1, A2, A3, A4} {GP S, F M S} {M f, IO} {(1336, A1), (1347, A2), (1359, A3), (1361, A4)} {(A1, GP S), (A2, GP S), (A3, GP S), (A3, F M S)} {(A1, M f ), (A2, M f ), (A3, IO), (A4, M f )} {(1336, ”..GP S..”), (1347, ”..GP S..”), (1359, ”..GP S..”), (1361, ”..GP S..”)}
A1 AviationIssue Aircraft NavInUse hasNarrative repP roblem
..GPS..
Narrative
GPS
Mf
CompProb
It is easy to see that the AviationIssue 1336 is an instance of C, but the problem is that we also find C(1361) = >, thus C does not classify the objects in the intended way. To establish how to improve C, we use algorithm 1 to obtain Rx, and from this set of necessary role assertions we obtain its leafs and the possible properties to specialize it:
Rx = {involves(1336, A1)}
Leafsx = {1336, A1} Extx,C = {hasN arrative(1336, ”...GP S...”),
usesN av(A1, GP S), repP rob(A1, M f )} It is out of the scope of this paper how to construct a concept expression using the identified properties, nevertheless we provide some examples to illustrate the approach. If we first consider hasN arrative to specialize C, we can add a restriction in the following way:
C0 ⌘ 9 involves.> ^ 9
hasN arrative.{”...GP S...”} The concept C0 expects that any report mentioning GPS in its narrative is indeed a ”GPS related report”.
But even though report 1361 mentions GPS, it is not classified as ”GPS related reports” by the experts (set Pos). Thus, we learn that hasN arrative is not the property that allows us to distinguish them. We proceed now with the property usesN av. We can specialize C by:
C00 ⌘ 9
Involves.9 usesN av.> Then C00 correctly classifies Pos and Neg (since (where: Mf=Malfunctioning,CompProb=ComponentProblem, C00(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 specialization 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 interthe form: esting concept expression, representing those ”Avia
C ⌘ 9 involves.> tTiohne Issestuseosfthpaotsiitnivveolavneda npergoabtlievemsawmitphleGsPbSecdoemviec:es”. 2Aviation Safety Report System (https://asrs.arc.nasa.gov) 3The samples have been simplified for this paper.
Pos = {1336, 1347} , Neg = {1359, 1361} Considering again object 1336 and C00 as part of the input, the graph representation of its necessary properties is:
Leafsx,C00 = {1336, A1}
Extx,C00 = {hasN arrative, repP rob} If we select repP rob we can construct a concept expression of the form:
C000 ⌘ 9
Involves.(9 usesN av.> u 9 repP rob.{M f }) We can see that C000 properly distinguishes between Pos and Neg, and we learn that the most important property to make this distinction w.r.t. C00 is repP rob, where the most relevant objects (leafs) and their properties provide the key to construct such expressions. Aviation Issues A.I. mention GPS A.I. related to GPS
A.I. present GPS problems
We consider that the most simple case (without a TBox) is the most appropriate way to introduce our work and show how it can be used to obtain those properties relevant for a concept to capture an object. This information can be used to guide the refinement process or generalizing a concept, since we know exactly up to which point the properties of the object are taken into account by the concept expression in the input. The approach can also be useful for optimizing concept learning techniques, given that the scenario is restricted to our specifications. A constructive way for obtaining the refined concept can be given, which is dependent of the DL-family chosen for the ontology. Finally, we will study the method for generating rich features for action prediction in the avionics maintenance domain.