Hoeffding tree† 通常の決定木との違いは Hoeffding限界を使って,ノードの分割に使う特徴を近似的に選ぶ 全部のデータを保持することはせず,ノードを分割するごとにデータを捨てる. そして,ストリームからの新たなデータを使ってその後の学習を行う. 特徴選択の近似手法 幅 \(R\) の区間に生じる値が,\(n\) 個あるとする. このとき,標本平均を \(\bar{x}\) とすると,真の平均が \(\bar{r}-\epsilon\) 以上である確率が \(1-\delta\) 以上になるには, 片側のHoeffdingの不等式から: \[\epsilon=\sqrt{\frac{R^2\ln(1/\delta)}{2 n}}\] 今,ある決定木が仮に得られているとする. ここで,ある葉ノードには幾つか事例が分類されているとする. 全ての特徴に対し,ID3の情報量利得や