Collaborative filtering

협업 필터링이라고도 부른다.   행렬 분해(matrix decomposition)를 활용한 상품 추천 시스템(recommendation system)에 사용된다.  또는 아주 큰 데이터(big data)에 내재되어 있는 내부 성질을 파악하기 위한 마이닝(mining) 알고리즘으로도 사용될 수 있다.


웹 Market에서 상품을 팔면서 구매자의 만족도를 조사하였다.

6명의 구매자에 대해 5개의 상품을 0~5점으로 나누어 만족도가 높을수록 5점에 가까운 점수를
주게 하였더니 아래와 같은 행렬이 얻어졌다.

>>A=[2 3 5 0 0; 1 2 4 0 0; 4 5 4 0 0; 0 1 0 3 4; 1 0 0 4 5; 0 0 0 5 4];
>> A

A =
     2     3     5     0     0
     1     2     4     0     0
     4     5     4     0     0
     0     1     0     3     4
     1     0     0     4     5
     0     0     0     5     4

행렬에서 행(row)은 구매자이고 열(column)은 개별 상품에 해당한다.

행렬을 보고 대략 추정해보면 1~3번 상품에 대해 호의적인 사용자들과
4~6번의 상품에 호의적인 사용자들의 두 그룹으로 나누어진다는 것을 알 수 있다.


A행렬을 특이값 분해(SVD, singular value decomposition)해보면

>>[u,d,v]=svd(A)

u =
   -0.4719    0.3337   -0.4308    0.0716    0.1067   -0.6810
   -0.3382    0.2434   -0.5548    0.1188   -0.0594    0.7078
   -0.5811    0.3908    0.6720   -0.1899   -0.0353    0.1436
   -0.3004   -0.3804    0.0835    0.4957   -0.7101   -0.0901
   -0.3610   -0.5078    0.1044    0.3629    0.6803    0.0801
   -0.3234   -0.5235   -0.1927   -0.7532   -0.1299   -0.0100

d =
   10.6983         0         0         0         0
         0   10.1159         0         0         0
         0         0    2.4316         0         0
         0         0         0    1.1504         0
         0         0         0         0    0.9895
         0         0         0         0         0

v =
   -0.3709    0.1944    0.5659   -0.1171    0.7005
   -0.4952    0.3026    0.4284   -0.0013   -0.6925
   -0.5643    0.4157   -0.6929    0.0641    0.1564
   -0.3704   -0.5724   -0.1216   -0.7190   -0.0592
   -0.4020   -0.6084    0.0349    0.6821    0.0419

세개의 행렬 u, d, v가 얻어진다.

d행렬 내의 특이값을 보면 2개의 성분이 크고 나머지는 작다.
즉, A행렬의 내재된 성분이 2개가 중요하다는 의미이다.


2개의 성분과 그에 해당하는 u, v행렬의 값만을 이용하여 A행렬을 다시 재생해 보면

>> vt = v';
>> u(:,1:2)*d(1:2,1:2)*vt(1:2,:)

ans =
    2.5285    3.5220    4.2523   -0.0619   -0.0241
    1.8206    2.5374    3.0657   -0.0693   -0.0437
    3.0741    4.2755    5.1518    0.0396    0.0935
    0.4441    0.4272    0.2140    3.3931    3.6334
    0.4338    0.3579    0.0438    4.3709    4.6782
    0.2538    0.1107   -0.2491    4.3124    4.6127

이고 A행렬과 비교해 보면 값이 비슷하다(잘 재생된다).

내재된 성분의 의미를 파악해 보자.

>> u(:,1:2)*d(1:2,1:2)

ans =
   -5.0490    3.3752
   -3.6186    2.4625
   -6.2169    3.9535
   -3.2142   -3.8482
   -3.8621   -5.1373
   -3.4597   -5.2956

행렬의 행은 사용자를 표현하고, 열은 두개의 내재된 성질에 대한 것이다. 즉, 사용자는 2개의 그룹으로 나누어지며
1~3번 사용자는 첫번째 성질에 속하고, 4~6번 사용자는 두번째 성질에 속하는 정도가 크다 (행렬 요소값의 절대치 크기만 보자).

>> vt(1:2,:)

ans =
   -0.3709   -0.4952   -0.5643   -0.3704   -0.4020
    0.1944    0.3026    0.4157   -0.5724   -0.6084

5개의 상품(각 열)에 대해 첫번째 성질(사용자 그룹)은 1~3열의 상품에 대한 선호도가 높고, 2번째 성질은 4~5열의 상품에 대한 선호도가 높다.


이상과 같이 행렬을 분해해 주는 방법인 SVD를 이용하면 데이터에 내재되어 있는 의미 파악이 가능하다. 이를 이용하면 상품 추천시스템을 만들 수 있다.




이제 어떤 사람의 구매 만족도를 조사하였더니 아래와 같은 데이터가 주어졌다.

B=[3 ? 4 ? 2]

이 사용자는 상품 2, 4를 아직 구매하지 않았다.
이 사람에게 상품 2와 4 중에서 어떤 것을 추천할 것인지 계산해 보자.

먼저 평가가 있는 세개의 상품에 대해 평균을 구해 '?'위치에 대치하자.
(3+4+2)/3=3이므로 3을 대입한다.

>>B=[3 3 4 3 2];


이 사용자를 A행렬의 마지막 행에 추가하고 SVD를 다시 수행한다.

>> C=[A; B]

C =
     2     3     5     0     0
     1     2     4     0     0
     4     5     4     0     0
     0     1     0     3     4
     1     0     0     4     5
     0     0     0     5     4
     3     3     4     3     2

>> [u,d,v]=svd(C)

u =
   -0.4049    0.3207    0.4210   -0.1967   -0.0883    0.7109   -0.0642
   -0.2900    0.2341    0.5467   -0.2343    0.0295   -0.6759   -0.2227
   -0.4980    0.3749   -0.6820   -0.0475    0.1547   -0.0733   -0.3388
   -0.2424   -0.3885   -0.0945   -0.6518    0.4371    0.0039    0.4068
   -0.2938   -0.5175   -0.1111   -0.1982   -0.7383   -0.0344   -0.2190
   -0.2644   -0.5321    0.1912    0.4180    0.4667    0.1088   -0.4540
   -0.5376    0.0046    0.0290    0.5151   -0.1157   -0.1394    0.6418

d =
   12.6750         0         0         0         0
         0   10.1164         0         0         0
         0         0    2.4328         0         0
         0         0         0    1.4264         0
         0         0         0         0    1.0250
         0         0         0         0         0
         0         0         0         0         0

v =
   -0.3943    0.1850   -0.5604    0.3711   -0.5988
   -0.4844    0.2896   -0.4361   -0.2823    0.6416
   -0.5781    0.4011    0.6907   -0.0352   -0.1635
   -0.3816   -0.5814    0.1295    0.6218    0.3360
   -0.3606   -0.6188   -0.0456   -0.6282   -0.3004



이제 내재된 2개의 성질을 이용하여 원래 행렬을 재생해 보면

>> vt=v';
>> u(:,1:2)*d(1:2,1:2)*vt(1:2,:)

ans =
    2.6239    3.4256    4.2679    0.0722   -0.1568
    1.8875    2.4663    3.0746    0.0254   -0.1403
    3.1904    4.1556    5.1695    0.2037   -0.0706
    0.4845    0.3498    0.1994    3.4574    3.5400
    0.5003    0.2878    0.0530    4.4650    4.5828
    0.3258    0.0642   -0.2220    4.4083    4.5394
    2.6959    3.3143    3.9577    2.5738    2.4292


마지막 사용자의 2, 4번째 상품에 대한 평가치는 3.3143>2.5738이므로 2번째 상품을 추천한다.



References

[1] 한국정보처리학회, Tutorial(빅데이터 분석 및 소셜 컴퓨팅), 2014.

FastSLAM

EKF SLAM의 문제점

- 2차원 평면상에서 $K$개의 landmark 존재.  LM 파라미터: $(x_i, y_i)$

- robot pose: $(x, y,  \phi)$

- 합하면 $2K+3$개의 인자

- Kalman filter를 통해 이것들을 추정하면 mean값을 $2K+3$개를 유지

  Covariance matrix는 $(2K+3)^2$크기가 요구
- LM의 수가 늘어 감에 따라 유지해야 하는 파라메터의 수가 급격히 증가(계산량 증가)

FastSLAM에서의 개선

- Landmark는 로봇의 pose가 주어진다면 상호 독립이라 가정

- 각 landmark에 대해 $2\times2$ covariance matrix

  전체 인자의 수: $K(2+2\times2)+3$

Robot poses: $s^t=s_1, s_2, ...,s_t$
Robot actions: $u^t=u_1,u_2,...,u_t$
Observations: $z^t=z_1,z_2,...,z_t$
Landmarks: $\boldsymbol{\theta}=\theta_1,...,\theta_k$
Correspondence: $n^t=n_1,n_2,...,n_t$
- $n_t=k$는 $z_t$가 $\theta_k$의 관찰 값임을 의미
- landmark는 한번에 하나씩 관찰된다고 가정

그림에서 shade영역은 $t_1\sim$현재까지의 로봇의 경로이다.
만일 로봇의 실제 경로를 안다면(즉 shade영역) LM $\theta_1$과 $\theta_2$는 서로 독립이다.


SLAM 문제
- action model: $p(s_t|u^t,s^{t-1})$
- sensor model: $p(z_t|s_t,\boldsymbol{\theta},n_t)$

SLAM 문제는 $z^t, u^t, n^t$가 주어질 때 $\boldsymbol{\theta},s^t$를 추정하는 문제이다.  Bayes theory를 이용하면

$p(s^t,\boldsymbol{\theta}|z^t,u^t,n^t)=
{{p(\boldsymbol{\theta},s^t,z^t,u^t,n^t)} \over {p(z^t,u^t,n^t)}}={{p(\boldsymbol{\theta}|s^t,z^t,u^t,n^t)p(s^t,z^t,u^t,n^t)} \over {p(z^t,u^t,n^t)}}$
$=p(\boldsymbol{\theta}|s^t,z^t,u^t,n^t)p(s^t|z^t,u^t,n^t)$

landmark의 독립가정$^{주1}$에 따라
$p(s^t,\boldsymbol{\theta}|z^t,u^t,n^t)
 =p(s^t|z^t,u^t,n^t)\prod_k^{}p(\theta_k|s^t,z^t,u^t,n^t)$

- trajectory 추정 $p(s^t|z^t,u^t,n^t)$
- robot의 자세 추정은 particle filter를 이용하고, 각 particle에 대한 landmark위치와 분산의 갱신의 EKF를 사용
- particle당 $K$개의 Kalman filter가 있으므로 particle의 수가 $M$개라면 갱신과정의 시간 복잡도는 $O(MK)$이다.



(주1) 독립가정에 따라
$p(\boldsymbol{\theta}|s^t,z^t,u^t,n^t)=...$



References
[1] M. Montemerlo, FastSLAM: A Factored Solution to the Simultaneous Localization and Mapping Problem With Unknown Data Association, CMU-CS-03, Ph.D. thesis, 2003.
[2] Benjamin Kuipers, FastSlam, lecture notes, CS 344R/393R: Robotics.