Spectral Methods for Indian Buffet Process Inference
The Indian Buffet Process is a versatile statistical tool for modeling distributions over binary matrices. We provide an efficient spectral algorithm as an alternative to costly Variational Bayes and sampling-based algorithms. We derive a novel tensorial characterization of the moments of the Indian Buffet Process proper and for two of its applications. We give a computationally efficient iterative inference algorithm, concentration of measure bounds, and reconstruction guarantees. Our algorithm provides superior accuracy and cheaper computation than comparable Variational Bayesian approach on a number of reference problems.
Spectral methods are based on decomposing moment tensors.  If data are generated from latent variable models, their empirical moment tensors have a kind of (approximate) low-rank decomposition (approximate due to both noisy observations and finite sample estimation error in the empirical moments).  These decompositions can be computed from the moment tensors, e.g. using a kind of power iteration method on related (symmetrized) tensors.  The basic ideas of these spectral methods are fairly well established and many examples have been explored, especially in [6].This paper applies spectral fitting methods to data modeled as being generated from an IBP, including two common emission models (a linear gaussian model and a sparse factor analysis model, described in Section 2).  The main ingredients are a calculation of the appropriate moment tensors and corresponding symmetrized versions (Section 3), an application of the standard tensor power decomposition method (Section 4), and concentration proofs to offer recovery guarantees when data are generated from the model (Section 5).  There are also experiments (Section 6).The paper applies existing methodology and 'turns the crank' in the context of the IBP. While having such methods available for the IBP is interesting to the community, their development would fit better as an example in a paper like [6] than a full NIPS paper. Therefore the technical contribution and originality seem low.There could be contributions here that I'm not appreciating. For example, there could be substantial deviations from the standard machinery that are required, either for the algorithm or for the analysis in Section 5. In developing the algorithm, there is a need to use fourth-order moments (Section 3.1), though this doesn't seem like a significant leap. In the analysis of Section 5 the authors suggest (around line 281) that they provide a more general methodology for producing relevant concentration of measure bounds, but again it is not made clear whether this is a contribution of great originality or significance outside of the scope of this paper. If there are contributions in this paper that differentiate it from a 'turn the crank' application of standard machinery, the authors should highlight them in their response and clarify them in the text.The paper is decently written overall, though some points that seem relevant are not discussed. For example, Section 5 seems cut short and seems a bit disconnected from the rest of the paper. It could benefit substantially from more explicit connections back to the IBP. In addition, it could be made clear how the notion of concentration of measure interacts with the nonparametric generative model; does the size of K grow with the number of samples m? (The references [6,7] do not mention the Dirichlet process explicitly as far as I can tell, so I'm not sure if the nonparametric aspect of the story is made clear in some existing work without a more direct reference.) Also, does the notation for the number of samples switch between m and n in Sections 5.1 and 5.2?The experiments in Section 6 seem a bit weak. Both the first and second involve data that are essentially generated from the model (the first being synthetic data and the second being the IBP classic of objects-in-images) and therefore they don't shed much light on whether the method can perform well when data are not extremely close to following the model's assumptions, a question which seems especially relevant for spectral methods. In the short discussion of the third experiment, there isn't much to reveal the advantages and disadvantages of the proposed spectral algorithm over other algorithms. If the proposed method and analysis are essentially an application of existing machinery to the IBP, then experiments could provide a real contribution in shedding light on when spectral methods may be appropriate and when they may fail. But this experiments section does not provide such insight.Here are some miscellaneous points:- Since [6,7] don't mention the Dirichlet process explicitly (based on searching the text), the reference around line 38 seems strange.- Line 113 says all proofs are deferred to the appendix, but one proof remains in the paper.- The {0;1} on line 134 should probably be {0,1}, though that sentence could be revised for clarity.- The comment on line 142 that "[t]his is undesirable for the power method" could be clarified.- The plots in Figure 1 look like they were saved to a raster format, which makes them hard to read. The text and line sizes should probably be adjusted.- In Figure 3, was the MCMC algorithm stopped short at 1.72 seconds, or was there some reason to believe it was stuck in such a suboptimal mode?