The EM Perspective of Directional Mean Shift Algorithm

• URL: http://arxiv.org/abs/2101.10058v1
• Date: Mon, 25 Jan 2021 13:17:12 GMT
• Title: The EM Perspective of Directional Mean Shift Algorithm
• Authors: Yikun Zhang, Yen-Chi Chen
• Abstract summary: The directional mean shift (DMS) algorithm is a nonparametric method for pursuing local modes of densities defined by kernel density estimators on the unit hypersphere. We show that any DMS can be viewed as a generalized Expectation-Maximization (EM) algorithm.
• Score: 3.60425753550939
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The directional mean shift (DMS) algorithm is a nonparametric method for pursuing local modes of densities defined by kernel density estimators on the unit hypersphere. In this paper, we show that any DMS iteration can be viewed as a generalized Expectation-Maximization (EM) algorithm; in particular, when the von Mises kernel is applied, it becomes an exact EM algorithm. Under the (generalized) EM framework, we provide a new proof for the ascending property of density estimates and demonstrate the global convergence of directional mean shift sequences. Finally, we give a new insight into the linear convergence of the DMS algorithm.

Related papers

• Weighted quantization using MMD: From mean field to mean shift via gradient flows [5.216151302783165]
  Approximating a probability distribution using a set of particles is a fundamental problem in machine learning and statistics. We show that MSIP extends the (non-interacting) mean shift algorithm, widely used for identifying modes in kernel density estimates. We also show that MSIP can be interpreted as preconditioned gradient descent, and that it acts as a relaxation of Lloyd's algorithm for clustering.
  arXiv  Detail & Related papers  (2025-02-14T23:13:20Z)
• A Bias-Correction Decentralized Stochastic Gradient Algorithm with Momentum Acceleration [19.83835152405735]
  We propose a momentum-celerated distributed gradient, termed Exact-Diffusion with Momentum (EDM) EDM mitigates the bias from data heterogeneity and incorporates momentum techniques commonly used in deep learning. Our theoretical analysis demonstrates that the EDM algorithm converges sublinearly to the neighborhood optimal solution.
  arXiv  Detail & Related papers  (2025-01-31T12:15:58Z)
• Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm [80.94861441583275]
  We investigate the complexity of the generalization bound of the decentralized gradient descent (D-SGDA) algorithm. Our results analyze the impact of different top factors on the generalization of D-SGDA. We also balance it with the generalization to obtain the optimal convex-concave setting.
  arXiv  Detail & Related papers  (2023-10-31T11:27:01Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• Low-Discrepancy Points via Energetic Variational Inference [5.936959130012709]
  We propose a deterministic variational inference approach and generate low-discrepancy points by minimizing the kernel discrepancy. We name the resulting algorithm EVI-MMD and demonstrate it through examples in which the target distribution is fully specified. Its performances are satisfactory compared to alternative methods in the applications of distribution approximation, numerical integration, and generative learning.
  arXiv  Detail & Related papers  (2021-11-21T03:09:07Z)
• Improving Metric Dimensionality Reduction with Distributed Topology [68.8204255655161]
  DIPOLE is a dimensionality-reduction post-processing step that corrects an initial embedding by minimizing a loss functional with both a local, metric term and a global, topological term. We observe that DIPOLE outperforms popular methods like UMAP, t-SNE, and Isomap on a number of popular datasets.
  arXiv  Detail & Related papers  (2021-06-14T17:19:44Z)
• Linear Convergence of the Subspace Constrained Mean Shift Algorithm: From Euclidean to Directional Data [3.60425753550939]
  We argue that the SCMS algorithm is a special variant of a subspace constrained gradient ascent algorithm with an adaptive step size. We prove the linear convergence of our proposed directional SCMS algorithm.
  arXiv  Detail & Related papers  (2021-04-29T01:46:35Z)
• Space Partitioning and Regression Mode Seeking via a Mean-Shift-Inspired Algorithm [5.990174495635326]
  Mean shift (MS) algorithm is a nonparametric method used to cluster sample points and find the local modes of kernel density estimates. We develop an algorithm to estimate the modes of regression functions and partition the sample points in the input space.
  arXiv  Detail & Related papers  (2021-04-20T16:35:17Z)
• Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
  Hybrid Monte Carlo is a powerful Markov Chain Monte Carlo method for sampling from complex continuous distributions. We introduce a new approach based on augmenting Monte Carlo methods with SurVAE Flows to sample from discrete distributions. We demonstrate the efficacy of our algorithm on a range of examples from statistics, computational physics and machine learning, and observe improvements compared to alternative algorithms.
  arXiv  Detail & Related papers  (2021-02-04T02:21:08Z)
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm [59.99439951055238]
  We show how (discrete-time) Lyapunov stability theory can serve as a powerful tool to aid, or even lead, in the analysis (and potential design) of optimization algorithms that are not necessarily gradient-based. The particular ML problem that this paper focuses on is that of parameter estimation in an incomplete-data Bayesian framework via the popular optimization algorithm known as maximum a posteriori expectation-maximization (MAP-EM) We show that fast convergence (linear or quadratic) is achieved, which could have been difficult to unveil without our adopted S&C approach.
  arXiv  Detail & Related papers  (2020-06-23T01:34:18Z)

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.