[semi-supervised learning] basic assumption

이 포스팅에는 semi-supervised learning이 동작하는데 필요한 전제 조건 또는 가정에 대해 정리한다.
내용은 mit press semi supervised learning을 참고 했다.

semi supervised learning을 왜 사용하는가?
semi-supervised learning의 주목적은 단순한 질문에서 시작된다.

"label이 존재하는 데이터만 사용하는 것과 비교했을때 unlabeled data points를 이용해 더 정확한 예측을 할수 있을까?"

이론적으로 답은 당연히 "yes"이다.  다만 여기엔 전제 조건이 있고 지금 부터 그 전제 조건들을 정리해보자.

수학적으로 위 문장을 표현해 보자면 unlabeled data로 부터 얻은 random variable x에 대한 지식 $p(x)$가 조건부 확률 $p(y|x)의 추정에 도움이 될때 semi-supervised learning은 효과가 있다.  이 전제가 깨지면 semi-supervised learning은 의미가 없다.

Semi-supervised smoothness assumption

if two points $x_{1}, x_{2}$ in a high-density region are close, then so should be the corresponding outputs $y_{1}, y_{2}$ 

말인 즉 "데이터 x_{1}, x_{2}가  데이터 공간상에서 가까운 거리에 있다면 그 대응 되는 출력(outputs이라고 되어 있는데 예측(=prediction) 값을 말한다)도 예측 공간상에서 가까운 거리에 위치 해야 한다"는 의미이다.

다른 말로 하면 비슷한 입력에 대해 비슷한 출력을 갖는다는 것이다. 즉, 데이터 공간에서 인접한 점들은 유사한 레이블을 갖는 경향이 있다는 것이다.

Smoothness assumption은 레이블이 없는 데이터를 활용하여 결정 경계(decision boundary)를 부드럽게 만드는 데 도움을 준다. 즉, 레이블이 있는 데이터에 대한 정보를 기반으로 레이블이 없는 데이터를 예측하는 과정에서, smoothness assumption에 따라 이웃하는 데이터의 레이블 정보를 활용하여 결정 경계를 조정하거나 보완하는 것이다

 

Cluster assumption

If points are in the same cluster, they are likely to be of the same class

데이터가 같은 클러스터에 속한다면 같은 클래스에 속할 것이다. 라는 뜻으로 매우 합리적으로 보인다.
이 가정이 어떻게 semi-supervised learning을 지지하는 가정일까?
입력 데이터가 데이터 공간에서 cluster를 형성한다고 가정해 보자. 그렇다면 입력 데이터 공간에서 clustering 알고리즘을 이용해 cluster를 분리 하고 labeled data를 이용해 각 cluster에 class를 부여 할 수 있다. 이 과정에서 데이터 공간상의 unlabeled data를 이용한다면 각 cluster의 경계를 더 잘 구분할 수 있을 것이다. 왜냐면 unlabeled data까지 활용 한다면 각 cluster에 속한 데이터의 분포를 더 정확히 추정할 수 있고 이는 곳 더 정확한 cluter 사이의 경계 추정을 할 수 있다는 의미 이기 때문이다.

여기서 한 가지  당연한 질문을 생각 할 수 있는데 "그럼 클러스터의 경계는 어디에 형성되는가?" 이다.  
답은 "Low density region"이다.

Low density separation: The decision boundary should lie in a low-density region.
클러스터를 나누는 경계는 low-density 영역에 있어야 한다 는 말로 이는 cluster assumption과 동일한 의미로 받아 들일 수 있다.
왜 동일 한 의미로 받아 들일 수 있을까?
  low density separation을 부정해 보자. (엄격한 의미에서 논리 학적인 부정은 아닐 것 같다 더 잘 아시는 분이 있다면 댓글로 이 연결고리를 완성시켜 주시면 좋겠다.)
  결정경계(decision boundary)가 high-density 영역에 놓인다면 결정 경계는 같은 클러스터에 속한 데이터를 서로 다른 class로 분류 하게 된다. 이는 같은 클러스터에 속한 데이터는 같은 클래스를 갖을 것이라는 cluster assumption을 부정 하게 되므로 하나를 부정하면 다른 하나도 부정되기 때문에 같은 말의 다른 표현이라고 할 수 있다.

smoothness assumption 과 cluster assumption의 차이
1. smoothness assumption은 입력 공간에서 인접한 데이터가 대체로 비슷한 출력을 갖는 경향이 있다는 가정이고 cluster assumption은 입력 공간에서 데이터 들이 군집(cluster)을 이루는 경향이 있다는 것이다.
2. smoothness assumption을 이용하면 레이블이 없는 데이터의 출력을 결정하기 위해 이웃하는 레이블이 있는 데이터를 활용할 수 있다.
3. cluster assumption을 이용 하면 레이블이 없는 데이터의 클래스를 결정하기 위해 주변 군집의 정보를 활용할 수 있다.

위 말을 자세히 보면 smoothness assumption은 입력 데이터의 관계와 출력 데이터의 관계가 서로 유사할 것이다 라고 만 말하고 있지 서로 다른 둘을 어떻게 분류 할지에 대한 정보는 담고 있지 않다.
반면 cluster assumption을 서로 다른 둘을 어떻게 분류 할수 있는지에 대한 가정을 담고 있다.

Manifold assumption

The high-dimensional data lie on a low-dimensional manifold

Manifold란 데이터의 내재된 구조를 나타내는 개념이다. 유사하게 데이터가 고차원에 존재할 경우
manifold란 데이터가 실재로 존재하는 저차원 하위 공간(subspace)을 나타 낼 수도 있다.
Manifold learning이란 고차원 데이터를 저차원 manifold 공간으로 맵핑 하는 방법을 의미한다.

manifold assumption은 semi-supervised에서 왜 중요한가?  
high dimensional data의 문제는 연산량 증가, pairwise distance가 유사해 지며 데이터가 자체의 특성이 가려지는 문제 등이다. manifold는 그 개념 자체가 데이터의 내재된 구조, 그 구조를  잘 나타내는 저차원 공간을 나타내기 때문에 manifold에서 density와 distance등을 이용해 데이터 분포를 더 잘/쉽게 표현할 수 있다. 데이터 분포를 더 잘 표현 할 수 있으면 당연히 분포 모델링도 쉬워질 수 있다.

Transduction

transduction을 설명 하기 위해 induction을 먼저 설명해야 할거 같다.
induction이란 귀납적 인것이다. 이는 supervised learing의 기저에 깔린 개념으로 특수한 케이스(학습 데이터 셋)와 그 라벨을 아는 상태에서 입력 데이터와 출력 라벨의 관계를 설명하는 일반적 규칙을 학습하는 것을 목표로 한다. 그 후 학습한 규칙을 unlabeled data에 대입해 label을 추론 한다.

transduction은 학습 과정에서 모든 관측치를 다 사용 한다. 즉 라벨이 있는 관측치든 없는 관측치든 모두 사용 하는 것이다. 모든 관측치를 사용해 공통된 특징, 패턴, 연관관계 등을 학습해 당장 풀고자 하는 목표 문제의 해답만을 찾는 것을 목표로 한다. 즉 일반적인 규칙을 학습하고자 하는 것이 아니다.

 

transduction 에 대한 개인 적인 의견 
이렇게만 설명되어 있는 글들을 보다 보니 생긴 의문이 그럼 transduction은 너무 한정적인것 아닌가? 였다.
하지만 이는 transduction의 개념일 뿐이다. 어떤 것을 정의 하는 개념과 그것의 특성을 어떻게 사용(application) 할 것인지는 전혀 다른 얘기다. transduction이 unlabeled data를 포함한 사용 할 수 있는 모든 관측치를 이용해 당장 해결하고자하는 문제, 예를 들어 classification,의 최적 답을 찾고자 하는 개념이라면 이 문제를 푸는 과정에서 transduction의 개념을 이용하는 알고리즘은 앞서 말했듯이 labeled data와 unlabeled data 모두를 이용해 그들의 공통적인 성질, 특성등 즉 representation을 추출할 수 있다는 말과도 같을 것이다. 이 특성을 활용 하면 semi-supervised learning에서 transduction의 개념을 차용 할 수 있다.  

(mit press의 semi-supervised learning에서는 transduction과 semi-supervised learning을 동일 한 것으로 보지 않는데 다른 책 또는 블로그에서는 transductive learning = semi-supervised learning이으로 용어를 정의해 설명하기도 해서 서로 다른 책과 블로그에서 설명이 약간 다를 수 있다.)