SVN(Support Vector Machine)を調べたときに役立ったサイトメモ

Support Vector Machineの原理を調べてるときに役立ったサイトを張っておく。

一昔前に一世を風靡した手法だが、まじめにロジックを追うと数学的な知見が結構使用されていた。

どれか一個を見れば、完璧！見たいのは残念ながらなかったが私の場合は下記のサイトをいったりきたりしながら読み込んでいったら大体理解できた。

もちろん、これ以外のサイトも多数見たが、よくわからなかったり、明らかに間違ってたりといった質的にいまいちなサイトも多くあったことを記しておく。


名古屋大学の人が書いた説明
短くまとめられているので、全体像を把握するのに役立った。
付録として掲載されているKKT法の例も有益。

静岡理工大の人が書いた資料
一般的なSVNでは多次元を前提として説明されているので、数式が若干追いづらい。
このサイトでは、入力が2次元であることを前提に説明しているので、論理展開がわかりやすい。
数学的厳密性は気にしてなかったので非常に重宝した。

個人的には、2次元で説明しているために、マージンの距離の求め方が、単に点と直線の距離の距離の公式を使って求めているに過ぎないことがわかり、これのおかげでつまづきが解消された。マージンの距離については、必ずしもそういう説明をしてくれないサイトも多かったんだよね。

産業技術総合研究所の人が書いた資料
一番教科書的に使える資料。ただし、式の展開などはわかっていることが前提でさっくり飛ばしているので、初学には向かない。俗に言うインデックスとして資料するのにお薦めな資料。

海洋大学の人の書いた資料
KKT方について調べるのに役立った。

Deep Learning用のモデルを簡単に作成できるLabellioを使ってみた

本記事は Deep Learning Advent Calendar 2015 22日目の記事です。

AlpacaがリリースしているDeep LeaningのWebサービスにLabellioというのがあります。これを使うと、画像データを与えるだけで、自動的にDeep Learningで学習を行いモデルを作成することができます。モデルはもちろんエクスポート可能であり、著名なDeep LearningフレームワークのひとつであるCaffeに対応した形式でエクスポートすることができます。

学習はすべてLabellioの用意するリソース上で行われるので、自前で用意するのは訓練用の画像データとそのラベルだけでよいという優れものです。
訓練データは自前で用意したものをUploadすることもできますし、とりあえず試したいのであればLabellioが提供するAPIを利用してFlickr/Bingから訓練データを自動的に取得させることもできます。

今回は、Flickrから取得したデータを使ってみました。例としてフルーツの画像分類器を作成してみます。

まずモデル名として"Fruits"と指定します。
そして訓練データをFlickr上から取得するように指定します。

SourceとしてFlickrを指定。
LabelにOrange, Apple, Bananaを入力する。



ラベルの入力が終わったらAddを押す。





ここでNextを押すと学習用の処理がLabellioにenqueueされる。



後はTrainingが終わるのを待つ。
今回の場合は150個程度の訓練データしか使ってないようなので、数分程度で学習が終了した。


学習が終わった後、適当にGoogleで見つけたバナナの画像をこの分類器に与えてみる。




結果が出るまで少し待つ




それ程時間がかからずに結果が出る。
バナナな確率0.6。思ってたより数値が良くないのは訓練データが少ないせいだろうか。
そういえば訓練結果のAccuracyも0.57だった。

もう少しいろいろデータを用意して試してみたいところだ。

使ってみた感触

もはや画像データを渡せばいいだけなので、Deep Learningが何なのかといった知識がまったく不要である。また学習のリソースごと提供してくれているのが非常にポイントが高い。フレームワークはオープンソースで無料なのがいくつも存在するが、学習用のリソースはそうはいかない。

営利目的でしっかりとしたものを作るのならともかく、単に学習を目的としていたり、趣味でちょこっと作りたいときなど、学習リソースの調達はネックになることが多いであろう。

そのなかで学習環境もセットで提供されているLabellioは非常に存在価値が高いといえる。

Courseraの講義資料をダウンロードする方法

Couseraで人気のAndrew Ng氏によるMachine Learningの講義資料をダウンロードする方法のメモ。

なお、このスクリプトはCousera全般に対応しているので基本的にはどれも落とせる様子(未検証)

前提条件

講義資料への正しいアクセス権を持っていること。
つまり、普通にブラウザ経由で講義を見れている人が、オフラインで見たいなどのケースを想定。アカウント持ってないけど、資料を見たいという人は、無料なのでまずアカウントを作ってください。

準備

cousera-dlをインストール。

%> pip3 install coursera

詳細はcousera-dlを見てください。

ダウンロード

%> cousera-dl -u <username> -p <password>  ml-005

usernameとpasswordは、couseraにログインするときに使う、メールアドレスとパスワード。
ml-005はAndrew Ng氏のMachine Learningの識別子。

後はスクリプトが終わるまで待つ。
私の環境では10-20分程度は時間がかかった。

[Octave] broadcasting

Octaveにはbroadcastingという概念があるらしい。

これは例で言うと、下記のような演算ができるようになるもの

>A = [ 1 2 3; 4 5 6; 7 8 9]
>B = [1]
>C=  [ 10 20 30]
>bsxfun(@plus,A,B)
[2 3 4; 5 6 7; 8 9 10]

全部の要素に1が足されている 

 

>bsxfun(@plus,A,C)
[11 22 33; 14 25 26; 17 28 39]

一行目には10、二行目には20、三行目には30が足されている。

ちなみに、bsxfun関数を使わなくとも、A + BやA + Cをやっても同じ結果が返される。デフォルトで有効になっているということだろうか。(後で調べる)

OctaveやNumpyではbroadcastingと呼んでいるが、Matlabではbinary singleton expansion、Rではsingle instruction multiple dataとかreplicationと呼ばれたりするらしい。

A note on terminology: “broadcasting” is the term popularized by the Numpy numerical environment in the Python programming language. In other programming languages and environments, broadcasting may also be known as binary singleton expansion (BSX, in MATLAB, and the origin of the name of the bsxfun function), recycling (R programming language), single-instruction multiple data (SIMD), orreplication. 

 

GNU Octave 19.2 broadcasting
Mathworks bsxfun

単純に行列演算してる分にはとっつきやすい印象があったOctaveだが、ちょっと突っ込んで使い始めると意外にぱっと見わかりにくい機能が多い

[読書感想文]エンジニアとして世界の最前線で働く選択肢 ~渡米・面接・転職・キャリアアップ・レイオフ対策までの実践ガイド

本書のような自分のキャリアを振り返った本を読む場合、何よりも気になるのは著者の経歴である。中には職歴が2年程度しかないのに、FacebookやGoogleのような有名企業に入ったというだけで、本の出版に至ってしまうような人も昨今少なからず見受けられる。そのような本を購入した時のがっかり感はなんとも言えない。

著者の名前で軽く検索をかけてみると、そんなことはないようだ。
新卒として日本HPに入社し、駐在員としての米国勤務を経た後、AmazonやMicrosoftなどの企業を渡りあるいているようだ。

仕事以外でも、「シアトル界隈のIT関係者が集まって勉強会や講演会などを行う非営利団体シアトルITジャパニーズプロフェッショナルズ（SIJP）の副会長」として精力的に活動されているようであり、少なくとも充分に耳を傾けてみたい経験をお持ちのように見えた。

ちなみに下記のWebサイトが面白かった。購入を迷ってる人はぜひとも読んで欲しいし、読んでしまった人でもまた違うエピソードが紹介されてたりするのでまた違った楽しみを味わえる。


Story of My Life 竜 盛博さん

シリコンバレーで管理職になる道


さて、かなり期待感を膨らませて本を読み始めたが、期待は決して裏切られなかった。
副題の通り、採用、面接、レイオフについて、客観的な情報に、自身が経験した主観を匠に織り交ぜており、一気に読み進めてしまった。採用や面接の情報は筆者自身が採用の経験が豊富であることもあり、非常に高価値な情報が満載である。

いくつか心に残ったことをメモしておく。

• キャリアは運に大きく左右される。

これは私もしみじみと実感していることである。私も海外赴任に手を上げて、どう選ばれるかも不明なプロセスを何年も待ち続けたことがある。成果を出せばいいという簡単なものでもなく、その時の募集状況やプロジェクトの予算など自分の努力ではどうしようもない要因に悩まされた。

• レイオフは避けられないので、されてもすぐ転職できるように日頃から準備するしかない。

私はまだレイオフを経験したことがない。しかしこれは真理なのだろう。心に止めておかないと行けない

• 35歳プログラマ定年説のないアメリカでも、50歳を超えると転職は難しい

50歳になって米国で職が見つからない場合、日本での求職はもっと絶望的だろう。米国で働き続けるのならば、これが最大のリスクといえるかもしれない。


本書は、「はじめに」に筆者がいうように、米国でソフトウェアエンジニアで働くことの美点しか強調されない昨今の風潮に違和感を感じメリットとともにデメリットも知ってほしいという思いで書かれている。一貫して中立した立場で書かれており、非常に読んでて安心できる。どうするべきかなど安易な結論を書いたりせず、また、筆者自身もまだ悩み続けている様子が描写されており、同じく米国で働く身として大きな親近感を抱いた。



米国で働きたいと考える人には必読といえる一冊である。

Define-by-RunとDefine-and-Run

Neural Networkの設計思想を表す用語のようだ。

The "Design-by-Run" scheme is also an important design decision to neuron that has both pros and cons. Most existing neural network library today follows "Design-and-Run" scheme or a declarative approach that first compile a pre-determined network structure and then train against a dataset. In such way, one can pre-allocate any necessary cache space to ensure that there are minimal memory reallocations in training, thus minimize the memory footprint whenever possible and have substantially optimized performance. Meanwhile, such a declarative approach also makes the underlying neural network static during the lifetime of training. The "Design-by-Run" scheme instead treats the neural networks morphologically, i.e. they are composed and (can) deform on-the-fly. At a cost, it will ask for onsite memory allocation whenever needed

簡単に日本語でまとめると

Neural Networkの設計にはDesign-and-RunとDesign-by-Runという二つの設計思想がある。

Design-and-run

• 今日の一般的なスキーマで宣言的なアプローチに分類される
• 宣言的なアプローチとは事前に決定されたネットワーク構造を利用し、トレーニングを行うもの。
• キャッシュスペースが事前に割り当てられるので、メモリの使用を最小化し、性能を最適化することができる。しかしトレーニングの間にネットワーク構造を変更できないという欠点がある。

Design-by-run

• ニューラルネットワークを形態学的に(morphologically)扱うことができる。
• ネットワークの構造変更が容易にできるが、メモリの割り当てなどは最適化できない。

https://github.com/bobye/neuron/wiki/Basics#design-rationale

MNISTの解凍済みデータ

ディープラーニングとかで話題のニューラルネットワーク。
このニューラルネットワークの代表的な応用例として、手書き文字の認識というのがあります。

これはその名のとおり、お絵かきツールなどでフリーハンドで書いた数字が、0から9のどれにあたるのかを判定するものです。

ニューラルネットの練習としてこの手書き文字(数字)認識を実装してみようとすると、訓練データが必要となります。この訓練データはまじめに用意しようとすると大変なんですが、幸いなことにMNISTにデータが公開されています。

ただし、このデータはIDX file formatというフォーマットで圧縮されているために、そのままでは利用できません。

その場合は、下記のような方法でデータを利用することができます。

Nodejs

mnistというnodejsのアプリを使うと、json形式の訓練データとテストデータを取得することができます。取得自体にはnodejsが必要ですが、テキスト形式で取得できるので、その後どんな言語にでも利用することができます。jsonで取得できるのはうれしいですが、nodejsの環境が手元にないと使えないところが少々不便。

Python

deeplearning.netにPickle形式のデータが公開されています。pythonでサンプルを書こうと思ってる方はこちらのほうが手っ取り早いでしょう。


しかし、IDXフォーマットとか非常に面倒ですね。データ圧縮率とか優れているのかも知れませんが、普通にzipとかにしてもいまどき大して困らなかった気がするんですが。理論上の性能を追い求めるあまり、利便性を犠牲にしている気がします。

Javaにデバック用のログを追加できるライブラリLogAdderを公開

LogAdderはJavaの各メソッドの先頭にトレース用のログを埋め込むことができるオープンソースソフトウェア。

下記の順にメソッドが実行されるJavaのソースがあったとする。

 
public static void main(String[] args){
   step1()
   step2()
   step3()
}

public static void step1(){

}

public static void step2(){

}

public static void step3(){
}

このソースコードに対してLogAdderを実行すると、下記のようにトレースが追加される

 
public static void main(String[] args){
  System.out.println("I'm at " + new Exception().getStackTrace()[0].toString());
   step1()
   step2()
   step3()
}

public static void step1(){
  System.out.println("I'm at " + new Exception().getStackTrace()[0].toString());
}

public static void step2(){
  System.out.println("I'm at " + new Exception().getStackTrace()[0].toString());
}

public static void step3(){
  System.out.println("I'm at " + new Exception().getStackTrace()[0].toString());
}

そして、このログ追加済みのソースコードを実行すると、下記のような標準出力が出される。

I'm at com.github.kentan.logadder.sample.data.Sample1.main(Sample1.java:6)
I'm at com.github.kentan.logadder.sample.data.Sample1.step1(Sample1.java:14)
I'm at com.github.kentan.logadder.sample.data.Sample1.step2(Sample1.java:19)
I'm at com.github.kentan.logadder.sample.data.Sample1.step3(Sample1.java:24)

これを見ると、ログ(この場合は標準出力)を見ることによって、実行順序がわかる。

私がこれを作ったきっかけは、非常に大規模なプロジェクトで、マルチスレッド、キューイング

メッセージングが多用されたソースコードを解析する必要があったためだ。

そのようなソースコードでは手続き型言語を読むように、ただ呼び出しを追っていくだけで解析を進めることは非常に難しい。同じようなソースを読む必要に遭遇したとき、本ライブラリは大いに役立つとと思う。

react.jsとjquery mobile

reactjsで書いたコンポーネントをjquery mobile風にしたくて試してみた。

まず単純に、react.jsのコードにjquery mobileのコードを書いてみた。

render()メソッドの中に書く。

<body>
<script type="text/jsx">
React.render(
        <ul data-role="listview">
          <li><a href="acura.html">Acura1</a></li>
          <li><a href="audi.html">Audi1</a></li>
          <li><a href="bmw.html">BMW1</a></li>
        </ul>
);
</script>
</body>

すると何も表示されない。

次に、htmlのbodyタグ直下に書いて見る。

<body>
    <div id="content"></div>
        <ul data-role="listview">
         <li><a href="acura.html">Acura</a></li>
         <li><a href="audi.html">Audi</a></li>
         <li><a href="bmw.html">BMW</a></li>
        </ul>
    </div>
<script>省略</script>
</body>

これはきちんと表示される。

react.jsもjquery mobileもタグのattributeを元に、domの操作をしているから、この辺の処理がバッティングしているのかもしれない。

調べてみたところ、jquery mobileが変換するclassを直に指定すれば出来るとの情報がstackoverflowにあった。なるほど。

やってみる。

<body>
<script type="text/jsx">
React.render(
   <ul class="ui-listview" data-role="listview" >
        <li class="ui-first-child"><a href="acura.html">Acura3</a></li>
        <li><a href="audi.html">Audi</a></li>
        <li class="ui-last-child"><a href="bmw.html">BMW</a></li>
   </ul>
);
</script>
</body>

ブラウザで再度確認する。今度は表示された。しかし、jquery mobileのスタイルではなく、ただのul要素として描画されている。つまり、class以下は無視されたようだ。

試しにstackoverflowで例として出されていたbuttonを表示してみる。

<body>
<script type="text/jsx">
React.render(
　<button className="ui-btn"/>
);
</script>
</body>

こちらはきちんとjquery mobile風で表示された。

出来るのと出来ないのがあるようだ。

listviewの場合は、それを含む外のdomもclass指定すれば出来たりするのだろうか。

ただ、いずれにせよいちいちclassを調べなければいけないのはだるすぎる。

あまりこの組み合わせは推奨出来るようなものではなさそうだ。

Koansでreacjs入門

koansはreact.jsを手を動かしながら学ぶコンセプトで作られたプロジェクト。
node.jsのユニットテストを利用し、正しく実装できるとテストが合格する。

ちょうどreact.jsに入門したかったこともありやってみた。
いい感じに入門できる。

javascriptと、ある程度のプログラミングに対する前提知識があればきちんとついていけるようにできている。

githubのreadmeに本の紹介があるけど、プロモーションの一貫なんだろうか。

http://blog.arkency.com/rails-react/

49ドルはちょっと高い気がするが、koanの出来の良さを考えると、お値段分の価値はあるかもしれない。

サンプルがあるので、まずはこれを読んでみるか。

ゲーム理論のナッシュ均衡と最適戦略

用語の整理。
定義上、ナッシュ均衡は全プレイヤーがbest responseを取った状態のことであるが、これを「わかりやすく」説明しようと試みた結果、逆にわかりにくかったり、正確ではない言い方になっていることが多かったので、自分の言葉でまとめなおした。



・ナッシュ均衡

すべてのプレイヤーが最適戦略（best response）である戦略をとっている状態

a ∗ = (a ∗ 1 , · · · , a ∗ n ) ∈ A is a Nash Equilibrium if
   a ∗ i ∈ Bi(a ∗ −i ) for every i ∈ N. 

・Best Response
ほかのプレイヤーの戦略を固定値としたまま、自分の戦略だけを動かして、最大値を取れる戦略。数式で書くと以下の定義。

ai ∈ Ai is a best response to a−i ∈ A−i if
　ui(ai , a−i) ≥ ui(a*i , a−i) for all a*i ∈ Ai

ポイントはbest response(最適戦略)であろうか。bestあるいは最適という言葉に引きづられて、あたかもナッシュ均衡を目指す戦略がもっとも報酬が高い戦略であるという風に説明されていることもおおいように思える。

しかし、囚人のジレンマなどでも有名なようにナッシュ均衡は必ずしも、全プレイヤーに最高の結果をもたらす戦略ではない。あくまでも、自力でがんばれる範囲（＝ほかのプレイヤーの戦略値を固定値としたまま） でもっとも報酬が高い（＝その環境において最適な）戦略を全プレイヤーがとった状態だ。自分だけでは戦略を変更しても、メリットはないため均衡に陥る。

均衡の定義自体はわかりやすいが、定義したことのメリットがわかりづらいため、いろいろな説明が生まれて、その結果混乱の元になっているのだろうか。

参考文献
http://www.econ.ucla.edu/iobara/Nash201B.pdf

Ubuntu on ESXi on VMWare Player on Win7

下記の構成で、ESXiの検証環境を作れたのでメモ

1. まず物理環境
OS:Windows 7
CPU: Xeon e5440

2. 1の上にVMWare Player 7.1.0 (Build 2496824)をインストール

3. 2の上にESXi 6.0.0 (249585)をインストール

4. 3の上にUbuntu 32bitをインストール。

なお、Xeon e5440はEPT(Extended Page Table)機能がないために、4として64ビットOSをインストールすることが出来ない。

参考文献

CPUの機能要件についてはこちらが詳しい
Having Difficulties Enabling Nested ESXi in vSphere 5.1?


VM Player上でESXiの動作が公式にサポートされているのかは見つけられなかったが、vmware.comドメインで運営されている下記でVMWare Playerに言及されているので、公式にサポートされているとみなしても良さそう。

Running Nested VMs

他にも個人運営のブログ等ではESXiをVMWare Player上で動かした際の情報がたくさん見つかる。古いバージョンの話なので、最新のバージョンの動作保証とするには少々微妙だが。

CFR(Counterfactual regret minimization)でdudo

CFR で三目並べに続いてdudoというdiceゲームをCFRで書いてみた。


GitHubのソースコード

dudoのゲームルールはこちらを参照。
三目並べと比較すると、dudoは非完全情報ゲームなので、CFRを適用するにはちょうどいい対象である。


CFRの評価がしたかったので、ゲームの実装は実際のdudoに比べて下記のように簡略化してある。

• 1の目はワイルドカードとしてカウントしない。
• プレイヤーの数は二人
• 各プレイヤーが持つダイスの数は2つ。

200回ほどトレーニングをさせたCFRと、単純に相手のコールにひとつだけ上乗せをする戦略をとるBoarPlayerを戦わせたところ、大体75%ほどの勝率でCFRは勝利を収めた。

MSCFの理解に役立ったリンク

ファイルサーバを例に設定の仕方が細かく載っている。
Failover Cluster Step-by-Step Guide: Configuring a Two-Node File Server Failover Cluster

VMWare上のWindows 2008R2でMSFC

VMware Playerの上で動かしたwin2008R2同士でクラスタを組んだ。

どっちも同じvmdkファイルをコピーして使いまわしていたら、フェールオーバクラスタマネージャの構成の検証でネットワーク周りのエラーが出た。

こんな感じのエラー

ネットワークトポロジを読み込み中にエラーが発生しました 0x90070005

無視して進もうにも、クラスターの作成、のウィザードで「アクセスが拒否されました」とエラーメッセージが出て進めなかった。

いろいろ調べたところ、原因はvmdkファイルを使いまわしたことによってドメインSIDが重複していることがわかった。これは、クラスターのノードとなる2008R2のアプリケーションログを見ることによって発見した。

下記のページの手順に沿ってSIDを再度設定しなおしたところ、構成の検証が通るようになった。

Windows 2012 R2でSysprepを実行してゲストOSを初期化してみる

ドメインSIDについてはこちらを参照

オブジェクトを識別するSIDとは？

classloaderとstatic変数

classloaderとstatic変数の関係を調査してみた。

基本的にはclassloaderが異なると、static変数の値も異なるというのが仕様のようだ。
ただし、classloaderのhierarchyで同じparentを共有していると、static変数は共有される。

詳細はstackoverflowで。

Multiple instances of static variables


ちなみに下記の日本語ブログでも、static変数はクラスローダごとに別になるとの情報があるが、ブログに載ってるサンプルコードを実行したところ、２つのクラスローダでstatic変数は共有されているようだった。

[Java]別々の ClassLoader にロードされたクラスのフィールドは別になる


URLClassLoaderとPluginClassLoaderが階層的にどういう関係にあるのか調べてないけど、親をどっかで共有してたりするのだろうか。または、2006年の情報なのでjavaのバージョンが関係して足りすのだろうか。

pipでプロキシを設定する方法

環境変数に設定する。

%> export https_proxy="http://<proxy.server>:<port>"
%> pip install <xxxxx>

参考文献
http://stackoverflow.com/questions/19080352/how-to-get-pip-to-work-behind-a-proxy-server

 

RHELでCentOSのレポジトリを使用する方法まとめ

RHELは標準構成ではほとんどソフトウェアがインストールされていないので、いろいろ開発していると追加でインストールする必要が出てくる。 RHELにソフトウェアをインストールする方法は大きく2つ。

1. rpmをどっかから持ってきてインストール
2. yumを使う

ただし、yumを利用する場合RedHatの契約が必要になる。 正式運用環境ならともかく、単なる開発環境ではそんなもの用意してられないので、こういう時はCentOSのレポジトリにつないでインストールするといい。 ここではそのための設定をまとめる。

レポジトリの設定

下記のパスのファイルを新規作成し、下記の内容を記述する。

/etc/yum.repos.d/CentOS-Base.repo

[base]
name=CentOS-6 - Base
mirrorlist=http://mirrorlist.centos.org/?release=6&arch=$basearch&repo=osbaseurl=http://mirror.centos.org/centos/6/os/$basearch/gpgcheck=1
gpgkey=http://mirror.centos.org/centos/RPM-GPG-KEY-CentOS-6

プロキシの設定

プロキシを使っていない場合は、この設定は不要。
下記のファイルに

/etc/yum.conf

下記の設定を行う

proxy=<url>:<port>

CFR(Counterfactual regret minimization)で三目並べ(Tic Tac Toe)

CFRの習い作として三目並べ(Tic Tac Toe)のAIを書いてみた。

が、書き始めて気づいたのだが、三目並べは完全情報ゲームであり、探索空間も狭いため、1回の試行で全部の戦略を探索できてしまう。
正直、CFRの例としてあまり意味をなしてないが、まあCFRとはなんぞやというのを理解する目的は果たせてると思うので、一応公開することとした。



CFR for Tic Tac Toe

Counterfactual regret minimization(CFR)

概要

ポーカーとかのAIで有名なcounterfactual regret minimization(CFR)。

ひとことで言うと、近似ナッシュ均衡を求めるための手法。

Regret Minimization

まず、CFRの元となったRegret Minimizationの説明から。
Regret Minimizationとは、その名の通り、過去の学習データから、regret(後悔)が最も小さくなる(minimization)手を選択する手法。

じゃんけんの例

例として、二人でじゃんけんを繰り返し行う場合を考える。
この時、勝つと1点、負けると-1点、引き分けると0点もらえるとし、これを繰り返し試行する仮定する。


まず1回目としてプレイヤーAがグー、プレイヤーBがパーを出したとする。
そしてプレイヤーAは負けたので-1点となる。

ここでプレイヤーAはパーを出してれば引き分けで0点、チョキを出していれば勝利で1点もらえる。

つまりプレイヤーAは1回目の戦略に対して、下記のように後悔の値を定量化することが出来る。この定量化した値をregretと呼ぶ。

• 戦略パー       0 - (-1) = 1
• 戦略チョキ   1-  (-1) = 2

CFRでは、2回目の戦略を決めるにあたって、regretに比例した確率で戦略を決定する。
つまり、2回目にチョキを選ぶ確率は2/3、パーを選ぶ確率は1/3、グーを選ぶ確率は0である。


ここで2回目の試行としてプレイヤーAがチョキ、プレイヤーBがグーを出したとする。
2回目の試行もプレイヤーAの負けなので、-1点となる。regretはそれぞれ次のようになる。

• 戦略パー    1 - (-1) = 2
• 戦略グー   0 - (-1) = 1

3回目の試行では、1,2回目を通したregretの値を利用する。

• 戦略パー     1 + 2 = 3
• 戦略チョキ 2 + 0 = 2
• 戦略グー　 0 + 1 = 1

よって、3回目の試行でそれぞれの戦略が選ばれる確率は、パーが3/6=1/2、チョキが2/6=1/3、グーが1/6である。

これがRegret Minimization。
ここで非常に重要なのが、Regret Minimizationにおいて、プレイヤーの平均的なregretがe未満であるとき、その時の戦略は近似ナッシュ均衡戦略であるといえる、という定理があること。


つまり、言い換えるとRegret Minimizationは近似ナッシュ均衡戦略を求める手法であるということが出来る。

Counterfactual Regret Minimization

そしてようやく出てきてCFR。
これのコンセプト自体を直感的に説明するのは少々難しいので別の機会に譲る。

ただ、これがなぜ重要なのかだけをメモしておく。

まず、CFRで提案されている概念のRegret(Immediate counterfactual regret) は必ず、Regret Minimizationのregret以上の値になる。つまり、Immediate counterfactual regretを最小化することは、Regretを最小化することにつながる。仮にImmediate counterfactual regretがaと求められたのならば、少なくともその時の戦略はa以下の近似ナッシュ均衡戦略であると言えるわけだ。

なぜ、こんなめんどくさいことが重要かといえば、解を解くときの計算量の関係。
ナッシュ均衡はとてもじゃないけど求められないし、近似ナッシュ均衡戦略を求めるregret minimizationもまだ十分に計算量が多い。そこで計算量が小さいCFRが重宝されている。

参考文献

An Introduction to Counterfactual Regret Minimization

Regret Minimization in Games with Incomplete Information

VMWare Playerでコピペ出来ない時にする設定

VMware playerにVMWare Toolsを入れればコピペ出来るはずなんだけど、なぜかたまにコピペが効かない時がある。そんな時にする設定


vmxファイルに下記の設定を追加して、ゲストOSを再起動

isolation.tools.copy.disable = false
isolation.tools.paste.disable = false

Androidアプリ 麻雀点数計算機をリリース

麻雀の点数計算を練習するアプリをAndroidでリリースしました。

Google Playはこちら

麻雀は点数計算をマスターするのが結構面倒だったりします。
特に符計算とか細かい条件がありすぎて出来る人に任せっきりだったりします。

しかし、誰もが一度は点数計算覚えてみようかな、と思ったことがあるはず。
そんな時にはぜひこのアプリを使って点数計算をマスターしてください。