A collection of historic NLI systems. It is meant to give you a quick overview of the field, as a sort of index.
The term in blue shows the main function.
The bullet points in the form of a gem - - mark innovations.
In the dialogs, H: means the human user, and C: the computer system.
Note that is a work-in-progress. -- Patrick
The Conversation Machine(1959)
This program is generally considered as the first one to enter in a natural language dialog with a user. The subject of the conversation was restricted to the weather.
The program was prepared with information about the current weather of today, yesterday, and tomorrow. It was also given information about the weather each month of the year, and of the seasons. Lastly it was given emotional attachments to different types of weather. It likes sunny skies and warm breezes.
Three types of words were recognized from user input: ordinary words ("snow"), time words ("October", "last week"), and operator words ("not").
Each word was given an id and a degree. For example (3, 1) for "drizzle" (light rain), (9, 1) for "downpour" (heavy rain); 1 is the id here, 3 and 9 are degrees. Together this represents the meaning of the word. Function words could be combined with ordinary words to create new words: "not", "enjoy" -> "dislike".
The program determined whether the contents of the user's sentence was in agreement with its own knowledge of the weather.
Based on keywords in the input, and the agreement with its own knowledge, the program selected an answer frame. For example:
H: I do not enjoy rain during July. C: Well, we don't usually have rainy weather in July, so you will probably not be disappointed.
- First natural language system
- The meaning of each word is stored as an attribute-value pair
- Conversation with a computer - Green, Berkeley, Gotlieb (1959) - https://archive.org/details/bitsavers_computersA_8003153/page/n7
This system is designed to handle the breadth and complexity of language found in a book on astronomy. Input text is translated to the intermediate language ('Flex') which bears a strong relationship to dependency structure. Analysis of a sentence includes linking to entries in a thesaurus (for word synonyms). The system does not find an exact answer but merely tries to match the question to the sentences in the source text as best as possible, using 'semantic correlation' calculations. We would now call this information retrieval.
The sequence of operations is that the question is first analyzed and assigned Flex and thesaurus codes, then sentences are selected and matched, and finally the paragraphs that contain supposed answering sentences are printed out with their scores.
- Uses a thesaurus
- Calculates the correlation of the question with all sentences under its control
- Quart. rep. on automatic language analysis - Householder, Lyons, Thorne (1960 - 1962)
- Automatic language analysis - Thorne (1962) - https://apps.dtic.mil/dtic/tr/fulltext/u2/297381.pdf
Baseball(1960 - 1963)question-answering
Baseball answers questions about the scores, teams, locations and dates of baseball games. It uses list structures to organize data. The input questions are restricted to single clauses. The parser creates a tree structure of word groups. The semantic analyzer builds a spec list from the parsed question. With this spec list the acceptable answers are located. The logical processor processes the aggregations for 'every', 'either' and 'how many'.
H: How many games did the Yankees play in July?
- Uses a specification list to locate acceptable answers
- Baseball: an automatic question-answerer - Green, Wolf, Chomsky, Laughery (1963)
- Computers and Thought - Feigenbaum, Feldman, eds (1963)
Phillips wrote this program as part of his Master's Thesis. It was written in LISP (which had been created just a year earlier by Phillips' supervisor, John McCarthy).
The program takes a as input a sentence (the question) and a set of other sentences (the body of knowledge). A sentence might contain a subject, a verb and a single object, along with a prepositional phrase for time and for space.
Syntactic analysis consisted of these phases: lexicalization (looking up the part-of-speech of each word); parsing using Chomsky's phrase structure rules; ordering (placing subject, verb, object, time-phrase and space-phrase in the canonical order [subject, verb, object, place, time]). Past and perfect tense were recognized.
In the matching phase the question was compared to each of the sentences in the body of knowledge.
The program handled yes/no questions (does ...?; which were answered with "YES" or "THE ORACLE SAYS NO") and wh-questions (who, what, whom, when, where; they were answered with the requested noun or by the text "THE ORACLE DOES NOT KNOW").
- A question-answering routine - Philips (1960) - ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-016.pdf
PLM accepts both pictures and English statements as input and translates both into a common logical language. Then it determines whether the statement about the picture is true. It is composed of three subsystems: a parser, a formalizer and a predicate evaluator. The formalizer creates a first-order functional calculus expression like (∀X1)[ Cir(X1) → (∃X2)[ Cir(X2) & Bk(X2) & (X2 = X1) ] ]. The predicate evaluator tests the truth value of the expression against the predicate representation of the pictures in the input.
- Uses first-order functional calculus to represent meaning
- Computer interpretation of English text and picture patterns - Kirsch (1964)
- Picture processing in a picture language machine - Cohen (1962)
- A programmable grammar for a fragment of English for use in an information retrieval system - Rankin (1961)
- An algorithm for representing English sentences in a formal language - Sillars (1963)
The General Inquirer(1962)information-retrieval
An information retrieval system that uses a custom-built thesaurus to match a word to a cluster of concepts. Syntactic analysis is very limited and function words are removed from the search altogether.
- The general inquirer: a computational system for content analysis and retrieval based on the sentence as a unit of information - Stone, Bayles, Namerwirth, Ogilvie (1962)
This system has a two-phase strategy to find an answer in a large text.
In the first phase all the content words of the text are looked up in an index that was extracted from the text. Words of related meaning (thesaurus) are involved. From these an information score is calculated and the highest scoring five or ten potential answers are retrieved from the original text.
In the second phase the question and the potential answers are parsed using a dependency grammar. Human interaction is needed to remove ambiguities. The matching is done by building a matrix from all the words from the question and the possible answers.
H: What do worms eat? C: - Worms eat grass - Grass is eaten by worms - Birds eat worms - Worms eat the way through the ground - Horses with worms eat grain
- Uses a dependency grammar
- Uses related words to match the input
- Indexing and dependency logic for answering English questions - Simmons, Klein, McConlogue (1964)
SAD SAM answers questions about human relationships. Lindsay's primary interest was in machine comprehension of English. SAD SAM reads Basic English sentences about family relationships and extracts from them data for the database. The database is in the form of a family tree represented in the program by a hierarchical set of lists. The system has a parser and a semantic analyzer. The parser handles simple sentences, relative clauses and some appositional strings and forms a (phrase structure) parse tree. The semantic analyzer searches for subject-complement combinations (i.e. Bill is Mary's father) and forms triplets (i.e. Bill (father) Mary)
- The parser handles arbitrarily complex grammars
- Constructs semantic structures composed of triplets (proper noun, relation word, proper noun)
- Makes inferences while answering questions
- Inferential memory as the basis of machines which understand natural language - Lindsay (1963)
- Computers and Thought - Feigenbaum, Feldman, eds (1963)
ELIZA(1964 - 1966)chatbot
ELIZA was one of the first "chatterbots", systems that are able to freely communicate with humans, but lacking real understanding. The NLI was copied widely and many variations where made from it.
ELIZA was able to run different scripts. One script, called DOCTOR, provided a parody of "the responses of a non-directional psychotherapist in an initial psychiatric interview".
Response to a question consists of these steps:
- examining the text input for the word (the keyword) with the highest rank
- responses associated with this keyword are looked up (a response contains a decomposition rule and a reassembly rule)
- the decomposition rules collects the variable parts from the input
- the reassembly rule creates the response from the response template and the variables
- pronouns are switched ('you' => 'me', 'myself' => 'yourself')
There are also a number of responses that apply when no keyword is present.
'hate' I hate it that (1) => 'Why do you say that (1)' I hate (1) => 'Why do you hate (1)?'
'because' Because (1) => 'Tell me more about it'
H: Men are all alike. C: In what way? H: They're always bugging us about something specific or other. C: Can you think of a specific example? H: Well, my boyfriend made me come here. C: Your boyfriend made you come here?
- Shows that simple pattern matching combined with many canned responses can go far to create the illusion of understanding
- ELIZA - a computer program for the study of natural language communications between man and machine - Weizenbaum (1966)
- Computer Power and Human Reason: From Judgment to Calculation - Weizenbaum (1976)
PhD thesis of Raphael under supervision of Minsky.
SIR accepts a fixed set of sentence types and converts these into relations. From these relations it is able to deduce the answer to a fixed set of questions. It is also able to reply with a question to the user about missing information.
For example the sentence type "Every boy is a person" is recognized as "Every X is a Y" and is added as the relation SETR(Boy, Person).
Every boy is a person / SETR(Boy, Person) John is a boy / SETR(John, Boy) Any person has two hands / PARTRN(Hand, Person, 2) A finger is part of a hand / PARTR(Finger, Hand) H: How many fingers are on John? / PARTRNQ(Finger, John) C: How many fingers per hand? H: Every hand has five fingers / PARTRN(Finger, Hand, 5) C: The answer is 10
- Queries the user about missing information
- SIR: a computer program for semantic information retrieval - Raphael (1964)
This system accepts a very limited set of sentences in the form 'IF a THEN b'. Simple declarative statements ('Pluto is next smaller than Mars') are stored as IF/THEN statements with an empty antecedent (IF).
A question is transformed into a simple relation. This relation is matched to the consequent of each of the available IF/THEN rules. If it matches the antecedents are processed. A rules with no antecedents always matches.
Mercury is next smaller than Pluto Pluto is next smaller than Mars Mars is next smaller than Venus If X is next smaller than Y, then X is smaller than Y. If X is next smaller than Y and Y is smaller than Z then X is smaller than Z. H: Is Pluto smaller than Venus? C: Yes
- Its knowledge base is a set of conditional statements IF A THEN B
- A declarative statement is a conditional with an empty antecedent
- A deductive question-answering system - Black (1964)
PhD thesis of Bobrow under supervision of Minsky.
An algebra problem solver which accepts programs phrased in a subset of English and transforms these into equations which can be solved arithmetically.
It can handle problems such as this:
If the number of customers Tom gets is 2 times the square 20 percent of the number of advertisements he runs, and the number of advertisements he runs is 45, what is the number of customers Tom gets?
Analysis is done by replacing words as "twice" by two time, detect words as "plus" and "times" as operators. The rest of the analysis consists of a series of heuristics.
H: If the number of customers Tom gets is 2 times the square 20 percent of the number of advertisements he runs, and the number of advertisements he runs is 45, what is the number of customers Tom gets?
- Transforms the input into a set of mathematical equations
- Natural language input for a computer problem-solving system - Bobrow (1964)
The Cooper System(1964)
An elegant example of translation from simple English statements into Aristotelian logic.
Statements are translated into one of the four basic Aristotelian sentence types, "All x is y", "no x is y", "some x is y", and "not all x is y".
The system correctly answers "false" to the assertion "sodium chloride is an element" having already been given the statements, "sodium chloride is salt", "salt is a compound", and "elements are not compounds".
- Uses Aristotelian logic to answer questions
- Fact retrieval and deductive question-answering information retrieval systems - Cooper (1964)
The Darlington Logic Programs(1964)question-answering
A series of COMIT programs translate a subset of English into various forms the of propositional and predicate calculi. They then test the validity of the arguments using the Davis-Putnam algorithm.
The Darlington system can be appreciated as a specialized question answerer which tests a verbal argument for internal consistency.
H: Do all who draw circles draw figures? C: All circles are figures. Therefore all who draw circles draw figures.
- Uses the Davis-Putnam algorithm to test the validity of arguments
- A COMIT program for the David-Putnam algorithm - Darlington (1962)
- Translating ordinary language into symbolic logic - Darlington (1964)
DEACON uses a list-structured database of military shipments. It does not break neatly into a parsing system, a semantic analyzer and a data processor. The sentence is being processed while it is parsed. For example the rule L1 = M + L : T1(M, L) means that when the combination of word classes M + L is found, substitute for L1 the list which is generated by T1 operating to extract the sublist M from the major list L.
H: The cost of what Air Force shipments to Omaha exceeds 100,00 dollars? C: Shipments Cost Origin Destination Shipment a $ 39,000 Detroit Washington Shipment b $103,000 Boston Omaha
- Each rule in the phrase structure grammar has attached a function that transforms the data list structures that are part of the parse
- DEACON: Direct English Access and Control - Craig, Berezner, Carney, Longyear (1966)
- DEACON breadboard summary - Thomson (1964)
- Grammatical aspects of a system for natural man-machine communication - Graig (1963)
It stores data statements such as:
- There are 5 fingers on a hand
- There is one hand on an arm
- There are 2 arms on a man
and inference rules in the form of conditional statements that included variables as in the following:
- If there are m X's on a V and if there are n V's on a Y, then there are m*n X's on a Y
By substituting data statements for the variables in conditional expressions, DEDUCOM answers questions such as the following:
H: How many fingers on a man? C: 10
- Experiments with a deductive question-answering program - Slagle (1965)
Converse(1966 - 1968)virtual-assistant
"Unique to the Kellogg system is a satisfying sense of completeness; first it is programmed and operating as a complete system; second, it accepts natural language questions and statements and retrieves data or modifies the data base; third, it includes minimally adequate syntactic and semantic analysis approaches that are based on current linguistic theory; finally, it incorporates sufficient logical structure to support deductive procedures based on both mathematical and logical relations." - Simmons (1970)
- First virtual assistant
- An approach to the on-line interrogation of structural files of facts using natural language - Kellogg (1966)
- CONVERSE-A system for the on-line description and retrieval of structured data using natural language - Kellogg
- Data management in ordinary English: examples - Kellogg
- Designing artificial languages for information storage and retrieval In Borko H (Ed) Automated Language Processing
- A natural language compiler for on-line data management - Kellogg (1968)
- On-line translation of natural language questions into artificial language queries - Kellogg
LUNAR (aka LSNLIS)(1967 - 1971)question-answering
It was created in the wake of the Apollo 11 space mission that brought the first men to the moon. The soil samples that came back were catalogued in a database and LUNAR allowed this database to be queried with plain English sentences.
The language processor translates from natural language queries or statements into a quantified formal expression in a procedural language. The quantification process is explained in detail.
H: WHAT IS THE AVERAGE CONCENTRATION OF ALUMINIUM IN HIGH ALKALI ROCKS C: 8.134996 . PCT
- First use of the Augmented Transition Network grammar, invented by Woods
- A semantic interpretation of English questions on a structured data base - Woods (1967)
- Procedural semantics for a question-answering machine - Woods (1968)
- Progress in natural language understanding - An application to lunar geology - Woods
- Semantics and quantification in natural language question answering - Woods
- What's in a link: Foundations for Semantic Networks - Woods (1975)
- The Lunar Sciences Natural Language Information System - Woods, Kaplan, Nash-Webber (1972)
- The Lunar Sciences Natural Language Information System: Final Report
PARRY(1967 - 1972)chatbot
The purpose of Colby's systems is to accumulate belief statements held by the user.
Originally it used a set of pattern-oriented rules much like those of ELIZA, but Colby added pushdown stacks to maintain the continuity of the conversation. This allowed the system to interpret an input sentence as a response to an earlier question, for example.
A directed graph model of concepts in relation to other concepts has been developed to model the belief systems of the persons being conversed with.
Rules of inference are also embedded in this structure in the form of conditional statements with variables. The principal inference rule is of the form "A implies B" where "implies" is understood to mean a psychological expectation and the A term may involve multiple conditions.
Beliefs are evaluated by a technique that computes credibility as a weighted function of consistency and evidential foundation of each belief.
H: Why are you in the hospital? C: I shouldn't be here. H: Who brought you here? C: The police. H: What trouble did you have with the police? C: Cops don't do their jobs.
- Heuristic methods for computer understanding of natural language in context-restricted on-line dialogues - Colby, Enea (1967)
- Inductive Inference by Intelligent Machines - Colby, Kenneth (1968)
- Dialogues between humans and an artificial belief system - Colby, Smith (1969)
- A directed graph representation for computer simulation of belief systems - Tesler, Enea, Colby (1968)
- Idiolectic language-analysis for understanding doctor-patient dialogues - Enea, Colby (1972)
SHRDLU(1968 - 1970)virtual-assistant
PhD thesis of Winograd, supervised by Seymour Papert.
SHRDLU allows a user to interact with a microworld of blocks. It has an impressive list of features. Over 50 years old, it still is the most expressive natural language processing system ever.
- It allows question, imperative and declarative sentences
- It uses a procedural representation of knowledge that allows it to reason
- It has strong support for determiners and quantifiers ('how many', 'at least one', ...)
- It includes a large number of common sense rules to help understand the user and give helpful responses
- It has a representation for the user (do i own the box?) and itself ('which i told you to pick up')
- You can use pronouns (it, the one) to refer to objects and past events, and it responds by using pronouns
- It names objects differently in different contexts, depending on the information needed by the user (compare 'a big green cube' to 'the large green one which supports the red pyramid')
- It has many forms of clarification questions ('i don't understand which pyramid you mean')
- It knows some heuristics to help dissolve syntactic ambiguities
- And you can say "thank you", simple idioms with canned responses
- It has an ontology of a blocks world, and holds some explicit meta knowledge about its objects
- You can ask meta questions ('can the table pick up blocks?')
- You can learn it new rule-based knowledge ('I own blocks which are not red, ...')
- You can learn it new concepts ('A steeple is a stack which contains ...') which you can then use in the dialog
- You can learn it names for specific objects ('call the biggest block "superblock"')
- It derives the meaning of words like 'littlest' from the stem
- You can use OR in a question or command, and NOT
Time, goals and actions
- It stores events as objects (reification)
- It stores its own actions and goals in the dialog context and is able to answer questions about them
- You can refer to specific time spans in the dialog by describing them ('before you put the green one on ...')
- You can ask questions about the actions that it performed in a given span of time ('how many objects did you touch while you were doing it?')
- You can ask questions about a scene at a given time ('what did the red cube support before you started to clean it off?')
- You can ask about a specific action in some span of time ('had you touched any pyramid ... ?')
- You can ask 'when' questions and it answers by describing the active action at the moment ('when...?', 'while i was stacking up ...')
- You can ask 'why' questions about actions and it answers by giving the active goal ('why?', 'to get rid of it')
- You can ask 'how' questions about compound actions and it answers by giving the composing actions
Some parts of an interaction:
H: Find a block which is taller than the one you are holding and put it into the box. C: BY "IT", I ASSUME YOU MEAN THE BLOCK WHICH IS TALLER THAN THE ONE I AM HOLDING. H: Which cube is sitting on the table? C: THE LARGE GREEN ONE WHICH SUPPORTS THE RED PYRAMID. H: Why did you clear off that cube? C: TO PUT IT ON A LARGE GREEN CUBE.
This system is really full of innovations, but I will sum them up as follows
- Procedural representation of knowledge that used both for questioning, commanding and teaching
- Explicit representation of goals and past events, and allowing the user to ask "how" and "why" questions
- Uses an ontology to help parsing and to ask meta-questions about the characteristics of the objects in the domain
- Allows pronouns to refer to objects and events previously mentioned
- Learns names, rules and concepts from the user
- Procedures a representation for data in a computer program for understanding natural language - Winograd (1971)
- Understanding Natural Language - Winograd (1972)
CARPS is a program that solves calculus word problems. It is a generalization and expansion of techniques introduced by STUDENT.
H: If the radius of the base of the filter is 5.0 inches and the altitude is 10.0 inches, find rate at which the water level rising when the volume is 100.0
- Computer solution of calculus word problems - Charniak (1969)
The semantic approach includes the notion of a model of what is being talked about and an unambiguous formal language, the predicate calculus, which can express the facts of the model.
H: Bring me a small cube at 3:00 p.m. C: There are two small cubes. H: Bring me the smaller cube. C: OK
- Uses Earley's algorithm to parse a sentence
- Talking with a robot in English - Coles (1969)
A question-answering system. The data must consist of ring structures.
- definition of new concepts in natural language
H: What were the averages between 1967 and now of SDS, RCA and Digital Equipment Corporation stock prices? C: SDS 105.30 RCA 49.80 Digital Equipment Corp. 115.72
- REL: A Rapidly Extensible Language System (1969)
- A project report on REL (1971)
- The REL System Prototype (1975)
- A net structure based relational question answerer - Shapiro (1969)
- Introduces semantic memory
- The teachable language comprehender - Quillian (1969)
Heidorn developed this automatic programming system, which allows users to describe simulation problems in English. The system takes an English partial description of a problem and fits it into an internal description language, building pieces of the problem. From the partial internal description, questions are generated which request missing pieces of information.
- Natural Language Inputs to a Simulation Programming System - Heidorn (1972)
- English as a Very High Level Language for Programming - Heidorn (1972)
- Augmented Phrase Structure Grammars, in: Proceedings of a Workshop on Theoretical Issues in Natural Language Processing. -Eds. R. Schank and B.L. Nash-Webber (1975)
ACT-R(1973 - present)cognitive-model
ACT-R is a cognitive architecture. It also has a natural language component.
- Interpretation-based processing: a unified theory of semantic sentence comprehension - Budiu, Anderson (2002)
MARGIE is based on Roger Schank's Conceptual Dependency framework. From the input it receives, it creates inferences and is able to paraphrase a text.
Input: John told Mary that Bill wants a book. Output:
- A book about what?
- Mary knows that bill wants a book
- Bill wants to come to have a book
- Bill wants someone to cease to have a book
- Bill wants to read a book
Input: John advised Mary to drink the wine. Output: John told Mary that drinking the wine would benefit her.
Conceptual Dependency theory postulates six basic concept types: things, actions, attributes of things, attributes of actions, times and locations. These concept types are connected in 16 ways. There are 14 possible actions: ATRANS, PTRANS, PROPEL, MTRANS, MBUILD, SPEAK, ATTEND, MOVE, GRASP, INGEST, EXPEL
Processing a sentence goes through these steps:
- the language analyzer extracts the conceptual dependency (CD) representation from a sentence
- the CD representation is converted to positional internal memory form; this involves linking to occurrence sets
- create references from proper names (i.e. 'John') in the text to concepts in memory
- extract sub-propositions (like: COLOR VAL (RED)
- generate inferences of five basic types: NORMATIVE, PERIPHERAL, CAUSATIVE, RESOLUTIVE, PREDICTIVE
- make use of RESULTATIVE and CAUSATIVE inferences to fill in missing causal chains
- "knitting" together of equal inferences
- detect and fill in missing or unspecified concepts or events during inferencing
- generate the surface lexical form for the responses, using discrimination nets
- Conceptual dependency: a theory of natural language understanding - Schank (1972)
- Primitive concepts underlying verbs of thought - Schank et al (1972)
- The fourteen primitive actions and their inferences - Schank (1973)
- Conceptual memory - Rieger (1973)
- Computer analysis of natural language in context - Riesbeck (1973)
- Inference and the computer understanding of English - Schank, Rieger (1973)
- Margie memory, analysis, response generation, and inference on English - Schank, Goldman, Rieger, Riesbeck (1973)
Its major application is in a text-based, question answering system for elementary mathematics.
H: Are there any even prime numbers that are greater than 2? H: Is the sum of 5 and 2 less than the product of 5 and 2 but greater than the difference of 5 and 2?
The semantic basis of the system is a collection of procedures for generating and manipulating sets and numbers.
- A question-answering system for elementary mathematics - Smith (1974)
- CONSTRUCT: In search of a theory of meaning - Smith, Smith, Rawson (1974)
RENDEZVOUS(1974 - 1977)question-answering
Created by the inventor of the relational database, E.F. Codd, this system was designed to meet the quirks of the casual user as much as possible.
The user was allowed to enter one or more sentences, or sentence-parts. He or she was allowed to make mistakes and add and change the restrictions of the question later. The system had a very extended clarification dialog aimed to make sure that the system understood exactly what the user meant. For the same reason, it had extensive support for paraphrasing the generated knowledge base query so as to be comprehensible to the user.
In contrast to other systems, this system does not parse the user's sentence into a parse tree. In stead, using conditional rules, patterns of words were interpreted directly as parts of a relational query.
- The use of clarification dialog to unveil the real intent of the user
- Seven Steps to Rendezvous with the Casual User
- RENDEZVOUS Version 1: An Experimental English Language Query Formulation System for Casual Users of Relational Data Bases
Luigi was designed to answer questions about the results and implications of performing a process. It uses cooking as an example domain.
It makes a distinction between its understanding of the world (its "Mental World") and the actual state of the world (the "Real World").
H: Make a baked Virginia ham and very sharp Cheddar cheese sandwich C: OK H: What did you use to make the sandwich? C: Baked Virginia ham, very sharp Cheddar cheese, lettuce, mustard, butter, knife, plate H: What utensils would I need if I toasted bread? C: I know one utensil. A knife. H: How do you toast bread? C: If I want to toast bread, then I must do the following: I put the bread in the toaster I wait until it is done I pick up the toast I put the toast on the plate I spread the butter on the toast with the knife
- Answers "What if" questions in a hypothetical world
- Answering questions about processes - Scragg (1975)
- Explorations in cognition - Norman, Rumelhart eds(1975)
PHLIQA1(1975 - 1983)question-answering
The question undergoes a series of translation operations. The first, English -> EFL (English-oriented Formal Language), determines the logical relations between the various parts of the sentence. The second, EFL -> WML (World-Model Language), reformulates the question in terms of the subject domain and checks whether the question makes sense in that domain. The third translation operation, WML -> DBL (Data-Base Language), provides the link between the contents of the question and the chosen data base.
H: Is each cpu in Eindhoven a P1400? C: No
- Distinguishes clearly between different levels of semantic analysis
- The question answering system PHLIQA1 - Bronnenberg (1980)
- English words and data bases: how to bridge the gap - Scha (1981?)
- Logical foundations for Question Answering, proefschrift - Scha (1983)
- PHLIQA 1, a question-answering system for data-base consultation in natural English - PHLIQA Project Group (1979)
- Natural Language Question Answering systems (contains "The question answering system PHLIQA1") - Bolc editor (1980)
Planes(1975 - 1978)question-answering
A natural language question-answering system for a database containing detailed records of U.S. Naval aircraft maintenance and flight information over a period of time.
The system understands requests by matching the requests with prestored request patterns. During this process standard terms are substituted for synonymous words or phrases, simple misspellings are corrected and appropriate items are inserted for pronouns and referential phrases.
If the matching is successful, a unique pre-stored request form will be specified, consisting of three structures:
- an English sentence skeleton which expresses the meanings of the request if fragments of the original request sentence are inserted This will be called the request meaning skeleton .
- a search function which can operate on the data base and return the appropriate answer(s) . This will be called the search function skeleton .
- an English sentence skeleton which can be used to answer the request when filled in with retrieved data . This will be called the answer skeleton.
- Natural Language Access to a Large Data Base: An Engineering Approach - Waltz (1975)
- An English Language Question Answering System for a Large Relational Database (1978)
SAM(1975 - 1978)story-understanding
SAM was Roger Schank's main program for understanding stories, based on Conceptual Dependency theory and Scripts Theory. Many of his students worked on it.
SAM creates a causal linked chain of conceptualizations that represent what took place in each story. It uses ELI (English Language Interpreter, by Chris Riesbeck) as a language module.
John went to a restaurant. He sat down. Het got mad. He left.
John was hungry. He decided to go to a restaurant. He went to one. He sat down in a chair. A waiter did not goto the table. John became upset. He decided he was going to leave the restaurant. He left it.
- Scripts Plans Goals and Understanding - Schank, Robert Abelson (1977)
EUFID(1976 - 1981)question-answering
It makes the distinction between the user's view and the database's view on application data. This leads to the distinct position that the interpretation of a question goes through two separate domain specific phases. First the question is interpreted in a domain specific way that leads to a representation of the user's view of the domain. Next this representation is transformed into the database's view of the question
- EUFID: A Friendly And Flexible Front-End For Data Management Systems
- Problems in natural-language interface with examples from EUFID
- Semantic database mapping in EUFID
LIFER(1976 - 1977)question-answering
LIFER is a system for creating natural language interfaces to relational databases.
It handles ellipsis by automatically deducing possible elliptical structures from the grammars supplied for complete constructions.
For example: the sentence
position and date hired
will be recognized as
What is the position and date hired of Eric Johnson?
LIFER also uses spelling correction and anaphoric reference resolution. It is able to define synonyms and abbreviations.
It uses a left-to-right parser following a simplifications of the ATN system of Woods.
- LIFER: A Natural Language Interface Facility - Hendrix (1976)
- The LIFER Manual: A Guide to Building Practical Natural Language Interfaces - Hendrix (1977)
- Human engineering for applied natural language processing - Hendrix (1977)
PAM(1976 - 1978)story-understanding
Successor to SAM, following Roger Schank's theories. Whereas SAM was supposed to understand stories because it was aware of scripts, PAM could understand stories that had no available scenario. PAM would have to get knowledge of plans and goals.
John needed money so he took a gun and went to the liquor store and said to the owner that he wanted money and the owner gave John money and John left. H: Why did the owner give John the money? C: The owner was afraid John would shoot him.
Uses PHRAN (PHRase ANalyzer) by Yigal Arens) as a frontend to convert raw text into a semantic representation. PHRAN uses a set of text patterns that map directly to conceptual dependency structures.
- PAM - A Program That Infers Intentions - Wilensky
- PHRAN - A Knowledge-Based Natural Language Understander - Wilensky, Arens (1979?)
- Scripts Plans Goals and Understanding - Schank, Robert Abelson (1977)
Rus(1976 - 1978)question-answering
The design of the RUS system may be best understood by contrasting it with the design of two earlier natural language systems, the LUNAR system and the "semantic grammar" system used in SOPHIE, which represent two extremes in the way in which syntax and semantics can be combined in a natural language system. The RUS system can be viewed as a synthesis of these two approaches.
- First to use a cascaded Augmented Transition Network parser
- The RUS System, in: Research in Natural Language Understanding - William A. Woods, Ronald J. Brachman, editors (1978)
SOPHIE helps the user to find the fault in an electronic system.
H: INSERT A FAULT C: THE INSTRUMENT HAS A FAULT AND ITS PRESENT CONTROL SETTINGS ARE: CC 1.0 CURRENT CONTROL-FROM 0.0 (MIN CURRENT) TO 1.0 CR HIGH CURRENT RANGE SWITCH, HIGH=1 AMP, LOW=.1 AMP LOAD 1000 LOAD RESISTANCE.IN OHMS VC 1.0 VOLTAGE CONTROL-FROM 0.0 (MIN VOLTAGE) TO 1.0 VR HIGH VOLTAGE RANGE SWITCH, HIGH=30, LOW=10 VOLTS H: WHAT IS THE OUTPT? C: OUTPT => OUTPUT THE OUTPUT VOLTAGE IS 1.2 VOLTS IF YOU ARE NOT SURE WHETHER A VALUE IS CORRECT, YOU CAN ASK "IS THAT VALUE CORRECT?" H: IS THAT RIGHT C: IN A WORKING CIRCUIT THE OUTPUT VOLTAGE IS 30.1 VOLTS. THAT VALUE IS INCORRECT. H: WHAT IS THE VOLTAGE BETWEEN THE CURRENT LIMITING TRANSISTOR AND THE CONSTANT CURRENT SOURCE? C: THE VOLTAGE AT NTIS 2.46 VOLTS.
- Semantic Grammar: An engineering technique for constructing natural language understanding systems - Burton (1976)
Veronica Dahl's systems(1976 - 1981?)question-answering
- Translating Spanish into Logic through Logic - Dahl (1981)
- GUS, a frame-driven dialog system - Bobrow, Kaplan, Kay, Norman, Thompson, Winograd (1977)
LADDER(1977 - 1978)question-answering
The system was developed as a management aid to Navy decision makers.
LADDER’s first component, called INLAND, accepts questions in a restricted subset of natural language and produces a query or sequence of queries to the database as a whole. The queries to the database, as produced by INLAND, refer to specific fields, but make no commitment about how the information in the database is broken down into files.
INLAND, the linguistic component of the intelligent interface to distributed data, has been constructed within Hendrix's LIFER framework. It handles ellipsis and spelling mistakes. It uses semantic grammars.
Queries from INLAND are directed to the second component of LADDER, called IDA (for intelligent data access). Employing a model of the structure of the database, IDA breaks down a query against the entire database into a sequence of queries against individual files.
It is the function of the third major component of LADDER, FAM (for File Access Manager) to find the location of the generic files and manage the access to them.
- Developing a Natural Language Interface to Complex Data - Hendrix, Sacerdoti, Sagalowicz, Slocum (1978)
- Managing network access to a distributed data base - Morris, Sagalowicz (1977)
- Language access to distributed data with error recovery - Sacerdoti (1977)
- IDA: An intelligent data access program - Sagalowicz (1977)
This system does not produce a computer program that can be run; the program is executed by OWL itself.
H: Check sensitivity due to thyroid function C: (CHECK (SENSITIVITY (DUE (TO THYROID-FUNCTION))))
- An overview of OWL - Szolovitz, Hawkinson, Martin (1977)
Doctoral dissertation by Wendy Lehnert based on the Conceptual Dependency and Scripts and Plans frameworks of Roger Schank.
Used by the systems SAM and PAM to answer questions about the stories that they read.
This is a profound work that needs a lot more attention.
- Human and computational question answering - Lehnert (1977)
- The process of question answering - Lehnert (1978)
Owned by AICorp
The syntactic analysis is carried out by an augmented transition network (ATN) parser of the type developed by Woods. This syntactic analysis is domain independent. The primary factor that allows the ROBOT system to be applied so quickly to different databases is the fact that the database itself is used as the world model.
H: PRINT A REPORT OF DIRECT COMMISSION, NET LOSS INCURRED AND CHANGE IN INBR FOR REGION B, SORTED BY NET LOSS. H: GIVE ME SUBTOTALS BY MONTH FOR 1977 OF NET WRITTEN PREMIUMS AND NET EARNED PREMIUMS FOR REGION M PLANNING LINE 1000.
- User-oriented Data Base Query with the ROBOT Natural Language Query System - Harris (1977)
- The ROBOT System: Natural Language Processing Applied to Data Base Query (1978)
- Experience with ROBOT in 12 Commercial Natural Language Data Base Query Applications (1979)
A system that takes a specification as input, resolves imprecisions and produces an executable program.
H: The message is distributed to each assigned office. C: (FOR ALL (offices assigned TO message FOR ANYTHING) (distribute-process#2 message office))
- A 15 year perspective on automatic programming - Robert Balzer (1980)
- Informality in program specifications - Balzer, Goldman, Wile (1978)
- Interpretation of natural language in an information system - Lehmann (1978)
FAUSTUS (aka PAMELA)(1978?)story-understanding
An extension to PAM using frames.
- Frame Activated Inferences in a Story Understanding Program - Norvig (1983?) https://norvig.com/ijcai83.html
Intellect(1980 - 1984)question-answering
INTELLECT is a commercial system from Trinzic (formed by the merger of AICorp and Aion). This system is based on experience with ROBOT.
H: I WONDER HOW ACTUAL SALES FOR LAST MONTH COMPARES TO THE FORECAST FOR PEOPLE UNDER QUOTA IN NEW ENGLAND C: PRINT A COMPARISON OF LAST NAME, 82 JUL ACT SALES AND 82 JUL EST SALES OF ALL SALES PEOPLE WITH REGION = NORTHEAST & 82 YTD ACT % QUOTA UNDER 100 00 THE NUMBER OF RECORDS TO BE SEARCHED IS 40
- Experience with INTELLECT: Artificial Intelligence Technology Transfer - Harris (1984)
- INTELLECT Query System User's Guide, 2nd. Edition (1980)
TEAM(1980 - 1984)question-answering
TEAM is the first system that could be used in a new domain by users that had no technical knowledge of the system. Users did not need to have any linguistic knowledge. A database expert with knowledge of the database was all that was needed to transport the system to a new domain.
- TEAM: An experiment in the design of transportable natural-language interfaces - Grosz, Appelt, Martin, Pereira
- DIALOGIC: a core natural-language processing system
- TEAM: A transportable natural-language interface system
- Transportability and Generality in a Natural-Language Interface System (1986)
Chat-80(1981 - 1982)question-answering
Together with the system of Veronica Dahl, on which it is based, these are the first NLI systems built in Prolog. The code of Chat-80 was circulated widely, and formed the basis of several other experimental NliDbs (e.g. Masque)
H: Which European country exports no arms to countries in Africa?
- The first major system to use Prolog
- A demonstration of the use of Extraposition Grammars
- Uses explicit (declarative) query optimization, to avoid slow database access.
- An efficient easily adaptable system for interpreting natural language queries - Pereira, Warren (1982)
- Efficient Processing of Interactive Relational Database Queries Expressed in Logic - Warren (1981)
- Extraposition Grammars - Pereira (1981)
- Logic for natural language analysis - Pereira (1983)
- Applied logic - its use and implementation as a programming tool - Warren (1983)
- Issues in natural language access to databases from a logic programming perspective - Warren (1982?)
Jabberwacky(1981 - 2006)chatbot
Jabberwacky is an artificial intelligence - a chat robot, often known as a 'chatbot' or 'chatterbot'. It aims to simulate natural human chat in an interesting, entertaining and humorous manner. Jabberwacky is different. It learns. In some ways it models the way humans learn language, facts, context and rules.
The whole thing started way back in 1988, and went on the web in 1997. It is unique - not related to any other known AI technologies!
The 'general AI' of Jabberwacky stores everything everyone has ever said, and finds the most appropriate thing to say using contextual pattern matching techniques. In speaking to you it uses just that learnt material, and borrows a little bit of your intelligence as it learns more. With no hard-coded rules, it relies entirely on the principles of feedback. This is very different to the majority of chatbots, which are rule-bound and finite. If you speak in a foreign language it will learn it, and respond appropriately if it has enough to go on. It can be taught slang English, word games, jokes and any other form of identifiable language trait. Everyone contributes, so everyone can enjoy chatting - you could say it's a conversational wikipedia.
Learning purely from conversation gives an AI's general intelligence and character - but is not meant for use in business circumstances where more control over conversational flow is required. For that reason we have a commercial set of Scripting tools that allow for a branching tree of possibilities, plus loops, returns, sentence generation from phrases within phrases, predictions, data extraction and lots more, all handled very unlike any other technology - with fuzzy pattern matching, variety and deep context. Naturally the more freeform "general AI" is combined with this approach to give the best of both worlds.
Icogno Ltd is Jabberwacky's commercially-oriented parent company. The Icogno website contains many pages that will explain further our approach to AI.
TQA (aka REQUEST)(1981?)question-answering
- Operating statistics for the transformational question answering system (1981)
- Problems and Some Solutions in Customization of Natural Language Front Ends (1985)
ARGOT(1982 - 1984)
- Uses propositional attitudes
- ARGOT: The Rochester Dialogue System - Allen, Frisch, Litman (1982)
- A Plan Recognition Model for Clarification Subdialogues - Litman, Allen (1984)
A natural language system by the creator of Prolog, Alain Colmerauer. Written in Prolog, it answers questions about space, in French and English.
H: Who discovered Pluto? C: Tombaugh H: Quel est le diametre de Leda ? C: 140 km
- ORBIS - 9th International Conference on Computational Linguistics, COLING - Colmerauer, Kittredge (1982)
A problem solving program specialized in common sense. PANDORA detects its own goals in an event-driven fashion, dynamically interleaving the creation, execution and revision of its plans.
By itself it does not have natural language interface, but I include this program because it is an important extension to Roger Schank's type of programs.
PANDORA had just awoken. She had been told that there is a newspaper at the entrance of the driveway. She notices it's raining outside. She knows that she wants to stay dry. So she must come up with a plan to get the newspaper without getting wet. She comes up with the solution to put on a rain coat.
- PANDORA - A Program for Doing Commonsense Planning in Complex Situations - Faletti (1982)
Helps the user to build an information retrieval query for online databases using a generated dialog.
- Generates a strategy for asking the user questions in order to help him with information retrieval
C: Please specify your request! H: I would like to have information about intelligent terminals for online information retrieval C: Do you prefer an high recall or an high precision search? H: A high recall one C: Do you have any particular point of view to consider for this research? H: Yes, cost considerations C: The concept "online information retrieval" could be splitted into - online - information retrieval Please validate! H: yes
- IR-NLI: An expert natural language interface to online data bases - Guida, Tasso (1982?)
Ask allowed end-users to teach the system new words and concepts at any point during the interaction. Ask was actually a complete information management system, providing its own built-in database, and the ability to interact with multiple external databases, electronic mail programs and other computer applications.
H: What is the home port of the Tokyo Maru? C: Yokohama H: Home port of the Tokyo Maru is Hong Kong. C: Yokohama has been replaced by Hong Kong as home port of Tokyo Maru. H: The cargo of the Tokyo Maru is coal. C: Coal has been added as the cargo of Tokyo Maru. H: What is the cargo of the Tokyo Maru? C: Grain Coal
- Ask is transportable in half a dozen ways (1985)
- Introducing Ask, a simple knowledgeable system (1983)
Pique maintains a connection graph, which models the user's view of the database structure. Whenever a user utterence reflects awareness or presupposition of a database object, link, restriction, etc., the graph is modified accordingly. Every time an ambiguous update request is encountered, the system consults the connection graph to determine which of the possible interpretations of the update request are meaningful with respect to the user's current view of the underlying database. It then ranks the remaining candidate interpretations, using a set of heuristic rules.
- Models the user's view of the database structure
- Natural Language Access to Data Bases: Interpreting Update Requests (1983)
SOAR(1983 - present)cognitive-model
SOAR is a cognitive architecture. It also has a natural language component: NL-SOAR.
- A Building Block Approach to a Unified Language Capability - Lehman, J., VanDyke, J. Lonsdale, D., Green, N., and Smith, M
Uses a set of "discourse expectations" and "contextual substitution" rules, that allow elliptical utterances, such as the ones shown below, to be understood:
H: What is the price of the three largest single port fixed media disks? H: speed? Q; two smallest? H: How about the price of the two smallest? H: Also the smallest with two ports? H: speed with two ports?
- Handles complex forms of elliptical sentences
- Discourse pragmatics and ellipsis resolution in task-oriented natural language interfaces - Carbonell (1983)
The general purpose language processor transforms the sentence into a semantic net. The database application program transforms it into a database query.
H: does every department head in 1135 have an office in holmde[? C: No. all heads that work For center number 11.]5 are not located in an office in holmdel
- A Robust Portable Natural Language Database Interface - Ginsparg (1983)
The user uses menu's to create sentences.
- Menu-Based Natural Language Understanding (1983)
- Usable Natural Language Interfaces through Menu-Based Natural Language Understanding (1983)
CYC(1984 - today)
CYC is the world's most comprehensive ontology and common sense knowledge base.
It's not an application solving a specific problem, but a platform that is used by many applications.
Its syntactic parser utilizes a phrase-structure grammar loosely based on Government and Binding principles.
Cyc-NL’s semantic component transforms syntactic parses into CycL formulas. The output of the semantic component is "pure" CycL: a parsed sentence can immediately be asserted into the KB, for example, or a parsed question can be presented to the SQL generator in order to pose a database query. Cyc’s semantic interpreter incorporates principles of Montague semantics. Semantic structures are built up piece-by-piece and combined into larger structures. For each syntactic rule, there is a corresponding semantic procedure which applies.
- User Models in Dialog Systems - Wahlster (1984)
Provides separate representation schemes for linguistic knowledge, general world knowledge, and application domain knowledge to achieve a high degree of portability and extendability.
H: Which female Ph.D.s earn more than 40000 dollars?
- Interaction of Knowledge Sources in a Portable Natural Language Interface - Hafner (1984)
- Portability of Syntax and Semantics in Datalog (1985)
- Design of Natural Language Interfaces: A Case Study - Hafner, Godden (1984)
- Categorizing Natural Language Queries for Intelligent Responses - Godden (1984)
- The Syntax and Semantics of User-Defined Modifiers in a Transportable Natural Language Processor (1984)
- LDC-1: A Transportable, Knowledge-based Natural Language Processor for Office Environments - Ballard, Lusth, Tinkham (1984)
DAYDREAMER(1985 - 1987)cognitive-model
This Cognitive architecture was written by Erik T. Mueller's for his 1987 dissertation.
Daydreaming is the process of "the spontaneous activity - carried out in a stream of thought - of recalling past experiences, imagining alternative courses that a past experience might have taken, and imagining possible future experiences."
Mueller has gone way beyond that single subject, and worked out an impressive cognitive architecture that includes many mental faculties. He supports it with a massive base of research literature. Based on this architecture is the DAYDREAMER Lisp program.
At the core of the architecture are personal goals and needs. These include achievement goals: to maintain self esteem, to have friends, and so on; and cyclic goals: food, money, entertainment.
In order to achieve these personal goals, DAYDREAMER has knowledge about "persons, physical objects, locations, possession of physical objects, ... mental states, interpersonal relationships, actions, and activities" (the "interpersonal domain"). This knowledge is implemented as planning rules and inference rules.
The program also applies these rules to other entities than itself in order to represent and make inferences on the mental states of others. This is called "other planning".
"Most AI programs take a request from a human user, handle the request, and terminate...In contrast, DAYDREAMER has a collection of goals which are instantiated and processed as the program sees fit."
A task or activity on behalf of an active top-level goal is called a "concern". Several concerns may be active at any time. "Each subsequence of contiguous representations produced on behalf of a given concern may be called a 'daydream'".
The program uses emotions to determine which concern to choose at any time ("emotion-driven planning"). Several emotions are created in different phases of a concern. For example, when a concern terminates a new positive or negative emotion is created. These emotions may trigger new concerns.
The architecture allow for two types of creative mechanisms: Serendipity and Action Mutation. Serendipity-based planning uses new input, as a fortunate coincidence, to help progress concerns that are not currently active. Action Mutation modifies events and goals in arbitrary ways (mutation) in order to find novel solutions.
Events are stored in episodic memory.
Emotions, Daydreaming goals, learning, and creativity
It continues with the description of the personal goals that are specific to daydreaming: rationalization, roving, revenge, reversal, recovery, rehearsal, and repercussions. These goals are activated when a person is idle. "Daydreaming goals are heuristics for how to exploit surplus processing time in a useful way." They are activated by emotions and directed, among others, towards the reduction of negative emotional states, and the exploration of consequences of possible actions.
The natural language interface is almost taken for granted in this work, but it is there nevertheless, and forms an important part of its interface.
- Produces impressively human-like thought processes
- Daydreaming in humans and computers - Mueller, Dyer (1985)
- Towards a computational theory of human daydreaming - Mueller, Dyer (1985)
- Daydreaming in humans and machines - Mueller (1990)
The user is allowed to input only questions of a specific syntactic pattern. This allows the users to have a clear view of the questions the system is able to answer, and that the pattern is easy to remember.
- Uses a "most right association principle" to resolve relative clauses attachment
- Transportable Natural Language Processing Through Simplicity - the PRE System (1985)
CLE(1986 - 1989)question-answering
Was named the current state of the art by Androutsopoulos et al (1995).
CLE distinguishes several distinct stages in the processing of the semantic representation.
- Uses unification for semantic composition.
- Performs quantifier scoping
- CLARE - A Contextual Reasoning and Cooperative Response Framework for the Core Language Engine (1992)
- The Core Language Engine
An extension of the RUS system.
- The IRUS transportable natural language database interface - Bates, Moser, Stallard (1986)
"Since experience has shown that neither users nor svstem designers can predict in advance all the words, phrases, and associated meanings that will arise in accessing a given database. we have sought to make TELI "transportable" in an extreme sense, where customizations may be performed (1) by end users, as opposed to the system designers, and (2) at any time during the processing of English sentences, rather than requiring a complete customization before English processing may occur."
TELI derives from previous work on the LDC project.
H: Which trails that aren't long lead to a mountain on franconia ridge C: - TRAIL - LENGTH-KM OLD-BRIDLE-PATH 4.1 LIBERTY-SPRING 4.7
- Semantic Acquisition in TELI - Ballard, Stumberger (1986)
- User Specification of Syntactic Case Frames in TELI, A Transportable, User-Customized Natural Language Processor - Ballard (1986)
H: What is the capital of each country bordering Greece?
- MASQUE Modular Answering System for Queries in English - Programmers's Manual (1986)
PhD thesis of Swagerman, supervised by N.H. Frijda and B.J. Wielenga.
The model has a number of concerns, which the user can influence. When that happens, the model becomes emotional, and acts accordingly.
The user input is limited to a number of commands with arguments, but the response of the system is rich.
H: Name emotion C: My experience can be named as: security: 100% contentment: 79% pride: 75% H: show concept hat C: Incorrect argument: hat H: show concept hat C: Incorrect argument: hat H: show concept hat C: You put too little variety in your instructions! You make too many mistakes! When are you going to tell me about your own emotional experience? H: Kill C: You endanger my safety! Please do not let me die. Please type in "live". H: Kill C: May your life end as miserable as mine!
- The Artificial Concern REalization System ACRES - A computermodel of emotion - Swagerman (1987)
- LOKI: A logic oriented approach to data and knowledge bases supporting natural language interaction - Binot (1988)
A query language for temporal (historical) databases.
- Natural language querying of historical databases - Clifford (1988)
- Formal semantics and pragmatics for natural language language querying - Clifford (1990)
- Formal semantics for time in databases - Clifford, Warren (1983)
Allows a user to ask questions about UNIX commands.
Uses ALANA as a parser.
- ALANA : augmentable language analyzer - Cox (1986) https://apps.dtic.mil/dtic/tr/fulltext/u2/a611782.pdf
Data Talker (aka Natural Language)(1989)
- Natural Languages - Manferdelli (1989)
Janus had the ability to interface to multiple underlying systems (databases, expert systems, graphics devices, etc) All the underlying systems could participate in the evaluation of a natural language request, without the user ever becoming aware of the heterogeneity of the overall system. Janus is also one of the first nli-db systems to support temporal questions.
Uses Montague-rules to build semantics.
- Access to multiple underlying systems in Janus - Resnik (1989)
- A compositional semantics of temporal expressions in English - Hinrichs
- A hybrid approach to representation in the JANUS natural language processor - Weischedel
- Coping with Ambiguity and Unknown Words through Probabilistic Models - Weischedel, Schwartz, Palmucci, Meteer, Ramshawi
- Discourse entities in JANUS - Ayuso
- Multiple Underlying Systems: Translating User Requests into Programs to Produce Answers - Bobrow, Resnik, Weischedel
- Portability in the Janus Natural Language Interface Weischedel, Bobrow, Ayuso, Ramshaw (1989)
- Research and Development in Natural Language Understanding as Part of thr Strategic Computing Program. Volume 1: Overview of Technical Results (1986)
- Tense, Quantifiers, and Contexts - Hinrichs (1988)
Commercial software, built on experience from the development of the Rus and Irus systems.
Handles elliptical sentences, as illustrated by the example below:
H: Does the highest paid female manager have any degrees from Harvard? C: Yes, 1. H: How about MIT? C: No, none. H: Who is the manager of the largest department? C: Name Dept. Count Patterson 045 40 H: The smallest department? C: Name Dept. Count Saavedra 011 2
Forgives dropped articles, sentences where subject and verb cases or numbers do not agree, capitalisation errors and punctuation errors.
- BBN Parlance Interface Software - System Overview (1989)
"The communication behavior of a system designed for consultation dialogs must be very flexible. Both partners may initiate new subdialogs, e.g., by asking for explanation or additional facts. In order to master this task a system must be able to infer the relevant intentions behind each user utterance. In WISBER those intentions are the basis for determining how the dialog will continue."
The chosen domain of application is financial investment.
C: Hello, this is WISBER H: I have inherited 40000 DM and want to invest this sum. C: What term should the investment have? H: The term of the investment should be eight years. C: Do you have a savings account with more than 2 net months income? H: 1 have five net months income in several savings accounts. C: Do you want to be able to have access to your money during the term of the investment? H: No. C: Then I recommend bonds to you. They have an interest rate of 7 %. H: Are there investment forms with an interest rate higher than 7 % ? C: No.
- From Meaning to Meaning - a Walk through WISBER - Horacek, Bergmann, Block, Fliegner, Gerlach, Poesio, Sprenger (1988)
- Dialog Control in a Natural Language System - Gerlach, Horacek (1989)
The system first generates a logic query, expressed in a version of untyped lambda-calculus. The lambda-calculus expression is then transformed into a first-order predicate logic expression, which is subsequently translated into universal-domain relational calculus, domain relational calculus, tuple relational calculus, and finally SQL.
- The SNAP System: A Natural Language Front End to Text and Data Bases (1996)
- A Natural Language System Based on Formal Semantics (1991?)
- A Formal Approach to Translating English into SQL in Aspects of Databases (1991)
- Modal Reasoning in Relational Systems (1991)
- An Approach to Paraphrasing Logical Query Languages in English (1991)
"Shoptalk is a prototype manufacturing information and decision-support system to help factory personnel perform tasks as quality assurance monitoring, work-in-progress tracking, and production scheduling."
Uses both a GUI and natural language.
- The role of natural language in a multimodal interface - Cohen (1991)
A commercially available nli-db
H: Who works on 3 projects? C: B. Vandecapelle, C. Willems, D. Sedlock, J.L. Binot, L. Debille H: Which of them are project leaders? C: D. Sedlock, J.L. Binot H: Documents describing the project? C: BIM_LOQUI: "The Logui NliDB", "BIM_LOQUI" MMI2: "Technical Annex" H: How many of these projects do not finish before 1994? C: 2: BIM_LOQUI, MM2 H: Are they led by JBL or DS? C: The former
- Loqui: An Open Natural Language Query System - General Description (1991)
- Natural Language Interfaces: A New Philosophy (1991)
FORR(1992 - present)cognitive-model
FORR is a cognitive architecture. It also has a natural language component.
Commercial software by IBM.
- Aspects of the Automatic Generation of SQL Statements in a Natural Language Query Interface - Ott (1992)
ThoughtTreasure(1994 - 1996)cognitive-model
This system integrates a natural language component in a full-blown AI architecture that includes scripts, spatial orientation, planning, understanding, and even emotions. It also has a wide support for various natural language constructs. It makes commonsense reasoning explicit in the form of understanding agents.
H: What time is it? C: It is a quarter past ten am. H: Are elephants purple? C: No, the are not purple, they are gray. H: What is the circumference of the earth? C: 40003236 meters is its circumference.
H: Jacques is an enemy of François. He hates François. C: Right, he is an enemy of François. H: Jacques succeeded at being elected President of France. He is happy. C: Right, he succeeds at being the president of France. H: François is happy for Jacques. C: True, he succeeds at being the president of France. But I thought that he was an enemy of François.
- Uses different types of internal representation; each best suited to its task
- Natural Language Processing with ThoughtTreasure
A.L.I.C.E.(1995 - 2004)chatbot
- First use of AIML to mark up a dialog
Tries to match the user's question to one of the questions in a FAQ file.
- Question Answering from Frequently-Asked Question Files: Experiences with the FAQ Finder System - Burke et al (1997)
The search for the answer is based on a novel form of indexing called paragraph indexing.
- LASSO: A Tool for Surfing the Answer Net - Moldovan et al (1999)
- Falcon - Boosting Knowledge for Answer Engines - Moldovan et al (2000)
- Scaling Question Answering to the Web - Kwok, Etzioni, Weld (2000)
- Finding an answer based on the recognition of the issue focus - Ferret, Grau, Huraults-Plantet (2000)
Eugene Goostman(2001 - present)chatbot
Eugene Goostman is a chatbot that is portrayed as being a 13-year-old boy from Odessa, Ukraine, who has a pet guinea pig and a father who is a gynaecologist.
In a 2014 Turing Test contest, held by the University of Reading in England, it succeeded to convince 33% of the 30 judges that it was human; thereby passing the test (which requires at least 30%). This lead some critics to believe that the Turing Test is unable to measure real intelligence and this in turn brought about the Winograd Schema Challenge
H: Which is bigger, a shoebox or Mount Everest? C: I can’t make a choice right now. I should think it out later. And I forgot to ask you where you are from… H: How many legs does a camel have? C: Something between 2 and 4. Maybe, three? :-))) By the way, I still don’t know your specialty – or, possibly, I’ve missed it? H: How many legs does a millipede have? C: Just two, but Chernobyl mutants may have up two five. I know you are supposed to trick me. H: No, I need to know that you're not a chatbot. Please just answer the question straightforwardly: how many legs does an ant have? C: Something between 2 and 4. Maybe three? :-))) Oh, what a fruitful conversation ;-)
- Syntactic Clues and Lexical Resources in Question-Answering - Litkowski (2001)
- Syntactic and Semantic Decomposition Strategies for Question Answering from Multiple Resources - Katx, Borchardt, Felshin
- Omnibase: Uniform Access to Heterogeneous Data for Question Answering - Felshin, Yuret, Ibrahim, Lin, Marton, McFarland, Temelkuran (2002)
- Answering English Questions using Foreign-Language Semi-Structured Sources - Katz, Felshin, When, Zaccak
- External Knowledge Sources for Question Answering - Katz et al
CALO(2003 - 2008)virtual-assistant
It is part of the largest NLI attempt in history, the SRI / DARPA project PAL, and was an important influence for the popular commercial system SIRI.
Its main function is that of meeting planner. It integrates heterogeneous knowledge sources that each return subgoals or ground facts.
- Integration of Heterogeneous Knowledge Sources in the CALO Query Manager
- Towards a Theory of Natural Language Interfaces to Databases - Popescu, Etzioni, Kautz (2003)
ORAKEL(2004 - 2007)question-answering
ORAKEL is a modern variant of TEAM.
- Towards portable natural language interfaces to knowledge bases - The case of the ORAKEL system - Cimiano, Haase, Heizmann, Mantel, Studer (2007)
- Porting Natural Language Interfaces between Domains - An Experimental User Study with the ORAKEL System - Cimiano, Haase, Heizmann
- ORAKEL: A Natural Language Interface to an F-Logic Knowledge Base - Cimiano
- NaLIX: an Interactive Natural Language Interface for Querying XML - Yunyao, Huahai, Jagadish (2005)
Cleverbot(2006 - present)chatbot
A successor to Jabberwacky.
Unlike some other chatterbots, Cleverbot's responses are not pre-programmed. Instead, it learns from human input: Humans type into the box below the Cleverbot logo and the system finds all keywords or an exact phrase matching the input.
Since launching on the web, the number of conversations held has exceeded 150 million(!)
Ginseng provides a quasi natural language querying access to any OWL knowledge base.
- Ginseng: A Guided Input Natural Language Search Engine - Bernstein, Kauffmann, Kaiser, Kiefer (2006)
- NLP-Reduce: A naive but domain-independent natural language interface for querying ontologies - Kaufmann, Bernstein, Zumstein (2006)
- Querix: A natural language interface to query ontologies based on clarification dialogs - Kaufmann, Bernstein, Zumstein (2006)
Watson(2006 - 2011)question-answering
Watson is for Natural Language Interaction what Deep Blue was for Chess computers. It played on live American national television against some of the best contestants in the game of Jeopardy!, a game that requires you to find the question to an answer that is given.
Watson, or DeepQA as it is called by the development team, is a Question Answering system. It is very good at searching for specific entities through large amounts of unstructured text documents based on a question in natural language and providing the confidence it has in each of the answers it finds. It also integrates structured sources like triple stores and lookup tables. It is able to combine information of multiple sources of information to answer a single question. It handles nested subquestions and certain questions that require problem solving. At the time of the Jeopardy! event it just handled English questions.
It is a very complex system. Almost literally, every technique available from literature was tried and integrated in this machine. Next to the answering machine that contains countless algorithms and manually added (Prolog) rules, it consists of many different machine learning processes, content crawlers, and uses several different types if database engines. It is a distributed system that And then there is the game engine that knows the strategies of playing Jeopardy! at the highest level.
In its essence, Watson executes the following "pipeline" as it answers a question:
- Question Analysis: extract information from the question
- Hypothesis Generation: use this information to search for possible answers (candidate answers, or hypotheses)
- Hypothesis and evidence scoring: determine the confidence on each hypothesis: how well does it match the question?
- Final merging and ranking: merge and rank the hypotheses based on the confidence values
Example questions and answers:
Puzzle: ASTRONOMICAL RHYME TIME: Any song about earth’s natural satellite. Answer: "Moon tune" Multiple Choice: BUSY AS A BEAVER: Of 1, 5, or 15, the rough maximum number of minutes a beaver can hold its breath underwater. Answer: "15" Common Bond: BOND, COMMON BOND: Fan, form, poison pen. Answer: "letters" Fill-in-the-Blank (FITB): SCHOOL OF ROCK: History: Herman’s Hermits hit number 1 in 1965 singing "I’m" this man, "I Am." Answer: "Henry VIII" Constraint Bearing: ARE YOU A FOOD"E"?: Escoffier says to leave them in their shells & soak them in a mixture of water, vinegar, salt, and flour. Answer: "Escargots" Pun bearing: HIP-HOP ON POP: From this "M.D.": "It’s like this & like that & like this & uh, its like that & like this & like that & uh" Answer: "Dr. Dre"
- Creates top-level performance at Jeopardy!
- Integrates the ranked responses of many sources of information
- Building Watson: An Overview of the DeepQA Project - Ferrucci, D, et al. (2010)
- Question analysis: How Watson reads a clue - Lally, A. et al (2012)
- Deep parsing in Watson - McCord, M.C. et al (2012)
- Relation extraction and scoring in DeepQA - Wang, C. et al (2012)
- Finding needles in the haystack: Search and candidate generation - Chu-Carroll, J. et al (2012)
- Typing candidate answers using type coercion - Murdock, J. et al (2012)
- Textual evidence gathering and analysis - Murdock, J. et al (2012)
- Relation extraction and scoring in DeepQA - Wang, C. et al (2012)
- A Comparison of Hard Filters and Soft Evidence for Answer Typing in Watson - Welty, C. et al (2012)
- A framework for merging and ranking of answers in DeepQA - Gondek, D.K. et al (2012)
- Fact-based question decomposition in DeepQA - Kalyanpur, A. et al (2012)
- Identifying implicit relationships - Chu-Carroll, J. et al. (2012)
- Special Questions and techniques - Prager, J.M. et al. (2012)
- Textual resource acquisition and engineering - Chu-Carroll, J. et al (2012)
- Automatic knowledge extraction from documents - Fan, J. et al (2012)
- Structured data and inference in DeepQA - Kalyanpur, A. et al (2012)
- Final Jeopardy: The Story of Watson, the Computer That Will Transform Our World - Stephen Baker (2012)
- The Ephyra QA system at TREC 2006
- PANTO: A portable Natural Language Interface to Ontologies - Wang, Xiong, Zhou, Yu (2007)
Transforms a sentence into triples, which are then used to query a triple store.
A sentence is parsed using the GATE NLP platform: English tokenizer, sentence splitter, POS tagger and VP chunker. It uses JAPE grammars. The result of this parse is a domain independent representation.
The core of the system is the Relation Similarity Service (RSS). The RSS creates an ontology-compliant logical query. If it encounters an ambiguity, it interacts with the user and it will remember (learn) from his choice. It maps domain independent representations to domain representations; it handles synonyms; it resolves proper nouns. It combines triples and determines their order in execution.
- AquaLog: An ontology-driven question answering system for organizational semantic intranets - Lopex, Uren, Motta, Pasin (2007)
- Lingual Question Answering using QRISTAL - Laurent, Séguéla, NègreCross (2007)
- A Web-based Question Answering System for Effective e-Learning - Parthasarathy, Chen (2007)
C-PHRASE(2008 - 2014)question-answering
Based on tuple calculus.
- C-Phrase: A system for building robust natural language interfaces to databases
OpenCog(2008 - present)cognitive-model
OpenCog is a cognitive architecture. It also has a natural language component.
- A General Intelligence Oriented Architecture for Embodied Natural Language Processing - Ben Goertzel et al
- A text-based query interface to owl ontologies - Damljanovic, Tablan, Bontcheva, (2008)
- A natural language query interface to structured information - Tablan, Damljanovic, Bontcheva, (2008)
Wolfram|Alpha(2009 - present)question-answering
Wolfram|Alpha is a powerful computational knowledge engine that allows restricted natural language input.
H: Notable people born in New Orleans metro area C: Lil' Wayne (Monday, September 27, 1982) Ellen DeGeneres (Sunday, January 26, 1958) ... (total: 100)
- Addressing Ontology-based question answering with collections of user queries - Fernandez, Izquierdo, Ferrandez, Vicedo (2009)
"We present an approach where instead of encoding the specific rules into our NLI system (which would increase the chance of being domain-specific), we use the knowledge encoded in ontologies as the primary source for understanding the user’s question, and only then try to use the output of the syntactic parsing in order to provide the more precise answer."
"Our system is similar to Querix in many aspects, with the main difference that the primary goal of the dialog in our system is not only to resolve ambiguities, but also to map question terms to the relevant ontology concepts."
- Natural Language interface to ontologies: Combining syntactic analysis and ontology-based lookup through the user interaction - Damljanovic, Agatonovic, Cunningham (2010)
SIRI(2010 - present)virtual-assistant
Apple's virtual assistant.
- Pythia: Compositional meaning construction for ontology based question answering on the semantic web - Unger, Cimiano (2011)
Google Now(2012 - 2016)virtual-assistant
Google's virtual assistant.
An evolution from Aqualog, extending it to use multiple ontologies. It is intended to query multiple Linked Open Data sources on the Semantic Web.
Poweraqua has a pipeline architecture that has four parts:
- Linguistic Component: The output of this module is a set of Query-Triples <subject, predicate, object>
- The Element Mapping Component (PowerMap): identifies those semantic resources that may be relevant to the user query
- The Triple Mapping Component (Triple Similarity Service -TSS): determines the most likely interpretation of a user query as whole
- The Merging and Ranking Component: integrates the set of ontological facts (triple patterns), recovered in the previous step from multiple semantic resources
Poweraqua has plugins for the Watson SW gateway (API calls), Virtuoso (SPARQL), Sesame (SeRQL queries)
- PowerAqua: supporting users in querying and exploring the Semantic Web - Lopex, Fernández, Motta, Stieler (2012)
- QAKiS: an open domain QA system based on relational patterns - Cabrio et al (2012)
- Template-based question answering over RDF data - Unger et al(2012)
"SEMPRE is a toolkit for training semantic parsers, which map natural language utterances to denotations (answers) via intermediate logical forms."
It allows you to create rules that map words and phrases to lambda functions and Java structures. This leads to executable Java code. Focuses on NP's and question sentences.
Its main application is access of Freebase.
Makes use of Lambda DCS for shorter lamdba expressions.
H: The person who has the most number of children C: Chulalongkorn H: The five largest cities by area
- Semantic Parsing on Freebase from Question-Answer Pairs - Jonathan Berant, Andrew Chou, Roy Frostig, Percy Liang (2013)
- Semantic Parsing via Paraphrasing - Jonathan Berant, Percy Liang (2013)
- Natural language query processing for SPARQL generation: A prototype system for SNOMEDCT - Kim, Cohen (2013)
- SQUALL: A Controlled Natural Language as Expressive as SPARQL 1.1 - Ferré (2013)
Alexa(2014 - present)virtual-assistant
Amazon's virtual assistant.
The paper "Just ASK" describes the Alexa Meaning Representation Language.
- Just ASK: Building an Architecture for Extensible Self-Service Spoken Language Understanding - Anjishnu Kumar et al (2018)
Cortana(2014 - present)virtual-assistant
Microsoft's virtual assistant
XiaoIce(2014 - present)chatbot
Microsoft's XiaoIce, an "Empathetic Social Chatbot" is based on an emotional computing framework.
It has over 660 million registered users.
"Xiaoice has been spreading its influence from China to the whole world. Right now, it has landed on more than 40 platforms in five countries (China, Japan, USA, India and Indonesia) including apps such as WeChat, QQ, Weibo and Meipai in China, and Facebook Messenger in USA and LINE in Japan."
"Over the last 5 years XiaoIce has developed more than 230 skills, ranging from answering questions and recommending movies or restaurants to comforting and storytelling. The most important and sophisticated skill is Core Chat, which can engage long and open-domain conversations with users."
XiaoIce aims to optimize for "expected Conversation-turns Per Session" (CPS). The larger the CPS is, the better engaged the social chatbot is. "Expected" corresponds to long term results.
A sample dialog session:
H: Have you watched Inuyasha? (Note: a Japanese comic) C: Everytime Kagome comes back to the modern world, math test is waiting for her H: Bravo, well, do you know how Naraku died? C: Naraku is not dead and Shikon Jewel does not disappear. H: So amazing! C: Why amazed? H: Awesome! Surprised that you also like comic
- Establishes a long-term emotional relationship with the user
- Empathic computing. In Ambient Intelligence in Everyday Life - Cai (2006)
- The Design and Implementation of XiaoIce, an Empathetic Social Chatbot - Zhou, Gao, Li, Shum (2018)
- CASIA@V2: A MLN-based question answering system over linked data - Shizhu, Yuanzhe, Liu, Zhao (2014)
- Swip: A Natural Language to SPARQL Interface Implemented with SPARQL - Pradel, Haemmerlé, Hernandez (2014)
Google Assistant(2016 - present)virtual-assistant
Google's virtual assistant.
SOPHIA(2016 - present)chatbot
A robot with a human-like face, facial expressions and speech generation. It gives interviews on TV in many countries and gives the impression of being intelligent.
It has some primitive pattern matching skills (like ELIZA), but most of its responses are written by a human operator working in the background (Wizard of Oz)
Bixby(2017 - present)virtual-assistant
Samsung's virtual assistant
Winner of the Alexa Prize of 2017.
Sounding Board is built on top of the Alexa Skills Kit powered by Echo devices, and most of the computation is done in the cloud.
"A hierarchical dialogue manager is employed where a master manages the overall conversation and a collection of miniskills manage different conversation segments. The system constructs responses using speech acts selected by the dialogue manager, where each speech act is instantiated with randomness to introduce variation to the conversation. Further, we analyze the impact of miniskill variety, user personality, and speech recognition performance on user interaction ratings."
The miniskills are content oriented (trending topics, facts, opinions, general news, sports news, jokes, question answering), personality assessment (openness, extraversion) and general (greeting, menu, exit).
- The use of miniskills to implement different aspects of conversation.
- Sounding Board – University of Washington’s Alexa Prize Submission - Fang et al (2017)
Woebot(2017 - present)therapy
A chatbot guide who could take users through exercises based on Cognitive Behavioral Therapy, which helps people interrupt and reframe negative thought patterns.
It’s very transparently non-human.
GPT(2018 - present)chatbot
Neural-net based chatbot by OpenAI
- Language Models are Few-Shot Learners - Brown et al (2019)
BlenderBot(2020 - present)chatbot
Neural-net based chatbot, by Facebook AI Research.
Based on the open source ParlAI framework https://parl.ai/ . ParlAI is a python-based platform for enabling dialog AI research.
The bot is trained by feeding it the input/output pairs of the following datasets:
- ConvAI2: conversations of people talking about their persona
- Empathetic Dialogues (ED): conversations between humans displaying empathy
- Wizard of Wikipedia (WoW): questions and human generated answers using Wikipedia
It uses a Seq2Seq Transformer architecture (for an explanation see this blog) to generate responses.
- Recipes for building an open-domain chatbot - Stephen Roller et al (2020)
DialoGPT(2020 - present)chatbot
Neural-net based chatbot by Microsoft
DialoGPT extends the Hugging Face PyTorch transformer
- DialoGPT: Large-Scale Generative Pre-training for Conversational Response Generation - Yizhe et al (2019)
Lee Luda(2020 - 2021)chatbot
Lee Luda is a self-learning South Korean chatbot in the form of a 20-year old female student.
It was trained on billions of conversions from KakaoTalk, South Korean's popular messaging app, and when it went online, it learned from user interaction.
Scatter Lab had to take it offline after it started to engage in sexist and discriminatory talk, that was picked up from a small group of its users.
This FAQ explains that Scatter Labs had learned from Microsoft's Tay problems in the past and how it had expected to prevent the problems that occurred. User input was not fed directly into the learning process. Rather it would be labeled as appropriate / inappropriate first. The inappropriate text would even be used to train the system to recognized adversarial attacks.
- Is trained to recognize inappropriate content
Meena(2020 - present)chatbot
Neural-net based chatbot by Google AI.
At its heart lies the Evolved Transformer seq2seq architecture.
- Towards a Human-like Open-Domain Chatbot - Adiwardana et al (2020)
Much of the information in this text was drawn from:
- Answering English Questions by Computer: A Survey - R.F. Simmons (1965)
- Natural Language Question-Answering Systems: 1969 - R.F. Simmons (1970)
- Into the heart of the mind - F. Rose (1984)
- Natural Language Interfaces to Databases – An Introduction - I. Androutsopoulos, G.D. Ritchie, P. Thanisch (1995)
- Question Answering Systems: Survey and Trends - A. Bouziane, D. Bouchiha, N. Doumi, M. Malki (2015)
"Into the heart of the mind" is translated in Dutch as "De leerlingen van Frankenstein", which I think is brilliant :)