Understanding Halfspaces in Binary Classification

Realizable ERM for homogeneous halfspaces can be expressed as a feasibility problem.

Programming

From Perfect Classification to Feasibility

In realizable binary classification, the training data can be classified perfectly by a homogeneous halfspace. That changes the shape of the ERM problem. Instead of comparing imperfect predictors and selecting the one with the fewest mistakes, we search for one vector w that makes no training mistakes at all. The task becomes a feasibility problem: find any vector that satisfies every requirement imposed by the labeled examples.

For realizable ERM, feasibility comes before optimization. The important question is whether a vector satisfies all training constraints, not which feasible vector is best.

Why does realizable ERM search for any vector that correctly classifies every training instance?

The Requirement for Each Example

Suppose the training set contains labeled instances (x_i, y_i), where each label is positive or negative. A suitable vector w must satisfy the requirement y_i ⟨w, x_i⟩ ≥ 1 for every training instance. The label is part of the requirement: it makes the same inequality work for both positive and negative examples. All examples constrain the same vector w, so w must satisfy the complete collection of inequalities simultaneously.

y_i ⟨w, x_i⟩ ≥ 1

How does each label determine an inequality such as y_i(w ⋅ x_i) ≥ 1, and how do all inequalities constrain the same vector w?

Testing a Candidate Vector

Checking Two Labeled Instances

Consider two labeled instances in two dimensions: (x_1, y_1) = ((1, 0), 1) and (x_2, y_2) = ((0, 1), -1). Test the candidate vector w = (2, -3).

First instance: For x_1 = (1, 0) and y_1 = 1, the signed inner product is y_1⟨w, x_1⟩ = 1((2)(1) + (-3)(0)) = 2. Since 2 is at least 1, the first requirement is satisfied.

Second instance: For x_2 = (0, 1) and y_2 = -1, the signed inner product is y_2⟨w, x_2⟩ = -1((2)(0) + (-3)(1)) = 3. Since 3 is at least 1, the second requirement is satisfied.

Combined conclusion: The candidate vector satisfies both requirements, so it is feasible for this pair of training examples.

The vector w = (2, -3) satisfies y_i⟨w, x_i⟩ ≥ 1 for both examples and therefore produces zero training errors for this generated training set.

Checking feasibility means checking every example. Passing one inequality is not enough; the same candidate vector must satisfy all of them.

Building the Constraint Matrix

The individual inequalities can be collected into matrix form. For each labeled example, multiply the instance vector x_i by its label y_i. The resulting signed vector y_i x_i becomes one row of the matrix A. This works because the inner product of that row with w is exactly y_i⟨w, x_i⟩. If v contains one entry for each training example and every entry of v is 1, the complete system is Aw ≥ v.

How does each labeled example become one row of A, and how do the row indices correspond to the training instances?

Forming A and v

Use the two generated instances x_1 = (1, 0), y_1 = 1 and x_2 = (0, 1), y_2 = -1.

Sign the first instance: Multiply x_1 by y_1: y_1x_1 = 1(1, 0) = (1, 0). This becomes the first row of A.

Sign the second instance: Multiply x_2 by y_2: y_2x_2 = -1(0, 1) = (0, -1). This becomes the second row of A.

Assemble the matrix: The rows give A = [[1, 0], [0, -1]]. There is one entry in v for each training example, so v = (1, 1).

Check the candidate: For w = (2, -3), multiplying A by w produces (2, 3). Both components are at least the corresponding components of v, so Aw ≥ v.

The two separate requirements are represented together by Aw ≥ v, with A = [[1, 0], [0, -1]] and v = (1, 1).

The LP Feasibility Pipeline

How does data move from labeled examples to linear constraints, through the LP solver, and finally to a vector that defines the classifier?

Once A and v have been constructed, the ERM task can be presented to a linear-programming solver. The solver searches for a vector w satisfying Aw ≥ v. If it returns a feasible vector, that vector satisfies every labeled-example requirement and therefore defines an ERM predictor with zero training errors in the realizable setting.

Why the Objective Is Zero

A conventional LP may use an objective to choose one feasible solution over another. This realizable ERM formulation does not need such a preference. Every vector satisfying all the constraints is an acceptable output hypothesis. Therefore the LP uses the dummy objective u = (0, ..., 0). Maximizing u ⋅ w gives the same objective value for every w, so the constraints, rather than the objective, carry the substantive meaning.

LP component	Role in this formulation
Constraints Aw ≥ v	Require the candidate vector to satisfy every labeled-example condition.
Dummy objective u = (0, ..., 0)	Does not distinguish among feasible vectors.
Feasible solution w	Provides a vector defining an ERM predictor with zero training errors.

Mistakes in the Translation

Treating realizable ERM as a search for the best nonzero error rate.
In the realizable case, the goal is to find a vector with no training mistakes, expressed as a set of requirements that must all hold.
Fix: Treat the task as finding any vector satisfying every inequality y_i⟨w, x_i⟩ ≥ 1.
Using x_i as a row of A without incorporating the label.
The row must represent y_i⟨w, x_i⟩, not only ⟨w, x_i⟩.
Fix: Multiply each instance by its label first, then use y_i x_i as the corresponding row.
Using a different vector for each training example.
All constraints must be satisfied by one common vector w.
Fix: Construct the complete system and search for a single w satisfying Aw ≥ v.
Assuming the zero objective selects a preferred feasible vector.
Every feasible vector has the same value under the zero objective.
Fix: Understand the LP as a feasibility search in which the constraints determine acceptability.

Practice: Assemble the System

EASY

Given the generated labeled instances (x_1, y_1) = ((1, 0), 1) and (x_2, y_2) = ((0, 1), -1), write the two signed rows of A, write v, and check whether w = (2, -3) satisfies Aw ≥ v.

Hints

Compute y_1x_1 and y_2x_2 separately.
Use one entry of 1 in v for each training example.
Multiply A by w and compare the resulting components with v.

Your attempt (not saved)

What do you think happens?

For the generated system with A = [[1, 0], [0, -1]], v = (1, 1), and w = (2, -3), what does Aw equal?

(2, -3)
(2, 3)
(1, 1)
(0, 0)

Reveal answer

Answer: (2, 3)

The first row dotted with w gives 2, and the second row dotted with w gives 3. Both values meet the corresponding requirement in v.

Summary

In the realizable setting, ERM for homogeneous halfspaces seeks a vector with zero training errors.
Each labeled example contributes the inequality y_i⟨w, x_i⟩ ≥ 1.
Multiplying x_i by y_i turns each labeled example into one row of A.
The complete system is Aw ≥ v, where v contains one entry of 1 for each training example.
The LP uses a zero objective because any feasible vector is acceptable; an LP solver can return such a vector as the ERM predictor.

Key Takeaways

Realizable ERM becomes a feasibility problem because the target is zero training error.
A candidate vector must satisfy y_i⟨w, x_i⟩ ≥ 1 for every labeled example.
The signed vectors y_i x_i form the rows of A, producing the system Aw ≥ v.
The zero objective does not choose among feasible vectors; it leaves the constraints to define the solution.
An LP solver can find a feasible w, which defines an ERM predictor for the training set.