編集距離で遊ぶ

自然言語処理 プログラミング

はじめに

簡単な例としてよく出てくる「編集距離」を使って、英単語の修正を試してみる。(編集距離が小さいものを列挙するまで)
dpができなすぎるので、「dpやるだけ」って言えるようになりたい。

編集距離とは

  • ある文字列sからある文字列tへ、文字の削除、挿入、置換などの操作をするとき、最小の操作回数(または最小操作コスト)
  • dp[i][j] := s[0..i-1]からt[0..j-1]にするのにかかる最小操作回数(または最小操作コスト)
  • さまざまな変形や拡張が研究されてる
    • 近似文字列照合
許可する操作による違い
  • 編集距離(Levenshtein distance)
    • 挿入、削除、置換
  • Damerau distance
    • 挿入、削除、置換、隣接文字同士の入替
  • Longest common subsequence distance
    • 挿入、削除
  • ハミング距離(Hamming distance)
    • 置換のみ

コード

高速化は何もしてない。いつものごとく適当なコード。

#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <algorithm>

class EditDistance {
  bool ins, del, rep, twi; //許可する操作(挿入、削除、置換、隣接文字同士の入替)
  
public:
  EditDistance(bool ins, bool del, bool rep, bool twi):
    ins(ins), del(del), rep(rep), twi(twi)
  {}
  
  int solve(const std::string& src, const std::string& tgt){
    std::vector< std::vector<int> > D(src.length()+1, std::vector<int>(tgt.length()+1, INT_MAX));
    
    for(int i=0; i<src.length()+1; i++) D[i][0] = i; //srcからすべて削除していけばtgt(=NULL)にできる
    for(int i=0; i<tgt.length()+1; i++) D[0][i] = i; //src(=NULL)にすべて追加していけばtgtにできる

    for(int i=1; i<=src.length(); i++){
      for(int j=1; j<=tgt.length(); j++){
        
        int op_nop = INT_MAX;
        if(src[i-1] == tgt[j-1]){
          op_nop = D[i-1][j-1];
        }
        int op_ins = INT_MAX;
        if(ins && D[i][j-1] != INT_MAX){
          op_ins = D[i][j-1] + 1; //srcに1文字足す事でtgtと同じにした
        }
        int op_del = INT_MAX;
        if(del && D[i-1][j] != INT_MAX){
          op_del = D[i-1][j] + 1; //srcから1文字消すことでtgtと同じにした
        }
        int op_rep = INT_MAX;
        if(rep && D[i-1][j-1] != INT_MAX){
          op_rep = D[i-1][j-1] + 1; //srcの1文字を置換することでtgtと同じにした
        }
        int op_twi = INT_MAX;
        if(twi && i>1 && j>1 && D[i-2][j-2] != INT_MAX){
          if(src[i-1]==tgt[j-2] && src[i-2]==tgt[j-1]){
            op_twi = D[i-2][j-2] + 1; //srcの連続した2文字を入れ替える事でtgtに同じにできる場合、それをしてtgtと同じにした
          }
        }

        D[i][j] = std::min(D[i][j], op_nop);
        D[i][j] = std::min(D[i][j], op_ins);
        D[i][j] = std::min(D[i][j], op_del);
        D[i][j] = std::min(D[i][j], op_rep);
        D[i][j] = std::min(D[i][j], op_twi);
      }
    }
    return D[src.length()][tgt.length()];
  }
};


int main(int argc, char** argv){
  if(argc != 2){
    std::cerr << "Usage : " << argv[0] << " dictionary_file" << std::endl;
    return 1;
  }

  std::ifstream dic_ifs(argv[1]);
  std::vector<std::string> dic;
  std::string word;
  while(dic_ifs >> word) dic.push_back(word);
  
  //編集距離で近い単語を見つける
  EditDistance ed(true, true, true, true); //すべての編集操作を有効

  while(std::cin >> word){
    for(size_t i=0; i<dic.size(); i++){
      int dist = ed.solve(word, dic[i]);
      if(dist <= 2){
        std::cout << "\t" << dist << " " << dic[i] << std::endl;
      }
    }
  }
  return 0;
}

英単語(名詞)リストの準備

試す

$ g++ edit_distance.cc -O2
$ ./a.out noun.dict
doctar
        2 cottar
        2 docker
        1 doctor
        2 dollar
        2 donar
        2 dotard
        2 kotar
        2 lontar
        2 mortar
        2 nectar
        2 octad
        2 ottar
programing
        0 programing
        1 programming
colour
        2 cloud
        2 clout
        2 coleus
        2 collar
        2 colobus
        2 colon
        2 colony
        1 color
        2 colors
        0 colour
        1 colours
        2 colter
        2 contour
        2 cooler
        2 copout
        2 dolor
        1 dolour
        2 flour
        2 honour
        2 odour
        2 valour
        2 velour
disatnce             
        1 distance

候補多すぎ。実用的には、さらに生起確率や前後文脈とか考慮すれば使えそうかも？
キーボードの打ち間違えであれば、ホームポジションからずれて入力した場合とかも考慮したら面白そう。

参考

単語の数学的表現メモ

自然言語処理

はじめに

単語をベクトルや確率分布などの数学的表現で扱いたい場合があったりする。
しかし、「どのようなベクトル・確率分布にすべきか？」などはタスクに依存したりして、自明じゃない。
たくさんあって、派生や新しいものもどんどんでていると思うので、どんなものがあるか調べたかぎりメモ。

One hot表現

  • 各次元が「その単語か否か」を表すベクトルで表現
  • 素性のどれか1つしか1にならなくてスパースネスの問題がでる
  • 未知語はゼロベクトルになってしまう

文字nグラムによる表現

  • 単語の表層から得られる情報を利用
    • 単語に出現している文字nグラムを利用
    • カタカナ語とか有効そう
    • 例: スカイツリー = (「スカ」の出現回数, 「カイ」の出現回数, 「イツ」の出現回数, 「アア」の出現回数, ...) = (1,1,1,0,...)

文脈ベクトル

  • 対象単語の前後/周辺にでてくる単語を利用
    • 例: スカイツリー = (1つ左に「東京」がくる頻度, 1つ右に「クッキー」がくる頻度, ...)
    • 「よく似た共起語分布を持つ単語は、よく似た意味を持つ」という考え
  • 素性(各次元)は、だいたい人手でデザインされる
  • 素性
    • 文脈窓(context window,考慮している範囲)をどのようなものにするか
    • 文脈幅(context window size,考慮している範囲の大きさ)をどの程度にするか
    • 前後の区別
    • 対象単語との相対位置の区別
    • 複数回でてくる単語を区別するか(type,token)
    • 先頭末尾にダミー文字を考慮するか否か
  • 素性値
    • 出現回数
    • 出現するか否か
    • TFIDF
  • 構文情報などを利用

外部の情報を素性に使う

  • ベクトルの各次元(素性)として使える外部の情報はいろいろ考えられる
  • (こういう情報でベクトル表現するのはなんていうんだろう)
    • 品詞,活用形
    • シソーラス情報
    • 辞書の説明文
    • WordNet
    • KnowledgeBase(wikipedia)の情報
      • Explicit Semantic Analysis: 各要素が概念を意味し、単語とそれらとの関連度を値に持つような概念ベクトルが提案されている

Distributional表現

  • (文脈ベクトルとほぼ同じ意味で、)各行が単語w、各列が文脈を表す行列Fで表現
    • 「文脈」を何にするかは文脈ベクトルと同様に検討の必要がある
  • 行列Fの列を次元圧縮して次元dにする(f=g(F)する写像gを考える)ことも検討される
  • 関連表現と次元圧縮
    • 自己組織化セマンティックマップ
    • LSA, LSI, LDA
      • それぞれの結果をさらに単語表現に使うのもありうる(単語の各トピックでの生成確率をベクトルで表現とか)
    • Hyperspace Analogue to Language
    • 独立主成分分析(ICA)
    • Random Projection

確率分布による表現

Brownクラスタリング

  • 単語を階層的クラスタリング(ハードクラスタリング)すると、各階層で単語の集合(クラス)ができる
  • 各単語は、そのクラス情報を使って表現
  • Brown Clustring Model
    • p(w_1, w_2, ..., w_T) = Πe(w_i|C(w_i))*q(C(w_i)|C(w_{i-1}))
      • C(w) : 単語wのクラス番号を返す関数
      • e(w|c) : クラス番号がcの時の単語wの出現しやすさ
      • q(c'|c) : クラス番号cからクラス番号c'への連続のしやすさ
    • Cがどの程度イケてるかをQuality(C)で測る
      • Quality(C) = Σ_c Σ_c' p(c,c') log p(c,c')/(p(c)*p(c')) + Const.
      • p(c,c') : C(w)において、cにつづいてc'が現れる回数の全体での割合
      • p(c) : C(w)において、cが出現する回数の全体での割合
    • アルゴリズム
      • 最初に各単語は別々のクラスタにしておいて、クラスタ数があらかじめ定めたk個になるまでQuality(C)が最大と成る2つのクラスタをマージするのを繰り返す
      • 最初に頻度の多いm単語に別々のクラスタにしておいて、m+1単語目以降は1単語ずつQuality(C)が最大となる2つのクラスタをマージするのを繰り返す

分散表現

  • 単語を表現するベクトルの素性や素性値を機械学習によって学習
    • おおよその場合、低次元で密な実数ベクトルを得る事を目指す
    • 潜在的な特徴(意味的な、統語的な)を学習できる可能性がある(似た単語が似たベクトルを持つ)
  • Word Embeddingsとも呼ばれる
NeuralNetwork, DeepLearning系の言語モデル
  • 言語モデルの枠組みで、各単語をNeuralNetwork内の隠れ層や写像行列を通して変換させるようにして、学習させる
    • 学習された隠れ層や写像行列が各単語の分散表現として使える
    • FeedForward NN, Recurrent NN
      • Recurrentの方は、繰り返し、前の状態を入力するので、単語の周辺情報を広く考慮させる事ができている
    • Hierarchical log-bilinear(HLBL) model
Log-linear, Skip gramモデル

参考

日猫/猫日翻訳を試す

misc. プログラミング

はじめに

先日北海道で行われたNLP2014(Neko Language Processing 2014)で最優秀賞だった「ビットペア法を用いた日本語-猫語翻訳アルゴリズム」を試してみました。

ネコ氏の鳴き声を分析したところ特徴的なパターンが見られ、日本語とネコ語間の変換ルールを明らかにした事で話題になりました。
アルゴリズムは簡単だったので、これを用いて日ニャー/ニャー日翻訳機を作ってみました。

アルゴリズム

論文によると、日本語をビット列にして隣り合うビットのペアを4パターン(ニャ、ニャッ、ニャン、ニャー)の鳴き方にする事で、意思疎通できたそうです。

コード

日本語からネコ語へ変換
#!/usr/bin/perl
use strict;
use warnings;
use Encode;
use utf8;

binmode STDIN, ":utf8";
binmode STDOUT, ":utf8";

sub nichinya {
    my ($text) = @_;

    my $arr = unpack("B*", encode('UTF-8', $text));
    my @bin = split(//, $arr);
    for(my $i=0; $i<@bin; $i+=2){
        if   ($bin[$i] eq '1' && $bin[$i+1] eq '1'){ print "ニャッ"; }
        elsif($bin[$i] eq '1' && $bin[$i+1] eq '0'){ print "ニャン"; }
        elsif($bin[$i] eq '0' && $bin[$i+1] eq '1'){ print "ニャー"; }
        else { print "ニャ"; }
    }
    print "\n";
}

while(<>){
    chomp;
    print "翻訳結果\n";
    nichinya($_);
}
ネコ語から日本語へ変換
#!/usr/bin/perl
use strict;
use warnings;
use Encode;
use utf8;

binmode STDIN, ":utf8";
binmode STDOUT, ":utf8";

sub nyanichi {
    my ($text) = @_;
    
    $text =~ s/ニャッ/11/g;
    $text =~ s/ニャン/10/g;
    $text =~ s/ニャー/01/g;
    $text =~ s/ニャ/00/g;

    my $arr = pack("B*", $text);
    print decode('UTF-8', $arr), "\n";
}

while(<>){
    chomp;
    print "翻訳結果:\n";
    nyanichi($_);
}

結果

# 日本語->猫語
$ perl nichinya.pl
通じてるかにゃ？
翻訳結果:
ニャッニャンニャンニャーニャンニャニャニャニャンニャーニャンニャンニャッニャンニャニャッニャンニャニャニャーニャンニャーニャンニャニャッニャンニャニャッニャンニャニャニャーニャンニャンニャーニャンニャッニャンニャニャッニャンニャニャニャンニャンニャニャンニャッニャッニャンニャニャッニャンニャニャニャーニャンニャニャンニャッニャッニャンニャニャッニャンニャニャニャーニャンニャンニャンニャッニャッニャンニャニャッニャンニャニャニャンニャンニャニャニャッニャッニャンニャッニャッニャンニャッニャッニャニャンニャーニャッニャッ

踏んでください
翻訳結果:
ニャッニャンニャンニャニャンニャッニャンニャニャンニャニャッニャッニャッニャンニャニャッニャンニャニャニャンニャンニャーニャニャッニャッニャンニャニャッニャンニャニャニャーニャンニャンニャーニャッニャッニャンニャニャッニャンニャニャニャーニャンニャニャッニャッニャッニャンニャニャッニャンニャニャニャーニャンニャンニャニャニャッニャンニャニャッニャンニャニャニャーニャンニャーニャーニャーニャッニャンニャニャッニャンニャニャニャーニャンニャニャーニャ

# 猫語->日本語
$ perl nyanichi.pl
ニャッニャンニャンニャーニャンニャニャニャニャンニャーニャンニャンニャッニャンニャニャッニャンニャニャニャーニャンニャーニャンニャニャッニャンニャニャッニャンニャニャニャーニャンニャンニャーニャンニャッニャンニャニャッニャンニャニャニャンニャンニャニャンニャッニャッニャンニャニャッニャンニャニャニャーニャンニャニャンニャッニャッニャンニャニャッニャンニャニャニャーニャンニャンニャンニャッニャッニャンニャニャッニャンニャニャニャンニャンニャニャニャッニャッニャンニャッニャッニャンニャッニャッニャニャンニャーニャッニャッ
翻訳結果:
通じてるかにゃ？

ニャッニャンニャンニャニャンニャンニャーニャッニャンニャンニャーニャンニャッニャンニャニャッニャンニャニャニャンニャンニャニャンニャッニャッニャンニャニャッニャンニャニャニャーニャンニャンニャンニャッニャッニャンニャニャッニャンニャニャニャンニャンニャニャニャッニャッニャンニャッニャッニャンニャッニャッニャニャンニャニャニャー
翻訳結果:
触るにゃ！
　　　　　　　　　　　. ｨ 
._ .......､._　　　 _　／:/l! 
　:~""''.>ﾞ' "~　,､､''‐'､|　　　　　　　　　_ 
ﾞ､'､::::::ﾉ:::::::_,.-=.　 _〜:、 　 　 　 　 ／_.}'':, 
　``､/:::::::::__....,._ `ﾞ'Y' _.ｪ-､....._　／_ﾞ''iﾞﾉ､ﾉ 
　,.--l‐''"~..-_'.x-='"ﾞｰ ､`'-､　,:'　　ﾉﾞﾉﾌﾞ 
"　　 .!-'",／　 `'-‐'') /＼　`/　てﾞノ-〈 
　.-''~　>'ﾞ::　　　 ‐'"ﾞ./　　ヽ.,'　　 ~　／ 
　　 ／/:::::　　　　 　 ',　 　 /　　　 ,:'ﾞ

ニャッニャンニャニャッニャンニャニャニャンニャンニャンニャンニャニャッニャンニャニャッニャンニャニャニャッニャンニャッニャッニャニャッニャンニャニャッニャンニャニャニャッニャンニャーニャーニャッニャッニャンニャニャッニャンニャニャニャッニャンニャンニャンニャンニャッニャンニャニャッニャンニャニャニャッニャンニャンニャンニャッニャッニャンニャニャッニャンニャニャニャッニャンニャーニャーニャーニャッニャンニャニャッニャンニャニャニャッニャンニャッニャッニャニャッニャンニャニャッニャンニャニャニャッニャンニャンニャンニャッニャッニャンニャニャッニャンニャニャニャーニャンニャンニャーニャッニャッニャンニャニャッニャンニャニャニャーニャンニャーニャンニャーニャッニャンニャニャッニャンニャニャニャーニャンニャンニャンニャッニャッニャンニャニャッニャンニャニャニャンニャンニャニャニャッニャニャッニャンニャンニャニャンニャンニャー

ナップサック問題として複数文書要約を解くを試す

自然言語処理 プログラミング

はじめに

複数文書要約をナップサック問題として解く、という話を聴いて、簡単に試せそうなのでやってみる。

手法

西川ら「冗長性制約付きナップサック問題に基づく複数文書要約モデル」
https://www.jstage.jst.go.jp/article/jnlp/20/4/20_585/_pdf

上記の論文中で紹介されている「動的計画ナップサックアルゴリズム」を参考に。
(論文で提案されている手法ではないことに注意)

コード

#include <iostream>
#include <vector>
#include <map>
#include <sstream>


class KPSummary {
  // T[i][k] := 文iまでで最大要約長がkのときの最適解値
  // U[i][k] := 経路復元用(文iを利用したかどうか)
  std::vector< std::vector<int> > T, U;
  int maxN, maxK;

public:
  KPSummary(int maxN, int maxK):
    maxN(maxN),
    maxK(maxK),
    T(maxN+1, std::vector<int>(maxK+1, 0)),
    U(maxN+1, std::vector<int>(maxK+1, 0))
  { }

  std::vector<std::string> summary(
                                   const std::vector<std::string>& text, //文
                                   const std::vector<int>& s, //文の重要度
                                   int K //要約後のテキスト長
                                   )
  {
    //DPtableのサイズで足りない場合は結果なし
    if(text.size() > maxN || K > maxK) return std::vector<std::string>();

    int n = text.size();
    for(int k=0; k<=K; k++) T[0][k] = 0;
    for(int i=1; i<=n; i++){
      for(int k=0; k<=K; k++){
        T[i][k] = T[i-1][k];
        U[i][k] = 0;
      }
      int li = text[i-1].length() + 1; //改行文字含み
      int si = s[i-1];
      for(int k=li; k<=K; k++){
        if(k-li<0) continue;
        if(T[i-1][k-li] + si >= T[i][k]){
          T[i][k] = T[i-1][k-li] + si;
          U[i][k] = 1;
        }
      }
    }

    std::vector<std::string> ret;
    {
      int k = K;
      for(int i=n; i>=1; i--){
        int li = text[i-1].length() + 1; //改行文字含み
        if(U[i][k] == 1){
          ret.push_back(text[i-1]);
          k = k - li;
        }
      }
    }
    std::reverse(ret.begin(), ret.end());
    return ret;
  }
};



std::pair<int, std::string> split(const std::string& str){
  std::pair<int, std::string> ret;

  size_t spi = 0;
  for(int i=0; i<str.length(); i++) if(str[i] == '\t'){ spi = i; break; }
  
  std::stringstream ss(str.substr(0, spi));
  ss >> ret.first;
  ret.second = str.substr(spi+1);

  return ret;
}


int main(){

  KPSummary summary(1000, 1000); //1000文書以下、1000byte以下
  std::vector<std::string> text;
  std::vector<int> s;

  std::string str;
  int weight;
  while(std::getline(std::cin, str)){
    std::pair<int, std::string> sp = split(str);

    s.push_back(sp.first);
    text.push_back(sp.second);
  }

  //500byte以下に要約
  std::vector<std::string> res = summary.summary(text, s, 500);
  for(int i=0; i<res.size(); i++){
    std::cout << res[i] << std::endl;
  }

  return 0;
}

入力

子安さんがプリキュアに出てたのでtwitterで「子安」の検索結果をいくつかピックアップ。
タブ区切りで「RT数\tツイート」形式。

0	寝ぼけながらプリキュア見たらテラ子安だったしそのあと二度寝したしおはようござまし
0	子安
0	子安声でグリだもんね…。(白目)あれ、子安ボイチェン使ってたけど中身はラビのｶｰﾁｬﾝでした！って今思うと結構な力業よな(笑)
0	いきなりファンレターは云々とか言い出して噴いた////オレスキー子安面白すぎ///
0	敵キャラですwwwwwwww 子安は来週も出演しますよー 井上和彦は敵キャラのラスボスに情報を提供する鏡のキャラなので不定期ですがwwwwwww
0	ノリノリやん子安
0	オレスキー子安か……
0	うちの地元に子安ってとこあるな　地名で
0	子安さんまた変な役やってたね(´｀)
0	テラ子安wwwwwwやばいwww
0	プリキュア子安すぎかwwwwwwwwwwwwwww
0	オレスキー子安は改心しそうなキャラだなあ
0	敵幹部に子安ｗｗｗ
0	では、私ももう一個。子安さんはどうです？？
0	プリキュアの敵キャラに子安出てたけどプリキュアに出るのこれで何度目だｗ
0	敵に子安きたああ□&#65038;ほんと子安は良い声だよぉ…
0	子安の塔wwwwwwwwwwwwwwwwwwwww
0	子安の声でなぎさってこの妹の声確実に本名陽子さんだわ
0	子安ボイスの幹部強そう
0	森久保さんの声は、森久保さんって認識すると全てが森久保さんってキャラになる。子安さんの声が子安ってキャラになるのと同じ。
0	子安がイケメン
0	今季のプリキュア、あまり興味もてなかったんだが、なんか変なテンション高い敵がでてきて（cv.子安）少し興味がでてきた（≧∇≦）
0	花粉の予感！てかハピネスに子安さんだって！！やべぇ
276	あなたの子安武人、どこから？
1	子安かわええ
0	今日プリキュア見たら子安出ててわろちw
0	テラ子安ｗｗｗ
0	＿人人 人人＿ ＞ 　子安　 ＜ ￣Y^Y^Y^Y￣
0	プリキュアに子安さんが出てたと聞いて…軍服…か……えっ軍服！！！？
0	子安オン・ステージ
0	子安ｗｗｗｗ
0	子安のじてんでふぁん！
0	声は子安です
0	音だけ聞いてたらプリキュアにディオ出てきたかと思った…焦った…子安さん…？
0	子安いいキャラしてんな
0	プリキュアのレギュラーで出てきそうな敵キャラがテラ子安で、ファンクラブの年会費800円らしいっすよww＼(^o^)／
0	オレスキーさんは子安ｗｗ
0	子安が出てましたwwwwwwww 井上和彦も出演してて 簡単にまとめるとカーズ様の部下がDIOです
0	テラ子安
0	子安！テラ子安！
0	今話題の子安

結果

#ツイートの順番を入れ替えて9個要約を作成
$ for i in {1..9};do cat test.txt| perl -MList::Util=shuffle -e 'print shuffle(<>)'| ./a.out > res.${i}.txt; done
$ wc res*
      15      21     497 res.1.txt
      11      16     498 res.2.txt
      10      13     498 res.3.txt
      12      17     499 res.4.txt
       8      11     499 res.5.txt
      12      15     498 res.6.txt
      10      12     494 res.7.txt
      13      15     500 res.8.txt
      12      15     496 res.9.txt
     103     135    4479 total

$ cat res.1.txt
子安かわええ
テラ子安
あなたの子安武人、どこから？
子安ｗｗｗｗ
子安がイケメン
子安！テラ子安！
いきなりファンレターは云々とか言い出して噴いた////オレスキー子安面白すぎ///
子安ボイスの幹部強そう
テラ子安ｗｗｗ
子安
今話題の子安
子安オン・ステージ
子安さんまた変な役やってたね(´｀)
＿人人 人人＿ ＞ 　子安　 ＜ ￣Y^Y^Y^Y￣
テラ子安wwwwwwやばいwww

$ cat res.2.txt
子安
あなたの子安武人、どこから？
テラ子安
森久保さんの声は、森久保さんって認識すると全てが森久保さんってキャラになる。子安さんの声が子安ってキャラになるのと同じ。
子安かわええ
子安オン・ステージ
今日プリキュア見たら子安出ててわろちw
オレスキー子安は改心しそうなキャラだなあ
子安いいキャラしてんな
子安がイケメン
子安の塔wwwwwwwwwwwwwwwwwwwww

$ cat res.3.txt
あなたの子安武人、どこから？
子安のじてんでふぁん！
今話題の子安
子安いいキャラしてんな
オレスキーさんは子安ｗｗ
声は子安です
子安かわええ
寝ぼけながらプリキュア見たらテラ子安だったしそのあと二度寝したしおはようござまし
子安さんまた変な役やってたね(´｀)
子安が出てましたwwwwwwww 井上和彦も出演してて 簡単にまとめるとカーズ様の部下がDIOです

500byte以下に収まってて、RT数が多いものはちゃんと入ってる。
ただ、重要度sにRT数しかいれていないので、そのツイートがどの程度中身のあることを言っているかは考慮していない。
(ツイートだったら考慮する必要ないかもしれないけど)

EntityLinkingメモ

自然言語処理

はじめに

WSDM2014(WWW2013,YSS2013,SIGIR2013)のチュートリアルで「EntityLinking」といタスクが紹介されていたので、ちょっと調べてメモしておく。
次元圧縮！

Entity Linkingとは

  • テキストに出てくるエンティティ(実体)を識別・決定するタスク
    • 固有名詞抽出は「固有名詞を識別して取り出す」タスクなので、異なる
  • 雑にいうと、KnowledgeBaseと呼ばれる(識別された)エンティティ集合からテキストにでてくるエンティティを決定すること
    • KBにない新しい固有名詞を発見することも含まれたりする(「NIL」として取り扱う)
実際の例
できること
  • セマンティック検索
  • 高度なUI/UX
  • 自動的にKnowledgeBaseとつなげることでドキュメントがよりリッチな情報を持つ
  • インラインアノテーション
  • オントロジー学習
  • 機械学習の素性としての利用
  • 次元削減
  • など
主な問題
  • Name Variation
  • Entity Ambiguity
    • 1つの表記が複数のエンティティの曖昧性を持ってしまっている、複数のKBに対応するものが存在する、など
    • 「木」という表記が「植物の木」「データ構造の木」などのどれに対応するのか
    • →Ranking and Features for Entity Disambiguation
  • Absence
    • 表記に紐づけるべきエンティティがKBにない(NIL,無)
    • →Learning NILs
用語
  • Named Entity Linking(NEL)
    • 固有名詞のEntityLinking。Wikiepdiaの場合、必ずしも固有名詞ではないので注意が必要。
  • Wikify, ウィキ化
    • 既存の記事をWikipediaの一般的なスタイル(リンク入れたりなど)に整える作業
  • Knowledge Base(KB)
    • 知識ベース。エンティティ(実体)を持つ集合・データベースのこと。Wikipedia・DBpediaやFreebaseがよく使われたりする。
    • Wikipediaの場合は、各ページがエンティティに相当する(曖昧性解消ページやカテゴリページなどもあるので注意)

現状の典型的な手法

  • 1. リンクできるフレーズを選ぶ
    • MD, Mention Detection
  • 2. フレーズに紐づけられる、候補となるエンティティをKBからランキング/選択
    • LG, Link Generation
    • (ターゲットとなるエンティティがKB内にないかもしれないことも考慮)
  • 3. コンテキスト情報を使って曖昧性解消/フィルタリング/改善
    • DA, Disambiguation

関連してそうな論文/資料

とりあえず、読んでおきたいものを列挙。後で読む。
(リンク先が信頼できるネットワークかどうかは未確認なので注意)

参考

Counting Bloom Filterを試す

プログラミング

はじめに

悩み多き年頃なので、進捗ダメです。
KVS見てるときに出てきた、次元圧縮っぽさがあるBloom Filterを試してみる。

Bloom Filterとは

  • 「ある要素が集合に含まれるか否か？」を扱えるデータ構造
  • 要素をそのまま保存せず、ハッシュ値にしたものを配列に保存する
  • アルゴリズム
    • サイズがMの配列A[]を用意し、すべて値を0にしておく
    • 要素の追加
    • 要素の検索
      • 追加時と同様にハッシュ値にし、すべて1になっていれば、要素が含まれると判断する
  • 他の組み合わせでも1となってしまう組み合わせがあるために、「間違って要素がある、と判断してしまう可能性」がある＝偽陽性
  • MやKを調整する事で、記憶容量と偽陽性のトレードオフを実現できる
Counting Filter
  • 基本的にBloom Filterのアルゴリズムでは削除ができない
    • 無理矢理行おうとすると、予期せぬ組み合わせで消してしまって偽陰性も出てしまう
  • Bloom Filterの配列において、0/1のビットではなく、カウンタに拡張したもの
  • 追加ではインクリメント、削除では存在を確認してデクリメント、検索では0でないこと、で実現できる

コード

文字列を要素に、Counting Bloom Filterで要素の追加・検索を試してみる。

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

class CountingBloomFilterForString {
  int M; //配列のサイズ
  int N; //現在登録されている数
  std::vector<int> base; //ハッシュ関数のBASE値
  std::vector<int> bit; //保存用の配列

  //ハッシュ関数
  unsigned long long hash(const std::string& str, int b){
    unsigned long long ret = 0;
    for(size_t i=0; i<str.length(); i++){
      ret = ret * b + (char)(str[i]);
    }
    return ret;
  }

public:
  //M : 配列のサイズ
  //h_base : ハッシュ関数のBASE値
  CountingBloomFilterForString(int M, const std::vector<int>& h_base):
    M(M),bit(M,0),base(h_base),N(0)
  {}

  //配列の状態をダンプ
  void dump_bit(){
    int zero = 0, nonzero = 0;
    for(int i=0; i<bit.size(); i++){
      std::cout << bit[i];

      if(bit[i] > 0) nonzero++;
      else zero++;
    }
    std::cout << std::endl;

    std::cout << "zero:    " << zero << std::endl;
    std::cout << "nonzero: " << nonzero << std::endl;
  }

  //要素を追加
  void insert(const std::string& str){
    for(int k=0; k<base.size(); k++){
      unsigned long long h = hash(str, base[k]);
      bit[ h%M ]++;
    }
    N++;
  }

  //要素を削除
  bool remove(const std::string& str){
    if(!find(str)) return false;
    for(int k=0; k<base.size(); k++){
      unsigned long long h = hash(str, base[k]);
      bit[ h%M ]--;
    }    
    return true;
  }

  //要素を検索
  bool find(const std::string& str){
    for(int k=0; k<base.size(); k++){
      unsigned long long h = hash(str, base[k]);
      if(bit[ h%M ] <= 0) return false;
    }    
    return true;
  }

  //find()が間違って「ある」と判定する確率
  double prob_fp(int n){
    int K = base.size();
    return pow(1.0-exp(-K*(double)n/M), K);
  }
};


//乱数
// 注意: 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)) );
}
//適当な文字列を返す
std::string get_random_text(){
  std::string ret = "";
  for(int i=0; i<10; i++){
    ret += 'a' + xor128() % 26;
  }
  return ret;
}


int main(){
  
  int M = 100000; //配列のサイズ
  int N = 10000; //入力文字列の数

  std::vector<int> base; //ハッシュのBASE値
  base.push_back(41);


  CountingBloomFilterForString bf(M, base);

  //ランダムな文字列を生成
  std::vector<std::string> strs;
  for(int i=0; i<(int)(N); i++){
    strs.push_back(get_random_text());
  }

  //生成した文字列を追加
  for(int i=0; i<strs.size(); i++){
    std::cout << strs[i] << std::endl;
    bf.insert(strs[i]);
  }
  
  //追加された状態を表示
  bf.dump_bit();

  //追加した文字列がすべて問題なく入っているか確認
  for(int i=0; i<strs.size(); i++){
    if(bf.find(strs[i]) != true){
      std::cout << "Error" << std::endl;
    }
  }

  //現在のFP率を出力
  std::cout << bf.prob_fp(strs.size()) << std::endl;

  //関係ない文字列を検索してみる
  std::cout << (bf.find("cba123")?"find!":"none") << std::endl;

  return 0;
}

結果

適当な文字列をN個入れたとき、(M,BASE)なBloomFilterの配列(ゼロと非ゼロの個数)、FP率、適当な別の文字列を検索したときの結果、を表示。

  • M=100000, N=10000, BASE=41
...
zero:    90479
nonzero: 9521
0.0951626
none
  • M=100000, N=10000, BASE=41,57
...
zero:    81899
nonzero: 18101
0.0328585
none
  • M=10000, 10000, BASE=41
...
zero:    3657
nonzero: 6343
0.632121
none
  • M=10000, 10000, BASE=41,57
...
zero:    1310
nonzero: 8690
0.747645
none

できてるっぽい。MとKでFP率の変化の仕方が変わる。
ハッシュ関数はどういうのがよいのだろうか。。。

参照

Matrix Factorizationで遊ぶ

機械学習 プログラミング

はじめに

次元削減せずにはいられない。
0の扱いがいまいちピンとこなかったので、ちょっと調べて試してみた。

Matrix Factorizationとは

  • Netflix Prizeという推薦システム・協調フィルタリングのコンテストで良い結果を残した手法
  • 行列Mを、2つの行列P,Qの掛け算で近似するもの
    • 行列Mが与えられたとき、行列Pと行列Qをそれぞれ見つける
    • ユーザー数m、アイテム数nとして、Mはm*n行列。Pはm*k行列。Qはn*k行列。
    • 行列Mには欠損データが含まれている
  • 行列PとQを求めるために次式を最小化する
  • min Σ_{(u,i)∈κ} (M[u][i] - Q_vec[i]*P_vec[u])^2 + λ(|Q_vec[i]|^2 + |P_vec[u]|^2)
    • κは、既知のM[u][i]が存在する(u,i)のペアの集合
  • SGDで解を探す場合は以下の反復式になる
  • e_ui := M[u][i] - Q_vec[i]*P_vec[u]
  • Q_vec[i] ← Q_vec[i] + γ*(e_ui * P_vec[u] - λ*Q_vec[i])
  • P_vec[u] ← P_vec[u] + γ*(e_ui * Q_vec[i] - λ*P_vec[u])

コード

欠損データは0として、学習時には無視する。

#include <iostream>
#include <vector>
#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));
}
//[0,1)の一様乱数
double frand(){
  return xor128()%10000000000/static_cast<double>(10000000000); 
}


//Matrix Factorization
class MF {
  std::vector< std::vector<double> > P, Q;
  int m, n, k;

public:
  MF(int m, int n, int k):
    P(m, std::vector<double>(k, 0)),
    Q(n, std::vector<double>(k, 0)),
    m(m), n(n), k(k)
  {
    for(int u=0; u<m; u++){
      for(int j=0; j<k; j++){
        P[u][j] = frand();
      }
    }
    for(int i=0; i<n; i++){
      for(int j=0; j<k; j++){
        Q[i][j] = frand();
      }
    }
  }

  void calc(const std::vector< std::vector<double> >& r, int ITER = 100000, double gamma = 0.0002, double lambda = 0.02){
    std::vector<double> tmp_p(k), tmp_q(k);

    for(int itr=0; itr<ITER; itr++){
      double e_sum = 0.0;
      for(int u=0; u<m; u++){
        for(int i=0; i<n; i++){
          if(r[u][i] > 0){
            double e = r[u][i];
            for(int j=0; j<k; j++){
              e -= P[u][j] * Q[i][j];
              tmp_q[j] = Q[i][j];
              tmp_p[j] = P[u][j];
            }
            
            e_sum += fabs(e);
            
            for(int j=0; j<k; j++){
              tmp_q[j] += gamma * (e * P[u][j] - lambda * Q[i][j]);
              tmp_p[j] += gamma * (e * Q[i][j] - lambda * P[u][j]);
            }
            
            for(int j=0; j<k; j++){
              Q[i][j] = tmp_q[j];
              P[u][j] = tmp_p[j];
            }
          }
        }
      }
      std::cout << "err : " << e_sum << std::endl;
    }
  }

  double getQP(int u, int i){
    double ret = 0.0;
    for(int j=0; j<k; j++){
      ret += P[u][j] * Q[i][j];
    }
    return ret;
  }
};


int main(){
  int m, n, k;

  std::cin >> m >> n >> k;

  MF mf(m, n, k);
  std::vector< std::vector<double> > mat(m, std::vector<double>(n));

  for(int i=0; i<m; i++){
    for(int j=0; j<n; j++){
      std::cin >> mat[i][j];//欠損データは0(以下)にしておく
    }
  }

  mf.calc(mat);

  for(int i=0; i<m; i++){
    for(int j=0; j<n; j++){
      //推定値[実際の値]
      std::cout << mf.getQP(i, j) << "[" << mat[i][j] << "] ";
    }
    std::cout << std::endl;
  }

  return 0;
}

結果

以下のパターンを試す。

  • 入力
    • m,n,kと行列の要素
5 4 2
5 3 0 1
4 0 0 1
1 1 0 5
1 0 0 4
0 1 5 4
  • 結果
4.95413[5] 2.96558[3] 4.763[0] 1.0043[1] 
3.96507[4] 2.38903[0] 4.01191[0] 1.00021[1] 
1.00855[1] 0.977924[1] 5.78876[0] 4.94156[5] 
0.995749[1] 0.893576[0] 4.78884[0] 3.96817[4] 
1.21817[0] 1.02418[1] 4.97002[5] 3.98115[4]

既知のデータに対しては近似値、欠損値に対しては推定値がちゃんと入っているのでよさそう。
欠損データも学習したら0に近い値でるんじゃないのかと思ってたけど、観測データのみ(欠損データは使わない)でモデル作るらしいですね。


mを文章、nを形態素の有無として、動詞と格助詞の関係性とか名詞の共起関係とか取り出せたら面白そうと思ったけど、いろいろ無理がある・・・

参考

大野の語彙法則を試す

自然言語処理

はじめに

読んでた本に出てきた法則が気になったので、試してみた。

大野の語彙法則

  • 任意の3作品A,B,Cについて、品詞ごとの構成比を計算しておく
  • 名詞の構成比をX_0, x, X_1とし、任意の品詞の構成比をY_0, y, Y_1とする
  • 次の関係式が近似的に成り立つ
    • (y-Y_0) / (Y_1-Y_0) ≒ (x-X_0) / (X_1-X_0)
  • (X_0, Y_0)と(x,y)と(X_1, Y_1)が直線上に並ぶ
原版

試す

作品の準備
品詞の割合の計算
  • mecab＋ipadicを利用
    • 品詞体系がipadicに依存するので、上記法則の形態素の単位として適切かどうかは不明
  • 以下のスクリプトを実行して、集計
#!/usr/bin/perl
# MeCabのperlラッパーのインストールが必要
# Usage : ./countup.pl < テキストファイル
use strict;
use warnings;
use MeCab;

my $mecab = new MeCab::Tagger("");

my %pos_count;
my $cnt = 0;

while(<>){
    chomp;
    my $text = $_;
    
    for(my $n = $mecab->parseToNode($text); $n; $n = $n->{next}){
        my @fts = split(/,/, $n->{feature});
        next if($fts[0] eq "BOS/EOS");

        #print $n->{surface}, "\t", $fts[0], "\n";
        $pos_count{$fts[0]}++;
        $cnt++;
    }
}

print 100 * $pos_count{"名詞"} / $cnt, "\n";
print 100 * $pos_count{"動詞"} / $cnt, "\n";
print 100 * $pos_count{"形容詞"} / $cnt, "\n";
print 100 * $pos_count{"助詞"} / $cnt, "\n";
print 100 * $pos_count{"助動詞"} / $cnt, "\n";

結果

確かに直線上になってるっぽい。("注文"は、ひらがなが多い気がするので、解析ミスってるかも・・・？)
名詞の割合が決まれば、その他の品詞の割合がおおよそ決まるとは。不思議。

ツイート文とかニュース記事とかだとどうなるのかな。

参考

SdAで遊ぶ

機械学習 プログラミング

はじめに

Deepな話で、簡単に試せそうだったStacked Denoising AutoEncoderを試しに遊んでみる。
あんまり詳しく調べていないので、お遊びレベルという感じで・・・

注意:下記では「特徴抽出器」として利用する方法を試しています。通常は事前学習として行い、それを初期値に使い、普通にニューラルネットの学習を行うことを指すと思いますが、下記のような特徴抽出器的使い方もありみたいですね(ref.機械学習プロフェッショナルシリーズ「深層学習」pp.72-74)。

Stacked AutoEncoderとは

  • BengioやVinsentによって提案や紹介
  • AutoEncoderを何層も重ねたもの
  • 各層の学習は、一つ前の隠れ層を入力にAutoEncoderを学習し、出力部分を捨てて次の層を学習する
    • Unsupervised layer-wise pre-training
  • 層の最後の部分でロジスティック回帰などを利用する事で教師あり分類器などを行える

コード

liblinear形式のデータを、学習し、学習したSdA通した後の特徴に変換してliblinear形式で出力まで。
結果をliblinearで学習・評価してみる。

#include <iostream>
#include <vector>
#include <cmath>
#include <fstream>
#include <sstream>
#include <cstdlib>

//行列計算用クラス
class Matrix {
  int m, n;
  std::vector<double> val;

  void splice(int i, int j){
    int N = val.size();
    if(i+(j-1)<N){
      std::vector<double> vl(N-j, 0.0);
      int vl_idx = 0, val_idx = 0;
      while(val_idx<N){
        if(val_idx<i||i+j-1<val_idx){
          vl[vl_idx] = val[val_idx];
          vl_idx++;
        }
        val_idx++;
      }
      val = vl;
    }
  }
  Matrix clone(){
    Matrix ret(m, n);
    for(int i=0; i<m; i++){
      for(int j=0; j<n; j++){
        ret.setVal(i, j, val[n*i+j]);
      }
    }
    return ret;
  }

public:
  Matrix():m(0),n(0){}
  Matrix(int m, int n):m(m),n(n){
    if(m>0 && n>0){
      for(int i=0; i<m*n; i++){
        val.push_back(0.0);
      }
    }
  }
  Matrix(const Matrix& mat){
    m = mat.m;
    n = mat.n;
    val = mat.val;
  }

  int getM() const { return m; }
  int getN() const { return n; }
  double getVal(int i, int j) const { return val[n*i+j]; }
  void setVal(int i, int j, double x){ val[n*i+j] = x; }
  bool isSquare(){ return n==m; }

  Matrix add(const Matrix& mat){
    if(m == mat.m && n == mat.n){
      Matrix ret(m, n);
      for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
          ret.setVal(i, j, val[n*i+j] + mat.getVal(i,j));
        }
      }
      return ret;
    }
    return Matrix(-1, -1);
  }
  Matrix operator+(const Matrix& mat){ return add(mat); }

  Matrix sub(const Matrix& mat){
    if(m == mat.m && n == mat.n){
      Matrix ret(m, n);
      for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
          ret.setVal(i, j, val[n*i+j] - mat.getVal(i,j));
        }
      }
      return ret;
    }
    return Matrix(-1, -1);
  }
  Matrix operator-(const Matrix& mat){ return sub(mat); }

  Matrix prod(const Matrix& mat){
    if(n == 1 && mat.n == 1 && m == mat.m){
      Matrix ret(m, 1);
      for(int i=0; i<m; i++){
        ret.setVal(i, 0, getVal(i, 0) * mat.getVal(i, 0));
      }
      return ret;
    }
    else if(n == mat.m){
      Matrix ret(m, mat.n);
      for(int i=0; i<m; i++){
        for(int j=0; j<mat.n; j++){
          double d = 0.0;
          for(int k=0; k<n; k++){
            d += val[n*i+k] * mat.getVal(k,j);
          }
          ret.setVal(i, j, d);
        }
      }
      return ret;
    }
    return Matrix(-1, -1);
  }
  Matrix operator*(const Matrix& mat){ return prod(mat); }

  void time(double x){
    for(int i=0; i<m; i++){
      for(int j=0; j<n; j++){
        val[n*i+j] *= x;
      }
    }
  }

  Matrix transpose(){
    Matrix ret(n, m);
    for(int i=0; i<m; i++){
      for(int j=0; j<n; j++){
        ret.setVal(j, i, val[n*i+j]);
      }
    }
    return ret;
  }
  
  double cofactor(int i, int j){
    Matrix mat = clone();
    mat.splice(i*mat.n, mat.m);
    mat.m -= 1;
    for(int k=mat.m-1; k>=0; k--){
      mat.splice(k*mat.n+j, 1);
    }
    mat.n -= 1;
    return mat.det() * ( ((i+j+2)%2==0) ? 1 : -1);
  }
  double det(){
    if(isSquare()){
      if(m == 2){
        return val[0]*val[3]-val[1]*val[2];
      }else{
        double d = 0;
        for(int k=0; k<n; k++){
          d += val[k] * cofactor(0, k);
        }
        return d;
      }
    }else{
      return 0.0;
    }
  }
  Matrix cofactorMatrix(){
    Matrix mat(m, n);
    for(int i=0; i<m; i++){
      for(int j=0; j<n; j++){
        mat.setVal(j, i, cofactor(i, j));
      }
    }
    return mat;
  }
  Matrix inverse(){
    if(isSquare()){
      double d = det();
      if(d != 0){
        Matrix mat;
        if(m>2){
          mat = cofactorMatrix();
        } else {
          mat = Matrix(2, 2);
          mat.setVal(0, 0, val[3]);
          mat.setVal(0, 1, -val[1]);
          mat.setVal(1, 0, -val[2]);
          mat.setVal(1, 1, val[0]);
        }
        mat.time(1 / d);
        return mat;
      }
    }else{
      return Matrix(-1, -1);
    }
    return Matrix(-1, -1);
  }
};
std::ostream& operator<<(std::ostream& os, const Matrix& mat){
  for(int i=0; i<mat.getM(); i++){
    for(int j=0; j<mat.getN(); j++){
      os << mat.getVal(i,j) << " ";
    }
    os << std::endl;
  }
  return os;
}



//乱数計算用関数
//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));
}
//[0,1)の一様乱数
// 注意: int(32bit)にしたらint_maxで割ったほうがよい
double frand(){
  return xor128()%10000000000/static_cast<double>(10000000000); 
}


// binary-inputs denoising autoencoder (tied W, W' = W^T)
//  y = sigmoid(W x' + b)
//  z = sigmoid(W' y + b') ~ x
class DenoisingAutoEncoder {
  int num_visible, num_hidden;
  Matrix W, bvis, bhid;
  double p, eps;

  double sigmoid(double x){
    return 1.0 / (1.0 + exp(-x));
  }

public:
  DenoisingAutoEncoder(int num_visible = 1, int num_hidden = 1, double p = 0.0, double eps = 0.0):
    num_visible(num_visible),
    num_hidden(num_hidden),
    W(num_hidden, num_visible),
    bvis(num_visible, 1),
    bhid(num_hidden, 1),
    p(p),
    eps(eps)
  {
    //initial W
    for(int i=0; i<num_hidden; i++){
      for(int j=0; j<num_visible; j++){
        W.setVal(i, j, 1.0 - 2.0 * frand());
      }
    }
  }

  void train(const std::vector<int>& in){
    //make input x
    Matrix x(num_visible, 1);
    for(int i=0; i<in.size(); i++){
      x.setVal(i, 0, in[i]);
    }
    //noise addition
    Matrix noisex(num_visible, 1);
    for(int i=0; i<in.size(); i++){
      double val = in[i];
      if(frand() < p){
        if(val < 0.5) val = 1.0;
        else val = 0.0;
      }
      noisex.setVal(i, 0, val);
    }
    //vector one
    Matrix one(num_hidden, 1);
    for(int i=0; i<num_hidden; i++){
      one.setVal(i, 0, 1.0);
    }
    //make y
    Matrix y = W * noisex + bhid;
    for(int i=0; i<num_hidden; i++){
      y.setVal(i, 0, sigmoid(y.getVal(i, 0)));
    }
    //make z
    Matrix z = W.transpose() * y + bvis;
    for(int i=0; i<num_visible; i++){
      z.setVal(i, 0, sigmoid(z.getVal(i, 0)));
    }

    //make grad bhid
    Matrix gradbhid = W * (x-z) * y * (one-y);
    //make grad bvis
    Matrix gradbvis = x - z;
    //make grad W
    Matrix gradW = (gradbhid * noisex.transpose()) + ((gradbvis * y.transpose()).transpose());

    //update W
    for(int i=0; i<num_hidden; i++){
      for(int j=0; j<num_visible; j++){
        W.setVal(i, j, W.getVal(i, j) + eps * gradW.getVal(i, j));
      }
    }

    //update b
    for(int i=0; i<num_hidden; i++){
      bhid.setVal(i, 0, bhid.getVal(i, 0) + eps * gradbhid.getVal(i, 0));
    }

    //update b'
    for(int i=0; i<num_visible; i++){
      bvis.setVal(i, 0, bvis.getVal(i, 0) + eps * gradbvis.getVal(i, 0));
    }
  }
  
  //隠れ層の値を取得
  std::vector<double> getHiddenValues(const std::vector<int>& in){
    std::vector<double> ret;
    
    //make input x
    Matrix x(num_visible, 1);
    for(int i=0; i<in.size(); i++){
      x.setVal(i, 0, in[i]);
    }
    //make y
    Matrix y = W * x + bhid;
    for(int i=0; i<num_hidden; i++){
      ret.push_back( sigmoid(y.getVal(i, 0)) );
    }
    
    return ret;
  }

  //出力層の値を取得
  std::vector<double> getOutputValues(const std::vector<int>& in){
    std::vector<double> ret;

    //make input x
    Matrix x(num_visible, 1);
    for(int i=0; i<in.size(); i++){
      x.setVal(i, 0, in[i]);
    }
    //make y
    Matrix y = W * x + bhid;
    for(int i=0; i<num_hidden; i++){
      y.setVal(i, 0, sigmoid(y.getVal(i, 0)));
    }
    //make z
    Matrix z = W.transpose() * y + bvis;
    for(int i=0; i<num_visible; i++){
      ret.push_back( sigmoid(z.getVal(i, 0)) );
    }

    return ret;
  }

  //重み行列Wを出力
  void dumpW(){
    std::cout << "Weight W" << std::endl;
    std::cout << W << std::endl;
  }
  //バイアスbとb'を出力
  void dumpb(){
    std::cout << "bhid" << std::endl;
    std::cout << bhid << std::endl;

    std::cout << "bvis" << std::endl;
    std::cout << bvis << std::endl;
  }
};


//SdA
class StackedAutoEncoders {
  int epoch;
  DenoisingAutoEncoder* das[10];
  std::vector<int> hN;

  StackedAutoEncoders(const StackedAutoEncoders&);
public:
  StackedAutoEncoders(int dim_input, const std::vector<int>& hN_input, double noiseP, double eps, int epoch_input):
    hN(hN_input),
    epoch(epoch_input)
  {
    //10層まで
    if(hN.size() > 10) throw "too deep";
    for(int i=0; i<10; i++) das[i] = NULL;

    //各層のDenoisingAutoEncoderを用意する
    for(int i=0; i<hN.size(); i++){
      if(i==0){
        das[i] = new DenoisingAutoEncoder(dim_input, hN[i], noiseP, eps);
      }else{
        das[i] = new DenoisingAutoEncoder(hN[i-1], hN[i], noiseP, eps);
      }
    }   
  }
  ~StackedAutoEncoders(){
    for(int i=0; i<hN.size(); i++){
      if(das[i] != NULL){
        delete das[i];
        das[i] = NULL;
      }
    }
  }

  void train(const std::vector< std::vector<int> >& inputs){
    std::vector< std::vector<int> > now(inputs.size(), std::vector<int>(inputs[0].size()));
    for(int i=0; i<inputs.size(); i++){
      for(int j=0; j<inputs[i].size(); j++){
        now[i][j] = inputs[i][j];
      }
    }

    //greedy & layer-wise pre-training
    for(int d=0; d<hN.size(); d++){
      //層dについて、入力nowで学習する
      for(int t=0; t<epoch; t++){
        std::cout << "epoch" << t << std::endl;
        for(int i=0; i<now.size(); i++){
          std::cout << i << " " << now[i].size() << std::flush;
          das[d]->train(now[i]);
          std::cout << "             \r";
        }
        std::cout << std::endl;

        if(t%10==0){
          //エラー率の確認
          int errSum = 0;
          for(int i=0; i<now.size(); i++){
            std::vector<double> res = das[d]->getOutputValues(now[i]);
            for(int j=0; j<now[i].size(); j++){
              if( now[i][j] != (res[j]>0.5?1:0) ) errSum++;
            }
          }
          std::cout << "layer[" << d << "]" << " : Err = " << (100.0 * errSum / (now.size() * now[0].size())) << "%" << std::endl;
        }

      }
      
      //学習結果から隠れ層を次の入力にする
      for(int i=0; i<now.size(); i++){
        std::vector<double> resH = das[d]->getHiddenValues(now[i]);
        std::vector<int> newIn;
        for(int j=0; j<resH.size(); j++){
          newIn.push_back( (resH[j]>0.5?1:0) ); //01入力のDAEなので、0.5より大きければ1,そうでなければ0と決定的に決めたものを使用する
        }
        now[i] = newIn;
      }
    }
  }

  //SdAを通した後の特徴の出力
  std::vector<int> output(const std::vector<int>& input){
    std::vector<int> res = input;

    for(int d=0; d<hN.size(); d++){
      std::vector<double> resH = das[d]->getHiddenValues(res);
      res.clear();
      for(int j=0; j<resH.size(); j++){
        res.push_back( (resH[j]>0.5?1:0) ); //同上
      }
    }
    return res;
  }

};


int main(){

  std::string trainFilename, testFilename;
  int InputDim, dataNum, Epoch;
  double noiseP, epsilon;
  int hNsize;

  //設定の読み込み
  std::cin >> trainFilename >> testFilename;
  std::cin >> InputDim >> dataNum;
  std::cin >> noiseP >> epsilon >> Epoch;
  std::cin >> hNsize;
  std::vector<int> hN;
  for(int i=0; i<hNsize; i++){
    int tmp;
    std::cin >> tmp;
    hN.push_back(tmp);
  }


  std::ifstream trainfile(trainFilename.c_str());
  std::string line, feat;
  //inputs
  //liblinear形式だけど、素性値は無視して、素性がでているものは1、でていないものは0として利用
  //「+1 1:0 2:1」などでも1:1 2:1として利用するので注意
  std::vector<int> in_y;
  std::vector< std::vector<int> > in(dataNum, std::vector<int>(InputDim, 0));
  for(int i=0; i<dataNum; i++){
    std::getline(trainfile, line);
    int t;
    std::stringstream ss(line);
    ss >> t;
    if(t>0) t = 1;
    else t = 0;
    in_y.push_back(t);

    while(ss >> feat){
      std::string::size_type idx = feat.find(":");
      int id = atoi(feat.substr(0, idx).c_str());
      int value = atoi(feat.substr(idx+1).c_str());

      in[i][id-1] = value;
    }
  }

  //train
  StackedAutoEncoders sae(InputDim, hN, noiseP, epsilon, Epoch);
  sae.train(in);

  //学習データの出力
  std::ofstream trainout((trainFilename + ".sda").c_str());
  for(int i=0; i<dataNum; i++){
    std::vector<int> res = sae.output(in[i]);

    trainout << in_y[i];
    for(int j=0; j<res.size(); j++){
      if(res[j] == 1){
        trainout << " " << j+1 << ":1";
      }
    }
    trainout << std::endl;
  }

  //評価データの出力
  std::ifstream testfile(testFilename.c_str());
  std::ofstream testout((testFilename + ".sda").c_str());
  while(std::getline(testfile, line)){
    int t;
    std::stringstream ss(line);
    ss >> t;
    if(t>0) t = 1;
    else t = 0;
    testout << t;
    
    std::vector<int> tmp(InputDim, 0);
    while(ss >> feat){
      std::string::size_type idx = feat.find(":");
      int id = atoi(feat.substr(0, idx).c_str());
      int value = atoi(feat.substr(idx+1).c_str());

      tmp[id-1] = value;
    }
    std::vector<int> res = sae.output(tmp);
    for(int i=0; i<res.size(); i++){
      if(res[i] == 1){
        testout << " " << i+1 << ":1";
      }
    }
    testout << std::endl;
  }

  return 0;
}

試し

とりあえず、いつも使ってるa9aを利用。
http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/

a9a
  • 設定ファイル
# liblinear形式の学習ファイル liblinear形式のテストファイル
# 素性数 学習ファイルの行数
# ノイズの割合 学習率 各層のIteration回数
# 層の数
# 各層の隠れ層のノード数
# ...
$ cat a9a.test
a9a a9a.t
123 32561
0.1 0.001 50
9
110
100
90
80
70
60
50
40
30
  • 実行
$ g++ -O2 sda.cc
$ ./a.out < a9a.test
...
$ ../liblinear/liblinear-1.93/train -s 0 -c 0.1 a9a.sda
$ ../liblinear/liblinear-1.93/predict a9a.t.sda a9a.sda.model out
Accuracy = 77.8515% (12675/16281)


# 参考
$ ../liblinear/liblinear-1.93/train -s 0 -c 0.1 a9a
$ ../liblinear/liblinear-1.93/predict a9a.t a9a.model out 
Accuracy = 85.0132% (13841/16281)

うあああ、がっつり下がった。。。

けど、123次元→30次元に落とした特徴でも77.8%ぐらい出てるので、まあまあ方向はあっていそうかも。
パラメータ未調整というのはおおいにあるけど、Iteration回数が十分に収束しないのに次の層の学習に進んでいるのでErrorが蓄積してしまっているっぽくも見える。(3層ぐらいだとそんなにAcc落ちずに次元だけ落ちる)
あと、時間結構かかる・・・

a9a(2014/1/16追記)

ちゃんと収束がしてくれる程度にIteration回数を確保＆学習率をちょっと大きめに取ってやってみる。
9層はおおすぎるかなと思うので、5層に減らす。

  • 設定ファイル
a9a a9a.t
123 32561
0.1 0.005 500
5
110
100
90
80
70
  • 実験
$ ../liblinear/liblinear-1.93/predict a9a.t.sda a9a.sda.model out
Accuracy = 84.2884% (13723/16281)

結構Accを落とさず次元減らせた。
いい感じの表現を事前学習できたかも。



画像とかで試した方がよさそうなので、やってみたい。

参考

格メモ

自然言語処理

はじめに

少しずつ曖昧な理解の部分をなくしていきたい。
「格」についてちょっとメモ。

格(case)

  • おおざっぱに言うと、文法的または意味的役割のこと
    • 格の種類を見れば、役割を判断できるような感じ
  • 別の定義では、語と語(名詞と述語)の間に成り立つ意味関係を表すもの
    • 日本語は、典型的には格助詞によって表される(そうでないものもある)
      • 例：「AがBをCに渡す」のA、B、Cなどが何を意味しているか？
  • 「格」は、概念としては曖昧で、細かな基準はあまり定まっていない
    • いろんな人によるいろんな概念定義が存在している
格文法
  • 1968年にフィルモアによって提唱された文法理論
    • 文中に出現する語の意味関係を分析する理論
  • 動詞に注目し、「格」を単語間(主に、動詞と名詞)の意味的な関係を指す、と考えた
格標識
  • 格を決めるための要素の事
  • 日本語などの場合は主として格助詞、など
  • 英語などの場合は、語順や前置詞、など
格フレーム(case frame)
  • 「述語＆格＆格に対応する名詞・意味カテゴリ」の構造・パターンのこと
    • 例えば、「述語:食べる　格:ヒト＋が格、モノ＋を格」のような感じの情報
  • 格フレーム辞書は、格フレーム情報を大量に収録した辞書、データベースのこと

格の種類

表層格(surface case)
  • 位置関係や格助詞などによって表層的に決まる格のこと
  • いくつかの視点で分ける事ができる
    • 主格、目的格などの分類
    • 格助詞による分類
      • が格(「〜が」形式で現れる)
      • を格(「〜を」形式で現れる)
      • に格(「〜に」形式で現れる)
      • から格(「〜から」形式で現れる)
      • へ格(「〜へ」形式で現れる)
      • と格(「〜と」形式で現れる)
      • より格(「〜より」形式で現れる)
      • まで格(「〜まで」形式で現れる)
      • で格(「〜で」形式で現れる)
      • など
深層格(deep case)
  • 表層ではなく、意味的に決まる格のこと
  • 以下のような意味を表す格がある
    • 動作主格(AGENT)
    • 経験者格(EXPERIENCER)
    • 対象格(OBJECT)
    • 道具格(INSTRUMENT)
    • 源泉格(SOURCE)
    • 目標格(GOAL)
    • 場所格(LOCATION)
    • 時間格(TIME)
    • などがあるが、特に厳密に決まっているわけではない
    • 名称を決めず、どのような意味的役割か？で分類した物も
  • また、深層格は表層格と1対1対応するわけではない
表層格・深層格の例

「箸で食べる」「大学で食べる」はそれぞれ「で格」は「箸+で」と「大学+で」だが、
前者の「箸」は道具格で、後者の「大学」は場所格、になるような感じ。

必須格と任意格

  • 必須格
    • 文中に必ず出現しなければいけない格
  • 任意格
    • 必ずしも文中に出現しなくてもよい、省略可能な格

格解析

  • 入力テキストに対して、格構造を解析する事
    • 述語項構造解析、意味役割付与
  • いくつ格を持つか？深層格は何か？
  • アプローチは以下のようなものがある
    • 選択制限による手法
      • 各フレーム辞書の意味標識(意味素)による制約で判断する
    • 用例による手法
      • 格構造付きの用例から類似度の高いものから判断する
    • など
  • 解析器

参考