AlgorithmicAnalysis of Statistical Mechanical Heuristics

点击翻译按钮获取中文摘要

We investigate various heuristics that have been proposed and studied in statistical physics and related areas. Our results are classified into the following three topics.1. Average-case analysis of local search algorithms:There are many local search heuristics for satisfiability problems, which have been shown to solve given problems efficiently by, mainly, computer experiments. We proposed an approach for investigating such heuristics as rigorously as possible. One key method of this approach is "pseudo expectation", a way to analyze the average state of relatively simple (but with a large state space) Markov processes.2. Design method for efficient learning algorithms:Boosting method has been studied as one of the important approach for designing learning algorithms. We studied the algorithmic aspects of boosting. We proposed "MadaBoost", a simple boosting algorithm that shows better performance for data with noise and outliers. We also proposed an adaptive sampling method as an implementations technique of boosting. On these methods and their statistical investigations have been summarized as a book (in Japanese), which will appear in 2006.3. Design and analysis of message passing algorithmsBelief propagations have been studied in AI and statistical physics as a promising approach for solving hard combinatorial problems. Based on belief propagation, we derived similar message passing type algorithms for Graph Bisection problem and Max-2SAT problem, well-know NP-hard optimization problems. We also proved that they solve these problems with high probability under certain average-case models.