[논문 번역] A Neural Probabilistic Language Model (2)

3. 병렬 구현

모델의 파라미터 수는 입력 윈도우와 어휘의 크기에 대해 훌륭하게, 즉 선형적으로 증가하지만, 출력 확률을 얻기 위해 필요한 연산량은 n-gram 모델에 대해 필요한 것보다 훨씬 크다.

주된 이유는 n-gram 모델에서는 상대 빈도의 선형 결합이 훈련을 수행할 때 이미 정규화되어 있기 때문에 특정 $P(w_t|w_{t-1}, \cdots, w_{t-n+1})$은 어휘의 모든 단어에 대한 확률을 계산할 필요가 없기 때문이다.

신경망 구현에서 주요 계산 병목은 출력층의 활성화 연산이다.

 

병렬 컴퓨터에서 (훈련과 테스트 모두) 모델을 실행하는 것은 연산 시간을 줄일 수 있는 방법이다.

우리는 두 가지 형태의 플랫폼, 공유 메모리 프로세서 머신과 빠른 네트워크를 가진 리눅스 클러스터로 병렬화를 실험했다.

 

 

---

 

 

3-1. 데이터 병렬 처리

공유 메모리 프로세서의 경우, 공유 메모리간의 매우 낮은 프로세서 통신 오버헤드 덕분에 병렬화가 쉽다.

이 경우에 우리는 각 프로세서가 데이터의 서로 다른 부분집합을 처리하는 데이터 병렬 구현을 선택했다.

각각의 프로세서는 자신의 예시에 대한 그래디언트를 계산하고, 공유 메모리 영역에 간단히 저장되는 모델의 파라미터에 대해 확률적 그래디언트 업데이트를 수행한다.

최초 구현에서는 매우 느렸고, 각각의 프로세서가 위의 파라미터 하위 집합 중 하나에서 다른 프로세서와 동시에 쓰지 않도록 하기 위해 동기화에 의존했다.

각각의 프로세서 사이클의 대부분은 다른 프로세서가 파라미터에 대한 쓰기 권한 잠금 해제를 기다리면서 사용되었다.

 

대신에 우리는 각 프로세서가 공유 메모리 영역에서 언제든 쓸 수 있는 비동기 구현을 택했다.

때때로, 프로세서 중 하나의 파라미터 벡터에 대한 업데이트의 일부가 사라지거나, 다른 프로세서의 업데이트에 의해 덮어써지면서 파라미터 업데이트에 약간의 노이즈가 생긴다.

하지만, 이 노이즈는 매우 작고 학습을 실질적으로 저해하지 않았다.

 

불행하게도, 대형 공유 메모리 병렬 컴퓨터는 매우 값비싸고, 프로세서의 속도 또한 클러스터로 연결 가능한 상용 CPU들에 비해 느린 편이다.

따라서 고속 네트워크 클러스터에서 훨씬 더 빠른 학습을 달성할 수 있었다.

 

 

---

 

 

3-2. 파라미터 병렬 처리

만약 병렬 컴퓨터가 CPU의 네트워크라면, 일반적으로 프로세서 간 모든 파라미터를 자주 교환하는 것은 비현실적인데, 그 작업이 수십 메가바이트나 되기 때문(가장 큰 네트워크의 경우 거의 100 메가바이트)에 로컬 네트워크에서 너무 많은 시간이 걸릴 것이다.

대신에 우리는 파라미터 간의 병렬화, 특히 출력 유닛의 가중치에 집중했는데, 거기서 우리 아키텍처에 대한 대부분의 연산이 수행되기 때문이다.

각각의 CPU는 출력의 하위 집합에 대한 비정규화 확률을 계산하고, 해당 출력 유닛 파라미터(해당 유닛으로 전달되는 가중치)에 대한 업데이트를 수행한다.

이 전략은 무시할 만한 통신 오버헤드로 병렬화 확률적 경사 상승을 수행할 수 있도록 했다.

CPU들은 본질적으로 다음 두 가지 정보를 상호 통신해야 한다:

(1) 출력 softmax의 정규화 계수, (2) 은닉층(아래에서 a로 표기)과 단어 피처 층(x로 표기)의 그래디언트이다.

모든 CPU는 출력 유닛 활성화 이전까지의 연산, 예를 들어 단어 피처 선택, 은닉층 활성화 a의 연산과 대응 역전파 및 업데이트 단계를 중복 계산한다.

하지만 이 계산들은 네트워크의 전체 계산량 중 무시할 만한 부분이다.

 

예를 들어, AP(Associated Press) 뉴스 데이터 실험에서 사용된 다음 아키텍처를 고려해보라: 어휘 크기는 |V| = 17,964, 은닉층의 수는 h = 60, 모델 차수는 n = 6, 단어 피처수는 m = 100이다.

하나의 학습 예시를 수행하기 위한 총 수치 연산의 수는 약 $|V|(1+nm+h)+h(1+nm)+nm$이다(여기서 각 항은 출력 유닛, 은닉 유닛, 그리고 단어 피처 유닛의 계산에 해당된다).

이 예시에서 출력 유닛의 가중합을 계산하는 데에 필요한 전체 계산의 비율은 대략 $\frac{|V|(1+(n-1)m+h} {|V|(1+(n-1)m+h)+h(1+(n-1)m) + (n-1)m} = 99.7\% $이다.

이 계산은 다른 작업과 관련한 실제 CPU 시간이 다르기 때문에 근사치이지만, 일반적으로 출력 유닛별 계산을 병렬화하는 것이 유리하다는 것을 보여준다.

모든 CPU가 계산의 아주 작은 부분만 복제한다는 사실은 여기서 추구하는 병렬화의 수준, 즉 수십 개의 프로세서에 대한 총 계산 시간에 영향을 미치지 않는다.

만약 히든 유닛의 수가 크다면, 계산을 병렬화하는 것은 역시 이점이 있게 되지만, 우리 실험에서 그 접근법은 조사하지 않았다.

 

이 전략의 구현은 Myrinet 네트워크(저지연 기가비트 근거리 통신망)를 통해 연결된 1.2 GHz 클럭 스피드의 Athlon 프로세서(32 x 2 CPU) 클러스터에서 수행되었으며, 병렬화 루틴에는 MPI(Message Passing Interface) 라이브러리 (Dongarra et al., 1995)를 사용했다.

아래에는 M개의 프로세서 클러스터에 있는 CPU i에 의해 병렬로 실행되는 단일 예시 $(w_{t-n+1}, \cdots, w_t)$에 대한 병렬화 알고리즘이 개략적으로 나와 있다.

CPU i(0부터 M-1까지)는 $start_i = i \times \lceil|V|/M\rceil$에서 시작하는 출력 유닛의 블록을 담당하고, 이 블록의 길이는 $min(\lceil|V|/M\rceil, |V| - start_i)$이다.

 

 

프로세서 i에서의 연산, 예제 t

1. 순방향 단계

(a) 단어 피처층에서의 순방향 계산 수행:

$$(x(k) \leftarrow C(w_{t-k}),$$

$$x=(x(1), x(2), \cdots, x(n-1))$$

(b) 은닉층에서의 순방향 계산 수행:

$$o \leftarrow d + Hx$$

$$a \leftarrow tanh(o)$$

(c) i번째 블록의 출력 유닛에서의 순방향 계산 수행:

$$s_i \leftarrow 0$$

i번째 블록에서 j 반복

                   i.  $$ y_j \leftarrow b_j + a.U_j$$

                   ii. (직접 연결이 있다면) $$ y_j \leftarrow y_j + x.W_j $$

                   iii. $$ p_j \leftarrow e^{y_j}$$

                   iv. $$s_i \leftarrow s_i + p_j$$

(d) 모든 프로세서 간 $S=\sum_{i}s_i$ 공유. 이 합을 호율적으로 계산하고 공유할 수 있는 MPI Allreduce 작업으로 쉽게 수행 가능.

(e) 확률 정규화:

i번째 블록에서 j 반복,

$$ p_j \leftarrow p_j/S$$

(f) 로그 우도 업데이트. 만약 $w_t$가 CPU i > 0의 블록에 포함되면, CPU i는 $p_{w_t}$를 CPU 0으로 전송. CPU 0은 $L=logp_{w_t}$를 계산하고 전체 로그 우도를 추적.

 

2. 역방향/업데이트 단계, 학습률 $\varepsilon$

(a) i번째 블록의 출력 유닛에 대한 그래디언트 역전파 수행:

그래디언트 벡터 $\frac{\partial L}{\partial a}$ 와 $\frac{\partial L}{\partial x}$ 초기화.

i번째 블록에서 j 반복

                   i. $$\frac{\partial L}{\partial y_j} \leftarrow 1_{j==w_t} - p_j$$

                   ii. $$b_j \leftarrow b_j + \varepsilon\frac{\partial L}{\partial y_j}$$

                      (직접 연결이 있다면) $$ \frac{\partial L}{\partial x} \leftarrow \frac{\partial L}{\partial x} + \frac{\partial L}{\partial y_j}W_j$$

                   $$ \frac{\partial L}{\partial a} \leftarrow \frac{\partial L}{\partial a} + \frac{\partial L}{\partial y_j}U_j$$

                      (직접 연결이 있다면) $$ W_j \leftarrow W_j + \varepsilon \frac{\partial L}{\partial y_j}x$$

                   $$ U_j \leftarrow U_j + \varepsilon \frac{\partial L}{\partial y_j} a$$

(b) 프로세서간 $ \frac{\partial L}{\partial x}$와 $ \frac{\partial L}{\partial a}$ 합산 및 공유. MPI Allreduce 연산을 사용하여 쉽게 구현 가능.

(c) 은닉층 가중치 역전파 및 업데이트:

1과 h 사이 k 반복

$$ \frac{\partial L}{\partial o_k} \leftarrow (1 - a_k^2) \frac{\partial L}{\partial a_k}$$

$$ \frac{\partial L}{\partial x} \leftarrow \frac{\partial L}{\partial x} + H' \frac{\partial L}{\partial o}$$

$$ d \leftarrow d + \varepsilon \frac{\partial L}{\partial o}$$

$$ H \leftarrow H + \varepsilon \frac{\partial L}{\partial o}x'$$

(d) 입력 단어의 단어 피처 벡터 업데이트:

1과 n-1 사이 k 반복

$$C(w_{t-k}) \leftarrow C(w_{t-k}) + \varepsilon \frac{\partial L}{\partial x(k)}$$

여기서 $ \frac{\partial L}{\partial x(k)}$는 벡터 $\frac{\partial L}{\partial x}$의 k번째 블록(길이 m)

 

가중치 감쇠 정규화는 위의 실행에서 보이지 않지만 가중치 감쇠 인자 x 학습률 x 파라미터의 값을 매 업데이트마다 각각의 파라미터에 뺌으로써 쉽게 적용할 수 있다.

파라미터 업데이트는 속도 향상을 위해 매개변수 그래디언트 벡터를 통하지 않고 직접 수행되고, 실험에서는 메모리 액세스가 계산 속도의 제한 요인으로 작용했다.

 

순전파 단계에서 지수 계산에 수치적인 문제가 있을 수 있는데, 모든 $p_j$가 수치적으로 0이되거나 그 중 하나가 지수를 계산하기에 너무 클 수 있다(위의 step 1(c)ii).

이 문제를 피하기 위해, 일반적인 해결책은 소프트맥스에서 지수를 구하기 전에 $y_j$의 최댓값을 빼는 것이다.

따라서 우리는 $p_j$의 지수를 계산하기 전 M개의 프로세서 간에 $y_j$의 최댓값을 공유하기 위해 추가적인 Allreduce 연산을 추가했다.

블록 i의 $y_j$의 최댓값을 $q_i$라고 하자.

그러면 전체 최댓값 $Q = max_i q_i$가 M개의 프로세서 간에 공동으로 계산되어 공유된다.

그 다음에 지수는 다음과 같이 계산된다: $p_j \leftarrow e^{y_j-Q}$ (step 1(c)ii 대신)는 적어도 하나의 $p_j$가 수치적으로 0이 아니고, 지수 인수의 최댓값이 1이 되도록 보장한다.

 

병렬 버전의 클록 시간과 단일 프로세서의 클록 시간을 비교했을 때, 통신 오버헤드가 하나의 학습 에포크에 대해 전체 시간의 1/15 수준에 불과하다는 것을 확인했다: 따라서 우리는 고속 네트워크에서 이 알고리즘을 사용하면 병렬화를 통해 거의 완벽한 속도 향상을 얻을 수 있다.

 

저속 네트워크의 클러스터에서도 각각의 예시가 아닌 매 K개 예시(미니 배치)마다 통신을 수행함으로써 효율적인 병렬화를 얻는 것이 가능할 수 있다.

이렇게 하기 위해서 각각의 프로세서에 신경망의 활동과 그래디언트에 대한 K개의 버전을 저장해야 한다.

K개 예시에 대한 순전파 후에 확률합은 프로세서 간에 공유되어야 한다.

그러면 K 부분 그래디언트 벡터 $\frac{\partial L} {\partial a}$와 $\frac{\partial L} {\partial x}$를 얻기 위해 K 역전파 단계가 시작된다.

프로세서 간에 이 그래디언트 벡터가 교환된 후에 각 프로세서는 역전파 단계를 완료하고 파라미터를 업데이트한다.

이 방법은 주로 네트워크 통신 지연 시간(전송되는 데이터 양은 동일)을 단축하여 시간을 절약한다.

만약 K가 너무 크면 수렴 시간에서 손실이 있을 수 있는데, 이는 배치 경사 하강이 일반적으로 확률적 경사 하강보다 느린 것과 같은 이유다(LeCun et al., 1998).

 

 

---

 

 

4. 실험 결과

다양한 영어 텍스트와 책에서 발췌한 1,181,041개 단어로 구성된 Brown 코퍼스를 대상으로 비교 실험을 수행했다.

첫 800,000 단어는 학습을 위해서, 다음 200,000 단어는 검증(모델 선택, 가중치 감쇠, 조기 종료)를 위해, 그리고 남은 181,041 단어는 테스트를 위해 사용했다.

서로 다른 단어의 수는 47,578개(구두점, 대분자와 소문자 구분, 텍스트와 단락을 구분하는 데 사용되는 구문 기호 포함)이다.

빈도가 3보다 적거나 같은 희소한 단어들은 하나의 기호로 병합하여 어휘의 크기를 |V| = 16,383으로 줄였다.

 

실험은 또한 1995년부터 1996년까지 Associated Press (AP) News의 텍스트로도 수행되었다.

학습 셋은 1400만(13,994,528) 단어, 검증 셋은 1백만(963,138)단어, 테스트 셋 역시 1백만(963,071) 단어로 구성되어 있다.

원본 데이터는 148,721개의 서로 다른 단어(구두점 포함)가 있었는데, 가장 자주 사용되는 단어만 유지하고(구두점 유지), 대문자를 소문자로, 숫자 형태를 특수 기호로, 희소 단어를 특수 기호로, 고유 명사를 다른 특수 기호로 매핑하여 |V| = 17964로 줄였다.

 

신경망을 학습하기 위해, 초기 학습률은 아주 작은 데이터셋으로 몇 번 시도해본 후 $\varepsilon_o = 10^{-3}$으로 설정했고, 다음 계획에 따라 점진적으로 줄였다: $\varepsilon_t = \frac{\varepsilon_o}{1+rt}$ 여기서 t는 수행된 파라미터 업데이트 횟수이고, r은 휴리스틱하게 $r = 10^{-8}$로 선택된 감소 인자이다.

 

 

---

 

 

4-1. N-Gram 모델

신경망을 비교한 첫 번째 벤치마크는 보간 또는 평활된 트라이그램 모델이다(Jelinek and Mercer, 1980).

$q_t = l(freq(w_{t-1}, w_{t-2}))$는 입력 문맥 $(w_{t-1}, w_{t-2})$의 이산화된 발생 빈도를 나타낸다고 하자.

그러면 조건부 확률 추정값은 조건부 혼합의 형태를 갖는다:

$$ \hat{P}(w_t|w_{t-1}, w_{t-2}) = \alpha_0(q_t)p_0 + \alpha_1(q_t)p_1(w_t) + \alpha_2(q_t)p_2(w_t|w_{t-1}) + \alpha_3(q_t)p_3(w_t|w_{t-1}, w_{t-2})$$

여기서 조건부 가중치는 $\alpha_i(q_t) \geq 0, \sum_i \alpha_i(q_t) = 1$이다.

기본 예측 변수는 다음과 같다: $p_0 = 1 / |V|$, $p_1(i)$는 유니그램(훈련 셋에서 단어 i의 상대 빈도), $p_2(i|j)$는 바이그램(이전 단어가 j일 때 단어 i의 상대 빈도), 그리고 $p_3(i|j,k)$는 트라이그램 (이전 2 단어가 j, k일 때 단어 i의 상대 빈도)이다.

동기는 $(w_{t-1}, w_{t-2})$의 빈도가 클 때, $p_3$가 가장 신뢰할 수 있는 반면, 빈도가 낮을 때 $p_2, p_1$, 또는 $p_0$의 저차 통계량이 더 신뢰할 수 있다는 것이다.

$q_t$의 각 이산값(맥락 빈도 구간)에 대해 서로 다른 혼합 가중치 $\alpha$ 셋이 있다.

유니그램, 바이그램, 트라이그램 상대 빈도를 추정하는 데 사용되지 않는 데이터 셋(검증 셋)을 사용하여 대략 5번의 반복을 통해 EM 알고리즘을 사용해 쉽게 추정할 수 있다.

보간 n-gram은 아주 다른 방식으로 '오류'를 발생시키는 것으로 보이기 때문에 MLP와 혼합된 형태를 형성하는 데 사용되었다.

 

다른 최신 n-gram 모델과의 비교도 이루어졌다: Modified Kneser-Ney 알고리즘(Kneser and Ney, 1995, Chen and Goodman., 1999)을 사용한 back-off n-gram 모델과 클래스 기반 n-gram 모델(Brown et al., 1992, Ney and Kneser, 1993, Niesler et al., 1998)이다.

검증 셋은 클래스 기반 모델의 n-gram의 차수와 단어 클래스의 수를 선택하는 데 사용되었다.

이 알고리즘의 구현은 Stolcke (2002)와 www.speech.sri.com/projects/srilm/에 설명된 SRI 언어 모델 툴킷을 활용했다.

아래에 보고된 back-off 모델 퍼플렉시티를 계산하는 데 사용되었으며, 우리의 신경망 퍼플렉시티에서처럼 로그 우도 계산에서 문장 끝 토큰의 특별한 지위를 부여하지 않았다.

모든 토큰(단어와 구두점)은 로그 우도를 평균화하는 데에서 동일하게 처리되었다(따라서 퍼플렉시티를 얻는 데에서도 동일하게 적용되었다).

 

 

---

 

 

4-2. 결과

아래는 다양한 모델 $\hat{P}$에 대한 테스트 셋 퍼플렉시티 ($1 / \hat{P}(w_t|w_1^{t-1}))$의 기하평균)의 측정치이다.

확률적 경사 상승 절차의 명백한 수렴은 Brown 코퍼스에서 10에서 20 에포크 후에 얻어졌다.

AP 뉴스 코퍼스에서는 (검증 셋에서) 과적합의 신호를 찾을 수 없었는데, 이는 (40개 CPU를 3주 동안) 오직 5개의 에포크만 실행했기 때문일 수 있다.

검증 셋에서의 조기 종료도 사용되었지만, Brown 실험에서만 필요했다.

Brown 실험에서 $10^{-4}$의 가중치 감쇠 페널티가 사용되었고 AP News 실험에서는 $10^{-5}$의 가중치 감쇠가 사용되었다(검증 셋 퍼플렉시티에 기반한 몇 번의 시도로 선택됨).

표 1은 Brown 코퍼스에서 얻어진 결과를 요약한다.

표의 모든 back-off 모델들은 수정된 Kneser-Ney n-gram으로, 표준 back-off 모델보다 훨씬 더 잘 작동했다.

표에서 back-off 모델에 대해 m이 지정되면, 클래스 기반 n-gram이 사용된다(m은 단어 클래스의 수).

단어 피처의 무작위 초기화(신경망 가중치의 초기화와 유사하게)가 이루어졌지만, 지식 기반 초기화로 더 나은 결과를 얻을 수 있을 것으로 의심된다.

 

주요 결과는 신경망을 사용할 때 n-gram을 사용하는 것 중 가장 최고의 성능일 때와 비교하여, 검증 세트에서 가장 잘 작동하는 n-gram과 MLP를 사용했을 때 Brown에서의 경우 약 24%, AP News의 경우 약 8%의 테스트 복잡도 차이로 상당히 더 나은 결과를 얻을 수 있다는 것이다.

표는 또한 신경망이 더 많은 문맥을 활용할 수 있었음을 시사한다(Brown에서, 문맥의 수를 2단어에서 4단어로 늘리면 신경망에서는 개선이 있지만 n-gram에서는 없음).

결과는 또한 은닉 유닛이 유용하다는 것(MLP3 vs MLP1, MLP4 vs MLP2)을 보여주고, 보간 트라이그램과 신경망의 출력 확률을 혼합하면 항상 퍼플렉시티를 줄이는 데 도움이 된다는 것을 보여준다.

단순 평균화가 도움이 된다는 사실은 신경망과 트라이그램이 서로 다른 곳에서 오류(즉, 관찰된 단어에 낮은 확률을 부여하는 것)를 발생시키는 것을 시사한다.

결과를 통해 입력에서 출력으로 직접 연결하는 것이 유용한지 아닌지 말할 수는 없지만, 더 긴 훈련 시간을 지불하면 적어도 작은 코퍼스에서 입력-출력 연결 없이 더 나은 일반화가 달성될 수 있다는 것을 시사한다: 비록 약간 낮은 퍼플렉시티 값이 나오긴 했지만, 직접 연결이 없을 때 네트워크는 수렴하는 데 두 배의 시간이 걸린다(10 대신 20 에포크).

합리적인 해석은 직접 입력-출력 연결이 단어 피처를 로그 확률값으로 매핑하는 것의 '선형' 부분에 대한 더 많은 용량과 더 빠른 학습을 제공한다는 것이다.

반면, 이러한 연결이 없으면 은닉 유닛은 더 나은 일반화를 강요할 수 있는 좁은 병목을 형성한다.

 

표 1

표 1: Brown 코퍼스에 대한 비교 결과. 삭제된 보간 트라이그램은 검증 퍼플렉시티가 가장 낮은 신경망보다 테스트 퍼플렉시티가 33% 더 높다. 최상의 n-gram(500개의 단어 클래스를 가진 클래스 기반 모델)의 경우 차이는 24%이다.

n: 모델의 차수. c: 클래스 기반 n-gram의 단어 클래스의 수. h: 은닉 유닛의 수.

m: MLP의 단어 피처 수, 클래스 기반 n-gram의 클래스의 수.

direct: 단어 피처에서 출력으로의 직접 연결 여부.

mix: 신경 확률의 출력 확률이 트라이그램의 출력과 혼합되는지 여부(각각 0.5의 가중치로).

마지막 세 개 열은 훈련, 검증, 그리고 테스트 셋에 대한 퍼플렉시티를 나타낸다.

 

 

표 2는 더 큰 코퍼스(AP News)에서의 비슷한 결과를 보여주며, 퍼플렉시티의 차이는 8%로 더 작다.

약 3주 동안 40개 CPU로 오직 5번의 에포크가 수행되었다.

클래스 기반 모델은 이 경우 n-gram 모델에 도움이 되지 않았지만, 고차원의 수정된 Kneser-Ney back-off 모델은 n-gram 모델 간에 최고의 결과를 보였다.

 

표 2

 

표 2: AP News 코퍼스에 대한 비교 결과. 열 레이블은 이전 표 참고.