1
$\begingroup$

I found a recursive version of the forward algorithm on wikipedia, however I don't understand the notation given in the pseudocode: pseudocode from wikipedia

What means $$x_{t-1}$$ under the summation sign? What do I need to sum? It would be really helpful if someone could provide a calculation example. Thank you!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

We have a sequence of observations $x_1, x_2,...,x_T$, so $x_{t-1}$ is simply the observation just before $x_t$ (for any $t>0$).

When simulating the forward algorithm it's useful to write a table where $T$ (number of observations) is the number of columns and the number of rows is the number of possible labels. Each cell $(t,y)$ in this table will eventually contain the probability to have label $y$ at time $t$. The table is filled column by column starting from the left, i.e. initialize $t=0$ for all labels first. Then for every column the calculation depends only on the previous column (thanks to the independence assumption).

You can find a detailed explanation in this book for example.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your comment! In the book you referenced the alphas don't add up to 1 . As far as I understand, each cell (t, y) is actually the alpha, right?Shouldn't the (t, y) for all ys add up to 1? $\endgroup$
    – teoML
    Commented Jul 2, 2022 at 9:10
  • $\begingroup$ @teoML No, the columns don't have to sum to 1 because the alphas represent joint probabilities, their sum for all $y$ is equal to the prob of the current sequence of observation $x_1,..,x_t$. But if each value is divided by their sum for all $y$, then we obtain the conditional prob $p(y|x_1,..,x_t)$ and these probs would sum to 1. $\endgroup$
    – Erwan
    Commented Jul 2, 2022 at 10:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.