1. Distributed SGD
Simple parallel SGD for MF
MF에서는 rating이 있는 entry를 이용해 W와 H의 메트릭스를 업데이트 하는 것입니다.
MSGD
각 machine에 대해 분산된 데이터를 각 머신의 W와 H가 학습합니다. 각 머신은 own 데이터를 학습시키고, 머신 각각에 대해 수렴된 W와 H 매트릭스를 평균내면 되기에 서로 소통할 필요가 없습니다. 그러나 여기서 문제가 있는데, 각 머신의 local minimum이 실제 local minimum이라는 보장이 없습니다. 즉, 이를 평균 낸 것이 실제 local minimum이라는 보장이 없는거죠.
ISGD
MSGD의 map과 reduce의 전체 프로세스가 여러번 반복됩니다. 하지만 이 방법론도 문제가 있는데요, 매우 수렴이 느리다는 것입니다. 수렴의 관점에서 평균 내는 것 (average)이 효율적인 방법은 아니기 때문이죠. 그래서 더 적은 반복 횟수로 빠르게 수렴하기 위해서는 새로운 방법이 필요합니다.
여기서 나오는 개념이 Interchangability입니다. 만약 두 개의 entry가 각각 다른 W, H의 열과 행으로부터 업데이트 된다면 interchangable 하다고 볼 수 있습니다. 그런데 만일 같은 행 / 열로부터 업데이트 된다면 이는 interchangable 하지 않다고 말합니다. Entry 각각을 업데이트 하는 것의 순서가 서로 영향을 줄 수 있기 때문입니다.
Distributed SGD
W, H, V 행렬이 있습니다. (블록) 블록의 개수는 머신의 개수와 동일합니다. 다른 머신은 다른 파라미터를 읽고 업데이트(write) 합니다(Interchagable). 이렇게 할 경우 충돌이 발생하지 않으며, 위에서 문제가 되었던 average 계산을 할 필요가 없습니다. 참고로 V는 weighting matrix 입니다. 예를 들어 W1 W2 W3, H1 H2 H3, V1 V2 V3가 있으면 W1 H1 V1는 동일한 머신에 할당이 됩니다. 각자 파라미터를 각각 업데이트 하는 것이 핵심입니다.
그렇다면 Interchanable V 블록들은 그럼 어떻게 될까요? Set of interchangable block 들은 Sub-iteration에 V 블락이 1번만 사용될 수 있도록 합니다.
DSGD의 장단점
MSGD와 ISGD는 average step이 있었는데요, 이와 달리 averaging step이 없기에 더 빠르게 수렴할 수 있다는 장점이 있습니다. 또한 모든 매트릭스를 메모리에 올리지 않고, 각 머신은 적은 크기의 factor, rating matrix를 메모리에 올리면 되기 때문에 더욱 메모리 효율적이라고 볼 수 있습니다.
하이퍼파라미터가 많다는 것이 단점입니다. (step size, regularization parameter, rank)
2. Alternating Least Square (ALS)
우리의 손실함수를 생각해보면, argmin L(V,W,H) 인데, 이는 convex 문제가 아닙니다. ALS의 핵심은 W와 H를 번갈아 고정함으로써 convex한 문제로 바꿔서 푸는 것이라 할 수 있습니다. 만약 H를 고정한다면 H의 non-missing entries가 있는 V의 i번째 행을 이용하면 됩니다.
즉, 수도코드는 다음과 같습니다. 먼저 W와 H를 랜덤하게 초기화하고, H를 고정한채 W 업데이트 & W를 고정한채 H를 업데이트. 이 과정을 여러 번 수렴할 때까지 반복하면 됩니다. Loss 함수는 점차 감소하는 방향으로 진행이 되며 증가하지 않습니다. 이유는 H를 고정한채
W를 업데이트 하는 것은 H가 고정된 이 상태에서는 optimal 하기 때문입니다. 반대의 경우도 마찬가지입니다. H를 고정하고 W를 업데이트 한다면 H를 읽을 필요가 없습니다(no read).
만일 머신이 3개이고 H를 업데이트 한다면, H1 H2 H3가 있는데, 각 머신에서 업데이트 되는 H1 H2 H3는 다른 머신 2개에 공유 됩니다. 예를 들어 머신1에서 H1를 업데이트 한다면 머신2와 머신3에 H1는 broadcast 되고, 이 때 충돌은 발생하지 않습니다.
이처럼 W의 i번째 행을 업데이트 한다면, rating matrix V의 i번째 행이 업데이트 되는 것이고 H 전체가 쓰입니다. 이때도 마찬가지로 W는 read 할 필요가 없습니다.
하이퍼파라미터가 적다는 장점이 있습니다 (step size 필요 없음). 대신, 연산 비용이 크다는 단점이 있습니다. Main Memory에 모든 W를 한번에 로드하는게 .
