30 Parsing and Inference

(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?)))))

  

Earlier in the course we introduced the idea of Principles of Inductive Inference and discussed two such principles: the Principle of Maximum Likelihood and Inference Using Conditionalization. Recall that a principle of inductive inference provides a way of choosing amongst elements of a hypothesis space in light of some evidence.

Hidden Markov models and finite-state automata introduced a new kind of hidden or latent structure into our modeling idiom: sequences of categories or states. Given a sequence of words, we must perform some kkind of inference to reason about the sequence of unobserved categories over those words. Computation done to perform such inference about the latent structure underlying sentences is so important in computational linguistics that it has a special name: parsing. Over the next several lectures, we will consider different approaches to parsing for finite-state/hidden-Markov models. These approaches can again be categorized into maximum likelihood methods which, as before, seek a single sequence of categories which maximizes the probability of the data and Bayesian methods which, as before, seek tocapture the whole conditional distribution over category sequences given the observed sequence of words.

← 29 Determinism and Non-Determinism 31 The Viterbi Algorithm →