(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 list-unfold [generator len]
  (if (= len 0)
    '()
    (cons (generator)
    (list-unfold generator (- len 1)))))

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


  

In Heads and Dependents, we introduced the notions of heads, dependents, and argument structure as critical aspects of linguistic theory that were difficult to capture with FSAs/HMMs. By modeling phrasal dependence between parent and child phrases (or predicates and arguments, heads and dependents), we showed how contex-free grammars could model the center embedded structures which are captured in formal languages such as \(a^n b^n\) or \(\alpha \alpha^R\) but are beyond the capacity of finite-state automata.

Is the ability to model such basic dependence between phrase types sufficient for capturing natural language syntax? It turns out that it will get you pretty far. Most modern theories of grammar make use of some mechanism for modeling phrasal dependence as their backbone. Nevertheless, it is widely believed that this kind of phrasal dependence is not sufficient for capturing all syntactic phenomena.

In the history of generative approaches to syntax, arguments against the adequacy of context-free grammars for natural language syntax date back to the introduction of the formalism by Chomsky in the 1950s. However, the most compelling arguments were based on appeals to elegance or parsimony, rather than formal-language theoretically rigorous arguments.

It was in the 1980s, that rigorous arguments first emerged. The most famous of these concerns Swiss German data. Consider the following sentence with its gloss and translation.

Jan saït das mer d’chind em Hans es huus haend wele laa hälfe aastriche

Jan says that the children-ACC Hans-DAT the house-ACC have wanted let[ACC] help[DAT] paint[ACC]

Jan says that we have wanted to let the children help Hans paint the house

The key linguistic phenomenon here is that in Swiss German certain verbs take dative objects (i.e. help) while others take accusative objects (e.g., paint, let). Each verb is matched with its object and the dependencies are cross serial. That is, the verbs appear in the same order as their objects. This structure can be repeated indefinitely leading to an unbounded set of cross-serial dependencies.

Jan saït das mer d’chind d’chind em Hans em Frans es huus haend wele laa laa hälfe hälfe aastriche

Jan says that the children-ACC the children-ACC Hans-DAT Frans-DAT [the house-ACC have wanted] let[ACC] let[ACC] help[DAT] help[DAT] paint[ACC]

Jan says that we have wanted to let the children let the (other) children help Hans help Frans paint the house.

We can formalise this argument by giving a homomorphism.

\[\begin{eqnarray} h(d'chind) & = & a \\ h(em\ Hans) & = & b\\ h(laa) & = & c\\ h(h\ddot{a}lfe) & = & d\\ h(Jan\ sa\ddot{i}t\ das\ mer ) & = & w\\ h(es\ huus\ haend\ wele ) & = & x\\ h(aastriiche) & = & y\\ h(s) & = & z \ \mathrm{otherwise} \end{eqnarray}\]

We apply this homomorphism to Swiss German and then intersect the result with the regular langauge \(wa^* b^* xc^* d^*y\). The result is the language \(wa^m b^n xc^m d^n y\). This language is not context free by the pumping lemma in the last chapter.

---

← 49 The Pumping Lemma for CFLs 51 Adjunction →