Model-based clustering using non-parametric Hidden Markov Models

• URL: http://arxiv.org/abs/2309.12238v2
• Date: Mon, 25 Sep 2023 13:12:43 GMT
• Title: Model-based clustering using non-parametric Hidden Markov Models
• Authors: Elisabeth Gassiat, Ibrahim Kaddouri, Zacharie Naulet
• Abstract summary: We study the Bayes risk of clustering when using HMMs and to propose associated clustering procedures. Results are shown to remain valid in the online setting where observations are clustered sequentially.
• Score: 5.314335654467143
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Thanks to their dependency structure, non-parametric Hidden Markov Models (HMMs) are able to handle model-based clustering without specifying group distributions. The aim of this work is to study the Bayes risk of clustering when using HMMs and to propose associated clustering procedures. We first give a result linking the Bayes risk of classification and the Bayes risk of clustering, which we use to identify the key quantity determining the difficulty of the clustering task. We also give a proof of this result in the i.i.d. framework, which might be of independent interest. Then we study the excess risk of the plugin classifier. All these results are shown to remain valid in the online setting where observations are clustered sequentially. Simulations 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.