Seonglae ChoNCH
Classify a test sample x by measuring its distance to each class's convex hull, then assign it to the class with the nearest convex hull
(PDF) Nearest convex hull classification
PDF | Consider the classification task of assigning a test object to one of two or more possible groups, or classes. An intuitive way to proceed is to... | Find, read and cite all the research you need on ResearchGate
https://www.researchgate.net/publication/46434323_Nearest_convex_hull_classification
This work views each layer's activation space (the set of layer output vectors) in neural networks as a "geometric object," specifically summarizing the structure using convex hulls of class-wise activation vectors. The key contributions are: (1) developing an algorithm to approximate convex hulls in high dimensions, (2) identifying common properties of activation spaces from a convex hull perspective, and (3) creating a Nearest Convex Hull (NCH) classifier that experimentally outperforms the neural network itself in certain cases.
- (A) "All points matter" - almost all points are extreme points
- (B) "No mis-inclusion" - no points fall into other classes' hulls
- (C) Within-class distance distributions are generally unimodal, with deeper layers showing greater cohesion
- (D) Monotonic trends in inter-class distances with positive correlation to intra-class distances
When summarizing activation space with convex hulls, well-separated geometric structures emerge for each class. The NCH classifier using this structure shows better generalization than the neural network (especially in overfitting scenarios), and the paper proposes this as a new metric for overfitting and pruning perspectives.
arxiv.org
https://arxiv.org/pdf/1904.01399
Proposes an algorithm to efficiently find the nearest point on a convex hull to an external query point in high-dimensional, large-scale datasets. The problem is essentially a least-squares problem with linear constraints (convex optimization), but existing optimization methods have high computational costs when the number of data points is very large. Based on the observation that optimal solutions are very sparse, it leverages the fact that only a small fraction of all data points are actually needed. The data is sorted by distance to the query point, then the convex hull is progressively expanded in sketch-sized subsets. At each step, the solution from the previous step is used as the initial value, and the Gradient Projection Method is applied to update only the active constraints. This approach naturally excludes unnecessary points while maintaining the exact optimal solution. The proposed sketching-based algorithm can accurately compute the nearest point on a convex hull in high-dimensional, large-scale data much faster than existing off-the-shelf optimization techniques.
arxiv.org
https://arxiv.org/pdf/2102.10502