New Monte Carlo Methods for Scientific and Statistical Computing

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