這篇是為自己學習而做的筆記，因為可能有錯，後續可能會修修改改，如果讀者拿此文章上台報告，導致被老師或聽眾釘在台上，本人不負任何責任。

以下資料引用的書是Tom M. Mitchell寫的 Machine Learning的第一七六頁，引用順序有打亂。

H是 hypothesis space。假設H裡面眾多hypothesis的機率是uniform分布，那麼根據現在的version space隨機選到的hypothesis h，用來分類下一筆新進來的資料(instance)時，預期該hypothesis h分類錯誤的期望值，最多只會大於由Bayesian optimal classifier分類錯誤期望值的兩倍。

version space不知道指H，也就是 hypothesis space，還是指train data。

為什麼會有Gibbs algorithm這個演算法？

雖然Bayes optimal classifier可從training data 得到最好的分類效果，但是它使用上非常耗計算成本(例如，時間)。因為它需要計算每個 hypothesis 的 posterior probability，然後結合每個 hypothesis 的預測(prediction)，去分類每個新進來的資料(instance)。於是Opper and Haussler想出了 Gibbs algorithm 這個替代的方法。

第一步，根據 hypothesis space H 的 posterior probability distribution，從hypothesis space H 隨機選出一個 hypothesis h。

第二步，使用上一步隨機選到的 hypothesis h，分類新進來的資料(instance)。