ミンスキーに話を聞いてきた

f:id:awakia-n:20090622235129j:image

人工知能という分野を築いたといっても過言ではんはない人Marvin Minskyがいま日本に来ていて、その講演を聞くどころか直接話す機会(ついでにノートにサインもしてもらった)まであったので、今頭に残ってる話をできるだけ書いておこうと思う。自分の英語力と理解力のフィルターを通っているので多少の間違いがあるかもしれない。


とりあえず会った印象を書いておく。ミンスキーさんは80を超えてるとは思えないほど背筋が伸びていて話し方もしっかりしていた。普通の話題をしていれば気さくで面白い人だけれど、議論をしたらぜんぜん勝てない・・・。パーセプトロン限界説で人工知能研究が下火になったってのもうなずけるような力をもった人だった。


長い間生きているだけあっていろいろと現状に不満も抱えているようだった。例としては次の三つ。
今の学校制度で、子供が難しい問題を長い時間考えるということがなくなったこと。
今の研究者が昔(1960年代ごろ)やられてたことをちゃんと知りもせずに同じようなことをして失敗していること。
人工知能研究が細分化され、各研究者がある一つの理論に固執していること。


後はQ&A形式で書いておく。

感情(Emotion)は知能をもった機械を作る上で大切だと思いますか?

その質問自体が私の講演をよく理解していない。
多くの人が感情は複雑と思っているけれど、むしろ感情なんて幻想。感情(Emotion)と考え(Thinking)の違いなんてない。

講演でニューラルネットや統計的学習などいろいろ否定していましたが、どうすれば人間のような機械ができると思いますか?

In the Book("The Emotion Machine")

ほんとですか!?もしやったら何年ぐらいでできると思います?

それは、どれだけ研究をハードにやるかにかかってるよ。


(AIの)最終的なゴールは何ですか?

あらゆるシチュエーションに適切に対応できる機械を作ること。
別に人を作るということではない。

人工知能の研究を始めたばかりの若いころも「人間を作ろう」というような考えをもったことはなかったのですか?

ないよ。むしろ他のことに興味があった。数学とかエンジニアリングとか。

じゃぁ何で人工知能を研究したのですか?

運がよかった。正しい時に正しい場所にいたからだよ。
特に〜〜の研究所にいて、・・・(人の名前は誰だったか忘れたけど3人ぐらいあげていた)。



他にも難しい話(やどうでもいい話)をしていたのだけれど何を言っているかよく把握できなかったので、ミンスキーさんがこれをやれば人工知能はできると豪語している"The Emotion Machine"を読んでからまとめてみようと思う。

ミンスキー博士の脳の探検 ―常識・感情・自己とは―The Emotion Machine: Commonsense Thinking, Artificial Intelligence, and the Future of the Human Mind

for文で降順にループを回す

0,1,2,...じゃなくて...,2,1,0って降順にループを回したい時どうするかって話。


例えば、CとかJavaで以下の文は

for (int i = 0; i < n; i++)

pythonでは

for i in xrange(n)

って書く。じゃぁ

for (int i = n-1; i >= 0; i--)

は、どうやるんだよってので結構悩んだ。


さっそく答え。

for i in reversed(xrange(n))

reversed使うだけだった。
ここで、rangeじゃなくてxrangeを使うのが効果あるのかは要調査だけど。


てか、"python for 降順"じゃなくて"python for 逆順"で検索すれば一瞬ででてきた・・・。

アメリカ留学失敗しました。

そろそろ、自分の中で気持ちの整理もできたし、新学期が始まる前にけじめをつけるためにも、このお題について書こうと思う。

落ちた理由

TOEFLGRE、エッセイが出願に必要なメインのものだから、英語力の問題ももちろんあったと思う。でも、それ以上に自分がエッセイでしっかりしたメッセージを書けなかったからだと思ってる。


大学入るころ、自分が一番やりたかったのは
「人間のように色んなことを学んだり感じたりできる、コンピュータを作りたい」
ってことだった。それで、自分は情報分野に進んだ。


ただ、大学に入って勉強してみると、逆に、夢が遠のいて狭まった。


全然人間に到達してないような既存の理論ですら、自分が理解できない部分が死ぬほどある。

さらに、自分がやりたいと思ってることをそのままやってるような研究をしてる人がいない・・・。もちろん、顔認識とか、ロボットとか近いところはあるんだけれども、見込みがないのか、研究費がとれないのか、まぁこんな単純なことをそのまま取り組んでる人いない。


これじゃぁ、自分の目標を追い求めることなんて無理。せめて、一緒に自分の目標とするところに向かってくれる仲間がほしい。
それが多分アメリカに行こうとした一番の理由だったように思う。ただ、このアプローチが今考えれば甘えていたなぁと思うんだけれども・・・。

具体的には・・・

アメリカの大学の出願時に求められるエッセイでは、

  • あなたは何がやりたいのか?
  • あなたがやりたいことは何故重要なのか?
  • あなたのどこにそれをやる資質があるのか?

といったことがストレートに聞かれる。

正直、自分はこのどれにも歯切れの良い答えが導き出せなかったように思う。

あなたは何がやりたいのか?

これは大きくは「人間のように色んなことを学んだり感じたりできる、コンピュータを作りたい」でいいと思う。

でもこれだけでは、
「で、どうすれば実現できるの?」
「あなたは、そのために何をやるの?」
ってことにぜんぜん答えれてない。

自分は生物をもっと研究するといったことを書いてみたけれど、もうちょっと深く突っ込めたかもしれないと思う。

あなたがやりたいことは何故重要なのか?

これは困った。
「コンピュータが見た時から、これで人間と同じことできないかな」
って思うのは自然な流れだと思っていて、別に大した理由もなかった。
「ただ自分がやりたいと思った」ってだけだ。

でも、もしかしたら、素直にそう書いておけばこれはこれでよかったのかもしれない。

あなたのどこにそれをやる資質があるのか?

自分では、大学では結構がんばってきたつもりだった。アイデアが浮かんできたときのために必要な実装力をつけるとか、大まかに機械学習のアルゴリズムを網羅するとか、情報科学をやるために基礎的な素養はつけてきたと思う。

でも、書いてるうちに気づいたんだけれど、直接的に自分の目標につながるようなことは何一つできてなかった。
その時は、論文も一つもかけてなかったし、他にも目立った業績も何もなかったしね。

最後に

やっぱり、後悔はあるよ。

  • いろんなことに手広げて、留学だけに対してしっかり準備できなかったこと
  • 願書を出した直後にやった卒論を書いて添削をされる作業を経て、自分のエッセイに欠けていたのがわかったこと
  • 結局今何事もなかったように普通に人生を歩めていていること

実は最後のが一番苦しい。結局自分の中で留学の重要性が明確化してなかった。そんなんじゃ受かっても失礼だわ。落ちる要素しかない。


でも、挑戦してみたことでわかったこともある。

  • 自分の今ある環境でも、もっともっとできることがあるってわかったこと
  • 自分が何を大切にしてるのかが、ちょっとだけ明確になったこと

結局これから自分がどうするべきか、まだちゃんと答えは出てないけど、
前よりも受け身じゃない道がとれるようになった気がする。


応援してくれた皆さん、留学しようとしていたせいで迷惑をかけてしまった皆さん、ごめんなさい。それと、ありがとうございました。

中央値乱択アルゴリズム

O(n)のはず。
結構昔に作ったものだけど、ブログにメモとして載せとく。
確か、アルゴリズムデザインって本を参照したはず。

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;

int select(vector<int> S, int k) {
  int n = S.size();
  int i = rand() % n; // n/2;
  vector<int> R, T;
  for (int j = 0; j < n; j++) {
    if (S[j] < S[i]) R.push_back(S[j]);
    else if (S[j] > S[i]) T.push_back(S[j]);
  }
  if (R.size() > k) return select(R, k);
  else if (n-T.size() <= k) return select(T, k-n+T.size());
  else return S[i];
}

int main() {
  srand(time(NULL));
  int a[] = {2,1,3,0,4,3,1};
  vector<int> S;
  for (int i = 0; i < sizeof(a)/sizeof(a[0]); i++) {
    S.push_back(a[i]);
  }
  for (int i = 0; i < S.size(); i++) {
    cout << i+1 << "th value : " << select(S, i) << endl;
  }
  cout << "median : " << select(S, S.size()/2) << endl;
  return 0;
}

中央値というか、n番目の数値を乱択で求めるアルゴリズムだけど。
ま、でも、アルゴリズム本のクイックソート扱った後の練習問題でよく、「O(n)の中央値選択アルゴリズムを示せ」とか書いてあるから、それの答えってことで。

会津から帰ってきた。

一日延泊して埼玉大の人たちと会津を満喫してきて、今日帰ってきた。紅葉がきれいだったのと羊羹がうまかったので満足。


今日はICPC行ってきた適当な感想を書いてみる。ちなみに、自分たちはna[^k]という名前のチームで出てました。自分はアメリカの大学院に行くこととかも考えていて、来年出れるかどうかわからないから、結構大切なICPCだった。


やっぱり、今回は国内予選でミスってしまったせいでOBOG合宿いけなかったので、上位層の常連チームの人たちと久しぶりにちゃんと話す機会があったのでそれが一番嬉しかった。特にHITORI++の人とか話したかったのでそれが達成できてよかった。


本番の大会の方は自分たちは8位だった。国内大学順位2位を目指していたので、会津大にそれをとられたのは残念だったけど、問題数で差をつけられたので、もうそれは仕方がない。ほんと会津大の人たちは世界大会にいけるといいなと思った。
今回は1年、2年が強くて目立ってた。てか強さというか、テンションのせいでかもしれないけど。東大はもちろん大阪大のImoもすごかったしな。東北大も今年は強かったけど、あれは情報オリンピック関係あるのかな?
kkntkrは前日から全体的にお疲れムードで2位に終わってしまった。でも初速はダントツだった。隣にいたから実は結構あせらされた。自分はにゃぁさんにはとてもお世話になっていて一番になってほしいと思っていたのでそこはちょっと残念。ただ、HITORI++も名前入力欄チームも練習がんばってるの知ってるから、複雑なところなのだけれども。kkntkrは来週台北でがんばってほしい。__________も韓国でガンバレ!


Javaチャレンジはいつもどおり運ゲーだった。あの鬼のようなHITORI++がはまって動けなくなって奇跡的に勝てた!・・・と思いきや次の試合では今度はこっちが動けなくなり、優勝チームのActiveJにあっさり負けてしまった。ブロックされたとき対策はしてたはずなのに、 何故はまってしまったのかはわからないんだけども。


予想外の人の集まりに10mlしかガソリンが入らなかった裏ICPC。自分は、なぜか盛り上がりを見せた腕相撲に参加したのと、kkntkrや関西の大学の人たちと話をしてた。

腕相撲とか大の苦手なのに、打倒チャンピオンの人海戦術の一員として借り出されてしまった。チャンピオンがなかなか止めを刺してくれなかったせいで、腕というか肩の付け根が筋肉痛になって次の日とても惨めだった。チャンピオンが自分のチームのコーチにも負けなかったのに女の子にはあっさり負けてるところが面白かったw

京大のd3xpの人はなんかすごいがんばっているようでICPCのテクニックを受け継ぐためのサークルを作ろうとしていて、すごく応援したくなった。実は早稲田も同じ様な状況で、ある程度強いチームがいるときもまったく個人技だけで出ているので、毎年強いということがない。うちらのチームも前にサークルというような組織を作ろうとしたけれども、自分たちの負担が大きかったのと、周りのモチベーションをあげることができなかったので破綻してしまった。京大ではうまくいくことを願う。

imosはもちろん、Imoの女の子二人とも話した。自分は関西弁大好きなので、あの二人が普通に話してても面白かった。応援だけしてると言ってた女の子たちもなんか来年は自分たちもがんばろうって言うムードが出てたのでちょっと感動した。
二人のために書いておくと、うちのチームが2年のとき出たとき、id:nobu-qが一人の力だけで国内予選突破してくれて、自分はまったく何もできなかった。あれから申し訳なさと悔しさでいろいろ勉強してきて、追いついたとはいかないまでもメンバーとして役に立つようにはなったと思うので、メインの人をサポートする視点でのアドバイス。


自分はプログラミングとかコンピュータ関係のことをちゃんとやるようになったのは大学はじめなのに対して、やってる人は小学生からプログラミングやってたりするので、正直埋まらない差は埋まらないことはもう最初っから認めちゃった方がいいと思う。
だって、おんなじことを学ぶのにもその人たちの何十倍も時間がかかっちゃうから、最初の時点で差が離れてるのに、同じように努力してももっと差が離れてくから。
でも、昔からやってる人でもICPCは結構特殊だし、どんな人にも苦手な分野とかあると思うから、imosの苦手なところとかを意識して重点的に練習するといいと思う。ただ後追いするだけだとやっぱ精神的にもきついし、続かないと思うから。
例えば上位チームが公開してくれてるライブラリでimosが知らないアルゴリズムを覚えて使えるようにするとか。今回のICPCで言うとProblemC以降の問題を一人で1問通してくれるだけで相当ありがたいと思うんだよね。
練習方法自体はみんなが言うようにPKUとかTopCoderとかでいいと思うけど、やっぱ何意識するかで結構同じ練習も変わってくると思う。


あぁ、来年も出たいなぁ・・・。

ページランクのメモリに乗る場合の実装

チョイ暇だったので、30分ぐらいで作ってみた。本当はディスク使うからこんな風にstlvector使ってやればいいってもんじゃないんだけど・・・。
検証してないから間違ってるかもしれない。
詳しい解説は・・・後で書くかもしれない。


実装的にはTrustRankとかにも使えるように、初期&一定確率で飛ばすノードを指定できるようにしといた。何にも指定しないと、全部に平等に飛ばす。

C++ソース

pagerank.cpp

#include <iostream>
#include <vector>
using namespace std;

const double EPS = 1e-9;
typedef float number;
typedef vector<vector<int> > adj_t; // 隣接リスト方式で作る
class PageRank {
private:
  int n; // ページ数
  adj_t a; // リンクデータ
  number alpha; // ランダムに飛ぶ確率
  vector<int> initial; // 最初に値を振るノード
  
  inline double sq(double x) { return x*x; }
  double diff(const vector<number>& prev, const vector<number>& cur) {
    double ret = 0.0;
    for (int i = 0; i < n; i++)
      ret += sq(cur[i]-prev[i]);
    return ret;
  }
public:
  PageRank(int n, number alpha): n(n), a(n), alpha(alpha) {
    for (int i = 0; i < n; i++) initial.push_back(i);
  }
  PageRank(int n, number alpha, vector<int> initial): n(n), a(n), alpha(alpha), initial(initial) {}
  void add_link(int from, int to) {
    a[from].push_back(to);
  }
  vector<number> calc() {
    //シーケンシャルアクセス用にソートしておく。(HDでは重要、今回はほぼ意味なし)
    for (int i = 0; i < n; i++) sort(a[i].begin(), a[i].end());
    
    const int ini_size = initial.size();
    const number beta = 1.0/ini_size; // ベータはつまりこういう意味
    vector<number> prev(n), cur(n, beta);
    do {
      cur.swap(prev);
      cur.clear();
      cur.resize(n);
      for (int i = 0; i < n; i++) {
        const int size = a[i].size();
        const double val = 1.0/size * (1.0-alpha);
        for (int j = 0, ; j < size; j++)
          cur[a[i][j]] += prev[i]*val;
      }
      const number alphabeta = alpha*beta;
      for (int i = 0; i < ini_size; i++)
        cur[initial[i]] += alphabeta;
      
      //for debug
      for (int i = 0; i < n; i++) cerr<<prev[i]<<" "; cerr<<endl;
    } while (diff(prev,cur) > EPS);
    return cur;
  }
};

int main() {
  const number alpha = 0.15;
  int n; cin>>n; // ノード数
  PageRank pr(n, alpha);
  for (int i = 0; i < n; i++) {
    int m; cin>>m;
    assert(m > 0); // 終端ノードがないことを保障
    for (int j = 0; j < m; j++) {
      int k; cin>>k;
      pr.add_link(i,k);
    }
  }
  vector<number> result = pr.calc();
  number sum = 0.0;
  cout<<"\nresult:"<<endl;
  for (int i = 0; i < result.size(); i++) {
    sum += result[i];
    cout<<result[i]<<endl;
  }
  cout<<"sum="<<sum<<endl; // 1にならないとおかしい
  return 0;
}

入力データ例

input.txt

4
3 1 2 3
2 2 3
2 1 3
1 0

形式はこんな感じ

n
m1 k_1,1 k_1,2 ... k_1,m1
m2 k_2,1 k_2,2 ... k_2,m2
 .                     .
 .                     .
 .                     .
mn k_n,1 k_n,2 ... k_n,mn

nはページ数で番号は0からn-1までで振られる。
mi[i=1,2,...,n]は各ページがリンクしているページ数で、
k_i,j[j=1,2,...,mn]は指しているページ番号。
注意点としてmiは1以上じゃないといけない。これは、どこにもリンクしてないページはダメだよってこと。実用でもこういうのを取り除いて計算してから、取り除いたページは計算が終わった後で、元の位置に戻してうまく値を割り振るってことが行われたりする。
まぁ、これを取り除かないで、イテレーションのたびに合計が1になるように正規化する手法もあるんだけど。

実行例

$./pagerank < input.txt
0.25 0.25 0.25 0.25
0.25 0.214583 0.214583 0.320833
0.310208 0.199531 0.199531 0.290729
0.28462 0.210193 0.210193 0.294994
0.288245 0.207474 0.207474 0.296806
0.289785 0.207346 0.207346 0.295523
0.288694 0.207728 0.207728 0.29585
0.288972 0.207581 0.207581 0.295865
0.288986 0.207597 0.207597 0.295819
0.288946 0.207608 0.207608 0.295837

result:
0.288961
0.207602
0.207602
0.295835
sum=1

追記

同じ研究室の友達の検証によるとあっていたっぽい。よかった。
ちなみに、このinitialにページ一個だけ渡してやるとPersonalRankというのになるらしい。

新WindowsPCにインストールするものメモ

気が向いたらor必要になったら