幾乎所有的機器學(xué)習(xí)算法都歸結(jié)為求解最優(yōu)化問題。有監(jiān)督學(xué)習(xí)算法在訓(xùn)練時通過優(yōu)化一個目標(biāo)函數(shù)而得到模型,然后用模型進行預(yù)測。無監(jiān)督學(xué)習(xí)算法通常通過優(yōu)化一個目標(biāo)函數(shù)完成數(shù)據(jù)降維或聚類。強化學(xué)習(xí)算法在訓(xùn)練時通過最大化獎勵值得到策略函數(shù),然后用策略函數(shù)確定每種狀態(tài)下要執(zhí)行的動作。多任務(wù)學(xué)習(xí)、半監(jiān)督學(xué)習(xí)的核心步驟之一也是構(gòu)造目標(biāo)函數(shù)。一旦目標(biāo)函數(shù)確定,剩下的是求解最優(yōu)化問題,這在數(shù)學(xué)上通常有成熟的解決方案。因此目標(biāo)函數(shù)的構(gòu)造是機器學(xué)習(xí)中的中心任務(wù)。
本文介紹機器學(xué)習(xí)中若干典型的目標(biāo)函數(shù)構(gòu)造方法,它們是對問題進行建模的關(guān)鍵環(huán)節(jié)。針對實際應(yīng)用問題,在構(gòu)造目標(biāo)函數(shù)時可以借鑒前人的經(jīng)驗和技巧。接下來將分有監(jiān)督學(xué)習(xí)(進一步細分為分類問題,回歸問題,概率模型,混合問題),無監(jiān)督學(xué)習(xí)(進一步細分為數(shù)據(jù)降維問題,聚類問題),半監(jiān)督學(xué)習(xí),距離度量學(xué)習(xí),以及強化學(xué)習(xí)進行介紹。
對于最優(yōu)化方法與目標(biāo)函數(shù)數(shù)學(xué)原理的詳細講解可以閱讀人民郵電出版社本月或者下個月將出版的《機器學(xué)習(xí)的數(shù)學(xué)》,雷明著。全書由一元函數(shù)微積分,線性代數(shù)與矩陣論,多元函數(shù)微積分,最優(yōu)化方法,概率論,信息論,隨機過程,圖論8章構(gòu)成。精準(zhǔn)地覆蓋了機器學(xué)習(xí)的數(shù)學(xué)知識,講解清晰透徹。
對于各類機器學(xué)習(xí)算法原理的詳細講解,可以閱讀清華大學(xué)出版社《機器學(xué)習(xí)-原理,算法與應(yīng)用》,雷明著。全書系統(tǒng)得講述了有監(jiān)督學(xué)習(xí),無監(jiān)督學(xué)習(xí),半監(jiān)督學(xué)習(xí),強化學(xué)習(xí)的算法的原理與典型應(yīng)用。
有監(jiān)督學(xué)習(xí)
有監(jiān)督學(xué)習(xí)算法有訓(xùn)練過程,算法用訓(xùn)練集進行學(xué)習(xí),然后用學(xué)習(xí)得到的模型進行預(yù)測。典型的應(yīng)用,如圖像識別、語音識別等都屬于有監(jiān)督學(xué)習(xí)問題。有監(jiān)督學(xué)習(xí)的樣本由輸入值與標(biāo)簽值組成
其中x為樣本的特征向量,是機器學(xué)習(xí)模型的輸入值;y為標(biāo)簽值,是模型的輸出值。標(biāo)簽值可以是整數(shù)也可以是實數(shù),還可以是向量。訓(xùn)練時的目標(biāo)是給定訓(xùn)練樣本集
,根據(jù)它確定一個函數(shù)
實現(xiàn)從輸入值x到輸出值的y映射。確定此函數(shù)的依據(jù)是它能夠很好地預(yù)測這批訓(xùn)練樣本,與盡可能的接近。這通過優(yōu)化某一目標(biāo)函數(shù)實現(xiàn)。大多數(shù)算法事先確定函數(shù)的形式,訓(xùn)練時確定函數(shù)的參數(shù)。
如果樣本標(biāo)簽是整數(shù),則稱為分類問題。此時的目標(biāo)是確定樣本的類別,以整數(shù)編號。預(yù)測函數(shù)是向量到整數(shù)的映射。分類問題的樣本標(biāo)簽通常從0或1開始,以整數(shù)編號。
如果標(biāo)簽值是連續(xù)實數(shù)則稱為回歸問題。此時預(yù)測函數(shù)是向量到實數(shù)的映射。某些實際應(yīng)用問題可能既包含分類問題,又包含回歸問題。計算機視覺中的目標(biāo)檢測問題是典型代表。算法要找出圖像中所有給定類型的目標(biāo),判斷它們的類別,確定其位置與大小。檢測問題包含分類和定位兩部分,分類用于判定某一圖像區(qū)域的目標(biāo)類型;定位則確定物體的位置與大小,是回歸問題。
分類問題
下面介紹分類問題的典型目標(biāo)函數(shù)。感知器算法的是最簡單的線性分類器訓(xùn)練算法,它的目標(biāo)是讓所有樣本盡可能分類正確。對于二分類問題,線性分類器的判別函數(shù)為
樣本的標(biāo)簽值為+1或-1,分別對應(yīng)正樣本和負樣本。如果函數(shù)預(yù)測出來的值和樣本的真實標(biāo)簽值不同號,預(yù)測錯誤;如果同號,預(yù)測正確。感知器算法的目標(biāo)函數(shù)為
此損失函數(shù)的意義為對于每個訓(xùn)練樣本,如果預(yù)測正確即與標(biāo)簽值同號,則會有一個負的損失,否則有一個正的損失。這里的目標(biāo)是將損失最小化。
與感知器損失類似的是合頁損失函數(shù)。對于二分類問題,定義為
這是一種截斷函數(shù)。其意義為當(dāng)
即當(dāng)模型的預(yù)測值與樣本標(biāo)簽值同號且預(yù)測值的絕對值非常大
樣本的損失是0。否則樣本的損失是。這種函數(shù)迫使模型的預(yù)測值有大的間隔,即距離分類界線盡可能遠。支持向量機的目標(biāo)函數(shù)可以用合頁損失函數(shù)進行解釋。
離散型AdaBoost算法采用了指數(shù)損失函數(shù),對于二分類問題,定義為
如果標(biāo)簽值與強分類器的預(yù)測值同號,且強分類器預(yù)測值的絕對值越大,損失函數(shù)的值越小,反之越大。
對于二分類和多分類問題,都可以用歐氏距離作為分類的損失函數(shù)。對于多分類問題,一般不直接用類別編號作為預(yù)測值,而是為類別進行向量化編碼,如one-hot編碼。因為類別無法比較大小,直接相減沒有意義。如果樣本屬于第i個類,則其向量化的標(biāo)簽值為
向量的第i個分量為1,其余的均為0。假設(shè)類別標(biāo)簽向量為y。歐氏距離損失函數(shù)定義為
是向量二范數(shù)的平方,衡量了兩個向量之間的差異。在人工神經(jīng)網(wǎng)絡(luò)發(fā)展的早期,這種函數(shù)被廣泛使用,但后來對于多分類問題,更多的采用交叉熵損失函數(shù)。
回歸問題
對于回歸問題,通常采用歐氏距離作為損失函數(shù)。除此之外還可以使用絕對值損失,以及Huber損失。歐氏距離損失定義為
它迫使所有訓(xùn)練樣本的預(yù)測值與真實標(biāo)簽值盡可能接近。絕對值損失定義為
與歐氏距離類似,預(yù)測值與真實標(biāo)簽值越接近,損失函數(shù)的值越小。對單個樣本的Huber損失定義為
當(dāng)預(yù)測值與真實標(biāo)簽值接近即二者的差的絕對值不超過時使用歐氏距離損失,如果二者相差較大時使用絕對值損失。這種做法可以減小預(yù)測值與真實標(biāo)簽值差距較大時的損失函數(shù)值,因此Huber損失對噪聲數(shù)據(jù)有更好的健壯性。此外,Huber損失更利于梯度下降優(yōu)化。遠離目標(biāo)值時有較大的梯度,接近目標(biāo)值時梯度較小。分類問題和回歸問題目標(biāo)函數(shù)的細節(jié)可以閱讀《機器學(xué)習(xí)的數(shù)學(xué)》第4.9節(jié)“目標(biāo)函數(shù)的構(gòu)造”。
概率模型
機器學(xué)習(xí)算法有時候需要估計概率分布的參數(shù),典型的方法是最大似然估計,最大后驗概率估計,貝葉斯估計,以及核密度估計。
最大似然估計為樣本集構(gòu)造一個似然函數(shù),通過讓似然函數(shù)最大化,求解出參數(shù)。直觀解釋是,尋求參數(shù)的值使得給定的樣本集出現(xiàn)的概率(或概率密度函數(shù)值)最大。最大似然估計認為使得觀測數(shù)據(jù)出現(xiàn)概率最大的參數(shù)為最優(yōu)參數(shù),這一方法體現(xiàn)了“存在的就是合理的”這一樸素的哲學(xué)思想:既然這組樣本出現(xiàn)了,那它們出現(xiàn)的概率理應(yīng)是最大化的。
假設(shè)樣本服從的概率分布為,其中x為隨機變量,為要估計的參數(shù)。給定一組樣本,它們都服從這種分布且相互獨立。它們的聯(lián)合概率為
這個聯(lián)合概率也稱為似然函數(shù)。似然函數(shù)是優(yōu)化變量的函數(shù),目標(biāo)是讓該函數(shù)的值最大化,即求解如下最優(yōu)化問題
乘積求導(dǎo)不易處理且數(shù)值計算時不穩(wěn)定,將似然函數(shù)取對數(shù),得到對數(shù)似然函數(shù)
最后要求解的問題為
貝葉斯分類器,概率圖模型(包括貝葉斯網(wǎng)絡(luò),隱馬爾可夫模型,條件隨機場),高斯混合模型與EM算法,logistic回歸,softmax回歸,受限玻爾茲曼機,變分自動編碼器等機器學(xué)習(xí)算法均采用了最大似然估計。
最大似然估計將參數(shù)看作固定值(普通的變量),但其值未知。最大后驗概率估計則將參數(shù)看作隨機變量,假設(shè)它服從某種概率分布,通過最大化后驗概率確定其值。其核心思想是使得在樣本出現(xiàn)的條件下參數(shù)的后驗概率最大化。求解時需要假設(shè)參數(shù)服從某種分布(稱為先驗分布)。
假設(shè)參數(shù)服從概率分布。根據(jù)貝葉斯公式,參數(shù)對樣本集的后驗概率(即已知樣本集x的條件下參數(shù)的條件概率)為
如果確定了概率密度函數(shù)的形式,可以根據(jù)樣本的值x進行計算,與最大似然估計相同,是未知量。因此最大化該后驗概率等價于
上式第二步忽略了分母的值,因為它和參數(shù)無關(guān)且為正。對最大似然估計與貝葉斯估計等參數(shù)估計算法的詳細了解可以閱讀《機器學(xué)習(xí)的數(shù)學(xué)》第5.7節(jié)“參數(shù)估計”。
有些時候,機器學(xué)習(xí)模型的輸出是一個概率分布,此時我們要擬合一個概率分布,讓它和目標(biāo)概率分布盡可能接近。這就需要用到衡量兩個概率分布差距的指標(biāo),典型的是交叉熵,KL散度,JS散度等。
交叉熵定義在兩個概率分布之上,衡量了二者的差異程度。對于離散型隨機變量X,p(x)和q(x)是兩個概率分布的概率質(zhì)量函數(shù),交叉熵定義為
其值越大,兩個概率分布的差異越大;其值越小,則兩個概率分布的差異越小。交叉熵常用于構(gòu)造機器學(xué)習(xí)的目標(biāo)函數(shù),如logistic回歸與softmax回歸。此時可從最大似然估計導(dǎo)出交叉熵損失函數(shù)的形式。
對于softmax回歸,對數(shù)似然函數(shù)為
讓對數(shù)似然函數(shù)取極大值等價于讓下面的損失函數(shù)取極小值
這就是交叉熵損失函數(shù),反映了預(yù)測值與真實標(biāo)簽值的差距,二者均為多項分布。
KL散度也稱為相對熵,同樣用于衡量兩個概率分布之間的差距。其值越大則說明兩個概率分布的差距越大;當(dāng)兩個分布完全相等時KL散度值為0。
對于兩個離散型隨機概率分布p和q,它們之間的KL散度定義為
其中p(x)和q(x)為這兩個概率分布的概率質(zhì)量函數(shù)。對于兩個連續(xù)型概率分布p和q,它們之間的KL散度定義為
其中p(x)和q(x)為這兩個概率分布的概率密度函數(shù)。變分推斷,變分自動編碼器的目標(biāo)函數(shù)均使用了KL散度,具體可以閱讀《機器學(xué)習(xí)的數(shù)學(xué)》第6.3.5節(jié)“應(yīng)用-變分推斷”。
JS散度衡量兩個概率分布之間的差異。對于兩個概率分布和,它們的JS散度定義為
其中概率分布m為p和q的平均值,概率質(zhì)量函數(shù)或概率密度函數(shù)的均值。生成對抗網(wǎng)絡(luò)的訓(xùn)練目標(biāo)可以用JS散度進行解釋,最小化生成器生成的樣本的概率分布與真實樣本概率分布之間的JS散度。具體可以閱讀《機器學(xué)習(xí)的數(shù)學(xué)》第6.4.3節(jié)“應(yīng)用-生成對抗網(wǎng)絡(luò)”。
混合任務(wù)
下面介紹既有分類問題又有回歸問題的情況。對于目標(biāo)檢測問題,算法要找出圖像中各種大小、位置、種類的目標(biāo),即要同時判斷出每個目標(biāo)的類型以及目標(biāo)所在的位置、大小。
目標(biāo)的位置和大小通常用矩形框來定義目標(biāo),稱為外接矩形(bounding box),用參數(shù)表示為(x,y,w,h),其中(x,y)是矩形左上角的坐標(biāo),w為寬度,h為高度。判定物體的類別是一個分類問題,確定物體的位置與大小是一個回歸問題。為了同時完成這些目標(biāo),設(shè)計出了多任務(wù)損失函數(shù)。此函數(shù)由兩部分構(gòu)成,第一部分為分類損失,即要正確的判定每個目標(biāo)的類別;第二部分為定位損失,即要正確的確定目標(biāo)所處的位置。以Fast R-CNN為例,它的損失函數(shù)為
前半部分為分類損失,可以采用交叉熵損失函數(shù)。后半部分為定位損失,確定矩形框的大小和位置,采用了smooth L1 損失,定義為
這是一種Huber損失,其優(yōu)點在前面已經(jīng)介紹。之后的Faster R-CNN,YOLO,SSD等目標(biāo)檢測算法都采用了多任務(wù)損失函數(shù)的思路。
無監(jiān)督學(xué)習(xí)
無監(jiān)督學(xué)習(xí)對無標(biāo)簽的樣本進行分析,發(fā)現(xiàn)樣本集的結(jié)構(gòu)或者分布規(guī)律,它沒有訓(xùn)練過程。其典型代表是數(shù)據(jù)降維,以及聚類。
數(shù)據(jù)降維問題
數(shù)據(jù)降維算法將n維空間中的向量x通過函數(shù)映射到更低m維的維空間中,在這里m<
降維之后的數(shù)據(jù)要保持原始數(shù)據(jù)的某些特征。通過降維可以使得數(shù)據(jù)更容易進一步處理。如果降維到2維或3維空間,則可將數(shù)據(jù)可視化。
主成分分析是一種無監(jiān)督線性降維方法,它通過線性變換將向量投影到低維空間。對向量進行投影就是對向量左乘一個矩陣,得到結(jié)果向量
降維要確保的是在低維空間中的投影能很好的近似表達原始向量,即重構(gòu)誤差最小化。如果要將向量降到維,每個向量可以表示成
在這里都是單位向量,并且相互正交,是要尋找的低維空間中的標(biāo)準(zhǔn)正交基。重構(gòu)誤差函數(shù)為
使得該函數(shù)取最小值的為散度矩陣最大的個特征值對應(yīng)的單位長度特征向量。即求解下面的優(yōu)化問題
其中tr為矩陣的跡,I為單位矩陣,該等式約束保證投影基向量是標(biāo)準(zhǔn)正交基。矩陣W的列是要求解的基向量。
線性判別分析是一種有監(jiān)督的數(shù)據(jù)降維算法,其基本思想是通過線性投影來最小化同類樣本間的差異,最大化不同類樣本間的差異。具體做法是尋找一個向低維空間的投影矩陣W,樣本的特征向量x經(jīng)過投影之后得到新向量
同一類樣本投影后的結(jié)果向量差異盡可能小,不同類的樣本差異盡可能大。直觀來看,就是經(jīng)過這個投影之后同一類的樣本盡量聚集在一起,不同類的樣本盡可能離得遠。
最后的目標(biāo)為求解下面的最優(yōu)化問題
其中tr為矩陣的跡。分母是類內(nèi)差異,分子是類間差異。這個問題等價于優(yōu)化下面的問題
接下來介紹流形學(xué)習(xí)數(shù)據(jù)降維算法的目標(biāo)函數(shù)。
局部線性嵌入將高維數(shù)據(jù)投影到低維空間中,并保持數(shù)據(jù)點之間的局部線性關(guān)系。其核心思想是每個點都可以由與它相鄰的多個點的線性組合來近似重構(gòu),投影到低維空間之后要保持這種線性重構(gòu)關(guān)系,即有相同的重構(gòu)系數(shù)。
假設(shè)數(shù)據(jù)集由n個D維向量組成,它們分布在D維空間中的一個流形附近。每個數(shù)據(jù)點和它的鄰居位于或者接近于流形的一個局部線性片段上,即可以用鄰居點的線性組合來重構(gòu)
權(quán)重系數(shù)通過最小化下面的重構(gòu)誤差確定
假設(shè)算法將向量從D維空間的x映射為d維空間的y。每個點在d維空間中的坐標(biāo)由下面的最優(yōu)化問題確定
這里的權(quán)重和上一個優(yōu)化問題的值相同,在前面已經(jīng)得到,是已知量。這里優(yōu)化的目標(biāo)是,此優(yōu)化問題等價于求解稀疏矩陣的特征值問題。得到y(tǒng)之后,即完成了從D維空間到d維空間的非線性降維。
拉普拉斯特征映射是基于圖論的方法。它為樣本點構(gòu)造帶權(quán)重的圖,然后計算圖的拉普拉斯矩,對該矩陣進行特征值分解得到投影變換結(jié)果。這個結(jié)果對應(yīng)于將樣本點投影到低維空間,且保持樣本點在高維空間中的相對距離信息。
算法為樣本點構(gòu)造加權(quán)圖,圖的節(jié)點是每一個樣本點,邊為每個節(jié)點與它的鄰居節(jié)點之間的相似度,每個節(jié)點只和它的鄰居有連接關(guān)系。算法的目標(biāo)是投影之后保持在高維空間中的距離關(guān)系,假設(shè)投影后到低維空間后的坐標(biāo)為y,它通過最小化如下目標(biāo)函數(shù)實現(xiàn)
此函數(shù)的含義是如果樣本和的相似度很高即在高維空間中距離很近,則它們之間的邊的權(quán)重很大,因此投影到低維空間中后兩個點要離得很近,即和要很接近,否則會產(chǎn)生一大個的損失值。求解該目標(biāo)函數(shù)等價于下面的優(yōu)化問題
其中
為投影后的坐標(biāo)按列構(gòu)成的矩陣,這里加上了等式約束條件以消掉y的冗余,選用矩陣D來構(gòu)造等式約束是因為其主對角線元素即節(jié)點的加權(quán)度反映了圖的每個節(jié)點的重要性。
局部保持投影通過最好的保持一個數(shù)據(jù)集的鄰居結(jié)構(gòu)信息來構(gòu)造投影映射,其思路和拉普拉斯特征映射類似。
假設(shè)有樣本集,它們是空間中的向量。這里的目標(biāo)是尋找一個變換矩陣,將這些樣本點映射到更低維的空間,得到向量,使得能夠代表,其中
假設(shè)
,其中M是空間中的一個流形。
目標(biāo)函數(shù)與拉普拉斯特征映射相同,定義為
所有矩陣的定義與拉普拉斯特征映射相同。投影變換矩陣為
即
假設(shè)矩陣X為所有樣本按照列構(gòu)成的矩陣。這等價于求解下面的問題
等距映射使用了微分幾何中測地線的思想,它希望數(shù)據(jù)在向低維空間映射之后能夠保持流形上的測地線距離。
在這里測地線距離通過圖構(gòu)造,是圖的兩個節(jié)點之間的最短距離。算法的第一步構(gòu)造樣本集的鄰居圖,第二步計算圖中任意兩點之間的最短路徑長度,可以通過經(jīng)典的Dijkstra算法實現(xiàn)。假設(shè)最短路徑長度為,由它構(gòu)造如下矩陣:
其元素是所有節(jié)點對之間的最短路徑長度。算法的第三步根據(jù)矩陣構(gòu)造d維嵌入y,這通過求解如下最優(yōu)化問題實現(xiàn)
這個問題的解y即為降維之后的向量。這個目標(biāo)函數(shù)的意義是向量降維之后任意兩點之間的距離要盡量的接近在原始空間中這兩點之間的最短路徑長度,因此可以認為降維盡量保留了數(shù)據(jù)點之間的測地距離信息。
隨機近鄰嵌入基于如下思想:在高維空間中距離很近的點投影到低維空間中之后也要保持這種近鄰關(guān)系,在這里距離通過概率體現(xiàn)。假設(shè)在高維空間中有兩個點樣本點和,以的概率作為的鄰居,將樣本之間的歐氏距離轉(zhuǎn)化成概率值,借助于正態(tài)分布,此概率的計算公式為
在低維空間中對應(yīng)的近鄰概率記為,計算公式與上面的相同。
上面定義的是點與它的一個鄰居點的概率關(guān)系,如果考慮所有其他點,這些概率值構(gòu)成一個離散型概率分布,是所有樣本點成為的鄰居的概率。在低維空間中對應(yīng)的概率分布為,投影的目標(biāo)是這兩個概率分布盡可能接近,因此需要衡量兩個概率分布之間的相似度或距離。這里用KL散度衡量兩個概率分布之間的距離。由此得到投影的目標(biāo)為最小化如下函數(shù)
這里對所有樣本點的KL散度求和,為樣本數(shù)。SNE的改進型算法-t-SNE同樣采用了KL散度作為目標(biāo)函數(shù)。具體的原理可以閱讀《機器學(xué)習(xí)的數(shù)學(xué)》第6.3.4節(jié)“應(yīng)用-流形降維”以及《機器學(xué)習(xí)-原理,算法與應(yīng)用》第7.2節(jié)“流形學(xué)習(xí)”。
聚類問題
下面介紹聚類算法的目標(biāo)函數(shù)。聚類算法將一組樣本劃分成k個類
,確保同一類中的樣本差異盡可能小,而不同類的樣本之間盡量不同。K均值算法基于這一思想構(gòu)造損失函數(shù)
其含義是每一類樣本距離它的類中心要近,可以理解為每個類的方差。所有類的方差之和要盡可能小。
基于圖的聚類算法把樣本數(shù)據(jù)看作圖的頂點,根據(jù)數(shù)據(jù)點之間的距離構(gòu)造邊,形成帶權(quán)重的圖。通過圖的切割實現(xiàn)聚類,即將圖切分成多個子圖,這些子圖就是對應(yīng)的簇。這類算法的典型代表是譜聚類算法。譜聚類算法首先構(gòu)造樣本集的鄰接圖,得到圖的拉普拉斯矩陣,接下來對矩陣進行特征值分解,通過對特征向量進行處理構(gòu)造出簇。
算法首先根據(jù)樣本集構(gòu)造出帶權(quán)重的圖G,聚類算法的目標(biāo)是將其切割成多個子圖,每個子圖即為聚類后的一個簇。假設(shè)圖的頂點集合為V,邊的集合為E。聚類算法將頂點集合切分成k個子集,它們的并集是整個頂點集
任意兩個子集之間的交集為空
對于任意兩個子圖,其頂點集合為和,它們之間的切圖權(quán)重定義為連接兩個子圖節(jié)點的所有邊(即跨兩個子圖的邊)的權(quán)重之和
這可以看作兩個子圖之間的關(guān)聯(lián)程度,如果兩個子圖之間沒有邊連接,則該值為0。從另一個角度看,這是對圖進行切割時去掉的邊的權(quán)重之和。
對圖頂點子集,定義這種分割的代價為:
其中為的補集。該值與聚類的目標(biāo)一致,即每個子圖內(nèi)部的連接很強,而子圖之間的連接很弱,換一種語言來表述就是同一個子圖內(nèi)的樣本相似,不同子圖之間的樣本不相似。但直接通過最小化這個值實現(xiàn)聚類還有問題,它沒有考慮子圖規(guī)模對代價函數(shù)的影響,使得這個指標(biāo)最小的切分方案不一定就是最優(yōu)切割。
解決這個問題的方法是對代價函數(shù)進行歸一化。第一種方法是用圖的頂點數(shù)進行歸一化,由此得到優(yōu)化的目標(biāo)為
其中為子集的元素數(shù),稱為RatioCut。另外一種歸一化方案為
其中vol是圖中所有頂點的加權(quán)度之和
稱為NCut。這兩種情況都可以轉(zhuǎn)化成求解歸一化后的拉普拉斯矩陣的特征值問題。對譜聚類算法的詳細了解可以閱讀《機器學(xué)習(xí)-原理,算法與應(yīng)用》第18.6節(jié)“基于圖的算法”。
半監(jiān)督學(xué)習(xí)
半監(jiān)督學(xué)習(xí)的訓(xùn)練樣本中只有少量帶有標(biāo)簽值,算法要解決的核心問題是如何有效的利用無標(biāo)簽的樣本進行訓(xùn)練。
有監(jiān)督學(xué)習(xí)中一般假設(shè)樣本獨立同分布。從樣本空間中抽取l個樣本用于訓(xùn)練,他們帶有標(biāo)簽值。另外從樣本空間中抽取u個樣本,它們沒有標(biāo)簽值。半監(jiān)督學(xué)習(xí)要利用這些數(shù)據(jù)進行訓(xùn)練,得到比只用l個樣本更好的效果。下面介紹半監(jiān)督學(xué)習(xí)中的生成模型,半監(jiān)督支持向量機,基于圖的模型的目標(biāo)函數(shù)。
生成模型假設(shè)每個類的樣本服從概率分布,其中是概率密度函數(shù)的參數(shù)。如果無標(biāo)簽樣本與有標(biāo)簽樣本來自同一概率分布,則將這些無標(biāo)簽樣本加上推測出來的標(biāo)簽值之后作為訓(xùn)練樣本能夠提高模型的準(zhǔn)確率。如果這一假設(shè)不正確,用推理出來的錯誤標(biāo)簽進行模型訓(xùn)練反而會降低模型的準(zhǔn)確率。
無標(biāo)簽樣本由每個類的概率分布的混合來生成,常用的是高斯混合模型,假設(shè)每個類的數(shù)據(jù)服從正態(tài)分布。樣本數(shù)據(jù)與標(biāo)簽值的聯(lián)合概率密度函數(shù)可以由類的條件概率密度函數(shù)得到:
每個類的參數(shù)向量的值是要確定的參數(shù),利用有標(biāo)簽樣本和無標(biāo)簽樣本得到,即求解下面的最優(yōu)化問題(對數(shù)似然函數(shù))
半監(jiān)督支持向量機是標(biāo)準(zhǔn)支持向量機的半監(jiān)督學(xué)習(xí)版本,它可以用部分標(biāo)注的樣本進行訓(xùn)練,找到的分界面是樣本稀疏的地方,使用了低密度分割假設(shè)。半監(jiān)督支持向量機的目標(biāo)是對無標(biāo)簽樣本進行預(yù)測,使得分類間隔對所有樣本最大化。在這里用有標(biāo)簽樣本集進行訓(xùn)練,對無標(biāo)簽集進行測試
訓(xùn)練時求解的問題為
實現(xiàn)時首先用帶標(biāo)簽的樣本進行訓(xùn)練,然后用得到的模型對無標(biāo)簽樣本進行預(yù)測,得到這些樣本的偽標(biāo)簽值。接下來再用這無標(biāo)簽的樣本進行訓(xùn)練得到新的模型。
基于圖的算法為樣本構(gòu)造帶權(quán)重的無向圖,用圖表示有標(biāo)簽和無標(biāo)簽樣本數(shù)據(jù),圖的構(gòu)造和流形降維算法相同。圖的頂點是有標(biāo)簽和無標(biāo)簽樣本,邊的權(quán)重為樣本之間的相似度。建立圖之后可以得到它的拉普拉斯矩陣,通過優(yōu)化某一目標(biāo)函數(shù)得到模型參數(shù)。分類函數(shù)要保證對有標(biāo)簽樣本預(yù)測正確,對于圖的點的預(yù)測結(jié)果是連續(xù)的,這通過引入正則化項來實現(xiàn)。
流形正則化算法假設(shè)每個類的有標(biāo)簽樣本和無標(biāo)簽樣本分布在同一個流形M上。訓(xùn)練時要求解的問題為
其中l(wèi)為有標(biāo)簽的訓(xùn)練樣本數(shù),M為樣本所在的流形。損失函數(shù)的第一項是對有標(biāo)簽樣本的分類損失。第二項是預(yù)測函數(shù)的正則化項,用于控制預(yù)測函數(shù)的復(fù)雜度。第三項是流形正則化項,用于實現(xiàn)流形假設(shè),即有標(biāo)簽樣本與無標(biāo)簽樣本分布在同一個流形上。其中H為再生核希爾伯特空間,和是正則化項系數(shù)。
對半監(jiān)督學(xué)習(xí)的進一步了解可以閱讀《機器學(xué)習(xí)-原理,算法與應(yīng)用》的第19章“半監(jiān)督學(xué)習(xí)”。
距離度量學(xué)習(xí)
通常情況下,距離函數(shù)是人工定義的。也可以通過機器學(xué)習(xí)來學(xué)習(xí)得到一個距離函數(shù),一般是Mahalanobis距離中的矩陣S,這稱為距離度量學(xué)習(xí)。距離度量學(xué)習(xí)通過樣本集學(xué)習(xí)到一種線性或非線性變換,目前有多種實現(xiàn)。
距離度量學(xué)習(xí)可形式化的定義為根據(jù)一組樣本
確定距離函數(shù)
距離度量學(xué)習(xí)的經(jīng)典實現(xiàn)有ITML,NCA,LMNN等。下面對這些算法的原理進行介紹。
LMNN尋找一個變換矩陣,使得變換后每個樣本的個最近鄰居都和它是同一個類,而不同類型的樣本通過一個大的間隔被分開,這和線性判別分析的思想類似。
假設(shè)原始的樣本點為x,變換之后的點為y,在這里要尋找的是如下線性變換
其中L為線性變換矩陣。訓(xùn)練時優(yōu)化的損失函數(shù)由推損失函數(shù)和拉損失函數(shù)兩部分構(gòu)成。拉損失函數(shù)的作用是讓和樣本標(biāo)簽相同的樣本盡可能與它接近
推損失函數(shù)的作用是把不同類型的樣本推開
如果,則,否則。函數(shù)
定義為:
如果兩個樣本類型相同,則有因此推損失函數(shù)只對不同類型的樣本起作用。總損失函數(shù)由這兩部分的加權(quán)和構(gòu)成
ITML的優(yōu)化目標(biāo)是在保證同類樣本距離相近,不同類樣本之間距離遠的約束條件下,迫使度量矩陣所代表的正態(tài)分布接近于某一先驗概率分布。算法使用了信息論中的KL散度,因此得名。
假設(shè)有n個中的樣本點。度量矩陣為,這里的距離采用馬氏距離的平方和。如果兩個樣本點之間相似,則有如下的不等式約束
即它們之間的距離小于某一較小的閾值u。這一約束通常用于同類的樣本點之間。反之如果兩個樣本點之間不相似,則有如下不等式約束
其中l(wèi)為一個較大的閾值。這一約束通常用于不同類的樣本點之間。
矩陣通常要符合某些先驗知識。例如,如果數(shù)據(jù)服從正態(tài)分布,則該矩陣為正態(tài)分布協(xié)方差矩陣的逆矩陣;而對有些場景,歐氏距離平方作為距離函數(shù)有很好的效果,此時該矩陣為單位矩陣。因此可以對矩陣正則化,迫使其盡可能接近于某一已知的馬氏距離矩陣。
因此需要衡量與之間的接近程度。如果以度量矩陣作為協(xié)方差矩陣的逆矩陣,則此多維正態(tài)分布為
其中Z為歸一化常數(shù),μ為均值向量,為協(xié)方差矩陣。如果將馬氏距離所作用的樣本集看作服從正態(tài)分布,則可以用KL距離衡量二者的差異。根據(jù)KL散度的定義,這兩個度量矩陣所代表的正態(tài)分布之間的KL散度為
因此得到如下優(yōu)化問題
其中S為相似的樣本對的集合,D為不相似的樣本對的集合。目標(biāo)函數(shù)為兩個矩陣之間的KL散度,實現(xiàn)先驗知識。
與LMNN類似,NCA同樣與近鄰算法有關(guān)。在保證其優(yōu)化目標(biāo)是使得每個樣本的同類樣本被近鄰算法正確分類的概率最大化,以此構(gòu)造目標(biāo)函數(shù)。
首先定義每個樣本點的鄰居的概率分布,是其他樣本所有樣本是此樣本鄰居的概率。樣本是的鄰居的概率定義通過下式計算
這兩個樣本點經(jīng)過變換之后相距越遠則此概率值越小;反之則越大。樣本成為其自身的鄰居的概率定義為0,即。在對樣本點進行分類時,如果采用這些鄰接作為其標(biāo)簽值,則可以計算出樣本點被正確分類的概率。定義為樣本點i被正確的分類的概率,是它所有同類樣本成為其鄰居的概率之和
其中為i 的同類樣本集合,即
。為樣本的類別標(biāo)簽值。NCA的優(yōu)化目標(biāo)是所有樣本的之和
強化學(xué)習(xí)
強化學(xué)習(xí)類似于有監(jiān)督學(xué)習(xí),其目標(biāo)是在當(dāng)前狀態(tài)s下執(zhí)行某一動作,反復(fù)執(zhí)行這一過程,以達到某種目的。算法需要確定一個稱為策略函數(shù)的函數(shù),實現(xiàn)從狀態(tài)到動作的映射
對于某些實際問題,動作的選擇是隨機的,策略函數(shù)給出在狀態(tài)下執(zhí)行每種動作的條件概率值在每個時刻t,算法在狀態(tài)下執(zhí)行動作之后,系統(tǒng)隨機性地進入下一個狀態(tài),并給出一個獎勵值。強化學(xué)習(xí)算法在訓(xùn)練時通過隨機地執(zhí)行動作,收集反饋。系統(tǒng)對正確的動作做出獎勵(reward),對錯誤的動作進行懲罰,訓(xùn)練完成之后用得到的策略函數(shù)進行預(yù)測。這里的獎勵(也稱為回報)機制類似于有監(jiān)督學(xué)習(xí)中的損失函數(shù),用于對策略的優(yōu)劣進行評估。
強化學(xué)習(xí)的目標(biāo)是最大化累計獎勵
其中稱為折扣因子,用于體現(xiàn)未來的不確定性,使得越遠來的未來所得到的回報具有越高的不確定性;同時保證上面的級數(shù)收斂。
算法需要確保在所有狀態(tài)按照某一策略執(zhí)行,得到的累計回報均最大化。因此可以定義狀態(tài)價值函數(shù)。在狀態(tài)下反復(fù)地按照策略Π執(zhí)行,所得到的累計獎勵的數(shù)學(xué)期望稱為該狀態(tài)的價值函數(shù)
使用數(shù)學(xué)期望是因為系統(tǒng)具有隨機性,需要對所有情況的累計獎勵計算均值。類似的可以定義動作價值函數(shù),它是在當(dāng)前狀態(tài)下執(zhí)行動作,然后按照策略Π執(zhí)行,所得到的累計獎勵的數(shù)學(xué)期望
構(gòu)造出目標(biāo)函數(shù)之后,尋找最優(yōu)策略Π可以通過優(yōu)化算法實現(xiàn)。如果用神經(jīng)網(wǎng)絡(luò)表示策略,則可以將這些目標(biāo)函數(shù)作為神經(jīng)網(wǎng)絡(luò)的目標(biāo)函數(shù),使用梯度下降法完成訓(xùn)練。對強化學(xué)習(xí)的進一步了解可以閱讀《機器學(xué)習(xí)-原理,算法與應(yīng)用》的第22章“強化學(xué)習(xí)”。
參考文獻
[1]機器學(xué)習(xí)原理、算法與應(yīng)用
[2] 機器學(xué)習(xí)的數(shù)學(xué).
責(zé)任編輯:xj
原文標(biāo)題:機器學(xué)習(xí)中的目標(biāo)函數(shù)總結(jié)
文章出處:【微信公眾號:深度學(xué)習(xí)自然語言處理】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。
-
目標(biāo)函數(shù)
+關(guān)注
關(guān)注
0文章
2瀏覽量
6121 -
機器學(xué)習(xí)
+關(guān)注
關(guān)注
66文章
8406瀏覽量
132567
原文標(biāo)題:機器學(xué)習(xí)中的目標(biāo)函數(shù)總結(jié)
文章出處:【微信號:zenRRan,微信公眾號:深度學(xué)習(xí)自然語言處理】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
相關(guān)推薦
評論