Markov Chains to Transformers

Markov and n-gram models

$$ P(x_{0:T}) = P(x_0)\prod_{t=1}^{T}P(x_t \mid x_{t-1}) $$

$$ P(x_t \mid x_{<t}) \approx P(x_t \mid x_{t-n+1:t-1}) $$

Hidden Markov models

$$ P(z_{0:T},x_{0:T}) = P(z_0)\prod_{t=1}^{T}P(z_t \mid z_{t-1})P(x_t \mid z_t) $$

$$ z_{t-1}\rightarrow z_t,\qquad z_t\rightarrow x_t $$

Recurrent and gated state models

$$ h_t = f_\theta(x_t,h_{t-1}) $$

$$ c_t = f_t\odot c_{t-1} + i_t\odot\widetilde{c}_t $$

$$ s_t = A s_{t-1} + Bx_t,\qquad y_t = Cs_t $$

Causal convolutions

$$ h_t = f_\theta(x_t,x_{t-1},\ldots,x_{t-k+1}) $$

$$ h_t = f_\theta(x_t,x_{t-d},x_{t-2d},\ldots) $$

Self-attention

$$ \operatorname{Attention}(Q,K,V) = \operatorname{softmax}\left(\frac{QK^\top}{\sqrt{d_k}}\right)V $$

Decoder-only causal attention

$$ P(x_t \mid x_{<t}),\qquad \mathcal{E}_{\mathrm{causal}} = {(x_j,x_i): j\leq i} $$

Encoder-only bidirectional attention

$$ \mathcal{E}_{\mathrm{full}} = {(x_j,x_i): 0\leq i,j\leq T} $$