Alternating-Least-Squares with Weighted-lambda-Regularization(ALS-WR)
Purpose
ALS-WR 는 model-based 방식으로 원래 matrix R을 iterate하면서 U, M 두개의 matrix로 factorize한다.
R = (user, item, rate)형식의 matrix로 U X I의 사이즈를 가진다.
원래는 R안에 대부분의 R(i, j)는 다 비어 있다. Collaborative Filtering의 목적은 이 비어 있는 R(i,j)들을 어텋게 예측 할 거 인가이다.
Background
CF는 크게 3가지로 나뉜다.
| 방식 | 장점 | 단점 |
|---|---|---|
| memory-based | 결과이해 쉬움, 구현 쉬움, centent frer | 사람이 매기는 rating에 섞인 noise에 대처 미흡, spare한 data에선 performance down, new user/new item에 no result, not very scalable. |
| model-based | rate자체보다는 training set의 pattern이용, sparse data에 비교적 강함, 직관적 결과이해 | model building에 비용 큼, scalability 와 performance간의 trade off, reduction model때문에 원래 useful data can be lost |
| hybrid | memory-based + model-based | 비용큼 |
Introduction
시작하기 전에 matrix factorization에 대한 설명(?정확히는 svd개념설명)으로 링크를 달아 놓았다.
ALS-WR는 model-based방식으로써 원래 rating matrix R(user x item)을 least squared error 를 최소로 하는 U(user x hidden feature), M(item x hidden feature)로 factorize하는 알고리즘이다.
말은 거창한데, 결국 어떤 cost function F(U, M) = square error part + regularization part 을 최소로 하는 U, M을 찾는 문제이다.
자세한 식은 논문을 참조 하고, 이해한 대로만 의견을 추가하겠다.
앞에 square error part는 (실제 rate R(i, j) - 예측 rate R^(i, j))를 error라고 정의하고, 이 error^2들의 합을 의미한다.
Regularization은 machine learning 분야에서 자주 사용 되는 용어로써, model이 overfit하는 것을 방지하는데 도움을 주는 방식이다.
overfit이 모냐
위의 식에서 전체 cost는 각각의 data들과 예측 곡선 y = ax + b와의 거리들의 제곱의 합이다. 그럼 위의 optimization problem에서 cost 를 최소화 하려면 1차식이 아닌 y = ax^50 + bx^49.... 식의 높은 차원식(곡선이 될것이다?) 을 사용하면 될것이다. 문제는 굉장히 복잡한 식을 써서 training set에서의 cost를 최소로 만들어 봐야 training set을 잘 대변 할 수 있지는 않다. training set을 잘 대변 하는 식을 찾아야 test set에서도 잘 작동하는데, training에 특화된 높은 차원식은 보통 test set에서는 높은 error를 보인다. 이를 이 높은 차수의 식은 overfit되었다고 한다.
다시 말해 cost를 최소로 하는 U, M을 찾는것이 문제이고, 이때 overfit을 방지하기 위해 regularization part를 추가 한 것이다.
algorithm(아주간략)
ALS-WR는 M을 고정하고, U를 optimize하고, U를 고정하고 M을 optimize하는 일을 한 번의 iteration으로 한다.
처음 M은 평균 rating들에서 작은 random number만큼의 차이가 나는 임의의 rate로 initialize되고 iteration을 거치면서 M과 U를 optimize한다.
Recommendation
결국 최종적으로 R^(i, j)를 어텋게 예측 하느냐는 다음과 같다.
ALS-WR를 통해서 R => U, M으로 factorize된다. 다른말로 U는 user를 hidden feature space로, M은 item을 hidden feature space로 project하여 hidden feature space에서의 similarity를 측정하여
user의 item에 예상 R^(i, j)를 계산 하게 된다.
R' = U x transpose(M)이 된다.
Test
mahout-0.6-snapshot을 이용하여 test 해보았다. Cluster는 8 core, 16G서버 10대
| Iteration # | Hidden Feature # | RMSE | Running time |
|---|---|---|---|
| 20 | 30 | 0.9167081037790646 | 2 hour |
