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

• URL: http://arxiv.org/abs/2410.06065v1
• Date: Tue, 8 Oct 2024 14:12:51 GMT
• Title: Posets and Bounded Probabilities for Discovering Order-inducing Features in Event Knowledge Graphs
• Authors: Christoffer Olling Back, Jakob Grue Simonsen,
• Abstract summary: Event knowledge graphs (EKG) capture multiple, interacting views of a process execution. We tackle the open problem of EKG discovery from uncurated data. We derive an EKG discovery algorithm based on statistical inference.
• Score: 6.96958458974878
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 upon 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 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 show that the posterior probability as defined is 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.

Related papers

• pEBR: A Probabilistic Approach to Embedding Based Retrieval [4.8338111302871525]
  Embedding retrieval aims to learn a shared semantic representation space for both queries and items. In current industrial practice, retrieval systems typically retrieve a fixed number of items for different queries.
  arXiv  Detail & Related papers  (2024-10-25T07:14:12Z)
• Data-Driven Abstractions via Binary-Tree Gaussian Processes for Formal Verification [0.22499166814992438]
  abstraction-based solutions based on Gaussian process (GP) regression have become popular for their ability to learn a representation of the latent system from data with a quantified error. We show that the binary-tree Gaussian process (BTGP) allows us to construct an interval Markov chain model of the unknown system. We provide a delocalized error quantification via a unified formula even when the true dynamics do not live in the function space of the BTGP.
  arXiv  Detail & Related papers  (2024-07-15T11:49:44Z)
• MissDAG: Causal Discovery in the Presence of Missing Data with Continuous Additive Noise Models [78.72682320019737]
  We develop a general method, which we call MissDAG, to perform causal discovery from data with incomplete observations. MissDAG maximizes the expected likelihood of the visible part of observations under the expectation-maximization framework. We demonstrate the flexibility of MissDAG for incorporating various causal discovery algorithms and its efficacy through extensive simulations and real data experiments.
  arXiv  Detail & Related papers  (2022-05-27T09:59:46Z)
• Multi-task Learning of Order-Consistent Causal Graphs [59.9575145128345]
  We consider the problem of discovering $K related Gaussian acyclic graphs (DAGs) Under multi-task learning setting, we propose a $l_1/l$-regularized maximum likelihood estimator (MLE) for learning $K$ linear structural equation models. We theoretically show that the joint estimator, by leveraging data across related tasks, can achieve a better sample complexity for recovering the causal order.
  arXiv  Detail & Related papers  (2021-11-03T22:10:18Z)
• Probabilistic Entity Representation Model for Chain Reasoning over Knowledge Graphs [18.92547855877845]
  We propose a Probabilistic Entity Representation Model (PERM) for logical reasoning over Knowledge Graphs. PERM encodes entities as a Multivariate Gaussian density with mean and covariance parameters to capture semantic position and smooth decision boundary. We demonstrate PERM's competence on a COVID-19 drug-repurposing case study and show that our proposed work is able to recommend drugs with substantially better F1 than current methods.
  arXiv  Detail & Related papers  (2021-10-26T09:26:10Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data. Our algorithms are validated extensively on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-10-12T02:21:30Z)
• Complex Event Forecasting with Prediction Suffix Trees: Extended Technical Report [70.7321040534471]
  Complex Event Recognition (CER) systems have become popular in the past two decades due to their ability to "instantly" detect patterns on real-time streams of events. There is a lack of methods for forecasting when a pattern might occur before such an occurrence is actually detected by a CER engine. We present a formal framework that attempts to address the issue of Complex Event Forecasting.
  arXiv  Detail & Related papers  (2021-09-01T09:52:31Z)
• Improving Efficiency and Accuracy of Causal Discovery Using a Hierarchical Wrapper [7.570246812206772]
  Causal discovery from observational data is an important tool in many branches of science. In the large sample limit, sound and complete causal discovery algorithms have been previously introduced. However, only finite training data is available, which limits the power of statistical tests used by these algorithms.
  arXiv  Detail & Related papers  (2021-07-11T09:24:49Z)
• Probabilistic DAG Search [29.47649645431227]
  We develop a probabilistic framework to exploit a search space's latent structure and share information across the search tree. We empirically find our algorithm to compare favorably to existing non-probabilistic alternatives in Tic-Tac-Toe and a feature selection application.
  arXiv  Detail & Related papers  (2021-06-16T11:35:19Z)
• A Robust Functional EM Algorithm for Incomplete Panel Count Data [66.07942227228014]
  We propose a functional EM algorithm to estimate the counting process mean function under a missing completely at random assumption (MCAR) The proposed algorithm wraps several popular panel count inference methods, seamlessly deals with incomplete counts and is robust to misspecification of the Poisson process assumption. We illustrate the utility of the proposed algorithm through numerical experiments and an analysis of smoking cessation data.
  arXiv  Detail & Related papers  (2020-03-02T20:04:38Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.