10 minute read

Item2Vec

  • 이전에 배운 협업 필터링(CF) 알고리즘은 아이템 유사도를 생성하기 위해 아이템-아이템 간 관계를 분석하다는 점에서 아이템 기반이다.
  • Word2Vec으로 알려진, Negative Sampling을 사용한 Skip-gram(SGNS)은 자연어 처리분야에서 좋은 결과를 가지고 왔다.
  • 아이템 기반 CF가 뉴럴 단어 임베딩으로 만들 수 있다는 것을 이용하는데, 이것을 이용해 Item2Vec라고 불린 잠재공간에서 아이템에 대한 임베딩을 만드는 아이템 기반 CF를 제시한다.
  • 이 방법으로 유저 정보를 이용할 수 없을 때도 아이템-아이템 관계를 추론할 수 있다.
  • 대규모 데이터셋에서 Item2Vec의 효과를 증명하고 SVD와의 경쟁력을 보여준다.

Item2Vec을 알아보기 전에 원천이 되는 Word2Vec에 대해 먼저 알아보자.

Word2Vec

  • 자연어 처리 분야에서 좋은 성능을 보여주는 방법론이다.
  • 뉴럴 네트워크 기반, 대량의 문서 데이터셋을 vector공간에 투영
  • 압축된 형태의 많은 의미를 갖는 dense vector로 표현
  • 효율적이고 빠른 학습이 가능하다.

Word2Vec에서 사용하는 Word Embedding에 대해 알아보자.

Embedding

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

Sparse Representation: 아이템의 전체 개수와 차원의 수가 동일하다. -> 아이템 개수가 많아질수록 벡터 차원은 한없이 커직 공간이 낭비된다.
ex) one-hot encoindg or multi-hot encoding

Dense Representation: 아이템의 전체 가짓수보다 훨씬 작은 차원으로 표현 -> 이진값(0또는 1)이 아닌 실수값으로 이루어진 벡터로 표현
ex) 마우스 = [0.2,1.4,-0.1,1.2,1.1]

Word Embedding

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

  • one-hoe encoding -> dense representation

단어 간 의미적인 유사도를 구할 수 있다.

  • 비슷한 의미를 가진 단어일 수록 embedding vector가 가까운 위치에 분포한다.

임베딩으로 표현하기 위해서는 학습 모델이 필요하다

  • 이전에 배운 MF도 유저/아이템의 임베딩으로 볼 수 있으며, 데이터로부터 학습한 매트릭스가 곧 임베딩이다.

Word2Vec 학습 방법.

Word2Vec을 학습 하는 CBOW, Skip-Gram, Skip-Gram Negative Sampling(SGNS)에 대해 알아보자.

Continous Bag of Words(CBOW)

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

  • 예측을 위해 단어 앞뒤로 몇개(n)의 단어를 사용할 것인지 정해야 한다.

학습 방법

The quick brown fox jumps over the lazy dog.

위와 같은 문장이 있을때 fox에 대해 vector를 생성하고 어떻게 학습 파라미터를 업데이트하는지 알아보자.

  • 먼저 n을 2로 정했을때 quick, brown, jumps, over이 사용된다.
그림1 그림2
cbow1 cbow1.5
  • 그림 1에서 quick, brown, jumps, over를 사용하여 fox vector를 생성하는 것을 알 수 있다.
  • 그림 2에서 V는 단어의 총 개수, M은 임베딩 벡터의 사이즈, 학습 파라미터: \(W_{VXM}\), \(W'_{MXV}\) 이다.

cbow2

  • 주변 단어들을 학습 파라미터인 \(W_{VXM}\)과 곱을 통해 각 단어에 대한 Vector를 계산한다.

cbow3

  • 모든 Vector들을 더하고 2*n(사전에 정의해둔 앞뒤 단어의 갯수)를 나누어주어 v vector를 구해준다.

cbow4

  • 마지막으로 구한 v벡터를 \(W'_{MXV}\)과 곱하고 소프트맥스 함수를 통해 \(\hat{y}\)를 구하고 one-hot vector y의 차이를 최소화 하도록 모델을 학습한다.
  • 학습 파라미터인 \(W_{VXM}\), \(W'_{MXV}\)가 우리가 사용할 Word2Vec에 해당한다.

Skip-Gram

SG

  • CBOW의 입력층과 출력층이 반대로 구성된 모델이다.
  • 벡터의평균을 구하는 과정이 없다.
  • 일반적으로 CBOW보다 Skip-Gram이 성능이 좋다고 알려져 있다.

Skip-Gram with Negative Sampling (SGNS)

Skip-Gram방법에 Negative Sampling을 진행한 방법이다.

Negative Sampling

SGNS

  • 레이블 이라는 정보를 추가하고 Negative Sampling을 통해 주변 단어가 아닌 값은 0으로 레이블링 해준다.
  • 입력 1은 중신단어 임베딩 레이어를 업데이트 하는데 사용되고, 입력 2는 주변단어 임베딩 레이어를 업데이트하는데 사용된다.

SGNS

  • 중심 단어를 기준으로 주변 단어들과의 내적 sigmoid를 예측값으로 하여 0과 1을 분류한다.
  • 역전파를 통해 각 임베딩이 업데이트 되면서 모델이 수렴한다.
  • 최종 생성된 워드 임베딩이 2개이므로 하나만 선택적으로 사용하거나 평균을 사용한다.

Item2Vec에 대해서 알아보자.

Item2Vec

  • 위에 배운 Word2Vec에서 Word대신 Item을 사용하여 임베딩을 한다.
  • 유저가 소비한 아이템 리스트를 문장으로, 아이템을 단어로 가정하여 Word2Vec을 사용한다.
    • 그렇기에 유저-아이템 관계를 사용하지 않기 때문에 유저 식별 없이 세션 단위로 데이터 생성 가능.
  • 앞서 배운 SGNS 기반의 Word2Vec을 사용하여 아이템을 벡터화 하는 것이 목표이다.
  • 유저 혹은 세션 별로 소비한 아이템 집합을 생성한다.
    • 이 때 시퀀스를 집합으로 바꾸면서 공간적/시간적 정보는 사라진다.
    • 집합 안에 존재하는 아이템은 서로 유사하다고 가정한다.
  • 공간적 정보를 무시하므로 동일한 아이템 집합 내 아이템 쌍들은 모두 SGNS의 positive Sample이 되고 아닌 것은 negative Sample이 된다.

예제

item2vec

Approximate nearest Neighbor (ANN)

Nearest Neighbor(NN)

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

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

  • 유저에게 아이템을 추천할 경우 해당 유저 vector와 후보 아이템 Vector들의 유사도 연산이 필요하다.
  • 비슷한 아이템끼리 연관 추천할 경우 아이템 vector와 다른 모든 후보 아이템 Vector 유사도 연산이 필요하다.

추천 모델 서빙 = Nearest Neighbor Search

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

vector의 인접한 이웃을 찾는 가장 단순한 방법은 모든 경우의 수를 계산하여 찾는 것이다. 이를 Brute Force KNN이라고 하면 주변 k개의 이웃을 모든 경우의 수를 계산하여 찾는다. 하지만 모든 경우의 수를 계산하기 때문에, 아이템, 유저 수가 늘어난다면 경우의 수가 급격하게 늘어나므로 속도면에서 엄청나게 오래 걸린다.
200초의 100%의 정확도가 효과적일까, 2초의 99%의 정확도를 구하는 것이 효과적일까? 당연히 후자이다 바로 ANN

ANN 기법들

ANNOY, HNSW, IVF, Product Quantization 방법들에 대하여 알아보자. 다양한 ann기법들의 성능비교를 확인 할 수 있다. -> ann benchmarks github

ANNOY (Approximate Nearest Neighbors Oh Yeah~)

ANNOY에 대한 자세한 설명 : spotify github

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을 찾는다.

ANNOY

  • 문제점 : 가장 근접한 점이 tree의 다른 node에 있을 경우 해당 점은 후보 subset에 포함되지 못한다.
  • 해결 방안 : priority queue를 생성하여 가까운 다른 node를 검색한다. binary tree를 여러 개 생성하여 병렬적으로 탐색한다.
  • 특징
    • Search Index를 생성하는 것이 다른 ANN 기법에 비해 간단하고 가볍다. -> 아이템 개수가 많지 않고 벡터의 차원이 낮은 경우 사용하기 적합하고, GPU연산은 지원하지 않는다.
    • Search 해야 할 이웃의 개수를 알고리즘이 보장한다.(number_of_trees, search_k 파라미터를 둔다.)
    • 파라미터를 조정해 정확도와 스피드의 trade-off 조정 가능하다.
    • 기존 생성된 binary tree에 새로운 데이터를 추가 할 수 없음(추가할 경우 새로 tree생성)

HNSW (Hierarchical Navigable Small World Graphs)

HNSW 이름이 긴 그대로 계층적으로 작은 세상을 그래프로 나타낸다.

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

  • Layer를 여러 개 만들어 계층적으로 탐색을 진행한다 -> search 속도 향상.
  • Layer0에는 모든 노드가 존재하면 올라갈 수록 노드 개수가 줄어든다.

작동 방식

  1. 최상위 Layer의 임의의 노드에서 시작
  2. 현재 Layer에서 타겟 노드와 가장 가까운 노드로 이동
  3. 현재 Layer에서 더 가까워 질 수 없다면 하위 Layer로 이동
  4. 타겟 노드에 도착 할 떄까지 2,3반복한다.
  5. 2~4를 진행할 때 방문했던 노드들만 후보로 하여 NN을 탐색한다.

대표 라이브러리: nmslib, faiss

IVF (Inverted File Index)

ivf

작동 방식

  1. 주어진 vector를 clustering을 통해 n개의 cluster로 나눠서 저장
  2. vector의 index를 cluster별 inverted list로 저장.
  • query vector에 대해서만 해당 cluster를 찾고 해당 cluster의 inverted list안에 있는 vector들 대해서 탐색
  • 탐색해야 하는 cluster 개수를 증가시킬수록 정확도와 속도의 trade-off가 발생.

Product Quantization - Compression

Quantization clustering의 중심 대표값을 활용하는 방식으로 모든 벡터를 n개의 centroid로 압축해서 표현한다.

작동 방식 1) 기존 vector를 n개의 sub-vector로 나눔 2) 각 sub-vector 군에 대해 k-means clustering을 통해 centroid를 구함 3) 기존의 모든 vector를 n개의 centroid로 압축해서 표현

  • 두 vector의 유사도를 구하는 연산이 요구되지 않는다.(미리 구한 centroid사이의 유사도를 활용한다.)
  • PQ와 IVF를 동시에 사용해 더 빠르고 효율적인 ANN 수행을 가능하게한다(fassi 라이브러리 제공)

마무리

NLP에서 사용하는 Word2Vec작동 방식을 응용하여 추천 시스템에 적용한 Item2Vec에 대하여 알아보았고, 이를 최적화 하는 다양한 ANN기법들에 대하여 알아보았다.

Comments

You May Also Enjoy