The Concave-Convex Procedure (CCCP)
Published 3 January 2001
Alan Yuille, Anand Rangarajan
Citations381
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work introduces the Concave-Convex procedure (CCCP) which constructs discrete time iterative dynamical systems which are guaranteed to monotonically decrease global optimization/energy functions and proves relationships to some applications of Legendre transform techniques.
Abstract
We introduce the Concave-Convex procedure (CCCP) which constructs discrete time iterative dynamical systems which are guaranteed to monotonically decrease global optimization/energy functions.
Keywords
Computer ScienceMathematicsEngineering
Journal of the Royal Statistical Society Series B (Statistical Methodology)Maximum Likelihood from Incomplete Data Via the <i>EM</i> Algorithm
49,657 Citations1977A. P. Dempster, N. M. Laird +1 more
Computers in PhysicsSavitzky-Golay Smoothing Filters
11,624 Citations1990William H. Press, Saul A. Teukolsky
Machine LearningAn Introduction to Variational Methods for Graphical Models
3,775 Citations1999Michael I. Jordan, Zoubin Ghahramani +2 more
This paper presents a tutorial introduction to the use of variational methods for inference and learning in graphical models (Bayesian networks and Markov random fields), and describes a general framework for generating variational transformations based on convex duality.
USSR Computational Mathematics and Mathematical PhysicsThe relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming
2,659 Citations1967L.M. Bregman
This method can be regarded as a generalization of the methods discussed in [1–4] and applied to the approximate solution of problems in linear and convex programming.
Neural ComputationHierarchical Mixtures of Experts and the EM Algorithm
2,639 Citations1994Michael I. Jordan, Robert A. Jacobs
A View of the Em Algorithm that Justifies Incremental, Sparse, and other Variants
2,187 Citations1998Radford M. Neal, Geoffrey E. Hinton
An incremental variant of the EM algorithm in which the distribution for only one of the unobserved variables is recalculated in each E step is shown empirically to give faster convergence in a mixture estimation problem.
The Annals of Mathematical StatisticsGeneralized Iterative Scaling for Log-Linear Models
1,203 Citations1972J. N. Darroch, D. Ratcliff
IEEE Transactions on Pattern Analysis and Machine IntelligenceInducing features of random fields
1,044 Citations1997S. Della Pietra, V. Della Pietra +1 more
The random field models and techniques introduced in this paper differ from those common to much of the computer vision literature in that the underlying random fields are non-Markovian and have a large number of parameters that must be estimated.
NatureAn analogue approach to the travelling salesman problem using an elastic net method
810 Citations1987Richard Durbin, David Willshaw
This work describes how a parallel analogue algorithm, derived from a formal model for the establishment of topographically ordered projections in the brain, can be applied to the travelling salesman problem, and produces shorter tour lengths than another recent parallel analogue algorithms.
Journal of Computational and Graphical StatisticsOptimization Transfer Using Surrogate Objective Functions
725 Citations2000Kenneth Lange, David R. Hunter +1 more
Because optimization transfer algorithms often exhibit the slow convergence of EM algorithms, two methods of accelerating optimization transfer are discussed and evaluated in the context of specific problems.
IEEE Transactions on Pattern Analysis and Machine IntelligencePairwise data clustering by deterministic annealing
461 Citations1997Thomas Hofmann, Joachim M. Buhmann
A deterministic annealing approach to pairwise clustering is described which shares the robustness properties of maximum entropy inference and the resulting Gibbs probability distributions are estimated by mean-field approximation.
Statistics & Probability LettersAnother interpretation of the EM algorithm for mixture distributions
250 Citations1986Richard J. Hathaway
This view of the iteration partially illuminates the relationship of EM to certain clustering techniques and explains global convergence properties of the algorithm without direct reference to an incomplete data framework.
Additive versus exponentiated gradient updates for linear prediction
226 Citations1995Jyrki Kivinen, Manfred K. Warmuth
The main methodological idea is using a distance function between weight vectors both in motivating the algorithms and as a potential function in an amortized analysis that leads to worst-case loss bounds.
Neural ComputationGeneralized Deformable Models, Statistical Physics, and Matching Problems
224 Citations1990Alan Yuille
Techniques from statistical physics are used to exploit the power of statistical techniques to put global constraints on the set of allowable states of the binary matching elements and be preferable to existing methods of imposing such constraints by adding bias terms in the energy functions.
Neural ComputationAn Analysis of the Elastic Net Approach to the Traveling Salesman Problem
191 Citations1989Richard Durbin, Richard Szeliski +1 more
The analysis presented in this paper gives a better understanding of the behavior of the elastic net, allows us to better choose the parameters for the optimization, and suggests how to extend the underlying ideas to other domains.
Bethe free energy, Kikuchi approximations, and belief propagation algorithms
164 Citations2001Jonathan S. Yedidia, William T. Freeman +1 more
It is shown that BP canonly converge to a stationarypoint of an approximatefree energy, known astheBethefreeenergy in statisticalphysics, as of its release on April 4, 2001.
Neural NetworksThe invisible hand algorithm: Solving the assignment problem with statistical physics
147 Citations1994J.J. Kosowsky, Alan Yuille
A novel method is proposed for solving the assignment problem using techniques adapted from statistical physics to derive a convex effective energy function whose unique minimum corresponds to the optimal assignment.
Physical review. A, General physicsDynamics of iterated-map neural networks
134 Citations1989C. M. Marcus, R. M. Westervelt
Neural ComputationStatistical Physics Algorithms That Converge
124 Citations1994Alan Yuille, J.J. Kosowsky
Close connections are demonstrated between mean field theory methods and other approaches, in particular, barrier function and interior point methods, for obtaining approximate solutions to optimization problems.
Expectation-Maximization as lower bound maximization
90 Citations1998Thomas P. Minka
This note derives EM from the lower bounding viewpoint Luttrell which better illustrates the convergence properties of the Expectation Maximization algorithm and its variants.
Neural ComputationA Novel Optimizing Network Architecture with Applications
84 Citations1996Anand Rangarajan, Steven Gold +1 more
A novel optimizing network architecture with applications in vision, learning, pattern recognition, and combinatorial optimization is presented and a new technique, softassign, is introduced, which is used to satisfy this constraint.
Neural NetworksAlgebraic transformations of objective functions
60 Citations1990Eric Mjolsness, Charles Garrett
This work exhibits a collection of algebraic transformations which reduce network cost and increase the set of objective functions that are neurally implementable, and applies them to simplify a number of structured neural networks.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsAnalog neural networks with local competition. I. Dynamics and stability
32 Citations1993F. R. Waugh, R. M. Westervelt
Pattern RecognitionSelf-annealing and self-annihilation: unifying deterministic annealing and relaxation labeling
30 Citations2000Anand Rangarajan
Experimental results on synthetic matching and labeling problems clearly demonstrate the three-way relationship between deterministic annealing, relaxation labeling and self-annealing.
A Convergence Proof for the Softassign Quadratic Assignment Algorithm
26 Citations1996Anand Rangarajan, Alan Yuille +2 more
A proof of convergence is provided for the most general form of the softassign quadratic assignment algorithm, which has recently emerged as an effective strategy for a variety of optimization problems in pattern recognition and combinatorial optimization.
Neural ComputationConvex Potentials and their Conjugates in Analog Mean-Field Optimization
11 Citations1995Ibrahim M. Elfadel
The saddle-point paradigm of mean-field methods in statistical physics provides a systematic procedure for finding a mapping of constrained optimization problems onto analog networks via the notion of effective energy, and it is shown that within this paradigm, to each closed bounded constraint set is associated a smooth convex potential function.