Message-Passing-Algorithmen, Informationstheoretische Schwellwerte und Grenzen der effizienten Lösbarkeit

• Antragsteller: Professor Dr. Amin Coja-Oghlan
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2018
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 393689644

Zahlreiche wichtige Aufgaben in der Informatik und ihren Anwendungsgebiten können am besten als Inferenzprobleme beschrieben werden. In solchen Problemen geht es darum, den Wert gewisser Variablen auf Grundlage indirekter, möglicherweise ungenauer Messungen zu lernen. Das Gruppentestproblem ist ein ausgezeichnetes Beispiel. In diesem Problem geht es darum, diejenigen Individuen in einer grossen Gruppe zu identifizieren, die mit einer seltenen Erkrankung infiziert sind. Zu diesem Zweck werden Pooltests durchgeführt, wobei jedes Individuum zu einem oder zu mehreren Testpools zugeordnet wird. Das Ergegbnis eines Pooltests sollte genau dann positiv sein, wenn eines der beteiligten Individuen infiziert ist; allerdings sind die Tests nicht notwendigerweise huntertprozentig zuverlässig. Jedenfalls ist das Ziel, auf Grundlage der Testergebnisse die infizierten Individuen so zuverlässig wie möglich zu identifizieren.In Abhängigkeit der genauen Problemstellung können Inferenzprobleme entweder lösbar, schwer oder unmöglich sein. Lösbar bedeutet dabei, dass es einen effizienten Algorithmus gibt, der zuverlässig auf Grundlage der vorliegenden Daten das Problem löst. Schwer heisst, dass die vorhandenen Daten zwar prinzipiell ausreichen, um das Problem zu lösen, dass aber die dafür notwendigen Resources wie Rechenzeit oder Speicherplatz exorbitant sind. Unmöglich ist ein Problem dann, wenn die Daten informationstheoretisch nicht ausreichen, um die gewünschten Rückschlüsse zu ziehen.Ziel dieses Projektes ist die Untersuchung derartiger Inferenzprobleme aus dem rigorosen Blickwinkel der Theoretischen Informatik, zum Zweck einer Klassifizierung nach ihrer Lösbarkeit sowie zur Entwicklung neuer Verfahren und Algorithmen.In dieser zweiten Projektphase sind wir insbesondere an nicht Bayes-optimeln Problemen interessiert. Das bedeutet, dass der Inferenzalgorithmus nicht notwendigerweise die genauen Parameter kennt. Beispielsweise hat der Algorithmus im Gruppentestproblem nur eine ungenaue Schätzung der Infektionsrate und/oder der Testgenauigkeit zur Verfügung. Eine weitere Stossrichtung sind adaptive Inferenzverfahren. Dabei soll die Aufgabe in mehreren interaktiven Stufen gelöst werden, um die Qualität der Ergegbnisse zu verbessern. Im Gruppentestproblem bedeutet das beispielsweise, dass die Tests nicht alle gleichzeitig, sondern in mehreren Phasen eingesetzt werden. Abgesehen von diesen neuen Herausforderungen werden wir weiterhin an einer Vervollständigung der Theorie der Bayes-optimalen Inferenz arbeiten.

• DFG-Verfahren: Sachbeihilfen