AlgorithmicAnalysis of Statistical Mechanical Heuristics

我们调查了在统计物理学和相关领域提出和研究的各种启发式方法。我们的研究结果分为以下三个主题。局部搜索算法的平均情况分析：对于可满足性问题，有许多局部搜索启发式算法，主要是通过计算机实验证明它们能够有效地解决给定问题。我们提出了一种尽可能严格地调查这种启发式的方法。该方法的一个关键方法是“伪期望”，这是一种分析相对简单（但具有大状态空间）马尔可夫过程的平均状态的方法。高效学习算法的设计方法：boost方法是设计学习算法的重要方法之一。我们研究了助推的算法方面。我们提出了“MadaBoost”，这是一种简单的增强算法，对带有噪声和异常值的数据表现出更好的性能。我们还提出了一种自适应采样方法作为增强的实现技术。关于这些方法及其统计调查已总结成一本书（日文），将于2006年出版。消息传递算法的设计和分析信念传播作为解决复杂组合问题的一种有前途的方法，已经在人工智能和统计物理中进行了研究。基于信念传播，我们为众所周知的NP-hard优化问题Graph bissection问题和Max-2SAT问题导出了类似的消息传递型算法。我们还证明了它们在一定的平均情况模型下以高概率解决了这些问题。

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.