Deskriptive Komplexität des Maschinellen Lernens

• Antragsteller: Professor Dr. Martin Grohe
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2017 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 389872375

• Erstellungsjahr: 2023

Zusammenfassung der Projektergebnisse

Die deskriptive Komplexitätstheorie stellt eine Beziehung zwischen der algorithmischen und der sprachlichen Komplexität von Berechnungsproblemen her. In diesem Projekt haben wir den Ansatz der deskriptiven Komplexitätstheorie auf das maschinelle Lernen übertragen, indem wir effiziente Lernbarkeit anhand der deskriptiven Komplexität der Modelle erklärt haben, also anhand der sprachlichen Ressourcen, die erforderlich sind, um die Modelle zu beschreiben. Um den abstrakten modelltheoretischen Rahmen unseres deskriptiven Ansatzes mit praktischen maschinellen Lernverfahren zu verbinden, haben wir die theoretischen Grundlagen von Graph Neural Networks (GNNs) als moderne Lernarchitekturen für Graphen und diskrete Strukturen untersucht. Wir konnten erstaunlich enge Verbindungen zwischen Logik und GNNs herstellen. Basierend auf GNNs haben wir weiterhin eine Lernarchitektur für den logischen Formalismus von Constraint Satisfaction Problemen entwickelt.

Projektbezogene Publikationen (Auswahl)

• “Learning MSO-definable hypotheses on strings”. In: International Conference on Algorithmic Learning Theory, ALT 2017, 15-17 October 2017, Kyoto University, Kyoto, Japan. Ed. by S. Hanneke and L. Reyzin. Vol. 76. Proceedings of Machine Learning Research. PMLR, 2017, pp. 434–451.
  M. Grohe; C. Lüding & M. Ritzert
  
• Learning Concepts Definable in First-Order Logic with Counting. 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 1-13. IEEE.
  van Bergerem, Steffen
  
• Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 4602-4609.
  Morris, Christopher; Ritzert, Martin; Fey, Matthias; Hamilton, William L.; Lenssen, Jan Eric; Rattan, Gaurav & Grohe, Martin
  
• “Learning Definable Hypotheses on Trees”. In: 22nd International Conference on Database Theory, ICDT 2019, March 26-28, 2019, Lisbon, o Portugal. Ed. by P. Barcel´ and M. Calautti. Vol. 127. LIPIcs. Schloss Dagstuhl - u Leibniz-Zentrum f¨r Informatik, 2019, 24:1–24:18.
  E. Grienenberger & M. Ritzert
  
• Graph Neural Networks for Maximum Constraint Satisfaction. Frontiers in Artificial Intelligence, 3.
  Tönshoff, Jan; Ritzert, Martin; Wolf, Hinrikus & Grohe, Martin
  
• The Logic of Graph Neural Networks. 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 1-17. IEEE.
  Grohe, Martin
  
• The Surprising Power of Graph Neural Networks with Random Node Initialization. Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, 2112-2118. International Joint Conferences on Artificial Intelligence Organization.
  Abboud, Ralph; Ceylan, İsmail İlkan; Grohe, Martin & Lukasiewicz, Thomas
  
• “Learning Concepts Described By Weight Aggregation Logic”. In: 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, January 25-28, 2021, Ljubljana, Slovenia (Virtual Conference). Ed. by C. Baieru and J. Goubault-Larrecq. Vol. 183. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨r In- formatik, 2021, 10:1–10:18.
  S. van Bergerem & N. Schweikardt
  
• “Learning on graphs with logic and neural networks”. PhD thesis. RWTH Aachen University, Germany, 2021.
  M. Ritzert
  
• On the Parameterized Complexity of Learning First-Order Logic. Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 337-346. ACM.
  van Bergerem, Steffen; Grohe, Martin & Ritzert, Martin
  
• “Descriptive complexity of learning”. PhD thesis. RWTH Aachen University, Germany, 2023.
  S. van Bergerem