AlgorithmicAnalysis of Statistical Mechanical Heuristics

统计机械启发法的算法分析

• 批准号: 14084207
• 负责人: WATANABE Osamu
• 金额: $ 16.06万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 2005
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-14084207/
• 关键词: Average-Case Analysis of Algorithms; Satisfiability Problem; Local Search Algorithms; Pseudo Expectation; Boosting; 確率アルゴリズム; 乱択計算; 局所探索法; マルコフ過程; 近似解析; サンプリング技法; 片誤り性; 確立アルゴリズム; ランダマイズド計算; 制約解探索問題; アルゴリズムの状態確率の変化

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.

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

项目成果

O.Watanabe, T.Sawai, H.Takayashi: "Analysis of a randomized local search algorithm for LDPCC decoding problem"Proc.2nd Int'l Sympos.on Stochastic Algorithms, LNCS. 2827. 50-60 (2003)

O.Watanabe、T.Sawai、H.Takayashi：“LDPCC 解码问题的随机局部搜索算法分析”Proc.2nd Intl Sympos.on Stochastic Algorithms，LNCS。

J.Cai, O.Watanabe: "Stringent relativization"Proc.23rd FSTTCS Conference, LNCS. 2914. 408-419 (2003)

J.Cai、O.Watanabe：“严格相对化”Proc.23rd FSTTCS 会议，LNCS。

Iwama, K., Morizumi, H.: "An Explicit Lower Bound of $5n-o(n)$ for Boolean Circuits"Proc.MFCS2002. 353-364 (2002)

Iwama, K., Morizumi, H.：“布尔电路的显式下界 $5n-o(n)$”Proc.MFCS2002。

On proving circuit lower bounds against the polynomial-time hierarch

关于针对多项式时间层次结构证明电路下界

• 发表时间: 2004
• 期刊: SIAM J.Computing 33・4
• 作者: J.Y.Cai;O.Watanabe
• 通讯作者: O.Watanabe

Average-case analysis for the MAX-2SAT problem

MAX-2SAT 问题的平均情况分析

• 发表时间: 2010
• 期刊: Theoretical Computer Science 411
• 作者: O. Watanabe;M. Yamamoto
• 通讯作者: M. Yamamoto