CSC 485H/2501H: Computational linguistics, Fall 2024

Assignment 3

Overview: Symbolic Machine Translation

In this assignment, you will learn how to write phrase structure grammars for some different lin- guistic phenomena in two different languages: English and Chinese. You can use the two grammars to create an interlingual machine translation system by parsing in one, and generating in the other. Don’t panic if you don’t speak Chinese, and also don’t cheer up yet if you can speak the language — it won’t give you much of an advantage over other students. A facility with languages in general will help you, as will the ability to learn and understand the nuances between the grammars of two different languages. In particular, you will start by working on agreement. Then, you will need to analyse the quantifier scoping difference between the two languages.

TRALE Instructions    The instructions to setup and launch TRALE on teach.cs can be found in:

https://www.cs.toronto.edu/~niu/csc485/trale/setup/

1. Agreement: Determiners, Numbers and Classifiers [10 marks]

English expresses subject–verb agreement in person and number. English has two kinds of number: singular and plural. The subject of a clause must agree with its predicate: they should be both singular or both plural. However, the number of a direct object does not need to agree with anything.

(1)        A programmer annoys a dolphin.

(2)        Two programmers annoy a dolphin.

(3)      * Two programmers annoys two dolphins.

(4)      * A programmer annoy two dolphins.

Chinese, on the other hand, does not exhibit subject–verb agreement. As shown in the examples below, most nouns do not inflect at all for plurality. Chinese does, however, have a classifier (CL) part of speech that English does not. Semantically, classifiers are similar to English collective nouns (a bottle of water, a murder of crows), but English collective nouns are only used when describing collectives. With very few exceptions, classifiers are mandatory in complex Chinese noun phrases. Different CLs agree with different classes of nouns that are sorted by mostly semantic criteria. For example, 学生 (xuesheng)  student is a person and an occupation, so it should be classified by either 个 (ge) or 名 (ming) and cannot be classified by the animal CL 只 (zhi). However, the rules of determining a noun’s class constitute a formal system that must be followed irrespective of semantic similarity judgements. For example, while wolves and sheep are both animals and can both be classified by the animal CL 只 (zhi), 狼 (lang) wolf can take another classifier, 匹 (pi).

(5)        一 个   学生

yi   ge      xuesheng one ge-CL student

(6)        两  个   学生

liang ge      xuesheng two   ge-CL student

(7)        三  个   学生

san   ge      xuesheng three ge-CL student

(8)      * 三  学生

san   xuesheng three student

(9)      * 三  只   学生

san   zhi      xuesheng three zhi-CL student

(10)        一 只   羊

yi   zhi      yang  one zhi-CL sheep

(11)        两  只   羊

liang zhi      yang  two   zhi-CL sheep

(12)        三  只   羊

san   zhi      yang  three zhi-CL sheep

(13)      * 三  匹  羊

san   pi      yang  three pi-CL sheep

(14)      * 三  名     羊

san   ming      yang  three ming-CL sheep

You should be familiar by now with the terminology in the English grammar starter code for

this question. The Chinese grammar is fairly similar, but there is a new phrasal category called a classifier phrase (CLP), formed by a number and a classifier. The classifier phrase serves the same role as a determiner does in English.

The two grammars below don’t appropriately constrain the NPs generated. You need to design your own rules and features to properly enforce agreement.

Here is a list of all of the nouns in this question and their acceptable classifiers:

•  狼 lang wolf: 只 zhi; 匹 pi;

•  羊 yang sheep: 只 zhi

•  学生 xuesheng student: 个 ge, 名 ming.

(a)  (6 marks) Implement one grammar for each language pursuant to the specifications above. English: q1_en.pl and Chinese: q1_zh.pl.

Neither of your grammars need to handle embedded clauses, e.g., a student caught two wolves see a sheep. Similarly for Chinese, your grammar doesn’t need to parse sentences like example (15):

(15)    一 名  学生    看见  两  匹 狼  追逐   一 只 羊

yi  ming xuesheng kanjian liang pi  lang zhuizhu yi  zhi yang A student saw two wolves chase a sheep.

For the Chinese grammar, code the lexical entries in pinyin (the Romanized transcriptions of the Chinese characters).

(b)  (4 marks) Use your grammars to parse and translate the following sentences. Save and submit all the translation results in the .grale format. The results of sentence (16) should be named q1b_en.grale and the results of sentence (17) should be named q1b_zh.grale.

(16)    Two wolves saw one sheep

(17)    两  个 学生    追逐   三 只 羊

liang ge xuesheng zhuizhu san zhi yang

Operational Instructions

•  Independently test your grammars in TRALE first, before trying to translate.

•  Use the function translate to generate a semantic representation of your source sen- tence. If your sentence can be parsed, the function translate should open another gralej interface with all of the translation results.

| ?- translate([two,wolves,catch,one,sheep]).

•  To save the translation results, on the top left of the Gralej window (the window with the INITIAL CATEGORY entry and all of the translated sentences listed),click File >> Save all >> TRALE format.

•  Don’t forget to close all of the windows or kill both of the Gralej processes after you finish. Each Gralej process will take up one port in the server, and no one can use the server if we run out of ports.

2. Quantifier Scope [30 marks]

For this assignment, we will consider two quantifiers: the universal quantifier (every, 每 mei) and the existential quantifier (a, 一 yi). In English, both quantifiers behave as singular determiners.

(18)        A professor stole every cookie.

(19)      * A professor stole every cookies.

(20)      * A professors stole every cookie.

In Chinese, both of these quantifiers behave more like numerical determiners. In addition, when a universal quantifier modifies an NP that occurs before the verb (such as with a universally quanti- fied subject), the preverbal operator 都 (dou) is required. When a universally quantified NP occurs after the verb, the dou-operator must not appear with it.

(21)        Every professor stole a cookie.

(22)        A professor stole every cookie.

(23)        每 个   教授    都 偷了 一 块    饼干

mei ge      jiaoshou  dou  tou-le yi  kuai      binggan ∀   ge-CL professor DOU stole   ∃  kuai-CL cookie

(24)      * 每 个   教授    偷了 一 块    饼干

mei ge      jiaoshou  tou-le yi  kuai      binggan ∀   ge-CL professor stole   ∃  kuai-CL cookie

(25)        一 个   教授    偷了 每 块    饼干

yi  ge      jiaoshou  tou-le mei kuai      binggan ∃  ge-CL professor stole   ∀   kuai-CL cookie

(26)      * 一 个   教授    都 偷了 每 块    饼干

yi  ge      jiaoshou  dou tou-le mei kuai      binggan ∃  ge-CL professor dou stole   ∀    kuai-CL cookie

Quantifier Scope Ambiguity    In lecture, we talked about different kinds of ambiguity. In many English sentences, no matter what the order of the quantifiers, there is a quantifier scope ambiguity. For example, the sentence every student takes a course has two readings:

•  (∃ > ∀) Every student takes a course. [The course is Math.]

•  (∀ >  ∃) Every student takes a course.  [Some students take Math and some students take History.]

The symbol (∃ > ∀) means the existential quantifier outscopes the universal quantifier in a logical form. representation of the sentence.

Figure 1: Beta Reduction. What should be the LF of S?

We can write the semantics of the two sentences in their logical forms (LF) to distinguish the two readings:

•  ∃y.(course(y) Λ ∀x.(student(x) ⇒ take(x, y)))

•  ∀x.(student(x) ⇒ ∃y.(course(y) Λ take(x, y)))

English sentences (27, 28) are scopally ambiguous no matter what the linear order of the quan- tifiers is. But in Chinese, a sentence is scopally ambiguous only when the universally quantified NP precedes the existential NP: (29) is ambiguous, but (30) is unambiguous.

(27)    Every student takes a course Ambiguous: ∃ > ∀, ∀ > ∃

(28)    A student takes every course Ambiguous: ∃ > ∀, ∀ > ∃

(29)    每 个   学生    都  会上    一 种      课程

mei ge      xuesheng dou  huishangyi  zhong      kecheng ∀   ge-CL student     DOU take          ∃  zhong-CL course    Ambiguous: ∃ > ∀, ∀ > ∃

(30)    一 个   学生    会上   每 种      课程

yi  ge      xuesheng huishang mei zhong      kecheng ∃  ge-CL student     take         ∀   zhong-CL course    Unambiguous: ∃ > ∀

How can we derive the LF of the two readings? We use a process called beta reduction. Recall the lambda-calculus notation: λx.x2  denotes a function that takes a variable x, and returns the square of its value (x2 ). After substituting the value for the bound variable x, we can reduce the function application in the body of the lambda term to a new expression. For example, applying 2 to λx.x2 will get us:

λx.x2 (2) = 22

Figure 2: Beta reduction analysis of the sentence every student takes a course.

This process is also known as beta reduction (denoted as β ). Note that beta reduction itself does not tell us that this equals 4. That is obtained by a subsequent process of arithmetic evaluation. But we can use beta reduction even if we don’t evaluate.

We can also perform beta reduction on variables for functions. For example, applying in λF.F (2) to λx.x2  will yield:

λF.F (2) (λx.x2 ) = (λx.x2 )(2) = 22

Now, let’s look at an example that uses beta reduction to compute the LF of a sentence. For ex- ample, as shown in figure 1, we know that the LF of the NP every student is λP.丫x.(student(x) 今 P (x)) and the LF of the VP takes a course is λz.彐y.(course(y) Λ take(z, y)). What is the LF of every student takes a course?

λP.丫x.(student(x) 今 P (x))(λz.彐y.(course(y) Λ take(z, y))) 今β  丫x.(student(x) 今 λz.彐y.(course(y) Λ take(z, y))(x))

今β  丫x.(student(x) 今 彐y.(course(y) Λ take(x, y)))

Each step of repeatedly applying beta reduction to every subterm until we reach an irreducible statement is called beta normalisation.

Figure 2 shows the complete analysis of the sentence every student takes a course. Familiarize yourself with every part of the analysis. But this only generates one of the two readings – the surface reading (丫 > 彐). We will use a technique called quantifier storage to capture the scopal ambiguity and make both readings available.

Quantifier Storage    If quantifier scoping is a semantic effect, how do we represent it in syntax? When there is no ambiguity, keeping track of the quantifier scope is pretty straightforward. To keep track of and resolve scope ambiguities, we will use a list called a quantifier store. The idea behind QSTORE is that, instead of consuming all of the LF components right away, we can choose to keep them in QSTORE and apply them later.

Figure 3: Quantifier Storage. Storing the quantifier at (1), and retrieve it later at (2).

Let’s go back to the example, every student takes a course (figure 3). We first store the LF of the NP a course at (1) and replace the LF of the NP with a placeholder λF.F (z). The variable z in this expression is a free occurrence, and it is the same variable as the z in the store and in the LF of the sentence (the free occurrences of z are highlighted in red). We retrieve the logical form from the store at (2). The retrieval process consists of three steps:

1.  First, we construct a function λz.LS , where LS is the current LF, and z is the variable paired in the QSTORE entry. In our particular case, this will yield λz. (丫x, student(x) 今 take(x, z)).

2.  Then, we apply this function to the LF from the QSTORE entry.

3.  Finally, we beta normalise. Using beta normalisation, we obtain the second reading of the sentence.

λG.彐y.(course(y) Λ G(y))(λz. (丫x, student(x) 今 take(x, z))) 今β  彐y.(course(y) Λ (λz. (丫x.student(x) 今 take(x, z))(y))

今β  彐y.(course(y) Λ (丫x.student(x) 今 take(x, y))