Concepts / Understanding Halfspaces in Binary Classification

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.

Key point

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

Labeled trainingdataOne requirement perexampley_i(w ⋅ x_i) ≥ 1Feasible vector wzero training errorscreatesall satisfied by
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.

Formula, step by step
  1. 1
    Take the inner product ⟨w, x_i⟩ between the candidate vector and the training instance.
  2. 2
    Multiply that value by the example's label y_i.
  3. 3
    Require the resulting signed value to be at least 1.
  4. 4
    Repeat this requirement for every labeled training instance.
y_ilabelwsame vector for everyexample⟨w, x_i⟩inner producty_i⟨w, x_i⟩signed inner product1required lower boundmultipliescombined withmust reachused in every constraint
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

Worked example

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

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

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

  3. 3
    Combined conclusion

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

Result

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.

Key point

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.

(x_1, y_1)((1, 0), 1)A row 1y_1x_1 = (1, 0)v(1, 1)(x_2, y_2)((0, 1), -1)A row 2y_2x_2 = (0, -1)multiply by labelmultiply by labelcompared withcompared with
How does each labeled example become one row of A, and how do the row indices correspond to the training instances?
Worked example

Forming A and v

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

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

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

  3. 3
    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).

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

Result

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

The LP Feasibility Pipeline

Labeled examples(x_i, y_i)Signed instancesy_i x_iLinear constraintsAw ≥ vLP solverzero objectiveVector wERM predictormultiply each instance by its labelform rows of Asubmit feasibility problemreturns a feasible solution
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 componentRole in this formulation
Constraints Aw ≥ vRequire the candidate vector to satisfy every labeled-example condition.
Dummy objective u = (0, ..., 0)Does not distinguish among feasible vectors.
Feasible solution wProvides a vector defining an ERM predictor with zero training errors.

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

Mistakes in the Translation

  • Common mistake

    Treating realizable ERM as a search for the best nonzero error rate.

    What it looks like

    Trying to rank candidates by how many training examples they misclassify.

    Why it fails

    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.

    Do this instead

    Treat the task as finding any vector satisfying every inequality y_i⟨w, x_i⟩ ≥ 1.

  • Common mistake

    Using x_i as a row of A without incorporating the label.

    What it looks like

    Putting x_i directly into A for both positive and negative examples.

    Why it fails

    The row must represent y_i⟨w, x_i⟩, not only ⟨w, x_i⟩.

    Do this instead

    Multiply each instance by its label first, then use y_i x_i as the corresponding row.

  • Common mistake

    Using a different vector for each training example.

    What it looks like

    Checking whether each example has some vector that satisfies its own inequality.

    Why it fails

    All constraints must be satisfied by one common vector w.

    Do this instead

    Construct the complete system and search for a single w satisfying Aw ≥ v.

  • Common mistake

    Assuming the zero objective selects a preferred feasible vector.

    What it looks like

    Expecting u ⋅ w with u = (0, ..., 0) to rank candidate vectors.

    Why it fails

    Every feasible vector has the same value under the zero objective.

    Do this instead

    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.

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

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

At a glance

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

Related Topics

Related concepts

More concepts starting with U