从扩展示例中学习抽象论证中的攻击关系

《Journal of Logic and Computation》:Learning attack relations in abstract argumentation from extension examples

【字体: 大 中 小 】 时间:2026年10月22日 来源:Journal of Logic and Computation 0.7

编辑推荐:

   摘要 我们研究了 Dung 抽象论证的一个逆问题。一个有限论证集 A?,|A|=n? 是固定的,攻击关系是未知的,每次观察根据候选子集 S?A 在所选语义下是否为扩展对其进行标记。我们在可实现的大概可学习模型中,针对这类扩展成员资格

  

摘要

我们研究了 Dung 抽象论证的一个逆问题。一个有限论证集 A?,|A|=n? 是固定的,攻击关系是未知的,每次观察根据候选子集 S?A 在所选语义下是否为扩展对其进行标记。我们在可实现的大概可学习模型中,针对这类扩展成员资格示例形式化预测问题,并将信息论意义上的泛化与寻找相容关系的计算任务区分开来。对于每种基于扩展的语义,其诱导假设类的 Vapnik–Chervonenkis(VC)维满足 VC(Hσ)≤n(n?1) 在我们默认的无反射约定下(?n2 若允许自攻击)。对于无冲突语义,我们证明了在无反射情况下其精确值为 (n2),在允许环的情况下为 max{n,(n2)}。我们还刻画了无冲突观察等价性,并获得了允许环的不同分类器的精确数量。对于可容许的、稳定的、完整的和优选的语义,一个显式的有向构造给出了 VC(Hσ)≥?n/3?2?,因此它们的维数为 Θ(n2)?。有界入度给出了稀疏性敏感的上下界;在稠密阈值以下,两者最多相差一个对数因子。在计算方面,我们为无冲突一致性问题给出了直接的多项式时间刻画和见证构造,并为可容许和稳定一致性问题给出了自包含的多项式规模布尔可满足性编码。这些编码是早期论证框架构造工作的零损失特化,而非对其的替代。最后,我们通过不可知风险形式化了含噪观察,并展示了如何为每个示例引入一个松弛变量,将编码转化为加权部分最大可满足性实例,以最小化示例级的经验 0–1 损失。示例演示、图示、约定表和完整证明明确阐明了哪些可以被预测、哪些无法被识别,以及统计主张与计算主张的分歧之处。

相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号