SSNT Recursion Derivation

Forward

Let

$p_{i,j}$ be the emission probability,

$p(y_j|h_i,s_j)$ be the word prediction probability. Then the forward variable

${\alpha }_{i,j}$ can be expressed as follows according to eq (9)(12):

$${\alpha }_{i,j}=p(y_j|h_i,s_j)p_{i,j}\sum _{k=1}^i({\alpha }_{k,j-1}\prod _{d=k}^{i-1}(1-p_{d,j}))$$
Take the last entry from the summation (

$k=i$) out :

$$p(y_j|h_i,s_j)p_{i,j}(\sum _{k=1}^{i-1}({\alpha }_{k,j-1}\prod _{d=k}^{i-1}(1-p_{d,j}))+{\alpha }_{i,j-1})$$
Take the last entry from the product (

$d=i-1$) out :

$$p(y_j|h_i,s_j)p_{i,j}((1-p_{i-1,j})\sum _{k=1}^{i-1}({\alpha }_{k,j-1}\prod _{d=k}^{i-2}(1-p_{d,j}))+{\alpha }_{i,j-1})$$
Recognize that middle summation part can be recursively defined by

${\alpha }_{i-1,j}$, up to a scaling by the word prediction and the emission, thus:

$$p(y_j|h_i,s_j)p_{i,j}((1-p_{i-1,j})\frac{{\alpha }_{i-1,j}}{p(y_j|h_{i-1},s_j)p_{i-1,j}}+{\alpha }_{i,j-1})$$
Let

$q_{i,j}=\frac{{\alpha }_{i,j}}{p(y_j|h_i,s_j)p_{i,j}}$, then:

$$q_{i,j}=(1-p_{i-1,j})q_{i-1,j}+{\alpha }_{i,j-1}$$
This allows us to compute

${\alpha }_{i,j}$ directly from

${\alpha }_{i-1,j}$ and

${\alpha }_{i,j-1}$.

Parallelize

Furthermore, every vector

$q_i$ can be computed directly from vector

${\alpha }_{i-1}$ via parallelizable cumulative sum and cumulative product operations. See eq (23)-(30) in Online and Linear-Time Attention by Enforcing Monotonic Alignments for the derivation the original formula.