Boosting學習（一）——PAC學習模型到Boosting

• PAC ( Probably Approximately Correct)可能近似正确學習模型
• 因為我們不能指望學習能夠零錯誤，并且也不能要求對任意資料的預測能夠成功，但是我們需要将錯誤率和預測失敗率控制在一定範圍内，也就是近似正确，而不是以1為名額的。
• 定義 (PAC Model)：我們稱一個 concept class C 是 PAC 可學習 的，如果存在一個算法 L ，使得對任意的 target concept c∈C ，以及任意 X 上的分布 μ ，和任意 0<ϵ<1/2 、0<δ<1/2 ，在給定 oracle EX(c,μ) 以及 ϵ、δ 的情況下，L 能夠以至少 1−δ 的機率得到一個 hypothesis concept h∈C ，滿足誤差 E(h)≤ϵ 。 如果 L 的運作時間複雜度關于 1/ϵ 、1/δ 、輸入空間 X 的次元以及 target concept c 的大小是多項式的，我們則稱 C 是 efficiently PAC learnable 的。
• 強可學習：一個多項式的學習算法，正确率很高（>(1-ϵ)）。
• 弱可學習：一個多項式學習算法，正确率僅比随機猜想略高。
• 弱可學習可以提升為強可學習。
• 弱學習器提升為強學習器的過程稱為Boosting。
• Boosting可以産生一系列的學習器，後産生的學習器的訓練集取決于之前的産生的學習器，之前被誤判的示例在之後獲得較大的機率。