Jan, 2022

无限概念精确学习

PDF
TL;DR本文基于精确学习、测试理论和粗糙集理论的结果，研究了由无限个元素和无限个该集合的子集所组成的任意无限概念族，并考虑了这些概念族上的问题，其中算法为五种不同类型的决策树。在最坏情况下，当问题描述中元素数量增加时，第一型决策树的最小深度要么按对数增长，要么按线性增长，而其他每种类型的决策树的最小深度或者受到上限的约束，或者按对数增长，或者按线性增长。得到的结果可以区分无限概念族的七个复杂度类。
exact learningtest theoryrough set theoryinfinite families of conceptsdecision trees
发现论文，激发创造
  • 关于机器教学中出现的一个组合问题

    我们研究了一种机器教学模型，其中教师映射是根据概念和示例的大小函数构建的。我们证明了最小示例数量问题的一个猜想，该猜想认为在这个模型中，作为概念类的大小函数的函数，最坏情况发生在一致性矩阵包含从零开始的数字的二进制表示时。

    Feb, 2024

  • 概念的简洁表示

    通过基于范畴论的简洁概念表示，可以训练模型从而精确理解概念，并产生不变性属性以及层级分解，以验证每个部分来学习复杂概念或纠正误解。

    Mar, 2023

  • 层次化测试设计用于模式识别

    本文探讨了 “二十个问题” 的模式识别方法的理论基础，其中通过假设检验对可能的解释集合 Y 中的真实解释集合 Η 进行限制，提出了一种逐步测试策略，并针对测试成本和后期处理成本的总成本进行了优化。

    Jul, 2005

  • 可学习性是一个紧凑属性

    近期的学习研究显示，学习问题的可学习性可能是不可判定的，或者与标准集合论的 ZFC 公理无关。此外，这些问题的可学习性可能不是有限特性：简单来说，通过检查问题的有限投影无法检测出可学习性。然而，学习理论在定义学习的维度时充斥着只考虑问题的有限限制的概念，即具有有限特性的性质。如何调和这些结果呢？具体而言，哪些学习问题容易受到逻辑不可判定性的影响，哪些问题可以用有限特性来解决？我们证明了具有测度损失的监督学习的困难可以通过有限特性来精确描述。尤其是我们证明了学习一个假设类的样本复杂度可以通过检查其有限投影来判断。对于广泛类别的适当损失函数的可实现和了解学习，我们证明了一个确切的紧致性结果：一个类别在具有给定样本复杂度时可以学习，仅当其所有有限投影也是如此。对于具有不适当损失函数的可实现学习，我们证明了样本复杂度的确切紧致性可能会失败，并提供了样本复杂度相差 2 倍的相匹配上下界。我们猜想对于了解学习的情况可能存在更大的差距。我们技术工作的核心是一个关于变量分配的紧致性结果，它在保持函数类别在目标值以下方面具有广泛的兴趣，该结果推广了霍尔（Hall）经典匹配定理，可能具有独立的兴趣。

    Feb, 2024

  • 一个与 ZF 公理无关的学习问题

    研究 Expectation Maximization 问题的可学习性和采样复杂度，特别是在布尔函数情形下的研究以及其与集合论关系的探讨，结论表明该问题的可学习性与集合论 ZFC 公理无关。

    Nov, 2017

  • Graph2Tac: 数学定理证明中的数学概念的分层表示学习

    使用新的基于图的数据集进行 Coq 的机器学习，我们提出了 Graph2Tac（G2T）模型，通过考虑以往定义层次与当前目标之间的依赖关系，将新的数学概念整合到模型的知识库中。

    Jan, 2024

  • 有限宽度反模理论的一阶查询可决定性

    提出了一个通用的查询决策框架，基于计数模型的结构简单性，可以确定各种逻辑蕴涵问题（简称查询）的可决性，其中 Blumensath 的分区宽度作为一个特别强大的宽度度量提出，重点介绍存在规则的形式化，其中分区宽度的规则子域覆盖范式为一周围侧子域。

    Apr, 2023

  • FACT：学习整数序列背后的支配抽象

    本研究介绍了学习整数序列的一种新方法和一组基准测试任务，用于机器学习模型的概念理解和知识抽象能力的评估。通过 FACT 工具包中的大型整数序列数据集和性能评估工具以及基线模型实现的集合，为知识表示和推理领域的研究提供了便利。

    Sep, 2022

  • 定性推理问题的多元复杂度分析

    本文介绍了单指数算法，并通过多元分析研究了时间推理问题，特别是针对 Allen 的时间间隔代数，证明了一个新问题可以在单指数时间内解决，并且这种方法可以更广泛地用于其他问题。

    Sep, 2022

  • 非均匀在线学习：走向理解归纳

    物理学家和归纳推理的非均匀在线学习的作用和限制，以及与在线学习理论和 Littlestone 类的关系。

    Nov, 2023