[Machine Learning] Gradient Descent with Large Datasets

해당 내용은 Andrew Ng 교수님의 Machine Learning 강의(Coursera)를 정리한 내용입니다.

 

이번 강의에서는 대규모의 머신러닝에 대해 알아보겠다. 알고리즘이지만, 빅데이터 관점에서 보는 것이다.

최근 5~10년 전 머신러닝을 되돌아보면, 최근 학습알고리즘이 훨씬 더 높은 성능을 보이는 이유 중의 하나는 훈련할 수 있는 엄청난 양의 데이터 때문이다. 이번에는 이러한 대규모의 데이터가 있을 때, 처리하는 알고리즘에 대해서 알아보자.

 

- Learning With Large Datasets

우리는 이전에 이미 머신러닝의 성능을 높이는 방법 중의 하나가 더 많은 데이터를 학습하는 것(Low Bias일 경우)이라는 것을 배웠었다. 위와 같은 비교를 통해서 머신러닝에서 가장 좋은 알고리즘이 중요한 것이 아니라 얼마나 많은 데이터를 가지고 있는 것이 더 중요하다는 것을 알았다. 따라서 우리는 많은 데이터 세트에서 학습을 해야하기를 원하는데, 이러한 대용량 데이터 세트를 학습하는 데에는 한 가지 큰 문제가 있는데, 그것이 바로 계산적인 부분에 대한 문제(Computational problem)이다.

 

만약 우리가 100,000,000개의 데이터 세트를 학습한다고 가정해보자. 이 숫자는 실제 우리가 다루어야 하는 많은 데이터의 실질적인 양이다. 이러한 데이터를 가지고 Linear Regression 모델이나 Logistic Regression을 학습하길 원하고, 우리는 Gradient Descent를 적용해야한다. \(m = 100,000,000\)이므로 우리는 Gradient Descent 한 단계를 수행하기 위해서 100,000,000번의 덧셈을 해야한다. 

100,000,000번의 계산을 하는데 드는 계산적인 비용이 너무 크기 때문에 우리는 더 효율적인 방법을 찾아볼 것이다.

예를 들어, 무작위로 1,000개의 데이터만 추출해서 학습을 했을 때, 성능이 좋다면 우리는 전체 데이터세트를 가지고 학습을 할 필요는 없을 것이다. 

이것은 아래처럼 Learning Curve를 그려서 확인할 수 있다.

위 그래프는 High Variance 형태의 Learning Curve이다. 따라서 더 많은 데이터를 사용해서 학습을 하면 성능이 좋아질 것이라고 볼 수 있다.

위 Learning Curve는 High Bias 형태의 그래프이다. 이런 경우에는 우리가 더 많은 데이터를 사용해 학습한다 하더라도 성능의 향상이 보장되지 않는다. 따라서 더 많은 데이터를 사용하는 것보다 그냥 1000개의 데이터를 유지하는 것이 좋을 것이다.

 

만약 High Bias와 같은 상황에 있다면, feature를 추가하거나, NN에서 Hidden Unit을 추가하는 등의 방법이 있을 수 있다. 이런 조치를 취한다면 Hign Variance의 그래프에 가까워지고 우리는 더 많은 데이터를 사용하면 이제는 성능이 좋아질 것이라고 예상할 수 있다.

 

대규모 머신러닝 시스템에서 큰 데이터세트를 다루기 위해서 우리는 합리적이고 효율이 높은 두 가지의 방법을 알아볼 것이다. 첫 번째 방법은 Stochastic Gradient Descent이고, 두번째는 Map Reduce라는 방법이다.

 

- Stochastic Gradient Descent

많은 학습 알고리즘에서 우리는 Cost Fucntion과 최적화를 통해서 알고리즘을 유도했다. 그리고 Gradient Descent와 같은 방법을 사용해서 Cost Fucntion을 최소화하는 알고리즘을 사용했다. 우리가 많은 양의 데이터를 다룰 때, Gradient Descent는 연산 비용이 매우 클 것이다. 

우리가 Linear Regression 모델을 학습하고, Gradient Descent를 사용한다고 가정해보자. 우리의 Hypothesis와 Cost Function은 아래와 같을 것이고, Cost Function은 convex(bow-shaped function)일 것이다. 오른쪽은 \(\theta_0, \theta_1\)에 대한 J 함수의 그래프이다. 그리고 Gradient Descent도 다음과 같다.

우리가 이미 잘 알고있듯이, 아래 그래프 처럼 Gradient Descent를 매 iteration마다 반복하면 우리는 global minimum으로 향하게 되어서 최적의 parameter를 찾을 것이다. 

이제 문제는 \(m\)이 너무 크다는 것이다. 따라서 모든 m에 대해서 덧셈을 진행해야하므로 기울기를 계산하는 연산 비용이 너무 크다. 이렇게 모든 m에 대해서 Gradient Descent를 Batch Gradient Descent라고 부르기도 한다. Batch라는 용어는 모든 Trainig examples을 살펴본다는 것을 의미한다. 좋은 이름은 아니지만, 사람들은 이것을 특정 버전의 Gradient Descent라고 부르는 것이다.(...?)

만약 3억명에 대한 조사 기록이 디스크에 저장되어 있다면, 우리는 미분항을 계산하기 위해서 3억개의 기록을 모두 컴퓨터 메모리로 읽어야한다는 의미이다. 모든 기록을 컴퓨터 메모리에 저장할 수 없기 때문에 이러한 기록을 컴퓨터를 통해 스트리밍해야하고, 우리는 미분을 계산하기 위해서 합을 축적해야한다. 이런 작업이 다 완료되면 Gradient Descent를 사용할 수 있고, 한 단계가 완료되는 것이다. 

 

그래서 많은 데이터 세트를 사용할 수 있는 더 효율적인 알고리즘인 Stochastic Gradient Descent를 살펴보자. 

Stochastic Gradient Descent의 Cost Function은 전체 m에 대한 것이 아니라 i번째 example의 Cost만을 의미한다. 즉, 모든 m의 cost를 다 더하는 것이 아니라 한 개의 샘플의 Cost만을 가지고 Cost Function으로 사용한다. 따라서 미분항을 계산할 때, 모든 m에 대해서 미분항을 계산할 필요가 없고, i-th example에 대한 미분항만 계산하면 되는 것이다.

알고리즘을 정리하면 다음과 같다.

첫 번째로는 Training Example의 순서를 섞는다. 그리고 Gradient Descent를 적용하는데, 하나의 example에 대한 미분항만을 사용해서 parameter를 계산한다. 기존 방법처럼 모든 example에 대해서 미분항을 계산하는 것이 아닌 하나의 example만 계산해서 m번 반복하는 것이다.

 

오른쪽 그래프처럼 보통 Global Minimum을 향해 수렴하지만, 항상 그렇지는 않다. Batch Gradient Descent처럼 동일한 곳에 수렴하지는 않고 Global minimum 주위를 방황하게 된다. 하지만 이것은 큰 문제가 되지 않고, global minimum에 꽤 가까이 있다면, 꽤 괜찮은 Hypothesis라고 볼 수 있다.

보통 1 ~ 10회 정도 반복하고, 전체 Training Example에 대한 Gradient Descent를 하나의 example에 대해서만 미분항을 구하고 진행하기 때문에 Batch Gradient Descent에 비해서 정확도는 떨어지지만 속도를 향상되었다.

 

- Mini-Batch Gradient Descent

Stochastic Gradient Descent와 유사한 Mini-batch Gradient Descent에 대해서 알아보자.

Mini-batch는 Batch와 Stochastic의 중간에 위치한 Gradient Descent라고 할 수 있다. 각 Iteration마다 b examples만을 사용하기 떄문이다. 보통 b는 2 ~ 100으로 선택한다.

idea는 다음과 같다. 만약 b = 10이라고 정한다면, 우리는 Gradient Descent를 구할 때, i ~ i+9 example에 대한 미분항만을 구해서 parameter를 최적화한다. 

 

전체 알고리즘은 다음과 같다.

모든 m에 대해서 10개씩 뽑아서 parameter를 최적화해 나가는 것이다. 

 

Mini-batch Gradient Descent에서 한 가지 단점은 추가해야될 변수 b가 있다는 것이다. Mini-batch의 크기는 조절해야하므로 이것 때문에 시간이 걸릴 수 있다. 하지만 Vectorization가 잘된 구현이 있다면 이 방법은 Stochastic Gradient Descent보다 더 빠를 수도 있다. 일반적으로 b = 10을 사용하지만 2 ~ 100까지의 다른 값들도 꽤나 합리적이다. 따라서, 우리는 b를 선택하고 좋은 벡터화된 구현을 사용하면 다른 두 가지의 Gradient Descent보다 더 빠르게 계산될 수 있다.

 

 

- Stochastic Gradient Descent Convergence

우리는 방금 Stochastic Gradient Descent 알고리즘을 배웠고, 여기서 중요한 것은 이 알고리즘이 수렴하고 있는지 확인하는 것이 중요하다. 동일하게, 우리가 Learning Rate \(\alpha\)를 조절하는 것도 중요하다. 이번에는 이것들을 위한 테크닉에 대해서 알아보자.

 

Batch Gradient Descent를 수행할 때, 수렴하는 지 확인하기 위해서 우리는 \(J_{train}(\theta)\)의 그래프를 그려서 매 Gradient Descent마다 감소하는지 확인을 했었다.

 

Stochastic Gradient Descent에서는 알고리즘이 수렴하는지 확인하기 위해서, 다음과 같은 방법을 사용한다.

매 iteration마다 계산된 cost를 그리는 것이 아니라, 매 1000번의 iteration마다 그 1000번의 cost의 평균을 구해서 그래프에 나타내는 것이다.

 

그래프를 그려보면 노이즈가 심하거나, 매 iteration마다 감소하지 않을 수 있다.

 

위 그래프에서 빨간색 그래프의 Learning Rate가 파란색 그래프보다 작다. 위 그래프는 결국 수렴하는 방향으로 가고 있지만, Learning Rate가 작다면 더 늦게 감소하는 모습을 보이고 있다. 우리가 Stochastic Gradient Descent에서 Global minimum 주변을 멤돈다는 것을 알고 있기 때문에, 결국에는 작게 진동하는 것을 볼 수 있다. 때때로, Learning Rate가 작을 때 더 좋은 parameter값을 얻을 수 있다.

 

위 그래프에서 파란색 그래프는 1000 iterations 마다 평균을 낸 것이고, 빨간색 그래프는 5000 iterations 마다 평균을 낸 그래프이다. 따라서 빨간색이 조금 더 곡선에 가까운 모습을 보여주고 있다.

 

위 그래프에서 파란색 그래프는 1000 iterations 마다의 평균인데, noisy한 모습을 보여주고 있어서 Cost의 경향을 알 수가 없다. 파란색 그래프는 실제로는 빨간색 그래프와 같은 경향을 보일 수 있는데, 이것을 확인하려면 평균 주기를 5000 iterations로 증가시키면, 빨간색이나 보라색 그래프와 같이 확인할 수 있을 것이다. 

만약, Cost가 평평한 모습을 보인다면, 우리는 학습 알고리즘이 잘 동작하지 않는다는 것을 알 수 있고, Learning Rate를 변경하거나 feature를 변경하는 등, 알고리즘의 다른 부분을 변경해야 한다.

 

마지막 그래프는 발산하는 그래프의 모습을 보여주고 있다. 이런 경우에는 더 작은 Learning Rate를 사용해야 한다.

 

 

따라서 그래프가 너무 noisy하거나 진동이 심하면 평균을 내는 example 수를 늘리면, 전체적인 경향을 더 잘 볼 수 있다. 그리고 Cost가 증가하고 발산한다면 더 작은 Learning Rate \(\alpha\)를 사용하면 된다.

 

마지막으로 Learning Rate에 대해서 조금 더 살펴보자.

실제 Stochastic Gradient Descent를 진행하면 오른쪽 그래프처럼 Global minimum을 향해 왔다갔다 하면서 접근하게 되고, 실제로 수렴하지는 않고 대신 minimum 주위를 계속 멤도는 모습을 보일 것이다. 따라서, 정확한 global minimum이 아닌 global minimum에 가까운 값을 얻게 된다.

이러한 문제를 해결하기 위해서 일반적으로 일정한 상수인 Learning Rate를 천천히 감소시키는 방법이 있을 수 있다. 따라서 \(alpha\)를 설정하는 일반적인 방법은 다음과 같이 설정하는 것이다.

\[\alpha = \frac{\text{const1}}{\text{iterationNumber } + \text{const2}}\]

const1과 const2는 좋은 성능을 얻기 위한 역할을 하는 추가 매개변수가 된다.

 

사람들이 const1과 const2를 사용하지 않는 이유는 추가적인 매개변수를 다루어야하고, 알고리즘이 더 복잡해질 수 있기 때문이다. 하지만 매개변수를 잘 조정하면 Learning Rate가 서서히 작아지면서 global minimum에 수렴할 때까지 점점 더 작은 step을 수행할 것이다. 

결과적으로 Learning Rate를 0으로 천천히 감소시켜가면 더 좋은 Hypothesis를 얻을 수 있다.

 

 

- Online Learning

이번에는 Online Learning Setting이라 불리는 머신러닝 Setting에 대해서 알아보자.

Online Learning setting은 알고리즘을 학습하는데, Training Data가 계속해서 수집될 때 모델링 할 수 있게 한다.

오늘날 많은 웹사이트에서 방문하는 유저로부터 학습하기 위해서 다양한 Online Learning 알고리즘을 사용한다. 

 

한 가지 예로, 배송 서비스 웹사이트에 출발지와 도착지를 특정하면 배송비를 받고 배송을 해준다는 견적을 제공한다. 그러면 사용자는 우리의 배송 서비스를 선택할 수도 있고 아닐 수도 있다.(y = 1 or 0)

우리가 이 웹사이트를 계속 동작시킬 때, Online Learning 알고리즘은 계속해서 반복한다. 그래서 최적의 parameter는 계속 업데이트될 것이다. 여기서 Online Learning 알고리즘은 실제로 고정된 training set을 사용하는 것이 아니라, 우리가 새로운 example을 얻었을 때, 우리는 이 example을 가지고 학습하고, 버린다. 그래서 한번 사용된 example은 다시 사용하지 않는다. 위에서 인덱스 i가 삭제된 이유가 바로 이런 이유 때문이다.

 

실제로 사용자가 지속적으로 유입되는 웹사이트가 운영될 때, 이런 종류의 알고리즘은 꽤나 합리적인 알고리즘이다. 데이터가 너무나 많고 계속해서 제공된다면 학습한 example을 두번 이상 볼 필요가 없다. 물론 만약 사용자가 적다면 위와 같은 online learning 알고리즘보다 고정된 training set에 모든 데이터를 저장하고, 이 training set에 대해서 학습 알고리즘을 실행하는 것이 좋다.

그러나 실질적으로 연속적으로 많은 양의 데이터가 지속적으로 유입된다면, online learning을 통해서 사용자 선호도 변화에 적응할 수 있다는 것은 매우 흥미롭다.

 

다른 예시를 살펴보자. 위의 예시는 사용자에게 적절한 검색 목록을 제공하는 방법을 학습하기 위한 학습알고리즘이다. 

만약 가게에 100대의 휴대전화가 있고, 'Android phone 1080p camera'와 같은 검색어를 입력했을 때, 우리는 10개의 휴대전화를 선택해서 제공하고 싶고, 학습 알고리즘을 통해 이 10대의 휴대전화가 무엇인지 알아내고 싶다. 문제를 해결하는 방법은 다음과 같다. 

각 휴대전화에 대해서 사용자 쿼리가 제공되고, feature vector로는 사용자의 쿼리가 휴대전화의 이름이나 설명서에서 얼마나 많은 단어가 유사한지 등을 사용할 수 있다. 그리고, 사용자가 해당 휴대전화를 클릭할 확률을 계산해서 가장 높은 확률의 휴대전화 10개를 제공한다.

이러한 문제를 click-through rate(CTR);클릭률 학습 문제라고 한다. 이것은 사용자가 제공되는 특정 링크를 클릭할 화귤을 학습하는 것이다. 

 

 

- Map-reduce and Data parallelism

이전 강의에서 배웠던 알고리즘들은 하나의 기계나 하나의 컴퓨터에서 실행이 가능했다.

하지만 어떤 머신러닝 시스템은 하나의 기계에서 실행하기에 너무 커서, 모든 데이터를 하나의 컴퓨터에서 실행할 수 없을 때, 어떻게 해결할 수 있는지 살펴보자.

즉, Map Reduec approach라 불리는 Large-scale 머신러닝을 알아보자.

 

아이디어는 다음과 같다.

만약 우리가 linear regression이나 logistic regression 모델을 학습하기 원할 때, 우리는 batch-gradient descent를 사용한다고 하고, training example의 크기 m은 400이라고 하자. 물론 실제로 크기와 비교해서는 매우 작은 값이다.

Map reduce는 다음과 같다. 400개의 example을 나눈다. 만약 4개의 컴퓨터를 사용한다면, 우리는 4개의 subset으로 나누어서 각각의 컴퓨터에서 100개의 example들을 학습할 것이다.

이렇게 각각의 컴퓨터에서 temp 변수를 구하고, 다 구한 후에는 master 서버로 전달해서 마스터 서버에서 오른쪽과 같이 parameter를 업데이트 할 것이다. 

 

일반적인 Map-reduce는 다음과 같다.

 

 

만약 속도를 높이기 위해서 Map-reduce를 적용하기 위해서는 우리의 학습 알고리즘이 계산을 병렬화해서, Training Set에 대한 합계로 표현할 수 있는가에 대한 여부이다. 많은 학습 알고리즘들이 Training Set에 대한 함수의 계산 합계로 표현될 수 있고, 대용량 데이터 세트에서 이것을 실행하는데 연산 비용이 크기 때문에 학습 알고리즘 작업의 대부분이 Training Set에 대한 합계로 표현될 수 있을 때 Map-reduce를 통해서 학습 알고리즘을 확장하기 좋다.

 

Map-reduce는 Multi-core를 사용해서 하나의 컴퓨터에서도 가능하다.

여러 기기에서 하는 것보다 유용한 점은 네트워크 지연에 대해서 걱정할 것이 없다는 것이다.