Search, Knowledge and Reasoning

Week 3 of 14 · Foundations · 7 days

Week 03 · Foundations

Search, Knowledge and Reasoning

Week 03 · Day 1 of 7

Answers You Derive Rather Than Learn

States, goals, and the one line that separates two search strategies

Week 2 was about learning from examples. This week is about the other half of artificial intelligence, the half that came first and is still running a great deal of software: getting an answer by searching through possibilities rather than by learning from data.

It matters for two reasons. Plenty of real problems have this shape and are solved badly with machine learning. And the vocabulary of this tradition, states, goals, heuristics and constraints, is how a lot of AI work is still described.

The problem shape

A search problem: A set of states, a rule for which states you can move to from each one, a starting state and a test for whether you have arrived. Nothing is learned. The answer is derived, and it can be proved optimal.

GRID = [
    '...#........',
    '...#........',
    '.#......#..#',
    '....#..#..#.',
    '#...#...#...',
    '..........##',
    '...#........',
    '.#..........',
    '.#....#.##..',
    '.##.#....#..',
    '....##.###..',
    '#.###..#.##.',
]
ROWS, COLS = len(GRID), len(GRID[0])
START, GOAL = (0, 0), (ROWS - 1, COLS - 1)

def neighbours(cell):
    r, c = cell
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < ROWS and 0 <= nc < COLS and GRID[nr][nc] != '#':
            yield (nr, nc)

def show(path):
    marked = set(path or [])
    for r in range(ROWS):
        print(''.join('o' if (r, c) in marked else GRID[r][c]
                      for c in range(COLS)))
show([])
print()
print('start %s, goal %s' % (START, GOAL))

...#........
...#........
.#......#..#
....#..#..#.
#...#...#...
..........##
...#........
.#..........
.#....#.##..
.##.#....#..
....##.###..
#.###..#.##.

start (0, 0), goal (11, 11)

Breadth first: correct, and wasteful

Explore everything one step away, then everything two steps away, and so on. The first time you reach the goal you are guaranteed to have done it in the fewest possible moves, because you have already ruled out every shorter route.

GRID = [
    '...#........',
    '...#........',
    '.#......#..#',
    '....#..#..#.',
    '#...#...#...',
    '..........##',
    '...#........',
    '.#..........',
    '.#....#.##..',
    '.##.#....#..',
    '....##.###..',
    '#.###..#.##.',
]
ROWS, COLS = len(GRID), len(GRID[0])
START, GOAL = (0, 0), (ROWS - 1, COLS - 1)

def neighbours(cell):
    r, c = cell
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < ROWS and 0 <= nc < COLS and GRID[nr][nc] != '#':
            yield (nr, nc)

def show(path):
    marked = set(path or [])
    for r in range(ROWS):
        print(''.join('o' if (r, c) in marked else GRID[r][c]
                      for c in range(COLS)))
from collections import deque

def breadth_first(start, goal):
    queue = deque([[start]])
    seen = {start}
    expanded = 0
    while queue:
        path = queue.popleft()
        expanded += 1
        if path[-1] == goal:
            return path, expanded
        for nxt in neighbours(path[-1]):
            if nxt not in seen:
                seen.add(nxt)
                queue.append(path + [nxt])
    return None, expanded

path, expanded = breadth_first(START, GOAL)
show(path)
print()
print('%d steps, %d states examined' % (len(path) - 1, expanded))

o..#........
o..#........
o#......#..#
oo..#..#..#.
#o..#...#...
.o........##
.oo#........
.#ooooooooo.
.#....#.##o.
.##.#....#o.
....##.###oo
#.###..#.##o

22 steps, 108 states examined

Depth first: cheap, and not shortest

GRID = [
    '...#........',
    '...#........',
    '.#......#..#',
    '....#..#..#.',
    '#...#...#...',
    '..........##',
    '...#........',
    '.#..........',
    '.#....#.##..',
    '.##.#....#..',
    '....##.###..',
    '#.###..#.##.',
]
ROWS, COLS = len(GRID), len(GRID[0])
START, GOAL = (0, 0), (ROWS - 1, COLS - 1)

def neighbours(cell):
    r, c = cell
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < ROWS and 0 <= nc < COLS and GRID[nr][nc] != '#':
            yield (nr, nc)

def show(path):
    marked = set(path or [])
    for r in range(ROWS):
        print(''.join('o' if (r, c) in marked else GRID[r][c]
                      for c in range(COLS)))
def depth_first(start, goal):
    stack = [[start]]
    seen = {start}
    expanded = 0
    while stack:
        path = stack.pop()
        expanded += 1
        if path[-1] == goal:
            return path, expanded
        for nxt in neighbours(path[-1]):
            if nxt not in seen:
                seen.add(nxt)
                stack.append(path + [nxt])
    return None, expanded

path, expanded = depth_first(START, GOAL)
print('%d steps, %d states examined' % (len(path) - 1, expanded))
print('breadth first found a shorter route, having looked at more')

48 steps, 64 states examined
breadth first found a shorter route, having looked at more

One line differs between those two functions: whether you take work from the front of the queue or the back. That single choice decides whether the answer is guaranteed shortest and how much memory the search needs, which is a good illustration of how much structure sits in very small decisions here.

Week 03 · Day 2 of 7

Giving the Search a Hint

Heuristics, A*, and reducing work without changing the answer

By Pawan Rama Mali640 words

Breadth first searches in every direction equally, including directly away from the goal. Since we know where the goal is, that is obviously wasteful, and the fix is to give the search a hint.

A heuristic: A cheap estimate of the remaining distance from a state to the goal. If it never overestimates, it is called admissible, and a search that prefers states with the lowest estimated total cost is still guaranteed to find the shortest route.

GRID = [
    '...#........',
    '...#........',
    '.#......#..#',
    '....#..#..#.',
    '#...#...#...',
    '..........##',
    '...#........',
    '.#..........',
    '.#....#.##..',
    '.##.#....#..',
    '....##.###..',
    '#.###..#.##.',
]
ROWS, COLS = len(GRID), len(GRID[0])
START, GOAL = (0, 0), (ROWS - 1, COLS - 1)

def neighbours(cell):
    r, c = cell
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < ROWS and 0 <= nc < COLS and GRID[nr][nc] != '#':
            yield (nr, nc)

def show(path):
    marked = set(path or [])
    for r in range(ROWS):
        print(''.join('o' if (r, c) in marked else GRID[r][c]
                      for c in range(COLS)))
import heapq

def manhattan(cell, goal):
    """Straight line distance ignoring walls. It can never be more
    than the true distance, which is what makes A* safe to trust."""
    return abs(cell[0] - goal[0]) + abs(cell[1] - goal[1])

def a_star(start, goal):
    queue = [(manhattan(start, goal), 0, [start])]
    best = {start: 0}
    expanded = 0
    while queue:
        _, cost, path = heapq.heappop(queue)
        expanded += 1
        if path[-1] == goal:
            return path, expanded
        for nxt in neighbours(path[-1]):
            if cost + 1 < best.get(nxt, 10 ** 9):
                best[nxt] = cost + 1
                heapq.heappush(queue, (cost + 1 + manhattan(nxt, goal),
                                       cost + 1, path + [nxt]))
    return None, expanded

path, expanded = a_star(START, GOAL)
show(path)
print()
print('%d steps, %d states examined' % (len(path) - 1, expanded))

ooo#........
..o#........
.#ooooo.#..#
....#.o#..#.
#...#.oo#...
.......ooo##
...#.....ooo
.#.........o
.#....#.##.o
.##.#....#.o
....##.###.o
#.###..#.##o

22 steps, 74 states examined

GRID = [
    '...#........',
    '...#........',
    '.#......#..#',
    '....#..#..#.',
    '#...#...#...',
    '..........##',
    '...#........',
    '.#..........',
    '.#....#.##..',
    '.##.#....#..',
    '....##.###..',
    '#.###..#.##.',
]
ROWS, COLS = len(GRID), len(GRID[0])
START, GOAL = (0, 0), (ROWS - 1, COLS - 1)

def neighbours(cell):
    r, c = cell
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < ROWS and 0 <= nc < COLS and GRID[nr][nc] != '#':
            yield (nr, nc)

def show(path):
    marked = set(path or [])
    for r in range(ROWS):
        print(''.join('o' if (r, c) in marked else GRID[r][c]
                      for c in range(COLS)))
from collections import deque
import heapq

def breadth_first(start, goal):
    queue, seen, expanded = deque([[start]]), {start}, 0
    while queue:
        path = queue.popleft()
        expanded += 1
        if path[-1] == goal:
            return path, expanded
        for nxt in neighbours(path[-1]):
            if nxt not in seen:
                seen.add(nxt)
                queue.append(path + [nxt])
    return None, expanded

def manhattan(cell, goal):
    return abs(cell[0] - goal[0]) + abs(cell[1] - goal[1])

def a_star(start, goal):
    queue, best, expanded = [(manhattan(start, goal), 0, [start])], {start: 0}, 0
    while queue:
        _, cost, path = heapq.heappop(queue)
        expanded += 1
        if path[-1] == goal:
            return path, expanded
        for nxt in neighbours(path[-1]):
            if cost + 1 < best.get(nxt, 10 ** 9):
                best[nxt] = cost + 1
                heapq.heappush(queue, (cost + 1 + manhattan(nxt, goal),
                                       cost + 1, path + [nxt]))
    return None, expanded

print('%-16s %8s %10s' % ('', 'steps', 'examined'))
for name, fn in [('breadth first', breadth_first), ('a star', a_star)]:
    path, expanded = fn(START, GOAL)
    print('%-16s %8d %10d' % (name, len(path) - 1, expanded))

                    steps   examined
breadth first          22        108
a star                 22         74

The same shortest route, found while looking at fewer states. That is the entire contribution of a heuristic: it does not improve the answer, it reduces the work needed to prove the answer. On a ten by ten grid this is a curiosity. On a road network it is the difference between a route planner and a machine that never replies.

This is the tradition modern AI grew out of

A* is from 1968. Route planning, puzzle solving, task scheduling and game playing all still use it or its descendants, and a satellite navigation system is doing this rather than anything learned. Search did not get replaced by machine learning. It continued to be the right tool for problems where the rules are known and the difficulty is the size of the space.

Week 03 · Day 3 of 7

Assignments That Break No Rules

Constraint problems, backtracking, and proving there is no solution

By Pawan Rama Mali445 words

A second classical shape, and one you will recognise from timetabling, rostering, seating plans and sudoku: you are not looking for a path, you are looking for an assignment that breaks no rules.

A constraint satisfaction problem: Variables, a set of allowed values for each, and constraints saying which combinations are permitted. A solution assigns every variable a value while satisfying every constraint.

# Four talks, three rooms, some of which cannot share a slot because
# the same speaker or the same audience is involved.
TALKS = ['ethics', 'vision', 'language', 'safety']
SLOTS = ['morning', 'afternoon', 'evening']
CLASH = [('ethics', 'safety'), ('vision', 'language'),
         ('ethics', 'language')]

def ok(assignment):
    for a, b in CLASH:
        if a in assignment and b in assignment:
            if assignment[a] == assignment[b]:
                return False
    return True

def solve(assignment, tried):
    """Backtracking: assign one variable, check, and undo if stuck."""
    if len(assignment) == len(TALKS):
        return assignment, tried
    talk = TALKS[len(assignment)]
    for slot in SLOTS:
        assignment[talk] = slot
        tried += 1
        if ok(assignment):
            result, tried = solve(assignment, tried)
            if result:
                return result, tried
        del assignment[talk]
    return None, tried

answer, tried = solve({}, 0)
for talk in TALKS:
    print('%-10s %s' % (talk, answer[talk]))
print()
print('found after %d assignments, out of %d possible timetables'
      % (tried, len(SLOTS) ** len(TALKS)))

ethics     morning
vision     morning
language   afternoon
safety     afternoon

found after 6 assignments, out of 81 possible timetables

The important number is the last line. There are eighty-one possible timetables and the solver examined far fewer, because checking constraints as it went let it abandon whole branches the moment they became impossible. That is the core idea, and it scales to problems with billions of combinations.

When there is no solution

TALKS = ['a', 'b', 'c']
SLOTS = ['morning', 'afternoon']
CLASH = [('a', 'b'), ('b', 'c'), ('a', 'c')]

def ok(assignment):
    return all(not (a in assignment and b in assignment
                    and assignment[a] == assignment[b])
               for a, b in CLASH)

def solve(assignment):
    if len(assignment) == len(TALKS):
        return assignment
    talk = TALKS[len(assignment)]
    for slot in SLOTS:
        assignment[talk] = slot
        if ok(assignment):
            result = solve(assignment)
            if result:
                return result
        del assignment[talk]
    return None

print('three talks that all clash, two slots: %s' % solve({}))
print('the solver proves there is no timetable, rather than guessing')

three talks that all clash, two slots: None
the solver proves there is no timetable, rather than guessing

Something no learned model can do

The solver returned None, and that answer is certain. It did not fail to find a timetable, it established that none exists.

A neural network asked the same question would return a confident-looking answer, because returning something is all it can do. When a problem requires a guarantee, and scheduling, routing and verification often do, this tradition is not a fallback. It is the only option.

Week 03 · Day 4 of 7

Writing Down What You Know

Knowledge bases, inheritance, and the penguin that broke them

By Pawan Rama Mali460 words

The third classical strand tried to capture knowledge itself: facts and rules about the world, in a form a program could reason over. This was the dominant idea of AI for roughly thirty years and it is worth understanding both for what it does well and for how it failed.

FACTS = {
    ('sparrow', 'is a', 'bird'), ('bird', 'is a', 'animal'),
    ('penguin', 'is a', 'bird'), ('animal', 'needs', 'food'),
    ('bird', 'can', 'fly'), ('penguin', 'cannot', 'fly'),
}

def ask(subject, relation, depth=0):
    """Follow 'is a' links upward, inheriting properties."""
    answers = []
    for s, r, o in FACTS:
        if s == subject and r == relation:
            answers.append((o, depth))
    for s, r, o in FACTS:
        if s == subject and r == 'is a':
            answers.extend(ask(o, relation, depth + 1))
    return answers

for subject in ['sparrow', 'penguin']:
    print('%s can: %s' % (subject,
                          [a for a, _ in ask(subject, 'can')]))
    print('%s needs: %s' % (subject,
                            [a for a, _ in ask(subject, 'needs')]))

sparrow can: ['fly']
sparrow needs: ['food']
penguin can: ['fly']
penguin needs: ['food']

Nobody wrote down that a sparrow needs food. The system derived it from two facts and one rule about inheritance, and it can explain exactly how. That combination, deriving new facts and being able to justify them, is what made this approach so attractive.

And here is where it broke

FACTS = {
    ('penguin', 'is a', 'bird'), ('bird', 'can', 'fly'),
    ('penguin', 'cannot', 'fly'),
}

def inherited(subject, relation):
    out = []
    for s, r, o in FACTS:
        if s == subject and r == relation:
            out.append(o)
    for s, r, o in FACTS:
        if s == subject and r == 'is a':
            out.extend(inherited(o, relation))
    return out

print('can a penguin fly?')
print('   inherited from bird:', inherited('penguin', 'can'))
print('   stated directly:    ', inherited('penguin', 'cannot'))
print()
print('the knowledge base now says both, and nothing in it decides')

can a penguin fly?
   inherited from bird: ['fly']
   stated directly:     ['fly']

the knowledge base now says both, and nothing in it decides

Birds fly. Penguins are birds. Penguins do not fly. Every one of those is true, and together they are inconsistent unless the system knows that specific facts override inherited ones, and by how much, and what to do when two specific facts disagree.

Why symbolic AI stalled

Each exception is easy to patch. The difficulty is that there are an unbounded number of them, most are never written down because they are too obvious to state, and every patch can interact with every other. Systems built this way became too large for anybody to maintain and too brittle to trust outside the cases they were built for.

This is not a story about a bad idea. It is a story about a good idea meeting the fact that most human knowledge is tacit, and it is precisely the gap that learning from examples fills, because examples contain the exceptions without anyone having to enumerate them.

Week 03 · Day 5 of 7

Reasoning Under Uncertainty

The 99 percent accurate test that means almost nothing

By Pawan Rama Mali339 words

Both traditions have a way of handling uncertainty. The symbolic one attaches probabilities to facts, and the arithmetic that results is worth doing once by hand, because the answer is deeply counter-intuitive and it appears constantly in medicine, screening and fraud.

# A test for a condition that affects 1 person in 1000.
prevalence = 0.001
sensitivity = 0.99   # finds 99% of real cases
specificity = 0.99   # correctly clears 99% of healthy people

population = 1_000_000
ill = population * prevalence
well = population - ill
true_positive = ill * sensitivity
false_positive = well * (1 - specificity)

print('in a million people:')
print('  %8.0f have the condition' % ill)
print('  %8.0f of them test positive' % true_positive)
print('  %8.0f healthy people also test positive' % false_positive)
print()
print('so a positive test means a %.1f%% chance of being ill'
      % (100 * true_positive / (true_positive + false_positive)))

in a million people:
      1000 have the condition
       990 of them test positive
      9990 healthy people also test positive

so a positive test means a 9.0% chance of being ill

A test that is 99 percent accurate in both directions, and a positive result still means you are probably fine. There is no error in the arithmetic. There are simply far more healthy people, so the one percent of them that the test gets wrong outnumbers the ill people it gets right.

Base rate neglect: Judging the meaning of evidence without accounting for how common the thing was to begin with. It is the single most consequential statistical mistake in applied AI, and it is the same fact that made week 2's 96 percent accurate fraud model worthless.

Where this bites in practice

Any model looking for something rare produces mostly false positives at the point of use, however good its metrics look. A screening tool, a fraud flag, a security alert: if the thing is rare enough, most of what the system reports will be wrong, and the system can still be extremely useful.

What it cannot be is automatic. It is a filter that makes human review affordable, and describing it as anything more than that sets up a failure.

Week 03 · Day 6 of 7

Two Traditions, One System

What each is genuinely good at, and how real systems combine them

By Pawan Rama Mali264 words

Neither tradition won. The interesting systems now use both, and knowing which part of a problem belongs to which is a genuinely useful skill.

	Search and rules	Learning from examples
Needs	Someone who knows the rules	Labelled examples
Handles novelty	Only within the rules it was given	Interpolates, and fails unpredictably outside its data
Explains itself	Completely	Only with extra work
Can prove there is no answer	Yes	No
Handles messy input	Badly	Well
Fails	Visibly, by finding nothing	Quietly, with a confident wrong answer

How they combine in real systems

A route planner learns how long each road takes from traffic data, then searches over the road network with those learned costs. Learning supplies the numbers, search supplies the guarantee.
A game engine learns a rough evaluation of positions, then searches ahead using it. This is how the strongest chess and go programs work, and neither half would be enough alone.
A language model with tools generates text and calls a calculator, a database or a solver for the parts that need an exact answer. This is the same division of labour with new names.
A fraud system scores transactions with a model and applies hard rules for the cases where the law or the policy is not negotiable.

The pattern worth extracting

In every one of those, learning is used where the pattern is real but nobody can state it, and search or rules are used where an answer must be exact, explainable or guaranteed. That division is not a compromise between two schools. It is what each is actually good at.

Week 03 · Day 7 of 7

Learned Numbers, Derived Answers

A worked hybrid, and what it does and does not guarantee

By Pawan Rama Mali410 words

One problem, solved with both halves of the week, which is the shape a real system usually takes.

import heapq

# Delivery times between stops, as learned from historical data.
# In a real system these numbers come from a regression model.
LEARNED_MINUTES = {
    ('depot', 'north'): 12, ('depot', 'east'): 9,
    ('north', 'ring'): 7, ('east', 'ring'): 15,
    ('east', 'south'): 8, ('ring', 'airport'): 11,
    ('south', 'airport'): 21, ('north', 'east'): 6,
}
STOPS = set()
for a, b in LEARNED_MINUTES:
    STOPS.update([a, b])

def cheapest(start, goal):
    """Search, over costs that were learned rather than measured."""
    queue = [(0, [start])]
    best = {start: 0}
    while queue:
        cost, path = heapq.heappop(queue)
        if path[-1] == goal:
            return cost, path
        for (a, b), minutes in LEARNED_MINUTES.items():
            if a == path[-1] and cost + minutes < best.get(b, 10 ** 9):
                best[b] = cost + minutes
                heapq.heappush(queue, (cost + minutes, path + [b]))
    return None, None

cost, path = cheapest('depot', 'airport')
print('%d minutes: %s' % (cost, ' -> '.join(path)))
print()
print('the travel times were learned; the route was derived')
print('and is provably the cheapest given those times')

30 minutes: depot -> north -> ring -> airport

the travel times were learned; the route was derived
and is provably the cheapest given those times

Note carefully what is guaranteed and what is not. The route is provably optimal given the travel times. If the learned times are wrong, the route is confidently wrong, and the search cannot tell. Combining the two traditions does not combine their guarantees, it chains them.

What the week established

Search solves problems where the rules are known and the difficulty is the number of possibilities, and it can prove its answer optimal.
A heuristic does not improve the answer, it reduces the work needed to reach it.
Constraint problems can prove that no solution exists, which no learned model can do.
Symbolic knowledge systems reason and explain beautifully, and failed on the unbounded number of exceptions nobody writes down.
Base rates decide what a positive result means, and ignoring them is the most consequential statistical error in this field.
Real systems use both traditions, with learning supplying the estimates and search supplying the guarantees.

Carrying this into the rest of the course

Weeks 4 to 10 are entirely about learning from examples, because that is what the language and vision problems need. Keep this week in view anyway: a good deal of the work labelled AI in industry is a search or a rule engine, and proposing a neural network for it is a mistake this week should have made you able to avoid.