程序代写代做代考 C chain N-gram Language Models

COMP90042
L3
Add-one Example the rat ate the cheese
What’s the bigram probability P(ate|rat) under add-one smoothing?
= 𝐶(𝑟𝑎𝑡𝑎𝑡𝑒)+1= 2 V={the,rat,ate,cheese,} 𝐶(𝑟𝑎𝑡) + |𝑽 | 6
What’s the bigram probability P(ate|cheese) under add-one smoothing?
= 𝐶(𝑐h𝑒𝑒𝑠𝑒 𝑎𝑡𝑒) + 1 = 𝐶(𝑐h𝑒𝑒𝑠𝑒) + | 𝑽 |
1 6
15

COMP90042
L3
Add-k Smoothing
• • •
𝑃 (𝑤|𝑤 ,𝑤 )=𝐶(𝑤𝑖−2,𝑤𝑖−1,𝑤𝑖)+𝑘 𝑎𝑑𝑑𝑘 𝑖 𝑖−1 𝑖−2 𝐶(𝑤𝑖−2,𝑤𝑖−1)+𝑘|𝑽|
• Havetochoosek
‣ number of “classes” is huge (n-grams), so can have a big effect
Adding one is often too much Instead, add a fraction k
AKA Lidstone Smoothing
16

COMP90042
L3
Lidstone Smoothing
Context = alleged
• 5 observed bi-grams • 2 unobserved bi-grams
20 1.0 20 1.0
(8 + 0.1) / (20 + 7 x 0.1) 17

COMP90042
L3
Lidstone Smoothing
Context = alleged
• 5 observed n-grams • 2 unobserved n-grams
20 1.0 20 1.0
(0 + 0.1) / (20 + 7 x 0.1)
(8 + 0.1) / (20 + 7 x 0.1) 18

COMP90042
L3
Lidstone Smoothing
Context = alleged
• 5 observed n-grams • 2 unobserved n-grams
20
1.0 20 1.0 0.391 x 20
(0 + 0.1) / (20 + 7 x 0.1)
(8 + 0.1) / (20 + 7 x 0.1) 19

COMP90042
L3
•
•
‘Borrows’ a fixed probability mass from observed n-gram counts
Absolute Discounting
Redistributes it to unseen n-grams
20

COMP90042
L3
Absolute Discounting
Context = alleged
• 5 observed n-grams • 2 unobserved n-grams
8 – 0.1
(0.1 x 5) / 2
total amount of discounted probability mass (0.1 x 5) / 20
21

COMP90042
L3
•
•
Backoff
Absolute discounting redistributes the probability
mass equally for all unseen n-grams
Katz Backoff: redistributes the mass based on a
lower order model (e.g. unigram)
⎧C(wi−1,wi)−D , P (w|w )=⎨ C(wi−1)
P(w )
i ,
if C(wi−1, wi) > 0 otherwise
unigram probability for wi
katz i i−1
⎩α(wi−1) × 􏰀
sum unigram probabilities for all words
that do not co-occur with context wi-1
wj:C(wi−1,wj)=0 P(wj)
the amount of probability mass that has been discounted for context wi-1 ((0.1 x 5) / 20 in previous slide)
22

COMP90042
L3
katz i i−1
⎩α(wi−1) × 􏰀
Issues with Katz Backoff
⎧C(wi−1,wi)−D , P (w|w )=⎨ C(wi−1)
P(w )
i ,
wj:C(wi−1,wj)=0 P(wj)
if C(wi−1, wi) > 0 otherwise
•
•
•
•
Francisco
I can’t see without my reading ___
C(reading, glasses) = C(reading, Francisco) = 0 C(Fransciso) > C(glasses)
Katz backoff will give higher probability to
23

COMP90042
L3
•
•
Redistribute probability mass based on how many number of different contexts word w has appeared in
Kneser-Ney Smoothing
This measure is called “continuation probability”
24

COMP90042
L3
PKN (wi|wi−1) =
􏰅C(wi−1,wi)−D , C(wi−1)
α(wi−1 )Pcont (wi ), where
if C(w , w ) > 0 i−1 i
otherwise
Kneser-Ney Smoothing
􏰀|{wi−1 : C(wi−1, wi) > 0}|
wi |{wi−1 : C(wi−1, wi) > 0}|
Pcont(wi) =
• Highcontinuationcountsforglasses(men’sglasses,
black glasses, buy glasses, prescription glasses, etc) • LowcontinuationcountsforFranciso(SanFrancisco)
25

COMP90042
L3
Interpolation
• Abetterwaytocombinedifferentordern-grammodels
• Weightedsumofprobabilitiesacrossprogressively shorter contexts
• Interpolatedtrigrammodel:
Learned based on held out data
26

COMP90042
L3
Interpolated Kneser-Ney Smoothing
•
Interpolation instead of back-off
PIKN (wi|wi−1) = C(wi−1, wi) − D + β(wi−1)Pcont(wi) C (wi−1 )
• where β(wi−1) =
‣ normalising constant so that sums to 1.0
PIKN (wi|wi−1)
27

COMP90042
L3
•
•
Commonly used Kneser-Ney language models use 5-grams as max order
In Practice
Has different discount values for each n-gram order.
28

COMP90042 L3
Generating Language
29

COMP90042
L3
Generation
• Given an initial word, draw the next word according to the probability distribution defined by the language model.
• Include (n-1) start tokens for n-gram model, to provide context to generate first word
‣ never generate
‣ generating terminates the sequence
30

COMP90042
L3
• •
Generation (Bigram LM) Sentence =
P(? | ) = “a” 0.5
0.375 0.25 0.125 0
cow grass
eats a
31

COMP90042
L3
• •
Generation (Bigram LM) Sentence = a cow eats grass
P(? | grass) = “” 0.6
0.45 0.3 0.15 0
cow grass
eats a
35

COMP90042
L3
• •
Sentence = a cow eats grass Done!
Generation (Bigram LM)
36

COMP90042
L3
How to Select Next Word?
• Argmax:takeshighestprobabilitywordeachturn ‣ Greedy search
•
Beam search decoding:
‣ Keeps track of top-N highest probability words each turn
‣ Produces sentences with near-optimal sentence probability
• Randomlysamplesfromthedistribution(e.g. temperature sampling)
37

COMP90042 L3
Evaluating Language Models
38

COMP90042
L3
Evaluation
‣ E.g. spelling correction, machine translation
• Intrinsic
‣ Perplexity on held-out test set
•
Extrinsic
39