Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2017 Aug:70:3949-3957.

Latent Feature Lasso

Ian E H Yen  1 , Wei-Cheng Lee  2 , Sung-En Chang  2 , Arun S Suggala  1 , Shou-De Lin  2 , Pradeep Ravikumar  1
Affiliations

Latent Feature Lasso

Ian E H Yen et al. Proc Mach Learn Res. 2017 Aug.

Abstract

The latent feature model (LFM), proposed in (Griffiths & Ghahramani, 2005), but possibly with earlier origins, is a generalization of a mixture model, where each instance is generated not from a single latent class but from a combination of latent features. Thus, each instance has an associated latent binary feature incidence vector indicating the presence or absence of a feature. Due to its combinatorial nature, inference of LFMs is considerably intractable, and accordingly, most of the attention has focused on nonparametric LFMs, with priors such as the Indian Buffet Process (IBP) on infinite binary matrices. Recent efforts to tackle this complexity either still have computational complexity that is exponential, or sample complexity that is high-order polynomial w.r.t. the number of latent features. In this paper, we address this outstanding problem of tractable estimation of LFMs via a novel atomic-norm regularization, which gives an algorithm with polynomial run-time and sample complexity without impractical assumptions on the data distribution.

PubMed Disclaimer

Figures

Figure 1:
Figure 1:
The frequency of failures of condition in Theorem 4 out of 100 trials, for a spectrum of i.i.d. Bernoulli parameter p and different K. We use algorithm proposed in (Slawski et al., 2013) to check the condition efficiently.
Figure 2:
Figure 2:
From left to right, each column are results for Syn0 (K=4), Syn2 (K=14), Syn3 (K=35) and Syn1 (K=35) respectively. The first row shows the Hamming loss between the ground-truth binary assignment matrix Z∗ and the recovered ones Z^. The second row shows RMSE between Θ∗ = Z∗W∗ and the estimated Θ^=Z^W^.
Figure 3:
Figure 3:
From left to right are results for Tabletop, Mnist1k, YaleFace and Yeast, where Spectral Method does not appear in the plots for YaleFace and Yeast due to a much higher RMSE, and Variational method reports a runtime error when running on the YaleFace data set.
Figure 4:
Figure 4:
Sample images from the synthetic data we created (i.e. Syn1, Syn2, Syn3). The first row shows observations Xi,:, and the second row shows latent features Wk,:.
See this image and copyright information in PMC

References

    1. Airoldi Edoardo M, David Blei, Erosheva Elena A, and Fienberg Stephen E. Handbook of Mixed Membership Models and Their Applications. Chapman and Hall/CRC, 2014.
    1. Boumal Nicolas, Voroninski Vlad, and Bandeira Afonso. The non-convex burer-monteiro approach works on smooth semidefinite programs. In Advances in Neural Information Processing Systems, pp. 2757–2765, 2016.
    1. Broderick Tamara, Kulis Brian, and Jordan Michael I. Mad-bayes: Map-based asymptotic derivations from bayes. In ICML (3), pp. 226–234, 2013.
    1. Chandrasekaran Venkat, Recht Benjamin, Parrilo Pablo A, and Willsky Alan S. The convex geometry of linear inverse problems. Foundations of Computational mathematics, 12(6):805–849, 2012.
    1. d’Aspremont Alexandre, Ghaoui El, Laurent Jordan, Michael I, and Lanckriet Gert RG. A direct formulation for sparse pca using semidefinite programming. SIAM review, 49(3):434–448, 2007.

LinkOut - more resources