{"id":912,"date":"2018-04-22T09:11:15","date_gmt":"2018-04-22T03:41:15","guid":{"rendered":"http:\/\/www.rangakrish.com\/?p=912"},"modified":"2018-04-22T11:09:31","modified_gmt":"2018-04-22T05:39:31","slug":"question-answering-using-dependency-trees","status":"publish","type":"post","link":"https:\/\/www.rangakrish.com\/index.php\/2018\/04\/22\/question-answering-using-dependency-trees\/","title":{"rendered":"Question Answering\u00a0Using Dependency Trees"},"content":{"rendered":"

A few weeks ago I had written about my brief experiment with Mathematica’s new feature<\/a>, which provides answers to questions based on given text. After that post, I spent some time thinking about how to implement something similar. In today’s post, I want to show you what I have been able to do in the last two weeks.<\/p>\n

Here is what the QA system (a bit naive for now) will attempt to do:<\/p>\n

(1) Given a piece of text, it will build an internal representation of the text<\/p>\n

(2) When asked a direct<\/strong><\/em> question, it will find the sentences in the text, which match the question, and print the complete sentences<\/p>\n

Let me elaborate item (2) further. A direct<\/strong><\/em> question is one that does not require inferencing, or looking beyond the given text for an answer. Suppose the text is Peter eats a lot of sweets even though he is diabetic<\/strong><\/em>, a direct question could be What does Peter eat?<\/strong><\/em>, but not What is diabetes?<\/strong><\/em><\/p>\n

Also, the system will print the complete matching sentence(s) even though the answer is contained in a part of the sentence. Thus, when asked the question What does Peter eat?<\/strong><\/em>, the system will respond Peter eats a lot of sweets even though he is diabetic, <\/strong><\/em>and not just\u00a0Peter eats a lot of sweets.<\/em><\/strong><\/p>\n

Clearly, these are limitations, but we can live with these for now.<\/p>\n

Dependency trees are used widely in NLP these days. Efficient parsers and 3rd party libraries are available for this purpose. Here is an example dependency tree for the sentence Peter likes salad.<\/strong><\/em><\/p>\n

\"Dependency<\/a>
Dependency Tree<\/strong><\/figcaption><\/figure>\n

Here is one more example. The sentence Vicky is my pet dog<\/strong><\/em> will have the following representation:<\/p>\n

\"Another<\/a>
Another Dependency Tree Example<\/strong><\/figcaption><\/figure>\n

My strategy is the following:<\/p>\n

1) Parse the given text into dependency trees and prepare N-tuples of the form:<\/p>\n

<sentence-id, dependency-label, head-word, tail-word><\/strong><\/span><\/p>\n

2) Parse the question into a dependency tree and prepare N-tuples of the form:<\/p>\n

<question-id, dependency-label, head-word, tail-word><\/strong><\/span><\/p>\n

3) Convert all N-tuples to logical clauses for efficient matching\/unification. I will be using LispWorks Lisp, which includes a Prolog engine.<\/p>\n

Parsing the text and question into corresponding dependency trees can be done using spaCy<\/strong><\/em><\/a>\u00a0or using commercial APIs such as TextRazor<\/a><\/strong><\/em>. I decided to use spaCy<\/strong><\/em>. This posed a minor challenge because it is a Python library, but my implementation is in Lisp. To facilitate the interaction, I wrote a Python REST server (using Flask framework<\/strong><\/em><\/a>) that would parse the submitted text using spaCy<\/strong><\/em> and send back N-tuples as result. This way, my Lisp program can easily communicate with the local REST server to parse the text.<\/p>\n

For example, the sentence Vicky is my pet dog.<\/strong><\/em>, when sent to the REST server, returns the following structure:<\/p>\n

(DEFSENT S1 “Vicky is my pet dog.”\u00a0<\/span><\/strong><\/span><\/p>\n

(NSUBJ “is” “vicky”)\u00a0<\/span><\/strong><\/span><\/p>\n

(ROOT “is” “is”)\u00a0<\/span><\/strong><\/span><\/p>\n

(POSS “dog” “my”)\u00a0<\/span><\/strong><\/span><\/p>\n

(AMOD “dog” “pet”)\u00a0<\/span><\/strong><\/span><\/p>\n

(ATTR “is” “dog”)\u00a0<\/span><\/strong><\/span><\/p>\n

(PUNCT “is” “.”))<\/strong><\/span><\/p>\n

This structure will be evaluated by the Lisp client to build the Prolog-compatible clauses for further processing. In the same manner, all sentences of the given text as well as the questions will be converted to the above format.<\/p>\n

OK, let us look at an actual interaction to understand how well the system performs.<\/p>\n

First, we give the whole text (5 sentences in this example) and ask the system to build a model:<\/p>\n

\"Building<\/a>
Building a Model from Text<\/strong><\/figcaption><\/figure>\n

The function parse-text<\/strong><\/em> sends the text to the spaCy<\/strong><\/em> server running on the same machine and evaluates the returned N-tuples to build a model.<\/p>\n

Let us ask a question:<\/p>\n

\"Question-1\"<\/a>
Question-1<\/strong><\/figcaption><\/figure>\n

The function answer-the-question<\/strong><\/em> takes a model and a question. It sends the question to the server and gets an N-tuple of the question, and then passes it to the model to find a match for the question. If there is a valid match (multiple sentences could match a question), the result is returned.<\/p>\n

Here are some more examples:<\/p>\n

\"Question-2\"<\/a>
Question-2<\/strong><\/figcaption><\/figure>\n

 <\/p>\n

\"Question-3\"<\/a>
Question-3<\/strong><\/figcaption><\/figure>\n

 <\/p>\n

\"Question-4\"<\/a>
Question-4<\/strong><\/figcaption><\/figure>\n

Notice how, for the last question, the system gives the complete sentence as reply although the best answer would be\u00a0He is 5 years old.<\/strong><\/em><\/p>\n

Looks promising, isn’t it? Does it mean it is perfect? Of course not. Here is a simple question that the system is not able to handle:<\/p>\n

\"This<\/a>
This Question Fails<\/strong><\/figcaption><\/figure>\n

What happened? Easy to guess. Whereas the actual text contains the pronoun He<\/strong><\/em>, the question uses the word Vicky<\/strong><\/em>, and hence the subject of the question and that of the potentially short-listed sentence do not match. This happens because we have not performed\u00a0coreference resolution<\/strong><\/em><\/a>. This is a common requirement in any text understanding system.<\/p>\n

For now, this is a good start. In the next post, I will discuss how we can address this problem.<\/p>\n

Have a nice weekend!<\/p>\n","protected":false},"excerpt":{"rendered":"

A few weeks ago I had written about my brief experiment with Mathematica’s new feature, which provides answers to questions based on given text. After that post, I spent some time thinking about how to implement something similar. In today’s post, I want to show you what I have been able to do in the […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[18,107,17],"tags":[140,138],"class_list":["post-912","post","type-post","status-publish","format-standard","hentry","category-lisp","category-natural-language-processing","category-programming","tag-dependency-tree","tag-question-answering"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p9OLnF-eI","jetpack-related-posts":[{"id":870,"url":"https:\/\/www.rangakrish.com\/index.php\/2018\/03\/25\/question-answering-in-mathematica\/","url_meta":{"origin":912,"position":0},"title":"Question Answering in Mathematica","author":"admin","date":"March 25, 2018","format":false,"excerpt":"About 10 days ago, I received an update for Mathematica. The latest version is 11.3.0. As usual, I looked through the list of new features\u00a0in this release. There are several new features, but one of them attracted my attention immediately: There is a new function FindTextualAnswer\u00a0that, given a piece of\u2026","rel":"","context":"In "Mathematica"","block_context":{"text":"Mathematica","link":"https:\/\/www.rangakrish.com\/index.php\/category\/mathematica\/"},"img":{"alt_text":"Example 1","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2018\/03\/Example1.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2018\/03\/Example1.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2018\/03\/Example1.png?resize=525%2C300 1.5x"},"classes":[]},{"id":1068,"url":"https:\/\/www.rangakrish.com\/index.php\/2018\/09\/16\/dependency-graph-to-rdf\/","url_meta":{"origin":912,"position":1},"title":"Dependency Graph to RDF","author":"admin","date":"September 16, 2018","format":false,"excerpt":"Dependency parsing is widely used these days, and many NLP tools give a dependency graph as the parsed representation of the input text. See for example, SpacY and TextRazor.\u00a0 The following is the dependency tree corresponding to the sentence Mary is drinking cold water: The above tree was generated using\u2026","rel":"","context":"In "Natural Language Processing"","block_context":{"text":"Natural Language Processing","link":"https:\/\/www.rangakrish.com\/index.php\/category\/natural-language-processing\/"},"img":{"alt_text":"Dependency Graph","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2018\/09\/DepGraph.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2018\/09\/DepGraph.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2018\/09\/DepGraph.png?resize=525%2C300 1.5x"},"classes":[]},{"id":1863,"url":"https:\/\/www.rangakrish.com\/index.php\/2020\/01\/02\/book-review-automatic-text-simplification\/","url_meta":{"origin":912,"position":2},"title":"Book Review – Automatic Text Simplification","author":"admin","date":"January 2, 2020","format":false,"excerpt":"Title: Automatic Text Simplification Author: Horacio Saggino Publisher: Morgan & Claypool Publishers Year: 2017 Automatic Text Simplification is an active area of research in NLP and has been going on for over 20 years. The idea is to transform a given text T1 into text T2 such that T2 is\u2026","rel":"","context":"In "Book Review"","block_context":{"text":"Book Review","link":"https:\/\/www.rangakrish.com\/index.php\/category\/book-review\/"},"img":{"alt_text":"Automatic Text Simplification","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2020\/01\/IMG_1496-edited-225x300.jpeg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":1870,"url":"https:\/\/www.rangakrish.com\/index.php\/2020\/01\/19\/experimenting-with-text-simplification\/","url_meta":{"origin":912,"position":3},"title":"Experimenting with Text Simplification","author":"admin","date":"January 19, 2020","format":false,"excerpt":"After my last book review, I decided to check out a few websites that claim to simplify English text and\/or help compute the measure of readability. In today\u2019s post, I am sharing the results of my experiment. www.simplish.org This site has some interesting functionality. It does spelling check, grammar check,\u2026","rel":"","context":"In "Natural Language Processing"","block_context":{"text":"Natural Language Processing","link":"https:\/\/www.rangakrish.com\/index.php\/category\/natural-language-processing\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":1541,"url":"https:\/\/www.rangakrish.com\/index.php\/2019\/04\/21\/textcontents-function-in-mathematica-12\/","url_meta":{"origin":912,"position":4},"title":"TextContents[ ] Function in Mathematica 12","author":"admin","date":"April 21, 2019","format":false,"excerpt":"Mathematica 12 was released a few days ago.\u00a0 It has been over a year since version 11.3 came out in March 2018. The long wait appears justified since the new release boasts of numerous improvements and new features across several areas. You may want to read this blog post\u00a0by Stephen\u2026","rel":"","context":"In "Mathematica"","block_context":{"text":"Mathematica","link":"https:\/\/www.rangakrish.com\/index.php\/category\/mathematica\/"},"img":{"alt_text":"Importing Text File","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/04\/FileImport.png?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/04\/FileImport.png?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/04\/FileImport.png?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":2131,"url":"https:\/\/www.rangakrish.com\/index.php\/2020\/09\/13\/mathematica-using-textcases-to-extract-information-from-natural-language-text\/","url_meta":{"origin":912,"position":5},"title":"Mathematica: Using TextCases to Extract Information from Natural Language Text\u00a0","author":"admin","date":"September 13, 2020","format":false,"excerpt":"Extracting meaningful information from unstructured, human readable text is a hot topic of research today and has important applications in many domains. I have written a few blogs related to this topic, for example, see this\u00a0and this. In today\u2019s article, I would like to show how Mathematica can be a\u2026","rel":"","context":"In "Mathematica"","block_context":{"text":"Mathematica","link":"https:\/\/www.rangakrish.com\/index.php\/category\/mathematica\/"},"img":{"alt_text":"Extracting Sentences","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2020\/09\/ex1-2-300x106.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]}],"_links":{"self":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/912","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/comments?post=912"}],"version-history":[{"count":0,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/912\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/media?parent=912"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/categories?post=912"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/tags?post=912"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}