Overview
Nonparametric latent feature models offer a flexible way to discover the hidden features underlying data without having to specify their number in advance. The Indian Buffet Process (IBP) is a popular example of such a model. However, inference in IBP-based models remains a significant challenge.
This paper introduces a beam search-based approach to find the Maximum A Posteriori (MAP) estimate for the IBP. By treating inference as a search problem rather than a sampling or optimization problem, the authors achieve significantly faster results than standard methods like Gibbs sampling while maintaining high accuracy in discovering latent features.
The Inference Bottleneck in the IBP
The Indian Buffet Process (IBP) is a powerful tool in non-parametric Bayesian statistics. Imagine a buffet with infinite dishes; each customer (data point) chooses a set of dishes (features). The IBP allows the model to determine the number of features ($K$) automatically from the data, rather than requiring the user to guess $K$ in advance.
However, the IBP has a major bottleneck: inference. Traditionally, researchers use Markov Chain Monte Carlo (MCMC) sampling, which is computationally expensive and slow to converge, or Variational Inference, which is faster but often gets stuck in local optima. In many real-world applications, we don't actually need the full posterior distribution; we just want the single "best" feature assignment matrix—the MAP estimate. This paper asks: if we only want the MAP, why not search for it directly?
A Beam Search Approach
The authors propose a Beam Search algorithm (similar to A* search) to find the MAP estimate of the latent feature matrix $Z$.
- The Search Space: The algorithm processes observations one by one. At each step, it explores possible feature assignments for the current observation, maintaining a "beam" of the top $b$ most promising candidate matrices.
- Scoring Function: To decide which candidates are "promising," the algorithm uses a scoring function that approximates the joint probability $P(Z, X)$. Since the algorithm only sees a subset of data at any given time, it must "look ahead" by upper-bounding the probability of the remaining, unseen data.
- Heuristics for the Likelihood: Upper-bounding the likelihood of future data is the hardest part. The authors propose three heuristics:
- Trivial: Ignores future data (admissible but loose).
- Inadmissible: A "greedy" look-ahead that assumes each future data point gets its own unique feature. While not a strict upper bound, it is computationally efficient and performs best in practice.
- Clustering-based: Uses a quick pre-clustering of the data to guess future feature assignments.
Key Insights and Ideas
- Search vs. Sampling: The core realization is that for many tasks, the "mode" (the most likely state) is sufficient. By framing inference as a search through a tree of binary assignments, the authors bypass the "random walk" inefficiencies of MCMC.
- The Power of Inadmissibility: In search theory, an "admissible" heuristic never overestimates the cost (or underestimates the probability). Surprisingly, the authors found that their inadmissible heuristic—which technically violates search theory guarantees—was the fastest and most effective at finding high-quality solutions.
- MAP as a "Warm Start": Even if you eventually want a full posterior distribution via MCMC, starting the sampler at the MAP estimate found by beam search leads to much faster convergence (mixing) than starting from a random initialization.
Key Results
The authors evaluated their approach on four distinct types of data: synthetic block-images, E-Coli gene expression data, sonar signals, and scene classification images.
- Speed: On the E-Coli dataset, the "Inadmissible" search found a solution in 10.3 seconds, compared to 49.8 seconds for Gibbs sampling.
- Accuracy: The search-based methods consistently recovered the correct number of latent features ($K=8$ for E-Coli), whereas Variational Inference struggled, often underestimating the number of features ($K=3$).
- Predictive Performance: In classification tasks (Sonar and Scene), the features found via beam search yielded SVM accuracies competitive with or superior to those found via Gibbs sampling, but in a fraction of the time.
Limitations and Future Work
- Combinatorial Explosion: While beam search limits the search space, the number of possible assignments for a new observation is $2^K$. If $K$ (the number of features) becomes very large, even a single step of the search becomes expensive. The authors suggest a "search-within-search" (expanding column-wise) as a potential fix.
- Fixed Hyperparameters: The current model assumes hyperparameters (like the IBP's $\alpha$) are fixed. Future work could involve integrating hyperparameter estimation into the search process.
- Non-Conjugate Models: The paper primarily focuses on "conjugate" cases where the feature effects ($A$) can be integrated out. For non-conjugate models, the search would need to explicitly track and optimize $A$ alongside $Z$.
Summary updated