概要

KyTeaのソースのわかち書きの部分だけ読んだ時に残したメモ書き。読み推定やtrain関連はまだ見ていない。憶測で書いてるとこが多々あるのでいろいろ間違ってそう。

文中に出てくる計算途中のスコアはKyTea同梱のモデルを使ったもの。

train関連のメモはこちら

@CretedDate 2012/07/12
@Env KyTea0.4.2

src/api/api-example.cpp

わかりやすいところでapi-example.cppから読み始めてみる。このソースは名前の通り、APIを使う際のサンプルコードで、形態素解析をしてその結果を出力するだけの簡易な処理を実行している。

このソースでは、まず、Kyteaクラス(kytea.cpp)のインスタンスを生成している。Kyteaクラスには形態素解析とか学習とかを実行する部分のコードが書かれている。

次にKytea::readModelを呼び出してファイルからモデルをロードしている。

Kytea kytea;

// モデルのロード
kytea.readModel("../../data/model.bin");

KyteaSentenceというクラスに、解析したい文字列を設定し、Kytea::calculateWSを呼び出す。calculateWSを実行すると、KyteaSentence(文章)が分割されて、わかち書きされたKyteaWord(単語)のvecotrが生成される。

その後、各KyteaWordに対して、Kytea::calculateTagsを呼び出し、タグ情報を付加している。わかち書きするだけで読み推定もしないならここは実行しなくても良い。

// 解析する文字列をKyteaSentenceに設定
KyteaString surface_string = util->mapString("これはテストです。");
KyteaSentence sentence(surface_string, util->normalize(surface_string));

// SentenceをWordに分割
kytea.calculateWS(sentence);

// 各Wordにタグ情報を付加する
for (int i = 0; i < config->getNumTags(); i++)
    kytea.calculateTags(sentence, i);

あとは生成されたWordとかタグ情報を標準出力して終了。

重要なのはわかち書きを実行しているcalculateWSだと思われる。次はそこを追ってみる。

Kytea::calculateWS

calculateWSはKyteaSentenceを引数に取って、各文字にスコアを割り振り、スコアから文字の連結を予測し、文章をWordに分割している。

行われているスコア計算は、3種類。

文字タイプは、KANJI、KATAKANA、HIRAGANA、ROMAJI、DIGIT、OTHERの6種類が用意されている。カタカナ同士はくっつきやすいよねとか、ひらがな同士はそうでもないよねとか、そういう感じのスコアになる。

これらの処理は、FeatureLookupクラスで行われる。その辺りの処理を追うのは後回しにして、まずは各処理でどうスコア付けされるのかを見てみる。 試しに下記のような文字を分析して、スコアの変遷を見てみる。

KyTeaで解析する
# 解析前
K:472 y:472 T:472 e:472 a:472 で:472 解:472 析:472 す:472

# Ngramのスコア付け後
K:-3413 y:14173 T:-6770 e:-4798 a:2896 で:8766 解:-15316 析:28063 す:-25664

# 文字タイプのスコア付け後
K:-10754 y:5150 T:-16636 e:-16691 a:26320 で:27369 解:-22314 析:39994 す:-17099

# 辞書のスコア付け後
K:-10859 y:5045 T:-16741 e:-16796 a:25861 で:28232 解:-25081 析:41890 す:-21700

# 出たスコアをmultiplier(デフォルトだと0.000489371?)を掛ける
K:-5.31408 y:2.46888 T:-8.19256 e:-8.21947 a:12.6556 で:13.8159 解:-12.2739 析:20.4997 す-10.6193

# 解析結果
Ky | Tea | で | 解析 | する

こんな感じで、それぞれの解析結果のスコアが加算されていき、KyteaConfig::getConfidence(デフォルトは0.0)以下のスコアが振られた文字は、次の文字と連結する。

上の例では、Kは0.0以下だから次の文字と連結、yは0.0以上だから連結しない、となる。

試しにconfidenceの値を3.0にしてみたところ、y:2.46888が連結対象となり、結果が「KyTea | で | 解析 | する」となった。

実際のコードでは、下記のように3つの関数を通しつつスコアを加算している。

FeatureLookup * featLookup = wsModel_->getFeatureLookup();

// スコアを入れるvectorを用意する
vector<FeatSum> scores(sent.norm.length()-1, featLookup->getBias(0));

// Ngramのスコアを付ける
featLookup->addNgramScores(featLookup->getCharDict(),
                           sent.norm, config_->getCharWindow(),
                           scores);

// 文字タイプのNgramのスコアを付ける
featLookup->addNgramScores(featLookup->getTypeDict(), 
                           util_->mapString(util_->getTypeString(sent.norm)), 
                           config_->getTypeWindow(), scores);

// 辞書のスコアを付ける
if(featLookup->getDictVector())
    featLookup->addDictionaryScores(
        dict_->match(sent.norm),
        dict_->getNumDicts(), config_->getDictionaryN(),
        scores);

1つ目の処理は、addNgramScoresに対して、文字列とngram用の辞書を渡している。

2つ目の処理は、addNgramScoresに対して、文字列を文字タイプに変換した値と文字タイプ用の辞書を渡している。

3つ目の処理は、addDictionaryScoresという関数を呼び出している。

なので、FeatureLookupaddNgramScoresaddDictionaryScoresの2つを見れば、なんとなくスコアの計算についても分かるはず。

このあたりの処理は、こちらの論文とかこちらの論文あたりに説明が載っている。

FeatureLookup::addNgramScores

やってることはngramのスコアを取ってきて足し合わせること。上の論文に書いてあるのと一緒だけど、Window Sizeのデフォルトは3になっている。

つまり、前後3つの文字を見て、スコアを計算することになる。

featLookup->getCharDict()->match()に文字列を渡すと、スコアが返ってくる。

単純な例として「ああああああ」という6文字を渡すと、下記のようなニ次元配列っぽい形で結果が返ってくる。

    -73     -407     -945    -2053     -126      930
      0        0    -1725     8482        0        0
    -73     -407     -945    -2053     -126      930
      0        0        0    -1976        0        0
      0        0    -1725     8482        0        0
    -73     -407     -945    -2053     -126      930
      0        0        0    -1976        0        0
      0        0    -1725     8482        0        0
    -73     -407     -945    -2053     -126      930
      0        0        0    -1976        0        0
      0        0    -1725     8482        0        0
    -73     -407     -945    -2053     -126      930
      0        0        0    -1976        0        0
      0        0    -1725     8482        0        0
    -73     -407     -945    -2053     -126      930

を足し合わせると1文字目の「あ」が連結するスコアに、を足し合わせると2文字目の「あ」が連結するスコアになる。それ以外の部分はスコアとは無関係。

結果、スコアは-4259 4097 3051 3124 3531となり、わかち書きの結果は「ああ | あ | あ | あ | あ」となる。1文字目以外で出現する8482が効いてるね。

それぞれ、unigram、bigram、trigramのスコアに対して、ポジションごとのスコアを加算しているものと思われる。

だとすると、「あ」という文字は単体だと-2053、「あ - あ」は-1725だけど、「ああ - あ」の連結に対しては8482、ということだろうか。(未調査)

とりあえず、featLookup->getCharDict()で取れる辞書の中には、こんな感じのngramの情報が詰まっていて、そこからスコアを計算しているらしい。

文字タイプ(KANJI, HIRAGANA, KATAKANA等)を利用する場合も、辞書が変わるだけで処理自体は同じ。

このスコアはモデルファイルから読み込んでいるわけだけど、じゃ、そのモデルファイルはどうやって作られたかというところはtrain編で。

FeatureLookup::addDictionaryScores

addDictionaryScoresは、辞書のスコアを足し合わせる。

機構自体は上のaddNgramScoresとそれほど大きくは変わらない。但し、足し方が少し変わる。

試しに「今日子」という言葉を解析してみる。この言葉は「今日子」「今日」「今」「日」「子」などが辞書登録されているはず。

事前情報として、addDictionaryScoresをかける前の段階(Ngramだけでスコアを出した状態)では、スコアは「-11566 6946」になっている。「今 - 日」は連接しやすいけど、「日 - 子」が連接することは珍しいので、Ngramのスコアでは「今日 | 子」となる。

辞書情報を適用すると、これが「-15723 -5699」となり「日 - 子」も連接されることになる。

「日 - 子」の連接部分が辞書の影響によって-12648減になっているわけだけど、これはどういった計算になっているか。

とりあえずどういった単語が辞書から取れているか見てみる。

const Dictionary<ModelTagEntry>::MatchResult & matches = dict_->match(sent.norm);
for (int i = 0; i < (int) matches.size(); i++) {
    ModelTagEntry* myEntry = matches[i].second;
    std::cout << "entry : " << util_->showString(myEntry->word) << std::endl;
}

実行結果

entry : 今
entry : 今日
entry : 日
entry : 今日子
entry : 日子
entry : 子

日子という単語もいるんだ。

次にFeatureLookup::addDictionaryScoresの中で、有効になる(onが1になる)辞書スコアを設定している箇所で、その内容を出力してみると、こんな風になった。

word    pos    di  idx  score  スコア対象
今      right   0    2   -644  今-日
今      right   1   26   -369  今-日
今      right   4   98    114  今-日
今日    middle  4  100  -2881  今-日
今日    right   4  113  -1080  日-子
日      left    0    0   -544  今-日
日      right   0   14   -644  日-子
日      left    4   96   -219  今-日
日      right   4  110    114  日-子
今日子  middle  0    7   -973  今-日
今日子  middle  0   19   -973  日-子
今日子  middle  4  103  -4218  今-日
今日子  middle  4  115  -4218  日-子
日子    left    0    3    281  今-日
日子    middle  0   16   -612  日-子
日子    left    1   27   4018  今-日
日子    middle  1   40  -3748  日-子
日子    left    4   99   1278  今-日
日子    middle  4  112  -2881  日-子
子      left    0   12   -544  日-子
子      left    4  108   -219  日-子

まず、各単語に対してleft/right/middleというステートがある。それぞれ、辞書の単語に対して、左隣にいる、右隣にいる、単語内にいることを表す。

たとえば「日子」という単語は、「日-子」の連接には-612-3748-2881=−7241のスコアになるが、その左側の文字の連接に対しては281+4018+1278=5577となる。

辞書にある言葉同士がぶつかった場合、自身をマイナス、お隣さんをプラスにすることで、よりありがちな言葉が勝つようになっているっぽい。

ところで「di」ってなんだろ。自作の単純な辞書を使った場合は、di=0しか出現しなかったのだけど。この点、未調査。

KyteaStringについて

冒頭で出てきてすっ飛ばしていた、KyteaStringというクラスについて。

// 解析する文字列をKyteaSentenceに設定
KyteaString surface_string = util->mapString("もじれつ");

これは文字をいい感じにマッピングして扱うものらしい。文字情報は1文字ごとにshortで持つようになっている。

たとえば、abcはこんな感じに変換される。

a : 7085
b : 833
c : 7086

あいうえおはこんな感じ。

あ : 31
い : 57
う : 18
え : 27
お : 39

マッピングのルールは詳しく見てない。文字列はStringUtil::mapStringでマッピングされ、StringUtil::showStringで文字列に戻る。

StringUtil::Normailzeを使うと、アルファベットや記号の半角全角の違いが吸収された状態でマッピングされる。