Energy-Based Learning for Cooperative Games, with Applications to Valuation Problems in Machine Learning

Yatao Bian, Yu Rong, Tingyang Xu, Jiaxiang Wu, Andreas Krause, Junzhou Huang

TL;DR

This paper introduces a novel energy-based framework for cooperative games, providing a unified probabilistic perspective on how we value individual contributions in machine learning. By treating player valuations as a mean-field variational inference problem, the authors show that classical metrics like the Shapley and Banzhaf values are actually "one-step" approximations of a more fundamental measure they call the Variational Index.

What Problem Does This Paper Address?

In machine learning, we often need to assign "value" to specific components. Which features were most important for this prediction? Which data points in the training set were most useful? Which models in an ensemble contribute the most?

These are typically modeled as cooperative games, where a set of "players" (features, data points, etc.) work together to produce a "payoff" (model accuracy, a specific prediction). The challenge is decoupling: players interact in complex, correlated ways, making it hard to isolate the importance of just one. While the Shapley value is the gold standard for this, it is computationally expensive and its theoretical motivations are purely axiomatic. This paper seeks a more principled, probabilistic foundation for these valuations.

Methods

The authors propose an Energy-Based Model (EBM) approach. They argue that the most "natural" probability distribution over coalitions of players is the one that maximizes entropy while matching the expected payoff—this leads directly to the Boltzmann distribution: $p(S) \propto \exp(F(S)/T)$, where $F(S)$ is the game's value function and $T$ is a temperature parameter.

Overview of the energy-based framework for cooperative games, showing how fixed-point iterations recover classical values and lead to the Variational Index.

To find individual player valuations, they perform mean-field variational inference. They approximate the complex, correlated distribution $p(S)$ with a simple, fully factorized distribution $q(S; \mathbf{x})$ where players are independent.

The "Aha!" Moment: The authors discover that if you start with a neutral initialization and perform just one step of a fixed-point iteration to maximize the ELBO (Evidence Lower Bound):

  • You recover the Banzhaf value if you initialize at a specific point.
  • You recover the Shapley value if you average the one-step results across a diagonal path.

By running this iteration to convergence (usually 5–10 steps), they arrive at the Variational Index, which represents the best possible independent approximation of the players' contributions.

Datasets

The researchers evaluated their framework on three types of valuation problems:

  1. Synthetic Submodular Games: Using Facility Location ID (FLID) objectives where ground-truth marginals can be calculated.
  2. Data Valuation: Using the Breast Cancer (569 samples) and Digits (1797 samples) datasets from the UCI repository to identify which training samples are most critical for model accuracy.
  3. Feature Attribution: Using the Adult Census dataset to explain the predictions of XGBoost, Logistic Regression, and MLP classifiers.

Key Insights and Ideas

  • Valuation as Decoupling: The paper reframes "importance" as a signal-processing problem. Assigning a single value to a player is essentially trying to find the best independent (decoupled) representation of a highly dependent system.
  • Classical Values are "Shallow": The revelation that Shapley and Banzhaf values are one-step approximations suggests they might not fully capture the "equilibrium" of player contributions in complex games.
  • Axiomatic Guarantee: Despite being derived from a probabilistic framework, the authors prove that their Variational Index still satisfies core game-theoretic axioms: Null Player (useless players get zero value), Symmetry (identical players get identical value), and Marginalism.
  • The Role of Temperature: The parameter $T$ acts as a "fairness" knob. High $T$ spreads importance evenly, while low $T$ concentrates it on the most dominant players.

Key Results

  • Lower Decoupling Error: The Variational Index consistently achieved lower KL-divergence (decoupling error) compared to Shapley and Banzhaf values across all synthetic tests.
  • Better Data Valuation: In "data removal" experiments (where you remove the most "valuable" data points to see how fast model accuracy drops), the Variational Index often induced a faster performance decline than classical methods, indicating it more accurately identified the most influential samples.
Data valuation results showing test accuracy decline as top-valued training data is removed. The Variational Index often induces a faster drop, indicating better identification of crucial samples.
  • Computational Efficiency: While the Variational Index requires multiple iterations, the authors introduced a "one-shot sampling trick" that allows it to be computed with a cost similar to the Banzhaf value.

Limitations and Future Work

  • Temperature Selection: The authors acknowledge that choosing the optimal temperature $T$ is currently empirical. Future work could explore automated ways to tune this parameter based on the specific game.
  • Efficiency vs. Fairness: There is an inherent tradeoff between how well a value decouples interactions and how "fairly" it treats players according to certain axioms (like the Efficiency axiom, which the Variational Index does not strictly satisfy by default).
  • Interactive Indices: The current work focuses on individual player values. The authors suggest extending this EBM framework to value groups of players (size-$k$ coalitions) to capture higher-order interactions.

Summary updated

Abstract

Valuation problems, such as feature interpretation, data valuation and model valuation for ensembles, become increasingly more important in many machine learning applications. Such problems are commonly solved by well-known game-theoretic criteria, such as Shapley value or Banzhaf value. In this work, we present a novel energy-based treatment for cooperative games, with a theoretical justification by the maximum entropy framework. Surprisingly, by conducting variational inference of the energy-based model, we recover various game-theoretic valuation criteria through conducting one-step fixed point iteration for maximizing the mean-field ELBO objective. This observation also verifies the rationality of existing criteria, as they are all attempting to decouple the correlations among the players through the mean-field approach. By running fixed point iteration for multiple steps, we achieve a trajectory of the valuations, among which we define the valuation with the best conceivable decoupling error as the Variational Index. We prove that under uniform initializations, these variational valuations all satisfy a set of game-theoretic axioms. We experimentally demonstrate that the proposed Variational Index enjoys lower decoupling error and better valuation performance on certain synthetic and real-world valuation problems.
BibTeX
@inproceedings{bian2022energy,
  author = {Yatao Bian and Yu Rong and Tingyang Xu and Jiaxiang Wu and Andreas Krause and Junzhou Huang},
  title = {{Energy-Based Learning for Cooperative Games, with Applications to Valuation Problems in Machine Learning}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=xLfAgCroImw},
}
Figure