Failure-Driven Reminding for Incremental Learning

ABSTRACT

Much of adult learning is gradual, almost imperceptible. Our model for this knowledge-based, incremental learning is to augment normal story comprehension processing with a failure tracking mechanism. When a comprehension rule fails, the failure and its correction are stored in an exception episode attached to the failing rule. The rule is otherwise unchanged. Subsequent failures of that rule trigger the retrieval of these exception episodes (failure-drivep repipdipg). Rule modification occurs when classes can be found for the known exceptions. The ALFRED program is a preliminary implementation that classifies and remembers failures of "everyday knowledge" in the domain of political economics.

A. LEARNING EXAMPLE

One of the members of our learning group read an article in favor of controlling credit cards. The article said that they account for $55 billion of the total credit in the American economy, and this convinced him that credit . cards contribute to inflation and probably should be controlled.

But two days later he read an article that said that credit cards were insignificant compared to the $1.23 trillion of total credit in the economy. This changed his mind. He realized he had been wrong in thinking $55 billion was a large part of total credit.

A week later, he read an article that said that adding a 10~ per gallon tax on gas would decrease consumption by 100,000 barrels a day. At first, that effect looked too big, but then he remembered having misjudged the size of $55 billion the week before. Reading further, he found that current consumption was over 6 millions barrels a day, so the expected decrease was actually quite small, in keeping with the small

size of the tax.

This work w~s funded in part by the Office of

Naval Research under contract N00014-75-C-llll.

Failure-driven reminding for incremental learning

Christopher K. Riesbeck

Computer Science Department Yale University

We believe failures is part learning process: that of being reminded the following of prior underlying

1. When new beliefs, beliefs contradict debugging processes which belief to reject and inference rule to blame for old decide which having accepted that belief (a non-trivial problem -- see [6] and [12]).
2. An exceptiop episode describing both the failure and the fix is attached to the faulty inference rule.
3. Later, if the same rule is blamed for another failure in some new situation, the previously stored episode is retrieved (this is called failure-driven remindipg).
4. When a subset of the exception episodes can be grouped into a class (e.g., episodes within one domain), the failing rule can be modified to treat that class correctly, and the exceptions removed.

We do not have a classification scheme for exception episodes to handle the last step, but we hope that existing methods (e.g., [7])) will be appropriate. We report here on a special -- but common -- case of the above process: the failure of "everyday knowledge," such as that 55 billion is a ~ig n~mber. We use such rules freely and yet we _f1nd 1t very hard to give reasons why we b~l1eve them. As we become more expert in some f1eld, we learn to replace these rules with more specific facts, and to use more cautious rules,

such as: "don't assume -- find out!"

Thus, as we become better at economics, we learn not only the real sizes of various economic quantities, but we learn to postpone judging the re~ative sizes ~f things until we have explicit po1nts for compar1son. Outside of economics, of course, we will still think 55 billion is a lot.

Nor do we stop using everyday rules in economics immediately. The first time one fails, it is neither removed nor changed. It is only tagged with the failure episode. The rule is still used to generate new beliefs, as long as no further problems arise. If a problem does arise, however, and the rule is considered suspect, its previous failures are remembered.

The advantage of this approach is that rules stay simple and efficient as long as they work most of the time. But failures are noted and changes made if a rule fails several times. The disadvantage of this approach is that a rule known to have problems may still be adding plausible, but incorrect, beliefs to the system.

ill. ~ PROJECT

ALFRED (Automatic Learning using Failure-driven Reminding in an Expert Domain) is a program being developed at Yale to model learning sequences such as the one above. In February and March, 1980, several learning sequences were gathered by the ALFRED project while reading stories in the HAll ~ Journal and the New York ~ about politicians and their proposals regarding the economy.* These stories were about credit controls, anti-inflation proposals, economic platforms, partisan battles over budget cut s, and so on. As our initial beliefs about inflation, recession, politicians, and so on, were found wanting, a number of obvious learning experiences became the basis for our research.

LEARNING ~ UNDERSTANDING

Like Soloway (11] and Sussman [12), we believe that learning does not start from scratch, but occurs in the context of an ongoing application of knowledge that already exists . New things are interpreted as instances of old things , and failures of fit cause existing knowledge and processing structures to be modified. In our case, we made ALFRED a story understanding program, similar to SAM [4) and PAM [13), but with three major differences .

First, ALFRED does not yet take natural language input. We give it conceptual representations equivalent, at a crude level, to sentences from selected articles. This is a serious weakness. We feel that skimming and focusing strategies are closely linked with the learning process. ALFRED needs more than a "natural language front-end." It needs a well-developed model of language analysis driven by dynamically changing interests and be l i efs.

Second, ALFRED changes its knowledge structures on the basis of the stories it understands. It is not enough for ALFRED to understand an argument. It must also decide

whether to believe it or not.

*Members of the Yale learning group have included Hark Burstein, Gregg Collins, Drew McDermott,

Shoshana Hardt and Alan Cypher.

Third, ALFRED is designed to deal with expectations that fail rather than succeed. We deliberately choose stories that contradict what ALFRED already believes.

m_~ PROGRAM

We developed two programs to test the failure-driven reminding aspect of our learning model. One program, written by Hark Burstein, covered the the credit card and gas tax example given at the start of this paper. The program took hand-analyzed input, looked for related stored beliefs, and checked for contradictions. If one was found, the belief supported only by an everyday rule was rejected and the everyday rule was marked with an exception episode.

The first input represented "The government has proposed controls on credit cards." ALFRED linked this to a belief that credit causes inflation, and predicted further input supporting the notion that credit card control would reduce

inflation.

(PROPOSED-ACT ACT (GOVT-CONTROL

OBJECT (CREDIT TYPE (CREDIT-CARD))))

Found causal connection

(CAUSE

ANTE (RATE-CH DIR *DVAR OBJ (CREDIT))

CONSE (RATE-CH DIR *DVAR OBJ (INFLATION)))

Inferring PROBLEM is INFLATION

Expecting support for (CAUSE ACTOR (US-GOVT) ANTE (RATE-CH DIR (NEG) OBJ (CREDIT TYPE (CREDIT-CARD))) CONSE (RATE-CH DIR (NEG) OBJ (INFLATION)))

The next input represented "Credit cards contribute $55 billion in credit." ALFRED used a set of rules called CHECK-SCALES which decided that $55 billion was enough to make credit cards a significant part of total credit and hence a significant factor in causing inflation.

(FRACTION

PART (CREDIT TYPE (CREDIT-CARD) AMOUNT (55 SCALE (BILLION) UNIT ($))) OF (CREDIT ACTOR (CONSUMER)))

CHECK-SCALES -- CREDIT-CARD is a SIGNIFICANT part

of total CREDIT

Accepting input as support for

(CAUSE ANTE (RATE-CH DIR (NEG) OBJ (CREDIT TYPE (CREDIT-CARD))) CONSE (RATE-CH DIR (NEG) OBJ (CREDIT)))

ALFRED now believed credit card control would work. The next input represented "Controls on credit cards will do little to combat inflation," which was contradicted the newly acquired belief. The input was not yet supported however so nothing happened.

(CAUSE

ANTE (GOVT-CONTROL-ECONOHY OBJ (CREDIT TYPE (CREDIT-CARD))) CONSE (RATE-CH DIR (NEG) OBJ (INFLATION) SIZE (SMALL)))

Found referent GOVT-CONTROL-ECONOHYO

*** Input is CONTRADICTION to known causal - expecting support for contradiction statement.

The next input represented "Credit cards are only $55 billion out of $1.23 trillion in total credit." CHECK-SCALES said that this made $55 billion a small fraction of total credit, supporting the new claim. Since it was an everyday rule in CHECK-SCALES, called CS-DEFAULT-WHOLE, that said that $55 billion was big, ALFRED saved the current story as an exception to CS-DEFAULT-WHOLE.

(FRACTION OF (CREDIT AMOUNT (1230 UNIT ($) SCALE (BILLION))) PART (CREDIT TYPE (CREDIT-CARD) AMOUNT (55 UNIT ($) SCALE (BILLION))))

CHECK-SCALES CREDIT-CARD is a SHALL part of total CREDIT

Accepting input as support for negation of (CAUSE

ANTE (RATE-CH DIR (NEG) OBJ (CREDIT TYPE (CREDIT-CARD))) CONSE (RATE-CH DIR (NEG) OBJ (CREDIT)))

***** Processing error -- accepted contradictory supports

Searching for errors made in process CHECK-SCALES

Found probable source of error in use of CS-DEFAULT-WHOLE in CHECK-SCALES

when processing input (FRACTION SIZE (LARGE) PART (CREDIT TYPE (CREDIT-CARD)) OF (CREDIT ACTOR (CONSUMER)))

Indexing error episode EPl on mop CHECK-SCALES

Now ALFRED was give~ the representation for "The government announced a 10 cent tax on oil to reduce its consumption." This was linked to a belief that prices affect consumption.

(PROPOSED-ACT

ACT (GOVT-CONTROL

PROBLEM (OIL-CONSUMPTION)

SOLUTION <t

(SALES-TAX

OBJECT (OIL UNIT (GAL))

AMOUNT (10 UNIT (CENTS)))))

Fo\lnd support (CAUSE ANTE (CHANGE DIR *DVAR OBJ (PURCHASE-PRICE OBJ *OVAR))

CONSJ (RATE-CH

DIR *DINV OBJ ($BUY ACTOR (CONSUMER) OBJ *OVAR)))

for input.

The next input represented "This would save 100,000 barrels of oil per day." This was linked to a belief that causal effects are commensurate; hence, a small change in price should lead to a small change in consumption. But CHECK-SCALES, using CS-DEFAULT-WHOLE, said that 100,000 barrels was a large change. An internally generated contradiction was noted, blamed on CS-DEFAULT-WHOLE, and the previous story episode was remembered.

(CAUSE

ANTE (SALES-TAX OBJECT (OIL UNIT (GAL)) AMOUNT (10 UNIT (CENTS)))

CONSE (RATE-CH DIR (NEG)

OBJ ($BUY ACTOR (CONSUMER) OBJ (OIL))

AMOUNT

(100 SCALE (THOUSAND) UNIT (BARREL) PER (DAY)))),

CHECK-SCALES -- (10 UNIT (CENTS)) is a SHALL part of total (PURCHASE-PRICE OBJ (OIL UNIT (GAL)))

CHECK-SCALES -- (100 SCALE (THOUSAND) UNIT (BARREL) PER (DAY))

is a SIGNIFICANT part of total $BUYO

Error detected

(SIZE) of consequent ~ SIGNIFICANT

Does not ma~ch expectation given antecedent (SIZE) · SHALL

Noted error in applying VERIFY-PREDICTION Found probable source of error in use of CS-DEFAULT-WHOLE in CHECK-SCALES

** Step CS-DEFAULT-WHOLE caused previous error in episode EPl

Reducing certainty of process-step

CS-DEFAULT-WHOLE to 0

There are many problems with the program just presented. ' It was not a general purpose story understander, and it did not start with a lot of knowledge. But the most glaring problem to us was that we had no well-defined structure for episodes and no well-defined description of the debugging process. Our solution, presented in the rest of this paper, tries to answers both deficiencies with the same data structure.

ALFRED's processing structures are based on Schank's Memory Organization Packets (HOPs) [9). Although HOPs are basically just frames ([1), [3)), the important thing is that they organize episodic experiences in long-term memory while they simultaneously process those experiences. Reminding is basic to understanding, since the process of understanding is the same as the process of episodic memory search. Furthermore, as inputs change the set of categories used in memory, the course of future understanding is changed.

MOPs in ALFRED have the following parts:

1. a conceptual pattern called the trigger
2. a set of conceptual patterns, that make up the content of the MOP
3. a set of indices to subMOPs or episodes
4. a set of rules for filling in the variables in the conceptual patterns

In the description below, we shall mostlly ignore the indices. Each index value labels a link to either a particular episode, or a subMOP collecting together a set of similar episodes (see [ 7) and [ 8) ) ·

Here is an outline of GOVT-CONTROL, a HOP organizing knowledge about governmental regulation of some activity:

GOVT-CONTROL

Trigger: ?Actor control ?Object

Concepts: ?Actor authorize LEGAL-CONSTRAINT(Use of ?Object) CAUSE

Rate of ?Activity a Decrease

Goa l of ?Actor a GOVT-FIX-PROBLEH(?Pr oblem)

Indices: Domain of activity Kind of regulation Object regulated

Rules: TO FILL ?Activity:

?Activity (a function of ?Object

TO FILL ?Problem: Find an undesired state caused by

?Activity

Question marks precede the variables in the conceptual patterns . LEGAL-CONSTRAINT and GOVT-FIX-PROBLEH are other HOPs. LEGAL-CONSTRAINT contains knowledge about how laws work. GOVT-FIX-PROBLEM contains knowledge about reducing unwanted situations by regulation, de-regulation,

taxation, and so on. "Authorize" is one of several kinds of predicates and relationships needed in the political domain (see [10)).

GOVT-CONTROL is invoked after reading a sentence such as "Carter proposes controls on

credit cards." This fills two variables:

Actor <a Carter/US-Government Object <a credit cards

Because the normal function of credit cards is to get credit:

Activity <· Get credit

Because credit causes inflation and inflation is one of the problems the government wants to fix:

Problem <· inflation

In this way, ALFRED infers that Carter intends to limit credit card use in order to fight inflation.

The rules used to fill variables are important in ALFRED because they explicitly represent a kind of knowledge that changes during learning. In particular, there is a class of rules, called default rules, that fill in variables with approximate answers when exact ones can't be found. As ALFRED becomes more expert in political economics, it has to learn to replace these default rules with more specific, more

accurate ones.

To organize rules, we use process ~· Where a regular HOP organizes events and other MOPs, a process MOP organizes inference rules. A pattern in a process HOP may say something like "rule ?R failed," where the variable R is filled

with a pointer to some rule.

One use of process HOPs is to organize a set of rules into a strategy, which can then be used as a rule. For example, CHECK-SCALES is a set of

rules for judging the relative size of a number:

CHECK-SCALES:

Trigger: To find the relative size 7R for ?N units of ?X

Rules: TO FILL ?R:

Compare ?N against a known scale for ?X

If this fails, compare ?N against a known scale for a superclass of ?X

rule. The second rule for filling ?R is a default

Another example of a process HOP is the EXCEPTION HOP. It records what happens when a problem in understanding occurs. Below are the trigger and conceptual parts for the EXCEPTION process MOP (the rules will be described shortly):

EXCEPTION:

Trigger: Belief ?Bl conflicts with ?B2

?B3 is supported by rule ?Rl.

Concepts: Belief ?B3 is wrong. Use ?R2 instead of ?Rl.

This says that when a new belief contradicts an old one, find the incorrect belief, B3, find the rule Rl that led to it, and find a better rule, R2.

The EXCEPTION process MOP provides not only a mechanism for fixing the problem, but a frame for remembering how the problem was fixed. With the EXCEPTION process MOP we have both a mechanism to drive the debugging process, and, at the same time, a knowledge structure to organize the relevant pieces of the episode for long-term memory.

The EXCEPTION process MOP is invoked when a belief conflict is recognized. Sometimes, an article may explicitly contradict a held belief. More commonly, the conflict arises during the inference process. For example, when the member of our learning group read that an additional tax on gas of 10~ per gallon would cause consumption to decrease by 100,000 barrels per day, he thought that this effect was too big for that small an increase in the price of gas.

In our model, the contradiction arose from infewences triggered by this causal:

Increase price of gas by lOc'/ a gallon CAUSE

Decrease use of gas by 100,000 barrels a day

Knowledge about causation includes the following inference rule:

IF A causes B

AND A and B are changes in quantities THEN the change in B is commensurate with

the change in A

In order to use this rule, we find out how big the changes are with the CHECK-SCALES process MOP. CHECK-SCALES compares the 10~ gas tax against the cost of a gallon of gas ($1.25) and concludes that the increase is small. Therefore, the causal rule above predicts that only a small change should result in something else.

But when CHECK-SCALES looks at the decrease of 100,000 barrels per day, it can't find any actual value for gas consumption. Therefore it uses a default value of millions of barrels per year. Millions of barrels per year implies that 100,000 barrels per day is a large change.

The contradiction between the small change predicted by the causal and the large change returned by CHECK-SCALES invokes the EXCEPTION process MOP. Ita job is to find out what went wrong and fix it.

The EXCEPTION process MOP fills in its variables by finding the belief at fault, where that belief came from, and what can be done to prevent it from happening again. To do this, the EXCEPTION process MOP has the following rules:

EXCEPTION:

Trigger: Belief ?Bl conflicts with ?B2

Concepts: Belief ?B3 is wrong. ?B3 is supported by rule ?Rl. ?R2 should be used instead of ?Rl.

Rules: TO FILL ?B3, ?Rl (the incorrect belief

and rule):

If ?Bl is not yet supported then "wait for more input"

If ?Bl (?B2) is supported only by a default rule ?R, then ?Bl (?B2) and ?R are at fault

TO FILL ?R2 (the better rule): If a default rule is at fault, and ?V is the variable that the rule fills, then use the rule: "TO FILL

?V: wait for more input"

The above assumes that ALFRED at least partially remembers how it inferred the faulty belief. Also it only deals with failures by default rules. A more realistic MOP would reconstruct probable sources of faulty beliefs and

would deal with other kinds of rule failures.

The EXCEPTION process MOP waits until the new input is su~ported. Then it finds the faulty belief by looking to see which one is supported by a default rule. The belief based on a default rule is replaced by the belief that contradicted it, and the default rule is replaced with the more cautious ''Wait for more input." If the faulty belief is the new one, then the replacement rule can be used immediately. In our example, when our learner realized that he might have incorrectly scaled 100,000 barrels in the article he was reading, the '~ait for more input" was applied at

once. He looked for the real value to use.

''Wait for more input," by delaying variable bindings, can cause some complex and difficult problema for a predictive understanding process. An alternative possibility would be to scan the text for the desired information, just as the FRUMP program [S] skimmed newspaper articles to fill in ita sketchy scripts.

SUM}:IMY QI. .TI.!]_ LEARNING MOPEL

Our research has stressed several regarding the learning process: ideas

1. Episode-saving when an inference rule in a MOP fails (or is inadequate) in understanding an episode, an exception link is made from that rule to the episode, specifying what the correct rule should have been.
2. Failure-driven reminding when an inference rule in a MOP fails (or is inadequate), its exception links (if any) are followed to see if a previous episode provides a better answer.
3. The EXCEPTION process MOP this directs recovery and organizes the memory of the failure for later retrieval.