Invitational round | 15 points | N/A | Problem statement | Official solution | Tags: ComputationalSyntax
I originally thought this is a pure math puzzle like most similar computational problems; but no this one involves non-trivial syntax theory! We need to first and foremost understand how the attention is calculated. Look at the example matrix. Most entries are .05, which is probably the "base value". The diagonal values are .60 by default. If there are other entries that are more than .05, then the diagonal is reduced accordingly to maintain the row sum. We focus on the other words that has attention.
| the | cat | eat | s | the | rat | on | the | mat | |
|---|---|---|---|---|---|---|---|---|---|
| the | |||||||||
| cat | .30 | ||||||||
| eat | .15 | .20 | .10 | .10 | |||||
| s | .40 | ||||||||
| the | |||||||||
| rat | .20 | ||||||||
| on | |||||||||
| the | |||||||||
| mat | .20 |
So there are three conclusions:
In N1, first look at the verb row. "chase" attends to subject "dog", tense "was" and aspect "-ing", object "cat", and location "yard". The weights satisfy object = location < subject < tense = aspect. Furthermore if the verb attends to X with weight w, then X attends to the verb with weight 2w. All as expected.
a. "fast" is not one of the verb's attentions, so it only attends to itself, like "the": fast→fast = .60.
b. For non-diagonal entries, the base value is used: fast→dog = .04.
c. chase→cat = .08, so cat→chase = .16, leaving cat→cat = 1 － .04×9 － .16 = .48.
d. chase→yard = .08, so yard→chase = .16.
Now we need to understand how the attention weights are calculated for the verb. We know that:
Obviously there's a fixed proportion of the constituents: verb itself = 5x, tense = aspect = 4x, subject = 3x, object = location = 2x, other parts = 1x. We just need to calculate x based on the sum.
Therefore in "the cat meowed", the verb itself gets 5x, tense gets 4x, subject gets 3x, "the" gets x; they total to 12x, so x = 1/12, and we should get meow→meow = .417. However the problem says .40, so we need to adjust the proportions as: 4x, 3x, 2x, x (i.e., since there's no object or location, the higher-priority constituents have lower proportions too). This gives x = .10 and meow→meow = .40, exactly what we want. Therefore, (f) meow→cat = 2x = .20; (g) meow→ed = 3x = .30; meow→the = x = .10 (base value). Vertically, every non-diagonal, non-base entry is double the corresponding horizon entry: (e) cat→meow = .40; (h) ed→meow = .60. Finally the other two grayed cells of "ed" are both .10, so (i) ed→ed = .20.
For N3, we again focus on the non-diagonal, non-base values. There's exactly one row per table with multiple non-base values.
For A and E, we don't have the 5x rank, so they are missing something. We know that the highest-ranked must be the verb, and the lowest must be "other".
For E, 3 should be "tense" and 2 should be "subject", because the verb-tense-subject order is present in B and C too. However, I don't want to do the same for A, because that creates verb-subject-object and puts a "tense" at the beginning, both of which we've never seen. Instead, if we assume that 3 is "subject" and 2 is "object", then we create the familiar verb-object-subject order seen in D.
Take a brief look at the scripts. Notice that we have 1 4-word sentence, 3 3-word sentences, and 2 2-word sentences. Naturally, these words correspond to: subject, object, verb, location. Presumably, the trailing "object" and "subject" after the verb itself are just agreement markers, and so is the "tense", so this whole thing is one word. Also presumably, "other" after the object should be merged with the object; otherwise A would have 5 words. It's unclear if sentence-initial "other" should be merged too, but I assume no, because otherwise we have 3 3-word sentences.
But in any case, there's one matrix (A) with two lexical objects (plus subject and verb), and one sentence (4) with 4 words, so they must match.
We are looking for a sentence that matches one of the English sentences: The cat eats the rat on the mat., The dog was chasing the fast cat around the yard., The cat meowed.. The last, should it match one, may only match the subject-only E, but E requires the existence of an "other" morpheme (which is not the determiner; determiners are probably unmarked in this language due to the general insufficiency of "other" morphemes). The first two sentences both contain 4 constituents, so either one must be A. A does not have tense, but the second sentence has marked past tense, so only The cat eats the rat on the mat. is viable, also revealing to us that present tense is unmarked in this language.
The words "rat" appeared again in 1. ᱜᱩᱵᱩ-ᱥᱮᱡ ᱦᱮᱡᱮᱱᱟᱠᱳ. Because it's suffixed by something, this matches the pattern for C. (ᱥᱮᱡ = "toward" is not deducible from the data.)
The word "cat" appears again in 5. ᱥᱮᱛᱟ ᱯᱩᱥᱤ-ᱥᱟᱶ ᱦᱮᱡᱳᱜᱟᱮ. Because it's also suffixed by something, this matches the pattern for B. (ᱥᱮᱛᱟ = "dog", ᱥᱟᱶ = "with" are not deducible from the data.)
Whatever ᱥᱮᱛᱟ is, it must be a noun like "cat" and "rat" because it's in subject position. It appears in 6. ᱥᱮᱛᱟ-ᱥᱟᱶ ᱨᱚᱲᱮᱱᱟᱧ. Due to the extra suffix, it must again be the (C) structure.
Now we know that C has been used twice, the other two matrices, D and E, shall only be used once for 2 and 3. In 3, look at the verb word: ᱨᱚᱲᱮᱱᱟᱮ. "ᱮᱱ" appears in 1 and 6 in the middle; "ᱟᱮ" appears in 4 and 5 at the end; "ᱨᱚᱲ" appears in 6 at the beginning. Put together, this should correspond to V-T-S, so 3 is E, leaving 2 to be D.
For N5, we must tokenize these sentences.