2004 · 60 citations · 10 references
ComputingComputer ScienceMathematicsAlgorithmsMachine LearningOptimizationApproximation AlgorithmsCombinatorial OptimizationDynamic ProgrammingGraph-based LearningOptimization For Machine LearningConditional IndependenceConditional Independence ModelsGraphical Model LearningGraphical ModelsKullback-leibler DivergencePolynomial-time AlgorithmsSubmodular MaximizationSubmodular Optimization
We show that the class of strongly connected graphical models with treewidth at most k can be properly efficiently PAC-learnt with respect to the Kullback-Leibler Divergence. Previous approaches to this problem, such as those of Chow ([1]), and Hoffgen ([7]) have shown that this class is PAClearnable by reducing it to a combinatorial optimization problem. However, for k> 1, this problem is NPcomplete ([15]), and so unless P=NP, these approaches will take exponential amounts of time. Our approach differs
10
Minimizing symmetric submodular functions
Maurice Queyranne · Mathematical Programming · 1998 · 177 citations