文字列カーネルで遊ぶ - Negative/Positive Thinking

はじめに

ちょっと、高次元特徴空間での2つの文字列の像の内積である文字列カーネルで遊んでみる。
文字列カーネルを類似度として使いたい。遊びなので、数式はちゃんと追ってない、、、

文字列カーネル

文字列に対するカーネル
- カーネルKは、入力空間Xから特徴空間Fへの写像φについて、x,y∈Xに対してK(x,y)=<φ(x),φ(y)>を満たす関数のこと
2つの文字列の距離的なものを考えるのに、共通する部分列や部分文字列を考えたもの
- いろんな考え方ができるので、いろんなものが存在する

部分列と部分文字列の違い

部分列(Subsequence)
- 記号列に対して、「並び」だけを保持した部分的な記号列
- 「abcde」に対して、「abd」や「be」や「bcde」など
- 長さがkの部分列は「k-merの部分列」という
部分文字列(Substring)
- 記号列に対して、「隣接性」と「並び」を保持した部分的な記号列
- 「abcde」に対して、「abc」や「de」など。「abe」などはダメ

文字列カーネルの種類

スペクトルカーネル
- 共通する長さpの部分文字列(文字p-gram)の数を考え、ヒストグラムを比較する
全部分列カーネル
- 文字列のすべての部分列(空文字を含む)で共通する数を考え、ヒストグラムを比較する
固定長部分列カーネル
- 文字列のp-mer部分列で共通する数を考え、ヒストグラムを比較する
ギャップ加重部分列カーネル
- 文字列のp-mer部分列で、すべて同じの重みではなく、隣接性を考慮し、比較する
- 重みλ∈(0,1)を指数的に重みづける
文字加重文字列カーネル
- 文字列の部分文字列について、特定の文字や文字列にそれぞれ重みを考え、比較する
ソフトマッチング文字列カーネル
- 文字間の類似性尺度を考えて、比較する
ギャップ数加重文字列カーネル
- ギャップの長さではなくギャップ数により重み付けし、比較する
など

コード

参考文献の書籍の方を参考に。LCSは比較用。
(書籍の疑似コード怪しい気がする...のでこのコードも怪しいかも...要原論文確認)

追記(2013/04/06):「全部分列カーネル」のdp初期化を0でしていたものを1に修正。

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cmath>

//UTF8の文字列を扱うためのクラス
class utf8_string {
  std::vector<std::string> str;
  int num_byte(const char &cc){
    unsigned char c = static_cast<unsigned char>(cc);
    if(c <= 0x7f) return 1;
    if(0xc0 <= c && c <= 0xcf) return 2;
    if(0xd0 <= c && c <= 0xdf) return 2;
    if(0xe0 <= c && c <= 0xef) return 3;
    if(0xf0 <= c && c <= 0xf7) return 4;
    if(0xf8 <= c && c <= 0xfb) return 5;
    return 6;
  }
  void init_str(const std::string &s){
    for(size_t i=0; i<s.length();){
      int n = num_byte(s[i]);
      str.push_back(s.substr(i,n));
      i += n;
    }
  }
public:
  utf8_string(const std::string &s){ init_str(s); }
  utf8_string(const char *p){
    std::string s(p);
    init_str(s);
  }
  
  size_t length() const { return str.size(); }
  std::string operator[](size_t idx) const {
    return str[idx];
  }
  bool operator==(const utf8_string &s){
    if(length() != s.length()) return false;
    for(size_t i=0; i<length(); i++){
      if(str[i] != s[i]) return false;
    }
    return true;
  }
  std::string substr(size_t begin, size_t len) const {
    std::string ret;
    for(size_t i=begin; i<begin+len; i++){
      ret += str[i];
    }
    return ret;
  }
  std::string operator[](size_t i){
    return str[i];
  }
};


//LCS(最長共通部分列)による類似度
double similarity_LCS(const utf8_string& text1, const utf8_string& text2){
  //dp[i][j] := text1[1..i]とtext2[1..j]でのLCSの長さ
  std::vector< std::vector<int> > dp(text1.length()+1, std::vector<int>(text2.length()+1, 0));
  
  for(size_t i=0; i<text1.length(); i++){
    for(size_t j=0; j<text2.length(); j++){
      if(text1[i] == text2[j]){
        dp[i+1][j+1] = dp[i][j] + 1;
      }else{
        dp[i+1][j+1] = std::max(dp[i][j+1], dp[i+1][j]);
      }
    }
  }

  return 2.0 * dp[text1.length()][text2.length()] / (text1.length() + text2.length());
}

//pスペクトルカーネル(共通の長さpの部分文字列を何個もつか？)による類似度
int kernel_pspectrum(size_t p, const utf8_string& text1, const utf8_string& text2){
  if(text1.length()<p || text2.length()<p) return -1.0;

  std::map<std::string,int> memo;
  int ret = 0;

  for(size_t i=0; i<text1.length()-p+1; i++){
    std::string sub = text1.substr(i,p);
    memo[sub]++;
  }
  for(size_t i=0; i<text2.length()-p+1; i++){
    std::string sub = text2.substr(i,p);
    ret += memo[sub];
  }

  return ret;
}
double similarity_kernel_pspec(size_t p, const utf8_string& text1, const utf8_string& text2){
  //return kernel_pspectrum(p, text1, text2);
  //正規化カーネル
  return kernel_pspectrum(p, text1, text2) / sqrt(kernel_pspectrum(p, text1, text1) * kernel_pspectrum(p, text2, text2));
}

//全部分列カーネルによる類似度
int kernel_allsubseq(const utf8_string& text1, const utf8_string& text2){
  size_t n = text1.length(), m = text2.length();
  std::vector< std::vector<int> > dp(n+1, std::vector<int>(m+1, 1)); //追記：ここを0->1に修正
  std::vector<int> P(m+1, 0);

  for(size_t j=1; j<=m; j++){
    dp[0][j] = 1;
  }
  for(size_t i=1; i<=n; i++){
    size_t last = 0;
    P[0] = 0;
    for(size_t k=1; k<=m; k++){
      P[k] = P[last];
      if(text1[i-1] == text2[k-1]){
        P[k] = P[last] + dp[i-1][k-1];
        last = k;
      }else{
        P[k] = P[last];
      }
    }
    for(size_t k=1; k<=m; k++){
      dp[i][k] = dp[i-1][k] + P[k];
    }
  }

  return dp[n][m];
}
double similarity_kernel_allsubseq(const utf8_string& text1, const utf8_string& text2){
  //return kernel_allsubseq(text1, text2);
  //正規化カーネル
  return kernel_allsubseq(text1, text2) / sqrt(kernel_allsubseq(text1, text1) * kernel_allsubseq(text2, text2));
}

//固定長部分列カーネルによる類似度
int kernel_psubseq(size_t p, const utf8_string& text1, const utf8_string& text2){
  if(text1.length()<p || text2.length()<p) return -1.0;

  size_t n = text1.length(), m = text2.length();
  std::vector< std::vector<int> > dp(n+1, std::vector<int>(m+1, 1)), dprec;
  std::vector<int> P(m+1, 0);

  for(size_t l=1; l<=p; l++){
    dprec = dp;
    for(size_t j=0; j<=m; j++){
      dp[0][j] = 0;
    }
    for(size_t j=0; j<=n; j++){
      dp[j][0] = 0;
    }
    for(size_t i=1; i<=n-p+l; i++){
      size_t last = 0;
      P[0] = 0;
      for(size_t k=1; k<=m; k++){
        if(text1[i-1] == text2[k-1]){
          P[k] = P[last] + dprec[i-1][k-1];
          last = k;
        }else{
          P[k] = P[last];
        }
      }
      for(size_t k=1; k<=m; k++){
        dp[i][k] = dp[i-1][k] + P[k];
      }
    }
  }

  return dp[n][m];
}
double similarity_kernel_psubseq(size_t p, const utf8_string& text1, const utf8_string& text2){
  //return kernel_psubseq(p, text1, text2);
  //正規化カーネル
  return kernel_psubseq(p, text1, text2) / sqrt(kernel_psubseq(p, text1, text1) * kernel_psubseq(p, text2, text2));
}


//ギャップ加重部分列カーネル
double kernel_gapsubseq(double lambda, size_t p, const utf8_string& text1, const utf8_string& text2){
  if(text1.length()<p || text2.length()<p) return -1.0;

  size_t n = text1.length(), m = text2.length();
  std::vector< std::vector<double> > dp(n+1, std::vector<double>(m+1, 0));
  std::vector< std::vector<double> > dps(n, std::vector<double>(m, 0));
  std::vector<double> Kern(p+1,0);

  for(size_t i=0; i<n; i++){
    for(size_t j=0; j<m; j++){
      if(text1[i] == text2[j]){
        dps[i][j] = lambda * lambda;
      }
    }
  }
  for(size_t l=2; l<=p; l++){
    Kern[l] = 0;
    for(size_t i=0; i<n; i++){
      for(size_t j=0; j<m; j++){
        if(!((i==n-1) || (j==m-1))){
          dp[i][j] = dps[i][j];
          if(i>0) dp[i][j] += lambda * dp[i-1][j];
          if(j>0) dp[i][j] += lambda * dp[i][j-1];
          if(i>0 && j>0) dp[i][j] -= lambda * lambda * dp[i-1][j-1];
        }else{
          dp[i][j] = 0;
        }

        if(text1[i] == text2[j]){
          if(i>0 && j>0) dps[i][j] = lambda * lambda * dp[i-1][j-1];
          else dps[i][j] = 0;
          Kern[l] = Kern[l] + dps[i][j];
        }else{
          dps[i][j] = 0;
        }
      }
    }
  }

  return Kern[p];
}
double similarity_kernel_gapsubseq(double lambda, size_t p, const utf8_string& text1, const utf8_string& text2){
  //return kernel_gapsubseq(lambda, p, text1, text2);
  //正規化カーネル
  return kernel_gapsubseq(lambda, p, text1, text2) / sqrt(kernel_gapsubseq(lambda, p, text1, text1) * kernel_gapsubseq(lambda, p, text2, text2));
}

int main(){

  std::string text1, text2;

  std::cin >> text1;
  std::cin >> text2;

  utf8_string t1(text1), t2(text2);
  
  std::cout << "LCS : " << similarity_LCS(t1, t2) << std::endl;

  std::cout << "Pspec(2) : " << similarity_kernel_pspec(2, t1, t2) << std::endl;
  std::cout << "Pspec(3) : " << similarity_kernel_pspec(3, t1, t2) << std::endl;

  std::cout << "AllSubseq : " << similarity_kernel_allsubseq(t1, t2) << std::endl;
  std::cout << "PSubseq(2) : " << similarity_kernel_psubseq(2, t1, t2) << std::endl;
  std::cout << "PSubseq(3) : " << similarity_kernel_psubseq(3, t1, t2) << std::endl;

  std::cout << "GapSubseq(0.5, 3) : " << similarity_kernel_gapsubseq(0.5, 3, t1, t2) << std::endl;

  return 0;
}

結果

今日は晴れ
明日は晴れ
LCS : 0.8
Pspec(2) : 0.75
Pspec(3) : 0.666667
AllSubseq : 0.5
PSubseq(2) : 0.6
PSubseq(3) : 0.4
GapSubseq(0.5, 3) : 0.597015


今日は晴れ
今日の晴れ
LCS : 0.8
Pspec(2) : 0.5
Pspec(3) : 0
AllSubseq : 0.5
PSubseq(2) : 0.6
PSubseq(3) : 0.4
GapSubseq(0.5, 3) : 0.149254


今日の天気
今日の天気は晴れ
LCS : 0.769231
Pspec(2) : 0.755929
Pspec(3) : 0.707107
AllSubseq : 0.353553
PSubseq(2) : 0.597614
PSubseq(3) : 0.422577
GapSubseq(0.5, 3) : 0.664535

なんとも言えないかな。。。
カーネル法による文書分類などでは高次元空間へのマッピングが変わることで分類に役立つけど、類似度の数値(％)として使う話だと、見るだけじゃ判断できなそう。
わかりにくくなるから、LCSやスペクトルカーネル(文字ngramコサイン類似度)あたりでよさそう。。。（◞‸◟）

参考文献

John Shawe-Taylor & Nello Cristianini, カーネル法によるパターン解析
http://www.slideshare.net/abicky/ss-9200313