Hidden Markov part-of-speech tagging by the Viterbi algorithm

Viterbi dynamic programming finds the best tag sequence in O(T |S|^2) rather than the |S|^T sequences a brute-force search would visit. Working in logs keeps the recursion safe for long sentences. The tests check the returned path against exhaustive enumeration on a short sentence, which is the only way to be sure the back-pointers are right.

Usage

HmmTag(X, tagset, start = NULL, trans = NULL, emit = NULL)

Arguments

X

Word indices, 0-based.

tagset

Tag labels; only the count is used.

start

Initial tag distribution.

trans

Tag transition matrix.

emit

Emission matrix, tags by vocabulary.

Value

List with estimate (best log probability), path (1-based tag indices), logprob, n, method.

Details

Formula: argmax_y prod_t P(y_t | y_{t-1}) P(x_t | y_t).

References

Charniak (1993), Statistical Language Learning, MIT Press, ch. 3; Viterbi (1967), IEEE Transactions on Information Theory 13(2):260-269. doi:10.1109/TIT.1967.1054010

Examples

X <- c(0, 1, 2, 1, 0)
tagset <- c("N", "V")
start <- c(0.5, 0.5)
trans <- matrix(c(0.7, 0.3, 0.4, 0.6), 2, 2, byrow = TRUE)
emit <- matrix(c(0.3, 0.4, 0.3, 0.2, 0.3, 0.5), 2, 3, byrow = TRUE)
HmmTag(X, tagset, start, trans, emit)
#> $estimate
#> [1] -7.564347
#> 
#> $path
#> [1] 1 1 1 1 1
#> 
#> $logprob
#> [1] -7.564347
#> 
#> $n
#> [1] 5
#> 
#> $method
#> [1] "Viterbi maximisation of prod P(y_t|y_{t-1}) P(x_t|y_t), Charniak (1993) ch. 3"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"