Note that P i, j is the score of the j-th tag for the i-th word.
the probability of the output tag sequence where Y w is the set of all possible tag sequences, A is a matrix of transition scores, A i, j represents a score that transits from the i-th tag to the j-th tag, and y −1 and y N+1 are the special tag for the start of the sentence and the end of sentence, respectively.