(def categories '(N V Adj Adv P stop))

(def vocabulary '(Call me Ishmael))

(defn logsumexp [& log-vals]
  (let [mx (apply max log-vals)]
    (+ mx
       (Math/log2
	     (apply +
	       (map (fn [z] (Math/pow 2 z))
		    (map (fn [x] (- x mx))
			log-vals)))))))
			
(defn flip [p]
  (if (< (rand 1) p)
    true
    false))

(defn sample-categorical [outcomes params]
  (if (flip (first params))
    (first outcomes)
    (sample-categorical (rest outcomes)
                        (normalize (rest params)))))

(defn score-categorical [outcome outcomes params]
  (if (empty? params)
    (throw "no matching outcome")
    (if (= outcome (first outcomes))
     (Math/log2 (first params))
      (score-categorical outcome (rest outcomes) (rest params)))))

(defn normalize [params]
  (let [sum (apply + params)]
  (map (fn [x] (/ x sum)) params)))

(defn sample-gamma [shape scale]
(apply + (repeatedly
  shape  (fn []
		     (- (Math/log2 (rand))))
		)))

(defn sample-dirichlet [pseudos]
  (let [gammas (map (fn [sh]
                     (sample-gamma sh 1))
                pseudos)]
				(normalize gammas)))

(defn update-context [order old-context new-symbol]
  (if (>= (count old-context) order)
    (throw "Context too long!")
    (if (= (count old-context) (- order 1))
      (concat  (rest old-context) (list new-symbol))
      (concat old-context (list new-symbol)))))

(defn hmm-unfold [transition observation order context current stop?]
  (if (stop? current)
    (list current)
    (let [new-context (update-context
	           order
		       context
		       current)
	        nxt (transition new-context)]
	  (cons [current (observation current)]
	  (hmm-unfold
	         transition
	         observation
	         n-gram-order 
			 new-context
			 nxt
			 stop?)))))

(defn all-but-last [l]
  (cond (empty? l) (throw "bad thing")
        (empty? (rest l)) '()
        :else (cons (first l) (all-but-last (rest l)))))

In the last chapter, we derived the Viterbi algorithm as a way of implementing the principle of maximum likelihood for parsing problem for HMMs and FSAs. In this chapter, we turn to the Bayesian formulation of this problem. In the Bayesian setting we wish to give some representation for the entire posterior distribution over sequence of categories given the observed sentence, rather than finding a single point estimate for the probability of the sentence.

Recall the definition of conditional probability from Independence, Marginalization, and Conditioning.

\[\Pr(H=h \mid D=d)=\frac{\Pr(D=d, H=h)}{\sum_{h'\in H} \Pr(D=d H=h')}=\frac{\Pr(D=d ,H=h)}{\Pr(D)}\]

In the case of the HMM/FSA this becomes:

\[\Pr(c^{(1)},\cdots,c^{(k)} \mid w^{(1)}, \cdots, w^{(k)})=\frac{\Pr(w^{(1)}, \cdots, w^{(k)}, c^{(1)},\cdots,c^{(k)})}{\sum_{\bar{c}^{(1)},\cdots,\bar{c}^{\prime (k)}} \Pr(w^{(i)},\cdots, w^{(i)}, \bar{c}^{(1)},\cdots,\bar{c}^{(k)})}\]

Substituting in the expressions capturing the conditional independence assumptions of the model, we define our desired posterior distribution over categories.

\[\Pr(c^{(1)},\cdots,c^{(k)} \mid w^{(1)}, \cdots, w^{(k)})=\frac{\prod_{i=1}^k \Pr(w^{(i)} \mid c^{(i)}) \Pr(c^{(i)} \mid c^{(i-1)})}{\sum_{\bar{c}^{\prime (1)},\cdots,\bar{c}^{\prime (k)}}\prod_{i=1}^k \Pr(w^{(i)} \mid \bar{c}^{(i)}) \Pr(\bar{c}^{(i)^\prime} \mid \bar{c}^{(i-1)})}\]

As we have seen several times now with this class of models, computing such posterior probabilities in the naive way is intractable. In the next lectures, we will examine techniques for handling this.

---

← 31 The Viterbi Algorithm 33 Exact Sampling and Scoring →