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。有效学习算法的设计方法：已将增强方法研究为设计学习算法的重要方法之一。我们研究了增强的算法方面。我们提出了“ madaboost”，这是一种简单的增强算法，显示出具有噪音和异常值的数据的更好性能。我们还提出了一种自适应抽样方法作为增强的实现技术。关于这些方法及其统计调查已被总结为一本书（日语），该书将于2006.3出现。通过AI和统计物理学，已经研究了消息传递算法传播的消息的设计和分析是解决硬组合问题的一种有希望的方法。基于信仰的传播，我们得出了相似的消息传递类型算法，以解决图形分配问题和Max-2SAT问题，NP-HARD优化问题。我们还证明，在某些平均案例模型下，它们以很高的可能性解决了这些问题。

项目成果

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

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

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。

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

S.Aida, M.Crasmaru, K.Regan, O.Watanabe: "Games with a uniqueness property"Theory of Comput.Systems. 37. 29-47 (2004)

S.Aida、M.Crasmaru、K.Regan、O.Watanabe：“具有唯一性属性的游戏”计算系统理论。