Random Matrix Analysis to Balance between Supervised and Unsupervised Learning under the Low Density Separation Assumption

• URL: http://arxiv.org/abs/2310.13434v1
• Date: Fri, 20 Oct 2023 11:46:12 GMT
• Title: Random Matrix Analysis to Balance between Supervised and Unsupervised Learning under the Low Density Separation Assumption
• Authors: Vasilii Feofanov, Malik Tiomoko, Aladin Virmaux
• Abstract summary: We introduce QLDS, a linear classification model, where the low density separation assumption is implemented via quadratic margin. We show that particular cases of our algorithm are the least-square support vector machine in the supervised case, the spectral clustering in the fully unsupervised regime, and a class of semi-supervised graph-based approaches.
• Score: 9.620832983703863
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a theoretical framework to analyze semi-supervised classification under the low density separation assumption in a high-dimensional regime. In particular, we introduce QLDS, a linear classification model, where the low density separation assumption is implemented via quadratic margin maximization. The algorithm has an explicit solution with rich theoretical properties, and we show that particular cases of our algorithm are the least-square support vector machine in the supervised case, the spectral clustering in the fully unsupervised regime, and a class of semi-supervised graph-based approaches. As such, QLDS establishes a smooth bridge between these supervised and unsupervised learning methods. Using recent advances in the random matrix theory, we formally derive a theoretical evaluation of the classification error in the asymptotic regime. As an application, we derive a hyperparameter selection policy that finds the best balance between the supervised and the unsupervised terms of our learning criterion. Finally, we provide extensive illustrations of our framework, as well as an experimental study on several benchmarks to demonstrate that QLDS, while being computationally more efficient, improves over cross-validation for hyperparameter selection, indicating a high promise of the usage of random matrix theory for semi-supervised model selection.

Related papers

• Synergistic eigenanalysis of covariance and Hessian matrices for enhanced binary classification [75.90957645766676]
  We present a novel approach that combines the eigenanalysis of a covariance matrix evaluated on a training set with a Hessian matrix evaluated on a deep learning model. Our approach is substantiated by formal proofs that establish its capability to maximize between-class mean distance and minimize within-class variances.
  arXiv  Detail & Related papers  (2024-02-14T16:10:42Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• ClusterDDPM: An EM clustering framework with Denoising Diffusion Probabilistic Models [9.91610928326645]
  Denoising diffusion probabilistic models (DDPMs) represent a new and promising class of generative models. In this study, we introduce an innovative expectation-maximization (EM) framework for clustering using DDPMs. In the M-step, our focus lies in learning clustering-friendly latent representations for the data by employing the conditional DDPM and matching the distribution of latent representations to the mixture of Gaussian priors.
  arXiv  Detail & Related papers  (2023-12-13T10:04:06Z)
• Making Linear MDPs Practical via Contrastive Representation Learning [101.75885788118131]
  It is common to address the curse of dimensionality in Markov decision processes (MDPs) by exploiting low-rank representations. We consider an alternative definition of linear MDPs that automatically ensures normalization while allowing efficient representation learning. We demonstrate superior performance over existing state-of-the-art model-based and model-free algorithms on several benchmarks.
  arXiv  Detail & Related papers  (2022-07-14T18:18:02Z)
• Supervised Dictionary Learning with Auxiliary Covariates [0.0]
  Supervised dictionary learning (SDL) is a machine learning method that simultaneously seeks feature extraction and classification tasks. We provide a novel framework that lifts' SDL as a convex problem in a combined factor space. We apply SDL for imbalanced document classification by supervised topic modeling and also for pneumonia from chest X-ray images.
  arXiv  Detail & Related papers  (2022-06-14T12:10:03Z)
• Estimating Average Treatment Effects with Support Vector Machines [77.34726150561087]
  Support vector machine (SVM) is one of the most popular classification algorithms in the machine learning literature. We adapt SVM as a kernel-based weighting procedure that minimizes the maximum mean discrepancy between the treatment and control groups. We characterize the bias of causal effect estimation arising from this trade-off, connecting the proposed SVM procedure to the existing kernel balancing methods.
  arXiv  Detail & Related papers  (2021-02-23T20:22:56Z)
• Robust Unsupervised Learning via L-Statistic Minimization [38.49191945141759]
  We present a general approach to this problem focusing on unsupervised learning. The key assumption is that the perturbing distribution is characterized by larger losses relative to a given class of admissible models. We prove uniform convergence bounds with respect to the proposed criterion for several popular models in unsupervised learning.
  arXiv  Detail & Related papers  (2020-12-14T10:36:06Z)
• Selective Classification via One-Sided Prediction [54.05407231648068]
  One-sided prediction (OSP) based relaxation yields an SC scheme that attains near-optimal coverage in the practically relevant high target accuracy regime. We theoretically derive bounds generalization for SC and OSP, and empirically we show that our scheme strongly outperforms state of the art methods in coverage at small error levels.
  arXiv  Detail & Related papers  (2020-10-15T16:14:27Z)
• Sparse Methods for Automatic Relevance Determination [0.0]
  We first review automatic relevance determination (ARD) and analytically demonstrate the need to additional regularization or thresholding to achieve sparse models. We then discuss two classes of methods, regularization based and thresholding based, which build on ARD to learn parsimonious solutions to linear problems.
  arXiv  Detail & Related papers  (2020-05-18T14:08:49Z)
• Saliency-based Weighted Multi-label Linear Discriminant Analysis [101.12909759844946]
  We propose a new variant of Linear Discriminant Analysis (LDA) to solve multi-label classification tasks. The proposed method is based on a probabilistic model for defining the weights of individual samples. The Saliency-based weighted Multi-label LDA approach is shown to lead to performance improvements in various multi-label classification problems.
  arXiv  Detail & Related papers  (2020-04-08T19:40:53Z)

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.