nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Nyström Sketches

verfasst von : Daniel J. Perry, Braxton Osting, Ross T. Whitaker

Erschienen in: Machine Learning and Knowledge Discovery in Databases

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Despite prolific success, kernel methods become difficult to use in many large scale unsupervised problems because of the evaluation and storage of the full Gram matrix. Here we overcome this difficulty by proposing a novel approach: compute the optimal small, out-of-sample Nyström sketch which allows for fast approximation of the Gram matrix via the Nyström method. We demonstrate and compare several methods for computing the optimal Nyström sketch and show how this approach outperforms previous state-of-the-art Nyström coreset methods of similar size. We further demonstrate how this method can be used in an online setting and explore a simple extension to make the method robust to outliers in the training data.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

über 102.000 Bücher
über 537 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

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Learning Łukasiewicz Logic Fragments by Quadratic Programming

Nächstes Kapitel Crossprop: Learning Representations by Stochastic Meta-Gradient Descent in Neural Networks

Alaoui, A.E., Mahoney, M.W.: Fast randomized kernel methods with statistical guarantees. arXiv:1411.0306, 1–17 (2014)

Alzate, C., Suykens, J.A.K.: Kernel component analysis using an epsilon-insensitive robust loss function. IEEE Trans. Neural Netw. 19(9), 1583–1598 (2008)CrossRef

Calandriello, D., Lazaric, A., Valko, M.: Distributed adaptive sampling for kernel matrix approximation. In: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, vol. 54, pp. 1421–1429 (2017)

Chin, T.-J., Suter, D.: Incremental kernel principal component analysis. IEEE Trans. Image Process. 16(6), 1662–1674 (2007)MathSciNetCrossRef

Drineas, P., Mahoney, M.W.: On the Nyström method for approximating a gram matrix for improved kernel-based learning. J. Mach. Learn. Res. 6, 2153–2175 (2005)MathSciNetMATH

Fonollosa, J., Sheik, S., Huerta, R., Marco, S.: Reservoir computing compensates slow response of chemosensor arrays exposed to fast varying gas concentrations in continuous monitoring. Sens. Actuators B: Chem. 215, 618–629 (2015)CrossRef

Jolliffe, I.: Principal component analysis. Wiley Online Library, Hoboken (2002)MATH

Kwok, J.T.-Y., Tsang, I.W.: The pre-image problem in kernel methods. IEEE Trans. Neural Netw. 15(6), 1517–1525 (2004)CrossRef

Le, Q., Sarlós, T., Smola, A.: Fastfood-approximating kernel expansions in loglinear time. In: Proceedings of the International Conference on Machine Learning (2013)

10.

Lichman, M.: UCI machine learning repository (2013)

11.

Lopez-Paz, D., Sra, S., Smola, A., Ghahramani, Z., Schölkopf, B.: Randomized nonlinear component analysis. arXiv preprint arXiv:1402.0119 (2014)

12.

Ng, A.Y., Jordan, M.I., Weiss, Y., et al.: On spectral clustering: analysis and an algorithm. In: Advances in Neural Information Processing Systems, vol. 2, pp. 849–856 (2002)

13.

Ouimet, M., Bengio, Y.: Greedy spectral embedding. In: Proceeding of 10th International Workshop on Artificial Intelligence and Statistics, pp. 253–260. Citeseer (2005)

14.

Pearson, K.: Principal components analysis. London, Edinb. Dublin Philos. Mag. J. Sci. 6(2), 559 (1901)CrossRef

15.

Rahimi, A., Recht, B.: Random features for large-scale kernel machines. In: Advances in Neural Information Processing Systems, pp. 1177–1184 (2007)

16.

Rahimi, A., Recht, B.: Weighted sums of random kitchen sinks: replacing minimization with randomization in learning. In: Advances in Neural Information Processing Systems, pp. 1313–1320 (2009)

17.

Schölkopf, B., Mika, S., Smola, A., Rätsch, G., Müller, K.R.: Kernel PCA pattern reconstruction via approximate pre-Images. In: Niklasson, L., Ziemke, T. (eds.) ICANN 1998. Perspectives in Neural Computing, pp. 147–152. Springer, London (1998). https://doi.org/10.1007/978-1-4471-1599-1_18

18.

Schölkopf, B., Smola, A., Müller, K.-R.: Nonlinear component analysis as a kernel eigenvalue problem. Neural Comput. 10(5), 1299–1319 (1998)CrossRef

19.

Schubert, E., Zimek, A., Kriegel, H.-P.: Generalized outlier detection with flexible kernel density estimates. In: Proceedings of the 14th SIAM International Conference on Data Mining (SDM), Philadelphia, PA, pp. 542–550 (2014)

20.

Smola, A.J., Mangasarian, O.L., Schölkopf, B.: Sparse kernel feature analysis. In: Gaul, W., Ritter, G. (eds.) Classification, Automation, and New Media. Studies in Classification, Data Analysis, and Knowledge Organization, pp. 167–178. Springer, Heidelberg (2002). https://doi.org/10.1007/978-3-642-55991-4_18

21.

Smola, A.J., Schökopf, B.: Sparse greedy matrix approximation for machine learning. In: Proceedings of the 17th International Conference on Machine Learning, pp. 911–918. Morgan Kaufmann Publishers Inc., (2000)

22.

Snape, P., Zafeiriou, S.: Kernel-PCA analysis of surface normals for shape-from-shading. In: 2014 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1059–1066. IEEE (2014)

23.

Teixeira, A.R., Tomé, A.M., Stadlthanner, K., Lang, E.W.: KPCA denoising and the pre-image problem revisited. Digit. Sig. Process. 18(4), 568–580 (2008)CrossRef

24.

Tipping, M.E.: Sparse kernel principal component analysis. In: Advances in Neural Information Processing Systems, pp. 633–639 (2001)

25.

Wang, J., Lee, J., Zhang, C.: Kernel trick embedded Gaussian mixture model. In: Gavaldá, R., Jantke, K.P., Takimoto, E. (eds.) ALT 2003. LNCS (LNAI), vol. 2842, pp. 159–174. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-39624-6_14 CrossRef

26.

Williams, C., Seeger,M.: Using the Nyström method to speed up kernel machines. In: Proceedings of the 14th Annual Conference on Neural Information Processing Systems, number EPFL-CONF-161322, pp. 682–688 (2001)

27.

Wright, S.J., Nocedal, J.: Numerical optimization, vol. 2. Springer, New York (1999)MATH

28.

Xiao, Y., Wang, H., Wenli, X., Zhou, J.: L1 norm based KPCA for novelty detection. Pattern Recogn. 46(1), 389–396 (2013)CrossRefMATH

29.

Yang, T., Li, Y.-F., Mahdavi, M., Jin, R., Zhou, Z.-H.: Nyström method vs random fourier features: a theoretical and empirical comparison. In: Advances in Neural Information Processing Systems, pp. 476–484 (2012)

Titel: Nyström Sketches
verfasst von: Daniel J. Perry
Braxton Osting
Ross T. Whitaker
Verlag: Springer International Publishing
Buch: Machine Learning and Knowledge Discovery in Databases
Print ISBN: 978-3-319-71248-2

Electronic ISBN: 978-3-319-71249-9

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-71249-9_26

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"