Zuqiang Meng
email: zqmeng@126.com

Hongli Li

A Fast Granular Method for Classifying Incomplete Inconsistent Data

Keywords: attribute-value blocks, data classification, classifier, incomplete inconsistent data, granulation model

Today extracting knowledge from "inferior quality" data that is characterized by incompleteness and inconsistency is an unavoidable and challenging topic in the field of data mining. In this paper, we propose a fast granular method to classify incomplete inconsistent data using attribute-value block technique. Firstly, a granulation model is constructed to provide a foundation for efficient computation. Secondly, an algorithm of acquiring classification rules is proposed and then an algorithm of minimizing rule sets is proposed, and with these proposed algorithms, a classification algorithm is designed to construct a rule-based classifier. Finally, we use the experiment results to illustrate the effectiveness of the proposed algorithms.

Introduction

Data classification is an important task in the field of data mining. Related classification methods and techniques are increasingly extensively studied and some of them have been successfully used to solve practical problems [START_REF] Liu | A method for multi-class sentiment classification based on an improved one-vs-one (OVO) strategy and the support vector machine (SVM) algorithm[END_REF][START_REF] Nakashima | A weighted fuzzy classifier and its application to image processing tasks[END_REF][START_REF] Stimpfling | Extensions to decision-tree based packet classification algorithms to address new classification paradigms[END_REF] . In the era of big data, the volume and variety of data is growing and growing. Big data shows features of not only large volume but also "inferior quality". "Inferior quality" of data embodies in many aspects, two of which are incompleteness and inconsistency. Data's incompleteness means that there are missing values in data while the inconsistency refers to that data contains conflicting descriptions. There are many reasons that cause the incompleteness and inconsistency, such as objective and subjective factors, noisy data, variety of data.

In fact, problems caused by the incompleteness and inconsistency are unavoidable when extracting knowledge from big data [START_REF] Conde-Clemente | Generating automatic linguistic descriptions with big data[END_REF] . The incompleteness usually enhances the degree of inconsistency. Actually the problems of incompleteness and inconsistency

This work is supported by the National Natural Science Foundation of China (No. 61363027), the Guangxi Natural Science Foundation (No. 2015GXNSFAA139292).

are interwoven and can not totally separated, which makes the problem of knowledge extraction more complicated. Therefore, it is difficult and meaningful to solve classification problems oriented to "inferior quality" data that is characterized mainly by incompleteness and inconsistency.

There are many ways to handle missing values. Stefanowski, etc. [START_REF] Stefanowski | Tsoukià s. Incomplete information tables and rough classification[END_REF] distinguished two different semantics for missing values: the ''absent value'' semantics and the ''missing value'' semantics. Grzymala-Busse, etc. [START_REF] Grzymala-Busse | A rough set approach to data with missing attribute values[END_REF] further divided such missing values into three categories according to their comparison range: ''do not care'' conditions, restricted ''do not care'' conditions, and attribute-concept values. In 2009 we utilized sorting technique to design a fast approach to compute tolerance classes [START_REF] Meng | A fast approach to attribute reduction in incomplete decision systems with tolerance relation-based rough sets[END_REF] . But this approach has the problem of data fragmentation when the degree of missing values increases to a certain level. Recently, we presented a new method called index method to quickly compute attribute-value blocks [START_REF] Meng | On efficient methods of computing attribute-value blocks in incomplete decision systems[END_REF] , which can completely eliminate data fragmentations. In this paper, we studied on a fast classification problem of incomplete inconsistent data by using and improving such index methods.

Preliminaries

Incomplete decision systems (IDSs) and attribute-value blocks

A decision system that contains missing values is called an incomplete decision system (IDS), which can be described as 4-tuple:

IDS = (U, A = C ∪ D, V =  A a a V  , {f a }) a  A ,
where U is a finite nonempty set of objects, indicating a given universe; both C and D are finite nonempty set of attributes (features), called condition attribute set and decision attribute set, respectively, where C ∩ D = ; V a is the domain of attribute a  A, and |V a | denotes the number of elements in V a , i.e., the cardinality of V a ; f a : U →V is an information function from U to V, which maps an object in U to a value in V a . Some-

times (U, A = C ∪ D, V =  A a a V  , {f a }) a  A is expressed as (U, C ∪ D) for simplicity if
V and f a are understood. Without loss of generality, we suppose D = {d} in this paper; that is, D is supposed to be composed of only one attribute. A missing value is usually denoted as "*". That is, if there exists a  C such that *  V a , then the decision system (U, C ∪ D) is an incomplete decision system.

For an incomplete decision system IDS = (U, C ∪ D), we define the concept of missing value degree (the degree of missing values) [START_REF] Meng | On efficient methods of computing attribute-value blocks in incomplete decision systems[END_REF] , denoted as MD(IDS), for IDS:

| || | values attribute missing of number the ) ( C U IDS MD  .
Obviously, missing value degrees have great effects on classification performance, but related studies on this problem are little reported.

Attribute-value blocks were presented by Grzymala-Busse to analyze incomplete data [START_REF] Meng | On efficient methods of computing attribute-value blocks in incomplete decision systems[END_REF] . Here we first introduce some concepts related to attribute-value blocks.

In an incomplete system (U, C ∪ D), for any a  C and v  V a , (a, v) is said to be an attribute-value pair, which is an atomic formula of decision logic [START_REF] Meng | An Attribute-value Block based Method of Acquiring Minimum Rule Sets: A Granulation Method to Construct Classifier[END_REF] . Let [(a, v)] denote all the objects from U which can be matched with (a, v), and [(a, v)] is the socalled attribute-value (pair) block [START_REF] Grzymala-Busse | Generalized probabilistic approximations of incomplete data[END_REF] . According to the semantics of ''do not care'' conditions, we have:

        else. , *; if *}, ) ( or ) ( | { )] , [( U v y f v y f U y v a a a
Actually, v = f a (x) for some x  U, and therefore block [(a, v)] is usually denoted by K a (x) or S a (x) in many studies, i.e., K a (x) = S a (x) = [(a, f a (x))]. For B  C, the attributevalue block with respect to B, K B (x), is defined as follows:

  B a a B a a B x K x f a x K     ) ( ))] ( , [( ) (
.

Property 1. For B, B  C, if B  B, K B (x)  K B (x).

Incomplete inconsistent decision systems (IIDSs)

In an incomplete system (U, C ∪ D), since V D does not contain missing values, D can partition U into a family of equivalence classes, which are called decision classes. In this paper, we let D x denote the decision class that contain object x, where x  U.

Definition 1. For an object x  U, let  B (x) = | ) ( | | ) ( | x K D x K B x B



, denoting the degree to which object x belongs to decision class D x with respect to B, and then  B (x) is called the consistency degree of object x with respect to B.

Obviously, 0 <  B (x) ≤ 1. If  C (x) = 1, object
x is said to be a consistent object, otherwise an inconsistent object. It is not difficult to find that an inconsistent object x means that block K C (x) intersects at least two different decision classes, i.e., K C (x)  D x .

For an incomplete decision system (U, C ∪ D), if U contains inconsistent objects, i.e., there exists y  U such that  C (y) < 1, then the decision system is said to be an incomplete inconsistent decision system (IIDS), denoted as IIDS = (U, C ∪ D). Definition 2. Let id(IIDS) denote the ratio of the number of inconsistent objects to the number of all objects in U, i.e., id(IIDS) = |{x  U |  C (x) < 1}| / |U|, and then id(IIDS) is called inconsistency degree of the decision system IIDS. Obviously, 0 ≤ id(IIDS) ≤ 1. In order to judge if an object x is consistent, we need to compute its consistency degree  B (x), which is possibly a time-consuming computational process because it involves set operations. The following property can make preparation for efficiently computing  B (x).

Property 2. For incomplete inconsistent decision system (U, C ∪ D) and any x 

U, K B (x) ∩ D x = {y  U | y  K B (x) and f d (y) = f d (x)}, and therefore  B (x) = | ) ( | | )} ( ) ( ) ( | { | x K x f y f x K y U y B d d B    
, where B  C and D = {d}.

A granulation model based on IIDSs

In order to compute K B (x), we generally need to traverse all objects in U, and therefore it takes the computation time of O(|U| 2 |B|) to compute K B (x) for all x  U, which is a time-consuming computation process. However, we notice that when considering only one attribute, we can derive some useful properties to accelerate the computation process.

(v) = {y  U - * a U | f a (y) = v}. It is not difficult to find that  a ∪{ * a U } is a coverage of U; each element in  a ∪{ * a U } is a subset of U,
K a (x) =       else U x f if U x a a a * ) ( ] [ *  where [x] a   a .
Property 3 provides a method for us to use  a and * a U to compute K a (x). We notice that |V a | almost does not increase with |U|, with which we can design an efficient algorithm to compute  a and * a U for all a  C. The algorithm is described as follows. In fact, Algorithm1 is to granulate each "column" for an IIDS and therefore to con- With the granulation model, we can compute any block K B (x) by using formula

Algorithm 1: compute  a and * a U for all a  C Input: (U, C ∪ D), where U = {x 1 , x 2 ,..., x n } Output:  a and * a U for all a  C Begin (1) For each a  C do (2) { (3) Let * a U =  and  a = ; (4) For i = 1 to n do // n = |U| (5) { (6) If f a (x i ) = * then {let * a U = * a U ∪{x i }; continue;} //Suppose  a = { a (v 1 ),…, a (v t )} at this moment, where t = | a | ≤ |V a | (7) Let flag = 0; (8) For j = 1 to t do (9) If f a (x i ) = v j then {  a (v j ) =  a (v j )∪{x i }; let flag = 1; break;} (10) If flag = 0 then { let  a (v t+1 ) = {x i };  a =  a ∪{ a (v
K B (x) =  B a a x K  ) ( .
In order to quickly compute K B (x), we should know "where K a (x) is". So we construct an index structure to store the addresses of K a (x) for all aC and xU.

A granulation-model-based method for constructing classifier 4.1 An attribute-value block based method of acquiring classification rules

A classification rule can viewed as an implication relation between different granular worlds, and each object x can derive a classification rule, which is a "bridge" between such two worlds. Firstly, let's consider the following inclusion relation:

K B (x)  D x . K B (x)
and D x has their own descriptions, which are formulae of decision logic [START_REF] Meng | An Attribute-value Block based Method of Acquiring Minimum Rule Sets: A Granulation Method to Construct Classifier[END_REF] . Suppose their descriptions are  and , respectively. Then, object x can derive rule  → .

According to Property 1, when removing attribute from B, K B (x) would enlarge, and therefore the generalization ability of rule  →  would be strengthened. But its consistency degree  B (x) may decrease and then increase its uncertainty. Therefore the operation of removing attributes from B must be done under a certain limited condition. Now we give the concept of object reduction, which is used to acquire classification rules. C (x). Actually, it is time-consuming to find a reduce for an object, because it needs take too much time to search each subset of B so as to satisfy condition (b). A usual method is to select some attribute from C to constitute B such that  B (x) ≥  C (x). Such a method is known as feature selection, with which we can easily obtain corresponding classification rule. In the following, we give an algorithm to perform feature selection for all objects x  U and derive corresponding classification rules.

) ( i B x j  can be computed in the complexity of ) ( | | | ) ( | 1 j m j i B B x K O j   . Therefore, the complexity of Algorithm 3 is O( | | | ) ( | 1 1 j n i m j i B B x K j    
). Suppose t is the average size of blocks ) (

} { i a B x K j 
for all a j  C and x i  U and h is the average length of B j , then

O( | | | ) ( | 1 1 j n i m j i B B x K j     ) = O(|U||C|• t• h). Generally, t << |U| and h << |C|, so O(|U||C|• t• h) << O(|U| 2 |C| 2 ).
It should be pointed that Algorithm 3 can not guarantee each generated attribute subset is a reduct, but it does remove some redundant attributes from C and therefore can finish the task of feature selection.

Rule set minimum

Since each rule in S is induced by an object in U, these rules and objects are one to one correspondence. Usually, we let r i denote the rule that is induced by object x i , i.e., r i corresponds to x i . We notice that |S| = |U| and there are many redundant rules in it. Therefore we need to further remove those redundant rules, and this process is so-called rule set minimum. For two rules r x :  x →  x and r y :  y →  y , if coverage(r x )  coverage(r y ), then rule r x is redundant and should be removed. Based on this consideration, we design the following algorithm to minimize the rule set S. End. In Algorithm 4, the key operation is to compute coverage(r i-1 ). Suppose B i-1 is a set of all attributes which are contained in rule r i-1 , and then computing coverage(r i-1 ) is equivalent to computing block

) ( 1 1   i B x K i , whose complexity is O(| ) ( 1 1   i B x K i ||B i-1 |) by using [, ]. Suppose the average size of blocks ) ( 1 1   i B x K i is p and the average length of B i-1 is o, then the complexity is O(| ) ( 1 1 x K B ||B 1 |+| ) ( 2 2 x K B ||B 2 | + … + | ) ( n B x K n ||B n |) = O(|U|• p• o). Generally, p << |U| and o << |C|. Therefore O(|U|• p• o) << O(|U| 2 |C|).

A classification algorithm for constructing rule-based classifier

Using the above four provided algorithms, we here give a complete algorithm to acquire a rule set, which is used as a classifier to classify incomplete inconsistent data. The complete algorithm is described as follows.

Experimental analysis

In order to verify the effectiveness of the proposed methods, we conduct several experiments using UCI data sets (http://archive.ics.uci.edu/ml/datasets.html). These experiments ran on a PC equipped with a Windows 7, Intel(R) Xeon(R), CPU E5-1620v3,and 8GB memory. The data sets are outlined in Table 1, where |U|, |C| and |Vd| stand for the numbers of samples, condition attributes, and decision classes, respectively. Form Fig. 1 we can find that the running times of Algorithm 5′ increase much more rapidly than that of Algorithm 5. Therefore, the constructed granulation model can greatly improve computational efficiency for Algorithm 5.

Algorithm 5 consists of Algorithms 1, 2, 3 and 4. We count the time for each algorithm when they are executed on Mushroom and Nursery, and the results are shown in Table 2.

It can be seen from Table 2 that, comparing with Algorithms 3 and 4, it only takes a little time for Algorithms 1 and 2 to construct granulation model. This means that constructing granulation model cost very little but it forms the foundation for fast feature selection and building classifiers. Additionally, Table 2 also shows that Algorithm 3 is the most time-consuming algorithm. To verify the classification performances of Algorithm 5, we utilize Voting-records, Tic-Tac-Toe, and Nursery to test Algorithm 5 using 10-fold cross-validation. The results are shown in Table 3. From Table 3, we can find that Algorithm 5 can have relatively high precision and recall on these data sets. This shows that the proposed algorithm has better application values. Additionally, Table 3 also shows that Algorithm 5 is suitable not only for incomplete inconsistent data but also for complete consistent data. Of course, it has better classification performances on complete consistent data than on incomplete inconsistent data.

Conclusion

Extracting rules from data sets and then using a rule set as a classifier to classify data is one of our purposes recent years. In this paper, oriented to incomplete inconsistent data, we first used attribute-value block technique to construct a granulation model, which actually consists of a block-based model and a index matrix; secondly, based on the constructed granulation model, an algorithm of acquiring classification rules is presented and then an algorithm of minimizing rule sets is proposed; with the proposed algorithms, we designed a classification algorithm for constructing a rule-based classifier; finally, we conducted some experiments to verify the effectiveness of the proposed algorithm. The experiment results are consistent with our theoretical analysis. Therefore, the work in this paper has a certain theoretical value and application value, and provides a new idea to classify incomplete inconsistent data.

Definition 3 .

 3 In an IIDS (U, C ∪ D), for a given attribute a  C, let * a U denote the set of all objects that f a (x) = *, i.e., * a U = {x  U | f a (x) = *}; attribute a can partition U -* a U into a family of equivalence classes, which are pairwise disjoint, and let [x] a de- note an equivalence class containing x, i.e., [x] a = {y  U -* a U | f a (y) = f a (x)}, where x  U, and let  a denote such a family, i.e.,  a= {[x] a | x  U -* a U }.Each element in  a is an equivalence class. Those objects are drawn together in an equivalence class due to that they have the same attribute value on corresponding attribute. Sometimes, in order to emphasize the attribute value, we let  a (v) denote an equivalence class in  a where all objects have attribute value v, i.e.,  a

  and they are also pairwise disjoint. Property 3. Given  a and * a U , for any B  C and x  U, we have

  struct a granulation model for the IIDS. Let * a  =  a ∪{ * a U }, and such a granulation model is denoted as  = (U, { * a  }aC, D) in this paper.

U ( 8 )

 8 Such an index structure is expressed as a matrix  = U×C = [m(x,a)]xU, aC, where m(x, a) is the index or address of  a (v) and v = f a (x). The algorithm of constructing matrix  is described as follows. Algorithm 2: construct matrix  for granulation model  Input:  = (U, { * a  } aC , D) Output:  = U×C = [m(x,a)] xU, aC , Begin (1) For each aC do (2) { (3) For each  * a If f a (x) = * then let m(x,a) = null;// in this case,  = * a Else let m(x,a) = loc( a (v)); // the index or address of  a (v) is to traverse all objects in * a  for all aC. We notice that ∪ * a  = U and the elements (subset) in * a  are pairwise disjoint, therefore the complexity of this algorithm is exactly equal to O(|U||C|), which is linear complexity. Both granulation model  and index matrix  are denoted as ordered pair [, ]. If there is no confusion, [, ] is also called a granulation model. The purpose of constructing [, ] is to provide a way to quickly compute block K B (x) for any xU, with complexity of about O(|K B (x)||B|).

Definition 4 .

 4 In an IIDS = (U, C ∪ D), for any object x  U, B  C is said to be a reduct of object x, if the following conditions can be satisfied: (a)  B (x) ≥  C (x), and (b) for any B  B,  B (x) < 

Algorithm 3 :( 6 )( 7 )

 367 construct a classification rule set Input: [, ] and (U, C ∪ D) // suppose U = {x 1 , x 2 , …, x n } and C = {a 1 , a 2 , …, a m } Output: S // a rule classification set Begin (1) Let S = ; (2) For i = 1 to n do //n = |U| (3) { (4) Let B = C; (5) For j = 1 to m do //m = Use B to construct  → ; Let S = S∪{ → }; step (5) is to remove redundant attributes in C, which is actually to perform feature selection. Let B j = B-{a j }. According to Property 2, with [, ],

Definition 5 .

 5 For rule r:  → , let coverage(r) denote all objects which can match rule r, i.e., coverage(r) = {xU | x|= r}.

Algorithm 4 : 1 )

 41 minimize a rule set Input: [, ] and S // S is a rule set which is generated by Algorithm 3 Output: MS // MS is a minimized rule set Begin (Compute |coverage(r)| for all r  S; (2) Sort all rules from S in a descending order by |coverage(r)| and suppose S = {r 1 , r 2 , …, r n } after sorting; (3) Let MS = {r 1 }; (4) For i = 2 to n do //n = |U| (5) { (6) If x i  coverage(r i-1 ) then let MS = MS∪{r i }; // r i is induced by x i (7) } (8) Return MS;

Algorithm 5 :( 4 )

 54 construct a rule-based classifier Input: (U, C ∪ D) Output: MS // MS is a rule-based classifier Begin (1) Use Algorithms 1 and 2 to construct granulation model [, ]; (2) Use Algorithm 3 to construct rule set S by using [, ]; (3) Use Algorithm 4 to minimize rule set S to be MS by using [, ] and S; Return MS; End. As analyzed above, the complexities of Algorithms 1 and 2 are all O(|C||U|), and those of Algorithms 3 and 4 are O(|U||C|• t• h) and O(|U|• p• o), respectively, which are much less than O(|U| 2 |C| 2 ) and O(|U| 2 |C|), respectively. Therefore, it can be seen that the time-consuming step is step (3), and then the complexity of Algorithm 5 is O(|U||C|• t• h), which is much less than O(|U| 2 |C| 2 ).

Fig. 1

 1 Running times of Algorithm 5 and Algorithm 5′ for Mushroom and Nursery

  we can find that its time complexity is O(|C||U|t) ≤ O(|C||U||V a |). As mentioned above, |V a | almost does not increase with |U|, so |V a | can be regard as a constant generally. Therefore, the time complexity of this algorithm almost approaches linear complexity O(|C||U|).

	t+1 )} };
	(11) }
	(12) }
	(13) Return  a and * a U ;
	End.
	From Algorithm1,

Table 1 .

 1 Description of the four data sets.For there exist missing values in incomplete decision system and the relation between objects are tolerance relation, instead of equivalence relation, we can not use sorting technique to accelerate the process of computing blocks and therefore need to compare x with all other objects in U when computing block K B (x), where x  U. Replace the method of computing attribute-value blocks in Algorithm 5, which is based on the granulation model, with such a method of computing blocks and keep other parts uncharged. Thus we would obtain another algorithm, denoted as Algorithm 5′. To compare the running times for a varying number of data records, we execute Algorithm 5 and Algorithm 5′ on two data sets, Mushroom and Nursery, for four times, with randomly extracting different objects at each time, and the results are shown in Fig.1.

	No. Data sets	|U|	|C|	|Vd|	MD(IIDS)	id(IIDS)
	1	Voting-records	435	17	2	0.0563	0.6736
	2	Tic-Tac-Toe	958	9	2	0	0
	3	Mushroom	8124	22	2	0.0139	0
	4	Nursery	12960	8	5	0	0

Table 2 .

 2 Running times of Algorithms 1-4 for Mushroom and Nursery

	Data sets and		Size of data set
	the used algorithms	1000	3000	5000	7000
	Mushro om	Algo. 1+ Algo. 2 Algo. 3 Algo. 4	0.062 20.524 1.602	0.109 293.039 49.749	0.548 1148.922 233.802	0.710 2748.864 545.356
		Algo. 1+ Algo. 2	0.042	0.058	0.164	0.358
	Nursery	Algo. 3	1.955	28.818	119.987	278.489
		Algo. 4	1.382	53.047	287.059	771.875

Table 3 .

 3 Precision and recall of Algorithm 5

		6 x 10 4									6000
		5									5000
	Running time (Sec.)	3 4			Algorithm 5 Algorithm 5′					Running time (Sec.)	4000 3000			Algorithm 5 Algorithm 5′
		2									2000
		1									1000
		1000 0	1500	2000	2500	3000	3500	4000	4500	5000	1000 0	2000	3000	4000	5000	6000	7000
					Size of data set								Size of data set


Jorge Martinez-Gil
email: jorge.martinez-gil@scch.at

Automated Knowledge Base Management: A Survey

Keywords: Information Systems, Knowledge Management, Knowledge-based Technology Knowledge Exploitation Knowledge Maintenance Knowledge Acquisition Knowledge Reasoning Knowledge Meta-Modeling Knowledge Representation Knowledge Retrieval Knowledge Integration Knowledge Storage and Manipulation Knowledge Sharing Knowledge Validation

A fundamental challenge in the intersection of Artificial Intelligence and Databases consists of developing methods to automatically manage Knowledge Bases which can serve as a knowledge source for computer systems trying to replicate the decision-making ability of human experts. Despite of most of tasks involved in the building, exploitation and maintenance of KBs are far from being trivial, significant progress has been made during the last years. However, there are still a number of challenges that remain open. In fact, there are some issues to be addressed in order to empirically prove the technology for systems of this kind to be mature and reliable.

Introduction

Knowledge may be a critical and strategic asset and the key to competitiveness and success in highly dynamic environments, as it facilitates capacities essential for solving problems. For instance, expert systems, i.e. systems exploiting knowledge for automation of complex or tedious tasks, have been proven to be very successful when analyzing a set of one or more complex and interacting goals in order to determine a set of actions to achieve those goals, and provide a detailed temporal ordering of those actions, taking into account personnel, materiel, and other constraints [START_REF] Chen | Intelligent scheduling algorithm and application in modernizing manufacturing services[END_REF]. However, the ever increasing demand of more intelligent systems makes knowledge has to be captured, processed, reused, and communicated in order to complete even more difficult tasks. Nevertheless, achieving these new goals has proven to be a formidable challenge since knowledge itself is difficult to 1 explicate and capture. Moreover, these tasks become even more difficult in fields where data and models are found in a large variety of formats and scales or in systems in which adding new knowledge at a later point is not an easy task.

But maybe the major bottleneck that is making very difficult the proliferation of expert systems is that knowledge is currently often stored and managed using Knowledge Bases (KBs) that have been manually built [START_REF] De Bruijn | A semantical framework for hybrid knowledge bases[END_REF]. In this context, KBs are the organized collections of structured and unstructured information used by expert systems. This means that developing a system of this kind is very expensive in terms of cost and time. Therefore, most current expert systems are small and have been designed for very specific environments. Within this overview, we aim to focus on the current state-of-the-art, problems that remain open and future research challenges for automatic building, exploiting and maintaining KBs so that more sophisticated expert systems can be automatically developed and practically used.

The rest of this work is structured as follows: Section 2 presents the state-of-the-art concerning automated knowledge-base management. Section 3 identifies the problems that remain open. Section 4 propose those challenges that should be addressed and explain how their solution can help in the advancement of this field. Finally, we remark the conclusions.

State-of-the-art

Although the challenge for dealing with knowledge is an old problem, it is perhaps more relevant today than ever before. The reason is that the joint history of Artificial Intelligence and Databases shows that knowledge is critical for the good performance of intelligent systems. In many cases, better knowledge can be more important for solving a task than better algorithms [START_REF] Rudas | Information aggregation in intelligent systems: An application oriented approach[END_REF].

It is widely accepted that the complete life cycle for building systems of this kind can be represented as a three-stage process: creation, exploitation and maintenance [START_REF] Felfernig | Intelligent engineering techniques for knowledge bases[END_REF]. These stages in turn are divided into other disciplines. In Table 1 we can see a summary of the major disciplines in which the complete cycle of knowledge (a.k.a. Knowledge Management) is divided 1 .

Table 1: Summary of concepts in the Knowledge Management field

Concerning the automatic creation of KBs (a.k.a. knowledge learning, knowledge extraction or knowledge generation), there are three major steps that should be fulfilled: automatic acquisition of the knowledge, appropriate representation of that knowledge, and storage and manipulation of the knowledge into the KB. These major steps are summarized below:

• The process of automatic knowledge acquisition starts by extracting concepts and relations among the concepts from texts or document libraries using some kind of methods for terminology extraction [START_REF] Barker | A knowledge acquisition tool for course of action analysis[END_REF]. Then, concrete instances for these concepts should be also extracted [START_REF] Zhao | Instance-based ontological knowledge acquisition[END_REF]. This usually involves the use of natural language processing techniques [START_REF] Kumar | Extracting large-scale knowledge bases from the web[END_REF]. Then statistical or symbolic techniques are applied to extract relations between the terms and concepts [START_REF] Gomez | Semantic interpretation and knowledge extraction[END_REF]. The intentional aspects of domain are formalized by means of a schema or ontology. Meanwhile, the extensional part is based on instances of concepts and relations on the basis of the given schema or ontology.

• Knowledge representation phase consists of providing a formal specification of a knowledge domain using some kind of logical notation to represent the concepts, properties for these concepts, relations among these concepts, and the underlying rules of that domain [START_REF] Balzer | Automated enhancement of knowledge representations[END_REF]. The conditions and constraints of knowledge formation and organization have to be formally specified [START_REF] Arevalillo-Herráez | Domain-specific knowledge representation and inference engine for an intelligent tutoring system[END_REF]. A notation of this kind follows a logical specification using expressions and symbolical structures, such as taxonomies, classes, and axioms [START_REF] Wang | Knowledge representation and reasoning for qualitative spatial change[END_REF].

• Another important aspect consists of storing and manipulating large KBs. This means the design of a physical and logical support, on which applications and users can rely in order to store and share the knowledge [START_REF] Balch | Collection, storage and application of human knowledge in expert system development[END_REF]. This involves using standard ways to communicate knowledge units and retrieve them [START_REF] Filali | A survey of structured p2p systems for rdf data storage and retrieval[END_REF]. Metadata and annotations should be properly taken into account. Ignoring the inherent inferential capability given by KBs each KB is also a database in the sense that there is a schema, i.e. the concepts and roles, and a set of instances. Therefore, adopting database technology as key method to address this issue is an idea adopted by most of the solutions.

Concerning the automatic exploitation of KBs (a.k.a. knowledge exploitation or knowledge application) can be divided in two subgroups: knowledge utilization and knowledge transfer. At the same time, the utilization of knowledge can be used for knowledge reasoning or for knowledge retrieval (in the way the Question and Answering (Q & A) systems work [START_REF] Yen | A support vector machine-based context-ranking model for question answering[END_REF]). Meanwhile, the purpose of knowledge sharing (a.k.a. knowledge exchange) is the process through which explicit or tacit knowledge is communicated to others.

• Knowledge reasoning consists of inferring logical consequences from a set of asserted facts or axioms [START_REF] Levesque | A completeness result for reasoning with incomplete first-order knowledge bases[END_REF]. The notion of a reasoner generalizes that of an inference engine, by providing a richer set of mechanisms to work with [START_REF] Zhang | An argumentation framework for description logic ontology reasoning and management[END_REF]. Formal specification is required in order to be able to process ontologies and reasoning on ontologies automatically. By reasoning, it is possible to derive facts that are not expressed in the KB explicitly. Some of the facts that can be automatically derived could be:

-Consistency of ABox with respect to TBox, determine whether individuals in ABox do not violate descriptions and axioms described by TBox -Satisfiability of a concept, determine if a description of the concept is not contradictory -Subsumption of concepts, determine whether concept A subsumes concept B -Retrieval of individuals, find all individuals that are instances of a concept -Realization of an individual, find all concepts which the individual belongs to, especially the most specific ones

• Knowledge retrieval aims to help users or software applications to find knowledge that they need from a KB through querying, browsing, navigating and/or exploring [START_REF] Nevo | The knowledge demands of expertise seekers in two different contexts: Knowledge allocation versus knowledge retrieval[END_REF]. The goal is to return information in a structured form, consistent with human cognitive processes as opposed to plain lists of items [START_REF] Shekarpour | Dc proposal: Automatically transforming keyword queries to sparql on large-scale knowledge bases[END_REF]. It is important to remark that traditional information retrieval organize information by indexing. However, knowledge retrieval aims ti organize information by indicating connections between different elements [START_REF] Sharma | Automatic extraction of efficient axiom sets from large knowledge bases[END_REF].

• Knowledge sharing consists of exchanging knowledge units between entities so that each entity gets access to more than the knowledge it has been able to build up [START_REF] Lin | The effect of knowledge sharing model[END_REF]. Obviously, each entity is then more prepared to make the correct choices in their field. In this way, unprecedented situations can be resolved satisfactorily. However, knowledge is currently exchanged inefficiently. This means that exchange mechanisms are restricted to very specific domains. This fact reduces knowledge propagation in space and time. To address this problem, the Knowledge Interchange Format (KIF) was designed [START_REF] Ginsberg | Knowledge interchange format: the kif of death[END_REF]. KIF is a language designed to be used for exchange of knowledge between different expert systems by representing arbitrary knowledge units using the first order predicate logic.

Concerning the automatic maintenance of KBs (a.k.a. knowledge maintenance or knowledge retention), there are three important phases: knowledge meta-modeling, i.e. modeling knowledge about the KB, knowledge integration which consists on merging past and new knowledge, and knowledge validation to assure the correctness of the new knowledge added to the KB.

• Knowledge meta-modeling can be considered as a process for adding explicit descriptions (constructs and rules) of how a domain-specific KB is built [START_REF] Lahoud | A metamodeling and transformation approach for knowledge extraction[END_REF]. In particular, this comprises a formalized specification of the domain-specific notations, a centralized repository about data such as meaning, relationships to other data, origin, usage, and format. This repository is mainly accessed by the various software modules of the KB itself, such as query optimizer, transaction processor or report generators.

• Knowledge integration is considered to be the process of incorporating new information into a body of existing knowledge with an interdisciplinary approach [START_REF] Hung | An empirical study on knowledge integration, technology innovation and experimental practice[END_REF]. A possible technique which can be used is semantic matching [START_REF] Martínez-Gil | Reverse ontology matching[END_REF]. This process involves determining how the new information and the existing knowledge interact, how existing knowledge should be modified to ac-commodate the new information, and how the new information should be modified in light of the existing knowledge [START_REF] Martínez-Gil | Maf: An ontology matching framework[END_REF]. These techniques can be used for going beyond the literal lexical match of words and operate at the conceptual level when comparing specific labels for concepts (e.g., Finance) also yields matches on related terms (e.g., Economics, Economic Affairs, Financial Affairs, etc.). As another example, in the healthcare field, an expert on the treatment of cancer could also be considered as an expert on oncology, lymphoma or tumor treatment, etc.

• Knowledge validation is a critical process in the maintenance of the KBs. Validation consists of ensuring that something is correct or conforms to a certain standard. A knowledge engineer is required to carry out data collection and data entry, but they must use validation in order to ensure that the data they collect, and then enter into their systems, fall within the accepted boundaries of the application collecting the data [START_REF] Ardimento | Empirical validation of knowledge packages as facilitators for knowledge transfer[END_REF]. Therefore, the ultimate goal of this process is to make the KB satisfy all test cases given by human experts [START_REF] Dinh | On automatic knowledge validation for bayesian knowledge bases[END_REF]. This is further complicated by factors such as temporal validity, uncertainty and incompleteness. Most of current expert systems incorporate simple validation procedures within the program code. After the expert system is constructed, it is usually maintained by a domain expert.

Concerning explanation delivery, the purpose is that expert systems may be able to give the user clear explanations of what it is doing and what it has deduced. The most sophisticated expert systems are able to detect contradictions [START_REF] Arman | Fault detection in dynamic rule bases using spanning trees and disjoint sets[END_REF] in user information or in the knowledge and can explain them clearly, revealing at the same time the expert's knowledge and way of thinking, what makes the process much more interpretable.

Open problems

From the state-of-the-art, we can deduce that a lot of successful work have been done in the field of automated knowledge-base management during the last years. However, despite of these great advancements, there are still some problems that remain open. These problems should be addressed to support a more effective and efficient knowledge-base management. Therefore, the gist of these problems is to support the complete life cycle for large KBs so that computer systems can exploit them to reflect the way human experts take decisions in their domains of expertise. These tasks are often pervasive because large KBs must be developed incrementally, this means that segments of knowledge are added separately to a growing body of knowledge [START_REF] Bareiss | Supporting start-to-finish development of knowledge bases[END_REF]. Satisfactory results in this field can have a great impact in the advancement of many important and heterogeneous disciplines and fields of application. However, there are a number of challenging questions that should be successfully addressed in advance. These problems which are summarized as follows:

• The first problem concerns the automatic generation of large KBs. Every expert system has a major flaw: knowledge collection and its interpretation into rules is quite expensive in terms of effort and time [START_REF] Cimiano | Comparing conceptual, divise and agglomerative clustering for learning taxonomies from text[END_REF]. Most expert systems have no automated methods to perform this task.

Instead it is necessary to work manually, increasing the likelihood of errors and the costs in terms of money and time. In order to develop new methods for automatic knowledge learning, it is important to have a strong methodology for their evaluation and comparison. This problem is even more critical in environments working with large KBs, as it is not viable to manually evaluate the inclusion of new knowledge.

• The second problem concerns the efficiency of methods for exploiting KBs. These methods include: knowledge reasoning, knowledge sharing and knowledge retrieval (e.g. Question & Answering tools [START_REF] Zhou | Improving question retrieval in community question answering using world knowledge[END_REF]). Beside quality, the efficiency of this kind of methods is of prime importance in dynamic applications, especially, when it is not possible to wait too long for the system to respond or when memory is limited. Current expert systems are mostly design-time tools which are usually not optimized, this means that many useful systems cannot be practically used mainly due to the lack of scalability.

• The third problem concerns automatic selection, combination and/or tuning of methods for KB maintenance. These methods include knowledge integration, meta-modeling or new knowledge validation. For example, the vital task of knowledge integration (inclusion of external knowledge in the KBs) requires complex methods for identifying semantic correspondences in order to proceed with the merging of past and new knowledge [START_REF] Kenney | Knowledge integration in organizations: an empirical assessment[END_REF]. For the detection of semantic correspondences, it is necessary to perform combination and self-tuning of algorithms that identify those semantic correspondences at run time [START_REF] Martínez-Gil | Evaluation of two heuristic approaches to solve the ontology meta-matching problem[END_REF]. This means that efficiency of the configuration of different search strategies becomes critical. As the number of available methods for KB maintenance as well the knowledge stored in the KB increases, the problem of their selection will become even more critical.

• The fourth problem concerns explanation delivery in order to improve the expert systems, thereby providing feedback to the system, users need to understand them. It is often not sufficient that a computational algorithm performs a task for users to understand it immediately. In order for expert systems to gain a wider acceptance and to be trusted by users, it will be necessary that they provide explanations of their results to users or to other software programs that exploit them. This information should be delivered in a clear and concise way so that it cannot be any place for misunderstanding.

Future challenges

In view of the state of the art and the open problems that need to be investigated, it is possible to identify four major future research challenges that should be addressed:

4.1 Challenge 1: methodology for the comparison and evaluation of KBs which have been automatically built.

We know that evaluation of KBs refers to the correct building of the content of a KB, that is, ensuring that its definitions correctly implement requirements or perform correctly in the real world. The goal is to prove compliance of the world model (if it exists and is known) with the world modeled formally.

From the literature, we have found that the problem of evaluating an automatically-built KB involves six criteria:

• Accuracy which consists of determining the precision of the extracted knowledge and its level of confidence.

• Usefulness which consists of determining the relevancy of the knowledge for target tasks, its level of redundancy, and its level of granularity.

• Augmentation which consists of determining if the new knowledge added something new to the past knowledge.

• Explanation which consists of determining the provenance of the knowledge [START_REF] Dividino | Provenance, trust, explanations -and all that other meta knowledge[END_REF], and if there is something contradictory.

• Adaption which consists of determining if current knowledge could be adapted to new languages and domains and how much effort should be made to do that.

• Temporal qualification which consists of determining the temporal validity of the knowledge.

One possible way to evaluate these criteria could consists of treating the KB as a set of assertions, and use set-oriented measures such precision and recall to determine the accuracy of the recently built KB. Treating each assertion as atomic avoids the need to perform alignment between the expert system output and ground truth. Comparing the expert system and ground truth KB should require encoding the assertions in compatible or mappable ontologies. Identifying the differences should take into account the logical dependencies between assertions for not over-penalizing an expert systems for missing assertions from which many others are derivable [START_REF] Dredze | Entity disambiguation for knowledge base population[END_REF]. Evaluation of temporal qualification can be partially handled by treating the KB as a sequence of fixed sets of assertions over time. Augmentation can also be examined by performing ablation studies over the assertions in the KB.

The TAC KBP 2013 Cold Start Track 2 could serve as a base for this research. The idea behind this workshop is to test the ability of proposed methods to extract specific knowledge from text and other sources and place it into a KB. The schema for the target KB is specified a priori, but the KB is otherwise empty to start. Expert systems should be able to process some sources, extracting information about entities mentioned in the collection, adding the information to a new KB, and indicating how entry point entities mentioned in the collection correspond to nodes in the KB [START_REF] Mcnamee | An evaluation of technologies for knowledge base population[END_REF]. The sources consists of tens of thousands of news and web documents that contain entities that are not included in existing well-known KBs.

4.2 Challenge 2: improving the efficiency of the knowledge exploitation methods.

The second challenge should lay on the development of strategies for improving the efficiency of tasks exploiting the KB. Moreover, these strategies should not alter the capability of current methods to produce desired results by comparing them with task requirements. These methods are those concerning to knowledge reasoning, knowledge retrieval, and knowledge sharing. It is necessary to focus in many different aspects and requirements brought by these exploitation methods. Some of them may concern on efficiency, e.g., time and space complexity of the algorithms developed, and the rest will concern the effectiveness in relation to efficiency, e.g. correctness, completeness, and so on. Therefore, the problem needs to be addressed from a point of view involving multi-decision criteria.

The ultimate goal is to measure and improve the extent to which time, effort or cost is well used for the intended KB exploitation methods. According the literature, efficiency issues are currently tackled through a number of computational strategies. This strategies could be organized as follows:

• Parallelization of exploitation methods.

• Distribution of exploitation methods over computers with available computational resources.

• Approximation of results, which over time become better (more complete).

• Modularization of the KB, yielding smaller more targeted exploitation tasks.

• Optimization of existing exploitation methods.

To the best of our knowledge the first two items above remain largely unaddressed so far. Maybe the reason is that researchers thought that more computing power does not necessarily improve effectiveness of exploitation methods. However, it is possible to think that, at least at the beginning, it would accelerate the first run and the analysis of the bottlenecks [START_REF] Shvaiko | Ontology matching: State of the art and future challenges[END_REF]. In order that parallelization and distribution become really useful it possible that a traditional approach of divide-and-conquer with an iterative procedure whose result converges towards completeness over time will be necessary. Concerning the last three items, some solutions have been proposed in the past but only in relation to the TBox [START_REF] Shvaiko | Ontology matching: State of the art and future challenges[END_REF].

Therefore, there are still many interesting insights on potential further developments of the themes of approximation, modularization and optimization in the ABox.

Challenge 3: automatically selection, combination and tuning of algorithms for the maintenance of a KB.

The research challenge 3 should focus primarily in the development of methods for the maintenance of the KBs. These methods include the maintenance of the meta-knowledge, the knowledge integration tasks, and the knowledge validation using test cases from users. It is necessary to design solutions avoiding to choose these methods arbitrarily, but in automatic way, by applying machine learning techniques on an ensemble of methods. Sequential and parallel composition of methods should be also studied.

Hereby it is necessary to learn rules for the correctness on the output of different methods and additional information about the nature of the elements to be operated. The final goal is to leverage the strengths of each individual method.

Let us focus in semantic matching which is a well established field of research in the field of Knowledge Integration. Two entities in a KB are assigned a score based on the likeness of their meaning [START_REF] Pirrò | A semantic similarity metric combining features and intrinsic information content[END_REF]. Automatically performing semantic matching is considered to be one of the pillars for many computer related fields since a wide variety of techniques rely on a good performance when determining the meaning of data they work with.

More formally, we can define semantic matching as a function µ 1 x µ 2 → R that associates the degree of correspondence for the entities µ 1 and µ 2 to a score s ∈ R in the range [0, 1] , where a score of 0 states for not correspondence at all, and 1 for total correspondence of the entities µ 1 and µ 2 .

Traditionally, the way to compute the degree of correspondence between entities has been addressed from two different perspectives: using semantic similarity measures and semantic relatedness measures.

Fortunately, recent works have clearly defined the scope of each of them [START_REF] Sánchez | Ontology-based information content computation[END_REF]. Firstly, semantic similarity is used when determining the taxonomic proximity between objects. For example, automobile and car are similar because the relation between both terms can be defined by means of a taxonomic relation. Secondly, the more general concept of semantic relatedness considers taxonomic and relational proximity. For example, blood and hospital are not completely similar, but there is still possible to define a naive relation between them because both belong to the world of healthcare.

In most of cases, the problem to face is more complex since it does not involve the matching of two individual entities only, but two complete KBs. This can be achieved by computing a set of semantic correspondences between individual entities belonging to each of the two KBs. A set of semantic correspondences between entities is often called an alignment. It is possible to define formally an alignment A as a set of tuples in the form {(id, µ 1 , µ 2 , r, s)}, where id is an unique identifier for the correspondence, µ 1 and µ 2 are the entities to be compared, r is the kind of relation between them, and s the score in the range [0, 1] stating the degree of correspondence for the relation r.

Therefore, when matching two KBs, the challenge that scientists try to address consists of finding an appropriate semantic matching function leading to a high quality alignment between these two KBs.

Quality here is measured by means of a function A × A ideal → R × R that associates an alignment A and an ideal alignment A ideal to two real numbers ∈ [0, 1] stating the precision and recall of A in relation to A ideal .

Precision represents the notion of accuracy, that it is to say, states the fraction of retrieved correspondences that are relevant for the matching task (0 stands for no relevant correspondences, and 1 for all correspondences are relevant). Meanwhile, Recall represents the notion of completeness, thus, the fraction of relevant correspondences that were retrieved (0 stands for not retrieved correspondences, and 1 for all relevant correspondences were retrieved).

Challenge 4: methods which can explain what happens inside a KB in a clear and concise way.

The fourth challenge should find a way to provide explanations in a simple, clear and precise way to the users or software applications in order to facilitate informed decision making. In particular, most of techniques used by expert systems do not yield simple or symbolic explanations. It is necessary to take into account that different types of explanations may be needed. For example, if negotiating agents trust each others information sources, explanations should focus on the manipulations. If on the other hand, the sources may be suspect, explanations should focus on meta information about sources. If a user wants an explanation of the reasoning engine used by the expert system, a more complex explanation may be required.

There are some preliminary works which try to address the problem, i.e. laying the foundations about how an expert system should deliver explanations. According the literature, there are a set of requirements that are intended to act as criteria for the evaluation of explanations given by expert systems. For instance, Moore [START_REF] Moore | Participating in explanatory dialogues : interpreting and responding to questions in context[END_REF] states that explanations given by an expert system should have the characteristics listed below:

• Naturalness. Explanations should appear natural to the user. Explanations that are not structured according to standard pattern of human discourse often obscure critical elements of an explanation.

• Responsiveness. An expert system should have the ability to accept feedback from the user and to answer follow-up questions.

• Flexibility. An explanation should be able to offer an explanation in more than one way in order to accommodate differences knowledge and abilities of users.

• Sensitivity. An explanation should take into account the user's goals, the problem solving situation and the previous explanatory dialogue.

• Fidelity. An explanation should accurately reflect the knowledge from the KB and reasoning from the engine.

• Sufficiency. An explanation should be able to answer a range of questions users want to ask and not to be limited to those questions predicted by developers.

• Extensibility. An expert system should be easy to extend in order to accommodate questions not conceived at design time.

To the best of our knowledge, current expert systems are not able to cover all of these characteristics. Some expert systems try to use pre-written text attached to knowledge units or apply simple transformations to produce explanations from program code. This type of explanation is very simple to generate and easy to understand. However, this way to proceed is very far from the guidelines we have reviewed above. It is necessary to follow these guidelines for designing and evaluating new explanation delivery mechanisms so that they can meet this set of desirable characteristics.

Impact of future challenges

As already described before, the importance of satisfactorily addressing these four research challenges is given by contributions in several areas.

• Concerning the systematic development of a methodology for the comparison and evaluation of recently built KBs; the essence of the creation stage is that no one fully understands the idea or emerging body of knowledge, not even those creating it [START_REF] Zang | A survey of commonsense knowledge acquisition[END_REF]. The process of creation is messy by nature and does not respond well to formal methodologies or rigid time lines [START_REF] Lenat | Problems of scale in building, maintaining and using very large formal ontologies[END_REF]. The design of an evaluation methodology can definitely help to develop automatic solutions for addressing this problem since it is possible to learn the impact of each decision in the final quality of the KB.

• The importance of creating strategies for improving the efficiency of the knowledge exploitation methods is out of doubt. The impact of this approach is given by the fact that current methods for exploiting KBs are developed without taking into account its efficiency. For example, reasoning is a very complex process which needs a lot of time and memory space to be performed. As the KB grows, this issue become more critical, so it is quite important to build methods that meet their goals but these methods should also meet them efficiently.

• The idea of developing methods to automatically select, combine and/or tune algorithms for the maintenance of a KB is of vital importance [START_REF] Martínez-Gil | An overview of current ontology meta-matching solutions[END_REF]. The design of novel approaches that attempt to tune and adapt automatically current solutions to the settings in which an user or application operates are vital for a real automatic maintenance of large expert systems become real. This may involve the run time reconfiguration of the methods by finding their most appropriate parameters, such as thresholds, weights, and coefficients. In this way, tasks than currently are performed by humans can be automated.

• The novelty of the research concerning explanation delivery in a simple, clear and precise way to the users or software applications can have a better understanding of the knowledge provided by the expert systems. The idea to standardize explanations or proofs of tasks inside the KB in order to facilitate the interaction of expert systems with people or other software programs will have a positive impact in the development of this field and widespread of expert systems.

Fields of application that could get benefit

The spectrum of potential application domains that could be benefited from these advances is really wide. Let us summarize some application fields which can be benefited from satisfactorily addressing the aforementioned research challenges: Financial decision support. The financial services industry has been a traditional user of expert systems [START_REF] Ben-Assuli | Assessing the perception of information components in financial decision support systems[END_REF]. Some systems have been created to assist bankers in determining whether to make loans to businesses and individuals, insurance firms have used expert systems to assess the risk presented by a given customer or software applications has been built for foreign exchange trading. Therefore, advances in this field could be beneficial for improving the traditional systems, by aggregating new knowledge sources, improving the real time performance, explaining the rationale behind financial decisions, and so on.

Manufacturing industry. Configuration, whereby a solution to a problem is synthesized from a given set of elements related by a set of constraints, is one of the most important of expert system ap-plications [START_REF] Jones | Decision making in support of manufacturing enterprise transformation[END_REF]. Configuration applications were pioneered by computer companies as a means of facilitating the manufacture of semi-custom minicomputers. Nowadays, expert systems have found its way into use in a wide range of different industries, from textile industry where fabrics must be optimally cut, to failure detection in factories which consists of deducing faults and suggest corrective actions for malfunctioning devices or processes [START_REF] Lepuschitz | A multi-layer approach for failure detection in a manufacturing system based on automation agents[END_REF].

Question & Answering systems. Expert systems in this field are able to deliver knowledge that is relevant to the user's problem, in the context of the user's problem [START_REF] Morrissey | R/quest: A question answering system[END_REF]. In case ne improvements may be proposed, very interesting Q & A systems would be built. For example, a computational assistant which may give some hints to a user on appropriate grammatical usage in a text, or a tax advisor that accompanies a tax preparation program and advises the user on individual tax policy. Therefore, advances in this field could help to the popularization of this kind of systems in many additional fields like education, eTourism, personal finance, and so on.

Scientific research. Scientists need to be able to easily gain access to all information about chemical compounds, biological systems, diseases, and the interactions between these kinds of entities, and this requires data to be effectively integrated in order to provide a greater level view to the user, for instance, a complete view of biological activity [START_REF] Karp | Development of large scientific knowledge bases[END_REF]. Therefore, advances on the automatic building, exploitation and maintenance of large KBs will certainly help scientists to more easily work with all knowledge of their interest. More specifically, the benefits include the aggregation of heterogeneous sources using explicit semantics, and the expression of rich and well-defined models for working with knowledge.

Conclusions

In this work, we have presented the current state-of-the-art, problems that are still open and future research challenges for automated knowledge-base management. Our aim is to overview the past, present and future of this discipline so that complex expert systems exploiting knowledge from knowledge bases can be automatically developed and practically used.

Concerning the state-of-the art, we have surveyed the current methods and techniques covering the complete life cycle for automated knowledge management, including automatic building, exploitation and maintenance of KBs, and all their associated tasks. That it is to say, knowledge acquisition, representation, storage and manipulation for automatic building of KBs. Knowledge reasoning, retrieval and sharing for exploitation of KBs, and knowledge meta-modeling, integration and validation for the automatic maintenance.

From the current state-of-the-art, we have identified some problems that remain open and represent a bottleneck that is avoiding the rapid proliferation of systems of this kind. In fact, we have identified flaws in some areas including: a) automatic generation of large KB, b) lack of efficiency in methods for exploiting KBs, c) lack of automatic methods for smartly configuring maintenance tasks, and d) need of improving explanation delivery mechanisms. The final goal of automated knowledge-base management should be to empower people and intelligent software applications with the knowledge that they need to make well-informed decisions in an increasingly complex and changing world.

Finally, in view

  of the state-of-the-art and open problems, we have identified four research challenges that should be addressed in the future: a) methodology for the comparison and evaluation of KBs which have been automatically built, b) improving the efficiency of the knowledge exploitation methods, c) automatically selection, combination and tuning of algorithms for the maintenance of a KB, and d) design of methods which can explain what happens inside a KB in a clear and concise way. We think that satisfactorily addressing these challenges could have a positive impact not only in basic research but in a lot of application domains too.

In general, there is no agreement about the nomenclature used in the literature, but we will try to explain these discrepancies. In general we will use the expression a.k.a. (also knows as) for the same discipline receiving different names

http://www.nist.gov/tac/2013/KBP/ColdStart

Acknowledgments

We would like to thank in advance the reviewers for their time and consideration. This work has been partially funded by Vertical Model Integration within Regionale Wettbewerbsfahigkeit OO 2007-2013 by the European Fund for Regional Development and the State of Upper Austria.


Samuel Deleplanque
email: samuel.deleplanque@ifsttar.fr

Maintenance on the Railway Network: Disruptions and re-scheduling

Keywords: Scheduling, Railway, Maintenance Works, Mixed Integer Programming

Many studies had been made on optimization problems related to the maintenance operation works in the railway world. In this paper, we focus on lesser-known type of these problems. Here, the maintenance is already scheduled and the infrastructure manager can only change the train timetables and the routing. This problem is not well treated in the literature. In this work, we define the problem and we present a model. Since several days are available to solve the problem, the level of abstraction of the model and the size of the considered instances let us use an exact method. We propose a Mixed Integer Linear Program minimizing the primary delays. Results on real world instances are reported.

Introduction

In European railway systems, some Infrastructure Managers (IM) need a rescheduling tool which automatically updates the original timetables and routings, when some maintenance operations must be made on the network. Some of these works can be scheduled a long time in advance, sometimes while the timetables are made, and some other works can be scheduled while the rail is not used (e.g. by night). However, the maintenance operations considered in this paper have to be done at a specific time. The IM can only make a change on the timetables for the trains which normally use the same track and during the same time window of the works.

This specific re-scheduling process is often made by hand, and it is not usually well optimized when the traffic is dense. In this work, we propose an optimization model for modifying the timetables in order to minimize the delays while the work maintenance can be completed on time.

The main difficulties are the number of constraints, the size of the network, the quantity of trains and many other features related to the considered railway system. These difficulties imply that some choices have to be made. For example, one can reduce the space and the time window where and when trains can be rescheduled. However, the maintenance works considered in this paper are planned 3 weeks in advance. In this work, the level of abstraction of the model and the time available for solving the instances considered allow us to implement an exact method.

Our optimization model is based on a Mixed Integer Linear Program (MILP). It can take into account several maintenance operations for a given time window and for a given area. The direction of the optimization in the experiments is the minimization of the arrival delays.

The literature on the delay management had been particularly prolific. Minimizing primary or secondary delays is an important topic in the Operation Research literature applied on railway problems. In [START_REF] Dollevoet | Delay management and dispatching in railways[END_REF] and [START_REF] Dollevoet | Delay management with rerouting of passengers[END_REF], the authors propose a way to decide which connecting trains should wait for a delayed train. They consider the propagation of the delays in order to know if it is relevant for these trains to wait knowing that they will arrive with another delay at the next station where other passengers want to transfer. These recent works include several aspects of the real world which are not usually considered in the literature. For example, they consider different waiting times according to the number of people and the moment of the day. If a large flow of people is transferred to a train, the waiting time would be different comparing with a small flow of people. And, for the same number of people, the flows could be more or less fast at different moments of the days.

In [START_REF] Dollevoet | Delay management with rerouting of passengers[END_REF], the optimization model takes the point of view of the passengers. Here, when a transfer is planned, the system takes into account the possibility that a passenger might take another train if the primary delay (of his first train) makes the second train schedule not optimal for the passenger since taking another train can be a better solution at the station where the transfer will be made.

This work is focusing mainly on primary delays since there are not any connections considered in the instances. Minimizing delays had been studied in several contexts included when the maintenance works must be done.

In [START_REF] Louwerse | Adjusting a railway timetable in case of partial or complete blockades[END_REF], the authors define two separated sets: the complete blockades, where all the tracks are blocked and the partial blockades, where one or few tracks are not available. This paper proposes a method to handle the disturbances for the second case. The main contribution is a static optimization model based on a model of [START_REF] Törnquist | N-tracked railway traffic re-scheduling during disturbances[END_REF] and adapted for our specific problem.

This paper is structured as follows. In section 2, we first present the train maintenance problem considered in this work. In section 3, the optimization model is formally defined by a Mixed Integer Program. Finally, in section 4, we describe the experimental setup and discuss the results.

Problem definition

This work considers a problem of re-scheduling in a railway system. Some maintenance operations had been planned during a specific period on some part of a track. At that period, the trains which are usually running on that track will have to be rerouted and/or postponed.

The model presented in this paper takes into account several parallel tracks with some switches allowing the trains to change from one track to another. As in Figure 1, the other switches are not taken into account.

Definitions

We need to define the notions of segment and event which are two main concepts used in the problem formulation:

• A segment is a specific portion of a railway network. A segment gathers all the parallel tracks between two points A and B. In a given segment, it is impossible to go from one track to another: the trains can only change their routes at one end of the segment. Such a segment is composed of one or several tracks. There are often 2 tracks in a real railway network. In this case, we have one way for each direction. Also, some segments represent only one point (A=B) if they are related to the idle trains.

• An event is the process of a train going from a point A to a point B by a segment. One event is linked with exactly one segment and only one train. The related track is chosen by the IM and it is modifiable in our problem.

An event is also defined with a departure time and an arrival time. When the segment of this event corresponds to a single point, it represents the waiting time of the train at this point.

Problem data

The following model is an adaptation of the one proposed in [START_REF] Törnquist | N-tracked railway traffic re-scheduling during disturbances[END_REF]. Some constraints have been removed. For instance, we don't check if a train can fit in the track section modeled by a event. Conversely, some other constraints had been added mainly to integrate the works. We define first the parameters obtained from the input. We note R, E, W and S the sets of train routes, events, works and segments, respectively. In the same order, these sets are indexed by r, e, w and s. SE s , s ∈ S, is a subset of E the set of events. This is the ordered list of events on all the tracks of the given segment s. RE r , r ∈ R, is another subset of E. It corresponds to the ordered list of events on the train route r. The last event for a given r in RE r is noted n r . The orders of SE s , s ∈ S, and RE r , r ∈ R, follow the original timetable in chronological order.

We denote by T s the set of tracks t, t = 1..|T s |, for a given segment s, s ∈ S. For any segment s, s ∈ S, the model considers two sets of positive constants called separation time. ∆ F s is the minimum time separating two consecutive trains following each other and, ∆ M s is the minimum time separating two trains in opposite direction.

In the original timetable, an event e, e ∈ E, starts initially at time τ begin e and finishes at time τ end e . According to the type of an event e, e ∈ E, the parameter d e describes the minimum running time or a minimum waiting time. The first time is related to an event e, e ∈ E, with a train running from one point to another (this situation is modeled with the equality i e = 0). The second time corresponds to the stop duration at a point (i e = 1).

The constant o e indicates the direction of the train for the event e, e ∈ E. For instance, two consecutive events e, e ∈ E, and e , e ∈ E, with the related train route r, r ∈ R, and r , r ∈ R, We now define the 7 sets of variables. The 3 first sets are containing continuous variables:

following
• x begin e is the time when the event e, e ∈ E, starts;

• x end e is the time when the event e, e ∈ E, ends;

• z e is the delay of the event e, e ∈ E.

The 4 other sets contain binary variables:

• q et is equal to 1 if the event e, e ∈ SE s , s ∈ S, is planned on track t, t ∈ T s , s ∈ S, 0 otherwise;

• α wt e is equal to 1 if the event e, e ∈ E, will be scheduled before the fixed maintenance work w, w ∈ W , 0 otherwise;

• γ eê is equal to 1 if, as in the original timetable, e is located before ê on the events ordered list SE s , SE s ∈ E, s ∈ S, 0 otherwise;

• λ eê is equal to 1 if, on the contrary to the original timetable, ê is located before e on the events ordered list SE s , SE s ∈ E, s ∈ S, 0 otherwise.

Optimization model

We present here the optimization model. First we detail the constraints and second we define the objective function.

Constraints

For a given train, a series of events is controlled by Constraints (1) which force an event to start once the previous one is finished. Constraints (2) give a lower bound on the event duration. Here, a train can speed up but can't be faster than the minimum time d e of the event.

x end e = x begin e+1 , e ∈ RE r , r ∈ R : e = 1..n r -1, (1)

x end e ≥ x begin e + d e , e ∈ E, (2)
In Constraints (3), an event e cannot be scheduled before it had been already scheduled in the timetable by τ begin e while Constraints (4) just give the delay value of an event e to z e .

x begin e ≥ τ begin e , e ∈ E :

i e = 1, (3)
x end e -τ end e ≤ z e , e ∈ E, (4)
For each event of each segment, Constraints (5) force the usage of one and only one track.

t∈Ts q et = 1, e ∈ SE s , s ∈ S, (5)
Constraints ( 6) and ( 7) force the events planned during the work maintenance to be rescheduled. If such an event e is still planned on the same track of the work w, Constraints (6) will force e to start after the end of w or Constraints (7) will force e to finish before the beginning of w. The big-M will activate one or the other constraint.

x begin e ≥ w end t q et -M α wt e , e ∈ SE s , t ∈ T s , s ∈ S,

x end e ≤ w begin t

q et + M (1 -α wt e ), e ∈ SE s , t ∈ T s , s ∈ S, (7)
Constraints (8) and ( 9) are made to activate the Constraints (10, 11, 12, 13) by giving values to λ eê and γ eê according to the order of events in case they are scheduled on the same tracks.

q et + q êt -1 ≤ λ eê + γ eê , e, ê ∈ SE s , t ∈ T s , s ∈ S : e < ê, (8)
λ eê + γ eê ≤ 1, e, ê ∈ SE s , s ∈ S : e < ê, (9)
The 4 sets of Constraints (10, 11, 12, 13) activate the separation times on two consecutive trains for a given track. If the trains are running in opposite direction (o e = o ê), the Constraints (10, 12) apply a separation time ∆ M s for the segment s. Otherwise, if the trains are running in the same direction (o e = o ê), the Constraints (11, 13) apply a shorter separation time ∆ F s of the same segment s.

x begin ê -x end e ≥ ∆ M s γ eê -M (1 -γ eê ), e < ê ∈ SE s , s ∈ S, o e = o ê, (10) x begin ê -x end e ≥ ∆ F s γ eê -M (1 -γ eê ), e < ê ∈ SE s , s ∈ S, o e = o ê, (11) x begin e -x end ê ≥ ∆ M s λ eê -M (1 -λ eê ), e < ê ∈ SE s , s ∈ S, o e = o ê, (12) x begin e -x end ê ≥ ∆ F s λ eê -M (1 -λ eê ), e < ê ∈ SE s , s ∈ S, o e = o ê, (13)
The binary and continuous variables are finally defined by Constraints (14, 15, 16).

x begin e , x end e , z e ≥ 0, e ∈ E, (14) γ eê , λ eê , ∈ {0, 1} , e, ê ∈ SE s , s ∈ S : e < ê, (15)

q et , α wt e ∈ {0, 1} , e ∈ SE s , t ∈ T s , s ∈ S, (16)

Objective function

We define a simple objective function which minimizes the final delays of the trains. We note z nr the delay variable of the last event considered in the instance for the train r. The objective function is the following:

min r∈R z nr (17)

Experiments

The instances are based on real data from the Belgian network. The instances are randomly chosen in terms of time and space. However, the size of these instances are based on what the IM needs to solve in general. We consider here the typical case with two parallel tracks and with 4 or 5 switch points. Periods from 10 hours to 18 hours are considered. The instances had been solved by CPLEX 12.6 running on a 3Ghz Intel i7 CPU. Table 1 shows the 2 sets of 9 instances. CPU times in seconds and the number of nodes needed by CPLEX are given for each time windows (TW) in hours.

These instances are tackled within 10 seconds including the ones covering a full day of exploitation. The efficiency of the optimization model seems to be sufficient since these maintenance operations are known weeks in advance.

Fig. 1 .

 1 Fig. 1. Switch points considered in the model

  each other, imply the equality o e = o e . Otherwise, if the trains are moving in opposite direction, we have o e = o e . A work maintenance w t , w t ∈ W , has a time window noted [w begin

t

; w end t ]. We consider that a given track t, t ∈ T s , on a segment s ∈ S, is limited to only one work.

Table 1 Computational

 1 Results on the instances with 4 and 5 switch points

		4 switch points 5 switch points
	TW (h) CPU(s) Nodes CPU(s) Nodes
	10	0.91	1	0.90	79
	11	1.15	1	1.36	279
	12	1.26	1	1.95	87
	13	0.95	1	7.60	1367
	14	0.89	1	1.64	151
	15	1.17	82	8.50	959
	16	2.73	65	1.54	73
	17	2.05	49	5.84	498
	18	3.53	138	4.73	224

Acknowledgment

This project is studied at the Université Libre de Bruxelles in collaboration with INFRABEL, the Belgian railway infrastructure manager. It is financed by the COFUND program of the European Union (FP7 -Marie Curie Actions) with the Beware Academia Fellowship.


Philippe Dessus

Louise-Héléna Aubineau

Dominique Vaufreydaz

James Crowley

A Framework for a Multimodal Analysis of Teaching Centered on Shared Attention and Knowledge Access

The Activity of Teaching: A Social Learning Strategy

•Everybody can try to learn anything alone, but some content is better learned socially (time, energy, opportunities, danger) (Kendal et al., 2018) •Teaching, a.k.a. social learning with explicit instructions, is a form of social and cultural learning that relies on domain-general abilities

The Abilities Grounding Teaching

•Heyes (2018) argues that ability of teaching is built on top of social faculties like:

• Selective social learning

• Imitation

• Mind reading In which Occasions does Teaching Occur, Actually?

•When a Learner encounters 2 kinds of difficulties (Kline, 2015), either

• to have access to the Content, or

• to focus her attention to C

•And when a Teacher can allocate some time to help L (even it's costly)

Some Cues to Trigger Access or Attention

•Communicative and attentional cues are crucial in social learning, to make teaching easier

• Visual or vocal priming: e.g., T pointing to C in presence of L

• Joint attention to C (in some cases, parallel)

• Action and speech contingencies

• Adapted communication ("teacherese")
Research Questions

•Which framework for accounting teaching processes?

•How to capture (part of) teaching processes by eye-tracking and signal processing tools?

•Which experiments using this framework to deploy in classrooms?

Components of the Teaching Process

•Two steps: Initial situation (without social help) and teaching situation (with social help)

•Determination criteria: how this teaching situation can be automatically determined?

•Five levels of teaching, of increasing complexity (from Kline, 2015)

Level 1 -Social Tolerance (Teacher as a model)

•Initially: L can perceive C but its access depends on T's willingness

•Teaching: T tolerates that L observes her during standard activities, without modifying anything

•Criteria: L visually tracks T frequently; T doesn't track L at all

Level 2 -Opportunity Provisioning (a.k.a. Playground Making)

•Initially: L would be able to perceive C, but its access is difficult

•Teaching: T devises specific activities so that L can learn (play, chores, etc.)

•Criteria: C is modified by T; T doesn't track L; parallel attention towards C (is the task completed?)

Level 3 -Teaching by Stimulus or Local Enhancement (actual teaching)

•Initially: L can access C but lacks attention to it

•Teaching: T points towards C, slows down her action and speech

•Criteria: Frequent reciprocal gazes between T and L, "teacherese", action exageration: T's larger body's bounding volume

Teaching: Higher Levels (not detailed there)

•Teaching by evaluative feedback (L accesses C but lacks information on her performance) or by direct explanations (L lacks both attention and access to C, and needs explicit information)

•Involves mind reading more intensively, and language, so more difficult to be captured by eye tracking tools only

Understanding Classroom Situations

  •Capture teaching levels in a "smart classroom" context: cameras, mobile eye-tracker for T, camera glasses for Ls •Use this framework (likely extended to variables like position, noise level) to investigate notions in educational psychology (Ls time on task, or steering group, T immediacy, etc.)(Cortina et al., 2015; Dessus et al., 2016)

-Multimodal Analysis of Teaching • Dessus, Aubineau, Vaufreydaz, & Crowley • Eye Movements Conf. • Grenoble June 8, 2018

-Multimodal Analysis of Teaching • Dessus, Aubineau, Vaufreydaz, & Crowley • Eye Movements Conf. • Grenoble June 8, 2018

-Multimodal Analysis of Teaching • Dessus, Aubineau, Vaufreydaz, & Crowley • Eye Movements Conf. • Grenoble June 8, 2018

-Multimodal Analysis of Teaching • Dessus, Aubineau, Vaufreydaz, & Crowley • Eye Movements Conf. • Grenoble June 8, 2018

-Multimodal Analysis of Teaching • Dessus, Aubineau, Vaufreydaz, & Crowley • Eye Movements Conf. • Grenoble June

8, 2018

-Multimodal Analysis of Teaching • Dessus, Aubineau, Vaufreydaz, & Crowley • Eye Movements Conf. • Grenoble June 8, 2018

-Multimodal Analysis of Teaching • Dessus, Aubineau, Vaufreydaz, & Crowley • Eye Movements Conf. • Grenoble June 8, 2018

-Multimodal Analysis of Teaching • Dessus, Aubineau, Vaufreydaz, & Crowley • Eye Movements Conf. • Grenoble June 8, 2018

-Multimodal Analysis of Teaching • Dessus, Aubineau, Vaufreydaz, & Crowley • Eye Movements Conf. • Grenoble June 8, 2018

-Multimodal Analysis of Teaching • Dessus, Aubineau, Vaufreydaz, & Crowley • Eye Movements Conf. • Grenoble June 8, 2018

-Multimodal Analysis of Teaching • Dessus, Aubineau, Vaufreydaz, & Crowley • Eye Movements Conf. • Grenoble June 8, 2018

Thanks for your attention! Any questions?

@pdessus

References @ https://frama.link/eye-mov