In this paper we will describe the NL2KR system that translates natural language sentences to a targeted knowledge representation formalism. The system starts with an initial lexicon and learns meaning of new words from a given set of examples of sentences and their translations. We will describe the rst release of our system with several examples.
Our approach to understanding natural language involves translating natural
language text to formal statements in an appropriate knowledge representation
language so that a reasoning engine can reason with the translated knowledge
and give a response, be it an answer, a clarifying question or an action. To
translate natural language text to a formal statement we propose to use the
compositional method of Montague [
The NL2KR system uses an initial lexicon containing some words and their meanings and a set of training corpus containing sentences in natural language and their translations to learn new meanings of words. The system then uses the new learned lexicon to translate new sentences. In this paper, we would like to give an overview of the NL2KR system and examples of using it.
Shown below in Fig. 1 is the architecture of the NL2KR system. It has two subparts which depend on each other (1) NL2KR-L for learning and (2) NL2KR-T for translating.
The NL2KR-L sub-part takes an initial lexicon consisting of some words and their meanings in terms of -calculus expressions & a set of training sentences and their target formal representations as input. It then uses a Combinatorial Categorical Grammar (CCG) parser to construct the parse trees. Next, the learning sub-part of the system uses Inverse- and Generalization algorithms to learn meanings of newly encountered words, which are not present in the initial lexicon, and adds them to the lexicon. A parameter learning method is then used to estimate a weight for each lexicon entry (word, its syntactic category and meaning) such that the joint probability of the sentences in the training set getting translated to their given formal representation is maximized. The result of NL2KR-L is the nal lexicon, which contains a larger set of words, their meanings and their weights.
Once the training component nishes its job, the translation sub-part (NL2KRT) uses this updated lexicon and translates sentences using the CCG parser. Since words can have multiple meanings and their associated -calculus expressions, weights assigned to each lexical entry in the lexicon helps in deciding the more likely meaning of a word in the context of a sentence. 3
Third Party Software Used by NL2KR The current version of NL2KR uses the following libraries and tools developed by others: { Scripting language Python (version 2.6) { AspCcgTk version 0.3 1 { Stanford Log-linear Part-Of-Speech Tagger 2 (version 3.1.5) { Oracle Java (version 1.6) { ASP grounder and solver: gringo (version 3.x), clasp (version 2.x) and clingo (version 3.x) 3 3.2
The NL2KR package contains a readme le and a zipped le which contains { AspCcgTk { Jar le and models of Stanford Log-linear Part-Of-Speech Tagger { Jar le and con gurations for NL2KR { Gringo, clasp and clingo After unzipping the package, the instruction in the readme le directs how to install NL2KR. 3.3
Following is a brief list of important les/folders in the package: { README: Installation instruction and examples of how to use NL2KR. { NL2KR.jar: NL2KR's classes packed in a jar le. { con g.properties: Default con guration of the NL2KR system. { install.sh: Script to install NL2KR. { ccgParser.sh: Script to get a CCG parse tree of a given sentence. { Generalization.sh: Script that gives generalized meanings of a word. { Inverse.sh: Script to compute the inverse using the inverse lambda algorithms. { Lambda.sh: Script to do application operation, given a function and an argument in -calculus. { NL2KR-L.sh: Script to run the NL2KR-L sub-part. { NL2KR-T.sh: Script to run the NL2KR-T sub-part. { RunCon guration: Example inputs of the preceding scripts. { resources: Folder containing AspCcgTk package, gringo, clasp and clingo. { examples: Folder containing examples in various domains for NL2KR-L and
NL2KR-T. 1 http://www.kr.tuwien.ac.at/sta /former sta /ps/aspccgtk 2 http://nlp.stanford.edu/software/tagger.shtml 3 http://potassco.sourceforge.net/
To execute any of the scripts one needs to go to the NL2KR's root directory and run
./ < script name > < RunConfiguration file > [ Optional params ] where script name is the name of one of the six scripts (e.g. ./Lambda.sh), RunCon guration le contains corresponding parameters for the script, and optional parameters are for the Java Virtual Machine (JVM) to execute the module that corresponds to the script. For learning and testing large dataset with NL2KR-L or NL2KR-T, it is recommended to provide more memory for the JVM and enable garbage collection if needed (i.e. Use -Xmx and -XX:
3.5
To use the lambda application script, the function and the argument of the lambda application need to be provided. For example, the following snippet in the RunCon guration le speci es that we need to apply the argument #x:x@mia to the function #y:#x:loves(x; y) (note: # is for ).
However, in the following con guration, the argument cannot be applied to the function since there is no free variable in the function.
3.6
Given two lambda expressions g and h, the lambda application gives us f = g@h
or f = h@g. But sometime, we have only f and g and we need to nd h. The
inverse application allow us to calculate the lambda expression h so that f = g@h
or f = h@g. More details about the inverse application can be found in [
In the rst example below, since there does not exist a lambda expression h (right child) so that mia@h = #x:loves(x; mia), the inverse algorithm returns right child expression = null. However, when mia is the right child, inverse lambda returns Lef tchild = #x1:#x:loves(x; x1) because #x1:#x:loves(x; x1)@mia = #x:loves(x; mia). In case the CCG parse tree speci es that the meaning of \Mia" must be in the left child, using left child as #x:x@mia instead of mia will do the trick and let us have the same right child: #x1:#x:loves(x; x1). Example 1. Input: parent =# x. loves (x , mia ) left_child = mia
Parent = #x. loves (x , mia ) Left child = mia Right child = null Example 2. Input: parent =# x. loves (x , mia ) right_child = mia
Parent = #x. loves (x , mia ) Right child = mia Left child = # x1 .# x. loves (x , x1 ) Example 3. Input:
Parent = #x. loves (x , mia ) Left child =# x.x @ mia Right child = # x1 .# x. loves (x , x1 ) 3.7
The inverse lambda module is not always adequate to learn new meanings of
words when we lack meaning of words that will allow us to use the inverse
lambda module. To address that we have developed a generalization module in
NL2KR system, where the generalization technique described in [
In this case, the word Mia can be obtained by generalization from the words Vincent, plane and boxers, each of category N (meaning noun); and the output is
New lexical items learned through Generalization : Mia [N] #x. mia (x) Mia [N] mia
We can restrict generalization by modifying the con g.properties le. For example, adding the following snippet to con g.properties will skip the generalization process for NP and N categories, and generalization for the words: on, of, by and in. 3.8
GENERALIZATION_D_EXCLIST =[ NP ] ,[N]
GENERALIZATION_D_PREPOSITIONLIST =on ,of ,by , in
The input of the CCG parser module is the sentence we want to parse and an
optional path of the le containing the words and their additional categories
we want to use. The parser will parse the input sentence and output its CCG
parse tree. Our CCG parser is based on ASP ccgT k [
sentence =' Every boxer walks ' syntaxFile =./ examples / sample / syntax . txt where syntax.txt contains takes (S\ NP )/ NP Every (S /( S\ NP ))/ NP Some (S /( S\ NP ))/ NP walks S\ NP fights S\ NP loves (S\ NP )/ NP walks" in ASP format as follows nl2kr_token (t1 , " Every ", "( S /( S\ NP ))/ NP ", 1) . nl2kr_token (t2 , " boxer ", " NP ", 2) . nl2kr_token (t3 , " walks ", "S\ NP ", 3) . nl2kr_token (t4 , " Every boxer ", "S /( S\ NP ) " ,1) . nl2kr_token (t5 , " Every boxer walks ", "S", 1) . nl2kr_child_left (t4 , t1 ). nl2kr_child_right (t4 , t2 ). nl2kr_child_left (t5 , t4 ). nl2kr_child_right (t5 , t3 ). nl2kr_valid_rootNode ( t5 ).
The output of the CCG parser is a parse tree of the sentence \Every boxer The predicate nl2kr valid rootN ode is used to specify the root node of the parse tree (corresponds to the whole sentence). nl2kr token is used to specify nodes in the tree and nl2kr child lef t, nl2kr child right are for the left child and the right child of a node. The four atoms of nl2kr token are respectively the node ID, the corresponding phrase, its CCG category and its starting position in the sentence. 3.9
NL2KR-L: the learning module of NL2KR To run the learning module NL2KR-L we need to set the initial lexicon le path, the override le for syntax categories (optional), the training data le and the output dictionary le path (optional) in the RunCon guration le of the
Ldata =./ examples / sample / train . txt Ldictionary =./ examples / sample / dictionary . txt Lsyntax =./ examples / sample / syntax . txt Loutput =./ examples / sample / dictionary_train . out For example, the preceding snippet speci es that: the training data is in ./examples/train.txt, the initial lexicon is in ./examples/sample/dictionary.txt, and the override syntax categories are in ./examples/sample/syntax.txt. The override syntax categories will be used in CCG parsing step as showed in the previous subsection. If it is not speci ed, the output dictionary is saved as dictionary train.out in ./output folder.
The training data le contains the training sentences and their formal representation such as: Some boxer walks EX . ( boxer (X) ^ walk (X)) John takes a plane EX . ( plane (X) ^ takes ( john , X)) John walks walk ( john ) In the above, EX denotes 9X.
The initial lexicon contains words and the their meanings that we already know: 5
John N john takes (S\ NP )/ NP #w. #z. ( w@ #x. takes (z ,x) ) plane N #x. plane (x) boxer N #x. boxer (x) fights S\ NP #x. fight (x)
The NL2KR-L sub-part learns the new meanings of words in multiple iterations. It stops when it cannot learn any new word. Below we give the output of the script with example inputs.
We start with some snippets of the running output in the following. From line 5 to 9, NL2KR-L was checking if it has the meaning of Some boxer and walks. It then learned the meaning of walks by generalization.
From line 15 to 19, NL2KR-L was trying to learn the meaning of Some boxer given the meaning of walks and the meaning of the whole sentence Some boxer walks from the training data. Using inverse lambda, it gured out that the meaning of Some boxer is #x1:EX:boxer(X) ^ x1@X.
NL2KR-L did not go further to the meaning of \some" because the meaning \boxer" of boxer was not helpful. 5 10 15 20 25 30 35 40 45 5
However, using the second parse tree where the meaning #x:boxer(X) of boxer is used, NL2KR-L can get the meaning of some (line 42-49) : #x2:#x1:EX:x2@X^ x1@X. ****** Learning lexicon ... ...
Processing sentence number 1 Processing Parse Tree 1 Word : Some boxer walks sem :: null Both children do not have current lambda expression : Some boxer , walks Generalizing for leafs with no expected lambda : walks New lexical item Learned by Expansion : walks ////[ S\ NP ]////# x. walk (x) ...
Processing sentence number 1 Processing Parse Tree 1 Word : Some boxer walks sem :: null Applying inverse : EX . boxer (X) ^ walk (X) #x. walk (x) INVERSE_L Tried : Some boxer walks (H) = EX . boxer (X) ^ walk (X) walks (G) = #x. walk (x) Some boxer (F) = # x1 . EX . boxer (X) ^ x1 @ X Word : walks sem ::# x. walk (x) Word : Some boxer sem :: null Applying inverse : # x1 . EX . boxer (X) ^ x1 @ X boxer INVERSE_L Tried : Some boxer (H) = # x1 . EX . boxer (X) ^ x1 @ X boxer (G) = boxer Some (F) = null Generalizing for leafs with no expected lambda : Some Generalizing for leafs with no expected lambda : boxer Word : boxer sem :: boxer Word : Some sem :: null Processing Parse Tree 2
At the end of the learning phase, parameter estimation is run to assign the weights for each meaning of words. NL2KR-L then uses those meanings to check if they are enough to translate the training sentences correctly. ****** Evaluation on training set ...
Processing training sentence : Some boxer walks Predicted Result : EX . boxer (X) ^ walk (X) Correct Prediction Processing training sentence : John takes a plane Predicted Result : EX . plane (X) ^ takes ( john ,X)
Correct Prediction 10 5 10 15 5 5
Following is the output lexicon learned with the example inputs mentioned earlier. Each row contains a word, its CCG category, its meaning and the associated weight. Compared to the initial dictionary, we can see that NL2KR-L learned 14 more word meanings. Note that some words such as likes and eats are in the \syntax.txt". In this subsection, we present an example of using NL2KR-L for the GEOQUERY4 domain. GEOQUERY uses a Prolog based language to query a database with geographical information about the U.S. The input of NL2KR-L is speci ed in the RunCon guration le as: Ldata =./ examples / geoquery / train . txt Ldictionary =./ examples / geoquery / dictionary . txt Lsyntax =./ examples / geoquery / syntax . txt Loutput = where ./examples/geoquery/train.txt contains How large is texas answer (X) ^ size (B ,X) ^ const (B ,sid , texas ) How high is mountmckinley answer (X) ^ elevation (B , X) ^ const (B ,
pid , mountmckinley ) How big is massachusetts answer (X)^ size (B , X) ^ const (B ,
sid , massachusetts ) How long is riogrande answer (X)^ len (B , X) ^ const (B , rid , riogrande ) How tall is mountmckinley answer (X)^ elevation (B , X)^ const (B ,
pid , mountmckinley ) ./examples/geoquery/dictionary.txt contains How S/S #x. answer (X) ^ x@X texas NP #x. const (x ,sid , texas ) mountmckinley NP #x. const (x ,pid , mountmckinley ) massachusetts NP #x. const (x ,sid , massachusetts ) riogrande NP #x. const (x ,rid , riogrande ) is (S\ NP )/ NP #y. #x.x @ y
and ./examples/geoquery/syntax.txt contains 4 http://www.cs.utexas.edu/users/ml/geo.html 5 10 15 5 10 15 20 How S/S texas NP mountmckinley massachusetts riogrande NP is (S\ NP )/ NP rivers NP large NP is (S\ NP )/ NP high NP big NP long NP the NP / NP How S /( S\ NP ) long S\ NP tall NP colorado NP arizona NP
NP
NP
After the learning module is executed, 15 more word meanings were learned by NL2KR-L and the result is: is [( S\ NP )/ NP ] #y .# x.x @ y -0.0015125279 texas [ NP ] #x. const (x ,sid , texas ) 0.07666666 texas [ NP ] #x. const (x ,rid , texas ) -0.023256822 texas [ NP ] #x. const (x ,pid , texas ) -0.023256822 riogrande [ NP ] #x. const (x ,pid , riogrande ) -0.02315781 riogrande [ NP ] #x. const (x ,rid , riogrande ) 0.07646726 riogrande [ NP ] #x. const (x ,sid , riogrande ) -0.02315781 mountmckinley [ NP ] #x. const (x ,sid , mountmckinley ) -0.055226557 mountmckinley [ NP ] #x. const (x ,pid , mountmckinley ) 0.14075616 mountmckinley [ NP ] #x. const (x ,rid , mountmckinley ) -0.055226557 massachusetts [ NP ] #x. const (x ,rid , massachusetts ) -0.023190754 massachusetts [ NP ] #x. const (x ,sid , massachusetts ) 0.0765336 massachusetts [ NP ] #x. const (x ,pid , massachusetts ) -0.023190754 long [ NP ] # x3 .# x1 . len (B , x1 ) ^ x3 @ B 0.010111484 How [S/S] #x. answer (X) ^ x @ X 0.009999999 high [ NP ] # x3 .# x1 . elevation (B , x1 ) ^ x3 @ B 0.010112147 big [ NP ] # x3 .# x1 . size (B , x1 ) ^ x3 @ B 0.010111821 tall [ NP ] #x. const (x ,rid , tall ) -0.014923776 tall [ NP ] #x. const (x ,pid , tall ) -0.014923776 tall [ NP ] # x3 .# x1 . elevation (B , x1 ) ^ x3 @ B 0.084677815 tall [ NP ] #x. const (x ,sid , tall ) -0.014923776 large [ NP ] # x3 .# x1 . size (B , x1 ) ^ x3 @ B 0.010112498 3.11
NL2KR-T: the translation sub-part of NL2KR Similar to NL2KR-L, in the RunCon guration le of NL2KR-T, we need to set the lexicon le path, the override le for syntax categories(optional), and the testing data le as given below: Tdata =./ examples / sample / test . txt Tdictionary =./ output / dictionary_train . out Tsyntax =./ examples / sample / syntax . txt For example, the preceding snippet speci es that: the testing data is in ./examples/sample/test.txt, the lexicon is in ./output/dictionary train.out, and the override syntax categories are in ./examples/sample/syntax.txt.
The content of ./examples/sample/test.txt is Mia sleeps sleep ( mia ) John catches a bus
EX . ( bus (X) ^ catches ( john , X)) ****** Parsing Sentences ... ...
Parsing test sentence : John catches a bus Expected Representation : EX . ( bus (X) ^ catches ( john , X)) Generalizing bus = [ bus : [N] : #x. bus (x) , bus : [N] : bus ] Generalizing catches = [ catches : [( S\ NP )/ NP ] : #w .# z.w @ #x. catches (z ,x)] Predicted Result : EX . bus (X) ^ catches ( john ,X) Correct Prediction ...
Note that the expected translation in \test.txt" is optional. Without it, the evaluation is not correct but NL2KR-T still gives its results. 4
In this work, we presented the NL2KR system, which is used for translating natural language to a formal representation. The input of the NL2KR system are training sentences and their formal representation; and an initial lexicon of some known meanings of words. NL2KR system will try to learn the meaning of others words from the training data. We presented six scripts to execute several modules of NL2KR and show how to use them through examples.
In the future, we plan to make NL2KR more scalable and add more features to the NL2KR system such as (1) automatically constructing the initial lexicon and (2) using more knowledge such as word sense to select the correct meaning of words.