Sep, 2010

查询答案和非答案的因果关系和责任的复杂性

PDF
TL;DR该论文研究了查询的答案和非答案的原因和责任的计算方法以及 P 和 NP 的情况和 LOGPACE 的完整性，并证明了某些查询中的因果关系可以通过关系查询在多项式时间内计算。
lineage expressioncausalityresponsibilityconjunctive queriescomplexity
发现论文，激发创造
  • 基于结构的因果关系的计算复杂度

    对 Halpern 和 Pearl 提出的实际因果关系进行定义，并且针对计算是否为一个因果关系提出复杂性问题，进行定义修正，并探究其对复杂度的影响，引入了新的复杂度类 D_k^P，并且对计算因果关系的复杂度进行了全面分类和探究，还介绍了责任和指责的概念

    Dec, 2014

  • 数据库查询结果的原因：Datalog 推理、视图更新和完整性约束

    本研究建立了 QA 因果关系与数据库诊断、维护完整性约束、视图定义更新的联系，研究了限制条件下的诊断算法工具的复杂性，并获得了新的算法工具。

    Nov, 2016

  • Datalog 查询的 Why-Provenance 复杂性

    本文旨在填补 why-provenance 计算复杂性方面的空白，我们确定了 Datalog 查询和其子类的 why-provenance 的数据复杂度，得出结论，由于其计算复杂性的特殊性质，递归查询的 why-provenance 是一个棘手的问题。

    Mar, 2023

  • 从数据库查询的原因到修复和基于模型的诊断再到返修

    本研究旨在探究数据库中查询答案、拒绝约束下数据库修复、基于一致性的诊断之间的关系，并提出了计算实际查询答案的原因及其责任的新问题，然后建立这些问题与超图中的击中集和顶点覆盖的关系，从而产生了若干新的算法和复杂性结论。

    Jul, 2015

  • 概率和因果可满足性：边缘化的影响

    研究了 Pearl 的因果层次结构 (PCH) 框架中的推理和计算复杂性，重点关注概率和因果语言中表达的满足性问题，特别是与边缘化相关的方程，证明了不同层次和操作符的确切计算复杂性结果，以及对受限模型进行了考虑。

    May, 2024

  • 关于概率和因果推理的困难程度

    研究员从计算复杂性的角度出发，研究了能够完全表达数量化概率推理和因果效应的形式语言。研究集中于可表达许多概率和因果推断任务的可满足性问题，并建立了这些可满足性问题的确切计算复杂性。研究结果表明，一些在概率和因果推断中常用的标准语言的变体的算法限制更强。

    May, 2023

  • 责任与归咎：一种结构模型方法

    本文提出新的因果关系定义，以考虑 A 对 B 的责任程度与 A 的认知状态相关联的程度，并定义了一种责任程度的概念，用于衡量 A 对 B 的责任程度，从而得出预期的 A 对 B 的责任程度。

    Dec, 2003

  • 针对细粒度因果推理和问答的探索

    本文介绍了一种新的精细化因果推理数据集，并在自然语言处理中提出了一系列新的预测任务，例如因果检测、事件因果提取和因果问答。作者通过大量实验和分析表明，数据集中的复杂关系对最先进的方法带来了独特的挑战，并强调了潜在的研究机会，特别是在发展 "因果思维" 方法方面。

    Apr, 2022

  • 因果层级上的概率推理

    本研究将 3 层因果关系层次结构分为概率逻辑语言模型，第一层表达定量概率推断，第二层编码用于因果效应的 do-calculus 推理，第三层捕捉任意反事实查询。相关的公理化表达完全考虑了因果模型和概率编程，并证明了每种语言的可满足性和有效性都可以在多项式空间内可判定。

    Jan, 2020

  • 强化学习下的因果问答

    本研究利用强化学习在 CauseNet 知识图谱上应用 Actor-Critic 方式，通过搜索图谱回答因果问题，并通过经验学习和算法改进降低搜索空间，结果表明与朴素的宽度优先搜索相比，每个二元因果问题访问不到 30 个节点，在路径上的边均有原始来源，可轻松验证。

    Nov, 2023