MUNI
FI
Grouping Words
PA154 Language Modeling (7.1)
Pavel Rychly
pary@fi.muni.cz March 30,2023
Linguistic Objects in this Course
Trees (with strings at the nodes)
■ Syntax, semantics
■ ALgorithms: Generation, parsing, inside-outside, build semantics Sequences (of strings)
■ n-grams, tag sequences
■ morpheme sequences, phoneme sequences
■ ALgorithms: Finite-state, best-paths, forward-backward "Atoms" (unanaLyzed strings)
■ Words, morphemes
■ Represent by contexts - other words they occur with ALgorithms: Grouping similar words, splitting words into senses
Source: Natural Language Processing (600.465) Jason Eisnerjonns Hopkins Univ. www.cs.jn u.edu/~jason/465/
^avel Rycniý ■ Grouping Words ■ March 30,2023
^avel Rycniy ■ Grouping Words ■ Marcn 30,2023
A Concordance for "party" - from www.webcorp.org.uk
WebCorOg
Concordance the web in real-time.
Search      Wordlist Tool      User Guide      WebCorp LSE      Publications Feedback
Wet'Corp Live lets you access the Web as a ojiplis - a large irijlleclion jf texts from which examples of real language use can be extracted. More...
Case Insensitive: j
Span: | 50 characters *|
Language:     |.Jo, Sp-ecifled
Advanced Options
^avel Rychlý ■ Grouping Words ■ March 30,2023
A Concordance for "party" - from www.webcorp.org.uk
■ thing. She was taLking at a party thrown at Daphne's restaurant in
■ have turned it into the hot dinner-party topic. The comedy is the
■ seLection for the WorLd Cup party, which wiLL be announced on May 1
■ in the 1983 generaL eLection for a party which, when it couLd not bear to
■ to attack the Scottish NationaL Party, who Look set to seize Perth and
■ that had been passed to a second party who made a financiaL decision
■ the by-pass there wiLL be a street party. "Then," he says, "we are going
■ number-crunchers within the Labour party, there now seems LittLe doubt
■ poLiticaL tradition and the same party. They are both reLativeLy AngLophiLic
■ he toLd Tony BLair's modernised party they must not retreat into "warm
■ "Oh no, I'm just here for the party," they said. "I think it's terribLe
■ A future obLiges each party to the contract to fuLfU it by
■ be signed by or on behaLf of each party to the contract." Mr David N
^avelRycniý ■ Grouping Words ■ Marcn 30,2023 4/27
What Good are Word Senses?
■ thing. She was taLking at a party thrown at Daphne's restaurant in
■ have turned it into the hot dinner-party topic. The comedy is the
■ seLection for the WorLd Cup party, which wiLL be announced on May 1
■ in the 1983 generaL eLection for a party which, when it couLd not bear to
■ to attack the Scottish NationaL Party, who Look set to seize Perth and
■ that had been passed to a second        who made a financiaL decision
■ the by-pass there wiLL be a street party. "Then," he says, "we are going
■ number-crunchers within the Labour party, there now seems LittLe doubt
■ poLiticaL tradition and the same party. They are both reLativeLy AngLophiLic
■ he toLd Tony BLair's modernised party they must not retreat into "warm
■ "Oh no, I'm just here for the party," they said. "I think it's terribLe
■ A future obLiges each        to the contract to fuLfU it by
■ be signed by or on behaLf of each        to the contract." Mr David N
^avelRycniy- Grouping Words ■ Marcn 30,2023 5/27
What Good are Word Senses?
■ thing. She was taLking at a party thrown at Daphne's restaurant in
■ have turned it into the hot dinner-party topic. The comedy is the
■ seLection for the WorLd Cup party, which wiLL be announced on May 1
■ the by-pass there wiLL be a street party. "Then," he says, "we are going
■ "Oh no, I'm just here for the party," they said. "I think it's terribLe
■ in the 1983 generaL eLection for a        which, when it couLd not bear to
■ to attack the Scottish NationaL Party, who Look set to seize Perth and
■ number-crunchers within the Labour party, there now seems LittLe doubt
y. They are both reLativeLy l they must not retreat into
poLiticaL tradition and the same | AngLophiLic
he toLd Tony BLair's modernised p "warm
that had been passed to a second        who made a financiaL decision
A future obLiges each        to the contract to fuLfU it by RyffiyS.'gflf^pwoPJsPRatefe?lfef each        t0 the contract." Mr David6N2;
What Good are Word Senses?
What Good are Word Senses?
John threw a "rain forest" party Last December. His Living room was fuLL of pLants and his box was pLaying BraziLian music ...
^avel Rychlý ■ Grouping Words ■ March 30,2023
What Good are Word Senses?
■ number-crunchers within the Labour party, there now seems Little doubt
■ political tradition and the same party. They are both relatively Anglophilic
■ he told Tony Blair's modernised party they must not retreat into "warm
■ thing. She was talking at a party thrown at Daphne's restaurant in
■ have turned it into the hot dinner-party topic. The comedy is the
■ selection for the World Cup Party, which will be announced on May 1
■ the by-pass there will be a street party. "Then," he says, "we are going
■ "Oh no, I'm just here for the party," they said. "I think it's terrible
■ an appearance at the annual awards bash , but feels in no fit state to
■ -known families at a fundraising bash on Thursday night for Learning
■ Who was paying for the bash? The only clue was the name Asprey,
■ Mail, always hosted the annual bash for the Scottish Labour front-
■ popular. Their method is to bash sense into criminals with a short,
■ just cut off people's heads and bash their brains out over the floor,
^avel Rychlý- Grouping Words ■ March 30,2023 9/27
What Good are Word Senses?
Semantics /Text understanding
■ Axioms about TRANSFER apply to (some tokens of) throw
■ Axioms about BUILDING apply to (some tokens of) bank
Machine translation
Info retrieval / Question answering / Text categ.
■ Query or pattern might not match document exactly Backoff for just about anything
■ what word comes next? (speech recognition, language ID,...)
■ trigrams are sparse but tri-meanings might not be
■ bilexical PCFGs:
■ p(S[devour] -> NP[lion] VP[devour] | S[devour])
■ approximate by p(S[EAT] -> NP[lion] VP[EAT] | S[EAT])
Speaker's real intention is senses; words are a noisy channel
RepLace word w with sense s
1. Splits w into senses: distinguishes this token of w from tokens with sense t
2. Groups w with other words: groups this token of w with tokens of x that also have sense s
^avel Rychlý ■ Grouping Words ■ March 30,2023
What Good are Word Senses?
■ number-crunchers within the Labour party, there now seems little doubt
■ political tradition and the same party. They are both relatively Anglophilic
■ he told Tony Blair's modernised party they must not retreat into "warm
■ thing. She was talking at a party thrown at Daphne's restaurant in
■ have turned it into the hot dinner-party topic. The comedy is the
■ selection for the World Cup party, which will be announced on May 1
■ the by-pass there will be a street party. "Then," he says, "we are going
■ "Oh no", I'm just here for the party," they said. "I think it's terrible
■ an appearance at the annual awards bash, but feels in no fit state to
■ -known families at a fundraising bash on Thursday night for Learning
■ Who was paying for the bash? The only clue was the name Asprey,
■ Mail, always hosted the annual bash for the Scottish Labour front-
■ popular. Their method is to bash sense into criminals with a short,
=av*RW.^PfÍ»Sdy.LBa>cRfr|21á3ana' baSh their brainS 0ut °ver the fl°ffl$>27
Cues to Word Sense
Adjacent words (or their senses) GrammaticaLLy reLated words (subject, object,...) Other nearby words Topic of document
Sense of other tokens of the word in the same document
^avel Rychlý ■ Grouping Words ■ March 30,2023
11/27
^avel Rychlý ■ Grouping Words ■ March 30,2023
12/27
Word Classes by Tagging
Word Classes by Tagging
Every tag is a kind of class
Tagger assigns a class to each word token
^'~\ /-'"\ PN     Verb     Det    Noun    Prep    Noun Prep
Bill   directed    a    cortege    of     autos throught
Every tag is a kind of class
Tagger assigns a class to each word token
■ Simultaneously groups and spLits words
■ "party" gets spLit into N and V senses
■ "bash" gets spLit into N and V senses
■ {party/N, bash/N} vs. {party/Y bash/V}
■ What good are these groupings?
^avel Rychly ■ Grouping Words ■ March 30,2023
^avel Rychly ■ Grouping Words ■ March 30,2023
Learning Word Classes
Words and Vectors
Every tag is a kind of class
Tagger assigns a class to each word token
■ {party/N, bash/N} vs. {party/V, bash/V}
■ What good are these groupings?
■ Good for predicting next word or its cLass! Role of forward-backward algorithm?
■ It adjusts cLasses etc. in order to predict sequence of words better (with Lower perpLexity)
Represent each word type w (party) by a point in k-dimensional space
■ e.g., k is size of vocabuLary
■ the 17th coordinate of w represents strength of w's association with vocabuLary word 17
^avel Rychly ■ Grouping Words ■ March 30,2023
^avel Rychly ■ Grouping Words ■ March 30,2023
Word
aardvark abacus abandoned abbot abduct above zygote zymurgy
Count
0
0 3
1
0 7
1 0
too high
too low
From corpus:
Jim Jeffords abandoned the Republican party. There were lots of abbots and nuns dancing at that party. The party above the art gallery was, above all, a laboratory for synthesizing zygotes and beer.
Represent each word type w (party) by a point in k-dimensional space
■ e.g., k is size of vocabuLary
■ the 17th coordinate of w represents strength of w's association
with vocabuLary word 17. How might you measure this?
■ how often words appear next to each other
■ how often words appear near each other
■ how often words are syntacticaLLy Linked
■ shouLd correct for commonness of word (e.g., "above")
^avel Rychly ■ Grouping Words ■ March 30,2023
17/27
^avel Rychly ■ Grouping Words ■ March 30,2023
18/27
Learning Classes by Clustering
Represent each word type w (party) by a point in k-dimensional space
■ e.g., k is size of vocabuLary
■ the 17th coordinate of w represents strength of w's association with vocabuLary word 17.
Plot all word types in k-dimensional space
Look for clusters of close-together types
Plot all word types in k-dimensional space Look for clusters of close-together types Plot in k dimensions (k=3)
^avel Rychly ■ Grouping Words ■ March 30,2023
^avel Rychly ■ Grouping Words ■ March 30,2023
Bottom-Up Clustering
Single-Link
Start with one cluster per point Repeatedly merge 2 closest clusters
■ Single-link: dist(A.B) = min dist(a,b)/or a e A,b e 6
■ Complete-link: dist(A,B) = max dist(a,b)/or a e A, b e
each word type is a single-point cluste
Again, merge closest pair of clusters:
Single-link: dusters are cLose if any of their points are dist(A.B) = min dist(a,b)/or a eA,b e 6
^avel Rychly ■ Grouping Words ■ March 30,2023
^avel Rychly ■ Grouping Words ■ March 30,2023
Single-Link
Complete-Link
Fast, but tend to get long, stringy, meandering clusters
Again, merge closest pair of clusters:
■ Complete-link: dusters are dose onLy if all of their points are dist(A.B) = max dist(a,b)/or a e A,b e 6
^avel Rychly ■ Grouping Words ■ March 30,2023
23/27
^avel Rychly ■ Grouping Words ■ March 30,2023
24/27
Summary
■ Start with one cluster per point
■ Repeatedly merge 2 closest clusters
Single-link: dist(A.B) = min dist(a,b)/or a e A, b e 6
■ Complete-link: dist(A.B) = max dist(a,b)/or a e A,b e B
■ too slow to update cluster distances after each merge; but alternatives!
■ Average-link: dist(A,B) = mean dist(a,b)/or a e A,b e B
■ Centroid-link: dist(A,B) = dist(mean(A),mean(B))
■ Stop when clusters are "big enough"
■ e.g., provide adequate support for backoff (on a development corpus)
■ Some flexibility in defining dist(a,b)
■ Might not be Euclidean distance; e.g., use vector angle
^avelRychly ■ Grouping Words ■ March 30,2023 26/27
EM Clustering (for k clusters)
■ EM algorithm
■ Viterbi version - called "k-means clustering"
■ Full EM version - called "Gaussian mixtures"
■ Expectation step: Use current parameters (and observations) to reconstruct hidden structure
■ Maximization step: Use that hidden structure (and observations) to reestimate parameters
■ Parameters: k points representing cluster centers
■ Hidden structure: for each data point (word type), which center generated it?
Complete-Link
■ Slow to find closest pair - need quadratically many distances
^avel RychLy ■ Grouping Words ■ March 30,2023
27/27