(머신러닝) 23 - Map Reduce

map reduce 는 large scale dataset 을 다루는 경우 사용하는 방법들 중 하나다.

large scale dataset을 다루는 방법들에는 stochastic gradient descent나 mini-batch gradient descent가 있었다.

이 알고리즘들은 parameter를 update 하기위해 한 대의 컴퓨터만 사용했다.

이번에 소개할 Map Reduce는 여러대의 컴퓨터가 데이터를 나누어 가져가서 학습을 시켜 다시 master computer로 결과를 보내주어 합치는 알고리즘이다.

 

1. Map Reduce

---

 

Batch Gradient Descent

$\\for\quad j=1:n\\ { \theta_{j}=\theta_{j}-\frac{\alpha}{400,000,000} \sum_{i=1}^{400,000,000}(h_{\theta}(x^{(i)})-y^{(i)})x_{j}^{(i)} }$

 

Map-Reduce

Map Reduce에서는 여러대의 컴퓨터가 학습 데이터를 등분하여 학습 parameter를 계산한다.

아래는 총 4대의 컴퓨터가 4억개의 데이터를 각각 1억개씩 가져가서 학습을 시키는 경우이다.

$temp^{(1)}_{j}=\sum_{i=1}^{100,000,000}(h_{\theta}(x^{(i)})-y^{(i)})x_{j}^{(i)}$

$temp^{(2)}_{j}=\sum_{i=100,000,001}^{200,000,000}(h_{\theta}(x^{(i)})-y^{(i)})x_{j}^{(i)}$

$temp^{(3)}_{j}=\sum_{i=200,000,001}^{300,000,000}(h_{\theta}(x^{(i)})-y^{(i)})x_{j}^{(i)}$

$temp^{(4)}_{j}=\sum_{i=300,000,001}^{400,000,000}(h_{\theta}(x^{(i)})-y^{(i)})x_{j}^{(i)}$

위와 같이 계산된 값들이 master server에 전송이 되면 최종적으로 parameter는 다음과 같이 update 된다.

$\theta_{j}:=\theta_{j}-\frac{\alpha}{400,000,000}(temp^{(1)}_{j}+temp^{(2)}_{j}+temp^{(3)}_{j}+temp^{(4)}_{j})$

이 작업은 완전히 Batch Gradient Descent와 동일하다. 단지 여러대의 컴퓨터가 데이터를 나누어 계산을 하기때문에 계산 속도 성능이 4배로 향상된 것일 뿐이다.