Dynamic Clustering Algorithms via Small-Variance Analysis of Markov Chain Mixture Models
© 1979-2012 IEEE. Bayesian nonparametrics are a class of probabilistic models in which the model size is inferred from data. A recently developed methodology in this field is small-variance asymptotic analysis, a mathematical technique for deriving learning algorithms that capture much of the flexib...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/134985 |
| _version_ | 1826217020458270720 |
|---|---|
| author | Campbell, Trevor Kulis, Brian How, Jonathan |
| author_facet | Campbell, Trevor Kulis, Brian How, Jonathan |
| author_sort | Campbell, Trevor |
| collection | MIT |
| description | © 1979-2012 IEEE. Bayesian nonparametrics are a class of probabilistic models in which the model size is inferred from data. A recently developed methodology in this field is small-variance asymptotic analysis, a mathematical technique for deriving learning algorithms that capture much of the flexibility of Bayesian nonparametric inference algorithms, but are simpler to implement and less computationally expensive. Past work on small-variance analysis of Bayesian nonparametric inference algorithms has exclusively considered batch models trained on a single, static dataset, which are incapable of capturing time evolution in the latent structure of the data. This work presents a small-variance analysis of the maximum a posteriori filtering problem for a temporally varying mixture model with a Markov dependence structure, which captures temporally evolving clusters within a dataset. Two clustering algorithms result from the analysis: D-Means, an iterative clustering algorithm for linearly separable, spherical clusters; and SD-Means, a spectral clustering algorithm derived from a kernelized, relaxed version of the clustering problem. Empirical results from experiments demonstrate the advantages of using D-Means and SD-Means over contemporary clustering algorithms, in terms of both computational cost and clustering accuracy. |
| first_indexed | 2024-09-23T16:56:47Z |
| format | Article |
| id | mit-1721.1/134985 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T16:56:47Z |
| publishDate | 2021 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1349852022-03-29T20:51:31Z Dynamic Clustering Algorithms via Small-Variance Analysis of Markov Chain Mixture Models Campbell, Trevor Kulis, Brian How, Jonathan © 1979-2012 IEEE. Bayesian nonparametrics are a class of probabilistic models in which the model size is inferred from data. A recently developed methodology in this field is small-variance asymptotic analysis, a mathematical technique for deriving learning algorithms that capture much of the flexibility of Bayesian nonparametric inference algorithms, but are simpler to implement and less computationally expensive. Past work on small-variance analysis of Bayesian nonparametric inference algorithms has exclusively considered batch models trained on a single, static dataset, which are incapable of capturing time evolution in the latent structure of the data. This work presents a small-variance analysis of the maximum a posteriori filtering problem for a temporally varying mixture model with a Markov dependence structure, which captures temporally evolving clusters within a dataset. Two clustering algorithms result from the analysis: D-Means, an iterative clustering algorithm for linearly separable, spherical clusters; and SD-Means, a spectral clustering algorithm derived from a kernelized, relaxed version of the clustering problem. Empirical results from experiments demonstrate the advantages of using D-Means and SD-Means over contemporary clustering algorithms, in terms of both computational cost and clustering accuracy. 2021-10-27T20:10:11Z 2021-10-27T20:10:11Z 2019 2019-10-28T17:07:36Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/134985 en 10.1109/TPAMI.2018.2833467 IEEE Transactions on Pattern Analysis and Machine Intelligence Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Campbell, Trevor Kulis, Brian How, Jonathan Dynamic Clustering Algorithms via Small-Variance Analysis of Markov Chain Mixture Models |
| title | Dynamic Clustering Algorithms via Small-Variance Analysis of Markov Chain Mixture Models |
| title_full | Dynamic Clustering Algorithms via Small-Variance Analysis of Markov Chain Mixture Models |
| title_fullStr | Dynamic Clustering Algorithms via Small-Variance Analysis of Markov Chain Mixture Models |
| title_full_unstemmed | Dynamic Clustering Algorithms via Small-Variance Analysis of Markov Chain Mixture Models |
| title_short | Dynamic Clustering Algorithms via Small-Variance Analysis of Markov Chain Mixture Models |
| title_sort | dynamic clustering algorithms via small variance analysis of markov chain mixture models |
| url | https://hdl.handle.net/1721.1/134985 |
| work_keys_str_mv | AT campbelltrevor dynamicclusteringalgorithmsviasmallvarianceanalysisofmarkovchainmixturemodels AT kulisbrian dynamicclusteringalgorithmsviasmallvarianceanalysisofmarkovchainmixturemodels AT howjonathan dynamicclusteringalgorithmsviasmallvarianceanalysisofmarkovchainmixturemodels |