A quasi-Bayesian perspective to online clustering

DOI10.1214/18-EJS1479MaRDI QIDQ1786586zbMATH OpenOpenAlexWikidataFDO

Authors Le Li, Benjamin Guedj, Sébastien Loustau

Publication date 24 September 2018

Published in Electronic Journal of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.00522, https://projecteuclid.org/euclid.ejs/1537430425

zbMATH Keywords

reversible jump Markov chain Monte Carloonline clusteringRJMCMCBayesian on-line clusteringminimax regret boundsPACBOprobability approximately correctquasi-Bayesian learning

Mathematics Subject Classification ID

Bayesian inference (62F15) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Monte Carlo methods (65C05) Learning and adaptive systems in artificial intelligence (68T05) Minimax procedures in statistical decision theory (62C20)

Abstract: When faced with high frequency streams of data, clustering raises theoretical and algorithmic pitfalls. We introduce a new and adaptive online clustering algorithm relying on a quasi-Bayesian approach, with a dynamic (i.e., time-dependent) estimation of the (unknown and changing) number of clusters. We prove that our approach is supported by minimax regret bounds. We also provide an RJMCMC-flavored implementation (called PACBO, see https://cran.r-project.org/web/packages/PACBO/index.html) for which we give a convergence guarantee. Finally, numerical experiments illustrate the potential of our procedure.

Recommendations

• Weak convergence and optimal tuning of the reversible jump algorithm
• A fast and recursive algorithm for clustering large datasets with \(k\)-medians
• Reversible jump MCMC
• R package rjmcmc: reversible jump MCMC using post‐processing
• Model-based clustering of high-dimensional data streams with online mixture of probabilistic PCA
• Efficient Construction of Reversible Jump Markov Chain Monte Carlo Proposal Distributions
• An adaptive sequential Monte Carlo sampler
• A data-driven selection of the number of clusters in the Dirichlet allocation model via Bayesian mixture modelling
• Bayesian inference for continuous-time hidden Markov models with an unknown number of states

Cites work

• scientific article; zbMATH DE number 5544465 (Why is no real title available?)
• scientific article; zbMATH DE number 3579840 (Why is no real title available?)
• scientific article; zbMATH DE number 1348600 (Why is no real title available?)
• scientific article; zbMATH DE number 2117879 (Why is no real title available?)
• scientific article; zbMATH DE number 3429948 (Why is no real title available?)
• scientific article; zbMATH DE number 3215519 (Why is no real title available?)
• A Criterion for Determining the Number of Groups in a Data Set Using Sum-of-Squares Clustering
• Aggregation by Exponential Weighting and Sharp Oracle Inequalities
• Aggregation by exponential weighting, sharp PAC-Bayesian bounds and sparsity
• An MCMC model search algorithm for regression problems
• An algorithm for online \(k\)-means clustering
• An oracle inequality for quasi-Bayesian nonnegative matrix factorization
• Analysis of two gradient-based algorithms for on-line regression
• Competitive On-line Statistics
• Estimating the number of clusters in a data set via the gap statistic
• Exponentiated gradient versus gradient descent for linear predictors
• Fast learning rates in statistical inference through aggregation
• Finding Groups in Data
• Harris recurrence of Metropolis-within-Gibbs and trans-dimensional Markov chains
• How to use expert advice
• I-divergence geometry of probability distributions and minimization problems
• Learning Theory
• Mirror averaging with sparsity priors
• Multivariate T-Distributions and Their Applications
• On Bayesian model and variable selection using MCMC
• On the number of groups in clustering
• Optimal learning with Bernstein online aggregation
• PAC-Bayesian Generalisation Error Bounds for Gaussian Process Classification
• PAC-Bayesian bounds for sparse regression estimation with exponential weights
• PAC-Bayesian estimation and prediction in sparse additive models
• PAC-Bayesian high dimensional bipartite ranking
• Prediction, Learning, and Games
• Relative loss bounds for on-line density estimation with the exponential family of distributions
• Reversible jump Markov chain Monte Carlo computation and Bayesian model determination
• Slope heuristics: overview and implementation
• Some PAC-Bayesian theorems
• Sparse regression learning by aggregation and Langevin Monte-Carlo
• Sparse single-index model
• Statistical learning theory and stochastic optimization. Ecole d'Eté de Probabilitiés de Saint-Flour XXXI -- 2001.
• The minimax distortion redundancy in empirical quantizer design
• The weighted majority algorithm

Cited in

(4)

• PACBO
• Strategies for online inference of model-based clustering in large and growing networks
• SAKM: self-adaptive kernel machine. A kernel-based algorithm for online clustering
• Online model-based clustering for crisis identification in distributed computing

Describes a project that uses

Uses Software

• R
• CAPUSHE
• bridgesampling
• rjmcmc
• clusfind

This page was built for publication: A quasi-Bayesian perspective to online clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1786586)