Processing of the Natural Language for Information retrieval

The algorithm of Viterbi

The algorithm of Viterbi initially was developed to find, given a sequence of symbols, the series of transitions more probable between the states of a chain of Markov necessary to produce this sequence. This problem is the equivalent markoviano to the syntactic analysis in a estocástica regular grammar and it serves to us like desambigüación tool.

    The algorithm of Viterbi is a particular case of the algorithm of Dynamic Programming used to find a extremal way in a multi-stage graph. Like in the case of the syntactic analysis for nondeterminist regular grammars, one resorts to trellis, but in this case weight, not is defined the function the dominion of the boolean ones, but in the interval [0..1], since now it represents the probability of a rule or transition:

and the functions “extremiza” by “max” and [are replaced respectively circlemultiply] by the product:

At the end of process C (n, |Q|) it provides the probability (of Maxima probability) of which the analyzed chain belongs to the language of the grammar.

References:

Conference ISWC2003
Semantic Web

Downloads:

Date completes update: 05 of April of 2.007