Optimization methods & software · 2008 · 125 citations · 19 references
ComputingComputer ScienceAlgorithmsMachine LearningOptimizationConvex OptimizationGraph AlgorithmsGraph TheoryMaximum Likelihood EstimationOptimization For Machine LearningUnconstrained OptimizationClique AlgorithmsClique StructureConditional IndependenceConditional Independence ModelsGaussian Graphical ModelsGraphical ModelsIterative Maximum Likelihood AlgorithmsLog-likelihood Functions
We describe algorithms for maximum likelihood estimation of Gaussian graphical models with conditional independence constraints. This problem is also known as covariance selection, and it can be expressed as an unconstrained convex optimization problem with a closed-form solution if the underlying graph is chordal. The focus of the paper is on iterative algorithms for covariance selection with nonchordal graphs. We first derive efficient methods for evaluating the gradient and Hessian of the log-likelihood function when the underlying graph is chordal. The algorithms are formulated as simple recursions on a clique tree associated with the graph. We also show that the gradient and Hessian mappings are easily inverted when the underlying graph is chordal. We then exploit these results to obtain efficient implementations of Newton's method and the conjugate gradient method for large nonchordal graphs, by embedding the graph in a chordal graph.
19
Algorithm 457: finding all cliques of an undirected graph
Coen Bron, Joep Kerbosch · Communications of the ACM · 1973 · 2.5K citations · Full text
Parallel and distributed computation
Dimitri P. Bertsekas, John N. Tsitsiklis, Alexander N. Sennikov · 1989 · 1.2K citations