임의보행 기반 접근 (DeepWalk)

임의보행 기반 접근법의 손실 함수를 실제 예시와 함께 자세히 설명해드리겠습니다.

1. 네트워크 예시:

철수 - 영희 - 민수
  |     |     |
지영 - 상우 - 동준

2. 임의보행 수행:
   시작노드 '철수'에서의 임의보행 시퀀스 예:

R₁: 철수 → 영희 → 민수
R₂: 철수 → 지영 → 상우
R₃: 철수 → 영희 → 상우

3. 확률 계산 P(v|z_u):

철수의 임베딩 z_철수 = [0.8, 0.2]
영희의 임베딩 z_영희 = [0.7, 0.3]
민수의 임베딩 z_민수 = [0.5, 0.5]

P(영희|z_철수) = exp(z_철수 · z_영희) / Σ exp(z_철수 · z_w)
                = exp(0.62) / [exp(0.62) + exp(0.4) + ...]

5. 손실 함수 상세 설명:

L = Σ     Σ      -log(P(v|z_u))
   u∈V  v∈N_R(u)

여기서:

• V: 모든 노드 집합
• N_R(u): u에서 시작한 임의보행에서 방문한 이웃 노드들
• z_u: 노드 u의 임베딩 벡터
• P(v|z_u): u의 임베딩이 주어졌을 때 v로 이동할 확률

6. 실제 계산 예시:

1단계: z_u · z_v 계산
철수→영희: 0.8×0.7 + 0.2×0.3 = 0.62

2단계: softmax 적용
P(영희|z_철수) = exp(0.62) / Σ exp(z_철수 · z_w)

3단계: 음의 로그 취하기
Loss = -log(P(영희|z_철수))

• 2,3단계 아래 확인

7. 최적화 목표:

• 임의보행에서 연속으로 나타나는 노드들의 임베딩을 가깝게
• 실제 이웃 노드로의 전이 확률 높이기
• 비이웃 노드로의 전이 확률 낮추기

8. 특징:

• 지역적 구조 보존
• 확률적 접근
• 효율적인 학습

9. 장점:

• 대규모 네트워크 처리 가능
• 점진적 학습 가능
• 병렬 처리 용이

10. 구현시 고려사항:

def calculate_loss(walk, embeddings):
    loss = 0
    for i in range(len(walk)-1):
        u = walk[i]
        v = walk[i+1]
        prob = softmax(dot(embeddings[u], embeddings[v]))
        loss += -log(prob)
    return loss

이러한 방식으로 임의보행 기반 접근법은 네트워크의 지역적 구조를 효과적으로 포착하면서도, 확률적 모델링을 통해 더 유연한 임베딩 학습이 가능합니다.

---

2,3단계 설명

간단한 예시로 설명하겠습니다:
철수의 이웃: [영희, 지영]

1. 각 노드의 임베딩 벡터 (2차원):

z_철수 = [0.8, 0.2]
z_영희 = [0.7, 0.3]
z_지영 = [0.3, 0.7]

2. 내적 계산 (z철수 x z다른노드):

z_철수 · z_영희 = (0.8 × 0.7) + (0.2 × 0.3) = 0.62
z_철수 · z_지영 = (0.8 × 0.3) + (0.2 × 0.7) = 0.38

3. exp(내적) 계산:

exp(z_철수 · z_영희) = exp(0.62) = 1.859
exp(z_철수 · z_지영) = exp(0.38) = 1.462

4. Softmax 계산:

분모 = Σ exp(z_철수 · z_w) = 1.859 + 1.462 = 3.321

P(영희|z_철수) = 1.859 / 3.321 = 0.56 (56%)
P(지영|z_철수) = 1.462 / 3.321 = 0.44 (44%)

5. 손실 계산 (-log 적용):

Loss = -log(P(영희|z_철수))
     = -log(0.56)
     = 0.579

이해를 돕기 위한 핵심 포인트:

1. Softmax가 필요한 이유:

• 내적값을 [0,1] 범위의 확률로 변환
• 모든 확률의 합이 1이 되도록 보장

2. -log를 취하는 이유:

• 확률이 1에 가까울수록 손실 작아짐
• 확률이 0에 가까울수록 손실 커짐
• 올바른 예측 장려, 잘못된 예측 페널티

3. 수치 예시:

높은 확률의 경우:
P = 0.9 → Loss = -log(0.9) = 0.105 (낮은 손실)

낮은 확률의 경우:
P = 0.1 → Loss = -log(0.1) = 2.302 (높은 손실)

이렇게 계산된 손실 함수를 최소화하는 방향으로 임베딩을 학습하면, 실제 임의보행에서 자주 함께 나타나는 노드들의 임베딩이 서로 가까워지게 됩니다.