[논문] Item2Vec: Neural Item Embedding for Collaborative Filtering(2016)

Abstract

 

---

• 대부분의 CF 알고리즘들은 아이템과 아이템간의 관계를 분석해 아이템 similarity를 생산해내는 아이템 기반 기법 

  • Collaborative Filtering(CF): 많은 사용자로부터 얻은 기호 정보에 따라 user들의 관심사를 자동으로 예측하게 해주는 기법

• Skip-gram with Negative Sampling(SGNS), 흔히 word2vec이라고 불리는 기법이 등장하면서 NLP 분야에서 sota 결과를 얻고 있음

• item 기반 CF에 워드 임베딩 프레임워크(SGNS)를 도입

• 각 아이템 별 임베딩을 생성해내는 iiten-based CF 기법인 item2vec에 대해 소개

• 유저 정보를 사용할 수 없는 상황에서도 아이템과 아이템 간 관계 추론이 가능

 

1. Introduction and Related Work

---

• 최근의 recommender system에서 아이템 간 유사도를 계산하는 것이 핵심

• 많은 추천 알고리즘들이 유저와 아이템간의 임베딩을 러닝하고, 그것을 이용해 아이템 유사도를 구 함

• 온라인 소매업에서는 이렇게 구한 유사도를 이용해 단일 아이템에 대한 추천을 하는데 이용한다.

• Window 10 App Store에서 각 어플이나 게임 설명 페이지에 다른 비슷한 어플리케이션들이 추천되는 것

• 이런 single 아이템에 대한 추천은 그동안의 유저와 아이템 간 추천 시스템과는 다름

  • 특정 iten에 대한 유저의 관심과 구매하려는 의도 속에서 추천하는 것이기 때문

  • 그래서 종종 단일 아이템에 대한 추천이 유저-아이템 기반 추천보다 더 높은 Click-Through Rates(CTR)를 보이기도 하며 더 높은 수익 창출로 이어지기도 한다.

• 따라서 아이템과 유저간의 커넥션을 통해 아이템 관계를 바로 학습하는 user-item CF보다 단일 아이템 추천이 더 더 나은 아이템 representation을 생산해 낸다.

• 아이템 기반 CF을 필요로 하는 상황도 존재한다.

  • 아이템의 갯수보다 유저의 수가 훨씬 많은 대용량의 데이터셋의 경우, 유저와 아이템 간 관계를 동시에 구하게 되면 계산복잡도가 엄청나게 증가하게 된다.

  • eg) 음악 사이트의 경우, 유저는 수백만명인데 비해 아티스트(아이템)은 몇천명 정도에 불과

• 또 해당 유저에 대한 정보가 없는 경우에는 user-item relation을 적용할 수 없다.

• 최근 NLP 분야에서 linguistic task를 처리하기 위한 뉴럴 임베딩 기법이 엄청나게 발전하면서 sota 성능을 내고 있다.

• 특히, SGNS, 또는 word2vec이 최고의 결과를 내고 있으며, NLP의 다양한 기법에 적용되고 있다.

• 본 논문은 item-based CF에 SGNS를 적용하는 새로운 기법인 item2vec을 고안한다. 

 

 

2. Skip-Gram with Negative Sampling

---

skip-gram 구조( https://arxiv.org/pdf/1301.3781.pdf  Mikolov et al.)

• Skip-gram with negative sampling(SGNS): Milolov et. al에 의해 고안된 neural word embedding 기법

• 문장 안에서 한 단어에 대해 그 단어 주변의 단어를 찾을 수 있는 단어 분산 표현을 만들어 내는 것을 목표로 하는 기법이다. 

  • c: context 윈도우 사이즈($w_i$ 크기에 따라 결정)

  • $p(w_{j}|w_{i})$: softmax 함수 $$p(w_{j}|w_{i}) = {\frac{exp({u^{T}_i}{v_{j}})}{{\sum\limits_{{k}\in{I_{W}}}}exp({u^{T}_i}{v_k})}}$$

  • $u_{i}\in{U(\subset{\mathbb{R}^m})}$, $v_{i}\in{V(\subset{\mathbb{R}^m})}$은 각각 단어 $w_{i} \in {W}$에 대한 타깃/문맥 분산 표현의 latent vector

  • 단어 집합 $W = \{w_i\}^{K}_{i=1}$에 속하는 단어 시퀀스 $(w_i)^{K}_{i=1}$가 주어졌을 때, Skip-gram은 다음 식을 최대화 하는 것을 목표로 한다: $${\frac{1}{K}} {\sum_{i=1}^K} {\sum_{{-c}\le{j}\le{c},\;{j}\neq{0}}} {\log p(w_{i+j}|w_i)}$$

• $I_{W}\overset{\Delta}{=}\{1,\cdots{|W|}\}$ ($I_W$는 1부터 $|W|$ 중 하나로 defined)

• m: 데이터셋 사이즈에 따라 정해짐

• 하지만 보통 단어 집합 갯수가 $10^5 ~ 10^6$이므로 softmax 함수를 계산하는데 너무 많은 계산량이 든다.

  • 네거티브 샘플링 이용 $$p(w_{j}|w_{i}) = \sigma{(u^{T}_{i}v_j)} \prod_{k=1}^{N} \sigma{(-u^{T}_{i}v_k)}$$

  • $\sigma({x})= 1/1+exp(-x)$

  • N: positive example마다 샘플링할 negative example 갯수

  • negative word $w_i$: unigram distribution에 3/4 제곱한 값에서 샘플링

• 자주 나오는 단어와 희귀하게 나오는 단어 사이의 차이를 극복하기 위해 다음과 같은 방법 사용:

  • 단어 시퀀스가 주어졌을 때, 각 단어 w를 $p(discard|w) = 1 - \sqrt{\frac{\rho}{f(w)}}$

    • $f(W)$: 단어 w의 frequency, $\rho$: threshold

  • 러닝 속도를 올리고 희소한 단어에 대한 분산표현을 개선

  • Mikolov T, Sutskever I, Chen K, Corrado GS, Dean J. Distributed representations of words and phrases and their compositionality. In Proceedings of NIPS 2013 (pp. 3111- 3119).

• $U$, $V$: Skip-gram 식에 stochastic gradient ascent를 적용해 계산

 

 

3. Item2vec - SGNS for item similarity

---

• CF에서 다루는 데이터와 같이, 아이템들은 user-generated set로 주어진다.

• 이때 유저와 아이템셋에 대한 정보가 없을 수도 있다

  • eg) 여러개의 아이템셋이 같은 유저에 속할 수도 있지만, 이 정보는 제공되지 않음

• 이 논문에서는 아이템 기반 CF에 SGNS를 적용한 기법을 제안하고 있다.

  • 단어 시퀀스가 아이템 집합 또는 basket과 동일한 맥락이라는 관점에서 SGNS를 CF 데이터에 응용하는 것은 직관적!

  • 따라서 "word"와 "item"을 지금부터는 동일한 맥락에서 사용함

  • (단어) 시퀀스에서 (아이템) 집합을 다루면서 시간/공간의 정보를 없애기로 함.

  • 이 논문은 어떤 순서로, 언제 생성되었는지에 상관 없이 같은 아이템을 공유하는 아이템 집합은 similar하게 처리하는 static 환경을 가정

    • 다른 시나리오에서는 지속되지 않을 수도 있지만 일단 이 논문 안에서는 그런 시나리오들은 다루지 않음

• 공간 정보를 무시하기 때문에 같은 아이템 집합을 공유하는 아이템 쌍은 positive example으로 처리

  • 따라서 window size는 집합 사이즈에 따라 결정된다.

  • 아이템 집합에 대해 목적 함수는 다음과 같이 수정: $${\frac{1}{K}} {\sum_{i=1}^K} {\sum_{{j}\neq{i}}} {\log p(w_{j}|w_i)}$$

    • 즉 자기 자신($w_i$)을 제외한 다른 아이템들 간의 유사도 계산

  • 기존의 목적 함수를 유지하고 각 아이템 셋을 런타임 중에 랜덤으로 섞는 방법도 있지만, 두 옵션이 같은 결과를 보임

• $u_j$: i번째 아이템의 최종 분산 표현

  • 아이템 쌍 간의 관련성은 코사인 유사도를 이용해 계산

  • 또 다른 옵션으로는 $v_i$를 사용해

    • additive composition: $u_{i} + v_i$
    • concatenation ${[u^{T}_{i}v^{T}_{i}]}^T
    • 어떤 경우에는 이 옵션들이 더 우수한 분산 표현을 만들어 내기도 한다.

 

 

4. Experimental Setup and Results

---

• baseline 아이템 기반 CF 알고리즘으로는 item-item SVD를 사용

 

4.1 Datasets

---

• 두가지의 데이터셋을 이용(데이터셋은 공개하지 않음)
• 첫번째 데이터셋은 Microsoft Xbox Music service의 user-artist 데이터
• 9M개의 이벤트로 구성되어 있으며 각 이벤트는 유저-아티스트 관계(유저가 노래를 들은 특정 아티스트)로 이루어져 있다.
• 723K명의 유저와 49K명의 아티스트로 구성
• 두번째 데이터셋은 Microsoft Store의 제품들에 대한 주문 데이터
• 유저에 대한 다른 정보는 포함되어 있지 않으며 그 유저가 주문한 아이템 리스트로 이뤄짐.
• 따라서 유저와 아이템 간 결속력이 없기 때문에 이 데이터셋 안의 정보는 약하다.
• 397K개의 주문(하나 이상의 아이템 포함), 1706개의 아이템

 

4.2 System and Parameters

---

• 네거티브 샘플링 N=15
• m은 각각 100과 40으로 설정
• subsampling 적용, $\rho$은 각각 $10^{-5}$, $10^{-3}$
• 다른 매개변수 값을 설정한 경우는 데이터셋의 사이즈가 다르기 때문

 

• 비교 baseline으로는 SVD 기반의 아이템-아이템 유사도 시스템 이용
• 아이템 갯수 길이를 가지는 직각 행렬에 SVD를 적용
• ($i,\;j$): ($w_i,\;w_j$)가 함께 주문된 횟수
• 각 entry는 각 행과 열의 합의 내적의 제곱근 값으로 정규화 
• latent representation은 $US^{1/2}$
• $S$: 대각행렬, 각 대각성분은 top m 특잇값으로 이뤄짐
• $U$: 왼쪽 특이 행렬
•  $A = USV^T$일때 U의 열벡터를 왼쪽 특이 행렬, V의 행벡터를 오른쪽 특이 행렬이라고 부른다.
• 아이템간 연관성은 코사인 유사도를 사용해 계산

• 참고: https://datascienceschool.net/view-notebook/30055dc68e8f4db0b7f6e4b56a571d52/

Data Science School

 

 

4.3 Experiments and Results

---

• 음악 데이터셋이 장르 메타데이터를 포함하고 있지 않기 때문에 장르데이터를 인터넷에서 찾아와 장르-아티스트 카탈로그를 만들었다.

• 그런 다음 좋은 분산표현이 아티스트들을 장르에 따라 클러스터링 해줄 것이라는 가정에 따라 이 카탈로그를 이용해 학습한 분산표현과 장르간의 관계를 시각화

• 마지막으로 각 장르마다 top 100명의 아티스트들로 구성된 집합을 만듬

  • R&B/Soul, Kids, Classical, Country, Electronic/Dance, Jazz, Latin, Hip Hop, Reggae/Dancehall, Rock, Word, Christian/Gospel, Blues/Folk

• t-SNE를 이용해 아이템 벡터의 차원을 2로 축소한 뒤 각 아티스트 점들을 장르에 따라 색칠

  • t-SNE: t-분포 확률적 임베딩, 차원축소 알고리즘으로 비슷한 데이터는 근접한 2, 3차원 지점으로, 다른 데이터는 멀리 떨어진 지점으로 맵핑

Fig.2: (a) item2vec을 이용해 만들어진 아이템 벡터 임베딩 (b) SVD / 각 아이템은 웹에서 얻어진 장르 메타데이터를 이용해 장르별로 색칠

 

• Fig 2(a)는 item2vec에 대해, Fig(b)는 SVD에 대해 t-SNE를 이용해 만들어진 2D 임베딩

• 그림에서도 볼 수 있듯이 item2vec이 더 클러스터링을 잘 하고 있다. 

• Fig 2(a)에서 같은 장르로 구성된 영역에 다른 아이템이 위치해 있기도 하지만, 이 경우는 웹에서 장르를 가지고 올 때 잘못 라벨링 된 경우나 두가지 이상의 장르로 구성되어 있는 경우이며 거의 대부분 잘 분류했다.

Tavle 1: 장르가 불일치 하는 경우(웹 카탈로그 / item2vec에 기반한 KNN 예측)

Table 2: Top Popular 아티스트 집합 사이즈에 따른 SVD와 Item2vec의 장르 분류 성능 비교 

 

• Table 1에서는 인터넷에서 가져온 장르 메타데이터가 정확하지 않거나 위키피디아 정보와 불일치하는 몇가지 예시에 대해 볼 수 있다.

  • item2vec이 잘못 라벨링 된 데이터를 인식할 수 있을 뿐만 아니라 KNN 분류기를 이용하면 올바른 라벨을 제안할 수도 있다는 결론을 얻을 수 있다.

  • 유사도의 성능을 수치화하기 위해 각 아이템과 nearest neighbors 사이의 장르 일관성을 테스트했다.

    • top $q$개(다양한 $q$ 값으로 진행)의 popular 아이템에 대해 반복해서 진행하였고, 그 아이템의 장르와 그 아이템과 과 가까운 k개의 nearest 아이템의 장르가 일관성이 있는지를 체크

    • 단순 다수결을 이용

    • 이 실험을 다양한 neighborhood 사이즈($k=6,\;8,\;10,\;12\;and\;16)로 진행했으며, 이 크기에 따른 눈에 띄는 변화는 관측하지 못함.

• Table 2는 $k\;=\;8$일 때 결과를 보여주고 있다.

  • item2vec이 SVD 모델보다 더 좋은 일관성을 보여주고 있으며, $q$ 값이 증가할수록 둘 사이의 차이는 더 커지고 있다.

    • 따라서 item2vec이 SVD보다 덜 popular한 아이템에 대해서도 더 좋은 분산 표현을 만들어 내고 있다.

      • 이는 item2vec이 popular한 아이템은 subsampling하고 popularity에 따라 negative examples도 샘플링하고 있기 때문이다.

Table 3: 음악 데이터셋에서의 Item2Vec과 SVD에 대한 양적 비교

Table 4: 스토어 데이터셋에서의 Item2Vec과 SVD에 대한 양적 비교 

 

• item2vec이 SVD보다 더 좋은 성능을 가진다는 가정을 입증하기 위해 이것을 10K개의 unpopular 아이템에 적용했다

  • unpopular: 재생수가 15회 미만인 아티스트의 경우

  • item2vec은 68%, SVD는 58.4%의 정확도를 보였다.

• Table 3-4는 음악 데이터셋과 스토어 데이터셋에 대한 양적 비교에 대한 표이다.

  • seed 아이템과 가장 가까운 4개의 neighbor를 나타내었다.

  • 장르별로 비교하는 것 보다 훨씬 더 선명하게 아이템간의 유사도를 볼 수 있다는 것이 이 비교의 가장 큰 장점이다.

  • 또 스토어 데이터셋은 tag/label에 대한 정보를 포함하고 있지 않아 질적 비교가 불가능하다.

    • * 논문에는 'a qualitative evaluation is inevitable'이라고 적혀있지만, 그러면 질적 비교가 불가피하다 = 질적 비교를 해야 한다는 말인데, 문맥상 질적 비교가 불가능하다하고 판단해서 적어놓음ㅠㅠ

  • 두가지 데이터셋 모두 item2vec이 SVD보다 seed 아이템과 관련된 아이템 리스트를 더 잘 만들어냈다.

  • 정보가 부족한 스토어 데이터셋에 대해서도 item2vec이 더 아이템 간 관계를 더 잘 추론해냈다.

 

 

5. Conclusion

---

• 본 논문에서는 아이템 기반 CF를 위한 neural embedding algorithm, Item2vec을 제안했다.

  • item2vec은 minor한 수정을 거친 SGNS에 기반한다.

• SVD 기반 아이템 유사도 모델과 비교해 item2vec의 효과를 입증하기 위해 양적/질적 평가를 진행하였으며, item2vec이 베이스라인 모델인 SVD 보다 더 좋은 아이템 분산 표현을 만들어내는 것을 확인하였다.

  • 또 둘 사이의 차이는 unpopular한 아이템일때 더 커졌다.

    • 이것은 item2vec이 negative sampling을 사용하고 있기 때문