2011年12月10日土曜日

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 部分については使ってみたいという希望者が居るようなら改めて公開考えてみます。

2011年6月25日土曜日

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



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

2011年6月12日日曜日

実数素性テンプレートの使える 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 クラスの出力に予測時のスコアを出すようにすれば、1段目の CRF の出力を2段目の CRF の学習素性に使うというようなスタッキングも出来るようになるかなと思う次第。
そのうち CNF とかと一緒にまとめて API を変えとこうかな。

2011年6月8日水曜日

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

まだ生きてます。

ここしばらくはちと研究のまねごとなどを会社でしている事もあって、あんまりブログに書ける事も無い日々です。
とりあえず対外的に問題ない範囲だと、去年の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 実装してます。