paper.ps

这是一款很好用的工具包

(associated)f(with)f(that)h(type)g(of)g(LM.)-186 5078
y(The)d(types)h(of)f(models)h(supported)h(are)e(described)i(further)e
(in)g(Section)g(3.3.)-61 5165 y(Be)o(yond)22 b(LM)g(e)n(v)n(aluation,)h
Fh(ngram)e Fj(is)h(really)f(a)h(tool)g(to)f(manipulate)-186
5252 y(LMs)c(in)g(a)g(v)n(ariety)h(of)f(w)o(ays.)23 b(Besides)18
b(computing)g(test)f(set)g(log)h(probabil-)-186 5339
y(ities)g(from)h(te)o(xt)g(or)g(counts,)g(it)f(can)2020
83 y Fi(\017)42 b Fj(renormalize)19 b(a)g(model)h(\(recomputing)g(back)
o(of)n(f)g(weights\))2020 206 y Fi(\017)42 b Fj(approximate)19
b(a)e(class-based)i(or)e(interpolated)h(N-gram)g(with)f(a)h(stan-)2100
293 y(dard)h(w)o(ord-based)i(back)o(of)n(f)f(LM)2020
416 y Fi(\017)42 b Fj(prune)20 b(N-gram)f(parameters,)g(using)h(an)f
(entrop)o(y)h(criterion)f([10])2020 539 y Fi(\017)42
b Fj(prepare)18 b(LMs)g(for)f(con)m(v)o(ersion)j(to)d(\002nite-state)g
(graphs)h(by)h(remo)o(ving)2100 626 y(N-grams)g(that)g(w)o(ould)h(be)f
(superseded)h(by)g(back)o(of)n(fs)2020 749 y Fi(\017)42
b Fj(generate)20 b(random)g(sentences)g(from)f(the)g(distrib)o(ution)g
(embodied)h(by)2100 835 y(the)f(LM.)2100 960 y(The)32
b(ability)g(to)h(approximate)g(class-based)h(and)f(interpolated)g(N-)
1975 1047 y(gram)d(LMs)g(by)g(a)f(single)h(w)o(ord)g(N-gram)g(model)g
(deserv)o(es)h(some)f(dis-)1975 1134 y(cussion.)47 b(Both)27
b(of)f(these)h(operations)h(are)e(useful)h(in)g(situations)f(where)1975
1220 y(other)f(softw)o(are)g(\(e.g.,)g(a)f(speech)i(recognizer\))f
(supports)h(only)f(standard)1975 1307 y(N-grams.)g(Class)19
b(N-grams)g(are)h(approximated)h(by)e(e)o(xpanding)j(class)d(la-)1975
1394 y(bels)f(into)f(their)f(members)i(\(which)f(can)h(contain)g
(multiw)o(ord)f(strings\))g(and)1975 1481 y(then)g(computing)h(the)f
(mar)o(ginal)f(probabilities)h(of)f(w)o(ord)h(N-gram)g(strings.)1975
1567 y(This)22 b(operation)h(increases)g(the)f(number)h(of)g(N-grams)f
(combinatorially)-5 b(,)1975 1654 y(and)20 b(is)f(therefore)g(feasible)
g(only)g(for)g(relati)n(v)o(ely)g(small)g(models.)2100
1742 y(An)f(interpolated)g(back)o(of)n(f)h(model)f(is)g(obtained)g(by)h
(taking)f(the)g(union)1975 1829 y(of)41 b(N-grams)f(of)g(the)g(input)h
(models,)k(assigning)d(each)e(N-gram)h(the)1975 1916
y(weighted)22 b(a)o(v)o(erage)e(of)h(the)g(probabilities)f(from)h
(those)g(models)g(\(in)f(some)1975 2003 y(of)e(the)g(models)g(this)g
(probability)g(might)g(be)h(computed)g(by)f(back)o(of)n(f\),)h(and)1975
2089 y(then)27 b(renormalizing)f(the)g(ne)n(w)g(model.)44
b(W)-6 b(e)25 b(found)i(that)f(such)g(interpo-)1975 2176
y(lated)e(back)o(of)n(f)h(models)f(consistently)g(gi)n(v)o(e)g
(slightly)g(lo)n(wer)f(perple)o(xities)1975 2263 y(than)28
b(the)f(corresponding)i(standard)f(w)o(ord-le)n(v)o(el)g(interpolated)f
(models.)1975 2350 y(The)c(reason)g(could)h(be)f(that)f(the)h(back)o
(of)n(f)h(distrib)o(utions)e(are)h(themselv)o(es)1975
2436 y(obtained)h(by)f(interpolation,)h(unlik)o(e)g(in)f(standard)g
(interpolation,)h(where)1975 2523 y(each)c(component)h(model)e(backs)h
(of)n(f)f(indi)n(vidually)-5 b(.)1975 2693 y Fl(3.3.)45
b(Language)20 b(model)e(types)1975 2816 y Fj(Besides)23
b(the)f(standard)h(w)o(ord-based)h(N-gram)e(back)o(of)n(f)h(models,)j
Fk(S)t(R)t(I)t(L)t(M)1975 2903 y Fj(implements)k(se)n(v)o(eral)g(other)
f(LM)g(types,)j(most)e(of)f(them)g(based)h(on)g(N-)1975
2990 y(grams)20 b(as)f(basic)g(b)o(uilding)g(blocks.)2100
3078 y Fg(Class-based)k(models)g Fj(\227)f(N-grams)h(o)o(v)o(er)f(w)o
(ord)h(classes)g(are)f(an)h(ef-)1975 3165 y(fecti)n(v)o(e)h(w)o(ay)g
(to)f(increase)h(the)f(rob)o(ustness)h(of)f(LMs)g(and)h(to)g
(incorporate)1975 3252 y(domain)29 b(kno)n(wledge,)i(e.g.,)e(by)g
(de\002ning)f(w)o(ord)g(classes)g(re\003ecting)g(the)1975
3339 y(task)33 b(semantics.)65 b Fk(S)t(R)t(I)t(L)t(M)32
b Fj(allo)n(ws)g(class)g(members)h(to)f(be)g(multiw)o(ord)1975
3425 y(strings)e(\(e.g.,)i(\223san)e(francisco\224)h(can)f(be)g(a)g
(member)g(of)g(class)g(\223CITY)-8 b(-)1975 3512 y(N)m(AME\224\).)25
b(This,)h(and)g(the)f(f)o(act)g(that)g(w)o(ords)h(can)g(belong)g(to)f
(more)g(than)1975 3599 y(one)j(class,)g(requires)f(the)g(use)g(of)f
(dynamic)i(programming)g(to)f(e)n(v)n(aluate)1975 3686
y(a)f(class)h(N-gram.)45 b(W)-6 b(ord)26 b(classes)g(may)h(be)f
(de\002ned)h(manually)g(or)f(by)h(a)1975 3772 y(separate)j(program,)j
Fh(ngram-class)p Fj(,)d(which)f(induces)i(classes)f(from)1975
3859 y(bigram)20 b(statistics)e(using)h(the)g(Bro)n(wn)h(algorithm)f
([11)q(].)2100 3947 y Fg(Cac)o(he)39 b(models)f Fj(\227)g(This)g
(well-kno)n(wn)h(LM)f(technique)h(assigns)1975 4034 y(nonzero)26
b(probability)g(to)e(recent)h(w)o(ords,)h(thus)f(modeling)h(the)e
(tendenc)o(y)1975 4121 y(of)d(w)o(ords)h(to)f(reoccur)h(o)o(v)o(er)f
(short)g(spans)h([12)q(].)29 b(The)o(y)21 b(are)g(usually)h(inter)o(-)
1975 4208 y(polated)e(with)f(a)f(standard)i(model)g(to)f(obtain)g(an)g
(adapti)n(v)o(e)h(LM.)2100 4296 y Fg(Dis\003uency)c(and)g(hidden)g(e)o
(vent)g(langua)o(g)o(e)h(models)f Fj(\227)e(Hidden)i(e)n(v)o(ent)1975
4383 y(LMs)37 b(incorporate)g(special)g(w)o(ords)g(that)f(appear)h(in)g
(the)f(model')l(s)h(N-)1975 4469 y(grams,)18 b(b)o(ut)e(are)h(not)g(o)o
(v)o(ert)g(in)f(the)h(observ)o(ed)h(w)o(ord)g(stream.)k(Instead,)17
b(the)o(y)1975 4556 y(correspond)30 b(to)d(the)h(states)g(of)f(a)h
(hidden)h(Mark)o(o)o(v)g(model,)h(and)e(can)g(be)1975
4643 y(used)19 b(to)f(model)g(linguistic)g(e)n(v)o(ents)g(such)h(as)f
(unmark)o(ed)h(sentence)g(bound-)1975 4730 y(aries.)41
b(Optionally)-5 b(,)26 b(these)f(e)n(v)o(ents)h(can)f(be)g(associated)g
(with)g(nonle)o(xical)1975 4817 y(lik)o(elihoods)20 b(to)f(condition)h
(the)f(LM)g(on)g(other)g(kno)n(wledge)i(sources)e(\(e.g.,)1975
4903 y(prosody\))34 b([13].)62 b(A)31 b(special)h(type)h(of)f(hidden)h
(e)n(v)o(ent)f(LM)g(can)g(model)1975 4990 y(speech)c(dis\003uencies)f
(by)f(allo)n(wing)h(the)f(hidden)i(e)n(v)o(ents)f(to)f(modify)h(the)
1975 5077 y(w)o(ord)21 b(history;)g(for)f(e)o(xample,)h(a)f(w)o(ord)h
(deletion)g(e)n(v)o(ent)g(w)o(ould)g(erase)f(one)1975
5164 y(or)f(more)h(w)o(ords)f(to)g(model)g(a)g(f)o(alse)g(start)g
([14].)2100 5252 y Fg(Skip)i(langua)o(g)o(e)i(models)e
Fj(\227)g(In)f(this)h(LM,)f(w)o(ords)h(in)g(the)g(history)g(are)1975
5339 y(probabilistically)16 b(skipped,)h(allo)n(wing)f(more)g(distant)f
(w)o(ords)i(to)e(tak)o(e)h(their)p eop
%%Page: 3 3
3 2 bop -186 83 a Fj(places.)37 b(The)23 b(skipping)i(probabilities)f
(associated)g(with)f(each)h(w)o(ord)g(are)-186 170 y(estimated)19
b(using)h(e)o(xpectation)g(maximization.)-61 260 y Fg(HMMs)j(of)h(N-gr)
o(ams)f Fj(\227)g(This)g(LM)g(consists)h(of)g(a)f(hidden)i(Mark)o(o)o
(v)-186 347 y(model)18 b(\(HMM\))g(where)g(each)g(state)f(is)g
(associated)i(with)e(its)g(o)n(wn)h(N-gram)-186 434 y(distrib)o(ution.)
24 b(The)19 b(model)h(generates)g(from)f(a)h(certain)f(state)g(until)g
(the)g(lo-)-186 520 y(cal)f(N-gram)h(issues)g(an)g(end-of-sentence,)h
(at)e(which)h(point)g(it)f(transitions)-186 607 y(probabilistically)25
b(to)g(a)g(neighboring)i(state.)41 b(HMMs)26 b(of)f(N-grams)g(pro-)-186
694 y(vide)g(a)f(general)i(frame)n(w)o(ork)f(that)f(can)h(encode)h(a)f
(v)n(ariety)g(of)f(LM)h(types)-186 781 y(proposed)18
b(in)e(the)g(literature,)g(such)h(as)f(sentence-le)n(v)o(el)h(mixtures)
f([15)q(])g(and)-186 867 y(pi)n(v)o(ot)j(LMs)g([16].)-61
958 y Fg(Dynamically)26 b(interpolated)h(LMs)f Fj(\227)f(T)-6
b(w)o(o)26 b(or)g(more)h(LMs)e(can)i(be)-186 1044 y(interpolated)f
(linearly)f(at)g(the)g(w)o(ord)h(le)n(v)o(el)f(such)h(that)f(the)h
(interpolation)-186 1131 y(weights)f(re\003ect)f(the)h(lik)o(elihoods)h
(of)f(the)g(models)g(gi)n(v)o(en)h(the)f(recent)g(N-)-186
1218 y(gram)i(history)f([8].)45 b(W)m(ith)26 b(a)g(null)g(history)-5
b(,)29 b(we)d(obtain)h(the)f(usual)h(static)-186 1305
y(LM)20 b(interpolation)h(approach)h(that)e(is)g(often)h(used)g(to)g
(combine)g(dif)n(ferent)-186 1391 y(sources)f(of)f(training)g(material)
f(into)h(a)g(single)g(model.)-186 1572 y Fl(3.4.)45 b(Other)19
b(applications)e(of)i(language)g(models)-186 1699 y Fj(Ov)o(er)h(the)f
(years)j Fk(S)t(R)t(I)t(L)t(M)e Fj(has)g(e)n(v)o(olv)o(ed)g(to)g
(include)g(tools)g(that)f(go)i(be)o(yond)-186 1785 y(simple)i(LM)g
(construction)h(and)g(e)n(v)n(aluation,)h(co)o(v)o(ering)f(mainly)f(LM)
g(ap-)-186 1872 y(plications)c(arising)g(in)g(speech)h(recognition.)
-186 2023 y Fh(disambig)40 b Fj(\227)23 b(an)g(HMM-based)h(tagger)g
(that)f(uses)g(N-gram)g(LMs)g(of)-61 2110 y(arbitrary)18
b(order)i(to)f(model)g(the)g(prior)g(on)g(tag)g(sequences.)-186
2237 y Fh(hidden-ngram)39 b Fj(\227)28 b(a)h(w)o(ord)g(boundary)h
(tagger)m(,)h(based)e(on)g(hidden)-61 2324 y(e)n(v)o(ent)19
b(N-gram)g(models.)-186 2451 y Fh(segment-nbest)39 b
Fj(\227)31 b(a)h(rescoring)g(tool)g(that)f(applies)h(a)g(language)-61
2537 y(model)18 b(o)o(v)o(er)h(a)f(sequence)i(of)e(adjoining)i(N-best)e
(lists,)f(thereby)j(o)o(v)o(er)o(-)-61 2624 y(coming)f(sentence)h(se)o
(gmentation)g(mismatch)g([17].)-186 2751 y Fh(lattice-tool)39
b Fj(\227)19 b(a)g(tool)g(to)g(rescore)g(and)g(e)o(xpand)i(w)o(ord)e
(lattices.)-186 2878 y Fh(nbest-lattice)39 b Fj(\227)31
b(a)h(tool)g(to)f(perform)h(w)o(ord)h(error)e(minimiza-)-61
2965 y(tion)38 b(on)i(N-best)f(lists)f([18])h(or)f(construct)i
(confusion)g(netw)o(orks)-61 3052 y(\(\223sausages\224\))21
b([19].)k(T)-6 b(ogether)20 b(with)g(a)f(helper)i(script,)e(this)g
(tool)h(also)-61 3138 y(implements)28 b(a)h(w)o(ord)g(posterior)o
(-based)g(N-best)g(generalization)g(of)-61 3225 y(the)19
b(R)m(O)l(VER)f(algorithm)h([20)q(,)f(21)q(].)-186 3352
y Fh(nbest-scripts)39 b Fj(\227)17 b(a)g(collection)h(of)g(wrapper)f
(scripts)h(that)f(manip-)-61 3439 y(ulate)h(and)i(rescore)f(N-best)g
(lists.)-186 3566 y Fh(pfsg-scripts)39 b Fj(\227)19 b(for)g(con)m(v)o
(erting)h(LMs)f(to)f(w)o(ord)i(graphs.)-186 3693 y Fh(nbest-optimize)39
b Fj(\227)28 b(optimizes)h(log)g(linear)f(score)h(combination)-61
3780 y(for)18 b(w)o(ord)i(posterior)o(-based)g(\(\223sausage\224\))g
(decoding.)157 3969 y Fl(4.)45 b(DESIGN)18 b(AND)g(IMPLEMENT)-7
b(A)g(TION)-184 4129 y Fk(S)t(R)t(I)t(L)t(M)19 b Fj(is)f(designed)j
(and)e(implemented)h(in)f(three)g(layers.)-159 4260 y(1.)42
b(At)32 b(the)i(core)g(are)f(libraries)g(comprising)i(about)f(50)g(C++)
f(classes)-61 4347 y(for)26 b(language)i(models)f(and)g(miscellaneous)h
(objects)f(\(such)g(as)f(v)o(o-)-61 4433 y(cab)o(ulary)k(symbol)i
(tables,)h(N-best)d(lists,)i(w)o(ord)f(graphs,)j(DP)c(trel-)-61
4520 y(lises\),)15 b(which)h(in)g(turn)g(mak)o(e)h(use)f(of)g(a)f
(library)h(of)g(ef)n(\002cient)f(container)-61 4607 y(classes)k
(\(e.g.,)f(arrays,)h(hash)g(tables\).)-159 4734 y(2.)42
b(The)47 b(14)i(main)f(e)o(x)o(ecutable)h(tools)f(such)h(as)f
Fh(ngram-count)p Fj(,)-61 4821 y Fh(ngram)p Fj(,)30 b(and)g(taggers,)i
(are)d(written)f(in)i(C++)f(on)g(top)h(of)f(the)g(API)-61
4907 y(pro)o(vided)20 b(by)f(the)g(libraries.)-159 5034
y(3.)42 b(Numerous)24 b(helper)g(and)f(wrapper)h(scripts)f(perform)h
(miscellaneous)-61 5121 y(tasks)17 b(that)g(are)g(more)g(con)m(v)o
(eniently)i(implemented)f(in)f(the)g(ga)o(wk)h(and)-61
5208 y(Bourne)h(shell)g(scripting)g(languages.)-186 5339
y(W)-6 b(e)18 b(summarize)i(the)f(characteristics)g(of)g(each)h
(implementation)f(layer)l(.)1975 83 y Fl(4.1.)45 b(Class)19
b(libraries)1975 221 y Fj(C++)h(class)h(libraries)e(implement)i(the)f
(API)f(of)j Fk(S)t(R)t(I)t(L)t(M)r Fj(.)j(Object-oriented)1975
308 y(programming)17 b(turns)e(out)g(to)g(be)g(an)h(e)o(xcellent)f
(match)g(for)g(LM)g(implemen-)1975 395 y(tation,)21 b(for)g(se)n(v)o
(eral)g(reasons.)28 b(A)21 b(class)f(hierarchy)h(naturally)g
(re\003ects)g(the)1975 482 y(specialization)d(relation)f(between)h(dif)
n(ferent)f(LM)f(types)i(\(e.g.,)e(a)h(class)g(N-)1975
568 y(gram)k(is)f(a)g(special)h(case)f(of)h(an)f(N-gram,)h(which)g(is)f
(a)g(special)g(case)h(of)f(an)1975 655 y(LM\).)j(Inheritance)h(allo)n
(ws)f(ne)n(w)h(LM)e(v)n(ariants)i(to)f(be)g(deri)n(v)o(ed)h(from)g(e)o
(x-)1975 742 y(isting)19 b(ones)h(with)f(minimal)g(ef)n(fort.)k(A)c(ne)
n(w)h(LM)f(class)g(minimally)g(needs)1975 829 y(to)f(de\002ne)f(only)h
(a)g Fh(wordProb)d Fj(function,)k(the)e(method)h(used)g(to)g(compute)
1975 916 y(conditional)25 b(probabilities)e(gi)n(v)o(en)h(a)f(w)o(ord)h
(and)g(its)e(history)-5 b(.)3594 884 y Ff(1)3659 916
y Fj(Most)24 b(LM)1975 1002 y(functions)f(are)f(de\002ned)h
(generically)-5 b(,)23 b(and)g(need)f(not)g(be)h(reimplemented)1975
1089 y(for)28 b(a)g(ne)n(w)g(deri)n(v)o(ed)g(LM)g(class.)49
b(F)o(or)27 b(e)o(xample,)k Fh(sentenceProb)25 b Fj(is)1975
1176 y(de\002ned)j(in)e(terms)g(of)h Fh(wordProb)d Fj(and)k(typically)e
(inherited)h(from)g(the)1975 1263 y(generic)h(LM)e(class;)31
b(ho)n(we)n(v)o(er)m(,)e(a)e(gi)n(v)o(en)g(LM)g(can)g(de\002ne)g(its)f
(o)n(wn)h(v)o(er)o(-)1975 1349 y(sion)20 b(of)g Fh(sentenceProb)p
Fj(,)d(for)i(ef)n(\002cienc)o(y)h(or)g(to)f(change)i(the)f(standard)
1975 1436 y(beha)o(vior)l(.)2100 1533 y(Hash)h(tables,)g(arrays,)g
(tries,)f(and)h(other)g(basic)g(data)g(structures)f(ha)o(v)o(e)1975
1620 y(been)g(implemented)g(from)f(scratch,)f(for)h(speed)h(and)f
(compactness)i(under)1975 1706 y(the)c(types)f(of)g(uses)h(associated)g
(with)f(LM)g(data)g(structures.)3528 1675 y Ff(2)3580
1706 y Fj(T)-5 b(emplatized)1975 1793 y(data)21 b(structures)f(and)h
(functions)g(are)f(v)o(ery)g(useful)h(be)o(yond)g(the)g(lo)n(w-le)n(v)o
(el)1975 1880 y(containers;)27 b(N-gram)c(statistics)g(and)h
(estimation)g(functions,)h(for)e(e)o(xam-)1975 1967 y(ple,)c(are)g
(templatized)g(to)g(support)h(both)f(inte)o(ger)h(and)f(fractional)g
(counts.)1975 2179 y Fl(4.2.)45 b(Executable)19 b(tools)1975
2318 y Fj(The)28 b(e)o(x)o(ecutable)g(tools)g(are)f(designed)i(to)e(be)
h(both)g(self-contained)g(and)1975 2405 y(combinable)20
b(in)e(useful)g(w)o(ays.)23 b(Thus,)18 b(as)g(sho)n(wn)h(earlier)m(,)f
(a)g(standard)h(LM)1975 2491 y(can)j(be)g(b)o(uilt)e(from)h(a)g(te)o
(xt)g(\002le)g(in)g(a)g(single)g(in)m(v)o(ocation.)31
b(More)22 b(comple)o(x)1975 2578 y(manipulations)29 b(are)e(possible)h
(by)g(chaining)g(together)g(tools,)i(using)e(the)1975
2665 y(Unix)21 b(standard)h(input/output)f(and)h(\223pipe\224)f
(mechanism.)29 b(Thus,)21 b(a)g(class-)1975 2752 y(based)d(N-gram)g
(model)f(can)h(be)f(trained,)h(pruned,)g(e)o(xpanded)h(into)e(a)g(w)o
(ord)1975 2838 y(trigram)j(model,)g(and)h(interpolated)g(with)e
(another)i(model)f(using)h(the)f(fol-)1975 2925 y(lo)n(wing)g(pipeline)
f(\(some)h(options)f(ha)o(v)o(e)g(been)h(omitted)f(to)g(sa)o(v)o(e)g
(space\):)1975 3118 y Fh(replace-words-with-classes)41
b(TRAINDATA)i(|)i(\\)1975 3205 y(ngram-count)e(-text)h(-)h(-lm)f(-)h(|)
g(\\)1975 3292 y(ngram)f(-lm)h(-)f(-prune)g(1e-5)g(-write-lm)g(-)g(|)h
(\\)1975 3378 y(ngram)f(-lm)h(-)f(-expand-classes)f(3)h(-write-lm)g(-)g
(|)h(\\)1975 3465 y(ngram)f(-lm)h(-)f(-mix-lm)g(LM2)g(-write-lm)g
(MIXLM)1975 3678 y Fl(4.3.)h(Helpers)19 b(and)f(wrappers)1975
3816 y Fj(Miscellaneous)39 b(other)e(tools)g(are)g(implemented)g(in)g
(ga)o(wk)g(and)h(shell)1975 3903 y(scripts,)64 b(either)55
b(because)h(the)o(y)g(in)m(v)o(olv)o(e)f(simple)g(te)o(xt)g(manipula-)
1975 3990 y(tions)g(that)f(are)g(more)h(con)m(v)o(eniently)h(done)g
(this)e(w)o(ay)h(\(such)g(as)1975 4077 y Fh(replace-words-with-classes)
20 b Fj(in)25 b(the)g(e)o(xample)g(abo)o(v)o(e\),)i(or)1975
4163 y(because)20 b(the)o(y)e(only)h(require)f(a)g(wrapper)h(that)f
(combines)h(the)f(basic)h(tools.)1975 4250 y(An)30 b(e)o(xample)h(of)f
(the)g(latter)f(is)h Fh(change-lm-vocab)p Fj(,)f(a)h(script)g(that)1975
4337 y(modi\002es)i(the)g(v)o(ocab)o(ulary)g(of)f(an)h(e)o(xisting)g