Gradient Boosts the Approximate Vanishing Ideal

Hiroshi Kera, Yoshihiko Hasegawa

Abstract

In the last decade, the approximate vanishing ideal and its basis construction algorithms have been extensively studied in computer algebra and machine learning as a general model to reconstruct the algebraic variety on which noisy data approximately lie. In particular, the basis construction algorithms developed in machine learning are widely used in applications across many fields because of their monomial-order-free property; however, they lose many of the theoretical properties of computer-algebraic algorithms. In this paper, we propose general methods that equip monomial-order-free algorithms with several advantageous theoretical properties. Specifically, we exploit the gradient to (i) sidestep the spurious vanishing problem in polynomial time to remove symbolically trivial redundant bases, (ii) achieve consistent output with respect to the translation and scaling of input, and (iii) remove nontrivially redundant bases. The proposed methods work in a fully numerical manner, whereas existing algorithms require the awkward monomial order or exponentially costly (and mostly symbolic) computation to realize properties (i) and (iii). To our knowledge, property (ii) has not been achieved by any existing basis construction algorithm of the approximate vanishing ideal.

Introduction

In machine learning, data is often assumed to lie near a geometric structure known as an algebraic variety—a set of points where a system of polynomials vanishes. Identifying these polynomials, the "vanishing ideal," is crucial for understanding data structure, dimensionality reduction, and classification. However, existing methods face a tradeoff: computer algebra methods are theoretically sound but rely on rigid monomial ordering and symbolic math, while machine learning methods like Vanishing Component Analysis (VCA) are flexible but suffer from spurious vanishing, inconsistency under data transformation, and high redundancy.

Methodology: Gradient-Based Basis Construction

The core innovation of this work is the Simple Basis Construction with Gradient Normalization (SBC-ng). By utilizing the gradient of polynomials at data points, the authors address the limitations of previous order-free algorithms.

Gradient Normalization and Redundancy Removal

Instead of the computationally expensive coefficient-based normalization, the proposed method normalizes polynomials by the norm of their gradient at input points. This approach filters out "spurious" polynomials—those that appear to vanish only due to small coefficients—in polynomial time. Furthermore, the linear dependency of gradients is used to identify and prune redundant polynomials. If a new polynomial's gradient can be expressed as a combination of gradients from lower-degree polynomials, it is deemed redundant and removed.

Differentiation-Free Computation

A key efficiency gain comes from the iterative nature of the algorithm. Since polynomials are built by multiplying lower-degree terms, exact gradients can be calculated using the product rule without symbolic differentiation, keeping the process purely numerical and fast.

Experimental Evaluation

The method was evaluated on synthetic varieties ($D_1$, $D_2$) and standard UCI datasets (Iris, Vowel, Vehicle).

Performance and Efficiency

The gradient-based approach ($n_g$) demonstrates massive speedups. In the $D_2$ synthetic test, SBC-ng was approximately 1,000 times faster than the coefficient-normalized version ($n_c$).

Runtime and basis count comparison on synthetic datasets. The gradient-based approach ($n_g$) demonstrates significant speedups over coefficient-based normalization ($n_c$).

Dimensionality Reduction and Robustness

On real-world datasets, the basis reduction significantly pruned the output. For the "Vehicle" dataset, feature dimensionality was reduced from over 8,000 to just 260 while maintaining classification accuracy. Additionally, the algorithm provides consistent output regardless of data translation or scaling, a property lacking in previous state-of-the-art ML methods.

Classification performance and dimensionality reduction on UCI datasets. SBC-ng with basis reduction (br.) achieves the most compact representation.

Conclusion and Future Work

By leveraging gradients, this work bridges the gap between the theoretical rigor of computer algebra and the practical flexibility of machine learning. The resulting algorithms are faster, more robust, and produce more compact models. Future work includes formally proving the necessity of the basis reduction method and exploring its behavior on extremely sparse data.

Summary updated

Abstract

In the last decade, the approximate vanishing ideal and its basis construction algorithms have been extensively studied in computer algebra and machine learning as a general model to reconstruct the algebraic variety on which noisy data approximately lie. In particular, the basis construction algorithms developed in machine learning are widely used in applications across many fields because of their monomial-order-free property; however, they lose many of the theoretical properties of computer-algebraic algorithms. In this paper, we propose general methods that equip monomial-order-free algorithms with several advantageous theoretical properties. Specifically, we exploit the gradient to (i) sidestep the spurious vanishing problem in polynomial time to remove symbolically trivial redundant bases, (ii) achieve consistent output with respect to the translation and scaling of input, and (iii) remove nontrivially redundant bases. The proposed methods work in a fully numerical manner, whereas existing algorithms require the awkward monomial order or exponentially costly (and mostly symbolic) computation to realize properties (i) and (iii). To our knowledge, property (ii) has not been achieved by any existing basis construction algorithm of the approximate vanishing ideal.
BibTeX
@inproceedings{kera2020gradient,
  author = {Hiroshi Kera and Yoshihiko Hasegawa},
  title = {{Gradient Boosts the Approximate Vanishing Ideal}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=aiIFTtl5Wr},
}

Loading related content...

Figure