[10주차] Large Scale Machine Learning

※ 본 내용은 Coursera, Machine Learning - Andrew Ng 강의, 강의자료를 바탕으로 작성하였습니다.

 

<Large Scale Machine Learning>

실제 머신러닝 모델을 구현하다보면 상당히 큰 수의 데이터셋을 다룰 일이 생길 것이다.

ex) m = 300,000,000

 

이번 장에서는 그러한 경우 발생하는 문제와 극복하는 방법을 다루었다.

 

우선 해당 문제를 다루기 전에 항상 주의해야될 점이 있다.

 

(1) 적은 수의 데이터셋으로도 충분한 성능의 모델을 구축할 수 있는지.

-> 매우 많은 데이터셋이 아니더라도 충분한 모델을 구축할 수 있다면, 굳이 많은 데이터셋을 사용할 필요가 없다.

 

(2) 많은 데이터가 도움이 될지, bias 문제는 아닌지

-> 앞서 bias 문제의 경우 데이터의 수를 늘리는 것이 모델의 성능에 큰 도움이 되지 않는다는 것을 다뤘다. 따라서 

learning curve 등을 이용하여 bias 문제인지 여부를 검사해봐야 한다.

 

- Stochastic Gradient descent

Linear Regression의 Batchc Gradient Descent 알고리즘

Linear Regression의 cost function과 gradient descent 알고리즘은 위와 같다. 

파라미터를 업데이트시키는 한 iteration마다 i=1~m까지, 모든 데이터에 대해 sum 연산을 수행한다.

*모든 데이터를 대상으로 하기 때문에 batch gradient descent라고 한다.

* gradient descent를 적용하는 모든 알고리즘에 적용이 가능하다.(예시가 linear regression일 뿐)

 

이때 m이 매우 큰 300,000,000 정도인 데이터 셋이라면 위 연산은 매우 expensive한 연산이 된다.

 

이러한 문제를 해결하기 위해 사용하는 알고리즘이 Stochastic Gradient Descent 이다.

Batch vs Stochastic graident descent

Batch Gradient 에서는 한 iteration마다 모든 데이터에 대해 연산을 수행한 후 업데이트를 했다면,

Stochastic gradient descent에서는 한 iteration마다 하나의 데이터에 대해서만 업데이트를 수행한다.

 

즉, iteration 한 번마다 파라미터를 업데이트하는 수식이 다음과 같다.

$ \theta_j :=\theta_j-\alpha(h_\theta(x)-y^{(i)})x^{(i)}_j $, (for all j =0 ~ n)

 

위 수식을 적용하기 전, 데이터를 무작위하게 셔플해야 한다. 이 후 순서대로 하나의 데이터에 대해 업데이트를 진행하는 것이다.

 

전체 데이터에 대해 업데이트하는 과정을 일반적으로 1~10회 정도 수행한다.

 

Batch에서는 매 업데이트마다 300,000,000개의 데이터에 대해 연산을 수행해야 했다면, 

Stochastic Gradient Descent에서는 전체 데이터를 훑는 과정을 대략 1~10회 정도만 수행하는 것이다.

 

Stochastic Gradient Descent 시각화

Stochastic Gradient Descent가 진행되면서 파라미터가 global optimum에 근접해가는 과정은 위 그림과 같다.

다음과 같은 특징을 갖는다.

 

- $ J(\theta)$가 항상 감소하는 것은 아니다.

- global opima 에 근접해가지만, 완벽하게 수렴하지는 않고 그 주변에서 진동한다. 

($ \alpha $ 의 크기가 작을수록 더욱 근접하여 진동한다.)

 

- Mini-Batch Gradient Descent

m이 큰 데이터에 대해 적용할 또 다른 Gradient Descent 알고리즘 중 하나는 Mini-batch gradient descent 알고리즘이다.

Mini-Batch Gradient Descent

 Min-batch gradient Descent 알고리즘은 위와 같다.

Stochastic 방식과 비슷하지만, 매 업데이트에서 b개의 example에 대해서 연산을 수행한 후 업데이트한다.

마치 batch와 stochastic 방식의 중간 형태처럼 연산을 수행한다.

 

그러나 stochstic 방식과 같은 특징을 갖는다. (J 증가 가능, global optima 수렴 x)

 

또한, Mini-batch의 경우 b개의 데이터에 대해 병렬 처리가 가능한 경우에 Stochastic 방식보다 효율적이라고 할 수 있다. 

 

- Stochastic Gradinet Descent Convergence

Batch Gradient Descent에서는 매 iteration마다 $ J(\theta)$의 증가여부를 보면서 debugging을 할 수 있었지만, 

앞서 얘기했듯이 Stochastic Gradient Descent 알고리즘에서는 $ J(\theta)$가 증가할 수 있다.

그렇다면 어떻게 알고리즘의 동작을 확인해야할까?

 

Stochastic Gradient Descent 방식의 debbuging

1000개(예시) 정도의 데이터마다 각 데이터에 대한 cost를 평균으로 계산하여, plot해보는 방식으로 debugging을 수행한다.

 

plotting의 결과로 예상할 수 있는 내용과 그에 따른 해석은 다음과 같다.

 

- ①번 그래프

알고리즘이 정상적으로 작동하는 경우, 파라미터가 점점 최적화되고 cost의 평균은 낮아질 것이다. 

(cost의 평균은 전체 평균이 아닌, 마지막 1000개의 데이터에 대한 cost의 평균이다.)

빨간석으로 덮어진 그래프가 $ \alpha$가 작은 경우이고 그렇지 않은 그래프가 큰 경우로 볼 수 있다.

$\alpha$가 작으면 초기 단계에서는 업데이트가 천천히 되어 더 큰 cost를 보이지만, 앞서 말했듯 global optima에 더욱 근접하기 때문에 iteration이 반복할 수록 상대적으로 cost가 작아진다.

 

- ②번 그래프

평균을 내는 기준을 마지막 1000개로 그린 그래프와 그 위에 5000개를 기준(부드러운 형태, 빨간색)으로 했을 때의 그래프이다.

평균을 내는 기준의 수를 늘릴 수록 더욱 부드러운 그래프가 나온다.

 

- ③번 그래프

②번 그래프와 유사한 경우이다. 평균을 내는 기준을 2-3개 정도로 작게한다면, 수렴해가는 여부를 판단하기 어려울 것이다. 수를 늘리면 밑의 파란 라인처럼 수렴하는게 보일 수 있다.

만약 그렇게 했을 때도 빨간 그래프처럼 점점 작아지지 않는다면 알고리즘의 동작에 문제가 있는 것이다.

$ \alpha$를 조정하거나 아예 모델의 feature를 수정해야 될 수도 있다.

 

- ④번 그래프

오히려 계속하여 증가하는 경우, 더 작은 \$alpha\를 사용해야 한다. 

 

- non-constant alpha?

 

$\alpha$가 작을 수록 global optima에 근접한다면, 다음과 같이 iteration이 늘어날 수록 작아지는 값을 사용하면 더욱 global optima에 가까운 파라미터를 구할 수 있을 것이다.

실제로 위 방법을 사용하기도 하고, 효과가 있는 방법이다.

특히, 결국 알파가 0에 가까워지고 global optima와 근접한 한 값에 수렴할 것이다.

 

그러나 위 식 중 const1과 const2 또한 학습을 위해 조정해야할 새로운 파라미터가 되고, 이는 모델을 까다롭게 만들기 때문에 사용하지 않는 경우도 많다고 한다. 기존 constant 방법도 유효하다.

 

- Online Learning

Online Learning은 실시간으로 들어오는 데이터를 반영하여 모델을 업데이트하는 방식이다. 

Stochastic Gradient Descent 알고리즘에서 한 데이터에 대해 업데이트를 수행했던 것처럼, 들어오는 새로운 데이터에 대해 업데이트를 수행한다. 

Online Learing

주로 대규모 웹 사이트에서 사용하는 기법이다. 

 

 

- Map-Reduce

대규모 데이터에 대한 연산을 처리하는 또 다른 방법으로는 Map-Reduce가 있다.

Batch Gradient descent, Map-Reduce 적용

Batch Gradient Descent 알고리즘을 큰 데이터에 적용할 때 부담이 된 점은 편미분값으로 모든 데이터에 대해 연산을 수행하고 합해야되는 것이다. 

 

그러나 합해야되는 각 값, $(h_\theta(x^{(i)})-y^{(i)})x^{(i)}_j $은 서로 영향을 미치지 않는다. 

따라서 병렬로 계산을 수행하고, 합치면 그만큼 빠르게 알고리즘이 동작할 것이다.

 

위 슬라이드와 같이 400개의 데이터에 대해 sum을 구해야한다면, 4개의 컴퓨터가 각각 100개씩 합을 구하고 최종적으로 다시 그 결과를 합하면 400개의 데이터에 대해 연산을 수행한 결과를 4배 더 빠르게 계산할 수 있게 되는 것이다.

(물론 실제로는 network로 인한 지연이 존재한다,

꼭 network를 이용하는 것이 아니더라도, 멀티 코어를 이용할 수도 있다.)

 

이처럼 큰 데이터셋에 대해 Map-Reduce를 적용하여 연산을 수행하면 알고리즘이 보다 빠르게 동작할 수 있다.

연산이 병렬화될 수 있는 경우라면 Map-Reduce를 적용할 수 있다.

Logistic Regression의 cost function

위 식을 보면 Logistic Regression에 대해서도 적용이 가능하다는 것을 알 수 있다.

 

※ Neural Network의 Forward Propagation과 Backwork Propagation에 대해서도 적용이 가능하다.

Backpropagation

각 데이터별로 forward progation을 수행하고, 다시 backword propagation을 수행하는 과정을 i=1~m까지 적용하고, 누적 합을 계산하는 과정이 최종 편미분값을 얻는 과정이다.

m을 4개의 데이터셋으로 나누고, 각 데이터셋에 대해 서로 다른 컴퓨터가 누적합을 계산하고 다시 그 결과들을 합치는 식으로 병렬화를 할 수 있다.