PaperlayerView exact revision on arXiv

Source-linked AI summary

Probabilistic Embedding of Knowledge Graphs with Box Lattice Measures

Luke Vilnis, Xiang Li, Shikhar Murty, Andrew McCallum

arXiv:1805.06627v1stat.MLcs.LG

TL;DR

Existing order embeddings impose useful structure but deterministic or cone-based probabilistic variants lack expressive uncertainty and cannot represent negative correlations. The paper develops a probabilistic box lattice whose volumes and overlaps support richer queries, then reports improved Flickr and WordNet entailment modeling. The approach is promising for structured knowledge representation, though probability-mass coverage and exact marginal matching remain difficult.

  • Problem

    Order embeddings and probabilistic extensions do not provide both rich uncertainty-based querying and representation of negative correlations in knowledge graphs.

  • Method

    The paper models concepts as high-dimensional boxes, using box volumes for unary probabilities and overlaps for joint probabilities within a probabilistic lattice.

  • Results

    The model achieves state-of-the-art Flickr denotational probability modeling and matching state-of-the-art WordNet hypernymy performance.

  • Takeaways & Limitations

    Probabilistic ordering models support new training and querying forms and are promising for representing structured knowledge.

  • Takeaways & Limitations

    Ensuring total box probability mass equals 1 or exactly matching marginals while modeling all correlations is difficult and generally impossible.

Abstract

from arXiv · show

Embedding methods which enforce a partial order or lattice structure over the concept space, such as Order Embeddings (OE) (Vendrov et al., 2016), are a natural way to model transitive relational data (e.g. entailment graphs). However, OE learns a deterministic knowledge base, limiting expressiveness of queries and the ability to use uncertainty for both prediction and learning (e.g. learning from expectations). Probabilistic extensions of OE (Lai and Hockenmaier, 2017) have provided the ability to somewhat calibrate these denotational probabilities while retaining the consistency and inductive bias of ordered models, but lack the ability to model the negative correlations found in real-world knowledge. In this work we show that a broad class of models that assign probability measures to OE can never capture negative correlation, which motivates our construction of a novel box lattice and accompanying probability measure to capture anticorrelation and even disjoint concepts, while still providing the benefits of probabilistic modeling, such as the ability to perform rich joint and conditional queries over arbitrary sets of concepts, and both learning from and predicting calibrated uncertainty. We show improvements over previous approaches in modeling the Flickr and WordNet entailment graphs, and investigate the power of the model.

1 Introduction

Structured probabilistic embeddings combine order-based inductive biases with uncertainty, but cone-based probability measures cannot represent negative correlations. The paper introduces box-based modeling and reports improved entailment results.

  • Motivation: Probabilistic models support consistency with noisy data, semisupervised learning from expectations, uncertainty representation, and joint queries over more than two variables.Complex queries require a true joint probabilistic model with tractable inference.
  • Motivation: POE assigns probability measures to forward cones but cannot model negative correlations between concepts.This limitation motivates replacing cone-based events with box-based events.
  • Approach: The model represents objects, concepts, and events as products of intervals, using box volumes for unary probabilities and overlaps for joint probabilities.This provides finite geometric events while retaining structural biases for transitive and asymmetric relations.
  • Approach: OE, POE, and the proposed model share slackness: once an edge or non-edge is predicted with probability 0 or 1, repeated evidence does not update the model.The parameter space still retains degrees of freedom for embedding complex structure without loss.
  • Results: The experiments achieve state-of-the-art denotational probability modeling on Flickr and matching state-of-the-art WordNet hypernymy performance.Additional co-occurrence expectations from leaf types yield the best reported results.
  • Results: The authors conclude that probabilistic ordering models enable new forms of training and querying and are promising for structured knowledge representation.This conclusion follows the reported empirical performance of the box lattice model.

2 Related Work

The paper situates box-based probabilistic relational modeling among graphical-model, partitioning, and embedding approaches. Its focus is scalable probabilistic modeling for arbitrary DAG-structured knowledge.

  • Graphical models: The work relates directed, transitive relational modeling and ontology induction to directed graphical models, causal modeling, and structure learning.It also connects to undirected structure learning through pairwise joint and conditional probabilities.
  • Graphical models: Related Bayesian-network methods often restrict taxonomic structure to trees, whereas this work focuses on arbitrary directed acyclic graphs.The comparison concerns the structure class supported by inference and learning methods.
  • Geometric models: Unlike Mondrian-process models, the box model permits arbitrary box placement for DAG structure and is more tractable in high dimensions.Mondrian processes partition space as high-dimensional trees, while the proposed representation does not impose that restriction.
  • Embedding models: Matrix factorization scores relation links, whereas POE and the proposed model represent subsets of probabilistic event space and directly integrate them.The latter are full joint probabilistic models rather than approximations limited to low-order probabilities.
  • Scalability: Embedding-based learning scales to probability distributions with hundreds of thousands of events, unlike the combinatorial structure learning of classical probabilistic graphical models.The paper identifies this advantage in both its WordNet and Flickr experiments.

3 Background

The background develops partial orders, lattices, and order embeddings before introducing probabilistic order embeddings. It shows that cone-based measures yield valid probabilities but only nonnegative dependence.

  • Partial orders and lattices: A poset generalizes a total order by allowing incomparable elements and models acyclic directed-graph data in knowledge bases.Its defining structure is a binary relation satisfying the partial-order axioms.
  • Partial orders and lattices: A lattice is a poset in which every subset has a unique least upper bound and greatest lower bound, called its join and meet.Bounded lattices additionally contain top and bottom elements for the entire space.
  • Order embeddings: Order embeddings map partially ordered data into another partially ordered space to enable generalization, using a reverse product order on a vector space.In this construction, an embedding is below another when all coordinates are larger, with 0 as the top element.
  • Order embeddings: Order-embedding vectors can also be viewed as cones extending toward infinity, with entailed concepts lying inside the corresponding cone.The ordering is optimized from ordered examples and negative samples using a max-margin loss.
  • Probabilistic order embeddings: POE assigns exponential-measure volumes to cone events and their intersections, producing a valid probability distribution over concepts.The construction uses the fact that a vector meet corresponds to intersection of its area cones.
  • Probabilistic order embeddings: POE can model only positive Pearson correlations, because its covariance expression is always nonnegative.Consequently, conditioning on additional concepts can only increase or preserve probabilities, such as p(dog|plant) ≥ p(dog).
  • Probabilistic asymmetric transitive relations: Probabilistic pairwise conditional tables can almost always be asymmetrized into DAGs by selecting an edge when P(a|b) > P(b|a).The paper contrasts this consistency property with pairwise Gaussian KL divergences, which cannot be asymmetrized consistently in the same way.

4 Method

The method replaces cone-based probabilistic order embeddings with probabilistic box lattices, allowing both positive and negative correlations while retaining tractable volume-based inference. Box intersections support joint probabilities and surrogate-gradient learning, although exact probability coverage and arbitrary distributions remain constrained.

  • Box-lattice construction: The model uses hypercube box embeddings to represent concepts probabilistically and capture both positive and negative correlations.Cone-based measures are shown to be nonnegative-correlating under product measures, motivating boxes with an additional degree of freedom.
  • Box-lattice construction: Box inclusion defines the partial order, while intersection gives the meet and the smallest enclosing box gives the join.The resulting lattice is strictly more general than the order-embedding lattice in any dimension.
  • Probabilistic interpretation: Under the uniform measure, unary and joint probabilities are computed from box volumes and intersections, enabling marginal and conditional inference.The model represents each concept with minimum and maximum coordinate vectors in the unit hypercube.
  • Correlation expressiveness: For Bernoulli variables, box volumes can realize every correlation from -1 to 1, including disjoint concepts and perfectly correlated identical boxes.Continuously translating intersecting boxes spans intermediate correlations.
  • Limitations: The representation cannot encode all probability distributions or generally match arbitrary marginals and correlations through box packing, though complements can be queried with inclusion–exclusion.Unions with mass below one can be interpreted as an open-world assumption for the knowledge base.
  • Learning: Because joint probabilities are nondifferentiable for nonintersecting boxes, learning optimizes a differentiable lower bound whose gradient shrinks enclosing boxes and enlarges individual boxes until intersection.Unary and binary conditional terms are optimized separately by maximum likelihood when full conjunctive likelihoods are intractable.

5 Experiments

Experiments evaluate the box lattice on a synthetic probabilistic lattice, WordNet hypernym prediction, and Flickr entailment probabilities. The model supports multi-way queries, negative correlations, and improves over prior approaches on both real datasets.

  • Toy probabilistic lattice: The toy experiment trains a 2-dimensional box model on unary marginals and pairwise conditional probabilities, testing its self-organized event space and multi-variable queries.The associated CPD is formed by weighted aggregation of leaf elements.
  • Toy probabilistic lattice: The box lattice produces negatively correlated variables and allows conditional probabilities to change with additional evidence or contradiction, unlike POE.POE can only raise or preserve probability when conditioning.
  • WordNet: WordNet experiments use 50-dimensional boxes and show significant improvement over POE, with soft conditional edges further reaching state-of-the-art performance.The comparison also includes a 100-dimensional POE model for matched parameter capacity.
  • Flickr entailment graph: On Flickr, the box model substantially improves KL and Pearson correlation with ground-truth entailment probabilities over POE.The largest gains occur for small entailment probabilities, indicating finer-grained distinctions.

6 Conclusion and Future Work

The paper identifies broad opportunities for applying box-lattice probabilistic modeling beyond the demonstrated experiments. Proposed directions include richer relational data, more flexible geometric representations, and improved inference.

  • Future work: Future work includes multi-relational general knowledge representation, higher-flexibility polyhedral event spaces, and better latent-box inference through optimization or Bayesian methods.The authors describe current applications as only an initial exploration.

A Queries with Negated Variables

The model handles queries involving negated variables even though complements of boxes are not themselves boxes. It computes these probabilities with Inclusion-Exclusion over unions of boxes.

  • Negated-variable queries: Negated-variable queries are evaluated with the standard Inclusion-Exclusion formula for volumes of unions of hyperrectangles.Non-negated variables are first intersected into a conjunction box, after which union volumes provide the query probability.
  • Negated-variable queries: The resulting probability is obtained by subtracting the volume for the negated variables alone from the volume including the non-negated conjunction.This cancellation recovers the joint probability of the original query.

B.1 Non-Distributivity

The box lattice is non-distributive and therefore strictly more general than order embeddings, supporting disjoint events that distributive order-embedding lattices cannot represent. Its pseudocomplements exist almost always, but can poorly approximate true complements.

  • B.1 Non-Distributivity: Order embeddings form a distributive lattice, whereas the box lattice is non-distributive.The box lattice therefore does not satisfy the distributive identity for all elements.
  • B.1 Non-Distributivity: A one-dimensional counterexample shows different results for x ∧ (y ∨ z) and (x ∧ y) ∨ (x ∧ z).For x = [0, 0.3], y = [0.2, 0.6], and z = [0.5, 1.0], the two expressions yield [0.2, 0.3] and [0, 0.6].
  • B.1 Non-Distributivity: The box lattice strictly generalizes order embeddings and is not equivalent to order embeddings of any dimensionality.The disjoint elements in the counterexample also motivate non-distributivity for modeling disjoint events.
  • B.2 Pseudocomplemented: The box lattice is almost always pseudocomplemented, aside from symmetry concerns that can be removed by infinitesimal perturbations.This property is understood in a measure-theoretic sense because exact symmetries can create multiple equally large pseudocomplements.
  • B.2 Pseudocomplemented: Box-lattice pseudocomplements can be arbitrarily poor approximations of a box’s true complement, especially for large, nearly centered cubes.Thus pseudocomplementation does not generally provide an accurate geometric complement.

C.3 Order Embeddings

The order-embedding asymmetrization procedure is conjectured to consistently produce directed acyclic graphs, supported by extensive simulations but not yet proven. WordNet training additionally prevents negative samples from artificially shrinking boxes and creating disjoint pairs.

  • C.3 Order Embeddings: Millions of random order-embedding parameter sets produced no cycles after asymmetrization using the order-embedding energy function.The authors conjecture that the energy acts like a Lagrangian relaxation penalizing violations of a true partial order.
  • C.3 Order Embeddings: Sets of order embeddings are conjectured to be consistently asymmetrizable into directed acyclic graphs.The conjecture is motivated by simulations that found no cycles, but the authors explicitly leave it unproven.
  • C.3 Order Embeddings: For WordNet, the delta embedding is not updated on negative samples because random negatives otherwise decrease box volumes and create artificially disjoint pairs.This constraint is used because WordNet links are binary and negative links come from random negative sampling.
  • C.3 Order Embeddings: The reported best WordNet configuration uses batch size 800, dimension 50, edge loss weight 1.0, unary loss weight 9.0, and learning rate 0.001.It also uses Adam, minimum dimension delta size 1e-6, and dimension-max regularization weight 0.005.
  • C.3 Order Embeddings: WordNet training with additional soft CPD edges retains the same parameters and prunes pairs to probabilities ≥0.6 with reverse probabilities ≤0.4.The pruning is applied to the generated CPD file.

D.2 Flickr Parameters

The Flickr model uses a tuned neural configuration with dropout and weighted unary and edge losses. Initialization and positivity constraints are chosen to begin with substantial box overlap while preserving valid box dimensions.

  • D.2 Flickr Parameters: The best Flickr configuration uses batch size 512, dropout 0.5, unary loss weight 8.0, edge loss weight 2.0, and learning rate 0.0001.It also uses minimum dimension delta size 1e-6 and the Adam optimizer.
  • D.2 Flickr Parameters: The delta network is initialized to promote high initial overlap, while softplus enforces positive embedding dimensions and a minimum dimension size.Minimum embeddings use ReLU clipping, and box minimums use Glorot initialization.
  • D.2 Flickr Parameters: Flickr hyperparameters sweep edge loss weights from 1.0 to 9.0, unary loss weights from 9.0 to 1.0, and learning rates in {0.001, 0.0001}.Initialization ranges for the delta network include [5.0, 5.5], [10.0, 10.5], and [15.0, 15.5].
Loading 1805.06627v1…