焼きなまし法で単語分割 - Negative/Positive Thinking

はじめに

オライリーの「入門自然言語処理」に、焼きなまし法を使った教師なし単語分割について書かれていたので、これを試す。

アプローチ

「出現単語数」＋「のべ出現単語数」＋「入力文の文字数(固定)」＝目的関数を最小化
単語の区切り位置を温度によって変化させる(近傍探索)
温度をどんどん冷やしていき、それに伴い、変化させる区切り位置の数を減らす

コード

#include <iostream>
#include <vector>
#include <set>
#include <cmath>

//xorshift
// 注意: longではなくint(32bit)にすべき
unsigned long xor128(){
  static unsigned long x=123456789, y=362436069, z=521288629, w=88675123;
  unsigned long t;
  t=(x^(x<<11));
  x=y; y=z; z=w;
  return w=(w^(w>>19))^(t^(t>>8));
}


class word_segment_by_sa {
  //目的関数 : この値が最小となる区切りを探す
  int evaluate(std::string& text, std::string& segs){
    std::vector<std::string> word = segment(text, segs);
    std::set<std::string> dic;

    for(size_t i=0; i<word.size(); i++){
      dic.insert(word[i]);
    }

    int text_size = word.size(); //出現単語数
    int lexicon_size = 0; //出現単語(uniq)の文字数の和(のべ出現単語数を含む)
    
    std::set<std::string>::iterator itr = dic.begin();
    while(itr != dic.end()){
      lexicon_size += (*itr).length() + 1;
      ++itr;
    }

    return text_size + lexicon_size;
  }

  //区切りフラグをランダムにn回入れ替える
  std::string flip_n(std::string segs, int n){
    for(int i=0; i<n; i++){
      size_t r = xor128()%(segs.length());
      if(segs[r] == '0') segs[r] = '1';
      else segs[r] = '0';
    }
    return segs;
  }

public:
  word_segment_by_sa(){}

  //単語に分割
  std::vector<std::string> segment(const std::string& text, std::string& segs){
    std::vector<std::string> ret;
    size_t last = 0;

    for(size_t i=0; i<segs.length(); i++){
      if(segs[i] == '1'){
	ret.push_back(text.substr(last,i+1-last));
	last = i+1;
      }
    }
    ret.push_back(text.substr(last));

    return ret;
  }

  //目的関数が最小化する区切りを焼きなましで探索
  std::string simulated_annealing(std::string& text, std::string& init_segs, int iter, double cooling_rate){
    double temp = init_segs.size();
    std::string segs = init_segs;

    while(temp > 0.5){
      std::string best_segs = segs;
      int best_score = evaluate(text, segs);
      
      for(size_t i=0; i<iter; i++){
	std::string guess = flip_n(segs, round(temp));
	int score = evaluate(text, guess);
	if(score < best_score){
	  best_score = score;
	  best_segs = guess;
	}
      }
      segs = best_segs;
      temp = temp / cooling_rate;
      
      //デバッグ用
      std::cerr << temp << " : " << best_score << std::endl;
      std::vector<std::string> ret = segment(text, segs);
      for(size_t i=0; i<ret.size(); i++){
	std::cerr << "    " << ret[i] << std::endl;
      }
    }

    return segs;
  }
};


int main(){

  word_segment_by_sa ws;

  std::string text = "doyouseethekittyseethedoggydoyoulikethekittylikethedoggy"; //元のテキスト
  std::string segs = "0000000000000001000000000010000000000000000100000000000";  //テキストの区切り情報

  //最適解の探索
  std::string best_segs = ws.simulated_annealing(text, segs, 10000, 1.2);
  std::vector<std::string> words = ws.segment(text, best_segs);

  //結果の表示
  std::cout << "Best Result ==================" << std::endl;
  for(size_t i=0; i<words.size(); i++){
    std::cout << words[i] << std::endl;
  }
  
  return 0;
}

イテレーションを本に書いてある5000回の2倍まわして、十分な回数をまわす。

結果

45.8333 : 64
    doyouseethekitty
    seethedoggy
    doyoulikethekitty
    likethedoggy
...
0.480452 : 43
    doyou
    see
    thekitty
    see
    thedoggy
    doyou
    like
    thekitty
    like
    thedoggy
Best Result ==================
doyou
see
thekitty
see
thedoggy
doyou
like
thekitty
like
thedoggy

いい感じにわかれた。

参考文献

オライリー, 入門自然言語処理