해당 포스팅은 네이버 부스트캠프 AI Tech 학습 정리 자료임을 알려드립니다.
1. 강의 정리
신기정 교수님 - 그래프의 정점을 어떻게 벡터로 표현할까?
1) 정점 표현 학습
정점 표현 학습은 그래프의 정점들을 벡터의 형태로 표현하는 것을 말합니다. 이를 간단하게 정점 임베딩(Node Embedding)이라고도 부릅니다. 정점 임베딩은 벡터 형태의 표현 그 자체를 의미하기도 합니다. 이렇게 정점이 표현되는 벡터 공간을 임베딩 공간이라고 부릅니다. 주어진 그래프의 정점 $u$에 대한 임베딩 즉, 위에서 표현한 것과 같이 $Z_{u}$가 정점 임베딩의 출력입니다.
위의 그림처럼 정점을 벡터로 임베딩하게 되면 벡터 형태의 데이터를 위한 도구들을 그래프에도 적용이 가능해집니다. 한가지 예시로 로지스틱 회귀분석, 다층 퍼셉트론과 같은 분류기와 K-means, DBSCAN과 같은 군집 분석 알고리즘은 모두 벡터 형태로 표현된 인스턴스들을 입력으로 받습니다. 그래서 정점을 벡터 형태로 표현할 수 있다면 위에서 언급한 알고리즘 외에도 다양한 학습도구들을 정점 분류와 군집 분석에 활용할 수 있습니다.
그러면 어떤 기준으로 정점을 벡터로 변환해야 할까요? 정점 표현 학습은 그래프에서의 정점간 유사도를 임베딩 공간에서도 보존하는 것을 목표로 합니다. 임베딩 공간에서의 유사도로는 내적(Inner Product)를 사용합니다. 우리가 임베딩한 벡터를 각각 $Z_{u}$와 $Z_{v}$라고 했을 때의 내적 값은 아래의 식으로 구할 수 있습니다.
$$ Z_{v}^{T}Z_{u} = ||Z_{u}||\cdot ||Z_{v}|| \cdot cos(\theta)$$
내적 값이 클 수록 같은 방향을 향하는 것을 알 수 있습니다. 그러면 정점의 유사도는 어떻게 정의할 수 있을까요? 정점의 유사도는 다음에 3가지 접근법을 통해서 알아보겠습니다.
2) 인접성 기반 접근법
인접성(Adjacency) 기반 접근법에서는 두 정점이 인접할 때 유사하다고 간주합니다. 여기서 인접하다의 의미는 두 정점 $u$와 $v$를 직접 연결하는 간선 $(u, v)$가 있는 것과 같습니다. 위의 그림처럼 각 정점들이 다른 정점들을 연결하는 간선이 있는 경우 행렬 값을 1로, 없다면 0으로 해서 인접행렬을 구성할 수 있습니다. 인접성 기반 접근법의 손실함수는 아래와 같습니다.
$$ \mathcal{L} = \sum_{(u,v) \in V \times V} ||z_{u}^{T}z_{v} - A_{u,v}||^2 $$
위의 식에서 임베딩 공간에서의 유사도를 그래프에서의 유사도인 $A_{u,v}$의 차이로 구한 값을 모든 정점에 대해 합산한 손실함수를 최소화 하는 확률적 경사하강법을 이용합니다.
하지만, 인접성만으로 유사도를 판단하는 것은 한계가 있습니다. 위의 그림에서 빨간색 정점과 파란색 정점의 거리는 3이고, 파란색과 초록색 정점은 거리가 2이지만 인접성만을 고려할 경우 거리에 대한 고려 없이 두 경우의 유사도는 0으로 동일하게 됩니다. 또한 빨간색 정점은 파란색과 다른 군집에 속하고, 초록색과 파란색 정점은 같은 군집에 속함에도 두 개의 유사도는 0으로 동일합니다. 이렇게 인접성만을 유사도로 판단하는 것은 거리와 군집관계를 무시하는 한계가 존재합니다.
3) 거리/경로/중첩 기반 접근법
먼저, 거리 기반 접근법에서는 두 정점 사이의 거리가 충분히 가까운 경우 유사하다고 간주합니다. 위의 그림의 빨간색 정점은 초록색 정점들과의 거리는 1이고, 파란색 정점과는 2만큼 거리를 가지고 있습니다. 여기서, 충분히 가깝다의 정의를 2라고 했다고 하면, 2의 거리까지의 정점들은 유사하다고 간주해서 유사도가 1이 됩니다. 하지만, 보라색 정점은 빨간색을 기준으로 3만큼 떨어져 있기 때문에 충분히 유사하지 않기 때문에 유사도가 0이 됩니다.
두 번째로 경로 기반 접근법에 대해 알아보면, 경로 기반 접근법은 두 정점 사이의 경로가 많을 수록 유사하다고 간주합니다. 두 정점 $u$와 $v$의 사이의 경로 중 거리가 $k$인 것의 수는 $A_{u,v}^{k}$와 같습니다. 즉 인접행렬 $A$의 $k$ 제곱의 $u$행 $v$열 원소와 같습니다. 경로 기반 접근법의 손실 함수는 다음과 같습니다.
$$ \mathcal{L} = \sum_{(u,v) \in V \times V} ||z_{u}^{T}z_{v} - A_{u,v}^{k}||^2 $$
마지막으로 중첩 기반 접근법에서는 두 정점이 많은 이웃을 공유할 수록 유사하다고 간주합니다. 위의 그림에서 빨간색 정점은 파란색 정점과 두 명의 이웃을 공유하기 때문에 유사도는 2가 됩니다. 정점 $u$의 이웃 집합을 $N(u)$, 정점 $v$의 이웃 집합을 $N(v)$라고 하면 두 정점의 공통 이웃 수 $S_{u,v}$는 다음과 같이 정의됩니다.
$$ S_{u,v} = |N(u) \cap N(v)| = \sum_{w \in N(u)\cap N(v)} 1$$
중첩 기반 접근법의 손실 함수는 다음과 같이 표현할 수 있습니다.
$$ \mathcal{L} = \sum_{(u,v) \in V \times V} ||z_{u}^{T}z_{v} - S_{u,v}^{k}||^2 $$
여기서 사용하는 공통 이웃 수를 대신 자카드 유사도나 Adamic Adar 점수를 사용할 수도 있습니다. 자카드 유사도는 공통 이웃의 수 대신 비율을 계산하는 방식으로 아래와 같이 표현합니다.
$$ 0 \leq \frac{|N_{u} \cap N_{v}|}{|N_{u}\cup N_{v}|} \leq 1 $$
Adamic Adar 점수는 공통 이웃 각각에 가중치를 부여하여 가중합을 계산하는 방식으로 아래와 같이 표현할 수 있습니다.
$$\sum_{w \in N_{u}\cap N_{v}} \frac{1}{d_{w}} $$
예를 들어서, BTS에게는 엄청난 팔로워가 있기 때문에 내가 BTS에게 팔로우를 하게 되면 그 팔로워들은 거리가 가깝게 되는 현상을 방지하는 방법이라고 생각하시면 될 것 같습니다. 영향력이 클 수록 가중치는 작게 줍니다.
4) 임의 보행 기반 접근법
임의보행 기반 접근법에서는 한 정점에서 시작하여 임의보행을 할 때 다른 정점에 도달할 확률을 유사도로 간주합니다. 임의보행은 현재 정점의 이웃 중 하나를 균일한 확률로 선택해서 이동하는 과정을 반복하는 것을 의미합니다. 임의 보행을 사용할 경우 시작 정점 주변의 지역적 정보와 그래프 전역 정보를 모두 고려할 수 있다는 장점이 있습니다. 여기서 그래프 전역 정보를 고려한다는 것은 거리 제한을 두지 않기 때문에 그래프 전체를 돌아다닐 수 있게 됩니다.
임의보행 기반 접근법은 세 단계를 거칩니다.
-
각 정점에서 시작하여 임의보행을 반복 수행합니다.
-
각 정점에서 시작한 임의보행 중 도달한 정점들의 리스트를 구성합니다. 이때, 정점 $u$에서 시작한 임의보행 중 도달한 정점들의 리스트를 $N_{R}(u)$라고 하고, 한 정점을 여러 번 도달한 경우, 해당 정점은 $N_{R}(u)$에 여러 번 포함될 수 있습니다.
-
손실함수를 최소화하는 임베딩을 학습합니다.
여기서 사용되는 손실함수는 아래와 같습니다.
$$ \mathcal{L} = \sum_{u \in V} \sum_{v \in N_{R}(u) } -log(P(v|z_{u})) $$
여기에 표현된 $P(v|z_{u})$는 $u$에서 시작한 임의보행이 $v$에 도달할 확률을 임베딩으로부터 추정한 결과를 의미합니다. 그렇다면 임베딩으로부터 도달 확률을 어떻게 추정할 수 있을까요? 아래의 식을 통해서 추정이 가능합니다.
$$ P(v|z_{u}) = \frac{exp(z_{u}^{T}z_{v})}{\sum_{n \in V} exp(z_{u}^{T}z_{n})} $$
식의 특성상 유사도 $z_{v}^{T}z_{u}$가 높을 수록 도달 확률이 높습니다.
임의 보행의 방법에 따라 DeepWalk와 Node2Vec이 구분됩니다.
DeepWalk는 앞서 설명한 기본적인 임의보행을 사용합니다. 즉, 현재 정점의 이웃 중 하나를 균일한 확률로 선택해서 이동하는 과정을 반복합니다.
Node2Vec은 2차 치우친 임의보행(Second-order Biased Random Walk)을 사용합니다. 현재 정점($v$)과 직전에 머물렀던 정점($u$)을 모두 고려하여 다음 정점을 선택합니다. 직전 정점의 거리를 기준으로 경우를 구분하여 차등적인 확률을 부여합니다. Node2Vec에서는 부여하는 확률에 따라서 아래 그림처럼 다른 종류의 임베딩을 얻습니다.
왼쪽 그림은 멀어지는 방향에 높은 확률을 부여한 경우로, 정점의 역할(다리 역할, 변두리 정점 등)이 같은 경우 임베딩이 유사합니다. 오른쪽 그림은 가까워지는 방향에 높은 확률을 부여한 경우로, 같은 군집(Community)에 속한 경우 임베딩이 유사합니다.
임의보행 기법의 손실함수는 계산할 때, 정점의 수의 제곱에 비례하는 시간이 소요됩니다. 중첩된 합 때문에 그렇습니다. 그래서 정점이 많은 경우, 구하기가 어렵습니다. 이를 해결하기 위해서 많은 경우 근사식을 사용합니다.
모든 정점에 대해서 정규화하는 대신 몇 개의 정점을 뽑아서 비교하는 형태입니다. 이때, 뽑힌 정점들을 네거티브 샘플이라고 부릅니다.
$$ log (\frac{exp(z_{u}^{T}z_{v})}{\sum_{n \in V} exp(z_{u}^{T}z_{n})}) \approx log(\sigma (z_{u}^{T}z_{v})) - \sum_{i=1}^{k} log(\sigma (z_{u}^{T}z_{n_{i}})), \, n_{i} \sim P_{V} : 확률분포 $$
연결성에 비례하는 확률로 네거티브 샘플을 뽑으며, 네거티브 샘플이 많을 수록 학습이 더욱 안정적입니다. (손실함수 근사부분 이해 필요)
5) 변환식 정점 표현 학습의 한계
지금까지 소개한 정점 임베딩 방법들은 변환식(Transductive) 방법입니다. 변환식 방법은 학습의 결과로 정점의 임베딩 자체를 얻는다는 특성이 있습니다. 정점을 임베딩으로 변화시키는 함수, 즉 인코더를 얻는 귀납식 방법과 대조됩니다.
이러한 변환식 임베딩 방법은 여러 한계를 가집니다.
-
학습이 진행된 이후에 추가된 정점에 대해서는 임베딩을 얻을 수 없습니다.
-
모든 정점에 대한 임베딩을 미리 계산해서 저장해야 합니다.
-
정점이 속성 정보(부가 정보)를 가진 경우에 이를 활용할 수 없습니다.
이런 단점을 극복한 귀납식 임베딩 방법인 그래프 신경망은 추후에 소개할 예정입니다.
신기정 교수님 - 그래프를 추천시스템에 어떻게 활용할까?
1) 넷플릭스 챌린지 소개
넷플릭스 챌린지에서는 사용자별 영화 평점 데이터를 활용해서 추천시스템의 성능을 10%이상 향상시키는 대회였습니다. 훈련데이터는 2000년부터 2005년까지 수집한 48만명 사용자의 1만 8천개의 영화에 대한 1억 개의 평점으로 구성했으며, 평가 데이터는 각 사용자의 최신 평점 280만개로 구성되었습니다. 평균 제곱근 오차를 0.9514에서 0.8563까지 낮출 경우 100만불의 상금을 받는 조건이였고, 이것을 계기로 추천시스템의 성능이 비약적으로 발전했습니다.
2) 잠재 인수 모형
잠재 인수 모형(Latent Factor Model)의 핵심은 사용자와 상품을 벡터로 표현하는 것입니다. SVD, UV Decomposition이라고 부르기도 합니다. 위의 그림은 영화와 사람을 벡터로 임베딩해서 표현한 결과입니다. 기존에 부여된 가벼운 영화, 로맨스와 같이 고정된 인수 대신 효과적인 잠재 인수를 학습하는 것을 목표로 합니다.
사용자와 상품을 임베딩하는 기준은 임베딩 내적이 최대한 평점과 유사하도록 하는 것 입니다. 사용자 $x$의 임베딩을 $p_{x}$, 상품 $i$의 임베딩을 $q_{i}$, 사용자 $x$의 상품 $i$에 대한 평점을 $r_{xi}$라고 하면, 임베딩의 목표는 $p_{x}^{T}q_{i}$가 $r_{xi}$와 유사하도록 하는 것 입니다.
사용자 수의 열과 상품 수의 행을 가진 평점 행렬을 $R$이라고 하고, 사용자들의 임베딩 행렬을 $P$, 영화들의 임베딩 행렬을 $Q$이라고 했을 때, 위의 그림처럼 표현할 수 있습니다.
잠재 인수 모형은 다음 손실 함수를 최소화하는 $P$와 $Q$를 찾는 것을 목표로 합니다.
$$ \sum_{(i,x) \in R}(r_{xi} - p_{x}^{T}q_{i})^2 $$
위의 식을 계산할 때에는 훈련 데이터에 있는 평점에 대해서만 계산을 합니다. 하지만, 위 손실 함수를 사용할 경우 과적합이 발생할 수 있습니다. 여기서의 과적합은 기계학습 모형이 훈련 데이터의 잡음(Noise)까지 학습하여, 평가 성능은 오히려 감소하는 현상을 의미합니다. 그래서 과적합을 방지하기 위한 방법으로 l2-정규화 항을 손실 함수에 더해주면 아래와 같은 식을 얻을 수 있습니다.
$$ \sum_{(i,x) \in R}(r_{xi} - p_{x}^{T}q_{i})^2 + [\lambda_{1} \sum_{x}||p_{x}||^2 + \lambda_{2} \sum_{x}||q_{i}||^2] $$
(이 식에 대한 설명은 추가적으로 필요), 정규화는 극단적인, 즉 절댓값이 너무 큰 임베딩을 방지하는 효과가 있습니다. 그렇게 하게 되면, 취향이 너무 확고해도 좀 더 다양한 추천을 할 수 있도록 완화해줍니다.
손실함수를 최소화하는 $P$와 $Q$를 찾기 위해서는 (확률적) 경사하강법을 사용합니다. 경사하강법은 손실함수를 안정적으로 하지만 느리게 감소시킵니다. 확률적 경사하강법은 손실함수를 불안정하게 하지만 빠르게 감소시킵니다. 실제로는 확률적 경사하강법을 더 많이 사용합니다.
3) 고급 잠재 인수 모형
고급 잠재 인수 모형에는 사용자와 상품의 편향을 모형과 시간에 따른 편향을 고려한 모형이 존재합니다. 먼저 사용자의 편향은 해당 사용자의 평점 평균과 전체 평점 평균의 차입니다. 그래서 각 사용자의 평균 평점이 전체 사용자의 평균 평점보다 높으면 후하게 평점을 주는 경향이 있는 것입니다. 상품의 편향도 사용자의 편향과 동일한 방식으로 해당 상품에 대한 평점 평균과 전체 평점 평균의 차로 구할 수 있습니다.기존에 있던 상호작용에 위에서 언급한 사용자 편향과 상품 편향, 전체 평균을 포함해서 개선된 잠재 인수 모형에서의 평점을 정의할 수 있습니다.
개선된 잠재 인수 모형의 손실 함수는 아래와 같습니다.
$$ \sum_{(i,x) \in R} (r_{xi} - ( \mu + b_{x} + b_{i} + p_{x}^{T}q_{i})^2 + [\lambda_{1} \sum_{x}||p_{x}||^2 + \lambda_{2} \sum_{x}||q_{i}||^2 + \lambda_{3} \sum_{x}b_{x}^2 + \lambda_{4} \sum_{x}b_{i}^2] $$
(확률적) 경사하강법을 통해 손실 함수를 최소화하는 잠재 인수와 편향을 찾아냅니다.
이번에는 시간적 편향을 고려한 잠재 인수 모형을 이야기해보려고 합니다. 넷플릭스 시스템의 변화로 평균 평점이 크게 상승하는 사건이 있었습니다. 중간에 시스템 평점에 대해 변동사항이 있었기 때문일 것이라고 생각합니다. 또한 영화의 평점은 출시일 이후 시간이 지남에 따라 상승하는 경향을 갖습니다. 이렇게 시간적 편향을 고려하기 위해 사용자 편향과 상품 편향을 시간에 따른 함수로 가정하고 평점을 아래의 수식으로 표현합니다.
$$ r_{xi} = \mu + b_{x}(t) + b_{i}(t) + p_{x}^{T}q_{i} $$
이렇게 다양한 인수 모형을 넷플릭스 챌린지에 적용한 결과는 위에 보시는 바와 같습니다. 하지만, 아직도 목표 오차에 도달하지 못하는 모습을 볼 수 있습니다.
4) 넷플릭스 챌린지의 결과
BellKor 팀은 앙상블 학습을 사용해서 처음으로 목표 성능에 도달했고 다른 팀들도 앙상블을 통해서 목표 성능에 도달했습니다. 두 팀의 오차는 정확하게 동일했으나, BellKor팀이 더 빨리 제출했기 때문에 우승으로 돌아가게 되었습니다.
