Constituency
Hypertext and constituency
Results and discussion
References.

.

The Constituency of Hyperlinks
in a Hypertext Corpus
mitcho (Michael Yoshitaka Erlewine)
Massachusetts Institute of Technology
mitcho@mitcho.com

International Society for the Linguistics of English
Boston University, June 19, 2011

The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

The generative notion of constituency
Testing constituency
The limits of constituency tests. The generative notion of constituency

Certain substrings of sentences form natural units of linguisticimport. Such units are called constituents.
Constituents are motivated and veriﬁed empirically byconverging evidence of different kinds.

The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

The generative notion of constituency
Testing constituency
The limits of constituency tests. Constituency tests(1)

John ate an old hamburger.

Q: Is “an old hamburger” a constituent?
a) Clefting:It’s an old hamburger that John ateb) Fronting:
An old hamburger, John ate.

.

ok!

, but a fresh orange, he didn’tok!

c) Substitution:
Mary ate an old hamburger and John ate one too.
(“one” = “an old hamburger”)

The Constituency of Hyperlinks in a Hypertext Corpusok!

Constituency
Hypertext and constituency
Results and discussion
References

The generative notion of constituency
Testing constituency
The limits of constituency tests. Constituency tests(1)

John ate an old hamburger.

Q: Is “ate an old” a constituent?
a) Clefting:It’s ate an old that Johnb) Fronting:Ate an old, Johnhamburger.
hamburger...

c) Substitution:
Mary ate an old hamburger and John did sandwich too.
(“did” ≠ “ate an old”)

The Constituency of Hyperlinks in a Hypertext Corpus

no!
no!
no!

Constituency
Hypertext and constituency
Results and discussion
References

The generative notion of constituency
Testing constituency
The limits of constituency tests. Constituency structure
Constituents are organized hierarchically, reﬂecting a phrase
structure grammar:
SNP

VPNVJohnateNP
DetanA

Noldhamburger

The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

The generative notion of constituency
Testing constituency
The limits of constituency tests. Other converging evidence

Other forms of converging evidence for constituency:
Pscholinguistic evidence (Fodor et al., 1974, a.o.)Compositional semantics which tracks syntactic constituency(though perhaps not always perfectly), following Frege, Davidson,
Montague

The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

The generative notion of constituency
Testing constituency
The limits of constituency tests. The limits of constituency tests
Unfortunately, in some cases constituency tests may not apply or
may yield conﬂicting results.
Important proposals exist where constituency is at issue:
Binary branching (Kayne, 1984, a.o.)Branching in phrase structure grammars are always binary, notn-ary.
The DP hypothesis (Abney, 1987)
D(eterminers) are the head of what have traditionally been labeled“Noun Phrases,” with the D taking the Noun Phrase proper as its
complement.

As such, novel methodologies for constituency veriﬁcation arewelcome.

The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

Observation and goals
Methodology. Hypertext and constituency
Observation:
Not just any substring of sentences can be turned into hyperlinks.
Potential candidates seem to be rule-governed in some way.
http://metafilter.com/85556:
thoseagree
intheﬁght

The text “in the ﬁght agree” is not a syntactic constituent.
Upon closer inspection, it turns out this is actually two links:(4)... and those in the ﬁght agree.

The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

Observation and goals
Methodology. Goals. Test to what extent hyperlinks reﬂect the constituent structure of
their host sentences.
☞ Strong correlation!
2. Present a novel class of linguistic data, non-constituent links, for1

further study.

The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

Observation and goals
Methodology. A common insight: Spitovsky et al. (2010)

A connection between HTML markup and dependencies
Unsupervised grammar induction of a dependency-based parser(Klein and Manning, 2004) on a hypertext corpus, withconstraints limiting dependencies from within each markup
region5% improvement over previous state-of-the-art
But only minimal discussion of what kinds of linguistic objects
hyperlinks are

The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

Observation and goals
Methodology. Methodology
Corpus:MetaFilter (http://metafilter.com), a large, link-rich website.
Currently about 100,000 “entries.”
5.7m words, 375k human-annotated links.
Evaluation:
Statistical parsing in lieu of manual coding, as a ﬁrst
approximation
Parse the entry texts using the Stanford Parser (Klein andManning, 2003) trained primarily on the Wall Street Journal
section of the Penn Treebank (PTB; Marcus 1993).
Find the subset of the parse tree that corresponds to the link.
Check if this is a constituent.

The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

Observation and goals
Methodology. Methodology
Entry 85556:

SSCCSandOctober’s focus
on breast cancer
NP
is a curvy pinkdouble-edged
NPsword
PPDT

IN

thoseinVP
VBPNPDTNN

theﬁghtagree

The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

Results
Grammatical sensitivity
Non-constituent links
Conclusion. Results
A work-in-progress metric:
76.2% of all hyperlinks in the corpus are constituents.
This value is after one type semi-supervised correction of nounphrase structure.
“Out of the box”: 72%
Choosing random subsentences (null hypothesis) we would
expect ≈27.6% constituency.
Preliminary sampling and manual coding indicates anoverwhelming number of false negatives.

Average number of words per sentence: 15.658 (≈ 16)
P(link being constituent in 15-word sentence) =constituents in 15-word sentence = 15+15−1 = 29 = 27.6%
105
number of subsentences(152)
The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

Results
Grammatical sensitivity
Non-constituent links
Conclusion. Sources of error: n-ary branching
The Stanford Parser trained on the PTB produces n-arybranching structures (5a).
A common conﬁguration tagged by this methodology as a“non-constituent” are noun phrases missing their Determiners.
(5)

a.

b.

NP

DT

ADJP

NNPNN

the$CD

Aeronchair$800DP
DNP

the$800 Aeron chair

In a modern syntax following Abney’s (1987) DP hypothesis,“$800 Aeron chair” would actually be a constituent (5b).
This source of error has been adjusted for.
The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

Results
Grammatical sensitivity
Non-constituent links
Conclusion. Types of links by POS
Lowest node dominating all of the link:
POS
NP
S
NNP
VP
NN
NNS
JJ
RB
CD
PRN
FRAG
PP...

N
150458
46434
30651
25487
25173
12739
11228
7703
7201
6527
5409
4312

%
39.9986
12.3443
8.14846.77566.69213.38662.98492.04781.9144
1.7352
1.43801.1463<1Over 58% nominal
Spitovsky et al. (2010)
found 74.5% to be nominal
using the same metric, butwith a different corpus.
12.3% sentential, 6.8% verb
phrase-level

The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

Results
Grammatical sensitivity
Non-constituent links
Conclusion. A typology of “non-constituents”

Links deemed to be “non-constituents” by this methodology arethen categorized in terms of what material is missing which, ifincluded, would result in a constituent.
(6)

A Virginia jury has [found Ahmed Omar Abu Ali [guilty ofterrorism related crimes]].
46912⇒ Missing: PP after the link

The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

Results
Grammatical sensitivity
Non-constituent links
Conclusion. A typology of “non-constituent links”
Missing nodes from links classiﬁed as “non-constituents”:
category
PPDTNP
PRN
SBAR
JJ
NNPNNCC
NNP
VP...

position
after
before
after
after
after
beforeafter
beforeafterbefore
afterN
9166
8850
6173
4834
4571
4118
3602
3286
2999
2963
2859

%
12.17%
11.75%
8.19%
6.42%
6.07%
5.47%
4.78%
4.36%
3.98%
3.93%
3.79%

But it cannot just be that certain linguistic units in certain
positions (PPs on the right) tend to be left off...
The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

Results
Grammatical sensitivity
Non-constituent links
Conclusion. Grammatical sensitivity

Consider the frame “V NP PP.”
If V transitive, PP adjunct. If V ditransitive, PP argument.
Identical structure via the Stanford/PTB parser:
VPVNP

PP

The n-ary branching structure may again lead to false negatives.

The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

Results
Grammatical sensitivity
Non-constituent links
Conclusion. “V NP PP”
A more modern syntactic theory would structurally distinguishthe two PPs:1
PP adjunct:
VPVNP

PP

PP argument of V:
VPVNP

PPPredictions:
1. Linking “V NP PP” should entail that the PP is an adjunct.

. Linking “V NP PP” but not “V NP PP” indicates that the V isditransitive.

2The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

Results
Grammatical sensitivity
Non-constituent links
Conclusion. “V NP PP”
Verbs in “V NP PP” frame by link conﬁgurations

The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

Results
Grammatical sensitivity
Non-constituent links
Conclusion. Non-constituent links
Legitimate non-constituent links exist:(7)...the NY Times reports that the F.D.A. is cracking down. 21196(8)

If you’re going to kill off an entire section of a newspaper andﬁre all of the staffers who work there, it’s probably a goodidea to get the Twitter password ﬁrst.
87944

Intuitively:(8’)* ...kill off an entire section of a newspaper and ﬁre all of thestaffers who work there...

(8”)* ...kill off an entire section of a newspaper and ﬁre all of thestaffers who work there...
The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

Results
Grammatical sensitivity
Non-constituent links
Conclusion. Non-constituent links

These non-constituent links are not random; they are also
rule-governed in some way.
Perhaps it’s a semantic condition of referentiality?
The same string potentially being a constituent in a similarsentence?

The legitimate non-constituent links seem to be an interestingclass of linguistic objects which warrant further study.

The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

Results
Grammatical sensitivity
Non-constituent links
Conclusion. Conclusion. Hyperlinks have a strong tendency to reﬂect the constituent
structure of their host sentences, showing sensitivity to structural
distinctions.
2. The seeds of a novel methodology of studying hyperlink markup
1in a hypertext corpus to investigate syntactic constituency.
. True non-constituent links exist, but seem to form an interestingclass of linguistic objects which warrants further study.

3A novel type of linguistic data: a natural class of non-constituents

The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

Results
Grammatical sensitivity
Non-constituent links
Conclusion. Next steps

A more precise evaluation of the hyperlink-constituency
hypothesis, using sampling and manual coding.
Improvement of project corpus and tools, to be madepublicly-accessible.
Potentially, expansion of corpus and tools to another language.

The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

Results
Grammatical sensitivity
Non-constituent links
Conclusion. Acknowledgements

Many thanks to my UROP researchers and contributors:
Patrick Hulin, Patrick Hurst, and Antony Nguyen (MIT)
Vedrana Janković (Faculty of Electrical Engineering and Computing,Croatia)
and to David Barner, David Pesetsky, and Stuart Shieber for comments anddiscussion. All errors are my own.

The Constituency of Hyperlinks in a Hypertext Corpus

Constituency
Hypertext and constituency
Results and discussion
References

Abney, Steven. 1987. The English noun phrase in its sentential aspect.
Doctoral Dissertation, Massachusetts Institute of Technology.
Fodor, Jerry Alan, Thomas G. Bever, and Merrill F. Garrett. 1974. The
psychology of language: an introduction to psycholinguistics and generativegrammar. McGraw-Hill.
Kayne, Richard. 1984. Connectedness and binary branching. Foris, Dordrecht.
Klein, Dan, and Christopher D. Manning. 2003. Accurate unlexicalizedparsing. In Proceedings of the 41st Meeting of the Association for Computational
Linguistics, 423–430.
Klein, Dan, and Christopher D. Manning. 2004. Corpus-based induction ofsyntactic structure: Models of dependency and constituency. In ACL.
Larson, Richard K. 1988. On the double object construction. Linguistic Inquiry
29:335–392.
Marcus, Mitchell P. 1993. Building a large annotated corpus of English: thePenn Treebank. Computational Linguistics 19.
Spitovsky, Valentin I., Daniel Jurafsky, and Hiyan Alshawi. 2010. Proﬁting
from mark-up: Hyper-text annotations for guided parsing. In Proceedingsof ACL-2010.
The Constituency of Hyperlinks in a Hypertext Corpus