모델 기반 협업 필터링

Model-Based Collaborative Filtering

저번에는 협업 필터링이 무엇인지, 그리고 가장 기본이 되는 이웃 기반 협업 필터링을 배웠다. 협업 필터링은 기본적으로 유저-아이템 행렬의 빈칸을 채우는 예측 문제이며, 이 행렬의 특성에 의해 두 가지 문제가 발생한다. 
첫번째는 확장성Scalability(저번에는 나는 규모 확장성이라 번역했다). 유저와 아이템의 규모가 클수록 행렬의 크기가 증가하기 때문에 모델의 연산 시간이 너무 오래 걸리게 된다. 
그리고 희소성. 데이터가 부족할 때는 유사도 계산이 부정확하기에 추천 성능이 보장되지 않는다. 또 데이터가 없는 신규 유저가 나타날 경우 그에 대한 추천을 하는 것이 불가능한데, 이를 cold start라고 한다. 추천을 할 기반이 아예 없는 것.

이를 극복하면서 나오는 것이 바로 모델 기반 협업 필터링이다. 이것은 항목 간의 유사성을 직접 따지지 않고 데이터에 내재한 패턴을 파악해 추천하는 기법이다. 내재한 것을 어떻게 찾느냐? 우리야 모르지.. 다만 기계는 알 수도 있다. 머신러닝이 뭐냐, 기계가 직접 어떤 것을 학습하는 것 아니냐. MBCF도 전형적인 머신러닝에 해당하는 것으로 파라미터를 주어진 데이터를 이용해 학습한다. 이 파라미터에 데이터의 패턴이 압축된 형태로 담기게 되는 것이다.
덕분에 MBCF는 유저와 아이팀 간에 잠재적인latent 특성이나 패턴을 찾을 수 있다는 특징을 가진다. 또 NBCF는 데이터를 계산해서 행렬의 빈칸을 완성하는 방식으로 저장하는 반면 MBCF는 학습을 통해 변하는 파라미터를 저장한다. 
이러한 머신러닝의 기본적인 아이디어가 반영된 MBCF에서는 Matrix Factorization 기법이 가장 많이 사용되는데 특히 최근 딥러닝 모델에서도 응용된다고 알려져 있다. 

vs NBCF

NBCF와 비교했을 때의 장점. 유저-아이템 행렬(데이터)는 학습에만 사용되고 정작 저장되는 것은 압축된 모델이기 때문에 메모리를 비교적 적게 사용하며, 이렇게 학습된 모델로 추천을 진행하기에 서빙 중 속도에서 이점을 가진다.
또 위에서 언급된 희소성과 확장성의 문제를 훨씬 잘 해결한다.
또한 NBCF는 위의 문제 해결을 위해 KNN 기법을 사용하기에 특정 주변 이웃에 의해서만 크게 영향을 받는 과적합 문제가 발생하기도 하지만 이쪽은 전체 데이터를 활용하기에 과적합에서도 상대적으로 자유롭다.
마지막으로 NBCF는 어디까지나 유사도를 기반으로 한다. 그렇기에 위에서 문제로 제기한 cold start의 케이스나, 유사도가 높은 유저가 없는 유저의 경우 이웃이라는 효과를 보기가 어렵다. 반면 MBCF는 그런 문제에서도 자유로울 수 있다.

본격적으로 각 모델을 알아보기 이전에 알아두면 좋을 개념들을 잠시 짚어보자.

Implicit Feedback

본격적으로 들어가기에 앞서 알아야 할 개념. 명시적 피드백과 암묵적 피드백에 대해서는 초반에 설명한 바 있다. 명시적 피드백은 유저가 의식해서 선호도의 정보를 제공하는 데이터이지만, 실제로 우리가 다루는 데이터 중 대다수는 그렇지 않고 로그의 형태로 받게 되는 데이터들이다. 가령 클릭 여부, 시청 시간이나 여부 같은 것들. 

Latent Factor Model(= Embedding)

잠재 요인 모델. 최근의 표현으로는 임베딩.
임베딩은 뭐냐? 정확하게 뭐라고 하기에 내 머릿 속에 완전히 정리는 안 되어 있지만, 일단 간단하게는 주어지는 데이터들을 조밀한 벡터로 표현하는 행렬이라고 할 수 있겠다. word embedding에서 유래된 개념으로 어떤 문장의 원소들을 행렬로 표현하고자 할 때, 가장 쉬운 방법은 원핫벡터로 표현하는 방법이다. 이 경우 n개의 문장에 대해 n*n의 행렬이 생기게 되며 이 행렬은 희소 행렬이 되는데, 이것을 조금 더 밀집된 벡터로 압축하고 싶은 것이다. 그때 나오는 것이 바로 임베딩으로 n*k(k는 내가 원하는 정도의 차원) 정도로 줄여서 표현을 할 수 있게 된다. 그 밀집된 행렬 속에는 문장 원소들의 잠재적인 패턴이나 요인이 담겨있을 것이라 생각할 수 있다. 자세한 개념은 언젠가 다시 정리할 기회가 있었으면 좋겠다. 
아무튼 이 개념을 여기에 적용하면? 유저와 아이템의 데이터가 담긴 희소 행렬을 잠재적 요인으로 표현할 수 있다고 보고 저차원으로 분해하는 것. 
쉽게 용례만 생각해보자면 그냥 원핫벡터나 희소 행렬을 조금 더 컴팩트하게 압축된 행렬로 표현하는 것이라 보면 된다.
또 다른 용례도 있다. 유저의 수와 아이템 수가 다를 수 있다. 이때 임베딩을 통해 같은 차원에 놓이도록 만들게 되면 임베딩되어 나온 벡터를 통해 유저와 아이템 간의 유사도를 측정할 수도 있게 된다.

영화라는 아이템 벡터들과 유저 벡터들이 같은 차원에 그려진 모습. 유저와 가까운 아이템을 추천해주는 것이 아무래도 좋은 추천일 가능성이 높다. 여기에서 조심해야 하는 것은 웃김이나 남성향과 같은 특징들은 분포를 보고 추측한 것일 뿐 실제로 그런 것에 대한 정보를 정확하게 알 수는 없다는 것. 인간이 머신 러닝 속 파라미터의 분포를 보고 사실 패턴을 알아내는 것은 실질적으로 불가능하다..
(이것은 단순한 예시이고 실제로 유저와 아이템을 동일 차원에 두고 비교하는 것은 불가능하다고 생각한다. 임베딩해서 나온 값을 어떻게 모델에서 활용하느냐에 따라 임베딩 층은 같은 차원을 뽑더라도 다른 패턴을 학습하게 될 것이다.)

Singular Value Decomposition

SVD 분해 기법. 이것은 사실 선형대수학에서 2차원을 분해하는 기법으로 유저-아이템 행렬을 유저 잠재 요인 행렬, 잠재 요인 대각행렬, 아이템 잠재 요인 행렬로 만든다.

위는 SVD의 개념 그 자체, 아래는 축소 버전

보다시피 유저-아이템 행렬인 R이 유저 행렬인 U, 대각행렬인 $\sum$, 아이템 행렬인 V로 나뉘는 것을 볼 수 있다. 
이때 우리는 이것을 좀 더 압축해서 표현할 수 있다. 바로 아래처럼 truncated 하는 것이다. 어차피 대각행렬에는 중요도를 나타내는 특이치가 담겨있는데, 이 중 중요하다 생각되는 k개의 특이치만 사용해서 잠재 요인의 차원을 축소해서 표현한다. 이렇게 표현되는 $\hat{R}$은 완벽하게 R과 같지는 않지만 충분히 유사하다. 결과적으로 중요한 정보는 남은 채로 우리는 차원을 요약한 꼴이다.
그래서 이렇게 truncated으로 줄어든 SVD를 파라미터로 사용해 학습을 꾀한다는 것이 SVD를 통한 MBCF의 아이디어. 

그러나 이 방법은 문제가 있으니.. 우리의 데이터는 매우 희소한 행렬인데 그 희소한 부분이 전부 결측(측정되지 않음. 0이 아니라 아예 값이 없다)되어 있다는 것. 그러나 이 분해 기법은 결측된 상태에서 작동되지 않기에 우리가 임의로 채워넣어야만 한다. 그래서 그 결측치를 전부 0으로 메꾸거나, 현재 가지고 있는 값들의 평균으로 채우게 되는데 이러한 불필요한 연산이 필요하다는 게 문제이다. 이러한 연산 비용 증가 뿐만이 아니라 심지어 데이터를 왜곡시킨다는 문제도 가지고 있다. 

그래서 우리는 적은 차원으로 분해하는, 임베딩의 원리를 사용하되 다른 접근을 할 필요가 있다. 

Matrix Factorization

줄여서 MF. 이 개념이 언급했듯이 가장 많이 활용되니 잘 알고 있도록 하자. 
MF는 SVD처럼 저차원으로 분해한다는 것에 아이디어를 가지고 있으나, 오직 관측된 값만을 활용해 결측된 값들을 예측하는 모델을 만드는 것이 목표이다. 
유저-아이템 행렬(R)을 유저 행렬(P)과 아이템 행렬(Q)로 분해해서 원래 행렬과 유사한 행렬을 추론하는 방식.

위에서 본 모양과 꽤 유사하다

중간에 물결처럼 표현된 등호는 유사하다는 것을 나타내는 표현임을 명심하자. 그래서 P와 Q가 학습 파라미터로서 데이터를 받아서 학습하게 될 것이다.
그렇다면 어떤 손실 함수를 사용하여 최적화를 하는가? 우리가 흔히 아는 MSE를 통해 학습 파라미터를 최적화한다.

$\Large \sum(r_{u,i} - p_u^Tq_i)^2$

여기에서 연산이 이뤄지는 것은 오직 관측된 값에 한한다. 애초에 r값이 있는 것에만 해당 연산을 사용할 수 있으니 당연한 꼴. 관측이 되어 MSE를 낼 수 있는 값들에 대해서만 오차를 계산해 해당 값이 작아지도록 파라미터를 학습시킨다.

조금 더 정교한 목적함수

목적 함수라고 표현되는데, 그냥 손실 함수와 같은 개념이라 봐도 무방하다.
뒷 수식은 L2노름 정규화(regularization인데, 사실 규제화라고 하는게 맞지 않을까, normalization이랑 조금 다른 개념인데)로, 과적합이 되는 것을 방지하기 위한 장치이다. 곱해지는 하이퍼파라미터인 $\lambda$를 통해 적당하게 정규화의 정도를 조절할 수 있다.

대표적인 두가지 정규화 방식

손실 함수를 구했으니 어떻게 최적화할래? 이것도 초반에 배웠던 SGD(확률적 경사하강법)을 사용한다.

쓰기 귀찮은.. 식

지난날 힘들게 비슷한 수식을 손으로 미분했던 기억이.. 당장 또 해내라 하면 시간이 좀 걸릴 것 같은데, 이제는 수식을 봐도 얼추 이해하는 단계까지 왔으니 손으로 직접 미분을 하는 것은 사양하겠다. 

이러한 방식으로 식이 짜여지고 파라미터가 설정되어 학습이 이뤄진다.
이제 MF를 처음 발표한 논문에서 모델의 개선을 위해 사용한 갖가지 기법들을 알아보자.

adding biases

유저마다 평점을 다르게 줄 수 있다. 누구는 짜게 주고 누구는 후하게 주는 식. 이런 식의 편향이 발생할 수 있기에 편향을  반영할 파라미터를 추가하여 예측 성능을 높여줄 수 있다.

편향이 반영된 목적함수

$\mu$는 글로벌 편향으로 학습 파라미터는 아니다. 나머지 b들이 학습 파라미터로 각각 아이템에 대한, 유저에 대한 편향이다.

최적화 방법

adding confidence level

우리는 관측된 값들을 활용하는데 이 값들이 동일 신뢰도를 가지지 않을 수도 있다. 그래서 우리는 신뢰도에 따라 학습에 반영되는 정도를 다르게 하고 싶다. 특정 아이템에 대한 정보만 너무 많을 수도 있다. 이 경우에 이 데이터에 대한 신뢰도를 낮춰 다른 데이터들이 학습될 기회를 늘려줄 수 있다.
참고로 암묵적 피드백처럼 평점이 분명하지 않은, 정말 신뢰도가 떨어지는 값에 대해서도 이 테크닉을 통해 이득을 볼 수 있다.

이제는 맨 앞에 $c_{u,i}$를 붙인다. 이것이 바로 신뢰도를 나타내는 수치로 이것을 통해 값마다 학습에 반영되는 정도를 조절할 수 있게 된다.

adding temporal dynamics

시간에 대한 정보도 담고 싶다! 유저가 시간이 지나면서 평점을 내리는 성향이 바뀔 수도 있고, 아이템이 나온지 오래 되면 인기가 식는 경우도 있을 것이다. 그런 시간을 통해 바뀌는 정보도 담고 반영하고 싶다.  그래서 학습 파라미터가 시간을 반영하도록 모델을 바꾼다.

Alternative Least Square

줄여서 ALS. 이것은 MF를 개선하며 암묵적 피드백에 활용한 모델이다. 암묵적 피드백에 적합한 MF 설계!
기본적인 개념은 우리가 학습해야 할 P와 Q를 동시에 업데이트하지 않고 한쪽을 업데이트할 때마다 다른 한 쪽을 상수 취급하면서 업데이트하는 것이다. 이렇게 할 경우 least-square 문제(최소제곱법)로 변형된다고 하는데, 이게 무엇인지 검색을 해봤으나 잘은 이해가 되지 않았다.

다만 이런 수식으로 변형된다는 것을 이야기하는 듯.

목적 함수 식은 같다

보다시피 식의 변경점은 없으나, 최적화를 하는 방식이 다르다. 최소 제곱법으로 접근이 되니 굳이 미분을 해서 그 값을 빼는 방식으로 업데이트하지 않고 각 값의 해를 구하는 방식으로 매번 학습이 된다.

그래서 이게 어떻게 암묵적 피드백을 고려하는가? 조금 추가적인 기법이 들어간다. 먼저 우리가 구하고자 하는 것을 1과 0의 값만을 가진 이진 문제로 바꾼다. 그 후 신뢰도를 또 곱해주는데 이때의 신뢰도의 모양은 다음과 같다.

$\Large c_{ui} = 1 + \alpha \times r_{ui}$

여기에서 $\alpha$값을 조정해서 해당 값의 중요도를 조정하는 방식으로 작동한다. confidence 대충 이리 생겼다는 것이고, 아무튼 그래서 이제 이것을 고려하여 우리가 구하는 해는 다음과 같은 모양이 된다.

보기만 해도 복잡하다

f가 우리의 이진 값. c가 방금 같은 모양을 하고 있기 때문에 f가 0이어도 해가 0이 되어버리지 않는다. 이렇게 해서 ALS는 대체로 이진 값을 가지는 암묵적 피드백을 효과적으로 처리할 수 있게 되었다. 일단 연산량이 적어 빠른 한편 이진 문제를 잘 대처할 수 있다.

Bayesian Personalized Ranking

줄여서 BPR. 이것도 암묵적 피드백을 학습하는 MF에 관한 것이지만, 새로운 관점에서 접근했다는 점에서 의의가 있다. 이름 그대로 베이지안 추론 방식을 사용한다.

일단 personalized ranking이 무엇인가? 유저에게 '순서가 있는' 아이템 리스트를 제공하는 문제이다. 이는 유저가 a보다 b를 선호한다는 정보가 있을 때 이를 활용해서 모델을 학습시키겠다는 것이다. 
근데 우리가 다룰 암묵적 피드백에서는 그런 선호의 정도가 제대로 드러나지 않는다. 단순히 관측됐는지, 아닌지의 여부밖에 없다. 관측된 것은 관측된 것이지만, 결측에 대해서는 두 가지 추측이 가능한데, 하나는 유저가 아이템을 봤으나 정말로 선호하지 않아서 데이터가 없거나(클릭하지 않는다던가), 다른 하나는 유저가 관심은 있으나 해당 아이템의 정보가 유저에게 전달되지 않아 유저가 모르는 것일 수도 있다. 모쪼록 이러한 두 가지 가능성을 고려하면서 모델을 만들어낸 것이 바로 이 BPR이 되시겠다. 

그 방법은 다음과 같다. 일단 몇 가지 가정을 한다. 일단 관측된 아이템을 아무래도 관측하지 않은 것보다는 선호할 것이다. 그러면서 암묵적 피드백은 대부분 이진 값이기에 관측된 아이템끼리는 선호도를 추론할 수 없고, 마찬가지로 결측된 아이템끼리도 선호도를 추론할 수 없다.

어떻게 한다는 거냐!

왼쪽이 유저-아이템 암묵적 데이터라고 쳐보자. 물음표는 결측값, +는 관측값이다. 이 상태에서 우리는 위의 가정을 토대로 각 유저마다 행렬을 만들어나가는 것이다. 관측과 결측 사이에서 순위를 가려가면서 비교한다. 
이런 식으로 해서 유저마다, 관측된 아이템과 결측된 아이템을 각각 차원으로 가지는 3차원의 데이터가 만들어지게 된다.

이렇게 데이터를 만들어내면 학습은 어떻게 하는가? 이때 베이즈 정리를 활용한 최대 사후 확률 추정 기법(Maximum A Posterior)을 사용한다.

우리가 원하는 것은 유저의 선호 정보를 잘 예측하는 파라미터, 사후 확률이다. 이 값은 위 수식처럼 사전확률과 가능도에 비례하게 된다. 그래서 그나마 적절한 가정과 수식을 통해 얻을 수 있는 값들을 활용해 사후 확률 최대화하는 방향으로 추정하자는 것이 바로 이 학습 방식의 핵심이다. 

그렇다면 먼저 가능도를 계산해보자. 가능도는 파라미터를 고정시켜서 볼 때 유저의 선호 정보를 나타내는 확률값이다.

역시 확률을 사용하는 문제는 항상 어렵다..

가능도는 달리 말하자면 유저-아이템 행렬에서 유저가 i보다 j를 더 선호하는 확률을 구하는 것과 같으며, 그것은 각각의 예상 확률을 구해서 뺀 뒤에, 시그모이드를 씌워 0과 1사이의 값을 도출하는 것으로 구할 수 있다. 그렇게 나올 수 있는 값을 전부 곱하는 것이 바로 가능도(내가 제대로 이해를 하고 있지 않아서 그런지 정리가 잘 안 된다).
다시. 가능도는 파라미터가 이미 주어져 있다고 칠 때 유저의 선호 정보를 나타내는 확률값이다. 그리고 이것은 행렬에서 나타낼 수 있는 모든 선호 정보를 곱한 값으로 구할 수 있다. 그래서 그 선호 정보는 어떻게 구하는가? 선호의 우위를 가리기 위해 고정된 파라미터의 값으로 유저의 각 아이템에 대한 선호도를 에측하고, 이를 시그모이드를 씌워 확률값으로 표현한다. 

사전확률은 어떻게 계산하는가? 이것은 우리가 학습해야할 파라미터에 대한 확률이다. 보통 이 사전 확률은 정규분포를 따른다고 가정한다. 우리가 사용하는 데이터는 전부 벡터, 행렬이기에 정규분포도 행렬의 모습으로 정의되어야 한다.

평균은 0이고, 공분산 행렬은 $\sum_\theta$인 정규분포라는 가정을 한다.  $\lambda$는 하이퍼파라미터로 이후에 이것이 정규화의 정도를 조절한다는 것이 보여질 것이다.

공분산이란

이제 우리는 비로소 사후 확률을 최대가 되도록 추정할 수 있는 식들을 얻었다. 이를 토대로 목적 함수를 쓸 수 있게 된다.

로그를 씌우는 것은 이전에 MLE에서 봤던 것과 같은 것이라 보면 된다. 어차피 최대화시키는 부분에서는 로그를 씌운다고 해서 차이가 발생하지 않는다. 위에서 본 수식들을 그대로 대입하면 결과적으로 가장 아래에 있는 식과 같은 모양이 나오게 된다. 
위에서 봤다시피 결국 식에서 사전 확률은 정규화를 하는 역할을 하게 되며, 그 정도를 조절하고자 하이퍼 파라미터인 $\lambda$가 들어가는 것.

이 값은 미분이 가능하며 따라서 경사하강법을 통해 파라미터를 학습시키는 것이 가능하다. 그러나 논문에서는 그것을 권장하지 않는데, 그 이유는 관측된 것보다 결측된 것이 훨씬 많기 때문에 단순한 경사하강법은 학습의 비대칭을 해결하지 못하기 때문이다. 또한 동일한 정보에 대해서만 업데이트가 발생해서 수렴도 잘 일어나지 않는다고.
이에 해당 논문에서는 LEARNBPR이라는 독특한 방법을 제시한다. 유저가 관측한 아이템 하나와 결측된 아이템 하나를 짝을 지어서 샘플링해 bootstrap 방식의 학습을 하는 것. 비대칭을 다소 해결하고 위의 경우처럼 동일한 조합이 계속 등장하지 않기 때문에 학습이 잘 일어난다고 한다. 

결과적으로 이 모델의 특이한 점은, 암묵적 피드백을 통해 아이템 간의 선호도를 추출하고, MAP 방법을 통해 파라미터를 최적화하며, LEARNBPR를 통해 파라미터를 업데이트한다는 점. 
MF보다 우수한 결과를 얻었다고 한다.