티스토리 뷰
Candidate Sampling이란?
- Multiclass Classification를 수행하는 딥러닝 모델은 소프트맥스 확률을 계산하는 레이어를 지닌다.
- 모델 학습 과정에서 Backprogation을 위해서는 모든 클래스의 소프트맥스 확률을 계산이 필요하다.
- 문제는 클래스가 매우 많은 경우 소프트맥스 확률 계산에 많은 연산 비용이 든다는 점이다.
- 특히 NLP 문제의 경우 단어의 수가 많게는 수백만개에 이르기 때문에 이런 문제가 필연적이다.
- 수많은 아이템을 다루는 추천 시스템도 이런 문제를 겪는다.
- Candidate Sampling은 이런 문제를 해결하기 위해 고안된 방법론이다.
- 전체 클래스에 대해 소프트 맥스 확률값을 계산하는 대신에 일부 카테고리만 랜덤하게 뽑아 소프트맥스 확률값을 구하고, 파라미터를 업데이트 하는 방법이다.
- 이 글에서는 Candidate Sampling 방법 중 NCE(Noise Contrasive Estimation)과 이의 단순화된 버전인 Negative Sampling에 대해 정리한다.
Noise Contrasive Estimation
- NCE의 아이디어는 원래 문제를 (실제 분포에서 얻은 샘플 - Positive Sample)과 (인공적으로 만든 노이즈 - Negative Sample)를 구별하는 이진 분류 문제로 바꾸어 푸는 것이다.
- Negative Sample은 Noise Distribution으로 부터 클래스를 추출하여 생성한다.
- word2vec으로 생각해보면, Negative Sample은 window 내에 등장하지 않는 단어들이며 Positive Sample은 window 내에 등장하는 단어가 된다.
Multiclass classification를 위한 모델을 어떻게 이진 분류 모델로 변형하는지는 아래 과정을 통해 단계적으로 짚어보자.
- Training Example (x_i, T_i)을 가지고 있다고 하자.
- context x_i가 주어졌을 때, 타겟 클래스의 기대 값(count)은 다음과 같다.
- P(y|x) = E(T(y)|x)
- 학습의 목표는 F(x, y)를 log(P(y|x))에 근사하도록 하는 것이다.
- 일반적으로는 softmax & cross-entropy loss를 사용해서 모델을 학습하지만, 계산량을 줄이기 위해 sampled candidates와 true candidates를 분류하는 이진 분류 문제로 바꾸어 풀 것이다.
Sampling
- 각 example (x_i, T_i) 마다, 클래스의 집합인 S_i를 샘플링한다.
- 실제 타겟 클래스 T_i와 S_i의 합하여 Candidates를 구성한다.
-
C_i = T_i + S_i
- Candidates를 구성했으니, 이제 T_i에 대응되는 Positive Example과 S_i의 각 클래스에 대응되는 Negative Example을 가지게 되었다.
- 이제 이 데이터를 사용해서 positive class와 negative class를 분류하는 이진 분류 문제를 학습하면된다.
Logistic regression의 input
- logOdds(y came from T vs S |x)를 logistic regression loss의 input으로 입력할 것이다.
- (참고. 일반적인 logistic regression에서는 logOdds를 beta*x로 추정)
logOdds(y came from T vs S|x) = log(P(y|x)/Q(y|x)) = log(p(y|x)) - log(Q(y|x))
- 여기서 log(p(y|x))는 F(x, y)로 추정하고자 하는 값이다.
- F(x, y)를 나타내는 레이어에 -log(Q(y|x))를 더해서 logistic regression의 input을 구성한다.
- Q(y|x)는 샘플링 알고리즘에 따른 기대 값(count)이다.
- Q(y|x) := E(S(y)|x))
- 이 값을 analytically 계산하여 사용한다. (몬테카를로 방법론?)
- 정리하면, Logistic Regression Input = F(x, y) - log(Q(y|s))이며, backpropagation을 통해 F(x, y)가 근사적으로 학습된다.
Negative Sampling
- Negative Sampling은 NCE의 단순화된 버전이다.
- NCE에서는 sampling distribution의 loglikelihood인 log(Q(y|x))를 학습 과정에서 고려했다.
- (F(x, y) 레이어에서 log(Q(y|x))를 빼주어 F(x, y)가 log(E(y|x))를 근사하도록 함)
- 반면, Negative Sampling은 이를 학습과정에서 무시한다.
- 그 결과 F(x, y)는 log(E(y|x)) - log(Q(y|x))를 근사하도록 학습된다.
- 여기서, 근사하고자 하는 대상이 샘플링 분포인 Q에 의존한다는 점을 주목해야한다.
- 따라서, 네거티브 샘플링에서는 어떤 Sampling Distribution을 선택하느냐에 따라 학습 결과가 많이 달라진다.
Reference