請問隨機森林為什麼不會過度擬合?

Breiman說當隨機森林中的樹趨向於無窮時,模型的泛化誤差是收斂的。請問為什麼泛化誤差收斂就能說明不會出現過擬合問題


Overfitting的定義就是當Empirical Loss最優的時候,Generalization Loss不是最優,也就是說訓練集效果好,但測試集效果差。如果能證明Generalization Loss收斂到Empirical Loss同一個最優值,那就說明,在訓練集上效果多好,測試集上也有同樣的效果,所以沒有overfit。這其實不只針對隨機森林。


Breiman的這句話完全錯誤,根本沒有不過擬合的學習方法!

對於隨機森林來說: 在有躁音的情況下(注意,現實世界應用中躁音不能忽略),樹太少很容易過擬合,增加樹可以減小過擬合,但沒有辦法完全消除過擬合,無論你怎麼增加樹都不行。

相關研究見 http://escholarship.org/uc/item/35x3v9t4.pdf


為啥會有這麼多 xxx模型不會過擬合 的說法呢?機器學習研究的就是過擬合,要是發現一種不會過擬合的模型,哈哈,大家都可以洗洗睡了。


建議題主把「不會」改成「不易」會比較好!


首先什麼是overfitting。模型在訓練集上的表現和測試集/真實數據上的表現一般會有差異。常用的模型會在訓練集上表現不錯,但是真實數據上表現的好,這就是過擬合現象。是模型對數據進行了過度解讀的結果,表現為模型的范化能力。

random forest 確實是一個不會overfitting的模型。主要依靠了其中三個隨機過程,即產生決策樹的樣本是隨機生成,構建決策樹的特徵值是隨機選取,樹產生過程中裂變的時候是選擇N個最佳方向中的隨機一個裂變的。當隨機森林產生的樹的數目趨近無窮的時候,理論上根據大數定理可以證明訓練誤差與測試誤差是收斂到一起的。

當然實際過程中,由於不可能產生無窮的決策樹,模型參數的設置問題會影響在相同運行時間內擬合結果的過擬合程度的不同。但總而言之,調整參數後,隨機森林可以有效的降低過擬合的程度。

可以參考wiki的原話:

Random Forests does not overfit. The testing performance of Random Forests does not decrease (due to overfitting) as the number of trees increases. Hence after certain number of trees the performance tend to stay in a certain value. There are tons of examples about that.

詳細見外文視頻

Random forests - classification description


不是不會過擬合,而是在滿足一定的條件下不容易過擬合。特徵參數要足夠多,特徵參數之間相關性盡量低。


隨機森林也會過擬合,說不會過擬合的,都是鍵盤黨,沒做過實際項目。


圖片來源:肖堅《基於隨機森林的不平衡數據分類方法研究》(哈工大2013年12月碩士論文),這個界限決定了其不會過擬合。

RF他爹01年的論文定義Margin Function:

如果單棵元分類器的強度:

根據切比雪夫不等式,泛化誤差會收斂於:

如果

樹之間的平均相關度

切比雪夫不等式可以寫成:

收斂的方差

低方差保證了不會出現過擬合,即使精度上可能筆Boost演算法差一點。


因為隨機選的樣本和特徵吧。你每個樹用的都是樣本數據的很小的一部分。所以信息量沒有過於充裕,所以過擬合的可能性小。


隨機森林的隨機性體現在每棵樹的訓練樣本是隨機的,樹中每個節點的分裂屬性也是隨機選擇的。兩個隨機性的引入,使得隨機森林不容易陷入過擬合。


只是理論, 從演算法的腳本對比其它的演算法而言,然而在實際的模型中,過擬合與樣本數,樣本質量,特徵數量,特徵相關性都有關係,如果數據都OK,隨機森林用一個很簡單的參數不會那麼容易過擬合。


實際上會。。。


推薦閱讀:

有沒有機器學習方面集大成的教材推薦?
枚舉和窮儘是不是最有效,最暴力的演算法?
哪本《數據結構與演算法》最好?
機器學習演算法庫推薦?
程序語言中的取余是如何實現的?

TAG:演算法 | 數據挖掘 | 機器學習 | 模式識別 |