[5-2] Graph-based SSL

그래프 기반의 준지도 학습은 주어진 데이터를 노드로 표현한다. Node : 데이터 / Edge 유사성으로 표현할 수 있습니다. 기본적인 가정을 그래프가 주어지고 이 그래프는 레이블이 있는 데이터와 없는 데이터로 구성됩니다. 강한 간선으로 연결되어 있으면 두 노드는 같은 레이블일 것이라고 가정합니다.

상대적인 유사성을 계산에서 에지는 Similarity Weight 가 되는 것이고, 이를 표현하기 위해 두가지를 사용합니다. k nearest neighbor 그래프는 k개까지 둘 사이의 거리를 1로 표시합니다. 엡실론 라디어스 그래프라는 것은 특정 노드 기준으로 일정 cut-off 이상으로 하는 노드들을 연결해줍니다.

k-nearest 는 객체 기준으로 밀도가 고려되지 못합니다. 반면에 엡실론 같은 경우 모든 객체가 연결되지 않을 수 있기 때문의 임의의 i 와 j 가 연결된다는 보장이 없어진다는 단점이 있습니다. 따라서 엡실론 그래프를 만든 후 레이블이 propagation 이 될수 있도록 만들어 주는 것이 일반적입니다.

간선이 크면 클 수록 같은 레이블이 될 가능성이 높아진다는 가정이 있습니다. 따라서 아래 그림에서 x3 은 x1 과의 가중치가 크므로 블루 레이블을 가질 가능성이 큽니다.

이를 최적화 문제로 풀이해보도록 하겠습니다.

y 는 0 또는 1의 값을 가지고 이를 minimize 해야합니다. 만약 큰 wij 라면 yi 와 yj가 같아야 되며, 이래야 로스함수가 커지지 않습니다. 작은 wij는 yi와 yj 가 레이블이 다를 수 있다는 가능성을 허용합니다. 이것은 최적식의 두번째 Term 으로 표현합니다. 이는 폴리노미얼 타임 안에 솔루션을 구할 수 있는 문제입니다.

Harmonic 함수는 에너지 함수를 최소화 하는 것으로 변환됩니다. 솔루션은 가우시안 램덤셋의 평균이 되기 때문에 모든 j 에 대해서 가중치의 평균을 분모화 합니다.

이 식을 그래프 라플라시안이 가지고 있는 성질을 통해서 다시 한번 살펴보도록 하겠습니다. W 는 n by n 행력이고 W 는 labeld된 데이터와 unlabel 된 데이터의 합입니다. 이 Degree Matrix 는 그래프 라플라시안 행렬을 만들어 낼 수 있는데, 두 사이의 노드가 연결되어 있으면 가중치는 1로 표현됩니다. 그래프 라플라시안은 D-W로 정의될 수 있습니다.

라플라시안으로 표현되었을 때, F 는 벡터이므로 추정된 레이블의 벡터와 그래프 라플라시안의 결합으로 표현이 됩니다.

라플라시안 행렬을 재배치 하여 델타 엘엘, 델타 엘유, 로 재배치 하면, f 에 대한 L 이 0이 되어야 합니다.

처음에는 모든 데이터에 대해서 레이블이 0,1만 허용하였지만 이를 harmonic function을 통해서 언레이블된 데이터 0 또는 1이 아닌 continuous 값을 허용하였습니다.

그래프 기반의 준지도 기법은 단어의 레이블을 매기고 싶은데 침대에서의 졸리다가 긍정이고, 영황에서의 졸리다가 부정인것처럼 도메인 마다 긍부정 레이블이 달라졌을 때, 그래프 상에서 label 을 propagation 시켜서 판단이 가능합니다.