CS-431: Questions Quizz 2018

Hello,

For question 5.2 of last year's quizz, I don't understand why T₄is not crossed (apparently, 78% of last year's students also didn't ^^).

In slide 13 of PoS Tagging lecture, limited scope for syntactic dependencies at $k$ neighbours, is stated as dependent, for $T_i$ , on tags $T_{i-k} \to T_{i-1}$ . Why is $T_{i+1}$ also a dependence ? This does not seem to fit the Markov assumption...

Best

O. Cloux

(p.s. feel free to put your 2018 questions below to keep them grouped)

Re: Questions Quizz 2018

by Jean-Cédric Chappelier - Monday, 4 November 2019, 10:21 PM

It does! This is what I mentioned several times and very precisely when emphasizing the backward part of the Viterbi algorithm, but I know it's tricky (carefully look what the question is about): do not confuse what is computed with the way it is parametrized: it's not because we parametrize $P(T_1,...,T_n)$ with $P(T_i|T_{i-1})$ that we are not maximizing $P(T_1,...,T_n)$ .

More precisely w.r.t. that very question: if you want the formal proof in this very case: $P(T_3|T_1 T_2 T_4) = P(T_1 T_2 T_3 T_4) / P(T_1 T_2 T_4) = P(T_1) P(T_2 | T_1) P(T_3 | T_2) P(T_4|T_3) / \sum_t P(T_1) P(T_2 | T_1) P(t | T_2) P(T_4|t) = P(T_1) P(T_2 | T_1) P(T_3 | T_2) P(T_4|T_3) / (P(T_1) P(T_2 | T_1) \sum_t P(t | T_2) P(T_4|t)) = P(T_3 | T_2) P(T_4|T_3) / \sum_t P(t | T_2) P(T_4|t)) = P(T_3 | T_2) P(T_4|T_3 T_2) / \sum_t P(t | T_2) P(T_4|t T_2)) = P(T_3 T_4| T_2) / \sum_t P(t T_4| T_2) = P(T_3 T_4| T_2) / P(T_4| T_2) = P(T_3| T_2 T_4)$ . QED

But pay attention to what is referred to: parameters, not considered altogether, I mean, not when talking about the global proba $P(T_1,...,T_n)$ are indeed only left to right : $P(T_i|T_{i-1})$ ; but as soon as it's about the whole (global) proba, there is no "left-to-right biais" anymore, only the global proba is under consideration.
I hope it makes sense....