P. Covington, J. Adams, E. Sargin. Deep neural networks for youtube recommendations. Proceedings of the 10th ACM Conference on Recommender Systems, ACM (2016), pp. 191-198

I. Introduction

유튜브는 전세계에서 가장 큰 동영상 플랫폼 기업으로, 끊임없이 늘어나는 비디오 콘텐츠로부터 십억 명 이상의 유저들에게 개인화된 추천을 제공한다. 이 과정에서 풀어야 할 3개의 숙제는 다음과 같다.

• Scale: 대부분의 추천 알고리즘은 작은 데이터셋에서는 잘 작동하지만, 유튜브 정도의 규모에서 쓰기엔 어렵다. 유튜브의 수많은 유저와 영상을 기반으로 한 추천 알고리즘이 작동하기 위해서는 대규모 데이터셋에 특화된 알고리즘과 효율적인 서빙 시스템이 필요하다.

• Freshness: 유튜브는 1초에 수많은 영상들이 올라오는데, 그 길이도 제각각이다. 따라서 유튜브 추천시스템은 유저의 최신 행동 뿐만 아니라 실시간으로 업데이트되는 콘텐츠들도 다룰 수 있어야 한다.

• Noise: 데이터의 희소성과 관측되지 않은 다양한 external factor의 존재로 유저 행동을 예측하기 어려운 문제가 있다. 따라서 추천시스템에서는 implicit feedback signal을 통해 유저의 선호도를 추정한다. 이때 metadata가 잘 구축되어있지 않은 경우도 있는데, 추천시스템은 이런 노이즈에 대해서도 robust해야 할 필요가 있다.

본 논문에서는 유튜브 영상 추천시스템에 활용된 딥러닝 기술에 대해 다룰 것이다.

II. System Overview

유튜브 추천시스템의 대략적인 구조는 아래 그림과 같다. 크게 2개의 neural network로 구성되는데, 하나는 candidate generation의 역할을 하고 다른 하나는 ranking의 역할을 한다.

먼저 candidate generation network에서는 유저의 과거 기록을 input으로 받아 개인화된 영상 후보군을 도출한다. 이때 precision 값이 높게 나오도록 모델을 학습한다. candidate generation은 collaborative filtering을 통해 이루어지며, 그 과정에서 유저 간의 유사도를 계산하기 위해 시청한 영상 ID, 검색어, 인구통계학적인 정보를 사용한다.

다음으로 ranking network에서는 각각의 후보군 영상들과 유저 간에 점수를 매기고 순위를 부여한다. 이때는 recall 값이 높게 나오도록 모델을 학습하여 상대적인 중요도가 높은, 유저 화면에 배치할 영상을 선별한다.

모델 학습을 위해 precision, recall, ranking loss 등의 offline metric을 활용했지만, 실제 모델의 effectiveness를 평가할 때에는 A/B test를 진행하였다. A/B test를 통해서는 click-through rate, 시청 시간, 그리고 이외에 유저의 유입을 나타내는 다른 지표를 측정하고 비교할 수 있기 때문이다.

III. Candidate Generation

candidate generation은 수백만 개 이상의 유튜브 영상 중 유저와 관련 있는 수백 개의 영상만 필터링해주는 과정이다.

3.1 Recommendation as Classification

저자는 추천 작업을 multiclass classification 문제로 다루었다. corpus $V$에 있는 수백만 개의 영상 $i$(class) 중 유저 $U$와 맥락 $C$를 고려하여 $t$ 시점에 볼 영상 $w_t$을 예측하는 문제로 본 것이다.

$$ P(w_t =i ,|, U, C)= {{e^{v_i u}} \over{\sum_{j \in V}e^{v_j u}}} $$

식에서 $u \in \mathbb{R}^N$은 유저와 맥락에 대한 고차원 embedding, $v_j \in \mathbb{R}^N$은 각각의 후보군 영상에 대한 embedding을 의미한다. Deep neural network 태스크의 목표는 유저의 영상 시청 기록과 맥락을 기반으로 embedding $u$를 학습하여 softmax classifier로 영상을 식별해낼 수 있게 만드는 것이다.

유튜브에는 좋아요, 설문조사 등 explicit한 feedback이 존재하지만, 저자는 유저가 영상 시청을 끝까지 마친 경우를 positive example로 정의한 implicit feedback을 사용해 모델을 학습시켰다. 이는 sparse한 explicit feedback 데이터의 한계를 보완하며, 더 일반화된 추천이 가능하게 해준다.

Efficient Extreme Multiclass

수백만 개의 클래스를 다루는 모델을 효율적으로 학습시키기 위해서, background distribution으로부터 negative sample을 수집했다. 그리고 true label과 수집된 negative class간의 cross-entropy loss를 최소화하는 방식으로 모델을 학습시켰다.

모델 서빙 과정에서는 유저에게 추천해줄 top N개의 영상을 선택하기 위한 연산이 수행되어야 했는데, 이때 기존 유튜브 시스템에 활용되었던 hashing 방식을 이용해 수백만 개의 아이템에 대한 스코어링 시간을 sublinear하게 단축시켰다.

3.2 Model Architecture

모델 학습을 위해 우선 각각의 영상을 고정된 vocabulary로 이루어진 고차원 embedding으로 나타낸 후 feedforward neural network에 통과시켰다. 유저의 영상 시청 기록은 sparse한 영상 ID sequence로 나타내어지는데, 이때 앞에서 만들어진 embedding을 평균낸 값을 고정된 길이의 dense input으로 활용했다. 이외에 age, gender 등 feature들을 concatenate하여 첫 번째 wide layer에 투입했고 이후 fully connected ReLU layer를 쌓은 형태로 구조를 설계했다.

구체적인 모델 구조는 아래 그림과 같다.

3.3 Heterogeneous Signals

Deep neural network를 matrix factorization의 일환으로 사용했을 때의 장점은 연속형, 범주형 feature를 모델에 쉽게 추가할 수 있다는 점이다. 그 예로, 유저들의 검색어 데이터를 unigram과 bigram으로 tokenized하여 embedding을 만들고 이를 평균낸 dense vector를 검색 기록에 대한 representation으로써 모델에 투입할 수 있다. 또한 인구통계학적인 정보나 유저의 거주지, 디바이스 정보, 성별, 나이, 로그인 지역 등의 데이터 역시 [0, 1]의 크기로 normalized되어 network에 바로 투입될 수 있다.

"Example Age" Feature

유튜브 유저들은 fresh한 영상을 선호하는 경향이 있다. 따라서 추천에 있어서 최신성은 특히 중요하다. 다만 머신러닝은 과거 데이터로 미래를 예측하기 때문에 종종 과거의 아이템에 편향된 결과를 제공한다. 영상의 popularity는 시간에 따라 변화하지만, 위에서 제안된 모델 구조에서는 영상 시청 기록의 평균으로 input을 만들고 있어 시간적인 의미를 담지 못한다. 따라서 저자는 이를 보완해주기 위해 영상의 age를 feature로 추가하였다.

그 결과 아래 그래프에서 볼 수 있듯이 모델의 성능이 크게 개선되었다.

3.4 Label and Context Selection

대부분의 추천시스템은** surrogate problem**이 있다. 모델의 성능 평가를 위해서는 A/B testing이 필요하지만 매번 실제 유저들의 선택으로 성능을 평가하는 데에는 한계가 있으므로 Hit Rate, NDCG와 같은 offline metric을 이용하곤 한다.

유튜브 추천시스템에서 학습 데이터는 모델이 만들어내는 추천 결과 뿐만 아니라 외부 사이트를 포함한 모든 유튜브 시청 데이터를 기반으로 만들어져야 한다. 그렇지 않다면 exploitation에 편향이 생겨 새로운 콘텐츠에 대한 추천이 어렵기 때문이다. 만약 유저들이 제공받은 추천 알고리즘 외에 다른 방식으로 영상을 탐색한다면, 이를 collaborative filtering에 빠르게 반영해주어야 한다. 또 영상 시청 기록이 매우 많은 유저에게 과도하게 가중치가 부여되는 것을 방지하기 위해 유저별로 학습에 사용할 데이터의 길이를 고정시켜줄 필요가 있다.

직관에 반대될 수도 있겠지만, 모델의 overfitting 문제를 방지하기 위해 classifier에서 나온 정보를 추천 결과에 즉시 반영하지는 않는다. 하나하나의 검색 기록을 모두 추천 결과에 반영하면 오히려 성능이 낮아지는 현상이 나타났다.

또 유저의 비대칭적인 영상 시청 패턴을 모델이 학습할 수 있게 구조를 설계했다. 대부분의 collaborative filtering 시스템은 아래 (5a)와 같이 유저의 시청 기록 중 하나를 랜덤하게 가리고 다른 시청 기록으로부터 해당 영상이 무엇일지 예측하는데, 이 경우 비대칭적인 영상 시청 패턴을 무시하게 된다. 따라서 (5b)처럼 유저가 시청할 영상을 예측할 때 해당 시점 이전의 기록만을 input으로 받게 했다.

IV. Ranking

Ranking의 주요 역할은 impression 데이터를 사용해 후보군 영상들에게 정량적인 스코어를 매기는 것이다. 영상의 수가 수백 개로 줄어들었기 때문에 더 많은 feature를 투입해 영상과 유저 간의 스코어를 연산하는 것이 가능하다.

Ranking 과정에서는 앞서 candidate generation에 사용되었던 모델 구조와 비슷한 deep neural network를 사용하여 logistic regression으로 각 영상에 스코어를 부여했다. 그리고 최종적으로 한 번의 노출로 기대되는 시청 시간을 기준으로 A/B testing을 수행해 모델의 성능을 평가했다.

4.1 Feature Representation

Feature Engineering

ranking model에서 사용하는 feature 종류는 수백 개가 넘는다. 딥러닝은 데이터 전처리에 대한 수고를 덜어주지만, 그래도 유튜브에서 발생하는 raw data는 input으로 투입되기 위해 어느 정도 feature engineering 과정이 필요하다. 이때 주로 생각해봐야 할 점은 유저 액션에 대한 temporal sequence를 어떻게 나타낼지, 그리고 이를 영상 scoring에 어떻게 반영할 것인지이다.

저자는 추천해주려는 영상(또는 그와 비슷한 영상)과 유저의 과거 interaction 정보가 ranking에 있어서 중요한 signal이 된다는 사실을 발견했다. 예를 들어, 유저가 특정 채널에서 영상을 시청한 횟수나 특정 주제에 대한 영상을 시청했던 시점과 같은 데이터는 서로 다른 아이템 사이에서도 잘 일반화될 수 있는 feature이기 때문에 특히 중요하다. 이외에도 candidate generation 과정에서 얻을 수 있는 정보를 ranking에 전파하는 것이 중요하다는 사실과 과거에 영상이 얼마나 노출되었는지를 나타내는 frequency가 주요 feature가 된다는 점도 밝혔다.

Embedding Categorical Features

candidate generation을 수행했을 때처럼 sparse한 categorical feature를 dense representation으로 매핑해주기 위해 embedding을 시켜주었다. 만약 영상 ID나 검색어와 같이 space의 크기가 큰 경우에는 top N개의 빈도를 가진 것만 남기고 영벡터로 embedding 시켜주었다. 그리고 multivalent categorical feature embedding은 평균 벡터를 계산하여 network에 투입시켰다.

중요한 점은 같은 ID space의 categorical feature들이 같은 embedding을 공유했다는 것이다. 이는 generalization 성능을 높여주고 training 속도 향상과 메모리 공간 절약 측면에서 효율적이다.

Normalizing Continuous Features

neural network는 scaling과 input의 분포에 민감하다. 따라서 continuous feature $x$의 경우 누적 분포를 고려하여 [0, 1)의 크기를 갖는 $\tilde{x}$로 변환해주었다. 그리고 super-, sub-linear한 feature로도 설명력을 높이기 위해 $\tilde{x}^2$과 $\sqrt{\tilde{x}}$도 input으로 넣어주었다.

4.2 Modeling Expected Watch Time

유튜브 추천시스템은 추천된 영상에 대한 기대 시청 시간 예측하는 것을 목표로 weighted logisetic regression과 cross-entropy loss를 이용한다. 이때 positive sample은 실제 시청 시간을 가중치로 부여하고, negative sample의 경우엔 시청 시간이 0이기 때문에 unit weight을 부여한다. 이 방식대로라면 logistic regression의 odds는 ${{\sum T_i} \over {N-k}}$가 된다. $N$은 학습 데이터의 수, $k$는 positive sample의 수, $T_i$는 $i$번째 노출 영상의 시청 시간이다. positive impression의 비율이 작다고 가정하면 학습된 odds는 대략 $ET$가 된다. 이때 $P$는 클릭할 확률, $E[T]$는 노출된 영상에 대한 시청 시간의 기댓값인데, $P$가 작기 때문에 이 값은 $E[T]$와 비슷하다.

V. Conclusions

본 논문에서는 유튜브 영상을 추천해주는 deep neural network 구조를 2개의 task(candidate generation, ranking)로 나누어 소개한다. 비대칭적인 영상 시청 패턴을 학습하고 미래에 대한 정보를 막음으로써 기존 matrix factorization 방식보다 좋은 성능을 보여주었고, classifier로부터의 signal을 차단한 것도 과적합을 방지하는 데에 주요한 역할을 했다. 또 학습 데이터의 최신성을 고려한 추천으로 A/B testing 결과 시청 시간을 늘릴 수 있었다.

Ranking에서는 유저와 아이템의 과거 interaction을 주요한 feature로 판단해 이에 대한 feature engineering 과정을 거쳤고, categorical feature를 embedding하고 continuous feature를 normalize하여 DNN에 투입했다. 그리고 여러 층의 layer를 쌓아 non-linear한 interaction을 효과적으로 학습하였다.

마지막으로 logistic regression을 변형하여 기대되는 시청 시간을 예측하도록 목적함수를 설정했다. 이렇게 시청 시간을 예측하는 ranking 방식은 click-through rate을 예측했을 때보다 더 좋은 성능을 보였다.

평소에 나와 많은 시간을 함께 하고 있는 유튜브의 추천시스템에 관한 논문이라 흥미롭게 읽을 수 있었다. 성능이 아주 뛰어나다고 알려져있는 유튜브 추천시스템의 큰 틀을 이해할 수 있었고, 다른 논문과 다르게 모델 서빙에 관한 내용도 일부 담겨 있어 느낌이 색달랐다. 이렇게 좋은 추천 알고리즘을 개발하는 머신러닝 엔지니어가 되고 싶다🙂

S. Wu, Y. Tang, Y. Zhu, L. Wang, X. Xie, and T. Tan, “Session-based recommendation with graph neural networks,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, 2019, pp. 346–353.

I. Introduction

인터넷 상의 정보량이 매우 빠른 속도로 증가하는 오늘날, 추천시스템은 유저가 흥미를 느낄만한 정보를 획득하는 데에 도움을 준다. 전통적인 추천시스템은 유저의 정보와 과거 활동들이 꾸준히 기록된다는 가정 하에 작동한다. 하지만 대부분의 서비스에서 유저의 신원은 불분명한 경우가 많고, 진행 중인 session 내의 유저 행동만을 관찰할 수 있다.

이런 한계를 극복하기 위해 유저가 과거에 구매한 아이템을 고려하여 새로운 아이템을 추천해주는 Markov chain이나 Recurrent Neural Networks(RNN)에 기반한 session-based recommendation 방식이 개발되었지만 여전히 해결되지 않은 한계점이 존재한다. 바로 유저 representation을 추정하는 데에 어려움이 있다는 점과, 연속적인 아이템 간의 단방향 transition만을 고려하고 세션 내 다른 아이템 간의 transition은 무시한다는 점이다.

본 논문에서는 Session-based Recommendation with Graph Neural Networks(이하 SR-GNN)를 제안한다. SR-GNN은 아이템 간의 transition을 충분히 탐색하고 정확한 아이템 latent vector를 생성하는 모델이다.

위 그림은 SR-GNN의 흐름을 나타낸 것이다. 먼저 모든 session sequence를 directed session graph로 나타낸다. 각 session graph는 연속적으로 진행되고 모든 노드의 latent vector는 gated GNN을 통해 얻어진다. 이후 각 session을 global한 선호도와 유저 개인의 선호도를 조합해 표현한다. 이때 global, local session embedding vector는 node의 latent vector로 구성된다. 마지막으로 session별로 특정 아이템이 다음에 클릭될 확률을 예측해낸다.

SR-GNN은 분리되어 있는 session sequence들을 graph 구조의 data로 나타낸 후 GNN을 통해 복잡한 item transition들을 잡아낼 수 있다. 또 유저 representation 대신 각 session에 포함된 아이템들의 latent vector로 만들어진 session embedding을 활용한다.

II. Related Work

1. Conventional recommendation methods

추천시스템의 가장 일반적인 접근은 Matrix Factorization이다. MF의 목표는 유저-아이템 matrix를 유저와 아이템의 latent factor를 나타내는 두 개의 low-rank matrix로 factorize하는 것이다. 그러나 MF는 클릭 데이터만으로 유저의 선호도를 유추하기 때문에, session-based recommendation에는 적절하지 않다.

그래서 등장한 것이 item-based neighborhood 방법이다. 이 method에서는 같은 session 내에 아이템이 함께 등장하는 정도를 고려해 item similarity를 계산한다. 다만 아이템의 구매 순서를 고려하진 못한다는 한계점이 있다.

이후 유저의 다음 행동은 직전 행동에 영향을 받는다는 전제 하에 Markov chain을 이용한 sequential method가 제안되었다. 하지만 이런 Markov chain 기반 모델들은 과거 component들을 독립적으로 결합하여 예측 정확도가 그리 높지 않다.

2. Deep-learning-based methods

최근에는 언어 모델 분야에서 좋은 성능을 내고 있는 Recurrent Neural Networks(이하 RNN)를 session-based recommendation에 적용하려는 시도가 이어졌다. 그 예로 유저 행동의 시간적 변화를 고려한 모델, RNN과 neighborhood-based method를 합쳐 순차적 패턴과 co-occurrence signal을 포착한 모델, 3차원 CNN으로 아이템 카테고리와 세부 정보까지 학습하는 모델 등이 있다.

3. Neural network on graphs

Neural network는 그래프 형태로 구조화된 데이터를 표현하는 데에 사용되기도 한다. 대표적으로 word2vec을 확장한 비지도학습 알고리즘 DeepWalk는 random walk를 기반으로 그래프 노드 표현을 학습한다. 전통적인 CNN을 임의의 크기와 모양을 가진 그래프에 적용한 선행 연구도 존재한다.

하지만 undirected graph에서만 이루어진 위 모델들과 달리, directed graph에서 작동하는 GNN을 변형해 만들어진 gated GNN은 gated recurrent unit과 back-propagation through time(BPTT)을 사용하여 gradient를 계산한다. 최근 몇 년간 GNN은 script event prediction이나 situation recognition, image classification 등 다양한 task에 활용되고 있다.

III. The Proposed Method

1. Notations

Session-based recommendation은 유저의 장기적인 선호도를 고려하지 않고도 현재의 sequential session 데이터만으로 유저가 다음에 클릭할 아이템을 예측하는 데에 초점을 둔다.

논문에서 사용될 기호를 정리해보면, 우선 $V= { v_1, v_2, ..., v_m }$은 모든 session을 이루는 아이템 집합을 의미한다. 임의의 session sequence $s$는 시간 순서대로 $[v_{s,1}, v_{s,2}, ..., v_{s,n}]$로 표현되는데, 이때 $v_{s, i} \in V$는 유저가 session $s$에서 $i$번째 클릭한 아이템이다. 따라서 session-based recommendation의 목표는 session $s$에 대해 $v_{s, n+1}$을 예측하는 것이 된다.

각 session $s$에서 가능한 모든 아이템에 대해 output probability를 계산해서 vector $\hat{\mathbf{y}}$를 도출한다. 이 중 상위 $K$개의 아이템을 뽑아 candidate item으로 추천을 해준다.

2. Constructing Session Graphs

각각의 session sequence $s$는 directed graph $\mathcal{G}s =(\mathcal{V}_s, \mathcal{E}_s)$로 나타낼 수 있다. 그래프에서 각각의 노드는 아이템 $v{s, i} \in V$를 나타내고,** edge $(v_{s,i-1},v_{s,i})\in \mathcal{E}s$는 세션 $s$에서 유저가 아이템 $v{s,i-1}$를 클릭한 후 아이템 $v_{s,i}$를 클릭했다는 것을 의미**한다.

sequence 내에 아이템 조합이 여러 번 등장할 수도 있기 때문에, 그래프에서 각 edge에 normalized weight를 할당했다. 이때 weight은 edge의 등장 횟수를 해당 edge의 start node의 outdegree로 나누어 계산된다.

저자는 모든 아이템 $v \in V$를 통합된 embedding space에 대응시켰다. 노드 벡터 $\mathbf{v}\in\mathbb{R}^d$는 GNN을 통해 학습된 아이템 $v$에 대한 latent vector를 의미한다. 이 노드 벡터를 기반으로 각 session $s$는 embedding vector $\mathbf{s}$로 표현될 수 있다.

3. Learning Item Embeddings on Session Graphs

GNN은 session-based recommendation에 적합한 모델이다. 다양한 노드 connection을 고려하여 session graph로부터 feature를 뽑아낼 수 있기 때문이다. 노드 벡터를 학습시키기 위해 그래프 $\mathcal{G}s$의 노드 $v{s,i}$에 다음과 같은 update 함수들을 적용한다.

$$ \mathbf{a}^t_{s,i}=\mathbf{A}_{s,i:}[\mathbf{v}^{t-1}_1 , ..., \mathbf{v}^{t-1}_n]^{\top} \mathbf{H}+\mathbf{b} ;;;;;;;;;;;;(1) $$

$$ \mathbf{z}^t_{s,i}=\sigma (\mathbf{W}z ,\mathbf{a}^t{s,i} ,+\mathbf{U}_z\mathbf{v}^{t-1}_i) ;;;;;;;;;;;;;;;;;;;;(2) $$

$$ \mathbf{r}^t_{s,i}=\sigma(\mathbf{W}r ,\mathbf{a}^t{s,i} + \mathbf{U}_r\mathbf{v}^{t-1}_i) ;;;;;;;;;;;;;;;;;;;;;(3) $$

$$ \tilde{\mathbf{v}^t_i}=\text{tanh}(\mathbf{W}o,\mathbf{a}^t{s,i}+\mathbf{U}o, (\mathbf{r}^t{s,i},\odot,\mathbf{v}^{t-1}_i)) ;;;;(4) $$

$$ \mathbf{v}^t_i=(1-\mathbf{z}^t_{s,i})\odot\mathbf{v}^{t-1}i + \mathbf{z}^t{s,i} \odot \tilde{\mathbf{v}^t_i} ;;;;;;;;;;;;;(5) $$

식에서 $\mathbf{H} \in \mathbb{R}^{d \times 2d}$는 가중치 matrix, $\mathbf{z}{s,i}$와 $\mathbf{r}{s,i}$는 각각 update, reset gate이다. $[\mathbf{v}^{t-1}1 , ..., \mathbf{v}^{t-1}_n]$는 session $s$의 노드 벡터이고 $\sigma(\cdot)$는 sigmoid 함수, $\odot$은 element-wise multiplication 연산자, $\mathbf{v}_i \in \mathbb{R}^d$는 노드 $v{s,i}$의 latent vector를 의미한다. connection matrix $\mathbf{A}s \in \mathbb{R}^{n \times 2n}$은 그래프에서 각 노드가 서로 어떻게 상호작용하는지를 결정하는데 이때 $\mathbf{A}{s,i:} \in \mathbb{R}^{1 \times 2n}$은 $\mathbf{A}s$에서 노드 $v{s,i}$에 대응되는 부분이다.

$\mathbf{A}_s$는 두 개의 인접행렬 $\mathbf{A}^{\text{(out)}}_s$과 $\mathbf{A}^{\text{(in)}}_s$이 결합해서 만들어진다. 아래 session $s=[v_1, v_2, v_3, v_4, v_5]$에 대한 그래프 $\mathcal{G}_s$의 예시를 보면 이해가 쉬울 것이다.

session graph를 생성하는 방식은 저마다 다를 수 있지만 SR-GNN은 서로 다른 connection matrix $\mathbf{A}$를 지원할 수 있다. 나아가 만약 각 노드에 추가적인 content feature가 존재하는 경우 해당 feature들을 node vector와 결합하여 추가 정보를 학습시킬 수 있다.

각각의 session graph $\mathcal{G}_s$에 대해, gated graph neural network는 다음과 같은 작업들을 동시에 처리한다. 식 (1)은 matrix $\mathbf{A}_s$ 조건 하에서 서로 다른 노드 간에 정보를 전파한다. 구체적으로 이웃 노드 간에 latent vector를 추출해 GNN의 input으로 넣어주는 역할을 한다. 다음으로 update와 reset gate가 어떤 정보를 보존하고 삭제할지 결정해준다. 그렇게 되면 식 (4)에서 이전의 state와 현재 state, reset gate를 종합하여 candidate state가 도출된다. 마지막으로 update gate는 이전의 hidden state와 candidate를 얼마나 보존할지 결정해 final state를 도출한다. 모든 노드가 수렴할 때까지 업데이트가 완료되면 final node vector를 얻을 수 있다.

4. Generating Session Embeddings

기존 session-based recommendation들이 각 session에 대해 유저의 distinct한 latent representation이 있을 것이라고 가정한 것과 달리, SR-GNN은 session을 구성하는 노드만으로 session을 표현한다. 이때 유저의 장기적인 선호도와 현재 session에서의 관심도를 결합한 session embedding 방식을 제안했다.

모든 노드에 대해 node vector를 얻은 후, session $s$에 대한 local embedding $\mathbf{s}1$을 구했다. session $s=[v{s,1},v_{s,2},...,v_{s,n}]$에 대해 local embedding은 마지막에 클릭한 아이템 $v_{s,n}$의 벡터 $\mathbf{v}_n$이 된다.

다음으로 session graph $\mathcal{G}_s$의 모든 노드 벡터를 종합해 global embedding $\mathbf{s}_g$를 계산했다. 이때 soft-attention 메커니즘을 적용해 embedding의 우선순위가 다를 수 있다는 점을 고려했다. $$ \alpha_i=\mathbf{q}^{\top}\sigma (\mathbf{W}1\mathbf{v}_n+\mathbf{W}_2\mathbf{v}_i + \mathbf{c}) $$ $$ \mathbf{s}_g=\sum^n{i=1}\alpha_i \mathbf{v}_i $$

$\mathbf{q} \in \mathbb{R}^d$와 $\mathbf{W}_1, \mathbf{W}_2 \in \mathbb{R}^{d \times d}$는 item embedding vector의 가중치를 조절한다.

최종적으로, local embedding vector와 global embedding vector를 결합하고 선형 변환을 통해 hybrid embedding $\mathbf{s}_h$를 얻었다. 행렬 $\mathbf{W}_3 \in \mathbb{R}^{d \times 2d}$는 결합된 embedding vector를 $\mathbb{R}^d$ 차원의 latent space로 압축시키는 역할을 한다. $$ \mathbf{s}_h=\mathbf{W}_3[\mathbf{s}_1;\mathbf{s}_g] $$

5. Making Recommendation and Model Training

각 세션의 embedding을 모두 얻은 후 candidate item $v_i \in V$의 embedding $\mathbf{v}_i$와 session representation $\mathbf{s}_h$를 곱하여 score $\hat{\mathbf{z}_i}$를 계산했다. $$ \hat{\mathbf{z}_i}=\mathbf{s}_h^{\top}\mathbf{v}_i $$ 그리고 모델의 output vector를 얻고자 softmax 함수를 적용했다. $$ \hat y= \text{softmax}(\hat{\mathbf{z}}) $$ $\hat{\mathbf{z}}\in \mathbb{R}^m$은 모든 candidate item에 대한 recommendation score, $\hat{\mathbf{y}}\in \mathbb{R}^m$은 특정 노드가 session $s$의 다음 클릭이 될 확률을 의미한다.

loss function은 예측값과 실제값 간의 cross-entropy로 정의되었다. $$ \mathcal{L}(\hat{\mathbf{y}})=-\sum_{i=1}^m \mathbf{y}_i \text{log}(\hat{\mathbf{y}_i})+(1-\mathbf{y}_i)\text{log}(1-\mathbf{y}_i) $$

마지막으로 Back-Propagation Through Time(BPTT) 알고리즘을 이용해 SR-GNN 모델을 학습시킨다. 이때 대부분의 추천 상황에서 session의 길이는 그리 길지 않으므로 training step 수를 작게 해 overfitting을 방지했다.

IV. Conclusions

본 논문에서 제안한 SR-GNN은 session sequence를 graph 모델로 표현하는 방식의 session-based recommendation이다. SR-GNN은 session sequence 내에서 아이템의 복잡한 구조와 transition을 고려할 뿐만 아니라, 장기적인 선호도와 현재 선호도를 결합해 유저의 다음 action을 예측해낸다.

Graph Neural Network를 추천시스템에 적용하여 global, local 선호도를 추출한 점이 인상깊었다. GNN이 현업에서도 많이 사용된다고 들었는데, 관련해서 더 공부를 해봐야겠다!

Kang, Wang-Cheng & McAuley, Julian. (2018). Self-Attentive Sequential Recommendation. 197-206. 10.1109/ICDM.2018.00035.

I. Introduction

Sequential recommender system의 목표는 유저 데이터로 학습된 모델을 유저의 최근 action에 기반한 context와 결합하는 것이다. 다만 유저의 action을 얼마나 오래 전부터 살펴볼 것인지에 따라 input 데이터 차원이 기하급수적으로 커지기 때문에 이러한 sequential dynamics로 유용한 패턴을 잡아내기는 어려운 일이다.

따라서 고차원의 데이터 속에서 간결하게 context를 뽑아내기 위한 많은 연구들이 이루어졌다. 대표적으로 Markov Chains(MCs)가 있는데, 유저의 다음 action은 직전 action에만 영향을 받는다는 가정을 바탕으로 추천시스템이 단기간의 item transition을 잘 학습하도록 했다. 이와 다르게 Recurrent Neural Networks(RNNs)는 hidden state를 통해 유저의 과거 모든 action을 바탕으로 유저의 다음 action을 예측하고자 했다. MC 기반 추천시스템은 높은 sparsity 상황에서도 잘 작동하지만 복잡한 상황에서의 action을 잘 학습하지 못한다는 단점이 있다. 반대로 RNN은 많은 양의 데이터를 필요로 하지만 간단한 모델보다 성능이 뛰어나다.

저자는 최근 번역 task에서 좋은 성능을 내고 있는 Transformer라는 sequential model에 영감을 받아 새로운 모델을 제안한다. Transformer는 self-attention이라고 불리는 attention 메커니즘을 이용해 문장에서 단어 사이의 의미적, 구조적 패턴을 효과적으로 찾아낸다. 이 self-attention 메커니즘을 sequential recommendation problems에 적용하여 RNN과 같이 유저의 과거 모든 action으로부터 context를 파악하고 MC처럼 적은 수의 action만으로 예측을 해내는 모델을 만들고자 했다. 그리고 모델을 Self-Attentive Sequential Recommendation(SASRec)이라고 이름 붙였다.

SASRec은 아래 그림처럼 각 time step마다 이전의 아이템에 대한 가중치를 조정한다.

attention 메커니즘의 영향으로, SASRec은 dense한 dataset에서는 긴 시간 범위의 의존성을 고려하고, sparse dataset에서는 최근 활동에 좀 더 집중하는 경향이 있다. 즉 density가 변하는 data 환경에 잘 적응할 수 있다는 것을 의미한다. 또한 parallel acceleration에 적합하기 때문에 CNN/RNN 계열의 모델보다 훨씬 빠른 학습 속도를 자랑한다.

II. Related Work

1. General Recommendation

일반적인 추천시스템은 과거 feedback에 기반하여 유저와 아이템 간의 양립성을 모델링한다. 이때 feedback은 평점과 같은 explicit한 것일 수도 있고, 클릭, 구매, 댓글처럼 implicit할 수도 있다. 그 중 implicit feedback을 모델링하기는 특히 더 어려운데, 관찰되지 않은 데이터를 해석하기가 모호하기 때문이다.

General Recommendation model로는 대표적으로 Matrix Factorization(MF)가 있다. MF는 유저와 아이템 embedding 간의 inner product로 유저와 아이템 간 interaction을 나타낸다. 또 Item Similarity Models(ISM)는 item-to-item similarity matrix를 학습해서 유저가 이전에 구매한 아이템과 비슷한 다른 아이템을 추천해준다.

최근에는 다양한 딥러닝 기술이 추천시스템이 적용되었다. context-aware recommendation에서 아이템 feature를 뽑아내기 위한 용도로 neural network를 사용하기도 하고, NeuMF나 AutoRec처럼 전통적인 MF를 대체하기 위해 neural network를 사용한 선행 연구도 존재한다.

2. Temporal Recommendation

Temporal Recommendation은 유저의 action 시간대를 명시적으로 모델링함으로써 다양한 task에서 좋은 성능을 보여주었다. TimeSVD++과 같은 temporal recommendation 모델들은 시간에 따른 단기 혹은 장기 추이가 있는 dataset을 이해하기 위해 필수적이다. Sequential recommendation은 시간에 관계없이 단순히 action의 순서만을 고려한다는 점에서 temporal recommendation과 차이가 있다.

3. Sequential Recommendation

Sequential Recommendation 모델은 구매로 이어진 아이템 사이의 순차적 패턴을 기반으로 item-item transition matrices를 모델링한다. first-order MC은 유저의 다음 action에 영향을 미치는 주요한 요소는 직전 아이템이라는 점에 착안하여, 특히 sparse한 dataset에서 좋은 성능을 보여주었다. high-order MC는 이전의 더 많은 아이템을 고려하는데, CNN 기반의 Convolutional Sequence Embedding에 적용되어 이전에 구매한 L개의 아이템에 대한 embedding matrix를 통해 convolutional operation을 수행하고 transition을 뽑아낸다.

MC 기반 모델 외에도, RNN을 이용해 유저 sequence를 모델링하는 선행 연구도 존재한다. 예를 들어 GRU4Rec은 session-based recommendation으로 클릭 sequence를 모델링한다. 각 time step에서 RNN은 직전 step의 state와 현재 action을 input으로 받는다.

4. Attention Mechanisms

Attention 메커니즘은 이미지 인식이나 번역과 같은 task에서 좋은 성능을 보여주었다. 근본적인 아이디어는 각 sequential output이 모델이 집중해야 할 몇몇 input에 영향을 받는다는 것이다. attention 메커니즘을 추천시스템에 적용시킨 선행 연구가 있긴 하지만 기존 모델에 추가적인 component를 추가한 것이 전부이다.

최근 Transformer라고 불리는 순수한 attention 기반의 sequence-to-sequence method가 번역 task에서 RNN/CNN 기반 모델을 압도했다. Transformer는 self-attention 모듈을 이용해 문장의 복잡한 구조를 이해하고 다음 단어를 생성하기 위해 연관 단어를 찾는다. 이러한 transformer에 영감을 받아 저자는 self-attention으로 새로운 sequential recommendation model을 제안한다.

III. Methodology

sequential recommendation에서는 유저의 action sequence $\mathcal{S}^u =(\mathcal{S}^u_1, \mathcal{S}^u_2, \cdots, \mathcal{S}^u_{|\mathcal{S}^u|})$가 주어진 상태에서 다음 아이템을 예측한다. 즉 time step $t$의 모델은 이전 $t$개 아이템에 의존하여 다음 아이템을 예측한다. 모델의 input을 $(\mathcal{S}^u_1, \mathcal{S}^u_2, \cdots, \mathcal{S}^u_{|\mathcal{S}^u|-1})$, output을 $(\mathcal{S}^u_2, \mathcal{S}^u_3, \cdots, \mathcal{S}^u_{|\mathcal{S}^u|})$으로 생각하면 된다.

이외의 notation은 아래 표와 같다.

1. Embedding Layer

모델이 다룰 수 있는 sequence의 최대 길이를 $n$이라고 할 때, 우선 training sequence $(\mathcal{S}^u_1, \mathcal{S}^u_2, ..., \mathcal{S}^u_{|\mathcal{S}^u|-1})$를 고정된 길이의 sequence $s=(s_1, s_2, ..., s_n)$로 변환한다. 이때 만약 sequence 길이가 $n$보다 크다면 최근 $n$개의 action만을 취하고, 길이가 $n$보다 작다면 zero vector $\mathbf{0}$을 padding item으로써 길이가 $n$이 될 때까지 추가한다. 이 방법으로 item embedding matrix $\mathbf{M} \in \mathbb{R}^{\mathcal{|I|} \times d}$를 만들고 input embedding matrix $\mathbf{E} \in \mathbb{R}^{n \times d}$를 얻는다. 이때 $d$는 latent 차원이고 $\mathbf{E}i = \mathbf{M}{s_i}$가 성립한다.

Positional Embedding

self-attention model이 recurrent 혹은 convolutional 모듈을 포함하지 않기 때문에, 이전 아이템의 position을 고려하지는 못한다. 이런 이유로 input embedding에 position embedding $\mathbf{P} \in \mathbb{R}^{n \times d}$를 더해서 다음과 같은 최종 input embedding matrix를 얻었다.

$$ \hat{\mathbf{E}}= \begin{bmatrix} \mathbf{M}{s_1} +\mathbf{P}_1 \ \mathbf{M}{s_2} +\mathbf{P}2 \ \cdots\ \mathbf{M}{s_n} +\mathbf{P}_n \end{bmatrix} $$

2. Self-Attention Block

query를 $\mathbf{Q}$, key를 $\mathbf{K}$, value를 $\mathbf{V}$라고 할 때 scaled dot-product attention은 다음과 같이 정의된다. $$ \text{Attention}(\mathbf{Q, K, V})=\text{softmax}({{\mathbf{QK}^T}\over {\sqrt{d}}})\mathbf{V} $$ attention layer는 모든 value의 가중합을 계산하는데, 이때 query $i$와 value $j$ 사이의 가중치는 query $i$와 key $j$ 간의 interaction에 해당한다. scaled factor $\sqrt{d}$는 고차원에서 inner product 결과가 너무 클 경우를 방지하기 위한 값이다.

Self-Attention layer

self-attention operation은 embedding $\hat{\mathbf{E}}$를 input으로 받아 linear projection으로 3개의 matrix를 도출한다. 그리고 그것들을 attention layer에 투입한다. $$ \mathbf{S}= \text{SA}(\hat{\mathbf{E}})=\text{Attention}(\hat{\mathbf{E}}\mathbf{W}^Q , \hat{\mathbf{E}}\mathbf{W}^K, \hat{\mathbf{E}}\mathbf{W}^V) $$ projection $\mathbf{W}^Q, \mathbf{W}^K, \mathbf{W}^V$는 모델을 더 유연하게 만들어 비대칭적인 interaction을 학습할 수 있게 한다.

Causality

sequence의 특성상 모델은 $t$+1번째 아이템을 예측할 때 첫 $t$개의 아이템을 고려한다. 하지만 self-attention layer($\mathbf{S}_t$)의 $t$번째 output은 그 다음 아이템들에 대한 embedding을 포함하고 있다. 따라서 저자는 $\mathbf{Q}_i$와 $\mathbf{K}_j(j > i)$ 사이의 연결을 끊는 형태로 기존의 attention을 변형했다.

Point-Wise Feed-Forward Network

모델에 nonlinearity를 부여하고 서로 다른 latent 차원 사이의 interaction을 고려하기 위해, 저자는 모든 $\mathbf{S}_i$에 동일하게 point-wise two-layer feed-forward network를 적용했다. $$ \mathbf{F}_i=\text{FFN}(\mathbf{S}_i) =\text{ReLU}(\mathbf{S}_i\mathbf{W}^{(1)} +\mathbf{b}^{(1)})\mathbf{W}^{(2)}+\mathbf{b}^{(2)} $$ $\mathbf{W}^{(1)}, \mathbf{W}^{(2)}$는 $d \times d$ 행렬이고 $\mathbf{b}^{(1)}, \mathbf{b}^{(2)}$는 $d$ 차원의 벡터이다. $\mathbf{S}_i$와 $\mathbf{S}_j (i \ne j)$는 interaction이 없는데, 이는 유저들의 action이 서로 독립적이라는 것을 의미한다.

3. Stacking Self-Attention Blocks

첫 번째 self-attention block 이후, $\mathbf{F}_i$는 이전 모든 아이템의 embedding을 aggregate한다. 그런데 여기서 더 복잡한 아이템 transition을 알아내기 위해, 저자는 self-attention block을 여러 개 쌓았다. $b$번째($b>1$) block은 다음과 같이 정의된다.

$$ \mathbf{S}^{(b)}=\text{SA}(\mathbf{F}^{(b-1)}) $$

$$ \mathbf{F}^{(b)}_i=\text{FFN}(\mathbf{S}_i^{(b)}), ;;\forall i \in { 1, 2, ..., n } $$

첫 번째 block $\mathbf{S}^{(1)}=\mathbf{S}$이고 $\mathbf{F}^{(1)}=\mathbf{F}$이다.

하지만 network가 깊어질수록 과적합 문제가 발생하고, 학습 프로세스가 불안정해지고, 파라미터 수가 많아져 더 많은 학습 시간을 필요로 한다는 단점이 있다. 이를 해결하기 위해 self-attention layer 투입 전** input $x$에 대한 layer normalization과 output에 대한 dropout, 그리고 최종적인 output에 input $x$를 더해주는 방식으로 모델을 설계**했다. $$ g(x)=x+\text{Dropout}(g(\text{LayerNorm}(x))) $$

Residual Connections

residual network의 핵심은 낮은 layer의 feature를 더 높은 layer에 전달하는 것이다. 여러 개의 self-attention block들을 통과하다보면 가장 마지막에 구매한 아이템의 embedding이 이전의 아이템과 섞여 희미해진다는 단점이 있다. 따라서 residual connection을 통해 가장 마지막에 구매한 아이템의 embedding을 마지막 layer에 전달하여 낮은 layer의 정보를 모델이 잘 기억할 수 있게 한다.

Layer Normalization

layer normalization의 역할은 input을 feature별로 정규화하여 neural network 학습을 안정적이고 빠르게 만드는 것이다. batch normalization과 다르게 layer normalization에서는 통계량이 같은 batch의 다른 sample들에 독립적이다. 벡터 $\mathbf{x}$를 sample의 모든 feature를 포함하고 있는 input이라고 할 때, layer normalization 식은 다음과 같다. $$ \text{LayerNorm}(\mathbf{x});=;\alpha ;\odot {{\mathbf{x}-\mu}\over{\sqrt{\sigma^2 + \epsilon}}}+\beta $$ 식에서 $\odot$는 element-wise product, $\mu$와 $\sigma$는 벡터 $\mathbf{x}$의 평균과 분산, $\alpha$와 $\beta$는 각각 학습된 scaling factor와 bias 항을 의미한다.

Dropout

과적합 문제를 방지하기 위해 dropout regularization을 사용한다. dropout의 원리는 학습 과정에서 확률 $p$로 특정 neuron을 사용하지 않는 것이다. 이는 파라미터를 공유하는 거대한 앙상블 학습이라고 볼 수도 있다.

4. Prediction Layer

$b$개의 self-attention block이 이전에 구매된 아이템으로부터 정보를 추출한 후, $\mathbf{F}t^{(b)}$에 기반하여 다음 아이템을 예측한다. 아이템 $i$에 대한 relevance 스코어를 도출하기 위해 다음과 같이 **MF layer를 쌓아 interaction score $r{i, t}$를 계산**한다. $\mathbf{N} \in \mathbb{R}^{|\mathcal{I}|\times d}$는 item embedding matrix이다. $$ r_{i, t}=\mathbf{F}_t^{(b)}\mathbf{N}_i^T $$

Shared Item Embedding

저자는 모델의 크기를 줄이고 과적합을 방지하기 위해 하나의 item embedding $\mathbf{M}$을 공유해서 사용했다. $$ r_{i, t}=\mathbf{F}t^{(b)}\mathbf{M}_i^T $$ $\mathbf{F}_t^{(b)}$가 item embedding $\mathbf{M}: \mathbf{F}_t^{(b)}=f(\mathbf{M}{s_1}, \mathbf{M}{s_2}, ...,\mathbf{M}{s_t})$에 의존적인 함수라는 것을 고려하면, item embedding 간의 inner product가 비대칭적인 item transition을 나타낼 수 없을 것이라고 생각할 수 있다. 하지만 SASRec은 nonlinear transformation을 학습함으로써 같은 item embedding으로도 asymmetry를 학습할 수 있다. ($\text{FFN}(\mathbf{M}_i)\mathbf{M}_j^T \ne \text{FFN}(\mathbf{M}_j)\mathbf{M}_i^T$)

Explicit User Modeling

개인화된 추천을 제공하기 위해, explicit user embedding을 학습하는 방식과 implicit user embedding을 학습하는 두 가지 방식이 존재한다. SASRec은 유저의 모든 action을 고려해서 embedding $\mathbf{F}n^{(b)}$를 만들어내기 때문에 후자에 가깝다. 마지막 layer에 explicit user embedding을 추가하여 $r{u, i, t}=(\mathbf{U}_u+\mathbf{F}_t^{(b)})\mathbf{M}_i^T$ 형태로 구조를 바꿔보기도 했지만, 큰 성능 향상은 없었다.

5. Network Training

$o_t$를 time step $t$에서의 expected output이라고 하면, 아래와 같이 정의될 수 있다. $\langle \text{ pad }\rangle$는 padding item을 의미한다. $$ o_t= \begin{cases} \langle\text{ pad }\rangle,; ; \text{if} ;;s_t ;\text{ is a padding item}\ s_{t+1}, ;;;;;;,\text{if} ;;;,1\le t < n\ \mathcal{S}_{|\mathcal{S}^u|}^u, ;;;;;;\text{if} ;;;t=n \end{cases} $$

SASRec은 sequence $s$를 input으로 받아 expected output sequence $o$를 도출하는데 이때 각각의 epoch마다 sequence의 time step별로 negative item $j$를 하나씩 랜덤하게 생성했다. 그리고 binary cross entropy loss와 Adam optimizer로 모델의 목적함수를 설정하고 최적화했다. $$ -\sum_{\mathcal{S}^u \in \mathcal{S}} \sum_{t \in [1, 2, ..., n]} [\text{log} (\sigma (r_{o_t}, t))+ \sum_{j \notin \mathcal{S}^u} \text{log}(1-\sigma(r_{j, t}))]
$$

6. Complexity Analysis

Space Complexity

모델의 전체 파라미터 수는 $O(|\mathcal{I}|d+nd+d^2)$으로, FPMC의 space complexity $O(|\mathcal{U}|d+|\mathcal{I}|d)$와 비교했을 때 유저 수에 관한 항 $|\mathcal{U}|$가 없고 $d$가 매우 작다는 점에서 효율적이다.

Time Complexity

SASRec은 self-attention layer와 feed forward network에 큰 영향을 받아 $O(n^2d+nd^2)$의 시간 복잡도를 갖는다. RNN 기반 모델의 시간 복잡도는 $O(n)$이지만 SASRec에서는 self-attention layer에서의 연산을 병렬적으로 수행할 수 있기 때문에 GPU를 이용하면 RNN, CNN 모델보다 속도가 빠르다.

IV. Conclusion

SASRec은 recurrent/convolutional operation 없이 user sequence 전체를 모델링하여 다음에 구매할 아이템을 추천해준다. 소비된 아이템을 선별적으로 고려함으로써 sparse, dense dataset 모두에서 기존 baseline 모델보다 좋은 성능을 보였다. 그리고 CNN/RNN 기반 모델에 비해 빠른 연산 속도를 보여주었다.

NLP task에서 사용된 Transformer 구조가 추천시스템에도 활용될 수 있다는 사실이 신기했다. 알고보면 NLP와 Recommender System은 유사한 점이 많은 것 같다. 아직 transformer 원리를 100% 이해하진 못한 것 같지만..! 관련 내용을 더 찾아보고 공부해야겠다🙂

Oleksii Kuchaiev, Boris Ginsburg. 2017. Training Deep AutoEncoders for Collaborative Filtering. NVIDIA

1. Introduction

추천시스템은 크게 두 종류로 나눌 수 있다. 첫 번째는 context-based recommendations로, 위치, 날짜, 시간 등의 contextual factor를 고려하는 방법이다. 다른 하나는 personalized recommendations인데, collaborative filtering(CF) 방식으로 유저에게 아이템을 추천해준다. 이때 특정 아이템에 대한 유저의 선호도는 다른 유저들의 선호도와 그들간의 유사성을 기반으로 예측된다.

고전적인 CF task는 $m \times n$ 크기의 rating matrix $R$에서 비어있는 값을 추론하는 것으로 $(i, j)$ entry는 $i$번째 유저의 $j$번째 아이템에 대한 rating을 의미한다. 이러한 CF task의 성능은 보통 RMSE로 평가한다.

1.1 Related Work

딥러닝이 이미지 인식, 자연어 처리와 강화학습에서 좋은 성능을 보여줬기 때문에, 추천시스템에도 이를 적용하려는 시도가 자연스레 이어졌다. 관련해서 restricted Boltzman machines(RBM), feed-foward neural networks, recurrent recommender networks 등 많은 선행 연구가 이루어졌고, 본 논문에서는 그 중 I-AutoRec(item-based autoencoder)과 U-AutoRec(user-based autoencoder)을 확장한 deep autoencoder를 다룬다.

AutoRec에 대한 내용은 이전 논문 리뷰(AutoRec: Autoencoders Meet Collaborative Filtering)를 참고하길 바란다.

2. Model

Deep AutoEncoder 모델은 U-AutoRec으로부터 영감을 받아 만들어진 deep learning 모델이다. pre-training 없이 deep한 model을 학습시키기 위해, 저자는 scaled exponential linear units(SELUs), 높은 dropout rate과 iterative output re-feeding을 학습 과정에서 사용했다.

Autoencoder는 인코더 $encode(x): R^n \rightarrow R^d$와 디코더 $decode(z): R^d \rightarrow R^n$ 두 가지 transformation으로 이루어진 network로, $x$와 $f(x)=decode(encode(x))$ 사이의 오차를 최소화하는 $d$ 차원의 representation을 얻는 것이 목표이다. 이러한 Autoencoder는 차원 축소를 할 때 사용될 수 있는 좋은 모델로써 PCA(principle component analysis)의 일반화된 버전이라고 볼 수 있다. 아래 그림은 4-layer autoencoder network를 나타낸다.

저자들은 Deep AutoEncoder에서 인코더와 디코더를 모두 fully connected feed-forward neural network로 두었다. 즉 $l=f(W \cdot x +b)$ 형태가 되는데, $f$는 non-linear한 활성화 함수이다. 만약 활성화 함수의 범위가 데이터 범위보다 작다면, 디코더의 마지막 layer는 linear하게 두었다. 또 hidden layer의 활성화 함수 $f$는 0이 아닌 음수 부분을 포함하고 있어야 하는데, 이를 위해 SELU unit을 사용했다.

만약 디코더와 인코더의 구조가 동일하다면, $l$번째 디코더의 가중치 $W_d^l$은 $l$번째 인코더 가중치 $W_e^l$의 transpose로 둘 수 있다. 이런 autoencoder를 constrained 또는 tied autoencoder라고 부르는데, 일반적인 autoencoder에 비해 free parameter를 2배 정도 적게 가진다는 특징이 있다. 논문에서 제안된 모델도 constrained autoencoder에 해당한다.

forward pass 과정에서 모델은 sparse한 training set $x \in R^n$의 rating vector로 유저를 표현한다. 이후 디코더의 output $f(x) \in R^n$은 모든 item에 대한 rating 예측값을 포함하는 dense vector가 된다.

2.1 Loss Function

유저의 representation vector $x$에서 이미 0인 rating을 예측하는 것은 적절하지 않다. 따라서 AutoRec: Autoencoders Meet Collaborative Filtering 선행연구를 참고하여 다음과 같은 Masked Mean Squared Error loss를 optimize하고자 했다.

$$ MMSE = {{m_i \times (r_i - y_i)^2}\over{\sum_{i=0}^{n}m_i}} $$ 식에서 $r_i$는 실제 유저의 rating, $y_i$는 reconstructed, 즉 예측된 rating을 의미한다. $m_i$는 mask function으로써 $r_i \ne 0$이면 $m_i=1$이고, 아니면 $m_i=0$이다.

2.2 Dense re-feeding

한 유저가 rating을 매기는 대상은 전체 아이템의 극히 일부에 불과하기 때문에, input $x \in R^n$는 매우 sparse하다. autoencoder는 이 sparse한 input을 dense한 output $f(x)$로 변환한다.

아주 완벽한 $f$가 있는 이상적인 상황을 가정해보자. 그럼 $f(x)_i =x_i, ; \forall i: x_i \ne 0$이고 $f(x)_i$는 아이템 $i: x_i=0$에 대한 모든 유저의 future rating을 정확하게 예측해낸다. 즉 유저가 새로운 아이템 $k$에 대한 점수를 매겨 새로운 벡터 $x'$이 만들어졌을 때 $f(x)_k = x_k '$이고 $f(x)=f(x')$이 성립한다. 따라서 이 상황에서 $y=f(x)$는 $f(f(x))=f(x)$를 만족하는 fixed point여야 한다.

이러한 fixed point 제한 조건을 만족시키며 dense training update를 수행하기 위해 모든 optimization iteration마다 다음과 같은 dense re-feeding step을 거쳤다.

(1) 주어진 sparse 벡터 $x$에 대해 dense $f(x)$와 MMSE loss를 계산한다. (첫 번째 forward pass)

(2) gradient를 계산하고 가중치를 업데이트한다. (첫 번째 backward pass)

(3) 도출된 $f(x)$를 새로운 input으로 보고 $f(f(x))$를 계산한다. 이때 $f(x)$와 $f(f(x))$ 모두 dense하고 MMSE에서 모든 $m$이 0이 아닌 값을 갖는다. (두 번째 forward pass)

(4) gradient를 계산하고 가중치를 업데이트한다. (두 번째 backward pass)

각 iteration마다 (3)과 (4) 단계가 1회 이상 수행된다. 이를 통해 기존에 한 번씩만 이루어지던 forward, backward pass를 여러 번 수행시켜 모델의 성능을 높였다.

3. Conclusion

본 논문에서 제안된 Deep AutoEncoder는 dropout과 SELU등 최신 딥러닝 기술을 이용해 적은 양의 데이터로도 유저의 rating을 잘 예측해냈다. 또한 iterative output re-feeding은 collaborative filtering에서 학습 속도를 높이고 모델의 generalization 성능을 향상시키는데 도움을 주었다.

Suvash Sedhain, Aditya Krishna Menon, Scott Sanner, and Lexing Xie. 2015. Autorec: Autoencoders meet collaborative filtering. In Proceedings of the 24th International Conference on World Wide Web. ACM, 111–112.

1. Introduction

Collaborative Filtering(CF) 모델들은 아이템에 대한 유저의 선호도를 뽑아내 개인화된 추천을 제공하는 것을 목표로 한다. Netflix challenge를 통해 여러 종류의 CF 모델들이 제안되었고, 그 중 matrix factorization과 neighbourhood 모델이 인기를 끌었다.

본 논문에서는 AutoRec이라는 새로운 CF 모델을 제안한다. AutoRec은 최근 vision과 speech task 분야에서 좋은 성능을 보이고 있는 neural network, 그 중에서도 autoencoder를 추천시스템에 적용한 모델이다. 저자는 AutoRec이 기존에 있던 neural approach에 비해 representational, computational advantages를 가지고 있다고 말한다.

2. The AutoRec Model

rating-based collaborative filtering에서는 $m$명의 유저와 $n$개의 아이템, 그리고 partially observed 유저-아이템 rating matrix $R \in \mathbb{R}^{m \times n}$이 존재한다. 각각의 유저 $u \in U = {1 ,... ,m}$은 partially observed vector $\mathbf{r}^{(u)}=(R_{u1}, ..., , R_{un}) \in \mathbb{R}^n$ 으로 표현될 수 있다. 비슷한 방법으로 각각의 아이템 $i \in I = {1 ,...,n }$ 역시 partially observed vector $\mathbf{r}^{(i)}=(R_{1i},, ..., , R_{mi})$로 표현될 수 있다.

논문에서 AutoRec 모델은 아이템 기반 autoencoder를 학습한다. 즉 partially observed vector $\mathbf{r}^{(i)}$를 input으로 받아 저차원의 latent space에 투영시키고, 이를 다시 output space의 벡터 $\mathbf{r}^{(i)}$로 reconstruct하여 관찰되지 않았던 rating을 예측해내는 것이 목표이다. 유저 기반 autoencoder를 학습시키고 싶다면 $\mathbf{r}^{(u)}$를 이용해 같은 과정을 반복하면 된다.

$\mathbb{R}^d$의 벡터 집합 $\mathbf{S}$가 주어져 있을 때, 어떤 자연수 $k$에 대해 autoencoder는 다음과 같이 RMSE를 최소화하는 방향으로 학습된다. $$ \min_{\theta} \sum_{\mathbf{r} \in \mathbf{S}} ||\mathbf{r}-h(\mathbf{r};\theta)||_2^2 $$

$h(\mathbf{r};\theta)$는 활성화 함수 $f(\cdot)$, $g(\cdot)$를 이용한 input $\mathbf{r}\in \mathbb{R}^d$의 reconsturction을 나타낸다. $$ h(\mathbf{r};\theta)=f(\mathbf{W} \cdot g(\mathbf{Vr}+\mathbf{u})+\mathbf{b}) $$

식에서 $\theta={\mathbf{W}, \mathbf{V}, \mathbf{\mu}, b}$는 모델 파라미터로, backpropagation을 통해 학습된다. $\mathbf{W} \in \mathbb{R}^{d \times k}$, $\mathbf{V} \in \mathbb{R}^{k \times d}$는 transformation matrix, $\mu \in \mathbb{R}^k$, $\mathbf{b} \in \mathbb{R}^d$는 bias이다.

아래 그림은 아이템 기반 AutoRec 모델의 구조이다. AutoRec은 벡터 집합 ${\mathbf{r}^{(i)}}_{i=1}^n$을 autoencoder에 통과시킨다. 이때 각 $\mathbf{r}^{(i)}$에서 관측된 요소에 대해서만 backpropagation으로 가중치를 업데이트하였다. 또한 학습된 파라미터를 regularize하여 과적합을 방지하였다.

따라서 Item-based AutoRec(I-AutoRec) 모델의 목적 함수는 아래와 같다. $$ \min_{\theta} \sum_{i=1}^n ||\mathbf{r}^{(i)}-h(\mathbf{r}^{(i)};\theta)||{\mathcal{O}}^2,+ {\lambda \over 2} \cdot (||\mathbf{W}||_F^2 + ||\mathbf{V}||_F^2) $$ 식에서 $||\cdot||{\mathcal{O}}^2$는 연산 시 관찰된 rating만 고려했다는 것을 의미한다. User-based AutoRec(U-AutoRec)의 경우엔 ${\mathbf{r}^{(u)}}_{u=1}^m$으로 식을 대체하면 된다.

결론적으로, I-AutoRec은 $2mk+m+k$개의 파라미터를 요구한다. 학습된 파라미터 $\hat{\theta}$에 대해 I-AutoRec이 도출해내는 rating은 다음과 같다.

$$ \hat{R}_{ui}=(h(\mathbf{r}^{(i)};\hat{\theta}))_u $$

위 Figure 1에서 색칠된 노드는 관찰된 rating을 뜻하고, 실선 화살표는 input $\mathbf{r}^{(i)}$에 대해 업데이트되는 가중치를 의미한다.

3. Conclusion

AutoRec은 autoencoder에 기반한 discriminative model로, gradient 기반 backpropagation을 통해 빠르게 학습되는 장점을 가지고 있다. 파라미터 수가 적기 때문에 연산에 필요한 메모리가 적고 과적합 가능성도 낮다. 또 activation function $g(\cdot)$을 통해 nonlinear latent representation도 학습할 수 있다.

짧은 논문이었지만 인상적이었다..! encoding-decoding 과정을 통해 관찰되지 않은 rating을 얻어낸다는 아이디어가 신선했다👍

H. Guo, R. Tang, Y. Ye, Z. Li, and X. He, “Deepfm: A factorizationmachine based neural network for CTR prediction,” in Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, 2017, pp. 1725–1731.

1. Introduction

click-through-rate(CTR) 예측은 유저가 추천된 아이템을 클릭할 확률을 추정하는 task로, 추천시스템의 주요 과제 중 하나이다. 클릭 수를 높여 더 많은 수익을 내는 것은 많은 추천시스템의 목표라고 할 수 있다.

CTR 예측을 위해서는 유저의 클릭 행위 뒤에 숨겨진 implicit feature interaction을 학습할 필요가 있다. 예를 들어 앱 추천시스템의 경우 유저가 앱을 다운받는 행위는 시간대, 유저의 나이와 성별 같은 feature와 앱 카테고리 사이의 interaction이 CTR에 영향을 미칠 수 있다. 이러한 interaction은 매우 복잡하고 low, high-order feature interaction 가릴 것 없이 CTR에 있어서 모두 중요한 역할을 한다.

결국 중요 포인트는 feature interaction을 효과적으로 학습하는 것이다. 선행 연구에서는 generalized linear model부터 factorization machine, wide & deep learning까지 데이터 속에 감춰진 feature interaction을 머신러닝으로 잡아내기 위한 많은 시도가 이루어졌다. 하지만 low-order interaction이나 high-order interaction에만 편향되었거나, feature engineering 과정이 복잡해지는 등 몇몇 한계점이 존재했다.

논문에서 저자는 FM과 DNN의 구조를 결합한 DeepFM 모델을 제안한다. DeepFM은 FM의 특징을 가지고 있어 low-order feature interaction을 학습하고, DNN처럼 high-order feature interaction도 학습할 수 있다. wide & deep model과 같이 복잡한 feature engineering이 필요하지도 않다. 또 wide part와 deep part가 동일한 input, embedding vector를 공유한다는 특징이 있어 complexity를 감소시키고 효과적으로 학습될 수 있다.

2. Our Approach

모델 학습을 위한 데이터는 $n$개의 instance $(\chi, y)$로 구성되어 있다. $\chi$는 유저와 아이템 쌍을 포함하고 있는 $m$-fields data이고, $y \in {0, 1}$은 유저의 클릭 행위를 구분하는 associated label이다.

$\chi$는 범주형 변수와 연속형 변수를 모두 포함할 수 있는데, 범주형 변수의 경우 one-hot encoding으로 나타내고 연속형 변수의 경우 값 그 자체가 feature가 되거나 discretization 후 one-hot encoding으로 나타내는 방법이 있다.

이후 각 instance는 $(x, y)$로 변환된다. $x=[x_{field_1},x_{field_2}, \cdots,x_{field_j},\cdots x_{field_m}]$인 $d$차원 벡터로 $x_{field_j}$는 $\chi$에서 $j$번째 field의 벡터 표현식이다. 보통 $x$는 차원이 높고 희소한 벡터이다.

CTR 예측 task는 유저가 특정 앱을 클릭할 확률을 추정하는 예측 모델 $\hat{y}=CTR_model(x)$를 학습시키는 것이다.

2.1 DeepFM

DeepFM의 구조는 아래 그림과 같다. low-, high-order feature interaction을 학습하기 위해 Factorization Machine(FM)과 deep neural network를 결합한 구조를 가지고 있다.

DeepFM에서 FM component와 deep component는 같은 input을 공유한다. feature $i$에 대해서, 가중치 $w_i$는 order-1 importance를 나타낸다. 그리고 latent vector $V_i$는 FM component에서는 order-2 interaction, deep component에서는 high-order interaction을 나타내기 위해 사용된다.

$w_i$, $V_i$, 그리고 network parameter를 포함한 모든 파라미터들은 jointly train되어 다음과 같이 최종 예측값이 도출된다.

$$ \hat{y}=sigmoid(y_{FM}+y_{DNN}) $$ $\hat{y} \in (0, 1)$은 CTR 예측값, $y_{FM}$은 FM component의 output, $y_{DNN}$은 deep component의 output이다.

FM Component

FM component는 아래 그림과 같은 factorization machine이다.

FM은 linear interaction(order-1) 외에도 pairwise feature interaction(order-2)으로써 latent vector간의 inner product 연산을 이용한다. 기존 FM은 feature $i$와 $j$ 모두 한 data에 존재할 때 interaction이 학습될 수 있었는데, DeepFM의 FM component에서는 latent vector $V_i$와 $V_j$의 inner product를 통해 order-2 feature interaction이 좀 더 간편하게 계산될 수 있다.

FM 모델의 output은 위 그림에서 볼 수 있듯이 Addition unit과 Inner Product unit의 합이 된다.

$$ y_{FM}=\langle w, x\rangle + \sum_{j_1=1}^{d} \sum_{j_2 = j_1+1}^d \langle V_i, V_j \rangle x_{j_1} \cdot x_{j_2},,\ $$

$$ \text{where }w \in R^d , ; V_i \in R^k $$

Deep Component

deep component는 feed-forward neural network로 high-order feature interaction을 학습하는 것이 목적이다.

CTR 예측을 위한 raw feature input vector는 매우 sparse하고, 높은 차원을 가졌으며, 범주형 변수와 연속형 변수가 섞여있고, 필드들이 그룹화되어있다. 따라서 첫 번째 hidden layer에 통과시키기 전에 input vector를 저차원의 dense한 실수 벡터로 압축시켜주는 과정이 필요하다.

아래 그림은 input layer와 연결된 embedding layer의 구조를 보여준다.

위 network 구조는 두 가지 특징이 있다. 먼저 input field vector들끼리 크기가 다를 수 있음에도 embedding은 같은 크기 $k$로 맞춰진다는 것이다. 또 latent feature vector $V$가 여기서는 network weight 역할을 하게 된다.

선행연구에서 network를 초기화하기 위해 FM으로 사전학습된 latent feature vector를 사용한 것과 달리, 저자는 FM 모델도 전체 learning architecture에 포함시켰다. 즉 FM을 통한 사전학습 과정을 없애고 전체 network를 end-to-end로 jointly train시켰다.

embedding layer의 output을 $a^{(0)}=[e_1, e_2, \cdots , e_m]$이라고 할 때, $a^{(0)}$은 DNN에 투입되어 아래 식과 같은 forward process를 거친다.

$$ a^{(l+1)}=\sigma(W^{(l)}a^{(l)}+b^{(l)}) $$ 식에서 $l$은 layer depth, $\sigma$는 활성화 함수, $a^{(l)}$, $W^{(l)}$, $b^{(l)}$은 각각 $l$번째 layer의 output, weight, bias를 나타낸다.

이렇게 dense real-value feature vector가 만들어지면 sigmoid 함수 $y_{DNN} = \sigma(W^{|H|+1}\cdot a^H +b^{|H|+1})$ 를 거치면서 DNN을 통한 CTR 예측값이 도출된다. $|H|$는 hidden layer 수이다.

2.2 Relationship with the other Neural Networks

이어서 DeepFM을 CTR 예측에 사용되는 기존 모델들과 비교한다.

Figure 5에서 가장 왼쪽에 있는 모델은 FNN으로, FM-initialized feed-forward neural network이다. FM을 이용해 pre-train을 하는 원리이지만 몇 가지 단점이 존재한다. 바로 embedding parameter들이 FM에 과도하게 영향을 많이 받는다는 점과 pre-training 단계로 인해 학습 efficiency가 줄어든다는 점이다. 또 high-order feature interaction만을 잡아낸다는 단점도 있다. 반면 DeepFM은 사전학습이 필요없고 high-, low- order interaction을 모두 잡아낼 수 있다.

중앙에 있는 모델은 PNN이다. PNN은 embedding layer와 첫 번째 hidden layer 사이에 product layer를 넣어 inner product, 혹은 outer product로 high-order interaction을 잡아내고자 했다. 다만 outer product가 inner product에 비해 신뢰성이 떨어진다는 점과 연산의 복잡도가 높다는 한계가 존재한다.

가장 오른쪽에 있는 모델은 Wide & Deep Model로, low-, high- order feature interaction을 모두 잡아낼 수 있다는 장점을 가지고 있다. 하지만 wide part에 투입할 input을 만들어내는데 복잡한 feature engineering이 필요하다. DeepFM은 FM과 deep component가 같은 feature embedding을 공유할 수 있게 함으로써 이러한 한계를 극복했다.

FNN, PNN, Wide & Deep 모델과 DeepFM의 특징을 정리하면 아래 표와 같다.

3. Conclusions

CTR 예측을 위해 본 논문에서 제안된 DeepFM은 FM 기반 neural network 모델로써 deep component와 FM component가 jointly train 된다. DeepFM의 장점은 3가지 정도로 요약할 수 있다. 먼저 별다른 pre-training 과정이 필요하지 않다. 또 high-, low- order feature interaction을 모두 학습할 수 있다. 마지막으로 feature embedding을 공유하여 feature engineering 없이 동작한다.

Chen et al., 2016 Wide & deep learning for recommender systems. CoRR, abs/1606.07792, 2016.

1. Introduction

추천시스템의 주요 과제 중 하나는 memorization과 generalization 측면에서 동시에 좋은 성능을 내는 것이다. 여기서 memorization이란, 자주 함께 등장하는 아이템 쌍 혹은 feature 조합을 학습하는 것을 말한다. 그리고 generalization이란 상관관계의 transitivity에 기반하여 과거에 나타나지 않았던 새로운 feature 조합을 찾아내는 것을 말한다.

memorization에 기반한 추천은 주로 topical한 정보나 유저가 이미 취했던 action에 기반하여 item 랭킹을 매긴다. 반면 generalization에 기반한 추천은 추천된 아이템의 다양성을 높이는데 목적이 있다.

규모가 큰 온라인 추천시스템에서는 주로 로지스틱 회귀와 같은 generalized linear model이 쓰인다. 간단하고, 확장성이 있고, 해석 가능하기 때문이다. 이때 모델은 sparse feature 벡터 간의 cross-product로 feature interaction을 학습한다. 함께 등장하는 feature 쌍을 target label과 연관지어 memorization 성능을 높이는 것이다. 그러나 이러한 경우 training data에 없는 feature 조합에 대해서는 일반화시킬 수 없다는 한계가 존재한다.

반대로 factorization machine이나 DNN과 같은 embedding-based 모델은 관찰되지 않은 feature 조합에 대해서도 generalization 성능이 높다. 하지만 sparse, high-rank한 유저-아이템 matrix에서는 효과적으로 low-dimensional representation을 학습하기 어렵다. 결국 over-generalize 현상과 함께 전혀 관계없는 아이템 추천으로 이어질 수도 있다.

저자는 위 딜레마를 해결하기 위해 wide & deep learning framework를 제안한다. 아래 그림과 같이 linear model component와 neural network component를 공동으로 학습시켜 memorization과 generalization 측면에서 모두 좋은 성능을 내고자 했다.

2. Recommender System Overview

논문에서는 학습을 위한 데이터로 구글 플레이스토어의 앱 추천 task를 다루었다. 앱 추천 시스템의 flow는 다음과 같다.

유저가 플레이스토어에 진입하면 유저와 아이템에 대한 feature 데이터가 생성된다. 이때 추천시스템은 ranking된 앱 리스트를 반환하고 유저는 클릭, 설치와 같은 action을 수행한다. 그리고 이런 action 기록들은 training data가 된다.

다만 데이터베이스에 수백만 개의 앱이 존재하기 때문에, 짧은 시간 내에 모든 앱에 대해 순위를 매기는 것이 불가능하다. 따라서 유저가 특정 단어를 검색했을 때 해당 검색어와 관련된 앱 후보군을 먼저 rule-based 방식으로 추출한다. 그리고 이렇게 추출된 후보군들에 대해서만 추천 알고리즘을 이용해 score를 매긴다. score는 보통 $P(y|\mathbf{x})$를 사용하는데, 이는 feature 벡터 $\mathbf{x}$ 하에서 유저의 action이 일어날 확률을 의미한다.

3. Wide & Deep Learning

3.1 The Wide Component

wide & deep model에서 wide component는 generalized linear model로, $y=\mathbf{w}^T \mathbf{x} +b$ 형태이다. 이때 $y$는 예측값, $\mathbf{x}=[x_1 , x_2, \cdots , x_d]$는 $d$개의 feature로 이루어진 vector, $\mathbf{w}=[w_1, w_2, \cdots , w_d]$는 모델 파라미터이고 $b$는 bias를 의미한다.

feature set은 가공되지 않은 raw input feature와 transformed feature로 나뉜다. transformed feature를 만들어내기 위해 cross-product를 사용하는데, 다음과 같은 식으로 표현된다. $$ \phi_k (\mathbf{x})= \prod_{i=1}^{d}x_i ^{c_{ki}} \qquad c_{ki} \in { 0, 1} $$ $c_{ki}$는 이진 변수로 $i$번째 feature가 $k$번째 transformation $\phi_k$에 포함되면 1, 아니면 0이다. cross-product transformation은 모든 binary feature가 1일 때에만 1을 도출하고, 하나라도 0이 포함되어 있으면 0을 도출한다. 즉, cross-product를 통해 binary feature 간의 interaction을 잡아낼 수 있고, 이는 generalized linear model에 nonlinearity를 추가해준다.

3.2 The Deep Component

이어서 wide & deep model의 deep component는 feed-forward neural network로 두었다. 먼저 고차원의 categorical feature를 embedding vector로, 즉 저차원의 dense한 real-valued 벡터로 변환한다. 만들어진 embedding vector는 final loss function이 최소화되는 방향으로 학습된다. 이 과정에서 low-dimensional dense embedding vector는 neural network의 hidden layer를 통과하게 된다. 구체적인 수식은 아래와 같다.

$$ a^{(l+1)} =f(W^{(l)}a^{(l)}+b^{(l)}) $$

$l$은 hidden layer 번호, $f$는 활성화 함수를 의미하고 $a^{(l)}$, $b^{(l)}$, $W^{(l)}$은 각각 $l$번째 layer에서의 activation, bias, model weight을 의미한다.

3.3 Joint Training of Wide & Deep Model

이렇게 학습된 wide component와 deep component의 output log odds는 가중합해져 joint training을 위한 logistic loss function에 투입된다. 각 모델이 독립적으로 학습되는 ensemble 방식과 달리, joint training에서는 wide & deep 파트와 가중합을 모두 고려하여 파라미터들이 동시에 최적화된다. 또 deep model의 단점을 보완하기 위해 커다란 wide model을 학습할 필요 없이 작은 규모의 cross-product feature transformation만을 추가하면 된다.

wide & deep model의 joint training은 output gradient에 대한 back-propagation으로 수행된다. 저자는 학습을 위한 optimizer로 wide part에서는 FTRL 알고리즘을 이용했고 deep part에서는 AdaGrad를 이용했다.

마지막 logistic regression을 통한 모델의 prediction은 다음과 같다. $$ P(Y=1|\mathbf{x}) = \sigma (\mathbf{w}{wide}^{T}[\mathbf{x}, \phi(\mathbf{x})]+\mathbf{w}{deep}^{T} a^{(l_f)}+b) $$ $Y$는 binary class label, $\sigma(\cdot)$은 sigmoid 함수, $b$는 bias, $\phi(\mathbf{x})$는 original feature $\mathbf{x}$에 대한 cross product transformation 결과를 의미한다. $\mathbf{x}{wide}$와 $\mathbf{x}{deep}$은 각각 wide model의 가중치 벡터, deep model에서 마지막 activation $a^{(l_f)}$의 가중치 벡터이다.

4. Conclusion

추천시스템에 있어서 memorization과 generalization은 모두 중요하다. wide linear model은 cross-product transformation을 통해 희소한 feature간의 interaction을 효과적으로 memorize할 수 있다. 그리고 deep neural network는 이전에 관찰되지 않은 feature interaction을 low-dimensional embedding을 통해 generalize할 수 있다.

본 논문에서 제안된 wide & deep model은 앱 추천시스템에 큰 발전을 가져왔다.

앙상블의 효과는 역시 대단하다😀

S. Rendle, "Factorization Machines," 2010 IEEE International Conference on Data Mining, 2010, pp. 995-1000, doi: 10.1109/ICDM.2010.127.

1. Introduction

Support Vector Machine(SVM)은 머신러닝과 데이터마이닝 분야에서 가장 인기있는 모델 중 하나이다. 그럼에도 불구하고 collaborative filtering에서는 SVM보다 standard matrix/tensor factorization model 또는 factorized parameter를 활용한 specialized model이 좋은 성능을 낸다. 그 이유는 SVM이 sparse한 데이터 환경에서 non-linear한 kernel space의 reliable parameter를 학습하지 못하기 때문이다.

본 논문에서는 Factorization Machine(FM)이라고 불리는 새로운 모델을 제안한다. FM은 SVM과 같은 general predictor로써 어떤 실수 feature vector든지 학습하여 회귀, 분류 같은 작업을 수행할 수 있다. 나아가 높은 sparsity에서도 reliable parameter를 잘 추정해내는 모델이다. SVM이 dense parametrization을 이용한 것과 달리, FM은 factorized parametrization으로 복잡한 interaction을 잡아낸다.

또한 FM의 연산을 linear time으로 줄인 방법도 소개한다. 즉 파라미터의 수에만 의존하여 연산 속도가 결정되고, 이는 기존 SVM 모델이 support vector에 의존하여 이중 연산 형태를 수행한 것보다 훨씬 빠르다.

2. Prediction Under Sparsity

대부분의 prediction task는 실수 feature vector $\mathbf{x} \in \mathbb{R}^n$를 타겟 도메인 $T$에 매핑시키는 문제로 치환할 수 있다. 예를 들어 회귀 문제이면 $T = \mathbb{R}$, 분류 문제이면 $T = { +, -}$가 된다. ranking task에서는 feature vector $\mathbf{x}$를 특정 실수값에 대응시키는 function을 모델이 학습하고 이렇게 도출된 score에 따라 feature vector를 정렬한다.

본 논문에서는 $\mathbf{x}$가 매우 sparse한 경우를 다룬다. 즉, 벡터 $\mathbf{x}$를 구성하는 대부분의 요소 $x_i$가 0인 상황이다. 실생활에서 feature vector가 sparse한 사례는 상품 구매 데이터나 text 분석처럼 categorical variable이 많은 도메인에서 쉽게 찾아볼 수 있다.

아래 그림은 영화 리뷰 데이터 $S$로부터 feature 벡터가 어떻게 만들어질 수 있는지를 보여준다. 데이터는 어떤 유저 $u \in U$가 영화 $i \in I$에 대해 $t \in \mathbb{R}$ 시점에 매긴 평점 $r \in { 1, 2, 3, 4, 5}$로 구성되어 있으며** 모델의 목표는 유저의 평점 $y$을 예측하는 것**이다.

먼저 파란색 부분은 $|U|$명의 유저를 나타내기 위한 binary indicator variable vector이다. 하나의 리뷰는 한 명의 유저가 작성하기 때문에, 오직 하나의 variable만 1이 되고 나머진 0이다. 다음으로 주황색 부분은 $|I|$개의 영화를 나타내기 위한 vector이다. 마찬가지로 하나의 리뷰에는 한 개의 영화만 매핑되기 때문에, 오직 하나의 variable만 1이다. 노란색 부분은 유저가 과거에 리뷰를 남겼던 영화를 표현하기 위한 vector이다. 각각의 유저에 대해 variable의 총합이 1이 되도록 normalized 된 것이 특징이다. 초록색 부분은 날짜를 나타내는 부분으로, 특정 시점으로부터 몇 달이 흘렀는지를 표현한다. 마지막 갈색 부분은 유저가 직전에 리뷰를 남긴 영화를 나타내는 vector이다.

예를 들어, 두 번째 row는 A 유저가 14개월째에 NH 영화를 보고 평점 3점을 매겼다는 사실을 나타낸다. 또한 이 유저가 영화 TI, NH, SW를 봤고 NH를 보기 직전에 TI를 봤다는 것도 표현하고 있다.

3. Factorization Machines(FM)

3.1 Factorization Machine Model

저자가 제안한 degree=2인 Factorization Machine의 원리를 수식으로 표현하면 다음과 같다. $$ \hat{y}(\mathbf{x}) := w_0 + \sum_{i=1}^{n} {w_i x_i} + \sum_{i=1}^{n} \sum_{j=i+1}^{n} <\mathbf{v}_i , \mathbf{v}_j>x_i x_j $$

추정해야 할 모델 파라미터는 $w_0 \in \mathbb{R}$, $\mathbf{w} \in \mathbb{R}^n$, $\mathbf{V} \in \mathbb{R}^{n \times k}$로, $w_0$는 global bias, $w_i$는 $i$번째 변수에 대한 가중치이다.** $\hat{w}_{i, j}:=<\mathbf{v}_i, \mathbf{v}_j>$는 두 벡터 $\mathbf{v}_i , \mathbf{v}_j$에 대한 내적 연산인데, $i$번째 변수와 $j$번째 변수 간의 interaction을 표현**한다. 이를 통해 FM은 변수 간의 single, pairwise interaction을 잡아낼 수 있다.

latent vector의 차원 $k$가 충분히 크다면, 임의의 positive definite matrix $\mathbf{W}$에 대해 $\mathbf{W}=\mathbf{V} \cdot \mathbf{V}^t$를 만족하는 matrix $\mathbf{V}$가 항상 존재한다. 따라서 $k$만 크다면 FM은 어떤 interaction matrix $\mathbf{W}$도 표현할 수 있다. 그러나 sparse한 데이터 환경에서는 복잡한 interaction을 표현하기에 데이터가 부족하기 때문에 $k$를 제한할 수밖에 없다. 오히려 $k$를 줄이고 모델의 generalization을 높이는 선택을 한다.

FM은 interaction parameter간의 독립성을 깨뜨리고 factorize하여 sparse한 데이터로도 interation을 추정해내는 장점이 있다. 이는 하나의 interaction이 연관된 다른 interaction 사이의 파라미터를 추정하는데 도움을 줄 수 있다는 걸 의미한다.

연산의 시간 복잡도 측면에서도 FM은 장점을 가지고 있다. 위에서 제시한 식 형태를 보면 시간복잡도는 $O(kn^2 )$ 이다. 그러나 pairwise interaction 식을 재구성하여 다음과 같이 식을 변형할 수 있다.

$$ \sum_{i=1}^{n} \sum_{j=i+1}^{n} <\mathbf{v}i, \mathbf{v}_j>x_ix_j \qquad\qquad\qquad\qquad\qquad\qquad $$ $$ = {1 \over 2}\sum{i=1}^{n} \sum_{j=1}^{n} <\mathbf{v}i, \mathbf{v}_j>x_ix_j - {1 \over 2}\sum{i=1}^{n} <\mathbf{v}i, \mathbf{v}_j>x_ix_j $$ $$ = {1 \over 2} (\sum{i=1}^{n} \sum_{j=1}^{n} \sum_{f=1}^{k} v_{i,f} v_{j,f}x_ix_j - \sum_{i=1}^{n} \sum_{f=1}^{k} v_{i,f} v_{j,f}x_ix_i)\quad; $$ $$ = {1 \over 2} \sum_{f=1}^{k} ((\sum_{i=1}^{n} v_{i, f}x_i)(\sum_{j=1}^{n} v_{j,f}x_j) - \sum_{i=1}^{n} v_{i,f}^2 x_i^2)\qquad\quad;; $$ $$ = {1 \over 2} \sum_{f=1}^{k} ((\sum_{i=1}^{n} v_{i, f}x_i)^2- \sum_{i=1}^{n} v_{i,f}^2 x_i^2)\qquad\qquad\qquad\quad;;;; $$ 변형된 식은 $k$와 $n$에 대해 linear complexity를 가지며, 시간복잡도는 $O(kn)$이 된다.

나아가 $\mathbf{x}$의 elements 대부분이 0이기 때문에 $\sum$ 계산이 0이 아닌 elements에 대해서만 이루어지고 연산이 더 빠르게 수행된다.

3.2 Factorization Machines as Predictors

FM은 regression, binary classification, ranking 등 다양한 prediction task에 활용될 수 있다.

• Regression: $\hat{y}(\mathbf{x})$가 곧 predictor로 활용되며, optimization criterion으로 minimal least square error를 사용할 수 있다.

• Binary Classification: $\hat{y}(\mathbf{x})$의 부호가 곧 predictor이다. optimization criterion은 hinge loss나 logit loss를 주로 사용한다.

• Ranking: $\hat{y}(\mathbf{x})$의 score에 따라 벡터가 정렬된다. optimization은 pairwise classification loss를 사용한다.

3.3 Learning Factorization Machines

FM의 연산이 linear한 시간 복잡도를 가지기 때문에, 모델 파라미터 $w_0$, $\mathbf{w}$, $\mathbf{V}$는 SGD와 같은 gradient descent method로 학습된다. FM 모델의 gradient는 다음과 같다.

$$ {\partial \over \partial \theta} \hat{y}(\mathbf{x}) = \begin{cases} 1,\qquad\qquad\qquad\qquad\quad\quad;;;,\text{if }; \theta ;\text{ is } ;w_{0}\ x_i,\qquad \qquad\qquad\qquad\quad\quad;;\text{if }; \theta ;\text{ is } ;w_{i}\ x_i \sum_{j=1}^{n} v_{j, f}x_j - v_{i, f}x_i^2,\qquad \text{if }; \theta ;\text{ is } ;v_{i, f} \end{cases} $$ 식에서 $\sum_{j=1}^{n} v_{j, f}x_j$는 $i$에 무관하기 때문에 미리 계산될 수 있고, 각 gradient는 계산의 시간 복잡도는 $O(1)$이다. 또 sparsity 상에서도 각 파라미터 업데이트는 $O(kn)$만에 수행될 수 있다.

3.4 d-way Factorization Machine

앞서 제시한 2-way FM은 d-way FM으로 확장될 수 있는데, 그 식은 다음과 같다. $$ \hat{y}(x) := w_0 + \sum_{i=1}^{n}w_i x_i + \cdots+\sum_{l=2}^{d}\sum_{i_1=1}^n \cdots \sum_{i_l =i_{l-1}+1}^n (\prod_{j=1}^l x_{i_j} v_{i_j , f}^{(l)}) $$ $l$번째 interaction의 파라미터는 PARAFAC 모델로 factorized되며, 연산의 시간 복잡도는 $O(k_d n^d)$이다.

3.5 Summary

정리하면, FM은 factorized interaction을 이용해 feature vector $\mathbf{x}$에서 각 변수 간의 interaction을 잡아낸다. 이는 high sparsity 조건에서도 잘 작동하여** 관찰되지 않은 interaction을 generalize할 수 있다. 또 학습과 예측 단계의 시간 복잡도, 파라미터 수가 linear하다**는 점에서 SGD optimization을 가능하게 하고 다양한 loss function을 사용할 수 있다.

Factorization Machine은 추천시스템 뿐만 아니라 분류, 회귀 문제에도 적용될 수 있다고 한다. 유저, 아이템에 대한 다양한 feature를 투입할 수 있다는 점이 큰 장점으로 보인다. FM이 발전하여 만들어진 DeepFM 논문도 읽어봐야겠다.

Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, Tat-Seng Chua. 2017. Neural Collaborative Filtering. 2017 International World Wide Web Conference Committee

1. Introduction

추천 시스템은 이커머스, 온라인 뉴스나 소셜 미디어 사이트 등 많은 양의 정보가 있는 산업에서 필요한 정보만을 추출해주는 데에 중추적인 역할을 수행하고 있다. 대표적인 추천 시스템으로 유저와 아이템 간의 과거 상호작용을 토대로 개인화된 추천을 해주는 collaborative filtering 방식이 있는데, 그 중에서도 matrix factorization(MF)이 가장 잘 알려져 있다. MF는 유저와 아이템을 latent space로 투영시켜 latent feature에 대한 벡터로 각각을 나타낸다. 그리고 유저와 아이템의 상호작용을 나타내기 위해 latent 벡터 간의 inner product를 이용한다.

이렇게 만들어진 MF는 latent factor를 잡아낸 효과적인 model-based 추천 시스템이지만, 유저와 아이템 간의 상호작용을 간단하게 inner product로만 나타냈다는 점에서 한계가 존재한다. 단순히 latent feature들을 선형적으로 결합하는 것은 복잡한 상호작용을 잡아내기에 충분하지 않다는 것이다.

본 논문에서는 Deep Neural Networks(DNN)의 non-linearity를 이용해 유저의 implicit feedback signal을 잡아내는 방법을 다룬다. 나아가 MF가 Neural Collaborative Filtering(NCF)의 특수한 케이스임을 보이고 NCF의 효율성을 실험을 통해 증명한다. 여기서 implicit feedback이란 영상을 시청하거나 상품을 구매하고 아이템을 클릭하는 것처럼 유저의 행동에서 나타나는 선호도를 의미한다. implicit feedback은 자동으로 트래킹되고 content providers들이 쉽게 수집할 수 있는 데이터이지만 비정형 데이터이기 때문에 활용하기엔 까다롭다는 특징이 있다.

2. Preliminaries

2.1 Learning from Implicit Data

유저 수를 $M$, 아이템 수를 $N$이라고 하면, 유저의 implicit feedback으로부터 user-item interaction matrix $\text{Y} \in \mathbb{R}^{M \times N}$을 다음과 같이 정의할 수 있다. $$ y_{ui} = \begin{cases} 1, \text{ if interaction (user }u \text{, item }i \text{) is observed; }\ 0, \text{ otherwise.}
\end{cases} $$

$y_{ui}$가 1이면 유저 $u$와 아이템 $i$ 간에 상호작용이 존재하는 것을 의미한다. 하지만 그렇다고 해서 $u$가 $i$를 선호한다는 뜻은 아니다. 비슷하게, $y_{ui}$가 0이라고 해서 유저 $u$가 $i$를 선호하지 않는다고 말할 순 없다. 단순히 유저가 그 아이템에 관심이 없을 수도 있는 것이다.

결국 implicit feedback을 통한 추천은 $\text{Y}$에서 관찰되지 않은 요소들을 추정하는 문제가 된다. 이를 수식으로 표현하면 $\hat{y}{ui} =f(u, i | \Theta)$이 되고, 여기서 $\hat{y}{ui}$는 상호작용 $y_{ui}$에 대한 예측값, $\Theta$는 모델 파라미터, $f$는 interaction function을 의미한다.

파라미터 $\Theta$를 추정하기 위해, 흔히 두 가지 목적 함수를 이용한다. 바로 pointwise loss와 pairwise loss이다. pointwise loss는 회귀 문제에서 자주 사용되는 함수로 타겟 $y_{ui}$와 예측값 $\hat{y}_{ui}$의 squared loss를 최소화하는 것이다. 반면 pairwise loss는 관찰된 $y$ 값이 관찰되지 않은 값보다 더 큰 값을 갖도록 하여 둘 사이의 margin을 최대화하는 함수이다.

본 논문에서 NCF는 $\hat{y}_{ui}$를 추정하기 위한 interaction function $f$로 neural network를 사용하여, pointwise와 pairwise 둘을 모두 이용할 수 있다.

2.2 Matrix Factorization

MF는 각각의 유저와 아이템을 latent feature들의 실수 벡터로 나타낸다. 예를 들어 유저 $u$와 아이템 $i$의 latent vector를 $\mathbf{p}u$와 $\mathbf{q}_u$라고 하면 MF는 둘 사이의 interaction $y{ui}$을 다음과 같이 추정한다. $$ \hat{y}{ui} = f(u, i | \mathbf{p}_u , \mathbf{q}_i) = \mathbf{p}^T_u \mathbf{q}_i = \sum{k=1}^K{p_{uk} q_{ik}} $$ 식을 보면 알 수 있듯이 MF는 latent factor들의 선형 결합으로 만들어진 linear model이다. 다만 linear model이기에 발생하는 한계점이 존재한다. 위 그림 (a)에서 두 유저 $i$, $j$ 사이의 유사도 $s_{ij}$를 Jaccard coefficient를 이용해 계산하면, $s_{23}(0.66)>s_{12}(0.5)>s_{13}(0.4)$ 순으로 높다. 이를 latent space 상에 기하학적으로 나타낸 결과가 (b)의 $\mathbf{p}1$, $\mathbf{p}_2$, $\mathbf{p}_3$이다. 그런데 어떤 새로운 유저 $u_4$가 들어왔을 때, 기존 유저들과의 유사도를 계산하면 $s{41}(0.6)>s_{43}(0.4)>s_{42}(0.2)$ 순으로 높지만 새로운 벡터 $\mathbf{p}_4$를 $\mathbf{p}_1$과 가장 가깝고 $\mathbf{p}_2$보다는 $\mathbf{p}_3$에 가깝게 배치하려면 모순이 생긴다.

이는 MF가 복잡한 유저-아이템 interaction을 저차원의 latent space 상에서 표현하기 때문에 발생하는 문제이다. latent factor의 차원 $K$를 키우면 해결이 될 것이라 생각할 수도 있지만 오히려 overfitting 문제가 발생할 가능성이 크다. 따라서 저자는 이 한계를 극복하기 위해 non-linear한 DNN을 도입한다.

3. Neural Collaborative Filtering

3.1 General Framework

유저-아이템 interaction $y_{ui}$를 잡아내기 위해, 저자는 아래 그림과 같은 multi-layer representation을 이용했다.

기본적으로 한 layer의 output이 다음 layer의 input으로 들어가는 구조로 설계되어 있다. 가장 먼저 bottom layer의 input으로는 유저 $u$와 아이템 $i$에 대해 one-hot encoding된 벡터 $\mathbf{v}_u^U$, $\mathbf{v}_i^I$가 들어간다.

input layer 바로 위에는 embedding layer가 있는데, embedding layer은 fully connected layer로써 sparse한 input을 dense vector로 변환시켜주는 역할을 한다. 이렇게 만들어진 dense vector가 바로 latent vector라고 할 수 있다.

이어서 유저와 아이템의 embedding vector는 multi-layer neural architecture를 통과한다. neural collaborative filtering layers라고 명명된 이 layer들을 통과하면서 latent vector는 prediction score $\hat{y}_{ui}$로 변환된다.

이 과정을 수식으로 표현하면 다음과 같다.

$$ \hat{y}_{ui} = f(\mathbf{P}^T \mathbf{v}_u^U , \mathbf{Q}^T \mathbf{v}_i^I | \mathbf{P}, \mathbf{Q}, \Theta _f) $$ 식에서 $\mathbf{P} \in \mathbb{R}^{M \times K}$, $\mathbf{Q} \in \mathbb{R}^{N \times K}$는 latent factor matrix이고 $\Theta_f$는 interaction function $f$의 모델 파라미터이다. interaction function은 아래와 같은 식으로 나타낼 수 있는데,

$$ f(\mathbf{P}^T \mathbf{v}u^U , \mathbf{Q}^T \mathbf{v}_i^I) = \phi{out} (\phi_X (... \phi_2(\phi_1 (\mathbf{P}^T \mathbf{v}u^U , \mathbf{Q}^T \mathbf{v}_i^I))...)) $$ $\phi{out}$과 $\phi_{x}$는 각각 output layer와 $x$번째 layer의 mapping function을 의미한다.

모델에서 output $\hat{y}{ui}$는 0에서 1 사이의 값을 갖고, 타겟값 ${y}{ui}$는 0 또는 1의 값을 갖는다. ${y}{ui}=1$인 interaction의 집합을 $\mathcal{Y}$, ${y}{ui}=0$인 interaction의 집합을 $\mathcal{Y}^-$라고 할 때 likelihood function은 다음과 같다. $$ p(\mathcal{Y}, \mathcal{Y}^- |\mathbf{P}, \mathbf{Q}, \Theta_f) = \prod_{(u, i) \in \mathcal{Y}} \hat{y}{ui} \prod{(u, i) \in \mathcal{Y^-}} (1- \hat{y}{ui}) $$ 따라서 모델 학습을 위한 loss function은 양변에 -log를 취해주면 아래와 같은 형태가 된다. $$ L = - \sum{(u, i) \in \mathcal{Y}} \text{log}, \hat{y}{ui} - \sum{(u, i) \in \mathcal{Y}^-} \text{log}( 1- \hat{y}{ui})\ \qquad \qquad = - \sum{(u, i) \in \mathcal{Y} \cup \mathcal{Y}^-} y_{ui}, \text{log} , \hat{y}{ui} +(1-y{ui})\text{log}(1-\hat{y}_{ui}) $$

NCF는 위 binary cross-entropy 형태의 objective function을 최소화하는 방향으로 학습을 진행하며, 이때 stochastic gradient descent 방식으로 optimization이 수행된다.

3.2 Generalized Matrix Factorization(GMF)

우리가 기존에 알고 있던 MF는 NCF의 특수 케이스로 볼 수 있다. 논문에서는 다음과 같은 방법으로 이를 증명한다.

유저 latent 벡터 $\mathbf{p}_u$를 $\mathbf{P}^T \mathbf{v}_u^U$라고 하고, 아이템 latent 벡터 $\mathbf{q}_i$를 $\mathbf{Q}^T \mathbf{v}_i^I$라고 하자. NCF의 첫 번째 layer 함수를 다음과 같이 정의한다. $$ \phi_1 (\mathbf{p}_u, \mathbf{q}_i) = \mathbf{p}_u \odot \mathbf{q}_i $$

$\odot$은 벡터간의 element-wise product를 의미한다.

그럼 최종적으로 얻어지는 $\hat{y}_{ui}$는 아래 식을 따른다.

$$ \hat{y}{ui} = a{out} (\mathbf{h}^T (\mathbf{p}_u \odot \mathbf{q}_i)) $$

만약 activation function $a_{out}$을 identity function으로, output layer의 edge weight $\mathbf{h}$를 1로만 이루어진 단위벡터로 본다면, 결국 이는 MF 모델이 된다.

NCF framework 상에서 MF는 쉽게 확장되고 일반될 수 있다. 이를 Generalized MF로 이름 붙였으며, $a_{out}$에는 sigmoid 함수 $\sigma (x) = 1/(1+e^{-x} )$를 두었고 $\mathbf{h}$는 앞선 log loss를 통해 얻은 가중치로 두었다.

3.3 Multi-Layer Perceptron(MLP)

유저 벡터와 아이템 벡터를 단순히 concatenate 하는 것은 유저와 아이템 간의 복잡한 interaction을 설명하기에 충분하지 않다. 이를 해결하기 위해 저자는 concatenated vector에 hidden layer를 쌓는 MLP 구조를 이용해 모델의 flexibility와 non-linearity를 보장해주고 element-wise product만을 이용하는 GMF의 한계를 보완했다.

MLP 모델의 구조를 구체적으로 표현하면 다음과 같다. $$ \mathbf{z}1 = \phi_1 (\mathbf{p}_u, \mathbf{q}_i) = \begin{bmatrix} \mathbf{p}_u \ \mathbf{q}_i \end{bmatrix}, $$ $$ \phi_2(\mathbf{z}_1) = a_2 (\mathbf{W}_2^T \mathbf{z}_1 +\mathbf{b}_2), $$ $$ \cdots \cdots $$ $$ \phi_L(\mathbf{z}{L-1}) = a_L (\mathbf{W}L^T \mathbf{z}{L-1} +\mathbf{b}L), $$ $$ \hat{y}{ui} = \sigma(\mathbf{h}^T \phi_L(\mathbf{z}_{L-1})) $$ 식에서 $\mathbf{W}_x,$ $\mathbf{b}_x ,$ $a_x$는 각각 가중치 행렬, bias 벡터, 활성화 함수를 의미한다. 활성화 함수는 실험적으로 가장 좋은 성능을 보인 ReLU를 이용했다.

NN 구조는 tower pattern을 이용했는데, tower pattern이란 bottom layer에 가장 노드 수를 많이 두고 점차 노드 수를 줄여나간 형태를 말한다. 이런 구조에서 모델은 data의 abstractive feature를 더 잘 학습할 수 있다.

3.4 Fusion of GMF and MLP

지금까지의 내용을 정리하면, GMF는 linear kernel을 이용해서 latent feature interaction을 학습하고, MLP는 non-linear kernel로 interaction을 학습한다.

저자는 이 두 모델을 합쳐 각 모델이 가진 장점을 살리고자 했다. 우선 GMF와 MLP가 학습할 embedding을 분리해주고 모델이 학습된 후 마지막 hidden layer를 통과하며 도출된 결과를 concatenate하도록 아래 사진과 같은 구조를 설계했다.

이를 수식으로 표현하면 다음과 같다. $$ \phi^{GMF} = \mathbf{p}u^G \odot \mathbf{q}_i^G , $$ $$ \phi^{MLP} = a_L (\mathbf{W}_L^T (a{L-1}( \cdots a_2 (\mathbf{W}2^T \begin{bmatrix} \mathbf{p}_u^M \ \mathbf{q}_i^M \end{bmatrix}+b_2 ) \cdots)) + b_L) , $$ $$ \hat{y}{ui} = \sigma(\mathbf{h}^T \begin{bmatrix} \phi^{GMF} \ \phi^{MLP} \end{bmatrix}) $$ $\mathbf{p}_u^G$와 $\mathbf{p}_u^M$은 각각 GMF와 MLP의 유저 embedding, $\mathbf{q}_i^G$와 $\mathbf{q}_i^M$은 각각 GMF와 MLP의 아이템 embedding을 나타낸다. 앞서 언급했듯이 MLP의 활성화 함수로는 ReLU를 이용했다.

이렇게 만들어진 Neural Matrix Factorization(NeuMF) 모델은 MF의 linearity와 DNN의 non-linearity가 결합되어 유저-아이템 latent structure를 잘 학습했고 HR@10과 NDCG@10을 이용해 기존 모델과 비교했을 때 더 좋은 성능을 보였다.

Neural Collaborative Filtering은 papers with code 사이트에서 Recommendation Systems를 검색했을 때(https://paperswithcode.com/task/recommendation-systems) 가장 많이 implemented 되었다고 나오는 논문이다. 그만큼 딥러닝을 이용한 추천시스템의 기초가 된 논문이라고 할 수 있는데, 생각보다 어렵지 않고 아이디어가 간단해서 읽기 좋았다.

Jiaxin Huang, Yiqing Xie, Yu Meng, Yunyi Zhang, Jiawei Han. 2020. CoRel: Seed-Guided Topical Taxonomy Construction by Concept Learning and Relation Transferring. Proceedings of the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining.

1. Introduction

Taxonomy는 커다란 corpus의 단어들을 계층 구조로 나타내어 각 단어 사이의 관계를 이해하기 쉽게 분류하는 체계를 말한다. 특히 본 논문에서는 seed-guided taxonomy라 하여, 사람이 먼저 제시한 seed taxonomy를 기반으로 text corpus로부터 더 완전한 topical taxonomy를 구축하는 task에 대한 연구를 진행하였다.

위 그림에서처럼 user가 만약 음식에 대한 seed taxonomy와 corpus를 모델의 input으로 대입하면 더 깊고 넓은 계층 구조를 가진 taxonomy가 output으로 출력된다. 이때 각 노드는 비슷한 단어들의 묶음으로 이루어지고 이들을 대표하는 하나의 단어가 노드의 conceptual topic이 된다.

task를 성공적으로 수행하기 위해 본 논문에서는 relation transferring module과 concept learning module로 이루어진 CoRel framework를 제시하였다.

2. Problem Description

CoRel은 input으로 문서들의 집합 $D={ d_1, d_2, ..., d_{|D|}}$와 seed taxonomy $T^0$를 받는다. 이때 $T^0$의 각 노드 $e$는 corpus에 있는 하나의 단어가 된다. 또 $T^0$의 edge <$p_0$, $c_0$>는 user-interested parent-child pair를 의미하며, 특정 <$p$, $c$> pair를 포함하는 문장을 relation statement라고 정의한다. CoRel의 output은 더 complete한 버전의 topical taxonomy $T$가 되는데, 이때의 노드 $e$는 cluster를 대표하는 conceptual topic이다.

3. Methodology

3.1 Method Overview

논문에서 제안된 CoRel은 task를 수행하기 위해 2가지 종류의 module을 이용한다.

먼저 relation transferring module로 seed taxonomy에 있는 <$p_0$, $c_0$> 사이의 relation을 학습한다. 그리고 학습한 relation을 위쪽 방향으로 전달해서 root가 될 만한 단어를 찾는다. 아래 예시에서 "Lunch", "Food", "Dish"와 같은 general한 단어들이 taxonomy의 root 역할을 한다. 이어서 relation을 아래 방향으로 전달해 계층 구조에 새로운 topic과 subtopic들을 붙인다.

마지막으로 concept learning module을 이용해서 discriminative embedding space를 학습하고 각 concept node에 대한 topical cluster를 만들어 낸다.

3.2 Taxonomy Completion by Relation Transferring

1) Self-supervised Relation Learning

relation transferring module에서는 BERT 모델을 사용해서 parent-child relation을 학습한다. user-interested relation을 학습하기 위해, seed taxonomy에서 주어진 <$p_0$, $c_0$>의 relation statement를 positive training sample로 두었다. negative sample로는 sibling node의 relation statement와 랜덤한 문장을 사용했다.

모델의 input으로 parent와 child 단어를 [MASK] 토큰으로 가린 문장이 들어가면, classification layer를 통과하며 3개의 클래스로 분류된다. [MASK] 토큰에 해당하는 단어를 $e_1$과 $e_2$라고 할 때 각각 $e_1$이 $e_2$의 parent node인지, $e_2$가 $e_1$의 parent node인지, 또는 아무 관계가 없는지를 나타낸다. 이 훈련을 거치며 모델은 parent-child 사이의 relation을 학습하게 된다.

2) First-layer Topic Finding by Root Node Discovery

relation classifier를 얻은 후에는 taxonomy에서 target node를 정해서 그것의 parent node나 child node를 찾는다.

우선 root node를 찾기 위한 방법은 다음과 같다. 어떤 concept $e$와 그것의 parent가 될 수 있는 후보군 단어 $w$가 있을 때, $w$가 $e$의 parent가 될 확률을 KL divergence를 이용해 계산해준다. 그리고 이 확률이 threshold 값보다 크면 $w$를 $e$의 parent node로 지정한다.

$$ \text{Score(}w\rightarrow e\text{)}={{\sum_{s_{w\rightarrow e}} \mathbb{1}(\text{KL}(l ||p_w >\delta))}\over{\sum_{q \in Q}\sum_{s_{q}} \mathbb{1}(\text{KL}(l ||p_w >\delta))}} $$

사전에 주어진 seed taxonomy의 first-layer topic들에 대해 parent node가 되는 단어들을 각각 찾아 그 list를 만든다. 그리고 그 중 공통적으로 parent가 되는 node들을 taxonomy의 root node $R$로 지정한다.

first-layer의 새로운 topic 노드를 찾는 방법 역시 비슷하다. 위 식에서 $w$, $e$ 자리에 $r$, $w$를 대입해주면 $w$가 $r$의 child node가 될 확률을 계산할 수 있다. 그리고 모든 root node에 대해 $\text{Score}(r \rightarrow w)$를 계산하여 얻어진 평균을 기준으로 새로운 topic을 찾아낸다.

$$ \text{Score}(R \rightarrow w)={{\sum_{r \in R} \text{Score}(r \rightarrow w)}\over{|R|}} $$

3) Candidate term extraction for subtopics

first-layer topic을 생성한 후에는 각 topic에 대한 subtopic들을 찾는다. 사실 subtopic을 곧바로 찾는 것은 아니고 subtopic이 될 수 있는 후보군들을 탐색한다. 이 경우 $w$, $e$ 자리에 $e$, $w$를 대입해주어 어떤 단어 $w$가 topic node $e$의 child가 될 확률을 계산한다.

3.3 Generating Topical Clusters by Concept Learning

1) Concept Learning based on Taxonomy and Corpus

discriminative embedding space의 학습을 위해 3개의 loss function을 정의했다.

먼저 비슷한 단어들끼리는 비슷한 주변 단어를 공유한다는 가정 하에, window size가 $h$인 local context에서 주변 단어가 등장할 확률을 최대화시키는 $L_l$을 정의했다.

$$ L_l = - \sum_{d \in D} \sum_{1 \le i \le |d|} \sum_{0<|j-i|\le h} \text{log} P(w_j |w_i) $$

이어서 유사한 문서 내의 단어들은 비슷한 topic을 가진다는 점에서 단어가 어떤 문서 내에 들어있는지 예측하는 확률을 최대화시키는 loss fuction $L_d$를 정의했다. 식에서 $d$는 document embedding을 말한다.

$$ L_d = - \sum_{d \in D} \sum_{1 \le i \le |d|} \text{log} P(d|w_i) $$

마지막으로 확장된 taxonomy에서 서로 다른 concept 사이의 구별을 명확히 하기 위해, 매 epoch마다 concept cluster $C_e$에 distinctive한 단어를 하나씩 추가했다. 그리고 concept embedding과 cluster 간의 유사도를 높이기 위해 loss function $L_{prox}$를 정의했다.

$$ L_{prox}=\sum_{e \in \mathcal{T}} \sum_{w \in C_e} \text{log} P(e|w) $$

이렇게 정의된 3가지 loss function의 가중치 합으로 최종 목적함수가 만들어졌고, concept learning이 진행되었다.

$$ L=L_l + \lambda_d L_d + \lambda_p L_{prox} $$

2) Topic and Relation aware Subtopic Finding

topical constraints와 relational constraints를 고려한 subtopic을 찾기 위해 co-clustering method를 이용한다.

먼저 아래와 같은 Topic-Type table을 만든다.

단어들은 semantic meaning에 따라 열별로 분리되고, semantic type에 따라 행별로 구분된다. 구체적으로, topic에 따른 clustering은 discriminative embedding space에서 affinity propagation clustering을 거쳐 만들어진다. 반면 type별 clustering은 average BERT embedding space에서의 affinity propagation clustering으로 만들어진다.

이 table을 변형해서 subtopic과 type에 따른 결합확률분포를 나타내는 indicative Topic-Type matrix를 만든다. 그리고 만들어진 indicative topic-type matrix $M$에서 co-clustering을 이용해 consistency score가 높은 subtopic들을 추출한다.

$$ \text{Consistency(Cluster}k \text{)}={{\sum{\text{row label[i]==k}}\sum_{\text{col. label[j]==k}} M_{i,j}} \over{\sum_{\text{row label[i]==k}}\sum_{\text{col. label[j]==k}} 1}} $$

4. Experiments and Results

4.1 Experiment Setup

CoRel의 성능을 검증하기 위해 DBLP와 Yelp dataset을 사용했다.

DBLP는 컴퓨터 과학 내 여러 분야에서 쓰여진 논문들의 초록 데이터이다. AutoPhrase를 이용해 약 15만 개의 초록에서 의미 있는 단어들을 뽑았고, 16,650개의 단어를 추출했다.

Yelp는 108만 개의 레스토랑 리뷰 데이터를 가지고 있다. Yelp에서도 DBLP와 비슷한 방식으로 14,619개의 단어를 추출했다.

성능 비교를 위한 모델로는 Concept Learning을 결합한 Hi-Expan, TaxoGen, HLDA, HPAM를 두었다.

4.2 Qualitative Results

Yelp dataset으로 만든 topical taxonomy의 일부를 살펴보면, 최소한의 seed taxonomy가 주어졌을 때에도 output으로 완전한 topical taxonomy가 도출된 것을 확인할 수 있다. "soup", "pork", "beef"와 같은 음식들도 first-layer topic에 새로 추가되었다. 또 pork의 다양한 cooking style에 따라 명확히 구별되는 subtopic이 만들어졌다.

DBLP dataset의 결과도 성공적이다. input과 비교했을 때 훨씬 다양한 컴퓨터 과학의 분야가 taxonomy에 추가되었다.

relation learning module의 효과를 검증하기 위해 CoRel로 추출한 subtopic을 Hi-Expan으로부터 추출된 것과 비교해보았다. 아래 표에서 X로 표시된 것은 잘못된 subtopic 임을 나타내고, 가위 표시가 된 것은 중복된 단어이거나 기존 단어와 유의어 관계임을 나타낸다.

표에서 DBLP-Machine Learning의 예시를 보면 Hi-Expan은 "neural network"와 비슷한 개념들을 중복해서 추출해냈다는 것을 확인할 수 있다. "artificial neural networks"와 "multilayer perceptron"은 "neural network"의 sibling node가 아닌 cluster 내에 포함되어야 할 것이다. 반면에 CoRel에서는 그런 문제가 발생하지 않고 더 나은 성능을 보였다.

마지막으로 concept learning module이 cluster를 잘 만들어내는지 확인하기 위해 TaxoGen, HLDA, HPAM 모델과 비교했다.

그 결과, 관련이 없는 단어나 교차되는 개념의 단어를 포함하고 있는 TaxoGen, HLDA, HPAM과는 달리 CoRel은 일관적이고 서로 구별되는 단어들을 잘 찾아내는 것을 확인했다.

기존에 읽었던 논문들에서는 aspect 수를 명확히 지정해주어야 하는 단점이 있었는데, CoRel에서는 seed taxonomy만 제공해주면 unsupervised 방식으로 단어들을 추출해내고 clustering 된다는 점이 인상적이었다. 아마 CVF 탐색 과제를 위해 CoRel을 사용하게 될 것 같은데, 내용을 잘 이해하고 있어야겠다🙂

Ruidan He, Wee Sun Lee, Hwee Tou Ng, Daniel Dahlmeier. 2017. An Unsupervised Neural Attention Model for Aspect Extraction. Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics.

1. Introduction

sentiment analysis의 주요 과제 중 하나인 aspect extraction은 문장 내에서 토픽의 역할을 하는 aspect term을 추출하는 것을 목표로 한다.

aspect extraction은 2개의 sub-task로 이루어진다. 먼저 리뷰 문서 내의 모든 aspect term을 추출한다. 그리고 비슷한 의미를 가진 aspect term들을 하나의 aspect로 군집화한다. 예를 들어, "The beef was tender and melted in my mouth."라는 문장에서 aspect term을 추출하자면 "beef"가 될 것이다. 그리고 이렇게 리뷰 문서의 문장들로부터 "beef", "pasta", "pork"와 같은 토픽 단어들을 추출해내면 "food"라는 aspect로 군집화할 수 있다.

기존에는 rule-based, supervised, unsupervised 3가지 종류의 aspect extraction 방식이 있었다. 그러나 rule-based 방식은 추출한 aspect term들을 군집화하지 못한다는 단점이 있었고, supervised 방식은 데이터에 대한 labeling이 필요하다는 점과 새로운 데이터를 잘 분류하지 못한다는 문제가 있었다. 그래서 Latent Dirichlet Allocation(LDA) 모델처럼 labeled 데이터가 필요하지 않은 unsupervised 방식이 널리 사용되었다. 하지만 LDA 모델 또한 자주 함께 나오는 단어들에 대한 정보를 담지 못하고 길이가 짧은 리뷰 문서에서 aspect 분포를 추정하기가 어렵다는 단점이 존재했다.

이러한 LDA 모델의 단점을 보완하기 위해 본 논문에서는 Attention-based Aspect Extraction(이하 ABAE) 모델을 제안한다. attention mechanism은 어느 aspect에도 포함되지 않는 단어들에 대한 가중치를 줄여 모델이 aspect 관련 단어들에만 집중할 수 있도록 도와준다.

2. Model Description

ABAE의 궁극적인 목적은 aspect embedding을 학습하는 것이다. ABAE 모델을 통해 어떤 embedding 값이 주어졌을 때 동일한 선형 공간 상에서 aspect와 가까운 단어들을 찾을 수 있고, 해당 aspect가 의미하는 바를 쉽게 해석할 수 있다.

ABAE의 구조를 그림으로 도식화하면 아래와 같다.

ABAE의 input으로 리뷰 문장의 단어 index 리스트가 들어오면 먼저 attention mechanism을 통해 aspect와 관련이 없는 단어들을 필터링한다. 그리고 이렇게 필터링된 word embedding으로부터 sentence embedding $\mathbf{z}_s$를 만든다. 그 후 aspect와 단어가 같은 embedding 공간에 있도록 하기 위해 aspect embedding 행렬 $\mathbf{T}$를 이용해 sentence embedding을 aspect embedding의 선형 결합으로 reconstruct한다.

2.1 Sentence Embedding with Attention Mechanism

sentence embedding 단계에서는 attention mechanism을 이용하여 input sentence $s$에 대해 벡터 $\mathbf{z}_s$를 만든다. 이때 만들어진 벡터 $\mathbf{z}_s$가 문장의 aspect에 대한 정보를 최대한 많이 담을 수 있도록 해야 한다.

attention mechanism은 다음과 같은 순서로 수행된다. 먼저 input sentence의 단어 $w$를 특성 벡터 $\mathbf{e}_w \in \mathbb{R}^d$에 mapping 시킨다. 특성 벡터로는 pre-trained된 word embedding을 사용하는데, 이는 자주 함께 등장하는 단어를 embedding 공간에서 가깝게 mapping 시키는 word embedding의 성질을 활용하기 위함이다. 단어 집합의 크기를 $V$라고 할 때 이 특성 벡터들을 행으로 쌓으면 word embedding 행렬 $\mathbf{E} \in \mathbb{R}^{V \times d}$가 만들어진다.

그리고 모든 word embedding의 평균 $\mathbf{y}_s$를 구한다. 이때 $\mathbf{y}s$는 문장의 전체적인 내용을 대변하는 하나의 벡터가 된다. $$ \mathbf{y}_s = {1 \over n} \sum{i=1}^{n} \mathbf{e}{w_i} $$ 다음으로 $\mathbf{y}_s$와 word embedding $\mathbf{e}_w$를 mapping 해주는 행렬 $\mathbf{M} \in \mathbb{R}^{d \times d}$을 학습시킨다. 그리고 행렬 $\mathbf{M}$으로 단어들을 변환시켜 $K$개의 aspect와 관련 있는 단어들만 필터링시킨다. 이렇게 필터링된 단어들을 $\mathbf{y}_s$와 내적하여 문장과 각 단어의 관련성을 계산하고, $d_i$로 나타낸다. $$ d_i = \mathbf{e}{w_i}^{\top} \cdot \mathbf{M} \cdot \mathbf{y}s $$ 그리고 각각의 단어 $w_i$가 문장의 토픽과 관련되어 있을 확률을 나타내는 가중치 $a_i$를 아래와 같이 계산한다. $$ a_i = {{\text{exp}(d_i)}\over{\sum{j=1}^{n}{\text{exp}(d_j)}}} $$ 마지막으로 sentence embedding $\mathbf{z}s$를 word embedding $\mathbf{e}{w_i}$들의 가중치 합으로 정의한다. $$ \mathbf{z}s = \sum{i=1}^{n}{a_i \mathbf{e}_{w_i}} $$

2.2 Sentence Reconstruction with Aspect Embeddings

2.1의 과정을 거쳐 얻어진 sentence embedding에 대한 reconstruction 벡터를 구한다.

우선 $K$개의 aspect embedding에 대한 가중치 벡터 $\mathbf{p}_t$를 계산한다. sentence embedding $\mathbf{z}_s$의 차원을 $d$에서 $K$로 축소시키고 softmax 함수를 통과시키면 정규화된 가중치 벡터 $\mathbf{p}_t$를 얻어낼 수 있다.

$$ \mathbf{p}_t= softmax(\mathbf{W} \cdot \mathbf{z}_s +\mathbf{b}) $$

식에서 $W$와 $\mathbf{b}$는 각각 가중치 행렬과 편향 벡터로 training 과정에서 학습되는 파라미터이다. 이렇게 얻어진 벡터 $\mathbf{p}_t$의 요소들은 input 문장이 각 aspect에 속할 확률값이 된다.

그리고 aspect embedding 행렬 $\mathbf{T} \in \mathbb{R}^{K \times d}$를 설정하여 $K$개 aspect에 대한 aspect embedding을 학습한다.

최종적으로 reconstruction $\mathbf{r}_s$는 행렬 $\mathbf{T}$에 의한 변환으로 얻어진 aspect embedding의 선형 결합으로 정의된다. $$ \mathbf{r}_s= \mathbf{T}^{\top} \cdot \mathbf{p}_t $$

2.3 Training Objective

ABAE는 reconstruction 오차를 최소화하는 방향으로 훈련된다.

각각의 input 문장에 대하여, training data에서 무작위로 $m$개의 문장을 뽑아 negative sample로 둔다. 그리고 이 negative sample들의 word embedding 값을 평균낸 벡터를 $\mathbf{n}_i$로 표현한다.

training을 통해 재구성된 embedding $\mathbf{r}_s$는 target 문장의 embedding $\mathbf{z}_s$와 비슷하고 negative sample들과는 차이가 있어야 한다. 따라서 objective function $J$는 $\mathbf{r}_s$와 $\mathbf{z}_s$의 내적값은 키우고 $\mathbf{r}_s$와 negative sample 간의 내적은 줄이는 방향의 hinge loss 형태가 된다.

$$ J(\theta)=\sum_{s \in D}\sum_{i=1}^{m} \text {max}(0, 1-\mathbf{r}_s\mathbf{z}_s+\mathbf{r}_s\mathbf{n}_i) $$

식에서 $D$는 training data를 의미하고 $\theta ={\mathbf{E,T,M,W,b}}$는 모델의 파라미터이다.

2.4 Regularization Term

논문에서는 리뷰 dataset을 가장 잘 대변하는 aspect에 대한 vector representation을 얻고자 한다. 하지만 aspect embedding 행렬 $\mathbf{T}$는 training 과정에서 불필요한 중복 문제를 겪을 수 있다. 따라서 aspect embedding의 다양성을 높이기 위해 아래 식과 같은 regularization 항을 추가한다. $$ U(\theta)=\Vert \mathbf{T}_n \cdot \mathbf{T}^{\top}-\mathbf{I}\Vert $$

여기서 $\mathbf{I}$는 항등 행렬이고, $\mathbf{T}_n$은 $\mathbf{T}$의 각 행이 크기 1로 정규화된 행렬이다. 그리고 $\mathbf{T}_n \cdot \mathbf{T}_n^\top$의 대각성분이 아닌 요소들은 서로 다른 aspect embedding을 내적한 값이다. 이 값들이 0이 될 때 $U$는 최소가 된다. 따라서 regularization 항은 aspect embedding 행렬 $\mathbf{T}$의 행들이 서로 직교하도록 만들어주고, 서로 다른 aspect 벡터들 간의 중복을 줄이는 역할을 한다.

최종적인 objective function $L$은 앞서 정의한 $J$와 $U$를 합하여 만들어진다. $$ L(\theta)=J(\theta)+\lambda U(\theta) $$ 식에서 $\lambda$는 하이퍼파라미터로 regularization 항의 가중치를 조절하는 역할을 한다.

3. Experimental Setup

3.1 Datasets

1) Citysearch corpus

Citysearch New York의 레스토랑 리뷰 문서로, 50,000개 이상의 레스토랑 리뷰가 포함되어 있다. 선행연구에서 이 중 3,400개의 문장에 labeling을 해두어, 그 문장들을 모델의 aspect extraction 평가에 사용할 것이다. 'Food', 'Staff', 'Ambience', 'Price', 'Anecdotes', 'Miscellaneous' 6개의 aspect label이 존재한다.

2) BeerAdvocate

약 150만 개의 맥주 리뷰를 포함하고 있는 리뷰 문서이다. 그 중 1,000개의 리뷰, 9,245개의 문장이 5개의 aspect로 labeling 되어 있다. 5개의 aspect는 'Feel', 'Look', 'Smell', 'Taste', 'Overall'이다.

3.2 Baseline Methods

ABAE의 성능을 검증하고자 LocLDA, k-means, SAS, BTM 4가지의 비교 모델을 설정했다.

3.3 Experimental Settings

실험을 위해 ABAE의 word embedding 행렬 $\mathbf{E}$를 word2vec으로 학습된 word vector들로 초기화시켰다. embedding 크기는 200, window 크기는 10, negative sample 크기는 5로 두었다.

또한 k-means를 돌려 나온 cluster들의 중심으로 하여 aspect embedding 행렬 $\mathbf{T}$를 초기화했다. 나머지 파라미터들은 랜덤으로 초기화를 시켰다.

training 과정에서는 Adam optimizer를 이용해 word embedding 행렬 $\mathbf{E}$와 다른 파라미터들을 초기화시켰다. 학습률은 0.001로 두었고, epoch은 15개로, batch 크기는 50으로 설정했다.

이외에도 input 1개당 negative sample의 수를 20개로 정했고, orthogonality penalty weight $\lambda$를 1로 두었다.

4. Evaluation and Results

4.1 Aspect Quality Evaluation

아래 표는 레스토랑 리뷰에 대해 ABAE가 추출해낸 14개의 aspect를 정리해둔 것이다. gold aspect에서 'food'로 분류한 것을 'main dish', 'dessert', 'drink' 등으로 분류한 것처럼 ABAE가 좀 더 세분화된 aspect를 찾아냈음을 알 수 있다.

1) Cohesive Score

모델의 성능을 수치적으로 나타내기 위해, coherence score를 지표로 사용했다. aspect $z$가 있고 $z$와 가장 관련 있는 상위 $N$개의 단어 집합 $S^z={ w_1^z , ... , w_N^z}$가 주어졌을 때, coherence score는 아래와 같이 계산된다. $$ C(z;S^z)=\sum_{n=2}^{N} \sum_{l=1}^{n-1} \text{log} {{D_2 (w_n^z , w_l^z )+1}\over{D_1(w_l^z)}} $$ $D_1(w)$는 단어 $w$가 문서 내에서 나오는 빈도를 의미하고, $D_2(w_1, w_2)$는 단어 $w_1$과 $w_2$가 문서에서 함께 나오는 빈도를 의미한다.

아래 그래프는 레스토랑과 맥주 리뷰 각각에 대해 모델들의 평균 coherence 값을 계산하여 나타낸 것이다.

그래프를 살펴보면 ABAE가 다른 모델에 비해 높은 coherence 값을 가지고 있음을 확인할 수 있다. k-means의 성능이 ABAE만큼 뛰어난 것도 눈여겨볼 만하다.

2) User Evaluation

다음으로 ABAE가 찾아낸 aspect들이 실제로 사람이 판단했을 때 받아들일 만한지를 알아보고자 했다. 3명의 평가자가 판단하여 만약 상위 50개 단어가 일관성 있게 aspect를 나타낸다면 해당 aspect는 coherent 하다고 표현했다. 이 방식으로 레스토랑과 맥주 리뷰를 분석한 결과, 5개 모델 중 ABAE가 가장 많은 coherent aspect를 가지고 있었다.

그리고 각각의 coherent aspect에 대해, 상위 $n$개 단어를 뽑아 단어마다 해당 aspect를 잘 나타낸다고 판단되면 'correct'라는 label을 붙였다. 그리고 모델마다 precision을 계산하여 그래프로 나타냈다.

위 그래프를 살펴보면, ABAE의 precision이 타 모델에 비해 가장 높았고 그 차이는 $n$이 커질수록 명확해지는 것을 알 수 있다.

4.2 Aspect Identification

이제 ABAE의 sentence-level aspect identification 성능을 평가하기 위해, 예측된 label이 실제 label과 얼마나 비슷한지 precision, recall, F1 score를 계산하여 분석해보았다. 레스토랑 리뷰의 경우 앞서 설정한 비교 모델 이외에 MaxEnt-LDA와 SERBM을 추가로 도입하여 비교했다.

먼저 레스토랑 리뷰에 대한 결과를 표로 정리한 Table 4를 보면 ABAE가 'Staff'와 'Ambience' aspect에서 다른 모델보다 높은 F1 score를 가졌다. 하지만 'Food' aspect에서는 낮은 F1 score가 나타났다. 이것은 리뷰 문장에 구체적인 음식 메뉴가 나타나있지 않으면, 모델은 리뷰 문장을 'Food' aspect가 아닌 다른 aspect로 판단하는 경향이 있었기 때문이다.

맥주 리뷰에 대한 precision, recall, F1 score를 나타낸 Table 5를 보면, 마찬가지로 ABAE가 대부분의 aspect에서 높은 F1 score를 가진다는 것을 확인할 수 있다.

4.3 Validating the Effectiveness of Attention Model

마지막으로 attention layer의 중요성을 확인하기 위해 attention layer를 제거하고 word embedding의 평균값으로 sentence embedding을 계산한 ABAE$^-$ 모델을 설정했다. 그리고 이를 ABAE와 비교하여 precision, recall, F1 score 값을 계산했을 때, attention layer가 있는 ABAE 모델의 성능이 훨씬 좋다는 것을 알 수 있었다.

처음 논문을 읽으면서 ABAE의 구조를 이해하는 데에 어려움이 좀 있었다. 이렇게 리뷰를 쓰면서 검색도 많이 해보고 논문을 계속 반복해서 읽게 되어 개념이 명확해지는 것 같다. 앞으로 논문 리딩과 글쓰기 실력 모두 발전하기를..!

Manish Munikar, Sushil Shakya, Aakash Shrestha. 2019. Fine-grained Sentiment Classification using BERT. Pulchowk Campus, Institute of Engineering, Tribhuvan University.

앞서 포스팅했던 BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding 논문을 이해한 후 본 논문을 읽으면 좋을 것이다.

1. Introduction

sentiment classification은 단어, 문장 등의 텍스트를 사전에 정의한 sentiment 클래스로 분류하는 supervised machine learning task이다.

흔히 알려진 binary sentiment classification은 텍스트를 positive 또는 negative 2가지로만 분류하지만, fine-grained sentiment classification에서는 아래 그림과 같이 5가지의 클래스로 텍스트를 분류한다.

다른 언어 모델과 마찬가지로 sentiment classification 모델은 정해진 크기의 숫자 벡터를 input으로 가진다. 그동안 텍스트의 유의미한 정보를 숫자 벡터에 잘 담을 수 있도록 하는 다양한 NLP 모델이 개발되었는데, 대표적으로 구글이 만든 BERT가 있다. BERT는 양방향에서 문맥을 이해하는 transformer 구조 기반의 모델로 많은 NLP task들을 성공적으로 잘 수행한다.

선행 연구에 따르면 BERT는 binary sentiment classification task인 SST(Stanford Sentiment Treebank)-2 dataset에서 좋은 성능을 보였다. 따라서 본 논문에서는 BERT가 fine-grained sentiment classification도 잘 수행할 수 있는지를 확인하고자 했다.

2. Dataset

실험을 위한 dataset으로는 11,855개의 영화 리뷰 문장을 포함하고 있는 SST를 사용했다. SST는 약 21만 개의 labeled text를 가지고 있어 단어, 구문, 문장의 sentiment를 학습하기 좋을 것이라고 판단했기 때문이다.

SST의 각 문장은 Stanford constituency parser에 의해 트리 구조로 쪼개진다. 이때 root node에는 문장 전체가 존재하게 되고, leaf node에는 문장을 이루는 단어들이 들어간다. 그리고 각 node는 수작업으로 labeling이 되어있다.

아래 그림은 SST dataset의 한 리뷰 문장을 트리 구조로 나타낸 것이다.

SST-5에는 5개의 sentiment label(very negative, negative, neutral, positive, very positive)이 있는데, 각각 0에서 4까지의 숫자로 표현된다. 만약 이를 positive/negative로만 분류를 하면 SST-2 dataset이 된다.

실험을 위해, SST-2와 SST-5 각각의 모든 node의 label을 예측하는 task와 root node의 label을 예측하는 총 4가지 task를 수행하였다.

3. Methodology

3.1 BERT

BERT는 unlabeled text로부터 bidirectional representation을 학습할 수 있는 사전 훈련 모델이다. Masked word prediction과 Next sentence prediction을 거치며 양방향에서 문맥을 파악할 수 있게 되고, 사전 훈련된 파라미터에 downstream task의 종류에 따른 하나의 layer가 추가되어 fine-tuning이 이루어진다.

BERT의 구조는 아래 그림과 같다.

BERT의 input에는 특별한 token이 필요하다. 각 sequence의 시작에는 분류 token인 [CLS] token이 있어야 한다. 그리고 문장을 구분하는 역할을 하는 [SEP] token도 매 문장의 끝에 와야 한다.

실험을 위해 BERT Base와 BERT Large 모델을 사용하였는데, 두 모델에 대한 세부 정보는 아래 표와 같다.

3.2 Preprocessing

리뷰 텍스트를 모델에 투입시키기 전 다음과 같은 전처리 과정을 거친다.

1) Canonicalization

리뷰 텍스트의 숫자, 기호들을 제거하고 대문자를 모두 소문자로 바꾸어준다.

2) Tokenization

WordPiece tokenizer를 이용해 텍스트를 token들로 쪼갠다. 'playing'이라는 단어를 'play'+'##ing'로 분해하는 것처럼, 각 단어를 접두사와 접미사, 어근으로 쪼갠다.

3) Special token addition

마지막으로 [CLS]와 [SEP] token을 적절한 위치에 추가한다.

3.3 Proposed Architecture

논문에서 제안한 모델의 구조는 위 그림과 같다. 먼저 preprocessing을 거친 후, BERT를 통해 sequence embedding 값을 계산한다. 그 다음으로 dropout 층에서는 0.1의 확률로 몇몇 뉴런들을 dropout 시켜 과적합을 방지한다. 이 dropout 층은 훈련 단계에서만 사용되고, 추론 단계에서는 생략된다. 마지막으로 softmax classifier를 통과하여 input text가 어떤 class로 레이블링 될지를 예측한다.

4. Experiments and Results

4.1 Comparison Models

제안된 모델의 성능을 기존 모델과 비교하기 위해, 7개의 comparison model을 설정했다. 먼저 word embedding 모델 중 대량의 텍스트 corpus로 사전 훈련된 word vector와 paragraph vector가 sentiment classifier에 적용되었다. 그리고 RNN 모델 중에서는 standard RNN과 좀 더 정교한 RNTN을 사전 훈련 없이 사용했다. 또한 recurrent network를 대표하는 left-to-right LSTM과 bidirectional LSTM를 도입했고, 마지막으로 1차원 CNN이 feature extractor로써 사용되었다.

4.2 Evaluation Metric

SST는 dataset의 수가 각 클래스마다 균등하게 분포되어 있는 특징이 있다. 따라서 올바른 예측의 수를 전체 예측의 수로 나눈 accuracy measure를 모델 성능 평가의 지표로 이용하였다.

4.3 Results

실험 결과, 아래 Table II에서 볼 수 있듯이 BERT Base와 BERT Large가 기존 모델들에 비해 훨씬 높은 accuracy measure를 가졌다. BERT가 선행 연구에서 다루지 않았던 SST-5 task에 대해서도 좋은 성능을 보인다는 것을 확인할 수 있었다.

BERT의 성능이 정말 뛰어났다는 것을 다시 한 번 느낄 수 있었다. 이 논문에서는 수작업을 통해 이미 labeling이 되어있는 SST data를 사용했는데, 데이터마이닝 랩에서 진행 중인 프로젝트의 data는 labeling이 되어있지 않은 것 같아서 이 문제에 대해 좀 더 고민해보기로 했다.

Jacob Devlin, Ming-Wei Chang, Kenton Lee, Kristina Toutanova. 2019. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding, Google AI Language.

2018년 구글이 공개한 인공지능 언어 모델 BERT에 대한 논문이다. BERT는 등장과 동시에 자연어 처리(Natural Language Processing, 이하 NLP) 분야에서 획기적인 성능을 보여주었다.

1. Introduction

언어 모델을 사전 훈련시키는 것은 NLP task의 성능 향상에 효과적이라고 알려져 있다.

사전 훈련된 언어 모델이 작동하는 원리는 크게 2가지로 나뉜다. 먼저 특정 task에 특화된 네트워크 구조에 사전 훈련된 네트워크를 부가적인 feature로써 추가하는 방식이 있는데, 이를 feature-based 방식이라고 한다. 대표적으로는 ELMo가 있다. 반면에 모델의 범용성을 고려하여 모든 파라미터를 사전 훈련한 후 적용할 task의 종류에 따라 세부 조정하는 방식도 있는데, 이를 fine-tuning 방식이라고 한다. OpenAI GPT가 fine-tuning 모델의 대표적인 예시이다.

그러나 위 두 모델은 왼쪽에서 오른쪽으로, 또는 오른쪽에서 왼쪽으로 단방향 학습만 가능하다는 한계가 존재한다. 예를 들어, 'I like to ... soccer.'라는 문장의 빈칸을 채우는 문제에서 두 모델은 'I like to'에만 의존하여 빈칸에 들어갈 단어를 결정하고 오른쪽에 있는 'soccer'의 영향은 받지 않는다. 문맥을 이해하여 단어를 채우기 위해서는 빈칸 앞뒤 단어를 모두 고려하는 방식으로 훈련이 이루어져야 할 것이다.

따라서 저자들은 본 논문을 통해, 양방향에서 문맥을 이해하여 pre-train시키는 BERT(Bidirectional Encoder Representations from Transformers)를 제안한다.

2. BERT

BERT는 pre-training과 fine-tuning의 두 개 step으로 나뉜다.

먼저 pre-training 과정에서는 MLM과 NSP task를 비지도 방식으로 훈련하게 된다. MLM과 NSP task의 자세한 내용은 아래 2.1에서 다루겠다. pre-training이 끝나면 fine-tuning 단계로 넘어가 pre-train을 통해 얻어진 parameter들을 모델의 초기 parameter로 대입하고, downstream task의 labeled data에 맞게 파라미터를 세부 조정한다.

BERT는 양방향 트랜스포머 인코더를 여러 층 쌓아올린 구조를 가지고 있다. 논문에서는 실험을 위해 BERT Base(L=12, H=768, A=12)와 BERT Large(L=24, H=1024, A=16) 2개의 모델을 설정했다. L은 트랜스포머 블록의 수, H는 hidden size, A는 self-attention head의 수이다. 이때 BERT Base는 GPT와의 성능 비교 목적으로 제작된 모델이다.

BERT를 다양한 종류의 task에 사용하기 위해, input의 형태를 단일 문장과 쌍으로 구성된 문장을 모두 나타낼 수 있는 형태로 만들었다. 이를 sequence라고 표현한다. 각 sequence의 첫 번째 token은 [CLS]라는 token인데, 이것은 분류 문제에서 sequence의 의미를 응축해서 나타내는 역할을 한다. 분류 문제가 아닌 경우에는 사용하지 않는 token이 된다. 그리고 input이 쌍으로 이루어진 문장일 경우 문장을 구분하기 위해 [SEP]라는 token을 사용한다.

위 그림에서 볼 수 있듯이, BERT의 input은 token 임베딩과 segment 임베딩, position 임베딩을 더하여 만들어진다. 먼저 WordPiece 임베딩의 30,000개 vocabulary를 사용해 token을 임베딩한다. 그리고 segment 임베딩을 통해 문장 쌍이 input으로 들어왔을 때 각 문장을 구분한다. 마지막으로 position 임베딩에서 self-attention 모델이 token의 위치를 고려할 수 있도록 위치 정보를 담는다.

2.1 Pre-training BERT

BERT를 pre-train시키기 위해 사용한 두 개의 비지도 task를 소개한다.

Task #1: Masked Language Model(MLM)

MLM은 input token 중 일부를 가리고 가려진 token이 무엇인지를 예측하는 task이다.

논문에서는 각 sequence의 token 15%를 가리고 task를 수행했다. 이 15% token 중 80%는 [MASK] token으로 대체하고, 10%는 랜덤 token으로 대체했다. 그리고 나머지 10%는 가리지 않고 그대로 두었다. 이것은 fine-tuning 단계에서 [MASK] token이 나타나지 않기 때문에 pre-training과 fine-tuning 사이에 발생하는 불일치 문제를 해결하기 위한 방안이다.

MLM 예시

• 80%: my dog is hairy $\to$ my dog is [MASK]
• 10%: my dog is hairy $\to$ my dog is apple
• 10%: my dog is hairy $\to$ my dog is hairy

이러한 MLM task를 수행하며 모델은 앞뒤 문맥을 파악할 수 있는 방향으로 훈련된다.

Task #2: Next Sentence Prediction(NSP)

NSP는 두 문장 A, B가 있을 때 A 다음에 B가 올 것인지의 여부를 예측하는 task이다.

이때 50%는 연결이 되는 문장 쌍(IsNext), 50%는 서로 관련이 없는 문장 쌍(NotNext)을 투입하여 훈련시킨다.

NSP 예시

• IsNext: [CLS] the man went to [MASK] store [SEP], he bought a gallon [MASK] milk [SEP]
• NotNext: [CLS] the man went to [MASK] store [SEP], penguin [MASK] are flight ##less birds [SEP]

NSP task를 통해 모델이 두 문장 사이의 관계를 이해하여 Question Answering(QA)이나 Natural Language Inference(NLI)와 같은 task를 수행할 수 있다.

2.2 Fine-tuning BERT

Fine-tuning에서는 사전 학습된 BERT 파라미터에 label이 있는 downstream task를 추가로 지도학습시켜 파라미터들을 미세 조정한다.

input으로는 단일 문장이 들어갈 수도 있고, Question-Answering처럼 문장 쌍이 들어갈 수도 있다. output은 task의 종류에 따라 달라지는데, 분류 문제의 경우 [CLS] token을 사용해 분류 결과를 출력한다.

위 그림에서 (a)와 (b)는 sequence-level task이고, (c)와 (d)는 token-level task이다. (a)와 (b)는 분류 task이므로 [CLS] token을 classification output으로 사용한다. (c)는 Question이 주어졌을 때 Answer의 시작, 끝 위치를 찾는 task이다. (d)는 하나의 문장에 나오는 각 token들을 tagging하는 task이다.

fine-tuning은 pre-training에 비해 빠르게 학습되며, 데이터 크기가 클수록 정확도가 상승하는 특징이 있다.

3. Experiments

3.1 GLUE

먼저 General Language Understanding Evaluation(이하 GLUE)의 8개 task를 이용해 BERT의 성능을 측정했다. GLUE의 task들은 아래와 같다.

• Multi-Genre Natural Language Inference(MNLI): 두 문장이 주어졌을 때 뒷 문장이 앞 문장에 수반되는지/반대되는지/중립인지를 맞추는 task
• Quora Question Pairs(QQP): 두 question이 서로 동일한 의미를 갖는지 여부를 판단하는 task
• Question Natural Language Inference(QNLI): Question과 Sentence가 주어졌을 때, Question에 대한 답을 Sentence에서 찾을 수 있는지 판단하는 task
• Stanford Sentiment Treebank(SST-2): 영화 리뷰의 한 문장이 주어졌을 때, 긍정적인지/부정적인지를 분류하는 task
• Corpus of Linguistic Acceptability(CoLA): 문장이 문법적으로 옳은지를 판단하는 task
• Semantic Textual Similarity Benchmark(STS-B): 두 문장이 얼마나 비슷한지 1점에서 5점 사이의 점수로 나타내는 task
• Microsoft Research Paraphrase Corpus(MRPC): 두 문장이 서로 동일한 의미를 갖는지 여부를 판단하는 task
• Recognizing Textual Entailment(RTE): MNLI와 비슷하지만 더 적은 수의 training data로 뒷 문장이 앞 문장에 수반되는지 여부를 판단하는 task

결과를 살펴보면, BERT Base 모델은 GPT와 비교했을 때 모든 task에서 나은 성능을 보였다. 그리고 BERT Large는 5개 모델 중 GLUE task들을 가장 잘 수행했다.

3.2 SQuAD v1.1

이어서 Stanford Question Answering Dataset(이하 SQuAD)을 사용해 Question에 대한 Answer를 문단에서 찾아내는 task에 대한 수행도를 평가했다.

그 결과, single BERT 모델이 기존 앙상블 모델에 비해 더 높은 f1-score를 보였다. TriviaQA fine-tuning data를 제외해도 여전히 기존 모델에 비해 좋은 성능을 보인 것을 알 수 있다.

3.3 SQuAD v2.0

SQuAD 2.0 task는 Question에 대한 Answer를 문단에서 찾는 task임은 동일하지만, 길이가 짧은 Answer가 존재하지 않아 SQuAD 1.1에 비해 더 현실적이라고 할 수 있는 task이다.

SQuAD 2.0에서도 BERT가 기존 모델에 비해 좋은 f1-score를 얻었음을 확인할 수 있다.

3.4 SWAG

마지막으로 Situations With Adversarial Generations(이하 SWAG)을 이용해 4개의 문장 중에서 문장 A 뒤에 올 문장 B를 고르는 task를 수행했다.

이번에도 BERT는 ESIM+ELMo 모델보다 27.1%, OpenAI GPT보다 8.3% 높은 성능을 보였다.

정리하면, BERT는 MLM, NSP 사전 훈련을 거쳐 양방향에서 문맥을 이해하는 구조를 가진 모델로 기존 SOTA 모델과 비교했을 때 다양한 종류의 NLP task를 성공적으로 수행하는 모델이다.

소감

구글에서 연구한 모델이라니..! 양방향으로 문맥을 파악하는 BERT의 성능이 기존 모델들에 비해 월등했다는 점이 인상깊었다. 물론 지금은 2020년 6월에 나온 GPT-3가 가장 뛰어난 언어 모델이라고 한다. BERT도 나름 나온지 3년도 안된 따끈따끈한 모델인데, 그새 GPT-3에게 따라잡힌 것을 보면 AI 기술이 매년 빠르게 진화한다는 것이 실감났다.

Hongning Wang, Yue Lu, Chengxiang Zhai. 2010. Latent Aspect Rating Analysis on Review Text Data: A Rating Regression Approach, Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.

여름방학 중 데이터마이닝랩 인턴을 하며 Social CVF 탐색 과제 참여의 일환으로 읽게 된 논문이다.

1. Introduction

리뷰를 분석하여 주요한 문장을 추출하고, 상품이나 서비스에 대한 고객들의 의견을 파악하는 것은 중요한 과제이다. 특히 리뷰의 총점(이하 overall rating)이 같더라도 고객마다 중요하게 생각한 요소(이하 aspect)는 다를 수 있기 때문에, 주요 aspect들을 정하고 각각의 aspect에 대한 개별 rating을 분석하는 과정이 필요하다.

이와 관련한 연구를 Latent Aspect Rating Analysis(LARA)라고 부른다. LARA의 목표는 overall rating과 리뷰 내용을 바탕으로 주요 aspect들에 대한 고객의 rating과, 각 aspect에 대해 고객이 생각하는 상대적인 중요도(이하 aspect weight)를 추론하는 것이다.

LARA 문제 해결을 위해서는 2가지 가정이 필요하다. 하나는 고객이 매기는 overall rating은 각 aspect rating의 가중치 합으로 계산된다는 것이고, 다른 하나는 각 aspect에 대한 rating 또한 리뷰 내에서 등장하는 관련 단어들의 가중치 합으로 생성된다는 것이다.

본 논문에서는 위 가정을 바탕으로 2단계 접근법을 제시하였다. 1단계에서는 bootstrapping 기반 알고리즘을 이용해 리뷰의 주요 aspect를 파악하고 내용을 분할한다. 2단계에서는 분할된 리뷰의 내용과 overall rating에 generative Latent Rating Regression(LRR) 모델을 적용하여 aspect rating과 aspect weight을 추론한다. 이렇게 제안된 모델의 성능을 평가하기 위해 논문에서는 TripAdviser의 호텔 데이터를 이용했다.

2. Problem Definition

먼저 논문에서 사용된 용어의 정의이다. $D= { d_1, d_2,..., d_{|D|}}$ 를 리뷰 문서들의 집합이라고 하고, 각각의 리뷰 $d \in D$에 대하여 overall rating을 $r_d$라고 한다. 그리고 $n$개의 단어들의 집합 $V={w_1, w_2, ...,w_n}$이 있다고 가정한다.

Overall Rating

리뷰 $d$ 의 overall rating $r_d$는 $r_{min}$과 $r_{max}$ 사이의 값으로, 리뷰 $d$의 내용을 종합적으로 대변하는 하나의 수이다.

Aspect

Aspect $A_i$는 리뷰에서 동일한 평가 요소 속성을 가지는 단어들의 집합이다. 예를 들어, 호텔 리뷰에서 '가격', '가치', '값'과 같은 단어들은 공통적으로 호텔의 '가격'에 대한 특성을 나타내므로 하나의 aspect에 포함된다. 좀 더 수학적으로 표현하면 한 단어를 aspect에 mapping 시키는 함수를 $A(\cdot)$이라고 할 때, $A(i)={ w\mid w \in V, A(w) = i }$ 으로 나타낼 수 있다. 본 논문에서는 리뷰마다 $k$개의 aspect가 있다고 가정하였다.

Aspect Ratings

Aspect Rating $s_d$는 $k$개의 aspect에 대한 만족도를 요소로 가지는 $k$차원 벡터이다. 즉, $i$번째 요소 $s_{di}$는 리뷰 $d$를 작성한 고객이 $A_i$에 대해 얼마나 만족했는지를 표현하는 수이다. $s_{di} \in [r_{min},r_{max}]$의 값을 가지며, 수가 클수록 더 높은 만족도를 나타낸다.

Aspect Weights

Aspect Weight $\alpha_d$는 $k$개의 aspect에 대해 리뷰 $d$에서 여기는 중요도를 요소로 가지는 $k$차원 벡터이다. $i$번째 요소 $\alpha_{di}$는 $[0,1]$ 범위의 값을 가지며, $\sum_{i=1}^{k}{\alpha_{di}}=1$을 만족한다. aspect weight 값이 크다는 것은 리뷰를 작성한 고객이 해당 aspect에 더 큰 중요도를 부여한다는 뜻이다.

Latent Aspect Rating Analysis(LARA)

리뷰 집합 $D$와 주제 $T$가 주어졌을 때, LARA는 각각의 리뷰가 $k$개의 aspect에 대해 평가하는 점수 $s_{di}$와 상대적 중요도 $\alpha_{di}$를 찾는 연구이다.

3. Methods

3.1 Aspect Segmentation

aspect segmentation의 목적은 리뷰 내의 문장들이 어떤 aspect와 관련이 있는지를 mapping해주는 것이다. 본 논문에서는 사전에 7개의 aspect를 지정하고 각 aspect에 속하는 seed word들을 정해주었다.

aspect segmentation은 문장 단위로 이루어지기 때문에, 리뷰의 모든 문장들을 하나씩 split 시키는 전처리 과정이 선행되어야 한다. 그 후 아래 iterative algorithm을 통과시킨다.

알고리즘의 내용을 살펴보면, 먼저 리뷰 텍스트의 각 문장을 문장 내에서 가장 많은 단어들이 속한 aspect에 할당한다. 그리고 모든 aspect와 단어 사이의 dependency를 계산하기 위해 카이제곱 분포를 이용한 아래의 식을 이용한다. 식에서 $w$는 단어, $A_i$는 aspect를 나타낸다.

$$ \chi^2 (w,A_i)= {{C \times (C_1 C_4 -C_2 C_3)^2}\over{(C_1+ C_3)\times(C_2+C_4)\times(C_1+C_2)\times(C_3+C_4)}} $$

• $C_1$: aspect $A_i$에 속하는 문장들에서 등장하는 $w$의 수
• $C_2$: aspect $A_i$에 속하지 않는 문장들에서 등장하는 $w$의 수
• $C_3$: aspect $A_i$에 속하는 문장들 중 $w$가 포함되지 않은 문장의 수
• $C_4$: aspect $A_i$에 속하지도 않고, $w$도 포함하고 있지 않은 문장의 수
• $C$: 단어의 전체 등장 횟수

dependency를 계산한 후에는 aspect별로 가장 dependency가 높은 $p$개의 단어들을 골라 aspect keyword list를 만든다. 이때 $p$를 selection threshold라고 부른다.

이 과정을 keyword list가 더이상 변하지 않거나 iteration이 총 $i$회 돌 때까지 반복하면 aspect segmentation이 완료된다. aspect segmentation이 끝나면 리뷰 텍스트의 각 문장은 가장 관련성이 높은 aspect에 할당된 상태가 된다.

마지막으로 $k \times n$ 크기의 feature matrix $W_d$를 만드는데, 여기서 $d$는 리뷰 번호, $k$는 전체 aspect의 수, $n$은 전체 단어의 개수를 나타낸다. $W_d$의 각 원소 $W_{dij}$는 특정 aspect $A_i$에서 단어 $w_j$가 나오는 빈도를 전체 단어의 수에 대해 정규화한 값이다.

3.2 Latent Rating Regression Model(LRR)

LRR 모델은 앞서 aspect segmentation을 통해 만들어진 feature matrix $W_d$를 독립변수, overall rating $r_d$를 종속변수로 하는 회귀 모델이다.

먼저 aspect rating $s_{di}$를 계산하기 위해, 단어의 빈도를 나타내는 $W_d$에 단어의 sentiment polarity를 나타내는 벡터 $\beta_i$를 곱한다.

$$ s_{di} = \sum_{j=1}^{n} {\beta_{ij}W_{dij}} $$

한 가지 알아두어야 할 점은 각 aspect $A_i$에 대응되는 $\beta_i$가 각각 따로 존재한다는 것이다. 즉, 같은 단어라도 어떤 aspect 관점에서 보는지에 따라 sentiment polarity 값이 다를 수 있다. 예를 들어 'luxury'라는 단어는 'room' 측면에서는 긍정적일 수 있지만, 'price' 측면에서는 부정적이다.

이렇게 얻어진 $s_{di}$들의 가중치 합( $\alpha_d^T s_d = \sum_{i=1}^{k}{\alpha_{di}s_{di}}$ )으로 overall rating $r_d$를 나타낼 수 있는데, 이때의 계수인 $\alpha_{di}$는 aspect의 중요도를 나타내는 aspect weight가 된다. 이 aspect weight 값이 크다는 것은 해당 aspect가 overall rating에 중요한 영향을 미친다는 것을 의미한다.

overall rating 예측의 불확실성을 고려하여 베이지안 regression을 사용하면, 종속 변수를 하나의 값으로 예측하는 것이 아니라 종속 변수가 따르는 확률 분포를 예측하게 된다. 본 논문에서는 $r_d$가 정규분포를 따른다고 가정했다. 분산에 해당하는 $\delta^2$은 예측의 불확실성을 나타내는 모델 파라미터이다.

$$ r_d \sim N(\sum_{i=1}^{k}{\alpha_{di}} \sum_{j=1}^{n}{\beta_{ij} W_{dij}}, \delta^2 ) $$

또한 사람마다 aspect에 대한 중요도가 다를 것이고, aspect끼리의 독립성이 보장되지 않기 때문에 $\alpha_d$가 평균 $\mu$, 공분산 $\sum$의 다변량 정규분포를 따르는 확률변수라고 가정하였다. 이 분포는 베이지안 통계의 사전확률분포가 된다. $\mu$와 $\sum$ 또한 모델의 파라미터인데, 뒤에서 정의할 likelihood를 최대화하는 방향으로 값이 조정된다. $$ \alpha_d \sim N(\mu, \sum ) $$

지금까지의 내용을 정리하면 아래 그림과 같다.

overall rating $r$과 feature matrix element $w$는 input으로부터 얻어지는 값이고, $\theta=(\mu,\sum,\delta^2,\beta)$는 모델의 파라미터이다. $w$와 word sentiment polarity $\beta$를 곱하여 aspect rating $s$를 구하고 $s$와 $r$을 이용해 베이지안 regression 문제를 푼다. 이때 계수가 되는 aspect weight $\alpha$는 사전확률분포 $N(\mu, \sum)$를 따른다고 가정하였고, 예측에 대한 불확실성을 $\delta^2$으로 표현하였다.

다음으로 베이지안 regression 문제를 풀기 위해 MAP estimation method가 사용되었다. MAP estimation method는 주어진 관측 결과와 사전확률분포를 결합해서 최적의 모수를 찾아내는 방법이다. 최대화하고자 하는 목적함수는 아래와 같다.

목적함수는 $\alpha_d$에 대한 사전 확률과, 파라미터들이 주어졌을 때 관측한 $r_d$ 값이 나타날 likelihood의 곱으로 이루어져 있다. 식을 $\alpha_d$에 대해 정리한 후 미분하여 최적화 문제를 풀면 $\alpha_d$의 값을 구할 수 있다. $\alpha_d$는 aspect weight의 정의에 맞게 0 이상 1 이하의 값을 가지며 총합이 1이 된다.

3.3 LRR Model Estimation

3.2에서는 모델 파라미터 집합이 주어졌을 때 aspect weight $\alpha_d$를 구하는 방법에 대해 알아보았다. 사실 파라미터 값은 주어진 것이 아니기 때문에, 본 논문에서는 Maximum likelihood estimation을 사용하여 overall rating $r_d$가 관측될 확률을 최대화하는 LRR 모델의 파라미터 $\theta=(\mu,\sum,\delta^2,\beta)$를 구한다.

log-likelihood 함수는 다음과 같다.

따라서 ML estimate 식은 이 값을 최대화하는 $\theta$를 목표로 한다.

최적의 파라미터 $\theta$를 구하기 위해 $\theta_0$를 랜덤으로 초기화하고, 이후 EM algorithm을 반복한다. E-Step에서는 현재의 파라미터 $\theta$를 바탕으로 aspect rating $s_d$와 aspect weight $\alpha_d$를 구한다. 그리고 M-Step에서는 계산된 $s_d$와 $\alpha_d$, 관측된 $r_d$의 likelihood를 증가시키는 방향으로 $\theta$가 업데이트된다. 이 과정을 likelihood 값이 수렴할 때까지 반복하면 최적의 $\theta$ 값을 찾을 수 있다.

4. Experiment Results

4.1 Data Set and Preprocessing

제안된 모델의 성능을 검증하기 위해 TripAdvisor의 235,793개의 호텔 리뷰 데이터를 이용했다. TripAdvisor의 리뷰 데이터는 value, room, location, cleanliness, check in/front desk, service, business service의 총 7개 aspect에 대한 rating이 매겨져있기 때문에, overall rating과 리뷰 내용만을 가지고 LRR 모델을 훈련시킨 후 도출된 aspect rating을 실제값과 비교할 수 있다는 장점이 있다.

실험에 앞서 아래 그림과 같이 aspect 7개와 그에 해당되는 seed word를 사전에 정의해두었다.

논문에서는 selection threshold 값을 $p=5$로 설정했고, iteration step limit을 $I=10$으로 두었다.

4.2 Qualitive evaluation

Aspect-level Hotel Analysis

아래 표는 LRR 모델을 이용해 value, room, location, cleanliness 4개 aspect에 대한 aspect rating 값을 예측한 결과이다. 괄호 안의 값은 실제 고객이 매긴 aspect rating의 평균이다.

위 표에 있는 3개 호텔은 overall rating 값이 동일한 호텔들이다. 결과를 살펴보면 각 aspect에 대한 rating의 경향성이 실제값과 비슷하다는 것을 알 수 있다. 물론 LRR 모델이 aspect rating 값을 하나하나 정확하게 맞춘 것은 아니지만, overall rating과 리뷰 내용만으로 aspect rating을 예측하는 것이 가능함을 보여준다.

Reviewer-level Hotel Analysis

다음은 같은 호텔에 대해 서로 다른 고객의 aspect rating을 예측한 표이다. 괄호 안의 값은 실제 고객이 매긴 aspect rating이다.

표를 살펴보면, MR.Saturday는 cleanliness에 대해 높은 점수를 줄 것이라고 예측했고, 실제로도 가장 높은 5점을 주었다. 또 Salsrug는 value와 location에 대해 높은 점수를 줄 것으로 예측했고, 실제로도 비슷한 양상을 띠었다. 이처럼 리뷰 내용을 토대로 개인별 aspect rating이 어떻게 될 것인지를 예측하는 것도 가능하다.

Corpus Specific Word Sentimental Orientation

다음은 sentiment polarity $\beta$의 최종값을 바탕으로, value, rooms, location, cleanliness 4개 aspect에 대해 긍정적인 의미가 내포된 단어 5개와 부정적인 의미가 내포된 단어 5개를 정리한 표이다.

예를 들어, 'clean'이라는 단어는 청결 상태가 좋았음을 가장 잘 나타내는 단어이고, 'smelly'라는 단어는 반대로 청결 상태가 나빴음을 가장 잘 나타내는 단어라는 것을 알 수 있다. LRR 모델은 텍스트 데이터로 weight 값을 산출했기 때문에 domain specific한 sentiment polarity를 얻어낼 수 있다는 장점이 있다.

4.3 Applications

논문에서 제안된 LRR 모델을 적용할 수 있는 사례 3가지를 간략히 소개한다.

Aspect-Based Summarization

긴 리뷰 텍스트를 요약해서 간결한 aspect-based summary를 만들 수 있다. 수많은 리뷰를 직접 일일이 읽어보지 않고도 호텔의 장점과 단점을 요약하여 나타내준다.

User Rating Behavior Analysis

고객이 중요시하는 aspect가 무엇인지, 평가를 내리는 데에 가장 큰 영향을 미친 요소가 무엇인지 분석이 가능하다.

Personalized ranking

고객이 중요시하는 aspect를 기반으로 개인화된 호텔 ranking을 매길 수 있다. 논문에서는 한 고객과 비슷한 rating behavior를 가진 다른 고객들의 리뷰를 기반으로 호텔의 ranking을 매기는 방식을 제안했다.

소감

처음 접한 NLP 관련 논문이었는데, 생소한 텍스트마이닝 용어나 개념들이 나올 때마다 찾아보면서 스스로 공부하는 기회가 되었다. 호텔 리뷰 데이터로 aspect rating과 aspect weight을 도출해내는 내용 자체가 흥미로웠고, 논문에 수식이 많은 편은 아니라서 그나마 이해가 잘 됐던 것 같다. 프로젝트를 진행하려면 이 내용을 코드로 구현해야하는데, 어렵겠지만 한 번 도전해봐야겠다😄