發信人: GzLi (笑梨), 信區: DataMining
標  題: [合集]我也來說說VC維。
發信站: 南京大學小百合站 (Thu Apr 17 00:22:26 2003)

mnls (蒙娜麗莎的微笑) 于Mon Apr 14 16:57:57 2003)
提到：

vc維就是一個系數，這個系數就是為了度量一組函數集的容量(capacity)。注意這里的
“函數”是廣義的，線性函數、多項式函數當然都是函數；對于一個多蹭的神經網絡，
權值大小不知道（訓練神經元網絡就是為了確定權值），每組權值就可以認為對應一個
函數。
而容量就反映了一組函數集對樣本的區分能力，容量越大，對應的一組函數集區分能力
就越大；注意容量的大小跟這組函數集自由參數的多少是沒有必然聯系的（不確信這樣
說是否合適），因為函數集{y=sin(w*x+b),w,b(-R}的vc為即為無窮大。
還有一個應該注意的問題是：vapnik定義vc維是指能夠找到N個樣本可以被一組函數集打
散（不是任意N個樣本都滿足這個條件）的最大N。比如說二維平面上空間上對于所有的
線性分類面，能夠找到3個點可以被線性分類面打散，但不是任意三個點都能夠滿足這個
條件（是不是？很簡單的，相信你能夠找到這樣的三個點）。
再說說svm,說白了就是個線性分類面，不過是定義在高維特征空間上的，跟感知機算法
相比就多了一個最大間隔，沒別的，呵呵。（當然，暫時不考慮核函數映射問題）。那
為啥最大間隔最好呢？vapnik用vc維解釋這回事：所有把兩類樣本以d間隔分開的線性函
數組成的集合，假如記為F(隨便了，statistical learning theory中好像不是這樣記的
，忘了),那么d越大，函數集F的VC維就越小（vapnik的書有證明），d取極限情況不就是
最大間隔超平面嗎？
那為何vc維越小越好呢，就是因為這時推廣能力（或者說泛化能力，generalization，
隨呢咋叫）好。統計學習理論中被叫爛了的那個結構風險最小化就是說這個事的。簡單
的說就是推廣能力有兩個因素決定：訓練錯誤和置信范圍（置信范圍這個叫法很土），
也就是STL中一個很重要不等式右邊兩項，而結構風險最小化就是最小化前面那兩個的和
；對于svm，既然都被線性分開了，訓練錯誤當然就是零了，那分類器的泛化性能就只由
置信范圍來決定了，而vc維越小，置信范圍就越小了。繞來繞去，我也不知道說明白了
沒有。
因此,svm就是在最小化經驗風險的基礎上從vc維最小的函數集里面選擇函數，不是嗎？
（別忘了，vapnik也給什么是機器學習下了個定義，就是從一組函數集里面選擇函數，
就這么簡單）我們當然也可以用別的方法尋找最好的函數，只要在尋找的時候記住結構
風險最小，那我們就可能找到別的機器學習算法了，呵呵。
至于核，哎，太累，下次再寫。
這個版，我喜歡。


minus (qq) 于Mon Apr 14 18:40:09 2003)
提到：

真的是VC維越小越好嗎??

【 在 mnls (蒙娜麗莎的微笑) 的大作中提到: 】
: vc維就是一個系數，這個系數就是為了度量一組函數集的容量(capacity)。注意這里的
: “函數”是廣義的，線性函數、多項式函數當然都是函數；對于一個多蹭的神經網絡，
: 權值大小不知道（訓練神經元網絡就是為了確定權值），每組權值就可以認為對應一個
: 函數。
: 而容量就反映了一組函數集對樣本的區分能力，容量越大，對應的一組函數集區分能力
: 就越大；注意容量的大小跟這組函數集自由參數的多少是沒有必然聯系的（不確信這樣
: 說是否合適），因為函數集{y=sin(w*x+b),w,b(-R}的vc為即為無窮大。
: 還有一個應該注意的問題是：vapnik定義vc維是指能夠找到N個樣本可以被一組函數集打
: 散（不是任意N個樣本都滿足這個條件）的最大N。比如說二維平面上空間上對于所有的
: 線性分類面，能夠找到3個點可以被線性分類面打散，但不是任意三個點都能夠滿足這個
: 條件（是不是？很簡單的，相信你能夠找到這樣的三個點）。
: 再說說svm,說白了就是個線性分類面，不過是定義在高維特征空間上的，跟感知機算法
: 相比就多了一個最大間隔，沒別的，呵呵。（當然，暫時不考慮核函數映射問題）。那
: 為啥最大間隔最好呢？vapnik用vc維解釋這回事：所有把兩類樣本以d間隔分開的線性函
: 數組成的集合，假如記為F(隨便了，statistical learning theory中好像不是這樣記的
: ，忘了),那么d越大，函數集F的VC維就越小（vapnik的書有證明），d取極限情況不就是
: 最大間隔超平面嗎？
: 那為何vc維越小越好呢，就是因為這時推廣能力（或者說泛化能力，generalization，
: 隨呢咋叫）好。統計學習理論中被叫爛了的那個結構風險最小化就是說這個事的。簡單
: 的說就是推廣能力有兩個因素決定：訓練錯誤和置信范圍（置信范圍這個叫法很土），
: (以下引言省略 ... ...)


bjxue (南方小孩) 于Mon Apr 14 20:41:02 2003)
提到：

我認為不一定的說


對與不同的要求應該有不同的VC維


從張的那本書上也可以看出的


VC維太小了，期望風險也會大的


我們要的是期望風險最小-----這樣的話我們就可以構造一個函數集


使他的VC維滿足期望風險最小

【 在 minus 的大作中提到: 】

: 真的是VC維越小越好嗎??

: 【 在 mnls (蒙娜麗莎的微笑) 的大作中提到: 】

: (以下引言省略...)



GzLi (笑梨) 于Mon Apr 14 22:07:28 2003)
提到：

您沒有看明白mnls的話，
這個vc維最小的前提是數據可分，是利用間隔最大來取得vc維最小，
這里要強調的就是間隔的概念請先清楚了。
所以這是一個矛盾，一方面希望間隔大，一方面數據還要可分。
一方面置信范圍要小，一方面經驗風險要小。
最終是一個妥協。

【 在 minus (qq) 的大作中提到: 】
: 真的是VC維越小越好嗎??
: 【 在 mnls (蒙娜麗莎的微笑) 的大作中提到: 】
: (以下引言省略 ... ...)


minus (qq) 于Mon Apr 14 22:24:29 2003)
提到：

明白，呵呵。
看書上那個公式是間隔越大VC維越小，二者一致，都使得置信范圍
變小，而經驗風險可能會變大，是這個意思吧？
就是在結構選擇上不知道有沒有什么相對明確可操作的指導原則

【 在 GzLi (笑梨) 的大作中提到: 】
: 您沒有看明白mnls的話，
: 這個vc維最小的前提是數據可分，是利用間隔最大來取得vc維最小，
: 這里要強調的就是間隔的概念請先清楚了。
: 所以這是一個矛盾，一方面希望間隔大，一方面數據還要可分。
: 一方面置信范圍要小，一方面經驗風險要小。
: 最終是一個妥協。
: 【 在 minus (qq) 的大作中提到: 】


fpzh (fpzh) 于Mon Apr 14 23:26:55 2003)
提到：

所以我覺得，帶松弛變量的軟邊緣分類器是不是比不帶松弛變量的分類器更符合SRM的思
想呢。

【 在 GzLi (笑梨) 的大作中提到: 】
: 您沒有看明白mnls的話，
: 這個vc維最小的前提是數據可分，是利用間隔最大來取得vc維最小，
: 這里要強調的就是間隔的概念請先清楚了。
: 所以這是一個矛盾，一方面希望間隔大，一方面數據還要可分。
: 一方面置信范圍要小，一方面經驗風險要小。
: 最終是一個妥協。
: 【 在 minus (qq) 的大作中提到: 】


bjxue (南方小孩) 于Tue Apr 15 08:31:06 2003)
提到：

哦，原來是這樣。明白明白

以后看書，我還要仔細一點

我要多想一點了

【 在 mnls 的大作中提到: 】

: vc維就是一個系數，這個系數就是為了度量一組函數集的容量(capacity)。注意這里..
: “函數”是廣義的，線性函數、多項式函數當然都是函數；對于一個多蹭的神經網絡..
: 權值大小不知道（訓練神經元網絡就是為了確定權值），每組權值就可以認為對應一..
: 函數。

: 而容量就反映了一組函數集對樣本的區分能力，容量越大，對應的一組函數集區分能..
: 就越大；注意容量的大小跟這組函數集自由參數的多少是沒有必然聯系的（不確信這..
: 說是否合適），因為函數集{y=sin(w*x+b),w,b(-R}的vc為即為無窮大。

: 還有一個應該注意的問題是：vapnik定義vc維是指能夠找到N個樣本可以被一組函數