當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

PAC learning

發(fā)布時間：2024/3/12 编程问答 28 豆豆

生活随笔收集整理的這篇文章主要介紹了 PAC learning 小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

文章目錄

區(qū)間學習(Learning Intervals)
分布和假設(Distributions and Hypothese)
概念集(Concept Class)
PAC學習(probably Approximately Correct Learning)
番外:對區(qū)間學習是PAC可學習性的證明

本文是對Leslie Valiant博文PAC的翻譯，對原文內容有所取舍

區(qū)間學習(Learning Intervals)

從一個游戲開始：
玩家1：心里想一個范圍[a,b]，每次想一個數(shù)字并告訴玩家2這個數(shù)字在不在范圍[a,b]中
玩家2：從玩家1處得到信息后猜測這個范圍[a,b],隨著玩家1每次給出新的數(shù)字,玩家2會更新自己的預測
顯而易見，玩家2是不可能完全猜對的，但他可以盡可能接近準確答案。
假設玩家2在若干次更新后給出了自己的最終預測，玩家1開始源源不斷地給出數(shù)字，如果大多數(shù)情況下這些數(shù)字都落在玩家2所給的答案范圍里，我們就認為玩家2贏得了游戲，并稱這個問題是PAC可學習(PAC-learnable)的。
你可能會想，我把范圍保持為和玩家1給出的在范圍內數(shù)字的最大最小值一致不久可以了嗎？我們之后會證明這種方法確實可以贏得游戲。

分布和假設(Distributions and Hypothese)

把剛才猜數(shù)字的游戲放到一邊，玩家1不再需要每次給出數(shù)字了，他仍然需要想一個范圍 $X$ ，確切地說，一個集合 $X$ ,可以有限，可以無限，隨心所欲。接下來，他需要在這個集合范圍內想一種取出其中元素的規(guī)則，或者說，一個分布 $D$ 。他的任務就是根據 $D$ 從 $X$ 中不斷給出元素，注意，這些元素一定是獨立給出的，也即這些元素獨立同分布(independently and identically distributed),而玩家2則需要盡可能猜出這個分布。
如果一個算法 $A$ 對于 $X$ 上的所有分布 $D$ 都能以大概率在有限步內贏得游戲，我們就說這個問題是PAC可學習的。
問題來了？什么叫贏得游戲呢？或許說是犯錯的概率很小比較好。
玩家1列舉的集合中元素是有對應取值的，而這個取值根據特定函數(shù) $c$ 給出，我們把這個函數(shù)叫做概念(concept)或者目標，玩家2最終的目標，就是猜出這個概念。假設通過一些步驟，玩家2給出了他對概念的假設 $h$ ,而正確的概念是 $c$ ,如果 $h (x)$ 和 $c (x)$ 不相等，自然就是 $h$ 對于元素 $x$ 判斷出錯了，也就產生了誤差(error):
$errorc,Dh=PD(h(x)≠c(x))error_{c,D}h = P_D(h(x) \ne c(x))$
于是我們說：
如果一個算法 $A$ 對于 $X$ 上的所有分布 $D$ 和所有概念 $c$ ,都能以在有限步內給出一個假設，并且大概率該假設誤差很小，我們就說這個問題是PAC可學習的。

概念集(Concept Class)

概念集 $C$ 是一系列 $\rightarrow \{0,1\}$ 函數(shù)的集合,over

這么說似乎太簡略了，并且這個 $C$ 似乎太龐大了，因此，我們假設我們會知道關于 $C$ 的一些知識，于是我們說:
如果一個算法 $A$ 對于 $X$ 上的所有分布 $D$ 和所有概念 $\in C$ ,都能以在有限步內給出一個假設，并且大概率該假設誤差很小，我們就說 $C$ 是PAC可學習的。

PAC學習(probably Approximately Correct Learning)

把游戲拋到一邊吧，來嚴肅地聊點東西。

我們所真正關心的其實是是否存在一個算法可以對于任意數(shù)據都給出一個好的假設。我們也可以想見，對數(shù)據的認知越多，我們給的假設一定就會越好，但對數(shù)據認知越多，我們所需的時間也就越多，因此我們需要在誤差和學習數(shù)據數(shù)量上做一個平衡。

我們現(xiàn)在可以對前文所說的很小，大概率下定義了。

誤差很小：我們定義參數(shù) $\epsilon <1/2$ 表示誤差，我們期望大概率 $errorc,D(h)≤?error_{c,D}(h) \le \epsilon$ ，對誤差有一定要求，我們自然也會允許學習數(shù)據數(shù)量多一點點，我們希望算法運行時間是關于 $1?\frac{1}{\epsilon}$ 的多項式函數(shù)

大概率:我們定義參數(shù) $\delta < 1/2$ 表示我們運行算法誤差較大的概率，也就是說，有 $1?δ1-\delta$ 的概率算法誤差都小于 $?\epsilon$ ,即我們希望:
$PD(errc,D(h)<?)>1?δP_D(err_{c,D}(h) < \epsilon) > 1 - \delta$

我們對算法運行時間也會再放寬一點，我們希望算法運行時間是關于 $1?\frac{1}{\epsilon}$ 和 $1δ\frac{1}{\delta}$ 的多項式函數(shù)

我們終于可以給PAC可學習下一個精準的定義了:
定義: $X$ 是一個集合, $C$ 是 $X$ 上的概念集,如果有運行時間為 $O(poly(1?,1δ))O(poly(\frac{1}{\epsilon},\frac{1}{\delta}))$ 的算法 $A(?,δ)A(\epsilon,\delta)$ ，有一個先知會告訴它數(shù)據對應的取值(即不考慮此處時間復雜度)，對于任意 $\in C$ , $X$ 上的分布 $D$ ,以及 $\epsilon <1/2,0 < \delta < 1/2$ ,都有:
$PD(errc,D(h)≤?)≥1?δP_D(err_{c,D}(h) \le \epsilon) \ge1 - \delta$
那么 $C$ 是PAC可學習的
完美！

番外:對區(qū)間學習是PAC可學習性的證明

在經過一番努力后，玩家2給出了自己預測的區(qū)間 $I$ ，而正確區(qū)間是 $J$ ，根據區(qū)間預測的方法我們自然有 $\subset J$ ,并且有:
$errorJ,D≤Px～D(x∈A)+Px～D(x∈B)error_{J,D} \le P_{x \sim D}(x \in A) + P_{x \sim D}(x \in B)$ ,如圖所示

我們的目標是 $errorJ,D≤?error_{J,D} \le \epsilon$ ,如果 $A, B$ 區(qū)間占區(qū)間總長度(出錯概率)均不超過 $?/2\epsilon/2$ ，那么誤差就自然有保證了，事情并不往往遂人愿，我們假設 $A^{'}$ 占區(qū)間總長度 $?/2\epsilon/2$ ,如下圖所示:

某一個數(shù)據不在 $A^{'}$ 范圍內概率為 $1??/21-\epsilon/2$ ,如果我們查詢了 $m$ 個數(shù)據，這 $m$ 個數(shù)據均不在 $A^{'}$ 內概率為
$PD(A′?A)≤(1??/2)mP_D(A' \subset A ) \le (1-\epsilon/2)^m$ ,
$m$ 個數(shù)據均不在 $A^{'}$ 或對應右端的 $B^{'}$ 端的概率為
$PD(errorJ,D>?)≤2?(1??/2)mP_D(error_{J,D} \gt \epsilon) \le 2*(1-\epsilon/2)^m$
為了達到我們的目標，我們需要滿足
$2?(1??/2)m<δ2*(1-\epsilon/2)^m \lt \delta$
根據 $\le e^{-x}$ ，我們需要求解
$2e??m/2≤δ2e^{-\epsilon m/2 } \le \delta$
得到 $\ge (2/\epsilon log(2/\delta))$
也就是只要我們得到 $(2/?log(2/δ))(2/\epsilon log(2/\delta))$ 以上，就可以滿足對錯誤率和出錯概率的要求，換言之，這個問題是PAC可學習的

總結

以上是生活随笔為你收集整理的PAC learning的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

pac
learning