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.