[추천시스템] Item2Vec / ANN

Word2Vec

임베딩 (Embedding)

: 주어진 데이터를 낮은 차원의 벡터로 만들어서 표현하는 방법

 

Sparse Representation: 아이템의 전체 가짓수와 차원의 수가 동일

: 이진값으로 이루어진 벡터로 표현 -> 아이템 개수가 많아질수록 벡터의 차원은 한없이 커지고 공간이 낭비됨

Dense Representation: 아이템의 전체 가짓수보다 훨씬 작은 차원으로 표현

: 이진값이 아닌 실수값으로 이루어진 벡터로 표현

 

워드 임베딩 (Word Embedding)

: 텍스트 분석을 위해 단어를 벡터로 표현하는 방법

• 단어 간 의미적인 유사도를 구할 수 있음
• 비슷한 의미를 가진 단어일수록 embedding vector가 가까운 위치에 분포
• 임베딩으로 표현하기 위해서는 학습 모델이 필요

 

Word2Vec

특징

• 뉴럴 네트워크 기반 (기존의 NNLM 모델)
• 대량의 문서 데이터셋을 vector 공간에 투영
• 압축된 형태의 많은 의미를 갖는 dense vector로 표현
•  효율적이고 빠른 학습이 가능

 

 

1. CBOW (Continuous Bag of Words)

: 주변에 있는 단어를 가지고 센터에 있는 단어를 예측하는 방법

단어를 예측하기 위해 앞뒤로 몇 개(n)의 단어를 사용할 것인지 정해야 함

n =2, 앞뒤로 두개

↓

v : 단어의 총 개수 , M : 임베딩 벡터의 사이즈 , 학습 파라미터 : W, W'

V는 단어마다 모아서 총 v개를 모으고 평균을 구하면 최종 M이 됨. 이를 통해 W' 즉, fox 단어 예측하게 되는 것

최종적으로 softmax를 사용해 최종 one-hot vector로 표현

 

2. Skip-Gram

: CBOW의 입력층과 출력층이 반대로 구성된 모델 / 벡터의 평균을 구하는 과정이 없음

일반적으로 CBOW보다 Skip-Gram이 성능이 좋다고 알려져 있음

 

주어진 입력 단어에 대해서 주변 단어를 예측하는 multi class classification

 

3. Skip - Gram with Negative Sampling (SGNS)

Skip - Gram에서 주변에 있는 단어를, 원래 입력과 레이블의 값을 모두 입력 값으로 바꾸고, 그 단어가 주변에 있다면 1, 없다면 0으로 예측하는 binary classification (가운데 단어와 주변의 단어가 input)

Skip Gram에서의 데이터만 모두 바꿔준다면 데이터에는 1만 존재할 것이다. 그래서 가운데 있는 단어를 중심으로 주변에 있지 않은 단어를 강제로 sampling해야함. 이런 데이터들은 0이 된다. 

 

Negative Sampling의 개수는 모델의 하이퍼 파라미터

positive sample 하나당 k개 sampling / 학습 데이터가 적은 경우 5-20, 충분히 큰 경우 2-5가 적당

중심 단어와 주변 단어가 각각 임베딩 파라미터를 따로 가짐

- 중심 단어와 주변 단어가 서로 다른 lookup table을 통해 임베딩

 

① 중심 단어를 기준으로 주변 단어들과의 내적의 sigmoid를 예측값으로 하여 0과 1을 분류

② 역전파를 통해 각 임베딩이 업데이트 되면서 모델이 수렴함

③ 최종 생성된 워드 임베딩이 2개이므로 선택적으로 하나만 사용하거나 평균을 사용

---

Item2Vec

단어가 아닌 추천 아이템을 Word2Vec을 사용하여 임베딩

유저가 소비한 아이템 리스트를 문장으로, 아이템을 단어로 가정하여 Word2Vec 사용

- Item2Vec은 유저-아이템 관계를 사용하지 않기 때문에 유저 식별 없이 세션 단위로도 데이터 생성이 가능

앞서 배운 SGNS 기반의 Word2Vec을 사용하여 아이템을 벡터화하는 것이 최종 목표

- SVD 기반 MF를 사용한 IBCF보다 Word2Vec이 더 높은 성능과 양질의 추천 결과를 제공

 

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

- 이때 시퀀스를 집합으로 바꾸면서 공간적/ 시간적 정보는 사라짐

- 대신 집합 안에 존재하는 아이템은 서로 유사하다고 가정

공간적 정보를 무시하므로 동일한 아이템 집합 내 아이템 쌍들은 모두 SGNS의 Positive Sample이 됨

- 기존의 Skip-Gram이 주어진 단어 앞뒤로 n개의 단어를 사용하는 것과 달리 모든 단어 쌍을 사용

ex)

---

Approximate Nearest Neighbor (ANN)

Nearest Neighbor (NN)

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

 

MF 모델을 가지고 추천 아이템을 서빙한다면,

유저에게 아이템 추천: 해당 유저 Vector와 후보 아이템 Vector들의 유사도 연산이 필요함

비슷한 아이템 연관 추천: 해당 아이템 Vector와 다른 모든 후보 아이템 Vector 유사도 연산이 필요함

모델 학습을 통해 구한 유저/아이템의 Vector가 주어질 때, 주어진 Query Vector의 인접한 이웃을 찾아주는 것!

 

Brute Force KNN

NN을 정확하게 구하기 위해서는 나머지 모든 Vector와 유사도 비교를 수행해야 함

-> Vector의 차원과 개수에 비례한 비교 연산 비용 필요

-> 따라서 NN을 정확히 찾는 것이 아닌, Approximate Nearest Neighbor를 찾을 필요성이 높아짐 (정확도는 약간 낮아짐. 속도는 빨라짐)

 

ANNOY: Spotify에서 개발한 tree-based ANN 기법

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

1. Vector Space에서 임의의 두 점을 선택한 뒤, 두 점 사이의 hyperplane로 Vector Space를 나눔

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 : number_of_trees(생성하는 binary tree의 개수) & search_k(NN을 구할 때 탐색하는 node의 개수)

 

요약 및 특징

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

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

• Search 해야할 이웃의 개수를 알고리즘이 보장함
• 파라미터 조정을 통해 accuracy / speed trade-off 조정 가능 (num_tree, search_k)
• 단, 기존에 생성된 binary tree에 새로운 데이터를 추가할 수 없음

 

>> Search Space를 줄이는 방식

Hierarchicak Navigable Small World Graphs (HNSW) - 대표 라이브러리; mslib , faiss

벡터를 그래프의 node로 표현하고 인접한 벡터를 edge로 연결

- Layer를 여러 개 만들어 계층적으로 탐색 -> search 속도 향상

- Layer 0에 모든 노드가 존재, 최상위 Layer로 갈수록 개수가 적음 (랜덤 샘플링)

작동 방식

1. 최상위 Layer에서 임의의 노드에서 시작

2. 현재 Layer에서 타겟 노드와 가장 가까운 노드로 이동

3. 현재 Layer에서 더 가까워질 수 없다면 하위 Layer로 이동

4. 타겟 노드에 도착할 때까지 2와 3 반복

5. 2,3,4를 진행할 때 방문했던 (traverse) 노드들만 후보로 하여 NN을 탐색

 

Inverted File Index (IVF)

1. 주어진 vector를 clustering을 통해 n개의 cluster로 나눠서 저장

2. vector의 index를 cluster별 inverted list로 저장

-> query vector에 대해서 해당 cluster을 찾고 해당 cluster의 invert list 안에 있는 vector들에 대해서 탐색

-> 탐색해야 하는 cluster 개수를 증가시킬수록 accuracy ↔ speed trade-off 발생

 

 

>> 기존 벡터가 가지고 있는 고유 값을 압축해서 표현하는 방식

Product Quantization - 대표 라이브러리; faiss

 

1. 기존 vector를 n개의 sub-vector로 나눔

2. 각 sub-vector 군에 대해 k-means clustering을 통해 centroid를 구함

3. 기존의 모든 vector를 n개의 centroid로 압축해서 표현

 

-> 두 vector의 유사도를 구하는 연산이 거의 요구되지 않음. (미리 구한 centroid 사이의 유사도를 활용)

-> PQ와 IVF를 동시에 사용해서 더 빠르고 효율적인 ANN 수행이 가능