Project Details
Projekt Print View

Descriptive Complexity of Learning

Subject Area Theoretical Computer Science
Term from 2017 to 2022
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 389872375
 
Descriptive complexity theory explains the computational complexity ofalgorithmic problems in terms of the language resources required todefine the problems. In this project, we extend the descriptivecomplexity approach to machine learning problems: we aim to understandefficient learnability in terms of the descriptive complexity of themodel, that is, the language resources required to define thehypotheses to be learned.This work may serve as a foundation for a more declarative approach tomachine learning, where the model (the hypothesis class) isseparated from the solver (the optimisation algorithm computing thebest hypothesis).Applications of our framework can most likely be found in logic-affineareas such as automated verification and database systems, and we willexplore such applications.
DFG Programme Research Grants
 
 

Additional Information

Textvergrößerung und Kontrastanpassung