• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    二維歐氏空間內(nèi)線性凸區(qū)域概念的PAC學(xué)習(xí)算法

    2019-09-10 07:22許道云
    關(guān)鍵詞:實(shí)例算法函數(shù)

    許道云

    摘 要:實(shí)例空間X的一個子集規(guī)定一個概念,表現(xiàn)為一個函數(shù)c:X→{0,1}。給定X上一個分布D,可能近似正確(PAC)學(xué)習(xí)算法的目的是基于獨(dú)立同分布樣本S,由算法產(chǎn)生一個近似函數(shù)hS,以高概率保證它與目標(biāo)函數(shù)c的誤差不超過給定誤差值。如果存在這樣的算法其樣本復(fù)雜性及時間復(fù)雜性受多項(xiàng)式界,則認(rèn)為目標(biāo)概念可以有效PAC學(xué)習(xí)。本文討論二維歐氏空間上有界線性凸區(qū)域定義的目標(biāo)概念的學(xué)習(xí)理論和方法,證明了有界線性凸區(qū)域定義的目標(biāo)概念是有效PAC可學(xué)習(xí)的,其方法可以推廣到n維歐氏空間上由超平面界定的有界凸區(qū)域?qū)?yīng)的目標(biāo)概念學(xué)習(xí)。

    關(guān)鍵詞:

    二維歐氏空間;線性凸區(qū)域;概念學(xué)習(xí);PAC算法

    中圖分類號:TP301.6

    文獻(xiàn)標(biāo)識碼: A

    在機(jī)器學(xué)習(xí)中,對給定實(shí)例進(jìn)行分類是一種基本處理方法,其中二分類是重要而基礎(chǔ)的分類問題。當(dāng)實(shí)例空間較大或復(fù)雜時,精準(zhǔn)分類變得復(fù)雜或困難,依采樣進(jìn)行近似分類顯得有效和實(shí)用??赡芙普_(Probably Approximately Correct, PAC)算法提供了一種學(xué)習(xí)架構(gòu),其原理來源于依概率收斂假設(shè)。假定實(shí)例空間依賴于某個分布,通過獨(dú)立取樣得到容量為m的樣本S,如果存在一個算法A能夠產(chǎn)生一個輸出函數(shù)hS,當(dāng)m趨于無窮大時,hS依概率收斂于目標(biāo)函數(shù)c是PAC可學(xué)習(xí)的。形式上,對于任意給的誤差參數(shù)0<ε<1以及可靠性參數(shù)0<δ<1,存在一個正整數(shù)M,當(dāng)樣本容量m超過M時,算法輸出一個近似分類函數(shù)hS,至少以概率為(1-δ)確保hS與目標(biāo)分類函數(shù)c的誤差不超過ε。如果存在這樣的算法,其樣本復(fù)雜性M和算法的時間復(fù)雜性受1/ε,1/δ的多項(xiàng)式界,則稱目標(biāo)概念c是可以有效PAC學(xué)習(xí)的。PAC學(xué)習(xí)中,往往加強(qiáng)到對目標(biāo)概念集C、任意分布D下尋找有效PAC學(xué)習(xí)算法。如果這樣的算法存在,則稱概念集C是可以有效PAC學(xué)習(xí)的。

    在本文中,假定實(shí)例空間X為二維歐氏空間R2,R2的一個子集的特征函數(shù)c:R2→{0,1}規(guī)定一個概念。文章重點(diǎn)討論有界線性凸區(qū)域規(guī)定的概念的PAC學(xué)習(xí)理論和方法,線性凸區(qū)域是由一組線性不等式界定的區(qū)域{(x,y):aix+biy≤ci(i=1,2,……,k)},有界性指區(qū)域內(nèi)的點(diǎn)被一個有界矩形(或圓)包含,目標(biāo)概念c定義為:c(x,y)=1aix+biy≤ci(i=1,2,……,k)成立。 本文給出了這類概念學(xué)習(xí)的理論和方法,并證明了它是可以有效PAC學(xué)習(xí)的。相關(guān)的理論和方法容易推廣到n維歐氏空間由超平面界定的有界凸區(qū)域規(guī)定的目標(biāo)概念的PAC學(xué)習(xí)。

    這類概念的學(xué)習(xí)可以用于大范圍線性規(guī)劃問題可行解的近似識別。

    1 PAC學(xué)習(xí)基礎(chǔ)知識

    假定X為實(shí)例(數(shù)據(jù))空間,有限集Y作為數(shù)據(jù)標(biāo)記集,通常取Y={0,1}(或{-1,+1})。一個函數(shù)f:X→Y決定X中數(shù)據(jù)一個劃分(分類):f(x)=f(y)當(dāng)且僅當(dāng)x,y屬于同一類。X的一個子集稱為一個概念,可用其特征函數(shù)表示該子集。因此,形式上一個函數(shù)c:X→{0,1}表示一個概念,由概念構(gòu)成的集合C稱為概念集。本文中相關(guān)的基本知識來自于文獻(xiàn)[1], 更多的實(shí)例和應(yīng)用可參考文獻(xiàn)[2-4]。

    5 結(jié)語

    本文將軸對齊矩形概念的有效PAC學(xué)習(xí)方法一般化到歐氏平面上有界線性凸區(qū)域規(guī)定的概念學(xué)習(xí),其思想和方法在于有界線性凸區(qū)域是由有限條(k條)直線圍成的多邊形區(qū)域,在Pr[A]>ε條件下,幾何上可以構(gòu)造目標(biāo)區(qū)域A的邊界內(nèi)側(cè)的一條ε/k-環(huán)帶,該環(huán)帶由k個概率是ε/k區(qū)域構(gòu)成。并且,在條件Pr[A]>ε下,依樣本S從算法產(chǎn)生的目標(biāo)區(qū)域AS與其中之一不相交,此時有PrS~Dm[er(A,AS)>ε]≤k(1-εk)m≤kexp(-mεk)成立,由此估計(jì)算法的樣本復(fù)雜性。文中的方法對于n維歐氏空間中由超平面界定的有界線性凸區(qū)域的PAC學(xué)習(xí)方法與分析是有效的。

    文中的方法適用于數(shù)據(jù)集中的數(shù)據(jù)按預(yù)定凸區(qū)域聚類及誤差分析,也可通過適當(dāng)變換在非歐空間中討論P(yáng)AC學(xué)習(xí)算法。

    參考文獻(xiàn):

    [1]MOHRI M,ROSTAMIZADEH A,TALWAKAR A.Foundations of Machine Learning[M].Cambridge:The MIT Press,2012.

    [2]MITCHELL T M.機(jī)器學(xué)習(xí)[M].曾華軍,等譯.北京:機(jī)械工業(yè)出版社,2012.

    [3]周志華.機(jī)器學(xué)習(xí)[M].北京:清華大學(xué)出版社,2016.

    [4]GOODFELLOW I,BENGIO Y,COURVILLE A.深度學(xué)習(xí)[M].趙申劍,等譯.北京:中國工信出版集團(tuán),2017.

    (責(zé)任編輯:周曉南)

    猜你喜歡
    實(shí)例算法函數(shù)
    Travellng thg World Full—time for Rree
    學(xué)習(xí)算法的“三種境界”
    算法框圖的補(bǔ)全
    算法初步知識盤點(diǎn)
    關(guān)于函數(shù)的一些補(bǔ)充知識
    高中數(shù)學(xué)中二次函數(shù)應(yīng)用舉隅オ
    無獨(dú)有偶 曲徑通幽
    完形填空Ⅱ
    完形填空Ⅰ
    齐齐哈尔市| 浑源县| 长沙市| 萍乡市| 嘉定区| 荔浦县| 万荣县| 建平县| 辽宁省| 静安区| 称多县| 合川市| 梅河口市| 大庆市| 图们市| 普兰店市| 六枝特区| 珠海市| 桦南县| 大洼县| 华亭县| 阳东县| 东辽县| 山西省| 丹巴县| 石台县| 玛多县| 黎川县| 怀安县| 青冈县| 会宁县| 东平县| 伊宁市| 文登市| 民勤县| 长白| 南通市| 永顺县| 阿克苏市| 柳林县| 抚州市|