[BoostCamp] DAY24 Graph#4

[BoostCamp] DAY24 Graph#4

---

1. 그래프를 이용한 기계학습

1. 그래프의 정점을 어떻게 벡터로 표현할까?

1.1 정점표현 학습

정점 표현 학습이란?

• 정점 표현 학습이란 그래프의 정점들을 벡터의 형태로 표현하는 것이다.
• 정점 표현 학습은 간단히 정점 임베딩이라고 부른다.
• 정점 임베딩은 벡터 형태의 표현 그자체를 의미하기도 한다.
• 정점 이 표현된느 벡터 공간을 임베딩 공간이라고 부른다.
• 정점 표현 학습의 입력은 그래프이다.
  • 주어진 그래프의 각 정점u에 대한 임베딩, 즉 벡터표현 Zu가 정점 임베딩의 출력이다.

정점 표현 학습의 이유

• 정점 임베딩의 결과로 벡터 형태의 데이터를 위한 도구들을 그래프에도 적용할 수 있다.
  • 기계학습도구들이 한가지의 예시이다.
  • 대부분 분류기 그리고 군집 분석 알고리즘등은 벡터형태로 표현된 instance들을 입력으로 받는다.
• 그래프의 정점들을 벡터 형태로 표현할 수 있다면, 위의 대표적인 도구들 뿐만아니라,
• 최신 기계 학습 도구들을 정점 분류, 군집 분석들에 활용할 수 있다.

정점 표현 학습의 목표

• 그렇다면, 어떤 기준으로 정점을 벡터로 변환해야할까?
  • 그래프에서의 정점간 유사돌르 임베딩 공간에서도 보존하는 것을 목표로한다.
• 임베딩 공간에서의 유사도로는 내적을 사용한다.
  • 내적은 두 벡터가 클수록, 그리고 같은 방향을 향할 수록 큰 값을 가진다.
• 그래프에서의 두 정점의 유사도는 어떻게 정의할까?
  • 여러가지 답이 있을 수 있다.
  • 그 중 하나는 아래와 같다.
  • 

** 정점 임베딩은 아래의 두 단계로 이루어진다.**

1. 그래프에서의 정점 유사도를 정의하는 단계
2. 정의한 유사도를 보존하도록 정점 임베딩을 학습하는 단계

1.2 인접성 기반 접근법

인접성 기반 접근법

• 인접성 기반 접근법에서는 두 정점이 인접할 때 유사하다고 간주한다.
  • 두 정점 u와 v가 인접하다는 것은 둘을 집겁 연결하는 간선 (u, v)가 있음을 의미한다.
  • 인접 행렬 A의 u행 v열 원소 Au,v는 u와 v가 인접한 경우 1, 아닌 경우 0이다.
  • 인접행렬의 원소 Au,v를 두 정점 u와 v의 유사도로 가정하자.
• 인접성 기반 접근법의 손실함수는 아래와 같다,
  • 해당 함수가 최소가 되는 정점 임베딩을 찾는 것을 목표로 한다.
  • 

인접성 기반 접근법의 한계

• 인접성만으로 유사도를 판단하는 것은 한계가 있다.
• 
  1. 빨간 정점과 파란 정점 사이의 거리 : 3, 초록 정점과 파란 정점 사이의 거리 : 2
     • 그럼에도 인접성 만을 고려할 경우 두 유사도는 0으로 동일하다.
  2. 군집 관점에서 확인
     • 빨간 정점과 파란 정점은 다른 군집에 속한다.
     • 초록 정점과 파란 정점은 같은 군집에 속한다.
     • 이러한 사실에 고려를 하지 않고 인접성만 고려한다면, 두 경우의 유사도는 0이다.

1.3 거리/경로/중첩 기반 접근법

거리 기반 접근법

• 거리 기반 접근법에서는 두 정점 사이의 거리가 충분히 가까운 경우 유사하다고 간주한다.
  • 충분히의 기준을 n이라고 할때, 거리가 n이하이면 유사도가 1 이다.
  • n초과이면 유사도는 0이다.

경로 기반 접근법

• 경로 기반 접근 법에서는 두 정점사이의 경로가 많을 수록 유사하다고 간주한다.
  • 정점 u와 v사이의 경로는 아래 조건을 만족하는 정점들의 순열이다.
    1. u에서 시작해서 v에서 끝나야한다.
    2. 순열에서 연속된 정점은 간선으로 연결되어 있어야한다.
  • 두 정점 u와 v사이의 경로 중 거리가 k인것의 수는 와 같다.
  • 즉, 인접 행렬 A의 k제곱의 u행 v열 원소와 같다.
  • 경로 기반 접근법의 손실 함수는 아래와 같다.
  • 

중첩 기반 접근법

• 중첩 기반 접근법에서는 두 정점이 많은 이웃을 공유할 수록 유사하다고 간주한다.
  • 
    • 해당 예시를 확인해보면 빨간 정점과 파란 정점은 두명의 이웃을 공유한다.
    • 이때문에 이 둘 사이의 유사도는 2이다.
  • 정점 u의 이웃 집합을 N(u) 그리고 정점 v의 이웃 집합을 N(v)라고 하자.
    • 두 정점의 공통이웃 수 Su,v는 아래와 같이 정의된다.
    • 
    • 이에 대한 손실함수는 다음과 같다.
    • 
• 공통 이웃 수를 대신 자카드 유사도 혹은 Adamic Adar 점수를 사용할 수 있다.
  • 자카드 유사도 : 공통 이웃 수 대신 비율을 계산하는 방식
    • 
  • Adamic Adar 점수 : 공통 이웃 각각에 가중치를 부여하여 가중합을 계산하는 방식
    • 
    • dw –> 가중치

1.4 임의보행 기반 접근법

임의보행 기반 접근법

• 임의 보행 기반 접근법에서는 한 정점에서 시작하여 임의 보행을 할 때 다른 정점에 도달할 확률을 유사도로 가정한다.
  • 임의보행이란 현재 정점의 이웃 중 하나를 균일한 확률로 선택하는 이동 과정을 반복하는 것을 의미한다.
  • 임의 보행을 사용할 경우 시작 정점 주변의 지역적 정보와 그래프 전역 정보를 모두 고려한다는 장점이 있다.
• 임의보행 기반 접근법의 과정
  1. 각 정점에서 시작하여 임의보행을 반복 수행한다.
  2. 각 정점에서 시작한 임의보행 중 도달할 정점들의 리스를 구성한다.
     • 이때 정점 u에서 시작한 임의 보행중 도달한 정점리스트를 Nr(u)라고 하자.
     • 한 정점을 여러번 도달한 경우, 해당 정점은 Nr(u)에 여러번 포함될 수 있다.
  3. 다음 손실함수를 최소화하는 임베딩을 학습한다.
     • 

** 어떻게 임베딩으로부터 도달 확률을 추정할까?**

• 정점 u에서 시작한 임의보행이 정점 v에 도달할 확률 P(v|zu)를 아래와 같이 추정한다.
  • 

** 위에서 추정한 도달 확률을 사용하여 손실 함수를 완성하고 이를 최소화하는 임베딩을 학습한다.**

DeepWalk와 Node2Vec

• 임의보행의 방법에 따라 DeepWalk와 Node2Vec으로 구분된다.

DeepWalk

• 기본적인 임의보행을 사용한다. 즉, 현재 정점의 이웃 중 하나를 균일한 확률로 선택하는 이동과정을 반복한다.

Node2Vec

• 2차 치우친 임의보행을 사용한다.
  • 현재 정점과 직전에 머물렀던 정점을 모두 고려하여 다음 정점을 선택한다.
  • 직전 정점의 거리를 기준으로 경우를 구분하여 차등적 확률을 부여한다.
  • 
• Node2Vec에서는 부여하는 확률에 따라서 다른 종류의 임베딩을 얻는다.
• 
  • 멀어지는 방향에 높은 확률을 부여한 경우
    • 정점의 역할이 같은 경우 임베딩이 유사하다.
    • 파란색 정점 : 서로 인접하지 않지만, 다리 역할
    • 노란 정점 : 그래프 주변부
    • 빨간 정점 : 군집 역할을 하는 노드
  • 가까워지는 방향에 높은 확률을 부여한 경우
    • 같은 군집에 속한 경우 임베딩이 유사하다.

손실 함수 근사

• 임의보행 기법의 손실함수는 계산에 정점의 수의 제곱에 비례하는 시간이 소요된다.
• Why?
  • 중첩된 합 때문이다. 앞에서 배운 손실 함수를 고려해보자.
  • 
  • 위 의식을 고려하여봤을 때 정점이 많은 경우,
  • 엄청나게 큰 수가 결과 값으로 나올것이고 이를 계산하는데 소모되는 시간또한 어마어마할 것이다.
• ** 근사식을 사용하자.**
  • 모든 정점에 대해서 정규화하는 대신 몇 개의 정점을 뽑아서 비교하는 형태이다.
  • 이때 뽑힌 정점들을 네거티브 샘플이라고 한다.
  • 
    • 정점은 어떻게 뽑아요??
    • 주로 연결성에 비례하는 확률로 뽑는다.
    • 즉, 연결성이 높을 수록 뽑힐 확률이 높다.

1.5 변환식 정점 표현 학습의 한계

변환식 정점 표현 학습과 귀납식 정점 표현 학습

• 지금까지 배운 정점 임베딩 방법들은 변환식 방법이다.
  • 변환식 방법은 학습의 결과로 정점의 임베딩 자체를 얻는다는 특성이 있다.
• 이는 정점을 입베딩으로 변환시키는 함수, 즉 인코더를 얻는 귀납식 방법과 대조된다.

변환식 정점 표현 학습의 한계

• 변환식 임베딩 방법은 여러 한계를 가진다.
  1. 학습이 진행된 이후에 추가된 정점에 대해서는 임베딩을 얻을 수 없다.
  2. 모든 정점에 대한 임베딩을 미리 계산하여 저장해둬야 한다.
  3. 정점이 속성 정보를 가진 경우에 이를 활용할 수 없다.

2. 그래프를 추천 시스템에 어떻게 활용할까?(심화)

2.1 기본 잠재 인수 모형

잠재 인수 모형 개요

• 잠재 인수 모형의 핵심은 사용자와 상품을 벡터로 표현하는 것이다.
• 잠재인수 모형에서는 고정된 인수 대신 효과적인 인수를 학습하는 것을 목표로 한다.
  • 학습한 인수를 잠재 인수라고 한다.

손실 함수

• 사용자와 상품을 임베딩하는 기준은 무엇인가?
  • 사용자와 상품의 임베딩의 내적이 평점과 최대한 유사하도록 하는 것이다.
  • 사용자 x의 임베딩을 px, 상품 i의 임베딩을 qi라고 하자.
  • 사용자 x의 상품 i에 대한 평점을 rxi라고 하자.
  • 임베딩의 목표는 이 rxi와 유사하도록 하는 것이다.
• 행렬 차원에서 살펴보자.
  • R : 사용자 수의 열과 상품 수의 행을 가진 평점 행렬
  • P : 사용자들의 임베딩 죽, 벡터를 쌓아서 만든 사용자 행렬
  • Q : 영화들의 임베딩 즉, 벡터를 쌓아서 만든 상품 행렬
  • 
• 잠재 인수 모형은 다음 손실홤수를 최소화하는 P와 Q를 찾는 것을 목표로한다.
  • 
  • 하지만 위손실 함수를 사용할 경우 Overfitting이 발생할 수 있다.
  • Overfitting을 방지하기 위해서 정규화 항을 손실 함수에 더해준다.
  • 
  • 정규화는 극단적인, 즉 절대값이 너무 큰 임베딩을 방지하는 효과가 있다.

최적화

• 손실함수를 최소화하는 P와 Q를 찾기 위해서는 확률적 경사하강법을 사용한다.
  • 경사하강법은 손실 함수를 안정적으로 하지만 느리게 함소시킨다.
  • 확률적 경사하강법은 손실 함수를 불안정하지만 빠르게 감소시킨다.

2.2 고급 잠재 인수 모형

사용자와 상품의 편향을 고려한 잠재 인수 모형

• 각 사용자의 편향은 해당 사용자의 평점 평균과 전체 평점 평균의 차이다.
• 개선된 잠새인수 모형에서는 평점을 전체 평균, 사용자 편향, 상품편향, 상호작용으로 분리한다.
• 
• 이러한 식의 손실함수는 아래와 같이 표현 가능하다.
• 

시간에 따른 편향을 고려한 잠재 인수 모형

background

• 넷플릭스 시스템의 변화로 평균 평점이 크게 상승하는 사건
• 영화의 평점은 출시일 이후 시간이 지남에 따라 상승하는 경향이 있다.

개선된 잠재 인수 모형에서는 이러한 시간적 편향을 고려한다.

• •