[Model] Loss 함수 살펴보기

[bohyunshin]

이 discussion에서는 구현된 모델에서 사용한 손실 함수에 대해서 살펴봅니다. 먼저 임베딩 기반 모델의 손실 함수를 살펴보겠습니다. 스탠포드 cs224w 강의 노트를 참고해서 작성했습니다.

Random walk optimization

레포에 구현된 임베딩 모델은 비지도 학습을 기반으로 합니다. 라벨이 없기 때문에 파라미터를 학습하기 위해서 추가적인 시나리오를 세워야 하는데 저희 프로젝트에서는 random walk optimization을 사용합니다. random walk optimization은 다음과 같습니다.

1. 각각의 노드에서 출발하여 정해진 길이 만큼의 random walks을 생성합니다. 이때, unbiased random walk일지, biased random walk일지는 파라미터에 따릅니다. unbiased random walk는 deepwalk, biased random walk는 node2vec 입니다.
2. 각 노드($u$)에서 출발하여 생성한 random walk에서 방문된 노드를 $N_R(u)$로 정의합니다. 이 노드는 $u$의 이웃 노드입니다.
3. 이제 $u$가 주어졌을 때, $N_R(u)$가 나올 확률을 최대화하는 방향으로 임베딩을 학습합니다.

나이브한 목적 함수는 다음과 같습니다.

$argmax_z \sum_{u \in V} \log P(N_R(u) | z_u)$

$z_u$는 노드 $u$의 임베딩 벡터입니다.

수식을 손실 함수 관점에서 다시 적으면 다음과 같습니다.

$argmin_z L = \sum_{u \in V} \sum_{v \in N_R(u)} - \log P (v | z_u) $

여기서 확률을 아래와 같이 parameterize 합니다.

$P (v | z_u) = \dfrac{exp (z_u^T z_v)}{ \sum_{n \in V} exp (z_u^T z_n) }$

자세히 살펴보면 복잡할 것은 없고 노드 $v$가 나올 확률을 softmax로 구한 것 뿐입니다. 분모는 normalizer로, $n \in V$을 통해 모든 노드에 대한 exponential 값이 들어감을 확인할 수 있습니다.

왜 이런 형태로 parameterize할까? 를 잠깐 생각해보면.. 개인적으로는 multinomial 형태가 가장 일반적으로 생각할 수 있는 확률의 형태이고 word2vec도 이런 형태를 사용했기 때문이라고 생각합니다. 다른 의견 있으시면 말씀주세요~

그러면 이제 손실 함수를 하나로 적어봅니다.

$argmin_z L = \sum_{u \in V} \sum_{v \in N_R(u)} - \log \dfrac{exp (z_u^T z_v)}{ \sum_{n \in V} exp (z_u^T z_n) } $

생성한 random walk에서 방문한 노드를 이웃 노드로 정의하고 초기 노드가 주어질 때, 이웃 노드를 방문할 확률을 최대화 (-을 붙였으니 최소화)하는 방향으로 $z_i$을 학습합니다.

Computation complexity

그런데 여기서 문제가 발생합니다. 위의 손실함수에서 가장 outer summation은 $u \in V$이고 확률의 분모를 보면 동일한 summation인 $u \in V$가 있습니다. summation 안에 summation이 들어가 있는 형태이므로 $O( |V|^2 )$의 시간 복잡도가 소요됩니다. (이웃 노드의 수는 상대적으로 작으므로 시간 복잡도 계산에서 제외합니다)

이런 배경에서 negative sampling을 사용하게 됩니다. word2vec에서 최초로 소개가 되었습니다.

Approximation using negative sampling

word2vec에서 최초로 소개된 negative sampling은 아래의 approximation을 사용합니다.

$\log \dfrac{exp (z_u^T z_v)}{ \sum_{n \in V} exp (z_u^T z_n) } \approx \log (\sigma (z^T_u z_v)) + \sum^k_{i=1} \log (\sigma ( -z^T_u z_{n_i} )), n_i \sim P_V$

자세한 유도식은 논문을 참고해주세요. 유도 과정이 꽤나 흥미롭습니다 ㅋㅋ

Contrastive learning

저는 잘 몰랐었는데 이렇게 positive / negative sample을 정의하고 기준이 되는 노드와 positive sample은 가깝게, negative sample을 멀게 학습하는 방법을 contrastive learning이라고 하더군요. 다양한 contrastive learning 손실 함수가 있는 것 같은데 가장 많이 쓰이고 기본이 되는 손실 함수는 word2vec에서 제안한 함수인 것 같아요. (역시 근본이 짱이네요!)