周志華老師解釋集成學習時用到hoeffding不等式解釋誤差上限【機器學習，172頁】？

01-04

集成錯誤率上限是關於分類器數目和基分類器錯誤率的e指數，數目T很大，集成錯誤率為接近0，但好像基分類器錯誤率（如99%）對上限沒有任何影響（伯努利分布，上限的平方項）。問：數量多，錯誤率大的基分類器組合起來也可以很強大（集成誤差小）嘛？

來，咱們從頭開始推一遍不就明白了嗎？

由書上192頁習題8.1，我們知道 $P(H(n)leq k)=sum_{i=0}^{k}{C_{n}^{i}p^i(1-p)^{n-i}}$ ，這裡令 $p$ 為分類器正確預測的概率，假設每個基分類器的正確預測概率相同。

對 $forall delta >0$ ，有Hoeffding不等式 $P(H(n)leq (p-delta)n)leq e^{-2delta^2n}$ ，則當 $(p-delta)T=frac{T}{2}$ 向下取整時（因為打不出來向下取整隻能用文字描述）， $delta=p-frac{1}{T}frac{T}{2}geq p-frac{1}{2} =frac{2p-1}{2}$ ，因為 $p=1-epsilon$ ，所以 $deltageq frac{1-2epsilon }{2}$ 。

因為 $delta>0$ 這也就表示只有在 $p>0.5$ 的時候這個式子才會有意義，也就是說當 $pleq 0.5$ 時不能用這個式子估計。

在用簡單的多數投票方法做集成的時候，單個分類器的錯誤率不能大於0.5，否則（8.3）那個bound是不成立的。

前一頁中說了分類器應該「好而不同」，在多數投票的時候，「好」就是至少得比隨機猜（$epsilon=0.5$）好。

對，你理解的沒錯，只不過基分類器錯誤率越大，需要的數量越大，畢竟裡面那項是帶平方的！然後還乘2……

然後周老師寫得很清楚啊，這是個理想條件下的公式，也就是說只能定性分析一下，現實中，這個bound沒卵用。

理想條件，就是不能滿足的條件，然後我不覺得有什麼好方法能定量推算與『各個分類器錯誤率獨立』這理想條件間的差距。