機(jī)器學(xué)習(xí)：計(jì)算學(xué)習(xí)理論-資料下載頁
2025-08-01 15:04本頁面
【正文】 概念 c，令 MA(c)代表 A為了確切學(xué)到 c，在所有可能訓(xùn)練樣例序列中出錯(cuò)的最大值 ? 對(duì)于任意非空概念類 C，令 MA(C)=maxc?CMA(c) ? 定義： C為任意非空概念類， C的最優(yōu)出錯(cuò)界限定義為Opt(C)是所有可能學(xué)習(xí)算法 A中 MA(C)的最小值 )(mi n)( 學(xué) 習(xí) CMCO p t AA 算法?? 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 45 最優(yōu)出錯(cuò)界限（ 2） ? 非形式地說， Opt(C)是 C中最難的那個(gè)目標(biāo)概念使用最不利的訓(xùn)練樣例序列用最好的算法時(shí)的出錯(cuò)次數(shù) ? Littlestone1987證明了 ||lo g)()()( 2 CCMCO p tCVC H a lv in g ??? 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 46 加權(quán)多數(shù)算法 ? Halving算法的更一般形式稱為加權(quán)多數(shù)算法 ? 加權(quán)多數(shù)算法通過在一組預(yù)測算法中進(jìn)行加權(quán)投票來作出預(yù)測，并通過改變每個(gè)預(yù)測算法的權(quán)來學(xué)習(xí) ? 加權(quán)多數(shù)算法可以處理不一致的訓(xùn)練數(shù)據(jù)，因?yàn)樗粫?huì)消除與樣例不一致的假設(shè)，只是降低其權(quán) ? 要計(jì)算加權(quán)多數(shù)算法的出錯(cuò)數(shù)量邊界，可以用預(yù)測算法組中最好的那個(gè)算法的出錯(cuò)數(shù)量 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 47 加權(quán)多數(shù)算法（ 2） ? 加權(quán)多數(shù)算法一開始將每個(gè)預(yù)測算法賦予權(quán)值 1，然后考慮訓(xùn)練樣例，只要一個(gè)預(yù)測算法誤分類新訓(xùn)練樣例，它的權(quán)被乘以某個(gè)系數(shù) β， 0=β1。 –如果 β=0，則是 Halving算法 –如果 β0，則沒有一個(gè)預(yù)測算法會(huì)被完全去掉。如果一算法誤分類一個(gè)樣例，那么它的權(quán)值變小 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 48 加權(quán)多數(shù)算法（ 3） ? ai代表算法池 A中第 i個(gè)預(yù)測算法， wi代表與 ai相關(guān)聯(lián)的權(quán)值 ? 對(duì)所有 i，初始化 wi?1 ? 對(duì)每個(gè)訓(xùn)練樣例 x, c(x)做： – 初始化 q0和 q1為 0 – 對(duì)每個(gè)預(yù)測算法 ai ? 如果 ai(x)=0，那么 q0?q0+wi ? 如果 ai(x)=1，那么 q1?q1+wi – 如果 q1q0，那么預(yù)測 c(x)=1 – 如果 q0q1，那么預(yù)測 c(x)=0 – 如果 q0=q1，那么對(duì) c(x)隨機(jī)預(yù)測為 0或 1 – 對(duì)每個(gè)預(yù)測算法 ai ? 如果 ai(x)?c(x)，那么 wi?βwi 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 49 加權(quán)多數(shù)算法（ 4） ? 定理 ：加權(quán)多數(shù)算法的相對(duì)誤差界限 – 令 D為任意的訓(xùn)練樣例序列，令 A為任意 n個(gè)預(yù)測算法集合，令 k為 A中任意算法對(duì)樣例序列 D的出錯(cuò)次數(shù)的最小值。那么使用 β=1/2的加權(quán)多數(shù)算法在 D上出錯(cuò)次數(shù)最多為： (k+log2n) ? 證明： – 可通過比較最佳預(yù)測算法的最終權(quán)和所有算法的權(quán)之和來證明。令 aj表示 A中一算法，并且它出錯(cuò)的次數(shù)為最優(yōu)的 k次，則與 aj關(guān)聯(lián)的權(quán) wj將為 (1/2)k。 A中所有 n個(gè)算法的權(quán)的和 ， W的初始值為 n，對(duì)加權(quán)多數(shù)算法的每次出錯(cuò)， W被減小為最多 ，其原因是加權(quán)投票占少數(shù)的算法最少擁有整個(gè)權(quán) W的一半值，而這一部分將被乘以因子1/2。令 M代表加權(quán)多數(shù)算法對(duì)訓(xùn)練序列 D的總出錯(cuò)次數(shù)，那么最終的總權(quán) W最多為 n(3/4)M – 由 ，得 ? 意義：加權(quán)多數(shù)算法的出錯(cuò)數(shù)量不會(huì)大于算法池中最佳算法出錯(cuò)數(shù)量，加上一個(gè)隨著算法池大小對(duì)數(shù)增長的項(xiàng)，再乘以一常數(shù)因子 ??? ni iwW 1W43Mk n ????????????? 4321)lo g()43(lo g)lo g(222 nknkM ????? 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 50 小結(jié) ? 可能近似正確模型（ PAC）針對(duì)的算法從某概念類 C中學(xué)習(xí)目標(biāo)概念，使用按一個(gè)未知但固定的概念分布中隨機(jī)抽取的訓(xùn)練樣例，它要求學(xué)習(xí)器可能學(xué)習(xí)到一近似正確的假設(shè)，而計(jì)算量和訓(xùn)練樣例數(shù)都只隨著 1/?、 1/?、實(shí)例長度和目標(biāo)概念長度的多項(xiàng)式級(jí)增長 ? 在 PAC學(xué)習(xí)模型的框架下，任何使用有限假設(shè)空間 H的一致學(xué)習(xí)器，將以 1?的概率輸出一個(gè)誤差在 ?內(nèi)的假設(shè)，所需的訓(xùn)練樣例數(shù) m滿足 ? ?||ln)/1ln (1 Hm ?? ?? 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 51 小結(jié)（ 2） ? 不可知學(xué)習(xí)考慮更一般的問題：學(xué)習(xí)器不假定目標(biāo)概念所在的類別，學(xué)習(xí)器從訓(xùn)練數(shù)據(jù)中輸出 H中有最小誤差率的假設(shè)。學(xué)習(xí)保證以概率1?從 H中最可能的假設(shè)中輸出錯(cuò)誤率小于 ?的假設(shè)，需要的隨機(jī)抽取的訓(xùn)練樣例數(shù)目 m滿足 ? 學(xué)習(xí)器考慮的假設(shè)空間的復(fù)雜度對(duì)所需樣例的數(shù)目影響很大，而衡量假設(shè)空間復(fù)雜度的一個(gè)有用的度量是 VC維。 VC維是可被 H打散的最大實(shí)例集的大小 ? ?||ln)/1ln (2 1 2 Hm ?? ?? 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 52 小結(jié)（ 3） ? 在 PAC模型下以 VC(H)表示的足以導(dǎo)致成功學(xué)習(xí)的訓(xùn)練樣例數(shù)目的上界和下界分別是： ? 另一種學(xué)習(xí)模式稱為出錯(cuò)界限模式，用于分析學(xué)習(xí)器在確切學(xué)習(xí)到目標(biāo)概念之前會(huì)產(chǎn)生的誤分類次數(shù) – Halving算法在學(xué)習(xí)到 H中的任意目標(biāo)概念前會(huì)有至多 log2|H|次出錯(cuò) – 對(duì)任意概念類 C，最壞情況下最佳算法將有 Opt(C)次出錯(cuò)，滿足 VC(C)=Opt(C)=log2|C| ? ?)/13(lo g)(8)/2(lo g41 22 ??? HVCm ?? ?????? ?? ??? 32 1)(),/1lo g (1m a x CVCm 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 53 小結(jié)（ 4） ? 加權(quán)多數(shù)算法結(jié)合了多個(gè)預(yù)測算法的加權(quán)投票來分類新的實(shí)例，它基于這些預(yù)測算法在樣例序列中的出錯(cuò)來學(xué)習(xí)每個(gè)算法的權(quán)值。加權(quán)多數(shù)算法產(chǎn)生的錯(cuò)誤界限可用算法池中最佳預(yù)測算法的出錯(cuò)數(shù)來計(jì)算 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 54 補(bǔ)充讀物 ? 計(jì)算學(xué)習(xí)理論中許多早期的工作針對(duì)的問題是：學(xué)習(xí)器能否在極限時(shí)確定目標(biāo)概念 ? Gold1967給出了極限模型下的確定算法 ? Angluin1992給出了一個(gè)好的綜述 ? Vapnik1982詳細(xì)考察了一致收斂 ? Valiant1984給出了 PAC學(xué)習(xí)模型 ? Haussler1988討論了 ?詳盡變型空間 ? Bluer et PAC模型下的一組有用的結(jié)論 ? Kearns amp。 Vazirani1994提供了計(jì)算學(xué)習(xí)理論中許多結(jié)論的優(yōu)秀的闡述 ? 會(huì)議：計(jì)算學(xué)習(xí)理論年會(huì) COLT ? 雜志：機(jī)器學(xué)習(xí)的特殊欄目
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1