BPR優化的矩陣補全圖像分類算法

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

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

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

1 引言

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

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

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

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

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

本文結構如下:第二部分介紹算法相關技術;第三部分詳述矩陣分解的矩陣補全算法過程;第四部分進行實驗與分析結果;第五部分對全文進行了總結.

2 矩陣補全

2.1 壓縮感知技術

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

2.2 矩陣補全模型

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

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

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

2.2.1 基于核范數松弛的矩陣補全模型

為解決該問題，Fazel提出了基于核范數松弛的矩陣補全模型［14］，采用凸核范數代替非凸秩函數，將標準的矩陣補全問題轉換為如公式(2)所示的凸約束優化模型.

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

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

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

但基于非凸函數松弛的矩陣補全模型模型效率低、可擴展性受限，可能存在局部最優解，且當數據量較大時，性能較低.

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

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

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

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

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

3 BPR優化的矩陣補全模型

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

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

本文則將BPR的思想應用圖像分類領域，即將BPR思想與本文所提出的基于矩陣分解的矩陣補全模型融合，對預測出的標簽優化其排序結果，進而完成圖像分類.

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

首先，假設圖像與標簽的關系與其它圖像相互獨立，也就是圖像對標簽i或對j更為匹配，與其他的圖像無關.其次，假設圖像對不同標簽的匹配程度相互獨立.在此前提下，通過在先驗知識下去極大化后驗概率，優化標簽排序，補全標簽.

3.2 矩陣分解與補全

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

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

因此，本文利用BPR-OPT優化準則對矩陣分解優化，解決圖像標簽補全問題，完成圖像分類.

3.3 BPR優化的矩陣分解算法

3.3.1 模型推導

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

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

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

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

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

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

其中λθ為模型中的正則化參數.

3.3.2 隨機梯度下降算法

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

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

這里的α代表學習率(learning rate).

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

3.3.3 矩陣分解思想

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

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

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

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

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

3.3.4 算法流程

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

4 實驗與結果

4.1 數據集描述

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

數據集預處理

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

圖1 數據處理對比圖Fig.1 Comparison diagram of data processing

算法的整體流程為，首先在訓練集上多次迭代訓練模型，然后在測試集上確定算法參數，得到最優結果.

4.2 對比算法FunkSVD

為與本文提出的BPR優化的矩陣補全算法進行對比，本文選取經典的SVD改進算法——funkSVD算法.

4.2.1 模型推導

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

FunkSVD的目標函數如公式(15)所示:

mij:表示標簽i與標簽j的相關度;pi:表示第i個圖像的特征向量;qj:表示第j個標簽的特征向量.

4.2.2 梯度下降算法

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

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 實驗結果與分析

本算法選用LibRec作為運行平臺，使用Google發布的大規模圖像數據集Open Images進行驗證，并使用梯度下降方法進行模型訓練，比較FunkSVD算法與BPR優化的矩陣補全算法，由實驗結果得出相對于FunkSVD算法，矩陣分解的BPR優化算法具有更好的表現.三種評估指標結果如表1所示.

表1 算法結果對比表Table 1 Algorithm results comparison table

對比表中指標數據可得，BPR算法結果在準確率方面是FunkSVD算法結果的8.5倍，召回率方面是FunkSVD算法結果的14.8倍，AUC方面是 FunkSVD算法結果的1.6倍.因此，無論是在準確率、召回率還是AUC指標方面，BPR結果值都優于FunkSVD.

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

5 結論

本文摒棄了利用像素信息進行圖像分類的傳統方法，采用圖片與標簽相對應的方式進行圖像分類.

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