容錯性（PAC學習）

容錯性（PAC學習）在PAC學習中，容錯性指的是當收到的例子以某種方式被破壞時，算法的學習能力。事實上，這是一個非常普遍和重要的問題，因為在許多應用中，不可能獲得無噪聲的數據。噪聲會在不同層面上干擾學習過程：算法可能會收到偶爾被誤標的數據，或者輸入可能有一些錯誤的信息，或者例子的分類可能被惡意摻雜。符號和Valiant學習模型在下文中，讓當數據受到一些修改時的可學習性。分類噪聲在分類噪聲模型中，噪聲率0≤η<12被引入。然后，代替{displaystylehin{mathcal{H}}是選擇最佳函數h∈H｝{displaystyle1/2}，那么在任何計算時間內學習都是不可能的。

那么在任何計算時間內學習都是不可能的，因為每一個標簽都沒有傳達關于目標函數的信息。在分類噪聲模型中，如果存在一種學習算法。一個函數h∈H，一個函數h∈H滿足概率至少為1-。