Contents

Node Representation Learning
Latent Factor Model(잠재 인수 모형)

그래프의 정점을 벡터로 표현하는 방법인 정점 임베딩(Node Embedding)에 대해서 배웁니다. 기계학습의 다양한 툴은 벡터로 표현된 데이터를 입력으로 받습니다. 이번 강의에서는 그래프의 정점(Node)을 벡터로 표현하는 방법인 정점 임베딩(Node Embedding)에 대해 배웁니다. 정점을 어떻게 벡터로 표현하는지, 정점 사이의 유사성을 어떻게 표현하는지 집중하며 공부합니다.

Node Representation Learning

In this section, we study several methods to represent a graph in the embedding space. By “embedding” we mean mapping each node in a network into a low-dimensional space, which will give us insight into nodes’ similarity and network structure. Given the widespread prevalence of graphs on the web and in the physical world, representation learning on graphs plays a significant role in a wide range of applications, such as link prediction and anomaly detection. However, modern machine learning algorithms are designed for simple sequence or grids (e.g., fixed-size images/grids, or text/sequences), networks often have complex topographical structures and multimodel features. We will explore embedding methods to get around the difficulties.

What is Node Representation?

정점 표현학습 : 그래프의 Vertices를 vector로 표현하는 것

정점 표현 학습(Node Representation Learning)은 정점 임베딩(Node Embedding)이라고도 부른다.
node embedding은 vector 형태의 표현 그 자체를 의미하기도 한다.
정점이 표현되는 vector space를 Embedding Sapce라고 부른다.
node representation learning의 입력(input)은 graph이다.
주어진 graph의 각 vertex $u$에 대한 embedding, 즉 vector representation $z_u$는 node embedding의 output이다.

The reasons of Node embedding

node embedding을 진행함으로써 vector 형태의 데이터를 위한 도구를 그래프에 적용할 수 있다.
- 많은 분류기, Clustering 알고리즘 등은 벡터 형태로 표현된 instance를 입력으로 받는다.
- 그래프 정점 분류, 군집 분석 등에 사용할 수 있다.

Goal of Node embedding

Node embedding의 목표는 임베딩 공간에서의 유사성이 원래 graph network에서의 유사성과 유사하도록 node를 encoding하는 것에 그 목표를 두고 있다. 즉, graph 내에서 유사도가 높은 두 점은 임베딩 공간에서도 유사도가 높도록 하는 것이 목표이다.

The goal of node embedding is to encode nodes so that similarity in the embedding space (e.g., dot product) approximates similarity in the original network, the node embedding algorithms we will explore generally consist of three basic stages:

앞서 node embedding의 목표를 graph와 embedding space에서 유사도를 보존하기 위함으로 설명했다. 그렇다면 여기서 말하는 Graph structure와 embedding space에서의 유사도는 각각 어떻게 정의될까?

Embedding space : Inner product($z_v^\top z_u = \vert\vert z_u\vert\vert\cdot\vert\vert z_v\vert\vert\cdot cos(\theta)$)로 유사도를 표현한다.
Graph structure : similarity($u,v$)
- 이 때, Graph에서의 두 정점간 유사도를 정의하는 방식은 여러가지가 있다.
- 본 포스팅에서는 Adjency-base, distance-based, path-based, nesting-based, random walk based에 대해 간략히 소개한다.

결국, 정리하자면 Node embedding은 다음 두 단계로 이루어진다고 할 수 있다.

그래프 구조에서의 similarity define
step 1.에서 정의한 similarity가 $z_v^\top z_u$로 수렴하도록 학습하는 단계. 즉, 이 부분에 해당하는 내용을 Loss function으로 사용한다고 생각하면 이해하기 쉽다.

Graph similarity

그렇다면 앞서 말한 graph에서의 두 정점의 유사성에 대해 알아보자. 위에서도 언급했듯이 여러 similarity 정의가 있지만, 여기서는 총 5개의 유사도에 대해 설명하고자 한다.

Adjacency 기반 접근법

두 정점이 인접할 때 유사하다고 간주한다. 즉, 두 정점 $u, v$가 인접하다는 것은 두 정점을 연결하는 edge $(u, v)$가 있음을 의미한다.

$\vert V\vert$가 $n$인 graph의 Adjacency matrix $A_{u,v}$는 $n\times n$의 크기를 가지며 각 정점 $u,v\in V$간에 서로 인접한 경우 1 아닌경우 0으로 표현되는 matrix를 말한다. 이때, 인접행렬(Adjacency matrix)의 두 정점 $u,v$의 유사도로 가정한다.

이 때의 인접성 기반 접근법의 손실함수는 다음과 같다.

\[\mathcal{L}=\sum_{(u,v)\in V\times V}\vert\vert z_u^\top z_v - \mathbf{A}_{u,v}\vert\vert^2\]

즉, 이 손실 함수 $\mathcal{L}$이 최소가 되는 node embedding을 찾는 것을 목표로 한다. 이 loss function의 최소화를 위해서는 (stochastic) gradient descent를 사용한다.

하지만 이러한 인접성 기반의 유사도 판단은 한계가 있다.

위 그림에서 빨간색점은 파란색 점과의 거리 3이고, 초록색 점은 파란색 점과의 거리가 2로 초록색이 파란색에 더 유사하다고 할 수 있다. 하지만, 직접 연결된 edge가 없기에 adjacency matrix에서의 각 관계를 표현하는 값은 0으로 표현된다. 또한, 군집의 경우에도 고려되지 않는다.

이러한 인접성 기반 접근법의 한계를 개선하고자 다양한 접근법이 구상되었다.

Distance 기반 접근법

거리 기반 접근법은 두 정점 사이의 거리가 충분히 가까운 경우 유사하다고 간주한다. 두 정점의 기준 거리를 정해놓고, 두 정점이 기준 거리 이내일 때 1 그렇지 않을 때 0으로 간주하는 방식이다.

위 그림의 경우, 빨간점과 초록, 파랑은 유사하고, 보라색은 그렇지 않다.

Path 기반 접근법

경로 기반 접근법에서는 두 정점 사이의 경로가 많을 수록 유사하다고 간주하는 방식이다. 정점 $u$와 $v$ 사이의 Path의 정의는 다음의 두 조건을 만족하는 Sequence라고 할 수 있다.

$u$에서 시작해서 $v$에서 끝나야한다.
순열에서 연속된 정점은 간선으로 연결되어야 한다.

위 그림에서 정점 1에서 8로 가는 path를 살펴보면, 1, 4, 6, 8의 경로를 생각해볼 수 있다. 하지만, 1, 6, 8에서 (1,6)은 직접적인 edge로 연결되어 있지 않으므로 path라고 할 수 없다.

두 정점 $u$와 $v$ 사이의 경로중 거리가 $k$인 것의 수는 $A_{u,v}^k$와 같다. 이 때, $A_{u,v}$는 $u$와 $v$ 사이의 인접행렬을 말하며, 인접행렬의 $k$ 제곱의 $u$행 $v$열 원소와 같다.

이 방식에서의 경로기반 접근법 손실함수(loss function)은 다음과 같다.

\[\mathcal{L}=\sum_{(u,v)\in V\times V}\vert\vert z_u^\top z_v - \mathbf{A}_{u,v}^k\vert\vert^2\]

중첩 기반 접근법

두 정점이 많은 이웃을 공유할 수록 유사하다고 간주하는 방식의 접근법이다. 아래 그림에서 빨간색 정점은 파란색 정점과 두 명의 이웃을 공유하기 때문에 유사도는 2가 된다.

정점 $u$의 이웃 집합을 $N(u)$, 그리고 정점 $v$으 이웃 집합을 $N(v)$라고 할때, 두 정점의 공통 이웃 수 $S_{u,v}$는 다음과 같이 정의된다.

\[S_{u,v}=\vert N(u)\cap N(v)\vert=\sum_{w\in N(u)\cap N(v)}1\]

중첩 기반 접근법의 손실 함수는 다음과 같다.

\[\mathcal{L}=\sum_{(u,v)\in V\times V}\vert\vert z_u^\top z_v - S_{u,v}\vert\vert^2\]

이와 유사하게 자카드 유사도(Jaccard Similarity) 혹은 Adamic adar score를 사용할 수도 있다.

자카드 유사도는 공통 이웃의 수 대신 비율을 계산하는 방식이다.
\[\frac{\vert N_u\cap N_v\vert}{\vert N_u\cup N_v\vert}\]
이 자카드 유사도는 항상 0에서 1 사이의 값을 가진다. 이 때, 1의 값을 가지기 위해서는 두 정점 $u,v$의 이웃들의 집합인 $N(u)$와 $N(v)$가 정확히 같을 때 ($N(u)=N(v)$) 1의 값을 갖는다.
Adamic Adar 점수는 공통 이웃 각각에 가중치를 부여하여 가중 합을 계산하는 방식이다.
\[\sum_{w\in N_u\cap N_v}\frac{1}{d_w}\]
여기서 $d_w$는 $u$와 $v$가 공통적으로 이웃인 점 $w$의 degree를 의미한다.
예를 들어 $u$와 $v$가 공통으로 follow하는 트와이스 계정 $w$가 있다고 가정하자. 두 점 모두 트와이스 계정을 팔로우하고 있지만, 그렇다고 해서 $u$와 $v$에 큰 유사성을 부여하기는 어렵다. 그 이유는 트와이스 계정을 팔로우하고 있는 수백만 명의 팔로워 중 두 명일 뿐이기 때문이다. 따라서 트와이스 계정 $w$의 degree로 나눠주어 가중치를 줄이는 방식으로 계산을 하게 된다.

Random walk 기반 접근법

graph 구조에서 경로와 비슷한 개념인 보행(Walk)에 대해 먼저 정의하자. path와 기본적으로 비슷하지만, 변이 중복될 수 있는 경우를 walk라고 한다.

자세한 설명은 이 곳에서 확인할 수 있다. Walk, trail, path에 대한 개념을 구분하고 가는 것을 추천한다.

임의보행이란 현재 정점의 이웃 중 하나를 균일한 확률로 선택하는 이동하는 과정을 반복하는 것을 의미한다. 이 방식은 시작 node 주변의 지역적 정보와 그래프 전역 정보를 모두 고려한다고 할 수 있다. 거리를 제한하지 않고 확률적으로 전 그래프 전체 범위를 검사하기 때문이다.

Random-walk 기반 접근법은 다음 세 단계를 거친다.

각 정점에서 시작하여 random walk를 반복 수행한다.
각 정점에서 시작한 임의보행 중 도달한 정점들의 리스트를 구성한다. 이 때, 정점 $u$에서 시작한 임의보행 중 도달한 정점들의 리스트를 $N_R(u)$라고 한다. 한 정점을 여러 번 도달한 경우, 해당 정점은 $N_R(u)$에 여러 번 포함될 수 있다.
다음 손실함수를 최소화하는 임베딩을 학습한다.
\[\mathcal{L}=\sum_{u\in V}\sum_{v\in N_R(u)}-\text{log}(P(v\vert \mathbf{z}_u))\]
위 식에서 로그가 씌워지는 확률 $P(v\vert \mathbb{z}_u)$는 $u$에서 시작한 임의보행이 $v$에 도달할 확률을 임베딩으로부터 추정한 결과를 의미한다. 이 확률값은 크면 클 수록 추정을 잘 한 것이다.

그렇다면 임베딩으로부터 도달 확률을 어떻게 추정할까? 위 손실함수(loss function)에서의 정점 $u$에서 시작한 임의보행이 정점 $v$에 도달할 확률 $P(v\vert \mathbb{z}_u)$은 다음과 같이 추청한다.

\[P(v\vert \mathbb{z}_u)=\frac{exp(z_u^\top z_v)}{\sum_{n\in V}exp(z_u^\top z_v)}\]

즉, 유사도 $z_u^\top z_v$가 높을 수록 도달 확률이 높다. 결국 식은 다음과 같다.

\[\mathcal{L}=\sum_{u\in V}\sum_{v\in N_R(u)}-\text{log}(\frac{exp(z_u^\top z_v)}{\sum_{n\in V}exp(z_u^\top z_v)})\]

여기서 로그가 씌워진 부분은 임베딩으로부터 추정한 도달 확률
첫번째 summation(안쪽)은 임의보행 중 마주친 모든 정점에 대한 합산
두번째 summation(바깥쪽)은 모든 시작점에 대한 합산

이 손실함수를 완성하고 이를 최소화하는 방식으로 임베딩 학습을 한다.

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

Deepwalk는 앞서 설명한 기본 임의보행을 사용한다. 즉, 현재 정점의 이웃 중 하나를 균일한 확률로 선택하는 이동과정을 반복한다.
Node2Vec은 2차 치우친 임의보행(Second-order Biased Random Walk)를 사용한다.
- 여기서 SBRW는 현재 정점 뿐만 아니라 직전에 머문 정점까지 고려하여 다음 정점을 선택하는 방식을 말한다.
- 직전 정점의 거리를 기준으로 케이스를 구분하여 차등적인 확률을 부여한다.
- 예를 들어 직전 정점 : $u$, 현재 정점 : $v$일 때, 다음 도달할 정점의 확률은 위와 같은 원리로 차등 부여한다. $x$의 경우는 $u$에서 1이고, $u$와 $v$의 거리도 1이므로 거리가 유지되는 방향이다. 비슷한 원리로 $v$에서 바라봤을 때, $u$는 이전 정점과 가까워지는 방향이고, $y$는 멀어지는 방향이다.
- 이 세 가지 방향을 구분하여 확률을 차등 적용하고, 이 방식은 사용자가 지정 가능하다.
- 이 방식에 따라 전혀 다른 임베딩이 된다.

임베딩에 따른 Node2Vec 예시

아래의 두 예시는 Node2Vec으로 임베딩 수행 후, K-means 군집 분석을 수행한 결과이다.

멀어지는 방향에 높은 확률을 부여한 경우 위와 같은 모습으로 군집이 결정된다.
정점의 역할(bridge, leaf 등)이 같은 경우에 임베딩이 유사하게 된 모습이다.

가까워지는 방향에 높은 확률을 부여한 경우
같은 군집에 속한 경우 임베딩이 유사한 모습을 보인다.

Loss fucntion approximation

Random walk 기법의 loss는 계산에 점점의 수의 제곱에 비례하는 시간이 소요된다. 중첩의 합 때문이다.

점의 갯수가 많아질 수록 제곱의 크기는 더욱 커지게 된다. 따라서 많은 경우 근사식을 활용하여 이 문제를 해결한다.

모든 정점에 대해 정규화하는 대신 몇 개의 정점을 뽑아서 비교하는 형태로 이루어지며 이 때 뽑히는 정점들을 Negative sample이라고 부른다. 이때 여러 방식이 존재하지만, node의 degree가 클 수록 negative sample로 뽑힐 확률이 높게끔 뽑는다. 이렇게 할 수록 학습이 더욱 안정적으로 진행되며, negative sample이 많을 수록 안정적이다.

하지만, 위 식은 정확하지 않다. 해당 이슈에 대한 부스트캠프 이현주 조교님의 답변을 아래와 같이 첨부한다.
“위의 식이 어떻게 아래의 식으로 근사되는지 궁금해 하신 캠퍼분들이 굉장히 많으셨는데요, 해당 근사식은 수식적으로 받아들이시는 것보단 의미적으로 받아들이시는 것이 좋을 것 같습니다. 위의 수식(원래의 loss function)에서는 V에 있는 모든 노드들 중 v노드가 u노드와 가장 유사하도록 임베딩이 되는 것을 희망하는 것을 뜻합니다. 아래의 수식이 의미하는 것은 노드 u, v가 유사하게 임베딩 되었을 확률 - 노드 u와 negative sampled된 노드(u와 유사하지 않을 것이라 판단된 노드. random walk에서 u 근처에 나타나지 않은 노드들)이 유사하게 임베딩되었을 확률로, 아래의 수식을 높게 학습시킨다는 것은 u와 v의 임베딩은 유사하도록, u와 negative sample된 다른 노드들의 임베딩은 유사하지 않도록 학습시킨다는 것을 의미합니다. 아래의 수식에서의 sigmoid함수는 ‘확률화’의 기능으로써 도입되었습니다! (sigmoid 함수는 값을 0-1 사이의 값으로 mapping시켜주므로) 혹시 조금 이해가 되셨을까요?이 부분이 수식적으로 이해하기엔 굉장히 의아하고 의문스러운 부분이 많아서 많은 분들이 헷갈리셨을 것 같습니다 수식적으로 해당 식을 이해하시는 것보다는 위에서 말씀드린 것처럼 의미적으로 이해하시는 것을 추천드리고, 보다 깊은 공부를 하시고 싶으신 분들은 아래의 논문을 참고하시면 도움이 될 것 같습니다! ” http://proceedings.mlr.press/v9/gutmann10a/gutmann10a.pdf
아래 링크는 Word2vec의 negative sampling에 대한 loss 함수 유도가 포함된 내용이다. 더 자세한 내용을 원한다면 아래 논문을 확인하길 추천한다. https://arxiv.org/pdf/1402.3722v1.pdf

Transductive Node representation

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

쉽게 설명하자면 변환식은 node 각각에 대하여 임베딩 벡터를 얻는 것이고
귀납식은 각 정점을 임베딩 벡터로 변환시키는 함수, 즉 encoder 자체를 얻는 방식이다.

변환식 방법의 한계

학습이 진행된 이후에 추가된 정점에 대해서는 임베딩을 얻을 수 없다.
모든 정점에 대한 임베딩을 미리 계산하여 저장해두어야 한다.
정점이 속성(Attribute) 정보를 가진 경우에 이를 활용할 수 없다.

이런 단점을 극복한 귀납식 임베딩 방법과 더불어 대표적 귀납식 임베딩 방식인 그래프 신경망(Graph Neural Network)에서 소개하기로 한다.

Latent Factor Model(잠재 인수 모형)

“넷플릭스”를 사용해본적이 있으신가요? 사용해보셨다면, 넷플릭스가 사용자에게 언제부터 어떻게 미디어 콘텐츠를 ‘잘’ 추천할 수 있게 됐는지 궁금하지 않으신가요? 이번 강의에선 이와 관련한 대회인 “넷플릭스 챌린지“에 대해 소개합니다.

또, 지난 시간에 배웠던 협업필터링의 방법 이외에 추천의 새로운 방법, 잠재 인수 모형을 활용한 추천 시스템에 대하여 소개합니다. 특정 차원에서 단어를 벡터 하나로 나타내는 것처럼, 추천시스템에서의 사용자와 아이템도 벡터 하나로 표현할 수 없을까요? 또, 이 벡터를 어떻게 학습시킬까요? 이에 대한 해답들을 배우게됩니다.

Review

앞서 설명했던 내용들을 잠시 복습하는 의미에서 간단히 요약하겠다.

내용 기반 추천 시스템

내용 기반 추천은 각 사용자가 구매 / 만족했던 상품과 유사한 것을 추천하는 방법이다.
- 동일한 장르의 영화를 추천하는 것
- 동일한 감독의 영화 혹은 동일한 배우가 출연한 영화를 추천하는 것
- 동일한 카테고리의 상품을 추천하는 것
- 동갑의 같은 학교를 졸업한 사람을 친구로 추천하는 것
내용 기반 추천시스템의 장/단점
- (+) 다른 사용자의 구매 기록이 필요하지 않다.
- (+) 독특한 취향의 사용자에게도 추천이 가능하다
- (+) 새 상품에 대해서도 추천이 가능하다
- (+) 추천의 이유를 제공할 수 있다.
- (-) 상품에 대한 부가 정보가 없는 경우에는 사용할 수 없다.
- (-) 구매 기록이 없는 사용자에게는 사용할 수 없다.
- (-) 과적합으로 지나치게 협소한 추천을 할 위험이 있다.

협업 필터링(Collaborative Filtering)

협업 필터링은 유사한 취향의 사용자들이 선호 / 구매한 상품을 추천하는 방식이다. 사용자-사용자 협업 필터링은 다음의 세 단계로 이루어진다.

추천의 대상 사용자를 $x$라고 한다.
우선 $x$와 유사한 취향의 사용자를 찾는다.
다음 단계로 유사한 취향의 사용자들이 선호하는 상품을 찾는다.
마지막으로 이 상품을 $x$에게 추천한다.

Collaborative filtering의 장단점

(+) 상품에 대한 부가 정보가 없는 경우에도 사용할 수 있습니다

(−) 충분한 수의 평점 데이터가 누적되어야 효과적입니다(Cold )
(−) 새 상품, 새로운 사용자에 대한 추천이 불가능합니다
(−) 독특한 취향의 사용자에게 추천이 어렵습니다

잠재 인수 모형(Latent Factor Model)

가장 큰 성능 개선을 만들어낸 모형이며, 지금까지도 널리 사용되는 모형 중 하나이다.

overview of Latent Factor Model(UV decomposition or SVD)

잠재 인수 모형은 다른 표현으로 선형대수에서의 UV decomposition으로 표현하기도하며, SVD(Singular value decomposition - 특이값 분해)으로도 표현된다. 하지만 SVD는 Latent factor model과 유사할뿐 수학에서의 그것과는 차이가 있으므로 주의해서 사용한다.

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

2차원을 예시로 들 때, factor를 정의한 상태로 분류를 하는 것이 아니라 임베딩이 원활히 되게끔 하는 인수를 학습하게끔 하는 것이 목표이다.
여기서 학습한 인수를 Latent Factor라고 한다.

Loss function(손실 함수)

정점 임베딩에서는 그래프에서의 유사도를 임베딩 공간에서도 보존하게끔 하는 것이 목표였다. 잠재 인수 모형에서도 마찬가지로 비슷한 방식을 따른다.

사용자와 상품을 임베딩하는 기준?

사용자와 상품의 임베딩 벡터의 내적(Inner product)이 평점과 최대한 유사하도록 하는 것이다.
사용자 $x$의 임베딩을 $p_x$, 상품 $i$의 임베딩을 $q_i$, 사용자 $x$의 상품 $i$에 대한 평점을 $r_{xi}$라고 가정하자
이때 임베딩의 목표는 $p_x^\top q_i$가 $r_{xi}$와 유사하도록 하는 것이다.

행렬 차원에서 살펴보자

평점 행렬을 $R$, 사용자의 임베딩 벡터를 쌓아만든 사용자 행렬을 $P$, 영화들의 임베딩 벡터를 쌓아 만든 상품 행렬을 $Q$라고 하자.
위와 같이 $R$에서의 각 상품을 임베딩하여 잠재 인수 행렬 $Q$로 나타내고, 마찬가지로 사용자 임베딩 벡터를 쌓은 잠재인수 행렬 $P$의 transpose로 나타낸다.
이 두 행렬의 내적을 통해 $R$과 근사시키는 것을 목표로 손실함수를 계산하게 되는데 그 식은 이어서 살펴보도록 한다.

loss function

latent factor model의 loss function를 최소화하는 $P$와 $Q$를 찾는 것을 목표로 한다.

\[\sum_{(i,x)\in R}(r_{xi}-p_x^\top q_i)^2\]

일반적으로 위 식을 사용할 경우 overfitting이 발생할 가능성이 높다.
데이터의 noise까지 학습하여 평가 성능이 오히려 감소할 여지가 크기 때문이다.
이를 해결하기 위해 정규화 항을 손실 함수에 더해 준다. $\mathcal{L}=\sum_{(i,x)\in R}\underbrace{(r_{xi}-p_x^\top q_i)^2}_{\text{오차}} + \underbrace{\left[\lambda_1\sum_x \vert\vert p_x\vert\vert^2 + \lambda_2\sum_i \vert\vert q_i\vert\vert^2\right]}_{\text{모형 복잡도}}$
위와 같이 오차 term을 최소화하는 것 뿐만 아니라 모형 복잡도 부분을 함께 최소화한다.
이때 모형 복잡도를 최소화한다는 것은 $p_x$와 $q_i$가 너무 큰 값을 갖지 않는다는 것을 의미한다.
여기서 정규화는 L2-정규화를 사용한다.
결과적으로 Loss를 줄이는 방향으로 학습하게 되면, 오차를 줄이면서 모델의 복잡도가 너무 어렵지 않은 임베딩 방식을 학습하게 된다.
임베딩이 커진다는 것?
- 임베딩의 사이즈가 커진다는 것은 노이즈까지 학습할 여지가 많다는 것이다. 따라서 이를 방지하기 위해 임베딩 차원의 사이즈를 줄이기 위함이다.
이 정도는 $\lambda_1,\lambda_2$로 조절한다.

Optimization

Cost function을 최소화하는 $P$와 $Q$를 찾기 위해서는 (stochastic) gradient descent를 사용한다.

GD : loss를 안정적으로, 하지만 느리게 감소시킨다.
SGD : loss를 불안정하지만 빠르게 감소시킨다.
실제로는 SGD를 더 많이 사용한다.

Latent Factor Model의 사용으로 넷플릭스 챌린지 기준 목표 오차가 많이 낮아진 모습을 확인할 수 있다. 하지만 아직 목표 오차에는 많이 부족했기에 이를 개선하고자 고급 잠재인수 모형이 개발되었다.

고급 잠재 인수 모형(Advanced Latent Factor Model)

개선된 잠재 인수 모형에는 두 종류가 있다.

사용자와 상품의 편향을 고려한 잠재 인수 모형
시간에 따른 편향을 고려한 잠재 인수 모형

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

User Bias(사용자 편향)란 해당 사용자의 평점 평균과 전체 평점 평균의 차이를 말한다. 쉽게 말하자면 각 인스턴스의 평점에서 전체 평균의 평점을 뺀 값이다.
이와 비슷하게 상품 편향은 해당 상품에 대한 평점에서 전체 평점의 차이를 말한다.

개선된 잠재 인수 모형에서는 평점을 전체 평균, 사용자 편향, 상품 편향, 상호작용으로 분리한다. $\underbrace{r_{xi}}_{\text{평점}}=\underbrace{\mu}_{\text{전체 평균}}+\underbrace{b_x}_{\text{사용자 편향}}+\underbrace{b_i}_{\text{상품 편향}}+\underbrace{p_x^\top q_i}_{\text{상호 작용}}$

즉, 일반 잠재 인수 모형은 값 자체로 평점을 예측하려고 했었다면
고급 잠재 인수 모형은 사용자 편향, 상품 편향을 제외한 그 차이만으로 예측하는 방법이다.

Loss function

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

\[\mathcal{L}=\sum_{(i,x)\in R}\underbrace{(r_{xi}-(\mu+b_x+b_i+p_x^\top q_i))^2}_{\text{오차}} + \underbrace{\left[\lambda_1\sum_x \vert\vert p_x\vert\vert^2 + \lambda_2\sum_i \vert\vert q_i\vert\vert^2+\lambda_3\sum_x b_x^2+\lambda_4\sum_i b_i^2\right]}_{\text{모형 복잡도}}\]

기본 잠재 인수 모형에서 추가적으로 사용자 편향 $b_x$와 상품 편향 $b_i$를 학습하게 된다.
일반적으로 SGD를 통해 손실 함수를 최소화하는 잠재 인수와 편향을 찾아낸다.

일반 잠재 인수 모형보다 0.01 만큼의 mse가 낮아졌음을 확인할 수 있다.
하지만 여전히 목표 오차에는 많이 부족한 모습이다.

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

넷플릭스 시스템의 변화로 평균 평점이 크게 상승하는 사건이 있었을 때, 아래와 같이 갑자기 평균 평점이 증가하는 사례를 볼 수 있다.

영화의 평점이 출시일 이후 시간이 지남에 따라 상승하는 경향을 나타낸 그래프

뒤로 갈수록 영화를 좋아할 가능성이 높은 사람들이 찾아볼 여지가 많아 뒤로 갈 수록 높은 평점을 받는 모습이다.
반대로 초반에는 영화에 대한 기대감이 높고 이를 충족하지 못할 경우 낮은 평점을 보이는 모습을 확인할 수 있다.

개선된 잠재 인수 모형에서는 이러한 시간적 편향을 고려한다. 구체적으로 사용자 편향과 상품 편향을 시간에 따른 함수로 가정한다. 이는 다음과 같이 구성된다.

$\underbrace{r_{xi}}_{\text{평점}}=\underbrace{\mu}_{\text{전체 평균}}+\underbrace{b_x(t)}_{\text{사용자 편향}}+\underbrace{b_i(t)}_{\text{상품 편향}}+\underbrace{p_x^\top q_i}_{\text{상호 작용}}$ 이 모형을 이용하여 위 사용자와 상품 편향을 고려한 잠재 인수 모형과 비슷한 형태의 loss를 구성하게 된다.

이렇게 더 낮은 오차를 얻게되었다.

넷플릭스 챌린지 우승

앙상블 학습
- bellkor 팀이 처음으로 앙상블하여 처음으로 목표 성능에 도달하였다.
- 이에 위기감을 느낀 나머지 팀이 모두 연합하여 team Ensemble을 만들었다.
- 동일한 오차를 달성하였지만 먼저 제출한 Bellkor 팀이 우승을 차지하게 된다.

Further Reading

Further Questions

추천시스템의 성능을 측정하는 metric이 RMSE라는 것은 예상 평점이 높은 상품과 낮은 상품에 동일한 페널티를 부여한다는 것을 뜻합니다. 하지만 실제로 추천시스템에서는 내가 좋아할 것 같은 상품을 추천해주는것, 즉 예상 평점이 높은 상품을 잘 맞추는것이 중요합니다. 이를 고려하여 성능을 측정하기 위해서는 어떻게 해야 할까요?
추천 시스템의 성능을 향상시키기 위해서는 어떠한 것을 더 고려할 수 있을까?

GNN / Node2Vec and Latent Factor Model

Netflix Challenge with latent factor model

Node Representation Learning

What is Node Representation?

The reasons of Node embedding

Goal of Node embedding