Abstract
We introduce a nonparametric representation for graphical model on trees which expresses marginals as Hilbert space embeddings and conditionals as embedding operators. This formulation allows us to define a graphical model solely on the basis of the feature space representation of its variables. Thus, this nonparametric model can be applied to general domains where kernels are defined, handling challenging cases such as discrete variables whose domains are huge, or very complex, non-Gaussian continuous distributions. We also derive kernel belief propagation, a Hilbert-space algorithm for performing inference in our model. We show that our method outperforms state-of-the-art techniques in a cross-lingual document retrieval task and a camera rotation estimation problem.
Introduction
Probabilistic Graphical Models (PGMs) are a cornerstone of machine learning, providing a structured way to represent dependencies between variables. However, traditional PGMs often rely on restrictive assumptions: variables must either be discrete with a small number of states or follow simple parametric distributions like the Gaussian. In real-world applications—such as natural language processing, computer vision, or bioinformatics—data is frequently high-dimensional, non-Gaussian, or structured in ways that defy simple categorization.
This paper introduces Nonparametric Tree Graphical Models (NTGM) and the associated Kernel Belief Propagation (KBP) framework. By leveraging Reproducing Kernel Hilbert Space (RKHS) embeddings, the authors enable exact-style inference on tree-structured graphs for virtually any data type, provided a suitable kernel function can be defined.
Methods: Distribution-Free Inference
The core innovation lies in the nonparametric representation of probability distributions. Instead of explicitly modeling a density function $p(x)$, the distribution is mapped to a single point in a high-dimensional feature space, known as a "mean map."
- Embeddings as Proxies: A distribution becomes an element in an RKHS, allowing complex distributions to be handled as points in a vector space.
- Conditionals as Operators: Conditional distributions $p(y|x)$ are represented as linear operators. In this framework, applying a conditional distribution to a marginal distribution is reduced to a simple operator-vector multiplication.
- Kernel Belief Propagation (KBP): The classic "sum-product" algorithm is reformulated in the Hilbert space. The "sum" step becomes vector addition, and the "product" step involves element-wise multiplication of kernel weights.
Unlike traditional methods that require pre-defined potentials, KBP learns the model directly from training samples. This approach avoids the "exploding mixture" problem seen in previous nonparametric methods, where the complexity of messages grew exponentially. By using a fixed set of training samples as a basis, KBP maintains a compact and efficient representation.
Experimental Evaluation: Cross-lingual Document Retrieval
The authors evaluated NTGM on a challenging cross-lingual document retrieval task using the Europarl corpus. The goal was to retrieve a document in a target language given a query document in a source language, potentially passing through several intermediate languages in a chain or tree structure.
The model was tested across nine languages, including English, French, German, and Swedish. Because the state space of text documents is effectively infinite, this task perfectly highlights the strengths of a kernel-based nonparametric approach.
Key Results and Insights
The NTGM approach demonstrated significant performance gains over state-of-the-art baselines, such as Bilingual Topic Models (based on Latent Dirichlet Allocation).
Key findings include:
- Superior Retrieval: NTGM achieved much higher recall than topic models. While topic models struggled with the high-dimensional nature of the text, the kernel representation captured the underlying semantics more effectively.
- Robustness to Graph Depth: In chain-structured models, where information must pass through multiple nodes (languages), NTGM’s performance degraded much more slowly than competing methods.
- Linearizing the Non-linear: By moving to a high-dimensional Hilbert space, complex non-linear relationships between variables become linear operations, making the math of message passing cleaner and more efficient.
Limitations and Future Directions
While powerful, the current NTGM framework is limited to tree-structured graphs. Extending this to "Loopy KBP" for graphs with cycles is a primary area for future work. Additionally, the training phase involves $O(m^3)$ matrix inversions, where $m$ is the number of samples. While inference is a more manageable $O(m^2)$, scaling to massive datasets will require approximation techniques like Nyström methods or random Fourier features. Finally, as with all kernel methods, the choice of kernel and hyperparameter tuning remains a critical factor in performance.
Conclusion
Nonparametric Tree Graphical Models represent a significant step forward in making graphical models applicable to the "messy" data of the real world. By transforming probabilistic inference into linear algebra in a Hilbert space, KBP provides a robust, efficient, and theoretically sound framework for complex dependency modeling.
Summary updated