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?

Key point

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.

Formula

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

Worked example

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.

1
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.
2
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.
3
Combine the checks
The vector w satisfies both labeled-example requirements, so it is feasible for this generated constraint system.

Result

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?

Formula

Worked example

Forming A and Checking Aw

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

1
Form the first row
Multiply x_1 by y_1. The first row is y_1 x_1 = (1, 0).
2
Form the second row
Multiply x_2 by y_2. The second row is y_2 x_2 = (0, -1).
3
Assemble the system
The rows form A, and the right-hand side vector is v = (1, 1).
4
Multiply by w
For w = (2, -3), multiplying A by w produces (2, 3).

Result

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.

The constraints determine acceptability; the dummy objective does not rank feasible solutions.

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?

Best practice

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

Common mistake
Treating realizable ERM as a search for the vector with the smallest remaining training error.
What it looks like
Comparing candidates that make different numbers of mistakes.
Why it fails
In the realizable case, the goal is to find a vector that makes no training mistakes and satisfies every constraint.
Do this instead
Formulate the task as feasibility: find any w satisfying all labeled-example requirements.
Common mistake
Using x_i as a row of A without incorporating its label.
What it looks like
Putting x_2 = (0, 1) into A even though y_2 = -1.
Why it fails
The required quantity is y_i ⟨w, x_i⟩, not just ⟨w, x_i⟩.
Do this instead
Use the signed instance y_i x_i as the row associated with example i.
Common mistake
Forgetting that every constraint applies to the same vector w.
What it looks like
Checking each example with a different candidate vector.
Why it fails
A single hypothesis must satisfy the complete training set.
Do this instead
Collect all rows into A and require the one vector w to satisfy Aw ≥ v.
Common mistake
Trying to make the zero objective choose a preferred feasible vector.
What it looks like
Expecting u ⋅ w to rank feasible vectors when u = (0, ..., 0).
Why it fails
The dummy objective has the same value for every feasible vector.
Do this instead
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

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

At a glance

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.

More concepts starting with R