(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 introduced Gibbs sampling for HMMs. Gibbs sampling is a special case of a general set of techniques called Markov chain monte carlo (MCMC). The idea behind MCMC is that we can sampling from a complicated distribution by taking small steps that are conditioned on the preceding sample. Frequently, MCMC works by sampling a small subset of the random variables in a complex joint distribution while leaving the others fixed—this was how our Gibbs sampler worked.

Recall that earlier in the course we used the term Markov model to refer to n-gram models or strictly-local models. Markov chain is a more general term for stochastic processes defined by transition distributions from one state to the next.

Consider the Gibbs sampler. Our states here are point in the joint distribution over derivations and parameter values. By sampling from the conditional posteriors over parameters and derivations we are leaving most of the state space fixed while making small, correlated moves. Thus, our Gibbs sampler defines a Markov chain.

A important concept in the theory of Markov chains is the notion of a stationary distribution. The stationary distribution is a distriubution over states that represents the long run average of the amount of time the chain will stay in each state if you ran it forever.

---

← 38 Gibbs Sampling 40 Heads and Dependents →