CAREER: Novel Message-Passing Algorithms for Distributed Computation in Graphical Models: Theory and Applications in Signal Processing

职业：图形模型中分布式计算的新型消息传递算法：信号处理中的理论与应用

• 批准号: 0545862
• 负责人: Martin Wainwright
• 金额: $ 40万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-03-15 至 2012-02-29
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0545862&HistoricalAwards=false
• 关键词: CAREER; Novel; Message; Passing; Algorithms

Many real-world scientific and engineering systems consist of a large number of interacting subsystems. Examples include wireless sensor networks, in which low-power devices are used to monitor and detect events over an extended spatial region; and data compression in network settings where data is stored in a distributed manner (e.g., large databases distributed over multiple computer servers). Graphical models provide a powerful set of tools for modeling, analyzing, and designing systems of this nature. These models derive their power by combining a probabilistic model (i.e., one in which there is uncertainty or stochasticity in the system operation) with graphs that capture the dependencies among the systems. This research involves developing new algorithms for applying these graphical models to large-scale systems like sensor networks and data compression.Leveraging the full power of graphical models requires efficient methods for solving a core set of challenges. In this research, the investigator characterizes the limitations of existing algorithms, and moreover develops alternative and ultimately more powerful message-passing algorithms for solving these core computational problems. The following four projects address related aspects of this high-level goal: (a) analysis of provably effective algorithms based on linear programming; (b) novel message-passing algorithms for performing near-optimal lossy data compression; (c) fundamental research on issues of stability and robustness in message-passing; and (d) new methods for automated learning of models from data. These research thrusts are closely coupled with educational initiatives, including recruitment of undergraduates into research; broad dissemination of publicly-available survey papers, tutorial slides and software for graphical models; and the fostering of interaction between Engineering and Statistics via the Designated Emphasis in Communication, Computation and Statistics at UC Berkeley.

许多现实世界的科学和工程系统由大量相互作用的子系统组成。示例包括无线传感器网络，其中使用低功率设备来监视和检测扩展空间区域上的事件；以及以分布式方式存储数据的网络环境中的数据压缩(例如，分布在多个计算机服务器上的大型数据库)。图形模型为建模、分析和设计这种性质的系统提供了一套强大的工具。这些模型通过将概率模型(即，其中系统运行中存在不确定性或随机性的模型)与捕捉系统之间的依赖关系的图相结合来获得它们的能力。这项研究涉及开发新的算法，将这些图形模型应用于传感器网络和数据压缩等大规模系统。充分利用图形模型的全部能力需要有效的方法来解决一系列核心挑战。在这项研究中，研究人员描述了现有算法的局限性，并进一步开发了替代的、最终更强大的消息传递算法来解决这些核心计算问题。以下四个项目涉及这一高级别目标的相关方面：(A)基于线性规划的被证明有效的算法的分析；(B)用于执行近乎最佳的有损数据压缩的新的消息传递算法；(C)关于消息传递中稳定性和稳健性问题的基础研究；以及(D)从数据中自动学习模型的新方法。这些研究努力与教育举措紧密结合在一起，包括招募本科生从事研究；广泛传播公开可用的调查论文、教程幻灯片和图形模型软件；通过加州大学伯克利分校指定的通信、计算和统计重点，促进工程学和统计学之间的互动。