Knowledge representation
A computer cannot use knowledge unless it is written in a form it can handle. Knowledge representation means storing facts and relations so that a program can reason with them.
- Facts: "A sparrow is a bird." "A bird has wings."
- Rules: IF it has wings AND it lays eggs THEN it may be a bird.
- Semantic network: a graph. Circles are things (nodes). Arrows are relations, like "is a kind of". A child node inherits the facts of its parent, so we write "has wings" once at Bird and every bird gets it.
- Exceptions: a penguin is a bird but cannot fly. The network stores this special fact at Penguin so it overrides the usual one.
Other forms are frames (a record with slots such as name, colour, size), logic statements, and tables. A good representation is clear, easy to update and quick to search.
Heuristic search
Many AI problems are "find a path": a route on a map, a move in a puzzle, a step in a plan. A program tries options one after another. This is a search.
Blind (uninformed) search, such as breadth-first search, checks every neighbour level by level. It is sure to find the shortest path in a simple grid, but it wastes time on places far from the goal. In the 3D grid it checks 45 squares.
Heuristic search uses an extra clue, the heuristic h: a quick guess of how far the goal is. On a grid, h can be the number of squares straight across plus up or down (Manhattan distance). The search picks the most promising square first. In the 3D it checks only 9 squares.
A* search picks the square with the smallest f = g + h, where g is the steps taken so far and h is the guess to the goal. If h never overestimates, A* finds the shortest path.
A heuristic is only a hint. With a wall in the way, the hint can mislead for a while, so the search still checks more squares (29 in the 3D wall case), but still fewer than blind search (58).
Bayesian reasoning
Real life is uncertain. Bayesian reasoning tells us how to change our belief when we get new evidence.
Use natural counts. Take 100 people. 10 are sick (so the prior is 10%). The test finds 9 of the 10 sick. It also wrongly flags 10% of the 90 healthy people, that is 9 people. All positives: 9 + 9 = 18. Only 9 are really sick.
Chance of being sick given a positive test = 9 / 18 = 50%.
This surprises people. A test that is 90% good can still be wrong half the time when the disease is rare. In symbols, Bayes' rule is
P(A | B) = P(B | A) × P(A) / P(B)
Here A = sick and B = positive. The posterior (belief after evidence) depends on the prior, the test quality and the false alarms. More false alarms mean a positive test means less. AI uses this for spam filters, medical help and robots that guess where they are.
Expert systems
An expert system is a program that gives advice like a human expert in a narrow area, such as plant diseases, car faults or loan checks.
- Knowledge base: a list of IF-THEN rules written with the help of experts. Example: IF fever AND cough THEN flu is likely.
- Inference engine: the part that takes the facts you give and finds which rule fits. It can reason forward (from facts to conclusion) or backward (from a guess back to the facts that would prove it).
- User interface: asks questions and shows the answer, often with the reason.
Strengths: works day and night, gives the same answer each time, can explain its reason. Limits: knows only its own rules, cannot learn by itself, and fails when no rule fits (as in the "headache only" case). Today many systems mix rules with machine learning.
Try it
On paper, draw a 9 by 7 grid. Put S on the left middle and G on the right middle. First tick squares in rings around S until you hit G. Count the ticks. Then start again and move only toward G, ticking each square. Compare your two counts with 45 and 9 in the 3D. Next, in step 4 of the 3D, move the false-alarm slider to 20% and predict the percent before you read it.
Key formulas and definitions
- f = g + h (A* search)
- h = |x difference| + |y difference| (Manhattan distance)
- P(A | B) = P(B | A) × P(A) / P(B)
- Sick among positives = true positives ÷ (true positives + false positives)
- Expert system = knowledge base + inference engine + user interface
Worked examples
1. In a semantic network, Sparrow is a Bird and Bird is an Animal. Bird: has wings. Animal: needs food. Sparrow: can fly. List the facts of Sparrow.
Sparrow inherits from Bird and Animal: can fly (own), has wings (from Bird), needs food (from Animal).
2. 100 people, 10 sick. A test finds 9 sick people and wrongly flags 9 healthy people. A person tests positive. What is the chance they are sick?
Positives = 9 + 9 = 18. Sick among them = 9. Chance = 9/18 = 50%.
3. Same test, but the false-alarm rate is 20% of the 90 healthy people. Find the chance now.
False positives = 0.20 × 90 = 18. Positives = 9 + 18 = 27. Chance = 9/27 = 33.3%.
4. A grid search finds the goal. Blind search checked 45 squares and heuristic search checked 9. Which is better, and by how many times?
Heuristic search is better. 45 / 9 = 5 times fewer squares checked.
5. An expert system has R1: IF fever AND cough THEN flu likely. A user enters fever and cough. Which part matches the rule, and what is the output?
The inference engine matches the facts to R1. The output is "flu is likely".
Common mistakes
- Thinking a positive test means you are sick for sure. It depends on how common the disease is and the false-alarm rate.
- Saying a heuristic always finds the best path. It is a hint. A good one (never overestimating) works with A*; a bad one can mislead.
- Mixing up the knowledge base and the inference engine. The base stores the rules; the engine uses them.
- Thinking an expert system can learn new rules by itself. People must add them, unlike machine learning.