Learning Interpretable Relational Structures of Hinge-loss Markov Random Fields

Yue Zhang, Arti RameshIJCAI 2019 · DOI

TL;DR

This paper introduces A3SL, a novel deep reinforcement learning algorithm for automatically learning interpretable relational structures in Hinge-loss Markov Random Fields (HL-MRFs). By combining semantic constraints with data-driven exploration, A3SL learns models that are both understandable to humans and achieve strong predictive performance on complex real-world tasks like predicting alcohol recovery and detecting bullying.

What Problem Does This Paper Address?

Statistical relational models, such as Hinge-loss Markov Random Fields (HL-MRFs), are powerful tools for combining logic and uncertainty. They allow for the representation of complex relational dependencies using first-order logic clauses. However, manually defining the structure of these models (i.e., the clauses themselves) is a laborious and error-prone process. While existing methods can learn these structures from data, they often sacrifice interpretability for predictive accuracy, or vice-versa. This paper addresses the challenge of learning HL-MRF structures that are simultaneously interpretable, semantically meaningful, and performant, bridging the gap between human intuition and data-driven discovery.

Methods

The core of this work is the A3SL (Asynchronous Advantage Actor-Critic Structure Learning) algorithm. A3SL adapts the asynchronous advantage actor-critic (A3C) deep reinforcement learning framework to the problem of learning HL-MRF clause structures.

Here's a breakdown of the key methodological aspects:

  • Reinforcement Learning Formulation: The problem of learning HL-MRF structures is framed as a sequential decision-making process. An RL agent learns to construct clauses by sequentially adding predicates.
  • Asynchronous Advantage Actor-Critic (A3C): A3C is chosen for its ability to explore a large state space asynchronously and its scalability. This allows for parallel learning across multiple agents, speeding up the process and enabling diverse exploration.
  • Environment Definition: The "environment" for the RL agent consists of the set of available predicates (features, targets, and latent variables), the partially constructed clause, and the data.
  • State, Action, and Reward:
    • State: Represents the current set of partially or fully constructed clauses.
  • Action: Involves adding a new predicate to the current clause or signaling the end of a clause.
  • Reward: Is designed to balance predictive performance and interpretability. It's based on the HL-MRF's objective function, which includes a term for predictive accuracy (e.g., AUC-ROC) and penalty terms for deviations from semantic constraints and for clause complexity (length, number of clauses).
  • Semantic Constraints: A crucial innovation is the incorporation of domain-specific semantic constraints. These constraints guide the RL agent to learn clauses that align with human intuition and prior knowledge. For example, in modeling alcohol recovery, rules linking alcohol-related signals to relapse are encouraged.
  • Diversity Constraint: To encourage the learning of diverse models, an entropy prior is added to the policy gradient objective, promoting exploration and allowing domain experts to choose from a set of models with similar performance but different semantic interpretations.
  • HL-MRF Inference: The paper leverages the efficient inference capabilities of HL-MRFs, which is essential for the RL agent to receive rewards and update its policy.

Datasets

The paper evaluates A3SL on two real-world computational social science datasets:

  • Alcohol Use Disorder (AUD) Recovery Dataset: This dataset, previously used in [Zhang et al., 2018], contains tweets from users attending Alcoholics Anonymous, along with their friends' tweets, to predict recovery or relapse.
  • Formspring Dataset: This dataset, used for bullying detection, consists of messages from the Formspring social media platform.

Key Insights and Ideas

  • Bridging Interpretability and Performance: The most significant insight is that deep reinforcement learning, guided by semantic constraints, can effectively learn HL-MRF structures that are both highly interpretable and achieve state-of-the-art predictive performance. This addresses a long-standing trade-off in statistical relational learning.
  • Semantic Constraints as a Powerful Guide: Incorporating domain-specific "right reasons" or semantic constraints into the RL reward function is a key enabler for learning meaningful structures. This allows the model to go beyond purely data-driven pattern matching.
  • Latent Variable Discovery: A3SL demonstrates the ability to learn meaningful latent variables and their dependencies, which are crucial for capturing complex, underlying relationships in data that might not be directly observable.
  • Scalable Exploration for Diverse Models: The asynchronous nature of A3SL allows for extensive exploration of the clause space, leading to the discovery of multiple valid and diverse model structures, offering flexibility to domain experts.
  • Network Structure Learning: The algorithm effectively learns network rules that capture relationships between users and their friends, demonstrating its capability to model complex social interactions.

Key Results

  • Superior Predictive Performance: A3SL consistently outperformed baseline methods, including greedy structure learning, human-expert defined rules, and logistic regression, on both the AUD recovery and bullying detection tasks. For instance, in AUD recovery prediction, A3SL achieved an AUC-ROC of 0.8755, surpassing the human-expert model (0.8583) and Greedy-SL (0.8105).
  • Semantically Meaningful Structures: Qualitative analysis showed that A3SL learned clauses that align with human intuition and domain knowledge, often capturing nuanced relationships that were missed by simpler methods. For example, it learned rules combining alcohol and sober signals for AUD recovery prediction.
  • Improved Data Coverage for Network Rules: In the AUD recovery task, A3SL's learned network rules showed significantly higher instance coverage (average of ~200 instances) compared to human-expert rules (average of <30 instances), indicating better generalization to the data.
  • Stronger Latent Variable Correlations: In bullying detection, the latent variable learned by A3SL (intensity) showed consistently better correlation with the target variable (bullying) across cross-validation folds compared to human-designed rules.

Limitations and Future Work

  • Computational Cost: While A3SL is scalable due to its asynchronous nature, deep reinforcement learning can still be computationally intensive, especially for very large datasets or complex predicate sets.
  • Defining Semantic Constraints: The effectiveness of A3SL relies on the availability and quality of semantic constraints. For domains where such constraints are difficult to define, the algorithm might struggle to learn interpretable structures.
  • Future Work: The authors suggest exploring more sophisticated ways to incorporate domain knowledge and potentially developing methods for automatically discovering semantic constraints. Further research into optimizing the RL exploration strategy for even greater diversity and efficiency is also a promising direction. The paper also hints at the potential for A3SL to be applied to a wider range of complex relational learning problems.

Summary updated

BibTeX
@inproceedings{zhang2019learning,
  author = {Yue Zhang and Arti Ramesh},
  title = {{Learning Interpretable Relational Structures of Hinge-loss Markov Random Fields}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/838},
}
Figure