Return to basic course information.
Assigned: Wednesday, 9 April 2014
Due: 11:59pm, Thursday, 25 April 2014
For background on formal semantics see the lecture slides, Jurafsky & Martin chapters 18-20, or also the NLTK book, chapter 10.
[12 points] Translate the following sentences into quantified formulas of first-order logic:
[12 points] Translate the following verb phrases using $\lambda$-abstracts and quantified formulas of first-order logic:
[6 points] Let $g = chase$ and $h = \lambda x.\forall y.(dog(y) \Rightarrow chase(x, y))$. If $h = f(g)$, write down a $\lambda$-abstract for $f$.
[7 points] Let $g = give$ and $h = \lambda z.\lambda x.\exists y.(present(y) \wedge give(x, y, z))$. If $h = f(g)$, write down a $\lambda$-abstract for $f$.
Dekai Wu's inversion transduction grammar is a special case of synchronous context-free grammar. Furthermore, a special case of ITG is a bracketing transduction grammar (BTG), which has only one nonterminal. See the MT slides for more on ITG and bilingual parsing. If you're interested, you could also look at Dekai Wu's original paper from Computational Linguistics back in 1997.
For this section, we will be aligning English and German sentences with the following BTG: \begin{eqnarray*} A & \xrightarrow{e^{-1}} & [ A\ A ] \\ A & \xrightarrow{e^{-2}} & \langle A\ A \rangle \\ A & \xrightarrow{e^{-20}} & <English\ word> / \epsilon \\ A & \xrightarrow{e^{-21}} & \epsilon / <German\ word> \\ \ldots \end{eqnarray*} The rest of the grammar consists of word-to-word translation probabilities. For the present purposes, note that we assign all English-to-$\epsilon$ (empty word) alignments the uniform, small probability of $e^{-20}$; $\epsilon$-to-German alignments have probability $e^{-21}$. Recall that the rule $A \rightarrow \langle A\ A \rangle$ reverse the order of its children in German compared to English.
[5 points] Suppose that the grammar contains the following translation rules: \begin{eqnarray*} A & \xrightarrow{e^{-7.82}} & ! / ! \\ A & \xrightarrow{e^{-15.4}} & \mathrm{wonderful} / \mathrm{wunderbar} \end{eqnarray*} Given the following English-German sentence pair:
wonderful ! wunderbar !write down an expression for the probability of the following word alignment: \begin{matrix} \mathrm{wonderful} & \mathrm{!} \\ | & | \\ \mathrm{wunderbar} & \mathrm{!} \end{matrix}
[10 points] Given the grammar and sentence pair above, write down an expression for the probability assigned to all possible word alignments of that sentence pair. Since some alignments have the same score, you should be able to write down an expression that's simpler than exhaustive enumeration. There are some derivations that result in identical word alignments. Give an example of such an ambiguous alignment.
The next few questions use the following data:
test.en:
100 short English sentences, of no more than 10 words each, from
the European Parliament corpus, with all words lowercased;test.de:
German translations of those 100 sentences; anditg.dict: a probabilistic
translation dictionary with 1874 entries. This dictionary was
estimated by aligning parallel text from the Europarl corpus (not
including the sentences above). Entries containing words not
in the 100 sentence pairs above were removed, and not all word
pairs are included. Each line in this file contains an English
word, a German word, and a log probability, separated by tab
characters.[20 points] Write a parsing program that outputs the best word alignment for each sentence pair, given the grammar and dictionary. As with monolingual CKY, all rules are either binary, or unary terminal productions. In monolingual CKY, you need to keep track of the beginning and ending points of your constituents. Here, you need to keep track of constituent spans in two languages simultaneously. Please email your source code and any instructions for compiling and running it.
[5 points] In the alignments produced by your program, what percentage of the German words were aligned to $\epsilon$? What percentage of the English words were aligned to $\epsilon$?
[5 points] What percentage of the time was the “swap” rule $A \rightarrow \langle A\ A \rangle$ used, compared to the “in-order” rule?
[5 points] Disable the swap rule in your program. Now, alignments will be ``monotonic'', to use the MT jargon. What percentage of German and English words are aligned to $\epsilon$?