Concepts / Axis-Aligned Rectangles

Axis-Aligned Rectangles

The task is binary face recognition: classify an image as a human face or not.

  • 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.

classified asclassified asImage24 × 24 valuesHuman facepositive classNot a human facenegative class
How are image instances divided into the two classes used by the classifier?

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.

inputproducesused byformsImage x24 × 24 inputgscalar-producing functionScalarvalue from rectanglefdecision stumph(x)classifier output
How does the image x pass through g, the scalar-based decision function f, and the final classifier h?
PartRole
xThe input image
gA function parameterized by an axis-aligned rectangle; it maps the image to a scalar
fThe decision stump that uses the scalar produced by g
hThe 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.

sets boundaries withsets boundaries withteststestsLower boundsone per coordinateRectangle Rsides parallel to axesInput inside Rg produces a scalarUpper boundsone per coordinateInput outside Rg produces a scalar
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

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?

Check the first positive: The first positive example must lie inside the candidate rectangle.

Check the second positive: The second positive example must also lie inside the candidate rectangle.

Check the negative: The negative example must lie outside the candidate rectangle.

Check every label: All three required conditions hold, so the candidate agrees with every labeled example.

The candidate rectangle is consistent with the complete training set.

inspect positivesinspect negativesyes, for every positivenoyes, for every negativenoTraining setlabeled examplesPositive exampleinside R?Consistentall labels agreeNegative exampleoutside R?Inconsistentat least one error
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.

search withinconsiderall labels agreesome label disagreesLabeled trainingsetSHⁿaxis-aligned rectanglesCandidate hcheck all examplesZero training errorh(xᵢ) = yᵢ for all iTraining errorscandidate rejected
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

  • Treating the image x as if it were already the final classifier output.

    The source separates the image input from the functions g, f, and h.

    Fix: Track the composition: x enters g, g produces a scalar, f uses that scalar, and h is the final hypothesis.

  • Confusing g with the decision stump f.

    g maps the image to a scalar associated with a selected rectangle; f uses that scalar in the base hypothesis.

    Fix: Reserve the scalar-producing role for g and the decision role for f.

  • Allowing a rectangle to be rotated while still calling it axis-aligned.

    Parallelism with the coordinate axes is the defining restriction.

    Fix: Check that the rectangle's sides remain parallel to the axes.

  • Checking only most of the training examples.

    Consistency in the realizable case requires h(x_i) = y_i for every i.

    Fix: Inspect every labeled example; one disagreement makes the candidate inconsistent.

  • Assuming ERM must return a unique rectangle.

    The ERM goal is to find one hypothesis with zero training error, not necessarily a uniquely determined one.

    Fix: 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.

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.

Hints
  • Start with x.
  • Identify which function is parameterized by the rectangle.
  • End with h.

Key Takeaways

  1. The task is binary face recognition: classify an image as a human face or not a human face.
  2. A 24 × 24 real-valued image has 576 matrix positions and can be viewed as an input vector x with one coordinate per position.
  3. The base hypothesis has the structure h(x) = f(g(x)): g maps the image to a scalar using an axis-aligned rectangle, f uses that scalar, and h is the final classifier.
  4. Axis-aligned rectangles in R^n have sides parallel to the coordinate axes; for the 24 × 24 setting, the source states that there are at most 24^4 such rectangles.
  5. In the realizable case, ERM seeks one rectangle hypothesis that agrees with every labeled training example and therefore has zero training error.

Key Takeaways

  • Face recognition here is a binary classification task over 24 × 24 real-valued image inputs.
  • The decomposition h(x) = f(g(x)) separates image processing, scalar production, decision making, and final output.
  • An axis-aligned rectangle is defined by sides parallel to the coordinate axes and parameterizes g.
  • A training set is realizable when at least one rectangle hypothesis agrees with every label.
  • ERM must return a hypothesis with zero training error in the realizable case.

Related Topics

  • Empirical Risk Minimization
  • Binary Classification
  • AdaBoost
  • Hypothesis Classes