Item2Vec: Neural Item Embedding for Collaborative Filtering

Abstract

• 많은 CF (Collaborative Filtering) 알고리즘은 item의 유사성을 생성하기 위해 item-item
  관계를 분석한다는 점에서 item-based임

• SGNS를 이용하여 잠재 공간에있는 항목에 대한 임베딩을 생성하는 item-based CF에 대해 Item2Vec이라는 이름을 지정

• 이 방법은 사용자 정보를 사용할 수없는 경우에도 item to item 관계를 추론 할 수 있음

• SVD와 경쟁하는 것을 보여주는 대규모 데이터 세트 실험 결과 제시를 통해 Item2Vec 방법의 효과를 입증

1. Introduction

• item 유사성을 계산하는 것은 최신 추천 시스템의 핵심 구성 요소

• 많은 추천 알고리즘이 사용자와 item을 저 차원 임베딩으로 학습하는 데 초점을 맞추고
  있지만 item 유사성을 계산하는 것은 그 자체로 하나의 목적임

• item 유사성은 온라인 소매 업체에서 다양한 추천 작업을 위해 광범위하게 사용함

• 이 논문은 사용자에 관계없이 저 차원 공간에 item을 임베딩하여 item 유사성을 학습하는
  작업을 다룸

• item-based 유사성은 온라인 소매 업체에서 단일 항목을 기반으로 한 추천을 위해
  사용
  예를 들어 Windows 10 App Store에서 각 앱 또는 게임의 세부 정보 페이지에는 "People also like"라는 다른 유사한 앱 목록이 포함되어 있다.

• 이 목록은 그림 1과 같이 원래 앱과 유사한항목의 전체 페이지 추천 목록으로 확장 할 수 있음
  단일 항목과의유사점만을 기반으로하는 유사한 추천 목록이 대부분의 온라인 상점에 존재한다.

• 단일 아이템 추천은 "전통적인 (Traditional)" 유저-아이템 추천과는 다름
  전통적인 추천은 보통 특정 아이템에 대한 명시적인 유저 관심 맥락과 명시적 유저 구매 의도로 나타나기 때문이다.

• 따라서, 아이템 유사도 기반 단일 아이템 추천은 종종 유저-아이템 추천보다 더 높은 클릭 비율 (CTR, Click-Through Rates)을 가지며, 결과적으로 판매량이나 수익의 더 큰 몫을 책임짐

• 아이템 유사도 기반 단일 아이템 추천은 다양한 추천 작업에서 사용됨:

  • "Candy Rank" : 유사한 아이템 (보통 더 낮은 가격)추천은 결제 직전 체크아웃 페이지에서 제시됨

  • "Bundle" : 일부 아이템 집합이 그룹화 되어 함께 추천됨

• 아이템 유사도는 온라인 스토어에서 더 좋은 탐색과 발견을 위해 사용되며, 전반적인 사용자 경험을 향상시킴

• 유저에 대한 Slack변수들을 정의하여 암묵적으로 아이템들 사이의 연결성을 학습하는 유저-아이템 CF 방법은 아이템 관계를 직접 학습하기 위해 최적화하는 방법보다 더 좋은 아이템 표현을 생성할 수 있음

• 아이템 유사도는 아이템-아이템 관계에서 표현을 직접 학습하는 것을 목표로 두는 아이템 기반 CF 알고리즘의 핵심임

• 아이템 기반 CF 방법이 요구되는 몇 가지 시나리오:

  • 대규모 데이터셋에서, 아이템 수보다 유저 수가 훨씬 더 많을 때, 아이템만 단독으로 모델링하는 방법의 계산 복잡도는 유저와 아이템을 동시에 모델링하는 방법보다 훨씬 더 낮음

    • Ex) 온라인 뮤직 서비스들은 수만 명의 아티스트 (아이템)가 있고, 등록된 유저는 수억 명

  • 특정한 시나리오에서는, 유저-아이템 관계를 사용할 수 없는 경우도 있음.

    • Ex) 오늘날 온라인 쇼핑의 대부분이 명시적인 유저 식별 과정 없이 이루어지며 각 세션 정보를 대신 사용 가능, 이러한 세션을 "유저"로 다루는 것은 덜 유용할 뿐만 아니라 엄청나게 많은 비용이 듬.

• Word2Vec으로 알려진, Negative Sampling을 이용한 Skip-gram (SGNS) 방법은 NLP를 넘어 다른 도메인으로도 확장되고 있음

• 이 논문에서, 아이템 기반 CF에 SGNS 적용을 제시

• 다른 도메인에서의 성공으로 인해 동기 부여받았으며, 조금 수정한 SGNS가 CF 데이터셋에서 서로 다른 아이템 사이의 관계를 포착할 수도 있다는 것을 제안함

• Item2Vec, SVD를 사용한 아이템 기반 CF 비교를 통해 경쟁력 있는 유사도 측정을 유도할 수 있다는 것을 보여줌

  • 최고의 결과를 달성했다고 주장하는 것이 아닌, 단지 아이템 기반 CF에 대한 SGNS의 또 다른 성공적인 어플리케이션을 보여주기 위한 것

  • 따라서, SVD 기반 모델을 Item2Vec 방법과 비교하고, 다른 더 복잡한 방법과의 비교는 추후의 연구로 남겨둠

2. Skip-Gram with Negative Sampling (SGNS) - Related work

• SGNS은 Mikolove el al이 소개했던 뉴럴 단어 임베딩 방법

• 문장에서 한 단어와 그 단어 주위의 단어들 사이의 관계를 포착하는 단어 표현을 찾는 것을 목표로 함

• 유한한 어휘집합에서 단어 시퀀스가 주어졌을 때, Skip-gram의 목적은 수식 (1) 을 최대화하는 것:
  

• c는 문맥의 윈도우 크기 (wi에 의존함)

• p(wj|wi) 는 소프트맥스 함수:
  

• ui∈U (⊂R^m) 그리고 vi∈V (⊂R^m) 은 각각 단어 wi∈W에서 타겟과 문맥 표현에 해당되는 잠재 벡터

• IW ≜{1, ... , |W|}과 파라미터 m은 데이터셋 크기에 따라 경험적으로 선택됨

• 수식 (2)를 사용하는 것은 ▽p(wj|wi)의 계산 복잡도 때문에 비실용적이며, ▽p(wj|wi)는 보통 10^5 ~ 10^6크기를 가진 어휘 집합 |W|의 선형 함수임

• Negative Sampling은 아래와 같이 수식 (2)의 소프트맥스 함수를 대체함으로써 계산적 문제를 완화
  

• σ(x) = 1 / 1 + exp(−x)

• N은 Positive Sample 별로 뽑히는 Negative Examples의 수를 결정하는 파라미터

• Negative 단어 wi는 3 / 4 제곱된 유니그램 분포에서 샘플링됨

• 이 분포는 경험적으로 유니그램 분포가 상당히 우수함

• 희소 단어들과 빈번한 단어들 사이의 불균형을 극복하기 위해서, 다음과 같이 Subsampling 절차가 제시됨:

  • 입력 단어 시퀀스가 주어질 때, 우리는 확률 p(discard|w) = 1 - √ρ/f(w)와 함께 각 단어 w를 버림

  • f(w)는 단어 w의 빈발도

  • ρ는 규정된 임계값 (Threshold)

• 이 절차는 학습 과정을 가속화하고 희소 단어 표현을 상당히 향상시킴

• 결국, U와 V는 수식 1의 목적함수에 확률적 (Stochastic) 최적화를 적용하여 추정됨

3. Item2Vec - SGNS for item-based CF

• CF 데이터의 맥락에서, 아이템들은 유저가 생성한 집합 (as User generated sets)으로 주어짐

• 유저와 아이템 집합 사이의 관계에 대한 정보는 항상 사용 가능한 것은 아니라는 것을 유의
  예를 들어, 우리에게 주문을 한 사람에 대한 정보가 아무것도 없는 주문에서 생성된 데이터셋이 제공될 수 있다.

• 다수의 아이템 집합이 동일한 유저에 속할 수 있는 시나리오가 있지만, 이 정보는 제공되지 않음

아이템 기반 CF에 SGNS 적용

• CF 데이터에 SGNS를 적용하는 것은 일단 단어 시퀀스가 아이템 집합 (a set or basket of items) 과 동일하다고 간주, 지금부터 용어 "word" 와 "item"을 서로 바꿔서 사용

• 시퀀스에서 집합으로 옮김으로써, 공간적 / 시간적 정보 사라짐

• 이 논문에서, 유저가 생성한 순서 / 시간에 관계없이 동일한 집합을 공유하는 아이템이 유사하다고 생각되는 정적인 환경을 가정하므로 이 정보를 버리기로 선택함
  이 가정은 다른 시나리오에서는 유효하지 않을 수 있다.

• 공간 정보를 무시하기 때문에 동일한 세트를 공유하는 각 항목 쌍을 Positive sample로
  취급, 이는 집합 크기에서 결정되는 window 크기를 암시

• 구체적으로, 아이템 집합이 주어질 때, 수식 (1)의 목적함수는 다음과 같이 수정됨:
  

• 또 다른 옵션은 수식 (1)의 목적함수를 그대로 유지하고 실행시간동안 각 아이템 집합을 섞는 것

• 실험에서, 두 옵션 모두 동일한 성능을 발휘하며 과정의 나머지 부분은 Section 2에서 설명한 알고리즘과 동일

• 이 작업에서, 우리는 i번째 아이템의 최종 표현으로 ui를 사용했으며, 아이템 쌍 사이의 관련성은 코사인 유사도에 의해 계산됨

• 다른 옵션들은 vi, 추가적인 구성은 ui+vi, 또는 결합 [ui^T,vi^T]^T를 사용하는 것임
  

• 마지막 두 개의 옵션은 가끔 우수한 표현을 생성함

4. Experimental Results

• 이 Section에서, 우리는 Item2Vec 방법의 실증적인 추정을 제공

• 우리는 아이템에 대한 메타데이터가 존재하는지 여부에 따라 정성적, 정량적 결과를 모두 제공

• 아이템 기반 CF 알고리즘의 Baseline으로 아이템-아이템 SVD를 사용

4.1 Datasets

• 두 가지 서로 다른 유형의 데이터셋에 대한 방법을 비공개로 평가

첫 번째 데이터셋

• Microsoft XBOX Music service에서 검색된 유저-아티스트 데이터

• 이 데이터셋은 9M 이벤트로 구성되며, 각 이벤트는 유저-아티스트 관계로 구성되고, 이는 유저가 구체적인 아티스트의 노래를 재생했다는 것을 의미

• 데이터셋은 732K 유저와 49K의 다른 아티스트를 포함

두 번째 데이터셋

• Microsoft Store의 물리적인 상품 주문들을 포함

• 하나의 주문은 그 주문을 한 유저에 대한 어떠한 정보도 없이 아이템 바구니 (Basket) 에 의해 주어짐

• 따라서, 이 데이터셋 정보는 우리가 유저와 아이템 사이를 결합할 수 없다는 점 때문에 더 부족함

• 이 데이터셋은 379K 주문 (단일 아이템 이상을 포함하는) 과 1706의 다른 아이템들로 구성

4.2 Systems and parameters

System - Item2Vec

• 두 데이터셋에 Item2Vec을 적용

• 최적화는 SGD (Stochastic Gradient Descent) 사용

• 20 Epochs로 알고리즘 실행

• 두 데이터셋에 N = 15 로 Negative Sampling 수치를 설정

• 차원 파라미터 m은 각각 Music은 100, Store는 40으로 설정

• 추가로 Subsampling 값인 ρ는 각 데이터셋마다 Music -> 10^−5, Store -> 10^−3으로 적용

• 서로 다른 파라미터 값으로 설정한 이유는 데이터셋 크기가 다르기 때문

System - SVD

• SVD 기반 아이템-아이템 유사도 시스템과 Item2Vec 방법을 비교

• 비교를 위해 SVD를 아이템 수 크기의 사각 행렬에 적용, 여기서 (i,j) 엔트리는 (wi,wj)는 데이터셋에서 Positive 쌍으로 나타난 횟수를 포함

• 그런 다음, 각 엔트리를 행과 열 합계의 내적 제곱근 (Square Root of the Product)에 따라 정규화

• 잠재 표현은 US^1/2의 행으로 주어짐

  • S는 대각선이 Top m특이값을 포함하는 대각 행렬 (S is a diagonal matrix that its diagonal contains the top m singular values)
  • U는 해당하는 왼쪽 특이값을 열로 포함하는 행렬 (U is a matrix that contains the corresponding left singular vectors as columns)

• 아이템 간 관련성 (Affinity)은 아이템 표현들의 코사인 유사도로 계산

4.3 Experiments and results

• Music 데이터셋은 장르 메타데이터 제공하지 않으므로 각 아티스트에 대해 웹에서 장르 메타 데이터를 검색하여 장르-아티스트 카탈로그를 구성

• 학습 된 표현과 장르 사이의 관계를 시각화 하기 위해 이 카탈로그 사용

• 이는 학습된 표현이 그러한 장르에 따라 아티스트를 군집화시킬 것이라는 가정

• 따라서, 다음과 같이 구별되는 장르들에 대해 장르별 Top 100의 인기있는 아티스트를 포함하는 하위집합을 생성

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

• 아이템 벡터의 차원을 2로 감소시키기 위해 코사인 커널을 이용한 t-SNE를 적용

• 각 아티스트를 장르에 따라 색깔 점으로 매칭

• Figures 2 (a)와 2 (b)는 각각 Item2Vec과 SVD에 대해 t-SNE에 의해 만들어진 2차원 임베딩을 표현

• 위와 같이 Item2Vec이 더 좋은 클러스터링을 제공

• Fig 2 (a)에서 비교적 동질적인 영역들의 일부가 색상이 다른 아이템으로 오염되었음을 추가로 관찰함

• 이러한 사례들 중 많은 것들이 웹에서 잘못 표기되거나 혼합된 장르를 가진 아티스트에서 비롯된다는 것을 알아냄

• 아래의 Table 1은 주어진 아티스트와 관련된 장르(웹에서 검색한 메타데이터에 따라) 가 부정확하거나 최소한 Wikipedia에 모순되는 몇 가지 예시를 보여줌

• 따라서, Item2Vec 같은 모델 기반 사용이 잘못 표기된 데이터 발견에 유용할 수 있으며, 간단한 KNN(k nearest neighbor) 분류기를 사용하여 정확한 레이블에 대한 제안까지 제공한다고 결론지음

• 유사도 품질을 정량화 하기 위해 아이템과 아이템의 가장 가까운 아이템 사이의 장르 일관성을 테스트

• Top q(다양한 q값에 대해)개의 인기있는 아이템들에 대해 반복하여 수행, 이들의 장르가 이들 주위의 가장 가까운 k개의 아이템 장르와 일치하는지 체크

• 단순하게 다수결(Majority Voting)로 수행

• 서로 다른 이웃 크기 (k = 6, 8, 10, 12, 16)로 동일한 실험을 진행, 상당한 결과 변화는 관찰되지 않음

• Table 2는 k = 8 일 때 관찰된 결과를 제시

• 꾸준하게 Item2Vec이 SVD 모델 보다 더 좋다는 것을 관찰, 이 두 모델 사이의 차이는 q가 증가할때 마다 점점 커짐

• 이는 덜 유명한 아이템들에 대해, Item2Vec이 SVD 보다 더 좋은 표현을 생성한다는 것을 암시 이는 Item2Vec이 유명한 아이템을 Subsample하고 그러한 아이템들의 인기에 따라 Negative Example을 Sampling하기 때문이다.

• 추가로 10K의 비인기 아이템 하위집합 (Table 2의 마지막 행)에 동일한 "장르 일관성" 테스트를 적용하여 이 가설을 검증

• 어떤 아이템에 해당하는 아티스트를 재생한 유저가 15명 미만일 경우, 비인기 아이템으로 정의

• 정확도는 Item2Vec이 68%, SVD가 58.4%

• Item2Vec과 SVD 사이의 질적 비교는 각각 Music과 Store 데이터셋에 대해 Table 3 ~ 4 에 보여짐

• Table들은 Seed 아이템들과 이와 가장 가까운 5개 아이템을 보여줌

• 장르보다 더 높은 품질의 아이템 유사도를 검사할 수 있다는 것이 이 비교의 주된 이점

• Store 데이터셋은 유용한 태그 / 레이블이 없기 때문에 질적인 평가가 불가피

• 이 두 데이터셋들에 대해 Item2Vec이 SVD보다 Seed 아이템과 더 관련 있는 리스트를 제공

• Store 데이터셋이 더 부족한 정보를 포함함에도, Item2Vec이 꽤 아이템 관계를 잘 추론하고 있는 것을 알 수 있음

5. Conclusion

• 이 논문에서, 아이템 기반 CF에 대한 뉴럴 임베딩 알고리즘인 Item2Vec을 제시

• Item2Vec은 약간의 수정을 거친 SGNS 기반 모델

• SVD 기반 아이템 유사도 모델과 비교했을 때, Item2Vec의 효과를 증명하는 질적, 양적인 추정 을 모두 보여줌

• Item2Vec이 SVD 베이스라인 모델보다 더 좋은 아이템 표현을 생성한다는 것을 관찰, 또한 이 둘 사이의 격차는 비인기 아이템에서 좀 더 커짐

• Item2Vec이 인기 아이템의 Subsampling과 함께 Negative Sampling을 사용한다는 사실로 이것을 설명

Reference

• https://arxiv.org/abs/1603.04259

• https://soobarkbar.tistory.com/129