Maximum Likelihood Estimation and Other Probabilistic Algorithms

CCR-9820885 Kannan，S.本项目从事多个领域的研究，共同的主题是概率算法的设计和分析。极大似然估计是统计学中一种经典而重要的技术。这个一般问题的具体版本是通过考虑生成样本数据的特定随机过程来定义的。对于大多数有趣的应用，这个问题通常被认为在计算上很难处理。然而，这个项目寻求创建非常高效的算法，找到大致最可能的解决方案。具体地说，这样的算法被用于计算生物学中的重要问题，如系统发生图构建和多重比对。该项目还研究了推理信任网问题的类似方法，这是人工智能中一种流行的随机模型。争用问题涉及消息在以太网上的传输，其中消息按照泊松过程等随机过程到达。每条消息都使用一种协议，它试图在每个时刻以一定的概率发送自己。一个中心的悬而未决的问题是，是否有一种协议可以确保系统是“稳定的”。PI证明了对于许多“自然”类别的协议，答案是“不”，并且正在致力于将这些证明扩展到所有基于确认的协议。最后，该项目调查了程序检查领域的新模型和问题，这再次涉及随机算法的设计。

CCR-9820885Kannan, S.This project pursues research in a number of areas with the common theme being the design and analysis of probabilistic algorithms.Maximum Likelihood Estimation is a classical and important technique in statistics. Specific versions of this general problem are defined by considering specific stochastic processes that generate the sample data. This problem has generally been thought to be computationally intractable for most interesting applications. However, this project seeks to create very efficient algorithms that find approximately the most likely solutions. Specifically such algorithms are sought for important problems in computational biology such as phylogeny construction and multiple alignment. The project also investigates similar approaches for the problem of inferring Belief Nets, a popular stochastic model in artificial intelligence.The problem of contention is concerned with message transmission over an ethernet where messages arrive according to a stochastic process such as a Poisson process. Each message uses a protocol whereby it attempts to transmit itself at each time instant with some probability.A central open question is whether there is a protocol that ensures that the system is "stable." The PI proved that the answer is "no" for a number of "natural" classes of protocols and is working on extending these proofs to all acknowledgement-based protocols. Finally, the project investigate new models and problems in the area of program checking which again involves the design of randomized algorithms.