Learning Algorithm
A prediction rule maps a domain point to a label.
From Point to Label
A machine-learning learner ultimately needs to produce a way to make predictions. That way is a prediction rule: a function that takes a domain point and maps it to a label. Once the rule exists, it can be applied to new domain points, including points that were not part of the training sequence.
A prediction rule maps a domain point to a label.
Applying the Rule
To follow one prediction from start to finish, begin with a new domain point. Apply the prediction rule h to that point. The result is a label in Y. The point has been transformed into the label that will be used as its prediction; the rule's job in this step is to produce that output label.
A New Papaya Point
Suppose a prediction rule is used to predict labels for future papayas. What happens when a new papaya is supplied to the rule?
Start with the point: The new papaya is a domain point supplied as input to the prediction rule.
Apply the rule: The prediction rule h is applied to that domain point.
Read the result: The output is a label in Y, and that label becomes the prediction for the new papaya.
A new domain point is passed through h and receives a predicted label in Y.
Reading h : X → Y
The notation h : X → Y expresses the direction of the prediction rule. The symbol X identifies the domain of points that can be supplied to h. The symbol Y identifies the set of labels that can be produced. The arrow indicates that h maps from domain points to labels.
| Notation | Meaning |
|---|---|
| h | The prediction rule |
| X | The domain set of input points |
| Y | The set of possible labels |
| h : X → Y | h maps domain points to labels |
The parts of the prediction-rule notation
Generated example: if a particular domain point is written as x and the rule produces h(x), then x is an input from X and h(x) is an output label in Y. The notation describes the direction of the mapping; it does not by itself specify what the point or label looks like.
Algorithm and Hypothesis
A prediction rule is the general kind of object a learner must produce: a function that maps domain points to labels. A learning algorithm is the process that produces one particular prediction rule after receiving training data. The source uses A for the learning algorithm and S for the training sequence. The notation A(S) means the hypothesis returned by algorithm A after receiving S.
The word hypothesis names the prediction rule returned for a particular training sequence. Thus, A(S) is not a separate kind of output from a prediction rule; it is the particular prediction rule produced by A when it receives S.
Counting Computational Work
When we ask how complex a learning algorithm is, we are asking how much computational work it performs, not initially whether its code looks short or complicated. The source definition measures that work by counting the operations required by the algorithm.
Computational complexity measures the number of operations an algorithm performs.
Two Views of Complexity
The complexity of a learning algorithm is defined in two related stages. First, measure the complexity for one fixed learning problem. Second, examine how that complexity changes across a sequence of learning tasks. The definition therefore has both a fixed-task part and an across-tasks part.
- Hold one learning problem fixed. The source represents it with the triplet (Z, H, ℓ): a domain set, a benchmark hypothesis class, and a loss function.
- Measure how much computation the learning algorithm requires for that particular learning problem.
- Move from one task to a sequence of tasks.
- Examine the rate at which the measured complexity changes along that sequence.
Interpreting O(f)
In the formal statement described by the source, O(f) is attached to a learning task, an algorithm, and a function f. The statement also involves a constant c and every probability distribution D mentioned in the definition. Big O is therefore presented as part of a quantified statement about running-time growth, rather than as an isolated label attached to an algorithm.
When reading a statement involving O(f), identify the learning task being considered, the algorithm being measured, the function f describing the relevant growth, the constant c used by the abstract machine, and the distributions D over which the statement must hold.
The constant c is required to work for every probability distribution D mentioned in the definition. This quantification matters: the statement is not merely saying that one observed run took a certain amount of time. It describes the operation-based running-time behavior in the formal setting specified by the learning task and the algorithm.
Mistakes in Interpretation
Treating h as a label instead of a rule
h names the prediction rule. A point is supplied to the rule, and the resulting value h(x) is the label in Y.
Fix:
Separate the rule h from its output h(x).Confusing A with A(S)
A is the learning algorithm, while A(S) is the hypothesis, or prediction rule, returned after A receives the training sequence S.
Fix:
Use A for the process and A(S) for the produced prediction rule.Defining complexity by code appearance
The source defines computational complexity by counting the operations performed by the algorithm.
Fix:
Focus on the required computational work and its operation count.Using only one task when describing learning-algorithm complexity
The formal definition has a second stage that examines how complexity changes across a sequence of learning tasks.
Fix:
State both the fixed-task measurement and the across-tasks rate of change.
Check Your Understanding
Explain the complete path from a new domain point to its predicted label. In your response, use h : X → Y, identify the input and output sets, and explain how A(S) is related to h. Then describe the two stages used to define the complexity of a learning algorithm.
Hints
- Begin with the meaning of X and Y.
- Distinguish the rule h from the value h(x).
- Remember that A(S) is the prediction rule returned after algorithm A receives S.
- Name the fixed-learning-problem stage before the across-tasks stage.
Putting the Notation Together
A learner receives a training sequence S and returns A(S). What kind of object is A(S), and what happens when a new point x is supplied to it?
Identify the returned object: A(S) is the hypothesis returned by the learning algorithm A after receiving S.
Identify its role: The hypothesis is a prediction rule: it maps domain points to labels.
Apply it to the new point: The new point is passed through the returned prediction rule, producing a label in Y that serves as the prediction.
A(S) is a particular prediction rule produced from S, and applying it to a new domain point produces a predicted label.
Key Takeaways
- A prediction rule is a function that maps each supplied domain point to a label.
- The notation h : X → Y means that h maps points from X to labels in Y.
- A learning algorithm A receives a training sequence S and returns the hypothesis A(S), which is a particular prediction rule.
- Computational complexity measures an algorithm's computational work by counting its operations under an abstract-machine assumption with constant time c per operation.
- Learning-algorithm complexity is defined first for one fixed learning problem and then by examining how that complexity changes across a sequence of tasks; O(f) appears within this formal running-time statement.