Inductive Learning

Version Spaces

Structural concept learning systems are not without their problems.
The biggest problem is that the teacher must guide the system through carefully chosen sequences of examples.
In Winston's program the order of the process is important since new links are added as and when now knowledge is gathered.
The concept of version spaces aims is insensitive to order of the example presented.
To do this instead of evolving a single concept description a set of possible descriptions are maintained. As new examples are presented the set evolves as a process of new instances and near misses.
We will assume that each slot in a version space description is made up of a set of predicates that do not negate other predicates in the set -- positive literals.
Indeed we can represent a description as a frame bases representation with several slots or indeed use a more general representation. For the sake of simplifying the discussion we will keep to simple representations.
If we keep to the above definition the Mitchell's candidate elimination algorithm is the best known algorithm.
Let us look at an example where we are presented with a number of playing cards and we need to learn if the card is odd and black.
We already know things like red, black, spade, club, even card, odd card etc.
So the  is red card, an even card and a heart.
This illustrates on of the keys to the version space method specificity:

• Conjunctive concepts in the domain can be partially ordered by specificity.
• In this Cards example the concept black is less specific than odd black or spade.
• odd black and spade are incomparable since neither is more (or less) specific.
• Black is more specific than any card, any 8 or any odd card

The training set consist of a collection of cards and for each we are told whether or not it is in the target set -- odd black
The training set is dealt with incrementally and a list of most and least specific concepts consistent with training instances are maintained.
Let us see how can learn from a sample input set:

• Initially the most specific concept consistent with the data is the empty set. The least specific concept is the set of all cards.
• Let the  be the first card in the sample set. We are told that this is odd black.
• So the most specific concept is  alone the least is still all our cards.
• Next card : we need to modify our most specific concept to indicate the generalisation of the set something like ``odd and black cards''. Least remains unchanged.

• Next card : Now we can modify the least specific set to exclude the . As more exclusion are added we will generalise this to all black cards and all odd cards.
• NOTE that negative instances cause least specific concepts to become more specific and positive instances similarly affect the most specific.
• If the two sets become the same set then the result is guaranteed and the target concept is met.

The Candidate Elimination Algorithm
Let us now formally describe the algorithm.
Let G be the set of most general concepts. Let S be the set of most specific concepts.
Assume: We have a common representation language and we a given a set of negative and positive training examples.
Aim: A concept description that is consistent with all the positive and none of the negative examples.
Algorithm:

• Initialise G to contain one element -- the null description, all features are variables.
• Initialise S to contain one element the first positive example.

Inductive Learning

This involves the process of learning by example -- where a system tries to induce a general rule from a set of observed instances.
This involves classification -- assigning, to a particular input, the name of a class to which it belongs. Classification is important to many problem solving tasks.
A learning system has to be capable of evolving its own class descriptions:

• Initial class definitions may not be adequate.
• The world may not be well understood or rapidly changing.

The task of constructing class definitions is called induction or concept learning

A Blocks World Learning Example -- Winston (1975)

• The goal is to construct representation of the definitions of concepts in this domain.
• Concepts such a house - brick (rectangular block) with a wedge (triangular block) suitably placed on top of it, tent - 2 wedges touching side by side, or an arch - two non-touching bricks supporting a third wedge or brick, were learned.
• The idea of near miss objects -- similar to actual instances was introduced.
• Input was a line drawing of a blocks world structure.
• Input processed (see VISION Sections later) to produce a semantic net representation of the structural description of the object (Fig. 27)  
  Fig. 27 House object and semantic net
• Links in network include left-of, right-of, does-not-marry, supported-by, has-part, and isa.
• The marry relation is important -- two objects with a common touching edge are said to marry. Marrying is assumed unless does-not-marry stated.

There are three basic steps to the problem of concept formulation:

1. Select one know instance of the concept. Call this the concept definition.
2. Examine definitions of other known instance of the concept. Generalise the definition to include them.
3. Examine descriptions of near misses. Restrict the definition to exclude these.

Both steps 2 and 3 rely on comparison and both similarities and differences need to be identified.

Inductive Learning

• Analyzing words into their linguistic components (morphemes).

• Morphemes are the smallest meaningful units of language.

• Ambiguity: More than one alternatives

flies flyVERB+PROG

flyNOUN+PLU

adam adam+ACC - the man (accusative)

adam+P1SG - my man

ada+P1SG+ACC - my island (accusative)

Parts-of-Speech (POS) Tagging

• Each word has a part-of-speech tag to describe its category.

• Part-of-speech tag of a word is one of major word groups (or its subgroups).

– open classes -- noun, verb, adjective, adverb

– closed classes -- prepositions, determiners, conjuctions, pronouns, particples

• POS Taggers try to find POS tags for the words.

• duck is a verb or noun? (morphological analyzer cannot make decision).

• A POS tagger may make that decision by looking the surrounding words.

– Duck! (verb)

– Duck is delicious for dinner. (noun)

Lexical Processing

• The purpose of lexical processing is to determine meanings of individual words.

• Basic methods is to lookup in a database of meanings – lexicon

• We should also identify non-words such as punctuation marks.

• Word-level ambiguity -- words may have several meanings, and the correct one

cannot be chosen based solely on the word itself.

– bank in English

• Solution -- resolve the ambiguity on the spot by POS tagging (if possible) or passon

the ambiguity to the other levels.

Syntactic Processing

• Parsing -- converting a flat input sentence into a hierarchical structure that

corresponds to the units of meaning in the sentence.

• There are different parsing formalisms and algorithms.

• Most formalisms have two main components:

– grammar -- a declarative representation describing the syntactic structure

of sentences in the language.

– parser -- an algorithm that analyzes the input and outputs its structural

representation (its parse) consistent with the grammar specification.

• CFGs are in the center of many of the parsing mechanisms. But they are

complemented by some additional features that make the formalism more suitable

to handle natural languages.

Semantic Analysis

• Assigning meanings to the structures created by syntactic analysis.

• Mapping words and structures to particular domain objects in way consistent with

our knowledge of the world.

• Semantic can play an import role in selecting among competing syntactic analyses

and discarding illogical analyses.

– I robbed the bank -- bank is a river bank or a financial institution

• We have to decide the formalisms which will be used in the meaning

representation.

Knowledge Representation for NLP

• Which knowledge representation will be used depends on the application --

Machine Translation, Database Query System.

• Requires the choice of representational framework, as well as the specific

meaning vocabulary (what are concepts and relationship between these concepts

-- ontology)

• Must be computationally effective.

• Common representational formalisms:

– first order predicate logic

– conceptual dependency graphs

– semantic networks

– Frame-based representations