{"description": "", "language": {"code": "en", "dir": "ltr", "name": "English"}, "metadata": {}, "note": "", "resource_uri": "/api2/partners/videos/XaRKSNCZRO0x/languages/en/subtitles/", "site_url": "http://www.amara.org/videos/XaRKSNCZRO0x/en/229280/", "sub_format": "json", "subtitles": [{"end": 7200, "meta": {"new_paragraph": true}, "position": 1, "start": 2160, "text": "Let's talk about cases where we need to
interpolate be, between or back off from"}, {"end": 12145, "meta": {"new_paragraph": false}, "position": 2, "start": 7200, "text": "one language model to another one. And
we'll also touch on the web today. These"}, {"end": 17407, "meta": {"new_paragraph": false}, "position": 3, "start": 12145, "text": "are cases where it helps to use less
context rather than more. And the"}, {"end": 21920, "meta": {"new_paragraph": false}, "position": 4, "start": 17407, "text": "intuition is, suppose that, you have a, a
very confident trigram. You've seen a"}, {"end": 26319, "meta": {"new_paragraph": false}, "position": 5, "start": 21920, "text": "trigram a very large number of times.
You're very confident this trigram is a"}, {"end": 30832, "meta": {"new_paragraph": false}, "position": 6, "start": 26319, "text": "good estimator. Well we should use the
trigram. But suppose you only saw it once."}, {"end": 35460, "meta": {"new_paragraph": false}, "position": 7, "start": 30832, "text": "Well maybe you don't really trust that
trigram. So you might want to back off and"}, {"end": 39802, "meta": {"new_paragraph": false}, "position": 8, "start": 35460, "text": "use the bigram instead. And maybe you
haven't seen a bigram either. You might"}, {"end": 44258, "meta": {"new_paragraph": false}, "position": 9, "start": 39802, "text": "back off to the unigram. So he idea of
back off is, sometimes if you don't have"}, {"end": 48714, "meta": {"new_paragraph": false}, "position": 10, "start": 44258, "text": "a, a large count or a trustworthy evidence
for a larger order enneagram, we might"}, {"end": 54131, "meta": {"new_paragraph": false}, "position": 11, "start": 48714, "text": "back off to a smaller one. A related idea
is interpolation. Interpolation says, well"}, {"end": 59068, "meta": {"new_paragraph": false}, "position": 12, "start": 54309, "text": "sometimes the trigram may not be useful
and in that case, if we mix trigrams and"}, {"end": 63886, "meta": {"new_paragraph": false}, "position": 13, "start": 59068, "text": "bigrams and unigrams, well then we may get
more information from the unigrams and"}, {"end": 68823, "meta": {"new_paragraph": false}, "position": 14, "start": 63886, "text": "bigrams but other times trigrams will be
more useful and so interpolation suggests"}, {"end": 73700, "meta": {"new_paragraph": false}, "position": 15, "start": 68823, "text": "that we just mix all three all the time
and, and, and get the benefits of all of"}, {"end": 78391, "meta": {"new_paragraph": false}, "position": 16, "start": 73700, "text": "them and it turns out in practice that
interpolation works better than back off."}, {"end": 83931, "meta": {"new_paragraph": false}, "position": 17, "start": 78399, "text": "So most of the time in language modeling,
we'll be dealing with interpolation. There"}, {"end": 89724, "meta": {"new_paragraph": false}, "position": 18, "start": 83931, "text": "are two kinds of interpolation. Simple
linear interpolation, we have, our"}, {"end": 95592, "meta": {"new_paragraph": false}, "position": 19, "start": 89724, "text": "unigram, our bigram, and our trigram. And
we simply add them together with three"}, {"end": 101610, "meta": {"new_paragraph": false}, "position": 20, "start": 95592, "text": "weights... Lambda one, Lambda two, and
Lambda three. The Lambdas just sum to one"}, {"end": 107704, "meta": {"new_paragraph": false}, "position": 21, "start": 101610, "text": "to make this a probability. And, and, and,
and we can compute our new probability."}, {"end": 113647, "meta": {"new_paragraph": false}, "position": 22, "start": 107704, "text": "We'll call it P hat of a word given the
previous two words, by, by interpolating"}, {"end": 119609, "meta": {"new_paragraph": false}, "position": 23, "start": 113647, "text": "these three, language models. We can do
something slightly more complicated. We"}, {"end": 124784, "meta": {"new_paragraph": false}, "position": 24, "start": 119609, "text": "can condition our lambdas on the context.
So we can say, still mix our trigram or"}, {"end": 130023, "meta": {"new_paragraph": false}, "position": 25, "start": 124784, "text": "bigram with a unigram but now, the lambdas
are dependent on what the previous two"}, {"end": 135392, "meta": {"new_paragraph": false}, "position": 26, "start": 130023, "text": "words were. So we can train even a richer
and, and more complex context conditioning"}, {"end": 140696, "meta": {"new_paragraph": false}, "position": 27, "start": 135392, "text": "for deciding how to mix our trigrams and
our bigrams and our unigrams. So, where do"}, {"end": 146875, "meta": {"new_paragraph": false}, "position": 28, "start": 140696, "text": "the lambdas come from? The normal way to
set lambdas is to use a held out corpus."}, {"end": 151743, "meta": {"new_paragraph": false}, "position": 29, "start": 146875, "text": "So we've talked before about having a
training corpus. Here's our training"}, {"end": 156848, "meta": {"new_paragraph": false}, "position": 30, "start": 151743, "text": "corpus and our test corpus. A held out
corpus is yet another piece that we set"}, {"end": 162394, "meta": {"new_paragraph": false}, "position": 31, "start": 156848, "text": "out, set aside from our data. And we use a
held out corpus. Sometimes we, we use, a"}, {"end": 167419, "meta": {"new_paragraph": false}, "position": 32, "start": 162394, "text": "held out corpus called a dev set. A
development set, or other kinds of held"}, {"end": 171987, "meta": {"new_paragraph": false}, "position": 33, "start": 167419, "text": "out data. We use them to set
metaparameters and check for things. So in"}, {"end": 177012, "meta": {"new_paragraph": false}, "position": 34, "start": 171987, "text": "this, we can use the held out corpus to
set our Lambdas. And the idea is, we're"}, {"end": 181972, "meta": {"new_paragraph": false}, "position": 35, "start": 177012, "text": "gonna choose Lambdas which maximize the
likelihood of this held out data. So"}, {"end": 189379, "meta": {"new_paragraph": false}, "position": 36, "start": 181972, "text": "here's what we do. We take our training
data, and we train some enneagrams. Now,"}, {"end": 196933, "meta": {"new_paragraph": false}, "position": 37, "start": 189379, "text": "we say, which Lambdas would I use to
interpolate those enneagrams, such that,"}, {"end": 205535, "meta": {"new_paragraph": false}, "position": 38, "start": 196933, "text": "it gives me the highest probability of
this held out data. So we, we ask, find"}, {"end": 213928, "meta": {"new_paragraph": false}, "position": 39, "start": 205535, "text": "the set of probabilities, such that the
log probability of the actual words that"}, {"end": 226696, "meta": {"new_paragraph": false}, "position": 40, "start": 213928, "text": "occur in the held out data are highest.
Now we've talked about cases where there"}, {"end": 231233, "meta": {"new_paragraph": false}, "position": 41, "start": 226696, "text": "is zeros, so we haven't seen some bi-gram
before and we have to replace that zero"}, {"end": 235545, "meta": {"new_paragraph": false}, "position": 42, "start": 231233, "text": "count with some other count, that's
smoothing. But what do we do if the actual"}, {"end": 240067, "meta": {"new_paragraph": false}, "position": 43, "start": 235545, "text": "word itself has never been seen before.
Now sometimes that doesn't happen. In"}, {"end": 245186, "meta": {"new_paragraph": false}, "position": 44, "start": 240067, "text": "tasks where, let's say a menu based task,
where we're, where we have a thick set of"}, {"end": 250367, "meta": {"new_paragraph": false}, "position": 45, "start": 245186, "text": "commands, then no other words can ever be
said. Our vocabulary is fixed, and we have"}, {"end": 255422, "meta": {"new_paragraph": false}, "position": 46, "start": 250367, "text": "a, what's called a closed vocabulary task.
But, lots of times, language modeling is"}, {"end": 260847, "meta": {"new_paragraph": false}, "position": 47, "start": 255422, "text": "applied in cases where we don't know, any
word could be used and it could be words"}, {"end": 265315, "meta": {"new_paragraph": false}, "position": 48, "start": 260847, "text": "we've never seen in our training set. So
we call these words OOV or out of"}, {"end": 269843, "meta": {"new_paragraph": false}, "position": 49, "start": 265315, "text": "vocabulary words. And one way of dealing
with out of vocabulary words is as"}, {"end": 274417, "meta": {"new_paragraph": false}, "position": 50, "start": 269843, "text": "follows, we create a special token called
unk. And the way we train unk"}, {"end": 280065, "meta": {"new_paragraph": false}, "position": 51, "start": 274417, "text": "probabilities is we create a fixed
lexicon. So we take our training data and"}, {"end": 285489, "meta": {"new_paragraph": false}, "position": 52, "start": 280065, "text": "we first decide which, we hold out a few
words, the very rare words or the"}, {"end": 291360, "meta": {"new_paragraph": false}, "position": 53, "start": 285489, "text": "unimportant words, and we take all those
words and we change those words to unk."}, {"end": 297288, "meta": {"new_paragraph": false}, "position": 54, "start": 292440, "text": "Now we train the probabilities of unk like
a normal, any normal word. So we have our"}, {"end": 301553, "meta": {"new_paragraph": false}, "position": 55, "start": 297288, "text": "corpus, our training corpus. It has word,
word, word, and it has a really low"}, {"end": 306051, "meta": {"new_paragraph": false}, "position": 56, "start": 301553, "text": "probability word, word, word, word, and
we'll take that word and we'll change it"}, {"end": 311387, "meta": {"new_paragraph": false}, "position": 57, "start": 306051, "text": "to unk. And now we train out bigram word,
word, word unk word, word, word as just as"}, {"end": 316266, "meta": {"new_paragraph": false}, "position": 58, "start": 311387, "text": "if unk had been a word in there and now at
decoding time if you see a new word you"}, {"end": 321380, "meta": {"new_paragraph": false}, "position": 59, "start": 316266, "text": "haven't seen you replace that word with
unk and treat it like get its, its bigram"}, {"end": 325435, "meta": {"new_paragraph": false}, "position": 60, "start": 321380, "text": "probabilities and its trigram
probabilities from the unk word in the"}, {"end": 331942, "meta": {"new_paragraph": false}, "position": 61, "start": 325435, "text": "training set. Another important issue in M
grams has to do with web scale or very"}, {"end": 337474, "meta": {"new_paragraph": false}, "position": 62, "start": 331942, "text": "large M grams. So we introduced the Google
M grams corpus earlier. How do we deal"}, {"end": 343888, "meta": {"new_paragraph": false}, "position": 63, "start": 337474, "text": "with computing probabilities in such large
spaces? So, one answer is pruning. We only"}, {"end": 349579, "meta": {"new_paragraph": false}, "position": 64, "start": 343888, "text": "store n-grams that have a very large
count. So for example the very high order"}, {"end": 354341, "meta": {"new_paragraph": false}, "position": 65, "start": 349579, "text": "N grams we might want to remove all of
those singletons. All of the things with"}, {"end": 359224, "meta": {"new_paragraph": false}, "position": 66, "start": 354341, "text": "count one because by Ziff's law there's
gonna be a lot of those singleton counts."}, {"end": 364046, "meta": {"new_paragraph": false}, "position": 67, "start": 359224, "text": "And we can also use other kinds of more
sophisticated versions of this. We don't"}, {"end": 369110, "meta": {"new_paragraph": false}, "position": 68, "start": 364046, "text": "just remove things with counts we actually
use compute the [inaudible] perplexities"}, {"end": 374113, "meta": {"new_paragraph": false}, "position": 69, "start": 369110, "text": "on a test set and remove counts that are
contributing less to the probability on a"}, {"end": 378376, "meta": {"new_paragraph": false}, "position": 70, "start": 374113, "text": "particular held out set. So that's
pruning. We can do a number of other"}, {"end": 383029, "meta": {"new_paragraph": false}, "position": 71, "start": 378376, "text": "efficiency thing. We can use efficient
data structures like tries. We can use"}, {"end": 388173, "meta": {"new_paragraph": false}, "position": 72, "start": 383029, "text": "approximate language models which are very
efficient but are not guaranteed to give"}, {"end": 393071, "meta": {"new_paragraph": false}, "position": 73, "start": 388173, "text": "you the exact same probability. We can, we
have to do efficient things like don't"}, {"end": 397847, "meta": {"new_paragraph": false}, "position": 74, "start": 393071, "text": "store the actual strings but just store
indexes. We can use Huffman coding and"}, {"end": 402990, "meta": {"new_paragraph": false}, "position": 75, "start": 397847, "text": "often instead of storing our probabilities
as these big 8-byte floats, we might just"}, {"end": 407582, "meta": {"new_paragraph": false}, "position": 76, "start": 402990, "text": "do some kind of quantization and just
store a small number of bits for our"}, {"end": 413965, "meta": {"new_paragraph": false}, "position": 77, "start": 407582, "text": "probabilities. [sound] What about
smoothing for web scale enneagrams. Most"}, {"end": 419173, "meta": {"new_paragraph": false}, "position": 78, "start": 413965, "text": "popular smoothing methods for these very
large enneagrams is an algorithm called"}, {"end": 424915, "meta": {"new_paragraph": false}, "position": 79, "start": 419173, "text": "Stupid Back off. Stupid Back off is called
stupid because it's very simple but it"}, {"end": 430257, "meta": {"new_paragraph": false}, "position": 80, "start": 424915, "text": "works well at the very large scale. And
the fact it's been shown to work as well"}, {"end": 435800, "meta": {"new_paragraph": false}, "position": 81, "start": 430257, "text": "as any more complicated algorithm when you
have very large amounts of data. I mean"}, {"end": 441409, "meta": {"new_paragraph": false}, "position": 82, "start": 435800, "text": "intuition of Stupid Back off is if I wanna
compute the Stupid Back off probability of"}, {"end": 447131, "meta": {"new_paragraph": false}, "position": 83, "start": 441409, "text": "a word given some previous set of words. I
use the maximum likelihood estimator and"}, {"end": 453022, "meta": {"new_paragraph": false}, "position": 84, "start": 447131, "text": "this is the count of the words divided by
the count of the prefix, if that count is"}, {"end": 458771, "meta": {"new_paragraph": false}, "position": 85, "start": 453022, "text": "greater than zero, and if not, I just back
off to the, to the probability of the"}, {"end": 464256, "meta": {"new_paragraph": false}, "position": 86, "start": 458771, "text": "previous. The lower order n gram prefix
with some constant weight, so it's if, if"}, {"end": 469634, "meta": {"new_paragraph": false}, "position": 87, "start": 464256, "text": "the trigram would say occurs I just use
the count of the trigram, if it doesn't I"}, {"end": 474945, "meta": {"new_paragraph": false}, "position": 88, "start": 469634, "text": "take the bigram probability and multiply
it by point four and just use that. And"}, {"end": 480722, "meta": {"new_paragraph": false}, "position": 89, "start": 474945, "text": "then when I get down to the unigrams if I
don't have anything at all I just use the"}, {"end": 486787, "meta": {"new_paragraph": false}, "position": 90, "start": 480722, "text": "unigram, I just use the, the unigram
probability, so, We call this S. Instead"}, {"end": 492534, "meta": {"new_paragraph": false}, "position": 91, "start": 486787, "text": "of P, because stupid back off doesn't
produce probabilities because to produce"}, {"end": 498716, "meta": {"new_paragraph": false}, "position": 92, "start": 492534, "text": "probabilities we would actually have to
use various clever kinds of waiting a back"}, {"end": 503347, "meta": {"new_paragraph": false}, "position": 93, "start": 498716, "text": "off algorithm has to discount this
probability to leave some mass left over"}, {"end": 507881, "meta": {"new_paragraph": false}, "position": 94, "start": 503347, "text": "to use the bigram probabilities.
Otherwise, we're gonna end up with numbers"}, {"end": 512537, "meta": {"new_paragraph": false}, "position": 95, "start": 507881, "text": "that are greater than one, and we won't
have probabilities. But, but, so stupid"}, {"end": 517377, "meta": {"new_paragraph": false}, "position": 96, "start": 512537, "text": "back off produces something like scores,
or, or, rather than, than, probabilities."}, {"end": 523922, "meta": {"new_paragraph": false}, "position": 97, "start": 517377, "text": "But it turns out that this, this works
quite well. So, in summary, for smoothing"}, {"end": 528614, "meta": {"new_paragraph": false}, "position": 98, "start": 523922, "text": "so far, add one smoothing is okay for text
categorization, but it's not recommended"}, {"end": 533306, "meta": {"new_paragraph": false}, "position": 99, "start": 528614, "text": "for language modeling. The most commonly
used method we'll discuss in the advanced"}, {"end": 537712, "meta": {"new_paragraph": false}, "position": 100, "start": 533306, "text": "section of this week is, the, the
[inaudible] Nye algorithm, or the extended"}, {"end": 541774, "meta": {"new_paragraph": false}, "position": 101, "start": 537712, "text": "interpolated [inaudible] Nye algorithm.
But for very large enneagrams, like"}, {"end": 546409, "meta": {"new_paragraph": false}, "position": 102, "start": 541774, "text": "situations where you're using the web,
simplistic algorithms like stupid back off"}, {"end": 553521, "meta": {"new_paragraph": false}, "position": 103, "start": 546409, "text": "actually work quite well. How about
advanced language modeling issues? Recent"}, {"end": 558080, "meta": {"new_paragraph": false}, "position": 104, "start": 553521, "text": "research has focused on things like
discriminative models. So here, the idea"}, {"end": 562760, "meta": {"new_paragraph": false}, "position": 105, "start": 558080, "text": "is, pick the enneagram weights. Instead of
picking them to fit some training data,"}, {"end": 567434, "meta": {"new_paragraph": false}, "position": 106, "start": 562760, "text": "whether it's maximum likelihood estimate
or smooth. Instead, choose your enneagram"}, {"end": 572545, "meta": {"new_paragraph": false}, "position": 107, "start": 567440, "text": "weights that improve some task. So we'll
pick a, whatever task we're doing, machine"}, {"end": 577042, "meta": {"new_paragraph": false}, "position": 108, "start": 572545, "text": "translation or speech recognition, and
choose whatever enneagram weights make"}, {"end": 582364, "meta": {"new_paragraph": false}, "position": 109, "start": 577042, "text": "that task more likely. Another thing we
can do is instead of just using anagrams,"}, {"end": 587092, "meta": {"new_paragraph": false}, "position": 110, "start": 582364, "text": "we can use parsers. And we'll see the use
of parsers and statistical parsers later"}, {"end": 592504, "meta": {"new_paragraph": false}, "position": 111, "start": 587092, "text": "in the course. Or we can use caching
models. In a caching model we assume that"}, {"end": 596927, "meta": {"new_paragraph": false}, "position": 112, "start": 592504, "text": "a word that's been used recently is more
likely to appear again. So the"}, {"end": 601724, "meta": {"new_paragraph": false}, "position": 113, "start": 596927, "text": "probability, the cache probability of a
word, given some history, we mix the"}, {"end": 605850, "meta": {"new_paragraph": false}, "position": 114, "start": 601724, "text": "probability of the word. With some
function of the history, how, like, how"}, {"end": 610326, "meta": {"new_paragraph": false}, "position": 115, "start": 605850, "text": "much, how often the word occurred in the
history with, and we, we weight those two"}, {"end": 614579, "meta": {"new_paragraph": false}, "position": 116, "start": 610326, "text": "probabilities together. It turns out that
cache models don't work in certain"}, {"end": 618944, "meta": {"new_paragraph": false}, "position": 117, "start": 614579, "text": "situations, and in particularly, they
perform poorly for speech recognition. You"}, {"end": 623588, "meta": {"new_paragraph": false}, "position": 118, "start": 618944, "text": "should think about why that might be, that
a cache model performs poorly for speech"}], "title": "Interpolation", "version_no": 5, "version_number": 5, "video": "Interpolation", "video_description": "", "video_title": "Interpolation"}