그래프 기반 준지도 학습에서 빠른 낮은 계수 표현 기반 그래프 구축 및 꼭지점 중요도를 고려한 레이블 추론
Graph Construction Based on Fast Low-Rank Representation and Label Inference Considering Vertex Importance in Graph-Based Semi-Supervised Learning
- 주제(키워드) 도움말 준지도 학습 , 그래프 기반 준지도 학습 , 그래프 구축 , 레이블 추론 , 낮은 계수 표현 , 꼭지점 중요도 , 이미지 분류 , Semi-supervised learning , Graph-based semi-supervised learning , Graph construction , Label inference , Low-rank representation , Vertex importance , Image classification
- 발행기관 서강대학교 일반대학원
- 지도교수 양지훈
- 발행년도 2016
- 학위수여년월 2016. 2
- 학위명 박사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/sogang/000000059039
- 본문언어 한국어
- 저작권 서강대학교 논문은 저작권보호를 받습니다.
초록/요약
준지도 학습은 기계 학습의 한 분야로서, 레이블된 데이터와 레이블되지 않은 데이터 모두를 사용하여 모델을 학습한다. 이 방법은 여러 준지도 학습 가정을 사용하여 레이블되지 않은 데이터로부터 유용한 정보를 알아냄으로써, 레이블된 데이터만 사용하는 지도 학습에 비해 예측 정확도를 높일 수 있다. 특히 그래프 기반 준지도 학습은, 다른 준지도 학습에 비해 높은 예측 정확도 및 여러 장점으로 인하여 최근 많은 주목을 받고 있다. 일반적으로 그래프 기반 준지도 학습은 입력 데이터를 그래프의 형태로 변환하는 그래프 구축 단계와, 구축된 그래프를 입력으로 하여 레이블을 예측하는 레이블 추론 단계로 나뉜다. 그래프 구축을 위해서는 k-최근접 이웃 방법을 가장 많이 사용하지만, 최근 특징 선택 및 차원 축소, 다양체 학습, 낮은 계수 표현 등을 활용한 여러 연구가 발표되고 있다. 레이블 추론은 준지도 학습에서 가장 핵심이 되는 가정인 평활도 가정을 기반으로 하며, 더 높은 정확도를 달성하기 위한 다양한 방법이 연구되어 왔다. 따라서 본 논문은 그래프 기반 준지도 학습 알고리즘의 두 단계에서 기존 연구보다 발전된 방법을 제안하는 것에 중점을 둔다. 그래프 구축에서는 최근 여러 분야에서 널리 사용되는 낮은 계수 표현 기반 방법이 가진 단점인 높은 계산 복잡도를 해결하는 방법에 대하여 살펴보고, 계산 복잡도를 낮추면서도 더욱 더 예측 정확도를 높인 새로운 빠른 낮은 계수 표현 방법 및 그래프 구축 알고리즘을 제안한다. 그리고 레이블 추론에서는 기존 방법에 각 꼭지점 중요도를 결합함으로써 성능을 더욱 향상시키는 개선된 레이블 추론 방법을 제안한다. 이를 위하여 추론 과정에서 각 꼭지점이 학습에 미치는 영향을 조정할 수 있게 함으로써 그래프에서 추론을 불확실하게 만드는 꼭지점들의 중요도를 상대적으로 낮춘다. 본 논문에서 제안하는 그래프 구축 방법은, 높은 정확도로 각광받고 있지만 계산 복잡도가 높아서 큰 데이터에 사용하기 어려운 낮은 계수 표현 기반 방법의 단점을 보완함으로써, 이 방법을 기반으로 하여 데이터를 변환하는 여러 실제 응용 분야(이미지 및 영상 분류, 복원 등) 및 준지도 학습 연구에 널리 활용될 수 있다. 그리고 제안하는 레이블 추론 방법은 널리 사용되는 추론 알고리즘들 및 최신 추론 알고리즘의 예측 정확도를 안정적으로 향상시킬 수 있으므로, 관련 분야에서 널리 활용될 수 있을 것이라 기대된다.
more초록/요약
Semi-supervised learning is an area of machine learning that employs both labeled and unlabeled data in order to train a model. This method has the potential to improve prediction performance when compared to supervised learning by making use of some assumptions in semi-supervised learning that enable us to pick out useful information in unlabeled data. In particular, graph-based semi-supervised learning has recently come into focus with its high accuracy of prediction and several advantages when compared to other semi-supervised techniques. In general, graph-based semi-supervised learning consists of two phases: graph construction, which converts the input data into a graph, and label inference, which predicts the appropriate labels for unlabeled data using the constructed graph. k-Nearest Neighbor is the most commonly used method for graph construction, but much study is being given to graph construction utilizing feature selection, dimensionality reduction, manifold learning, low-rank representation, and so on. Label inference is mainly based on the smoothness assumption which is the core of semi-supervised learning, and there have been many studies for better models to accomplish high accuracy. Therefore, this dissertation puts an emphasis on presenting improved methods for the two phases of graph-based semi-supervised learning, as compared to the conventional approaches. For graph construction, we first study the means for solving the problem of high computational complexity and the inherent weakness of low-rank representation, which is a widely used method in many fields. We then propose a novel fast low-rank representation method and related graph construction method to achieve lower computational complexity and higher accuracy of prediction. For label inference, we propose an enhanced label inference method for improving performance by incorporating the importance of each vertex in the existing methods. For this, we lower the importance of vertices that make an inference unclear on a graph by allowing for the adjustment of the influence each vertex has on learning in the inference procedure. The graph construction method proposed in this dissertation makes up for the weakness of high computational complexity in low-rank representation, which causes difficulty in use for large datasets, and could be widely used as a data transformation method in various fields of real applications (classification or reconstruction of images/videos) and for research into semi-supervised learning. And the proposed method of label inference has the capacity to stably improve the prediction accuracy of conventional widely used inference methods and the state-of-the-art inference method, allowing it to be widely applicable in related fields.
more