Denso IT Laboratory に技術ブログができました。

本日より Denso IT Laboratory に技術ブログができました。 僕も早速初投稿です。 といっても勉強がてら自分用にメモした言語モデルのまとめスライドへの slideshare のリンクを張っただけですが。

google sparse_hashmap を使ってみる

自作のハッシュにバグがあるのだけど、作り直している余裕も時間もないため、google sparse_hash_map を使うことにした。 決め手は自分でシリアライザを書けばポインタを持つ構造体やクラスも保存/読み込みが可能なこと。

とりあえずやってみたコードを以下に書いておく。
公式のドキュメントにあるシリアライザのコードが動かないので結構苦戦した。

SHDCRF の実装をアップしておきました

公開するかどうか悩んだのですが、公開することにしました。

 http://code.google.com/p/uchumik/

説明のスライドも slideshare にアップしています。 ただいまコンバート中なのでまたそちらは後ほど。

コンバート終わったようなので埋め込み。
何故か17ページ目の周辺化の式でΣが出なくなっている様子。
コンバートのエラーかな。

Shdcrf from uchumik

スライドは元々 DSIRNLP#3 での 20 分の発表用に作ったため、CRF や Forward-Backward  アルゴリズム、 Viterbi アルゴリズムは聴衆者の方々が理解していることを前提としています。
なので、いきなり読んでも非常に分かりにくいものとなっています。
先に TokyoNLP で発表した CRF の資料を見てもらうと多少分かりやすくなるかと思います。

http://uchiumi.blogspot.jp/2011/06/crf_25.html

今日は眠いので説明はまた今度。

Ragnarok Online の AI に機械学習を入れてみた

Git hub を使えと言われたのだけど、使うのに登録やら設定やらしなければいけないのが面倒なので止めました。
一発ネタの Lua スクリプトを公開するためだけだしなぁ。

ということで久しぶりにブログをアップしてファイル添付をしようと思ったのですが、何と Blogger ではファイルの添付は出来ない模様。

短いとは言えコメント入れたら800行とか行くので、とりあえず Lua で書いた ML の部分だけ。

function dotproduct(v1,v2)
 local val = 0
 for k,v in pairs(v1) do
  if (v2[k]) then
   val = val + v * v2[k]
  end
 end
 return val
end

function logsumexp(x,y)
 if (not x) then
  return y
 end
 if (x == y) then
  return x + 0.69314718055
 end
 local min = math.min(x,y)
 local max = math.max(x,y)
 if (max > min + 50) then
  return max
 else
  return max + math.log(math.exp(min-max)+1)
 end

end

MLR = {} -- multiclass logistic regression
BLR = {} -- binary class logistic regression

MLR.new = function(num,r,c)
 local obj = {}
 obj.class = num
 obj.eta = r
 obj.pcache = {}
 obj.cc = c*obj.eta
 for i = 1, num, 1 do
  obj[i] = {} -- parameters
  obj.pcache[i] = {} -- penalties
 end

 obj.predict = function(self, fv)
  local max = nil
  local pc = 1
  for i = 1, self.class, 1 do
   local v = dotproduct(fv,self[i])
   max = max or v
   if (v > max) then
    max = v
    pc = i
   end
  end
  return pc
 end

 obj.update = function(self,cc,fv)
  local values = {}
  local z = nil
  for i = 1, self.class, 1 do
   values[i] = dotproduct(fv,self[i])
   z = logsumexp(z,values[i])
  end
  for i = 1, self.class, 1 do
   local grad = -math.exp(values[i]-z)
   if (i == cc) then
    grad = grad + 1
   end
   for k,v in pairs(fv) do
    if (type(v) == "number") then
     if (self[i][k]) then
      self[i][k] = self[i][k] + self.eta * grad * v
     else
      self[i][k] = self.eta * grad * v
     end
     if (not self.pcache[i][k]) then
      self.pcache[i][k] = 0
     end
     local p  = self.cc - self.pcache[i][k]
     self.pcache[i][k] = self.cc
     self[i][k] = self[i][k]/(1+p) -- 本当は正則化のペナルティも減衰させるんだけどとりあえず定数でやっておく
    end
   end
  end
  self.cc = self.cc + self.eta
 end

 return obj
end

BLR.new = function(r)
 local obj = {}
 obj.eta = r

 obj.predict = function(self,fv)
  local v = dotproduct(fv,self)
  return 1/(1+math.exp(-v))
 end

 obj.update = function(self,cc,fv) -- cc:1(correct) or 0(incorrect)
  local grad = cc - self:predict(fv)
  for k,v in pairs(fv) do
   if (type(v) == "number") then
    if(self[k]) then
     self[k] = self[k] + self.eta * grad * v
    else
     self[k] = self.eta * grad * v
    end
   end
  end
 end

 return obj
end

----
-- A learning to rank Algorithm
-- Top 1 ListNet
----
ListNet = {}
ListNet.new = function(r,c)
 local obj = {}
 obj.eta = r
 obj.pcache = {}
 obj.cc = c*obj.eta

 obj.predict = function(self,instances)
  local values = {}
  local max = nil
  local id = nil
  for k,v in pairs(instances) do
   values[k] = dotproduct(v,self)
   max = max or values[k]
   id = id or k
   if (values[k] > max) then
    max = values[k]
    id = k
   end
  end
  if (not max) then
   return
  end
  return id
 end

 obj.update = function(self,instances,c)
  local values = {}
  local z = nil
  for k,v in pairs(instances) do
   values[k] = dotproduct(v,self)
   z = logsumexp(z,values[k])
  end
  for k,v in pairs(instances) do
   local grad = -math.exp(values[k] - z)
   if (c == k) then
    grad = grad + 1
   end
   for i,w in pairs(v) do
    if (self[i]) then
     self[i] = self[i] + self.eta * grad * w
    else
     self[i] = self.eta * grad * w
    end
    if (not self.pcache[i]) then
     self.pcache[i] = 0
    end
    local p  = self.cc - self.pcache[i]
    self.pcache[i] = self.cc
    self[i] = self[i]/(1+p) -- 本当は正則化のペナルティも減衰させるんだけどとりあえず定数でやっておく
   end
  end
  self.cc = self.cc + self.eta
 end
 return obj
end

学習データがストリームとしてやってくるので、学習率のスケジューリングなどは今回はやっていません。
また、FOBOSによるL2正則化の累積ペナルティが追加学習を行う時にはリセットされています。
何でこんなことになっているのかというと、面倒くさかったというのももちろんある（というか大半はそれ）のですが、Ragnarok Online ではマップごとで出現する敵のタイプが異なるため、敵に関するアクティブになる素性は明らかにマップごとに分かれます。
そのため、ペナルティの累積を常に残しておくと、各マップで学習を行って以前行ったことのあるマップに行くと、AI の学習をさせた途端その事例に含まれる素性のパラメータが全て0になってしまい最初からやり直し･･･ということが想定されるので、そういう風にならないようにしています。
これはどういうことかというと、行動やスキルのモデルファイルは1つに見えますが、実際にはマップごとに別々にモデルを学習しているのと同じ事になっています。

Ragnarok Online の AI 部分については使ってみたいという希望者が居るようなら改めて公開考えてみます。

間違ってるかもしれないCRFの説明

Crfと素性テンプレート

View more presentations from uchumik

TokyoNLP で話す内容を貼っておきます。
きっと後で訂正が入るんだろうな。。

実数素性テンプレートの使える CRF

この間記事で書いた実数素性テンプレートを使える CRF を作ってみました。
google code

面倒くさかったのでだいぶコピペの目立つコードになってますが、その辺は勘弁。

• テンプレートが文字列を扱うバイナリな値を取る場合（%x マクロを使うもの）ならば、素性関数 f_k(y_{i-1},y_i,X) は 1 or 0 を取る。
• テンプレートが実数を扱う場合（%r や SUM, MAX, Value, etc. ）ならば、素性関数 f_k(y_{i-1},y_i,X) はテンプレートに書かれた演算結果の値 or 0 を取る。

と、実数素性を使わない CRF からの変更点はそれだけです。

以下は動作確認のためだけのコード。

# include "rtcrflearn.hpp"
# include "rtcrftagger.hpp"

using namespace RtCrf;
using namespace std;

int main(int argc, char **argv)
{
   Crflearn learner(*(argv+1),*(argv+2),1000000);
   learner.init();

   learner.learn(5,0);
   learner.save("test.model");

   Crftagger tagger(*(argv+1),1000000);
   tagger.read("test.model");
   tagger.tagging(*(argv+2));
   return 0;
}

下が動かしたときの出力。

# ./test template ../data/train.txt
labels: 2
bound: 3
ufeatures: 17
bfeatures: 1
instance: 1
uparameters: 34
bparameters: 8
model parameters: 42
epoch:  0 err:0.500000(2/4)
epoch:  1 err:0.000000(0/4)
epoch:  2 err:0.000000(0/4)
epoch:  3 err:0.000000(0/4)
epoch:  4 err:0.000000(0/4)
a b c 1.0 -1.0 L_A L_A
d e f -1.0 1.0 L_B L_B
p e f -0.5 0.1 L_B L_B
g b c 0.3 -0.1 L_A L_A

実数素性を使えそうな公開データとかあればそれで試してみたいですけど、とりあえず今日の所はここまで。

Tagger クラスの出力に予測時のスコアを出すようにすれば、１段目の CRF の出力を２段目の CRF の学習素性に使うというようなスタッキングも出来るようになるかなと思う次第。

そのうち CNF とかと一緒にまとめて API を変えとこうかな。

実数素性テンプレートを作ろう。

まだ生きてます。

ここしばらくはちと研究のまねごとなどを会社でしている事もあって、あんまりブログに書ける事も無い日々です。
とりあえず対外的に問題ない範囲だと、去年の11月にACMLという会議でポスター発表をしてみました。
ポスターはアブストの提出だけだったのですが、参考文献が後で見直したら壊れていたという大失敗。

後、同じ11月にNL研でクエリの訂正手法についての発表をしてきました。
広島のお好み焼きはおいしかったです。

あと、 NetWalker を活用するべくいくつか実装したものもあるのですが、そちらはまだしばらく非公開。

とりあえず生存報告はこんな所。
最近忙しいですが何となく以前よりは楽しく過ごせている気がします。

で、久しぶりに書いた記事がこれで終わりというのもなんなので、近々 TokyoNLP で発表しようかなと思っている CRF の素性テンプレート周りの話に関連して少々追記。

素性テンプレートが使える CRF というと、CRF++ や crfsgd がありますが、基本的にこれらの素性テンプレートは文字列を素性とするタイプで、素性関数は f_k(y,x) = 1 or 0 というようにバイナリの値を取るようになっています。
これはある素性関数は特定の y と x のペアが観測された時に 1 を返して、それ以外のときは 0 を取るという意味で、素性がテキストの時は特に問題になる事はありません。
が、最近はクエリログとかを扱う機会も多くなってきた都合上、出来れば実数値も扱いたいなーと思う事がしばしばです。
例えば、クエリに含まれるトークンにタグ付けをする際には、トークンの尤度を言語モデルで求めて、それを素性として扱いたいとかがあると思うのですが、それは現状だと数値の範囲を表す様なテキストに変更して素性として扱うしかなさそうです。
ですが、この方法だとスコアの範囲ごとに素性が分かれるので、やっぱり元々の言語モデルで求めた尤度を直接素性として扱うのとは違いそうです。

なので、実数の扱える素性テンプレートを作ってみました。
http://code.google.com/p/cnf/source/browse/#hg%2Ftoys%2Frtcrf%2Fsrc
動作としては、 f_k(y,テキスト素性) = 1 or 0、 f_k(y,実数素性) = 素性の実数値 or 0 となります。

もちろん、素性テンプレートというからには観測された素性の組み合わせを扱えないと格好が悪いので、実数素性でも組み合わせ（素性どうしの各種演算等）が扱えるようにしました。

で、ついでに素性テンプレートが今まで学習器とセットで独立性が低かった点も見直してみました。

使える演算としては、

• ( x )
• x + x
• x - x
• x * x
• x / x
• x % x
• -x
• log x
• sqrt x
• exp x
• max ( x,... )
• min ( x,... )
• sum ( x,... )
• prod ( x,... )
• x > x
• x >= x
• x < x
• x <= x

をひとまず用意。
上の例だと x は変数に見えますが、別の演算を x の所に入れる事も出来るので、

(x_1+x_2)*x_3*max(max(...),min(...),x_4,log(x_5),...)

みたいな事も出来ます。

とりあえず実際に適当に書いてみたテンプレートの例が以下です。

# Unigram
U00:%x[-2,0]
U01:%x[-1,0]_%x[0,0]
U02:%x[-1,0]_%x[0,0]_%x[1,0]
U03:1.0-%r[0,3]
U04:%r[0,3]+%r[0,4]
U05:%r[0,3]-%r[0,4]
U06:%r[0,3]*-%r[0,4]
U07:%r[0,3]/-%r[0,4]
U08:%r[0,3]%-%r[0,4]
U09:SUM(%r[.,3])
U10:PROD(%r[.,4])
U11:MIN(%r[0,3],%r[0,4])
U12:MAX(%r[0,3],%r[0,4])
U13:MIN(%r[.,3])
U14:MAX(%r[.,4])
U15:MIN(%r[0,.])
U16:MAX(%r[0,.])
U17:MIN(MAX(%r[0,.],%r[.,3]),%r[.,4])
U18:%r[0,3]/MAX(%r[.,3])
U19:%r[0,3]/SUM(%r[.,3])
U20:MIN(%r[0,3]+%r[0,4],%r[0,3])

# Bigram
B

で、入力に使ったこれまた適当データが次。

a b c 1.0 -1.0 L_A 
d e f -1.0 1.0 L_B 
p e f -0.5 0.1 L_B 
g b c 0.3 -0.1 L_A

これに上のテンプレートを使って素性を展開すると、次のようになります。

U00:_B-2:1 U01:_B-1_a:1 U02:_B-1_a_d:1 U05:2 U06:1 U07:1 U09:-0.2 U10:0.01 U11:-1 U12:1 U13:-1 U14:1 U15:-1 U16:1 U17:-1 U18:1 U19:-5 B:1 
U00:_B-1:1 U01:a_d:1 U02:a_d_p:1 U03:2 U05:-2 U06:1 U07:1 U09:-0.2 U10:0.01 U11:-1 U12:1 U13:-1 U14:1 U15:-1 U16:1 U17:-1 U18:-1 U19:5 U20:-1 B:1 
U00:a:1 U01:d_p:1 U02:d_p_g:1 U03:1.5 U04:-0.4 U05:-0.6 U06:0.05 U07:5 U08:-0.1 U09:-0.2 U10:0.01 U11:-0.5 U12:0.1 U13:-1 U14:1 U15:-0.5 U16:0.1 U17:-1 U18:-0.5 U19:2.5 U20:-0.5 B:1 
U00:d:1 U01:p_g:1 U02:p_g__E+1:1 U03:0.7 U04:0.2 U05:0.4 U06:0.03 U07:3 U08:0.1 U09:-0.2 U10:0.01 U11:-0.1 U12:0.3 U13:-1 U14:1 U15:-0.1 U16:0.3 U17:-1 U18:0.3 U19:-1.5 U20:0.2 B:1 

実装 は c++ で、 bison、 flex を使って作っています。
tsubosaka さんからはこのくらいの仕様なら bison、 flex なんて使わないでいいんじゃないの？というありがたいお言葉を頂いたのですが、残念ながら僕は 1 からパーザを書いた経験が無く、正直自信が無いためこれらを使っています。
ちなみに flex のバージョンが 2.5.35 、bison が 2.3 の環境で作っています。
bison は 2.1 以降なら c++ に対応しているので問題ないと思いますが、 flex の方は 2.5.35 だと yyFlexLexer::yywrap の実装がデフォルトで無いため、yywrap の実装を適当にソースコードの中に書いています。

これが 2.5.4 以降だと標準で実装されているので、多分コンパイル時に多重定義で怒られるんじゃないかなぁという気がします。

今週はきっとこれ使った CRF 実装してます。