Consider the basic Viterbi algorithm: Input: a sentence x1 ... xn, parameters q(s|u, v) and e(x|s). Definitions: Define K to be the set of possible tags. Define K−1 = K0 = {*}, and Kk = K for k = 1 ... n. Initialization: Set π(0, *, *) = 1. Algorithm: For k = 1 ... n, For u ∈ Kk−1, v ∈ Kk, π(k, u, v) = maxw ∈ Kk−2(π(k − 1, w, u) × q(v | w, u) × e(xk | v)) Return maxu ∈ Kn−1,v ∈ Kn(π(n, u, v) × q(STOP | u, v)) What is the complexity of this algorithm which tags a sequence of size n with a label set of size K?
קורסי בחירה במדעי המחשב NLP2020
Consider the basic Viterbi algorithm: Input: a sentence x1 ... xn, parameters q(s|u, v) and e(x|s). Definitions: Define K to be the set of possible tags. Define K−1 = K0 = {*}, and Kk = K for k = 1 ... n. Initialization: Set π(0, *, *) = 1. Algorithm: For k = 1 ... n, For u ∈ Kk−1, v ∈ Kk, π(k, u, v) = maxw ∈ Kk−2(π(k − 1, w, u) × q(v | w, u) × e(xk | v)) Return maxu ∈ Kn−1,v ∈ Kn(π(n, u, v) × q(STOP | u, v)) What is the complexity of this algorithm which tags a sequence of size n with a label set of size K?
1
| done | ||
מיין לפי
* השאלה נוספה בתאריך: 01-02-2020