Skip to main content
main-content
Top

Hint

Swipe to navigate through the chapters of this book

2019 | OriginalPaper | Chapter

TopSpin: TOPic Discovery via Sparse Principal Component INterference

Authors: Martin Takáč, Selin Damla Ahipaşaoğlu, Ngai-Man Cheung, Peter Richtárik

Published in: Modeling and Optimization: Theory and Applications

Publisher: Springer International Publishing

share
SHARE

Abstract

We propose a novel topic discovery algorithm for unlabeled images based on the bag-of-words (BoW) framework. We first extract a dictionary of visual words and subsequently for each image compute a visual word occurrence histogram. We view these histograms as rows of a large matrix from which we extract sparse principal components (PCs). Each PC identifies a sparse combination of visual words which co-occur frequently in some images but seldom appear in others. Each sparse PC corresponds to a topic, and images whose interference with the PC is high belong to that topic, revealing the common parts possessed by the images. We propose to solve the associated sparse PCA problems using an Alternating Maximization (AM) method, which we modify for the purpose of efficiently extracting multiple PCs in a deflation scheme. Our approach attacks the maximization problem in SPCA directly and is scalable to high-dimensional data. Experiments on automatic topic discovery and category prediction demonstrate encouraging performance of our approach. Our SPCA solver is publicly available.

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 15 Tage kostenlos.

Footnotes
2
A simple scaling argument shows that the solution must satisfy \(\Vert x\Vert _2= 1\).
 
Literature
1.
go back to reference Bart, E., Porteous, I., Perona, P., Welling, M.: Unsupervised learning of visual taxonomies. In: CVPR (2008) Bart, E., Porteous, I., Perona, P., Welling, M.: Unsupervised learning of visual taxonomies. In: CVPR (2008)
2.
go back to reference Blei, D.M., Griffiths, T.L., Jordan, M.I., Tenenbaum, J.B.: Hierarchical topic models and the nested Chinese restaurant process. In: NIPS (2004) Blei, D.M., Griffiths, T.L., Jordan, M.I., Tenenbaum, J.B.: Hierarchical topic models and the nested Chinese restaurant process. In: NIPS (2004)
3.
go back to reference Blei, D.M., McAuliffe, J.: Supervised topic models. In: NIPS (2007) Blei, D.M., McAuliffe, J.: Supervised topic models. In: NIPS (2007)
4.
go back to reference Blei, D.M., Ng, A.Y., Jordan, M.I.: Latent dirichlet allocation. J. Mach. Learn. Res. 3, 993–1022 (2003). Mar MATH Blei, D.M., Ng, A.Y., Jordan, M.I.: Latent dirichlet allocation. J. Mach. Learn. Res. 3, 993–1022 (2003). Mar MATH
5.
go back to reference d’Aspremont, A., Bach, F., Ghaoui, L.E.: Optimal solutions for sparse principal component analysis. J. Mach. Learn. Res. 9, 1269–1294 (2008) MathSciNetMATH d’Aspremont, A., Bach, F., Ghaoui, L.E.: Optimal solutions for sparse principal component analysis. J. Mach. Learn. Res. 9, 1269–1294 (2008) MathSciNetMATH
6.
go back to reference d’Aspremont, A., Ghaoui, L.E., Jordan, M.I., Lanckriet, G.R.G.: A direct formulation for sparse PCA using semidefinite programming. SIAM Rev. 48(3), 434–448 (2007) MathSciNetCrossRef d’Aspremont, A., Ghaoui, L.E., Jordan, M.I., Lanckriet, G.R.G.: A direct formulation for sparse PCA using semidefinite programming. SIAM Rev. 48(3), 434–448 (2007) MathSciNetCrossRef
7.
go back to reference Fei-Fei, L., Fergus, R., Perona, P.: Learning generative visual models from few training examples: an incremental bayesian approach tested on 101 object categories (2004) Fei-Fei, L., Fergus, R., Perona, P.: Learning generative visual models from few training examples: an incremental bayesian approach tested on 101 object categories (2004)
8.
go back to reference Grauman, K., Darrell, T.: Unsupervised learning of categories from sets of partially matching image features. In: CVPR (2006) Grauman, K., Darrell, T.: Unsupervised learning of categories from sets of partially matching image features. In: CVPR (2006)
9.
go back to reference Journée, M., Nesterov, Y., Richtárik, P., Sepulchre, R.: Generalized power method for sparse principal component analysis. J. Mach. Learn. Res. 11, 517–553 (2010) MathSciNetMATH Journée, M., Nesterov, Y., Richtárik, P., Sepulchre, R.: Generalized power method for sparse principal component analysis. J. Mach. Learn. Res. 11, 517–553 (2010) MathSciNetMATH
10.
go back to reference Kinnunen, T., Kamarainen, J.-K., Lensu, L., Kalviainen, H.: Unsupervised visual object categorisation via self-organisation. In: ICPR (2010) Kinnunen, T., Kamarainen, J.-K., Lensu, L., Kalviainen, H.: Unsupervised visual object categorisation via self-organisation. In: ICPR (2010)
11.
go back to reference Lowe, D.: Object recognition from local scale-invariant features. In: ICCV (1999) Lowe, D.: Object recognition from local scale-invariant features. In: ICCV (1999)
12.
go back to reference Mackey, L.: Deflation methods for sparse PCA. In: NIPS (2008) Mackey, L.: Deflation methods for sparse PCA. In: NIPS (2008)
13.
go back to reference Naikal, N., Yang, A., Sastry, S.: Towards an efficient distributed object recognition system in wireless smart camera networks. In: International Conference on Information Fusion (2010) Naikal, N., Yang, A., Sastry, S.: Towards an efficient distributed object recognition system in wireless smart camera networks. In: International Conference on Information Fusion (2010)
14.
go back to reference Naikal, N., Yang, A.Y., Shankar Sastry, S.: Informative feature selection for object recognition via sparse PCA. In: ICCV (2011) Naikal, N., Yang, A.Y., Shankar Sastry, S.: Informative feature selection for object recognition via sparse PCA. In: ICCV (2011)
15.
go back to reference Nister, D., Stewenius, H.: Scalable recognition with a vocabulary tree. In CVPR (2006) Nister, D., Stewenius, H.: Scalable recognition with a vocabulary tree. In CVPR (2006)
16.
go back to reference Richtárik, P., Takáč, M., Ahipasaoglu S.D.: Alternating maximization: unifying framework for 8 sparse PCA formulations and efficient parallel codes (2012). arXiv:​1212.​4137 Richtárik, P., Takáč, M., Ahipasaoglu S.D.: Alternating maximization: unifying framework for 8 sparse PCA formulations and efficient parallel codes (2012). arXiv:​1212.​4137
17.
go back to reference Sivic, J., Russell, B.C., Zisserman, A., Freeman, W.T., Efros, A.A.: Unsupervised discovery of visual object class hierarchies. In: CVPR (2008) Sivic, J., Russell, B.C., Zisserman, A., Freeman, W.T., Efros, A.A.: Unsupervised discovery of visual object class hierarchies. In: CVPR (2008)
18.
go back to reference Sivic, J., Zisserman, A.: Video google: a text retrieval approach to object matching in videos. In: ICCV (2003) Sivic, J., Zisserman, A.: Video google: a text retrieval approach to object matching in videos. In: ICCV (2003)
19.
go back to reference Tuytelaars, T., Lampert, C.H., Blaschko, M.B., Buntine, W.: Unsupervised object discovery: a comparison. IJCV 88(2) (2010) Tuytelaars, T., Lampert, C.H., Blaschko, M.B., Buntine, W.: Unsupervised object discovery: a comparison. IJCV 88(2) (2010)
20.
go back to reference J. Zhang, M. Marszalek, S. Lazebnik, and C. Schmid. Local features and kernels for classification of texture and object categories: a comprehensive study. IJCV (2007) J. Zhang, M. Marszalek, S. Lazebnik, and C. Schmid. Local features and kernels for classification of texture and object categories: a comprehensive study. IJCV (2007)
21.
go back to reference Zhang, Y., Ghaoui, L.E.: Large–scale sparse principal component analysis with application to text data. In: NIPS (2011) Zhang, Y., Ghaoui, L.E.: Large–scale sparse principal component analysis with application to text data. In: NIPS (2011)
22.
go back to reference Zou, H., Hastie, T., Tibshirani, R.: Sparse principal component analysis. Technical report, Stanford University (2004) Zou, H., Hastie, T., Tibshirani, R.: Sparse principal component analysis. Technical report, Stanford University (2004)
Metadata
Title
TopSpin: TOPic Discovery via Sparse Principal Component INterference
Authors
Martin Takáč
Selin Damla Ahipaşaoğlu
Ngai-Man Cheung
Peter Richtárik
Copyright Year
2019
DOI
https://doi.org/10.1007/978-3-030-12119-8_8

Premium Partner