Computers can make decisions, and they can do things very very fast.
An important part of computer science is understanding how computers can make the right decisions.
In this chapter, you’ll learn how computers use lots of simple decisions to make complex decisions quickly and precisely.
One of the ways computers make decisions is with a decision tree. Decision trees encode a series of simple yes-or-no questions that you can follow to answer a more complex question.
Here’s a simple face recognizer:
Which of the listed faces will require the computer to ask the most questions?
Let’s try building a face-recognizing decision tree from scratch.
The computer gets a few pieces of information from a camera that can detect glasses, long hair, and open mouths. The computer uses this information to answer the decision tree’s questions, allowing it to distinguish between all the faces.
The first question, which is at the very top of the decision tree, is an especially important one.
Imagine that you want to make a decision tree that can distinguish the four faces above. If you want the root of the decision tree to split the faces into two groups of two, which question should you ask first?
The first question in your decision tree splits the faces into two distinct groups.
What is a single question that you could ask of both remaining groups to narrow down to a single face?
In the last question, none of the choices you were given were able to further split up both of the groups of two faces.
However, you can make a decision tree that distinguishes all four faces by asking a different follow-up question based on the answer to the first question.
This flexibility makes decision trees quite powerful.
The last tree split the faces into even groups with each question. Decision trees like this are called balanced.
If we choose our questions carefully, we can build an even bigger balanced tree that can distinguish faces:
If your computer is using this decision tree, how many questions, on average, will it need to ask in order to distinguish a random face?
The shape of a decision tree can have a big impact on the number of questions you have to ask.
The tree we just saw was balanced, and could distinguish every face using questions.
The first tree we saw in this quiz distinguished the same faces, but had a wider range in the number of questions required:
How many of the faces take more than questions to identify using this decision tree?
This decision tree has instructions for distinguishing six faces. Which face will you land on if you use this to identify the following, different face?
The decision tree didn't do a good job recognizing this face. They're about as different as can be, but the computer decided they're similar!
Asked in the context of the original faces, the decision tree works just fine. But, with just a slight change in Person A's appearance, the tree is unable to distinguish him from Person F, blue hair and all.
This is a simple example, but if you pay attention to the news, you'll see real-world examples of the same kind of failure.
It can be funny when computers make mistakes because they were designed with limited information.
These mistakes happen because decision trees don’t “see” faces or dogs. They only consider the features that we tell them to.
In this case, the computer is focusing on the relative placement of dark circles and the fact that they’re inside of a tan colored circle. If the decision tree is calibrated for identifying breeds of dogs, but doesn’t know about muffins, hijinks may ensue.
Other cases are more worrying — many computer programs that do real-life facial recognition don't work well for people with darker skin.
This can happen when the facial recognition program is designed using pictures that skew too heavily toward lighter skin tones. The program ends up with less information about darker features, which lead it to make crude classifications.
We’ve picked up some key ideas behind decision trees:
However, decision trees aren't the right tool for every problem. For example, how would you use a decision tree to sort a deck of cards?
In the rest of Computer Science Fundamentals, you'll learn about many of the other tools computer scientists use to solve problems.