Learning Kolmogorov Models for Binary Random Variables

Hadi G. Ghauch, Mikael Skoglund, Hossein Shokri Ghadikolaei, Carlo Fischione, Ali H. SayedarXiv 2018 · arXiv

Introduction

Modern machine learning models, such as deep neural networks and standard matrix factorization, often function as "black boxes." While they achieve high predictive accuracy, they frequently fail to explain the underlying logic or the specific relationships between data points. This lack of interpretability is a significant hurdle in sensitive domains like medicine or finance, where understanding "why" a prediction was made is as important as the prediction itself.

This paper introduces a framework for learning Kolmogorov Models (KMs) for binary random variables. KMs bridge the gap between predictive power and interpretability by factorizing probabilities into a mixture of elementary events. This approach allows for the derivation of deterministic association rules—for example, "if a user likes Movie A, they must like Movie B"—providing a formal probabilistic grounding for "if-then" insights that methods like Non-negative Matrix Factorization (NMF) lack.

Methodology: The Kolmogorov Model

The authors model the probability of a binary outcome, such as a user liking a movie, as an inner product: $$P(X_{u,i} = 1) = \theta_u^T \psi_i$$ Where:

  • $\theta_u$ is a probability vector representing a user's profile (a mixture of "genres" or elementary events).
  • $\psi_i$ is a binary indicator vector representing which elementary events characterize an item.

Optimization via IKM

Because $\psi_i$ is binary, the learning problem is a "coupled combinatorial problem." To solve this, the authors developed the Iterative computation of KMs (IKM) algorithm, which utilizes Block-Coordinate Descent (BCD) to alternate between two steps:

  1. Refining the Profile ($\theta_u$): A convex quadratic problem solved using a low-complexity Frank-Wolfe algorithm.
  2. Refining the Indicator ($\psi_i$): An NP-hard discrete problem addressed via Semidefinite Relaxation (SDR).

The authors demonstrate that this relaxation is "quasi-optimal," meaning it closely approximates the exact solution as the model's dimensionality increases.

Figure 4: Convergence of the IKM algorithm compared to exhaustive search and Binary Matrix Factorization (BMF). The IKM approach closely matches the performance of the exhaustive search, validating the SDR relaxation.

Experimental Evaluation

The model was evaluated using the MovieLens 100K (ML100K) dataset, a standard benchmark for recommendation systems, and artificial data to validate convergence and optimality.

Key Results

The KM framework demonstrates that interpretability does not necessarily come at the cost of accuracy. On the ML100K dataset, the KM achieved competitive performance against established collaborative filtering methods.

Figure 6: Performance comparison (Normalized RMSE) on the MovieLens 100K dataset. The Kolmogorov Model (KM) outperforms several baselines, including NMF and SVD++, particularly as the latent dimension D increases.

Beyond accuracy, the model provides unique insights:

  • Deterministic Rules: If the "support" (active features) of one item is a subset of another, the model proves that a positive outcome for one deterministically implies the outcome for the other.
  • Influential Items: The model can identify "maximally influential" items—those that, if liked, imply a user will likely enjoy a large portion of the remaining catalog.
  • Generalization of K-Means: KM allows for "overlapping clusters," where an item can be characterized by multiple elementary events, unlike standard K-means which restricts items to a single cluster.

Conclusion and Future Work

The Kolmogorov Model offers a robust, interpretable alternative to traditional matrix factorization. While the current SDR step presents a computational bottleneck ($O(D^{4.5})$), the model's ability to extract deterministic rules from probabilistic data is a significant advancement. Future research will focus on scaling the algorithm to massive feature spaces and extending the model to handle time-varying data distributions.

Summary updated

BibTeX
@misc{ghauch2018learning,
  author = {Hadi G. Ghauch and Mikael Skoglund and Hossein Shokri Ghadikolaei and Carlo Fischione and Ali H. Sayed},
  title = {{Learning Kolmogorov Models for Binary Random Variables}},
  year = {2018},
  eprint = {1806.02322},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1806.02322},
}
Figure