Natural Language Processing · TEE · papers

Q3a · Hobbs algorithm and limitations

2023-12-01 · final · recovered AI paper

Previous examination · complete worked answers

Question. Explain Hobbs’ algorithm with an example and state its limitations. [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.