Axis-Aligned Rectangles

The vector viewpoint is useful because axis-aligned rectangles are defined in a coordinate space such as R^n.

Programming

From Image to Classification

The source material studies a binary face-recognition task. Each input is an image, and the classifier must decide between two classes: human face and not a human face. The important question is not only what answer the classifier produces, but how the image is transformed into that answer.

How are image instances divided into the two classes used by the classifier?

Key point

This is a binary classification problem: every image receives one of two class labels.

The Composition h(x)

The base hypothesis is decomposed as h(x) = f(g(x)). This notation describes a sequence of roles. The image x is first given to g. The function g uses an axis-aligned rectangle and produces one scalar associated with that rectangle. The function f then uses that scalar as part of the base hypothesis, and h produces the final classification output.

How does the image x pass through g, the scalar-based decision function f, and the final classifier h?

Part	Role
x	The input image
g	A function parameterized by an axis-aligned rectangle; it maps the image to a scalar
f	The decision stump that uses the scalar produced by g
h	The complete base hypothesis and final classifier output

The roles in h(x) = f(g(x))

Rectangle Parameters

An axis-aligned rectangle is a rectangle in R^{^n} whose sides are parallel to the coordinate axes. Its position is determined by lower and upper bounds along the coordinates. In the image setting, choosing those bounds selects the rectangle that parameterizes g.

Which coordinate lower and upper bounds define a rectangle, and how does g use membership in that rectangle?

The coordinate-axis condition is the defining geometric restriction. A general rectangle could be rotated, but an axis-aligned rectangle cannot: each side remains parallel to one of the coordinate axes. For a 24 × 24 image, the source states that there are at most 24^4 axis-aligned rectangles. These rectangle choices provide a finite collection of parameters for functions g in the base hypothesis class.

Tracing a Candidate Rectangle

Worked example

Checking Three Labeled Images

Suppose a candidate axis-aligned rectangle R is being considered for a labeled training set containing two positive examples and one negative example. The candidate is reported to contain both positive examples and to exclude the negative example. Is R consistent with this training set?

1
Check the first positive
The first positive example must lie inside the candidate rectangle.
2
Check the second positive
The second positive example must also lie inside the candidate rectangle.
3
Check the negative
The negative example must lie outside the candidate rectangle.
4
Check every label
All three required conditions hold, so the candidate agrees with every labeled example.

Result

The candidate rectangle is consistent with the complete training set.

How can we check whether every positive example lies inside a candidate rectangle and every negative example lies outside it?

The key word is every. A candidate is not consistent merely because it classifies most examples correctly. A single positive example outside the rectangle or a single negative example inside it is enough to make the candidate inconsistent with the training set.

Realizability and ERM

Let the labeled training set be written as S = (x_1, y_1), ..., (x_m, y_m). The training set is realizable for the axis-aligned-rectangle hypothesis class when at least one rectangle hypothesis h in H^n satisfies h(x_i) = y_i for every training example. Realizability therefore guarantees that a perfectly consistent rectangle exists, even though the learner still has to find one.

What does it mean for a rectangle to classify all training examples correctly, and how does ERM choose a rectangle with the fewest training errors?

In this setting, empirical risk minimization searches within H^n for a hypothesis with the fewest training errors. Because the case is realizable, the minimum is zero. The ERM output is therefore one axis-aligned rectangle hypothesis that agrees with every training label. The rectangle need not be unique; the requirement is to find one consistent member of the class.

Common Consistency Errors

Common mistake
Treating the image x as if it were already the final classifier output.
What it looks like
Saying that x itself decides whether the image is a face.
Why it fails
The source separates the image input from the functions g, f, and h.
Do this instead
Track the composition: x enters g, g produces a scalar, f uses that scalar, and h is the final hypothesis.
Common mistake
Confusing g with the decision stump f.
What it looks like
Describing g as the final yes-or-no decision.
Why it fails
g maps the image to a scalar associated with a selected rectangle; f uses that scalar in the base hypothesis.
Do this instead
Reserve the scalar-producing role for g and the decision role for f.
Common mistake
Allowing a rectangle to be rotated while still calling it axis-aligned.
What it looks like
Accepting a rectangle whose sides are not parallel to coordinate axes.
Why it fails
Parallelism with the coordinate axes is the defining restriction.
Do this instead
Check that the rectangle's sides remain parallel to the axes.
Common mistake
Checking only most of the training examples.
What it looks like
Accepting a rectangle because it classifies nine of ten examples correctly.
Why it fails
Consistency in the realizable case requires h(x_i) = y_i for every i.
Do this instead
Inspect every labeled example; one disagreement makes the candidate inconsistent.
Common mistake
Assuming ERM must return a unique rectangle.
What it looks like
Rejecting a valid ERM result because another consistent rectangle also exists.
Why it fails
The ERM goal is to find one hypothesis with zero training error, not necessarily a uniquely determined one.
Do this instead
Accept any member of H^n that agrees with all training labels.

Practice Check

EASY

A candidate axis-aligned rectangle contains every positive training image but also contains one negative training image. Is the candidate consistent with the training set? Explain which requirement fails.

Hints

Check the required relationship between negative examples and the candidate rectangle.
Consistency must hold for every labeled example.

Your attempt (not saved)

What do you think happens?

A candidate rectangle contains every positive example but contains one negative example. Is it consistent?

Yes, because all positive examples are included
No, because at least one label disagrees
Yes, because ERM allows one training error

Reveal answer

Answer:

No, because at least one label disagrees.

Consistency requires agreement with every training example. A negative example inside the candidate rectangle creates a training error, so the candidate is not the required zero-error hypothesis in the realizable case.

MEDIUM

Explain the four roles in h(x) = f(g(x)) using these terms: image input, scalar-producing function, decision stump, and final classifier output.