BPR優(yōu)化的矩陣補全圖像分類算法

梁順攀，雷 瑜，馮凱東，李 晨，原福永，黃國言

(燕山大學(xué)信息科學(xué)與工程學(xué)院，河北秦皇島066004)

E-mail:rararasr@stumail.ysu.edu.cn

1 引言

圖像分類是計算機視覺的熱門話題，通過提取圖像特征，使用分類器對其分類，從而實現(xiàn)圖像分類.目前圖像分類基本方法主要分為兩類:以詞袋模型(Bag-of-Words)［1］為代表的傳統(tǒng)圖像分類方法和以深度學(xué)習(xí)模型為代表的流行圖像分類方法.

傳統(tǒng)的詞袋模型(Bag-of-Words)最初用于文本處理領(lǐng)域，主要優(yōu)勢在于簡單、有效.它是最早且應(yīng)用最廣泛的判別式模型，詞袋模型與其相關(guān)方法在圖像領(lǐng)域主要描述圖像的局部特征，如 SIFT(Scale Invariant Feature Transform)［2］和HOG(Histogram of Gradient)［3］等.它將圖像看做無序詞塊集，用詞塊在圖像出現(xiàn)的次數(shù)描述圖像，實現(xiàn)圖像分類.Li等人基于BoW模型提出了上下文詞袋(Contextual Bag-of-Words，簡稱 CBoW)模型［4］，根據(jù)詞塊分布的相似性，通過語義概念關(guān)系進行建模.Farhangi構(gòu)建了詞塊的空間關(guān)系［5］，雖然準(zhǔn)確度得到提升，但詞塊過多計算時間復(fù)雜度過大.Chen提出一種新的詞袋模型空間構(gòu)造方法［6］，將圖像整體與局部的直方圖信息結(jié)合，完成詞袋模型的空間構(gòu)造.圖像特征提取一般是人為設(shè)定特征提取模式，然而，對于復(fù)雜圖像，人為難以有效設(shè)定.

深度學(xué)習(xí)模型［7］側(cè)重于自動提取有效圖像特征，保證精度且降低時間復(fù)雜度.AlexNet在ImageNet大規(guī)模視覺識別挑戰(zhàn)提出8層的深度卷積網(wǎng)絡(luò)［8］.VGG將卷積網(wǎng)絡(luò)的深度提高到19 層［9］.GoogleNet的 Inception 深層架構(gòu)［10］，構(gòu)建了 22層深層網(wǎng)絡(luò).為了利用重復(fù)訓(xùn)練同一訓(xùn)練圖像所帶來的差異性，Shi提出了一種對稱神經(jīng)網(wǎng)絡(luò)模型［11］，取得良好的分類性能.雖然網(wǎng)絡(luò)的深度對提升圖像分類性能有一定影響，但僅線性地增加網(wǎng)絡(luò)深度會造成梯度消失，網(wǎng)絡(luò)精度的下降，分類性能的降低.

此外，詞袋模型和深度學(xué)習(xí)模型都是基于圖像內(nèi)容的分類方法.而要獲取圖片的特征，僅靠對形狀、顏色、像素方面信息的計算有很大缺陷;且網(wǎng)絡(luò)中的圖片尺寸不一，分辨率不同，無法統(tǒng)一處理.

綜上所述，本文設(shè)計了BPR優(yōu)化的矩陣補全方法，該方法通過矩陣分解補全稀疏的圖像-標(biāo)簽矩陣;通過BPR-OPT優(yōu)化法則優(yōu)化，從而預(yù)測出圖片標(biāo)簽，實現(xiàn)圖像分類.本文將BPR(貝葉斯個性化排序)優(yōu)化的標(biāo)簽排序結(jié)果，與基于SVD的改進算法FunkSVD1https://sifter.org/～ simon/journal/20061211.html的標(biāo)簽排序結(jié)果進行對比，得出本文設(shè)計的模型在性能上更有優(yōu)勢.

本文結(jié)構(gòu)如下:第二部分介紹算法相關(guān)技術(shù);第三部分詳述矩陣分解的矩陣補全算法過程;第四部分進行實驗與分析結(jié)果;第五部分對全文進行了總結(jié).

2 矩陣補全

2.1 壓縮感知技術(shù)

如今，圖像數(shù)據(jù)的爆炸式增長，帶來諸多問題，例如海量圖片數(shù)據(jù)的存儲問題、對圖片信息的處理等.為了提高海量圖片在計算機上的處理效率，采用了壓縮感知［12］技術(shù).文中對圖片數(shù)據(jù)的存儲壓縮感知技術(shù)是對原圖片數(shù)據(jù)在保證不失真的同時進行采集與壓縮，用遠小于原圖片維數(shù)的稀疏特征表示圖片原始信息，通過低維的測量值向量恢復(fù)出高維稀疏的原始信號向量，極大提高了處理圖片的效率.但壓縮感知技術(shù)是面向一維空間的，而現(xiàn)實中對圖像的描述大多是多維的.

2.2 矩陣補全模型

矩陣補全［13］是壓縮感知理論在矩陣空間中的衍生，目前已廣泛應(yīng)用于圖像處理領(lǐng)域，其核心是根據(jù)矩陣已知元素估計未知元素，從而恢復(fù)出完整矩陣.若不對矩陣做任何假設(shè)，且矩陣缺失的元素值不受限制，則恢復(fù)出的矩陣不唯一.為了保證恢復(fù)矩陣唯一，通常會做一些假設(shè)，例如標(biāo)準(zhǔn)的矩陣補全問題可用如下的秩最小化約束優(yōu)化模型［14］公式(1)所示:

其中PΩ(X)表示矩陣X在集合Ω上的投影.

但是由于秩函數(shù)Rank()的非凸性使得標(biāo)準(zhǔn)矩陣補全問題成為一個NP難題.為解決該問題，本文簡介并分析以下三種解決方法.

2.2.1 基于核范數(shù)松弛的矩陣補全模型

為解決該問題，F(xiàn)azel提出了基于核范數(shù)松弛的矩陣補全模型［14］，采用凸核范數(shù)代替非凸秩函數(shù)，將標(biāo)準(zhǔn)的矩陣補全問題轉(zhuǎn)換為如公式(2)所示的凸約束優(yōu)化模型.

但此模型的局限性在于模型求解過程中用到復(fù)雜的矩陣奇異值分解，求解模型的效率和可擴展性較低，且不適用處理數(shù)據(jù)規(guī)模較大的場景.

2.2.2 基于非凸函數(shù)松弛的矩陣補全模型

雖然基于核范數(shù)松弛的矩陣補全模型的核范數(shù)是秩函數(shù)在單位球內(nèi)的最佳凸逼近，但二者之間仍存在較大差異.Nie等人提出的基于非凸函數(shù)松弛的矩陣補全模型［15］，采用更加貼合的非凸函數(shù)來逼近秩函數(shù)，具體表示為公式(3)所示:

但基于非凸函數(shù)松弛的矩陣補全模型模型效率低、可擴展性受限，可能存在局部最優(yōu)解，且當(dāng)數(shù)據(jù)量較大時，性能較低.

2.2.3 基于矩陣分解的矩陣補全模型

相對于上文所介紹的兩個模型，基于矩陣分解的矩陣補全［16］一方面可以適用于大規(guī)模問題，將目標(biāo)矩陣分解成兩個低秩矩陣的乘積，進而預(yù)測出圖片標(biāo)簽缺失的部分，充分利用隱式信息，提高圖像分類精確度.該模型另一方面可避免復(fù)雜的矩陣奇異值分解，實現(xiàn)分布式并行化，降低時間復(fù)雜度，加速算法執(zhí)行效率，提高圖像分類的效率.所以，本文選取基于矩陣分解的矩陣補全模型，具體形式如公式(4)所示:

其中Z為目標(biāo)矩陣，U，V為分解后的兩個低秩矩陣.

該模型在很大程度上提高了圖像分類的高效性和準(zhǔn)確性.

本文第三部分使用基于矩陣分解的矩陣補全模型對稀疏的圖像-標(biāo)簽矩陣進行補全，以減少計算時間，進而提高圖像分類精確度.

3 BPR優(yōu)化的矩陣補全模型

3.1 貝葉斯個性化排序(BPR)算法

BPR(個性化貝葉斯排序)常用于推薦系統(tǒng)領(lǐng)域，是基于矩陣分解的一種排序算法，該算法為用戶提供想購買的個性化商品推薦列表.BPR算法是基于貝葉斯后驗優(yōu)化的個性化排序算法.與經(jīng)典的funkSVD之類算法相比，它不是做全局的評分優(yōu)化，而是針對每一個用戶自己的商品喜好程度做排序優(yōu)化.例如用戶在瀏覽商品時，點擊了商品i，未點擊j，BPR算法認為，用戶對商品i的喜好程度大于j，則在推薦列表中，i的位置優(yōu)先于j.BPR在推薦領(lǐng)域取得巨大成功，一方面由于BPR計算復(fù)雜度低;另一方面，BPR對隱式反饋信息充分利用.

本文則將BPR的思想應(yīng)用圖像分類領(lǐng)域，即將BPR思想與本文所提出的基于矩陣分解的矩陣補全模型融合，對預(yù)測出的標(biāo)簽優(yōu)化其排序結(jié)果，進而完成圖像分類.

該算法的重點不是優(yōu)化圖像與標(biāo)簽的相關(guān)度，而是優(yōu)化為圖像推薦的標(biāo)簽順序.在推薦系統(tǒng)的應(yīng)用領(lǐng)域，由于BPR算法是基于貝葉斯理論的，所以存在的前提有兩個，一是每個用戶的偏好行為都獨立于其他用戶，即與其他用戶無關(guān);二是用戶對不同的物品的喜好程度相互獨立，即與其他物品無關(guān).本文將此算法應(yīng)用到圖像分類領(lǐng)域，做如下假設(shè).

首先，假設(shè)圖像與標(biāo)簽的關(guān)系與其它圖像相互獨立，也就是圖像對標(biāo)簽i或?qū)更為匹配，與其他的圖像無關(guān).其次，假設(shè)圖像對不同標(biāo)簽的匹配程度相互獨立.在此前提下，通過在先驗知識下去極大化后驗概率，優(yōu)化標(biāo)簽排序，補全標(biāo)簽.

3.2 矩陣分解與補全

矩陣分解的核心思想是由于用戶的興趣只受少數(shù)因子影響，因此將稀疏且高維的User-Item評分矩陣分解為兩個低秩矩陣，通過User-Item評分矩陣分解得到用戶特征矩陣P與物品特征矩陣Q，通過P和Q的乘積預(yù)測用戶對物品的評分.求解用戶和物品的特征向量時，可通過梯度下降(Gradient Descend)的方法高效地求解.

矩陣分解方法將高維User-Item評分矩陣映射為兩個低維用戶和物品矩陣，解決了數(shù)據(jù)稀疏性問題.但使用矩陣分解還具有模型訓(xùn)練比較費時，推薦結(jié)果可解釋性差等問題.

因此，本文利用BPR-OPT優(yōu)化準(zhǔn)則對矩陣分解優(yōu)化，解決圖像標(biāo)簽補全問題，完成圖像分類.

3.3 BPR優(yōu)化的矩陣分解算法

3.3.1 模型推導(dǎo)

本文用U代表所有圖片集合，I代表所有的標(biāo)簽集合，S表示所有圖片和標(biāo)簽的隱式反饋關(guān)系，并假設(shè)S中的所有反饋都是正反饋(圖片所缺失的相關(guān)標(biāo)簽).假若對于一對標(biāo)簽i和j，j跟圖片的相關(guān)度更高，則可以表示為i＞uj，最終本模型的求解目標(biāo)為 P(i＞uj|θ).

采用最大化后驗概率方法，應(yīng)用貝葉斯公式后，如公式(5)所示:

其中＞u為圖片的偏序關(guān)系，θ代表任意模型中的參數(shù)向量(本文為矩陣分解模型)，對于所有圖片公式(6)是成立的:Ds表示 u∈U;i，j∈I且的 i＞uj三元組集合.例如三元組(u，i，j)表示圖片u與標(biāo)簽i的相關(guān)度大于標(biāo)簽j.

將相對于標(biāo)簽j，圖片與標(biāo)簽i的相關(guān)度更高，定義為公式(7)所示:

其中σ為邏輯回歸函數(shù)，如公式(8)所示:

^Xu，i，j(θ)為模型參數(shù) θ的實值函數(shù)，用來表示圖片 u 與標(biāo)簽i、標(biāo)簽j的潛在關(guān)系.最終得出本模型的目標(biāo)函數(shù)如公式(9)所示:

其中λθ為模型中的正則化參數(shù).

3.3.2 隨機梯度下降算法

得到目標(biāo)函數(shù)，再對目標(biāo)函數(shù)求參.這里采用梯度下降方法中的隨機梯度下降方法求解參數(shù)，對BPR-OPT求梯度過程如下.

則在隨機梯度下降法中每次迭代的公式為(10)所示:

這里的α代表學(xué)習(xí)率(learning rate).

由于大多數(shù)的推薦算法都是基于一個標(biāo)簽i上用戶的偏好進行建模的，故在這里將三元組(u，i，j)分解成形式如公式(11)所示:

3.3.3 矩陣分解思想

X為圖像與標(biāo)簽的關(guān)系矩陣:X:U×I，Xui為矩陣中的元素，代表圖像對標(biāo)簽的關(guān)系，Xui值越大，代表圖像與標(biāo)簽之間的關(guān)系越強.

矩陣分解的目標(biāo)是將關(guān)系矩陣X近似分解為兩個低秩矩陣W:U×K，與矩陣H:I×K，如公式(12)所示.

矩陣W表示圖像的特征矩陣，矩陣H表示標(biāo)簽的特征矩陣，矩陣的每一行代表某個圖像的特征向量;矩陣W與矩陣H中的維數(shù)K代表矩陣分解思想中的潛在因子數(shù).

則在本模型中，上式可寫成為公式(13)所示:

將公式(11)和公式(13)代入到迭代公式中去，得出的結(jié)果如公式(14)所示:

3.3.4 算法流程

為驗證提出的BPR優(yōu)化的矩陣補全算法的良好性能，本文在Librec工具庫和數(shù)據(jù)集Open Images上進行實驗.

4 實驗與結(jié)果

4.1 數(shù)據(jù)集描述

本文選用的是Google發(fā)布的大規(guī)模圖像數(shù)據(jù)集Open Images.該數(shù)據(jù)集含大約900萬張的鏈接圖像，橫跨了大約6000個類別.其中圖像的標(biāo)簽是圖像層級的，即對于給定的一張圖像，標(biāo)注出圖像中包含的實體，場景等.每一張圖像都有唯一的64-bit的標(biāo)識碼(id)，數(shù)據(jù)集分為訓(xùn)練集(training set)，包含9011219張圖像，每一張圖像包含0個，1個或者多個圖像層次(image-level)的標(biāo)簽(LabelName).數(shù)據(jù)集中包含 image.csv，annotations-machine.csv 以及 labels.csv 三個文件.其中image.csv文件存儲原圖像信息，每一項包括原圖像的鏈接地址，圖片對于唯一的標(biāo)識碼(ImageID)、標(biāo)題、作者以及許可等信息.Annotations-machine.csv文件中存儲的是圖像和標(biāo)簽的對應(yīng)關(guān)系即圖片標(biāo)識碼(ImageID)，標(biāo)簽(Label-Name)以及二者的相關(guān)度(conf).labels.csv文件存儲的是標(biāo)簽(LabelName)具體含義.

數(shù)據(jù)集預(yù)處理

算法首先使用Python程序中的csv包，將annotationsmachine.csv數(shù)據(jù)文件讀入到內(nèi)存.將文件中的數(shù)據(jù)按4:1的比例劃分為訓(xùn)練集(training set)和測試集(testing set).為了便于算法計算與識別，將數(shù)據(jù)中的ImageID和LabelName全部用數(shù)字(0，1，2，…)重新編號，每一個 ImageID和 Label-Name分別由一個唯一的數(shù)字表示.數(shù)據(jù)處理前后對比如圖1所示.

圖1 數(shù)據(jù)處理對比圖Fig.1 Comparison diagram of data processing

算法的整體流程為，首先在訓(xùn)練集上多次迭代訓(xùn)練模型，然后在測試集上確定算法參數(shù)，得到最優(yōu)結(jié)果.

4.2 對比算法FunkSVD

為與本文提出的BPR優(yōu)化的矩陣補全算法進行對比，本文選取經(jīng)典的SVD改進算法——funkSVD算法.

4.2.1 模型推導(dǎo)

FunkSVD算法的提出主要是為了解決傳統(tǒng)的奇異值分解方法(SVD)所存在的問題，即矩陣分解操作耗時及只能對稠密矩陣使用.此種改進算法又被稱為隱語義模型(Latent factor model，LFM)或潛在因素模型.

FunkSVD的目標(biāo)函數(shù)如公式(15)所示:

mij:表示標(biāo)簽i與標(biāo)簽j的相關(guān)度;pi:表示第i個圖像的特征向量;qj:表示第j個標(biāo)簽的特征向量.

4.2.2 梯度下降算法

常見的梯度下降算法包括批量梯度下降以及隨機梯度下降等.批量梯度下降每次迭代需要對全部樣本計算，直到滿足收斂條件或達到最大迭代次數(shù)，如果樣本數(shù)據(jù)量大，訓(xùn)練過程較為緩慢;隨機梯度下降每次迭代使用一個樣本更新參數(shù)，不需要計算所有樣本，使得訓(xùn)練速度加快.由于本文利用龐大的數(shù)據(jù)集進行實驗，為了提升訓(xùn)練速度，選擇隨機梯度下降算法求解參數(shù)，對pi，qj求導(dǎo)過程如下.

pi和qj在梯度下降法中的迭代公式如(18)與公式(19)所示.

4.2.3 算法流程

FunkSVD算法描述如下:

1.Initialize the model parameterθ

2.Repeat

3.Calculate the gradients with Eq.(18)(19)

4.Until convergence

5.Return piand q

4.3 實驗結(jié)果與分析

本算法選用LibRec作為運行平臺，使用Google發(fā)布的大規(guī)模圖像數(shù)據(jù)集Open Images進行驗證，并使用梯度下降方法進行模型訓(xùn)練，比較FunkSVD算法與BPR優(yōu)化的矩陣補全算法，由實驗結(jié)果得出相對于FunkSVD算法，矩陣分解的BPR優(yōu)化算法具有更好的表現(xiàn).三種評估指標(biāo)結(jié)果如表1所示.

表1 算法結(jié)果對比表Table 1 Algorithm results comparison table

對比表中指標(biāo)數(shù)據(jù)可得，BPR算法結(jié)果在準(zhǔn)確率方面是FunkSVD算法結(jié)果的8.5倍，召回率方面是FunkSVD算法結(jié)果的14.8倍，AUC方面是 FunkSVD算法結(jié)果的1.6倍.因此，無論是在準(zhǔn)確率、召回率還是AUC指標(biāo)方面，BPR結(jié)果值都優(yōu)于FunkSVD.

相對于奇異值分解的改進算法(FunkSVD)，貝葉斯個性化排序算法(BPR)優(yōu)化后的矩陣分解不僅保證了使用矩陣分解對原矩陣未知值進行預(yù)測，避免數(shù)據(jù)冗余導(dǎo)致的高計算復(fù)雜度，還對預(yù)測結(jié)果進行了優(yōu)化排序，并在訓(xùn)練過程中，通過隨機采樣獲取數(shù)據(jù)值，在保證精確度的前提下，減少了算法的運行時間，因此矩陣分解的BPR優(yōu)化算法優(yōu)于FunkSVD算法.

5 結(jié)論

本文摒棄了利用像素信息進行圖像分類的傳統(tǒng)方法，采用圖片與標(biāo)簽相對應(yīng)的方式進行圖像分類.

本文的優(yōu)勢在以下幾個方面，首先在數(shù)據(jù)處理上，通過矩陣補全對數(shù)據(jù)先壓縮后提取，避免數(shù)據(jù)冗余導(dǎo)致的高計算復(fù)雜度，從而預(yù)測出圖片標(biāo)簽.當(dāng)數(shù)據(jù)集中不存在像素信息時，需要根據(jù)imageID和lable學(xué)習(xí)圖片與lable的對應(yīng)關(guān)系，不需要圖像信息參與計算，大大加快了訓(xùn)練過程.其次是模型的選取，本文提出的BPR優(yōu)化的矩陣補全算法與基于圖片內(nèi)容的圖像分類不同，解決了當(dāng)數(shù)據(jù)集中無可用圖像像素信息時的分類問題，大大減少計算時間，不需要通過圖片內(nèi)容信息去計算每張圖片的相似度，而是通過隱式地預(yù)測圖片的標(biāo)簽信息，快速為圖片添加標(biāo)簽.最后在算法結(jié)合方面，本文提出的基于矩陣分解的矩陣補全模型與BPR(貝葉斯個性化排序)算法結(jié)合，優(yōu)化標(biāo)簽排序結(jié)果.與基于 SVD的改進算法FunkSVD進行實驗對比，證明本文設(shè)計的模型在性能上更有優(yōu)勢.