Scalable Semi-Supervised Classification via Neumann Series

Chen Gong, Keren Fu, Lei Zhou, Jie Yang, Xiangjian He

Research output: Journal PublicationArticlepeer-review

2 Citations (Scopus)

Abstract

Traditional graph-based semi-supervised learning (GBSSL) algorithms usually scale badly due to the expensive computational burden. The main bottleneck is that they need to compute the inversion of a huge matrix. In order to alleviate this problem, this paper proposes Neumann series approximation (NSA) to explicitly approximate the inversion process required by conventional GBSSL methodologies, which makes them computationally tractable for relatively large datasets. It is proved that the deviation between the approximation and direct inversion is bounded. Using real-world datasets related to handwritten digit recognition, speech recognition and text classification, the experimental results reveal that NSA accelerates the speed significantly without decreasing too much precision. We also empirically show that NSA outperforms other scalable approaches such as Nyström method, Takahashi equation, Lanczos process based SVD and AnchorGraph regularization, in terms of both efficiency and accuracy.

Original languageEnglish
Pages (from-to)187-197
Number of pages11
JournalNeural Processing Letters
Volume42
Issue number1
DOIs
Publication statusPublished - 22 Aug 2015
Externally publishedYes

Keywords

  • Error bound
  • Neumann series
  • Scalability
  • Semi-supervised learning

ASJC Scopus subject areas

  • Software
  • Neuroscience (all)
  • Computer Networks and Communications
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Scalable Semi-Supervised Classification via Neumann Series'. Together they form a unique fingerprint.

Cite this