Skip to Content

3주차 - Autoformer (NeurIPS 2021) (1)

https://jamboard.google.com/d/10z-N93YK9NZAWKo_ori9pLmd8a6boJiexYUhb4oHdvU/edit?usp=sharing 

Efficient computation

Auto-correlation을 계산하는 것은 O(L2)O\left(L^{2}\right) 의 복잡도를 가짐

Rxx(τ)=lim⁡L→∞1L∑t=1Lxtxt−τ\mathcal{R}{x x}(\tau)=\lim {L \rightarrow \infty} \frac{1}{L} \sum{t=1}^{L} x{t} x_{t-\tau}

Time delay aggregation을 계산하는 것은 O(Llog⁡L)O(L \log L) 의 복잡도를 가짐

τ1,⋯ ,τk=arg⁡Topk⁡τ∈{1,⋯ ,L}(RQ,K(τ))R^Q,K(τ1),⋯ ,R^Q,K(τk)=SoftMax⁡(RQ,K(τ1),⋯ ,RQ,K(τk)) Auto-Correlation (Q,K,V)=∑ikRoll⁡(V,τi)R^Q,K(τi)\begin{gathered} \tau_{1}, \cdots, \tau_{k}=\underset{\tau \in\{1, \cdots, L\}}{\arg \operatorname{Topk}}\left(\mathcal{R}{Q, \mathcal{K}}(\tau)\right) \\ \hat{\mathcal{R}}{Q, \mathcal{K}}\left(\tau_{1}\right), \cdots, \widehat{\mathcal{R}}{Q, \mathcal{K}}\left(\tau{k}\right)=\operatorname{SoftMax}\left(\mathcal{R}{Q, \mathcal{K}}\left(\tau{1}\right), \cdots, \mathcal{R}{Q, \mathcal{K}}\left(\tau{k}\right)\right) \\ \text { Auto-Correlation }(Q, \mathcal{K}, \mathcal{V})=\sum_{i}^{k} \operatorname{Roll}\left(\mathcal{V}, \tau_{i}\right) \widehat{\mathcal{R}}{Q, \mathcal{K}}\left(\tau{i}\right) \end{gathered} 따라서 해당 Auto-Correlation Mechanism의 복잡도는 O(L2)\boldsymbol{O}\left(\boldsymbol{L}^{2}\right)

→ Fast Fourier Transform 으로 효율화

Fourier Transform

같은 형태를 반복하는 주기를 가진 파동은, 아무리 복잡한 것이라도 단순한 파동들이 결합 ( 복잡한 파동 )=( 단순한 파동 1)+( 단순한 파동 2)+( 단순한 파동 3)+ 임의의 주기함수 f(t)=a0+a1cos⁡2πTt+a2cos⁡2π⋅2Tt+⋯ancos⁡2π⋅nTt+b1sin⁡2πTt+b2sin⁡2π⋅2Tt+⋯+bnsin⁡2π⋅nTt=a0+∑n=1∞(ancos⁡2π⋅nTt+bn‾sin⁡2π⋅nTt) \begin{aligned} & (\text { 복잡한 파동 })=(\text { 단순한 파동 } 1)+(\text { 단순한 파동 } 2)+(\text { 단순한 파동 } 3)+ \\ & \text { 임의의 주기함수 } f(t)=a_{0}+a_{1} \cos \frac{2 \pi}{T} t+a_{2} \cos \frac{2 \pi \cdot 2}{T} t+\cdots a_{n} \cos \frac{2 \pi \cdot n}{T} t \\ & +b_{1} \sin \frac{2 \pi}{T} t+b_{2} \sin \frac{2 \pi \cdot 2}{T} t+\cdots+b_{n} \sin \frac{2 \pi \cdot n}{T} t \\ & =a_{0}+\sum_{n=1}^{\infty}\left(a_{n} \cos \frac{2 \pi \cdot n}{T} t+\underline{b_{n}} \sin \frac{2 \pi \cdot n}{T} t\right) \\ & \ \end{aligned}

Fourier Transform vs Inverse Fourier Transform

Wiener-Khintchine Theorm

For a well behaved stationary random process the power spectrum is equal to the Fourier transform of the autocorrelation function.

Sx(ejω)=∑k=−∞∞Rx(k)e−jωkS_{x}\left(e^{j \omega}\right)=\sum_{k=-\infty}^{\infty} R_{x}(k) e^{-j \omega k}

Sx(ejω)=lim⁡N→∞12N+1E[∣XN(ejω)∣2]=lim⁡N→∞12N+1E[(∑n=−NNx(n)e−jωn)(∑k=−NNx(k)e−jωk)∗]=lim⁡N→∞12N+1E[∑n=−NN∑k=−NNx(n)x(k)e−jω(n−k)]=lim⁡N→∞12N+1∑n=−NN∑k=−NNE[x(n)x(k)]e−jω(n−k)=lim⁡N→∞12N+1∑n=−NN∑k=−NNRx(n−k)e−jω(n−k)=lim⁡N→∞lim⁡M→∞12N+1∑n=−NN∑k=−MMRx(n−k)e−jω(n−k)=lim⁡N→∞12N+1∑n=−NNlim⁡M→∞∑k=−MMRx(n−k)e−jω(n−k)=lim⁡N→∞12N+1∑n=−NN(∑k=−∞∞Rx(k)e−jωk)=(∑k=−∞∞Rx(k)e−jωk)lim⁡N→∞12N+1∑n=−NN1=∑k=−∞∞Rx(k)e−jωk\begin{aligned} S_{x}\left(e^{j \omega}\right) & =\lim {N \rightarrow \infty} \frac{1}{2 N+1} E\left[\left|X{N}\left(e^{j \omega}\right)\right|^{2}\right] \\ & =\lim {N \rightarrow \infty} \frac{1}{2 N+1} E\left[\left(\sum{n=-N}^{N} x(n) e^{-j \omega n}\right)\left(\sum_{k=-N}^{N} x(k) e^{-j \omega k}\right)^{*}\right] \\ & =\lim {N \rightarrow \infty} \frac{1}{2 N+1} E\left[\sum{n=-N}^{N} \sum_{k=-N}^{N} x(n) x(k) e^{-j \omega(n-k)}\right] \\ & =\lim {N \rightarrow \infty} \frac{1}{2 N+1} \sum{n=-N}^{N} \sum_{k=-N}^{N} E[x(n) x(k)] e^{-j \omega(n-k)} \\ & =\lim {N \rightarrow \infty} \frac{1}{2 N+1} \sum{n=-N}^{N} \sum_{k=-N}^{N} R_{x}(n-k) e^{-j \omega(n-k)} \\ & =\lim {N \rightarrow \infty} \lim {M \rightarrow \infty} \frac{1}{2 N+1} \sum{n=-N}^{N} \sum{k=-M}^{M} R_{x}(n-k) e^{-j \omega(n-k)} \\ & =\lim {N \rightarrow \infty} \frac{1}{2 N+1} \sum{n=-N}^{N} \lim {M \rightarrow \infty} \sum{k=-M}^{M} R_{x}(n-k) e^{-j \omega(n-k)} \\ & =\lim {N \rightarrow \infty} \frac{1}{2 N+1} \sum{n=-N}^{N}\left(\sum_{k=-\infty}^{\infty} R_{x}(k) e^{-j \omega k}\right) \\ & =\left(\sum_{k=-\infty}^{\infty} R_{x}(k) e^{-j \omega k}\right) \lim {N \rightarrow \infty} \frac{1}{2 N+1} \sum{n=-N}^{N} 1 \\ & =\sum_{k=-\infty}^{\infty} R_{x}(k) e^{-j \omega k} \end{aligned}

About