추천 시스템 06. Matrix Factorization 행렬 분해

두 행렬(매트릭스)을 곱하는 방법! 알고 계시나요? 이미 빠삭하신 분들은 다음 섹션으로 바로 넘어가셔도 좋지만, 기억이 가물가물하거나 수학을 일찍 포기해버리셨던 분들을 위해 행렬의 곱셈에 대한 설명으로 글을 시작하겠습니다. 

Matrix Multiplication. 행렬의 곱셈.

두 수의 곱셈과 달리 두 행렬의 곱셈은 순서가 매우 중요합니다.

 

두 수 2와 3은 어느 수를 앞에 두어도 곱셈 결과가 같지만 ($2 \times 3 = 3 \times 2 = 6$), 두 행렬 A, B 간의 곱셈은 어떤 행렬을 앞에 두냐에 따라 결과가 달라집니다 ($ A \cdot B \neq B \cdot A $). 곧 설명할 두 행렬의 모양에 대한 룰을 지키지 못할 경우, 곱셈 연산 자체를 수행할 수 없기도 합니다. 따라서 어느 행렬을 앞에 놓을지 반드시 먼저 정해야 합니다.

 

이렇게 행렬의 순서를 정하고 나면, 왼쪽의 행렬은 가로(행) 방향의 벡터를 한 덩어리로, 오른쪽에 있는 행렬은 세로(열) 방향의 벡터를 한 덩어리로 생각합니다. 그 후 각 행 덩어리와 열 덩어리를 서로 곱해 결과값 행렬의 셀을 채웁니다. 아래 그림을 예로 들면, 왼쪽 행렬의 제1행과 오른쪽 행렬의 제1열의 내적(dot product)값은 $1\cdot7+2\cdot9+3\cdot11=58$이며 이 값은 결과값 행렬의 (1,1) 셀에 위치하게 됩니다. 왼쪽 행렬의 제2행과 오른쪽 행렬의 제2열이 곱해지면 결과값 행렬의 오른쪽 아래 코너를 채우게 되겠죠. 

 

 

Source: mathsisfun.com

 

그러고보니 왼쪽 행렬의 행의 갯수는 결과값 행렬의 행의 갯수와 연관되어 있고, 오른쪽 행렬의 열의 갯수는 결과값 행렬의 열의 갯수와 연관된어 있습니다. 즉, (1) 결과값 행렬의 모양은 왼쪽 행렬의 행의 갯수, 오른쪽 행렬의 열의 갯수에 의해 정해집니다. 그리고 (2) 왼쪽 행렬의 열의 갯수와 오른쪽 행렬의 행의 갯수가 일치해야지만 결과값 행렬을 온전히 채울 수 있습니다. 

 

수학적인 표현으로 정리하자면, $m \times n$ 차원(행이 $m$개, 열이 $n$개)의 행렬 $A$와 $j \times k$ 차원의 행렬 $B$의 행렬곱 $AB$는 $m \times k$ 차원의 행렬이며, $n=j$이어야지만 행렬곱을 구할 수 있습니다.

행렬 곱셈과 행렬 분해의 미묘한 관계.

행렬곱에 대한 이야기로 글을 시작한 이유는, 행렬곱을 알면 오늘의 주제인 Matrix Factorization (MF) 알고리즘의 70%를 이미 이해한 것이나 마찬가지이기 때문입니다. Matrix Factorization이라는 이름 자체가 굉장히 난해하게 느껴질 수 있는데, '행렬 분해'라는 한국어 뜻을 생각하면 오히려 쉽게 이해할 수 있습니다. 즉, Matrix Factorization은 매트릭스를 "분해"합니다. 다음 그림처럼요.

 

Source: medium.com/@connectwithghosh

이 그림, 익숙하지 않나요? 위 섹션에서 배운 행렬곱을 반대 방향으로 뒤집기만 하면 바로 행렬분해, Matrix Factorization이 됩니다. 

 

먼저 각 매트릭스에 이름을 붙여보겠습니다. 그림의 왼쪽에 있는 매트릭스는 04. 유저 기반 협업 필터링, 05. 아이템 기반 협업 필터링에서 자주 보던 그 아이입니다. 행은 유저, 열은 아이템으로 구성된 평점 매트릭스($R$)이죠. 이 매트릭스에서 $i$번째 행, $j$번째 열에 해당하는 값은 유저 $i$가 아이템 $j$에 준 평점을 나타냅니다. (또는 0과 1로 유저의 아이템 구매여부를 나타낼 수도 있습니다.) 등호($=$)의 오른편에 있는 두 매트릭스는 각각 '유저 매트릭스($U$)'와 '아이템 매트릭스($I$)'라 부르도록 하겠습니다.

 

앞서 행렬곱을 뒤집으면 행렬분해라고 했습니다. 그렇다면 도입부에서 배운 행렬곱의 특성 두 가지를 뒤집으면 우리가 행렬을 분해할 때 지켜야할 룰을 찾을 수 있을 것 같습니다.

 

우선 행렬곱의 첫번째 특성입니다.

   

    ✔ 왼쪽 행렬의 행의 갯수는 결과값 행렬의 행의 갯수를 결정하고, 오른쪽 행렬의 열의 갯수는 결과값 행렬의 열의 갯수를 결정한다.

 

이를 뒤집어 행렬분해에 적용하면 아래와 같습니다.

 

    ✔ $R$의 행의 갯수는 $U$의 행의 갯수와 일치하고, $R$의 열의 갯수는 $I$의 열의 갯수와 일치한다.

 

다음은 두번째 특성입니다. 

 

    ✔ 왼쪽 행렬의 열의 갯수와 오른쪽 행렬의 행의 갯수가 일치하여야지만 행렬을 곱할 수 있다.

 

이를 행렬분해에 적용하면 아래와 같습니다.

 

    ✔ $U$의 열의 갯수와 $I$의 행의 갯수는 일치해야 한다.

곱셈의 결과가 평점 매트릭스를 닮도록 분해하기

이제 행렬을 분해할 때 지켜야하는 최소한의 조건을 알았으니, 본격적으로 분해를 해보겠습니다. 위의 두 룰을 통해 매트릭스 $U$와 $I$의 모양은 어느 정도 파악하였으니 남은 일은 이제 각 셀의 값을 채우는 일입니다. MF 알고리즘은 매트릭스 $U$와 $I$의 행렬곱 $U \cdot I$가 매트릭스 $R$과 최대한 일치한 값을 갖게끔 두 매트릭스의 셀 값을 조정합니다. 

 

우선 첫번째 라운드는 랜덤한 숫자로 매트릭스 $U$와 $I$의 셀들을 채우고 시작합니다. 이 상태에서 행렬곱 $U \cdot I$를 구한 뒤 $R$과 비교합니다. (여기서 행렬곱 $U \cdot I$는 예측값(prediction), $R$은 실제값(ground truth)이라 부릅니다.) 첫번째 라운드의 예측 오류(prediction error)는 각 셀에 대해 예측값과 실제값 간의 차이를 구한 후 이를 모두 더한 값입니다. 

 

두번째 라운드의 목적은 매트릭스 $U$,$I$의 셀 값을 조정하여 조금 전보다 더 잘하는 것입니다. 즉, 앞 라운드의 예측 오류보다 더 적은 수준의 오류를 달성하는 것이 목표입니다. 그리고 그 이후의 라운드에서도 이러한 과정을 계속하여 반복합니다. 다시 말해, MF 알고리즘은 매 라운드가 진행될 때마다 예측값과 실제값 간의 오차를 점차 줄이려는 목표를 가지고 있으며 이는 다음과 같은 목표 함수(objective function)로 표현할 수 있습니다.

 

$$ minimize \sum_{i,j \in obs}(R_{(i,j)}-(U_i \times I_j))^2$$

 

위의 함수를 최소화 하는 최적의 솔루션을 찾기 위해서는 Stochastic Gradient Descent(SGD; 확률적 경사 하강법) 등 최적화 알고리즘을 활용하여야 하고, 그 결과에 따라 매트릭스 $U$, $I$의 셀 값을 조정하게 됩니다. 최적화 알고리즘 중에서도 MF에 가장 많이 쓰이는 기법은 Alternating Least Squares (ALS; 교대 최소 제곡법)입니다. 이 방법은, 매트릭스 $U$, $I$를 동시에 조정하지 않고, 한 회차는 매트릭스 $U$를, 다음 회차에는 매트릭스 $I$를 조정하는 식으로 두 매트릭스를 "교대로" 조정합니다. 한 번에 하나의 매트릭스만 신경씀으로써 더욱 효율적으로 최적화를 할 수 있는 것이죠.

 

* SGD 및 ALS 등 최적화 알고리즘을 정확히 설명하기 위해서는 별도의 포스팅이 필요하기 때문에, 여기서는 '예측 오류를 줄이기 위해 모델의 파라미터(Matrix Factorization의 경우에는 유저 및 아이템 매트릭스의 셀값)를 조정하는 알고리즘' 정도로만 이해하고 넘어가도록 하겠습니다.

 

수 많은 라운드 끝에 예측 오류가 더이상 줄어들지 않는 수준에 도달하면, 우리는 '오차를 최소화하는 최적 솔루션'을 찾았다고 결론짓고 MF 알고리즘을 마무리짓습니다. 이 과정을 통해 얻어낸 유저 매트릭스($U$)와 아이템 매트릭스($I$)를 곱하면 우리는 우리만의 최종 평점 매트릭스($\hat{R}$)를 얻게 됩니다.

추천 리스트 추려내기

Ground Truth 평점 매트릭스($R$)와 Prediction 평점 매트릭스($\hat{R}$)의 가장 큰 차이는 Ground Truth는 고객이 아직 평점을 부여하지 않은 아이템들이 있기 때문에 군데군데 비어있는 반면, Prediction은 빼곡히 차있습니다. 즉, 고객이 아직 평점을 부여하지 않은 아이템에 대해 우리는 이제 예측 평점을 갖게 된 것입니다. 이제 남은 것은 예측 평점 순서대로 아이템을 줄 세워 고객이 아직 접하지 않은 아이템을 추천 리스트에 포함하는 것입니다.

---

행렬곱부터 Matrix Factorization까지. 어려워 보이는 용어들이지만 생각보단 어렵지 않지 않았나요? 평점 매트릭스를 그냥 단순한 테이블로 보지 않고 선형대수를 이용하여 두 개의 매트릭스로 분해를 하겠다는 기가막히는 생각은 실제로 2006년 넷플릭스 컴피티션에서 예상을 뛰어넘는 퍼포먼스를 보여주었습니다. 그 이후 이 알고리즘을 기반으로 한 다양한 방법들이 생겨났고, 지금은 '추천 시스템'하면 떠오르는 가장 중요한 알고리즘이 되었습니다.

 

지금까지 인구통계학적 필터링, 컨텐츠 기반 필터링, 협업 필터링(유저 기반, 아이템 기반)부터 추천 시스템의 최종 보스인 MF 알고리즘에 대해 알아보았는데요. 많이 들어보긴 했지만, 정확히 어떻게 동작하는건지 알 수 없었던 '추천 시스템'에 대해 한발짝 다가간 시간이었기를 바랍니다. 그럼 저는 다른 포스팅으로 다시 돌아오겠습니다!

 

Happy Machine Learning! :)

 

Reference:

[1] Koren, Y., Bell, R., & Volinsky, C. (2009). Matrix factorization techniques for recommender systems. Computer, 42(8), 30-37. https://datajobs.com/data-science-repo/Recommender-Systems-[Netflix].pdf