發信人: GzLi (笑梨), 信區: DataMining
標  題: [合集]第七章的幾個重要的概念
發信站: 南京大學小百合站 (Tue Jan  7 11:02:10 2003)

nohau (nohau) 于Thu Jan  2 15:58:28 2003)
提到：

列出了第七章的幾個重要的概念.

我覺得這些概念是第七章的主要內容,準確的把握這幾個概念是下一步學習的基礎.

Chapter 7 

Concepts:

7.2 

真實錯誤率

True error: the true error of hypothesis h with respect to target concept c an
d distribution D is the probability that h will misclassify an instance drawn 
at random according to D.

       

Note:

The true error depend on the unknown distribution D .


訓練錯誤率

Training error: the probability of training examples misclassified by h.


Note:

1.The training error can be observed by the learner directly, and the true err
or can not.

2.The main problem of learning complexity is: “how probability of  the observ
ed training error for h gives a misleading estimate of the true error.”


樣本錯誤率

Sample error:(defined in chapter 5) The sample error of a hypothesis with resp
ect to some sample S of instances drawn from X is the faction of S that is mis
classified. 


Note:

If S is the set of the training data, the sample error is the training error.


可ＰＡＣ學習

Consider some class C of possible target concepts and a learner using hypothes
is space  H. If a learner L conform two things, C is PAC-learnable by L using 
H.: First, L must with arbitrarily high probability (1-d) output a hypothesis 
having arbitrarily low error (e). Second, it must be efficiently, in time that
 grows at most polynomially with 1/e and 1/d.


7.3

樣本復雜度

Sample complexity

The growth in the number of  required training examples with problem size, cal
led the complexity of the learning problem.


一致學習器

Consistent learner:

If a learner output hypothesis that perfectly fit the training data, it is cal
led consistent learner. 


e-詳盡

e-exhausted: The version space VSH,D is said to e-exhausted with respect to c 
and D, if every hypothesis h in VSH,D has error less than e with respect to c 
and D.



GzLi (笑梨) 于Thu Jan  2 17:35:52 2003)
提到：

這幾個概念的確很重要。
但本章主要講的還是我在5577文中提到的幾個概念。
你覺得我說的是否正確嗎？，我自己也不知道這么說是不是確切。
我們討論一下吧。

【 在 nohau (nohau) 的大作中提到: 】
: 列出了第七章的幾個重要的概念.
: 我覺得這些概念是第七章的主要內容,準確的把握這幾個概念是下一步學習的基礎.
: Chapter 7 
: Concepts:
: 7.2 
: 真實錯誤率
: True error: the true error of hypothesis h with respect to target concept c an
: d distribution D is the probability that h will misclassify an instance drawn 
: at random according to D.
:        
: Note:
: The true error depend on the unknown distribution D .
: 
: 訓練錯誤率
: Training error: the probability of training examples misclassified by h.
: 
: Note:
: 1.The training error can be observed by the learner directly, and the true err
: or can not.
: 2.The main problem of learning complexity is: “how probability of  the observ
: (以下引言省略 ... ...)


nohau (nohau) 于Thu Jan  2 20:23:33 2003)
提到：

版主發的文里講的是這一章的概括，我只是今天下午把前三節看完了，把看的主要內容寫
出來了，我還是新手，請版主多指教，呵呵。

【 在 nohau 的大作中提到: 】

: 列出了第七章的幾個重要的概念.

: 我覺得這些概念是第七章的主要內容,準確的把握這幾個概念是下一步學習的基礎.

: Chapter 7 

: Concepts:

: 7.2 

: 真實錯誤率

: True error: the true error of hypothesis h with respect to target concept ..
: d distribution D is the probability that h will misclassify an instance dr..
: at random according to D.

:        

: Note:

: The true error depend on the unknown distribution D .

: 

: 訓練錯誤率

: Training error: the probability of training examples misclassified by h.

: 

: Note:

: 1.The training error can be observed by the learner directly, and the true..
: or can not.

: 2.The main problem of learning complexity is: “how probability of  the ob..
: (以下引言省略...)



txytxy (nils) 于Thu Jan  2 21:07:16 2003)
提到：

我的理解如下，請同志們批評：

　　主動學習的最少訓練數為log!H!,監督學習為n+1,為了討論隨機采樣方式下的樣本復雜
度，從計算假設的真實誤差入手。“誤差”即為錯誤的判斷。

　　在樣本確定的情況下，可以確切計算出在確定范圍內某個“假設”的錯誤判斷率，這
就是“訓練錯誤率”。

　　在樣本不確定的情況下，即隨機按Ｄ分布抽取一批樣本時，計算假設的真實誤差，實
際上就是計算該假設對隨機樣本的錯誤判斷的概率，這就是“真實錯誤率”。

　　因此“訓練錯誤率”和“真實錯誤率”雖然都是“錯誤率”，但一個是百分比，一個
是概率，計算方法大不一樣。

　　進一步，由于Ｄ未知，所以所謂的“真實錯誤率”不能直接計算，只能靠樣本誤差來
逼近，思路是，在樣本誤差為０的情形下（即該假設屬于VS），如果我們能夠確認它所在
的VS是e-窮盡的，則可推知，該ｈ的“真實錯誤率”必然是有界的，這個界是由假設空間
的大小和訓練樣本數共同定義的，這樣就得到了隨機采樣方式下的樣本復雜度，即最少要
訓練書上（7.2)次。

     ps:關于定理7.1證明中，“由于已知有ｋ個假設錯誤率大于ｅ，那么至少有一個與所
有ｍ個訓練樣例都不一致的概率最多為：”我覺得這句話中“不一致”，應該為“一致”
，大家以為呢？


【 在 nohau 的大作中提到: 】

: 列出了第七章的幾個重要的概念.

: 我覺得這些概念是第七章的主要內容,準確的把握這幾個概念是下一步學習的基礎.

: Chapter 7 

: Concepts:

: 7.2 

: 真實錯誤率

: True error: the true error of hypothesis h with respect to target concept ..
: d distribution D is the probability that h will misclassify an instance dr..
: at random according to D.

:        

: Note:

: The true error depend on the unknown distribution D .

: 

: 訓練錯誤率

: Training error: the probability of training examples misclassified by h.

: 

: Note:

: 1.The training error can be observed by the learner directly, and the true..
: or can not.

: 2.The main problem of learning complexity is: “how probability of  the ob..
: (以下引言省略...)



GzLi (笑梨) 于Thu Jan  2 22:46:37 2003)
提到：

我也是初學，大家多討論。
我覺得這個沒有錯誤，是“不一致”，因為這個概率是“不一致”的概率，而不是
“一致”的概率。
不知道其它同志的意思是什么？

【 在 txytxy (nils) 的大作中提到: 】
:      ps:關于定理7.1證明中，“由于已知有ｋ個假設錯誤率大于ｅ，那么至少有一個..
: 有ｍ個訓練樣例都不一致的概率最多為：”我覺得這句話中“不一致”，應該為“一致”
: ，大家以為呢？
: 
: 【 在 nohau 的大作中提到: 】
: (以下引言省略 ... ...)


nohau (nohau) 于Fri Jan  3 09:15:37 2003)
提到：

 同意txytxy的意見,我也認為應該是"一致",因為任意假設真實錯誤率大于e,且與一個隨即
抽樣一致的可能性為(1-e),因此k個真實錯誤率大于e的假設中,至少有一個與所有m個樣例
一致的概率最多為:k(1-e)^m.

這個概率的意義在于它是"壞"假設的概率,即真實錯誤率大于e,但是滿足了所有的訓練樣例
的假設的概率.

【 在 nohau 的大作中提到: 】

: 列出了第七章的幾個重要的概念.

: 我覺得這些概念是第七章的主要內容,準確的把握這幾個概念是下一步學習的基礎.

: Chapter 7 

: Concepts:

: 7.2 

: 真實錯誤率

: True error: the true error of hypothesis h with respect to target concept ..
: d distribution D is the probability that h will misclassify an instance dr..
: at random according to D.

:        

: Note:

: The true error depend on the unknown distribution D .

: 

: 訓練錯誤率

: Training error: the probability of training examples misclassified by h.

: 

: Note:

: 1.The training error can be observed by the learner directly, and the true..
: or can not.

: 2.The main problem of learning complexity is: “how probability of  the ob..
: (以下引言省略...)



txytxy (nils) 于Fri Jan  3 16:58:08 2003)
提到：

1.“劃分”：相當于樣本集上的一個目標概念。n個樣本上最多有2^n個概念。

2.“打散”：如果樣本集上存在的每個目標概念，都有一個假設與之對應，則該假設空間
Ｈ“打散”了該樣本集S。換言之，如果Ｈ能識別出Ｓ上存在的所有目標概念，則Ｈ打散了
Ｓ。

3.樣本大小與假設空間的關系：樣本空間越大，則上含的概念越多，打散它就越困難。給
定假設空間，它能打散的樣本空間是有限的，能打散的最大一個樣本空間的大小稱為“vc
維”。


【 在 nohau 的大作中提到: 】

: 列出了第七章的幾個重要的概念.

: 我覺得這些概念是第七章的主要內容,準確的把握這幾個概念是下一步學習的基礎.

: Chapter 7 

: Concepts:

: 7.2 

: 真實錯誤率

: True error: the true error of hypothesis h with respect to target concept ..
: d distribution D is the probability that h will misclassify an instance dr..
: at random according to D.

:        

: Note:

: The true error depend on the unknown distribution D .

: 

: 訓練錯誤率

: Training error: the probability of training examples misclassified by h.

: 

: Note:

: 1.The training error can be observed by the learner directly, and the true..
: or can not.

: 2.The main problem of learning complexity is: “how probability of  the ob..
: (以下引言省略...)