Edit this page

Data Analysis ML 10: Stochastic Gradient, Synthetic Data, Ceiling Analysis

ML 10: Stochastic Gradient, Synthetic Data, Ceiling Analysis

이번 주에는 mini-batch, stochastic graident descent, online learning, map-reduce 등의 개념에 대해 배운다.

Learning With Large Datasets

(http://blog.csdn.net/linuxcumt)

왜 그렇게 큰 데이터 셋이 필요할까? 좋은 퍼포먼스를 얻기 위한 한 가지 방법이, low bias 알고리즘에 massive data 를 활용해 훈련하는 것이기 때문이다.

(http://blog.csdn.net/linuxcumt)

그러나 커다란 데이터 셋을 연산하기 위해서는 연산비용이 정말 비싸다. 예를 들어 m = 100,000,000 이라 하면 gradient 를 계산하기 위해 매번 k * m 의 연산이 필요하다.

따라서 모든 데이터를 이용해 알고리즘을 훈련하기 보다는, 랜덤하게 고른 작은 서브셋에 대해서 알고리즘을 개발하고, 이후에 전체 데이터에 대해서 훈련하는 방법을 쓰기도 한다.

그러면 m 이 작아도 알고리즘이 충분히 잘 훈련된다는 것을 어떻게 보장할까? 이는 learning curve 를 그려보면 된다.

위 슬라이드에서 우측 하단은 high bias 알고리즘인데 m 을 많이 투입해도 별다른 이득이 없으므로 적당한 수준에서 m 을 정하면 된다.

물론 만든 알고리즘이 우측처럼 high bias 로 나오면, 좀 더 자연스러운 생각은 hidden layer 를 추가한다거나, 새로운 feature 를 도입해서 bias 를 낮추는 것이다.

Stochstic Gradient Descent

(http://blog.csdn.net/linuxcumt)

gradient descent 를 이용하는 linear regression 에서

$h_\theta(x) = \sum_{j=0}^n \ \theta_jx_j$

$J_{train}(\theta) = {1 \over 2m} \sum_{i=1}^m\ (h_\theta(x)^{(i)} - y^{(i)})^2$

이미 언급했듯이 batch gradient descent 의 문제는, m 이 크면 J 의 연산이 어마어마하게 많아진다는 것이다. 매 스텝마다 m 을 읽고, 계산값을 저장하기 때문이다.

(http://blog.csdn.net/linuxcumt)

이 문제를 해결하기 위해 stochastic gradient descent 에서는 한 턴에 한 쌍의 x, y 에 대해서만 gradient 를 계산한다.

batch gradient decsent 에서는 한 턴마다 모든 모든 쌍의 x, y 에 대해 gradient (= theta_j) 를 계산 했었다.

$cost(\theta, (x^{(i)}, y^{(i)})) = {1 \over 2}\ (h_\theta(x^{(i)} - y^{(i)})^2$

$J_{train}(\theta) = {1 \over m} \sum_{i=1}^m cost(\theta, (x^{(i)}, y^{(i)}))$

라고 하면

- Randomly shuffle dataset  
- Repeat for i = 1 to m
  - 0_j := 0_j - a * derivative of cost(0, (xi, yi)

즉 J_train 의 미분 대신에 cost 의 미분값을 이용해서 연산을 줄이는 방법이다. 이 때 데이터가 이미 랜덤하게 섞였다는 점을 기억하자. 기하학적으로 보면

(http://blog.csdn.net/linuxcumt)

batch 에서는 올바른 방향을 향해 가지만, 보폭이 좀 좁다. stochastic 은 이리 갔다, 저리 갔다 하지만 결국에는 최저점을 향해 간다. 다만 global optima 에 도달하지 못하고 그 근처에 도착할 수 있다.

m 이 굉장히 크면, repeat 부분의 루프를 1번만 돌려도 될 테지만, 작으면 여러번 돌려서 최대한 좋은 퍼포먼스를 내도록 훈련시킬 수 있다.

Min-Batch Gradient Descent

(http://blog.csdn.net/linuxcumt)

Batch gradient descent: Use all m examples in each iteration
Stochastic gradient descent: Use 1 example in each iteration
Batch gradient descent: Use b examples in each iteration

$\theta_j := \theta-j - {\alpha \over b} \sum_{k = i}^{i + b - 1} (h_\theta(x^{(k)}) - y^{(k)}) x_j^{(k)}$

(http://blog.csdn.net/linuxcumt)

b 는 보통 2 - 100 사이의 값이기 때문에 batch 보다 훨씬 빠르다. 또한 vectorization 을 이용하면 gradient computation 을 partially parallelize 할 수 있기 때문에 stochastic 보다 더 빠를 수 있다. ~~병렬화의 미덕~~

단점으로는 추가적인 파라미터 b 가 필요하다는 점이다. 그러나 vectorization 을 잘 이용하면 더 빨라지므로 문제 없다.

Stochastic Gradient Descent Convergence

(http://blog.csdn.net/linuxcumt)

convergence 를 검증하는 방법으로, 훈련시키는 동안 얻은 cost(0, (xi yi) 평균값을 이용해 플롯을 그릴 수 있다.

(http://blog.csdn.net/linuxcumt)

stochastic 은 global optimum 을 찾아내지 못할 수도 있기 때문에, 그 주변에서 알짱거릴 수도 있다.

더 많은 m 을 투입하면, 까끌거리는 선보다 좀 매끄러운 곡선을 얻을 수도 있다.

때때로 알고리즘이 전혀 학습하지 못하는 것 처럼 보일수도 있는데, 그럴 경우 m 을 더 투입하면 좀 경사가 낮은 커브로 조금씩 decreasing 할 수 있다. 이를 보면 결국 훈련되긴 하는데, 평균값을 플랏으로 그리니 들쭉날쭉 해 보이는 것이다. (물론 학습하지 못하는 경우도 있다. m 을 더 늘려서 확인해 보자.)

cost 값이 증가한다면 더 작은 learning late 값을 이용하자.

(http://blog.csdn.net/linuxcumt)

learning rate 와 관련해서 위 슬라이드처럼 식을 만들면, 이터레이션 넘버가 천천히 증가하면서 alpha 가 감소해 converge 하는 결과를 얻을 수 있다.

If we reduce learning rate alpha (and run stochastic gradient descent long enough), it’s possible that we may find a set of better parameters than with large alpha