PFIセミナー見た - でかいチーズをベーグルする

初めてPFIセミナー見たからせっかくなのでメモ

今日は吉田（@oxy）さんによる確率不等式の話

吉田さんと言えばトップカンファレンスに通しまくってるすごい人http://research.nii.ac.jp/~yyoshida/

そんな人の話が聞けるってPFIセミナーすごいね、もっと前から見ておくんだった

以下、内容メモ

ーーーーーーーーー
ビッグデータって言うけど、大抵の場合は少数をサンプリングしてそれについて解析すれば事足りるよ

　計算量が落ちる

　精度はあまり落ちない

例えば、選挙の当確速報

　1000人くらいサンプリングして得票率を出せば大体分かる

　→開票率０％で当確が出る

以下の三つの不等式によって抑えられる

　三つの不等式は下に行くほどタイトな不等式だが、仮定が多い

マルコフの不等式

　仮定：確率変数Xが非負

　上限しか抑えられない

チェビシェフの不等式

　仮定：標準偏差が計算できている

　マルコフの不等式を用いて証明できる

　上限下限を抑えられる

　サンプル数が大きくなるに連れて上限下限が定数オーダでタイトになる

チェルノフ（ヘフディング）の不等式

　仮定：

　　　扱う確率変数がn個の平均である

　　　それぞれの確率変数は互いに独立で[0,1]の値

　上限下限を抑えられる

　nが大きくなるに連れて上限下限が指数オーダでタイトになる