Mahout 0.6のユーザベースレコメンダー

諸般の事情により古いMahout 0.6を使ってちょっと大きいデータでユーザベースレコメンダーの実験をしていたら、いつも一定の進捗で計算が止まってしまう…。ので、どこで止まっているのか調べたら、GenericItemPreferenceArrayクラスのselectionSortメソッドだった。メンバ変数のlong[] idsを与えられた基準でソートするのだが、O(n^2)のアルゴリズムなので、idsが凄い長いと、現実的な時間では終わらないようだ。

メソッド冒頭のコメントをみると、

// I think this sort will prove to be too dumb, but, it's in place and OK for tiny, mostly sorted data

とあり…。

で、試しにヒープソートに変えてみたら動いたのでメモ。

修正前

  private void selectionSort(int type) {
    // I think this sort will prove to be too dumb, but, it's in place and OK for tiny, mostly sorted data
    int max = length();
    boolean sorted = true;
    for (int i = 1; i < max; i++) {
      if (isLess(i, i - 1, type)) {
        sorted = false;
        break;
      }
    }
    if (sorted) {
      return;
    }
    for (int i = 0; i < max; i++) {
      int min = i;
      for (int j = i + 1; j < max; j++) {
        if (isLess(j, min, type)) {
          min = j;
        }
      }
      if (i != min) {
        swap(i, min);
      }
    }
  }

修正後

  private void selectionSort(int type) {
    int max = length();
    boolean sorted = true;
    for (int i = 1; i < max; i++) {
      if (isLess(i, i - 1, type)) {
        sorted = false;
        break;
      }
    }
    if (sorted) {
      return;
    }
    for(int i = 0; i < max; i++){
      int j = i;
      while(j > 0){
        int parent = (j-1)/2;
        if(isLess(parent, j, type)){          
          swap(j, parent);
        }
        j = parent;
      }
    }
    int toIdx = max - 1;
    while(toIdx > 0){
      swap(0, toIdx);
      int j = 0;
      int lChild = 2 * j + 1;
      int rChild = lChild + 1;          
      while(lChild < toIdx){
        int child = 0;
        if(rChild < toIdx && isLess(lChild, rChild, type)){
          child = rChild;
        }
        else{
          child = lChild;
        }
        if(isLess(j, child, type)){
          swap(child, j);
        }
        j = child;
        lChild = 2 * j + 1;
        rChild = lChild + 1;            
      }
      toIdx--;
    }    
  }

立方体の蛇パズルを解くプログラム

ばらしちゃったら元に戻せなくなってしまえなくなったパズルがもう一つあったので、これも解くプログラムを書いた(gist)。

himilk chocolateパズルの全列挙

ハイミルクチョコレートパズルの解答を全列挙するプログラム。

ピースの形は、ファイルから読み込めるようになっているので、別の箱詰めパズルで困った時にも使えるはず。ただし、ハイミルクチョコレートパズルは、長方形のピースがくっついた形なので、90度回転は無し。(裏返すのは有り)

• 単純に全列挙→終わらず
• 反転で同じ形になるものは、調べない→20分くらい
• ピースを置いた後に、「残りの空きスペースの最小面積 >= ピースの最小面積」のチェック→1分ちょっと

上下・左右の反転で重なる4通りが重複して出てきてしまうけど、これを検知して除外するにはどうしたら良いんだろう。

データサイエンスのお奨め教科書。統計屋さん的視点から

知人に、確率・統計を勉強するにはどんなん読んだら良いんかね？と聞かれたので、まとめる。

線形代数

統計を勉強しようと思ったら、先ず、線形代数を勉強するのが良いと思う。回帰分析とか主成分分析とか多次元尺度構成法とか、こういう有名ドコロが一発で分かる。線形代数を知らずに統計の本で「コレコレの計算で出てきた値が第一主成分だよ」みたいな説明を何回くり返し読んでも、多分、一生理解出来無いと思う。対称行列は直交行列で対角化出来るよね、とか、これは射影行列の形だね、とかが自然に分かるようになってから、統計の本を読むとよく理解出来る。

で、線形代数のお奨めはこれ。

プログラミングのための線形代数

プログラミングのための…とあるんだけど、確か、殆どプログラミングの話は出てこなかった気がする。唯一覚えているのは、線形代数の計算は世界中のガチ勢が凌ぎを削っている世界であり素人が手を出したら火傷確実なので、ライブラリを使いなさい、という忠告である。この他に、

統計のための行列代数 上

というのもある。これも、統計のための…とあるんだけど、統計の話は全然出て来ない。なんてこっちゃ。

数理統計学

数理統計学の教科書は、もの凄く沢山出ているし、多分、入門書の内容というのがほぼ確立されているので大抵の本で同じような内容なんだけど、私のお奨めは、これである。

数理統計学 (数学シリーズ)

とにかく何かしら数理統計学の本を一冊呼んで、統計屋さんがどういう風に問題を設定しているのかを把握しておくと、良いと思う。その他に、

数理統計学―データ解析の方法

現代数理統計学 (創文社現代経済学選書)

というのも良い本である。

ベイズ統計

パターン認識と機械学習 上

みんな大好きPRML。この本の良い所は、練習問題がとにかく沢山ある事である。この本の練習問題を全部解いたら、あなたも今日からデータサイエンティスト！

Information Theory, Inference and Learning Algorithms

この本は名著だと思う。話題の選び方も面白いし、単なる数学的な説明だけでなくて直観的な説明が豊富である。これも練習問題が沢山ある上に、一部には解答が付いているので、自習し易いかもしれない。著者は物理学者なので、統計の門外漢にも読み易いのではないかと思う。個人的にはPRMLよりも推しであるんだけど、勉強会やってますみたいな話は見たことないな。

おまけ：解析と確率論

統計をやるには、微分積分=解析も必要である。解析学も、大抵の入門的教科書で似たような内容なんだけど、次の本は凄く特徴的で変わったアプローチで、内容もとても面白い。昔の人がどういう風に考えていたかが、少し分かる気がする。

解析教程・上 新装版

統計学は確率論に基いているので、当然、厳密な確率論を知らないよりは知っていた方が良い。が、厳密な確率論=測度論的確率論はメチャクチャ難しい。もし、勉強するならば、易しいんだけどキチンと誤魔化さずに書いている次の本がお奨め。

A First Look at Rigorous Probability Theory

Raspberry Pi：SSHで接続出来るようになるまで

概要

Raspberry Piを箱から出して、自宅LANの中でSSH接続出来るようになるまでの手順メモ。

用意したもの

• Raspberry Pi Type B
• SD Card 8GB(Amazonのバルク)
• micro USBケーブル(スマホに付いてた奴)
• USB電源アダプタ(iPadに付いてた奴)

RPiに繋ぐモニタ、キーボードは用意せず、LAN経由のsshログインだけで何とかする。

SDカードの準備

RPiを動かすためのOSをSDカードにインストールする。RPiのサイトから、ディスクイメージを落としてきて、SDカードに書き込む。
まず、ディスクイメージをRaspberry Pi|Downloadsから落とす。OSは、Raspbian wheezyを選択した。無難に。
次に、SDカードをMacに差す。

$ diskutil list

とすると、SDカードが/dev/disk#(#は数字)と認識されているはずなので、それを確認。で、対象ディスクをアンマウントした後で、ddコマンドでディスクイメージをごそっと書き込む。

$ diskutil unmountDisk /dev/<disk#>
$ sudo dd bs=1m if=<イメージファイル> of=/dev/<disk#>

参考サイト：eLinux.org|RPi Easy SD Card Setup

RPiの起動とIPアドレスの特定

SDカードをRPiに差し込んで、micro USB経由で給電すれば、勝手に起動する。起動時に勝手にsshdが立ち上がっていて、

• id:pi
• password:raspberry

でログイン可能。
IPアドレスはDHCPで勝手に割り当てられていて不明なので、192.168.3.1から順にpingを絨毯爆撃。

固定IPの設定

IPを固定にする。/etc/network/interfacesファイルをいじる。

auto lo
iface lo inet loopback

auto eth0 
iface eth0 inet static 
  address 192.168.3.101
  netmask 255.255.255.0
  network 192.168.3.0
  gateway 192.168.3.1
  dns-nameservers 192.168.3.1
  broadcast 192.168.3.255 

allow-hotplug wlan0
iface wlan0 inet manual
wpa-roam /etc/wpa_supplicant/wpa_supplicant.conf
iface default inet dhcp

eth0がイーサネットポートなので、こいつの設定をちゃんと書けば良い。interfacesファイルの文法は、Debian リファレンス|5.5.2. "/etc/network/interfaces" の基本的なシンタックス。

その他

• ユーザの追加はadduserコマンド
  • useraddというコマンドもあるけど、「adduser使え」とmanに書いてある。
• .ssh/authorized_keysファイルの編集
  • ログイン元の公開鍵を買いておけば、パスワード入力が不要になる。
• /etc/sudoersの編集にはvisudoコマンドを使う
• sudo raspi-config --expand-rootfs で、SDカードを容量一杯使えるようになる。最初は2GB分しか使えないらしい。
• sudo vcgencmd measure_temp で、CPUの温度を計れる。
• sshのログイン元の/etc/hostsファイルを編集

参考リンク

• http://www.slideshare.net/tominagamichiya/raspberry-pi-20130616
• http://qiita.com/soramugi/items/cce8bb19aaa5604e0607
• http://blog.bnikka.com/raspberrypi/raspberrypi-install.html

みずほ証券(株)を退職します

7/31が最終出社で、8/31が退職日。1ヶ月間は有給消化(^^)

転職活動

ビズリーチ登録→エージェントから連絡→エージェントから案件紹介、という流れで、幸いな事に割りとすんなりと転職先は決まった。辞めようと決意したのが4月の終わり頃で、6/15に内定を貰えたので、すんなり過ぎたかもしれない。ビズリーチのお陰でエージェントを探す手間が省けて、エージェントのお陰で会社を探したり、その会社の情報を集めたり、という部分に掛かる労力をかなり節約出来た。色々な事をいう人もいるみたいだけど、ビズリーチは使えるのでは。一度も有料会員にはなってないけど、お祝いにアマゾンギフト券くれるみたいだし。まだ貰ってないからホントにくれるのか分からないけど。
エージェントからのアドバイスで、心がけるようにした事がある。面接の際に何かを話す時には、必ず具体例をくっつけて話すこと。例えば、単純に

• 「C++が書けます」と言うのではなくて、
• 「○○の業務の中で、△△をC++で実装しました」と言う。

最初の言い方だと、聞いてる方としては、「ふーん」で終わってしまう。何か向こうから質問してくれれば良いけれど、質問が無いと、C++に関する会話はこれで終わり。C++が自分のコアスキルだと思っていたとしても、それ以上にアピール出来なくなってしまう。2番目の言い方ならば、聞かれる前からさり気なく自分アピールを入れられる。そして、こっちから出す情報量が多いほど、聞く側も質問を出し易い。
CodeIQも利用した。何となく、「こういう書き方をすると、企業からのコンタクトが貰いやすいなぁ」という感触を得た頃、ビズリーチ経由の企業から内定が来て転職活動が終わったのだった。

有給消化

労働基準法だか何だかで、

• 企業は法律で定められた日数だけ、従業員に有給を支給しなければならない
• 企業は労働者からの有給申請を断る事は出来ない
• 但し、申請された取得日時をずらす事は許される
• 但し、退職時には取得日時をずらす事が不可能なので、無条件で申請を認めなければならない

と決まっているらしい。おかげで、夢の1ヶ月間休暇が実現した。
さて、何をしようか。

色々なプログラミング言語を触ってみた方が良いと思う理由

「○○が書けるからそれ以外のプログラミング言語を勉強する必要性は感じない」というような意見を聞いて、その時、直観的に「それは違うんではないかな」と思ったんだけど、どう違うと思うのかを上手く説明出来そうになかったので適当に相槌を打っといた、ということが何回かあったので、どう違うと思うのか、改めて考えみた。

やりたい事とやり方は分けて理解した方が良い。

普段はあまり意識しないけれども、アルゴリズムとそれを特定の言語で表現したプログラムは、別のレイヤーに属する物である。林檎でお腹は膨れるけれど、「林檎」という言葉を味わうことはできない、という事。
アルゴリズムによって現実の世界で何らかの機能を果たそうとすると、必ず何かしらの言語でプログラムとして表現される必要がある。だので、それらは別物なんだけれど、普段その事を意識する事はあまりないし、難しい。
話を分り易くするために、敢えて単純化して、以下ではアルゴリズムを考える事は知的で創造的な思考で、それをプログラムとして表現するのは単純で機械的な作業である、という立場を取る。自分が本心からこんな風にドラスティックに考えている訳ではなくて、敢えて単純化して話を分り易くしようとしている。大事なことなので二回言いました。
有名な話だけど、FizzBuzzを書けないプログラマが居る。なかなか納得し難い事態ではあるのだけれど、まぁ会社に入って大量のSEと仕事をしていると、何となく分かってしまう。ここに面白いジョークがあって、問題をこのように書けば、彼らでもFizzBuzzを書けるだろう、と。確かに、そう思う。ここで、FizzBuzzの要件からこのような手順を明示的に導き出せるのが、アルゴリズムを考えるという能力である。そして、この詳細設計書の手順を逐語的にコードに置き換えるのが、プログラムとして表現するという作業である。

単一の言語だけにしか触れないよりも、様々な言語に触れた方が、アルゴリズムについて考える能力を効率良く伸ばす事が出来ると思う。

自分は、普段はC++で仕事をしているが、ちょっと前にLispを勉強し始めた。LispとC++は大分違う。そして、自分は、LispよりはC++の方が経験が深い。なので、Lispを書いていると「C++だったらすんなり書けるのに、Lispだとどう書いて良いか分からん。うがー」という事がままある。この時、頭の中にはC++のコードが浮かぶ。そして、「C++でこうやって書いているのは、一体、何をやっているんだろう」と、思考がアルゴリズムのレイヤーに及ぶ。そこでやりたい事をクリアにした後、Lispでそれを実現する為のやり方を考える事になる。もし、自分がC++でしかプログラムを書いてこなかったならば、こういう頭の使い方をする機会はなかっただろう。

特定のどの言語からも独立した概念としてアルゴリズムを捉えられるのは有用な事であると思う。

全く触った事が無い言語でFizzBuzzを書け、と言われた時、アルゴリズムのレイヤーで物事を考えた事がない人は、お手上げだろう。少なくとも短時間で仕上げる事は難しいと思われる。Hellor Worldから始めて、様々な練習問題を解き、その言語における色々なやり方を頭に詰め込み、そのレパートリーが充分に広がった所で、FizzBuzzのプログラムが書けるようになるだろう。一方で、FizzBuzzを実現する為に必要なやりたい事を言語とは独立に頭に思い浮かべる事ができる人は、短時間で実装に辿り着く事が出来る。最終的に必要なやりたい事のやり方をググれば終わりだ。
日本語で作文をする際も、分かりやすい文章を書く為には、まずは言いたいことが何であるかをはっきりと意識する必要がある。その上でそれを伝える為に最も良いと考えられる言い方を模索しなければならない。思い付いたことをだらだらと並べるだけでは、何が言いたいのか全く分からない文章が出来上がる。
プログラムを書く時も同じで、やりたい事をキチンと意識して、それを分り易くコードとして表現するという態度で望まないと、とても簡単に、もの凄く分かりづらいコードが出来上がる。何に使われるのかよく分からない変数の宣言がだらだらと至る所に散漫と散らばっていたり。本来、分けて書かれるべき別個の処理のロジックが混在してしまっていたり。そんな調子で、最終的には、一つの関数に、考えられる全ての条件下における全ての必要な処理を何千行も費やして押し込めてしまう事になる。こういうプログラムをリファクタしたりデバッグするのは、とても、しんどい。

こういった事態を避ける為に、プログラムとは独立にアルゴリズムを把握出来る能力は、役に立つ。やりたい事を実現する為に必要かつ充分な準備は何か。やりたい事は、それより小さな粒度のどんなやりたい事の複合物であるのか。やりたい事を実現する為に処理を変えなければならない場合、処理方法を決定する要因は何であるのか。
こういった事を、漫然とプログラムを書き始める前に、頭の中に明示的に思い浮かべられると、出来上がるプログラムは読み易いものとなる。そして、そういった思考を養うのに、普段とは違う言語で書くというのは、絶好の訓練になるのだ。