Linear Classifiers in Mixed Constant Curvature Spaces
- URL: http://arxiv.org/abs/2102.10204v1
- Date: Fri, 19 Feb 2021 23:29:03 GMT
- Title: Linear Classifiers in Mixed Constant Curvature Spaces
- Authors: Puoya Tabaghi, Eli Chien, Chao Pan, Olgica Milenkovi\'c
- Abstract summary: 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.
- Score: 40.82908295137667
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Embedding methods for mixed-curvature spaces are powerful techniques for
low-distortion and low-dimensional representation of complex data structures.
Nevertheless, little is known regarding downstream learning and optimization in
the embedding space. Here, we address for the first time the problem of linear
classification in a product space form -- a mix of Euclidean, spherical, and
hyperbolic spaces with different dimensions. First, we revisit the definition
of a linear classifier on a Riemannian manifold by using geodesics and
Riemannian metrics which generalize the notions of straight lines and inner
products in vector spaces, respectively. Second, we prove that linear
classifiers in $d$-dimensional constant curvature spaces can shatter exactly
$d+1$ points: Hence, Euclidean, hyperbolic and spherical classifiers have the
same expressive power. Third, we formalize linear classifiers in product space
forms, describe a novel perceptron classification algorithm, and establish
rigorous convergence results. We support our theoretical findings with
simulation results on several datasets, including synthetic data, MNIST and
Omniglot. Our results reveal that learning methods applied to small-dimensional
embeddings in product space forms significantly outperform their algorithmic
counterparts in Euclidean spaces.
Related papers
- Intrinsic dimension estimation for discrete metrics [65.5438227932088]
In this letter we introduce an algorithm to infer the intrinsic dimension (ID) of datasets embedded in discrete spaces.
We demonstrate its accuracy on benchmark datasets, and we apply it to analyze a metagenomic dataset for species fingerprinting.
This suggests that evolutive pressure acts on a low-dimensional manifold despite the high-dimensionality of sequences' space.
arXiv Detail & Related papers (2022-07-20T06:38:36Z) - Fiberwise dimensionality reduction of topologically complex data with
vector bundles [0.0]
We propose to model topologically complex datasets using vector bundles.
The base space accounts for the large scale topology, while the fibers account for the local geometry.
This allows one to reduce the dimensionality of the fibers, while preserving the large scale topology.
arXiv Detail & Related papers (2022-06-13T22:53:46Z) - 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) - Measuring dissimilarity with diffeomorphism invariance [94.02751799024684]
We introduce DID, a pairwise dissimilarity measure applicable to a wide range of data spaces.
We prove that DID enjoys properties which make it relevant for theoretical study and practical use.
arXiv Detail & Related papers (2022-02-11T13:51:30Z) - Highly Scalable and Provably Accurate Classification in Poincare Balls [40.82908295137667]
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.
arXiv Detail & Related papers (2021-09-08T16:59:39Z) - 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) - Switch Spaces: Learning Product Spaces with Sparse Gating [48.591045282317424]
We propose Switch Spaces, a data-driven approach for learning representations in product space.
We introduce sparse gating mechanisms that learn to choose, combine and switch spaces.
Experiments on knowledge graph completion and item recommendations show that the proposed switch space achieves new state-of-the-art performances.
arXiv Detail & Related papers (2021-02-17T11:06:59Z) - Manifold learning with arbitrary norms [8.433233101044197]
We show that manifold learning based on Earthmover's distances outperforms the standard Euclidean variant for learning molecular shape spaces.
We show in a numerical simulation that manifold learning based on Earthmover's distances outperforms the standard Euclidean variant for learning molecular shape spaces.
arXiv Detail & Related papers (2020-12-28T10:24:30Z) - Manifold Learning via Manifold Deflation [105.7418091051558]
dimensionality reduction methods provide a valuable means to visualize and interpret high-dimensional data.
Many popular methods can fail dramatically, even on simple two-dimensional Manifolds.
This paper presents an embedding method for a novel, incremental tangent space estimator that incorporates global structure as coordinates.
Empirically, we show our algorithm recovers novel and interesting embeddings on real-world and synthetic datasets.
arXiv Detail & Related papers (2020-07-07T10:04:28Z)
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.