Difficulty Estimator for Converting Natural Language into ... - AI Group [PDF]

Difficulty Estimator for Converting Natural Language into First Order Logic Isidoros Perikos, Foteini Grivokostopoulou, Ioannis Hatzilygeroudis, Konstantinos Kovas School of Engineering Department of Computer Engineering & Informatics University of Patras 6500 Patras, Hellas (Greece) {perikos, grivokwst, ihatz, kobas}@ceid.upatras.gr

Abstract. The NLtoFOL system is an interactive web-based system for learning to convert natural language (NL) sentences into first order logic (FOL). In this paper, we present a difficulty estimating expert system that determines the difficulty level of a sentence‟s conversion process. Our approach is based on the complexity of the corresponding FOL formula instead of the NL sentence itself. Parameters like the number, the type and the order of quantifiers, the number of implications and the number of different connectives are taken into account. Experimental results show that for a significant part of sentences the difficulty estimating system produces the correct outputs. Keywords: Difficulty Estimation, Natural Language Formalization, First Order Logic

1 Introduction Knowledge Representation & Reasoning (KR&R) is a fundamental topic of Artificial Intelligence (AI). A basic KR language is First-Order Logic (FOL), the main representative of logic-based representation languages, which is part of almost any introductory AI course and textbook. So, teaching FOL as a KR&R language a vital aspect. Teaching FOL as a knowledge representation and reasoning language includes many aspects. One of them is translating natural language (NL) sentences into FOL formulas, often called logic formalization of NL sentences. It is an ad-hoc process; there is no specific algorithm that can be automated within a computer. This is mainly due to the fact that NL has no clear semantics as FOL does. Most of existing textbooks do not pay the required attention to the above aspect. They simply provide the syntax of FOL and definitions of the logical symbols and terms [10]. Even more specialized textbooks do the same [4]. At best, they provide a kind of more extended explanations and examples [6]. They do not provide any systematic guidance towards it. In [7], we introduced a structured process for guiding

students in translating a NL sentence into a FOL one. This process was implemented as a web-based interactive system NLtoFOL presented in [8]. However, the system in [8] cannot automatically determine the difficulty level of a sentence‟s conversion. In this paper, we present this new capability of the system, an expert system that determines the formalization difficulty level of a sentence based on its corresponding FOL expression(s). The structure of the paper is organized as follows. Section 2 presents related work. Section 3 deals with the NL to FOL conversion by presenting the SIP (Structured and Interactive Process) formalization process via an example. In Section 4, the revised architecture of the NLtoFOL system is presented. Section 5 deals with the difficulty estimating expert system. Section 6 presents and discusses experimental results. Finally, Section 7 concludes and provides directions for future research.

2 Related Work KRRT (Knowledge Representation and Reasoning Tutor) [1] is a web-based system that that aims at helping students to learn FOL as a KR&R language. It is based on FITS [1], its predecessor system, and deals with both knowledge representation and reasoning with FOL. The translation from NL to FOL takes place in its KR part. The student gives his/her FOL proposal sentence and the system checks its syntax and whether it is the correct one. However, it does not provide any information about the difficulty of the NL sentence‟s translation into FOL. In [3], a work that deals with the difficulty of the translation of NL into FOL is presented. Its main characteristic is that it tries to determine a NL sentence‟s formalization difficulty based on the students‟ responses. For this purpose, a corpus of twenty NL sentences was used and based on the students‟ answers two metrics were calculated. Those two metrics concern the proportion of students who get a particular sentence‟s formalization wrong and the number of attempts needed to determine the correct formula. Finally, based on those two metrics the NL sentences are characterized as Easy/Hard to get wrong and Easy/Hard to resolve. According to our knowledge, there is no system that automatically determines the difficulty level of a sentence‟s conversion process.

3 A Structured and Interactive process for NL to FOL conversion One problem in converting natural language into first order logic has to do with the unclear semantics that natural language has. Natural language has no clear semantics as FOL does. The main difficulty comes from the lack of a systematic way of doing the conversion. In a previous work [7], we introduce NLtoFOL SIP (Structured and Interactive Process) for translating NL sentences into FOL formulas. It is a process that guides a student in translating (or converting) a NL sentence into a FOL one and consists of ten steps. To demonstrate it, we present the conversion of the NL sentence “All farmers who own donkeys beat them” into a FOL formula based on the NLtoFOL SIP process.

Step 1: Spot the verbs, the nouns and the adjectives in the sentence and specify the corresponding predicates or function symbols. There are four such elements: farmers predicate: farmer donkeys predicate: donkey own predicate: owns beat predicate: beats Step 2: Specify the number, the types and the symbols of the arguments of the function symbols (first) and the predicates (next). They are presented in the following table: Predicate farmer donkey owns farmer beats

Arity 1 1 2 1 2

Types variable variable variable,variable variable variable, variable

Symbols x y x, y x x, y

Step 3: Specify the quantifiers of the variables. x→∀ (because of “All”), y →∀ (because of an implicit “(all of) them”) Step 4: Construct the atomic expressions (or atoms) corresponding to predicates. We construct as many atoms as the predicates: Atom 1: farmer(x) Atom 2: donkey(y) Atom 3: owns(x,y) Atom 4: beats(x, y) Step 5: Divide produced atoms in groups of the same level atoms. This mainly refers to grouping atoms that should be connected with each other with some connective: AtomGroup1: {farmer(x), donkey(y), owns(x,y)} AtomGroup2: {beats(x,y)} Step 6: Specify the connectives between atoms of each group and create corresponding logical formulas. We form the formulas corresponding to the groups of step 5: AtomGroup1 Form1: farmer(x) donkey(y)owns(x,y) AtomGroup2 Form2: feeds(x,y) Step 7: Divide produced formulas in groups of the same level formulas. This usually corresponds to specifying the left and right parts of an implication:

FormGroup1-1: {farmer(x) donkey(y)owns(x,y)} FormGroup1-2: {beats(x,y)} Step 8: If only one group of formulas is produced, specify the connectives between formulas of the group, create the next level formula and go to step 10. Not applicable. Step 9: Specify the connectives between formulas of each group, create the next level formulas and go to step 7. FormGroup1-1 Form1-1: farmer(x) donkey(y)owns(x,y) FormGroup1-2 Form1-2: beats(x,y) Step 7: FormGroup2-1: {(farmer(x) donkey(y)owns(x,y)), beats(x,y)} Step 8: FormGroup2-1: Form1-3: {(farmer(x) donkey(y) owns(x,y))  beats(x,y)} Step 10: Place quantifiers in the right points in the produced formula to create the final FOL formula. x) (y) (farmer(x) donkey(y)owns(x,y)) beats(x,y)

4 System Architecture The basic architecture of NLtoFOL system is presented in [8], which we revise here. Tutor

Student

Student Interface (SI)

Student Interface Configurator

Intelligent Data Analysis

Tutor Interface (TI)

Difficulty Estimating System (DES)

System Database (SD)

Figure 1: Extended Architecture of the NLtoFOL System

More specifically, we introduce a new component, which estimates the difficulty level of the conversions of the stored NL sentences. So, the system consists of two interfaces, the Student Interface (SI) and the Tutor Interface (TU). SI is dynamically configured [8] during the NL to FOL conversion session via the Student Interface Configurator . This is achieved via the guidance given by the Intelligent Data Analysis unit, which is a rule-based system that based on the input data from SI decides on which reconfigurations should be made to it or which kind of interaction will be allowed or given to the user. It is also responsible for tracing user’s mistakes and handling them in terms of appropriate feedback to the user. The Difficulty Estimating System (DES) is an expert system that is used to determine the difficulty level of a sentence’s formalization process. This can be done automatically without tutor intervention. Tutor can accept or not the result of DES. Finally, the System Database (SD) is used to store sentences and related information, including estimated difficulty level.

5 Difficulty Estimating System We have developed the Difficulty Estimating System (DES), which is able to automatically determine the difficultly level of a NL to FOL sentence conversion. The structure of DES is illustrated in Figure 2. DES is a rule-based expert system implemented in Jess, an expert system shell [5]. It consists of the Difficulty Parameters Fact Base (DPFB), where the values of the parameters which the estimation is based on are stored, the Difficulty Estimation Rule Base (DERB), where the rules for estimating the difficulty level are stored, and the Jess Inference Engine (JIE), which performs and controls the difficulty estimation process. The corresponding FOL formula of each NL sentence is analyzed via the FOL Formula Analyzer (FFA), the values for its estimation parameters are extracted and stored in DPFB as Jess facts. The output of the system is the difficulty level of the NL sentence conversion process. Knowledge Base

FOL Formula Analyzer (FFA)

FOL Formula

Difficulty Parameters Fact Base (DPFB)

Difficulty Estimation Rule Base (DERB)

Jess Inference Engine (JEI)

Difficulty Level

Figure 2: The structure of Difficulty Estimating System

We should also notice that the values of the parameters used for difficulty estimation are aslo permanently stored in SD for each sentence. To develop DES, we consulted an expert-tutor in the field. Most tutors empirically estimate the difficulty of a sentence‟s conversion/formalization. In cooperation with the expert-tutor, we tried to specify which factors/parameters have an impact on the difficulty level of sentences‟ conversions. Finally, we came up with the following difficulty estimation related parameters, which refer to the converted (FOL) sentence:  the number, the type and the order of the quantifier(s)  the number of the implication symbols  the number of the different connectives Connectives include { , , , }. So, DES determines the difficulty level of a conversion process based on the above parameters, which are all related to the resulted FOL formula. Based on the resulted FOL formula was the easiest and most effective choice. Afterwards, we consulted the expert-tutor to acquire the necessary rules for the difficulty estimation based on the above parameters. Table 1 presents the resulted rules, which classify sentences into five categories as far as the difficulty of their conversion process is concerned: very easy, easy, medium, difficult and advanced. Table 1: Rules for determine difficulty level exercises No

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Number Number Universal of of quantifiers implications quantifiers

0 0 0 0 0 1 0 0 ≤1 ≤1 ≤1 ≤1 1 1 1 1 ≥2 ≥2

0 ≤1 ≤1 ≥1 ≥1 ≤1 ≥2 ≥2 ≤1 ≤1 ≥1 ≥1 ≥2 ≥2 ≤1 ≤1 ≥2 ≥3

no yes no yes no yes yes yes yes no yes no yes yes yes no yes yes/no

Existential quantifiers

no no yes no yes no yes yes no yes no yes yes yes no yes yes yes/no

Number of  different before connectives 

0 0 0 ≤1 ≤1 ≤2 0 0 3 3 ≤3 ≤2 ≤2 ≤2 3 3 ≤3 ≤3

no yes no yes -

Difficulty Level

Very Easy Very Easy Very Easy Easy Easy Easy Easy Medium Medium Medium Medium Medium Medium Difficult Difficult Difficult Advanced Advanced

For example, for the NL sentence "Every city has a dog catcher that has been bitten by any dog living in the city" with corresponding FOL formula:

(x) city(x)  ((y) dog-catcher(y,x)(z) (dog(z)lives-in(z,x))  has-bitten(z, y)) the total number of implications are two, the total number of quantifiers are three, there are three quantifiers, two universal and one existential, and there are two different connectives (, ). So, rule 18 of Table 1 applies and the difficulty level of the sentence is estimated to be "Advanced". Table 2 presents some example sentences and corresponding difficulty levels of their conversion processes as produced by DES. Table 2 : Examples of difficulty levels estimated by DES Natural Language (NL) Pluto is a dog There is at least one thief Some cats are black Every apple is delicious Every gardener likes the sun. Ancestors of my ancestor are ancestors of mine No purple mushroom is poisonous. There is a barber in town who shaves all men in town who do not shave themselves.

First Order Logic (FOL) dog(Pluto) (x) thief(x) (x) cat(x) black(x) (x)apple(x) delicious(x) (x) gardener(x) likes(x,sun) (x)(y)(z) (ancestor (x, y) ancestor (y,z) ancestor(x,z)) (x)(mushroom(x)purple(x)) ¬poisonous(x) (x)(barber(x) inTown(x) (y)(man(y) inTown(y) shave(y,y)shave(x,y)))

Difficulty Level Very Easy Very Easy Easy Easy

Rule applied 1 3 5 6

Easy

6

Medium

11

Medium

9

Difficult

14

6 Experimental Results and Discussion To measure the performance of DES, an evaluation was performed. A corpus of 88 NL sentences and their corresponding FOL formulas was created and used for the system evaluation. The system was used to determine the difficulty level of those sentences, for which the expert-tutor had determined their difficulty levels. All sentences were given as inputs to DES and its outputs were produced. Evaluation of DES was based on the following metrics: accuracy, precision, sensitivity and specificity, which for two classes are defined as follows:

acc 

ad , abcd

prec 

a a , sen  , ac ab

spec 

d cd

where, a is the number of positive cases correctly classified, b is the number of positive cases that are misclassified, d is the number of negative cases correctly classified and c is the number of negative cases that are misclassified. By „positive‟

we mean that a case belongs to the class of the corresponding difficulty level and by negative that it doesn‟t. In case of multiple classes, as ours, the above metrics are calculated as follows: m

acc 

 acc

i

i 1

m

m

, prec 

 prec i 1

m

m

m

i

, sen 

 sen

i

i 1

m

, spec 

 spec i 1

i

m

where m is the number of output classes. They represent the average values of the metrics, across all classes. The results are presented in Table 3. Table 3: Evaluation metrics for DES Difficulty class Evaluation metric Accuracy Precision Sensitivity Specificity

Very Easy 0.909 0.600 1.000 0.894

Easy

Medium

Difficult

Advanced

Average

0.898 0.923 0.774 0.965

0.920 0.882 0.909 0.927

0.920 0.667 0.250 0.988

0.966 0.600 0.750 0.976

0.9226 0.7344 0.7366 0.9500

The results show a very good performance of DES. A noticeable point is the low sensitivity value in the case of „Difficult‟ class, which however is due to the small number of available sentences belonging to that class (only four). The general accuracy of the system shows the percentage of the sentences for which the system and the expert-tutor have determined the same difficulty level. From the corpus of 88 sentences that were tested, the system correctly identified the difficulty of 71 sentences. Thus, the general accuracy of the system is 0.8068, which also shows a very good performance. Looking at the sentences that DES failed to determine the right difficulty level (class), we came to the conclusion that it is mainly due to the fact that our approach does not take into account the NL version of the sentence, which plays a role in some cases. More specifically, for some NL sentences happens that while they have difficult semantics, which makes the expert-tutor to give a higher level of difficulty to them, they have rather simple corresponding FOL formulas. Thus, the system cannot give a correct estimation of their difficulty. One such case is the following: Natural Language (NL) Not all men that are vegeterian are happy

First Order Logic (FOL) (x) male(x)  vegeterian(x)  happy(x)

DES Result

Expert Classification

Easy

Medium

We also conducted a second experiment to test whether the proposed classification is valid. For this evaluation, a corpus of 20 sentences was used. The corpus created in such a way that four NL sentences from each difficulty level were randomly selected.

A group of 40 students was given that corpus and tried to convert the NL sentences into the corresponding FOL ones using the process presented in Section 3. In Table 4, the percentages of the correctly accomplished conversions per difficulty class are presented. It shows that difficulty levels specified by DES are reasonable and correspond more or less to reality. One could expect a less percentage of correct conversions in the difficult and the advanced levels. Table 4: Statistics based on students‟ answer analysis. Difficulty Level Very easy Easy Medium Difficult Advanced

Average correct conversions (%) 87 80 68 47 35

7 Conclusion and Future Work The NLtoFOL system is a web based interactive system for helping students to translate (or convert) natural language (NL) sentences into first-order logic (FOL) formulas. In this paper an expert system that determines sentences formalization/conversion difficulty is presented. The system takes as input the corresponding first order logic (FOL) formula of a NL sentence and gives as output an estimation of the difficulty of its conversion process. To do so, it computes a set of parameters, like the number and the type of the quantifier(s), the number of the implications and the different connectives of the FOL expression. Experimental results validate our approach in a large degree. However, there are some points that the system can be improved at. As mentioned above, DES works by analysing the FOL formula of the NL sentence. An improvement will be to take into account the natural language structure of the sentence and parameters related to the semantics of the sentence. Moreover, it could take into account the existence of some keywords like “everybody” or “somebody”, their number and their order. This is a direction for further research. Alternatively, use of a method similar to that in [9] could be investigated. This means to use a student-based approach instead of a sentence-based approach or a combination of them. This is another direction for further research.

Acknowledgement This work was supported by the Research Committee of the University of Patras, Greece, Program “Karatheodoris”, project No C901

References [1] [2] [3]

[4] [5] [6] [7]

[8]

[9]

[10]

Alonso, J.A., Aranda, G.A., Mart´ın.-Matceos, F.J.: FITS: Formalization with an Intelligent Tutor System. In: Proceedings of the IV International Conference on Multimedia and Information and Communication Technologies in Education (2006). Alonso, J.A., Aranda, G.A., Martin-Matceos, F.J.: KRRT: Knowledge Representation and Reasoning Tutor. In: Moreno Diaz, R., Pichler, F., Quesada Arencibia, A. (eds.) EUROCAST 2007. LNCS, vol. 4739, pp. 400–407. Springer, Heidelberg (2007). Barker-Plummer, D., Cox, R., Dale, R.: Dimensions of Difficulty in Translating Natural Language into First-Order Logic. Educational Data Mining 2009: 2nd International conference on Educational Data Mining, Cordoba, Spain. pp 220-228, (2009). Brachman, R.J., Levesque, H.J.: Knowledge Representation and Reasoning. Elsevier, Amsterdam (2004). E. Friedman-Hill: Jess in Action: Rule-Based Systems in Java. Manning Publications Company (2003). Genesereth, M. R. and Nilsson, N. J.: Logical Foundations of AI. Morgan Kaufmann, Palo Alto (1987). Hatzilygeroudis, I.: Teaching NL to FOL and FOL to CL Conversions. In: Proceedings of the 20th International FLAIRS Conference, Key West, FL, May 2007, pp. 309–314. AAAI Press, Menlo Park (2007). I. Hatzilygeroudis and I .Perikos: A web-Based Interactive System for Learning NL to FOL Convertion. New Directions in Intelligent Interactive Multimedia Systems and Services – 2. Studies in Computational Intelligence. Springer-Verlag, Volume 226/2009, 297-307 (2009). C. Koutsojannis, G. Beligiannis, I. Hatzilygeroudis, C. Papavlasopoulos, and J. Prentzas: Using a hybrid Al approach for exercise difficulty level adaptation, International Journal of Continuing Engineering Education and Life-Long Learning, 17(4-5), 256-272 (2007). Russell, S., Norvig, P.: Artificial Intelligence: a modern approach, 2nd edn. Prentice Hall, Upper Saddle River (2003)