言語処理学会 第25回年次大会 発表論文集 (2019年3月)

逐次語彙選択によるニューラル Input Method の高速化
朱 中元

李 心剣

jiayao@microsoft.com

shu@nlab.ci.i.u-tokyo.ac.jp

xinjianl@andrew.cmu.edu

マイクロソフト東京大学 大学院情報理工学系研究科

Carnegie Mellon University

大附 克年

中山 英樹

katsutoshi.ohtsuki@microsoft.com

nakayama@ci.i.u-tokyo.ac.jp

マイクロソフト東京大学 大学院情報理工学系研究科

今日はいい Today is good

はじめに
to kana1

姚 佳立

コンピューターやスマートフォンで，日本語や中国

きょ

lexicon lookup

語などの非アルファベット言語のテキストを入力する

kyouhaii

ためには，キー系列を目的言語の文字に変換する入力メソッド (Input Method) が必要となる．Input Method

contextvector

としては，n-gram 言語モデルが一般的に使われている．n-gram 言語モデルで trigram より長い文脈を扱おは

best path...

において単語系列の確率を評価するための言語モデル

ういいいい good

今日 todayは is

うとすると，モデルサイズやデータスパースネスの問
word lattice

題からあまり現実ではなく，n-gram とは別のモデルで長い文脈を扱うことが多い．一方で，RNN や LSTM

図 1: ニューラル言語モデルと Viterbi デコーディング

をはじめとするニューラル言語モデルは，長い文脈情による Input Method

報をモデルに含むことができ，n-gram 言語モデルよりも高い精度を達成している [1, 8, 9] だけでなく，扱う文脈を長くしても n-gram 言語モデルのようにモデルサイズが増大していかないという特徴がある．更に，カスタム ASIC [5] という新しい専用ハードウェア処理装置の開発により，ニューラルベースのモデルが今後多くのデバイスに適用されることが期待されている．

いて検討する．ニューラル言語モデルと Viterbi デコーディングによる Input Method の概念図を図 1 に示す．多くのニューラルベースのシステムと同様に，実行速度のボトルネックは言語モデル確率を得るためのsoftmax 演算部分となる．Input Method で必要な逐次

通常，ニューラルベースの音声認識や機械翻訳サー的な入力に対する softmax 演算を高速化するために，

ビスは，モデルサイズや計算リソースの要件からクラ時刻 t におけるサブセット語彙 Vt を構築する逐次語彙ウドサービスとして提供されていることが多く，その選択 (incremental vocabulary selection, IVS) という処理は入力チャンクに対するバッチ処理として実現さアプローチを提案する．|Vt | は通常，元の語彙サイズのれている．それに対して Input Method は，キー入力に対して対話的に実行され高速な応答速度が要求されるため，ニューラル言語モデルを適用する際には，既存1% 未満と小さく，softmax の演算を Vt に限定することで，演算コストを大幅に削減することが期待できる．

2のバッチ処理に対する高速化手法だけでなく，逐次的前述したように，ニューラル言語モデルでは softmaxな入力に対する高速化を実現する必要がある．
本 稿 で は， ニ ュ ー ラ ル 言 語 モ デ ル に よ る Input

Method の実時間処理を実現するための高速化につ関連研究演算が最も計算コストを必要とし，特に語彙サイズが大きい場合に顕著である．Differentiated softmax [2, 4]は，頻度の低い単語の embedding サイズを減らすこと― 1018 ―Copyright(C) 2019 The Association for Natural Language Processing.
All Rights Reserved.

により演算量を削減している．評価単語がわかっているワードラティスデコーダーでは，構造化された出力

アルゴリズム 1 逐次語彙選択
1: Initialize:

B ← beam size層によってすべての語彙に対する確率分布計算を避けΠ ← hypothesis dictionary

ることが行われる [10, 6, 11]．単語単位ではなく文字V̂ ← samples from vocabulary

単位で処理を行う character-level RNN [8] は，語彙サイズを大幅に減らすことができるが，漢字を含む日本語や中国語では英語などのラテン文字の言語に比べて削減効果は小さい．

softmax のコストを削減する別のアプローチとして語彙の操作がある．機械翻訳では，原文が与えられると，翻訳前に訳語の語彙を制限することができ，サブセット語彙で softmax を計算することができる [3, 7]．
ただし，Input Method の場合，必要な語彙はキー入力によって徐々に増加するために，その動的な変化に対応する必要がある．

t ← current step t

2: Vt ← sub vocabulary with Eq. 2
3: Vt ← Vt ∪ V̂
4: Vfix ← empty set
5: for k ← t − 1 to 1 do
6:Vfix ← Vfix ∪ (Vt \ Vk )7:Vk ← Vt

8: Re-compute the logits on Vfix for all past hyps
9: Evaluate Π[t]10: Π[t] ← best B hyps in Π[t]11: Update LSTM state for Π[t]3 提案手法

12: output Π[t]Input Method における逐次的なキー入力に対してニューラル言語モデルの softmax 演算量を削減する逐

softmax 分布は単語 wt を含まないことがある． Π[t]次語彙選択を提案する．アルゴリズムをアルゴリズム 1を評価するには，すでに計算された softmax 分布で欠に示す．Π は LSTM 状態の各時刻における最適経路のけている語彙項目を修正する必要がある．追加された連想配列である．各時刻での最適経路を得るための辞

語彙の logits を分母に追加することにより，時刻 k で書 lookup 操作として [·] を定義する．時刻 t までの入の古い確率を修正することができる．

力系列 (xi , ..., xt ) に対するラティス語彙 Dt は式 1 のように計算することができる．

Dt =t[P (yk = i|hk )exp(h>k Wi )P.
>
exp(hk Wj ) +exp(h>k Wj )j∈Vkj∈d= P

match(xi , ..., xt ),

(1)

i=1

ここで，関数 match(·) は，部分入力系列にマッチするすべての単語を返す．たとえば，入力系列「あした」を考えると，Dt には，「あした」，「した」，「た」に一致

ここで，W は出力層の分散表現行列である．hk は
経路 πk のキャッシュされた LSTM 状態で，これを使って必要な logit を計算することができる．d は時刻

lattice
するすべての単語が含まる．新たな文字
xttopが入力され
OOV

(3)

step t − 2samples

step t − 1step 𝑡ると，時刻 t までの入力系列に対してすべての可能な出力単語を含む語彙 Vt を次のように構築する．
latticeword

Vt =t[randomsamples(2)Di .

lattice vocab

diff vocab

i=1

...

...

...

仮 説 (πt−l , wt ) を 評 価 す る た め に 必 要 な 確 率p(wt |πt−l ) はすでに計算され，πt−l にキャッシュさlatentvector

pathℎ𝑡れていることが期待される．しかし，図 2 に示すように，Vt は逐次更新されるので，前の時刻で計算された(a)― 1019 ―図 2: 時刻によって増加する評価語彙(b)

Copyright(C) 2019 The Association for Natural Language Processing.
All Rights Reserved.

Vt \ Vk の間の語彙の差分である．実際には，経路ごとmodelに不足する語彙が異なるため，必要なすべての語彙の和集合 Vfix を計算してから，それらの log をまとめて

pp

top1

top10

hit %

hit %

uni-gram

833.55

26.95

45.85

bi-gram KN

99.30

51.15

78.10

最初のステップの語彙はかなり小さいので，すべてtri-gram KN

68.11

55.60

79.65の語彙からサンプリングしたサブセット語彙として Ṽ

LSTM baseline

41.39

61.20

88.30

再計算する．

を導入する．機械翻訳におけるビームサーチとは対照

表 1: 変換精度評価結果的に，異なる数の単語を含む経路を評価する必要がある．Ṽ と Vt を使用することによって単語の確率を近似する．
最適経路が決定されると，Π[t] の B 経路の LSTM状態を更新する．最適経路の Π[t] が変換結果として返示す．また softmax に要した演算時間もあわせて示す．
表 2 に評価結果を示す．提案手法である逐次語彙選択(IVS) が，ベースラインである LSTM (LSTM baseline

される．

w/ batch) の 84 倍の演算速度を実現していることが確

4 実験の語彙サイズに対して，たかだか数百単語であった．

4.1

認できる．フレーム当たりのアクティブな語彙は，50k

IVS がキーストロークごとに必要な演算時間は 3ms

実験設定

BCCWJ コーパスの 5.8M 文を用いて評価実験をであり，演算性能の低いデバイスであっても実時間処行った．データセットの 70% を学習用，20% を開発理が可能なレベルである．IVS により softmax に要す用，10% を評価用に分割した．データセットに出現る演算時間が大幅に削減され，必要な演算はほとんどする 611k 異なり単語のうち頻度上位 50k 語（被覆率97.3%）を Input Method の語彙とした．LSTM 言語モデルの学習は，バッチサイズ 384，dropout 確率はLSTM 自体のものとなっている．
IVS に，いくつかのサンプリング手法を適用した評価も行った．サンプル数 400 で top sampling と uniform

0.9，Adam 最適化の学習率 0.001 で行った．埋め込みsampling を適用した場合，top sampling の方が改善精層および隠れ層の次元数はそれぞれ 256 次元とした．

度が高かった．

また，Viterbi デコーディングのビーム幅は 10 とした．

4.2

精度評価

LSTM 言語モデルと n-gram 言語モデルによる Input Method 変換精度を，perplexity と文正解率とで比較した．n-gram 言語モデルは，カットオフ無しでKneser-Ney 平滑化を適用した．評価結果を表 1 に示す．表 1 をみると，LSTM 言語モデルは trigram 言語

Softmax の演算量を削減する方法として Differentiated softmax があるが，本評価のように語彙数が大きい場合には，その削減効果は限定的であった (D-Softmax[2], D-Softmax*[4])．語彙数を抑制する方法として，文字あるいは subword ベースの LSTM がある．
隠れ層と埋め込み層をそれぞれ 1024 次元，512 次元とした文字ベースの LSTM （語彙数 3,717）の評価をモデルに対して，perplexity を 68.11 から 41.39 へと行った (Char LSTM) が，入力メソッドタスクでは文約 40% 削減し，1-best 正解率および 10-best 正解率も字ベースのアプローチは曖昧性が高く，ビームサイズそれぞれ約 10% 改善していることが確認できる．

4.3を 50 まで大きくしても十分な精度を得ることができな
かった (Char LSTM w/ large beam)．

速度評価

LSTM 言語モデルの逐次語彙選択による実行速度の削減を評価した．本評価では，言語モデルの確率計算に5 おわりに必要な時間を比較した．LSTM 言語モデルでは，LSTM

Input Method は，日本語や中国語などの入力におと softmax の演算部分を，n-gram 言語モデルでは，確いてなくてはならないものであり，またキー入力およ率の look-up に要する部分を対象としている．ラティ

び操作に対して遅延があると操作性を大きく損なってス構築などは実装への依存性が高いので比較からは除外した．実験結果は，キーストロークごとの演算時間を― 1020 ―*1 ビームサイズは 50 に設定されている．

Copyright(C) 2019 The Association for Natural Language Processing.
All Rights Reserved.

total time

softmax time

top-1 hit

top-10 hit

(ms)

(ms)

(%)

(%)

tri-gram Kneser-Ney

0.0025

-55.6

79.6

LSTM baseline w/o batch

526

513

61.2

88.3

LSTM baseline w/ batch

8784

61.2

88.3

Char LSTM

632153.2

79.8

Char LSTM w/ large beam *1

1525554.4

85.2

D-Softmax

383560.8

86.8

D-Softmax

373560.9

87.5

IVS

3158.886.9w/ top sampling

4260.188.2w/ uniform sampling

4258.987.2w/ self-norm

31

60.1

88.2

non-incremental VS

112

58.8

86.9model∗

表 2: 処理速度評価結果
しまう．本稿では，n-gram 言語モデルより精度の高いLSTM 言語モデルを日本語の入力メソッドに適用することを検討した．LSTM 言語モデルは，softmax の演算が処理時間のボトルネックとなるが，提案した逐次語彙選択 (IVS) により，ベースラインの LSTM 言語モデルと同程度の精度を維持しながら，1 フレーム当たりの言語モデル演算時間を 3ms にまで削減することができた．これは，比較的低スペックのデバイスでも遅延を感じずに入力メソッドを使うことができる実用可能なレベルの速度であるといえる．

参考文献[1] Yoshua Bengio, Réjean Ducharme, Pascal Vincent, andChristian Jauvin. A neural probabilistic language model.
Journal of machine learning research, 3(Feb):1137–1155,
2003.
[2] Wenlin Chen, David Grangier, and Michael Auli. Strategies for training large vocabulary neural language models.
In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: LongPapers), volume 1, pages 1975–1985, 2016.
[3] Sebastien Jean, Kyunghyun Cho, Roland Memisevic, andYoshua Bengio. On using very large target vocabulary
for neural machine translation. In 53rd Annual Meeting of the Association for Computational Linguistics,
ACL-IJCNLP 2015, pages 1–10. Association for Computational Linguistics (ACL), 2015.
[4] Armand Joulin, Moustapha Cissé, David Grangier, Hervé
Jégou, et al. Efficient softmax approximation for gpus.
In International Conference on Machine Learning, pages
1302–1310, 2017.

[5] Norman P. Jouppi and Cliff Young. In-datacenter performance analysis of a tensor processing unit. 2017
ACM/IEEE 44th Annual International Symposium on
Computer Architecture (ISCA), pages 1–12, 2017.
[6] Hai Son Le, Ilya Oparin, Alexandre Allauzen, Jean-LucGauvain, and FranÃ§ois Yvon. Structured output layer
neural network language model. 2011 IEEE International
Conference on Acoustics, Speech and Signal Processing(ICASSP), pages 5524–5527, 2011.
[7] Haitao Mi, Zhiguo Wang, and Abe Ittycheriah. Vocabulary manipulation for neural machine translation. In Proceedings of the 54th Annual Meeting of the Associationfor Computational Linguistics (Volume 2: Short Papers),
volume 2, pages 124–129, 2016.
[8] Tomáš Mikolov, Martin Karafiát, Lukáš Burget, Jan Černockỳ, and Sanjeev Khudanpur. Recurrent neural network based language model. In Eleventh Annual Conference of the International Speech Communication Association, 2010.
[9] Tomas Mikolov and Geoffrey Zweig. Context dependent
recurrent neural network language model. 2012 IEEE
Spoken Language Technology Workshop (SLT), pages
234–239, 2012.
[10] Andriy Mnih and Geoffrey E Hinton. A scalable hierarchical distributed language model. In Advances in neural
information processing systems, pages 1081–1088, 2009.
[11] Yongzhe Shi, Weiqiang Zhang, Jia Liu, and Michael T.
Johnson. Rnn language model with word clustering andclass-based output layer. EURASIP J. Audio, Speech andMusic Processing, 2013:22, 2013.

― 1021 ―Copyright(C) 2019 The Association for Natural Language Processing.
All Rights Reserved.