2014年7月22日火曜日

知覚の諸問題


 
(SYNAPSEより)


Cognitive Neuroscience: The biology of the mind
Michael S. Gazzaniga, Richard B. Ivry and George R. Mangun
より5章Sensation and Perceptionの考察をまとめましたので、宜しければ。

文字認識とかでニューラルネットワークが使われますが、そこでのテクニックの多くは実際の人間の知覚を参考にしているところが多くあるのですね。

こういった認知科学の分野は、脳を分割していっても博物学的になるだけで面白い問題はないんじゃないかと思っていたんですが、意外と人間の脳というのは局所性があり、知能と「物質」を結びつけることができるようですね。

クオリアとかの主観的体験は観測することが出来ませんが、こういう機能論的な意味でのsensationを理解することはその礎になるのでしょう。



図表は全て上記論文より引用

2014年7月14日月曜日

マルチコアマシン環境における並列最良探索アルゴリズム

Best-First Heuristic Search for Multicore Machinesという論文をまとめたスライドです。

Ethan Burns, Sofia Lemons, Wheeler Ruml and Rong Zhou. (2010). Best-First Heuristic Search for Multicore Machines. Journal of Artificial Intelligence Research 39(2010) 689-743

内容は並列最良探索です。A*探索などの基本的な探索アルゴリズムを知っていることを前提としています。
よければどうぞ。



2014年7月12日土曜日

人工知能と生物知能

 人工知能と生物知能は何が違うのだろうか。Turing は『Computing Machinery and Intelligence』(1950)において計算機が考えることが出来るかを議論することはあまりに無意味だと主張した。Turingは人工知能の定義を「そのシステムが人間であると人間が判定すること」としてTuring Testを提案した。これは外系からシステムを観察するという点で認識論的・機能論的な立場に立った定義であるだろう。ここで人間に知能があるという前提があることにも注意されたい。しかしながら、そもそも人間に知能があるということはどう解釈されるのだろうか。


1. Turing Test

そもそも知能はどう定義されるのだろうか。Turing TestはAlan Turingが1950年に提案した人工知能の判定方法である。方法としては、判定者である人間が隔離された場所にいる人間と機械のそれぞれと自然言語での対話を行う。この時機械は人間であるかのように振る舞う。判定者が人間と機械の区別が出来なかった場合にその機械はテストに合格し、人工知能として認められる。
 
 しかしながらこのテストは様々な反論がある。例えば知能があるとはとても言えないシステムも真と判定されるという問題もあった。有名なものだとEliza Chat Botがある。面白いのでぜひ触ってみてほしい。このElizaを、知能だと思われるだろうか。もっとも重要な反論としては、Turing Testは、機械が自意識や認知能力がなくても知能であると判定しまうことがある。ここで「自意識や認知能力がある」とはstrong AIの立場に依る反論である(John Rogers Searle, 1980)。Searleは『Minds, Brains and Programs』(1980)においてstrong AIの立場を以下のように定義している。

「…強いAIによれば、コンピュータは単なる道具ではなく、正しくプログラムされたコンピュータには精神が宿るとされる」

 weak AIはそれと対象的に、自意識や認知能力ではなく問題解決器として定義される。Searleは前述の著書において、中国語の部屋という思考実験でstrong AIを不可能と示した。



2. 中国語の部屋

 中国語を理解できない人間を部屋の中に閉じ込める。外部とは遮断されており、唯一のやりとりは紙切れの交換で行われる。外から入れられる紙には中国語の文章が書かれているが、被験者は中国語を理解出来ないので、彼にはセマンティクスを持ったものとして認識されない。彼の課題はこの中国語の文章(彼にとっては意味のない記号列)に新しい記号を加えて外に戻すということである。ある記号列に対してどのような記号を書くかは部屋に置かれたマニュアルに全て書かれてある。

 実は外の世界では、この紙切れは部屋の中の彼への「質問」であった。そして部屋の中からは「回答」が返ってくるのだ。質問を投げる外にいる人間は、「中には中国語を理解する人間がいる」と考える。しかし中にいる彼は中国語など分からず、ただただマニュアル通りに、理解もせず、しかし外にいる人間は「対話」をしているのだ。

 さて、この思考実験が何をもたらすかを考えよう。
 まずこの中国語の部屋は人工知能のメタファーである。即ちマニュアルがメモリにあるコードで、何も理解せずにマニュアル通りに行動する人間がプロセッサ、紙の交換がI/Oに当たる。如何に機械が知能を持って見えたとしても、プロセッサとメモリそれぞれに知能はなく、受動的に行動するのだからstrong AIは不可能であるとSearleは主張する。weak AIは外系(即ち部屋の外の質問者)から見て知能を持って見えるものを知能と定義するので、中国語の部屋はweak AIの定義からは知能であるといえる。Searleはこの議論を持って人工知能と人間の知能は区別されるという。しかしながら、中国語の部屋の議論は人間おいては生物の知能についても同様の言及をすることが出来るだろう。
 

3. 生物知能

 生物に知能はあるのだろうか。あるとして、それはどういうメカニズムで生まれるのだろうか。まず、知能とは、心理学及びその周辺分野の研究者52人による『Mainstream Science on Intelligence』において以下のように定義されている。

A very general mental capability that, among other things, involves the ability to reason, plan, solve problems, think abstractly, comprehend complex ideas, learn quickly and learn from experience. It is not merely book learning, a narrow academic skill, or test-taking smarts. Rather, it reflects a broader and deeper capability for comprehending our surroundings—"catching on," "making sense" of things, or "figuring out" what to do.

 この定義は記述的であるが人間の「知能」をよく表していると言えるだろう。(ここで知能とは心理学者らのそれであることに注意されたい。)さて、では生物一般にこのような特徴はあるのだろうか。例えば大腸菌に知能はあるのだろうか。上の定義と照らし合わせたとしても、大腸菌の個体に知能がなくても、大腸菌の個体群もしくは生態系は知能があると言えるだろう。生物は進化というメカニズムで知能を実装している。人間などの脊椎動物は相互作用のある細胞(例えばニューロン)を多く一個体に含むためその知能を個体ベースで持っているだけだと考えることが出来る。
 大腸菌から人間まで同じ位相の「知能」を持っているとして、それをどう理解することが出来るのだろうか。先ほどの『Mainstream Science on Intelligence』は実はTuring Testと同様、機能主義的定義である。即ち、生物の知能も中国語の部屋と同様の議論が可能である。生物は外界からの刺激(紙切れ)に対して応答するが、それは「賢い」形態・行動ではなくただマニュアルに沿っているだけなのだと主張出来るだろう。

 ちなみに、マニュアルをゲノムや遺伝子に仮定することが出来る。この場合マニュアルは外界からの刺激によって書き換わるといえる。しかしそれも受動的なプロセスで、部屋の人間に依拠する知能は認められないだろう。同様の議論がコンピュータでも言える。



結句

 生物の知能と人工知能は同じ議論の下でしか定義することが出来ない。中国語の部屋の議論はstrong AIに対するアンチテーゼであるというより、strong intelligence一般に対するアンチテーゼである。転じて、生物に知能があると仮定すると、人工知能も知能があると言えるだろう。Turing Testとは、「人間に知能があるならば機械にも知能がある」という主張と考える方が厳密であるだろう。

2014年6月21日土曜日

C++11 スマートポインタの使い方・用途・サンプル

C++はガーベジコレクションがないので、動的にallocateしたオブジェクトは明示的にdeallocateしなければなりません。これを怠るとメモリリークなどもの問題が出てくるわけです。また逆に、オブジェクトを破棄したポインタを使いつづけるとnullポインタ、或いはダングリングポインタとしてエラーの原因になります。

C++において生来的ともいえるこれらの問題を解決しようというのがスマートポインタの機能です。簡単に言うと、ポインタのスコープに合わせてオブジェクトが勝手にdeallocate(deconstruct)されます。これによってオブジェクトとポインタの寿命が一致するのでメモリリーク、ダングリングポインタが防げます。

スマートポインタには何種類かあり、それぞれ異なる仕様・用途があります。以下、unique_ptr, shared_ptr, weak_ptr, auto_ptr(C++11以前)の説明をします。


1. unique_ptr

一番使われるのはunique_ptrでしょう。以上に述べたスマートポインタの特徴に加え、名の通り「指しているオブジェクトに対する唯一のポインタ」であることを保証します(低レベルで色々やれば崩せますが)。即ち、unique_ptrは他のスマートポインタからオブジェクトをコピーしたりアサインしたりすることが出来ません。

オブジェクトを他のポインタに割り当てたい場合はstd::moveを使う必要があります。これを使うと元のポインタはnullポインタになるので、やはり一つのポインタしかそれを指すことが出来ません。

以下のコードのように、いちいちdeleteなどしなくても使うことができます。


void unique_ptr_test() {
    cout << "----- unique_ptr test -----" << endl;
    std::unique_ptr<int> first(new int(1));
    std::unique_ptr<int> second(new int(2));

    // 関連して、nullptrも新しく加わった。0, NULLと区別される。
    std::unique_ptr<int> nullpo(nullptr);

    cout << "*first = " << *first << endl;
    cout << "*second = " << *second << endl;

//    std::unique_ptr<int> second = first; ERROR: コピーは出来ない。
//    second = first; ERROR: アサインも出来ない。

    // moveを用いることでオブジェクトをsecondに移すことが出来る。
    // そのとき、firstはnullptrになるので注意。
    // つまり、unique_ptrを参照できるポインタは常に一つである。(定義より)
    second = std::move(first);
    cout << endl << "second = std::move(first);" << endl << endl;
    cout << "*fisrt = " << (first? "not null" : "null") << endl;
    cout << "*second = " << *second << endl << endl;

    cout << "nullpo is " << (nullpo? "not null" : "null") << endl;

    // unique_ptrはスコープの外に出るときにdeconstructorを呼ぶ。
    {
        std::unique_ptr<Foo> locale(new Foo());
    }
}


2. shared_ptr

unique_ptrの使いやすさの一つに「オブジェクトを指す唯一のポインタ」であることがあるでしょうが、逆にそうでない方が使いやすい場合もあるでしょう。複数のスマートポインタで同じオブジェクトを指したい時に使われるのがshared_ptrです。

shared_ptrはunique_ptrと異なり、コピー・アサインをすることができます。また、オブジェクトを指している複数のshared_ptrのうちの一つだけを初期化したい場合にreset()を呼ぶことで、そのオブジェクトを破棄せずに(それによって他のポインタがnullポインタにならずに)そのポインタだけをnullポインタにすることができます。

また、共有されているオブジェクトはshared_ptrの全てがスコープから外れた時に破棄されます。



void shared_ptr_test() {
    cout << "----- shared_ptr test -----" << endl;
    std::shared_ptr<Foo> first(new Foo());
    std::shared_ptr<Foo> copy = first;

    // copyがまだあるのでresetでもオブジェクトは持続される。
    // しかしfirstはnullポインタになる。
    first.reset();
    cout << "first = " << (first? "not null" : "null") << endl;
    cout << "copy = " << (first? "not null" : "null") << endl;

    // copyもreset()が呼ばれるとdestructor
    copy.reset();
}


3. weak_ptr

 weak_ptrはshared_ptrをサポートするスマートポインタです。
weak_ptrはshared_ptrが指しているオブジェクトを同様に指すことが出来ます。しかし、先ほどshared_ptrの指すオブジェクトは、「shared_ptrの全てがスコープから外れたら破棄される」とありましたが、つまりweak_ptrが指していても、shared_ptrが全てなくなれば破棄される、ということです。

ではweak_ptrは何に使われるのかというと、 shared_ptrを用いてオブジェクトを破棄して新しいオブジェクトをconstructしたり、という流れの中で使われます。つまり、weak_ptrでshared_ptrのオブジェクトを参照しておき、それからshared_ptrで新しいオブジェクトをallocateすると、weak_ptrはNullを指すことになります。使ってみるとこれが便利な場合が結構あります。



void weak_ptr_test() {
    cout << "----- weak_ptr test -----" << endl;


    // 通常のポインタはDangling pointerとなるリスクがある。
    // 例えばここでrefはdangling pointerである。
    int* ptr = new int(10);
    int* ref = ptr;
    delete ptr;

    // それに対して、
    // weak_ptrは対象のオブジェクトがdeallocateされたかをexpired(), lock()で確認することが出来る。

    std::shared_ptr<int> sptr;
    // takes ownership of pointer
    sptr.reset(new int(10));

    // weak1は*sptrを参照はするが、保持はしない。
    std::weak_ptr<int> weak1 = sptr;

    // 前のオブジェクトを破棄し、新しいオブジェクトを作る。
    // ここでweak1がshared_ptrなら一緒に5を指すことになるが、ここではweak_ptrなので参照オブジェクトがなくなる。
    sptr.reset(new int(5));

    // 5を指すweak_ptr
    std::weak_ptr<int> weak2 = sptr;


    // weak1の指していたオブジェクトがdeallocateされたかはlock()で確認することが出来る。
    if ( auto tmp = weak1.lock() ) {
        std::cout << "weak1.lock() = " << *tmp << '\n';
    } else {
        std::cout << "weak1 is expired\n";
    }

    if ( auto tmp = weak2.lock() ) {
        std::cout << "weak2.lock() = " << *tmp << '\n';
    } else {
        std::cout << "weak2 is expired\n";
    }

}


4. auto_ptr (C++11以前)

 auto_ptrはレガシーです。簡単に言うならunique_ptrの下位互換です。C++11以前からあるので(これを発展させたものが今まで説明してきたスマートポインタら)、C++11を使いたくない事情がある場合に代用として使えます。基本的に使い方はunique_ptrと同じです。ただ隠蔽構造がやや不完全で、例えば以下のコードだとy = xでunique_ptrのy = std::move(x)に当たり、ここでxはnullポインタになるので、なかなか注意が必要な構造をしています。



void auto_ptr_test() {
    cout << "----- auto_ptr test -----" << endl;
    auto_ptr<int> x(new int(5));
    auto_ptr<int> y;

    y = x;

    cout << "x is " << (x.get() ? "not null" : "null") << endl; // Print NULL
    cout << "y is " << (y.get() ? "not null" : "null") << endl; // Print non-NULL address i
}


スマートポインタは通常のポインタと比べてそんなに遅くないそうです(アセンブリにして追加一行程度とのこと)。特にパフォーマンスが求められていない部分のコードは手軽く使っていけるようです。

2014年6月10日火曜日

Zobrist Hashing

Zobrist Hashingは将棋やチェスなどで用いられる、状態をハッシュ値に落とし込む方法です。

というのも将棋やチェスのような状態のハッシュ値を計算する場合、n進数や辞書順によるハッシュ関数では状態空間に対してハッシュ値を不偏的に散らすことはなかなか難しいです。そこでZobrist Hashingは乱数とXORを使って不偏性を作り出します。


WikipediaのZobrist Hashingの擬似コードを引用します。


   constant indices
       white_pawn := 1
       white_rook := 2
       # etc.
       black_king := 12
   
   function init_zobrist():
       # fill a table of random numbers/bitstrings
       table := a 2-d array of size 64×12
       for i from 1 to 64:  # loop over the board, represented as a linear array
           for j from 1 to 12:      # loop over the pieces
               table[i][j] = random_bitstring()
   
   function hash(board):
       h := 0
       for i from 1 to 64:      # loop over the board positions
           if board[i] != empty:
               j := the piece at board[i], as listed in the constant indices, above
               h := h XOR table[i][j]
       return h
(Wikipediaより: http://en.wikipedia.org/wiki/Zobrist_hashing)


・init_zobrist
まず下準備として、予めパズルの各マスに対してランダムビットstringを定義する。
例えば将棋なら、
7六に歩がある状態を 0100 0111 のように定義する。
7七に角がある状態を 1001 1100...
のように全てのマスの、全てのありうる状態に対するキーの値をテーブルに保存する。(以後テーブル値とする。)


・hash(board)
全てのマスの状態に対して定義されたテーブル値をビット毎のXORでかけていく。


さて、このZobrist Hashingの特徴を見ていきましょう。

・まず、Zobrist HashingはPerfect Hashingである保証は全くありません。盤が違う状態でも同じハッシュ値になり得ます。簡単な例だと
0000 XOR 0011 = 0011
0100 XOR 0111 = 0011
ですので。

・そこから一歩進んで、このハッシュ関数は同じフレームワークの中でビット長を変えることでハッシュの重複度を変化させることが出来ます。つまり、ビットを長くするほど違う盤の状態が同じハッシュ値を持つ割合(確率)を小さくさせることが出来ます。これは当然計算速度とメモリ量のトレードオフになります。

・n進数や辞書順によるハッシュ関数と比較して、盤の状態に対して偏りのないハッシュ値が得られることが多い。Bitwise XORなのでハッシュ値のビットストリングの各桁は、全てのマスの状態の関数なので、全てのマスのテーブル値を参照した結果の値といえる。ただしここで注意しなければならないのは、必ず偏りがないハッシュになるとは限らないということです。それは状態空間の性質にもよりますし、乱数の揺れにも依存します。



天才的な発想ですよね。どの位実用されているのかはよく知らないのですが、こういうアイディアの出せる人間になりたいものですね。




C++で簡単なサンプルを実装をしたものが以下のコードです。





/*
 * zobrist.cc
 *
 * Short sample to test Zobrist hashing.
 * Zobrist hashing is a hash function construction for abstract board games.
 *
 *
 *  Created on: Jun 10, 2014
 *      Author: Yuu Jinnai
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define INDICES 16
#define SIZE 32

void initZobrist(int* table);
void initRandomBoard(int* board);
int hash(int* board);

int* table;

int main() {

 srand(time(NULL));
 table = new int[SIZE*INDICES];
 initZobrist(table);

 int* board = new int[SIZE];
 for (int i = 0; i < 10; ++i) {
  initRandomBoard(board);
  printf("hash(board) = %d\n\n", hash(board));
 }

}

void initZobrist(int* table) {
 for (int i = 0; i < SIZE; ++i) {
  for (int j = 0; j < INDICES; ++j) {
   table[i+SIZE*j] = rand();
   printf("table[%d][%d] = %d\n", i, j, table[i+SIZE*j]);
  }
 }
}

void initRandomBoard(int* board) {
 for (int i = 0; i < SIZE; ++i) {
   board[i] = rand() % INDICES;
   printf("%d ", board[i]);
 }
 printf("\n");
}

int hash(int* board) {
 int h = 0;
 for (int i = 0; i < SIZE; ++i) {
  h = (h ^ table[i+SIZE*board[i]]);
 }
 return h;
}


2014年5月29日木曜日

コンピュータサイエンス

コンピュータサイエンスというのは色々なパラダイムが共存しているように思えます。

論理学や離散数学の延長といえるものもありますし、UIなど認知に伸びていく分野も多いですし、そもそもサイエンスといいつつ工学的な応用が非常に大きな部分を占めているように思えます。そうするとコンピュータサイエンスというくくりは大きすぎるのかもしれませんね。

それでも、ゴールは多岐に渡っても学ぶべきスキルというのはある程度収束するものだと思います。つまり共有できるツールや枠組みというのはあるのでしょう。やはり基礎から学ぶというのは定石の一つだと思います。イメージとしてはピラミッド型に伸びている科学技術の要の部分から学ぶということです。

さて、では基礎を学ぼうとしたときに、じゃあ基礎って何なんでしょうか。思うに本屋に並ぶ本はアプリケーションレベルのものばかりで、むしろ末端を深く解説するものが置かれている印象です。だからといってアプリケーションを作りたい人が記号論理学とかを学ぶにはモチベーションがないとやってけないように思えます。


ということでまずはコンピュータサイエンスを俯瞰するという作業がまず必要になるでしょう。どういう分野があって、どういう内容をやっていて、それらはどう関連しているのか。

お勧めの教科書はこちら。



一冊でだいたいの俯瞰が出来るようになります。
Cやjavaなどの高レベル言語が物理レベルまでどう翻訳されていくか、コンピュータが下部構造をいかに隠蔽してあるか、丹念に説明されています。


あとはADUniがおすすめです。
これは元々、他分野のバックグラウンドを持つ学生に一年間で情報科学を一通り教えるというコンセプトで生まれたプログラムです。各分野を体系立って学ぶことが出来ます。前述の教科書を見て面白いと思う分野があればこっちでもっと深く学ぶというのが良い方法だと思います。



2014年5月24日土曜日

プロファイラを使ってみよう

プロファイラって使ってますか?

なんか思ったよりもっさり動いているなぁという時に思いつくがままに改良してみて、あまり上手くいかないというのは、改良している部分がプログラムのボトルネックではないからです。

しかしプログラムの中のどの部分が時間を食っているのかは分かりづらいこともあります。

そこで便利なのがプロファイラ。
プロファイラは実行されたプログラムの関数ごとの計算時間、呼び出し回数などなとを計測するかなり便利な代物です。

ここでは例としてgnuのg++プロファイラ、gprofの使い方を説明します。
使い方の手順としては、


1. -pgオプションをつけてコンパイルする。 
g++ -pg main.cc

2. 実行する。 
./a.out

3. gprofを実行する。
gprof a.out


とするだけでプログラムの各関数の消費時間が空間的に理解できるように表示されます。

gprof出力の全文を載せるとちょっと詳細過ぎるのでここでは一番に見るべき情報に絞ります。

Flat profile: 各関数で結局どのくらい時間がかかったのか。
Call graph: 各関数がどのように他の関数から呼ばれたか。


Flat profile:

Each sample counts as 0.01 seconds.
%        cumulative self           self    total
time  seconds       seconds calls  s/call  s/call  name
67.15 30.77         30.77     2    15.39  23.14    f2
33.82 46.27         15.50     1    15.50  15.50    f1
0.07   46.30         0.03                          main

Call graph (explanation follows)

granularity: each sample hit covers 2 byte(s) for 0.02% of 46.30 seconds

index   %time        self  children  called  name

[1]     100.0        0.03   46.27             main [1]
                     30.77  15.50     2/2      f2 [2]
-----------------------------------------------------
                     30.77  15.50     2/2      main [1]
[2]     99.9         30.77  15.50     2      f2 [2]
                     15.50   0.00     1/1      f11 [3]
----------------------------------------------------
                     15.50   0.00     1/1      f2 [2]
[3]        33.5      15.50 0.00       1      f1 [3]
-----------------------------------------------
この辺りを見ればどの関数を手直しすべきか分かると思います。
プロファイラはユニットテストみたいに使うと便利なんじゃないかと思います。
つまり、


1. コードを改善する。

2. 実行してプロファイラにかける。

3. プロフィールを分析し、次に改善すべき関数を決める。


のイテレーションを行えば効率良く質の高いコードがかけます。

とにかくはしから改善していけばいいじゃないか、という考えもありますが、アムダールの法則をみるに、ボトルネックとなっている関数から改善するという考えの方がプログラマ的なんじゃないかなと思います。

複数人の開発なら端から改善していく、TOYOTA生産方式というのは有用でしょうが、一人の開発の場合資源の投下場所は考慮すべきでしょう。