Carathéodory's Theorem
Carathéodory's theorem gives a representation using at most d plus 1 points in d-dimensional space.
The Compression Question
A linear classifier may appear to depend on every training example. The construction studied here searches for a much smaller description: a subset of training points from which the classifier's separating vector can be reconstructed. The important distinction is that the compressed object is not the weight vector itself. It is a selected subset of training points.
The classifier is determined by a vector, but the compressed description consists of training points that can be used to rebuild that vector.
Homogeneous Halfspaces
For a vector w, a homogeneous halfspace is determined by the sign of the dot product between an input point x and w. A positive dot product places x on one side of the hyperplane, a negative dot product places it on the other side, and a zero dot product places it on the boundary. The hyperplane passes through the origin because there is no separate offset term in this description.
This sign rule explains why the vector selected from the training sample matters: if it has the required dot-product sign for every training point, it defines a separator for the sample.
Finding the Closest Hull Point
Start with the convex hull of the training sample. The construction selects the point w in that convex hull whose Euclidean norm is as small as possible. 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.
Following the geometric selection
Given a linearly separable training sample, identify the vector used by the compression construction.
- 1Form the hull
Combine the training points through their convex hull. The construction works with this geometric object rather than examining the points as an unrelated list.
- 2Search for the closest point
Among all points in the convex hull, select w, the point with the smallest Euclidean norm. It is the point in the hull closest to the origin.
- 3Use w as the separator
The selected vector is used as the separating vector for the homogeneous hyperplane.
The target of the compression process is the minimum-norm point w of the training sample's convex hull.
Why Separation Follows
The minimum-norm property does more than choose a convenient point. It forces w to separate the training data. Suppose, for contradiction, that some training point xi had a nonpositive dot product with w. Moving a suitable amount from w toward xi would stay inside the same convex hull while producing a point closer to the origin. That would contradict the choice of w as the closest point in the hull.
What do you think happens?
What would contradict the claim that w is the minimum-norm point of the convex hull?
Reveal answer
Finding a training point with a nonpositive dot product with w
A suitable move from w toward that training point would remain in the convex hull and get closer to the origin, contradicting the minimum-norm choice.
Carathéodory's Point Bound
Because w lies in the convex hull of the training sample, it can be written as a convex combination of sample points. Carathéodory's theorem gives a representation using at most d plus 1 points in d-dimensional space. In this construction, there is an additional geometric fact: the minimum-norm point lies on a face of the convex hull. The face property reduces the representation to a convex combination of d sample points.
| Geometric fact | Representation consequence |
|---|---|
| w lies in the convex hull | w can be written as a convex combination of training points |
| Carathéodory's theorem applies in d dimensions | At most d plus 1 points are needed in general |
| w lies on a face of the convex hull | This construction uses d points |
The general theorem and the additional face property play different roles.
Compression and Reconstruction
The process has two different stages. First comes compression: retain the small subset of training points that participates in a convex-combination representation of w. The points are the compressed description. Second comes reconstruction: use those selected points and their convex-combination coefficients to recover w. The classifier is then determined by the reconstructed vector.
Common mistake Treating w itself as the compressed object
What it looks likeKeeping only the separating vector and calling that the subset representation
Why it failsThe construction defines the compressed description as selected training points from which w can be reconstructed.
Do this insteadSeparate the roles: the subset is stored as the compressed description, and w is rebuilt from it.
Common mistake Assuming any correctly classifying examples form the compressed subset
What it looks likeChoosing points merely because they are classified correctly
Why it failsThe selected points come from a convex-combination representation of the minimum-norm point.
Do this insteadTie selection to the geometry of the convex hull and the representation of w.
Common mistake Stopping at the general d plus 1 bound
What it looks likeIgnoring the fact that w lies on a face
Why it failsThe face property gives the stronger d-point representation for this construction.
Do this insteadState both results: Carathéodory's general bound is d plus 1, while the additional face property reduces this case to d.
A Complete Trace
Tracing the full compression construction
Explain how a linearly separable training sample becomes a compact description of a classifier.
- 1Begin with the sample
Take the complete set of training points and consider its convex hull.
- 2Select w
Find the point in that convex hull with minimum Euclidean norm. This is the point closest to the origin.
- 3Use the separation property
If any training point had a nonpositive dot product with w, moving toward that point would create a closer hull point. Therefore the minimum-norm argument supplies a separating vector.
- 4Represent w
Because w belongs to the convex hull, express it as a convex combination of sample points.
- 5Reduce the representation
Carathéodory's theorem gives at most d plus 1 points in general. Since w lies on a face in this construction, use d points.
- 6Reconstruct later
Store the selected points as the compressed description. When needed, combine them with their coefficients to recover w and therefore the classifier.
The sample is compressed by retaining points, while the separating vector is reconstructed from those points rather than being treated as the compressed object.
The order matters. The minimum-norm point is selected before the small representation is extracted. Carathéodory's theorem does not by itself choose the classifier; it limits how many sample points are needed after the relevant convex-hull vector has been identified.
Practice Check
A training sample lies in d-dimensional space. Explain, in order, how to obtain a compressed description using the minimum-norm point of its convex hull. Your answer should identify the object selected first, explain why it separates the sample, state the general Carathéodory bound, state the stronger bound available here, and distinguish the stored subset from the reconstructed vector.
Hints
- Begin with the convex hull rather than with an arbitrary training point.
- Use the contradiction involving a nonpositive dot product to explain separation.
- Mention both d plus 1 and d, and explain why they differ.
- 1Carathéodory's theorem supports a compression construction for a linearly separable training sample. The process selects the minimum-norm point w of the sample's convex hull. That point separates the training data because a nonpositive dot product would allow a closer point in the same hull. Since w is in the convex hull, it has a convex-combination representation. Carathéodory's theorem gives at most d plus 1 points in general, and the face property reduces this construction to d points. Those selected training points are the compressed description; their coefficients are used later to reconstruct w.
Key Takeaways
- A homogeneous halfspace is defined by the sign of a dot product with a vector.
- The construction selects the minimum-norm point of the training sample's convex hull.
- The minimum-norm point separates the training data because a nonpositive dot product would contradict its closest-point property.
- Carathéodory's theorem gives a representation using at most d plus 1 points, while the face property reduces this construction to d points.
- The compressed object is a subset of training points, and the separating vector is reconstructed from that subset.