智能系統(tǒng)設(shè)計(jì)與應(yīng)用 Case VIHow to Measure the Difference

1、智能系統(tǒng)設(shè)計(jì)與應(yīng)用 (2022 春季學(xué)期) 主講教師：詹德川Case VI:How to Measure the Differencek 近鄰學(xué)習(xí)器k 近鄰 (k-Nearest Neighbor, kNN)懶惰學(xué)習(xí) (lazy learning) 的代表which class?k = 5k = 7基本思路：近朱者赤，近墨者黑關(guān)鍵： k 值選??；距離計(jì)算(投票法；平均法)Information RetrievalRanking basedSimilarity MeasureRecommendation SystemsSimilarity betweenConceptsUsersItemsHyb

2、rids距離度量的重要性人類很早就意識(shí)到距離的重要性，并且在文明發(fā)展之初就以統(tǒng)一度量衡作為進(jìn)步的標(biāo)識(shí)在信息檢索中如何比較提交的查詢和檢索結(jié)果之間是否相似？使用距離來(lái)表示樣本之間的不相似度使用最近鄰分類器如何判別一個(gè)樣本屬于哪個(gè)類別？近朱者，赤；近墨者，黑Kernel Machine核的生成也和距離度量有著密切的關(guān)系距離度量的種類Euclidean DistanceBlock DistanceGeodesic Distance研究者對(duì)距離度量的研究為特定應(yīng)用設(shè)計(jì)距離度量距離度量學(xué)習(xí)Isomap背景高維數(shù)據(jù)具有更加自然的低維結(jié)構(gòu)使用低維結(jié)構(gòu)上面的直線距離更加能夠反映樣本之間不相似的程度為特定應(yīng)用設(shè)

3、計(jì)距離度量Isomap為特定應(yīng)用設(shè)計(jì)距離度量要求的是兩點(diǎn)之間的測(cè)地線距離無(wú)法獲得測(cè)地線！怎么辦！近似獲得測(cè)地線距離：只有相近的點(diǎn)之間才能互相連接相隔較遠(yuǎn)的點(diǎn)之間的距離設(shè)置成無(wú)窮大使用最短路徑算法找任意兩點(diǎn)之間的最短路徑Isomap的缺陷及對(duì)其的改進(jìn)Isomap能夠度量樣本之間在低維本真空間上的距離卻容易受到噪音的影響，并且不利于分類改進(jìn)方法:引入類別信息，對(duì)距離度量進(jìn)行 改進(jìn) Supervised-Isomap Geng, Zhan and Zhou 05.為特定應(yīng)用設(shè)計(jì)距離度量研究者對(duì)距離度量的研究為特定應(yīng)用設(shè)計(jì)距離度量距離度量學(xué)習(xí)顧名思義，即利用學(xué)習(xí)的方法獲得更好的度量距離的方式大多數(shù)研究

4、者針對(duì)馬氏距離的度量矩陣A進(jìn)行學(xué)習(xí)對(duì)馬氏距離的進(jìn)一步解釋為什么要馬氏距離 ？我們回顧一下“什么是距離？”再思考一下“距離度量 ” 度量的是什么？Its a long distance to walk.旅行的開(kāi)銷！歐氏距離的缺陷但是：有緣千里來(lái)相會(huì)（歐氏距離大但開(kāi)銷少）無(wú)緣對(duì)面手難牽（優(yōu)勢(shì)距離小但開(kāi)銷大）馬氏距離應(yīng)運(yùn)而生為特定應(yīng)用設(shè)計(jì)距離度量 各向同性ABCABC咫尺天涯天涯咫尺利用邊信息的距離度量學(xué)習(xí)方法基本思想: 一個(gè)好的距離度量方法，應(yīng)該能夠使得同類之間的距離小于1，異類之間的距離大于1DML實(shí)現(xiàn)方法距離度量學(xué)習(xí)最小化同類之間的距離保持異類樣本之間的距離大于某個(gè)閾值限制學(xué)習(xí)到的距離度量矩陣

5、是半正定的；保證樣本之間的距離為正(或者0)，也即：dij=0是否馬氏距離就一定符合人們的認(rèn)知？在某些應(yīng)用中，距離的定義偏重于一些特定的屬性，并且對(duì)于不同的樣本，這些屬性是各不相同的距離的定義應(yīng)該是樣本自適應(yīng)的例如：當(dāng)我們將描述天空的圖片和其他圖片進(jìn)行比較的時(shí)候關(guān)注的是圖片的顏色（藍(lán)色）、紋理（有著特殊的光線）等當(dāng)我們將菲爾普斯II和其他游泳運(yùn)動(dòng)員比較的時(shí)候關(guān)注的是他腳的形狀，游泳的速度距離度量學(xué)習(xí)困境之一是否馬氏距離就一定符合人們的認(rèn)知？當(dāng)用戶提交“查詢1”時(shí)，圖像2與圖像1應(yīng)該比與圖像3更接近，因?yàn)榍皟烧叨及嗣枋觥吧帧边@個(gè)查詢概念的特征；而在用戶提交“查詢2”時(shí)，圖像2與圖像3應(yīng)該比

6、與圖像1更接近，因?yàn)閳D像2和圖像3都包含了描述“豹子”這個(gè)概念的圖像特征。距離度量學(xué)習(xí)困境之一距離計(jì)算方法和特定的樣本個(gè)體相關(guān)樣本自適應(yīng)方面已有的工作問(wèn)題：不同樣本有著各自不同的視角、語(yǔ)義著重或者說(shuō)，將樣本表示在高維空間中，樣本的距離度量和其本身的局部特性相關(guān)解決方案：對(duì)每個(gè)樣本賦以不同的距離度量QSim Zhou and Dai, ICDM06 Athitsos et al., TDS07Local distance functions Frome et al., NIPS06, ICCV07樣本自適應(yīng)距離度量學(xué)習(xí)以往樣本自適應(yīng)方法的缺陷Qsim：用于基于內(nèi)容的圖像檢索，對(duì)象之間的距離會(huì)受到

7、提交的檢索的影響主要問(wèn)題：該方法完全基于啟發(fā)式想法 啟發(fā)式想法 拍腦袋想辦法：人在解決問(wèn)題時(shí)所采取的一種根據(jù)經(jīng)驗(yàn)規(guī)則進(jìn)行發(fā)現(xiàn)的方法利用過(guò)去的經(jīng)驗(yàn),選擇已經(jīng)行之有效的方法，而不是系統(tǒng)地、以確定的步驟去尋求答案Local Distance Functions：Frome et al. NIPS06Frome et al. ICCV07樣本自適應(yīng)距離度量學(xué)習(xí)是否能夠同時(shí)為標(biāo)記樣本和未標(biāo)記樣本學(xué)習(xí)得到樣本自適應(yīng)距離度量呢？答案是肯定的，我們可以嘗試使用類似于標(biāo)記傳播的思想來(lái)進(jìn)行距離度量傳播！樣本自適應(yīng)距離度量學(xué)習(xí)什么是標(biāo)記傳播？一種基于圖的半監(jiān)督學(xué)習(xí)算法邊的權(quán)重往往和點(diǎn)之間的歐氏距離相關(guān)樣本自適應(yīng)距離

8、度量學(xué)習(xí)從標(biāo)記樣本中生成樣本自適應(yīng)距離度量，并且通過(guò)鄰域關(guān)系（圖）將這種樣本自適應(yīng)度量傳播出去標(biāo)記樣本上的樣本自適應(yīng)距離度量生成方式： 生成的度量應(yīng)該使得同類樣本之 間的距離小，異類樣本之間的距 離大未標(biāo)記樣本的自適應(yīng)距離度量應(yīng)該遵從相近相似的原則（Metric Propagation）從近鄰樣本處獲得樣本自適應(yīng)距離度量學(xué)習(xí)如何生成和傳遞樣本自適應(yīng)距離？進(jìn)行度量（標(biāo)記）傳播有兩種選擇：1. 采用隨機(jī)游走的策略進(jìn)行迭代求解；2. 將度量（標(biāo)記）傳播形式化成一個(gè)優(yōu)化問(wèn)題，這里我們選擇的是后者學(xué)習(xí)的度量在標(biāo)記樣本上犯下的錯(cuò)誤并不需要考慮所有的樣本，僅僅只要考慮特定樣本鄰域內(nèi)的關(guān)系即可該正則化項(xiàng)負(fù)責(zé)隱

9、式地進(jìn)行度量傳播可以定義為任何凸的損失函數(shù)，例如在分類中常用的hinge損失，以及在回歸中經(jīng)常使用的least square損失對(duì)于同類樣本來(lái)說(shuō)，我們僅僅考慮了鄰域內(nèi)的同類樣本；但是對(duì)于和特定樣本標(biāo)記不同的異類樣本而言，則是所有的都需要考慮受Zhu 2003的啟發(fā), 該正則化項(xiàng)可以定義為：樣本自適應(yīng)距離度量學(xué)習(xí)形式化模型可以在此使用其他不同的監(jiān)督信息，例如triplets informationL is set to identity matrixFSM Frome et al. NIPS06 is aspecial case of ISD雖然在我們的工作中僅僅考慮到了樣本對(duì)之間的信息，但是整

10、個(gè)ISD框架可以用于更普遍的情況樣本自適應(yīng)距離度量學(xué)習(xí)形式化模型的特例和泛化我們假設(shè)G是預(yù)先給定的，但是如果沒(méi)有給定GraphWeightsInitializeIn new ISD spaceUpdated GraphWeightsFinal ISD樣本自適應(yīng)距離度量學(xué)習(xí)圖的構(gòu)建和精化通過(guò)引入裕量考慮到w的數(shù)量很多，同時(shí)求解有困難：計(jì)算量過(guò)大！凸問(wèn)題 意味著全局最小=局部最小我們可以通過(guò)alternating descent的方法進(jìn)行優(yōu)化，也即：每次固定其他的ws，優(yōu)化其中的一個(gè)w，然后再反復(fù)迭代，直到收斂樣本自適應(yīng)距離度量學(xué)習(xí)損失函數(shù)的選擇 ISD-L1Primal:Dual:樣本自適應(yīng)距離

11、度量學(xué)習(xí)求解空間的選擇在加速算法方面，我們已經(jīng)做出的努力是： 使用alternating descend方法進(jìn)行優(yōu)化 對(duì)同類之間產(chǎn)生的約束的數(shù)量進(jìn)行了消減但是異類之間產(chǎn)生的約束的數(shù)量仍然可能十分巨大，從而導(dǎo)致算法異常耗時(shí)從nu-SVM中獲得靈感，我們是否可以利用類似的方法得到一種更有效率的方法呢？樣本自適應(yīng)距離度量學(xué)習(xí)加速方法答案是肯定的dropDual:注意：這里存在一個(gè)等式約束為了簡(jiǎn)化問(wèn)題，我們可以首先把這個(gè)約束條件給去掉，然后在求解出w之后再用下式讓w滿足最終的要求：因?yàn)榈仁郊s束的存在，這個(gè)Dual問(wèn)題可以快速地使用SMO (Sequential Minimal Optimization)求解樣本自適應(yīng)距離度量學(xué)習(xí)加速方法 ISD-L2距離度量學(xué)習(xí)困境之二如果標(biāo)記樣本特別少，怎么辦？最小化同類之間的距離保持異類樣本之間的距離大于某個(gè)閾值當(dāng)標(biāo)記樣本極少的時(shí)候，無(wú)法得到這些約束但是，如果你在web上面搜索的時(shí)候會(huì)提交多個(gè)查詢樣本么？（將查詢