HIPPO
HiPPO: Recurrent Memory with Optimal Polynomial Projections
Table of contents
TODO: Update detailed study log of this paper…
Sequence에서 어려운 점은 seq가 길어질수록 누적된 history를 표현하기 힘들다는 점이다. HIPPO는 polynomial base로 continuous, discrete time sequence를 projection하여 online compression을 수행한다.
시간 t에 대해 과거 시간의 중요도가 측정되면, online function approximation을 수행한다. 저자는 LMU (Legendre Memory Unit)의 미분값을 도출하고, GRU와 같은 gate mechanism을 generalization한다.
즉, time scale에서 이전 history를 기억하기 위해 시간에 따라 확장되는 memory update mechanism HIPPO-Legs를 제안한다.
\(\rightarrow\) time robust, bounded gradient, fast update
Intorudction
Language modeling, speech recognition, video processing와 같은 sequential data의 modeling 및 학습은 long-term에 대한 이전 step의 memory가 가장 중요한 측면이다. (Online update에 대해 bounded storage를 사용하여 전체 history representation을 학습)
RNN과 같은 memory unit을 통해 전체 history에 대한 information을 저장하는 방법은 vanishing gradient 문제가 생길 수 있다. LSTM과 GRU같은 gate나 LMU, Fourier Recurrent Unit과 같은 higher-order frequency도 unified understanding of memory는 도전적인 과제다. 또한 기존에는 전체 길이나 시간대에 대한 사전 제한이 있고 distribution shift가 발생하는 상황에선 문제가 될 수 있었다.
저나는 time scale에 대한 prior와 length에 대한 dependency가 없고 memory mechanism에 대해 이론적이며 기존 방법에 대해 unified method를 설계했다.
OP (Orthogonal Polynomial)
orthogonal polynomial sequence는 sequence내의 두 polynomial이 inner product 내에서 서로 orthogonal한 것을 의미한다. 많이 사용되는 orthogonal polynomial로는 Hermite, Laguerre, Jacobi, Gegenbauer, Chebyshev, Legendre polynomial 등이 있다.
OP는 특정 measure (weight) \(\mu_t\)에 대해 두 polynomial \(P_m, P_n\)의 적분이 다음과 같은 관계일 때 성립한다.
각 basis \(P_n (n=0, 1, 2, \cdots)\)은 Gram-Schmidt로 구할 수 있다.
Recurrence relation polynomials \(P_n\)은 \(A_n\)이 0이 아닐 때, 다음과 같은 recurrence relation을 만족한다.
Reconstruction
\[\begin{align} \sum^{N-1}_{i=0} c_iP_i(x) / \lVert P_i \rVert^2_\mu, \quad \mathrm{where} \; c_i = \left\langle f, P_i \right\rangle _\mu = \int f(x)P_i(x)d\mu(x) \end{align}\]Legendre Polynomial