Lecture 28

Heuristics

A heuristic is a 'rule of thumb' that can be used to speed up a search algorithm.

A good heuristic can considerably speed up the search.

For example, consider the route finding example from the last lecture.

A good heuristic for this example is the straight line distance to the goal. Our search will be much more efficient if we look at routes going towards the goal first.

      8        5     2 
      T---4----G--4--C   0
     /\        |         W
    /  \       5        /
   3    5      |       3
  /      \     |      /
 A---4----H-2--B--4--P
 10       6.8  6     3

The numbers in bold in this diagram are straight line distances from W. They can be used in a modified branch and bound algorithm to find the goal even more efficiently.

Neural Networks

What is a Neural Network?

Here is a definition from a book:

... a neural network is a system composed of many simple processing elements operating in parallel whose function is determined by network structure, connection strengths, and the processing performed at computing elements or nodes.

It has lots of very simple processing elements (or neurons or units). Each unit has inputs and an output. The unit is defined by a set of parameters (or weights).

Units are connected together in a regular way (a network). Input is placed on input units. There may be a number of hidden units that also perform processing and there will be some output units.

The network is trained by applying example inputs (where we know the correct output).

The weights are then changed so that the outputs are more like the correct outputs.

Example: NETtalk

The problem

Convert English text into the vowel and consonant sounds (phonemes) that make up speech. For example consider the following words: Albany, Albania, misled and bedraggled.

Traditional Approach

1. Create if-then rules to encode all the regularities in the language.
2. Maintain a database of exceptions to these rules.
3. Build a production system to resolve conflicts.

For example, a ``c'' can either be pronounced like an ``s'' as in center, icy, and city or a ``k'' as in cat and crumb. Here is a rule that might encode this difference:

if a ``c'' appears before an ``i'', ``e'', or ``y''
then pronounce it like an ``s'' 
else pronounce it like a ``k'' 

Exception: celtic 

Neural Network Approach

Allow a system to learn how to pronounce words by giving it lots of examples and correcting its mistakes.

1. Choose an architecture.
2. Choose a representation for the input and output.
3. Determine a training set. 16,000 words were chosen randomly from the 20,000 words in Webster's Dictionary.
4. Train the system. Give the network each word in the training set several times, and indicate the errors for learning.
5. Test the system. The network was able to respond correctly to 90%of the 4,000 remaining words from the dictionary.

Advantages of the Network Approach

• There may exist non-intuitive relationships between the problem's parameters that are easy for the network learning procedure to take advantage of but hard for a programmer to recognize
• A network can consider a much larger number of inputs and outputs (ranging in the thousands) than is computationally feasible for most traditional methods
• A network solution may often require less hardware and less software leading to lower costs and faster design cycles

Steps in the training of NETtalk

• Babbling
• Consonant and vowel sounds
• Pauses
• Words
• Phrases
• Full sentences