Natural language understanding

Learning to read by Sigurður málari, 19th century.

Natural language understanding is a subtopic of natural language processing in artificial intelligence that deals with machine reading comprehension.

The process of disassembling and parsing input is more complex than the reverse process of assembling output in natural language generation because of the occurrence of unknown and unexpected features in the input and the need to determine the appropriate syntactic and semantic schemes to apply to it, factors which are pre-determined when outputting language.

There is considerable commercial interest in the field because of its application to news-gathering, text categorization, voice-activation, archiving and large-scale content-analysis.

History

The program STUDENT, written in 1964 by Daniel Bobrow for his PhD dissertation at MIT is one of the earliest known attempts at natural language understanding by a computer.^{[1][2][3][4][5]} Eight years after John McCarthy coined the term artificial intelligence, Bobrow's dissertation (titled Natural Language Input for a Computer Problem Solving System) showed how a computer can understand simple natural language input to solve algebra word problems.

A year later, in 1965, Joseph Weizenbaum at MIT wrote ELIZA, an interactive program that carried on a dialogue in English on any topic, the most popular being psychotherapy. ELIZA worked by simple parsing and substitution of key words into canned phrases and Weizenbaum sidestepped the problem of giving the program a database of real-world knowledge or a rich lexicon. Yet ELIZA gained surprising popularity as a toy project and can be seen as a very early precursor to current commercial systems such as those used by Ask.com.^[6]

In 1969 Roger Schank at Stanford University introduced the conceptual dependency theory for natural language understanding.^[7] This model, partially influenced by the work of Sydney Lamb, was extensively used by Schank's students at Yale University, such as Robert Wilensky, Wendy Lehnert, and Janet Kolodner.

In 1970, William A. Woods introduced the augmented transition network (ATN) to represent natural language input.^[8] Instead of phrase structure rules ATNs used an equivalent set of finite state automata that were called recursively. ATNs and their more general format called "generalized ATNs" continued to be used for a number of years.

In 1971 Terry Winograd finished writing SHRDLU for his PhD thesis at MIT. SHRDLU could understand simple English sentences in a restricted world of children's blocks to direct a robotic arm to move items. The successful demonstration of SHRDLU provided significant momentum for continued research in the field.^[9][10] Winograd continued to be a major influence in the field with the publication of his book Language as a Cognitive Process.^[11] At Stanford, Winograd was later the adviser for Larry Page, who co-founded Google.

In the 1970s and 1980s the natural language processing group at SRI International continued research and development in the field. A number of commercial efforts based on the research were undertaken, e.g., in 1982 Gary Hendrix formed Symantec Corporation originally as a company for developing a natural language interface for database queries on personal computers. However, with the advent of mouse driven, graphic user interfaces Symantec changed direction. A number of other commercial efforts were started around the same time, e.g., Larry R. Harris at the Artificial Intelligence Corporation and Roger Schank and his students at Cognitive Systems corp.^[12][13] In 1983, Michael Dyer developed the BORIS system at Yale which bore similarities to the work of Roger Schank and W. G. Lehnart.^[14]

Scope and context

The umbrella term "natural language understanding" can be applied to a diverse set of computer applications, ranging from small, relatively simple tasks such as short commands issued to robots, to highly complex endeavors such as the full comprehension of newspaper articles or poetry passages. Many real world applications fall between the two extremes, for instance text classification for the automatic analysis of emails and their routing to a suitable department in a corporation does not require in depth understanding of the text, but is far more complex than the management of simple queries to database tables with fixed schemata.^[15]

Throughout the years various attempts at processing natural language or English-like sentences presented to computers have taken place at varying degrees of complexity. Some attempts have not resulted in systems with deep understanding, but have helped overall system usability. For example, Wayne Ratliff originally developed the Vulcan program with an English-like syntax to mimic the English speaking computer in Star Trek. Vulcan later became the dBase system whose easy-to-use syntax effectively launched the personal computer database industry.^[16][17] Systems with an easy to use or English like syntax are, however, quite distinct from systems that use a rich lexicon and include an internal representation (often as first order logic) of the semantics of natural language sentences.

Hence the breadth and depth of "understanding" aimed at by a system determine both the complexity of the system (and the implied challenges) and the types of applications it can deal with. The "breadth" of a system is measured by the sizes of its vocabulary and grammar. The "depth" is measured by the degree to which its understanding approximates that of a fluent native speaker. At the narrowest and shallowest, English-like command interpreters require minimal complexity, but have a small range of applications. Narrow but deep systems explore and model mechanisms of understanding,^[18] but they still have limited application. Systems that attempt to understand the contents of a document such as a news release beyond simple keyword matching and to judge its suitability for a user are broader and require significant complexity,^[19] but they are still somewhat shallow. Systems that are both very broad and very deep are beyond the current state of the art.

Components and architecture

Regardless of the approach used, some common components can be identified in most natural language understanding systems. The system needs a lexicon of the language and a parser and grammar rules to break sentences into an internal representation. The construction of a rich lexicon with a suitable ontology requires significant effort, e.g., the Wordnet lexicon required many person-years of effort.^[20]

The system also needs a semantic theory to guide the comprehension. The interpretation capabilities of a language understanding system depend on the semantic theory it uses. Competing semantic theories of language have specific trade offs in their suitability as the basis of computer automated semantic interpretation.^[21] These range from naive semantics or stochastic semantic analysis to the use of pragmatics to derive meaning from context.^[22][23][24]

Advanced applications of natural language understanding also attempt to incorporate logical inference within their framework. This is generally achieved by mapping the derived meaning into a set of assertions in predicate logic, then using logical deduction to arrive at conclusions. Systems based on functional languages such as Lisp hence need to include a subsystem for the representation of logical assertions, while logic oriented systems such as those using the language Prolog generally rely on an extension of the built in logical representation framework.^[25][26]

The management of context in natural language understanding can present special challenges. A large variety of examples and counter examples have resulted in multiple approaches to the formal modeling of context, each with specific strengths and weaknesses.^[27][28]

See also

• AI Winter
• Discourse analysis
• History of Natural language processing
• Parts of speech
• Speech Recognition
• WordNet

Notes

1. ^ American Association for Artificial Intelligence Brief History of AI [1]
2. ^ Daniel Bobrow's PhD Thesis Natural Language Input for a Computer Problem Solving System.
3. ^ Machines who think by Pamela McCorduck 2004 ISBN 1568812051 page 286
4. ^ Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach Prentice Hall, ISBN 0-13-790395-2, http://aima.cs.berkeley.edu/ , p. 19
5. ^ Computer Science Logo Style: Beyond programming by Brian Harvey 1997 ISBN 0262581507 page 278
6. ^ Weizenbaum, Joseph (1976). Computer power and human reason: from judgment to calculation W. H. Freeman and Company. ISBN 0-7167-0463-3 pages 188-189
7. ^ Roger Schank, 1969, A conceptual dependency parser for natural language Proceedings of the 1969 conference on Computational linguistics, Sång-Säby, Sweden, pages 1-3
8. ^ Woods, William A (1970). "Transition Network Grammars for Natural Language Analysis". Communications of the ACM 13 (10): 591–606 [2]
9. ^ Artificial intelligence: critical concepts, Volume 1 by Ronald Chrisley, Sander Begeer 2000 ISBN 041519332X page 89
10. ^ Terry Winograd's SHRDLU page at Stanford SHRDLU
11. ^ Winograd, Terry (1983), Language as a Cognitive Process, Addison–Wesley, Reading, MA.
12. ^ Larry R. Harris, Research at the Artificial Intelligence corp. ACM SIGART Bulletin, issue 79, January 1982 [3]
13. ^ Inside case-based reasoning by Christopher K. Riesbeck, Roger C. Schank 1989 ISBN 0898597676 page xiii
14. ^ In Depth Understanding: A Model of Integrated Process for Narrative Comprehension.. Michael g. Dyer. MIT Press. ISBN 0-262-04073-5
15. ^ An approach to hierarchical email categorization by Peinfeng Li et al. in Natural language processing and information systems edited by Zoubida Kedad, Nadira Lammari 2007 ISBN 3540733507
16. ^ Infoworld, Nov 13, 1989, page 144
17. ^ Infoworld, April 19, 1984, page 71
18. ^ Building Working Models of Full Natural-Language Understanding in Limited Pragmatic Domains by James Mason 2010 [4]
19. ^ Mining the Web: discovering knowledge from hypertext data by Soumen Chakrabarti 2002 ISBN 1558607544 page 289
20. ^ G. A. Miller, R. Beckwith, C. D. Fellbaum, D. Gross, K. Miller. 1990. WordNet: An online lexical database. Int. J. Lexicograph. 3, 4, pp. 235-244.
21. ^ Using computers in linguistics: a practical guide by John Lawler, Helen Aristar Dry 198 ISBN 0415167922 page 209
22. ^ Naive semantics for natural language understanding by Kathleen Dahlgren 1988 ISBN 0898382874
23. ^ Stochastically-based semantic analysis by Wolfgang Minker, Alex Waibel, Joseph Mariani 1999 ISBN 0792385713
24. ^ Pragmatics and natural language understanding by Georgia M. Green 1996 ISBN 080582166X
25. ^ Natural Language Processing Prolog Programmers by M. Covington, 1994 ISBN 0136294782
26. ^ Natural language processing in Prolog by Gerald Gazdar, Christopher S. Mellish 1989 ISBN 0201180537
27. ^ Understanding language understanding by Ashwin Ram, Kenneth Moorman 1999 ISBN 0262181924 page 111
28. ^ Formal aspects of context by Pierre Bonzon et al 2000 ISBN 0792363507