貝葉斯學習--極大后驗假設學習

我們假定學習器考慮的是定義在實例空間X上的有限的假設空間H，任務是學習某個目標概念c:X→{0,1}。如通常那樣，假定給予學習器某訓練樣例序列〈〈x₁，d₁，〉…〈x_m，d_m〉〉，其中x_i為X中的某實例，d_i為x_i的目標函數值（即d_i=c(x_i)）。為簡化討論，假定實例序列〈x₁…x_m〉是固定不變的，因此訓練數據D可被簡單地寫作目標函數值序列：D=〈d₁…d_m〉。

基于貝葉斯理論我們可以設計一個簡單的算法輸出最大后驗假設

Brute-ForceMAP學習算法

1．對于H中每個假設h，計算后驗概率：

2．輸出有最高后驗概率的假設h_MAP：

此算法需要較大的計算量，因為它對H中每個假設都應用了貝葉斯公式以計算P(h|D)。

雖然對于大的假設空間這很不切實際，但該算法仍然值得關注，因為它提供了一個標準，以判斷其他概念學習算法的性能。

下面為Brute-ForceMAP學習算法指定一學習問題，我們必須確定P(h)和P(D|h)分別應取何值（可以看出，P(D)的值會依這兩者而定）。

我們可以以任意方法選擇P(h)和P(D|h)的概率分布，以描述該學習任務的先驗知識。但是先要滿足下面的條件假設：

1．訓練數據D是無噪聲的（即d_i=c(x_i)）；

2．目標概念c包含在假設空間H中；

3．沒有任何理由認為某假設比其他的假設的可能性大。

一、如何確定P(h)的值

 對H中任一h：

二、如何選擇P(D|h)的值

換言之，給定假設h，數據D的概率在其與假設h一致時值為1，否則值為0。

接下來考慮該算法的第一步，使用貝葉斯公式計算每個假設h的后驗概率P(h|D)：

1、考慮h與訓練數據D不一致的情形

2、考慮h與D一致的情況

其中：

VS_H,D是H中與D一致的假設子集（即VS_H,D是相對于D的變型空間）

概而言之，貝葉斯公式說明在我們的P(h)和P(D|h)的定義下，后驗概率P(h|D)為：

其中|VS_H,D|是H中與D一致的假設數量。

在我們選定的P(h)和P(D|h)取值下，每個一致的假設后驗概率為（1/|VS_H,D|），每個不一致假設后驗概率為0。因此，每個一致的假設都是MAP假設。

來自： http://blog.csdn.net//u011067360/article/details/22882327