Application of Natural Language Processing for Use ... - Vijay Upadhya [PDF]

             

Application of Natural Language Processing for Use in Reasoning Machines  Vijay Upadhya  Montgomery Blair High School  Mentors: Dr. Don Perlis and Dr. Darsana Josyula,   University of Maryland 

                         

1 

Abstract  Natural Language Processing deals with understanding human languages, and processing  them in different ways. This is a main  component of machines that interact with humans and  adjust their behavior based on these interactions, such as Siri or Wolfram Alpha. Another such  machine in progress is Alfred (Active Logic For Reason Enhanced Dialogue). Alfred aims to  take input commands and try executing them in certain domains. To do this, Alfred would need  to have background information about the domain, but also fully understand the command. This  paper deals with identifying certain features of the commands for Alfred, such as spatial sources  or destinations within the commands. Toward this end, a program in Prolog was created and  tested with a set of sentences. It used a grammar parser and looked for certain relationships from  the parsed sentences to identify features of the sentence. For the majority of the sentences, the  program was successful. The situations in which the method for identifying these features  deviates from the expected values are discussed, as well as ways to avoid these situations.                    

2 

Introduction  Natural Language Processing (NLP) has many applications today , among which are  conversational and reasoning machines.  NLP can help such machines understand and recreate  dialogue, and learn from dialogue held with a user[1]. There are many ways of going about  understanding dialogue, and various parsers exist to assist machines in doing this.   The Link Parser by Carnegie Mellon University (CMU) is one such parser that takes in  sentences as input[2]. The output is a combination of the parts of speech of certain words it  recognizes, and  “links” between words. These links were made by CMU, and have very specific  rules and conditions for two words or phrases to be connected by that link. For example, the  sentence “Send the box from here to my apartment” would have a parser output as shown in  Figure 1.  One reasoning machine using NLP is Alfred (Active Logic For Reason Enhanced  Dialogue). Alfred turns input sentences into commands in specific domains[3]. Alfred will not  fully understand the command based on the sentence alone, however, as it must contain  knowledge about the domain. This knowledge is stored in its own dictionary of the domain, or  knowledge base[4].   This project helps Alfred understand certain things about the commands given to it in  each domain, and uses this information to more accurately interpret those commands. A program  was written that used the Link Parser to break down the command, and looked at combinations  of links in the sentence, which tells Alfred more about the command. Here, specific links are  used to determine the presence of spatial destinations and sources in the commands. If they are  present, this information was added to Alfred’s concept space, so the knowledge Alfred has can 

3 

be represented in more detail. A more complete knowledge base would help Alfred understand  and execute commands[5].     Methods  Parser­Side Procedure  The Link Parser was first connected to a stand­alone client written in Prolog. This  connection was neither an actual Transmission Control Protocol (TCP) nor a Secure Sockets  Layer (SSL) connection, but rather a means of communicating through a medium. In this case,  the medium was a text file. Once it was certain that both the parser and the client could access  the file, sentences could be parsed. For the scope of this project, a set of sentences was chosen,  where ideally the client would be able to identify certain things about each sentence, such as  whether or not there was a spatial destination. These sentences would then be fed to the parser,  which would send information about the parsed sentence to the intermediary text file. Each parse  contained information identifying the sentence, the links between each of the words in the  sentences, which words were identified as verbs, nouns, or adjectives, and which variables were  associated with which words. After the last sentence sentence was typed into the parser, typing  “close” would then close the connection to the text file and signify the end of all the desired  sentences. Closing this connection was necessary because if the connection between file and  parser were left open, the client would not be able to read information from the file. All the  information in the text file was in the format of Prolog facts and rules that were ready to be  inserted into the client’s database of relationships. This format was simply Prolog snippets put 

4 

into strings from the parser, like ready­made Prolog code. The general procedure of the program  is outlined by Figure 2.   Client­Side Procedure  The client then reads the information from the file, inserting each of the facts line by line.  Once the information is stored, the program can then determine features about the sentence, such  as the existence of spatial sources and destinations. The program would begin by determining  whether or not there was a ‘J’ link between any of the words. The J link signifies the connection  between a preposition and the object, and if the ‘J’ existed in the target sentence, that would have  been indicated in the set of information the parser put into the file. By searching for the J link, it  would really be searching for things of the form of “from Alaska” or “to Alaska”, in this case  anything related to a place. The client would also search for an ‘MV’ link, which signifies the  connection between a verb and a modifying phrase. Then, different combinations of ‘MV’ and  ‘J’ links were searched for, which would signify spatial sources or destinations. Oftentimes, the  combination for sources and destinations would be similar, so to distinguish between them,  certain words within the sentences were searched for. If words associated with destinations like  ‘to’ were present in the combination, the object of the ‘J’ link would be specified as a  destination. However, if words associated with sources were found, like ‘from’, it would be  specified as a source. If either relationship was found in a sentence, it would also be inserted into  the database. In addition, the direct object to which the verb was applied to was also identified  using an ‘O’ link (verb to object connection), and was also inserted into the database. This was  done for each of the sentences in the chosen list.   Results 

5 

To assess the program, the sources, destinations, and objects within each sentence in  Figure 3 were determined and then compared to the output of the program. This comparison is in  Figure 4. The program successfully determined whether or not certain sentences contained  spatial sources or destinations for some of the chosen sentences. However, it only worked for  sentences that had correct parses, and for sentences with certain words it recognized, like ‘to’  and ‘from’. All of the objects were identified correctly based on their O linkages, and if there  were sources or destinations, they were identified in the cases where there was a ‘to’ or ‘from’  along with the ‘J’ and ‘MVp’ link. However, in the case of sentences 6 and 7(Figure 3), there  were no sources identified, though there seem to be some. Also in sentence 6, there were no  destinations identified, though the door seems to be one as well. However with the exceptions of  sentences 6 and 7, the program worked for all the other cases, inserting the appropriate  information into the knowledge base.   Illustrations     

  Figure 1: An example of the output of the Link Parser is shown here. The dashed lines line up with words in the  sentence, and the letters in the lines are the links designated to those words.  

6 

  Figure 2: Outlines the basic structure and process of the program. 

 

   Figure 3: A list of the tested sentences.        7 

   

Actual  Source 

Observed  Source 

Actual  Observed  Destination  Destination 

Actual  Object 

Observed  Object 

Sentence 1 

none 

none 

none 

none 

the  block 

the block 

Sentence 2 

none 

none 

LocationA 

LocationA 

the red  block 

the red  block 

Sentence 3 

the door 

the door 

none 

none 

the toys  the toys 

Sentence 4 

Baltimore 

Baltimore 

Chicago 

Chicago 

the blue  the blue  parcel  parcel 

Sentence 5 

the windy  city 

the windy  city 

the east  coast 

the east  coast 

the bus 

the bus 

Sentence 6 

none/the  door 

none 

the  door/none 

the  door/none 

the  block 

the block 

Sentence 7 

the door 

none 

the other  room 

the other  room 

the  pillow 

the pillow 

Figure 4: The results of the program with the sentences from Figure 3. For sentence 6, there are 2 possible  interpretations of the sentence, so two are listed.     

  Figure 5: This shows two different interpretations of the same sentence by the parser. 

  Discussion  Figure 4 shows that for a majority of the cases, the program does work and is able to  identify sources, destinations, and objects within sentences. However, the cases in which the 

8 

program failed are interesting to note because of the double meaning of the command. The  command was “Push the block at the door.” This command is ambiguous, as it could mean to  push the block in the direction of the door, or to push the block currently located at the door.  This ambiguity leads to two different parses for the sentence(Figure 5), and the program does not  know which parse to use. The procedure of breaking it down to ‘MVp’ and ‘J’ links would have  worked with the first parse, identifying the door as the destination, but not the second. The  second parse would identify the door as the source. So, the procedure fails in the case where  there are differing parses. Additionally, ‘at’ cannot be definitively associated with words  identifying sources or destinations, because it could be used in both cases.   The program does work for the remaining cases, meaning it is reliable when there is one  main interpretation for the command. Searching for certain combinations of links and words  within the sentences was useful for learning things about the sentences, and so would help  Alfred’s understanding of the command and the domain. This approach is slightly different than  others in finding features of sentences or multiple sentences in that it uses the Link Parser, which  breaks down the sentence, then uses this information. Other research used probabilistic methods  and large data sets to train the machine to find features[6].   Conclusions and Future Work  This procedure of using different combinations of links given by the parser was very  useful for determining things about the sentence, in this case the existence of sources and  destinations with the commands. Although the procedure didn’t correctly identify features for  ambiguous commands, this can be fixed by devising a way to let the program know which  specific parse is desired. Additionally, Since the procedure worked fairly well for these features 

9 

in other cases, it can be extended to finding more about the commands, such as temporal  concepts, or starting and ending times for actions. Doing this will let Alfred understand more  about the specific domain in which it is in, and possibly learn faster.   References  [1] 

University of Sheffield NLP page, http://nlp.shef.ac.uk/research/dialogue.html , accessed 

september 2014   [2] 

Carnegie Mellon University, http://www.link.cs.cmu.edu/link/, 2012 

[3]

M. Anderson, D. Josyula, D. Perlis, K. Purang., Active Logic for More Effective 

Human­Computer Interaction and Other Commonsense Applications, In Proceedings of the  Workshop on Empirically Successful First Order Reasoning at the Second International Joint  Conference on Automated Reasoning, (IJCAR 2004).  [4] 

D. Perlis, <. Cox, M. Maynord, E. McNany, M. Paisner, V. Shivashankar, J. Shamwell, 

T. Oates, T.­C. Du, D. Josyula, M. Caro. A broad vision for intelligent behavior: perpetual  real­world cognitive agents., Submitted 2013  [5]

D. Josyula, S. Fults, M. Anderson, S. Wilson and D. Perlis, Application of MCL in a 

Dialog Agent, In Papers from the Third Language and Technology Conference (L&TC ­07) ,  2007  [6]

N. Agarwal, K. Ford, M. Shneider, Sentence Boundary Detection Using a MaxEnt 

Classifier, Stanford University,  http://nlp.stanford.edu/courses/cs224n/2005/agarwal_herndon_shneider_final.pdf , 2005 

10