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.
Introduction
In the intersection of computer algebra and machine learning, vanishing ideals offer a powerful lens for uncovering the geometric structures inherent in data. A vanishing ideal is defined as the set of all polynomials that evaluate to zero on a given set of points. In practical applications involving noisy data, researchers utilize approximate vanishing ideals—polynomials that yield values close to zero. However, a significant theoretical hurdle, termed the Spurious Vanishing Problem, often undermines the reliability of these models.
The Spurious Vanishing Problem
The Spurious Vanishing Problem occurs when a polynomial $g(x)$ appears to "vanish" (i.e., $\|g(X)\| \approx 0$) not because it accurately models the data's geometry, but simply because its coefficients are extremely small. Conversely, a polynomial that perfectly describes the data might be erroneously rejected if its coefficients are large, causing its evaluation values to appear significant.
As shown in the figure above, without normalization, basis construction algorithms can be misled by the scale of coefficients. For instance, $g_2$ achieves a vanishing value of $0.0$, but its coefficient norm is $4.1$, whereas $g_1$ provides a good fit with a unit norm. Standard polynomial-based algorithms like Vanishing Component Analysis (VCA) often suffer from numerical instability due to this lack of normalization, leading to "fake" features that degrade machine learning performance.
Proposed Methodology
The authors introduce a framework that integrates coefficient normalization directly into the basis construction process, specifically refining the Simple Basis Construction (SBC) algorithm.
1. Normalization via Generalized Eigenvalues
The core innovation involves formulating the search for vanishing polynomials as a Generalized Eigenvalue Problem (GEP). This approach identifies polynomials that minimize the vanishing value relative to the norm of their coefficients: $$\min \frac{\|g(X)\|^2}{\|\mathbf{n}_c(g)\|^2}$$ This ensures that a low evaluation value truly signifies a geometric fit rather than a mere scaling effect.
2. Iterative Coefficient Tracking
Calculating coefficient vectors for high-degree polynomials is computationally intensive. The authors developed an iterative method using a transformation matrix ($R_p^{\le t}$) to update coefficient vectors as the polynomial degree increases. This avoids the exponential cost of full symbolic expansion, making the normalization process feasible for higher-order models.
3. Data-Driven Coefficient Truncation
To further enhance efficiency, a truncation method is proposed. By retaining only the monomials with the most significant coefficients, the algorithm can achieve speedups of up to 20x. Unlike traditional methods that rely on fixed monomial orderings, this approach is entirely data-driven and adaptable to complex datasets.
Experimental Results
The proposed method, $SBC-n_c$, was evaluated against synthetic varieties and real-world datasets (Iris, Vowel, and Vehicle).
- Numerical Stability: While standard VCA saw coefficient norms fluctuate wildly between $10^{-15}$ and $10^{10}$, $SBC-n_c$ maintained stable unit norms throughout.
- Feature Reduction: On the Vehicle dataset, the method reduced the feature vector length by 36% (approximately 3,000 features) without sacrificing accuracy.
- Classification Performance: For the Vowel dataset, the error rate was reduced from 0.45 (VCA) to 0.34 ($SBC-n_c$), demonstrating that removing spurious features directly improves predictive power.
Conclusion and Future Directions
By addressing the spurious vanishing problem, this research provides a more stable and efficient framework for approximate vanishing ideals. The reduction in feature vector size and improvement in classification accuracy highlight the practical utility of coefficient normalization. Future research will explore Discriminative Vanishing Ideals, incorporating class labels into the normalization process to further enhance class separation in high-dimensional spaces.
Reference: Kera, H., & Hasegawa, Y. (2019). Spurious Vanishing Problem in Approximate Vanishing Ideal. arXiv:1901.08798v3 [stat.ML].
Summary updated