Neuer Algorithmus lernt Hypertrees optimal mit Pfadabfragen

Wissenschaftler haben ein neues Verfahren entwickelt, mit dem Hypergraphen – komplexe Strukturen, die in vielen Bereichen von Datenbanken bis zur Evolutionsforschung Anwendung finden – mithilfe von kürzesten Pfadabfragen (SP‑Abfragen) effizient erlernt werden können. Das Ergebnis ist der erste nachweislich optimale Online‑Algorithmus für eine weitreichende Klasse von Hypertrees, die als „ordnungsgemäß“ bezeichnet werden.

Der Algorithmus arbeitet in Echtzeit und kann anschließend in einen Offline‑Algorithmus umgewandelt werden, der dieselbe optimale Leistung erbringt. Damit wird die bisherige Lücke in der Lernforschung geschlossen: bislang fehlte ein Verfahren, das sowohl online als auch offline die minimal mögliche Anzahl an Abfragen garantiert.

Ordnungsgemäße Hypertrees gehören zur Fagin‑Hierarchie acyclischer Hypergraphen – einer gut erforschten Struktur in der Datenbanktheorie. Der neue Ansatz umfasst sogar die größte Klasse innerhalb dieser Hierarchie, die mit subquadratischer SP‑Abfragekomplexität erlernbar ist, und erweitert damit das bisherige Wissen um einen bedeutenden Schritt.

Darüber hinaus haben die Forscher ein Modell mit beschränkten Distanzabfragen untersucht, das in realen Szenarien relevant ist, in denen Messungen mit zunehmender Entfernung an Genauigkeit verlieren. Für dieses Modell konnten sie asymptotisch optimale Komplexitätsgrenzen für das Lernen beliebiger Hypertrees nachweisen, was die Anwendbarkeit des Ansatzes in der Praxis weiter stärkt.