[RecSys] 5. Item2Vec and ANN

In [1]:

from IPython.core.display import display, HTML

display(HTML("<style>.container { width:90% !important; }</style>"))

Item2Vec and ANN¶

Item2Vec은 Word2Vec을 추천분야에서 응용한 버전이다.

ANN은 주어진 벡터와 가장 가까이 있는 벡터를 근사적으로 찾는 방법이며, 실제 서빙할때 많이 사용하는 기법이다.

Word2Vec & Item2Vec¶

Item2Vec은 Word2Vec을 추천분야에서 응용한 버전이다.

Word2Vec의 학습방법론 - SGNS¶

Skip-Gram 에 Negative Sampling을 추가한 방법론,

Negative Sampling의 갯수는 모델의 하이퍼 파라미터로, 기존의 Skip-Gram 방식은 다중 분류였지만, SGNS의 방식으로 바뀌면서 이진분류(0과 1) 방식으로 변하였다. 주변에 없는 단어는 0, 있는 단어는 1로 설정하여 학습시킨다.

• 논문에선 학습데이터가 적은 경우 샘플링의 수는 5-20, 충분히 큰 경우는 2-5가 적당

중심 단어와 주변 단어를 내적을 sigmoid로 예측값으로 하여 0과 1을 분류

• Loss 함수는 크로스 엔트로피

• 최종 생성된 워드 임베딩이 목적이며, 선택적으로 하나만 싸용하거나 평균을 사용한다.

Item2Vec¶

word2vec의 단어가 아닌 추천시스템의 Item을 사용하여 임베딩

• 추천시스템에서의 문장은 아이템 리스트, 단어는 아이템 하나하나로 변경하여 쓴다.

  • 유저-아이템 정보 없이 유저 식별 정보 없이 세션 단위로 데이터 생성이 가능하다.

• 유저 혹은 세션 별로 소비한 아이템 집합을 생성

  • 시퀀스가 집합으로 바뀌면서 순서, 공간, 시간 정보가 사라진다. 실제로는 순서의 의미가 다르기 때문에 다 동일한 집합 형태로 변경해준다.
  • 집합 안에 존재하는 아이템은 서로 유사하다고 가정한다.

• 공간적 정보를 무시하여 동일한 아이템 집합 내 가능한 모든 경우의 수를 SGNS의 Positive Sample

  • Skip-Gram은 n개만 사용하지만, 여기선 모든 단어 쌍(경우의 수)를 사용

Approximate Nearest Neighbor(ANN)¶

Nearest Neighbor(NN)¶

Vector Space Model에서 내가 원하는 Qurey Vector와 가장 유사한 Vector를 찾는 알고리즘

• MF 모델로 추천 아이템을 서빙한다면?
  • 유저에게 아이템 추천 : 해당 유저 Vector와 후보 아이템 Vector들의 유사도 연산 필요
  • 비슷한 아이템 연관 추천 : 해당 아이템 Vector와 다른 모든 후보 아이템 Vector 유사도 연산이 필요

추천 모델 서빙은 NN Search와 유사한데, 모델 학습을 통해 구한 유저/아이템 Vector를 가지고 주어진 Qurey Vector(유저, 아이템)의 인접한 이웃(유사도)를 찾아주는 방식이다.

Brute Force KNN¶

NN을 정확히 구하기 위해서 나머진 모든 Vector와 유사도를 비교를 수행, 연산 비용이 너무 높다. (가성비가 떨어짐)

• 정확도는 조금 포기하고 빠른 속도로 => ANN 사용

---

근사 해법의 필요성¶

NN을 정확하게 찾는 것이 아니라 근사하여 찾는 필요성.

• 정확도와 속도는 Trade off 관계!

ANNOY¶

주어진 벡터들을 여러 개의 subset으로 나누어 tree 형태의 자료 구조를 구성하고 이를 활용하여 탐색

1. Vector Space에서 임의의 두 점을 선택한 뒤, 두 점 사이의 hyperplane으로 Vector Space를 나눈다.(subset 생성)
2. Subspace에 있는 점들의 개수를 node로 하여 binary tree 생성 혹은 갱신
3. Subspace 내에 점이 K개 초과로 존재하면, 해당 Subspace에 대해 1,2 반복 진행
   • ANN을 구하기 위해서 현재 점을 binary tree에서 검색하고 해당 subspace에서 NN을 search

ANNOY의 문제점과 해결방안¶

문제점 : 가장 근접한 점이 아슬아슬하게 tree의 다른 node에 있을 경우, 해당 점은 후보 subset에 포함되지 못한다.

• 해결방안

  1. priority queue를 사용해 가장 가까운 node를 탐색
  2. binary tree를 여러 개 생성하여 병렬적으로 탐색 : 앙상블 효과와 유사

• Annoy parameter

  1. number_of_trees : 생성하는 binary tree의 개수
  2. search_k : NN을 구할때 탐색하는 node의 개수

위와 같은 해결방안도 정확도는 올라가겠지만, 탐색시간이 늘어나게 된다.

ANNOY의 요약 및 특징¶

1. Search Index를 생성하는 것이 다른 ANN에 기법에 비해 간단하고 가벼움

   • 아이템 개수가 많지 않고 벡터의 차원(d<100)이 낮은 경우에 사용하기 적합
   • GPU 연산 지원 안함

2. Search 해야 할 이웃의 개수를 알고리즘이 보장