モデル選択の実験 (AIC vs LOOCV)

最近読んだ「データ解析のための統計モデリング入門――一般化線形モデル・階層ベイズモデル・MCMC (→ amazon)」に感化されて、モデル選択基準である、AIC、LOOCV (Leave One-Out Cross Validation) について実験してみた(参考:モデル選択の周辺の話の整理)。

LOOCV と AIC はある意味で両極端だ。LOOCV は利用するのに必要な仮定が少なく、直感的にも何をやっているのかわかりやすい(ただし計算量は非常に大きい)。一方で AIC は評価式の簡単さ(計算量の少なさ)とは裏腹に、背後には正則条件だとかネストだとかの直感的とは言いがたい仮定をしたりする。

まあ AIC とか LOOCV とかが常に正しいモデルを選択するわけじゃない、というのは直感的にはわかるけど、実際に試してみたことはなかったので、真のモデルを知っているという神の視点からみて、こいつらがどんな挙動を示すのかをシミュレーションで確かめてみた。

“モデル選択の実験 (AIC vs LOOCV)”の続きを読む

Ruby CGI で Insecure operation error

久しぶりの ruby ネタ。以下のような ruby CGI で 500 internal error が出た。

#!/usr/bin/ruby

require "cgi"
cgi = CGI.new
params = cgi.params

open(params["filename"],"w") { |f| f.puts "hoge" }
cgi.out { "hoge" }

apache のログを見てみるとファイルを作成する部分 (open) で Insecure operation というエラーが出ている。

いろいろ調べてみると、どうやら ruby CGI で URL のパラメータを使ったパス名でファイルを書き込もうとしたことが原因のようだ。パス名に空白とか入っていると悪さができそう、ということらしい。ごもっともです。
“Ruby CGI で Insecure operation error”の続きを読む

Rの配列/リストのランダムアクセスのパフォーマンスを調べてみた

よくRでは配列/リストに対してfor文+インデックスでアクセスしてはいけない、ということが言われますが、そうせざるを得ない場面にも時々遭遇します。少し気になってインデックスでアクセスした時のパフォーマンスの特性を調べて見ました。

通常、データ構造の意味で配列といえばランダムアクセスは定数時間、つまり O(1) で、リストのランダムアクセスは O(n) です。ところが、Rの場合は必ずしもそうなっていないようです

実験条件

2つのアクセスパターンで実験をしました。

■ アクセスパターン1
配列とリストの i 番目の成分に100万回 1 を加える。i=1,2000,4000,6000,…,20000 に対して実行時間を調べる。

■ アクセスパターン2
配列とリストの 1~i 番目の中のランダムに選んだ添字の成分に 1 を加える操作を100万回行う。i=1,2000,4000,6000,…,20000 に対して実行時間を調べる。

結果

2つのアクセスパターンに対する結果を表したのが次の図(使ったスクリプトは記事の一番最後):

縦軸は100万回のランダムアクセスに要した時間、横軸は上の実験条件の所で述べた i を示しています。

考察

はっきり言ってうまく実験がうまく制御されているかどうかについては自信がありませんが(定数分のオーバーヘッドがどこに起因しているのかよくわからない)、この実験の結果を真とすればアクセスパターン1では配列/リストともに定数時間であり、一方、アクセスパターン2では配列は定数時間ですが、リストの方は長さが増加するとアクセス時間が増加することになります。
この実験をする前は

  • リストと名のつくものは無条件で所要時間が線形に増えるだろう

と思っていたので少し新鮮な結果でした。

疑問・まとめ

  • リストの同じ添字にアクセスするのは定数時間なのは、最近アクセスした要素を何らかの方法でキャッシュしているから?
  • 配列に関して、パターン1よりもパターン2のほうが所要時間が短い理由はなぜ?

まあ、100万回程度のアクセスにこんなに時間がかかるならやっぱりできるだけ使わないほうがよいということでしょう(100万次元のベクトルの足し算などはこの実験よりもはるかに高速に行うことができる)。どうしても使う場合は、特にリストの場合はキャッシュが効くように同じ添字になるべく連続してアクセスすべし、ということを頭の片隅にいれておくことにします。

実験に使ったスクリプト

ntry <- 1000000 # Number of repeat

ary.len <- 20000

# Defining index for test
idx <- seq(0,ary.len,ary.len/10)
idx[1] <- 1

# Array access time --- Pattern 1
ary <- rep(0,ary.len)
durations.ary <- matrix(0,length(idx),5)
j <- 1
for(i in idx){
  n <- sample(1:i,ntry,T)
  start <- proc.time()
  for(k in 1:ntry)
    ary[i] <- ary[i] + 1
  durations.ary[j,] <- as.numeric(proc.time() - start)
  j <- j+1
  gc();gc();gc();
}

# List access time --- Pattern 1
lst <- list(0)
for(i in 1:ary.len)
  lst[[i]] <- 0
durations.lst <- matrix(0,length(idx),5)
j <- 1
for(i in idx){
  n <- sample(1:i,ntry,T)
  start <- proc.time()
  for(k in 1:ntry)
    lst[[i]] <- lst[[i]] + 1
  durations.lst[j,] <- as.numeric(proc.time() - start)
  j <- j+1
  gc();gc();gc();
}

tmp <- c(durations.ary[,3],durations.lst[,3])
par(mfrow=c(1,2))
plot(idx,durations.ary[,3],type="n",ylim=c(7,8),xlab="Index of array/list",ylab="Excution time")
lines(idx,durations.ary[,3],type="o",lw=2,col="steelblue")
lines(idx,durations.lst[,3],type="o",lw=2,col="pink")
legend("bottomright",legend=c("Array access time","List access time"),col=c("steelblue","pink"),pch=1,lw=2)
title("Access pattern 1")


# Array access time --- Pattern 2
ary <- rep(0,ary.len)
durations.ary2 <- matrix(0,length(idx),5)
j <- 1
for(i in idx){
  n <- sample(1:i,ntry,T)
  start <- proc.time()
  for(m in n){
    ary[m] <- ary[m] + 1
  }
  durations.ary2[j,] <- as.numeric(proc.time() - start)
  j <- j+1
  gc();gc();gc();
}

# List access time --- Pattern 2
lst <- list(0)
for(i in 1:ary.len)
  lst[[i]] <- 0
durations.lst2 <- matrix(0,length(idx),5)
j <- 1
for(i in idx){
  n <- sample(1:i,ntry,T)
  start <- proc.time()
  for(m in n){
    lst[[m]] <- lst[[m]] + 1
  }
  durations.lst2[j,] <- as.numeric(proc.time() - start)
  j <- j+1
  gc();gc();gc();
}


tmp <- c(durations.ary2[,3],durations.lst2[,3])
plot(idx,durations.ary2[,3],type="n",ylim=c(7,8),xlab="Index of array/list",ylab="Excution time")
lines(idx,durations.ary2[,3],type="o",lw=2,col="steelblue")
lines(idx,durations.lst2[,3],type="o",lw=2,col="pink")
legend("bottomright",legend=c("Array access time","List access time"),col=c("steelblue","pink"),pch=1,lw=2)
title("Access pattern 2")

[c++11] ネストしたクラスでの decltype

c++11 の decltype について。入れ子クラスの場合のちょっとした問題。下のサンプルコードの一番最後の行でコンパイルエラーが出る。

struct Outer {
  int x;
  struct Inner {
    int y;
  };
};


int main(){
  Outer outer;  // OK
  Outer::Inner inner;  // OK

  decltype(outer) outer2;  // Valid for c++11
  decltype(inner) inner2;  // Valid for c++11

  decltype(outer)::Inner inner3; // Error!!!!
}

コンパイル。

$ g++ decltype_test.cpp --std=c++0x
decltype_test.cpp: In function ‘int main()’:
decltype_test.cpp:16: error: expected initializer before ‘inner3’

decltype(outer) は Outer と展開されるので decltype(outer)::Inner は Outer::Inner と展開されて欲しいところだけど、できないみたいですね。g++ のバージョンは 4.4.3 と 4.5.2 でためしてみました。

ほとんどのケースでは auto を併用すれば問題は解決するのだけど、たまに困ります。これは仕様なのか、未実装なのかはわかりませんが。