IJCAIMay, 2020

关于可能性理论的可学习性

PDF
TL;DR研究使用 Angluin 的精确学习模型从蕴含中学习可能性理论的可学习性问题，我们考虑只有成员资格、仅等价性和两种查询可以被学习者提出的情况。对于一大类问题，我们证明了经典逻辑的多项式时间可学习性结果可以转移到相应的可能性扩展中。特别是，由我们的结果可知，命题 Horn 理论的可能性扩展可以在多项式时间内准确地学习。由于精确模型的多项式时间可学习性可转化为在会员资格查询扩展中扩展的经典大概近似正确模型，因此我们的工作也在此模型中确立了这样的结果。
learnabilitypossibilistic theoriesangluin's exact learning modelmembership queriespolynomial time
发现论文，激发创造
  • 通过默认规则学习 Possibilistic 逻辑理论

    从机器学习角度分析了默认形式 “如果 alpha 通常是 beta” 学习可能主义逻辑理论的问题，然后提出了一种启发式学习算法，可以轻松扩展到数千个默认项，并且能够处理嘈杂和冲突的默认集合。通过使用该方法，我们可以从众包数据中学习可能主义逻辑理论，并使用启发式 MAP 求解程序来近似命题 Markov 逻辑网络。实验结果表明了该方法的有效性。

    Apr, 2016

  • 轻量级描述逻辑本体的精确学习

    该论文研究了使用 Angluin 等人的准确查询学习框架来学习描述逻辑本体的问题，证明了可以用多项式大小的多项式查询来学习用 DL-Lite 描述逻辑和某些和 OWL 2 RL 相关的 EL 片段描述的本体，但即使只允许非循环本体，也不能用多项式大小的查询来学习用 EL 描述逻辑描述的本体。

    Sep, 2017

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

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

    Feb, 2024

  • 一阶逻辑隐式学习推理

    本文通过利用语言中常量的对称性，将隐式可学习性推广，提出了一种在第一阶逻辑中进行强健学习的新理论方法。

    Jun, 2019

  • 多智体信仰的 PAC 语义学习性

    此文介绍了使用多智能体认知逻辑演示 PAC 学习的技术基础，涉及逻辑和弱推理，以提供强大的模型理论框架来回答查询，并研究了该算法的正确性、样本复杂性以及其能够高效的情况，利用表述定理将模态推理纳入命题推理中。

    Jun, 2023

  • 时间实例查询的唯一可特征化性和可学习性

    通过分析命题线性时间逻辑 LTL 与 EL 或 ELI 描述逻辑中的概念结合的 2D 语言所查询的时间知识图中的路径形查询，研究了一些查询操作可以通过（多项式大小的）正 / 负时间数据示例的集合来唯一地描述的可能性，探讨了这些查询的多项式特性，并将其应用于活性学习框架中对时间实例查询的学习。

    May, 2022

  • 通过大型语言模型查询学习 Horn 包络

    该研究通过学习 Horn 理论的经典算法，提出了一种从训练好的神经网络中提取知识的方法。通过实验该方法在事先训练好的语言模型中提取规则，揭示了职业基础性别偏见。

    May, 2023

  • 一个基础信任函数逻辑

    本文研究不确定性理论中的可能性理论、信念函数和不精确概率与模态逻辑之间的二元性质，提出了一种基于最小认知逻辑和波兰式逻辑的简化信念函数逻辑，并且给出了使用 Shafer 基本概率分配的语义。

    Mar, 2023

  • 概率定理证明

    该论文提出了一种将概率论和第一阶逻辑相结合的方法，在有限域内具有 Herbrand 解释的情况下，定义了概率证明定理及其推广问题，然后提出了能够同时拥有图模型推理和一阶定理证明的完整能力的方法，并开发了一种高效算法。实验表明，当逻辑结构存在时，该算法远优于目前已有的方法。

    Feb, 2012

  • 联结查询：独特特征和精确可学性

    研究了如何构造多项式多个正负示例唯一确定的不变式查询，提出了前沿算法并讨论其在描述逻辑和模式映射中的应用。

    Aug, 2020