Boostcamp AI Tech (Day 024)

정점 표현 학습

정점 표현 학습
- 그래프의 정점들을 벡터 형태로 표현
- 정점 임베딩(node embedding)
- 입출력
  - 입력: 그래프
  - 출력: 주어진 그래프의 각 정점 $u$에 대한 임베딩, 즉 벡터 표현 $z_u$
- 그래프의 정점들을 벡터 형태로 표현하여, 분류기(로지스틱 회귀분석, 다층 퍼셉트론 등)와 군집 분석 알고리즘(k-means, DBSCAN 등), 최신 머신러닝 도구들(node classification, community detection) 등에 활용 가능
- 그래프에서의 정점간 유사도를 임베딩 공간에서도 보존하는 것을 목표로 함
- 임베딩 공간에서의 유사도
  - 내적(inner product)
    
    $similarity(u,v) \approx z_v^T z_u = \Vert z_u \Vert \cdot \Vert z_v \Vert \cdot cos(\theta)$
- 점점 임베딩의 단계
  1. 그래프에서의 정점 유사도를 정의
  2. 정의한 유사도를 보존하도록 정점 임베딩을 학습
접근법
- 인접성(adjacency) 기반 접근법
  - 두 정점이 인접할 때 유사하다고 가정
  - 인접행렬 $A$의 $u$행 $v$열 원소 $A_{u,v}$는 $u$와 $v$가 인접한 경우 1, else 0
  - $A_{u,v}$: 정점 $u$와 $v$의 유사도
  - 손실함수
    
    $L = \sum_{(u,v) \in V \times V} \Vert z_u^T z_u - A_{u,v} \Vert^2$
  - 거리, 군집 관계를 무시하기 때문에 한계를 가짐
- 거리/경로/중첩 기반 접근법
  - 거리
    - 두 정점 사이의 거리가 충분히 가까운 경우 유사하다고 가정
  - 경로
    - 두 정점 사이의 경로가 많을 수록 유사하다고 가정
      
      $L = \sum_{(u,v) \in V \times V} \Vert z_u^T z_u - A_{u,v}^k \Vert^2$
  - 중첩
    - 두 정점이 많은 이웃을 공유할 수록 유사하다고 가정
    - 공통 이웃 수 $S_{u,v} = \vert N(u) \cap N(v) \vert$
      
      $L = \sum_{(u,v) \in V \times V} \Vert z_u^T z_u - S_{u,v} \Vert^2$
    - Jaccard similarity: 공통 이웃의 비율 계산
    - Adamic Adar 점수: 공통 이웃 각각에 가중치 부여해 가중합 계산
- 임의보행 기반
  - 한 정점에서 시작해 임의보행을 할 때 다른 정점에 도달할 확률을 유사도로 가정
  - 임의보행: 현재 정점의 이웃 중 하나를 균일한 확률로 선택하여 이동하는 과정
  - 장점
    - 시작 정점 주변의 지역적 정보, 그래프 전역 정보를 모두 고려함
  - 단계
    1. 각 정점에서 시작해 임의보행을 반복 수행
    2. 정점 $u$에서 시작해 임의보행 중 도달한 정점들의 리스트 $N_R(u)$를 구성
    3. 손실함수를 최소화하는 임베딩 학습
      
      $L = \sum_{u \in V} \sum_{v \in N_R(u)} - \log (P(v \vert z_u))$
      
      $P(v \vert z_u)$: $u$에서 시작한 임의보행이 $v$에 도달할 확률을 임베딩으로부터 추정한 결과
      
      $P(v \vert z_u) = \frac{exp(z_u^T z_v)}{\sum_{n \in V} exp(z_u^T z_n)}$
  - DeepWalk
    - 기본적인 임의보행 사용
    - 현재 정점의 이웃 중 하나를 균일한 확률로 선택
  - Node2Vec
    - 2차 치우친 임의보행(second-order biased random walk) 사용
    - 현재 정점과 직전에 머물렀던 정점을 고려해 다음 정점 선택
    - 직전 정점의 거리를 기준으로 경우를 구분해 차등적인 확률 부여
  - 손실함수 계산시 정점 수 제곱에 비례하는 시간 필요
    - 몇 개의 정점을 뽑아서 비교하는 형태로 근사식 사용
    - 연결성에 비례하는 확률로 네거티브 샘플 뽑음
변환식(transductive) 정점 표현
- 학습의 결과로 정점의 임베딩 자체를 얻음
- 한계
  - 학습이 진행된 이후 추가된 정점에 대해서는 임베딩을 얻을 수 없음
  - 모든 정점에 대한 임베딩을 미리 계산하여 저장해둬야함
  - 정점이 속성(attribute) 정보를 가진 경우 활용 불가
- 귀납식(inductive) 방법과 대조됨
  - 정점을 인베딩으로 변화시키는 함수인 인코더를 얻음
  - 대표적으로 그래프 신경망(graph neural network)이 있음

Netflix challenge

데이터
- 2000~2005 사용자별 영화 평점 데이터
- 훈련 데이터
  - 48만명 사용자, 18000 영화, 1억개 평점
- 평가 데이터
  - 각 사용자 최신 평점 280만
진행
- 2006~2009
- 2700개 팀
- 100만 달러 상금

잠재 인수 모형

잠재 인수 모형(latent factor model)
- 사용자와 상품을 벡터로 표현
- 고정된 인수(로맨스 특성, 액션 특성 등) 대신 효과적인 인수를 학습 $\rightarrow$ 잠재 인수
- 사용자와 상품의 임베딩의 내적이 평점과 최대한 유사하도록 학습
  
  $p_x$: 사용자 $x$의 임베딩
  
  $q_i$: 상품 $i$의 임베딩
  
  $r_{xi}$: 사용자 $x$의 상품 $i$에 대한 평점
  
  목표: $p_x^T q_i$가 $r_{xi}$와 유사하도록 함
- 행렬 차원에서
  
  $R \approx Q \cdot P^T$
  
  $R$: 평점 행렬, $P$: 사용자 행렬, $Q$: 상품 행렬
- 손실함수
  
  $L = \sum_{(i,x) \in R} (r_{xi} - p_x^T q_i)^2 + [ \lambda_1 \sum_x \Vert p_x \Vert^2 + \lambda_2 \sum_i \Vert q_i \Vert^2]$
  
  $=$ (오차) + (모형의 복잡도, regularization)
- 최적화
  - 손실함수를 최소화하는 $P$와 $Q$를 찾기 위함
  - 경사하강법
  - Stochastic 경사하강법
- 개선된 잠재 인수 모형
  
  $r_{xi} = \mu + b_x + b_i + p_x^T q_i$
  
  $r_{xi}$: 평점, $\mu$: 전체 평균, $p_x^T q_i$: 상호작용
  
  사용자의 편향 $b_x$: 해당 사용자의 평점 평균 - 전체 평점 평균
  
  상품의 편향 $b_i$: 해당 상품에 대한 평점 평균 - 전체 평점 평균
  - 손실함수
    
    $L = \sum_{(i,x) \in R} (r_{xi} - (\mu + b_x + b_i + p_x^T q_i))^2 + [ \lambda_1 \sum_x \Vert p_x \Vert^2 + \lambda_2 \sum_i \Vert q_i \Vert^2 + \lambda_3 \sum_x b_x^2 + \lambda_4 \sum_i b_i^2]$
- 시간적 편향을 고려한 잠재 인수 모형
  
  $r_{xi} = \mu + b_x(t) + b_i(t) + p_x^T q_i$

정점 표현 학습

정점 표현 학습

접근법

변환식(transductive) 정점 표현

Netflix challenge

잠재 인수 모형

잠재 인수 모형(latent factor model)