Spurious Vanishing Problem in Approximate Vanishing Ideal

Hiroshi Kera, Yoshihiko Hasegawa

In the world of computer algebra and machine learning, "vanishing ideals" are a powerful way to uncover the hidden geometric structures of data. Imagine a cloud of points in space; a vanishing ideal is the set of all polynomials (equations) that evaluate to zero on those points. In practice, because data is noisy, we look for approximate vanishing ideals—polynomials that are almost zero.

However, a new paper by Hiroshi Kera and Yoshihiko Hasegawa reveals a fundamental flaw in how we’ve been building these models: the Spurious Vanishing Problem.

TL;DR

This paper identifies a theoretical "glitch" where polynomials appear to capture data structure simply because their coefficients are tiny, not because they actually fit the data. The authors propose a novel framework that integrates coefficient normalization into basis construction via generalized eigenvalue problems, resulting in more stable models and significantly shorter feature vectors for classification.

What Problem Does This Paper Address?

To understand the problem, consider a polynomial $g(x)$. If $g(x) \approx 0$ for all points in your dataset, you’ve found a "vanishing" polynomial that describes your data's shape.

The "Spurious Vanishing Problem" occurs because of simple math: if you take any polynomial and multiply all its coefficients by $0.00001$, the output value becomes very small. It "vanishes," but it hasn't learned anything about the data—it’s just been shrunk. Conversely, a polynomial that perfectly describes the data might be rejected if its coefficients are massive, making its output values look large.

Existing "polynomial-based" algorithms (like the popular Vanishing Component Analysis, or VCA) suffer from this because they don't account for the scale of the coefficients during construction. This leads to numerical instability, where coefficients either explode or vanish, creating "fake" features that degrade machine learning performance.

Methods

The authors introduce a refined version of the Simple Basis Construction (SBC) algorithm. Their core contributions are:

  1. Normalization via Generalized Eigenvalues: Instead of solving a standard eigenvalue problem to find vanishing polynomials, they formulate it as a Generalized Eigenvalue Problem (GEP). This allows them to find polynomials that minimize the "vanishing" value relative to the norm of their coefficients.
  2. Iterative Coefficient Tracking: Expanding polynomials to find their coefficients is computationally "expensive" (it grows exponentially). The authors developed a method to update coefficient vectors iteratively using a special matrix ($R_p^{\le t}$) that extends a degree-$t$ polynomial to degree-$(t+1)$ without full symbolic expansion.
  3. Coefficient Truncation: To keep the math fast, they propose a truncation method. They found that most monomials in a vanishing polynomial have negligible impact. By keeping only the "important" ones (those with large coefficients), they can speed up the algorithm by 2 to 20 times with minimal loss in accuracy.

Datasets

The researchers evaluated their method on two types of data:

  • Synthetic Algebraic Varieties: Geometric shapes like double concentric circles, triple concentric ellipses, and complex surfaces (e.g., $xz - y^2 = 0$).
  • Real-World Benchmarks: Three classic datasets from the UCI Machine Learning Repository: Iris (flower classification), Vowel (speech recognition), and Vehicle (object recognition).

Key Insights and Ideas

  • The "Aha" Moment on Scale: The authors prove that without normalization, polynomial-based methods are essentially "blind" to the scale of the equations they produce. By forcing the coefficient norm to be unity, they ensure that "vanishing" actually means "geometric fit."
  • Data-Driven Monomial Selection: Unlike traditional "monomial-based" methods that rely on a fixed ordering (like alphabetical order for variables), their truncation method is entirely data-driven. It keeps monomials that contribute most to the non-vanishing signal, making it more flexible for complex datasets.
  • Shorter is Better: One of the most interesting findings is that by fixing the spurious vanishing problem, the algorithm produces much smaller "basis sets." In machine learning terms, this means shorter feature vectors that are easier for a classifier to process.

Key Results

  • Stability: In synthetic tests, the standard VCA algorithm showed coefficient norms swinging wildly (from $10^{-15}$ to $10^{10}$). The proposed $SBC-n_c$ method kept norms perfectly stable at $1.0$.
  • Efficiency in Classification: On the Vehicle dataset, the proposed method reduced the length of the feature vector by 36% (about 3,000 fewer features) while maintaining or slightly improving classification accuracy.
  • Accuracy Boost: For the Vowel dataset, the error rate dropped from 0.45 (VCA) to 0.34 ($SBC-n_c$ with $\theta=1.0$), showing that removing "spurious" features directly helps the model learn.

Limitations and Future Work

While the truncation method significantly speeds up the process, the authors acknowledge that scalability remains a challenge for extremely high-dimensional data. The current method is "unsupervised"—it finds the structure of each class independently.

The authors suggest that the next logical step is Discriminative Vanishing Ideals: incorporating class labels directly into the normalization process to find polynomials that not only describe one class but specifically help distinguish it from others.

Reference: Kera, H., & Hasegawa, Y. (2019). Spurious Vanishing Problem in Approximate Vanishing Ideal. arXiv:1901.08798v3 [stat.ML].

Summary updated

Abstract

Approximate vanishing ideal is a concept from computer algebra that studies the algebraic varieties behind perturbed data points. To capture the nonlinear structure of perturbed points, the introduction of approximation to exact vanishing ideals plays a critical role. However, such an approximation also gives rise to a theoretical problem-the spurious vanishing problem-in the basis construction of approximate vanishing ideals; namely, obtained basis polynomials can be approximately vanishing simply because of the small coefficients. In this paper, we propose a first general method that enables various basis construction algorithms to overcome the spurious vanishing problem. In particular, we integrate coefficient normalization with polynomial-based basis constructions, which do not need the proper ordering of monomials to process for basis constructions. We further propose a method that takes advantage of the iterative nature of basis construction so that computationally costly operations for coefficient normalization can be circumvented. Moreover, a coefficient truncation method is proposed for further accelerations. From the experiments, it can be shown that the proposed method overcomes the spurious vanishing problem, resulting in shorter feature vectors while sustaining comparable or even lower classification error.
BibTeX
@inproceedings{kera2019spurious,
  author = {Hiroshi Kera and Yoshihiko Hasegawa},
  title = {{Spurious Vanishing Problem in Approximate Vanishing Ideal}},
  booktitle = {IEEE Access},
  year = {2019},
  url = {https://openreview.net/forum?id=TWzJ4wZbtXI},
}

Loading related content...

Figure