Clustering risk in Non-parametric Hidden Markov and I.I.D. Models

• URL: http://arxiv.org/abs/2309.12238v4
• Date: Tue, 27 May 2025 10:18:27 GMT
• Title: Clustering risk in Non-parametric Hidden Markov and I.I.D. Models
• Authors: Elisabeth Gassiat, Ibrahim Kaddouri, Zacharie Naulet,
• Abstract summary: We show that clustering based on the Bayes classifier does not always match the optimal Bayes clusterer.<n>A key quantity emerges, capturing the fundamental difficulty of both classification and clustering tasks.
• Score: 4.728478219127298
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We conduct an in-depth analysis of the Bayes risk of clustering in the context of Hidden Markov and i.i.d. models. In both settings, we identify the situations where this risk is comparable to the Bayes risk of classification and those where its minimizer, the Bayes clusterer, can be derived from the Bayes classifier. While we demonstrate that clustering based on the Bayes classifier does not always match the optimal Bayes clusterer, we show that this difference is primarily theoretical and that the Bayes classifier remains nearly optimal for clustering. A key quantity emerges, capturing the fundamental difficulty of both classification and clustering tasks. Furthermore, by leveraging the identifiability of HMMs, we establish bounds on the clustering excess risk of a plug-in Bayes classifier in the general nonparametric setting, offering theoretical justification for its widespread use in practice. Simulations further illustrate our findings.

Related papers

• Balancing Complexity and Informativeness in LLM-Based Clustering: Finding the Goldilocks Zone [0.0]
  This paper investigates the optimal number of clusters by quantifying the trade-off between informativeness and cognitive simplicity.<n>We use large language models (LLMs) to generate cluster names and evaluate their effectiveness.<n>We identify an optimal range of 16-22 clusters, paralleling linguistic efficiency in lexical categorization.
  arXiv  Detail & Related papers  (2025-04-06T01:16:22Z)
• A robust three-way classifier with shadowed granular-balls based on justifiable granularity [53.39844791923145]
  We construct a robust three-way classifier with shadowed GBs for uncertain data. Our model demonstrates in managing uncertain data and effectively mitigates classification risks.
  arXiv  Detail & Related papers  (2024-07-03T08:54:45Z)
• Precise analysis of ridge interpolators under heavy correlations -- a Random Duality Theory view [0.0]
  We show that emphRandom Duality Theory (RDT) can be utilized to obtain precise closed form characterizations of all estimators related optimizing quantities of interest.
  arXiv  Detail & Related papers  (2024-06-13T14:56:52Z)
• Near-Optimal Resilient Aggregation Rules for Distributed Learning Using 1-Center and 1-Mean Clustering with Outliers [24.88026399458157]
  Byzantine machine learning has garnered considerable attention in light of the unpredictable faults that can occur. The key to secure machines in distributed learning is resilient aggregation mechanisms.
  arXiv  Detail & Related papers  (2023-12-20T08:36:55Z)
• Capsa: A Unified Framework for Quantifying Risk in Deep Neural Networks [142.67349734180445]
  Existing algorithms that provide risk-awareness to deep neural networks are complex and ad-hoc. Here we present capsa, a framework for extending models with risk-awareness.
  arXiv  Detail & Related papers  (2023-08-01T02:07:47Z)
• Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity [7.57543767554282]
  This paper introduces a new formulation for risk-sensitive MDPs, which assesses risk in a slightly different manner compared to the classical Markov risk measure. We derive the policy gradient theorem for both problems, proving gradient domination and global convergence of the exact policy gradient method. We also propose a sample-based offline learning algorithm, namely the robust fitted-Z iteration (RFZI)
  arXiv  Detail & Related papers  (2023-06-20T15:51:25Z)
• Regret Bounds for Risk-sensitive Reinforcement Learning with Lipschitz Dynamic Risk Measures [23.46659319363579]
  We present two model-based algorithms applied to emphLipschitz dynamic risk measures. Notably, our upper bounds demonstrate optimal dependencies on the number of actions and episodes.
  arXiv  Detail & Related papers  (2023-06-04T16:24:19Z)
• On (assessing) the fairness of risk score models [2.0646127669654826]
  Risk models are of interest for a number of reasons, including the fact that they communicate uncertainty about the potential outcomes to users. We identify the provision of similar value to different groups as a key desideratum for risk score fairness. We introduce a novel calibration error metric that is less sample size-biased than previously proposed metrics.
  arXiv  Detail & Related papers  (2023-02-17T12:45:51Z)
• Parametric Classification for Generalized Category Discovery: A Baseline Study [70.73212959385387]
  Generalized Category Discovery (GCD) aims to discover novel categories in unlabelled datasets using knowledge learned from labelled samples. We investigate the failure of parametric classifiers, verify the effectiveness of previous design choices when high-quality supervision is available, and identify unreliable pseudo-labels as a key problem. We propose a simple yet effective parametric classification method that benefits from entropy regularisation, achieves state-of-the-art performance on multiple GCD benchmarks and shows strong robustness to unknown class numbers.
  arXiv  Detail & Related papers  (2022-11-21T18:47:11Z)
• Mitigating multiple descents: A model-agnostic framework for risk monotonization [84.6382406922369]
  We develop a general framework for risk monotonization based on cross-validation. We propose two data-driven methodologies, namely zero- and one-step, that are akin to bagging and boosting.
  arXiv  Detail & Related papers  (2022-05-25T17:41:40Z)
• A Survey of Risk-Aware Multi-Armed Bandits [84.67376599822569]
  We review various risk measures of interest, and comment on their properties. We consider algorithms for the regret minimization setting, where the exploration-exploitation trade-off manifests. We conclude by commenting on persisting challenges and fertile areas for future research.
  arXiv  Detail & Related papers  (2022-05-12T02:20:34Z)
• Learning Hidden Markov Models When the Locations of Missing Observations are Unknown [54.40592050737724]
  We consider the general problem of learning an HMM from data with unknown missing observation locations. We provide reconstruction algorithms that do not require any assumptions about the structure of the underlying chain. We show that under proper specifications one can reconstruct the process dynamics as well as if the missing observations positions were known.
  arXiv  Detail & Related papers  (2022-03-12T22:40:43Z)
• Self-Certifying Classification by Linearized Deep Assignment [65.0100925582087]
  We propose a novel class of deep predictors for classifying metric data on graphs within PAC-Bayes risk certification paradigm. Building on the recent PAC-Bayes literature and data-dependent priors, this approach enables learning posterior distributions on the hypothesis space.
  arXiv  Detail & Related papers  (2022-01-26T19:59:14Z)
• Detecting and Mitigating Test-time Failure Risks via Model-agnostic Uncertainty Learning [30.86992077157326]
  This paper introduces Risk Advisor, a novel post-hoc meta-learner for estimating failure risks and predictive uncertainties of any already-trained black-box classification model. In addition to providing a risk score, the Risk Advisor decomposes the uncertainty estimates into aleatoric and epistemic uncertainty components. Experiments on various families of black-box classification models and on real-world and synthetic datasets show that the Risk Advisor reliably predicts deployment-time failure risks.
  arXiv  Detail & Related papers  (2021-09-09T17:23:31Z)
• Correlation Clustering Reconstruction in Semi-Adversarial Models [70.11015369368272]
  Correlation Clustering is an important clustering problem with many applications. We study the reconstruction version of this problem in which one is seeking to reconstruct a latent clustering corrupted by random noise and adversarial modifications.
  arXiv  Detail & Related papers  (2021-08-10T14:46:17Z)
• Risk-Constrained Thompson Sampling for CVaR Bandits [82.47796318548306]
  We consider a popular risk measure in quantitative finance known as the Conditional Value at Risk (CVaR) We explore the performance of a Thompson Sampling-based algorithm CVaR-TS under this risk measure.
  arXiv  Detail & Related papers  (2020-11-16T15:53:22Z)
• A generalized Bayes framework for probabilistic clustering [3.3194866396158]
  Loss-based clustering methods, such as k-means and its variants, are standard tools for finding groups in data. Model-based clustering based on mixture models provides an alternative, but such methods face computational problems and large sensitivity to the choice of kernel. This article proposes a generalized Bayes framework that bridges between these two paradigms through the use of Gibbs posteriors.
  arXiv  Detail & Related papers  (2020-06-09T18:49:32Z)
• Provable tradeoffs in adversarially robust classification [96.48180210364893]
  We develop and leverage new tools, including recent breakthroughs from probability theory on robust isoperimetry. Our results reveal fundamental tradeoffs between standard and robust accuracy that grow when data is imbalanced.
  arXiv  Detail & Related papers  (2020-06-09T09:58:19Z)
• Open-Set Recognition with Gaussian Mixture Variational Autoencoders [91.3247063132127]
  In inference, open-set classification is to either classify a sample into a known class from training or reject it as an unknown class. We train our model to cooperatively learn reconstruction and perform class-based clustering in the latent space. Our model achieves more accurate and robust open-set classification results, with an average F1 improvement of 29.5%.
  arXiv  Detail & Related papers  (2020-06-03T01:15:19Z)
• Robust M-Estimation Based Bayesian Cluster Enumeration for Real Elliptically Symmetric Distributions [5.137336092866906]
  Robustly determining optimal number of clusters in a data set is an essential factor in a wide range of applications. This article generalizes so that it can be used with any arbitrary Really Symmetric (RES) distributed mixture model. We derive a robust criterion for data sets with finite sample size, and also provide an approximation to reduce the computational cost at large sample sizes.
  arXiv  Detail & Related papers  (2020-05-04T11:44:49Z)
• Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
  We develop Thompson Sampling-style algorithms for mean-variance MAB. We also provide comprehensive regret analyses for Gaussian and Bernoulli bandits. Our algorithms significantly outperform existing LCB-based algorithms for all risk tolerances.
  arXiv  Detail & Related papers  (2020-02-01T15:33:50Z)

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.