BoostCamp AI Tech - Day24

1. 정점 표현 학습

- 그래프의 정점들을 벡터의 형태로 표현하는 것으로 정점 임베딩(Node Embedding)이라고도 부른다.

- 정점 임베딩은 벡터 형태의 표현 그 자체를 의미

- 임베딩 공간 : 정점이 표현되는 벡터 공간

정점 표현 학습의 입력은 그래프이다. 주어진 그래프의 각 정점 𝑢에 대한 임베딩, 즉 벡터 표현 $z_{u}$가 정점 임베딩의 출력이다

 

1.1 정점 표현 학습의 이유

 

정점 임베딩의 결과로, 벡터 형태의 데이터를 위한 도구들을 그래프에도 적용할 수 있습니다

기계학습 도구들이 한가지 예시로 들겠다. 대부분 분류기(로지스틱 회귀분석, 다층 퍼셉트론 등) 그리고 군집 분석 알고리즘(K-Means, DBSCAN 등)은 벡터 형태로 표현된 사례(Instance)들을 입력으로 받는다. 그래프의 정점들을 벡터 형태로 표현할 수 있다면, 위의 예시와 같은 대표적인 도구들 뿐 아니라, 최신의 기계 학습도구들을 정점 분류(Node Classification), 군집 분석(Community Detection) 등에 활용할 수 있다.

 

1.2 정점 표현 학습의 목표

- 그래프에서의 정점간 유사도를 임베딩 공간에서도 “보존”하는 것

아래 그림의 왼쪽 그래프에서 보라색과 연두색이 군집화를 이루었다면, 그 오른쪽 임베딩 공간에서도 유사도를 같게 하라는 뜻이다. 따라서, 임베딩공간에서도 유사도는 높은 것은 가깝게, 유사도는 낮은 것은 멀게 표현하는 것이다.

 

임베딩 공간에서의 유사도는 내적을 사용한다. 따라서, 임베딩 공간에서의 u,v의 유사도는 다음과 같다.

이 때, 이 값은 두 벡터의 크기가 클 수록, 그리고 같은 방향을 향할 수록 큰 값을 같는다.

 

 

정점 임베딩은 다음과 같이 두 단계로 이루어진다.

1) 그래프에서의 정점 유사도를 정의하는 단계

2) 정의한 유사도를 보존하도록 정점 임베딩을 학습하는 단계

 

2. 인접성 기반 접근법

 

2.1 인접성 기반 접근법

 

 

인접하다는 것은 둘을 직접 연결하는 간선 (𝑢, 𝑣)가 있다는 의미다. 인접행렬(Adjacency Matrix) 𝐀의 𝑢행 𝑣열 원소 𝐀𝑢,𝑣는 𝑢와 𝑣가 인접한 경우 1아닌 경우 0이다.

인접행렬의 원소 𝐀𝑢,𝑣 를 두 정점 𝑢와 𝑣의 유사도로 가정한다.

 

인접성 기반 접근법의 손실 함수(Loss Function)는 아래와 같다.

 

즉, 이 손실 함수가 최소가 되는 정점 임베딩을 찾는 것이 목표다. 손실 함수 최소화를 위해서는 (확률적) 경사하강법 등이 사용된다.

 

2.2 인접성 기반 접근법의 한계

 

위 그림에서 빨간색 정점과 파란색 정점은 거리가 3인 반면 초록색 정점과 파란색 정점은 거리가 2이다. 인접성만을 고려할 경우 이러한 사실에 대한 고려 없이, 두 경우의 유사도는 0으로 같다.

 

군집 관점에서는 빨간색 정점과 파란색 정점은 다른 군집에 속하는 반면 초록색 정점과 파란색 정점은 다른 군집에 속합니다. 인접성만을 고려할 경우 이러한 사실에 대한 고려 없이, 두 경우의 유사도는 0으로 같다.

 

3. 거리 기반 접근법

 

거리 기반 접근법에서는 두 정점 사이의 거리가 충분히 가까운 경우 유사하다고 간주한다.

예를 들어, “충분히”의 기준을 2로 가정한다.

빨간색 정점은 초록색 그리고 파란색 정점들과 유사하다.

즉 유사도가 1입니다. 반면, 빨간색 정점은 보라색 정점과는 유사하지 않다. 즉 유사도가 0이다.

 

4. 경로 기반 접근법

 

경로 기반 접근법에서는 두 정점 사이의 경로가 많을 수록 유사하다고 간주한다.

 

정점 𝑢와 𝑣의 사이의 경로(Path)는 아래 조건을 만족하는 정점들의 순열(Sequence)이다.

 

(1) 𝑢에서 시작해서 𝑣에서 끝나야 한다

(2) 순열에서 연속된 정점은 간선으로 연결되어 있어야 한다

 

경로가 순열인 예시:

1,4,6,8

-> 1에서 8까지 모두 연속된 간선으로 연결되어 있다.

경로가 순열이 아닌 예시:

1,6,8

-> 1,6으로 직접이어진 간선이 없다.

1,3,4,5,6,8

-> 5,6사이에 간선이 없다.

 

두 정점 𝑢와 𝑣의 사이의 경로 중 거리가 𝑘인 것은 수는 $A^k_{u,v}$ 와 같다 즉, 인접 행렬 𝐀의 𝑘 제곱의 𝑢행 𝑣열 원소와 같습니다 경로 기반 접근법의 손실 함수는 다음과 같다.

 

5. 중첩 기반 접근법

 

중첩 기반 접근법에서는 두 정점이 많은 이웃을 공유할 수록 유사하다고 간주한다

 

아래 그림에서 빨간색 정점은 파란색 정점과 두 명의 이웃을 공유하기 때문에 유사도는 2가 된다.

정점 𝑢의 이웃 집합을 𝑁(𝑢) 그리고 정점 𝑣의 이웃 집합을 𝑁(𝑣)라고 하면 두 정점의 공통 이웃 수 𝑆𝑢,𝑣는 다음과 같이 정의 된다.

 

이 때, 손실함수는 다음과 같다.

공통 이웃 수를 자카드 유사도 혹은 Adamic Adar 점수를 대신해서 사용할 수 있다.

 

- 자카드 유사도(Jaccard Similarity) : 공통 이웃의 수 대신 비율을 계산하는 방식이다.

이 값은 0보다 크거나 같고, 1보다 작거나 같다. 단, 1은 $N_u = N_v$ 일 때, 성립한다.

 

- Adamic Adar 점수 : 공통 이웃 각각에 가중치를 부여하여 가중합을 계산하는 방식이다.

 

6. 임의보행 기반 접근법

 

- 임의보행 기반 접근법에서는 한 정점에서 시작하여 임의보행을 할 때 다른 정점에 도달할 확률을 유사도로 간주한다.

 

- 임의보행이란 현재 정점의 이웃 중 하나를 균일한 확률로 선택하는 이동하는 과정을 반복하는 것을 의미한다.(페이지 랭크 알고리즘 참고)

 

- 임의보행을 사용할 경우 시작 정점 주변의 지역적 정보와 그래프 전역 정보를 모두 고려한다는 장점이 있다.

- 임의보행 기반 접근법 단계

1) 각 정점에서 시작하여 임의보행을 반복 수행한다

2) 각 정점에서 시작한 임의보행 중 도달한 정점들의 리스트를 구성한다. 이 때, 정점 𝑢에서 시작한 임의보행 중 도달한 정점들의 리스트를 $N_R(u)$라고 하자. 한 정점을 여러 번 도달한 경우, 해당 정점은 $N_R(u)$에 여러 번 포함될 수 있다.

3) 다음 손실함수를 최소화하는 임베딩을 학습한다

임베딩으로부터 도달 확률을 추정하는 방법은 정점 𝑢에서 시작한 임의보행이 정점 𝑣에 도달할 확률 𝑃(𝑣|𝑧𝑢)을 다음과 같이 추정한다.

 

즉, 유사도 $z^{T}_{v} z_u$가 높을 수록 도달 확률이 높다.

 

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

 

임의보행의 방법에 따라 DeepWalk와 Node2Vec이 구분한다.

 

- DeepWalk

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

 

- Node2Vec

 

Node2Vec은 2차 치우친 임의보행(Second-order Biased Random Walk)을 사용한다.

 

현재 정점(예시에서 𝑣)과 직전에 머물렀던 정점(예시에서 𝑢)을 모두 고려하여 다음 정점을 선택한다.

직전 정점의 거리를 기준으로 경우를 구분하여 차등적인 확률을 부여한다.

Node2Vec에서는 부여하는 확률에 따라 다른 종류의 임베딩을 얻는다. 아래 그림은 Node2Vec으로 임베딩을 수행한 뒤, K-means 군집 분석을 수행한 결과이다.

 

멀어지는 방향에 높은 확률을 부여한 경우, 정점의 역할(다리 역할, 변두리 정점 등)이 같은 경우 임베딩이 유사하다. 파란 원(정점)은 서로 멀리 떨어져 있지만, 다리 역할 해주고, 노란 원(정점)들은 연결성이 높지 않아 주변부 역할을 한다. 또한, 빨간 원(정점)은 거리가 가까운 경우가 많으므로 같은 군집에 속해있음을 알 수 있다.

 

가까워지는 방향에 높은 확률을 부여한 경우, 같은 군집(Community)에 속한 경우 임베딩이 유사하다. 위 사진처럼 같은 색 끼리 군집이 이뤄졌기에 비슷한 벡터값을 형성했음을 알 수 있다.

 

- 손실 함수 근사

 

임의보행 기법의 손실함수는 계산에 정점의 수의 제곱에 비례하는 시간이 소요된다. 이유는 아래의 식 처럼 중첩된 합 때문이다.

정점이 많은 경우, 제곱은 매우 큰 숫자이다. 예시로 1억의 제곱은 1경 = 10,000조 이므로 시간이 매우 오래 걸린다. 따라서, 이처럼 정점이 많은 경우에는 근사식을 사용한다.

 

모든 정점에 대해서 정규화하는 대신 몇 개의 정점을 뽑아서 비교하는 형태다. 이 때 뽑힌 정점들을 네거티브 샘플이라고 부른다.

 

연결성에 비례하는 확률로 네거티브 샘플을 뽑으며, 네거티브 샘플이 많을 수록 학습이 더욱 안정적이다.

 

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

 

지금까지 소개한 정점 임베딩 방법들을 변환식(Transductive) 방법이다. 변환식(Transdctive) 방법은 학습의 결과로 정점의 임베딩 자체를 얻는다는 특성이 있다. 정점을 임베딩으로 변화시키는 함수, 즉 인코더를 얻는 귀납식(Inductive) 방법과 대조된다.

 

변환식 임베딩 방법은 여러 한계를 갖게된다.

 

1) 학습이 진행된 이후에 추가된 정점에 대해서는 임베딩을 얻을 수 없다. 즉, 새로 추가된 정점이 있다면, 처음부터 임베딩을 다시 수행하여야 한다.

2) 모든 정점에 대한 임베딩을 미리 계산하여 저장해두어야 한다

3) 정점이 속성(Attribute) 정보를 가진 경우에 이를 활용할 수 없다

 

8. 잠재 인수 모형

 

8.1 잠재 인수 모형의 개념

잠재 인수 모형(Latent Factor Model)의 핵심은 사용자와 상품을 벡터로 표현하는 것이다. 즉, 정점임베딩이다.

예) 사용자와 영화를 임베딩

 

이 때, 학습한 인수를 잠재인수라고한다.

 

Boost Camp AI Tech

8.2 손실 함수

 

사용자와 상품의 임베딩의 내적(Inner Product)이 평점과 최대한 유사하도록 하는 것이다

즉, 사용자 x의 임베딩을 $p_x$ , 상품 i의 임베딩을 $q_i$ , 사용자 x의 상품 i에 대한 평점을$r_{xi}$ 라고 하면, 임베딩의 목표는 $p^{T}_{x}q_i$ 이 $r_{xi}$ 와 유사하도록 하는 것이다.

 

행렬 차원에서 살펴보자

 

R : 사용자 수의 열과 상품 수의 행을 가진 평점 행렬

Q : 사용자들의 임베딩, 즉 벡터를 쌓아서 만든 사용자 행렬

P : 영화들의 임베딩, 즉 벡터를 쌓아서 만든 상품 행렬

 

잠재 인수 모형은 다음 손실 함수를 최소화하는 𝑃와 𝑄를 찾는 것을 목표로 한다.

 

하지만, 위 손실 함수를 사용할 경우 과적합(Overfitting)이 발생할 수 있다. 과적합이란, 기계학습 모형이 훈련 데이터의 잡음(Noise)까지 학습하여, 평가 성능은 오히려 감소하는 현상을 의미한다.

 

과적합을 방지하기 위하여 정규화(정확히는 L2-norm) 항을 손실함수에 더해준다.

 

여기서 정규화의 세기(${\lambda }_{1} , {\lambda}_{2}$)는 오차와 모형 복잡도를 두 가지를 최소화하는 데, 둘 중 어느 하나의 목표가 중요한 지 역할 지정하는 계수이다. 

 

또한, 정규화는 극단적인, 즉 절댓값이 너무 큰 임베딩을 방지하는 효과가 있다.

 

손실함수를 최소화하는 P와 Q를 찾기 위해서는 (확률적) 경사하강법을 사용한다.

 

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

 

각 사용자의 편향은 해당 사용자의 평점 평균과 전체 평점 평균의 차이다.

 

ex)

나연이 매긴 평점의 평균이 4.0개의 별, 다현이 매긴 평점의 평균이 3.5개의 별이라고 하자.

 

전체 평점 평균이 3.7개의 별인 경우, 나연의 사용자 편향은 4.0 - 3.7 = 0.3개의 별이고,

다현의 사용자 편향은 3.5 - 3.7 = -0.2개의 별이 된다.

 

영화 식스센스에 대한 평점의 평균이 4.5개의 별, 영화 클레멘타인이 매긴 평점의 평균이 3.0개의 별이라고 하자

전체 평점 평균이 3.7개의 별인 경우, 식스센스의 상품 편향은 4.5 – 3.7 = 0.8개의 별이다

클레멘타인의 상품 편향은 3.0 - 3.7 = -0.7개의 별이다

 

개선된 잠재 인수 모형에서는 평점을 전체 평균, 사용자 편향, 상품 편향, 상호작용으로 분리한다

 

개선된 잠재 인수 모형의 손실 함수는 아래와 같다.

 

그러나, 다음의 방법으로 목표 오차까지 다가갈 수 있다.

 

8.4 시간적 편향을 고려한 잠재 인수 모형

 

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

구체적으로 사용자 편향과 상품 편향을 시간에 따른 함수로 가정한다.