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.
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.
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.
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
Allow a system to learn how to pronounce words by giving it lots of examples and correcting its mistakes.
Advantages of the Network Approach
Steps in the training of NETtalk