Neuer Ansatz: Adaptive Sparse Möbius-Transformation zum Lernen von Polynomen

Wissenschaftler haben einen innovativen Weg entwickelt, um ein bislang schwieriges Problem der theoretischen Informatik zu lösen: das exakte Lernen eines s‑sparsen, reellen Booleschen Polynoms vom Grad d. Dabei handelt es sich um Funktionen der Form f: {0,1}^n → ℝ, die in der AND‑Basis dargestellt werden können – ein Verfahren, das als Möbius‑Transformation bekannt ist.

Im Gegensatz zur gut erforschten Paritätsbasis (Fourier‑Transform) ist die AND‑Basis stark kohärent, was herkömmliche Methoden der komprimierten Messung ausschließt. Die Forscher haben dieses Hindernis überwunden, indem sie adaptive Gruppentests nutzen, um die Möbius‑Transformation konstruktiv und abfrageeffizient umzusetzen. Zwei neue Algorithmen entstehen daraus: der Fully‑Adaptive Sparse Möbius Transform (FASMT), der mit O(sd log(n/d)) adaptiven Abfragen arbeitet und in O((sd + n) sd log(n/d)) Zeit läuft, sowie der Partially‑Adaptive Sparse Möbius Transform (PASMT), der mit O(sd² log(n/d)) Abfragen auskommt und die Anzahl der adaptiven Runden auf O(d² log(n/d)) reduziert.

Ein besonders spannender Anwendungsbereich ist die Rekonstruktion von Hypergraphen aus Kantenzählungsabfragen. Durch die neue Methode wird die bisherige kombinatorische Explosion bei hohen Rängen d vermieden, und die Ergebnisse übertreffen die bisherigen Baselines deutlich. Simulationen mit realen Hypergraphen zeigen die praktische Nützlichkeit der Algorithmen.

Diese Fortschritte markieren einen bedeutenden Schritt in der effizienten Analyse sparsamer Boolescher Polynome und eröffnen neue Möglichkeiten in Bereichen wie maschinelles Lernen, Bioinformatik und Netzwerkanalyse, wo komplexe Interaktionen häufig in sparsamen Strukturen vorliegen.