Sebastian Rudolph
email: sebastian.rudolph@tu-dresden.de

Christian Sȃcȃrea
email: csacarea@cs.ubbcluj.ro

Diana Troancȃ
email: dianat@cs.ubbcluj.ro

Conceptual Navigation for Polyadic Formal Concept Analysis

Formal Concept Analysis (FCA) is a mathematically inspired field of knowledge representation with wide applications in knowledge discovery and decision support. Polyadic FCA is a generalization of classical FCA that instead of a binary uses an arbitrary, n-ary incidence relation to define formal concepts, i.e., data clusters in which all elements are interrelated. We discuss a paradigm for navigating the space of such (formal) concepts, based on so-called membership constraints. We present an implementation for the cases n ∈ {2, 3, 4} using an encoding into answer-set programming (ASP) allowing us to exploit highly efficient strategies offered by optimized ASP solvers. For the case n = 3, we compare this implementation to a second strategy that uses exhaustive search in the concept set, which is precomputed by an existing tool. We evaluate the implementation strategies in terms of performance. Finally, we discuss the limitations of each approach and the possibility of generalizations to n-ary datasets.

Introduction

Conceptual knowledge is closely related to a deeper understanding of existing facts and relationships, but also to the process of arguing and communicating why something happens in a particular way. Formal Concept Analysis (FCA) [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF] is a mathematical theory introduced by Wille, being the core of Conceptual Knowledge Processing [START_REF] Wille | Methods of conceptual knowledge processing[END_REF]. It emerged from applied mathematics and quickly developed into a powerful framework for knowledge representation. It is based on a set-theoretical semantics and provides a rich amount of mathematical instruments for the representation, acquisition, retrieval, discovery and further processing of knowledge. FCA defines concepts as maximal clusters of data in which all elements are mutually interrelated. In FCA, data is represented in a basic data structure, called formal context. A dyadic formal context consists of two sets, one of objects and another of attributes and a binary relation between them, expressing which objects have which attributes. From such dyadic formal contexts, formal concepts can be extracted using concept forming operators, obtaining a mathematical structure called concept lattice. Thereby, the entire information contained in the formal context is preserved. The concept lattice and its graphical representation as an order diagram can then serve as the basis for communication and further data analysis. Navigation in concept lattices enables exploring, searching, recognizing, identifying, analyzing, and investigating; this exemplifies the fruitfulness of this approach for knowledge management.

In subsequent work, Lehmann and Wille extended dyadic FCA to a triadic setting (3FCA) [START_REF] Lehmann | A triadic approach to formal concept analysis[END_REF], where objects are related to attributes under certain conditions. The triadic concepts (short: triconcepts) arising from such data, can be arranged in mathematical structures called trilattices. Trilattices can be, up to some conditions, graphically represented as a triangular diagram, yet, this kind of knowledge representation is much less useful and intuitive than its dyadic counterpart, because of the difficulties of reading and navigating in such triadic diagrams. Even if the theoretical foundations of trilattices and that of 3FCA have been intensely studied, there is still a need for a valuable navigation paradigm in triadic concept sets. To overcome these difficulties, we proposed in 2015 a navigation method for triadic conceptual landscapes based on a neighborhood notion arising from dyadic concept lattices obtained by projecting along a dimension [START_REF] Rudolph | Towards a Navigation Paradigm for Triadic Concepts[END_REF]. This method enables exploration and navigation in triconcept sets by locally displaying a smaller part of the space of triconcepts, instead of displaying all of them at once. Voutsadakis [START_REF] Voutsadakis | Polyadic concept analysis[END_REF] further generalized the idea from dyadic and triadic to n-adic data sets, introducing the term Polyadic Concept Analysis. He describes concept forming operators in the n-dimensional setting as well as the basic theorem of polyadic concept analysis, a generalization of earlier results by Wille [START_REF] Wille | The basic theorem of triadic concept analysis[END_REF]. FCA was successfully used on triadic or tetradic (n = 4) datasets such as folksonomies [START_REF] Jäschke | Discovering shared conceptualizations in folksonomies[END_REF], data logs of rental services [START_REF] Cerf | Closed and noise-tolerant patterns in n-ary relations[END_REF] or data about mobile operators [START_REF] Ignatov | Triadic formal concept analysis and triclustering: searching for optimal patterns[END_REF]. However, a common problem for n-ary concept sets is their size and complexity. Even for n = 2 and for relatively small data sets, the number of formal concepts tends to be quite large (it can be of exponential size in the worst case), which makes the graphical representation of these sets in their entirety unusable for practical purposes. Several strategies have been proposed to overcome this problem. For instance, Dragos ¸et al. [START_REF] Dragos | Applying triadic FCA in studying web usage behaviors[END_REF][START_REF] Dragos | Behavioral pattern mining in web based educational systems[END_REF] are using a circular representation for triadic data while investigating users' behavioral patterns in e-learning environments. Sȃcȃrea [START_REF] Sȃcȃrea | Investigating oncological databases using conceptual landscapes[END_REF] uses a graph theoretical approach to represent triadic concept sets obtained from medical data. For n-adic concept sets with n ≥ 4, no navigation strategies have been presented yet. In 2015, we introduced membership constraints for n-adic concepts in order to narrow down the set of user-relevant n-concepts and to focus on a certain data subset one is interested to explore or start exploration from [START_REF] Rudolph | Membership constraints in formal concept analysis[END_REF]. As opposed to classical navigation tools, conceptual navigation has at its core a formal concept, i.e. a complete cluster of knowledge. We discussed the problem of satisfiability of membership constraints, determining if a formal concept exists whose object and attribute sets include certain elements and exclude others. In the current paper, we consider a general navigation paradigm for the space of polyadic concepts and implement this paradigm for the dyadic, triadic and tetradic case. For the triadic case, we try two different implementations. The first one uses the capabilities of Answer Set Programming (ASP) for computing concepts and solving the corresponding membership constraint satisfaction problem. By using this strategy, the implementation also explores optimization strategies offered by ASP. The second strategy is based on an exhaustive search of the set of polyadic concepts. The concept set is no longer computed using the ASP encoding but by one of the existing 3FCA tools. Finally, we evaluate the performance of these two strategies in terms of implementation and computation speed and we discuss the limitations of each approach and show that the ASP approach can be extended to any n-ary dataset.

Preliminaries

Formal Concept Analysis

In this section, we briefly present the necessary basic notions and definitions. For a more detailed introduction, please refer to [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF]. A dyadic context is defined to be a triple (G, M, I), where G and M are sets and I ⊆ G × M is a binary relation. The set G is called set of objects, M is the set of attributes and I is the incidence relation. Concepts are extracted herefrom using derivation operators. For A ⊆ G we define A = {m ∈ M | ∀g ∈ A, gIm}, i.e. A consists of all common attributes of all object from A. Dually, for a set B ⊆ M of attributes, we define B to be the set of objects sharing all attributes from B. The derivation operators are a Galois connection on the power sets of G and M , respectively. A formal concept is a pair (A, B) of objects and attributes, respectively, with A = B, B = A. The set of all formal concepts is ordered by the subconcept-superconcept relationship:

If (A, B), (C, D) are concepts, then (A, B) ≤ (C, D) if and only if A ⊆ C (which is equivalent to the condition D ⊆ B)
. By this, the set of all concepts becomes a complete lattice, called concept lattice. The triadic case has been studied by Lehmann and Wille ([16]). The fundamental structures used by triadic FCA are those of a triadic formal context and a triadic formal concept, also referred to as triadic concept or short triconcept. For a better understanding, we define the triadic context first, and then explain the notion of formal concept for the general case.

Definition 1. A triadic formal context K = (K 1 , K 2 , K 3 , Y
) is defined as a quadruple consisting of three sets and a ternary relation Y ⊆ K 1 × K 2 × K 3 . K 1 represents the set of objects, K 2 the set of attributes and K 3 the set of conditions. The notation for an element of the incidence relation is (g, m, b) ∈ Y or b(g, m) and it is read object g has attribute m under condition b.

Polyadic FCA is a direct generalization of the dyadic or triadic case, where n (not necessarily different) non-empty sets are related via an n-ary relation. An n-concept is a maximal cluster of n sets, with every element being interrelated with all the others.

Definition 2. Let n ≥ 2 be a natural number. An n-context is an (n + 1)-tuple K := (K 1 , K 2 , . . . , K n , Y ), where K 1 , K 2 , . . . , K n are sets and Y is an n-ary relation Y ⊆ K 1 × K 2 × • • • × K n . Definition 3. The n-concepts of an n-context (K 1 , . . . , K n , Y ) are exactly the n-tuples (A 1 , . . . , A n ) that satisfy A 1 × • • • × A n ⊆ Y
and which are maximal with respect to component-wise set inclusion. (A 1 , . . . , A n ) is called a proper n-concept if A 1 , . . . , A n are all non-empty.

Example 1. Finite dyadic contexts can be represented as cross-tables, rows being labeled with object names, columns with attribute names. In the triadic case, objects are related to attributes and conditions via a ternary relation and the corresponding triadic context can be thought of as a 3D cuboid, the ternary relation being marked by filled cells. Triadic contexts are usually unfolded into a series of dyadic "slices", like in the following example, where we consider a triadic context (K 1 , K 2 , K 3 , Y ) where the object set K 1 consists of authors of scientific papers, the attribute set K 2 contains conference names/journal names while the conditions K 3 are the publication years. For this small selection we obtain a 2 × 4 × 2 triadic context, the "slices" being labeled by condition names. The first four of these triconcepts are called proper.

If K = (K 1 , . . . , K n , Y
) is an n-context, membership constraints are indicating restricting conditions by specifying which specific elements a j ∈ K j must be included in the jth component of an n-concept, respectively which elements b j ∈ K j , j = 1, . . . , n must be excluded therefrom. We investigated the question of satisfiability of such membership constraints, i.e., to determine if there are any formal n-concepts which are satisfying the inclusion and exclusion requirements [START_REF] Rudolph | Membership constraints in formal concept analysis[END_REF].

Definition 4. An n-adic membership constraint on an n-context K = (K 1 , . . . , K n , R) is a 2n-tuple C = (K + 1 , K - 1 , . . . , K + n , K - n ) with K + i ⊆ K i called required sets and K - i ⊆ K i called forbidden sets. An n-concept (A 1 , . . . , A n ) of K is said to satisfy such a membership constraint if K + i ⊆ A i and K - i ∩ A i = ∅ hold for all i ∈ {1, . . . , n}.
We let Mod(K, C) (Mod p (K, C)) denote the set of all (proper) n-concepts of K that satisfy C.

An n-adic membership constraint C is said to be (properly) satisfiable with respect to K, if it is satisfied by one of its (proper) n-concepts, that is, if

Mod(K, C) = ∅ (Mod p (K, C) = ∅).
We have shown that the problem of deciding satisfiability of a membership constraint w.r.t. an n-context is NP-complete in general [START_REF] Rudolph | Membership constraints in formal concept analysis[END_REF]. The intractability easily carries over to proper satisfiability.

Answer Set Programming

Answer Set Programming (ASP) [START_REF] Gebser | Answer Set Solving in Practice[END_REF] is a logic programming formalism and hence uses a declarative approach to solve NP-hard problems. As opposed to the imperative approach, where the programmer tells the computer what steps to follow in order to solve a problem, declarative approaches merely describe the problem while the process of solving is delegated to generic strategies applied by highly optimized ASP engines.

Mainly, in ASP one has to express the problem in a logic programming format consisting of facts and rules, so that the solutions of the problem correspond to models of the logic program.

In what follows, we briefly introduce the syntax and semantics of normal logic programs under the stable model semantics [START_REF] Gebser | Answer Set Solving in Practice[END_REF][START_REF] Gelfond | The Stable Model Semantics For Logic Programming[END_REF]. We will present directly the syntax used in the source code in order to avoid a translation phase from one syntax to the other. Let D denote the domain, i.e. a countable set of elements, also called constants. Next, we define an atom as an expression of the type p(t 1 , . . . , t n ), where p is a predicate of arity n ≥ 0 and every t i is an element from the domain or a variable, denoted by an upper case letter. An atom is called ground if it is variable-free. The set of all ground atoms over D is denoted by G D . A (normal) rule ρ is defined as:

a 1 ← b 1 ∧ . . . ∧ b k ∧ ∼b k+1 ∧ . . . ∧ ∼b m ,
where a 1 , b 1 , . . . , b m are atoms m ≥ k ≥ 0 with the observation that the left or the right part of the rule might be missing, but not both at the same time. The left part of the rule, i.e. the part before "←" is called head, denoted H(ρ) = {a 1 }, while the right part is the body of the rule, denoted B(ρ) = {b 1 , . . . b k , ∼b k+1 , . . . , ∼b m }. As mentioned previously, a rule does not necessarily contain a non-empty head and body, namely, when the head of the rule is empty, we call the rule a constraint and, when the body of the rule is missing and a 1 is ground, it is called a fact. In case the rule is a fact, we usually omit the sign "←" and write just the atom in the head of the rule. In the definition of the rule, "∼" denotes default negation, which refers to the absence of information as opposed to classical negation "¬" which implies that the negated information is present. Intuitively, "∼a" means that a / ∈ I, while ¬a implies ¬a ∈ I, for an interpretation I, where I ⊆ G D can be understood as the set of ground atoms which are true. Furthermore, we denote In order to define when a program Π is satisfied by an interpretation I, let U Π denote the subset of constants from the domain that appear in the program Π and Gr(Π) the grounded program, i.e. the set of grounded rules obtained by applying all the possible substitutions from the variables to the constants in U Π , for all the rules ρ ∈ Π. We say that an interpretation I ⊆ G D satisfies a normal ground rule ρ ∈ Π if and only if the following implication holds:

B + (ρ) = {b 1 , . . . , b k } and B -(ρ) = {b k+1 , . . . , b m }. A rule ρ is called safe if each variable in ρ occurs in B + (ρ).
B + (ρ) ⊆ I, B -(ρ) ∩ I = ∅ ⇒ H(ρ) ⊆ I.
Then the interpretation I satisfies a non-groud rule if it satisfies all the possible groundings of the rule. Finally, the interpretation I satisfies a program Π if it satisfies all its rules, i.e. it satisfies the grounded program Gr(Π). An interpretation I ∈ G D is called an answer set or a stable model [START_REF] Gelfond | The Stable Model Semantics For Logic Programming[END_REF] of the program Π if and only if it is the ⊆-minimal model satisfying the reduct Π I defined by

Π I = {H(ρ) : -B + (ρ) | I ∩ B -(ρ), ρ ∈ Gr(Π)}.
Furthermore, we define the set of cautiously entailed ground atoms as the intersection of all answer sets. ASP solving is split in two phases. In the first phase, a grounder has to be used in order to process the logic program into a finite variable-free propositional representation of the problem encoding. In the next phase, a solver uses as input the output of the grounder and computes the solutions, i.e. the answer sets of the problem. Researchers from the University of Potsdam developed a tool suite called Potassco1 , which is a collection of answer set solving software. In our research we used the solving tools from the this collection [START_REF] Gebser | Potassco: The potsdam answer set solving collection[END_REF], since it is currently the most prominent solver leading in the latest competitions [START_REF] Calimeri | Design and results of the fifth answer set programming competition[END_REF]. In what follows, we will describe these tools in more details. The first tool, Gringo is a grounder that can be used in the first phase in order to transform the initial encoding into an equivalent variable-free, i.e. ground, program. Gringo has a simple, but comprehensive syntax that can express different types of rules (normal, choice, cardinality, etc.), constraints (integrity, cardinality, etc.), but also optimization statements. Intuitively, a constraint expresses a "forbidden" behavior of the models, i.e. if the body of the constraint is true then the model is not a stable model. The output of Gringo is in the smodels format, which is an intermediate format used for the ASP solver input. The second tool, Clasp, is a solver that uses the smodels format for the input and computes the answer sets of the program. The output of Clasp can be configured by the user and shows all or some of the following details: the number of solutions and whether the problem is satisfiable (i.e. if it has at least one stable model) or unsatisfiable, the solutions, and the detailed time of the execution. The format of the answer sets is also configurable by specifying in the encoding which predicates shall be printed in the output. Both tools, Gringo and Clasp, were combined into one tool, called Clingo, in order to avoid processing the ASP program with Gringo and then further process the output with Clasp. Avoiding the intermediate step is particularly useful if the grounded program is not of interest and the only results needed are the answer sets of the program. Furthermore, in case one needs to compute the execution time of the whole ASP solving process, the integrated tool shows the cumulative duration of the two phases, grounding and solving.

Encoding Membership Constraints in Answer Set Programming

Given that satisfiability of membership constraints can in general be NP-complete, it is nontrivial to find efficient algorithms for computing membership-constraint-satisfying concepts. We note here that the problem can be nicely expressed in answer set programming using an encoding introduced in a previous paper [START_REF] Rudolph | Membership constraints in formal concept analysis[END_REF]. We will consider the n-adic case. Given an n-adic membership constraint

C = (K + 1 , K - 1 , . . . , K + n , K - n ) on an n-context K = (K 1 , . . . , K n ,
R), we represent the specific problem by the following set of ground facts F K,C :

-set i (a) for all a ∈ K i , -rel(a 1 , . . . , a n ) for all (a 1 , . . . , a n ) ∈ R, -required i (a) for all a ∈ K + i , and -forbidden i (a) for all a ∈ K - i .
Now we let P denote the following fixed answer set program (with rules for every i ∈ {1, . . . , n}):

in i (x) ← set i (x) ∧ ∼out i (x) out i (x) ← set i (x) ∧ ∼in i (x)
← j∈{1,...,n} in j (x j ) ∧ ∼rel(x 1 , . . . , x n )

exc i (x i ) ← j∈{1,...,n}\{i} in j (x j ) ∧ ∼rel(x 1 , . . . , x n ) ← out i (x) ∧ ∼exc i (x) ← out i (x) ∧ required i (x) ← in i (x) ∧ forbidden i (x)
Intuitively, the first two lines "guess" an n-concept candidate by stipulating for each element of each K i if they are in or out. The third rule eliminates a candidate if it violates the condition A 1 × . . . × A n ⊆ R, while the fourth and fifth rule ensure the maximality condition for n-concepts. Finally, the sixth and the seventh rule eliminate n-concepts violating the given membership constraint.

There is a one-to-one correspondence between the answer sets X of F K,C ∪ P and the n-concepts of K satisfying C obtained as

({a | in 1 (a) ∈ X}, . . . , {a | in n (a) ∈ X}).
Consequently, optimized off-the-shelf ASP tools can be used for checking satisfiability but also for enumerating all satisfying n-concepts.

In this section, we describe a strategy for navigating the space of proper n-concepts of an n-context. 2 The basic idea is to use intuitive representations of "subspaces" of the overall space by specifying which elements must be included in or excluded from a certain proper n-concept component A i . Obviously, such a subspace is identified by a membership constraint C = (K + 1 , K - 1 , . . . , K + n , K - n ) specifying exactly the included and excluded elements for each component of the n-concepts. The n-concepts in the "subspace" associated with C are then the n-concepts from Mod p (K, C). Visually, C can be represented by displaying K 1 , . . . , K n as n lists and indicating for every element if it is included, excluded, or none of the two (undetermined). The user can then choose to restrict the space further by indicating for an undetermined element of some K i , if it should be included or excluded. What should, however be avoided is that by doing so, the user arrives at an empty "subspace", i.e., a membership constraint that is not satisfied by any proper n-concept (i.e., Mod p (K, C) = ∅). To this end, we will update the membership constraint directly after the user interaction in order to reflect all necessary inclusions and exclusions automatically following from the user's choice. Assume

C = (K + 1 , K - 1 , . . . , K + n , K - n )
is the membership constraint after the user interaction. The updated constraint can be described by

C = (L + 1 , L - 1 , . . . , L + n , L - n ),
where

L + i = (A1,...,An)∈Modp(K,C) A i and L - i = (A1,...,An)∈Modp(K,C) K i \ A i .
It is then clear that after such an update, for every element e of some K i which is still undetermined by C , there exist proper n-concepts (E 1 , . . . , E n ) and (F 1 , . . . , F n ) in Mod p (K, C ) with e ∈ E i but e ∈ F i . Consequently, whatever undetermined element the user chooses to include or exclude, the resulting membership constraint will be properly satisfiable. If the updated constraint C = (L + 1 , L - 1 , . . . , L + n , L - n ) determines for every element if it is included or excluded (i.e., if L + i ∪ L - i = K i holds for every i), the user's navigation has narrowed down the space to the one proper n-concept (L + 1 , . . . , L + n ). Considering the example from the previous section, assume the user has specified the inclusion of the attribute Corr in K 2 and the exclusion of the attribute ICC from K 2 , i.e., C = (∅, ∅, {Corr }, {ICC }, ∅, ∅).

The proper 3-concepts of K satisfying C are

Implementation

Following the general scheme described in the previous section, we implemented a navigation tool for the cases n ∈ {2, 3, 4}, using different strategies for n = 3. The two fundamentally different approaches differ in the method of computing the concepts (ASP vs different tool), as well as in which navigation step the concepts are computed.

In 2015, we proposed the ASP encoding for the membership constraint satisfiability problem presented in Section 3 and discussed how it could be deployed in an interactive search scenario [START_REF] Rudolph | Membership constraints in formal concept analysis[END_REF]. For the first approach presented in this paper 3 , we extended and implemented this scenario using diverse ASP optimization techniques. For grounding and solving in the ASP navigation tool, we used Clingo from the Potassco collection [START_REF] Gebser | Potassco: The potsdam answer set solving collection[END_REF] for the reasons mentioned in Section 2.2.

Recall that ASP solves a search problem by computing answer sets, which represent the models of a given answer set program (the so-called stable models) [START_REF] Gebser | Answer Set Solving in Practice[END_REF][START_REF] Gelfond | The stable model semantics for logic programming[END_REF][START_REF] Gelfond | Classical negation in logic programs and disjunctive databases[END_REF][START_REF] Marek | The Logic Programming Paradigm: A 25-Year Perspective, chap. Stable Models and an Alternative Logic Programming Paradigm[END_REF][START_REF] Niemelä | Logic programs with stable model semantics as a constraint programming paradigm[END_REF]. Our encoding, as presented in Section 3, is such that given K and C, an answer set program is created, such that there is a one-to-one correspondence between the answer sets and the n-concepts of K satisfying C. The known facts in a membership constraint satisfiability problem are the elements of the context K i , i ∈ {1, . . . , n}, the n-adic relation Y and the sets of required and forbidden elements. The answer set program can be conceived as a declarative implementation of the following "guess & check" strategy:

start from an empty constraint C decide for each element a ∈ K i , i ∈ {1, . . . , n}, if a ∈ K + i , i.e. included, or a ∈ K - i , i.e. excluded, hence reaching a membership constraint of the form

C = (K + 1 , K - 1 , . . . , K + n , K - n ) with K + i ∪ K - i = K i for every i -check if (K + 1 , . . . , K + n ) is component-wise maximal w.r.t. K + 1 ×K + 2 ×. . .×K + n ⊆ Y -check if
the required and forbidden elements are assigned correspondingly in the obtained membership constraint C, i.e. required elements belong to K + i , forbidden elements belong to K - j , for some i, j ∈ {1, . . . , n} At any step, if one of the conditions is violated, the membership constraint is eliminated from the set of models. Hence, in the end we obtain all the membership constraints that correspond to n-concepts satisfying the given restrictions. The ASP encoding can be easily extended to retrieve only the proper n-concepts satisfying C, by adding an additional check that ensures |K + i | > 0 for every i. Recall that the cautious option of ASP iteratively computes the intersection over all answer sets, in the order in which they are computed by the ASP solver. However, regardless of the ASP solver, the last outputted solution when using the cautious option is always the intersection of all answer sets of the program. Later in this section, we show how this option can be utilized to optimize the propagation phase of the navigation and, in the evaluation section, we present statistics showing that it has a great impact on the execution time of the tool we developed. The propagation algorithm tests for all elements that are still in an undetermined state, which of the possible decisions on that element (in or out) give rise to a satisfiable answer set program. In case one of the decisions generates an unsatisfiable problem, the complementary choice is automatically made. Remember that, as discussed in the previous section, when starting from a satisfiable setting, it cannot be the case that both choices generate an unsatisfiable program. The alternative to explicitly testing all the possible choices for every element in an undetermined state is to compute all the answer sets for the already added constraints and to obtain their intersection. This intersection contains the in and out choices that need to be propagated, since their complementary constraints are not included in any answer set and hence, would generate an unsatisfiable program. This approach is formally described in Algorithm 1.

Algorithm 1 propagation of user decisions optimized

function PROPAGATEOPTIMIZED(K, C) Input: n-context K, membership constraint C Output: updated membership constraint Data: membership constraint C = (K + 1 , K - 1 ,. . ., K + n , K - n )
for all i ∈ {1, . . . , n} do

L + i = (A 1 ,...,An)∈Modp(K,C) Ai L - i = (A 1 ,...,An)∈Modp(K,C) Ki \ Ai. end for C = (L + 1 , L - 1 , . . . , L + n , L - n ) return C end function
Algorithm 1 was implemented in the ASP navigation tool using the cautious option described previously. The implementation requires a single call to the ASP solver which computes the intersection of the models in the answer set. This intersection actually corresponds to the membership constraint containing all the inclusions and exclusions Fig. 2: Screenshot navigation tool: intermediate state that need to be propagated. In comparison, for the simple propagation algorithm, multiple calls to the ASP solver are necessary: For each element that is in an undetermined state, two membership constraint satisfiability problems are generated, checking whether adding the element to the required objects, respectively to the forbidden objects, generates an unsatisfiable program. The cautious-based optimized propagation algorithm proved to drastically decrease the computation time as well as the memory usage, hence improving the performance of the interactive navigation tool. The experimental results are described in more detail in the evaluation section. The optimized ASP approach was implemented and evaluated for triadic data. Furthermore, to show that it is easily extended to any n-adic context, we also implemented the dyadic and tetradic case, however, without evaluating their performance on real data sets. In fact, the only modifications that need to be made when updating the context's dimension are to add the new sets to the ASP encoding and to update the graphical interface and the context loader to the new context dimension. The second approach for the navigation is a brute force implementation 4 and uses an exhaustive search in the whole space of n-concepts. Hence, a prerequisite for this tool is to previously compute all n-concepts using an existing tool. We implemented the triadic case (n = 3) and used Trias [START_REF] Jäschke | TRIAS -an algorithm for mining iceberg tri-lattices[END_REF] to compute the triadic formal concepts. For that reason, the input for the navigation tool is adapted to Trias' output format. This approach follows the same steps described in Algorithm 1, however it uses different methods for implementing them. The first main difference lies in the method of computing the triconcepts. Instead of computing them at each step using a declarative approach, in the brute force approach, all triconcepts are computed in the preprocessing phase using an existing algorithm. In a navigation step an exhaustive search is necessary Fig. 3: Screenshot navigation tool: final state in order to select the subset of triconcepts that satisfy the constraints and compute the intersection. This subset of triconcepts is successively pruned in each navigation step until it contains a single triconcept, which represents the final state of the navigation. The graphical interface is the same for all implementations. The first column includes possible actions and information about the state of the navigation process (intermediate or final). The next columns each correspond to one dimension of the context and contain a list of the elements, each having two options next to it in or out. Figure 2 depicts a screenshot of the navigation example described in Section 4. It corresponds to the post propagation constraint C = ({Rumpe}, ∅, {Corr }, {ICC , PIMRC }, {2015}, ∅). This is an intermediate state, where required elements are marked with green, forbidden elements with red, while elements in an undetermined state are unmarked. Furthermore, required and forbidden elements have the in, respectively the out column checked. Figure 3 shows the final state of the navigation, that corresponds to the membership constraint C = ({Rumpe}, {Alouni}, {Corr , HICSS }, {ICC , PIMRC }, {2015}, {2014}).

Evaluation

In order to evaluate the implemented tools, we ran experiments on the dblp database 5 . The dblp database indexes conference and journal publications and contains information such as author, title, year, volume, and journal/conference name. In order to compare the ASP-based approach to the implemented brute force navigation, triadic datasets are needed. The triadic structure that we chose for the experiments contains the author's name, conference/journal name and year of the publication. We extracted the described triadic dataset from the dblp mysql dump and selected subsets of different dimensions. The subsets were selected by imposing restrictions on the number of publications per journal/conference, publication year and number of publications per author. For example, the dataset with 28 triples was obtained by the following steps:

eliminate all journals/conferences having less than 15000 publications eliminate all publications before the year 2014 eliminate all entries for authors that published less than 150 papers After selecting a triadic data subset, no preprocessing phase for the ASP navigation tool is needed, since its input must contain only the triadic relation. However, the brute force navigation tool requires a preprocessing phase. First the triconcept set needs to be computed with the Trias algorithm, hence the Trias tool 6 needs to be installed separately. If using the Trias algorithm without a database connection, the standard input file requires numeric data. Hence, in order to format the data according to the Trias tool input format, the elements of the dataset need to be indexed. After running Trias to obtain the triconcepts, the output needs to be formatted again before using the brute force navigation tool. Mainly the dimensions and encodings of the object, attribute and condition sets need to be added, so that the navigation tool can output the names of the elements and not their indexes. Only after these preprocessing steps can a user interactively navigate in the tricontext using the brute force navigation tool. Obviously, For measuring the runtimes of the two navigation tools, we have evaluated their performance on six different datasets containing between 28 and 8133 triples. The datasets are described in Table 1 and Table 2 (we ran both tools on the same datasets), where objects are identified with author names, attributes with conferences/journal names and conditions with the publication years. For each dataset, we chose some random navigation paths through the data, which contain between 4 and 13 navigation steps and end when a final state, i.e., a triconcept, is reached. By navigation step we understand not only the action of a user choosing an element as in or out, but also the subsequent propagation phase. In order to compare the two approaches we computed the average navigation step time for each dataset and measured the time used for loading the data. This information can be obtained from the file statistics.log which is created as an output by the navigation tools. Furthermore, for the brute force navigation we also measured the preprocessing time, i.e. the time that Trias needs to compute the triconcepts. Note that the time needed to index the dataset for the Trias input, as well as to add the encodings to the Trias output to obtain the input for the navigation tool, were excluded from this analysis, since this processing phase can be avoided by implementing different input/output formats for the Trias tool or for the brute force navigation tool. We denote First, we compared the different propagation implementations for the ASP approach: simple propagation vs. optimized propagation. The results are shown in Figure 4, where the y-axis depicts the logarithmically scaled time of execution, while the x-axis corresponds to the size of the relation. Besides the big difference in the execution time of each step, the ASP navigation tool with simple propagation uses a lot of memory. For the context with 8133 triples after a few navigation steps the execution was stopped by the system because it reached the limit memory of 4 GB RAM. In comparison, this problem does not occur for the navigation tool with optimized propagation. Next, we ran experiments on the same dataset to compare the ASP navigation tool with optimized propagation to the brute force navigation tool. Figure 5 shows the offline time of the ASP navigation tool vs. the brute force navigation tool on the logarithmically scaled y-axis in relation to the number of triples represented on the x-axis. As the chart shows, the offline time for the brute force navigation has a massive growth compared to the size of the triadic relation, while the offline time for the ASP navigation tool has a more linear growth. When comparing the average step time, the brute force navigation tool has slightly better results than the ASP navigation tool, but, as shown in Figure 6, for subsets with less than 6000 triples the average step time is under 1 second for both The experiments lead us to believe that for larger datasets, the ASP navigation tool should be the preferred one, since it has a small execution time for loading the data, as well as for each navigation step, both of which are important for an interactive tool. Furthermore, in case of dynamic datasets that change frequently, it makes sense to use the ASP navigation tool which requires no preprocessing of the data.

Tool Extension

Having practical applications of FCA as a main motivation, we developed an extended tool, FCA Tools Bundle (for more details please refer to [START_REF] Kis | FCA tools bundle -A tool that enables dyadic and triadic conceptual navigation[END_REF]), containing, besides basic FCA operations, the navigation method described in this paper as well as a different navigation method based on dyadic projections described in a previous paper [START_REF] Rudolph | Towards a Navigation Paradigm for Triadic Concepts[END_REF]. From the different implementation approaches described in Section 5 we chose The FCA Tools Bundle7 currently implements features for dyadic and triadic formal concept analysis. The dyadic part contains features for lattice building and lattice visualization, while the triadic part focuses on navigation paradigms for tricontexts.

The main purpose of the tool is to enable the user to visualize datasets of different dimensions as formal contexts and to interact with them. For this purpose, FCA Tools Bundle integrates different visualization formats offered by the formal contexts: concept list, concept lattice, local projections, particular formal concepts. The graphical interface is similar to the one in the previous ASP navigation tool. For example, the same intermediate state represented in Figure 2, can be seen in Figure 7.

In a similar manner, some of the elements are selected as being included or excluded, while the inclusions/exclusions of others ("Alouni","HICSS","2014") remains to be determined in the next steps of the navigation. This fact is highlighted using the message box which assists the user during the navigation: "A concept was not yet pin-pointed but the constraints have been updated to prevent reaching an invalid state.". In the final step of the navigation, the message shown to the user is updated accordingly: "A concept was found using the provided constraints.". This can be observed in Figure 8, which is the equivalent of Figure 3 from the previous navigation tool. Moreover, the formal concept that was reached is represented separately on its three components: extent, intent and modus. FCA Tools Bundle usefully integrates different navigation methods proposed for triadic formal contexts. Therefore, one can use the ASP-based navigation in order to pin-point a single formal concept and then continue using the navigation based on dyadic projections for further exploration of the tricontext. This can be seen in Figure 8, where before each component of the formal concept, there is a button "lock". This gives the user the possibility to project the context on that particular component and look at the corresponding dyadic concept lattice. Therefore, users can easily combine navigation methods to extensively explore a large dataset.

Conclusion

This paper presents a navigation paradigm for polyadic FCA using different implementation strategies. For higher-adic FCA, this is, to the best of our knowledge, the first navigation tool which allows to explore, search, recognize, identify, analyze, and investigate polyadic concept sets by using membership constraints, in line with the Conceptual Knowledge Processing paradigm. Experiments on 3-dimensional datasets strongly suggest that the ASP navigation approach with optimized propagation is, in general, the better choice since it has low execution times, even for larger contexts. Furthermore, in case one needs to adapt the navigation tool to an n-dimensional context for n ≥ 5, the ASP approach is easier generalized, by following the example of the already implemented cases n ∈ {2, 3, 4}, whereas for the brute force navigation approach, which was implemented only for n = 3 using Trias, one would first need to find an algorithm for computing the n-concepts. Moreover, we have presented a new tool, FCA tools Bundle, which allows users who are not familiar with FCA or ASP to analyze multidimensional datasets and browse through maximal clusters of data.

For future work, we intend to compare the ASP approach of the n-adic case with the naive approach that uses tools such as Data-Peeler [START_REF] Cerf | Closed patterns meet n-ary relations[END_REF] or Fenster [START_REF] Cerf | Closed and noise-tolerant patterns in n-ary relations[END_REF] which claim to be able to compute closed patterns for n-adic datasets. Also, some new features or new implementations for existing features will be integrated in the FCA tools Bundle.

Furthermore, are planning to further investigate exploration strategies and rule mining in polyadic datasets.

  Finally, we define a propositional normal logic program as a finite set of normal rules.

C 1 =

 1 ({Rumpe, Alouni}, {Corr}, {2014, 2015}) and C 2 = ({Rumpe}, {Corr, HICSS}, {2015}), therefore, we would obtain the updated constraint C = ({Rumpe}, ∅, {Corr }, {ICC , PIMRC }, {2015}, ∅). If the user now decided to additionally exclude 2014 from K 3 , leading to the constraint C = ({Rumpe}, ∅, {Corr }, {ICC , PIMRC }, {2015}, {2014}), the only proper 3-concept satisfying it is C 2 . Consequently, C will be updated to C = ({Rumpe}, {Alouni}, {Corr , HICSS }, {ICC , PIMRC }, {2015}, {2014}), which then represents the final state of the navigation.

Fig. 4 :

 4 Fig. 4: Average step time for ASP navigation with simple propagation vs optimized propagation

Fig. 5 :

 5 Fig. 5: Offline time for ASP vs brute force navigation tool with respect to the number of triples in the relation

Fig. 6 :

 6 Fig. 6: Average step time for ASP vs brute force navigation tool with respect to the number of triples in the relation

Fig. 7 :

 7 Fig. 7: Screenshot FCA Tools Bundle: intermediate state

Fig. 8 :

 8 Fig. 8: Screenshot FCA Tools Bundle: final state

Table 1 :

 1 ASP Navigator experiments

	number of objects	number of attributes	number of conditions	number of triples	ASP navigation data loading time (s)	ASP navigation average step time (s)
		2		15		2		28	0.015	0.1873
		14		62		5	680	0.109	0.2315
		41		67		7	2514	0.374	0.3278
		68		67		8	4478	0.546	0.5930
		83		67		9	5987	0.660	0.6350
	108		67		10	8133	1.070	1.1940
				Table 2: Brute Force Navigator experiments
	number of objects	number of attributes	number of conditions	number of triples	Trias pre-processing time (s)	brute force data loading time (s)	brute force average step time (s)
	2		15		2		28	0.27	0.016	0.0060
	14		62		5		680	1.04	0.421	0.0047
	41		67		7		2514	23.24	1.950	0.0219
	68		67		8		4478	644.758	4.384	0.0530
	83		67		9		5987 2152.839	6.992	0.1600
	108		67		10		8133	> 2h

http://potassco.sourceforge.net/

Non-proper concepts are considered out of scope for knowledge exploration, thus we exclude them from our consideration. The described navigation would, however, also work if these concepts were taken into account.

https://sourceforge.net/projects/asp-concept-navigation

https://sourceforge.net/projects/brute-force-concept-navigation

http://dblp.uni-trier.de/

https://github.com/rjoberon/trias-algorithm

https://fca-tools-bundle.com

Acknowledements

Diana Troancȃ's research on this topic was supported by a scholarship from DAAD, the German Academic Exchange Service. The authors also thank the anonymous reviewers of an earlier version of this paper. We thank Lukas Schweizer for technical advice regarding ASP. The FCA Tools Bundle was implemented by Lorand Kis.


Janusz Wojtusiak
email: jwojtusi@gmu.edu

Hua Min

Eman Elashkar
email: eelashka@gmu.edu

Hedyeh Mobahi
email: hmobahi2@gmu.edu

Guiding Supervised Learning by Bio-Ontologies in Medical Data Analysis

Keywords: Supervised Machine Learning, Biomedical Ontologies, UMLS

Ontologies are popular way of representing knowledge and semantics of data in medical and health fields. Surprisingly, few machine learning methods allow for encoding semantics of data and even fewer allow for using ontologies to guide learning process. This paper discusses the use of data semantics and ontologies in health and medical applications of supervised learning, and particularly describes how the Unified Medical Language System (UMLS) is used within AQ21 rule learning software. Presented concepts are illustrated using two applications based on distinctly different types of data and methodological issues.

Introduction

Recent advancements of Machine Learning (ML) made it applicable to wide range of problems, including those in medical, healthcare and health domains. These methods are able to make accurate predictions in uncertain environments, by finding patterns scattered over massive amounts of data. Strength of many of the newest methods comes also in the ability to combine Natural Language Processing (NLP) tools with learning from structured data. The majority of novel methods are statistical and focus on analysis of numeric data. The principles of these machine leaning methods usually rely on distributions and patterns inside the data sets only. They do not include the meanings of the data sets. Domain knowledge for such methods is limited to ad-hoc encoding of attributes in the data or prior parameters of the model being learned as in examples of deep learning of neural networks [START_REF] Gülçehre | Knowledge matters: Importance of prior information for optimization[END_REF]. Surprisingly, very few machine learning methods allow for modeling of domain knowledge in order to guide the learning process which can potentially make the learned models closer to human decision-makers.

The presented research explores the utilization of ontologies and data semantics to guide machine learning process. It provides the additional information to those distributions and patterns already inside the data sets. The motivations of this research come from the existence of rich biomedical ontologies created for the medical data integration methods, NLP algorithms and the Semantic Web [START_REF] Tresp | Towards machine learning on the semantic web[END_REF], as well as early research on human-oriented machine learning. This presence of domain knowledge provides an ideal opportunity to complement pure data for machine learning, with relationships that span over the data.

The researchers started to utilize domain knowledge to guide machine learning in some fields. For example, the frequent utilizations of the ontology exist in NLP, including ontology-based methods for indexing, extracting, and analyzing clinical notes [START_REF] Cai | Natural Language Processing Technologies in Radiology Research and Clinical Applications[END_REF][START_REF] Wu | Unified Medical Language System term occurrences in clinical notes: a large-scale corpus analysis[END_REF][START_REF] Xu | A Comprehensive Analysis of Five Million UMLS Metathesaurus Terms Using Eighteen Million MEDLINE Citations[END_REF]. In [START_REF] Kassahun | Automatic classification of epilepsy types using ontology-based and genetic-based machine learning[END_REF], the researchers classified patients with different types of epilepsy using different methodologies including ontology-based classification (OBC). The OBC achieved better results than others did.

After the brief introductions for biomedical ontologies and supervised machine learning, we will present an approach to handling semantic information and reasoning with ontologies in supervised learning.

Biomedical Ontologies

An ontology formally represents domain knowledge as a set of concepts and relationships between those concepts. The concepts in an ontology should be close to objects (physical or logical) in the real world. Relationships describe the interactions between concepts or a concept's properties. The most important relationship is the "IS-A" hierarchical relationship. It serves as the ontology's backbone and supports the property inheritance. The "IS-A" relationship connects a more specific concept (child concept) to a more general concept (a parent). Non-IS-A relationships, called associative or semantic relationships, connect concepts across the hierarchies in an ontology. Broadly speaking, ontologies include thesauri, terminologies, classifications, and coding systems. Ontologies play important roles in biomedical research through a variety of applications including data integration, knowledge management, natural language processing, and decision support [START_REF] Bodenreider | Biomedical ontologies in action: role in knowledge management, data integration and decision support[END_REF].

The most popular biomedical ontologies (Bio-Ontologies) include Systematized Nomenclature of Medicine-Clinical Terms (SNOMED CT) [START_REF] Stearns | SNOMED clinical terms: overview of the development process and project status[END_REF], International Classification of Diseases (ICD) [START_REF] Hirsch | ICD-10: History and Context[END_REF], Logical Observation Identifiers Names and Codes (LOINC) [START_REF] Huff | Development of the Logical Observation Identifier Names and Codes (LOINC) Vocabulary[END_REF], Gene Ontology (GO) [START_REF]Expansion of the Gene Ontology knowledgebase and resources[END_REF], Medical Subject Headings (MeSH) [START_REF] Coletti | Medical Subject Headings Used to Search the Biomedical Literature[END_REF], RxNorm [START_REF] Nelson | Normalized names for clinical drugs: RxNorm at 6 years[END_REF], Foundational Model of Anatomy (FMA) [START_REF] Rosse | A reference ontology for biomedical informatics: the Foundational Model of Anatomy[END_REF], and National Cancer Institute Thesaurus (NCI Thesaurus) [START_REF] Fragoso | Overview and Utilization of the NCI Thesaurus[END_REF]. Each ontology has its own purpose and scope. For example, SNOMED CT is a systematically organized computer processable ontology of medical terms. ICD defines the universe of diseases, disorders, injuries and other related health conditions. LOINC is a coding system for laboratory and clinical observations. GO provides controlled vocabularies of defined terms representing gene product properties including cellular components, molecular functions and biological processes. MeSH is designed to provide a hierarchically-organized terminology for indexing and cataloging of biomedical information such as MEDLINE/PubMed. RxNorm, published by National Library of Medicine (NLM), provides normalized names and a model for clinical drugs available in the US. FMA represents a coherent body of explicit declarative knowledge about human anatomy. Finally, NCI Thesaurus includes broad coverage related to the cancer research domain.

Therefore, there are communication barriers between various information systems or applications if the developers use different vocabularies in different systems. In order to solve these barriers, the Unified Medical Language System (UMLS) was developed by the NLM in 1986 [START_REF] Lindberg | The Unified Medical Language System (UMLS) of the National Library of Medicine[END_REF] and it is constantly being updated. The UMLS has three knowledge sources: Metathesaurus, Semantic Network, and SPECIALIST Lexicon. The UMLS (2016AB) contains more than 3.44 million concepts (Concept Unique Identifiers; CUIs), 22 million relationships among those concepts, and 13.7 million unique concept names (AUIs) from 199 source vocabularies. One important goal of the UMLS is to establish mappings between different Bio-Ontologies. A concept unique identifier (CUI) is assigned to the terms from various source ontologies that have the same meaning in the Metathesaurus. The mappings among these vocabularies allow computer systems to translate data among the various information systems. The rich relationships in the UMLS also provide a solid foundation for reasoning in the medical knowledge [START_REF] Bodenreider | Biomedical ontologies in action: role in knowledge management, data integration and decision support[END_REF]. Other UMLS applications include providing browser for its source ontologies, the Clinical Observations Recordings and Encoding (CORE) Problem List Subset [START_REF] Fung | The UMLS-CORE project: a study of the problem list terminologies used in large healthcare institutions[END_REF], NLP [START_REF] Cai | Natural Language Processing Technologies in Radiology Research and Clinical Applications[END_REF][START_REF] Wu | Unified Medical Language System term occurrences in clinical notes: a large-scale corpus analysis[END_REF][START_REF] Xu | A Comprehensive Analysis of Five Million UMLS Metathesaurus Terms Using Eighteen Million MEDLINE Citations[END_REF], and value sets for Clinical Quality Measures (CQMs) [START_REF] Bodenreider | The NLM Value Set Authority Center[END_REF].

Supervised learning

While machine learning is a broad area, the presented work is focused on supervised learning, and more specifically concept learning. The methodology described here can be applied to output concepts which are independent, ordinal or structured. One can also extend the method presented here into regression learning, as well as other forms of machine learning, i.e. unsupervised and reinforcement learning.

The problem considered here is to learn a model M: X à Y which can be viewed as a function that assigns classes from Y={y j }, j=1..k into objects from X. Learning is performed by an algorithm A given dataset D and background knowledge BG, A(D, BG) = M, where D={(x i , y i ), i=1..N}. This work focuses on the background knowledge, BG, and specifically its forms that can be retrieved from ontologies.

Many concept learning methods have been developed in the field, including symbolic methods for learning decision trees [START_REF] Quinlan | Induction of decision trees[END_REF] or rules [START_REF] Fürnkranz | Separate-and-conquer rule learning[END_REF], numeric methods for learning sets of equations such as Support Vector Machines [START_REF] Hearst | Support vector machines[END_REF], Logistic Regression [START_REF] Lemeshow | Applied Logistic Regression[END_REF], or non-Negative Matrix Factorization [START_REF] Wang | Nonnegative matrix factorization: A comprehensive review[END_REF]. Regardless of the used method, the general goal is to build models that maximize quality measure (or minimize loss function). An issue considered here is how to improve the methods when additional structure about the problem is known, i.e., in the form of hierarchical relationships between values of attributes, or non-IS-A relationships between attributes. In a sense, recent work on neural networks, related to deep learning [START_REF] Schmidhuber | Deep learning in neural networks: An overview[END_REF] can be viewed as a form of encoding of problem into structure of model. In deep learning different structures of networks are considered, which can be based on hierarchies, but typically represent components of the problem rather than semantic concepts.

Early and more recent work on learning structures [START_REF] Wang | Structure learning via parameter learning[END_REF] and use of background knowledge included advanced in Inductive Logic Programming (ILP) and hierarchical learning methods. In the ILP, the background knowledge is defined as a set of relations (predicates) that can be used in the definition of the target concept [START_REF] Kazakov | Machine Learning and Inductive Logic Programming for Multi-agent Systems[END_REF]. An ILP system derives rules based on an encoding of the known background knowledge and a set of examples represented as a logical database of facts. Another related field is the hierarchical Relational Reinforcement Learning (HRRL) [START_REF] Kaelbling | Reinforcement Learning: A Survey[END_REF][START_REF] Džeroski | Relational Reinforcement Learning[END_REF][START_REF] Tadepalli | Relational reinforcement learning: An overview[END_REF]. In those studies, hierarchies have been used to reduce the complexity of decision making and improve the actual process of learning. Both ILP and HRRL are particularly useful in bioinformatics, healthcare, and NLP.

Example Data

This paper illustrates concepts of using ontologies and semantics in machine learning on two examples of medical/health data. These are chosen because of inclusion of diverse types of data and are part of existing projects on using semantics in machine learning by the authors.

• SEER-MHOS: The example learning problem concerns the ability to automatically assess patient disabilities in performing Activities of Daily Living (ADLs). Such activities are important measures of patient independence, quality of life and need for care. However, the data about ADLs is not routinely collected along with clinical or administrative data. The purpose of this application is to automatically assess patients' functional disabilities based on general demographic information and known broad categories of diagnoses. Models are trained on SEER-MHOS (Surveillance, Epidemiology, and End Results -Medicare Health Outcomes Survey) which is a linked dataset. A subset of data with 1,849,311 unique patients, out which 102,269 patients diagnosed with cancer, have been used for this research. SEER is a cancer registry program that provides clinical, demographic and cause of death information [START_REF] Seer-Mhos | [END_REF]. MHOS data is a survey based report that contains both patient conditions and ADLs. In this research, SEER-MHOS data has been coded with UMLS CUIs and used to create models for predicting ADLs after cancer diagnosis.

• MIMIC-III: Learning from clinical data adds another level of complexity beyond standard administrative healthcare data. The MIMIC III ('Medical Information Mart for Intensive Care') is a large database that includes de-identified, comprehensive clinical data of patients admitted to critical care units at a large tertiary care hospital, Beth Israel Deaconess Medical Center in Boston, Massachusetts. The data are publicly available to researchers who satisfy certain conditions [START_REF] Goldberger | PhysioBank, PhysioToolkit, and PhysioNet: Components of a New Research Resource for Complex Physiologic Signals[END_REF]. MIMIC-III consists of over 58,000 hospital admissions for 38,645 adults and 7,875 babies. It is structured into 26 tables organized as a relational database. Data have been collected during routine hospital care between 2001 and 2012 and was downloaded from several sources including archives from critical care information systems, hospital electronic health record and Social Security Administration Death Master File [START_REF] Johnson | MIMIC-III, a freely accessible critical care database[END_REF]. In the presented work, MIMIC-III data has been mapped to UMLS ontology and used to create models for predicting 30-day post-hospitalization mortality.

AQ21, Semantics, and Ontologies

AQ21 is the latest of rule learning systems developed by Ryszard Michalski's team at George Mason University and previously at University of Illinois [START_REF] Michalski | AQVAL/1 (AQ7) User's Guide and Program Description[END_REF]. Currently AQ21 is being extended by methods that allow for reasoning with complex data, i.e., data that is mapped into ontologies, data with multiple types, and specifics of medical and health data [START_REF] Wojtusiak | Recent Advances in AQ21 Rule Learning System for Healthcare Data[END_REF]. The AQ family of rule learners follow traditional separate-and-conquer approach to learning, by generating multiple stars (all rules one positive example, the seed, that do not cover negative examples). From each star top rules are selected for further processing. This operation is repeated until all positive examples are covered in the training data. Finally, the learned rules are optimized to maximize their quality according to user-defined criteria. AQ21 software implements several additional modules for adjusting representation space by constructive induction [START_REF] Wnek | Hypothesis-driven Constructive Induction in AQ17-HCI: A Method and Experiments[END_REF][START_REF] Bloedorn | Data-Driven Constructive Induction[END_REF], testing and applying data, handling time series, generating natural language descriptions from rules, and others. The research on AQ rule learners follows the idea of natural induction [START_REF] Michalski | ATTRIBUTIONAL CALCULUS: A Logic and Representation Language for Natural Induction[END_REF] in which created models are in forms natural to people (transparent and consistent with their prior knowledge).

The general principle behind the work presented here is that a rule learning system that understands semantics as well as relationships between attributes or values, can reason better than one that is provided only data. This principle is grounded on how people reason. Instead of purely relying on data, people use their knowledge to put all data in context and reason about it. For example, knowing that Type I Diabetes and Type II Diabetes are both Diabetes, reduces complexity and allows for the learned description to be more general (handling IS-A relationships and reasoning with hierarchies is described later in this chapter). By semantics of data, we understand attribute types, meta-values, aggregated vs. individual data, and relationships between data elements.

Attribute types are used to specify which methods of reasoning, including data transformations, can be applied when learning. The basic recognized attribute types are: nominal (unordered sets of symbolic values, i.e., [treatment=radiation, surgery]), ordinal (ordered sets of symbolic values, i.e., [stage=I..III]), cyclic (ordered sets of symbolic values that form a cycle, i.e., [day=Friday..Monday]), structured (hierarchical sets of symbolic values, i.e., [treatment=surgery] with surgery having subcategories such as robotic surgery, etc.), graph (values are linked together by edges in a graph, i.e., ), set (multiple values can be selected at the same time, i.e., [diagnosis={diabetes, hypertension, obesity}]), set-defined (similar to set, but with additional structure added on top of values, i.e., diagnoses in previous example form a hierarchy), interval (numeric values with defined addition and subtraction, zero is not defined), ratio (numeric values with defined multiplication and division), cyclic-ratio (numeric values forming a cycle, i.e., [angle=276. .15]), and absolute (numeric values with only order defines and no operations permitted, i.e., social security number). These attribute types along with additional examples are explained in [START_REF] Wojtusiak | Semantic Data Types in Machine Learning from Healthcare Data[END_REF]. Attribute types are critical when attempting to generalize and reason with rules, as well as apply constructive induction methods, i.e. interval attributes should not be multiplied.

Aggregated data refer to data in which examples provided to the learning system describe a group of individual observations, rather than an individual object about which the system reasons [START_REF] Wojtusiak | Towards application of rule learning to the meta-analysis of clinical data: An example of the metabolic syndrome[END_REF]. Aggregated data are typically described using mean and standard deviation of attributes measured for a group of examples, or frequency of symbolic values. The learning problem from aggregated data is to create models for categorizing individual data when no individual training data are available, or only small portion of individual data are available with addition of aggregated data. Learning from aggregated data is particularly important in fields such as healthcare in which access to individual patient data is difficult or impossible. It is inspired by the field of metaanalysis in which aggregated data retrieved from published scientific studies can be analyzed to arrive at global conclusions supported by majority of studies.

Meta-values refer to special values present in the data, namely unknown, not applicable and irrelevant [START_REF] Michalski | Reasoning with Missing, Not-applicable and Irrelevant Meta-values in Concept Learning and Pattern Discovery[END_REF]. These meta-values correspond to potential reasons for which regular values are not present: they are not known, do not make sense, or are removed based on expert's judgment. The majority of machine learning and data mining methods ignore the fact that not all missing data are the same. Imputation methods can be meaningfully applied only to values that exist but are not known. Imputing data for notapplicable values simply does not make sense (for example replacing missing Prostatespecific Antigen (PSA) missing value for female patients in medical dataset). Similarly, imputing irrelevant values that were deliberately removed by experts makes no sense. In statistics, there is a distinction between data missing at random, missing completely at random, and missing not at random. While these classes partially correspond to semantic meaning of meta-values their interpretation is different. Meta-values represent background knowledge that is handled internally within learning systems such as AQ21.

Medical data in the electronic health record systems (EHRs) include a wide range of data from patient demographic, medical history, diagnosis, treatments, socioeconomic status, to genetic information. The medical data can be coded with concepts from one or multiple medical ontologies. Those concepts are connected by different type of relationships including most typically used IS-A relationships being part of hierarchies, or non-IS-A relationships that carry semantic meaning of the connections between concepts. The concepts and their relationships are represented in the medical ontologies in formal knowledge representation languages such as OWL and OBO. Thus, they are computationally processable by machine learning methods. In summary, semantic data description includes information about attribute types, inter-attribute relationships, value aggregation semantics, data transformations, and meta-values.

The main focus of the presented work is to use the semantics of data when applying supervised machine learning methods to construct classification models. The following sections describe how relationships can be extracted from UMLS and included as part of background knowledge used by AQ21. Generalization with hierarchies and IS-A relationships, learning with non-IS-A relationships, and finally learning hierarchical and ordinal models by AQ21 are presented.

Hierarchy Extraction from UMLS

The data pre-processing includes one major step that is a multi-step hierarchy extraction. It contains 4 steps: (1) Mapping data to the UMLS concepts (and identify their CUIs); (2) Extracting complete sub-hierarchy by following IS-A relationships using CUIs from step 1; (3) Resolving inconsistencies in the hierarchy (e.g., cycles, duplicates); and (4) Encoding extracted hierarchies in ML-software readable format (i.e., AQ21 requires a list of parent-child pairs for all relationships that form hierarchy). The detailed description is outlined below:

1. Map data to the UMLS concepts. The mapping is a challenge since the meaning of the concepts varies depending on specific sources and authors. For example, the definition of Congestive Heart Failure (CHF) from Elixhauser et al. in 1998 [START_REF] Elixhauser | Comorbidity measures for use with administrative data[END_REF] is different from UMLS. According to the definition from Elixhauser, there are 18 ICD-9 codes that are classified as CHF (see first column in Table 1). While in UMLS, to understand how CHF is defined, we need to follow hierarchy starting from the most general Congestive Heart Failure (CHF) concept, tracking down all its possible children through the hierarchy. This was done by tracking children of the concept, then children of all children, to last concept related to the main general concept, as shown in Figure 1. However, there are only 11 concepts (CUIs) that defines Congestive Heart Failure (CHF) in the UMLS system (and corresponding ICD-9 codes) as shown in second column in Table 1. In this case, CUIs resulting from tracking hierarchy of CHF concept in UMLS, were mapped again to corresponding ICD9 so we can show concepts in both Elixhauser and UMLS defined using ranges of ICD9. The seven inconsistent codes are highlighted in gray in Table 1. This is just one example of the fact that the mapping process is difficult, and currently needs to be done manually by domain experts.

2. Follow IS-A relationships in the UMLS for both parents and children until complete sub-hierarchy is extracted. The hierarchy should extend to the farthest common ancestors and descendants. In UMLS one should follow relationships corresponding to all considered source terminologies, not only one in which the original data is coded. 3. Resolve inconsistencies in the extracted hierarchies. Due to nature of UMLS and fact that it is constructed from multiple source terminologies, a number of inconsistencies may happen. For example, the extracted hierarchies often include cycles, which are not permitted in AQ21 (and make it impossible to reason with data). Figure 2 shows one example of cycles in UMLS. Cycles are resolved by breaking links that go back to concepts higher in the hierarchy, as measured by distance from the UMLS root. Other types of inconsistencies include use of duplicate concepts or depreciated concepts. Those inconsistencies should be removed from the final hierarchy.

4. Encode hierarchy in ML-software readable format, typically a list of parent-child pairs. AQ21 is a stand-alone software that reads input from text files. The files need to include all semantic information required to correctly reason with the data. Specifically, in AQ21 hierarchical relationships are part of definition of domains attributes that describe data.

Currently the steps 1-3 are completed outside of AQ21 software, but the system is being extended by the ability to link directly to UMLS. In principle, with right data preprocessing and representation transformations, it may be possible to encode semantic information in a way that most ML methods can use it.

Generalization with Hierarchies

Existing methods in AQ21 allow for using hierarchies extracted from ontologies to be used in specifying optimal generalization level of rules. The method is based on an approach first described by Kaufman and Michalski [START_REF] Kaufman | A Method for Reasoning with Structured and Continuous Attributes in the INLEN-2 Multistrategy Knowledge Discovery System[END_REF] and implemented in earlier AQ systems. The method follows IS-A relationships in the data to generalize or specialize rules in order to improve their accuracy and simplicity as defined by implemented rule quality measures.

The method can be applied to generalize beyond a single attribute in the data that implements set-valued attributes using binary indicators. This is particularly useful when analyzing coded medical data with potentially hundreds of thousands of binary attributes. For example, patient diagnoses coded using ICD-9 codes can result in the need to create close to 10,000 binary attributes. It is important to generalize ICD-9 codes in order to reduce the number of features. The generalization can be done by categorizing ICD-9 codes into Clinical Classifications Software (CCS) codes or finding a common ancestor for those codes by climbing the UMLS hierarchy. In this study, CCS was applied to generalize ICD-9 codes for the SEER-MHOS dataset. The goal was to find the predictor or set of predictors for the ADLs deficiencies.

Before analysis, the data were preprocessed as follows: First we limited our study population to those patients who completed at least one survey before their cancer diagnosis and one survey roughly one year after the diagnosis. If a patient had multiple surveys, we used the surveys closest to before and after the cancer diagnosis. These very strict criteria significantly reduced the data size and the process produced a cohort of 723 cancer patients. The set of output attributes included six ADL indicators (walking, dressing, bathing, moving in/out chair, toileting, and eating) that were extracted from the survey completed after the cancer diagnosis. Input attributes, extracted from survey completed prior to cancer diagnosis and cancer registry, were based on known ADL factors from the literature [START_REF] Amemiya | Activities of daily living and quality of life of elderly patients after elective surgery for gastric and colorectal cancers[END_REF][START_REF] Agborsangaya | Health-related quality of life and healthcare utilization in multimorbidity: results of crosssectional survey[END_REF][START_REF] Taneja | Re: impact of age and comorbidities on longterm survival of patients with high-risk prostate cancer treated with radical prostatectomy: a multi-institutional competing-risks analysis[END_REF][START_REF] Vissers | The impact of comorbidity on Health Related Quality of Life among cancer survivors: analyses of data from the PROFILES registry[END_REF]. They include patient demographic (age, race, marital stats), ADLs before cancer diagnoses, comorbidities (Diabetes, Hypertension, Arthritis, etc.), cancer characteristics (tumor size, staging, etc.), surgery and treatment indicators. The ICD-9 codes in the final dataset were mapped to the UMLS CUIs. These CUIs were used to extract the hierarchical relationships (Parents and Children) from UMLS until a common ancestor was found. The extracted hierarchies were added to the set of input variables.

AQ21 software was used to investigate the method with and without using background knowledge from UMLS. Application of the AQ21 software to SEER-MHOS data mapped to UMLS resulted in a number of models (rulesets) for predicting patients' deficiencies in performing activities of daily living. AQ21 has been executed in Approximate Theory Formation Mode (ATF), with weight w=0.3 of completeness vs. consistency gain. In the ATF mode, AQ21 produces rules that may be partially incomplete or inconsistent in order to maximize the rule quality measure. Below are two sample rules generated by AQ21 with and without using background knowledge:

The rules are similar using AQ21 with and without background knowledge. However, the quality of rule, as measured by Q(w), generated by the second method is improved. The last line in the rule set describes the numbers of positive examples (p), negative example (n) covered by the rule, and the rule quality. While the rules presented above correspond to each other, AQ21 with and without ontology are not guaranteed to create similar rules. Instead the program applies beam search to go through space of possible combinations of attributes and values to find the highest quality rules. Presence of additional ways of generalizing data available in the presence of hierarchies derived from an ontology may steer the process in different direction. Consequently, the quality of rules improves because of the ability to generalize using hierarchies.

Using non-IS-A Relationships

The current version of UMLS includes 727 types of relationships (NLM, 2016), with IS-A being just one of them. Semantics of these relationships need to be encoded in learning software, and their use and effect on reasoning process depends on specific meaning of that relationship. One simple way of encoding these relationships is that the data can then be extended by additional dimensions that correspond to presence of meaningful relationships. The following process is used to search for additional attributes to be added to problem representation space. It checks all pairs of attributes in the data and their values for existence of relationships. The following steps describe the method in terms of using UMLS, but can be easily extended to other ontologies.

1. Map the used attributes in the dataset (e.g., ICD-9) to the corresponding UMLS concept unique identifiers (CUIs). This can be done automatically if the coding system used to the attributes in data is part of UMLS' source vocabularies. Otherwise it can be done manually by experts. 2. For each pair of concepts retrieved:

2.1. Search UMLS for non-hierarchical relationship(s) between the two concepts and all their parents (generalize using IS-A to the closest parents, or those within a predefined distance) 2.2. Add all found relationships to a list of candidate attributes, and add new attributes to the data that indicates presence of the relationship. An example is shown in Figure 3. Concept X and Y exist in the dataset (see Figure 3a). The non-hierarchical relationship between X and Y is extracted from UMLS (see Figure 3b) and added as a new attribute X_Y to the dataset (see last column in Figure 3a). If the X and Y present in a patient's record, the value of the new attribute X_Y should be 1. Otherwise, it should set to 0. 2.3. Apply attribute selection methods to filter out potentially large number of new relation-based attributes from the data. Those methods select attributes for learning by computing the discriminatory power of each attribute and comparing it with the acceptance threshold. Attributes whose discriminatory power is below the threshold will not be used for learning. 3. Apply standard learning algorithms on the data. At this point the data consists of original attributes including those mapped to UMLS and additional binary attributes that represent relationships. This encoding allows the use of any learning methods applicable to the original dataset.

The above method generates potentially very large number of new attributes, significantly increasing size of representation space for learning. The data are also typically sparse because of frequency of the related concepts co-occur in the data. Thus, efficient attribute selection methods (Step 2.3) need to be applied to reduce dimensionality. Experimental results performed on MIMIC III data indicate that even for large datasets there is a need to select most relevant attributes. MIMC III contains rich clinical data including diagnoses and treatments for critical care patients. For example, some patients diagnosed with respiratory tract disease were treated by prednisone. As depicted in Figure 4, the non-IS-A relationship between "respiratory tract disease" and "prednisone" were extracted from the UMLS. Prednisone is a drug that "may treat" respiratory tract disease. Not surprisingly, the ontology includes also the reverse relationship "may be treated by". According to the Step 2.2, a new relation-based attribute "respiratory tract disease -prednisone" was added to the data. The value of the new attribute should be "1" for those patients for whom prednisone was used to treat that condition. In order to test the described method for using non-IS-A relationships, it was applied to MIMIC III dataset in order to construct models for predicting 30-day post-hospitalization mortality. The performance of the two methods, with and without using semantic (non-IS-A relationships), were compared. The primary input attributes included the diagnoses registered during hospitalization. In order to prepare data, patients with age 65 and older and their admission records were extracted from the data (25,525 hospitalization records). Diagnoses originally coded with ICD-9 codes in the data were mapped to Clinical Classifications Software (CCS) codes [48] to reduce the number of features in the data and group conditions into clinically meaningful categories.

As illustrated in Figure 3, candidate relationships were added as new attributes to the input set. CCS codes were mapped to CUIs. The IS-A relationships in UMLS is then followed to create the neighborhood space (parents and children) for each CUI. The neighborhood was used to find all non-IS-A relationships between each paired concepts. As a result, this method generated a relatively large number of new attributes (443) compared with the sample size. Hence, feature selection methods were used to decrease the size of representation space. The final dataset containing 421 features was used to learn models for predicting mortality.

Finally, standard learning algorithms such as Bayes network, naïve Bayes and logistic regression were applied to the dataset with and without using semantic. After adding semantics to the method, most models were able to capture more true positive cases and achieved higher recall which can be crucial in case of mortality prediction. For example, the naïve Bayes method without using semantics correctly classified 263 out of 555 death cases, while this method with semantics captures 10 more true positive instances.

Learning Ordinal and Hierarchical Outputs

A typical approach to building multiclass classifiers is to learn models for each class against all other classes in the data as shown in Figure 5a. While effective in many cases, this approach suffers particularly when dealing with problems with many classes or when there is inherit structure to the concepts being described. Independent binary classifiers also do not allow for weighting types of mistakes made during classification (i.e., classification error of diabetes vs. cancer is worse than one of type I and type II diabetes).

Building hierarchical classifiers has recently become popular approach in machine learning applications. Instead of building classifiers with large number of unrelated classes, information about structure of output (Figure 5c) may significantly improve performance of learning algorithms. Moreover, errors at lower levels of hierarchy are less critical than those at higher levels [START_REF] Kaufman | A Method for Reasoning with Structured and Continuous Attributes in the INLEN-2 Multistrategy Knowledge Discovery System[END_REF]. In order to build a hierarchical classifier, AQ21 starts with building models that distinguish general concepts at the top of the hierarchy (those connected to the root). Then data is limited to those within one general concept and models are built to describe sub-concepts. This operation is repeated recursively until all concepts in the hierarchy have corresponding models. AQ21 implements the method in breath-first search strategy but the order does not affect results nor computation time.

In addition to hierarchical structure within input attributes, AQ21 allows for ordered structures of output attributes. An example of ordinal (ordered) output is when one considers three or more levels of patient disability. A patient may be fully independent, partially dependent/needs some help, or fully dependent in performing a certain task. In order to learn ordinal output, the system will first build a model to distinguish between fully independent patients and those with any level of dependence, and then among the dependent patients, distinguish between those with partial and full dependence, as illustrated in Figure 5b. It is clear that the order of values in the domain of ordinal attribute affects results of learning. It can be also easily observed that the order high-to-low will result is completely different classifier than low-to-high, thus one needs to carefully design attribute domains.

Conclusions

Over the past decade significant progress has been made in the ability to use semantic information and ontologies in machine learning, despite being outside of mainstream research in the field. Research of our group at George Mason University focuses on selected aspects on using semantics (meta-values, ontologies, aggregated data) and is currently done in the context of analyzing medical, healthcare and health data.

In this study, we explored to include both hierarchical and non-hierarchical relationships in our data analysis. Both methods helped the learning process when models were created form the SEER-MHOS and MIMIC datasets. We have demonstrated that adding semantics to the ML method improved the performance of the prediction model by achieving higher recall. Capturing more true positive cases in the prediction model is important in some areas like predicting mortality or ICU admission. The results of the developed ML need to be interpreted by the domain experts. The new rules found by this study will be new hypotheses and validated by future investigations.

The presented preliminary study has a number of limitations. Several steps of data preparation need to be done manually, such as mapping data to the UMLS concepts. This causes problems related to resolving ambiguity between concepts and relationships among various ontologies, health agencies, users, and the way these ontologies are used. Different relationships between concepts may be important when a learning model preforms different tasks (i.e., differential diagnoses, comparative effectiveness of treatments, outcome prediction). Using UMLS in the ML is also challenge due to its extremely large size and high complexity. When we implemented the rich knowledge from UMLS and added them as new attributes, the dimension of the dataset increased dramatically. Thus, it brings another challenge for developing efficient attribute selection algorithms for data reduction. Currently our method increased only accuracy of models by small fraction. This may be the case that our simple strategy for hierarchical and non-hierarchical is not sophisticated enough to significantly improve the overall performance of our machine learning algorithm. Further research should be done to implement more sophisticated background knowledge and take greater advantage of the structure of the datasets. It is also important to study the effectiveness of problem of increasing dimensionality in context of size of data that is used for learning.

New wave of interest in artificial intelligence opens promise that methods using semantics and making computers "understand" objects which they reason or learn from will return to attention in machine learning. The most important work to be done in the near future concerns the ability to combine incredible advances make in statistical machine learning methods, with techniques described in this paper. High predictive accuracy of statistical models that also make sense to human experts is particularly important in domains such as healthcare where transparency is critical to users.

Fig. 1 .

 1 Fig. 1. Congestive Heart Failure concept hierarchy extracted from UMLS.

Fig. 2 .

 2 Fig. 2. Example cycle in UMLS created when combining multiple terminologies (SEER-MHOS Data).

Fig. 3 .

 3 Fig. 3. Example candidate attribute

Fig. 4 .

 4 Fig. 4. Example non-IS-A relationship within MIMIC III data extracted from UMLS.

Fig. 5 .

 5 Fig. 5. Learning unstructured and structured outputs.

Table 1 .

 1 Congestive Heart Failure (CHF) as defined by Elixhauser et al. and in the UMLS hierarchy (MIMIC III Data).

	Elixhauser	UMLS
	Definition	Definition	Description
	(ICD-9)	(CUI)
	398.91	C0155582 Congestive rheumatic heart failure
	402.01	Not CHF	Malignant hypertensive heart disease W heart failure
	402.11	Not CHF	Benign hypertensive heart disease W heart failure
	402.91	Not CHF	Unspecified hypertensive heart disease W heart fail-
			ure
	404.01	Not CHF	Hypertensive heart & chronic kidney disease, malig-
			nant, w heart failure & chronic kidney disease stage
			I -stage IV, or unspecified
	404.03	Not CHF	Hypertensive heart & chronic kidney disease, malig-
			nant, w heart failure & chronic kidney disease stage
			V -end stage renal disease
	404.11	Not CHF	Benign hypertensive heart & renal disease W CHF
	404.13	Not CHF	Benign hypertensive heart & renal disease W CHF &
			renal failure
	404.91	C3665458 Hypertensive heart & renal disease W heart failure &
			renal failure
	404.93	C0494576 Heart Failure, Systolic
	428.20	C1135191 Acute systolic heart failure
	428.21	C2732748 Chronic systolic heart failure
	428.22	C1135194 Acute on chronic systolic heart failure
	428.23	C2733492 Heart Failure, Diastolic
	428.30	C1135196 Acute diastolic heart failure
	428.31	C2732951 Chronic diastolic heart failure
	428.32	C2711480 Acute on chronic diastolic heart failure
	428.33	C2732749 Hypertensive heart & renal disease W heart failure &
			renal failure

Acknowledgments

Our current activities on using semantic in machine learning are supported part by the Jeffers Foundation and LMI Academic Partnership Program.