Realizable Binary Classification

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

Programming

From Perfect Data to Feasibility

In realizable binary classification, the training data can be classified perfectly by a homogeneous halfspace. That changes the ERM task. Instead of comparing candidates that make different numbers of training mistakes, we search for one vector w whose associated halfspace makes no training mistakes. Each labeled example becomes a requirement that the same vector w must satisfy.

How does realizable ERM become a search for any vector that satisfies every constraint rather than an optimization problem?

The central shift is from optimization over imperfect candidates to feasibility: find any vector that satisfies every training requirement.

The Constraint for One Example

Let a labeled training example be written as (x_i, y_i), where y_i is either positive or negative. For realizable ERM with homogeneous halfspaces, the vector w must satisfy the margin-style inequality y_i ⟨w, x_i⟩ ≥ 1. The label multiplies the inner product, so positive and negative examples are handled by the same expression. A suitable w must satisfy this requirement for every training example, not merely for one selected example.

y_i ⟨w, x_i⟩ ≥ 1

How does each labeled example produce an inequality, and how do all inequalities constrain the same vector w?

Testing Two Labeled Instances

Consider (x_1, y_1) = ((1, 0), 1), (x_2, y_2) = ((0, 1), -1), and w = (2, -3). Check the two realizable ERM inequalities.

First instance: The signed inner product is y_1 ⟨w, x_1⟩ = 1 times the inner product of (2, -3) and (1, 0), which equals 2. Since 2 is at least 1, the first constraint is satisfied.

Second instance: The inner product of (2, -3) and (0, 1) equals -3. Multiplying by y_2 = -1 gives 3. Since 3 is at least 1, the second constraint is satisfied.

Combine the checks: The vector w satisfies both labeled-example requirements, so it is feasible for this generated constraint system.

The signed inner products are 2 and 3, and both meet the required lower bound of 1.

Building the Matrix A

The individual inequalities can be collected into one matrix inequality. For each labeled example, multiply the feature vector by its label. The signed vector y_i x_i becomes one row of A because its inner product with w equals y_i ⟨w, x_i⟩. The right-hand-side vector v contains one entry for each training example, and every entry is 1.

How are the feature vectors and labels transformed into the rows of matrix A?

Aw ≥ v

Forming A and Checking Aw

Use x_1 = (1, 0), y_1 = 1, x_2 = (0, 1), y_2 = -1, and w = (2, -3).

Form the first row: Multiply x_1 by y_1. The first row is y_1 x_1 = (1, 0).

Form the second row: Multiply x_2 by y_2. The second row is y_2 x_2 = (0, -1).

Assemble the system: The rows form A, and the right-hand side vector is v = (1, 1).

Multiply by w: For w = (2, -3), multiplying A by w produces (2, 3).

Aw = (2, 3), which is componentwise at least v = (1, 1).

Why the Objective Is Zero

The LP convention uses a maximization objective, but realizable ERM does not need to prefer one feasible vector over another. Every vector satisfying all the constraints is an acceptable output hypothesis. Therefore the objective uses the dummy vector u = (0, ..., 0). Maximizing u ⋅ w gives the same objective value for every feasible w, so the constraints, rather than the objective, carry the substantive meaning.

Part of the formulation	Role in realizable ERM
Constraints	Require y_i ⟨w, x_i⟩ ≥ 1 for every labeled example.
Objective	Uses u = (0, ..., 0), so it does not distinguish feasible vectors.
Result	Any vector satisfying all constraints can provide the ERM hypothesis.

From Solver Output to Predictor

Once A and v have been constructed, the realizable ERM problem is presented to an LP solver as a feasibility formulation with the dummy objective. The solver searches for a vector w satisfying Aw ≥ v. If it finds one, that vector meets every labeled-example requirement and can be used to form the associated homogeneous halfspace predictor. The important output is therefore a feasible vector, not a uniquely best vector.

What does the LP solver do with the matrix constraints, and how does a feasible solution become the ERM predictor?

When reading this LP formulation, inspect the constraints first. They encode the classification requirements. The objective is deliberately neutral because the task is to find any feasible vector.

Common Formulation Mistakes

Treating realizable ERM as a search for the vector with the smallest remaining training error.
In the realizable case, the goal is to find a vector that makes no training mistakes and satisfies every constraint.
Fix: Formulate the task as feasibility: find any w satisfying all labeled-example requirements.
Using x_i as a row of A without incorporating its label.
The required quantity is y_i ⟨w, x_i⟩, not just ⟨w, x_i⟩.
Fix: Use the signed instance y_i x_i as the row associated with example i.
Forgetting that every constraint applies to the same vector w.
A single hypothesis must satisfy the complete training set.
Fix: Collect all rows into A and require the one vector w to satisfy Aw ≥ v.
Trying to make the zero objective choose a preferred feasible vector.
The dummy objective has the same value for every feasible vector.
Fix: Read the constraints as the substantive part of the formulation.

Check Your Construction

MEDIUM

For the generated examples x_1 = (1, 0), y_1 = 1 and x_2 = (0, 1), y_2 = -1, write the two rows of A and the vector v. Then explain why a vector w is acceptable when Aw is componentwise at least v.

Hints

Multiply each x_i by its corresponding label y_i.
Use one entry of v for each training example.
The two components of Aw represent the two signed inner products.

Your attempt (not saved)

What do you think happens?

For w = (2, -3), what does Aw equal for the generated matrix with rows (1, 0) and (0, -1)?

(2, -3)
(2, 3)
(-2, 3)

Reveal answer

Answer: (2, 3)

The first row gives 2. The second row gives the inner product of (0, -1) with (2, -3), which is 3.

Key Takeaways

Realizable ERM for homogeneous halfspaces searches for a vector w with zero training errors.
Each labeled example contributes the inequality y_i ⟨w, x_i⟩ ≥ 1.
The row for example i in A is the signed feature vector y_i x_i.
All requirements combine into Aw ≥ v, where v consists of ones.
The LP uses a zero objective because any feasible w is acceptable; the constraints determine the solution's validity.

Key Takeaways

Realizable ERM is a feasibility problem because the data can be classified perfectly.
A valid vector must satisfy y_i ⟨w, x_i⟩ ≥ 1 for every labeled training example.
Multiplying each feature vector by its label creates the rows of A, giving the system Aw ≥ v.
The zero objective does not rank feasible vectors; it allows the constraints to determine whether a solution is acceptable.
An LP solver can return a feasible w, which is then used as the associated homogeneous halfspace predictor.