Decoding Language: A Deep Dive into Part of Speech Tagging with Dynamic Algorithms

Unpacking the Algorithms

The Eager Approach

I started with the Eager algorithm—a straightforward, no-frills approach to POS tagging. This method handles one word at a time, determining the most likely tag by considering only the tag of the preceding word and the word itself. In my script, this process unfolds within the eager_algorithm function. For each word, I sift through every possible tag, crunch the numbers by multiplying each tag’s emission probability with the transition probability from the previous tag, and then select the tag with the highest score. It’s all about making the best choice, one step at a time.

For those curious about the math behind it, the Eager algorithm relies on a straightforward formula to make these tagging decisions. The formula looks like this:

\[\hat {t}_i = \argmax _{t_i} P(t_i \mid \hat {t}_{i-1}) \cdot P(w_i \mid t_i)\]

Let me break it down:

• \(\hat{t}_i\): This represents the most likely POS tag for the \(i\)-th word in the sentence. It’s what the algorithm is trying to determine.
• \(P(t_i \mid \hat{t}_{i-1})\): This is the transition probability—it tells us how likely the current tag \(t_i\) is, given that the previous word was tagged as \(\hat{t}_{i-1}\). Essentially, it’s about how well the current tag flows from the previous one.
• \(P(w_i \mid t_i)\): This is the emission probability, which measures how likely it is that the current word \(w_i\) would be associated with the tag \(t_i\). This helps the algorithm decide which tag makes sense based on the word itself.

In essence, for each word, the algorithm selects the tag that maximizes the combination of how well it fits with the previous tag and how well it matches the current word.

The Viterbi Algorithm

Moving on to the Viterbi algorithm, things get a bit more intricate. This algorithm isn’t satisfied with just the immediate context; it looks at the entire sentence to decide the sequence of tags that makes the most sense. In my script, I implement this within the viterbi_algorithm function. It begins by filling a matrix with log probabilities for the first word across all possible tags. It then iterates over each word in the sentence, updating the matrix based on the transition probabilities, emission probabilities, and previously computed log probabilities. Finally, it backtracks from the last word to determine the most probable sequence of tags. To avoid the pitfalls of multiplying very small probabilities—which can cause numerical underflow—I use log probabilities instead. By transforming probabilities into log space, multiplication operations become additions, significantly mitigating the underflow risk. This approach is critical for the Viterbi algorithm's reliability, especially in processing long sentences where the product of many small probabilities would otherwise approach zero.

Now let's break down the formula that the Viterbi algorithm uses to find the most likely sequence of tags for a given sentence:

\[ \hat{t}_1 \cdots \hat{t}_n = \arg\max_{t_1 \cdots t_n} \left( \prod_{i=1}^{n} P(t_i \mid t_{i-1}) \cdot P(w_i \mid t_i) \right) \cdot P(t_{n+1} \mid t_n) \]

Here’s what the terms mean:

• \(\hat{t}_1 \cdots \hat{t}_n\): This represents the most likely sequence of tags for the sentence, from the first word to the last.
• \(P(t_i \mid t_{i-1})\): The transition probability, which tells us how likely the current tag \(t_i\) is, given the previous tag \(t_{i-1}\).
• \(P(w_i \mid t_i)\): The emission probability, which measures how likely it is that the current word \(w_i\) corresponds to the current tag \(t_i\).
• \(t_0 = \langle \mathit{s} \rangle\): This is the start-of-sentence marker.
• \(t_{n+1} = \langle /\mathit{s} \rangle\): This is the end-of-sentence marker.

In simple terms, the Viterbi algorithm finds the sequence of tags that maximizes the product of the transition probabilities (from one tag to the next) and the emission probabilities (how well each word fits its tag) for the entire sentence. It also factors in the start and end markers to ensure the tagging process is coherent from beginning to end.

Individually Most Probable Tags

Lastly, the individually most probable tags algorithm represents the most detailed method in my toolkit. Implemented in the most_probable_tags_algorithm function, this algorithm leverages forward and backward probabilities to optimize the accuracy of POS tagging for each word based on the context provided by the other tags in the sentence. It relies on two support functions, forward_algorithm and backward_algorithm, which compute the forward and backward probabilities for each word being assigned each possible tag.

Here’s how it works: The most_probable_tags_algorithm function first calculates the cumulative forward probabilities—those that move from the start of the sentence up to the previous word, factoring in both emission and transition probabilities. Then, it computes the backward probabilities, which run from the end of the sentence to the next word. Using the logsumexp() function, I ensure accurate summation of these probabilities. Finally, by multiplying these summed forward and backward probabilities together, the algorithm identifies the most probable tag for each word.

In more formal terms, for each \(i\), the algorithm computes:

\[ \hat{t}_i = \arg\max_{t_i} \sum_{t_1 \cdots t_{i-1}, t_{i+1} \cdots t_n} \left( \prod_{i=1}^{n} P(t_i \mid t_{i-1}) \cdot P(w_i \mid t_i) \right) \cdot P(t_{n+1} \mid t_n) \]

However, computing this directly would be inefficient. Instead, we break it down using forward and backward probabilities, similar to the Baum-Welch algorithm. The result is:

\[ \hat{t}_i = \arg\max_{t_i} \begin{array}{l} \sum_{t_1 \cdots t_{i-1}} \Bigl( \prod_{k=1}^{i} P(t_k \mid t_{k-1}) \cdot P(w_k \mid t_k) \Bigr) \cdot \\[2ex] \sum_{t_{i+1} \cdots t_n} \Bigl( \prod_{k=i+1}^{n} P(t_k \mid t_{k-1}) \cdot P(w_k \mid t_k) \Bigr) \cdot P(t_{n+1} \mid t_n) \end{array} \]

This formula ensures that we not only consider the context of each word but also maximize the probability of each individual tag, making it a highly robust tagging method.