摘要 在很多實(shí)際應(yīng)用中，隨著數(shù)據(jù)采集技術(shù)和存儲(chǔ)技術(shù)的發(fā)展，獲取大量的無(wú)標(biāo) 號(hào)樣本已變得非常容易，而獲取有標(biāo)號(hào)樣本通常需要付出很大的代價(jià)。因而，相 對(duì)于大量的無(wú)標(biāo)號(hào)樣本，有標(biāo)號(hào)樣本通常會(huì)很少。傳統(tǒng)的無(wú)監(jiān)督學(xué)習(xí)只能利用無(wú) 標(biāo)號(hào)樣本進(jìn)行學(xué)習(xí)，監(jiān)督學(xué)習(xí)只利用少量的有標(biāo)號(hào)樣本學(xué)習(xí)，而半監(jiān)督學(xué)習(xí)則能 同時(shí)利用大量的無(wú)標(biāo)號(hào)樣本和少量的有標(biāo)號(hào)樣本來(lái)進(jìn)行學(xué)習(xí)，因此，半監(jiān)督學(xué)習(xí) 是非常有意義的研究課題。半監(jiān)督學(xué)習(xí)包括半監(jiān)督分類(lèi)、半監(jiān)督回歸、半監(jiān)督聚 類(lèi)和半監(jiān)督維數(shù)約減等幾個(gè)方面。本文以半監(jiān)督學(xué)習(xí)為基礎(chǔ)，主要做了以下一些 工作： 在半監(jiān)督維數(shù)約減方面，提出了一種新的算法i s s d r 。一方面，它能夠充分 利用正負(fù)約束信息，使得在低維空間中不屬于同一類(lèi)的數(shù)據(jù)離的越遠(yuǎn)越好，而屬 于同一類(lèi)的數(shù)據(jù)靠的越近越好。另一方面，引入剩余的大量未標(biāo)記數(shù)據(jù)，利用隱 藏在未標(biāo)記數(shù)據(jù)中的潛在信息，能很好的保持?jǐn)?shù)據(jù)集的全局以及局部結(jié)構(gòu)。實(shí)驗(yàn) 結(jié)果表明，該算法能從大量的未標(biāo)記數(shù)據(jù)以及有限的成對(duì)約束中學(xué)習(xí)出有用的知 識(shí)，實(shí)驗(yàn)證明了該算法的有效性。 在半監(jiān)督分類(lèi)方面，提出了一種新的集成算法e l n p 。它選用一種基于圖的 半監(jiān)督學(xué)習(xí)算法l n p 作為子學(xué)習(xí)器，通過(guò)選擇不同的特征個(gè)數(shù)以及學(xué)習(xí)參數(shù)，利 用子學(xué)習(xí)器分別多次訓(xùn)練進(jìn)行預(yù)測(cè)，然后將其預(yù)測(cè)結(jié)果按投票方式進(jìn)行集成，從 而得到最終的學(xué)習(xí)結(jié)果。實(shí)驗(yàn)表明e l n p 算法比僅使用單一的半監(jiān)督分類(lèi)器有更 強(qiáng)的泛化能力，能有效的提高分類(lèi)精度。 關(guān)鍵詞：半監(jiān)督學(xué)習(xí)維數(shù)約減集成學(xué)習(xí) a b s t r a c t i nm a n yp r a c t i c a la p p l i c a t i o n s ，a l o n gw i t ht h ed e v e l o p m e n to fd a t am i n i n ga n dd a t a s t o r i n gi ti sr e l a t i v e l ye a s i e rt oa c q u i r el a r g en u m b e ro f u n l a b e l e dd a t at h a nl a b e l e dd a t a ， s ot h e r eo f t e na m o u n to fu n l a b e l e dd a t aa n df e wl a b e l e dd a t a t h et r a d i t i o n a l u n s u p e r v i s e dl e a m i n gc a i lo n l yu s eu n l a b e l e dd a t aa n dt h es u p e r v i s e dl e a r n i n go n l yu s e f e wl a b e l e dd a t a t h es u p e r i o r i t yo fs e m i - s u p e r v i s e dl e a r n i n gi st h a ti tc a nu s eb o t h u n l a b e l e dd a t aa n dl a b e l e dd a t a , s oi t sav e r ys i g n i f i c a n c er e s e a r c hs u b j e c t t h e s e m i s u p e r v i s e dl e a r n i n g c o n t a i n ss e m i - s u p e r v i s e dc l a s s i f i c a t i o n ，s e m i s u p e r v i s e d r e g r e s s i o n ，s e m i - s u p e r v i s e dc l u s t e r i n ga n ds e m i - s u p e r v i s e dd i m e n s i o n a l i t yr e d u c t i o n ， e c t b a s e do nt h es e m i - s u p e r v i s e dl e a r n i n g , t h ef o l l o w i n gw o r k sa r ea c c o m p l i s h e d ： i nt e r m so fs e m i - s u p e r v i s e dd i m e n s i o n a l i t yr e d u c t i o n , an e wa l g o r i t h mi ss d ri s p r o p o s e d ：o nt h eo n eh a n d ，i tc a np r e s e r v et h ep o s i t i v ea n dn e g a t i v ec o n s t r a i n t s ，w h i c h m a k e sd i s t a n c e si nt h et r a n s f o r m e dl o w - d i m e n s i o n a ls p a c eb e t w e e ni n s t a n c e si n v o l v e d b yt h en e g a t i v ec o n s t r a i n t ss e ta sl a r g ea sp o s s i b l e ，w h i l ed i s t a n c e sb e t w e e ni n s t a n c e s i n v o l v e db yt h ep o s i t i v ec o n s t r a i n t sa ss m a l la sp o s s i b l e ；o nt h eo t h e rh a n d ，i tc a l la l s o p r e s e r v et h el o c a l a n dg l o b a ls t r u c t u r eb yu s i n gt h ep o t e n t i a li n f o r m a t i o ni nt h e n u m e r o u su n l a b e l e dd a t a 。e x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h a ti tc a l lg e th e l p f u l i n f o r m a t i o nf r o mt h ec o n s t r a i n t sa n dt h el a r g ea m o u n t so fu n l a b e l e dd a t a ，s oi ti sa n e f f e c t i v e n e s sm e t h o d i nt e r m so fs e m i - s u p e r v i s e dc l a s s i f i c a t i o n ，an e we n s e m b l el e a r n i n ga l g o r i t h m e l n pi sp r o p o s e di n t h i sp a p e r , a n di t sb a s el e a r n e r sl n p ( l i n e a rn e i g h b o r h o o d p r o p a g a t i o n ) a r es e l e c t e df r o mo n eo fs s ll e a r n i n ga p p r o a c h e sw i t hg r a p h s w ec h o o s e d i f f e r e n ti n p u ta t t r i b u t e sa n dl e a r n i n gp a r a m e t e r st op r o d u c eas e r i e so fc o m p o n e n t c l a s s i f i e dl e a r n e r s ，a n dc o m b i n et h ep r e d i c t i o n so ft h e s ec o m p o n e n tl e a r n e r sv i a m a j o r i t yv o t i n g ，a tl a s ta t t a i nt h ef i n a ll e a r n i n gp r e d i c t i o nr e s u l t s t h ee x p e r i m e n t a l r e s u l t ss h o wt h a tt h ee - l n pa l g o r i t h mp e r f o r m sb e t t e rt h a nj u s tas i n g l el e a r n e rd o ，a n d i tc a ni m p r o v et h ec l a s s i f i c a t i o np r e c i s i o ne f f e c t i v e l y k e y w o r d ：s e m i - s u p e r v i s e dl e a r n i n g d i m e n s i o n a l i t yr e d u c t i o n e n s e m b l e l e a r n i n g 西安電子科技大學(xué) 學(xué)位論文創(chuàng)新性聲明 秉承學(xué)校嚴(yán)謹(jǐn)?shù)膶W(xué)風(fēng)和優(yōu)良的科學(xué)道德，本人聲明所呈交的論文是我個(gè)人在導(dǎo) 師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。盡我所知，除了文中特別加以標(biāo)注 和致謝中所羅列的內(nèi)容以外，論文中不包含其他人已經(jīng)發(fā)表或撰寫(xiě)過(guò)的研究成果； 也不包含為獲得西安電子科技大學(xué)或其它教育機(jī)構(gòu)的學(xué)位或證書(shū)而使用過(guò)的材 料。與我一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均已在論文中做了明確的說(shuō)明 并表示了謝意。 申請(qǐng)學(xué)位論文與資料若有不實(shí)之處，本人承擔(dān)一切的法律責(zé)任。 本人簽名：l 遠(yuǎn)豁_ i 企 西安電子科技大學(xué) 關(guān)于論文使用授權(quán)的說(shuō)明 本人完全了解西安電子科技大學(xué)有關(guān)保留和使用學(xué)位論文的規(guī)定，即：研究 生在校攻讀學(xué)位期間論文工作的知識(shí)產(chǎn)權(quán)單位屬西安電子科技大學(xué)。學(xué)校有權(quán)保 留送交論文的復(fù)印件，允許查閱和借閱論文；學(xué)校可以公布論文的全部或部分內(nèi) 容，可以允許采用影印、縮印或其它復(fù)制手段保存論文。同時(shí)本人保證，畢業(yè)后 結(jié)合學(xué)位論文研究課題再撰寫(xiě)的文章一律署名單位為西安電子科技大學(xué)。( 保密的 論文在解密后遵守此規(guī)定) 本學(xué)位論文屬于保密，在一年解密后適用本授權(quán)書(shū)。 本人簽名： 導(dǎo)師簽名： 第一章緒論 第一章緒論 1 1 機(jī)器學(xué)習(xí) 學(xué)習(xí)，為什么會(huì)學(xué)習(xí)，如何更好的進(jìn)行學(xué)習(xí)，學(xué)習(xí)的內(nèi)在機(jī)理是什么，這些 都是人類(lèi)一直在積極探索的話(huà)題。學(xué)習(xí)能力是智能行為的一個(gè)非常重要的特征， 但至今人們對(duì)學(xué)習(xí)的機(jī)理尚不完全清楚。使計(jì)算機(jī)具有學(xué)習(xí)能力，這是人工智能 研究者幾十年來(lái)一直夢(mèng)寐以求的目標(biāo)，機(jī)器學(xué)習(xí)研究的目的也是為此。 自從計(jì)算機(jī)問(wèn)世以來(lái)，人們就想知道它們能不能自我學(xué)習(xí)。如果我們理解了 它們學(xué)習(xí)的內(nèi)在機(jī)制，即怎樣使它們能夠根據(jù)經(jīng)驗(yàn)來(lái)自動(dòng)提高自身的學(xué)習(xí)能力， 那帶來(lái)的影響將是空前的。想象一下，在未來(lái)，計(jì)算機(jī)能夠從醫(yī)療記錄中學(xué)習(xí)， 獲取治療新疾病最有效的方法；住宅管理系統(tǒng)能夠分析住戶(hù)的用電模式，以降低 能源消耗；個(gè)人助理軟件能夠跟蹤用戶(hù)的興趣，為其選擇最感興趣的在線(xiàn)早間新 聞。對(duì)計(jì)算機(jī)學(xué)習(xí)的成功實(shí)現(xiàn)將開(kāi)辟出許多全新的應(yīng)用領(lǐng)域，并使其計(jì)算能力和 定制性上升到新的層次。 通過(guò)一些專(zhuān)項(xiàng)成果，我們可以看到機(jī)器學(xué)習(xí)這門(mén)技術(shù)的研究現(xiàn)狀：計(jì)算機(jī)已 經(jīng)能夠成功地識(shí)別人類(lèi)的講話(huà)、預(yù)測(cè)肺炎患者的康復(fù)率、檢測(cè)信用卡的欺詐、在 高速公路上自動(dòng)駕駛汽車(chē)、以接近人類(lèi)世界冠軍的水平對(duì)弈西洋雙陸棋等。在過(guò) 去的幾十年中，無(wú)論是應(yīng)用、算法、理論，還是生物系統(tǒng)的研究，都取得了令人 矚目的發(fā)展和進(jìn)步。 那么，什么是機(jī)器學(xué)習(xí)呢? 機(jī)器學(xué)習(xí)一般被定義為一個(gè)系統(tǒng)自我改進(jìn)的過(guò)程。從最初的基于神經(jīng)元模型 以及函數(shù)逼近論的方法研究，到以符號(hào)演算為基礎(chǔ)的規(guī)則學(xué)習(xí)和決策樹(shù)學(xué)習(xí)的產(chǎn) 生，以及之后的認(rèn)知心理學(xué)中歸納、解釋、類(lèi)比等概念的引入，至最新的計(jì)算學(xué) 習(xí)理論和統(tǒng)計(jì)學(xué)習(xí)的興起，當(dāng)然還包括基于馬爾可夫過(guò)程的增強(qiáng)學(xué)習(xí)，機(jī)器學(xué)習(xí) 一直都在相關(guān)學(xué)科的實(shí)踐應(yīng)用中起著主導(dǎo)作用，研究人員們借鑒了各個(gè)學(xué)科的思 想來(lái)發(fā)展機(jī)器學(xué)習(xí)。 近幾年來(lái)機(jī)器學(xué)習(xí)發(fā)展迅速，已經(jīng)滲透到模式識(shí)別、計(jì)算機(jī)視覺(jué)、數(shù)據(jù)挖掘 等多個(gè)領(lǐng)域，隨著對(duì)計(jì)算機(jī)認(rèn)識(shí)的日益成熟，機(jī)器學(xué)習(xí)將會(huì)在計(jì)算機(jī)科學(xué)和技術(shù) 中扮演越來(lái)越重要的角色。 按照學(xué)習(xí)過(guò)程中有沒(méi)有教師的參與，學(xué)習(xí)可以分為三種基本形式：監(jiān)督學(xué)習(xí)、 增強(qiáng)學(xué)習(xí)和無(wú)監(jiān)督學(xué)習(xí)。而近年來(lái)隨著機(jī)器學(xué)習(xí)的發(fā)展，出現(xiàn)了第四種學(xué)習(xí)形式， 即本文中將要討論的半監(jiān)督學(xué)習(xí)。 2 半監(jiān)督降維和分類(lèi)算法研究 監(jiān)督學(xué)習(xí)：在監(jiān)督學(xué)習(xí)方式中，存在一個(gè)“教師”，它可對(duì)一組給定的輸入提 供應(yīng)有的輸出結(jié)果，學(xué)習(xí)按照“教師的監(jiān)督信息進(jìn)行著，如分類(lèi)。 增強(qiáng)學(xué)習(xí)：增強(qiáng)學(xué)習(xí)的典型做法是，給定一個(gè)輸入樣本，計(jì)算它的輸出類(lèi)別， 把它與已知的類(lèi)別標(biāo)記作比較，根據(jù)差異來(lái)改善分類(lèi)器的性能?！敖處煂?duì)這次分 類(lèi)任務(wù)的完成情況只給出“對(duì) 或“錯(cuò) 的反饋。 無(wú)監(jiān)督學(xué)習(xí)：在無(wú)監(jiān)督學(xué)習(xí)中并沒(méi)有顯式的“教師 ，系統(tǒng)對(duì)輸入樣本“自動(dòng) 形成聚類(lèi)或自然的組織。 半監(jiān)督學(xué)習(xí)g 半監(jiān)督學(xué)習(xí)是近年來(lái)機(jī)器學(xué)習(xí)領(lǐng)域新近提出的一種學(xué)習(xí)方式， 它結(jié)合了監(jiān)督學(xué)習(xí)和無(wú)監(jiān)督學(xué)習(xí)兩種學(xué)習(xí)方式，存在有限的“教師 信息，學(xué)習(xí) 算法能借助這些少量的“教師 信息來(lái)更好的進(jìn)行學(xué)。 1 2 半監(jiān)督學(xué)習(xí)的研究背景及內(nèi)容 隨著互聯(lián)網(wǎng)的普及，網(wǎng)上信息正在呈指數(shù)級(jí)增長(zhǎng)。如何合理地組織這些信息， 以便從茫茫的數(shù)據(jù)世界中檢索到期望的目標(biāo)，并有效地分析這些信息，以便挖掘 出新穎和潛在的有用模式，正在成為網(wǎng)上信息處理的研究熱點(diǎn)。網(wǎng)上信息的分類(lèi) 目錄組織是提高檢索效率和檢索精度的有效途徑，如在利用搜索引擎對(duì)網(wǎng)頁(yè)數(shù)據(jù) 進(jìn)行檢索時(shí)，若能提供查詢(xún)的類(lèi)別信息，必然會(huì)縮小與限制檢索范圍，從而提高 查準(zhǔn)率。同時(shí)，分類(lèi)可以提供信息的良好組織結(jié)構(gòu)，便于用戶(hù)進(jìn)行瀏覽和過(guò)濾信 息。很多大型網(wǎng)站都采用這種組織方式，如m o o 【l 】采用人工方式來(lái)維護(hù)網(wǎng)頁(yè)的目 錄結(jié)構(gòu)；g o o g l e 網(wǎng)站采用一定的排序機(jī)制，使與用戶(hù)最相關(guān)的網(wǎng)頁(yè)排在前面，便 于用戶(hù)瀏覽。d e e r w e s e r 等人【2 j 利用線(xiàn)性代數(shù)的知識(shí)，通過(guò)矩陣的奇異值分解來(lái)進(jìn) 行信息濾波和潛在語(yǔ)義索引，它將文檔在向量空問(wèn)模型中的高維表示投影到低維 的潛在語(yǔ)義空間中，這一方面縮小了問(wèn)題的規(guī)模，另一方面也從一定程度上避免 了數(shù)據(jù)的過(guò)分稀疏現(xiàn)象，它在語(yǔ)言建模視頻檢索及蛋白質(zhì)數(shù)據(jù)庫(kù)等實(shí)際應(yīng)用中取 得了較好的效果。聚類(lèi)分析是文本挖掘的主要手段之一p j ，它的主要作用是：( 1 ) 通過(guò)對(duì)檢索結(jié)果的聚類(lèi)，將檢索到的大量網(wǎng)頁(yè)以一定的類(lèi)別提供給用戶(hù)，使用戶(hù) 能夠快速定位期望的目標(biāo)；( 2 ) 自動(dòng)生成分類(lèi)目錄；( 3 ) 通過(guò)相似網(wǎng)頁(yè)的歸并，便于 分析這些網(wǎng)頁(yè)的共性。k 。均值聚類(lèi)是比較典型的聚類(lèi)算法，另外，自組織映射神 經(jīng)網(wǎng)絡(luò)聚類(lèi)和基于概率分布的貝葉斯層次聚類(lèi)等新的聚類(lèi)算法也正在不斷地被研 制與應(yīng)用。然而大部分的這些聚類(lèi)算法屬于無(wú)監(jiān)督學(xué)習(xí)，它對(duì)解空間的搜索帶有 一定的盲目性，因而聚類(lèi)的結(jié)果在一定程度上缺乏語(yǔ)義特征。同時(shí)，在高維情況 下，選擇合適的距離度量標(biāo)準(zhǔn)變得相當(dāng)困難。而網(wǎng)頁(yè)分類(lèi)是一種監(jiān)督學(xué)習(xí)，它通 過(guò)對(duì)一系列訓(xùn)練樣本的分析來(lái)預(yù)測(cè)未知網(wǎng)頁(yè)的類(lèi)別歸屬，目前已有很多有效的算 法來(lái)實(shí)現(xiàn)網(wǎng)頁(yè)的分類(lèi)，如n a i v eb a y e s i a n ，s v m 等。遺憾的是，獲得大量的帶有 第一章緒論 類(lèi)別標(biāo)注的樣本的代價(jià)是相當(dāng)昂貴的，而這些方法只有通過(guò)大規(guī)模的訓(xùn)練才能獲 得較高精度的分類(lèi)效果。此外，在實(shí)際應(yīng)用中，分類(lèi)體系常常是不一致的，這為 目錄的日常維護(hù)帶來(lái)了一定的困難。針對(duì)這些問(wèn)題，k a m a ln i g a m 等人1 4 提出從帶 有類(lèi)別標(biāo)注和不帶有類(lèi)別標(biāo)注的混合文檔中分類(lèi)w e b 網(wǎng)頁(yè)，它一方面克服了無(wú)監(jiān) 督學(xué)習(xí)中對(duì)求解空間搜索的盲目性；另一方面，它不需要對(duì)大量訓(xùn)練樣本進(jìn)行類(lèi) 別標(biāo)注，只需提供相應(yīng)的類(lèi)主題變量，把網(wǎng)站管理人員從繁瑣的訓(xùn)練樣本的標(biāo)注 中解脫出來(lái)，提高了網(wǎng)頁(yè)分類(lèi)的自動(dòng)性，這種方法就屬于半監(jiān)督學(xué)習(xí)算法。 隨著數(shù)據(jù)采集技術(shù)和存儲(chǔ)技術(shù)的發(fā)展，獲取無(wú)標(biāo)記樣本已變得非常容易。另 一方面，由于有標(biāo)記樣本的獲取需要相關(guān)領(lǐng)域的專(zhuān)家對(duì)樣本進(jìn)行標(biāo)記，因而相對(duì) 比較困難而且代價(jià)昂貴。例如，在醫(yī)學(xué)影像處理中，很容易從醫(yī)院得到大量的醫(yī) 學(xué)影像，但醫(yī)學(xué)專(zhuān)家不可能花費(fèi)大量的時(shí)間和精力來(lái)對(duì)所有的病灶都進(jìn)行標(biāo)記， 只能選擇其中的很少一部分進(jìn)行標(biāo)記。所以在許多實(shí)際應(yīng)用中，通常會(huì)有大量的 無(wú)標(biāo)記的樣本，而有標(biāo)記樣本只占很小的比例。當(dāng)用傳統(tǒng)的監(jiān)督學(xué)習(xí)方法( 比如 分類(lèi)) 來(lái)處理此類(lèi)問(wèn)題時(shí)，由于有標(biāo)記樣本較少，因而訓(xùn)練出來(lái)的分類(lèi)器精度有 限，同時(shí)僅使用少量“昂貴的有標(biāo)記樣本而不利用大量“廉價(jià)的”未標(biāo)記樣本， 則是對(duì)數(shù)據(jù)資源的極大的浪費(fèi)。另一方面，傳統(tǒng)的無(wú)監(jiān)督學(xué)習(xí)方法( 如聚類(lèi)) 則 沒(méi)有利用寶貴的已有標(biāo)記樣本指導(dǎo)聚類(lèi)，因而限制了聚類(lèi)性能的提高。因此，如 何利用大量的未標(biāo)記樣本來(lái)輔助有限的標(biāo)記樣本來(lái)提高學(xué)習(xí)的精確性是面臨的一 個(gè)新問(wèn)題。為了能更好地處理此類(lèi)問(wèn)題，目前在機(jī)器學(xué)習(xí)領(lǐng)域逐漸形成了一種介 于傳統(tǒng)監(jiān)督學(xué)習(xí)和無(wú)監(jiān)督學(xué)習(xí)之間的新的機(jī)器學(xué)習(xí)方法，稱(chēng)之為半監(jiān)督學(xué)習(xí) ( s e m i s u p e r v i s e dl e a r n i n g ) 。與只利用有標(biāo)記樣本的監(jiān)督學(xué)習(xí)以及只利用無(wú)標(biāo)記 樣本的無(wú)監(jiān)督學(xué)習(xí)相比，半監(jiān)督學(xué)習(xí)同時(shí)利用有標(biāo)記樣本和無(wú)標(biāo)記樣本來(lái)學(xué)習(xí)。 由于在諸如文本分類(lèi)等實(shí)際問(wèn)題上的出色性能，半監(jiān)督學(xué)習(xí)已在國(guó)際上引起高度 重視。半監(jiān)督學(xué)習(xí)開(kāi)始成為當(dāng)前國(guó)際機(jī)器學(xué)習(xí)界的一大研究熱點(diǎn)。近幾年來(lái)隨著 機(jī)器學(xué)習(xí)在數(shù)據(jù)分析和數(shù)據(jù)挖掘中的廣泛應(yīng)用，半監(jiān)督學(xué)習(xí)的理論研究成果已經(jīng) 部分地應(yīng)用于實(shí)際問(wèn)題的解決。 半監(jiān)督學(xué)習(xí)包括半監(jiān)督分類(lèi)、半監(jiān)督回歸、半監(jiān)督聚類(lèi)和半監(jiān)督降維。到目 前為止關(guān)于半監(jiān)督分類(lèi)方法的研究相對(duì)較多，并且有很廣泛的應(yīng)用范圍，包括網(wǎng) 頁(yè)分類(lèi)、人臉識(shí)別、目標(biāo)識(shí)別；信息檢索，如形狀信息檢索和手寫(xiě)數(shù)字檢索；圖 像分割等。相比之下，半監(jiān)督降維方面的研究相對(duì)較少。然而，我們?cè)诂F(xiàn)實(shí)生活 中遇到的待處理數(shù)據(jù)大部分是高維空間中的樣本集。比如隨著數(shù)碼產(chǎn)品的發(fā)展， 我們可以得到更清晰的圖片，但為此要付出的代價(jià)是更高維的數(shù)據(jù)，即更大的存 儲(chǔ)空間和更長(zhǎng)的處理時(shí)間，這會(huì)給計(jì)算機(jī)處理帶來(lái)更大負(fù)擔(dān)。而且高維的數(shù)據(jù)中 往往還帶有大量的冗余信息，在機(jī)器學(xué)習(xí)中難以發(fā)現(xiàn)模型的真正變量。因此很多 時(shí)候降維作為一種預(yù)處理過(guò)程是非常必要的。 4 半監(jiān)督降維和分類(lèi)算法研究 1 3 國(guó)內(nèi)外對(duì)半監(jiān)督學(xué)習(xí)研究的進(jìn)展及現(xiàn)狀 半監(jiān)督學(xué)習(xí)是模式識(shí)別和機(jī)器學(xué)習(xí)中的重要研究領(lǐng)域。近幾年隨著機(jī)器學(xué)習(xí) 理論在數(shù)據(jù)分析和數(shù)據(jù)挖掘的實(shí)際問(wèn)題，例如網(wǎng)頁(yè)檢索和文本分類(lèi)、基于生物特 征的身份識(shí)別、圖像檢索和視頻檢索、醫(yī)學(xué)數(shù)據(jù)處理等問(wèn)題中的廣泛應(yīng)用，半監(jiān) 督學(xué)習(xí)在理論和實(shí)際應(yīng)用研究中都獲得了長(zhǎng)足的發(fā)展。半監(jiān)督學(xué)習(xí)主要關(guān)注當(dāng)訓(xùn) 練數(shù)據(jù)的部分信息缺失的情況下，如何獲得具有良好性能和推廣能力的學(xué)習(xí)機(jī)器， 這里的信息缺失涵蓋數(shù)據(jù)的類(lèi)別標(biāo)簽缺失或者存在噪聲，數(shù)據(jù)的部分特征缺失等 多種情況。半監(jiān)督學(xué)習(xí)的理論研究對(duì)于我們深入理解機(jī)器學(xué)習(xí)中的許多重要理論 問(wèn)題，例如數(shù)據(jù)的流形與數(shù)據(jù)的類(lèi)別信息的關(guān)系、缺失數(shù)據(jù)的合理處理、標(biāo)注數(shù) 據(jù)的有效利用、監(jiān)督學(xué)習(xí)和非監(jiān)督學(xué)習(xí)之間的聯(lián)系、主動(dòng)學(xué)習(xí)算法的設(shè)計(jì)等都有 非常重要的指導(dǎo)意義。 自2 0 世紀(jì)八九十年代以來(lái)國(guó)際機(jī)器學(xué)習(xí)界研究者在半監(jiān)督學(xué)習(xí)研究領(lǐng)域展開(kāi) 了廣泛深入的探討和研究。其涵蓋的范圍非常廣泛，例如半監(jiān)督回歸問(wèn)題【5 】；利用 標(biāo)簽和特征維都缺失的數(shù)據(jù)集進(jìn)行學(xué)習(xí)【6 】；標(biāo)簽有噪聲時(shí)的數(shù)據(jù)處理【7 】；對(duì)各種監(jiān) 督學(xué)習(xí)算法進(jìn)行修改，探討如何融入非監(jiān)督數(shù)據(jù)信息【8 】或者對(duì)于非監(jiān)督學(xué)習(xí)算法進(jìn) 行修改，探討監(jiān)督數(shù)據(jù)信息的引入f 9 j ；利用有限混合模型對(duì)數(shù)據(jù)的概率分布進(jìn)行建 ?；蛘呃闷渌Ｐ蛯?duì)數(shù)據(jù)標(biāo)簽關(guān)于特征維的條件概率進(jìn)行建模，利用e m 算法 學(xué)習(xí)模型參數(shù)的半監(jiān)督學(xué)習(xí)的研究【1 0 】；引入合適的數(shù)學(xué)方法進(jìn)行半監(jiān)督學(xué)習(xí)，例 如基于核矩陣的譜分析【l ，高斯隨機(jī)場(chǎng)的利用【1 2 1 ，利用圖論中的方法來(lái)對(duì)于樣本 集進(jìn)行聚類(lèi)分析【1 3 】；半監(jiān)督數(shù)據(jù)的流形分析t 1 4 】等。研究者同時(shí)開(kāi)展了將半監(jiān)督學(xué) 習(xí)和傳統(tǒng)模式識(shí)別和機(jī)器學(xué)習(xí)中的一些問(wèn)題相結(jié)合的研究，例如基于半監(jiān)督學(xué)習(xí) 的特征提取【l6 1 ，半監(jiān)督學(xué)習(xí)和集分類(lèi)器的設(shè)計(jì)【1 7 】等。國(guó)際研究者同時(shí)開(kāi)展了與半 監(jiān)督學(xué)習(xí)有著密切關(guān)聯(lián)的一些相關(guān)研究，具有代表性的是利用半監(jiān)督數(shù)據(jù)和數(shù)據(jù) 的不同特征子集在數(shù)據(jù)的不同視圖上同時(shí)訓(xùn)練具有良好性能的學(xué)習(xí)機(jī)器【i 引。 目前半監(jiān)督學(xué)習(xí)的研究正在繼續(xù)從廣度和深度上不斷進(jìn)行擴(kuò)展。就廣度而言， 一方面不斷有各種傳統(tǒng)的或者新提出的監(jiān)督非監(jiān)督算法的半監(jiān)督情況下的修改算 法出現(xiàn)，另一方面，不斷有新的數(shù)學(xué)方法引入半監(jiān)督學(xué)習(xí)。同時(shí)，半監(jiān)督學(xué)習(xí)探 討的對(duì)象已經(jīng)由簡(jiǎn)單的利用半監(jiān)督數(shù)據(jù)訓(xùn)練擴(kuò)展到半監(jiān)督數(shù)據(jù)的流形分析，半監(jiān) 督數(shù)據(jù)和圖模型的關(guān)系，半監(jiān)督數(shù)據(jù)和基于核學(xué)習(xí)的關(guān)系。換而言之，半監(jiān)督學(xué) 習(xí)已經(jīng)與當(dāng)前機(jī)器學(xué)習(xí)研究的各熱點(diǎn)和重點(diǎn)問(wèn)題的研究緊密聯(lián)系在一起。就深度 而言，已經(jīng)有許多研究探討基于各種不同的有限混合模型的半監(jiān)督學(xué)習(xí)的統(tǒng)一方 法 1 9 j ，基于數(shù)據(jù)的特征視圖的半監(jiān)督學(xué)習(xí)機(jī)器的性能分析【2 0 j ，半監(jiān)督學(xué)習(xí)和主動(dòng) 學(xué)習(xí)相結(jié)合提高學(xué)習(xí)機(jī)器性能【2 l 】，半監(jiān)督學(xué)習(xí)的聚類(lèi)假設(shè)的顯式數(shù)學(xué)表達(dá)1 2 2 】等等。 第一章緒論 半監(jiān)督學(xué)習(xí)的理論研究在未來(lái)的一段時(shí)間將一直是機(jī)器學(xué)習(xí)研究的重點(diǎn)和熱點(diǎn)， 這些研究對(duì)于我們理解學(xué)習(xí)機(jī)器的學(xué)習(xí)機(jī)理以及人機(jī)交互都具有重要的理論意 義。 1 4 論文的研究?jī)?nèi)容及安排 半監(jiān)督維數(shù)約減和半監(jiān)督分類(lèi)是半監(jiān)督學(xué)習(xí)的重要方面，本文主要從以下兩 個(gè)方面做了一些工作： 第一，在對(duì)樣本集進(jìn)行維數(shù)約減方面，本文提出了一種新的半監(jiān)督維數(shù)約減 算法i s s d r ，它不僅能夠分別利用正負(fù)約束對(duì)中的信息，而且還利用了所有剩余 的大量未標(biāo)記數(shù)據(jù)，通過(guò)將其分為鄰域內(nèi)和鄰域外兩個(gè)部分來(lái)挖掘隱藏在其中的 潛在信息，實(shí)驗(yàn)結(jié)果表明，該算法能從大量的未標(biāo)記數(shù)據(jù)以及有限的成對(duì)約束中 學(xué)習(xí)出有用的知識(shí)，實(shí)驗(yàn)證明了該算法的優(yōu)越性。 第二，在對(duì)樣本集進(jìn)行分類(lèi)方面，本文提出了一種新的集成算法e l n p ，它 選用一種基于圖的半監(jiān)督學(xué)習(xí)算法l n p 作為子分類(lèi)器。每個(gè)子分類(lèi)器分別選擇不 同的樣本特征以及學(xué)習(xí)參數(shù)進(jìn)行訓(xùn)練，然后將得到的訓(xùn)練結(jié)果用投票方式進(jìn)行集 成，從而得到最終的學(xué)習(xí)結(jié)果。實(shí)驗(yàn)表明e l n p 算法比僅使用單一的半監(jiān)督分類(lèi) 器有更強(qiáng)的泛化能力。 本文的章節(jié)內(nèi)容安排如下： 第一章，首先簡(jiǎn)要介紹了什么是機(jī)器學(xué)習(xí)以及機(jī)器學(xué)習(xí)的分類(lèi)，引出了半監(jiān) 督學(xué)習(xí)的概念，接著介紹了半監(jiān)督學(xué)習(xí)算法的研究背景及意義，分析了國(guó)內(nèi)外研 究進(jìn)展及現(xiàn)狀，并概述了本文的研究?jī)?nèi)容和章節(jié)安排。 第二章，對(duì)半監(jiān)督學(xué)習(xí)理論進(jìn)行了整體的介紹。首先介紹了半監(jiān)督學(xué)習(xí)的基 礎(chǔ)知識(shí)，然后對(duì)已有分類(lèi)算法的半監(jiān)督學(xué)習(xí)框架和比較成熟的半監(jiān)督學(xué)習(xí)算法分 別進(jìn)行了詳細(xì)介紹。 第三章，從無(wú)監(jiān)督，監(jiān)督，半監(jiān)督三個(gè)方面介紹了已有的維數(shù)約減方法，提 出了一種半監(jiān)督維數(shù)約減方法i s s d r ，同時(shí)進(jìn)行了實(shí)驗(yàn)驗(yàn)證。 第四章，提出了一種基于集成算法的半監(jiān)督算法。首先介紹了集成算法的相 關(guān)知識(shí)以及l(fā) n p 算法的內(nèi)容，然后對(duì)提出的算法進(jìn)行了詳細(xì)的介紹并進(jìn)行了實(shí)驗(yàn) 驗(yàn)證。 6 半監(jiān)督降維和分類(lèi)算法研究 第二章半監(jiān)督學(xué)習(xí)理論 2 1 半監(jiān)督學(xué)習(xí)的基礎(chǔ)知識(shí) 一般認(rèn)為，半監(jiān)督學(xué)習(xí)的研究始于b s h a h s h a h a n i 和d l a n d g r e b e 的工作2 3 1 ， 但未標(biāo)記樣本的價(jià)值實(shí)際上早在上世紀(jì)8 0 年代末就已經(jīng)被一些研究者意識(shí)到了。 d j m i l l e r 和h s u y a r 【2 4 1 認(rèn)為，半監(jiān)督學(xué)習(xí)的研究起步相對(duì)較晚，可能是因?yàn)樵?當(dāng)時(shí)的主流機(jī)器學(xué)習(xí)技術(shù)( 例如前饋神經(jīng)網(wǎng)絡(luò)) 中考慮未標(biāo)記樣本相對(duì)比較困難。 隨著統(tǒng)計(jì)學(xué)習(xí)技術(shù)的不斷發(fā)展，以及利用未標(biāo)記樣本這一需求的同漸強(qiáng)烈，半監(jiān) 督學(xué)習(xí)才在近年來(lái)逐漸成為一個(gè)研究熱點(diǎn)。 半監(jiān)督學(xué)習(xí)的基本設(shè)置是給定一個(gè)來(lái)自某未知分布的有標(biāo)記樣本集 = ( 而，y 1 ) ，( x 2 ，y 2 ) ，( 1 上j ，朋上4 ) ) ，以及一個(gè)未標(biāo)記樣本集u = 西，恐，l ) ，期望 學(xué)得函數(shù)廠(chǎng)：x 專(zhuān)】，可以準(zhǔn)確地對(duì)樣本x 預(yù)測(cè)其標(biāo)記y 。這罩再，x ，x 均為d 維向 量，咒】，為樣本而的標(biāo)記，和i u f 分別為和u 的大小，即它們所包含的樣本數(shù)， 一般情況下i l i - j 的參數(shù)是 口m ，o f h i l l ，o f l l m , o f h u l m 以及 觸i 拍強(qiáng)，砌l ，批，z l i l 搦，膨l ，帆) 。其中皿表示第f 個(gè)高斯包含 的高斯數(shù)，即為珂；口。，表示第f 個(gè)高斯的條件下，第個(gè)子高斯的條件先驗(yàn)概率， h ： 并且滿(mǎn)足吁l f = 1 ，f l ，2 ，m ) 。t u 和l 分別表示第f 個(gè)高斯的第個(gè)子高斯 第二章半監(jiān)督學(xué)習(xí)理論 的均值向量和方差矩陣。從而，雙重高斯混合模型參數(shù)定義為 0 = ( a l ，a m ) ，( a l l l ，。i l 。q ，眥) ， ( 朋l f l i r t i ，p m i ，j t i m h u ，l i z l n , ，e m ! ，帆) ) 假設(shè)學(xué)習(xí)的樣本集是由部分已標(biāo)記的和大部分未標(biāo)記的樣本組成，即 s ：s l + s 。， s = ( 五，y 1 ) ，( x l ，y l ) ，也+ 1 ，也+ c ，) 對(duì)應(yīng)于未標(biāo)記的樣本五+ l ，x l + u 的標(biāo)記為耽+ l ，y + ，。整個(gè)訓(xùn)練樣本集s 共有 m 個(gè)類(lèi)，咒是其相應(yīng)的類(lèi)標(biāo)，所以y e l ，c 2 ，c m ) ，每一個(gè)五可以表示為一個(gè) 在d 維空間內(nèi)的由個(gè)特征向量集組成的有k 個(gè)成分的高斯混合模型 五= ，x ，r 口 每個(gè)j s 中的( x i ，y i ) ，認(rèn)為它們都是相互獨(dú)立且同分布的。對(duì)于每個(gè)未標(biāo)記的樣本 五，定義表示類(lèi)別數(shù)目的m 個(gè)隱含變量乃，j = l ，2 ，m ， 乃= 佗巍e 陋9 ， 乃2 1o 。珈贏e 【2 拶j 利用已標(biāo)記的樣本，計(jì)算出初始的迭代參數(shù)礦。然后再按照如下的步驟迭代計(jì)算： e - s t e p ls e t 三t + 1 ) = 研zis ；o q i m s t e p ls e t # + n = a r gm a x pp ( s ，z + 1 l 口) 在e - s t e p 中，根據(jù)最大后驗(yàn)概率，給每個(gè)未分類(lèi)的樣本一個(gè)類(lèi)別標(biāo)簽?？梢?用式( 2 - 1 0 ) 來(lái)計(jì)算求得z ： e z g ii s ；秒】= 尸( 片= c ji s ；p ) = p ( c 7l 五；口) ：= p ( x g ic j ) p ( c j ) ( 2 - 1 0 ) ：= 一 p ( x f ) 墨( 薈p ( i 舷，弦) ) 】幸p ( e j ) 知縣n ( 薈k p ( 毛i 舷，肚) ) 】宰p ( 勺) 】 其中k 是第- ，類(lèi)中混合成分的數(shù)目，舷是混合權(quán)重。p ( xl z y l ，弦) 是多元高斯混 合分布的概率密度函數(shù)。在m s t e p 中，根據(jù)新分配的類(lèi)標(biāo)和原有的類(lèi)標(biāo)，按照最 大似然，重新計(jì)算參數(shù)g 。 高斯混合模型的參數(shù)夠= a 肚，縱，弦) 是由e m 算法來(lái)估計(jì)的，對(duì)任何一個(gè)未 標(biāo)記的x ，通過(guò)計(jì)算最大后驗(yàn)概率來(lái)確定其所屬類(lèi)別。由此，我們可以計(jì)算出后 1 4 半監(jiān)督降維和分類(lèi)算法研究 驗(yàn)概率p ( 勺ix ) ，使得： 2 3 2 增量半監(jiān)督學(xué)習(xí)算法 ，= a r g m a x p ( c j ix ) j ( 2 1 1 ) 在許多時(shí)候，訓(xùn)練樣本不能次獲得。當(dāng)新的訓(xùn)練樣本到來(lái)時(shí)，若對(duì)所有訓(xùn) 練樣本進(jìn)行重新學(xué)習(xí)，計(jì)算開(kāi)銷(xiāo)將會(huì)很大，同時(shí)，為了保存原訓(xùn)練樣本也需要相 當(dāng)?shù)拇鎯?chǔ)空間。神經(jīng)網(wǎng)絡(luò)中的增量學(xué)習(xí)便能解決此類(lèi)問(wèn)題，它利用已有訓(xùn)練樣本 完成學(xué)習(xí)后能夠通過(guò)不斷學(xué)習(xí)新的樣本來(lái)提高分類(lèi)能力，適應(yīng)“只知部分不知全 局 的情況和動(dòng)態(tài)的環(huán)境。通常，增量學(xué)習(xí)算法需要滿(mǎn)足兩點(diǎn)：( 1 ) 當(dāng)分類(lèi)器遇到 新的樣本時(shí)，能夠?qū)W習(xí)其新的信息；( 2 ) 分類(lèi)器學(xué)習(xí)新的信息時(shí)，不會(huì)或盡可能不 忘記己經(jīng)學(xué)過(guò)的知識(shí)。 圈2 1 增量學(xué)習(xí)的實(shí)現(xiàn)過(guò)程 半監(jiān)督學(xué)習(xí)中的增量學(xué)習(xí)算法是基于以下事實(shí)的：一般情況下，提供的監(jiān)督 信息越充分，即標(biāo)記的樣本越多，對(duì)未標(biāo)記樣本的預(yù)測(cè)就越準(zhǔn)確，這一點(diǎn)在實(shí)際 問(wèn)題的應(yīng)用中也得到了驗(yàn)證【3 8 】。如圖2 1 所示，它是以迭代方式來(lái)實(shí)現(xiàn)的：在每次 迭代時(shí)選擇一些預(yù)測(cè)信任度較高的樣本加入到標(biāo)記樣本集，從而為下一次的迭代 做準(zhǔn)備，如此迭代直到滿(mǎn)足某一終止條件。所以，如何選擇一個(gè)可分性好的分類(lèi) 器及如何構(gòu)造一個(gè)合適的計(jì)算預(yù)測(cè)信任度的準(zhǔn)則是非常重要的。 常見(jiàn)的增量學(xué)習(xí)算法包括自訓(xùn)練算法和協(xié)同訓(xùn)練算法。 自訓(xùn)練算法的主要思想是：首先使用標(biāo)記樣本訓(xùn)練一個(gè)分類(lèi)器，其次用它來(lái) 分類(lèi)未標(biāo)記樣本，然后選出信任度較高的未標(biāo)記樣本及其對(duì)應(yīng)的預(yù)測(cè)類(lèi)標(biāo)加入訓(xùn) 練集進(jìn)行重新訓(xùn)練，重復(fù)此過(guò)程直到滿(mǎn)足某一終止條件。它可以被應(yīng)用于一些自 第二章半監(jiān)督學(xué)習(xí)理論 然語(yǔ)言處理任務(wù)，詞義消歧，主觀名詞識(shí)別，圖像中的目標(biāo)檢測(cè)等。 協(xié)同訓(xùn)練算法的基本思想是：首先分另u i ) l i 練標(biāo)記樣本集的兩個(gè)子特征集合得 到兩個(gè)不同的分類(lèi)器，再用每個(gè)分類(lèi)器標(biāo)記未標(biāo)記樣本，然后分別用由其中一個(gè) 分類(lèi)器輸出的預(yù)測(cè)信任度較高的樣本來(lái)“教導(dǎo) 另一個(gè)分類(lèi)器。每個(gè)分類(lèi)器由另 一個(gè)分類(lèi)器提供的部分訓(xùn)練樣本重新訓(xùn)練，如此重復(fù)這個(gè)過(guò)程。協(xié)同訓(xùn)練算法基 于很強(qiáng)的假設(shè)：( 1 ) 樣本特征可以分成兩個(gè)集合；( 2 ) 每個(gè)特征子集合都能足夠用來(lái) 訓(xùn)練個(gè)好的分類(lèi)器；( 3 ) 當(dāng)給定類(lèi)標(biāo)的條件下兩個(gè)子集合是相互條件獨(dú)立的。 2 3 3 基于圖的半監(jiān)督學(xué)習(xí)算法 基于圖的半監(jiān)督學(xué)習(xí)算法把問(wèn)題定義成一個(gè)圖，其中頂點(diǎn)表示樣本，邊( 可能 帶權(quán)值) 則表示樣本的相似性。圖方法是無(wú)參數(shù)的判別方法，大部分的基于圖的方 法是求解一個(gè)關(guān)于圖的函數(shù)，該函數(shù)必須同時(shí)滿(mǎn)足兩個(gè)條件：( 1 ) 在標(biāo)記樣本點(diǎn)上 必須近似等于給定的類(lèi)標(biāo)；( 2 ) 在整個(gè)圖上該函數(shù)是光滑的。然后，定義所需優(yōu)化 的目標(biāo)函數(shù)并使用決策函數(shù)在圖上的光滑性作為正則化項(xiàng)來(lái)求取最優(yōu)模型參數(shù)。 文獻(xiàn) 3 9 提出把半監(jiān)督學(xué)習(xí)問(wèn)題等價(jià)為圖最小分割問(wèn)題，而最小分割僅給出了硬分 類(lèi)，并沒(méi)有計(jì)算邊緣概率。針對(duì)這個(gè)問(wèn)題，文獻(xiàn) 4 0 1 中試著計(jì)算離散馬爾可夫隨機(jī) 場(chǎng)的邊緣概率，而高斯隨機(jī)場(chǎng)和調(diào)和函數(shù)【1 2 】實(shí)質(zhì)上是將離散馬爾可夫隨機(jī)場(chǎng)連續(xù) 化。基于圖的半監(jiān)督學(xué)習(xí)方法可等價(jià)為優(yōu)化一個(gè)帶調(diào)整項(xiàng)的損失函數(shù)。所以很多 這類(lèi)方法的差別實(shí)質(zhì)上是損失函數(shù)或調(diào)整函數(shù)的不同，于是出現(xiàn)了局部和全局一 致性【2 9 1 ，t i k h o n o v 正規(guī)算法和流形正規(guī)算法【4 2 】。w a n g 等人【3 8 】提出了一種有效 的線(xiàn)性鄰域傳播l n p 算法，并用它來(lái)解決人臉識(shí)別、物體識(shí)別和圖像分割等問(wèn)題， 文章將在第四章對(duì)此算法進(jìn)行詳細(xì)的介紹。下面介紹一種基于圖從局部和全局進(jìn) 行的半監(jiān)督學(xué)習(xí)算法1 2 9 。 設(shè)x = x l ，x 2 ，x t ，x + l , - - , x m ) cr d 是m 個(gè)樣本的集合，每個(gè)樣本的維數(shù)是d ， l = 厶，r 2 ，丘) 為樣本點(diǎn)的c 種類(lèi)別。記( 一，y 1 ) ，( x t ，y i ) 為給定的z 個(gè)已標(biāo)記樣 本，y i l 為x i 的標(biāo)記，( x t + l ，x t + 。) 為“個(gè)未標(biāo)記樣本，其中m = l + u ，一般情況 下，u 。 設(shè)f 為非負(fù)n x c 矩陣，數(shù)據(jù)集f - - f j ，露。】f 是每個(gè)樣本點(diǎn)x i 對(duì)應(yīng)標(biāo)記的 集合。定義一個(gè)n x c 矩陣y 萬(wàn)，若x i 為已標(biāo)記點(diǎn)且其標(biāo)記為y i = 歹，那么r , j = 1 ， 否則= 0 ；若x i 為未標(biāo)記點(diǎn)，則r , j = 0 ( 1 _ ，c ) ?？梢钥闯鰕 和初始標(biāo)記有關(guān)， 下面是算法的步驟： ，2 ( 1 ) 計(jì)算權(quán)矩陣形，若f 歹，= e x p ( 一i i x , 一勺2 仃) ， nw i = o 。 1 6 半監(jiān)督降維和分類(lèi)算法研究 ( 2 ) 構(gòu)造矩陣s ：d 一矽2 w d 一牝，其中d 是對(duì)角矩陣，對(duì)角線(xiàn)元素( f ，f ) 為w 的第f ( 3 ) 迭代，o + 1 ) = 口s f ( f ) + ( 1 一口) y 直至收斂，這里口為( 0 ，1 ) 之間的一個(gè)參數(shù)。 ( 4 ) 設(shè)，+ 為數(shù)列 ，( f ) 的收斂點(diǎn)，則每個(gè)樣本點(diǎn)而標(biāo)記為乃= a r g m a x j g cf i 。 可以證明此數(shù)列收斂且收斂到，= ( 1 一a ) f f a s ) - 1 y 。 對(duì)上面的迭代算法進(jìn)行推導(dǎo)可形成一個(gè)規(guī)則化框架。與f 有關(guān)的損失函數(shù)定 義為： 舭，= 圭c 砉叫擊巧一赤乃睜剛2 ，億塒 這里 0 為規(guī)則化因子，則分類(lèi)函數(shù)為 f a r g m f i f nq (f)(2-t3) 損失函數(shù)中右側(cè)第一項(xiàng)為光滑約束，這意味著一個(gè)好的分類(lèi)函數(shù)在鄰點(diǎn)間改變不 能太大。第二項(xiàng)為適應(yīng)約束，它意味著一個(gè)好的分類(lèi)函數(shù)與初始標(biāo)記設(shè)置相比改 變太大，它不僅包含標(biāo)記樣本而且包含未標(biāo)記樣本。參數(shù)用來(lái)均衡這兩個(gè)約束。 對(duì)q ( f ) 關(guān)于f 求導(dǎo)，得到 等f(wàn)i f = f - ，+ 一s f + ( ，一y ) = 。 ( 2 - 1 4 ) 可以轉(zhuǎn)化為 f 一擊曠一戔1 y - o ( 2 1 5 ) 1 + + 設(shè)口= _ i _ ，則( j a s ) f = ( 1 一a ) y 。由于j a s 可逆，所以得到： 1 + 口 f 。：( 1 一口) ( j a s ) 一y ( 2 1