最優(yōu)路徑森林算法原理及其相關(guān)反饋應(yīng)用

李宏林 朱建彬 徐夢迪

(1.泉州醫(yī)學(xué)高等?？茖W(xué)校,福建 泉州 362000;2.浙江大學(xué),浙江 杭州 310012)

0 引言

手機(jī)應(yīng)用端的普及與人工智能技術(shù)的廣泛應(yīng)用推動(dòng)了網(wǎng)絡(luò)大數(shù)據(jù)時(shí)代的迅猛發(fā)展；在電商、物流、教育等領(lǐng)域，機(jī)器分類技術(shù)被廣泛部署于信息檢索與模式識別等研究方向，相關(guān)反饋技術(shù)則進(jìn)一步改善了人機(jī)交流模式和理解機(jī)制，兩者的融合應(yīng)用有助于進(jìn)一步提升信息分類、檢索準(zhǔn)確率與用戶滿意度：通過機(jī)器分類提供首次檢索結(jié)果，運(yùn)用人機(jī)交互反饋進(jìn)一步縮小高層語義概念與低層機(jī)器特征之間的理解偏差。

相對于傳統(tǒng)分類算法，最優(yōu)路徑森林(OPF,Optimum-path forest)算法可同時(shí)在分類精度與速度上達(dá)到較高性能[1-3]，被廣泛部署于機(jī)器分類與相關(guān)反饋等工業(yè)及科研領(lǐng)域[4-6]。沈龍鳳等[4]描述了OPF算法原理并羅列其在國際領(lǐng)域的多項(xiàng)應(yīng)用，但僅限于算法流程[3]及相關(guān)應(yīng)用文獻(xiàn)的摘要翻譯。本文以圖文方式剖析OPF算法細(xì)節(jié)，展示其在服裝檢索與人臉生成領(lǐng)域的相關(guān)反饋實(shí)例應(yīng)用，為國內(nèi)同行復(fù)現(xiàn)該算法并部署在不同應(yīng)用領(lǐng)域提供有益借鑒。

1 相關(guān)研究

基于機(jī)器學(xué)習(xí)的分類技術(shù)被廣泛應(yīng)用于數(shù)據(jù)挖掘、計(jì)算機(jī)視覺、語音識別、自然語言處理等多個(gè)領(lǐng)域，代表性技術(shù)主要有線性與邏輯回歸、決策樹、貝葉斯、神經(jīng)網(wǎng)絡(luò)、遺傳算子、支持向量機(jī)[7]以及深度學(xué)習(xí)算法等。人機(jī)交互技術(shù)通過改善人與計(jì)算機(jī)的交流溝通模式進(jìn)而提升人機(jī)協(xié)同工作效率，在優(yōu)化用戶體驗(yàn)、離線數(shù)據(jù)采集與實(shí)時(shí)信息反饋等方面有廣泛應(yīng)用，主要有基于硬件的設(shè)備優(yōu)化(如虛擬現(xiàn)實(shí)與增強(qiáng)現(xiàn)實(shí))與基于軟件的操作界面與算法優(yōu)化(如可視化應(yīng)用)兩大研究方向，基于主動(dòng)學(xué)習(xí)的相關(guān)反饋技術(shù)被證明可以有效提高圖像檢索效果[8]。

OPF算法是由Papa等人提出并經(jīng)過多次更新優(yōu)化[1-3]的一種基于完全圖的半監(jiān)督分類算法，孫挺和耿國華提出的GL-OPF算法[9]進(jìn)一步提升了基于內(nèi)容的圖像檢索系統(tǒng)性能，國外多個(gè)科研與工業(yè)領(lǐng)域?qū)PF算法部署于智能分類等應(yīng)用[4]，李宏林等[5]采用基于OPF算法的相關(guān)反饋方法優(yōu)化服裝檢索結(jié)果，許彩娥等[6]運(yùn)用OPF算法改善人臉檢索結(jié)果并優(yōu)化以最優(yōu)人臉特征點(diǎn)為條件參數(shù)的生成式競爭網(wǎng)絡(luò)。相較于其他機(jī)器分類與交互反饋算法而言，OPF算法具有精度高、實(shí)時(shí)響應(yīng)快、初始標(biāo)記訓(xùn)練樣本需求不大及可迭代自優(yōu)化等優(yōu)點(diǎn)。

2 算法原理與流程剖析

OPF是由一群最優(yōu)路徑樹OPT(Optimum-path tree)組成，每棵OPT代表一個(gè)分類器，樹上每個(gè)節(jié)點(diǎn)均歸類于根節(jié)點(diǎn)所屬類別；相鄰節(jié)點(diǎn)之間的連接弧權(quán)值由兩者的距離值表征，權(quán)值越大，兩個(gè)節(jié)點(diǎn)的相似度越低；每條路徑首尾節(jié)點(diǎn)的相似度由其所包含的各連接弧中的最大權(quán)重值而非總和值表征，即通過相鄰節(jié)點(diǎn)的相似度傳遞而非累加獲得；每個(gè)待分類樣本有且僅與OPF中的某棵OPT的根節(jié)點(diǎn)基于最小代價(jià)值直接或間接連接，并被歸類到該根節(jié)點(diǎn)所屬類別；OPF算法包含了訓(xùn)練構(gòu)建與分類反饋兩個(gè)階段，并可迭代自優(yōu)化。

2.1 訓(xùn)練構(gòu)建

首先將候選數(shù)據(jù)庫視為訓(xùn)練數(shù)據(jù)集并轉(zhuǎn)化為某種形式的特征向量集，基于某種距離度量指標(biāo)建立相應(yīng)的特征空間；用戶對空間內(nèi)的初始給定樣本進(jìn)行類別標(biāo)記，最終該特征空間包含以下三類樣本：經(jīng)用戶評估的歸屬于某個(gè)類別的根節(jié)點(diǎn)、非根節(jié)點(diǎn)以及后續(xù)基于距離自動(dòng)歸類的非根節(jié)點(diǎn)。OPF算法包含一個(gè)初始化階段與三個(gè)主循環(huán)階段[3]。

2.1.1 OPF構(gòu)建步驟

(1)基于用戶評估的節(jié)點(diǎn)構(gòu)建完全圖并建立該圖的最小生成樹MST(Minimum Spanning Tree)，如圖1(A)至(B)所示。

(2)當(dāng)該MST的某連接弧兩端節(jié)點(diǎn)分屬不同類別，則斷開該連接弧，并將這兩端節(jié)點(diǎn)分別定義為分屬不同類別的兩棵OPT的根節(jié)點(diǎn)，如圖1(C)所示。由于某個(gè)根節(jié)點(diǎn)在斷開連接弧之前可能與多個(gè)屬于其他類別的根節(jié)點(diǎn)相連，因此特征空間中可能存在不同OPT對應(yīng)同一類別的現(xiàn)象。

(3)計(jì)算特征空間中其余未經(jīng)用戶評估的節(jié)點(diǎn)至每個(gè)根節(jié)點(diǎn)的所有可能直接或間接路徑的距離，將每個(gè)未評估節(jié)點(diǎn)基于最小距離路徑連接到相應(yīng)根節(jié)點(diǎn)完成對應(yīng)OPT的構(gòu)建，所有OPT構(gòu)成了OPF，如圖1(F)、(H)、(I)與(K)所示。

圖1 OPF構(gòu)建及算法流程圖

2.1.2 OPF算法流程

(1)初始化階段：①定義特征空間的所有S個(gè)根節(jié)點(diǎn)為S及其代價(jià)值均為0，定義特征空間的所有M個(gè)非根節(jié)點(diǎn)為Rj(j=1,2,...,S)∈R及其代價(jià)值均為正無窮；②以最小堆數(shù)據(jù)結(jié)構(gòu)建立一個(gè)空的優(yōu)先級隊(duì)列P。

(2)第一階段主循環(huán)：①將所有Rj送入隊(duì)列P，如圖1(D)所示；②從P出隊(duì)當(dāng)前代價(jià)值最小的Rj，計(jì)算所有Ti到該Rj的直接連接路徑的代價(jià)值，替換原有的正無窮初始值；③基于代價(jià)值以最小堆數(shù)據(jù)結(jié)構(gòu)將所有Ti依次送入P，如圖1(E)所示。此階段結(jié)束后,P內(nèi)包含S-1個(gè)Rj與M個(gè)Ti。

(3)第二階段主循環(huán)：①再次出隊(duì)當(dāng)前代價(jià)值最小的Rj，計(jì)算每個(gè)Ti到該Rj的直接連接路徑代價(jià)值，若新代價(jià)值低于原代價(jià)值，則更新代價(jià)值并將Ti基于最小堆數(shù)據(jù)結(jié)構(gòu)重新入隊(duì)；②循環(huán)執(zhí)行該步驟S-2次，最終所有Ti都有且僅與一個(gè)Rj以最小代價(jià)值直接連接。此階段結(jié)束后P內(nèi)僅剩M個(gè)Ti，如圖1(G)所示。

(4)第三階段主循環(huán)：①出隊(duì)當(dāng)前代價(jià)值最小的Ti(根據(jù)多連接弧路徑取最大值原理，該Ti必然位于所有可能連接路徑中的最小路徑上)，計(jì)算隊(duì)列中其余Tk(k≠i)∈T通過該出隊(duì)節(jié)點(diǎn)連接到其所在路徑的Rj的代價(jià)值，若該代價(jià)值低于原代價(jià)值，則更新代價(jià)值并將相應(yīng)Tk基于最小堆數(shù)據(jù)結(jié)構(gòu)重新入隊(duì)；②循環(huán)執(zhí)行上一步驟M-1次直至隊(duì)列為空，最終所有Ti都有且僅與一個(gè)Rj以最小代價(jià)值直接或間接連接。最終結(jié)果如圖1(K)所示。

2.2 分類反饋

分類精度高與對初始標(biāo)記訓(xùn)練樣本數(shù)量需求不大兩項(xiàng)優(yōu)點(diǎn)使得OPF在機(jī)器分類領(lǐng)域具有實(shí)際推廣價(jià)值，實(shí)時(shí)響應(yīng)快與可迭代自優(yōu)化特點(diǎn)則令其可部署于相關(guān)反饋領(lǐng)域。

2.2.1 機(jī)器分類

與最近鄰分類算法原理不同，對于待分類節(jié)點(diǎn)而言，OPF算法是基于其至各棵OPT根節(jié)點(diǎn)距離的最小值或類別平均值而非其所在區(qū)域鄰近節(jié)點(diǎn)所屬類別比例實(shí)現(xiàn)分類，待分類節(jié)點(diǎn)被分類后可進(jìn)一步擴(kuò)充優(yōu)化OPF，具體步驟如下：

(1)計(jì)算待分類節(jié)點(diǎn)到特征空間中OPF的每棵OPT的根節(jié)點(diǎn)的所有可能直接或間接連接距離。

(2)記錄該節(jié)點(diǎn)到每棵OPT根節(jié)點(diǎn)的最小距離值，按實(shí)際情況基于以下兩種方案分類：A.將其沿最小距離路徑連接到相應(yīng)根節(jié)點(diǎn)，進(jìn)而歸類至該根節(jié)點(diǎn)所屬類別；此方案適用于OPT數(shù)量較少的情況。B.對其連接至每項(xiàng)類別的同一類別的所有根節(jié)點(diǎn)的最小距離值取平均，將其分配到平均值最小的類別上，并沿最小距離路徑連接到該類別的對應(yīng)根節(jié)點(diǎn)上；此方案適用于OPT數(shù)量較多的情況。

2.2.2 相關(guān)反饋

在相關(guān)反饋應(yīng)用中，OPF包含的訓(xùn)練樣本僅被手動(dòng)或自動(dòng)標(biāo)記為與檢索樣本相關(guān)或非相關(guān)兩類?；谟脩魧z索內(nèi)容的每次評估結(jié)果，系統(tǒng)將反饋給用戶一組再檢索結(jié)果與一組再評估對象，兩組對象的選擇應(yīng)符合以下要求：A.再檢索結(jié)果應(yīng)盡可能逼近用戶理想需求，因此必然從相關(guān)類中選擇；B.再評估對象應(yīng)與用戶理想需求有一定差距但不能偏離過大，若從非相關(guān)類中選擇，則可能由于樣本差異顯著而難以獲得正例樣本，因此本文的再評估對象將選擇相關(guān)類中與相關(guān)類根節(jié)點(diǎn)差異最大的樣本；C.由于特征空間中存在非相關(guān)類根節(jié)點(diǎn)，僅基于與相關(guān)類根節(jié)點(diǎn)的距離來評判樣本是否具有強(qiáng)相關(guān)性是不足的(因?yàn)榭赡艽嬖谂c相關(guān)類及非相關(guān)類根節(jié)點(diǎn)都很近的相關(guān)類節(jié)點(diǎn))。

基于以上分析，在2.1.2節(jié)的定義基礎(chǔ)上，進(jìn)一步定義相關(guān)類根節(jié)點(diǎn)為Um(m=1,2,...,L)以及非相關(guān)類根節(jié)點(diǎn)為Vn(n=1,2,...,S-L)，其中Um∈R且≠Vn，反之亦然；定義相關(guān)類非根節(jié)點(diǎn)為Tp(p=1,2,...，Q,Q

(1)基于用戶對給定對象或首次檢索內(nèi)容的評估結(jié)果按照2.1.1節(jié)所述建立OPF。

(2)運(yùn)用公式(1)計(jì)算每個(gè)Tp的非相關(guān)值。

(3)將指定個(gè)數(shù)的具有最大和最小非相關(guān)值的Tp反饋給用戶，分別作為再評估對象與再檢索結(jié)果。

(4)用戶若對再檢索結(jié)果不滿意，則繼續(xù)對再評估對象進(jìn)行標(biāo)記，系統(tǒng)基于標(biāo)記內(nèi)容重新構(gòu)建OPF，重復(fù)步驟(2)至(4)，直至用戶滿意。

(1)

2.3 迭代自優(yōu)化

OPF可通過分類或交互反饋實(shí)現(xiàn)迭代自優(yōu)化。局部自優(yōu)化是指將待分類樣本依次納入訓(xùn)練樣本集，使其被分類后成為相應(yīng)OPT的一部分進(jìn)而迭代更新分類器；全局自優(yōu)化是指在訓(xùn)練樣本總數(shù)不變的情況下，基于每次交互反饋信息的評估結(jié)果重構(gòu)OPF；兩種優(yōu)化方式的下一次分類或評估的結(jié)果均受上一次結(jié)果的影響，因此屬于迭代自優(yōu)化。與需要大量標(biāo)記訓(xùn)練集的監(jiān)督分類算法不同，OPF算法僅需少量用戶標(biāo)注的訓(xùn)練樣本即可初始化分類器組，進(jìn)而基于最小路徑將其他未標(biāo)記訓(xùn)練樣本自動(dòng)連接到對應(yīng)分類器上實(shí)現(xiàn)該分類器組的構(gòu)造。實(shí)驗(yàn)表明，OPF算法可以通過交互反饋實(shí)現(xiàn)迭代自優(yōu)化，并在有限次數(shù)內(nèi)趨于穩(wěn)定[5-6]。需要注意的是，后續(xù)納入的訓(xùn)練樣本僅能優(yōu)化分類器性能而不能改變分類器數(shù)量，分類器數(shù)量僅受初始標(biāo)記樣本數(shù)量的影響。

3 交互反饋應(yīng)用

本節(jié)通過分析OPF算法在服裝檢索與人臉生成兩個(gè)實(shí)例上的應(yīng)用，進(jìn)一步展示其運(yùn)行機(jī)制與實(shí)際效果。

3.1 服裝檢索應(yīng)用

李宏林等[5]利用基于OPF的相關(guān)反饋去迭代優(yōu)化服裝檢索結(jié)果，如圖2所示(該圖展示僅包含兩類且只有兩棵最優(yōu)路徑樹的特殊情況)，具體步驟如下：

圖2 基于OPF的服裝檢索交互反饋

(1)將待檢索服裝圖像與候選數(shù)據(jù)庫圖像轉(zhuǎn)化為基于Saliency map &Sift方法抽取的特征向量，找出特征空間中與待檢索圖像在歐式距離上最接近的五張圖像作為首次檢索結(jié)果。

(2)用戶對首次檢索結(jié)果進(jìn)行評估，根據(jù)評估結(jié)果建立OPF。

(3)系統(tǒng)基于OPF算法按照公式(1)將非相關(guān)值最低和最高的相似圖像各5張，分別作為再檢索結(jié)果與再評估對象反饋給用戶。

(4)若用戶對再檢索結(jié)果滿意則終止交互反饋，否則重復(fù)步驟(2)至(4)，直至用戶滿意。

實(shí)驗(yàn)結(jié)果表明，OPF算法能在5次迭代內(nèi)顯著提升用戶對檢索結(jié)果的滿意度[5]。

3.2 人像生成應(yīng)用

許彩娥等[6]采用基于OPF的相關(guān)反饋、最優(yōu)相關(guān)點(diǎn)的位移優(yōu)化、以位移優(yōu)化點(diǎn)特征向量為條件參數(shù)的生成競爭網(wǎng)絡(luò)(Generative adversarial network，GAN)及以生成圖像相似度為權(quán)值的插值合成四個(gè)流程實(shí)現(xiàn)相似人像檢索合成，如圖3所示，具體步驟如下：

圖3 基于OPF的條件GAN人像生成交互反饋

(1)在特征空間中基于歐式距離搜索與輸入人像最相似的10張人像。

(2)用戶對檢索結(jié)果進(jìn)行相似與否的二類標(biāo)注，基于標(biāo)注結(jié)果建立OPF。

(3)根據(jù)公式(1)計(jì)算并定位非相關(guān)值最低的最優(yōu)特征向量，對其以基于方向、步長及范圍控制的位移方式在特征空間中移動(dòng)并獲得若干個(gè)人像特征向量。

(4)以這些特征向量作為生成競爭網(wǎng)絡(luò)的條件參數(shù)生成若干張候選圖像，若用戶對候選圖像總體滿意，則可選擇若干張最滿意的放入待插值圖像集合中，否則返回步驟(2)再次評估重置OPF。

(5)用戶對待插值圖像進(jìn)行相似度標(biāo)注，根據(jù)標(biāo)注相似度高低賦予待插值圖像不同的權(quán)重值，基于權(quán)重將待插值圖像在像素級別上進(jìn)一步合成最終人像，若用戶對最終結(jié)果不滿意，仍可回到步驟(2)重復(fù)上述操作。

實(shí)驗(yàn)結(jié)果表明，基于OPF算法的相關(guān)反饋能主動(dòng)干預(yù)并優(yōu)化基于GAN自動(dòng)生成的人臉圖像，但紋理細(xì)節(jié)方面還有待進(jìn)一步優(yōu)化[6]。

4 結(jié)論

分類精度高、實(shí)時(shí)響應(yīng)速度快、初始標(biāo)記訓(xùn)練樣本需求數(shù)量少及可迭代自優(yōu)化等優(yōu)點(diǎn)促使OPF算法能夠在機(jī)器分類與人機(jī)交互反饋等科研與工業(yè)領(lǐng)域得到進(jìn)一步推廣。本文基于圖文描述直觀剖析OPF算法原理與實(shí)現(xiàn)流程，有助于科研工作者更好地復(fù)現(xiàn)該算法并部署在相應(yīng)領(lǐng)域。通過近年來OPF算法在服裝檢索與人臉生成的兩個(gè)實(shí)例應(yīng)用，進(jìn)一步論證了其在人機(jī)交互反饋方面的可行性與實(shí)用性。未來可把OPF算法部署在服裝搭配等對主觀評價(jià)需求較高的研究領(lǐng)域，以進(jìn)一步提升用戶滿意度。