Zeta Hull Pursuits: Learning Nonconvex Data Hulls

Yuanjun Xiong, Wei Liu, Deli Zhao, Xiaoou Tang

In the era of big data, researchers frequently need to select a small, representative subset of samples from a massive dataset to reduce computational costs—a process known as column sampling. Most existing methods assume that data fits into simple structures like clusters or convex hulls (imagine stretching a rubber band around a set of points). However, real-world data often resides on complex manifolds with "dents" and concave regions. Traditional methods like Simplex Volume Maximization or Non-negative Matrix Factorization (NMF) struggle in these scenarios because they are mathematically tethered to the assumption of convexity.

This paper introduces Zeta Hull Pursuits (ZHP), a novel approach for column sampling that successfully captures complex, nonconvex data structures. By leveraging a graph-theoretic measure called the Zeta function to identify "extreme points" on a data hull, ZHP provides a robust way to represent data that outperforms traditional convex-based methods in both text and image classification tasks.

The Geometry of Graph Cycles

To tackle nonconvex boundaries, the authors propose a geometric model based on graph cycles rather than traditional shortest paths or clusters. They argue that cycles capture the "loopiness" and connectivity that truly define a shape's boundary.

The methodology breaks down into several key components:

1. The Zeta Function & Structural Complexity: The algorithm first builds a neighborhood graph of the data. To measure the "complexity" of this graph, it uses a Zeta function, which integrates the affinities of all possible cycles within the graph. This function is powerful because it naturally unites local connectivity (short cycles) and global structure (long cycles) into a single numerical measure.

2. Point Extremeness: The core innovation is a "leave-one-out" strategy. If you remove a point that is deep inside a cluster, the graph's structural complexity changes significantly. However, if you remove an "extreme point" located on the outer hull, the impact on the overall graph structure is minimal.

Removing extreme points on the outer hull minimizes the impact on the graph's core structural complexity.

The authors prove that this "extremeness" measure corresponds mathematically to the diagonal elements of a specific matrix inverse. This realization provides a mathematically rigorous way to define an extreme point without assuming a convex shape.

3. Zeta Hull Pursuits (ZHP): Using this extremeness measure, the authors developed a greedy algorithm to iteratively pick points with the highest extremeness while ensuring the selected points don't overlap too much (acting as a form of regularization).

4. Scalability via Anchors: Computing a matrix inverse for $n$ points is computationally expensive ($O(n^3)$). To make ZHP practical for large-scale datasets, the authors introduce an Anchor Graph technique. By approximating the large adjacency matrix using a small set of "anchor points," they reduce the computational complexity to $O(mnl^2)$. Furthermore, by using SVD "downdating" to reuse calculations from previous iterations, this Anchor-ZHP (A-ZHP) version becomes orders of magnitude faster.

Key Results and Nonconvex Mastery

The authors evaluated ZHP across a variety of benchmarks, including document classification (TDT2, Newsgroups) and image recognition (MNIST, Caltech101, MultiPIE).

Nonconvex Mastery on Toy Data: The most striking visual evidence of ZHP's capability comes from the "Two-Moons" dataset, a classic nonconvex distribution. While traditional methods like Simplex or CUR picked points that failed to represent the actual shape, ZHP successfully identified points along the curved boundaries of the moons.

Comparison of subset selection methods on the Two-Moons dataset. ZHP and A-ZHP successfully capture the nonconvex boundaries.

State-of-the-Art Accuracy: Beyond toy datasets, ZHP proved highly effective in real-world applications. In text classification (TDT2), ZHP achieved an error rate as low as 0.48%, significantly outperforming NMF-based and dictionary learning methods.

Image Robustness: On the MultiPIE face dataset, which evaluates face recognition under varying poses, the anchor-based version (A-ZHP) achieved the lowest recognition error (11.3%) compared to all other subset selection methods. This demonstrates that capturing the "nonconvex hull" retains more discriminative information for complex classification tasks.

Limitations and Future Work

While highly effective, the authors note a few limitations. ZHP can be sensitive to noise; if a noisy outlier is located far from the main data distribution, the algorithm might mistakenly identify it as an "extreme point." To mitigate this, future implementations could pair ZHP with established outlier removal preprocessing steps. Additionally, the method relies on a few free parameters (such as the Zeta function parameter and regularization weights) that currently require some manual tuning to optimize for specific datasets.

Overall, Zeta Hull Pursuits represents a significant step forward in data subset selection, freeing algorithms from the constraints of convexity and allowing them to map the true, complex boundaries of real-world data.

Summary updated

Abstract

Selecting a small informative subset from a given dataset, also called column sampling, has drawn much attention in machine learning. For incorporating structured data information into column sampling, research efforts were devoted to the cases where data points are fitted with clusters, simplices, or general convex hulls. This paper aims to study nonconvex hull learning which has rarely been investigated in the literature. In order to learn data-adaptive nonconvex hulls, a novel approach is proposed based on a graph-theoretic measure that leverages graph cycles to characterize the structural complexities of input data points. Employing this measure, we present a greedy algorithmic framework, dubbed Zeta Hulls, to perform structured column sampling. The process of pursuing a Zeta hull involves the computation of matrix inverse. To accelerate the matrix inversion computation and reduce its space complexity as well, we exploit a low-rank approximation to the graph adjacency matrix by using an efficient anchor graph technique. Extensive experimental results show that data representation learned by Zeta Hulls can achieve state-of-the-art accuracy in text and image classification tasks.
BibTeX
@inproceedings{xiong2014zeta,
  author = {Yuanjun Xiong and Wei Liu and Deli Zhao and Xiaoou Tang},
  title = {{Zeta Hull Pursuits: Learning Nonconvex Data Hulls}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure