Classifiers

A classifier produces behavior on domain examples, but describing that behavior is not enough for learning theory.

Programming

From Predictions to Cost

A classifier produces behavior on domain examples, but describing that behavior is not enough for learning theory. We also need a way to say how costly a particular classifier is on a particular domain example. A generalized loss function supplies that description. It accepts a hypothesis or model and a domain element, then returns a nonnegative real number.

Definition

A generalized loss function is written as ℓ : H × Z → R+. Its inputs are a hypothesis h from H and a domain element z from Z. Its output is a nonnegative real number representing the loss assigned to that pair.

What enters a generalized loss function, and what does it produce?

One Loss Versus Overall Risk

A single evaluation of ℓ describes one model-domain pair. Risk asks a broader question: how much loss should we expect from a chosen classifier when domain elements are distributed according to a probability distribution D over Z? Thus, risk is the expected loss of the classifier with respect to D.

Rule

How do losses on domain elements combine under D to produce a classifier's risk?

What is the difference between evaluating one pair and averaging expected loss over domain elements?

Worked example

Why the Distribution Matters

Suppose a fixed classifier and a fixed loss function are evaluated on domain elements z1 and z2. What can change if the distribution D changes?

1
Keep the classifier fixed
The selected classifier remains the same.
2
Keep the loss rule fixed
The generalized loss function still assigns a nonnegative value to each model-domain pair.
3
Change D
The probabilities used in the expectation change.
4
Recompute expected loss
Because the expectation is now taken with respect to a different distribution, the resulting risk can change.

Result

Risk can change when D changes even though the classifier and loss function remain unchanged.

Three Regions on the Real Line

A 3-piece classifier operates on the real line. It is specified by two real thresholds, theta_1 and theta_2, satisfying theta_1 < theta_2, together with a binary sign parameter b in {+1, -1}. The ordered thresholds divide the real line into three intervals. The sign parameter determines the classifier's binary prediction pattern across those regions.

How do two ordered thresholds divide the real line, and where does the sign parameter enter?

Worked example

Reading a 3-Piece Classifier's Structure

Consider parameters theta_1 = 2, theta_2 = 5, and b = +1. What structural information does this specify?

1
Check the threshold order
The thresholds satisfy 2 < 5, so they are valid ordered thresholds.
2
Locate the boundaries
The real line is divided at 2 and 5.
3
Identify the three regions
The classifier has a region to the left of the first threshold, a region between the thresholds, and a region to the right of the second threshold.
4
Apply the sign parameter
The value b = +1 selects the binary sign orientation used for the predictions in those regions.

Result

The parameters specify two ordered boundaries, three real-line regions, and a binary prediction orientation.

Stumps and Weak Learning

A decision stump is simpler than a 3-piece classifier. It uses one threshold theta and a sign parameter b, rather than two ordered thresholds. Consequently, a stump divides the real line using one boundary, while a 3-piece classifier divides it using two boundaries and has three prediction regions.

What changes when the prediction structure moves from one threshold to two?

In this example, decision stumps form the learner class B, while 3-piece classifiers form the larger target class H. The point of calling stumps a weak learner is not that a stump has the same structure as a 3-piece classifier. It does not. Rather, the simpler stump family can still provide a learning guarantee about the more structured target family.

How can a simpler one-threshold learner support learning about a two-threshold classifier family?

Definition

The statement that ERM_B is a gamma-weak learner for H with gamma equal to 1/12 means that empirical risk minimization over the stump class B provides a guarantee whose gap from the best classifier in the target class H is at most 1/12 in risk.

Common Misreadings

Common mistake
Treating the loss value and risk as the same quantity.
What it looks like
```
Calling ℓ(h,z) the risk of h.
```
Why it fails
ℓ(h,z) evaluates one hypothesis-domain pair, whereas risk is expected loss under D.
Do this instead
Use loss for one pair and risk for the distribution-based expectation.
Common mistake
Forgetting that D is part of the risk question.
What it looks like
Assuming a classifier has one fixed risk regardless of how domain elements are distributed.
Why it fails
Changing D can change the expectation.
Do this instead
Always specify the distribution with respect to which risk is measured.
Common mistake
Describing a 3-piece classifier with only one threshold.
What it looks like
Using a single boundary to describe the class H in this example.
Why it fails
The 3-piece class is specified by two ordered thresholds and a binary sign parameter.
Do this instead
Check for theta_1, theta_2 with theta_1 < theta_2, plus b in {+1, -1}.
Common mistake
Assuming a decision stump and a 3-piece classifier have the same structure.
What it looks like
Saying both classes divide the real line into three regions.
Why it fails
A stump uses one threshold, while the 3-piece classifier uses two.
Do this instead
Compare the number of thresholds and resulting regions.
Common mistake
Interpreting weak learner as perfect learner.
What it looks like
Assuming ERM_B must match the best classifier in H exactly.
Why it fails
The guarantee allows a risk gap of gamma, which here is 1/12.
Do this instead
Interpret the guarantee as being within 1/12 in risk of the best classifier in H.

Check Your Understanding

MEDIUM

A learning setup has a hypothesis class H, a domain Z, and a probability distribution D over Z. Explain, in your own words, the difference between evaluating ℓ(h,z) and evaluating the risk of h under D. Then compare the structures of a decision stump and a 3-piece classifier.

Hints

Start by identifying the two inputs to ℓ.
Ask whether the calculation concerns one domain element or an expectation over domain elements.
Count the thresholds in each classifier family.

Your attempt (not saved)

What do you think happens?

If the classifier and generalized loss function stay fixed but D changes, should the risk necessarily stay fixed?

Yes, because the classifier did not change
No, because risk is an expectation with respect to D

Reveal answer

Answer:

No, because risk is an expectation with respect to D.

Changing the distribution changes the weighting used in the expected loss, so it can change risk even when the classifier and loss function are unchanged.

Key Takeaways

1
A generalized loss function maps a hypothesis-domain pair from H × Z to a nonnegative real number.
2
Loss evaluates one pair, while risk is the expected loss of a classifier under a distribution D over Z.
3
A 3-piece classifier uses two ordered real thresholds and a binary sign parameter to divide the real line into three regions.
4
A decision stump uses one threshold and is therefore structurally simpler than a 3-piece classifier.
5
ERM_B being a 1/12-weak learner for H means that learning over the stump class B has a risk guarantee within 1/12 of the best classifier in H.

At a glance

Generalized loss functions assign nonnegative values to pairs consisting of a hypothesis and a domain element.
Risk is expected loss under a distribution D, not one individual loss value.
Two ordered thresholds create the three regions of a 3-piece classifier.
Decision stumps use one threshold and can still act as weak learners for the richer 3-piece class.
The value gamma = 1/12 describes the allowed risk gap in the weak-learning guarantee.

Related concepts

More concepts starting with C