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の情報量利得や
https://www.jstage.jst.go.jp/article/fss/26/0/26_0_168/_pdf
Extremely fast decision tree 論文紹介
