[Recommender System] - 추천 시스템에 사용되는 알고리즘들

이전 포스팅에 이어 계속하여 추천 시스템에 대해 살펴보자. 

[Recommender System] - 추천 시스템의 전반적인 내용 (1)

[Recommender System] - 추천 시스템의 전반적인 내용 (2)

---

1. 통계 기반 모델링에서 사용되는 알고리즘

지난 포스팅에서 카이제곱 분포를 이용한 검정방법에 대해 잠시 언급했었다. 설명했던 대로 추천 시스템에서 통계 기반 모델링이라는 것은 '이상' 징후를 보이는 아이템을 추출해내는 작업이라고 볼 수도 있겠다. 카이제곱 검정의 경우 구현하기도 어렵지 않고, 데이터를 전문적으로 하는 사람이라면 알고 넘어가야 하는 이론이기 때문에 조금 더 얘기해보자.

카이제곱을 통계적 모델링에 활용하는 방법은, χ2 = Σ (관측값 - 기댓값)2 / 기댓값 

의 수식을 가지는 카이제곱 계수를 이용하여, 관측값과 기댓값을 각각 관측 빈도와 기대 빈도로 치환하여 카이제곱 분포에 대한 계수 값을 계산한 뒤 이를 비정상적인 분포 검정에 활용하는 것이다. 만약 음주 여부에 따른 간질병 발병 빈도를 알고있다고 할 때 다음과 같은 표로 관측 빈도를 나타낼 수 있다.

	발병	정상	합계
음주	30%	15%	45%
비음주	10%	45%	55%
합계	40%	60%	100%

그리고 합계값을 이용하여 기대 빈도를 구한다면, 다음과 같은 표로 나타날 수 있다.

	발병	정상	합계
음주	100 * 0.45 * 0.4 = 18%	100 * 0.45 * 0.6 = 27%	45%
비음주	100 * 0.55 * 0.4 = 22%	100 * 0.55 * 0.6 = 33%	55%
합계	40%	60%	100%

이러한 두 테이블을 를 이용하여 카이제곱을 계산하는 것이다. 아이템의 관측 빈도를 알 수 있으니, 카이제곱 역시 적용하기에 쉬운 방법이다.

카이제곱 검정 외에도 쿨백-라이블러 발산, KLD(Kullback–Leibler divergence)은 두 확률분포의 차이를 계산하는 데에 사용하는 방법이다. 어떤 이상적인 분포에 대해, 그 분포를 근사하는 다른 분포를 사용해 샘플링을 한다면 발생할 수 있는 정보 엔트로피 차이를 계산한다. 상대 엔트로피(relative entropy), 인포메이션 다이버전스(information divergence)라고도 하는데, 정보이론의 한 방법이다. 이 방법의 핵심은 잘 일어나지 않는 사건은 자주 일어나는 사건보다 정보량이 높다는 것이다. 이 역시 수식이나 알고리즘이 간단한 편이고, 카이제곱 검정보다는 조금 더 많이 언급되는 듯 하다. 자세한 내용은 모름 생략.

2. CF 기반 모델링에서 사용되는 알고리즘

CF는 2가지 방법으로 일반적으로 분류되고, 그 안에서 몇가지로 또다시 분류된다. 먼저 Memory based 알고리즘은 Neighborhood model의 User based, Item based로 나뉘고 Model based 알고리즘은 Matrix Factorization(이하 MF), RBM, 베이지안 등으로 나뉘지만 이 글에서는 Memory based 알고리즘과 MF에 대해서만 설명하도록 하겠다. (RBM과 베이지안은 어려울 뿐더러 잘 사용되지도 않는 것 같다. 추후 공부를 할 예정)

메모리 기반 알고리즘(Neighborhood model 기준)은 유저와 아이템에 대한 matrix를 만든 뒤, 유저 기반 혹은 아이템 기반으로 유사한 객체를 찾은 뒤 빈공간을 추론하는 알고리즘이다.

위와 같은 유저-영화 테이블이 있다고 하자. 채워진 값들은 영화에 대해 내린 rating 값들이다(Implicit score를 가진 도메인의 경우, 이 rating을 채워넣는 것 자체가 문제가 된다). 미영은 레디플레이어원, 곤지암에 대해 점수를 평가했고, 시스템은 아직 보지 않은 영화들에 대해 점수를 매겨 미영이 볼 법한 영화를 추천해주어야 한다. 이때 user based CF의 경우, 미영과 가장 유사한 철수라는 유저를 통해, 어벤져스3에 대한 평점을 예측할 수가 있다. 

참고 : 유사도를 구하는 방법으로는 euclidean distance, cosine simularity, jaccard index, pearson correlation 등의 공식이 있다 (데이터에 특성에 따라 다르긴 하지만, 일반적으로는 코사인 유사도, 자카드 계수, 타니모토 계수 등을 사용한다고 알려져 있다)

반대로 item based CF의 경우, 어벤져스에 대해 내린 유저의 평가와 가장 유사한 레디플레이어원을 유사도 계산으로 찾아내어 빈공간을 메우는 것에 이용된다. 두 방법 모두 콜드 스타트 문제점을 안고있지만, item based CF가 Hybrid 방식을 적용하여 콜드 스타트 문제를 해결하기에 조금 더 능동적이다.

메모리 기반 알고리즘에서 rating의 빈공간을 추론하는 방법은, 아래에서 설명하게 될 MF와 문제가 동일하지만 해결 방식이 다르다. 메모리 기반 알고리즘에서는 빈공간을 유사 유저나 아이템의 유사도 계수를 이용하여 채워넣는 방법, 혹은 regression 문제로 만들어 해결하는 방법 등으로 채워나간다.

다음으로 모델 기반의 알고리즘에 대해 알아보자. 모델 기반의 알고리즘 중, 가장 널리 사용되는 MF만을 살펴보겠다. MF는 유저나 상품의 정보를 나타내는 벡터를 PCA나 SVD같은 알고리즘으로 분해하거나 축소하는 방법이다. 즉 Matrix Factorization은, 유저를 행으로 하고 상품에 대한 평가를 열로 하는 matrix가 있다고 할 때 이를 두 개의 행렬로 분해하는 방법으로, 유저에 대한 latent와 상품에 대한 latent를 추출해내는 것에 그 목적이 있다고 하겠다.

latent는 각각의 유저에 대한 특징을 나타내는 vector로, 머신이 이해하는 방법과 개수대로 생성해낸 것이다. latent vector 간의 distance를 이용하여 유사한 유저나 상품을 추천하는 것에 활용할 수 있다. (latent의 rank를 학습하는 알고리즘과 사용자 지정해주는 알고리즘으로 나뉜다) PCA의 에이겐 벡터 + 에이겐 벨류와 비슷한 개념이라고 생각하면 된다. 아래의 그림(Andrew Ng의 강의 슬라이드 발췌)을 보면 직관적으로 이해가 될 것이다.

MF의 가장 대표적인 방법은 SVD(Singular Value Decomposition)이다. 특이값 분해라고 하는데, 고유값 분해처럼 행렬을 대각화하여 분해하는 방법 중 하나이다. 고유값 분해와 다른 점은 nXn의 정방행렬이 아니어도 분해가 가능하다는 것이고, 이는 Sparse한 특성을 가지는 추천 시스템에서의 Matrix를 분해하는 것에 안성맞춤이다.

(이미지 출처 : ratsgo's blog)

U는 AAT를 고유값분해해서 얻어진 직교행렬로 U의 열벡터들을 A의 left singular vector라 부르고, V 의 열벡터들을 A의 right singular vector라 부른다. 또한 Σ는 AAT, ATA를 고유값분해해서 나오는 고유값들의 square root를 대각원소로 하는 m x n 직사각 대각행렬로, 그 대각원소들을 A의 특이값(singular value)이라 부른다. 즉 U, V는 특이 벡터를 나타낸 행렬이고 Σ 는 특이값에 대한 행렬이라고 할 수 있다.

Σ의 크기를 지정해 줌으로써 latent(의미 부여 벡터)의 크기를 지정해 줄 수도 있다. 이후 decomposition 된 행렬들을 이용하여 원래의 행렬 A와 사이즈가 동일한 행렬을 만들어내면, 비어있는 공간들을 유추해내는 새로운 행렬이 나타나는 것이다. 이를 Matrix Completion의 관점에서 보면, A 행렬에서 rating이 존재하는 데이터를 이용해 미지의 U, Σ, V를 학습하여 Completed 된 행렬 A`를 만들어내는 것이다.

SVD를 비롯한 MF에서 목적함수는, Predicted rating을 구하는 Matrix Completion의 경우, 최적의 해(Rating – Predicted Rating의 최소)가 없이 근사값을 추론하는 문제이다. 따라서 Gradient Descent 알고리즘, ALS(Alternating Least Square) 알고리즘 등으로, global minimum에 근접하는 thresh를 선정하여 이를 objective로 삼아 구하는 문제로 볼 수 있다. 일반적으로는 GD가 우수하지만, ALS는 병렬 처리 환경에서 좋은 성능을 보인다고 알려져 있다.

참고 : 학습이 완료된 후 user나 item에 대한 입력값의 행렬 연산 결과를 prediction을 할 때, 예상을 해야하는 결측값(Matrix에서 *으로 표기된 부분)의 초기값은 binary로 보정하거나 평균 혹은 중앙값으로 보정하기도 한다.

그래서 일반적으로 CF 기반의 추천 시스템을 구축할 때, 가장 많이 사용하는 알고리즘 스택은 SVD, 혹은 ALS를 기반으로 한 Hybrid 방법이 많다.

3. 딥 러닝 기반 모델링에서 사용되는 알고리즘

딥 러닝 기반 모델링에 사용되는 알고리즘에 대해서도 포스팅을 길게 작성하고 싶었지만, 이 방법론은 아직 명확하게 정착된 스택이 없는 것 같다. 이전의 포스팅 2개에서 언급했던 예제들이 현재 리서치가 가능한 내용의 전부이고, 이를 직관적으로 이해하기 위한 아래의 이미지로 충분하리라 생각된다.

(구글 논문에 게재된 추천 시스템 구조도 이미지)

추천 시스템의 각 도메인에서 CF나 통계적 모델링으로 해결하기 어려운 부분, 즉 기계와 인간 사이의 관계를 유추하는 부분에서 딥 러닝이 보완적 용도로 활용되고 있다(혹은 전체 시스템을 딥 러닝을 축으로 하는 프로젝트들도 나타나고 있긴 하다). 딥 러닝 기반 모델링이 잘 활용되는 대표적 예로는 역시 구글의 추천 시스템이 있는데, 유튜브의 추천 시스템은 아예 오픈된 소스와 논문으로 공개해 놓았다. 어차피 그만한 자료와 소스가 있어도 활용할 회사는 자기들 밖에 없다는 배짱같은데, 추천 시스템을 공부하고자 하는 사람이라면 한 번쯤 읽어볼 만한 논문인 것 같다. [Deep Neural Networks for YouTube Recommendations] 라는 키워드로 검색하면 쉽게 읽어 볼 수 있다.

---

이번 포스팅에서는 모델링 방법별 알고리즘과 현황들을 간략하게 살펴보았고, 개별적인 알고리즘에 대한 심화 내용을 추후 간단한 구현 코드(Python 혹은 PySpark, Scala가 될 수도 있다)와 함께 포스팅할 예정이다.