New Monte Carlo Methods for Scientific and Statistical Computing

-----------------------------------------------------------------------计划号：DMS 9803649 PI：军S刘研究所：斯坦福大学项目：科学和统计计算的新蒙特卡罗方法摘要：蒙特卡罗方法越来越被科学家们认为是解决复杂计算问题不可或缺的工具。它的应用包括生物化学、计算生物学、计算机科学、工程学、金融学、物理学、地震学、传统统计学等。本研究的主要目的是设计和分析新的马尔可夫链蒙特卡罗(MCMC)方法。研究计划包括三个相关项目，都集中在MCMC方法论上。第一个项目提出了两种新的混合蒙特卡罗方法。这些方法将梯度型移动或共轭方向型移动与Metropolis算法相结合。这些新方法旨在缓解离散朗之万扩散和分子动力学中观察到的慢混合行为(或“粘性”)，可用于模拟图像、预测蛋白质结构、神经网络训练等连续优化问题。第二个项目致力于推广物理学家在格子场论计算中使用的多重网格蒙特卡罗(MGMC)方法。我们的初步工作揭示了MGMC与统计文献中的再参数化方法之间的密切联系。本项目中提出的广义MGMC统一了这些看似不同的方法，并为寻找更有效的MCMC方案提供了一种通用的方法。目前，它在随机效果模型和概率模型中的应用正在研究中，并将探索它在贝叶斯图像分析中的应用，如模式合成和图像平滑。建议的第三部分是对Wong和Leung(1997)最近提出的动态加权法的理论分析。结果表明，该方法在旅行商问题、电路划分问题、神经网络训练和贝叶斯模型选择等各种优化问题中具有巨大的潜力。提出了动态加权的几种变化形式，并提出了一种泛函分析方法来研究DW的收敛性质和加权行为。人们早就认识到，许多复杂的系统，如原子弹中的反应、流体动力学、分子运动等，都可以通过计算机模拟来研究。这类方法中最流行的方法之一是蒙特卡罗技术，它模拟用概率分布描述的复杂系统。这项技术是以著名的赌博胜地命名的，因为它的程序包含了机会的元素。近二十年来，人们逐渐意识到蒙特卡罗技术也适用于更广泛的问题，包括全局优化、统计推断、信号处理、目标跟踪、人工智能、金融建模、计算生物学、数据挖掘等。PI已成功地将蒙特卡罗技术与适当的统计模型一起应用于了解远程相关DNA或蛋白质序列之间的关系；动态系统更新(如目标跟踪)；神经网络训练；以及贝叶斯统计推断。这个项目的目标是开发更有效的蒙特卡罗方法来处理具有挑战性的计算问题，例如根据蛋白质分子的初级序列预测蛋白质分子的三维结构。所有用于模拟复杂系统的蒙特卡罗方法的一个共同特点是，它们依赖于微小的、尽管是随机的局部变化的累积演化。这通常会导致非常慢的收敛算法。例如，由于S的这种局部运动，用现有的方法，人们需要数年的超级计算机时间来模拟蛋白质分子十分之一秒的运动。PI概述了在蒙特卡罗方法中进行全局移动的一般方法；建议结合优化文献中的思想(即，梯度和共轭方向法)来加速蒙特卡罗模拟；并为从理论上理解几种新的和有前途的蒙特卡罗方法提出了途径。这项研究的成功将有利于科学家和工程师应对他们的计算挑战。

----------------------------------------------------------------------- Proposal Number: DMS 9803649 PI: Jun S Liu Institution: Stanford University Project: New Monte Carlo Methods for Scientific and Statistical Computing Abstract: Monte Carlo methods have increasingly been recognized by scientists as indispensable tools for difficult computational problems. Its applications include biochemistry, computational biology, computer science, engineering, finance, physics, seismology, traditional statistics, etc. The primary objective of this research, as motivated by various applications encountered by the PI, is on designing and analyzing new Markov chain Monte Carlo (MCMC) methods. The research plan includes three related projects, all concentrating on the MCMC methodology. The first project proposes two new hybrid Monte Carlo methods. These methods combine a gradient-type move, or a conjugate direction-type move, with Metropolis algorithm. The new methods aim at alleviating slow-mixing behavior (or ``stickiness'') observed in discretized Langevin diffusion and molecular dynamics, and can be applied to simulating images, predicting protein structures, neural network training and other continuous-optimization problems. The second project focuses on generalizing the multigrid Monte Carlo (MGMC) method used by physicists in computations of lattice field theories. Our preliminary work reveals a close connection between the MGMC and the reparameterization method in statistics literature. The generalized MGMC proposed in this project unifies these seemingly different methods and provide a generic approach to the search of more efficient MCMC schemes. Its use in random effects model and probit model is currently under investigation and its applications in Bayesian image analysis, such as pattern synthesis and image smoothing, will be explored. The third part of the proposal is concerned with theoretical analyses of the dynamic weighting method recently proposed by Wong and Liang (1997). As shown by the authors, the method has tremendous potential in various optimization problems, such as the traveling salesman problem, circuit partitioning problem, neural network training, and Bayesian model selection. A few variations of the dynamic weighting are suggested and a functional analysis method is outlined for studying convergence properties and weight behavior of the DW. It has long been recognized that many complicated systems, such as reactions in atomic bombs, fluid dynamics, molecular movements, etc., can be studied via computer simulation. One of the most popular approach of this sort, the Monte Carlo technique, simulates a complex system described by probability distributions. The technique was named after the famed gambling resort because its procedures incorporate the element of chance. In the recent two decades, people come to realize that Monte Carlo techniques is also applicable to a much wider class of problems including global optimizations, statistical inferences, signal processing, target tracking, artificial intelligence, financial modeling, computational biology, data mining, and many others. The PI has successfully applied Monte Carlo techniques, together with suitable statistical models, to the understanding of relationship between remotely related DNA or protein sequences; to dynamic system updating (such as target tracking); to neural network training; and to Bayesian statistical inference. This project targets at developing more efficient Monte Carlo methods for dealing with challenging computational problems, such as prediction of the 3-D structure of a protein molecule from its primary sequence. A common feature of all Monte Carlo methods for simulating complex systems is that they rely on cumulative evolutions of small, albeit random, local changes. This often leads to a very slow-converging algorithm. For example, because of s uch local moves, with currently available methods one needs years of super-computer time in order to simulate one tenth of a second of movement of a protein molecule. The PI outlines a general method to conduct global moves in Monte Carlo methods; proposes to incorporate ideas in optimization literature (i.e., gradient and conjugate direction methods) to speed up Monte Carlo simulations; and suggests avenues for the theoretical understanding of several new and promising Monte Carlo methods. Success of this research will benefit scientists and engineers in coping with their computational challenges.