Logo: Back to home Active Robots: Supporting Education and Amateur Robotics Enthusiasts
18/08/2005 Home | Articles | Reviews | Interviews | Glossary | Features | Discussions | Search Contribute
Login
Login:

Password:

Keep me logged in. ( help )

Latest News
- NeuroEvolving Robotic Operatives (NERO) (25/06/2005)
- Senior Next-Gen Console Programmer at Infinity Ward (25/06/2005)
- Weekly Links (25/06/2005)
- Weekly Links (10/06/2005)
- NeuroSolutions v5.0 Now Available! (10/06/2005)

What's New?
- Expert System for Car Maintenance and Troubleshooting (26/06/2005)
- Expert System: PDAMum (26/06/2005)
- Towards General Purpose Vision (26/06/2005)
- Neural Architecture Part 1: Simple Logic Functions (26/06/2005)
- MobES Expert System (26/06/2005)

Friends and Affiliates
AboutAI
Active Robots
AI-Depot
Amazon.com
Amazon.co.uk
Flipcode
Generation5: At the forefront of Artificial Intelligence

Home > Articles > Natural Language Processing > Beginner
Conceptual Representation and Scripting
By James Matthews
Printable Version

Recall a famous story, perhaps the birth of Jesus, "Boy Cries Wolf", "Little Red Riding Hood" or any story that you know. Now, tell that story to a friend. After that, tell that story to another friend. Did you tell the story in the exact same way each time? It is highly likely you didn't. Why did you do this? The answer lies in the way you remember the story - you do not remember the story word for word, you store the ideas and the concepts of the story in your head. In Artificial Intelligence, this is called conceptual representation (CR).


Applications of CR

What does this have to do with Artificial Intelligence? Well, imagine the potential of a program that could parse information and store it in a string of concepts. Here are just a few applications that CR can be applied to:
  • Translation: Translation programs are notorious for their incredible sketchy translations, due to the fact they often took the absolute, or most common, meaning a word to translate. For example, a program might take the english phrase, "Mum, please don't hassle me, I've gotta fly to school now, I woke up late." and translate the word fly as to take a plane. If CR was used, firstly a parser would parse the sentence, then a conceptual-representor would create the necessary data structures (see CR Structures), then a translator would translate those concepts into the necessary language, without the complications that arose before.

  • Paraphrasing: When you paraphrase something, you take the information you were given and then recreate your own shorter version. The Microsoft Word paraphraser uses a mathematical approach to paraphrasing, here how it does it:

    How does AutoSummarize determine what the key points are? AutoSummarize analyzes the document and assigns a score to each sentence. (For example, it gives a higher score to sentences that contain words used frequently in the document.) You then choose a percentage of the highest-scoring sentences to display in the summary.
    (Extract from Microsoft Word Online Help)
    Whilst this is very effective when you would like to take a large document and only read the most important parts, such a mathematical method produces output that does not always make sense as a whole.

    If a CR-approach is used, the overall summary will not only highlight the most important parts, it will also make grammatical sense as a piece of text. Such a program would be great for radio stations and other networks that receive information from Press networks. Information could be paraphrased by the very computers receiving the information, making the job of making the news reports presentable, a lot easier.

  • Story creation: Apart from the field of computer arts, other applications of story creation could perhaps be in gaming, where the story is altered and reconstructed dynamically according to how the player changes the game world - imagine the long-term playability of that!

CR Structures (CRS)

After giving you three examples of how CR can be used, it makes you wonder why such programs aren't out yet. Creating a successful CR program is incredibly difficult. Let's look at one possible CRS. This CRS was devised at Yale for, as they put it, "possesion-changing-actions". They named it ATRANS, Abstract TRANSfer of Possesion. The example I am going to give is a very simple one — for more complicated diagrams, see Does the Top-Down or Bottom-Up Approach Best Model the Human Brain.

Basically, a CRS (like ATRANS) represents a very simple action, a base action that many other actions can be made up of. ATRANS can be used to represent give, trade, buy, exchange, sell and many, many more. Structurally, a CR is a series of 'slots', or expectations, that the computer fills as its parses and interprets the sentence. Input: "John sold Mary a book" Through the representation that would be created inferences such as these could be created:

  • Mary gave John some money and John gave her a book.
  • Mary bought John's book.
  • Mary paid John for a book.
Now, look at some of the inferences that the program could make:
  • Mary has a book.
  • John has money.
  • Mary wanted John's book.
  • John didn't want the book.
  • John had already read the book.
  • Mary will read the book.
  • John needed the money.
    This is based on an example in the The Cognitive Computer, page 100.
Obviously, for these type of inferences and paraphrases to be made, prior knowledge of various aspects must have been programmed into the application. Also, the inferences made are the every day type. The type that would be made if the program also utilized scripting. For example, John could have sold the book to Mary because it was a cookery book for Tahitian food, which John doesn't really like. Therefore, he didn't read the book...but the program would infer he had done. Perhaps with more advanced CR primitives, and a more powerful inference engine that will check for such possibilities before inferring them, such cases could be reduced or overcome completely.

Scripting

How does the program about create such inferences? I said that it uses prior knowledge - this prior knowledge will often come in the form of a script. Schank describes a script like this:
"...Scripts are prepackaged set of expectations, inferences, and knowledge that are applied in common situations, like a blueprint for action without the detail filled in..."
Cognitive Computer, pg 114.
Scripts are used by humans, in a sense. Imagine you hear this story: "Bob went to the shops. Ten minutes later, he walked out with his shopping and went home." You make a few assumptions - that Bob bought the shopping, that Bob was short of a few items etc. The reason you know this is because you follow a script unconciously in your head. You know the basic outline of shopping (due to experience) and you can fill in the details, and make assumptions from the rest. Let's look at another story: "Bob went to the gardeners. He asked the waiter for a BMW and left." Now, this story makes no sense whatsoever to the normal person! This is because is does not follow the "gardeners-script". Gardeners don't have waiters, nor do they sell BMWs!

Example of a Script.

Here is an incredibly simple example of a script, based on how to turn on a computer:

Script:       		COMPUTER-ON.
Track:	      		Computer Room.
Props:        		Computer.
              		On-button.
              		Keyboard.
Roles:             	User.


Entry Conditions: User needs computer. Computer is off. Results: User can use computer. Computer is on.


Scene 1: Locating On Button.

If PC, look on front (or back) of computer for on-switch. Wait.


Scene 2: Booting up.

Computer starts to boot up. If computer starts ok, go to (Operating System). Else: Look at error. Fix problem. (Another script). Turn off computer. Go to (Locating On Button).


Scene 3: Operating System.

Computer has started, run program needed. User computer.

To see an example of scripts at work, look at SAM.

CR Programs

Having said that CR programs are incredibly difficult to program, that doesn't mean such programs don't exist. All have been demonstration, proof-of-concept programs. I will look at two - one called SAM and another called IPP.

SAM

Perhaps one of the most famous AI programs, SAM (Script Applier Mechanism) was developed in 1975 by Richard Cullingford, Wendy Lehnert, Anatole Gershman and Jaime Carbonell. It was designed to read stories that followed basic scripts, and output summaries in several languages, and create questions and answers based on the text.

SAM had 4 basic modules: a parser and generator based on a previous program, then the main module - the Script Applier (by Cullingford), the question-answer module (Lehnert), and the Russian and Spanish generators (Gershman and Carbonell, respectively).

Here is some sample output from SAM:

Input:

Friday evening a car swerved off Route 69.  The vehicle struck a tree.
The passenger, a New Jersey man, was killed.  David Hall, 27, was
Pronouced dead at the scene by Dr. Dana Blanchard, medical examiner.  
frank Miller, 32, of 592 Foxon Rd., the driver, was taken to Milford 
Hospital by Flanagan Ambulance.  He was treated and released.  No
charges were made.  Patrolman Robert Onofrio investigated the accident.

English Summary:

AN AUTOMOBILE HIT A TREE NEAR HIGHWAY 69 FOUR DAYS AGO.  DAVID HALL, 
AGE 27, RESIDENCE IN NEW JERSEY, THE PASSENGER, DIED.  FRANK MILLER, 
AGE 32, RESIDENCE AT 593 FOXON ROAD IN NEW HAVEN, CONNECTICUT, THE 
DRIVER, WAS SLIGHTLY INJURED.  THE POLICE DEPARTMENT DID NOT FILE 
CHARGES.

Spanish Summary:

UN AUTO CHOCO CONTRA UN ARBOL CERCA DE LA CARRETERA 69 EL VIERNES AL
ANOCHECER.  DAVID HALL, DE 27 ANOS, QUE VIVIA EN NEW JERSEY, EL 
PASAGERO, SE MURIO.  FRANK MILLER, DE 32 ANOS, QUE VIVIA EN 593 CALLE
FOXON EN NEW HAVEN, CONNECTICUT, EL CHOFER, QUEDO UN POCO HERIDO. EL
DEPARTAMENTO DE POLICA NO ACUSO A NADIE.

Question-Answering Output:

Q1: Was anyone killed?
A1: YES, DAVID HALL DIED

Q2: Was anyone hurt?
A2: YES, FRANK MILLER WAS SLIGHTLY INJURED.

Q3: Why was Miller hurt?
A3: BECAUSE THE AUTOMOBILE HIT THE TREE.

Q4: Did Miller go to the hospital?
A4: YES, HE WAS IN THE MILFORD HOSPITAL.

Q5: How did Miller get to the hospital.
A5: THE FLANAGAN AMBULANCE COMPANY TOOK HIM TO THE MILFORD HOSPITAL.

SAM had a few shortcomings, though. If a story digressed from a script, SAM would have a hard time. A program that handled stories with more complicated plots, and characters would need more complicated structures. Five years and several programs later, IPP was developed.

IPP

IPP was developed in 1980 by Michael Lebowitz. IPP used slightly more advanced techniques than SAM -- in addition it to CR primitives and scripts it used plans and goals too (beyond the scope of this essay). IPP was built to look at newpaper articles of a specific domain, and to make generalizations about the information it read and remembered. IPP was important because it could update and expand its own memory structures.

Here is some sample output from the program, reading articles about Basque terrorism:

*(PARSE S1-7)

            (10 9 79) SPAIN

(STEPPING UP EFFORTS TO DETAIL A BASQUE HOME RULE STATUTE
THAT WILL BE PUT TO A REFERENDUM THIS MONTH BASQUE GUNMEN
IN SAN SEBASTIAN SPRAYED A BAR FREQUENTED BY POLICEMEN WITH
GUNFIRE WOUNDING 11 PERSONS)

(IN PAMPLONA ANOTHER BASQUE CITY TERRORISTS MURDERED A 
POLICE INSPECTOR *COMMA* KILLING HIM AS HE DREW HIS OWN
WEAPON IN SELF-DEFENSE)

>>> Beginning final memory inspection...

Feature analysis:  EV1  (S-DESTRUCTIVE-ATTACK)
   RESULTS         HEALTH        -10
                   AU            HURT-PERSON
                   HEALTH        -5
   VICTIM          NUMBER        MANY
                   ROLE          AUTHORITY
   TARGET          PLACE         BAR
   ACTOR           NATIONALITY   BASQUE
   METHODS         AU            $SHOOT-ATTACK
   LOCATION        AREA          WESTERN-EUROPE
                   NATION        SPAIN

Indexing EV1 (S1-7) as variant of S-DESTRUCTIVE ATTACK

>>> Memory incorporation complete.


            (5 15 80) SPAIN

(A BASQUE SEPARATIST GUERILLA SHOT TO DEATH THREE
YOUNF NATIONAL POLICEMEN AT POINT BLANK RANGE THURSDAY
AS THEY DRANK THEIR MORNING COFFEE IN A BAR)

>>> Beginning final memory incorporation...

Feature analysis:  EV5  (S-DESTRUCTIVE-ATTACK)
   TARGET          PLACE         BAR
   VICTIM          GENDER        MALE
                   ROLE          AUTHORITY
   ACTOR           NATIONALITY   BASQUE
                   DEMAND-TYPE   SEPARATISM
   METHODS         AU            $SHOOT-ATTACK
   LOCATION        AREA          WESTERN-EUROPE
                   NATION        SPAIN

Creating more specific S-DESTRUCTIVE-ATTACK
    (G1-1 : BASQUE-GEN) from events EV1 (S1-7)
     EV5 (S1-6) with features:

VICTIM    (1)   GENDER        MALE
                ROLE          AUTHORITY
ACTOR     (1)   NATIONALITY   BASQUE
METHODS   (1)   AU            $SHOOT-ATTACK
LOCATION  (1)   AREA          WESTERN-EUROPE
                NATION        SPAIN
TARGET    (1)   PLACE         BAR

>>>Memory incorporation complete

"Terrorist attacks in Spain are often shootings
 of policement in bars by Basques"

This program obviously had its limitations. Often the conclusions it made were a little deceptive, and the domain was limited. Nevertheless this program was a definite landmark in CR programs. Other CR programs included MARGIE, PAM, POLITICS, FRUMP, BORIS and the very impressive CYRUS. To find more information on these programs, refer to pgs 138-163 in Schank's Cognitive Computer.

Addendum: Problems with Conceptual Representation

This essay in its original form was one of the first I wrote for Generation5. I had the early AI researcher enthusiasm - since then, I have become rather disenchanted with the entire top-down approach to Artificial Intelligence. (For readers unsure about the concepts of 'top-down' and 'bottom-up' I'll refer you to Does the Top-down or the Bottom-Up Approach More Closely Model the Brain - the essay I wrote that started the whole disillusionment process!)

As I explained above, the problems with natural language processing as a whole are huge. Conceptual Representation is no exception to any of these. Imagine coding what we know as 'commonsense' into computer code? In fact, a project is on-going in Texas called the Cyc Project. After 14 years, they have a million or so facts down in computable form. While this is impressive - even more impressive will be the search algorithm to go through them! I think that while the goals of the Cyc Project are genuine, once finished (if ever) it will be of little use to anyone.

The lack of discourse knowledge is just one problem (albeit the biggest). Other areas of critique are the huge amount of domain knowledge required on top of 'commonsense'. The lack of biological plausibility is another - structures manipulated in a serial fashion is not how the brain works. The serial fashion of processing has another problem - speed!

Now, I believe that natural language processing will be one of the last (if not THE last) field of Artificial Intelligence to fully mature. Robots such as Cog may one day be able to come up with methods of learning language by themselves, without having to be explictly taught. This is the goal of robotics after all - implicit learning.

Last Updated: 13/12/1999

Article content copyright © James Matthews, 1999.
 Article Toolbar
Print
E-mail description
BibTeX entry

Search
Search:
Advanced Search

All content copyright © 1998-2004, Generation5 unless otherwise noted.
- Privacy Policy - Legal - Terms of Use -