[SSM Series]HiPPO: Recurrent Memory with Optimal Polynomial Projections

👀 이 SSM 시리즈는 State-space model에 대한 survey를 진행하기 위해서 Albert Gu의 논문들을 HiPPO부터 최근의 MAMBA까지 리뷰합니다. 각 논문의 SSM과 관련된 부분에 대해서 깊이 있게 정리할 예정이며, SSM과 관련이 적은 부분들은 간단하게 정리되는 점 참고 부탁드립니다.

Motivation & Contributions

• HiPPO : 대량의 누적 데이터를 polynomial bases에 projection하는 것.
• measures : 과거 시점의 중요성을 지정하는 척도
• HiPPO는 measures를 이용해서 최적의 function approximation를 푼다.
• 특수한 경우로, HiPPO는 GRU의 일반화이다. (이는 SSM 모델의 공통적인 특징이다. )

기존의 sequential forecasting 에서의 한계점

• 기존의 시계열 예측 방법은 일반적으로 sequence length나 time scale에 대한 prior가 필요하며 이 범위를 벗어나면 효과적이지 않다. 이는 distribution shift가 있는 설정에서는 문제가 될 수 있다.
  → 대다수의 모델들은 long-term dependency를 잘 포착하는지에 대한 이론적 보장이 부족함.
  
• 이러한 문제점을 해결하기위해서 HiPPO에서는 기존 방법들에 대한 통합된 관점을 가지고, time scale에 대한 prior 없이 모든 길이의 dependencies를 해결할 수 있으며, 해당 방법에 대한 이론적 보장이 가능함.
  → 통합된 관점 : SSM은 recurrent model, Temporal convolution differential equation model의 일반화이다. (이런 통합된 관점으로의 해석은 후속연구인 LSSL에서 자세하게 설명되어있음.)

Methods

• 누적되는 데이터를 polynomial basis에 projection 하기 위해서는
  1. a way to quantify the approximation
  2. suitable subspace( projection it onto a subspace of bounded dimension.)

1. HiPPO builds upon a rich history of the well-studied orthogonal polynomial and related transforms in the signal processing literature.

정의 1에 따른 HiPPO의 설명

HiPPO는 연속 함수 $f: R≥0 → R$이 주어졌을 때 (ground-truth)를 모든 시간 t에 대해 투영 연산자 $proj(t)$와 계수 추출 연산자 $coef(t)$를 정의합니다. 여기서 $proj(t)$는 시간 $t$까지의 함수 $f$를 다항식 $g(t) ∈ G$로 매핑하여 근사 오류 $‖f≤t − g(t)‖L2(μ(t))$를 최소화하고, coeff는 다항식 $g(t)$를 $μ(t)$에 대해 정의된 직교 다항식의 기저 계수 $c(t) ∈ RN$으로 매핑합니다. 이는 함수를 시간에 따라 변화하는 측정에 기반한 직교 다항식으로 근사하는 방법론을 제공합니다.

$(hippo(f))(t) = coef_t(proj_t(f))$

전반적으로 HiPPO에서는 OP로부터 basis를 계산한다.

어떤 OP를 선택하는지에 따라서 근사되는 함수가 다를 것.

정리

• HiPPO: Recurrent Memory with Optimal Polynomial Projections
• 유한한 용량의 문제로 누적된 데이터로 representation을 생성하기 힘들다.
• HiPPO는 continuous signal과 discrete time-series를 polynomial basis 위에 projection함으로써 online 압축을 할 수 있는 framework.
• 과거의 각 시점의 중요성을 지정하는 observation이 주어지면, HiPPO는 자연스러운 online function approximation 문제에 대한 optimal solution을 만든다.
• GRU와 같은 recurrent network의 gating mechanism의 일반화이다.
• 엄청난 continuous series data n-dimensional polynomial로 정의.

HiPPO 논문은 수많은 데이터, long-sequence data를 $g(t)$로 축약한다. $g(t)$로 축약하기 위해서 orthogonal polynomial을 사용한다. 이 orthogonal polynomial의 각 항 앞에서 들어가는 계수 $c(t)$를 계산하는 것이 이 논문의 주요 contribution이다.

Appendix를 보면, 이 논문에서는 일련의 증명과정을 통해 Orthogonal polynomial의 계수의 미분값이 아래와 같은 수식으로 정리됨을 증명한다.
$\frac{dc(t)}{dt} = A(t)c(t)+B(t)f(t)$

복잡한 orthogonal polynomial 로의 근사를 위의 식과 같이 간단한 수식으로 정리하는 것은 엄청난 contribution
(증명 과정은 생략 )이 되며, 후속 연구들인 LSSL, S4, MAMBA까지 이어진다.
여기서, $A,B$는 학습가능하지 않다.
Legendre orthogonal polynomial등을 풀면서 A,B등을 근사해서 사용함.