[U] Day 24 - 정점 표현 & 추천시스템 (심화)

[Graph 7강] 그래프의 정점을 어떻게 벡터로 표현할까?

정점 표현 학습

인접성 기반 접근법

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

임의보행 기반 접근법

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

실습 코드

[Graph 8강] 그래프를 추천시스템에 어떻게 활용할까? (심화)

넷플릭스 챌린지 소개

기본 잠재 인수 모형

고급 잠재 인수 모형

실습 코드

Reference

---

[Graph 7강] 그래프의 정점을 어떻게 벡터로 표현할까?

💡

그래프의 정점을 어떻게 벡터로 표현하고, 정점 사이의 유사성은 어떻게 표현하는지에 대해 알아본다.

정점 표현 학습

정점 표현 학습이란, 그래프의 정점들을 임베딩 공간의 벡터 형태로 표현하는 것을 의미한다. 이를 정점 임베딩이라고 하며, 정점이 표현되는 벡터공간을 임베딩 공간이라 칭한다. 주어진 그래프의 각 정점 $u$는 벡터표현의 $z_u$가 되는 것이며, 이를 입력과 출력의 관점으로 생각할 수 있다.

정점 임베딩은, 그래프의 정점 $u$를, $\mathbb{R}^d$공간의 벡터 $z_u$로 표현하는, 함수 $f$로 생각할 수 있다.

정점 표현 학습이 필요한 이유는, 벡터 형태를 요구하는 다양한 도구들을 사용할 수 있기 때문이다. 예를 들면, 머신러닝의 다양한 모델이나, 최적화 기법 등을 사용할 수 있게 된다.

정점 표현 학습의 목표는 그래프에서의 정점이 갖는 유사도를 임베딩 공간에서도 보존하는 것이다. 임베딩 공간에서의 유사도는 내적을 사용한다. 임베딩 공간의 $z_u$와 $z_v$가 유사한 방향과 크기를 갖는지 확인하기 위해 내적을 사용하는 것이다.

입력 그래프에서 각 정점의 유사도를 임베딩 공간에서 어떻게 잘 표현할 수 있을까?

즉, 정점 표현 학습은 다음 두 단계를 통해 이루어진다.

1. 그래프에서의 정점 유사도를 정의한다.

2. 정의한 유사도를 보존하도록 정점 임베딩을 학습한다.

인접성 기반 접근법

인접성 기반 접근법은 가장 단순한 형태로 정점의 유사도를 정의한다. 두 정점 $u$와 $v$사이에 간선이 있다면 유사도가 있는 것으로, 간선이 없다면 유사도가 없는 것으로 정의하는 것이다. 이를 인접행렬 $A$를 통해 표현하면 다음과 같다.

정점 1은 4와 유사도가 없지만, 5와는 유사도가 있다.

위와 같이 유사도를 정의했다면, 이 유사도를 잘 표현할 수 있도록 정점 임베딩을 학습시켜야 한다. 학습의 목적함수는 임베딩 공간에서의 유사도가 그래프에서의 유사도와 동일하도록 설계한다.

손실함수 $L$을 최소화하는 정점 임베딩을 학습시킨다.

위와 같이 인접성만으로 유사도를 판단하는 것은 많은 정보를 누락시킨다. 거리가 1 이상인 모든 정점에 대해서 유사도는 0으로 계산되며, 군집성과 같은 정보는 배제되기 때문이다.

정점 Blue 기준에서 Red와 Green은 동일한 값을 갖는다.

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

위와 같은 한계를 극복하기 위해 새로운 접근법이 등장했다.

거리 기반 접근법에서는 두 정점 사이의 거리가 '충분히' 가까운 경우 유사하다고 판단하는 것이다. 이 '충분히'의 기준은 연구자에 의해 결정되는 값 $k$이다.

$k$의 값이 2인 경우, 정점 Red는 Purple을 제외한 다른 모든 정점과 유사도를 갖는다.

경로 기반 접근법에서는 두 정점 사이의 경로가 많을수록 유사하다고 간주한다. 두 정점 사이의 경로 중 거리가 $k$인 것의 수를 세고, 이 값을 임베딩 공간에서도 표현하는 것이다.

$A^k_{u, v}$는 정점 $u,v$에 대해서 거리가 $k$인 경로의 수를 의미한다. 두 벡터의 내적이 해당 값과 유사할 수 있도록 학습하는 형태를 의미한다.

중첩 기반 접근법에서는 두 정점이 공유하는 이웃을 기준으로 유사하다고 판단한다.

정점 Red와 Blue는 2개의 이웃을 공유한다.

기본적인 중첩 기반 접근법은 각 이웃의 수 자체를 유사도 값으로 사용하므로, 다음과 같은 식을 도출할 수 있다.

각 노드의 성질이나, 이웃 노드의 성질을 고려하지 않고, 갯수로만 계산하는 접근법이다.

공통 이웃 수에서 그치지 않고, 다양한 방법으로 특성을 반영할 수 있다.

자카드 유사도는 공통 이웃의 비율을 계산하는 방식을 가진다. 각 노드가 몇개의 이웃을 가졌고, 그 중 몇개의 이웃을 공통으로 하는가를 유사도에 반영할 수 있는 것이다.

Adamic Adar 점수는 공통 이웃 각각에 가중치를 부여하는 방식을 가진다. 공통 이웃인 정점이 갖는 이웃수가 적을수록 높은 가중치를 갖게 된다.

두 점수 공통으로 갖지 않는 이웃에 대한 정보를 유사도에 반영한다.

임의보행 기반 접근법

임의보행 기반 접근법은 한 정점에서 시작해 임의보행을 하며 다른 정점에 도달할 확률을 유사도로 간주한다. 특정 정점을 시작으로 하여, 이웃 정점을 균일한 확률로 방문하는 것이다. 이를 통해 시작 정점 주변의 지역적 정보와 그래프 전역의 정보를 고려할 수 있다.

시작 정점 $u$ 주변의 정점의 정보도 포함되며, 횟수의 제약이 없기 때문에 그래프 전역의 정보도 포함된다.

임의보행 기반 접근법은 아래의 세 단계를 거친다.

임의보행 기반 접근법의 예시

$P(v|z_u)$는 정점 $u$에서 시작한 임의보행이 정점 $v$에 도달할 확률을 의미하고, 이는 다음과 같은 식으로 추정된다.

즉, $z^T_uz_v$가 높을수록 도달 확률이 높다.

이를 손실함수에 대입하면 다음과 같은 식이 완성된다.

위 손실함수를 줄이는 방향으로 학습을 해야하나, 계산의 양이 매우 방대하다.

임의보행 기반의 알고리즘으로는 DeepWalk와 Node2Vec이 있다. DeepWalk는 위와 같이 동일한 확률로 선택하여 이동하는 과정으로 수행된다. Node2Vec은 이동 시 차등적인 확률을 사용한다. 이를 '2차 치우친 임의보행'이라 칭한다.

세 방향에 대해 가중치를 부여하여, 차등적인 확률로 이동한다.

차등적인 확률을 통해 유사도를 정의하고, 임베딩하게 되면 각각 다른 형태의 임베딩 결과를 얻을 수 있다. 아래의 그림은 임베딩 후 K-means 군집분석을 한 결과이다.

멀어지는 방향에 높은 확률을 부여한 경우, 각 정점의 역할에 따라 임베딩이 수행되었다. 가까워지는 방향에 높은 확률을 부여한 경우, 각 정점의 군집에 따라 임베딩이 수행되었다.

위에서 살펴본 손실함수는 중첩된 Summation 연산을 포함하고 있어 매우 큰 자원을 요구한다. 따라서, 많은 경우에 근사식을 사용해 손실함수를 재정의한다. 기본적인 아이디어는, 모든 정점에 대해 정규화 하는 것이 아니라 몇개의 정점만을 뽑아서 비교하는 것이다. 이때 뽑힌 정점을 '네거티브 샘플'이라고 하며, 네거티브 샘플이 많을수록 학습이 안정적일 수 있다.

손실 함수에 대한 근사 예시

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

위의 방법은 모두 변환식 방법에 속한다. 변환식이란 의미는 학습의 결과로 정점의 임베딩 자체를 얻는다는 것이다.

변환식 정점 표현 학습의 출력은 $z_u$와 같은 벡터일 뿐, 함수에 해당하는 Encoder자체를 얻지 못한다.

변환식 임베딩은 다음과 같은 한계를 갖는다.

변환식 임베딩의 한계 예시

변환식 임베딩과는 다르게, Encoder 자체를 출력으로 받는 학습 방법을 '귀납식 임베딩'이라고 한다. 귀납식 임베딩의 대표적인 방법이 '그래프 신경망(GNN)'이다.

실습 코드

Node2Vec

---

[Graph 8강] 그래프를 추천시스템에 어떻게 활용할까? (심화)

💡

넷플릭스 챌린지에 대해 소개하고, 잠재 인수 모형과 같은 추천 시스템의 알고리즘에 대해 알아본다.

넷플릭스 챌린지 소개

넷플릭스 챌린지는 추천 시스템을 머신러닝의 한 분야로 인정 받게끔 많은 성과를 거둔 경진대회이다. 이를 통해 추천 시스템의 다양한 방법이 제시되었고, 성능이 비약적으로 향상되었다.

데이터는 사용자별 영화 평점 데이터가 사용되었다. 훈련 데이터로는 48만명의 사용자와 1만 8천개의 영화에 대한 1억개의 평점으로 구성되어 있었으며, 평가 데이터는 사용자의 최신 평점 280만개로 구성되어 있었다.

넷플릭스 챌린지의 목표는 추천 시스템의 성능을 10%이상 향상시키는 것이었고, 이에 참가한 다양한 팀의 시도가 현재에도 사용되고 있다.

기본 잠재 인수 모형

잠재 인수 모형은 넷플릭스 챌린지에서 제시되어, 가장 큰 성능 개선을 만든 아이디어이다. 이 아이디어의 핵심은 사용자와 상품을 벡터로 표현하는 것이다.

사용자와 상품을 임베딩 공간의 벡터로 표현하고자 하는 것이다.

즉, 사용자의 성향과 영화의 특성을 임베딩 공간에서 표현하려고 한 시도였다. 사용자와 영화가 벡터 형태로 표현되었을 경우, 내적을 통해 유사도를 구할 수 있을 것이다.

각 사용자가 임베딩 된 공간과 영화와의 유사도를 구할 수 있을 것이다.

이 때, 사용자의 성향이나 영화의 특성을 수치로 표현하는 데에는 어려움이 있기 때문에, 고정된 인수 대신 잠재 인수를 사용하고자 했다.

각 축의 특성을 형용할 수는 없으나, 사용자와 영화를 특정 공간에 표현할 수 있는 기준이 된다.

사용자와 상품을 특정 벡터 공간으로 임베딩하는 기준은 다음과 같다. 사용자와 상품의 임베딩을 내적한 값이 평점과 최대한 유사하도록 하는 것이다.

이와 같이 임베딩 할 수 있는 모델을 학습시킨다.

모델의 학습을 위해 손실함수는 다음과 같이 정의할 수 있을 것이다.

훈련 데이터에 명시적으로 존재하는 점수를 Ground Truth로 사용한다.

이 때, 훈련 데이터에 과적합 되지 않도록 각 항에 정규화 Term을 추가하여 식을 개선한다.

각 항의 계수가 과하게 커지지 않도록 규제한다. $\lambda$가 커질수록 모델의 복잡도가 낮아진다.

고급 잠재 인수 모형

기본적인 잠재 인수 모형을 기반으로 각종 고려사항을 추가한 모델이 제시되었다.

먼저, 편향을 고려하는 모델이 제시되었다. 편향은 특정 사용자나 상품의 경향을 의미한다. 예를 들어, 사용자 편향은 점수를 후하게 주는 경향이 있는지 혹은 박하게 주는 경향이 있는지를 고려하는 것이다. 이러한 편향은 사용자와 상품 모두 존재하며, 이 둘 사이의 상호작용까지 고려할 수 있다.

각 편향과 상호작용에 대한 예시

이러한 편향까지 고려하는 모델의 손실함수는 다음과 같다.

이 손실함수를 최소화하도록 모델을 학습시킨다.

평점에 대해 사용자와 상품 외적인 요인으로 시간을 꼽을 수 있다. 예를 들면, 넷플릭스 자체의 UX 개선으로 사용자가 일제히 평점을 높게 줄 수도 있고, 영화는 출시일 이후 시간이 지날수록 평점이 상승하는 경향을 보인다.

이러한 시간적 편향까지 고려하여, 사용자 편향과 상품 편향을 시간에 따라 변하는 것으로 가정할 수 있다.

Time Step을 의미하는 (t)가 추가되었다.

위와 같은 시도들을 통해 넷플릭스 챌린지는 성공적으로 마무리 되었으며, 추천시스템은 큰 발전을 이루었다.

실습 코드

Latent Factor based Recommendation System

---

Reference

Node2Vec Paper

Deep Walk Paper

Explain Recommendation System

Explain Matrix Factorization

Uploaded by Notion2Tistory v1.1.0