[논문리뷰/설명] Learning with Local and Global Consistency

현재 진행하고 있는 연구에서 활용하고 있는 데이터의 약 80%가 레이블이 없습니다. 이렇게 일부만 레이블이 있는 데이터를 활용하여 학습모델을 만드는 것을 Semi-supervised learning, 준지도학습이라고 합니다.

 

이번 논문 Learning with Local and Global Consistency는 데이터로부터 그래프 구조를 도출하고, 이를 바탕으로 준지도학습을 통해 레이블이 없는 데이터의 레이블을 예측합니다.  

 

특히, 이미 레이블이 있는 데이터로부터 레이블이 없는 데이터를 예측한다고 하여 Label propagation 방법으로도 불립니다.

 

시작하겠습니다!

 

논문링크: https://proceedings.neurips.cc/paper/2003/hash/87682805257e619d49b8e0dfdc14affa-Abstract.html

Learning with Local and Global Consistency

 

 

 

 

 Introduction

 

준지도학습의 기본 가정은 consistency 입니다. consistency는 두 가지 의미가 있습니다.

 

• 가까운 점들은 같은 레이블을 가져야 한다 (local consistency)
• 같은 구조(클러스터 또는 매니폴드)에 있는 점들은 같은 레이블을 가져야 한다 (global consistency)

 

consistency의 두 가지 의미를 직관적으로 살펴보기 위해 아래 예시를 살펴봅시다.

 

 

논문에서는 위의 활 모양을 moon으로 표현했습니다. 위의 데이터는 두 개의 moon 구조가 있는데, 우측 하단 그래프(Ideal Classification)처럼 분류되는 것이 가장 이상적입니다. Ideal Classification에서는 가까운 점들은 같은 레이블을 가지고 있고, 같은 구조(moon)에 있는 점들 또한 같은 레이블을 가지고 있습니다. 

 

본 논문에서 제시하는 Local and Global Consistency (LGC)는 두 consistency를 모두 만족하는 방법을 제시합니다. 논문에서는 이를 만족하기 위해 충분히 "smooth"한 분류함수를 만들어야한다고 언급하고 있는데, 위의 그림에서 SVM, k-NN의 예시처럼 데이터를 robust하게 분류하는 것이 아니라, 데이터의 분포로부터 내재적인 구조를 반영해야 한다는 의미로 받아들이면 될 것 같습니다. LGC는 이러한 "smooth"한 분류함수를 만드는 iteration 알고리즘을 제시합니다. 이어서 이 알고리즘이 어떻게 구성되었고 작동하는지 살펴봅시다.

 

 

 

 

 Algorithm

Notation

데이터셋 $\mathcal{X} = \left\{ x_1, \cdots, x_l, x_{l+1}, \cdots, x_n \right\} \subset \mathbb{R}^m$

레이블셋 $\mathcal{L} = \left\{ 1, \cdots, c \right\}$

분류모델 $F = \left[ F_1^T, \cdots, F_n^T \right]^T$, $F: \mathcal{X} \to \mathbb{R}^c$

 

• $x_l$까지는 레이블이 달린 데이터, 그 다음부터는 레이블이 없는 데이터 $x_u$ ($l+1 \le u \le n$)
• $x_i$의 레이블 $y_i \in \mathcal{L}$
• $y_i = \text{argmax}_{j \le c} F_{ij}$
• $Y$: $n \times c$ matrix, $Y_{ij} = 1$ if $y_i = j$ and $Y_{ij} = 0$ otherwise.

 

Algorithm

1. 그래프 구조를 나타내는 행렬 $W$를 정의. $W_{ij}$ 값이 클수록, $x_i, x_j$가 서로 관계된 정도가 높다. $W_{ii}=0$
   어떤 그래프를 정의할지는 사용자가 결정할 수 있고, 목적에 따라 그래프의 종류는 바뀔 수 있다.
2. 정의한 그래프 행렬 $W$를 정규화(normalize)하기 위해 $S = D^{-1/2}WD^{-1/2}$를 구성한다.
   $D$는 $D_{ii} = \sum_{j} W_{ij}$인 대각행렬이다.
3. $F(t+1) = \alpha SF(t) + (1 - \alpha)Y$를 수렴할 때까지 반복한다. $\alpha$는 0에서 1 사이의 값을 갖는 파라미터이다.
4. $F^{*}$를 수렴한 $F$라고 할 때, $y_i = \text{argmax}_{j \le c} F^{*}_{ij}$

 

위 알고리즘에서 $F(0) = Y$입니다. iteration을 계속하며, 데이터셋으로부터 구성한 그래프 행렬 $S$를 바탕으로 레이블 정보 $Y$를 전파(propagation)합니다. 

 

이어서 F가 발산하지 않고 수렴한다는 것을 증명해봅시다.

먼저 알고리즘 3번의 식 $F(t+1) = \alpha SF(t) + (1 - \alpha)Y$에 따라 다음과 같은 식을 얻을 수 있습니다.

$$F(t) = (\alpha S)^{t-1}Y + (1-\alpha) \sum_{i=0}^{t-1} (\alpha S)^i Y. \tag{1}$$

위 식에서, $S^{t} = D^{-1/2} W (D^{-1}W)^{t-1} D^{-1/2}$ 이고, $D^{-1}W$은 각 행의 합이 1인 마코프 행렬이므로, $t \to \infty$ 일 때 $S^t$는 어떤 한 행렬로 수렴하게 됩니다.

(마코프 행렬은 eigenvalue가 [-1, 1] 범위의 값을 갖고, 자기 자신을 계속해서 곱하면 어떤 하나의 행렬로 수렴합니다)

 

따라서 $$\lim_{t \to \infty} (\alpha S)^{t-1} = 0, \text{and } \lim_{t \to \infty} \sum_{i=0}^{t-1}(\alpha S)^i = (I - \alpha S)^{-1} \tag{2}$$ 이므로, $$F^* = \lim_{t \to \infty} F(t) = (1-\alpha)(I - \alpha S)^{-1}Y \tag{3}$$ 입니다.

 

이를 통해 우리는 $F^*$이 발산할 걱정 없이 이 알고리즘을 사용하면 된다는 것을 알 수 있습니다.

 

 

 

 

 Regularization Framework

 

앞서 제시한 알고리즘은 적절한 regularization을 통해 최적값이 결정됩니다. 분류모델 $F$에 대한 cost function은 다음과 같이 정의됩니다. $$\mathcal{Q}(F) = \frac{1}{2} \left( \sum_{i, j=1}^{n} W_{ij} \left| \left| \frac{1}{\sqrt{D_{ii}}} F_i - \frac{1}{\sqrt{D_{jj}}} F_j \right| \right|^2 + \mu \sum_{i=1}^{n} || F_i - Y_i ||^2  \right), \tag{4}$$

여기서 $\mu$는 regularization 파라미터입니다. 우리는 이 $\mathcal{Q}$를 최소로 하는 $F$를 찾아야하는 것입니다.

첫 번째 항은 서로 가까운 instance들은($W_{ij}$가 큰 경우) 비슷한 레이블을 가져야 한다는 것이고, 두 번째 항은 레이블이 있는 데이터는 실제 레이블($Y_i$)과 예측치($F_i$)가 비슷한 값을 가져야 한다는 것입니다.

 

$\mathcal{Q}(F)$를 $F$에 대해 미분하게 되면, 다음과 같이 식이 전개될 수 있습니다.

 

 

미분하면 $F^* - SF^*$이 어떻게 나오는지 한참 고민하긴 했는데,,, 전개해보니 대충으로만 이해가 되었던 것 같습니다,,, 대충 이해했던지라 설명은 잘 못하겠네요 ㅠㅠ  선형대수 잘하는 사람에게 물어봐야겠습니다,,,

 

어쨌든 이 부분에서의 결론은 cost function을 최소화하는 $F^*$가 앞서 알고리즘 부분에서 수렴하는 식과 일치하는 형태를 보인다는 것이었습니다.

 

 

 

 

 Conclusion

 

논문을 읽고나서 든 결론은,, 그래프를 활용한 레이블 추론 방법을 써야하는 상황에서, 비교 대상이 되는 메소드로 활용해볼 수 있겠다는 것이었습니다. 아무래도 20년이 다 된 논문이고, 이를 기반으로 더욱 발전된 메소드들이 (e.g. 딥러닝의 경우 GNN, GCN, etc) 많이 등장했기 때문입니다. 그럼에도 이 논문은 인용수가 4천회 이상에 달하는 매우 fundamental한 논문이고, LGC는 Label propagation 문제를 활용하는 논문에서는 어김없이 한 기준으로써 제시되는 방법입니다. 그런 점에서 충분히 깊게 뜯어볼만 한 논문이었던 것 같습니다.

 

감사합니다!