Linear Programming
Realizable ERM for homogeneous halfspaces can be expressed as a feasibility problem.
From Perfect Classification to Feasibility
In the realizable setting, the training data can be classified perfectly by a homogeneous halfspace. Realizable empirical risk minimization therefore does not need to compare imperfect candidate predictors. Instead, it searches for one vector w whose associated halfspace makes no training mistakes. This changes the task into a feasibility problem: find a vector that satisfies every requirement imposed by the labeled examples.
The important question is not which feasible vector is best according to an objective. The first question is whether a vector exists that satisfies every training constraint.
The Signed Inner-Product Test
For each labeled example (x_i, y_i), where the label is positive or negative, the required condition is y_i ⟨w, x_i⟩ ≥ 1. The label is multiplied into the inner product so that both positive and negative examples can be handled by the same inequality. A vector w is suitable when this inequality holds for every training 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 whether w satisfies the requirement for each instance.
First instance: The signed inner product is y_1⟨w, x_1⟩ = 1 multiplied by the inner product of (2, -3) and (1, 0), which equals 2. Since 2 is at least 1, the first requirement 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 requirement is also satisfied.
Conclusion: Both labeled instances meet the required inequality, so this vector passes the two-example feasibility check.
The vector w = (2, -3) satisfies both signed inner-product constraints.
Building the Constraint Matrix
The individual constraints can be placed into matrix form by attaching each label to its instance. For example i, form the signed vector y_i x_i. Its inner product with w is exactly y_i ⟨w, x_i⟩. Therefore, the signed vectors can be used as the rows of a single matrix A.
Constructing A and v
Use the two labeled instances (x_1, y_1) = ((1, 0), 1) and (x_2, y_2) = ((0, 1), -1).
Sign the first instance: Compute y_1x_1 = 1(1, 0) = (1, 0). This becomes the first row of A.
Sign the second instance: Compute 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)). The right-hand-side vector v contains one entry for each example, so v = (1, 1).
Check with w: Multiplying A by w = (2, -3) gives (2, 3). Both components are at least the corresponding components of v.
The matrix inequality Aw ≥ v records the two original signed inner-product checks.
The complete constraint system is written as Aw ≥ v, where A contains the signed training instances as rows and v consists of ones. The matrix inequality is not a new requirement; it is a compact way to record all of the individual requirements at once.
The Dummy Objective
The LP convention uses a maximization objective, but this realizable ERM formulation does not need to prefer one feasible vector over another. Every vector satisfying all the constraints is an acceptable output hypothesis. The formulation therefore uses the dummy objective u = (0, ..., 0). Maximizing u · w does not distinguish among feasible vectors, so the constraints carry the substantive meaning.
| Part of the LP | Role in this formulation |
|---|---|
| Constraint system Aw ≥ v | Requires the candidate vector to satisfy every training-example requirement. |
| Objective u · w | Uses u = (0, ..., 0), so it does not distinguish among feasible vectors. |
| Solver output | Any vector satisfying all constraints can serve as the ERM output. |
Solver to Predictor
- Start with the labeled training instances (x_i, y_i).
- Multiply each instance x_i by its label y_i.
- Place the signed instances y_i x_i as the rows of A.
- Create v with one entry for each training example.
- Give the solver the constraints Aw ≥ v and the dummy objective u = (0, ..., 0).
- Use a feasible output vector w as the ERM halfspace predictor.
The solver's role is to find a vector that passes all the constraints. Once such a vector is available, it defines the homogeneous halfspace associated with the ERM predictor. Because every training requirement was enforced, the resulting predictor makes no training mistakes in the realizable setting.
Common Construction Mistakes
Using x_i directly as a row of A for every example.
The row must represent y_i x_i so that its inner product with w equals y_i⟨w, x_i⟩.
Fix:
Multiply each instance by its label first. The negative example becomes (0, -1).Checking only whether the prediction is on the correct side of zero.
The required condition is y_i⟨w, x_i⟩ ≥ 1.
Fix:
Check the full margin-style inequality for every example.Trying to optimize a meaningful preference among feasible vectors.
This formulation accepts any feasible vector and uses a zero objective.
Fix:
Focus on satisfying Aw ≥ v; the dummy objective does not distinguish feasible outputs.Checking only some of the rows of A.
A zero-error predictor must satisfy the requirement contributed by every labeled training instance.
Fix:
Treat all rows of A as simultaneous constraints.
Check Your Construction
For the generated data set (x_1, y_1) = ((1, 0), 1), (x_2, y_2) = ((0, 1), -1), and w = (2, -3), write the two signed rows of A and decide whether w 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 result componentwise with v.
What do you think happens?
If a vector w makes every component of Aw at least the corresponding component of v, what can you conclude in the realizable ERM formulation?
Reveal answer
Answer: It is a feasible vector and can define a zero-error halfspace predictor.
The constraints encode the signed inner-product requirement for every training example. Satisfying all of them gives a feasible vector, and any feasible vector is acceptable in this formulation.
Key Takeaways
- Realizable ERM for homogeneous halfspaces searches for a vector that makes no training mistakes.
- Each labeled example contributes the inequality y_i⟨w, x_i⟩ ≥ 1.
- Multiplying each instance by its label creates the rows of A, producing the matrix system Aw ≥ v with v consisting of ones.
- The objective u = (0, ..., 0) is a dummy objective because any feasible vector is acceptable.
- An LP solver can return a feasible vector w, which is then used as the ERM halfspace predictor.
Key Takeaways
- Realizable ERM becomes a feasibility problem when the goal is zero training error.
- The required condition for every example is y_i⟨w, x_i⟩ ≥ 1.
- The signed training instances y_i x_i become the rows of A, giving Aw ≥ v.
- The zero objective does not rank feasible vectors; it simply accompanies the constraint system.
- A feasible solver output w defines the desired zero-error halfspace predictor.