Natural Language Processing · TEE · papers

Q3a · Hobbs and ambiguous professor–student reference

2024-12-03 · final · recovered AI paper

Previous examination · complete worked answers

Question. Explain Hobbs’ algorithm, including binding, gender, distance and recency. Resolve “The professor advised the student because she was struggling.” [10 marks]

Answer

Hobbs’ algorithm is a syntax-based procedure that searches constituent parse trees in a fixed order for a compatible noun-phrase antecedent of a pronoun. The tree determines which candidates are proposed first. Agreement and other relevant constraints determine whether a proposed candidate can be accepted.

It is not simply the rule “choose the closest noun”. A nearby noun may have the wrong number, may be syntactically ineligible, or may be visited after a structurally more prominent noun. The algorithm produces a preference under the supplied parse; ambiguous language can still require context.

The tree vocabulary you need

Term	Meaning	Example
NP	Noun phrase: a phrase referring to an entity	the student; Anita; they
S	A sentence/clause node	the node containing a subject and predicate
VP	Verb phrase	told Ravi that she should revise
X	The NP or S node currently being searched	An algorithm label, not a word
Path p	The branch travelled upward from the pronoun/previous X	Used to distinguish left and right subtrees
N-bar (N′)	The noun-centred part of an NP in a grammar using that label	The nominal-child test depends on the given tree
Breadth-first	Visit shallower nodes before deeper ones	Level 1 before level 2
Left-to-right	Visit equally deep nodes in their written/tree order	Earlier left branch before right branch

Locate pronoun NP

Climb to NP/S

Propose candidates in tree order

Check compatibility

Accept or continue searching

The complete search procedure

Step 1. Start at the pronoun

Locate the NP immediately dominating the pronoun. “Dominating” means containing it as a descendant in the tree.

Step 2. Climb to the first NP or S

Move upward to the first NP or S above that starting NP. Call this node X. Keep the upward path p.

Step 3. Search the left branches initially

Below X, traverse branches to the left of p breadth-first and left-to-right. At this initial search, propose an NP only if another NP or S lies between that candidate and X. Test proposed candidates for the required agreement and constraints.

Step 4. If X is the highest sentence node, inspect earlier sentences

Search previous sentence trees from most recent to oldest. Within each, use breadth-first, left-to-right order to propose NPs. Accept the first eligible compatible candidate, or report that no candidate was found in the available context.

Step 5. Otherwise climb again

Move from X to the next NP or S above it. Record this new X and the path followed during the climb.

Step 6. Apply the higher-NP test

If the new X is an NP, propose X when the path did not pass through its nominal N-bar child. Use the given parse labels; do not invent an N-bar branch missing from the question's structure.

Step 7. Search its left branches

Traverse branches below the new X to the left of the path, breadth-first and left-to-right, proposing NPs. The special intervening-NP/S restriction belongs to the initial search in Step 3.

Step 8. If X is S, search the permitted right branches

Search branches to the right of the path breadth-first and left-to-right. Do not descend below an encountered NP or S. Propose eligible NP candidates there.

Step 9. Repeat or stop

Return to the highest-S check and continue the climb/search procedure until a compatible candidate is accepted or the available trees are exhausted. Record the candidate order rather than only writing an unexplained name.

Why the first left search has an extra condition

In a simple clause such as “John saw him”, the subject NP John is directly under the clause S. There is no extra NP or S between John and that S. The initial-search restriction therefore prevents casually selecting John as the ordinary local antecedent of him. Compare the reflexive “John saw himself”, which is a different grammatical case; do not treat every pronoun type as interchangeable.

Worked tree 1 · move to the previous sentence

Question. Apply Hobbs’ search to “The student arrived. She smiled.” Assume the student is compatible with she.

Given

Previous tree: [S [NP The student] [VP arrived]]. Current tree: [S [NP She] [VP smiled]].

To find

The selected antecedent and the search path.

Method and why it applies

Use the supplied constituent trees. The current sentence has no earlier candidate, so the highest-S rule activates previous-sentence search.

Solution

Step 1. Draw both sentence structures

Previous sentence             Current sentence
S                             S
├── NP: The student            ├── NP: She ← start
└── VP: arrived                └── VP: smiled

Step 2. Locate and climb

Start at NP She. Its first higher NP/S is the current S. Set X to that S.

Step 3. Search left of the path

She is the leftmost subject. No NP lies to its left in the current sentence.

Step 4. Use the highest-S rule

This X is the highest S. Inspect the immediately preceding sentence tree.

Step 5. Propose its first NP

Breadth-first, left-to-right finds NP The student.

Step 6. Check compatibility and accept

The question stipulates that the student agrees with she. Accept this candidate.

Answer. She refers to the student under the supplied assumptions.

Worked tree 2 · reject an incompatible subject

Question. Resolve they in “Riya spoke to the students. They laughed.” Use a previous-sentence search and interpret they as plural.

Given

Previous tree has subject NP Riya, then VP spoke [PP to [NP the students]]. Current subject is NP They.

To find

The candidate order and accepted antecedent.

Method and why it applies

Breadth-first search favours a shallow subject, but agreement must still be applied; a first candidate is not automatically a valid answer.

Solution

Step 1. Draw the useful part of the previous tree

S
├── NP: Riya                 ← candidate 1
└── VP
    ├── V: spoke
    └── PP
        ├── P: to
        └── NP: the students ← candidate 2

Step 2. Search the current sentence

From NP They climb to its S; there is no earlier NP in “They laughed”. This is the highest S, so move to the previous tree.

Step 3. Visit Riya first

Riya is the shallower leftmost NP. Under the stated plural interpretation, this singular candidate fails number agreement.

Step 4. Visit the students

Continue breadth-first. The next relevant NP is the students.

Step 5. Apply number agreement

Students is plural and is an eligible candidate. It matches plural they.

Step 6. State the resolution

Accept the students. The method did not simply accept the first noun it saw.

Answer. They → the students. Candidate order: Riya rejected; the students accepted.

Worked tree 3 · climb out of an embedded clause

Question. Resolve she in “Anita told Ravi that she should revise.” Assume Anita is compatible with she and Ravi is not. Use the displayed parse.

Given

The pronoun is the subject of an embedded S inside the main VP.

To find

The preferred antecedent found by the climb and left-branch search.

Method and why it applies

The embedded clause has no left candidate. Climbing to the main S exposes its subject Anita as the first suitable higher-level candidate.

Solution

Step 1. Show the clause structure

S (main)
├── NP: Anita                  ← accepted candidate
└── VP
    ├── V: told
    ├── NP: Ravi
    └── SBAR: that
        └── S (embedded)       ← first X
            ├── NP: she        ← start
            └── VP: should revise

Step 2. Start inside the embedded clause

From NP she climb to the embedded S. There is no candidate to the left of she within this embedded S.

Step 3. Climb to the next NP/S

The embedded S is not the highest S. Move upward through SBAR and VP to the main S. These intermediate nodes are not NP/S search nodes.

Step 4. Search left of the upward path

At the main S, the subject NP Anita is a shallow left candidate. The object Ravi is deeper within the VP. Breadth-first order proposes Anita first.

Step 5. Check the stated compatibility

Anita is compatible with she by the question's assumption. Accept it; no need to choose a later incompatible candidate.

Step 6. Give the result and its limit

This is the algorithm's result under the displayed parse and agreement assumptions. It does not prove the intention of every speaker using an otherwise ambiguous sentence.

Answer. She → Anita under the stated tree and compatibility information.

Advantages, limitations and a complete exam answer

Advantages	Limitations
Explicit candidate order makes the decision traceable.	Wrong parse structure can produce the wrong search order.
Requires no labelled coreference-training corpus for its basic rules.	World knowledge and discourse intention may override syntactic preference.
Uses structure rather than only surface distance.	Some ambiguous, long-distance or unusual constructions need additional treatment.

For a longer answer, write the definition, inputs, tree notation, ordered algorithm, one labelled tree with a candidate table, final antecedent, and limitations. In a worked question show separately: candidate → why proposed → agreement result → accept/reject. Do not equate the selected candidate with a logically guaranteed interpretation when the sentence is ambiguous.

Yaad rakho: Tree order candidate deta hai; agreement usko allow/reject karta hai. Nearest noun automatically answer nahi.

The intended antecedent is not uniquely determined by the printed sentence. Both professor and student can be singular female people; neither noun supplies gender. Structural Hobbs search can propose the matrix subject professor early, while the causal meaning of advice because of struggling often supports student. Distance/recency favouring student is a preference, not proof.

Parse subject NP the professor, object NP the student, subordinate-clause subject she.
Generate structurally accessible earlier NPs through the Hobbs ascent and breadth-first leftward search.
Check grammatical number/person and binding constraints. Both candidates can pass here; she is not a reflexive.
Gender/world knowledge is unavailable, so do not invent either person’s gender.
Use broader discourse to select. Without it, report professor/student ambiguity; explain that contextual interpretation often prefers student but the syntax-only algorithm does not guarantee that intent.

Source / convention note. Pronoun referent is ambiguous without extra gender/discourse information; structural algorithm preference is separated from semantic interpretation.

The four requested properties

Property	What it means	Apply here
Binding	Syntactic restrictions on reference; ordinary personal pronouns and reflexives have different local-antecedent requirements	Do not mechanically link every nearby NP; he in an after/because clause can refer outside that local clause.
Gender agreement	Candidate must match the pronoun under available linguistic/contextual knowledge	John/he is the exercise’s conventional reading; professor/student do not provide gender by themselves.
Distance	Token, syntactic or sentence separation between pronoun and candidate	Closer candidates may be preferred, but cannot override incompatibility or Hobbs search order.
Recency	Recently mentioned discourse entities are often more salient	Mary/student is later than John/professor, but recency is a preference, not a guaranteed antecedent rule.