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, we often assume data points lie on or near an algebraic variety—a shape defined by a set of polynomial equations, such as a circle or a parabola. The "Vanishing Ideal" is the set of all polynomials that equal zero on those data points. Because real-world data is noisy, researchers use the Approximate Vanishing Ideal (AVI) to find polynomials that almost vanish.

While flexible algorithms exist to find these polynomials, they traditionally suffer from three major flaws: spurious vanishing (where polynomials look like they fit due to tiny coefficients), inconsistency under data scaling or translation, and high redundancy in the resulting basis set. This paper introduces a novel way to improve these algorithms by leveraging polynomial gradients.

Methodology: Gradient-Boosted AVI

The authors propose integrating gradient-based methods into a framework called Simple Basis Construction (SBC). Their key innovations include:

  • Gradient Normalization: Instead of normalizing polynomials by their coefficients, they normalize them by the norm of their gradients at the data points. This ensures a polynomial only "vanishes" if it is truly close to its roots, making the algorithm invariant to translation and scaling.
  • Efficient Gradient Computation: By building complex polynomials from simpler ones, the authors compute gradients exactly using the product rule without needing symbolic differentiation, maintaining low computational overhead.
  • Basis Reduction via Gradients: Redundant polynomials are pruned by checking if their gradients are linearly dependent on the gradients of lower-degree polynomials. This numerical shortcut sidesteps the exponentially costly symbolic computations usually required for redundancy removal.

Key Results

The methods were evaluated on synthetic varieties (D1, D2) and real-world classification benchmarks (Iris, Vowel, Vehicle).

Computational Efficiency

The gradient-based approach (SBC-ng) demonstrated massive speedups over coefficient-normalized versions (SBC-nc). On the D2 dataset, the runtime dropped from 17.5 seconds to just 11.4 milliseconds—a speedup of roughly 1,500x.

Table 1: Runtime and basis count comparison for synthetic datasets. The gradient-based method (ng) is significantly faster than the coefficient-based method (nc).

Dimensionality Reduction and Accuracy

In classification tasks, the basis reduction method drastically reduced feature counts. For the "Vowel" dataset, the number of features was reduced from 3,033 to 254 while actually improving classification accuracy (error dropped from 0.45 to 0.40).

Table 2: Performance on real-world datasets. The 'ng+br.' column highlights the reduction in dimensionality (dim.) and its effect on error rates.

Conclusion and Future Work

This research bridges the gap between numerical analysis and symbolic computer algebra, showing that numerical gradients can act as a proxy for symbolic properties. This allows for the theoretical benefits of computer algebra—like redundancy removal—in a fast, "monomial-order-free" way suitable for machine learning.

Future work remains to explore the method's performance on datasets with heavy outliers or non-algebraic structures. Additionally, while the basis reduction method is empirically robust, it relies on a conjecture regarding the link between local gradient dependency and global symbolic redundancy that invites further mathematical proof.

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