Convex Hulls and Convex Combinations
The compressed object is a subset of training points, not the weight vector itself.
From Classifier to Compressed Description
A separating classifier can appear to depend on every training example. The compression construction takes a different approach: it chooses one special vector from the training sample and keeps only enough training points to rebuild that vector. The retained subset, not the vector itself, is the compressed object.
Keep this distinction in view: the classifier is determined by w, while the compressed description consists of selected training points from which w can be reconstructed.
Reading a Homogeneous Halfspace
A homogeneous halfspace uses the sign of a dot product with a vector w. A point x is placed on the positive side when its dot product with w is positive, and on the nonpositive side when that dot product is nonpositive. The separating hyperplane is the boundary associated with w. In the construction studied here, the selected vector is required to separate the training points, so every training point has a positive dot product with w.
Building the Convex Hull
A convex combination forms a point by assigning nonnegative coefficients to sample points, with the coefficients summing to one. The convex hull is the collection of all points obtainable in this way from the training sample. Because the minimum-norm vector is chosen from this hull, it can ultimately be expressed as a convex combination of training points.
Representing the Chosen Vector
Suppose the selected vector w lies in the convex hull of the training sample. What does that tell us about its representation?
Start with hull membership: Because w belongs to the convex hull, it can be written as a convex combination of sample points.
Use valid coefficients: The coefficients multiplying the sample points are nonnegative and sum to one.
Interpret the result: The representation gives a recipe for rebuilding w from selected training points.
The vector w is not stored as the compressed object. The selected points and their convex-combination coefficients provide the reconstruction recipe.
Tracing the Minimum-Norm Choice
The compression algorithm first considers the convex hull of the entire training sample. It then selects the point w in that hull with the smallest Euclidean norm. Geometrically, w is the point where the line from the origin reaches the convex hull most closely. Equivalently, w is the Euclidean projection of the origin onto the convex hull.
The minimum-norm property does more than choose a convenient point. It forces w to separate the training points. If some training point xi had a nonpositive dot product with w, then moving a suitable amount from w toward xi would produce another point in the same convex hull that is closer to the origin. That would contradict the choice of w as the closest point in the hull. Therefore the minimum-norm point is a valid separating vector for linearly separable data.
What do you think happens?
If a training point had a nonpositive dot product with the minimum-norm point w, what would the geometric argument need to produce?
Reveal answer
Answer: A point inside the convex hull that is closer to the origin
Moving a suitable amount from w toward that training point stays within the convex hull. The resulting closer point contradicts the definition of w as the minimum-norm point.
Reducing the Training Sample
The full training sample is reduced in stages. First, the whole sample defines a convex hull. Next, the minimum-norm point w is selected from that hull. Finally, only a small set of training points is retained because those points can be used in a convex combination that reconstructs w.
Carathéodory's Representation Limit
Carathéodory's theorem limits how many sample points are needed to represent a point in the convex hull. In d-dimensional space, it first gives a representation using at most d + 1 points. In this construction, the minimum-norm point lies on a face of the convex hull. That additional face property reduces the representation to a convex combination of d sample points.
| Stage | What is being described | Number of points |
|---|---|---|
| General convex-hull representation | An arbitrary point in a d-dimensional convex hull | At most d + 1 |
| This minimum-norm construction | The minimum-norm point on a face of the hull | d |
Compression versus Reconstruction
Compression answers the question, “Which training points must be retained?” Reconstruction answers a different question, “How do those retained points produce w?” The compressed description contains selected sample points. Applying their convex-combination coefficients rebuilds w, and w determines the classifier.
Treating w itself as the compressed object.
The construction defines the compressed description as a subset of training points from which w can be recovered.
Fix:
Separate the classifier vector from the points used to reconstruct it.Assuming any correctly classifying points form the compressed representation.
The retained points are chosen because their convex combination reconstructs the particular minimum-norm vector.
Fix:
Focus on geometric reconstruction, not only on classification correctness.Stopping at the d + 1 bound.
The minimum-norm point lies on a face of the convex hull, which strengthens the representation to d points.
Fix:
Apply the face property after applying the general convex-hull representation result.
Practice the Mechanism
Describe the compression and reconstruction process in order. Your answer should identify the role of the full training sample, the convex hull, the minimum-norm point w, the retained subset, and the convex combination used to rebuild w.
Hints
- Begin with the convex hull of the entire training sample.
- Explain why w is selected from that hull.
- State what property makes w a separating vector.
- Finish by distinguishing the selected points from the vector they reconstruct.
A Complete Trace
Trace what happens to a linearly separable training sample under this compression construction.
Collect the sample: Start with all training points and consider their convex hull.
Choose w: Select the point in the hull with minimum Euclidean norm, meaning the point closest to the origin.
Verify separation: If any training point had a nonpositive dot product with w, moving toward it would yield a closer point in the same hull. Since that is impossible, w separates the training points.
Limit the representation: Because w is in the hull, it has a convex-combination representation. Carathéodory gives at most d + 1 points, and the face property improves this to d points.
Store and rebuild: Store the selected training points as the compressed description. Use their convex coefficients to reconstruct w when the classifier is needed.
The sample is compressed to a small subset whose convex combination recovers the separating minimum-norm vector.
Key Takeaways
- A homogeneous halfspace uses the sign of a dot product with a vector w.
- The algorithm finds the minimum-norm point in the convex hull of the training sample.
- That minimum-norm point separates the training data because a nonpositive dot product would create a closer point in the same hull.
- Carathéodory's theorem gives at most d + 1 points for a general representation, while the face property reduces this construction to d points.
- Compression retains selected training points; reconstruction combines them to recover w.
Key Takeaways
- The convex hull turns the full training sample into a geometric object containing all convex combinations of its points.
- The minimum-norm point in that hull is the central vector w.
- Linear separability follows from the contradiction that any nonpositive dot product would permit a closer point in the hull.
- The selected training points are the compressed representation, while their convex combination reconstructs the classifier vector.
- Carathéodory's theorem and the face property reduce the needed representation to d points in d-dimensional space.