Message passing algorithms, information-theoretic thresholds and computational barriers

消息传递算法、信息论阈值和计算障碍

• 批准号: 393689644
• 负责人: Professor Dr. Amin Coja-Oghlan
• 金额: --
• 依托单位: Informatik II - Lehrstuhl Effiziente Algorithmen und Komplexitätstheorie
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/393689644?language=en
• 关键词: Message; passing; algorithms; information; theoretic

Numerous critical problems in computer science and its applications can best be characterised as inference problems. Here the objective is to learn the values of certain variables on the basis of indirect, possibly noisy observations. The group testing problem is an excellent example. The goal in group testing is to identify those individuals within a group that are infected with a disease. To this end pooled tests are conducted where each individual takes part in one or more test pools. The result of a test pool should be positive if and only if at least one of the individuals in that pool are infected. However, the test results may not be entirely accurate. In any base, on the basis of the test results the infected individuals need to be identified as best as possible.Depending on the precise setup, inference tasks such as group testing may be feasible, hard or impossible to solve. Feasible means that there exists an efficient algorithm that can reliably solve the problem on the basis of the observed data. Hard means that the data suffices to solve the task in principle, but this would require exorbitant computational resources. Finally, if the data are insufficient from an information-theoretic viewpoint, solving the inference task is impossible.The goal of this project is to investigate inference problems from the rigorous viewpoint of the theory of computing, to classify them according to their feasiblity, and to develop new inference schemes and algorithms.In the second phase of the project we will be particularly interested in the non-Bayes optimal setting. This means that the inference algorithm may not know the problem parameters precisely. For example, in the group testing problem the inference algorithm may only have a rough estimate of the infection rate and of the accuracy of the tests. A second new challenge that we are going to investigate is adaptive inference tasks. Here the inference problem can be tackled interactively in several stages to improve results. For example, in group testing this means that tests are not conducted concurrently but in several stages. Beyond these new challenges we will also aim to complete the rigorous understanding of the fundamental Bayes-optimal scenario.

计算机科学及其应用中的许多关键问题可以最好地描述为推理问题。这里的目标是在间接的，可能有噪声的观察的基础上学习某些变量的值。组测试问题就是一个很好的例子。群体检测的目的是确定群体中感染了某种疾病的个体。为此目的，进行池测试，其中每个人都参加一个或多个测试池。当且仅当测试池中至少有一人被感染时，测试池的结果应为阳性。然而，测试结果可能并不完全准确。在任何基地，都需要根据检测结果尽可能确定受感染的个体。根据精确的设置，像组测试这样的推理任务可能是可行的，也可能是难以解决的，甚至是不可能解决的。可行是指存在一种有效的算法，能够在观测数据的基础上可靠地求解问题。困难意味着数据原则上足以解决任务，但这将需要过多的计算资源。最后，从信息论的角度来看，如果数据不足，解决推理任务是不可能的。本项目的目标是从计算理论的严格角度研究推理问题，根据其可行性对其进行分类，并开发新的推理方案和算法。在项目的第二阶段，我们将对非贝叶斯最优设置特别感兴趣。这意味着推理算法可能无法准确地知道问题的参数。例如，在群体测试问题中，推理算法可能只对感染率和测试的准确性有一个粗略的估计。我们要研究的第二个新挑战是自适应推理任务。在这里，推理问题可以分几个阶段进行交互处理，以改善结果。例如，在组测试中，这意味着测试不是同时进行的，而是分几个阶段进行的。除了这些新的挑战，我们还将致力于完成对基本贝叶斯最优情景的严格理解。