# CRF に基づく形態素解析器のスコア計算の分割による モデルサイズと解析速度の調整

赤部晃一 ${ }^{1}$ 神田峻介 1 小田悠介 ${ }^{2}$
${ }^{1}$ LegalOn Technologies Research ${ }^{2}$ 東北大学 データ駆動科学・AI 教育研究センター
\{koichi.akabe, shunsuke.kanda\}@legalontech.jp
yusuke.oda.c1@tohoku.ac.jp

## 概要

CRF に基づく形態素解析器において，2-gram ス コアの持ち方を変更し，用途に応じてモデルサイズ と解析速度の調整を行うことを提案する。代表的な CRF に基づく形態素解析器では, CRF の 2-gram ス コアを事前に計算して連接表に記憶しておくことで 予測を効率的に行うが，素性の設計によってはスコ アの事前計算は連接表を肥大化させる. 本稿では， 2-gram スコアの計算の一部を予測時に行うことで，連接表の肥大化を抑制する．また，2-gram スコアの 計算を効率的に行うことで，予測時に追加的に生じ る計算時間を抑制する。

## 1 はじめに

形態素解析は, 日本語の自然言語処理における基礎技術であり，情報検索や機械学習の前処理として 利用される. 日本語における代表的な形態素解析器 としては, MeCab [1] や KyTea [2] が挙げられる. こ のうち, MeCab は Conditional Random Fields (CRFs) [3] を利用してパラメータを学習し, 入力文から形態素ラティスを生成し，単一のノードから得られる 素性と, 隣合う 2 つのノードに対応した素性を用 い，各素性のパラメータを最尤推定する。

素性は解析精度等を考慮して設計されるが，設計 によってはモデルサイズが肥大化する．公開されて いる学習済みモデルを比較すると，IPAdic [4] では 連接表のサイズが $1,316 \times 1,316$ であるが，現代書 き言葉 UniDic [5] (Ver. 3.1.0) は 15,626×15,388であ り，各スコアを 16-bit で表現すると，連接表だけで $459 \mathrm{MiB}$ となる. UniDic では，素性テンプレートの 見直しによってモデルサイズを軽量化する試みが行 われているが，依然として組み込み機器や Web フロ ントエンド等の資源が限られた環境で利用するには
モデルサイズが大きく，可搬性が低い.

本稿では，まず $\mathrm{CRF}$ に基づく形態素解析について 説明し，一部のスコア計算を解析時に行うことで， モデルのパラメータに手を加えずにモデルサイズを 軽量化することを提案する。また，解析時のスコア 計算を効率的に行う方法についても示す.

## 2 CRF に基づく形態素解析

## 2.1 定式化

CRF [3] はラティス上に定義される線形識別モデ ルであり，入力単語列を $\boldsymbol{x}$ ，ラベル列（品詞，読み 等）を $\boldsymbol{y}$ とし，確率を式 (1)でモデル化する。

$
P(\boldsymbol{y} \mid \boldsymbol{x})=\frac{\exp \left(\boldsymbol{w}^{\top} \boldsymbol{\phi}(\boldsymbol{x}, \boldsymbol{y})\right)}{\sum_{\boldsymbol{y}} \exp \left(\boldsymbol{w}^{\top} \boldsymbol{\phi}(\boldsymbol{x}, \boldsymbol{y})\right)}
$

ここで,$w$ は重みべクトルであり,$\phi(x, y)$ はラティ ス上の各パスに対応した素性ベクトルである．素性 ベクトルを，各ノードに与えられる 1-gram 素性べ クトル $\left(\phi_{1}\right)$ と，各エッジに与えられる 2-gram 素性 ベクトル $\left(\phi_{2}\right)$ に分ければ，式 (2) のように表すこと が可能である.

$
\boldsymbol{\phi}(\boldsymbol{x}, \boldsymbol{y})=\sum_{i} \phi_{1}\left(\boldsymbol{x}, y_{i}\right)+\sum_{i, j} \phi_{2}\left(\boldsymbol{x}, y_{i}, y_{j}\right)
$

ここで， $y_{i}, y_{j}$ は隣り合う 2 つのノードを表す. 1-gram 素性は辞書中の各エントリ $e_{i}$ に付随した情報のみ利用しており，文脈に依存する情報を利用 しない. すなわち, $\boldsymbol{\phi}_{1}\left(\boldsymbol{x}, y_{i}\right):=\boldsymbol{\phi}_{1}\left(e_{i}\right)$.このため,各エントリ $e_{i}$ の 1-gram 素性のスコア $\boldsymbol{w}^{\top} \boldsymbol{\phi}_{1}\left(e_{i}\right)$ は エントリごとに事前に計算しておけば良い。一方， 2-gram 素性には隣り合う 2 つのエントリの情報を 用いる. すなわち, $\boldsymbol{\phi}_{2}\left(\boldsymbol{x}, y_{i}, y_{j}\right):=\boldsymbol{\phi}_{2}\left(e_{i}, e_{j}\right)$. 単純 に辞書内のすべてのエントリの組 $\left(e_{i}, e_{j}\right)$ に対して $\boldsymbol{w}^{\top} \boldsymbol{\phi}_{2}\left(e_{i}, e_{j}\right)$ を事前計算することは，モデルを肥大化させて現実的でないため，実際には各エントリを
素性情報に基づいてグループ化し, グループのイン デックスを用いて 2-gram 素性のスコアを参照する。

## 2.2 素性テンプレート

素性ベクトルの生成には複数の素性テンプレー ト関数が利用される。これは, 辞書のエントリを引数とした関数であり，主に人手で設計される．素性 テンプレート関数は 1-gram 素性と 2-gram 素性の両方に対して定義されるが，ここでは 2-gram 素性の み着目する， $K$ 個の素性テンプレートを用いると， 2-gram 素性のスコアは式 (3)で表される.

$
\boldsymbol{w}^{\top} \boldsymbol{\phi}_{2}\left(e_{i}, e_{j}\right)=\sum_{k=1}^{K} \boldsymbol{w}^{\top} \boldsymbol{t}_{k}\left(e_{i}, e_{j}\right)
$

ここで， $\boldsymbol{t}_{k}$ は $k$ 番目の 2-gram 素性テンプレート関数である. 次に, 式 (4)のように, 左右のエントリ $e_{i}, e_{j}$ から事前に素性テンプレートに対応した情報 を取り出し，その組み合わせによって素性べクトル を生成することを考える。

$
\boldsymbol{t}_{k}\left(e_{i}, e_{j}\right)=\boldsymbol{f}\left(l_{k}\left(e_{i}\right), r_{k}\left(e_{j}\right)\right)
$

ここで, $l_{k}, r_{k}$ は，それぞれ左右のエントリから $k$ 番目の素性テンプレートに対応した素性 IDを取得す る関数, $f$ は, 左右の素性 ID の組に応じて素性べ クトルを返す関数である。

次に，各エントリから全ての素性テンプレートに 対応した素性 ID を配列形式で取得する関数 $\boldsymbol{l}, \boldsymbol{r}$ を 式 (5), (6)のように定義する.

$
\begin{aligned}
\boldsymbol{l}\left(e_{i}\right) & :=\left(l_{1}\left(e_{i}\right), l_{2}\left(e_{i}\right), \ldots, l_{K}\left(e_{i}\right)\right) \\
\boldsymbol{r}\left(e_{j}\right) & :=\left(r_{1}\left(e_{j}\right), r_{2}\left(e_{j}\right), \ldots, r_{K}\left(e_{j}\right)\right)
\end{aligned}
$

さらに，左右の素性 ID の組 $(l, r)$ に対応したスコ ア $m$ を式 (7)のように事前に計算する.

$
m(l, r):=\boldsymbol{w}^{\top} \boldsymbol{f}(l, r)
$

これらを用い，各エントリの組に対応した 2-gram 素性のスコアを式 (8) で計算する.

$
\boldsymbol{w}^{\top} \boldsymbol{\phi}_{2}\left(e_{i}, e_{j}\right)=\sum_{k=1}^{K} m\left(l_{k}\left(e_{i}\right), r_{k}\left(e_{j}\right)\right)
$

## 3 2-gram スコアの部分的事前計算

## 3.1 連接表の大きさ

$\mathrm{MeCab}$ では, 全ての $\boldsymbol{l}\left(e_{i}\right), \boldsymbol{r}\left(e_{j}\right)$ の組に対してス コアを事前に計算しておき，それらを連接表に格納 する。重みの学習時に L1 正則化を行えばスパース
なモデルが学習されるため, $\boldsymbol{l}\left(e_{i}\right), \boldsymbol{r}\left(e_{j}\right)$ は辞書中 の複数のエントリで共通したものとなり，連接表の サイズをある程度抑えることが可能である．例えば 現代書き言葉 UniDic では，辞書に登録されている 語彙数は 1,879,222 語であるが，連接表のサイズは $15,626 \times 15,388$ であり，複数のエントリで共通した 素性情報が参照されていることが確認できる。それ でもなお, UniDic は素性テンプレートが詳細に設計 されていることもあり，1 節でも述べたようにモデ ルが大きく可搬性が低い.

## 3.2 部分的事前計算

この問題への解決策として，全ての 2-gram スコ アを事前に計算しておくのではなく，連接表肥大化 の原因となる素性テンプレートの集合 $S$ を予め定 め，事前計算と解析時の計算に分割する. 具体的に は式 (9) でスコアを計算する。

$
\begin{aligned}
\boldsymbol{w}^{\top} \boldsymbol{\phi}_{2}\left(e_{i}, e_{j}\right) & =\sum_{k \notin S} m\left(l_{k}\left(e_{i}\right), r_{k}\left(e_{j}\right)\right) \\
& +\sum_{k \in S} m\left(l_{k}\left(e_{i}\right), r_{k}\left(e_{j}\right)\right)
\end{aligned}
$

ここで，第 1 項は事前に計算する項，第 2 項は解析時に計算する項である.

$S$ が大きいほど解析時に必要な計算が多くなるた め，モデルサイズを効果的に軽量化できる小さい $S$ を定める必要がある. 本研究では $S$ の選び方として 以下の手法を比較する。

Various 生成される素性の種類が多い素性テンプ レートを優先的に選択する。これは，品詞など 種類数の少ない情報よりも，読みなど種類数の 多い情報を含むほうがモデルが複雑化して連接表が大きくなりやすいのではないかという仮説 に基づく.

Greedy 連接表のサイズに大きく影響を与える素性テンプレートを 1 つずつ調べ，貪欲的に選択 していく.

Greedy-2 Greedyでは，相関の強い素性テンプレー 卜など，同時に選択しなければ連接表が軽量化 しない素性テンプレートが選択されない。そこ で，2つの素性テンプレートを同時に選択した 際の連接表のサイズ変化も考慮する。

## 4 ダブル配列を用いたスコア辞書

2-gram スコアを解析時に計算すると，解析速度が 低下すると考えられる．そこで，式 (9) の計算を効

率的に行うために, 関数 $m$ の引数から值へのマッピ ングにダブル配列 [6] を用いることを提案する。

ダブル配列はトライ [7] の効率的な実装であり， 2 つの配列 BASE と CHECK，及び值配列 VALUE に よって構成される key-value マップである. 整数値 $k_{1}, k_{2}, t$ について式 (10) が満たされるとき，キー $\left(k_{1}, k_{2}\right)$ の值が VALUE $[t]$ であると見なす.

$
\operatorname{BASE}\left[k_{1}\right] \oplus k_{2}=t \wedge \operatorname{CHECK}[t]=k_{1}
$

ここで演算子 $\oplus$ は排他的論理和を表す1），ダブル配列を用いると，スコア計算は Algorithm 1 のとおり となる.

ダブル配列は，1) 配列の要素の取得，2) 排他的論理和の計算，3) 比較，という単純な処理によって構成されるため，Algorithm 1 内のループ処理は SIMD 命令 ${ }^{2}$ によって容易に並列化可能である.

## 5 実験

## 5.1 実験設定

モデル学習のためのデータセットとして，現代日本語書き言葉均衡コーパス (BCCWJ [8], Ver. 1.1) のうち，人手で短単位アノテーションされたコア データ $60 \mathrm{k}$ 文を利用した. 辞書には現代書き言葉 UniDic [5] (Ver. 3.1.0)を利用し，各パラメータを再学習した。


図 1 2-gram スコアの事前計算から除外する素性テンプ レートの数と連接表の要素数の関係

ベースラインとして CRF に基づく形態素解析器 である Vibrato ${ }^{3}$ を利用し，提案法は Vibrato を修正 する形で実装した. CRF の学習には rucrf $^{4)}$ を用い， OWL-QN 法 [9] による L1 正則化 [10] を行った.

計算を効率的に行うため，重み，及び統合後のス コアはすべて量子化した．スコアの事前計算では量子化前の值が用いられるが，解析時の計算では量子化後の值が用いられるため，手法によって算出され るスコアが僅かに異なる。しかし，その差は解析結果に大きな影響を与えるものではない.

実装にはプログラミング言語 Rust を用いた。コ ンパイラは rustc 1.65，コンパイルオプションは-C opt-level=3とした.

解析速度の測定には，BCCWJ のコアデータ以外 からランダムに抽出した $100 \mathrm{k}$ 文を利用し，100 回解析した平均值を用いた．測定の際は，分割対象の文 を先に RAM に読み込み，IO 処理にかかる時間は除外した。

実験は以下のスペックのマシンを用いてシングル スレッドで実施した。
- CPU: Intel Core i9-12900K CPU @ 3.2GHz
- Memory: 64GiB RAM (L1: 640KiB, L2: 14MiB)

## 5.2 スコアの部分的事前計算の効果

## 5.2.1 連接表のサイズの変化

解析時に統合する素性テンプレートのインデック ス集合 $S$ のサイズを変化させた際の連接表の要素数 の変化を図 1 に示す.

図を見ると，Greedy または Greedy-2 によって優先的に選択される素性テンプレートのうち，最初の

3) https://github.com/daac-tools/vibrato

4) https://github.com/daac-tools/rucrf
表 1 2-gram モデルサイズ [MiB] と解析時間 [s] の関係

5つの素性テンプレートをスコアの事前計算の対象 から除外するだけで，連接表のサイズが $10 \%$ 程度ま で軽量化することが確認された。一方で，Variousに よって優先的に選択される素性テンプレートを除外 しても，連接表の軽量化効果が殆どないことが確認 された.

この結果から, Greedy または Greedy-2 によって 貪欲的に選択される素性テンプレートを除外するこ とが，連接表の軽量化に有効であることが分かる.

Greedy-2 については，初期の軽量化効果は Greedy と比較して大きいものの，すぐに Greedy と大差が 無くなることが確認された。これは，2つの素性テ ンプレートのみが相関しているケースが少なかっ たためと考えられる。他の素性テンプレートを除外 した場合の影響を考慮する場合，計算量は考慮する 素性テンプレートの数 $n$ に対して指数関数的に増大するため,$n$ を増やすことは現実的ではない.こ のため，以降は単純に大きな軽量化効果を得られる Greedy を採用した。

## 5.2.2 モデルサイズと解析時間の比較

2-gram スコアの事前計算から除外する素性テンプ レートの数を変化させた際の，2-gram モデルサイズ と解析時間への影響を調査するため，以下の 3 つの 状況について測定した。ここにおける 2-gram モデ ルサイズとは，連接表のサイズと 2-gram スコアを 格納したダブル配列のサイズの総和である.

Matrix 全ての 2-gram スコアを事前に計算して連接表に格納する。(ベースライン)

Dual Greedyによって優先的に選択される 8 個の素性テンプレートについて連接表から除外し，解析時に計算を行う.

Raw 全ての 2-gramスコアを解析時に計算し，連接表は利用しない。 $(S=\{1,2, \ldots, K\})$

これらの結果を表 1 に示す. Dualでは，Matrix に 比べて 2-gram モデルサイズが 12\%以下になってい ることを確認できる．スコアの事前計算から除外す る素性テンプレートを増やすと，必然的にダブル配列のサイズは大きくなるが，その増加量は連接表の表 2 SIMDによる解析時間 [s] の変化

軽量化した分に比べれば十分に小さく，モデル全体の軽量化に効果的であることが分かる。一方で， Dual の解析時間は Matrix の 2.4 倍に増加しており,解析時に 2-gram スコアを計算することで解析が遅 くなることが伺える。

ここからモデルサイズと速度はトレードオフの関係であり，インデックス集合 $S$ のサイズは，許容さ れるモデルサイズと解析速度によって調整する必要 があることが分かる.

Raw は Dual と比較して傾向が顕著であり，2-gram モデルサイズは Matrix の $0.5 \%$ である一方，解析時間は Matrix の 23 倍であった.

## 5.3 スコア計算に SIMD を利用する効果

ここでは，解析時の 2-gram スコアの計算を SIMD 並列化することの効果を調査する．5.2.2 節の Dual および Raw の設定について，Algorithm 1 の処理を 8 並列化 ${ }^{5)}$ した場合の解析時間の変化を表 2 に示す.

この結果から，ダブル配列を用いたスコア計算が SIMD 命令によって実際に高速化されたことを確認 できる。ただし，全ての 2-gram スコアを事前計算 して参照する Matrix と比較すると，Dual は SIMD 命令を用いても 2 倍以上遅いことが確認できる。

## 6 まとめ

本稿では，CRF に基づく形態素解析器において， 2-gram スコアの計算を事前計算と解析時の計算に分割することで，モデルサイズを軽量化する手法を提案した. また，解析時の計算を SIMD 命令で高速化 できることを示した。提案法は，パラメータに手を 加えるなど，解析精度に影響を与えることは行わな い。このため，解析精度を維持したまま，組み込み 機器や Web フロントエンドなど，資源が限られた 環境でも利用可能なモデルを配布することが可能と なる。

今回の実験では，事前計算から除外する素性テン プレートを選択する際に，そのテンプレートの内容 までは考慮しなかったが，言語学的な知見を取り入 れることによる効果についても検討の余地がある。

5） AVX2 で 32-bit 演算を並列化できる最大の個数が 8 である.

## 参考文献

[1] Taku Kudo, Kaoru Yamamoto, and Yuji Matsumoto. Applying conditional random fields to Japanese morphological analysis. In Proceedings of the $\mathbf{2 0 0 4}$ Conference on Empirical Methods in Natural Language Processing, pp. 230-237, Barcelona, Spain, July 2004. Association for Computational Linguistics.

[2] Graham Neubig, Yosuke Nakata, and Shinsuke Mori. Pointwise prediction for robust, adaptable Japanese morphological analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 529533, Portland, Oregon, USA, June 2011. Association for Computational Linguistics.

[3] John D. Lafferty, Andrew McCallum, and Fernando C. N. Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the Eighteenth International Conference on Machine Learning, ICML '01, p. 282-289, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc.

[4] Masayuki Asahara and Yuji Matsumoto. ipadic version 2.7.0 User's Manual. https://ja.osdn. net/projects/ ipadic/docs/ipadic-2.7.0-manual-en.pdf, 2003.

[5] 岡照晃. CRF 素性テンプレートの見直しによるモ デルサイズを軽量化した解析用 UniDic — unidiccwj-2.2.0 と unidic-csj-2.2.0 一. 言語資源活用ワーク ショップ 2017 発表予稿集, 143-152.

[6] Jun'ichi Aoe. An efficient digital search algorithm by using a double-array structure. IEEE Transactions on Software Engineering, Vol. 15, No. 9, pp. 1066-1077, 1989.

[7] Edward Fredkin. Trie memory. Commun. ACM, Vol. 3, No. 9, p. 490-499, sep 1960.

[8] 前川喜久雄. 代表性を有する大規模日本語書き言葉 コーパスの構築 (〈特集〉日本語コーパス). 人工知能, Vol. 24, No. 5, pp. 616-622, 2009.

[9] Galen Andrew and Jianfeng Gao. Scalable training of 11regularized log-linear models. In Proceedings of the 24th International Conference on Machine Learning, ICML '07, p. 33-40, New York, NY, USA, 2007. Association for Computing Machinery.

[10] Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), Vol. 58, No. 1, pp. 267-288, 1996.
 赤部晃一 ${ }^{1}$ 神田峻介 1 小田悠介 ${ }^{2}$ ${ }^{1}$ LegalOn Technologies Research ${ }^{2}$ 東北大学 データ駆動科学・AI 教育研究センター \{koichi.akabe, shunsuke.kanda\}@legalontech.jp yusuke.oda.c1@tohoku.ac.jp  