VFDT - 機械学習の「朱鷺の杜Wiki」
Hoeffding tree† 通常の決定木との違いは Hoeffding限界を使って，ノードの分割に使う特徴を近似的に選ぶ 全部のデータを保持することはせず，ノードを分割するごとにデータを捨てる． そして，ストリームからの新たなデータを使ってその後の学習を行う． 特徴選択の近似手法 幅 \(R\) の区間に生じる値が，\(n\) 個あるとする． このとき，標本平均を \(\bar{x}\) とすると，真の平均が \(\bar{r}-\epsilon\) 以上である確率が \(1-\delta\) 以上になるには， 片側のHoeffdingの不等式から： \[\epsilon=\sqrt{\frac{R^2\ln(1/\delta)}{2 n}}\] 今，ある決定木が仮に得られているとする． ここで，ある葉ノードには幾つか事例が分類されているとする． 全ての特徴に対し，ID3の情報量利得や
マルコフの不等式をわかりやすく｜高信 真司
期待値から大きく外れるような観測値が得られることは、ほとんどあり得ないと直感的にわかりますが、マルコフの不等式はこれを数学的に記述したものになります。 マルコフの不等式を導くまずは以下のグラフを見てみます。 Xを非負の確率変数、cを非負の任意の定数とします。このとき破線（青色）と実線（赤色）は以下の式で表されます。 いわゆる、破線はステップ関数、実線は恒等関数です。 確率変数の和を考えたとき、破線は常に実線の下側にありますので p(i)をiが生起する確率とすると期待値は 左辺はX≧cの確率にcをかけたもの、右辺は実線のXの期待値なので これがマルコフの不等式です。 実際に使ってみる理解するためには実際に使ってみるのが一番です。まずは指数分布の例で試してみます。 Q.指数分布(λ=1)について、X≧aの確率をマルコフの不等式で考える。 指数分布(λ=1)のX≧aの確率は下図の網掛けの面積です
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
