Loading...

Efficient iterative Semi-Supervised Classification on manifold

Farajtabar, M ; Sharif University of Technology

1009 Viewed
  1. Type of Document: Article
  2. DOI: 10.1109/ICDMW.2011.181
  3. Abstract:
  4. Semi-Supervised Learning (SSL) has become a topic of recent research that effectively addresses the problem of limited labeled data. Many SSL methods have been developed based on the manifold assumption, among them, the Local and Global Consistency (LGC) is a popular method. The problem with most of these algorithms, and in particular with LGC, is the fact that their naive implementations do not scale well to the size of data. Time and memory limitations are the major problems faced in large-scale problems. In this paper, we provide theoretical bounds on gradient descent, and to overcome the aforementioned problems, a new approximate Newton's method is proposed. Moreover, convergence analysis and theoretical bounds for time complexity of the proposed method is provided. We claim that the number of iterations in the proposed methods, logarithmically depends on the number of data, which is a considerable improvement compared to the naive implementations. Experimental results on real world datasets confirm superiority of the proposed methods over LGC's default iterative implementation and the state of the art factorization method
  5. Keywords:
  6. Convergence analysis ; Iterative method ; Local and global consistency ; Manifold assumption ; Semi-supervised learning ; Factorization methods ; Global consistency ; Gradient descent ; Labeled data ; Large-scale problem ; Newton's methods ; Number of datum ; Number of iterations ; Real-world datasets ; Semi-supervised classification ; State of the art ; Theoretical bounds ; Time complexity ; Data mining ; Iterative methods ; Newton-Raphson method ; Supervised learning
  7. Source: Proceedings - IEEE International Conference on Data Mining, ICDM ; 2011 , Pages 228-235 ; 15504786 (ISSN); 9780769544090 (ISBN)
  8. URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6137384