"Efficient Online Learning Algorithms Based on LSTM Neural Networks" 논문 소개 & 개념 정리 - LSTM 기반의 online learning

"Efficient Online Learning Algorithms Based on LSTM Neural Networks"

Tolga Ergen and Suleyman Serdar Kozat, Senior Member, IEEE

 

 

 

Abstract

  우리는 nonlinear regression을 조사하고, LSTM network 기반의 novel regression structures를 소개한다. 이 구조를 설명하기 위해 효과적인 online training 방법을 제공한다. novel LSTM 기반 구조를 훈련시키기 위해서 우리는 기본 아키텍처를 주 공간 형태로 배치하고 매우 효율적인 PF(particle filtering) 기반 업데이트를 도입한다. 우리는 또한 확률적 경사 강하(stochastic gradient descent)와 확장된 칼만 필터(extended Kalman filter) 기반 업데이트를 제공한다. 우리의 PF 기반 훈련 방법은 충분한 수의 입자와 안전함이 확실한 기술적 환경에서 MSE로 최적의 파라미터에 수렴함을 보장한다. 더 중요한 것은, 입자 수를 조절함으로써 first-order gradient 기반 방법으로 연산 복잡성을 가진다. 우리의 접근 방식은 generic하기 때문에, 우리는 또한 LSTM 아키텍처를 GRU 아키텍처로 직접 대체함으로써 GRU 기반 접근 방식을 도입한다. 여기서 우리는 다른 실제 데이터 세트를 통한 순차 예측 작업에서 우리의 LSTM 기반 접근 방식의 우월성을 입증한다. 실험 결과는 여러 가지 다른 벤치마크 실제 데이터 세트에 대한 기존 방법과 관련하여 도입된 알고리즘에 의해 달성된 상당한 성능 개선을 보여준다.

 

* generic programming: 데이터 형식에 의존하지 않고, 하나의 값이 여러 다른 데이터 타입들을 가질 수 있는 기술에 중점을 두어 재사용성을 높일 수 있는 프로그래밍 방식 

 

 

 

1.Introduction

A. Preliminaries

  알 수 없는 원하는 신호를 추정하는 문제는 현대 online learning 문헌의 주요 관심 주제 중 하나이다. 우리는 신호의 다음 값을 예측하기 위해 원하는 신호와 관련된 데이터 시퀀스를 순차적으로 수신한다[1]. 이 문제는 온라인 회귀라고 알려져 있으며, 특히 예측 작업에 대해 신경망[2], 머신 러닝[1], 신호 처리 문자[3]에서 광범위하게 연구되고 있다[4]. 이러한 연구에서 비선형(nonlinear) 접근방식은 일반적으로 채택되는데, 이는 특정 애플리케이션의 경우 선형성에 대한 제약으로 인해 선형 모델링이 불충분하기 때문이다[3]. 여기서는 특히 데이터 시퀀스와 라벨을 순차적으로 관찰하여 미래 라벨을 예측하기 위한 그들 사이의 비선형 관계를 찾는 온라인 설정에서 비선형 회귀 분석을 연구한다.

회귀 분석을 위한 머신 러닝 및 신호 처리 literatures에는 광범위한 비선형 모델링 접근법이 존재한다[1][3]. 그렇지만, 대부분 이러한 접근들은 안정성과 overfitting 이슈 때문에 높은 연산 복잡성에 고통받고, 불충분한 성과를 제공한다[3]. 신경망 기반 회귀 알고리즘은 또한 비선형적이고 복잡한 구조를 모델링할 수 있기 때문에 비선형 모델링에도 도입된다. 그러나, 그것들은 또한 문제가 과도하게 발생하기 쉬우며 특정 애플리케이션에서 적절한 성능 미만을 입증하는 것으로 나타났다. 이러한 문제를 해결하고 그 성능을 더욱 향상시키기 위해, 최근 DNN으로 알려진 여러 layer으로 구성된 신경망이 도입되었다. DNN에서는 계층화된 구조를 채택하여 각 계층이 이전 계층에 기반한 형상 추출 작업을 수행한다. 이 메커니즘으로 DNN은 매우 비선형적이고 복잡한 구조를 모델링할 수 있다. 그러나 이러한 계층화된 구조는 데이터에서 시간 의존성을 포착하는 데 있어 성능이 좋지 않아서 DNN은 시계열 모델링 및 임시 데이터 처리에서 제한된 성능만 제공할 수 있다. 이러한 네트워크는 과거의 정보를 저장할 수 있는 고유의 메모리를 가지고 있기 때문에 치료법으로서 기본적인 RNN이 도입된다. 그러나 기본 RNN은 제어 구조가 부족하여 훈련 중 장기 구성요소가 지수적인 성장(exponential growth) 또는 norm of gradient의 붕괴를 야기하며, 이는 각각 잘 알려진 exploding&vanishing gradient problem이다. 따라서 데이터에 대한 장기 의존성을 포착하기에는 불충분하여 실제 작업에서의 수행이 상당히 제한된다. 이 문제를 해결하기 위해 여러 개의 제어 구조를 가진 새로운 RNN 아키텍처, 즉 LSTM 네트워크가 도입된다. 그러나 고전적인 LSTM 구조에서는 회귀 벡터(regression vector)가 출력에 직접 기여하는 것이 아니다. 즉, 원하는 신호는 상태 벡터(state vector)를 사용해서만 역추적된다. 따라서 본 논문에서는 LSTM 기반의 온라인 회귀 구조들을 소개하고, 여기서 우리는 잘 알려진 ARMA 모델에서 영감을 받은 회귀 벡터의 직접적인 기여도 통합한다.

  신경망 구조가 고정되면 해당 파라미터를 온라인 방식으로 교육하는 다양한 방법이 존재한다. 특히, 잘 알려진 backpropagation recursion 때문에 1차 경사법 기반 접근법이 훈련의 효율성으로 인해 널리 사용된다. 그러나 이러한 기법은 2차 경사 기반 기법에 비해 성능이 떨어진다. 예를 들어 RTRL(real-time recurrent learning) 알고리즘은 gradient 계산에 매우 효율적이다. 그러나 RTRL 알고리즘은 1차적 경사 정보만 이용하기 때문에 조건이 좋지 않은 문제에서는 성능이 떨어진다. 한편, 2차 경사 기반 기법은 훨씬 더 나은 성능을 제공하지만, 1차 순서 방식에 비해 매우 복잡하다. 예를 들어, 잘 알려진 확장 칼만 필터(EKF) 방식도 2차 정보를 사용하여 성능을 향상시키므로 매개변수 추정치의 오차 공분산 행렬을 업데이트해야 하며 그에 따라 추가적인 복잡성을 야기해야 한다. 또한, 2차 경사도 기반 방법은 신경망 기반 애플리케이션의 안장 포인트(saddle points)가 많기 때문에 제한된 훈련 성능을 제공한다. 훈련 문제를 완화하기 위해 LSTM 아키텍처를 위한 입자 필터링(PF) 기반의 온라인 업데이트를 도입한다. 특히, 먼저 LSTM 아키텍처를 비선형 상태 공간 형태(nonlinear state space form)로 배치하고 이 설정에서 매개변수 학습 문제를 공식화했다. 이 양식을 바탕으로 PF 기반 추정 알고리즘을 도입하여 파라미터를 효과적으로 학습한다. 여기서 우리의 훈련방법은 입자가 충분히 많고 특정 기술적 조건을 만족하는 경우 온라인 방식으로 최적 매개변수 추정 성과에 대한 정합성을 보장한다. 게다가, 우리는 실험에서 입자의 양을 조절함으로써, 기존의 2차적 방법에 비해 우수한 성능을 제공하면서 계산 복잡성을 크게 줄일 수 있다는 것을 증명한다. 여기서, 우리의 훈련 접근법은 일반적인 것으로, 우리는 또한 최근에 도입된 GRU 아키텍처를 비선형 상태 공간 형태로 놓고, 그 파라미터를 학습하기 위해 우리의 알고리즘을 적용한다. 광범위한 시뮬레이션을 통해, 기존의 방법에 비해 알고리즘에 의해 달성된 중요한 성능 개선을 설명한다.

 

 

B. Prior Art and Comparisons

  신경망 기반 학습 방법은 단일 hidden layer neural network가 모든 비선형 구조를 적절하게 모델링할 수 있는 것처럼 매우 비선형적인 구조를 모델링하는 데 강력하다. 또한 이러한 방법, 특히 복잡한 RNN 기반 방법은 시간 데이터를 효과적으로 처리하고 시계열을 모델링할 수 있다. 복잡한 RNN(예: LSTM network)은 네트워크 내부의 정보 흐름을 제어하기 위한 과거 정보와 몇 가지 제어 게이트를 유지하기 위한 메모리 덕분에 이러한 성능을 제공한다. 그러나 복잡한 RNN의 경우 적절한 성능은 높은 계산 복잡성을 필요로 한다. 즉, 매번 많은 수의 매개변수를 훈련해야 한다. 따라서 복잡성을 완화하기 위해 [16] 및 [5]의 LSTM 네트워크 기반 방법은 낮은 복잡도의 일차 경사도 기반 기법, 즉 확률적 경사 하강(SGD)을 선택하여 매개변수를 교육한다. [18]의 EKF와 [25]의 Hessian-free technology와 같이 2차 기법으로 훈련된 LSTM의 특정 적용이 존재함에도 불구하고, 복잡한 문제와 또한 많은 안장 포인트로 인한 성능 저하를 겪는다[20]. 반대로 기본 RNN의 경우, 훈련할 파라미터가 적지만, 이러한 신경망은 제어 구조를 가지고 있지 않다. 따라서, exploding&vanishing gradient problem는 장기적 구성요소(long-term components)로 인해 발생한다. 이러한 문제들은 기본 RNN들이 먼 사건들 사이의 상관관계를 배우는 것을 막는다[6]. [5]와 [16]의 기본 RNN 기반 학습 방법은 성능을 향상시키기 위해 고복합성 2차 경사 기반 기법(high-complexity second-order gradient-based techniques)을 선택하여 매개변수를 훈련한다.

따라서 저복합성 신경망(low-complexity neural networks)나 저복합성 훈련방법(low-complexity training method)이 선택되어 감당할 수 없는 계산 복잡성이 증가하지 않도록 한다. 그러나 기본 RNN은 복잡한 네트워크와 비교했을 때, long-term 및 short-term 의존성을 적절하게 포착하는 데 어려움을 겪는다. 반면에 1차 경사도 기반 방법은 2차 경사도 기반 기술에 비해 수렴 속도가 느리고 성능이 떨어진다. 이러한 문제를 피하기 위해, 본 문서는 LSTM 아키텍처를 훈련 시키기 위해 PF 알고리즘을 기바능로 온라인 업데이트를 도출한다. 따라서, 특별한 선형화(linearization) 없이 2차 교육을 제공할 뿐만 아니라, 1차 방법 정도의 계산 복잡성을 가진다(모델링에서 입자 수를 세심하게 제어함으로써).

  우리는 기존의 신경망 기반 학습 방법[5],[16],[18],[23]이 잘 알려진 복잡성-성능 절충(trade-off)에 시달리고 있음을 강조한다. 이러한 tradeoff로 인해 비선형 회귀(nonlinear regression) 문제를 해결하기 위해 대개 선택되지 않는다. 비선형 회귀 분석을 특별히 조사하는 특정 신경망 기반 방법[5],[16]이 있지만, 이러한 목적을 위해 기본 RNN 아키텍처만 사용한다. 또한 그들의 회귀 접근방식에서, 그들은 기본 RNN 아키텍처의 출력을 스칼라 값으로 설정하여 최종 추정치가 내부 상태들의 선형 조합이 되도록 함으로써 최종 추정치를 제공한다. 대신, 본 논문에서는 비선형 회귀 분석을 위해 LSTM 아키텍처를 채택하고, 최종 추정치에 대한 회귀 벡터의 직접적인 기여를 통합하기 위한 추가 용어를 도입한다. 따라서 우리는 시뮬레이션에서 설명된 바와 같이 회귀 성능을 상당히 개선한다.

 

 

C. Contributions 

우리의 주된 contribution은 다음과 같다.

1. 문헌의 첫 번째로서, 데이터 회귀 분석(data regression)을 위한 LSTM 아키텍처를 기반으로 한 online learning algorithms을 소개한다. PF 기반 접근법을 사용하여 온라인 방식으로 LSTM 아키텍처를 효율적으로 훈련 시킨다.
2. 최종 추정치를 계산하기 위해 새로운 LSTM 기반 회귀 구조를 제안한다. 여기서 우리는 ARMA 모델에서 영감을 받은 input regressor의 직접적인 기여를 통합하기 위해 기존의 LSTM 아키텍처에 대한 추가 게이트를 도입한다.
3. LSTM 방정식을 비선형 상태 공간 형태(nonlinear state space form)로 표시한 다음 각 매개변수[21][26]에 대한 최첨단 상태 추정 기법에 기반하여 온라인 업데이트를 도출한다. 우리의 PF 기반 방법은 기존의 2차 및 1차 방법[18][23]과 관련하여 온라인 파라미터 훈련에서 상당한 수행 향상을 달성한다.
4. 우리는 입자의 수를 컨트롤함으로써 계산 복잡도를 대략 first-order gradient 기반 방법 정도로 상당한 향상을 달성하였다. 우리의 시뮬레이션에서, 입자의 수를 조절함으로써 first- and second-order 방법에 비해 월등한 수행을 보이지만 first-order gradient 기반 방법과 복잡도는 같다는 것을 입증했다.
5. 실제 생활과 재무 데이터를 포함하는 광범위한 시뮬레이션 세트를 통해, 우리는 기존의 방법과 관련하여 알고리즘에 의해 달성된 성능 개선을 설명한다[18][23]. 더욱이, 우리는 접근법이 generic하기 때문에, 우리는 또한 GRU 아키텍처, 즉 Section IV에서 복잡한 RNN에 우리의 접근법을 직접 적용함으로써 GRU 기반 알고리즘을 도입한다.

 

D. Organization of This Paper

  이 논문의 구성은 다음과 같다. 우리는 온라인 회귀 문제를 소개한 후 Section II에서 우리의 LSTM 기반 모델을 설명한다. 그런 다음 Section III-A의 데이터 회귀 분석에 대한 최종 추정치를 계산하기 위해 서로 다른 아키텍처를 소개한다. Section III-B에서는 기존의 훈련 방법을 검토하고 이러한 방버븡ㄹ 도입 아키텍처까지 확장한다. 그런 다음 Section III-C에서 PF 기반 훈련 알고리즘을 소개한다. Section IV에서는, 제안된 알고리즘과 훈련 방법의 장점을 실제 생활과 재무 데이터를 포함하는 광범위한 일련의 실험을 통해 설명하고, 또한 온라인 학습 과제에 대한 GRU 기반 접근법을 소개한다. 그리고 나서 우리는 Section V에서 결론으로 논문을 마무리한다.

 

 

2. Model and problem desription

● 기본 RNN 구조 

● LSTM architecture

hidden layer가 한 개인 LSTM Neural network를 사용할 것이다. (핍홀 연결 제거된)

● final estimate

fig 1. 회귀 작업을 위해 (11)에서 제안된 아키텍처의 자세한 회로도 

게이트 및 h(·) 함수 이전의 합산에 대해 $x_{t}$및 $y_{t-1}$에 W(.) 및 R(.)을 각각 곱하고 가중치 벡터 b(.)를 이러한 합산에 추가합니다.

 

 

3. Novel Learning Algorithms based on LSTM Neural Networks

이 섹션에서 data regression에 대한 novel contributions을 소개한다. 이러한 기여들로 SGD, EKF, PF algorithms들을 기반으로 online updates함

 

A. Different Regression Architectures

output $y_{t}$와 weight vector $w_{t}$의 직접적인 선형결합을 먼저 고려한다.

(8)에서 우리는 최종 추정을 다음과 같이 만들었다.

시스템에서 최종 추정은 $x_{t}$에 직접적으로 의존하지 않는다. 그렇지만, generic non-linear regression 작업에서, 최정 추정치는 보통 현재 regression vector에 의존한다. 이러한 위해, input vector(즉, regression vector)의 효과를 fig 1에 표시된 최종 추정치에 통합하는 선형 항(linear term)을 소개합니다.

second regression architecture

여기서, 최종 추정치는 직접적으로 $x_{t}$에 의존하고의존성은 control gate($\alpha_{t}$)에 컨트롤된다.

(10)과 (11)에서 input과 state vectors의 영향은 control&output gate에 의해 제어된다.

따라서, 이 게이트들은 비선형 회귀 문제(nonlinear regression problem)에서 state 및 input contents의 노출을 제한 할 수 있다.

state와 input vectors의 내용들을 완전히 노출시키려면 우리는 control&output gate를 (11)에서 제거해야 한다.

third regression architecture

* $\hat{d}^{(1)}_{t}$에 대한 업데이트는 $A_{t}^{\alpha}$=0이고 $\hat{d}^{(3)}_{t}$에 대한 업데이트는 특별한 경우이므로 $\hat{d}^{(2)}_{t}$는 최종 추정치를 계산하는 가장 일반적인 아키텍처이다. $A_{t}^{o}$=I 이고 $A_{t}^{\alpha}$=I일 때

 

 

*제안한 online training method들의 연산 복잡도 비교

m: dimensionality of the network's output space

p: dimensionality of the regressor space

N: number of particles for the PF algorithm

 

 [표 1]

 

B. Conventional Online Training Algorithms

이 섹션에서는 소개된 아키텍처의 해당 매개 변수를 온라인 방식으로 학습하는 방법을 소개한다.

 

SGD algorithm 기반의 online update -> RTRL algorithm in the neural network iterature

 

RTRL(real-time recurrent learning) algorithm

• gradient 계산에 매우 효율적
• 1차적 경사(first-order gradient) 정보만 이용
• LSTM 아키텍처를 위한 online update를 얻기 위해 recursive gradient formulation을 끌어냄

SGD

• first-order gradient 정보만 이용
  • second-order gradient 기반 기술보다 수렴이 느리고 조건이 좋지 않은 문제에서 성능이 저하된다.
• 이를 완화하기 위해 우리는 second-order gradient를 고려한다
  • 수렴률(convergence rate)이 빠르고 conditioned problem에 대해 더 강력하다[17]

 

우리는 먼저 LSTM 방정식을 nonlinear state space 형태로 설정하여 온라인 방식으로 매개변수를 학습하기 위해 EKF 알고리즘을 고려할 수 있다[19]. 그러나 EKF 알고리즘은 비선형 네트워크 방정식을 선형화하기 위해 1차 Taylor 계열 확장이 필요하므로 성능이 저하됩니다[5][19]. 또한 [표 1] 은 EKF 알고리즘이 SGD 알고리즘에 비해 계산 복잡도가 높다는 것을 보여준다. 

 

다음 섹션에서는 SGD 및 EKF 기반 교육 방법을 모두 소개하고 이러한 파생물들을 (10)-(12)의 회귀 아키텍처로 확장합니다.

 

1. SGD 알고리즘을 사용한 online learning:

각 파라미터 셋에서 instantaneous loss인 l($d_{t}$,$\hat{d}_{t}$)=$(d_{t}-\hat{d}_{t})^{2}$을 최소화하기 위해 우리는 stochastic gradient update를 끌어왔다(RTRL 알고리즘이라 알려진). 그리고 소개된 아키텍처의 계산을 확장한다. weight vector의 경우, 우리는 사용한다

$\mu_{t}$를 learning rate이라고 할 때, 우리는 $\mu_{t}$->0은 t -> $\infty$이고 $\sum_{k=1}^{t}\mu_{k} ->\infty$이면 t-> $\infty$(예: $\mu_{t}=\frac{1}{t}$). 파라미터 $W_{(z)}$는 다음의 업데이트를 가진다.

 

1) Online learning with the SGD algorithm

2) Online learning with the EKF algorithm

우리는 (3)~(8),(10)에서 서술한 시스템의 파라미터들을 훈련시키기 위해 EKF 알고리즘 기반의 업데이트를 제공한다.

문헌에서, LSTM을 훈련시키기 위한 EKF 기반 방법이 있지만, 이 방법은 $\theta_{t}$만 추정한다. 그렇지만, 우리 방법으로는 LSTM의 state와 output vector를 각각 추정할 수 있다 ($c_{t}, t_{t}$). 

EKF 알고리즘은 관측치가 주어진 상태의 posterior density function이 가우스 인 것으로 가정합니다.

* 

이 가정은 gaussian noise를 통해 시스템 방정식에 perturbation((감정의) 동요, 변화)을 도입함으로써 만족될 수 있다.

따라서 먼저 LSTM 시스템을 비선형 상태 공간 형태로 작성한 다음 EKF 업데이트를 사용할 수 있는 gaussian noise terms을 도입한다.

 

 

C. Online Training Based on the PF algorithm

우리가 소개하는 novel PF 기반 방법은 second-order training 방법보다 우수하다

[표 1]에서 보여주듯 N을 선택해 대략 first-order 방법의 연산 복잡도인 performance를 달성했다

PF 알고리즘은 (29)와 (30)에서 노이즈 샘플의 독립성을 제외하고는 어떤 가정도 요구하지 않는다.

(40),(41)에서 우리는 E[$a_{t}|d_{1:t}$]를 얻기를 추구한다. (MSE 의미에서 최적의 state 추정치인)

이러한 목적으로, 우리는 먼저 posterior probability density function $p(a_{t}|d_{1:t})$를 찾는다.

그런 다음 posterior density function 기반인 state vector의 conditional mean을 계산한다. density function을 계산하기 위해 우리는 PF 알고리즘을 수행한다.

 

(공식 넘많... 넘어가규~)

 

 

PF 알고리즘을 적용하는 동안, 가중치의 분산은 시간이 지남에 따라 필연적으로 증가하므로 some time step 후에 가중치 중 하나를 제외한 모든 가중치는 0에 가까운 값을 얻는다. 이 때문에 (46)의 weight이 매우 작은 입자는 추정치에 거의 영향을 미치지 않지만 (40)과 (45)를 사용하여 업데이트해야합니다. 그러므로 우리의 계산 노력의 대부분은 무시할 수 있는 weight을 가진 입자에 사용되는데, 이것은 degeneracy problem이라고 알려져 있습니다[21]. degeneracy를 측정하기 위해 다음과 같이 계산된 (35)에 소개된 유효 샘플 사이즈를 사용합니다.

<- degeneracy 측정

 

$N_{eff}$는 가중치가 높은 분산을 나타낸다 (즉, degeneracy problem)

만약 $N_{eff}$이 특정 역치(한계점)보다 작아지면, 우리는 resampling 알고리즘을 적용한다 ([26]에서 소개한).

resampling 알고리즘은 무시할만한 weight을 가진 particle을 제거하고 큰 weight을 가진 particle들에 집중해 degeneracy를 피한다. 이렇게 우리는 E[$a_{t}|d_{1:t}$]에 수렴하는 online training method를 얻는다. 이 수렴은 다음의 조건 하에 있음이 보장된다.

 

 

 

 

Conclusion

최종 추정치를 계산하기 위해 새로운 회귀 알고리즘을 제안 

여기서 고전적인 LSTM 아키텍처에 추가 게이트를 도입

그런 다음 LSTM 시스템을 상태 공간 양식에 넣은 다음 이 양식을 기반으로 LSTM 아키텍처를 학습하기 위해 SGD, EKF, PF 알고리즘을 기반으로 온라인 업데이트를 도출했습니다.

이 방법은 충분한 수의 특정 기술적 조건을 충적한다. 우리는 입자의 수를 제어함으로써 1차 그래디언트 기반 방법의 계산 복잡도인 성능을 달성하였다.

LSTM 방정식을 GRU 아키텍처로 직접 대체하여 GRU 아키텍처 기반 접근법을 소개했지만, LSTM 기반 접긴이 GRU 보다 더 우수하다는 것을 관찰했다. ( 우리 접근의 generic한 구조 때문에)

 

 

 

* e.g. :  example

   i.e. : in other words

 

 

출처: https://ieeexplore.ieee.org/document/8036280

 

참고 자료:

gradient descent optimization algorithms 정리 

Extended Kalman Filter