word_segmentation - shigashiyama/nlp_survey GitHub Wiki
日本語における単語分割は,形態素解析として品詞付与と同時に行うことが多い.非 NN の統計的手法がデファクトスタンダードとなっており,純 NN モデルを用いた研究は僅か.
代表的な日本語形態素解析ツールとして,MeCab (Kudo 2004),kytea (Neubig 2011),JUMAN (Kurohashi 1994)/JUMAN++ (Morita 2015) がある.
ラティスベースの手法とは,辞書 (外部資源または訓練データ中の語彙) を基に単語・品詞対をノードとする単語ラティス ((Kudo 2004) の図参照) を構築し,ラティス中のパスを探索することで単語・品詞の系列を推定する手法.通常,辞書中のエントリだけ考慮するため Viterbi アルゴリズムにより効率的な探索が可能だが,基本的に辞書にある単語の組合せにしか分割できない.
- 概要:MeCab の論文.CRFによるラティスベースの日本語形態素解析手法.2000年前後に提案された HMM や MEMM に基づく手法と比べ,単語分割および単語分割+品詞付与において F値 で2〜5ポイント程度上回ることを示した.
- モデル:CRF
- 素性:単語表層,単語原型,単語活用形,品詞の unigram,bigram,それらの組合せなど
- 外部資源:なし
- 実装:http://taku910.github.io/mecab/
(Morita 2015) Morphological Analysis for Unsegmented Languages using Recurrent Neural Network Language Model, EMNLP, 2015
- 概要:JUMAN++ の論文.統計的モデルと NN モデルを併用した日本語形態素解析手法.単語ラティスに基づくベースモデルに加え,単語列の尤もらしさを評価する RNNLM (Recurrent Neural Network Language Model) を使用し,両者のスコアの重み付き和で単語・品詞列のスコアを計算している.RNNLM を用いることで,単語分割,単語分割+品詞付与両タスクにおいて,F値で0.2~0.6ポイント程度向上している.
- モデル:Soft Confidence-Weighted (ラティスのノードおよびエッジスコアの学習),RNNLM
- 素性:(Kudo 2004) の単語 unigram,bigram,品詞,単語活用形
- 外部資源:JUMAN 辞書および Wikipedia から抽出した単語の辞書 (ラティスの作成);京都大学テキストコーパス,京都大学ウェブ文書リードコーパスの訓練・テストデータ以外の部分 (RNNLM の学習)
- 実装:http://nlp.ist.i.kyoto-u.ac.jp/index.php?JUMAN++
- 概要:単語分割と品詞付与を2段階で解く形態素解析手法.単語分割では文字ごとに独立に単語境界ラベルを推定し,品詞付与では,認識した単語ごとに独立に品詞を推定する (下図).シンプルなモデルながら (Kudo 2004) の CRF 以上の精度を達成している.文中の一部の単語境界のみアノテーションされた部分アノテーションコーパスから学習できることから,ドメイン適応のコストが小さい手法である.
- モデル:ロジスティック回帰
- 素性:文字 n-gram,文字タイプ n-gram,辞書中の単語,辞書中の品詞
- 外部資源:なし
- 実装:http://www.phontron.com/kytea/index-ja.html
- 概要:JWS に NN を適用した数少ない研究.BCCWJ (ClassA) で F値 98.42 で KyTea (Neubig 2011) を上回る.
- モデル:features -> LSTM layer -> linear+softmax layer (下図)
- 素性:文字,文字 n-gram (n=2,3),文字種の embedding;辞書 (訓練データの語彙) に基づく0/1値ベクトル
- 学習:cross entropy loss
- 外部資源:なし
中国語単語分割では,2013年頃から end-to-end の NN モデルを適用したによる研究が盛ん.単語分割手法は,以下の文字ベースの手法と単語ベースの手法に二分できる.
- 文字ベース手法は,文字ごとに単語境界ラベル (Bigin, Inside, End, Single など) に対するスコアの分布を計算する方法.入力文字系列に対してスコアが最大となるラベル系列を Viterbi アルゴリズムにより O(文長^2) で効率的に求めることができる.一方,単語の情報を考慮する方法は自明でない.
- 単語ベース手法は,入力文字系列の先頭から逐次的に単語を決定していく方法.単語の情報を自然に組み込むことができる.一方,効率的な最適解の探索方法がない場合が多く,途中の k-best 解を保持する beam search 探索が用いられることが多いが,beam 幅を増やすと計算コストが増大するトレードオフの関係がある.
リッチな情報を組み込みやすい単語ベース手法に高精度な手法が多いが,パラメータ事前学習の工夫などにより文字ベース手法の方が高精度となることもあり,どちらのタイプの手法が SOTA であるかはデータにより異なる.
代表的な中国語単語分割のツールとして,Stanford Word Segmenter (TSeng 2005) がある.
(Tseng 2005) A conditional random field word segmenter for Sighn bakeoff 2005, Fourth SIGHAN Workshop on Chinese Language Processing, 2005
- 概要:Stanford Chinese Word Segmenter の論文.CRF に基づくモデルで,SIGHAN2005 の closed test (外部資源を使用しない) の4データ中2データにおいて SOTA を達成.
- モデル:linear-chain CRF
- 素性:文字 unigram,文字 bigram,prefix,suffix,単独で単語となる文字
- 外部資源:なし
- 実装:https://nlp.stanford.edu/software/segmenter.shtml
- 概要:中国語単語分割+品詞付与において,素性エンジニアリングの不要な NN に基づく手法を提案.CTB3 の品詞付与において,非 NN の SOTA を超える F値 91.82 を達成.
- モデル:features -> linear layer -> linear+CRF layer (下図)
- 素性:文字の embedding
- 学習:Sentence-level log likelifood;Perceptron-style algorithm
- 事前学習:SENNA で学習した文字 unigram ベクトルを使用
- 外部資源:Sina news (embedding の事前学習)
- 概要:CWS において,長距離の依存関係を考慮した手法として LSTM に基づく手法を提案.Linear layer に入力する LSTM の隠れベクトルのウィンドウはサイズ1 (注目する文字のみ) が最良で,サイズ3に増やた実験では F値 が収束せずサイズ1よりも劣っている.SIGHAN2005 PKU において F値 96.5 で SOTA を達成.ただし,(Cai 2016) によると辞書なしでは 94.8 止まり.
- モデル:features -> LSTM layers -> linear+CRF layer (下図は実験で最良であった2層 LSTM に基づくモデル)
- 素性:文字,文字 bigram の embedding
- 学習:max-margin loss
- 事前学習:word2vec で学習した文字 unigram ベクトルを使用.文字 bigram は unigram の平均で初期化.
- 外部資源:Chinese Wikipedia (embedding の事前学習);イディオム辞書 (構築方法不明,文字列を置換する前処理)
(Chen 2017a) A Feature-Enriched Neural Model for Joint Chinese Word Segmentation and Part-of-Speech Tagging, IJCAI, 2017
- 概要:中国語単語分割+品詞付与の結合タスクに対し,CNN と LSTM を併用したリッチな素性に基づく手法を適用.SIGHAN2008 CTB において CNN+Highway+BLSTM が F値90.39 で最良 (BLSTM のみ 89.63,CNN のみ 88.70,CNN+Highway のみ 90.24).
- モデル:features -> CNN / Highwey layer -> BiLSTM layer -> linear+CRF layer (下図)
- 素性:文字,文字 bigram の embedding
- 学習:max-margin loss
- 事前学習:word2vec で学習した文字 unigram ベクトルを使用.文字 bigram は unigram の平均で初期化.
- 外部資源:なし (embedding の事前学習には各データの訓練データを使用)
- マルチタスク:単語分割+品詞付与 (結合ラベル:両タスクのラベルを結合したラベルを予測)
- 概要:CWS において,単語の情報を組み込んだ文字ベースモデルを提案.単語の DAG を構築し,該当文字を含む長さの異なる複数の単語に対応する複数の忘却ゲート,セルを有する DAG-LSTM を提案し,通常の (Bi-)LSTM を超える精度を確認.訓練データ中の単語を一定確率で未知語とみなす dropout も提案し有効性を示している. DAG-LSTM
- モデル
- features -> Bi-LSTM or Bi-DAG-LSTM -> CRF layer
- 訓練データの語彙を基に,文ごとに可能な単語の遷移を列挙した DAG (Directed Acyclic Graph) を構築 (下図).DAG を利用し,注目する文字を終端/先頭とする複数の単語の embedding に対応する複数の忘却ゲート,セルを有する DAG-LSTM を提案
- 素性:文字,文字 bigram (-1:0, 0:1 両方) の embedding
- 学習:max-margin loss
- 事前学習:word2vec で学習した embedding ((Chen 2015) と同様に文字と文字 bigram?)
- 外部資源:Chinese Wikipedia (embedding の事前学習)
- その他:一定確率で単語に を割り当てる In-vocabulary (IV) word dropout を使用
(Shao 2017) Character-based Joint Segmentation and POS Tagging for Chinese using Bidirectional RNN-CRF, arXiv, 2017
- 概要:中国語単語分割+品詞付与の結合タスクに対し,文字 n-gram に加えて部首,文字画像の素性を用いた手法を適用.部首素性,画像素性ともデータにより精度向上と低下の両方のケースがあったが,悪影響が小さく計算コストの小さい部首素性が最終的に使われている.CTB5 での単語分割+品詞付与において F値94.38 (ensemble 4 models) で SOTA.
- モデル: features -> BiGRU layer -> CRF layer (下図)
- 素性:文字,文字 n-gram (n=2~5),部首の embedding;CNN による文字画像素性
- 学習:言及なし (sentence-level log likelifood?)
- 事前学習:GloVe で学習した文字 unigram ベクトルを使用
- 外部資源:Wikipedia,Sogou News Corpora (embedding の事前学習)
- マルチタスク:単語分割+品詞付与 (結合ラベル)
- その他:複数モデルのスコアを平均した ensemble decoding を使用
- 実装:https://github.com/yanshao9798/tagger
- 概要:CWS において,skip-gram よりも複雑な文字 embedding の事前学習方法を提案し,精度向上.パラメータの各種事前学習方法を比較し,「baseline (事前学習なし) ≒ self-training < tri-training (他モデルの自動分割データで事前学習) ≒ skip-gram < WCC embedding」という結果を得ている.CTB6 において F値 96.2,SIGHAN2005 MSR において F値 97.8 でともに SOTA.
- モデル
- Baseline:features -> linear layer -> BLSTM layer -> linear layer (下図)
- Word-context character (WCC) embedding:negative-sampling を用いて,文字から周辺文字とそれらのラベルを予測するタスクを解き,文脈中の位置ごとに異なる文字 embedding matrix (E_{-k}, ..., E_k) を学習.Bigram embedding も同様に学習
- 素性:文字,文字 bigram の embedding
- 学習:言及なし
- 事前学習:文字,文字 bigram ベクトルを skip-gram または WCC で学習.また,ZPar,ICTCLAS で自動分割したデータでパラメータを tri-training
- 外部資源:Chinese Gigaword,Zhuxian (free Internet novel)
- 実装: https://github.com/zhouh/WCC-Segmentation
- 概要:CWS と 英語 NERにおいて,NN に基づく Semi-CRF モデルを提案.Semi-CRF では,系列を最大長さ以下の segment の集合に分割し,系列のスコアを segment のスコアの和で定義する (ラベルの遷移は考慮しない).unit の表現ベクトルから segment の表現ベクトルを得る方法として,RNN,CNN,結合を用いた手法3種類を比較 (それぞれSRNN,SCNN,SCONCATE) し,SRNN と SCONCAT の有効性を確認.
- モデル:Neural Semi-CRF.
- unit embedding -> linear layer -> BiLSTM layer -> linear layer -> unit representation
- unit representation -> SComp (SRNN, SCNN or SCONCATE) -> segment representation (下図)
- Segment representation ○ Segment embedding ○ label embedding -> linear layer -> Semi-CRF layer
- 素性
- unit embedding (w/ and w/o fine tuning),segment embedding,label embedding
- CWS では unit=char,segment=word;NER では unit=word,segment=NE
- 学習:negative log-likelifood
- 事前学習:(Ling 2015) https://github.com/wlin12/wang2vec で学習したunit embedding,segment embeddingを使用.segment emebdding の学習には,離散素性に基づく CRF で自動分割したデータを利用.
- 外部資源:CWS では Chinese Gigaword,NER では RCV1 を embedding の事前学習に使用
- 概要:CWS において,最大単語長以内の単語候補を動的に生成しながら単語列候補のスコアを計算していく単語ベース手法を提案.文字から単語の表現ベクトルを得るため,Reset gate と update gate を持つ GCNN を提案し,linear layer と比べた有効性を確認.
- モデル:NN で単語スコア,リンクスコアを計算し,スコア最大の系列をデコード.ただし,単語の予測が決定的なため beamsearch で複数候補を保持
- 単語スコア:WE -> weight vector (内積)
- リンクスコア:WE -> LSTM layer -> linear layer -> weight vector (内積)
- 素性:character embedding -> GCNN (Gated Combination NN) -> word embedding
- 学習/デコード:max-margin loss / beamsearch
- 事前学習:word2vec で学習した文字 unigram ベクトルを使用
- 外部資源:Chinese Wikipedia (embedding の事前学習)
- 実装:https://github.com/jcyk/CWS (TensorFlow)
- 概要:CWS において,文字ごとに separate (SEP)/append (APP) を予測して決定的に単語を予測していく transition-based 手法を提案.入力文字列,認識済み単語列,action history の素性のうち,単語が最も精度に寄与することを確認.
- モデル:features -> linear layer -> SEP/APP weight vector (内積)
- 素性
- 入力文字列:uni+bigram character embedding -> linear layer -> BiLSTM layer
- 認識済み単語列: word embedding -> linear layer -> LSTM layer
- action (SEP/APP) 列: action embedding -> linear layer -> LSTM
- (Zhang and Clark 2011) の離散素性
- 事前学習:word2vec で学習した文字 unigram ベクトルを使用 文字 bi-gram
- 外部資源:Chinese Gigaword (embedding の事前学習)
- 学習/デコード:max-margin loss / beamsearch
- その他:訓練データの出現頻度1の単語をランダムに未知語扱い
- 実装:https://github.com/SUTDNLP/NNTransitionSegmentor
- to be written
- 概要:CWS において,文字ごとに separate/append を予測して決定的に単語を予測していく transition-based 手法を提案.生テキストを活用し,文字 embedding に関する4種類の事前学習を併用し精度向上.SIGHAN2005 PKU (F値 96.3),AS (95.7),CityU (96.9) において SOTA.
- モデル:features -> linear layers
- 素性
- 入力文字列: uni+bigram character embedding -> 5-window MLP and/or Bi-LSTM
- 部分単語:uni+bigram character embedding (-1,0) ○ 単語長さ embedding -> linear layer
- 認識済み単語: word embedding (-2,-1) -> linear layer
- 学習/デコード:max-margin loss / beamsearch
- 事前学習:5-window character を入力とする MLP により,文字 embedding の4種の事前学習を実施
- Punctuation: 入力5文字の2,3文字目間に括弧があるかを予測
- Automatically segmented text:自動分割データ (Stanford segmenter,ZPar の一致分) で入力文字の単語境界ラベル (B/M/E/S) を予測
- Heterogeneous training data: 分割基準の異なる複数の treebank で入力文字の単語境界ラベル (B/M/E/S) を予測
- POS data:文字の品詞ラベルを予測
- 外部資源:Chinese Gigaword (Punc,Auto),People's Daily corpus (Hetero,POS)
- 実装:https://github.com/jiesutd/RichWordSegmentor
- S. Kurohashi, Improvements of Japanese morphological analyzer JUMAN, Proceedings of the Workshop on Sharable Natural Language Resources, 1994
- T. Kudo et al., Applying Conditional Random Fields to Japanese Morphological Analysis, EMNLP, 2004, http://www.aclweb.org/anthology/W/W04/W04-3230.pdf
- G. Neubig et al., Pointwise prediction for robust, adaptable Japanese morphological analysis, HLT, 2011, http://aclweb.org/anthology/P/P11/P11-2093.pdf
- H. Morita et al., Morphological Analysis for Unsegmented Languages using Recurrent Neural Network Language Model, EMNLP, 2015, http://aclweb.org/anthology/D15-1276
- Y. Kitagawa and M. Komachi, Long Short-Term Memory for Japanese Word Segmentation, arXiv, 2017, https://arxiv.org/pdf/1709.08011.pdf
- H. Tseng et al., A conditional random field word segmenter for SIGHAN bakeoff 2005, Fourth SIGHAN Workshop on Chinese Language Processing, 2005, http://www.aclweb.org/anthology/I/I05/I05-3027.pdf
- X. Zheng et al., Deep Learning for Chinese Word Segmentation and POS Tagging, EMNLP, 2013, http://aclweb.org/anthology/D/D13/D13-1061.pdf
- X. Chen et al., Long Short-Term Memory Neural Networks for Chinese Word Segmentation, EMNLP, 2015, http://aclweb.org/anthology/D15-1141
- X. Chen et al., A Feature-Enriched Neural Model for Joint Chinese Word Segmentation and Part-of-Speech Tagging, IJCAI, 2017, https://www.ijcai.org/proceedings/2017/0553.pdf
- Y. Shao et al., Character-based Joint Segmentation and POS Tagging for Chinese using Bidirectional RNN-CRF, arXiv, 2017, https://arxiv.org/pdf/1704.01314.pdf
- X. Chen et al., DAG-based Long Short-Term Memory for Neural Word Segmentation, arXiv, 2017, https://arxiv.org/pdf/1707.00248.pdf
- H. Zhou et al., Word-Context Character Embeddings for Chinese Word Segmentation, EMNLP, 2017, http://aclweb.org/anthology/D17-1080
- Y. Liu et al., Exploring segment representations for neural segmentation models, IJCAI, 2016, https://www.ijcai.org/Proceedings/16/Papers/409.pdf
- D. Cai and H. Zhao, Neural Word Segmentation Learning for Chinese, ACL, 2016, http://aclweb.org/anthology/P16-1039
- M. Zhang et al., Transition-Based Neural Word Segmentation, ACL, 2016
- J. Yang et al., Neural Word Segmentation with Rich Pretraining, ACL, 2017, http://aclweb.org/anthology/P/P17/P17-1078.pdf
- S. Kurita et al., Neural joint model for transition-based chinese syntactic analysis, ACL, 2017, http://www.aclweb.org/anthology/P17-1111
- W. Ling et al., Two/too simple adaptations of word2vec for syntax problems, NAACL, 2015, http://www.cs.cmu.edu/~lingwang/papers/naacl2015.pdf