Efficient Weight Learning in High-Dimensional Untied MLNs

Khan Mohammad Al Farabi, Somdeb Sarkhel, Deepak VenugopalAISTATS 2018 · OpenReview

Abstract

Existing techniques for improving scalability of weight learning in Markov Logic Networks (MLNs) are typically effective when the parameters of the MLN are tied, i.e., several ground formulas in the MLN share the same weight. However, to improve accuracy in real-world problems, we typically need to learn separate weights for different groundings of the MLN. In this paper, we present an approach to perform efficient weight learning in MLNs containing high-dimensional, untied formulas. The fundamental idea in our approach is to help the learning algorithm navigate the parameter search-space more efficiently by a) tying together groundings of untied formulas that are likely to have similar weights, and b) setting good initial values for the parameters. To do this, we follow a hierarchical approach, where we first learn the parameters that are to be tied using a non-relational learner. We then use a relational learner to learn the tied-parameter MLN with initial values derived from parameters learned by the non-relational learner. We illustrate the promise of our approach on three different real-world problems and show that our approach yields much more scalable and accurate results compared to existing state-of-the-art relational learning systems.

The Challenge: High-Dimensionality in MLNs

Markov Logic Networks (MLNs) are a powerful way to combine first-order logic with probability. Traditionally, they rely on "weight tying," where every instance (grounding) of a logical rule shares the same weight. However, in real-world tasks like text classification, we need "untied" formulas. For example, the rule Word(+w, p) => Topic(p, +t) needs a different weight for every unique word-topic pair.

When you have thousands of words and multiple topics, the number of parameters explodes. This creates two massive hurdles:

  1. Symmetry Breaking: Standard "lifted" inference techniques, which speed up MLNs by exploiting symmetries, stop working when every rule has a unique weight.
  2. Search Space: The learning algorithm gets lost in a massive, high-dimensional parameter space, often failing to converge or taking days to run.

The SVMTied Approach

The authors propose a system called SVMTied. The core idea is to use a "dumb" but fast learner to guide a "smart" but slow one. The process follows these steps:

  1. Non-Relational Learning: They first treat the problem as a standard classification task, ignoring the relational dependencies. They train a multi-class SVM where each grounding of an untied formula is treated as a feature.
  2. Weight Initialization: The coefficients learned by the SVM serve as a "first guess" for what the MLN weights should be.
  3. Consistent Clustering: To reduce the number of parameters, they cluster groundings that have similar SVM weights. They use a joint clustering approach (tensor quantization) to ensure that the resulting "tied" formulas remain logically consistent across the database.
Dimensionality reduction via parameter clustering.
  1. Relational Fine-Tuning: Finally, they run a relational learner (like Tuffy) on this simplified, clustered MLN. Because the search space is smaller and the starting weights are already close to a good solution, the relational learner can efficiently capture the complex dependencies that the SVM missed.

Experimental Evaluation

The approach was evaluated on three classic relational benchmarks: WebKB (web page classification), Cora Entity Resolution, and Cora Information Extraction.

Key Results

The authors compared SVMTied against standard SVMs and "OrigTuffy" (the state-of-the-art MLN learner).

  • Accuracy: On the WebKB dataset, SVMTied achieved an F1-score of 0.84, compared to just 0.42 for a standard SVM. The original untied MLN (OrigTuffy) failed to finish within 24 hours.
  • Scalability: In Entity Resolution tasks, SVMTied outperformed "RandomizedTuffy" (which ties weights randomly) across all queries, showing that the way you group weights matters immensely.
  • Efficiency: SVMTied was significantly faster than randomized approaches. For example, on the Cora IE task, it reached a superior solution in 145 minutes, while the randomized version took over 300 minutes to reach a worse one.

Insights and Future Directions

The fundamental bet of this research is the "Similarity Assumption": if two features (like the words "neural" and "synapse") behave similarly in a simple non-relational model, they will likely have similar weights in a complex relational model. Beyond just saving time, tying weights for similar groundings acts as a form of regularization, preventing the model from overfitting noise in a single relational database instance.

Currently, the system requires manual selection of the number of clusters ($k$). Future work aims to automate the discovery of the optimal number of parameters and explore ways to learn the relational and non-relational models jointly rather than in a pipeline.

Summary updated

Abstract

Existing techniques for improving scalability of weight learning in Markov Logic Networks (MLNs) are typically effective when the parameters of the MLN are tied, i.e., several ground formulas in the MLN share the same weight. However, to improve accuracy in real-world problems, we typically need to learn separate weights for different groundings of the MLN. In this paper, we present an approach to perform efficient weight learning in MLNs containing high-dimensional, untied formulas. The fundamental idea in our approach is to help the learning algorithm navigate the parameter search-space more efficiently by a) tying together groundings of untied formulas that are likely to have similar weights, and b) setting good initial values for the parameters. To do this, we follow a hierarchical approach, where we first learn the parameters that are to be tied using a non-relational learner. We then use a relational learner to learn the tied-parameter MLN with initial values derived from parameters learned by the non-relational learner. We illustrate the promise of our approach on three different real-world problems and show that our approach yields much more scalable and accurate results compared to existing state-of-the-art relational learning systems.
BibTeX
@inproceedings{farabi2018efficient,
  author = {Khan Mohammad Al Farabi and Somdeb Sarkhel and Deepak Venugopal},
  title = {{Efficient Weight Learning in High-Dimensional Untied MLNs}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2018},
  url = {https://openreview.net/forum?id=QOp7c1cuFM},
}
Figure