Confusion regarding dynamic programming in CRF paper I was referring to this paper related to CRF.
However, I didn't get the part related to dynamic programming. Further I have question related to feature function selection. In this paper they have given this feature function
$$
F_j({{\bf{y}}},{{\bf{x}}}) = \sum_{i=1}^{n}f_j(y_{i-1},y_i,{\bf{x}},i)
$$
I didn't get why we have to sum from $i=1:n$. Is it because it allows to have particular $y_i$ and $y_{i-1}$ values to be satisfied by any ordered pairs like $(y_2, y_1),(y_3,y_2)$ and so on.
Now suppose I have a feature function such that I have to have this value $A, B$ at particular positions like $y=1$ and $y=2$, then I cannot sum from $i=1:n$ right. Or even if I do it will be all zeros right?
Now my question related to dynamic programming. I didn't understand the expression given after the following in the paper
it must be possible to eﬃciently compute the expectation of each feature function with respect to the CRF model distribution for every observation sequence $x_{(k)}$ in the training data given by...
So can anyone please explain with some short examples. I mean considering training data with 1-2 short sentences and with few labels. I think it will help me to get clear.
Also the paper says that if the output sequence has $n$ elements and there are possibly $y$ lables, then there are $n^y$ possible label sequences. But I have some confusion. Lets say I have two elements and the possible labels are $[A, B, C]$, then the possible sequences are:
A A
B B
C C 
A B
B A
A C 
C A
B C 
C B

which is equal to $9$ instead of $2^3=8$. So can anyone please provide some insights?
 A: Dynamic programming is a technique to improve efficiency of an algorithm. Basically, you make sure you don't make redundant calculations. We accomplish this by structuring our algorithm in a way to solve smaller, frequently used subproblems first, and then build up to our overall solution. This is similar to memoization, where we simply save the results we've already calculated. You can see this question for more details.
I skimmed over some of the details in the paper, but I think I have the gist of the algorithm (correct me if I'm wrong). In this case, I believe the algorithm is constructing a model  by iterating over length of the subsequences of inputs. Let's say that we have four symbols: X1, X2, X3, and X4. Our sequence is thus:
X1X2X3X4
We want to construct a model that takes into account the conditional probability of these symbols occurring in this order, given the previous symbols. The naïve approach would find model parameters for the longer subsequences first, recursing down each time:
X1X2X3X4 -> X1X2X3 -> X1X2 -> X1
                           -> X2
                   -> X2X3 -> X2
                           -> X3
         -> X2X3X4 -> X2X3 -> X2
                           -> X3
                   -> X3X4 -> X3
                           -> X4

As you can see, there is a lot of redundancy; parameters are calculated twice for X2X3, and three times for X2 and X3. A dynamic programming approach would find model parameters for the subsequences first, and then combine them in smart way, iterating from ground up:
X1 -> X1X2 -> X1X2X3 -> X1X2X3X4
X2 -> X2X3 -> X2X3X4
X3 -> X3X4
X4

As you can see, the dynamic programming approach has no redundancy. For sequences of longer lengths, a dynamic programming algorithm will run much, much faster.
