Tropical Support Vector Machine and its Applications to Phylogenomics

• URL: http://arxiv.org/abs/2003.00677v2
• Date: Tue, 24 Mar 2020 18:24:18 GMT
• Title: Tropical Support Vector Machine and its Applications to Phylogenomics
• Abstract summary: We propose tropical support vector machines (SVMs) to classify multi-locus data sets for phylogenetic analysis. Both hard margin tropical SVMs and soft margin tropical SVMs can be formulated as linear programming problems.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Most data in genome-wide phylogenetic analysis (phylogenomics) is essentially multidimensional, posing a major challenge to human comprehension and computational analysis. Also, we can not directly apply statistical learning models in data science to a set of phylogenetic trees since the space of phylogenetic trees is not Euclidean. In fact, the space of phylogenetic trees is a tropical Grassmannian in terms of max-plus algebra. Therefore, to classify multi-locus data sets for phylogenetic analysis, we propose tropical support vector machines (SVMs). Like classical SVMs, a tropical SVM is a discriminative classifier defined by the tropical hyperplane which maximizes the minimum tropical distance from data points to itself in order to separate these data points into sectors (half-spaces) in the tropical projective torus. Both hard margin tropical SVMs and soft margin tropical SVMs can be formulated as linear programming problems. We focus on classifying two categories of data, and we study a simpler case by assuming the data points from the same category ideally stay in the same sector of a tropical separating hyperplane. For hard margin tropical SVMs, we prove the necessary and sufficient conditions for two categories of data points to be separated, and we show an explicit formula for the optimal value of the feasible linear programming problem. For soft margin tropical SVMs, we develop novel methods to compute an optimal tropical separating hyperplane. Computational experiments show our methods work well. We end this paper with open problems.

Related papers

• cGAP: Generalized Association Plots with HOMALS-Guided Heatmaps for Visualization of High-Dimensional Categorical Data [1.4377432769428207]
  categorical Generalized Association Plots (cGAP) is a visualization framework for nominal, ordinal, and binary data.<n> cGAP uses Homogeneity Analysis (HOMALS) to embed subjects and category levels in a three-dimensional Euclidean space.<n>We show how cGAP supports transparent exploratory analysis by maintaining traceability between derived visual structure and the original categorical observations.
  arXiv  Detail & Related papers  (2026-07-16T14:05:37Z)
• Phylogenetic Tree Inference with Tropical Axial Attention [1.43494686131174]
  We introduce a Tropical Axial Attention neural reasoning architecture that replaces vanilla softmax dot-product attention with max-plus operators.<n>From multi-species sequence alignments, our model learns all possible pairwise distances.<n>We show that tropical attention provides a natural geometric framework for phylogenetic inference.
  arXiv  Detail & Related papers  (2026-05-12T10:54:37Z)
• Exact Dynamics of Multi-class Stochastic Gradient Descent [4.1538344141902135]
  We develop a framework for analyzing the training and learning rate dynamics on a variety of high-dimensional optimization problems trained using one-pass gradient descent (SGD)<n>We give exact expressions for a large class of functions of the limiting dynamics, including the risk and the overlap with the true signal, in terms of a deterministic solution to a system of ODEs.
  arXiv  Detail & Related papers  (2025-10-15T20:31:49Z)
• MORPH: Shape-agnostic PDE Foundation Models [37.26306668589026]
  MORPH is a shape-agnostic, autoregressive foundation model for partial differential equations (PDEs)<n>It is built on a convolutional vision backbone that seamlessly handles heterogeneous evaluations of varying data dimensionality (1D--3D)<n>Across extensive datasets, MORPH matches or surpasses strong baselines and recent state-of-the-art models.
  arXiv  Detail & Related papers  (2025-09-25T22:38:36Z)
• Classification by Separating Hypersurfaces: An Entropic Approach [0.0]
  We consider the classification problem of individuals characterized by a set of attributes represented as a vector in $mathbb RN$.<n>The goal is to find a hyperplane in $mathbb RN$ that separates two sets of points corresponding to two distinct classes.<n>We propose a novel approach by searching for a vector of parameters in a bounded $N-dimensional hypercube.
  arXiv  Detail & Related papers  (2025-07-03T15:43:54Z)
• Optimal Mixed Integer Linear Optimization Trained Multivariate Classification Trees [0.0]
  We propose two cut-based mixed integer linear optimization (MILO) formulations for designing optimal binary classification trees. Our models leverage on-the-fly identification of minimal infeasible subsystems (MISs) from which we derive cutting planes that hold the form of packing constraints.
  arXiv  Detail & Related papers  (2024-08-02T14:37:28Z)
• Latent Semantic Consensus For Deterministic Geometric Model Fitting [109.44565542031384]
  We propose an effective method called Latent Semantic Consensus (LSC) LSC formulates the model fitting problem into two latent semantic spaces based on data points and model hypotheses. LSC is able to provide consistent and reliable solutions within only a few milliseconds for general multi-structural model fitting.
  arXiv  Detail & Related papers  (2024-03-11T05:35:38Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Minimally Supervised Learning using Topological Projections in Self-Organizing Maps [55.31182147885694]
  We introduce a semi-supervised learning approach based on topological projections in self-organizing maps (SOMs) Our proposed method first trains SOMs on unlabeled data and then a minimal number of available labeled data points are assigned to key best matching units (BMU) Our results indicate that the proposed minimally supervised model significantly outperforms traditional regression techniques.
  arXiv  Detail & Related papers  (2024-01-12T22:51:48Z)
• Matrix Factorization in Tropical and Mixed Tropical-Linear Algebras [27.680519297540535]
  We investigate two problems involving matrix factorization over the tropical algebra. For the first problem, we propose an improved algorithm that avoids many of the local optima. The second formulation considers the approximate decomposition of a given matrix into the product of three matrices.
  arXiv  Detail & Related papers  (2023-09-25T07:29:59Z)
• Large-scale gradient-based training of Mixtures of Factor Analyzers [67.21722742907981]
  This article contributes both a theoretical analysis as well as a new method for efficient high-dimensional training by gradient descent. We prove that MFA training and inference/sampling can be performed based on precision matrices, which does not require matrix inversions after training is completed. Besides the theoretical analysis and matrices, we apply MFA to typical image datasets such as SVHN and MNIST, and demonstrate the ability to perform sample generation and outlier detection.
  arXiv  Detail & Related papers  (2023-08-26T06:12:33Z)
• VaiPhy: a Variational Inference Based Algorithm for Phylogeny [2.2499166814992435]
  We propose VaiPhy, a remarkably fast VI based algorithm for approximate posterior inference in an augmented tree space. VaiPhy produces marginal log-likelihood estimates on par with the state-of-the-art methods on real data, and is considerably faster since it does not require auto-differentiation.
  arXiv  Detail & Related papers  (2022-03-01T13:55:56Z)
• 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)
• Tropical Support Vector Machines: Evaluations and Extension to Function Spaces [0.0]
  tropical SVMs classify data points using a tropical hyperplane under the tropical metric with the max-plus algebra. We show theoretically by extreme value statistics that the tropical SVMs for classifying data points are fairly robust against the curse of dimensionality.
  arXiv  Detail & Related papers  (2021-01-27T16:35:34Z)
• Two-step penalised logistic regression for multi-omic data with an application to cardiometabolic syndrome [62.997667081978825]
  We implement a two-step approach to multi-omic logistic regression in which variable selection is performed on each layer separately. Our approach should be preferred if the goal is to select as many relevant predictors as possible. Our proposed approach allows us to identify features that characterise cardiometabolic syndrome at the molecular level.
  arXiv  Detail & Related papers  (2020-08-01T10:36:27Z)
• Learning Bijective Feature Maps for Linear ICA [73.85904548374575]
  We show that existing probabilistic deep generative models (DGMs) which are tailor-made for image data, underperform on non-linear ICA tasks. To address this, we propose a DGM which combines bijective feature maps with a linear ICA model to learn interpretable latent structures for high-dimensional data. We create models that converge quickly, are easy to train, and achieve better unsupervised latent factor discovery than flow-based models, linear ICA, and Variational Autoencoders on images.
  arXiv  Detail & Related papers  (2020-02-18T17:58:07Z)

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.