Highly Scalable and Provably Accurate Classification in Poincare Balls

• URL: http://arxiv.org/abs/2109.03781v2
• Date: Thu, 9 Sep 2021 15:24:50 GMT
• Title: Highly Scalable and Provably Accurate Classification in Poincare Balls
• Authors: Eli Chien, Chao Pan, Puoya Tabaghi, Olgica Milenkovic
• Abstract summary: We establish a unified framework for learning scalable and simple hyperbolic linear classifiers with provable performance guarantees. Our results include a new hyperbolic and second-order perceptron algorithm as well as an efficient and highly accurate convex optimization setup for hyperbolic support vector machine classifiers. Their performance accuracies on synthetic data sets comprising millions of points, as well as on complex real-world data sets such as single-cell RNA-seq expression measurements, CIFAR10, Fashion-MNIST and mini-ImageNet.
• Score: 40.82908295137667
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many high-dimensional and large-volume data sets of practical relevance have hierarchical structures induced by trees, graphs or time series. Such data sets are hard to process in Euclidean spaces and one often seeks low-dimensional embeddings in other space forms to perform required learning tasks. For hierarchical data, the space of choice is a hyperbolic space since it guarantees low-distortion embeddings for tree-like structures. Unfortunately, the geometry of hyperbolic spaces has properties not encountered in Euclidean spaces that pose challenges when trying to rigorously analyze algorithmic solutions. Here, for the first time, we establish a unified framework for learning scalable and simple hyperbolic linear classifiers with provable performance guarantees. The gist of our approach is to focus on Poincar\'e ball models and formulate the classification problems using tangent space formalisms. Our results include a new hyperbolic and second-order perceptron algorithm as well as an efficient and highly accurate convex optimization setup for hyperbolic support vector machine classifiers. All algorithms provably converge and are highly scalable as they have complexities comparable to those of their Euclidean counterparts. Their performance accuracies on synthetic data sets comprising millions of points, as well as on complex real-world data sets such as single-cell RNA-seq expression measurements, CIFAR10, Fashion-MNIST and mini-ImageNet.

Related papers

• From Semantics to Hierarchy: A Hybrid Euclidean-Tangent-Hyperbolic Space Model for Temporal Knowledge Graph Reasoning [1.1372536310854844]
  Temporal knowledge graph (TKG) reasoning predicts future events based on historical data. Existing Euclidean models excel at capturing semantics but struggle with hierarchy. We propose a novel hybrid geometric space approach that leverages the strengths of both Euclidean and hyperbolic models.
  arXiv  Detail & Related papers  (2024-08-30T10:33:08Z)
• Accelerating hyperbolic t-SNE [7.411478341945197]
  This paper introduces the first acceleration structure for hyperbolic embeddings, building upon a polar quadtree. We demonstrate that it computes embeddings of similar quality in significantly less time.
  arXiv  Detail & Related papers  (2024-01-23T12:59:40Z)
• Fast hyperboloid decision tree algorithms [0.6656737591902598]
  We present hyperDT, a novel extension of decision tree algorithms into hyperbolic space. Our approach is conceptually straightforward and maintains constant-time decision complexity. Building upon hyperDT we introduce hyperRF, a hyperbolic random forest model.
  arXiv  Detail & Related papers  (2023-10-20T22:31:10Z)
• Tight and fast generalization error bound of graph embedding in metric space [54.279425319381374]
  We show that graph embedding in non-Euclidean metric space can outperform that in Euclidean space with much smaller training data than the existing bound has suggested. Our new upper bound is significantly tighter and faster than the existing one, which can be exponential to $R$ and $O(frac1S)$ at the fastest.
  arXiv  Detail & Related papers  (2023-05-13T17:29:18Z)
• HRCF: Enhancing Collaborative Filtering via Hyperbolic Geometric Regularization [52.369435664689995]
  We introduce a textitHyperbolic Regularization powered Collaborative Filtering (HRCF) and design a geometric-aware hyperbolic regularizer. Specifically, the proposal boosts optimization procedure via the root alignment and origin-aware penalty. Our proposal is able to tackle the over-smoothing problem caused by hyperbolic aggregation and also brings the models a better discriminative ability.
  arXiv  Detail & Related papers  (2022-04-18T06:11:44Z)
• Provably Accurate and Scalable Linear Classifiers in Hyperbolic Spaces [39.71927912296049]
  We propose a unified framework for learning scalable and simple hyperbolic linear classifiers. The gist of our approach is to focus on Poincar'e ball models and formulate the classification problems using tangent space formalisms. The excellent performance of the Poincar'e second-order and strategic perceptrons shows that the proposed framework can be extended to general machine learning problems in hyperbolic spaces.
  arXiv  Detail & Related papers  (2022-03-07T21:36:21Z)
• A Local Similarity-Preserving Framework for Nonlinear Dimensionality Reduction with Neural Networks [56.068488417457935]
  We propose a novel local nonlinear approach named Vec2vec for general purpose dimensionality reduction. To train the neural network, we build the neighborhood similarity graph of a matrix and define the context of data points. Experiments of data classification and clustering on eight real datasets show that Vec2vec is better than several classical dimensionality reduction methods in the statistical hypothesis test.
  arXiv  Detail & Related papers  (2021-03-10T23:10:47Z)
• Linear Classifiers in Mixed Constant Curvature Spaces [40.82908295137667]
  We address the problem of linear classification in a product space form -- a mix of Euclidean, spherical, and hyperbolic spaces. We prove that linear classifiers in $d$-dimensional constant curvature spaces can shatter exactly $d+1$ points. We describe a novel perceptron classification algorithm, and establish rigorous convergence results.
  arXiv  Detail & Related papers  (2021-02-19T23:29:03Z)
• Robust Large-Margin Learning in Hyperbolic Space [64.42251583239347]
  We present the first theoretical guarantees for learning a classifier in hyperbolic rather than Euclidean space. We provide an algorithm to efficiently learn a large-margin hyperplane, relying on the careful injection of adversarial examples. We prove that for hierarchical data that embeds well into hyperbolic space, the low embedding dimension ensures superior guarantees.
  arXiv  Detail & Related papers  (2020-04-11T19:11:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.