POS-Tagging

6.1: sum the likelihoods of all 8 sequences: total $19/162$; those with $h_2 =$ plus: $25/486$. Hence $\Pr(h_2 = \text{plus} \mid o) = \dfrac{25/486}{19/162} = \dfrac{25}{57}$. 6.2: great is emitted only by plus and bad only by minus, so only (plus, minus, plus) has positive probability: $\frac12 \cdot \frac23 \cdot \frac23 \cdot \frac13 \cdot \frac23 \cdot \frac23 = \frac{8}{243}$. It is the most likely sequence.

def compute_likelihood(obs, states):
    p = iprob[states[0]] * eprob[states[0]][obs[0]]
    for i in range(1, len(obs)):
        p *= tprob[states[i-1]][states[i]] * eprob[states[i]][obs[i]]
    return p

def brute_force_hmm(obs):
    best, best_p = None, -1
    for a in range(2):
        for b in range(2):
            for c in range(2):
                p = compute_likelihood(obs, [a, b, c])
                if p > best_p:
                    best, best_p = [a, b, c], p
    return best

Observations GOOD, BAD. Initial: $P(\text{SUNNY}) = 3/4$, $P(\text{RAINY}) = 1/4$. Emissions: $P(\text{GOOD} \mid \text{SUNNY}) = 1$, $P(\text{BAD} \mid \text{SUNNY}) = 0$, $P(\text{GOOD} \mid \text{RAINY}) = P(\text{BAD} \mid \text{RAINY}) = 1/2$. Transitions: SUNNY$\to$SUNNY $1$, RAINY$\to$RAINY $1$ (others $0$). Greedy: step 1: SUNNY $3/4 \cdot 1 = 3/4$ beats RAINY $1/4 \cdot 1/2 = 1/8$, so $h_1 =$ SUNNY. Step 2: SUNNY gives $1 \cdot 0 = 0$, RAINY gives $0 \cdot 1/2 = 0$. Stuck, overall probability $0$. Viterbi: RAINY, RAINY has probability $\frac14 \cdot \frac12 \cdot 1 \cdot \frac12 = \frac1{16} > 0$ and is chosen. The greedy algorithm is locally optimal at step 1 but gets trapped; Viterbi finds the globally optimal path.

False. $D = \{1, 2\}$, $f(1) = 5$, $f(2) = 2$, $g(1) = 2$, $g(2) = 5$: $\max f g = \max\{10, 10\} = 10$, but $\max f \cdot \max g = 25$.

1. Along with the END tag, transition probabilities from the last hidden state to END were introduced.
2. They were also learned from data.
3. They reflect that some tags are more likely as the final tag of a sentence.
4. So yes, the END tag influences the result: it encodes prior knowledge about which tags end a sentence and can change which path Viterbi selects.