Computer Science › Section L · Artificial intelligence › Topic L.4

Additional areas: knowledge and learning

Perceiving and searching are not enough: an intelligent agent needs a store of knowledge it can use and keep up to date, and the ability to learn what nobody programmed into it. This topic covers how knowledge is represented, why using it is tricky, the main kinds of machine learning, and evolution-inspired genetic algorithms.

The knowledge problem

People understand a sentence or a scene by drawing on a vast store of everyday facts: cups hold liquids, a dropped glass breaks, people sleep at night. This real-world knowledge, often called common sense, is easy for us to use and very hard to give a machine. Computers store data superbly, and statistical tools can find patterns in huge data sets, but data is not yet knowledge. AI researchers must decide how to represent knowledge, how to find the part that matters for a task, and how to keep it current.

Ways to represent knowledge

Knowledge comes in declarative form (facts) and procedural form (skills), and no single scheme suits everything. A semantic net stores facts as a graph: nodes for things and concepts, and labelled links such as is-a, has-part or lives-in. A frame bundles the expected slots for one kind of thing, such as a restaurant visit with slots for place, time and bill. Logic stores facts and rules that inference can use directly, as Prolog does in 'Declarative programming'. Large modern knowledge graphs, used by search engines and digital assistants, are descendants of semantic nets.

Worked example: inheritance in a semantic net

Net: Pip is-a penguin; penguin is-a bird; bird is-a animal; animal can breathe; bird can fly; penguin cannot fly; Pip lives-in a zoo. Question 1: does Pip breathe? 1. Pip has no breathe link, so follow is-a links upward: penguin, then bird, then animal. 2. Animal can breathe, and Pip inherits it: yes. Question 2: can Pip fly? 3. Search upward from Pip and stop at the first node that answers. 4. Penguin, one step up, says cannot fly, before bird is reached. 5. Answer: no. Storing a fact once at the most general node saves space, and a more specific link overrides the general default, which is how the net copes with exceptions.

Finding what is relevant

Retrieving knowledge is more than looking it up. Asked 'Did Leo catch his train?', a helpful system might answer 'No, the line was closed by flooding', not just 'No'. But it must tell relevant facts from merely related ones: 'No, and his favourite colour is green' is related to Leo, yet useless. Systems also need meta-reasoning, reasoning about their own reasoning. One example is the closed-world assumption, met in 'Declarative programming': whatever cannot be derived is taken to be false. It works for a membership list, but it has traps. If the only fact is 'Ana or Ben is in the choir', neither name can be derived alone, so the assumption concludes both are false, contradicting the fact.

The frame problem

A further difficulty, first named by John McCarthy and Patrick Hayes in 1969, is the frame problem: keeping knowledge correct as the world changes, including what an action does not change and what it changes indirectly. A robot carrying a tray across a room must update the tray's position, and also the glass standing on it, an indirect effect nobody stated. Yet it should not waste time checking whether the walls changed colour. People handle this effortlessly; writing down every effect and non-effect of every action quickly becomes unmanageable.

Ways machines learn

We want agents that improve on their own, because many tasks cannot be fully programmed in advance. Approaches differ in how much a person must supply. Learning by imitation records steps a person demonstrates, like a macro recorder replaying a sequence of commands. Supervised learning gives labelled examples, the training set, and the system generalises to new cases: handwriting, spam, medical images. Reinforcement learning gives only a reward or penalty after trial and error; it suits games, where winning is easy to judge. Unsupervised learning gets no labels at all and looks for structure, for example clustering customers into groups with similar habits.

Supervised learning in practice

Arthur Samuel, whose 1950s draughts (checkers) program improved with play, is often credited with coining the term machine learning. In supervised learning, success is measured not on the training set but on a separate test set held back from training. A model that memorises its training examples, noise and all, may score almost perfectly on them and poorly on new data; this is overfitting. A classic success was ALVINN at Carnegie Mellon University in the late 1980s, a neural network that learned to steer a van by watching a human driver's steering choices and adjusting itself to match them.

Worked example: a nearest-neighbour classifier

Messages are described by (links, exclamation marks). Training set: A (0, 1) not spam; B (1, 0) not spam; C (6, 5) spam; D (5, 7) spam; E (2, 2) not spam. Classify a new message at (4, 4). 1. Measure squared distance to each example: A is 16 + 9 = 25, B is 9 + 16 = 25, C is 4 + 1 = 5, D is 1 + 9 = 10, E is 4 + 4 = 8. 2. The nearest is C, which is spam, so the 1-nearest-neighbour answer is spam. 3. With 3 neighbours, the closest three are C, E and D: two spam to one, so still spam. 4. Note what was learned: no rule was written; the labelled examples themselves decide.

Discovery

Learning has a target, such as recognising spam. Discovery is open-ended: finding something unexpected. A discovering system must judge which leads are worth following and which findings matter, since a data-mining program that reports every trivial pattern is useless. Programs named BACON, developed from the late 1970s, rediscovered laws of physics, including Kepler's third law of planetary motion, from tables of measurements. Today, learning systems help scientists sift data for new candidate materials, drugs and astronomical objects, though people still judge which results are real.

Worked example: one generation of a genetic algorithm

A genetic algorithm evolves solutions. Each trial solution is a chromosome made of genes; fitter ones are more likely to become parents; children mix their parents' genes by crossover, and occasional mutation adds random change. Task: find a 6-bit string with as many 1s as possible. Population: 110100, 011011, 000110, 111001, with fitness (number of 1s) 3, 4, 2, 4. 1. Select the two fittest, 011011 and 111001. 2. Cross over after bit 3: 011 + 001 gives 011001, and 111 + 011 gives 111011. 3. Mutate bit 4 of the first child: 011001 becomes 011101. 4. The best fitness rose from 4 to 5. There is no guarantee of the best answer, but repeated generations often find very good ones.

Common mistakes to avoid

First, treating stored data as knowledge: the hard part is representing, retrieving and updating what matters. Second, assuming the closed-world assumption is always safe; with an 'or' fact it produces a contradiction. Third, forgetting that a specific link such as 'penguin cannot fly' overrides an inherited default. Fourth, judging a learned model on its training data, which hides overfitting. Fifth, confusing reinforcement learning, which gets only rewards, with supervised learning, which gets the correct answers. Sixth, expecting a genetic algorithm to guarantee the optimum.

Key takeaways

Common-sense knowledge is easy for people and hard for machines. Semantic nets, frames and logic represent knowledge; semantic nets inherit along is-a links, with specific links overriding defaults. Systems must pick relevant facts, use meta-reasoning such as the closed-world assumption with care, and face the frame problem of tracking change. Learning ranges from imitation to supervised, reinforcement and unsupervised learning; test sets expose overfitting, and nearest-neighbour classifiers let labelled examples decide. Discovery seeks the unexpected. Genetic algorithms evolve solutions through selection, crossover and mutation.

Flashcards

Flashcard

Real-world knowledge

The vast store of everyday facts people use to understand the world

Often called common sense.

Test your understanding

Question 1 of 5

Using the training set from the nearest-neighbour example, which example is nearest to a new message at (1, 2), and how is the message classed?

Question 2 of 5

A program learns a video game by playing it repeatedly, told only its final score after each attempt. Which kind of learning is this?

Question 3 of 5

A library database lists the borrowers who owe fines. Maya is not on the list. Under the closed-world assumption, what does the system conclude?

Question 4 of 5

Parents 101100 and 010111 are crossed over after bit 2. What are the two children?

Question 5 of 5

A model scores 99% on its training examples but only 70% on a held-back test set. What does this most likely show?

← Previous topicNext topic →