그래프 기반 준지도 학습에서 빠른 낮은 계수 표현 기반 그래프 구축 = Graph Construction Based on Fast Low-Rank Representation in Graph-Based Semi-Supervised Learning

다국어 초록 (Multilingual Abstract)

Low-Rank Representation (LRR) based methods are widely used in many practical applications, such as face clustering and object detection, because they can guarantee high prediction accuracy when used to constructing graphs in graph – based semi-supervised learning. However, in order to solve the LRR problem, it is necessary to perform singular value decomposition on the square matrix of the number of data points for each iteration of the algorithm; hence the calculation is inefficient. To solve this problem, we propose an improved and faster LRR method based on the recently published Fast LRR (FaLRR) and suggests ways to introduce and optimize additional constraints on the underlying optimization goals in order to address the fact that the FaLRR is fast but actually poor in classification problems. Our experiments confirm that the proposed method finds a better solution than LRR does. We also propose Fast MLRR (FaMLRR), which shows better results when the goal of minimizing is added.

국문 초록 (Abstract)

낮은 계수 표현(Low-Rank Representation, LRR) 기반 방법은 얼굴 클러스터링, 객체 검출 등의 여러 실제 응용에 널리 사용되고 있다. 이 방법은 그래프 기반 준지도 학습에서 그래프 구축에 사용할 경우 높은 예측 정확도를 확보할 수 있어 많이 사용된다. 그러나 LRR 문제를 해결하기 위해서는 알고리즘의 매 반복마다 데이터 수 크기의 정방행렬에 대해 특이값 분해를 수행하여야 하므로 계산 비효율적이다. 이를 해결하기 위해 속도를 향상시킨 발전된 LRR 방법을 제안한다. 이는 최근 발표된 Fast LRR(FaLRR)을 기반으로 하며, FaLRR이 속도는 빠르지만 실제로 분류 문제에서 성능이 낮은 것을 해결하기 위해 기반 최적화 목표에 추가 제약 조건을 도입하고 이를 최적화하는 방법을 제안한다. 실험을 통하여 제안 방법은 LRR 보다 더 좋은 해를 빠르게 찾아냄을 확인할 수 있다. 또한, 동일한 해를 도출하는 방법을 찾아내기는 어렵지만 최소화하는 목표가 추가될 경우 더 좋은 결과를 나타내는 Fast MLRR(FaMLRR)을 제안한다.

참고문헌 (Reference)

1 "http://www.cad.zju.edu.cn/home/dengcai/Data/d ata.html"

2 Z. Lin, "The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices"

3 G. Liu, "Robust subspace segmentation by low-rank representation" 663-670, 2010

4 L. Zhuang, "Non-negative low rank and sparse graph for semi-supervised learning" 2328-2335, 2012

5 D. Zhou, "Learning with local and global consistency" 16 (16): 321-328, 2004

6 X. Lu, "Graph-regularized low-rank representation for destriping of hyperspectral images" 51 (51): 4009-4018, 2013

7 R. Lin, "Fixed-rank representation for unsupervised visual learning" 598-605, 2012

8 S. Xiao, "FaLRR: A fast low rank representation solver" 4612-4620, 2015

9 Y. Peng, "Enhanced low- rank representation via sparse manifold adaption for semi-supervised learning" 65 : 1-17, 2015

10 R. P. Brent, "An algorithm with guaranteed convergence for finding a zero of a function" 14 (14): 422-425, 1971

11 J. F. Cai, "A singular value thresholding algorithm for matrix completion" 20 (20): 1956-1982, 2010