Computation under finite resources

1Thinking takes time

So far we have asked what an agent should believe or do. We have quietly assumed it can always work the answer out. Real agents cannot. A phone has a small battery. A self-driving car has a fraction of a second to decide. Your brain runs on about 20 watts. Even a data centre has a budget.

So intelligence is not only about getting the right answer. It is about getting a good enough answer with the time, memory and data you actually have. The economist and computer scientist Herbert Simon called this bounded rationality, and he argued it was the normal condition of every real decision-maker.

This week gives you the tools to think about cost: how to count the work an algorithm does, how to spot work that explodes, and three ways intelligent systems cope. Two of those ways you have already seen without knowing it.

2Counting steps

An algorithm is a precise recipe for getting an answer: a list of steps that a computer, or a patient person, could follow without thinking. The same question can usually be answered by many algorithms, and some do far less work than others.

Take the simplest question there is: where is this item in a list? If the list is in no particular order, you have to look at items one by one until you find it. That is linear search. If the list is sorted, you can do what you did in Week 3's guessing game: look at the middle, throw away the half that cannot contain it, repeat. That is binary search.

def binary_search(items, target):
    lo, hi = 0, len(items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2           # look in the middle
        if items[mid] == target:
            return mid
        if items[mid] < target:
            lo = mid + 1               # throw away the left half
        else:
            hi = mid - 1               # throw away the right half

Making the list 1,000 times longer makes linear search 1,000 times slower, but adds only 10 steps to binary search. Each step of binary search is one yes-or-no question, so it needs about log₂ n steps: the number of bits needed to pick one item out of n. Week 3 and this week are closer than they look.

How the count grows: big-O

Exact step counts depend on details: the computer, the language, how you count. What matters more is how the count grows as the problem gets bigger. Computer scientists write this with big-O notation. "Linear search is O(n)" means: double the list, and the work roughly doubles. "Binary search is O(log n)" means: double the list, and the work goes up by one step.

The first three rows are called polynomial: they grow, but manageably. The last row is exponential, and it is a different kind of thing altogether. Every extra item doubles the work.

3The exponential wall

Back to the umbrella world. In Week 2 the agent asked: given all the rain so far, how likely is it that we are in the rainy season today? Here is the most obvious way to answer.

The season is hidden. On each day it was either rainy or dry, so over n days there are 2ⁿ possible season histories: rainy-rainy-dry-…, rainy-dry-dry-…, and so on. For each one, work out how likely it is and how well it explains the rain we saw. Then add up the histories that end in the rainy season and divide by the total. This is just Bayes' rule from Week 2, applied to whole histories. It is correct, and it is a disaster.

def brute_force(rains):
    top = total = 0.0
    for history in itertools.product(("rainy", "dry"), repeat=len(rains)):
        p = # chance of this history × chance it produces this rain
        total += p
        if history[-1] == "rainy":
            top += p
    return top / total

Part B of the code runs it on the first few days of a simulated record and, alongside it, the Week 2 belief agent.

Every four extra days multiply the brute-force work by about 20. Where does that lead? Scaling up the measured 4.2 seconds:

A faster computer barely helps. A machine a million times faster turns 460,000 years into about 5 months, and then adding just 20 more days of weather puts it back where it started. This is what people mean by an exponential wall. Many problems in AI hit it: planning many moves ahead, finding the best combination of features, reasoning about many hidden variables at once.

4Reuse your work: dynamic programming

Look at the last column of Table 3 again. The Week 2 belief agent gets exactly the same answers in 20 steps instead of 20 million. How?

Brute force recomputes everything from scratch for every history. But most of that work is repeated. Every history that starts rainy-rainy-dry shares the same first three days, and brute force works those out again for each of the millions of histories that begin that way. The belief agent does it once. At the end of each day it keeps one number, P(rainy season so far), which already sums up all the histories up to that point. Tomorrow it starts from there.

This strategy, store the answer to a smaller problem and build the next answer from it, is called dynamic programming. It turns the O(2ⁿ) wall into O(n): double the days, double the work.

It only works because of a property of the world. Tomorrow's season depends only on today's season, not on the whole history before it. That property means today's belief is a complete summary of the past for the purpose of predicting the future. Week 2 called this a belief state; now you can see why it is valuable. It is the summary that makes the computation cheap.

Established result For hidden-state models of this kind, this way of computing the belief (called the forward algorithm, or filtering) is exact and takes time proportional to the number of days. It is standard material in any probabilistic AI textbook.

5Memory has a cost too

Time is one resource. Memory, and the data needed to fill it, is another. In Week 1 the learner did not remember its exact past: it counted how many of the last k days were rainy. Suppose instead it remembered the exact pattern, like "rain, dry, dry, rain, …", and learned a separate rule for each pattern and each kind of sky.

With k days there are 2^k patterns, times 2 for the sky. With 14 days that is 32,768 situations. The learner has 20,000 days of training data. Part C of the code compares the two learners.

With exact patterns and 14 days of memory, nearly 30% of test days are situations the learner has never seen, so it has no rule for them and simply guesses "no rain". The situations it did see appeared only about twice each on average (8,851 situations from 20,000 days), so its rules rest on very little. The result, 0.639, is worse than looking at the sky alone (about 0.66 in Week 1). The count needs only 30 situations for 14 days, so each one is seen far more often, and it keeps its accuracy.

Notice that the exact pattern contains more information than the count. Week 3 would say it can only help. It does not help because the learner cannot afford it: there is not enough data to learn 32,768 separate rules. This problem has a name, the curse of dimensionality, and it is the starting point for Week 5: how to learn things that work on situations you have not seen before.

Exploratory observation In this simulation, exact memory beyond about 7 days hurt, and a coarse count did not. This is one world and one seed. Seminar exercise 3 asks how the picture changes with more training data.

6Good enough, on a budget

Dynamic programming worked because the umbrella world has a convenient structure. Many real problems do not, and there is no known trick that makes them fast. What then?

Often the answer is to approximate: accept an answer that is probably close, in exchange for a fixed, affordable cost. One of the most widely used methods is random sampling. Instead of listing all 2ⁿ season histories, draw a few thousand at random, weight each by how well it explains the rain, and use those as a stand-in for all of them. It is like an opinion poll: you do not need to ask everyone to get a decent estimate.

def sample_estimate(rains, samples, rng):
    top = total = 0.0
    for _ in range(samples):
        # draw one random season history, and a weight for
        # how well it explains the rain we actually saw
        ...
        total += weight
        if season == "rainy":
            top += weight
    return top / total

Part D estimates the belief after 40 days of weather, where brute force would take months. The exact answer, from the belief agent, is 0.1287. Each budget is tried 50 times.

Two things to notice:

• You choose the budget. The cost depends on the number of samples, not on the 2⁴⁰ histories. You can stop whenever you run out of time and still have an answer.
• Returns diminish. Each tenfold increase in samples only roughly halves the error. Getting very precise answers by sampling is expensive. Often you do not need them: Week 2 showed that a decision only depends on which side of a threshold you are on.

Bounded rationality

Put the three ideas together. Real intelligent systems rarely compute the perfect answer. They choose good summaries (Section 4), keep only what they can learn from (Section 5), and approximate when exact answers are out of reach (Section 6). Simon's word for aiming at "good enough" rather than "best" was satisficing. A newer view, sometimes called computational rationality, treats the choice of how much to think as a decision too: think longer only when the extra accuracy is worth the extra cost.

Open question Some problems seem to have no fast exact algorithm at all, however clever we are. Whether that is truly so for a large family of such problems is the famous "P versus NP" question. Nobody knows the answer, and there is a million-dollar prize for it.

7Summary

• Every computation costs time and memory, and real agents have limited amounts of both. Intelligence means getting good answers within those limits.
• An algorithm's cost is best described by how it grows with the problem size. Binary search is O(log n); linear search is O(n).
• Exponential algorithms double their work with every extra item. Brute-force season inference took 4 seconds for 20 days and would take hundreds of thousands of years for 60.
• Dynamic programming reuses earlier results. The Week 2 belief agent computes the same answer in time proportional to the number of days.
• Storing more detail can make learning worse when data is limited: exact 14-day patterns scored 0.639, while a simple count scored 0.719.
• Random sampling gives approximate answers at a cost you choose. Each tenfold increase in samples roughly halved the error.

·Key terms

Algorithm

A precise, step-by-step recipe for computing an answer.

Linear search

Checking items one at a time. O(n).

Binary search

Halving a sorted list at each step. O(log n).

Big-O notation

A description of how an algorithm's cost grows with the size of the problem.

Polynomial time

Cost that grows like n, n², n³ and so on. Usually manageable.

Exponential time

Cost that doubles (or worse) with every extra item, like 2ⁿ. Quickly hopeless.

Brute force

Solving a problem by trying every possibility.

Dynamic programming

Solving a problem by storing answers to smaller parts and building on them instead of recomputing.

Curse of dimensionality

As the number of details describing a situation grows, the number of possible situations explodes, and data to learn about each one runs out.

Approximation

Accepting an answer that is probably close, in exchange for a lower cost.

Random sampling

Estimating a quantity from randomly chosen cases instead of all of them.

Bounded rationality

Making the best decisions possible given limited time, memory, information and computing power.

·Check your understanding

Try each question before opening the answer.

1. About how many steps does binary search need for a sorted list of 1,000,000,000 items?
   Show answer

   About 30, because 2³⁰ ≈ 1,000,000,000. A thousand times more items than the million in Table 1, and only 10 more steps.

2. An algorithm is O(n²). It takes 1 second for 1,000 items. Roughly how long for 10,000?
   Show answer

   About 100 seconds. Ten times the items means 10² = 100 times the work.

3. Brute force for 20 days took about 4 seconds. Without looking at Table 4, roughly how long for 21 days? For 30?
   Show answer

   21 days: a bit more than double, about 9 seconds, because there are twice as many histories and each is one day longer. 30 days: ten more doublings, about 1,000 times longer, so over an hour; Table 4 says about 2 hours once the longer histories are counted.

4. Why can the belief agent get away with keeping just one number, when brute force has to look at every history?
   Show answer

   Because tomorrow's season depends only on today's. So everything the past says about the future is captured by today's belief about the season. Brute force does not exploit this and recomputes the shared parts of histories again and again.

5. The exact-pattern learner has more information than the counting learner. Why does it do worse at k = 14?
   Show answer

   It has 32,768 possible situations and only 20,000 training days. Many test situations were never seen (about 30%) and many others were seen too rarely to learn a reliable rule. The counting learner has only 30 situations, each seen many times.

·Seminar exercises

As always, write your prediction before you run anything.

1. Time it yourself. Run brute_force for 18, 20 and 22 days on your own computer. Predict the 22-day time from the 18- and 20-day times before you run it. How close were you?
2. Sorting costs. Write the simplest sorting method you can think of, and count its steps for lists of 100, 1,000 and 10,000 random numbers. What is its big-O? Compare with Python's sorted using time.perf_counter. Is binary search still worth it if you have to sort the list first, just to search it once? What if you search it a thousand times?
3. More data. Repeat Table 5 with 200,000 training days instead of 20,000. Predict first: at which k will the exact-pattern learner now start to fall behind the count? Does the 30% "unseen" figure change?
4. Thinking is a decision. Combine Week 2's costs (soaked: 3; carrying the umbrella for nothing: 1) with sampling. Suppose each 1,000 samples costs 0.01. Write an agent that chooses how many samples to draw each morning. When is it worth thinking harder?

·Readings

• Core. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms (4th ed.). MIT Press. Chapters 1 and 2, and the first part of Chapter 3 on growth of functions. Skim the proofs; focus on the examples.
• Core. Simon, H. A. (1955). A behavioral model of rational choice. Quarterly Journal of Economics, 69(1). The original argument for bounded rationality. Focus on the introduction and the idea of "satisfactory" outcomes.
• Further. Gershman, S. J., Horvitz, E. J., & Tenenbaum, J. B. (2015). Computational rationality: A converging paradigm for intelligence in brains, minds, and machines. Science, 349(6245). A short modern review of thinking as a resource-limited decision.