{"id":1792,"date":"2019-11-23T14:36:29","date_gmt":"2019-11-23T09:06:29","guid":{"rendered":"https:\/\/www.rangakrish.com\/?p=1792"},"modified":"2019-11-23T14:52:11","modified_gmt":"2019-11-23T09:22:11","slug":"using-augmented-transition-networks-atn-for-information-extraction","status":"publish","type":"post","link":"https:\/\/www.rangakrish.com\/index.php\/2019\/11\/23\/using-augmented-transition-networks-atn-for-information-extraction\/","title":{"rendered":"Using Augmented Transition Networks (ATN) for Information Extraction"},"content":{"rendered":"

After Wood\u2019s paper [1], Augmented Transition Networks<\/strong><\/em>\u00a0(ATN)<\/strong><\/em> became popular in the 1970s, for parsing text. An ATN is a generalized transition network with two major enhancements:<\/p>\n

    \n
  1. Support for recursive transitions, including jumping to other ATNs<\/li>\n
  2. Performing arbitrary actions when edges are traversed<\/li>\n
  3. Remembering state through the use of registers<\/strong><\/em><\/li>\n<\/ol>\n

    See the \u201cFurther Reading\u201d<\/strong> section at the end of this article for some good reading material on ATNs.\u00a0<\/span><\/p>\n

    Although the ATN formalism is quite powerful, because of its procedural<\/strong><\/em> nature, it tends to be fairly verbose. For this reason, designing and maintaining any non-trivial ATN grammar requires considerable effort.<\/p>\n

    Definite Clause Grammar<\/strong> <\/em>[5], introduced by Pereira and Warren in 1980, was implemented in Prolog<\/strong><\/em> and was shown to be clearer and more compact than ATN for the same problem. (I have also written an article<\/strong><\/em><\/a> on using DCG in Lisp.)<\/p>\n

    Without getting into any discussion (or debate) on whether ATNs are still relevant for solving general parsing problems, in today\u2019s article I would like to show how we can use ATNs to extract meaningful information from unstructured text.\u00a0<\/span><\/p>\n

    A Simple Grammar<\/h2>\n

    Let me start first with highly simplified English grammar for parsing a sentence made up of a noun phrase<\/strong><\/em> and a verb phrase<\/strong><\/em>:<\/p>\n

    \"Simple<\/a>
    A Simple ATN Grammar<\/strong><\/figcaption><\/figure>\n

    The above grammar defines 3 ATNs, namely, Sentence<\/strong><\/em>, NP<\/strong><\/em> and VP<\/strong><\/em>. The Sentence<\/strong><\/em> ATN has 3 nodes, whereas the NP<\/strong><\/em> and VP<\/strong><\/em> nodes each have 2 nodes. Control starts at the start<\/strong><\/em> node of Sentence<\/strong><\/em>, and as part of traversing the next two nodes, the ATNs NP<\/strong><\/em> and VP<\/strong><\/em> are respectively visited (in essence, like subroutine calls) and if the process is successful, a data structure representing the parsed information is synthesized. Again, I refer you to the reading material mentioned at the end, for learning more about the ATN formalism. Here is a convenient graphical representation of the above grammar:<\/p>\n

    \"Visualizing<\/a>
    Visualizing the ATN<\/strong><\/figcaption><\/figure>\n

    Although it might not be obvious, the ATN parser makes use of a lexicon to guide it. For example, the cat<\/strong><\/em> arc checks if the current input word belongs to a lexical category such as verb<\/strong><\/em>, noun<\/strong><\/em> or adverb<\/strong><\/em>. It is the lexicon that provides this information to the parser.<\/p>\n

    Here are some sample sentences parsed using this grammar:<\/p>\n

    \"Parsing<\/a>
    Parsing Examples<\/strong><\/figcaption><\/figure>\n

    I hope you can see why the last example fails. As per the grammar, we are expecting an adverb<\/strong><\/em> after the word chased<\/strong><\/em>, but the actual input is an article<\/strong><\/em>.\u00a0<\/span><\/p>\n

    Chunking<\/h2>\n

    Now consider this problem: We are given a sentence and we want to identify the verb phrase<\/strong><\/em> alone. We are not interested in anything before or after it. For simplicity, let us assume that the verb phrase<\/strong><\/em> is as defined in the above grammar \u2013 a verb<\/strong><\/em> followed by an adverb<\/strong><\/em>. Will the above ATN grammar work?\u00a0<\/span><\/p>\n

    The above grammar expects a noun phrase<\/strong><\/em> of a fixed pattern before the verb phrase<\/strong><\/em>. In this sense, it is a bit strict in accepting input sentences. What if the input sentence had a more complex noun phrase, for example, \u201cmy cute little dog\u201d,<\/strong><\/em> followed by the verb phrase \u201cran fast\u201d<\/strong><\/em>? Even though the verb phrase matches our pattern, the whole parse will fail because of the incorrect noun phrase. In this case, we are interested in chunking<\/strong><\/em>, instead of a full parse.<\/p>\n

    Chunking<\/strong><\/em>, as it is used in NLP, represents a form of shallow parsing<\/strong><\/em> where the goal is to extract meaningful fragments from given text. In contrast, traditional full parsing attempts to parse the entire text according to some well-defined grammar of the language, resulting in a complete syntactic structure of the text. This might or might not be the preferred approach, depending on the nature of the given text, and what we are looking to extract. Chunking<\/strong><\/em> is of practical significance in extracting information from unstructured<\/strong><\/em> text.<\/p>\n

    The popular Python<\/strong><\/em> library NLTK<\/strong><\/em><\/a>\u00a0has support for chunking<\/strong><\/em><\/a> based on part-of-speech (POS) tags. Although this will work in many situations, sometimes we might want to chunk based on keywords instead of using POS tags. In some other situations we might want to combine both POS tags and keywords while mining for some information.<\/p>\n

    Coming back to our ATN, here is a grammar for extracting just the verb phrase<\/strong><\/em> from input sentence:<\/p>\n

    \"Chunking<\/a>
    Chunking Grammar<\/strong><\/figcaption><\/figure>\n

    Here is the corresponding graphical representation:<\/p>\n

    \"Graphical<\/a>
    Graphical Representation of the Chunking Grammar<\/strong><\/figcaption><\/figure>\n

    What is different about this grammar is that in the start<\/strong><\/em> node, it looks for a verb<\/strong><\/em> and ignores other categories. When it sees a verb<\/strong><\/em> in the input, it goes to the next node and looks for an adverb<\/strong><\/em>. Any non-verb input is ignored (until end of the sentence is reached).<\/p>\n

    Here is a sample sentence parsed by this grammar:<\/p>\n

    \"Chunking:<\/a>
    Chunking: Example 1<\/strong><\/figcaption><\/figure>\n

    Here is a more interesting parse:<\/p>\n

    \"Chunking:<\/a>
    Chunking: Example 2<\/strong><\/figcaption><\/figure>\n

    Can you spot the difference between this example and the previous one?<\/p>\n

    You can see that there are two verbs in the second example, namely, shunned<\/strong><\/em> and worked<\/strong><\/em>. When the first verb shunned<\/strong><\/em> is seen, the parser jumps to the adverb<\/strong><\/em> node, but since temptations<\/strong><\/em> is a noun and not an adverb, it fails. The parser then backtracks<\/strong><\/em> and continues to look for the next verb<\/strong><\/em>. It finds worked<\/strong><\/em> this time, and the next word happens to be an adverb<\/strong><\/em>, satisfying the grammar. The extracted verb phrase is “worked harder\u201d<\/strong><\/em>. That is the power of the ATN \u2013 it can backtrack as needed till it finds (or has to necessarily give up) a proper match in the input. By the way, this can also be a concern from a performance point of view; we want to eliminate (or minimize) backtracking if at all possible because backtracking is costly. Often times, peeking ahead to select a valid option is preferred to blind backtracking, but that is beyond the scope of this article.<\/p>\n

    Generalized Information Extraction<\/h2>\n

    Now that you have understood how to collect fragments from an input text, let us apply this idea to extract important information from a homeopathy case record<\/strong><\/em>. Again, for the sake of illustration, I have deliberately kept the example simple.<\/p>\n

    Here is the text we want to analyze:<\/p>\n

    \"Homeopathy<\/a>
    Homeopathy Case Text<\/strong><\/figcaption><\/figure>\n

    We would like to extract the following information from this text:<\/p>\n

      \n
    1. Patient\u2019s age and gender<\/strong><\/li>\n
    2. Modalities: when does the complaint become better or worse?<\/strong><\/li>\n<\/ol>\n

      Here is the ATN to extract gender<\/strong><\/em>:<\/p>\n

      \"ATN<\/a>
      ATN for Gender<\/strong><\/figcaption><\/figure>\n

      The following 3 ATNs handle the age<\/strong><\/em><\/p>\n

      \"ATNs<\/a>
      ATNs for Parsing Age<\/strong><\/figcaption><\/figure>\n

      The reason why extracting age is slightly more involved is because we need to handle sentence patterns like these:<\/p>\n

      \u2026. 50 years old \u2026.<\/strong><\/em><\/p>\n

      \u2026. 50 years of age \u2026.<\/strong><\/em><\/p>\n

      \u2026. aged 50 years \u2026.<\/strong><\/em><\/p>\n

      Finally, the modality<\/strong><\/em> is handled by the following ATN:<\/p>\n

      \"ATN<\/a>
      ATN for Modality<\/strong><\/figcaption><\/figure>\n

      Let us parse the given text using the above ATNs.<\/p>\n

      \"Case<\/a>
      Case Output<\/strong><\/figcaption><\/figure>\n

      The output is as expected. I hope the above examples show the power and expressiveness of ATNs in parsing text. I have implemented the ATN parser in Lispworks<\/strong><\/em><\/a> Lisp.<\/p>\n

      Have a great weekend!\u00a0<\/span><\/p>\n

      Further Reading<\/h2>\n

      1) Woods, W.A., \u201cAugmented Transition Networks for Natural Language Analysis\u201d, Communications of the ACM, October 1970.<\/p>\n

      2) Madeline Bates, \u201cThe Theory and Practice of Augmented Transition Network Grammars\u201d in \u201cNatural Language Communication with Computers\u201d, Lecture Notes in Computer Science, Edited by Leonard Bloc, Springer-Verlag, 1978.\u00a0<\/span><\/p>\n

      3) Finin, T.W., \u201cThe Planes Interpreter and Compiler for Augmented Transition Network Grammars\u201d, in \u201cThe Design of Interpreters, Compilers, and Editors for Augmented Transition networks\u201d, Edited by Leonard Bloc, Springer-Verlag, 1983.<\/p>\n

      4) Terry Winograd, Language as a Cognitive process, Volume 1: Syntax, Addison-Wesley, 1983.<\/p>\n

      5) Pereira F.C.N. and Warren D.H.D., “Definite Clause Grammars for Language Analysis”, Artificial Intelligence 13 (1980).<\/p>\n","protected":false},"excerpt":{"rendered":"

      After Wood\u2019s paper [1], Augmented Transition Networks\u00a0(ATN) became popular in the 1970s, for parsing text. An ATN is a generalized transition network with two major enhancements: Support for recursive transitions, including jumping to other ATNs Performing arbitrary actions when edges are traversed Remembering state through the use of registers See the \u201cFurther Reading\u201d section at […]<\/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_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},"jetpack_post_was_ever_published":false},"categories":[18,107,17],"tags":[221,220,181,212],"class_list":["post-1792","post","type-post","status-publish","format-standard","hentry","category-lisp","category-natural-language-processing","category-programming","tag-atn","tag-augmented-transition-network","tag-chunking","tag-information-extraction"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p9OLnF-sU","jetpack-related-posts":[{"id":1817,"url":"https:\/\/www.rangakrish.com\/index.php\/2019\/12\/08\/using-definite-clause-grammars-dcg-for-information-extraction\/","url_meta":{"origin":1792,"position":0},"title":"Using Definite Clause Grammars (DCG) for Information Extraction","author":"admin","date":"December 8, 2019","format":false,"excerpt":"In the previous article, I showed how we can use ATNs for extracting key information from natural language text. I also pointed out in that article that Definite Clause Grammars (DCG) are a more compact formalism for doing this. That will be the focus of today's article. For a nice\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":"Processing the Text","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/12\/Processing-file-code.jpg?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/12\/Processing-file-code.jpg?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/12\/Processing-file-code.jpg?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":2366,"url":"https:\/\/www.rangakrish.com\/index.php\/2021\/03\/28\/implementing-ilexicon-using-litedb\/","url_meta":{"origin":1792,"position":1},"title":"Implementing iLexicon using LiteDB","author":"admin","date":"March 28, 2021","format":false,"excerpt":"iLexicon is an \"intelligent\" dictionary that can be used to build Natural Language applications. I have two implementations, one in Lisp and another in Prolog. Both implementations are memory-based, in order to speed up performance. I have written several articles referencing it, for example see this. \u00a0 LiteDB is a\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":"Sample Commands","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2021\/03\/Session1.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":575,"url":"https:\/\/www.rangakrish.com\/index.php\/2017\/08\/06\/text-generation-using-ilanggen-framework\/","url_meta":{"origin":1792,"position":2},"title":"Text Generation Using iLangGen Framework","author":"admin","date":"August 6, 2017","format":false,"excerpt":"The two primary areas in Natural Language processing are Natural Language Understanding and Natural Language Generation. The former is concerned with processing and making sense of natural language text, whereas the latter is concerned with synthesizing text, possibly from some deep representation. Both are fascinating and at the same time,\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"iLangGen Grammar","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/08\/Blog1.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/08\/Blog1.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/08\/Blog1.png?resize=525%2C300 1.5x"},"classes":[]},{"id":3283,"url":"https:\/\/www.rangakrish.com\/index.php\/2023\/12\/26\/homeopathy-case-analysis-using-retrieval-augmented-generation\/","url_meta":{"origin":1792,"position":3},"title":"Homeopathy Case Analysis Using Retrieval-Augmented Generation","author":"admin","date":"December 26, 2023","format":false,"excerpt":"Homeopaths, after detailed case taking, usually \u2018\u201crepertorize\u201d\u00a0 the case using software such as RadarOpus, MacRepertory, Vithoulkas Compass, etc., and finally consult a Materia Medica to confirm the remedy selection. There are some highly experienced homeopaths who have the gift of identifying the correct remedy without even repertorizing the case, but\u2026","rel":"","context":"In "Homeopathy"","block_context":{"text":"Homeopathy","link":"https:\/\/www.rangakrish.com\/index.php\/category\/homeopathy\/"},"img":{"alt_text":"Example Chat","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2023\/12\/Two-300x95.png?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2023\/12\/Two-300x95.png?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2023\/12\/Two-300x95.png?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":1532,"url":"https:\/\/www.rangakrish.com\/index.php\/2019\/04\/07\/book-review-grammar-as-science\/","url_meta":{"origin":1792,"position":4},"title":"Book Review: Grammar as Science","author":"admin","date":"April 7, 2019","format":false,"excerpt":"Title: Grammar as Science Author: Richard K. Larson Publisher: The MIT Press Year: 2010 I love studying English Grammar. That is one of the reasons I enjoy working in the area of NLP. Machine Learning techniques apart, I firmly believe that a good understanding of the conventional approaches to modelling\u2026","rel":"","context":"In "Book Review"","block_context":{"text":"Book Review","link":"https:\/\/www.rangakrish.com\/index.php\/category\/book-review\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":1410,"url":"https:\/\/www.rangakrish.com\/index.php\/2019\/01\/27\/generating-poetry-using-ilanggen\/","url_meta":{"origin":1792,"position":5},"title":"Generating Poetry Using iLangGen","author":"admin","date":"January 27, 2019","format":false,"excerpt":"In an earlier article, I wrote about using iLangGen to generate natural language text. iLangGen is a powerful text generation library that I have been working on over the years. Today, I would like to show how we can use that library to generate \"poetry\". Be warned, however, that the\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"Sample Output 2","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/01\/Output2.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]}],"_links":{"self":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/1792","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=1792"}],"version-history":[{"count":0,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/1792\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/media?parent=1792"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/categories?post=1792"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/tags?post=1792"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}