Counting further back
読了まで約40 分分、9 節 節の 7 例 例。
この部分はまだ翻訳されていないため、英語で表示している。
By the end of this chapter you can build an n-gram language model that looks several tokens back, smooth it with Kneser-Ney so it handles text it hasn't seen (smoothing gives some probability to what the counts never saw, as chapter 1 showed), measure the baseline that every neural model in this book is measured against, and see why counting, however clever, runs out of road.
Chapter 1 built a model that predicted the next word from the one before it, and two things went wrong. It looked back only one word, so a shopper who typed patio bar got the suggestions for bar. And it gave probability zero to every pair of words it hadn't counted, which made its perplexity on new text infinite. Chapter 2 then gave the book better units to count: the store's tokenizer, which splits every word into pieces it knows, so almost every word is spelled from tokens it has seen. This chapter goes back to counting with those tokens, looks further back, and handles the unseen properly.
Every method here is tried where the store, an online furniture and home-goods shop, needs it: on the product names its search box completes. From this chapter on, every model in the book is scored the same way: by its perplexity per token on the store's validation names, tokenized with the store's tokenizer. Product names are what the search box's autocomplete has to predict, and they're short enough for every example to run in seconds. One fixed text, one tokenizer and one measure make every model in the book comparable with every other on names; later chapters add descriptions, from chapter 8, and per-word scores, in chapter 10, where a model's tokenizer differs.
文脈が長いほど訓練テキストへの適合は良くなる
n-gram モデルは、各トークンを直前の n − 1 個のトークンから予測する。bigram モデル (n = 2) は 1 個から、trigram モデル (n = 3) は 2 個から、以下同様に予測する。予測されるトークンより前のトークンを、そのトークンの文脈と呼ぶ。文脈が多いほど予測は良くなるはずである。patio bar の次に来るトークンは、bar だけの後よりもはるかに予測しやすい。カウントの方法は第1章と全く同じだが、ここでのカウントの対象は、n − 1 個のトークンからなる文脈とその次に続くトークンの組である。また、各テキストの先頭には n − 1 個の開始マーカーを付け足すので、最初のトークンにも完全な文脈が与えられる。
平滑化を行わずに、カウントの元になった名前そのものでスコアを測ると、モデルがすでに記憶したテキストをどう扱うかが次数ごとに見えてくる。
1"""Counts the n-grams of orders 1 to 5 in the training names, and scores each order on those same names with no smoothing.2Read the training perplexity lines, which fall as the order grows, against the seen-once lines, which rise."""3import math4from collections import Counter56from lib.names import name_tokens7from lib.ngrams import ngrams, padded89train = name_tokens("train")10for n in [1, 2, 3, 4, 5]:11 # padded adds n-1 start markers and one end marker, so a name's first token has a full context12 pairs = Counter(pair for text in train for pair in ngrams(padded(text, n), n))13 contexts = Counter()14 for (context, _), count in pairs.items():15 contexts[context] += count16 # the total surprise, in nats: each n-gram's probability is its count over its context's count, the model's own estimate17 surprise = -sum(count * math.log(count / contexts[context]) for (context, _), count in pairs.items())18 print(f"{n}-gram training perplexity: {math.exp(surprise / sum(pairs.values())):.1f}")19 print(f"{n}-grams seen once: {sum(1 for c in pairs.values() if c == 1) / len(pairs):.0%}")
python ngram-memorizes.py1-gram training perplexity: 676.4
1-grams seen once: 8%
2-gram training perplexity: 23.9
2-grams seen once: 60%
3-gram training perplexity: 4.9
3-grams seen once: 76%
4-gram training perplexity: 3.2
4-grams seen once: 82%
5-gram training perplexity: 2.9
5-grams seen once: 85%
パープレキシティは文脈が長くなるにつれて急速に下がる。文脈がまったくない場合は 676.4、1 トークンの場合は 23.9、4 トークンの場合は 2.9 である。4 トークンの文脈では、モデルは各ステップで約 3 個のトークンから選んでいることになる。これほど長い n-gram のほとんどは 1 回しか現れないからである。訓練用の名前に含まれる 5-gram のうち 85% は 1 回しか出現せず、モデルはそれぞれの後に何が続いたかを記憶している。
ここに落とし穴がある。カウントに使ったテキストでは、文脈が長いほど常に良く見える。文脈が十分に長ければ、どのテキストも一意になり、モデルはそれをそのまま暗唱できるからである。モデルを自らの訓練テキストでスコアリングしても、測られるのは記憶である。第1章がそもそも検証用テキストを取り分けたのは、このためである。
実践ルール: n-gram モデルであれ他の言語モデルであれ、自らの訓練テキストでのパープレキシティで評価してはならない。モデルが記憶するにつれて、その値は 1 に近づいていく。次数は、本章の残りの部分で行うように、ホールドアウトしたテキストでのパープレキシティによって選ぶ。
長い文脈では根拠が尽きる
訓練データの名前を記憶しても、新しい名前については何も分からない。モデルが利用できるのは、数え上げた文脈だけである。ところが、取りうる文脈の数は文脈の長さに対して指数的に増える。4,000 個のトークンがあれば、2 つ組は 16,000,000 通り、3 つ組は 64,000,000,000 通りになる。これらをすべて網羅できる訓練テキストは存在しない。したがって、文脈が長いほど、新しいテキストがモデルの一度も見たことのない文脈を使う頻度は高くなる。
まず数値で確かめよう。4-gram について、検証用の名前に含まれる 4-gram のうち、訓練用の名前に一度も現れないものはどれだけの割合か。次に、1 から 5 までの各次数についてその割合を示す。
1"""Counts, for each order from 1 to 5, the share of the validation names' n-grams that never occur in the training names.2Compare the lines for 2-grams to 5-grams: that share rises with the order."""3from lib.names import name_tokens4from lib.ngrams import ngrams, padded56train, validation = name_tokens("train"), name_tokens("validation")7print("training tokens:", f"{sum(len(t) for t in train):,}")8print("validation tokens:", f"{sum(len(t) for t in validation):,}")9for n in [1, 2, 3, 4, 5]:10 seen = {pair for text in train for pair in ngrams(padded(text, n), n)} # padded, as in the model, so name starts count too11 held_out = [pair for text in validation for pair in ngrams(padded(text, n), n)]12 unseen = sum(pair not in seen for pair in held_out)13 print(f"{n}-grams in validation never seen in training: {unseen / len(held_out):.1%}")
python unseen-ngrams.pytraining tokens: 337,071
validation tokens: 42,422
1-grams in validation never seen in training: 0.1%
2-grams in validation never seen in training: 12.7%
3-grams in validation never seen in training: 31.1%
4-grams in validation never seen in training: 43.9%
5-grams in validation never seen in training: 53.4%
文脈が長いほど、検証用の名前の n-gram に新しいものが増える。未見のトークンは検証トークンのうち 0.1% にすぎず、これはストアのトークナイザが役割を果たしている結果である。検証用の 2-gram では 12.7% が未見であり、4-gram では 43.9%、5-gram では 53.4% が未見である。4 トークンの文脈では、予測に必要な情報の半分以上をモデルが一度も見ていないことになる。
訓練テキストを増やしても、期待するほどの効果は得られない。言語では、ごく一部の n-gram が非常に頻繁に現れ、大半の n-gram はまれにしか現れない。そのため、テキストを 2 倍にするたびに増えるのは、主に 1 回か 2 回しか現れない n-gram であり、これらは個々の予測を支えるカウントをほとんど改善しない。ストアのカタログにも、同じ傾向が小規模な形で表れている。coffee table のような一般的な句は 1,000 回を超えて数えられる一方、訓練用の名前の 4-gram のうち 82% は 1 回しか数えられていない。これは測定ではなく筆者の判断であるが、カタログが 10 倍の規模になったとしても、新しい 4-gram の大きな割合は未見のまま残るだろう。新しい製品ラインや、サイズと素材の新しい組み合わせが現れ続けるからである。
この 2 つの例は、数え上げ方式の中核的な問題を示している。長い文脈は、見たことがあれば予測の精度を高めるが、見かける機会は次第に減っていく。この章の以降の手法はいずれも、カウントが裏付けるときには長い文脈を使い、裏付けないときにはより短い文脈に切り替えるための方法である。
実践ルール: n-gram の次数を選ぶ前に、訓練テキストに一度も含まれない、保持した n-gram の割合を測定すること。経験則として、この割合が 3分の1 に近づく場合は、ストアの名前における 3-gram がそうであるように、その次数のモデルは未見の扱い方に大きく左右される。したがって、次数よりもスムージングのほうが重要になる。
短い文脈と長い文脈を混ぜる
未見の長い文脈への明らかな対処法は、より短い文脈に頼ることである。補間(interpolation)はこの後退をなめらかに行う。あるトークンの確率を、3-gram、2-gram、1-gramの各カウントが示す値の重み付き混合として求める。モデルがすでに見ている長い文脈はその鋭い予測を寄与し、見ていない部分は短い文脈が補う。和が1になる重みλ₃、λ₂、λ₁を用いると、次のようになる。
P(token | a b) = λ₃ · P₃(token | a b) + λ₂ · P₂(token | b) + λ₁ · P₁(token)
ここで各Pは、第1章の確率と同様に、カウントから得た最尤推定値である。平滑化手法に関するChenとGoodmanの研究は、補間とその変種を詳しく扱っている(Chen and Goodman, 1996)。
手で設定した重みを使うと、この考え方がわかりやすくなる。3つの次数に0.6、0.3、0.09を割り当て、残りの0.01をすべてのトークンに均等に配分する3-gram補間モデルを考える。こうすれば、どのトークンの確率もゼロにならない。ある文脈が一度も見られていないときは、その重みが下位の次数に渡されるため、確率の総和は1のままである。
1"""Builds an interpolated trigram model by hand, with fixed weights, and an add-one bigram model on the same tokens.2The two validation perplexity lines to compare are the interpolated trigram's and the add-one bigram's."""3import math4from collections import Counter56from lib.names import name_tokens7from lib.ngrams import ngrams, padded, perplexity89train, validation = name_tokens("train"), name_tokens("validation")10counts = {k: Counter() for k in (1, 2, 3)} # counts[k][(the k-1 tokens before, token)]11for text in train:12 for context, token in ngrams(padded(text, 3), 3):13 for k in (1, 2, 3):14 # a trigram's context holds two tokens; an order-k model conditions on the last k-1 of them15 counts[k][(context[3 - k:], token)] += 116totals = {k: Counter() for k in (1, 2, 3)}17for k in (1, 2, 3):18 for (context, _), count in counts[k].items():19 totals[k][context] += count20# the tokens the training names contain, plus one slot for a token they never contain21vocabulary = len({token for (_, token) in counts[1]}) + 122weights = {3: 0.6, 2: 0.3, 1: 0.09} # and 0.01 spread evenly over every token232425class Interpolated:26 n = 32728 def probability(self, context, token):29 p, carried = 0.0, 0.030 for k in (3, 2, 1):31 # each order's own context32 weight, total = weights[k] + carried, totals[k][context[3 - k:]]33 if total: # an unseen context passes its weight down34 p, carried = p + weight * counts[k][(context[3 - k:], token)] / total, 0.035 else:36 carried = weight37 # the even 0.01 share, plus any weight passed down from unseen contexts, over the vocabulary38 return p + (0.01 + carried) / vocabulary394041print("interpolated 3-gram validation perplexity:", round(perplexity(Interpolated(), validation), 1))4243# a bigram's context is the one token before the token44bigram_pairs = Counter((context[-1:], token) for text in train for context, token in ngrams(padded(text, 2), 2))45bigram_totals = Counter()46for (context, _), count in bigram_pairs.items():47 bigram_totals[context] += count484950class AddOne:51 n = 25253 def probability(self, context, token):54 # add-one: one added to every pair's count, and one per vocabulary token added to the total55 return (bigram_pairs[(context, token)] + 1) / (bigram_totals[context] + vocabulary)565758print("add-one 2-gram validation perplexity:", round(perplexity(AddOne(), validation), 1))
python interpolate-orders.pyinterpolated 3-gram validation perplexity: 31.4
add-one 2-gram validation perplexity: 218.6
次数を混ぜる方法は、第1章の加算1平滑化より優れている。公平な比較のため、ここでの加算1平滑化は同じ検証トークンに対する2-gramモデルで実行している。異なるトークン列に対するパープレキシティは比較できないからである。補間3-gramのスコアは31.4であり、加算1平滑化のスコアは218.6である。加算1平滑化は確率の大半を決して現れない組に振り向けてしまうが、次数を混ぜる方法は各次数が知っていることを保持する。
この方法には2つの弱点がある。第一に、重みが固定されており、しかもここでの重みは調整ではなく手で選んだものである。ある文脈が一度しか見られていなくても千回見られていても、3-gramには同じ0.6が割り当てられる。千回見られた文脈のほうが、より信頼されるべきであるにもかかわらずである。第二に、1-gramの部分は各トークンに出現頻度に比例した確率を与えるが、次の節で示すように、これは後退先に対する問いとしては適切でない。
実践ルール: 単一のn-gram次数だけを使ってはならない。必ず下位の次数と組み合わせ、すべてのトークンにいくらかの確率を残すこと。固定の重みよりも、後述のKneser-Neyのように、各文脈の重みをそのカウントから決める手法を選ぶこと。固定の重みを使う場合は、カウントに用いたテキストではなく、保持しておいた検証用テキストで重みを選ぶこと。
トークンが後に続く文脈を数える
モデルがより短い文脈へバックオフするとき、問うているのは次のことである。このトークンは、まだ見たことのない文脈にどれほど現れやすいか。生の頻度が答えるのは別の問いである。あるトークンが非常によく現れても、特定の一つか二つのトークンの後にしか現れないことがある。そのようなトークンは、新しい文脈に対する推測としては不適切である。より適切な尺度は、トークンの継続数(continuation count)、すなわちそのトークンが後に続く相異なるトークンの数である。多くの異なるトークンの後に現れたことのあるトークンは、新しいトークンの後にも現れる可能性が高い。
訓練データの商品名で頻度が上位300位以内のトークンのうち、出現頻度のわりに後に続く相異なるトークンの数が最も少ない3つを、ありふれた商品語2つと並べて示す。
1"""Counts, for each token in the training names, how often it occurs and how many different tokens come right before it.2Look at the three narrowest tokens, which occur often but follow few different tokens, beside table and chair."""3from collections import Counter, defaultdict45from lib.names import name_tokens67occurrences, before = Counter(), defaultdict(set)8for text in name_tokens("train"):9 for previous, token in zip(["<s>"] + text, text): # the start marker stands before each name's first token, so that token has something to follow too10 occurrences[token] += 111 before[token].add(previous) # the different tokens this one follows1213common = [t for t, _ in occurrences.most_common(300)] # the 300 most frequent tokens: the pool the prose ranks14# different tokens followed, per occurrence, lowest first: the three narrowest15narrow = sorted(common, key=lambda t: len(before[t]) / occurrences[t])[:3]16for token in narrow + ["table</w>", "chair</w>"]: # </w> marks a token that ends a word, as the store's tokenizer writes it17 print(f"{token:<14} occurs {occurrences[token]:>5,} times, after {len(before[token]):>4,} different tokens")
python continuation-counts.pytvs</w> occurs 323 times, after 1 different tokens
wide</w> occurs 1,985 times, after 14 different tokens
''</w> occurs 10,335 times, after 85 different tokens
table</w> occurs 3,487 times, after 154 different tokens
chair</w> occurs 2,791 times, after 138 different tokens
トークンtvsは数百回現れるが、その直前に来るトークンは1種類しかない。この店の商品名では、常に同じ句、つまりテレビ向けに作られた商品という句の一部として現れる。生の頻度にバックオフするモデルは、tvsをどの文脈でも妥当な推測だと考えてしまうが、実際にそうなることはほとんどない。wideが後に続くトークンはごくわずかで、そのほとんどは数字のインチ記号であり、そのインチ記号である''自体も、ほとんどが数字の後に続く。一方、tableとchairはそれぞれ100を優に超える異なるトークンの後に現れる。たとえばcoffee table、side table、outdoor tableである。継続数は、頻度が語らないことを語っている。これらのトークンは、100を優に超える異なるトークンの後に現れるのである。
継続数は計算が安価である。各トークンについて、その直前に見られたトークンの集合を保持し、その集合の大きさを数えればよい。追加のテキストも調整も必要なく、同じ計数に対して別の問いを立てるだけである。次の節はこれを土台とする。
これはKneser-Neyスムージング(Kneser and Ney, 1995)の背後にある洞察である。モデルがより短い文脈へ後退するとき、生の計数ではなく継続数を用いる。その結果、多くの文脈に現れるトークンに確率が多く割り当てられ、一つの固定された句にしか現れないトークンにはあまり割り当てられない。
実践ルール: 長い文脈から短い文脈へバックオフするときは、トークンを出現頻度ではなく、後に続く異なる文脈の数で重み付けする。生の計数を使うのは、文脈が実際に観測されている最高次の場合に限る。
この部分はまだ翻訳されていないため、英語で表示している。
Smooth with Kneser-Ney
Kneser-Ney smoothing combines interpolation of orders with continuation counts. At each order, Kneser-Ney subtracts a fixed discount d from every count it has seen, and gives the probability it took to the next order down, so a context seen often keeps nearly all its own prediction, and a context seen rarely leans on the shorter context, with the discount it frees going to tokens that turn up in many contexts.
The same formula applies at every order. Below the highest, the counts are continuation counts, except for n-grams that start a text, which keep their raw counts, as the KenLM toolkit does. For a context h and a token w, with c(h w) the count of the pair, c(h) the count of the context, and N(h) the number of different tokens seen after h:
P(w | h) = max(c(h w) − d, 0) / c(h) + d · N(h) / c(h) · P(w | shorter h)
The book's shared module lib.ngrams implements interpolated Kneser-Ney as Chen and Goodman describe it (Chen and Goodman, 1999), with a discount of 0.75, a common default. Its lowest order mixes in a uniform share over the vocabulary, so even a token never seen in training keeps a small probability.
Before trusting the module, work out one probability by hand: stool after a name that starts patio bar, order by order. Set it beside the module's answer, and beside the module's probabilities after this context, summed over every token:
1"""Works out the probability of stool after a name that starts patio bar, order by order, with the chapter's formula.2It checks the result against lib.ngrams and against the module's probabilities summed over the vocabulary: the3by hand line should match the lib.ngrams line, and the summed line should be a probability distribution's total."""4from lib import bpe5from lib.names import name_tokens6from lib.ngrams import START, KneserNey78model = KneserNey(name_tokens("train"), 4) # a 4-gram model; below the top order its counts are continuation counts, except for n-grams that start a name9context = tuple([START] + bpe.store_tokenizer().encode("patio bar")) # a name that starts "patio bar"10token, d = "stool</w>", model.d # </w> ends a word; d is the discount, 0.75 by default111213def by_hand(context, k): # the chapter's formula, one order at a time14 if k == 0:15 return 1 / (len(model.vocabulary) + 1) # order 0 is uniform over the vocabulary, with one more slot for an unseen token16 context = context[len(context) - (k - 1):] if k > 1 else () # the last k-1 tokens: the order-k model's own context17 following, total = model.counts[k][context], model.totals[k].get(context, 0)18 if total == 0:19 return by_hand(context, k - 1) # a context never seen gives all its weight to the order below20 kept = max(following[token] - d, 0) / total # the discounted count21 passed_down = d * len(following) / total # what the discount frees for the order below22 print(f"order {k}: kept {kept:.4f}, passed down {passed_down:.4f}")23 return kept + passed_down * by_hand(context, k - 1)242526print("by hand:", f"{by_hand(context, 4):.4f}")27print("lib.ngrams:", f"{model.probability(context, token):.4f}")28total = sum(model.probability(context, t) for t in model.vocabulary)29print("probabilities after the context, summed:", f"{total:.4f}")
python kneser-ney-by-hand.pyorder 4: kept 0.2500, passed down 0.7500
order 3: kept 0.8056, passed down 0.1667
order 2: kept 0.0630, passed down 0.1275
order 1: kept 0.0007, passed down 0.0318
by hand: 0.8621
lib.ngrams: 0.8621
probabilities after the context, summed: 1.0000
Worked by hand, the formula gives 0.8621 for stool, the same as the module's 0.8621. Each order keeps a share and passes the rest down; the shares add up to that answer. Over every token in the vocabulary, the module's probabilities after this context sum to 1.0000, as a probability distribution must.
Kneser-Ney models of every order from 1 to 5, scored on the validation names, show whether longer contexts now pay off:
1"""Builds Kneser-Ney models of orders 1 to 5 on the training names, scores each on the validation names, and estimates a2discount from the 4-gram counts. The lines to read are the validation perplexities, the 3-gram's set against the interpolated trigram's, and the discount line."""3from lib.names import name_tokens4from lib.ngrams import KneserNey, perplexity56train, validation = name_tokens("train"), name_tokens("validation")7for n in [1, 2, 3, 4, 5]:8 model = KneserNey(train, n)9 print(f"{n}-gram validation perplexity: {perplexity(model, validation):.1f}")1011model = KneserNey(train, 4)12# the highest order keeps raw counts, not continuation counts, so these are how often each 4-gram occurs in training13top = [c for following in model.counts[4].values() for c in following.values()]14once, twice = top.count(1), top.count(2)15print("4-grams seen once:", f"{once:,}")16print("4-grams seen twice:", f"{twice:,}")17# Chen and Goodman's estimate of the discount: D = n1 / (n1 + 2 n2), with n1 and n2 the counts seen once and twice18print("discount estimated from them:", f"{once / (once + 2 * twice):.2f}")
python kneser-ney-by-order.py1-gram validation perplexity: 687.2
2-gram validation perplexity: 46.9
3-gram validation perplexity: 24.9
4-gram validation perplexity: 23.1
5-gram validation perplexity: 23.5
4-grams seen once: 164,374
4-grams seen twice: 18,359
discount estimated from them: 0.82
Kneser-Ney beats the hand-weighted interpolated trigram from the interpolation section at the same order, with no weights to choose. Its trigram scores 24.9, against 31.4 for the hand-weighted one.
Longer contexts now help on new text, instead of only on the text the model counted, up to a point: validation perplexity falls from 46.9 for the bigram to 23.1 for the 4-gram, then rises to 23.5 for the 5-gram. The step from trigram to 4-gram is small, and the 5-gram is worse, because by then most contexts are unseen and the extra order adds noise. The discount, too, can be estimated from the counts: Chen and Goodman give D = n₁ / (n₁ + 2 n₂), where n₁ and n₂ are the numbers of n-grams seen once and twice, and on the store's 4-grams it's 0.82, close to the default.
Working rule: Smooth n-gram models with interpolated Kneser-Ney and a discount of 0.75 unless held-out text says otherwise. Raise the order only while validation perplexity keeps falling noticeably, and stop when a step barely helps or hurts, as the step from 4-gram to 5-gram does. A variant, modified Kneser-Ney, uses three discounts instead of one and is the one toolkits such as KenLM build; it would likely lower the baseline a little, and this book keeps the single discount because it's easier to follow by hand.
3トークンの文脈によるオートコンプリート
文脈を長くすれば、第1章で見た検索ボックスの最悪の候補が改善されるはずである。そこでは patio bar に対して bar と同じ候補が出ていた。4-gram の Kneser-Ney モデルは、買い物客が入力した直近の3トークンを参照するので、patio が視野から外れない。
候補は bar、patio bar、outdoor bar と変えると変わるだろうか。それぞれの後に続く次トークンのうち、4-gram モデルが最も可能性が高いと見る上位3つを取り上げる。各プレフィックスは、買い物客の入力と同じく、名前の先頭として扱う。各候補は、語末マーカーを除いたトークンで示す。
1"""Asks the 4-gram model for its three likeliest next tokens after bar, patio bar and outdoor bar, each typed as the start2of a name, then counts the training names that contain outdoor bar. The three suggestion lines carry the point, and the last line3counts the training names with outdoor bar in them."""4from lib import bpe5from lib.names import name_tokens6from lib.ngrams import START, KneserNey78model = KneserNey(name_tokens("train"), 4)9tokenizer = bpe.store_tokenizer()10candidates = sorted(model.vocabulary) # sorted first, so tokens with equal probability keep alphabetical order1112for typed in ["bar", "patio bar", "outdoor bar"]:13 # padded with start markers, then the last three tokens: a short prefix still gives a full context14 context = tuple([START] * 3 + tokenizer.encode(typed))[-3:]15 ranked = sorted(candidates, key=lambda t: -model.probability(context, t))[:3] # negated, so the likeliest sort first16 print(f"{typed:<12} -> " + ", ".join(f"{t.replace('</w>', '')} {model.probability(context, t):.2f}" for t in ranked))17# each name as one string of tokens, so the check below matches whole tokens rather than parts of them18names = [" ".join(t) for t in name_tokens("train")]19print("training names containing 'outdoor bar':", sum("outdoor</w> bar</w>" in n for n in names))
python ngram-autocomplete.pybar -> & 0.23, unit 0.13, with 0.11
patio bar -> stool 0.86, & 0.03, with 0.02
outdoor bar -> & 0.23, with 0.19, stool 0.06
training names containing 'outdoor bar': 0
bar だけの後では、モデルは & や with などの続きを候補に挙げる。これらは bar & counter stools のように始まる名前に属するものである。単語の位置を無視した第1章のバイグラムは、stool を最初に挙げていた。patio bar の後では、stool を高い確率で候補にする。文脈が予測を変えたのであり、バイグラムモデルにはこれができない。ところが outdoor bar の後では、候補は再び & と with の方へ戻ってしまう。例の最後の行が示すとおり、学習データの名前に outdoor bar を含むものがなく、モデルが bar の後に続くものへバックオフするからである。
& や with のような候補は、店の名前の実際の続きではあるが、買い物客が提示を望むことはまれである。検索ボックスでは、第1章で句読点について示したようにこれらを除外するか、単一のトークンではなくフレーズ全体に補完すればよい。これは表示方法の選択であり、モデルの確率はどちらでも変わらない。
outdoor bar の行は、カウントによる手法の限界を小さく示している。モデルは patio bar stool、outdoor patio、bar stool を何度も見ているので、屋外のバーにはおそらくスツールが付くと推測するための材料を持っている。しかし outdoor bar stool のカウントは表の中の独立した項目であり、patio bar stool とは何もつながっていない。モデルには、outdoor と patio が似ているという何らかの概念が必要だが、カウントにはそれがない。第4章で、店のトークンにその概念を与える。
実践ルール: 候補の生成には、モデルが支えられる最も長い文脈を使うこと。また、outdoor bar のように学習データでまれな文脈の候補は、一般的な文脈とは別に確認すること。カウントに基づくモデルが一般的な推測に戻ってしまうのは、そうした文脈である。
この部分はまだ翻訳されていないため、英語で表示している。
The baseline every later model is measured against
Every chapter from here on builds a model that learns, not one that counts, and each claims to predict the store's text better. A claim like that needs a baseline, a fixed yardstick: one model, one text, one tokenizer and one measure that every later model is compared against. A baseline should be the strongest simple model available, so that beating it means something.
The baseline for this book is the 4-gram Kneser-Ney model of this chapter, scored on the store's validation names with the store's tokenizer. Its validation perplexity is 23.1 per token, from the Kneser-Ney example. The 5-gram model is worse, at 23.5, and holds more counts, so the 4-gram is the baseline: the best of this chapter's counted models on the store's names. A stronger counted baseline exists, modified Kneser-Ney, and the book doesn't use it, for the reason the Kneser-Ney section gives.
The baseline also sets expectations. A perplexity near twenty means the model is, on average, choosing among about twenty likely tokens at each step of a product name. Some steps are nearly certain, such as table after coffee, and some are wide open, such as the first token of a product line's name. A neural model that beats the baseline should do so by predicting the open steps better, because it can relate one context to another, not by memorizing more.
Two things about the baseline will stay fixed for the rest of the book. Every perplexity is per token of the store's tokenizer, on the validation names, so the numbers in every chapter can be set side by side. And the test names stay untouched until the book's final comparison, so nothing in the book is tuned on them.
Working rule: Before building a learned model, build the strongest counted model you can and record its held-out perplexity as the baseline. Report every later model against it, on the same text and with the same tokenizer, and treat a learned model that doesn't beat it as a result to explain, never as a success. Later chapters find exactly that, and earn the learned models their place another way.
本番環境で起こる問題
n-gram モデルは、パープレキシティを最後の1ポイントまで下げることよりも、速度と透明性が重要な場面、たとえば高速なオートコンプリートでは、今も有用である。一方で、次のような問題が生じる。
- テーブルが肥大化する。 次数を1つ増やすごとに、カウントのテーブルが1つ増える。異なる n-gram の数は、テキストの量とほぼ同じ速さで増える。1回しか現れなかった n-gram は刈り込む。ただし、まれな n-gram にも実際に有用な情報を持つものがあるため、刈り込み後に検証用パープレキシティを測定する。
- まれな文脈には一般的な答えが返る。
outdoor barで示したように、モデルがほとんど見たことのない文脈では、より短い文脈が示す候補に後退する。よくある接頭辞だけでなく、まれな接頭辞に対する候補も監視する。 - 割引値は選択である。 0.75 という割引値は妥当な初期値であって、法則ではない。対象のテキストが店舗のテキストと大きく異なる場合は、保持しておいたテキストで調整する。
- 新しいテキストによってカウントが変わる。 商品ラインは入れ替わり、あらゆる候補の根拠となるカウントは、最後に再構築した時点のものでしかない。再構築は定期的に行い、最近のテキストでの検証用パープレキシティを基準値と比較して、モデルが古くなった時期を見極める。
- 確率の合計は1でなければならない。 手書きのバックオフ方式では、確率が失われたり二重に数えられたりすることが多く、パープレキシティが実際よりも良く、または悪く見えてしまう。いくつかの文脈について、語彙全体にわたる確率の合計がそれぞれ1になることを確認する。
この章で決めたこと
- 本書のすべてのモデルは、ストアの検証用の名前に対し、ストアのトークナイザを通して、トークンあたりのパープレキシティで評価する。 一つのテキスト、一つのトークナイザ、一つの尺度を用いることで、各章の数値を名前の上で比較できる。テスト用の名前は、本書の最終比較のために取っておく。最終比較は第11章で行う。
- n-gram モデルは、ディスカウント 0.75 の補間 Kneser-Ney 法で平滑化する。 同じ次数の手作業で重みを付けた補間より良い結果が得られ、調整すべき重みもない。これは、各文脈をその頻度に比例して信頼し、多くの文脈の後に続くトークンへバックオフするためである。
- ベースラインは 4-gram の Kneser-Ney モデルであり、 検証用の名前でのスコアはトークンあたり 23.1 である。5-gram モデルはスコアが悪く、保持するカウントも多いので、4-gram を基準の物差しとする。
- オートコンプリートは、3 トークンの文脈を用いた 4-gram モデルの候補を使う。
patio barは補完できるが、outdoor barのような稀な文脈では依然として一般的な候補に戻ってしまう。ここが学習モデルの改善すべき点である。 - 文脈を長くしても改善が止まるのは、文脈が重要でないからではなく、その文脈が未出現だからである。 検証用の名前の 5-gram の半数を超えるものが、学習データに一度も現れない。モデルは未出現の文脈を、出現済みの似た文脈と関連づけることができない。第4章では、どのトークンが似ているかを表すベクトルをトークンに与えることで、この問題に取り組み始める。
この版における本章
第2026.11.16版2026年11月19日時点で例が通過この章の7 例件のうち7件が合格
英語版の書籍(版2026.11.16)から翻訳した。