arXiv:2410.06065cs.LGcs.AI2024-10

用概率方法自动发现事件图谱中的有序特征,避免人工干预。

Posets and Bounded Probabilities for Discovering Order-inducing Features in Event Knowledge Graphs

  • 基于事件偏序构造概率模型,通过统计推断发现结构
  • 提出可计算的上界估计,实现快速搜索收敛
  • 适合需要自动化构建事件知识图谱的研究者

事件知识图谱(EKG)将经典轨迹概念扩展为捕捉多个交互过程视图。本文针对从非结构化数据中自动化发现EKG这一开放问题,提出一种基于事件特征诱导偏序的严格概率框架。该方法通过统计推断而非启发式或专家经验来发现图谱结构,但需在庞大且非凸的假设空间中搜索。其目标函数中的最大似然项涉及计数偏序集的线性扩展数,一般为#P完全问题。幸运的是,只需使用边界估计即可进行模型比较,并可嵌入定制的分支定界算法。我们建立了目标函数的上界,证明其在单调包含分支规则下随搜索深度递减,从而可剪枝大量搜索空间。实验表明,该方法能快速收敛至与人工构建一致的最优解。

原文摘要 · Abstract (English)

Event knowledge graphs (EKG) extend the classical notion of a trace to capture multiple, interacting views of a process execution. In this paper, we tackle the open problem of automating EKG discovery from uncurated data through a principled probabilistic framing based on the outcome space resulting from featured-derived partial orders on events. From this we derive an EKG discovery algorithm based on statistical inference rather than an ad hoc or heuristic-based strategy, or relying on manual analysis from domain experts. This approach comes at the computational cost of exploring a large, non-convex hypothesis space. In particular, solving the maximum likelihood term in our objective function involves counting the number of linear extensions of posets, which in general is #P-complete. Fortunately, bound estimates suffice for model comparison, and admit incorporation into a bespoke branch-and-bound algorithm. We establish an upper bound on our objective function which we show to be antitonic w.r.t. search depth for branching rules that are monotonic w.r.t. model inclusion. This allows pruning of large portions of the search space, which we show experimentally leads to rapid convergence toward optimal solutions that are consistent with manually built EKGs.

事件图谱概率建模偏序集自动发现

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。