iAnalysis 〜おとうさんの解析日記〜

■MapReduceできる10個のアルゴリズム

HadoopとMahoutにより、ビッグデータでも機械学習を行うことができます。Mahoutで実装されている手法は、全て分散処理できるアルゴリズムということになります。Mahoutで実装されているアルゴリズムは、ここに列挙されています。論文としても、2006年に「Map-Reduce for Machine Learning on Multicore」としていくつかのアルゴリズムが紹介されています。

そこで今回は、（何番煎じか分かりませんが自分の理解のためにも）この論文で紹介されているアルゴリズムと、どうやって分散処理するのかを簡単にメモしておきたいと思います。計算するべき統計量が、summation form（足し算で表現できる形）になっているかどうかが、重要なポイントです。なってない場合は、”うまく”MapReduceの形にバラす必要があります。

※例によって、間違いがあった場合は随時修正致しますのでご指摘下さい。

1. 局所重み付け線形回帰（Locally Weighted Linear Regression, LWLR）

• mapperでサブデータの重み付き平方和（xxとxy）を計算しreducerで足す。（以前の記事を参考）
• 重みが1の場合は通常の線形回帰になる。

2. ナイーブベイズ

• ナイーブベイズには条件付き確率が必要なので、mapperではそれぞれの条件付き”頻度”を計算しreducerで足す。
  • #(x=k|y=1), #(x=k|y=0), #(y=1), #(y=0)（#は頻度）

3. ガウシアン判別分析（Gaussian Discriminative Analysis, GDA）

• GDAに必要な4つのパラメータを分散計算する。
  • P(y), μ0, μ1, Σ

4. k-means

• mapperで中心に割り付け＆中心までの距離の合計とサンプル数を計算、reducerで中心の更新を行う。
• これを繰り返す。

5. ロジスティック回帰

• ニュートンラフソン法で尤度を最大化する。
• 更新に必要な部分をmapperで加法できるように計算し、reducerで合計して更新する。

6. ニューラルネットワーク

• バックプロバゲーションをmapperで行い、部分的な傾きを計算する。
• reducerでそれぞれの傾きを足し合わせ、重みを更新する。

7. 主成分分析（Principal Components Analysis, PCA）

• 共分散行列が求まれば良く、共分散行列はsummation formになっている。

8. 独立成分分析（Independent Component Analysis, ICA）

• mapperでICAに必要なunmxing matrix（W）の尤度を最大化するための部分傾き（？）を計算しreducerで足す。
  • unmxing matrixにかんしてはwikipediaで。
  • 最尤法でICAを計算する論文はこちら。

9. EMアルゴリズム（Expectation Maximization, EM）

• Eステップ、Mステップで推定するそれぞれのパラメータをうまくmapperとreducerにバラす
• EステップのMapReduce、MステップのMapReduceを繰り返す

10. サポートベクターマシン（Support Vector Machine, SVM）

• 線形SVMの2次損失関数の場合、ある方程式を解くことで最適化ができる
  • 部分的な傾きをmapperで計算しreducerで足す。これによって重みのwを更新する。

以上です。こうやって見るとsummation formになっていない場合は最尤法を使い、（傾きによる）尤度の更新を1回のMapReduceで行なっているようです。またEMアルゴリズムというとても汎用的な手法がMapReduceできるということで、多くの手法が分散処理できるということが分かります。しかし実際にはそれぞれのEMをMapReduceに分解しなくてはならないので、実装はかなり大変そうです。また毎回のパラメータ更新をMapReduceしなくてはならないので、結構な時間もかかりそうです。

ツイートする

Permalink | コメント(0) | トラックバック(0) | 00:02

■Pythonで分析や機械学習メモ

私はRからプログラミングに入って分析もRでやってるわけですが、ちょっと大きめのデータになるとRでは扱うのが難しくなります。そこで前々からPythonに手を出そうとしていたのですが、なかなかインストールがうまく行きませんでした。しかし、ようやくPython環境を整えることが出来たので、メモしておきます（@teikawさんにいろいろ教えてもらいました）。

Pythonのインストールは良く使われるパッケージが入っている、enthoughtやpythonxyで行うのが良いです。自分は前者のアカデミック版をインストールしました。インストールした後、環境変数の設定が必要かもしれません（以前にPython単体でインストールしたときに環境変数は設定していました）。

機械学習を実行するにあたって、今一番アツそうなのがscikits.learnというライブラリです。これはGoogle summer codeがきっかけで立ち上がったプロジェクトで、10人を超えるエンジニアが作っているようです。トップのUser Guideの中身をひと通り目を通しましたが、主な手法はほとんど入っています！欲を言えば、アンサンブル系がもっとあって欲しいですが。上記のパッケージでPythonをインストールしていれば、追加でパッケージを入れることなく、コンソール上でコードをコピペすれば結果を再現できます。Exampleにある画像も、ほとんどコピペで作成できます！（一部、改行やコメントの影響でエラーが出ました。）R使いな私としては、こういう手軽さがとても嬉しいですね。実際にRとどう住み分けるかは、引き続き考えなきゃいけないですが。

また、自学習用にscipyのチュートリアルもメモしておきます。

ツイートする

Permalink | コメント(0) | トラックバック(0) | 00:18

■因果推論のススメ

2012年3月12日、計算機科学分野の権威ある賞、チューリング賞（wikiはこちら）をJudea Pearl先生が受賞されました（米記事はこちら、日本記事はこちら）。Pearl先生は「因果推論」分野の権威です。因果推論はベイジアンネットワークや構造方程式モデリング（SEM、パス解析）などの基本理論になります。チューリング賞が出たこともあって因果推論が注目されそうですが、難易度が高い分野でもあります。そこで、私が読んで理解が進んだ本を紹介致します。

まずは、このエッセイ本を読むと「因果関係とは何か？」「効果とは何か？」といった事をとてもイメージしやすくなります。これは医療統計分野の本なので、「ランダム化試験」という用語で因果関係を説明していますが、web業界の方はA/Bテストと言った方が分かりやすいかもしれません。A/Bテストをすることでレイアウトの良し悪しが判明するのも、基礎には因果推論の考え方があります。

次に、理論的な内容のこれらの本があります。1つ目の星野先生の本は疫学や公衆衛生学寄りで、Rubin先生やModern Epidemiologyの説明に近いと思います。2つ目の宮川先生の本はグラフ理論やDAG（非循環有向グラフ）に基づいていて、Pearl先生の説明に近いです。傾向スコアや操作変数に関する解説があります。

上記の本で因果推論が分かってくると、Pearl先生の教科書が読みやすくなります。次のように、日本語訳もあります。ベイジアンネットワーク、SEMなどの説明があります。

また、DAGには3つ重要な基準があります（DAGであれば必ずこれらを満たすわけではないのでご注意下さい）。この特性は慣れないと理解が難しいので、自分の理解をメモしておきます（正確な定義は教科書をご覧下さい）。表現に間違いがあれば、後ほど修正致します。

1. 有向分離基準（d-separate）

有向分離基準を満たせば、集合Sによってaとbは独立となる。aとbの間の道上で、すべての合流点（collider）で条件付けると擬似相関が生まれる。また、aとbの共通因子や中間因子で条件付けると独立になる。

2. バックドア基準

バックドア基準を満たすSが存在すれば、xのyへの介入効果はSによって表現可能となる。このとき、xのyへの介入効果は識別可能という。このようなSの条件は、xがSの原因因子になっておらず、かつ、xからの矢線をとりのぞいたときにSがxとyを有効分離することである。

3. フロントドア基準

Sがフロントドア基準を満たせば、Sによってxのyへの介入効果は表現可能である。このときの条件は、Sの要素でxyの道を全てブロックしている、xからSへのバックドアパスは空集合でブロックされる、Sからyへのバックドアパスをxがブロックしている、の3つを満たすことである。未測定の交絡因子があるときの対処法の1つである「媒介変数法」を拡張したアイディアになっている。他の対処法としては、操作変数法や条件付き操作変数法がある。

また、過去にPearl先生の訳本を読みながら資料に起こしたものがありますので、紹介しておきます。

ツイートする

Permalink | コメント(1) | トラックバック(1) | 23:47

■一年で身に付ける！Rと統計学・機械学習の4ステップ

久しぶりの投稿です。この一年間、Rの勉強会などに参加したり主催したりしてきて、後輩や勉強会の方々の話をいろいろ聞くとこができました。そんな中、一年間でRと統計学・機械学習を身に付けれるようなフローを作れるかも？と思ったので、ここで記録しておきます。統計学や機械学習は理論を勉強するだけでなく、Rで実際に解析してみることで、より理解が深まります。

ステップ1. 分布・検定

理論

R本

ステップ2. 尤度・回帰

理論

R本

ステップ3. 多変量解析

理論

R本

ステップ4. 機械学習

理論（Hastie本、PDF）

R本

本の内容的に重複もあって、完全に上記のように分けれるわけではないですが、この順で学ぶことで理解が進むかと思います。また、それぞれのステップで代役になる本は他にもあります。例えば、ステップ2の理論本は、『現代数理統計学』でも同じくらいの難度だと思います。また、PRML本では、Hastie本とは違った見方で機械学習を学べます。それぞれのステップを3ヶ月くらいでこなせれれば、一年で統計学と機械学習の全体感を取得し、Rも使えるようになりますね。（最後のHastie本を3ヶ月は大変ですが笑）

実践から入りたい！！といった方は、ステップ3や4から入るのも良いと思います。もともと統計学は実データから生まれた学問なので、むしろそういうモチベーションは大事です。実際、私は「とりあえず分析して結果を見たい」派なので、R本が少なかった数年前は金先生のページの資料にある例を実行したりしていました。以前書いた「ぼくのかんがえたとうけいがくぶかりきゅらむ」も、実践を先に勉強しましょう、という趣旨で学習順序を構成しました。

この後は、「Rで学ぶデータサイエンス」シリーズで各論を学んだりすると、より高スキルが身につきます。また、ビッグデータを扱うためにHadoop+Mahoutを習得したり、切り出したデータを加工するためにRuby、Python、Perlなどのスクリプト言語を勉強したり、一度DBに格納してデータ操作をするためにMySQLやSQLiteなどのデータベースを扱えるようになれれば、データサイエンティストへより近づけますね。実際に、Facebookが求人しているデータサイエンティストは、以上のようなスキルを持った人です。

明後日からちょうど4月です。ぜひこの一年で、1人でも多くの人が統計学やデータ分析を取得して頂きたいものです。そしてデータ分析を社会に役立てて欲しいですね！

※なお、紹介している本や、ステップは随時変更するかもしれませんのでご了承下さい。

ツイートする

Permalink | コメント(2) | トラックバック(3) | 22:10

■バッギング、ランダムフォレスト、ブースティング

今回は集団学習（アンサンブル学習）で良く出てくる、バッギング、ランダムフォレスト、ブースティングについてメモしておきます。参考にしている教科書はこちらです。貼りつけている数式もこの教科書から抜粋しています。

どの手法も、「弱い学習器」をたくさん集めて良い予測値を得ることを目指しています。弱学習器を集めているせいか、予測精度は高いのに過適合しにくいのが特徴です。教科書の事例では学習データでどんどん学習させても、テストデータに対して予測エラーが全然上がらない（つまり過学習していない）。

1. バッギング（Bagging）

データをブートストラップサンプリングし、予測器f(x)を作る。それをB回繰り返し、それぞれの予測器の平均値を予測値とする。

特に、f(x)が決定木（decision tree）の場合をバッギング木（bagged tree）という。

2. ランダムフォレスト（Random Forest）

バッギング木と似たアルゴリズムだが、説明変数もランダムにm個選択するところが大きく異なる。バッギングと同じように、データは毎回ブートストラップサンプリングする（P588）。

3. ブースティング（Boosting）

アルゴリズムGの予測値を実測値に近づけるように、予測値の加重和パラメータω、アルゴリズムの加重和パラメータαを計算する。最終的にM個作ったアルゴリズムをαで加重和したものを予測値とする（下記の結果変数は[-1, 1]なのでsignを予測値としている）。

パラメータの計算方法で最も有名な方法が、アダブーストM1（Ada Boost.M1）である（P339）。また、アルゴリズムGの損失関数の微分（勾配）を利用して、パラメータ更新を素早く行うことのできる手法が、勾配ブースティングモデル（Gradient Boosting Model, GBM）である（P361）。

ツイートする

Permalink | コメント(0) | トラックバック(0) | 23:43

■Facebookの情報を取得する

あけましておめでとうございます。今年初の記事です。Rbloggersで気になった記事があったので、やってみようと思ったのですが、、、

http://applyr.blogspot.com/2012/01/mining-facebook-data-most-liked-status.html

いろいろ下記の設定をしたのですが、結局Rgraphvizが自分のマシンでは動かず、グラフを描くところまで行きませんでした。

• facebookアプリを作り、access_tokenを取得する
  • http://facebook.boo.jp/access-token%E3%82%92%E5%8F%96%E5%BE%97%E3%81%99%E3%82%8B

• Rgraphvizをインストールする
  • パッケージのインストール：http://bioconductor.org/packages/release/bioc/html/Rgraphviz.html
  • Rgraphvizに対応している2.20.3aをインストール：http://www.graphviz.org/pub/graphviz/stable/windows/

• RCurlをインストールする
  • http://www.stats.ox.ac.uk/pub/RWin/bin/windows/contrib/2.14/

コードはこちら↓

access_token <- "...................."

require(RCurl)
require(rjson)

# Facebook json function copied from original (Romain Francois) post
facebook <-  function( path = "me", access_token, options){
   if( !missing(options) ){
        options <- sprintf( "?%s", paste( names(options), "=", 
                           unlist(options), collapse = "&", sep = "" ) )
    } else {
        options <- ""
    }
    data <- getURL( sprintf( "https://graph.facebook.com/%s%s&access_token=%s",
                    path, options, access_token ), ssl.verifypeer = FALSE )
    fromJSON( data )
}


friends <- facebook( path=".../friends" , access_token=access_token)
# extract Facebook IDs
friends.id <- sapply(friends$data, function(x) x$id)


friends.name <- sapply(friends$data, function(x)  iconv(x$name,"UTF-8","ASCII//TRANSLIT"))
# short names to initials 
initials <- function(x) paste(substr(x,1,1), collapse="")
friends.initial <- sapply(strsplit(friends.name," "), initials) 

# friendship relation matrix
N <- length(friends.id)
friendship.matrix <- matrix(0,N,N)
for (i in 1:N) {
  tmp <- facebook( path=paste(".../mutualfriends", friends.id[i], sep="/") , access_token=access_token)
  mutualfriends <- sapply(tmp$data, function(x) x$id)
  friendship.matrix[i,friends.id %in% mutualfriends] <- 1
}

require(Rgraphviz)
# convert relation matrix to graph
g <- new("graphAM", adjMat=friendship.matrix)

# ellipse graph with initials
pdf(file="facebook1.pdf", width=25, height=25)
  attrs <- list(node=list(shape="ellipse", fixedsize=FALSE))
  nAttrs <- list(label=friends.initial)
  names(nAttrs$label) <- nodes(g)
  plot(g, "neato", attrs=attrs, nodeAttrs=nAttrs)
dev.off()

自分の環境では、最後のplot()でRがクラッシュてしまいます（32 bit版のRを使っても）。友人情報は取得できたので、Graphviz以外の方法でグラフを描けばいいかも。しかしRは他ソフトと連携しようとすると、エラーが多くなって安心して使えないですね。Rに限った話では無いかもしれませんが。

今回うまくいかなかったのも、原因は確定できませんが、64bitマシンを使ったからかなぁと。OSが変わるといろいろ大変ですね。。うまく行った方がいらっしゃれば、ぜひ教えて頂ければ幸いです。

ツイートする

Permalink | コメント(2) | トラックバック(0) | 18:32