Descriptive Complexity of Learning

点击翻译按钮获取中文摘要

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.