關聯學習:關聯關系挖掘新視角

錢宇華 張明星 成紅紅

(山西大學大數據科學與產業研究院 太原 030006) (計算智能與中文信息處理教育部重點實驗室(山西大學) 太原 030006) (山西大學計算機與信息技術學院 太原 030006)

探索未知事物的關聯關系有助于理解人類關聯認知機理.美國加州大學伯克利分校Speed[1]在《Science》雜志上發表論文稱，從龐大的數據集中發現數據之間潛在的關系十分重要.梁吉業等人[2]在2016年指出大數據相關分析是探尋與發現事物內在規律的重要“導航”工具，自然也是大數據分析與挖掘的關鍵科學問題.錢宇華等人[3]在2015年指出關聯性學習的概念，并指出關聯學習是大數據理論與基礎的重要研究內容之一.

早在19世紀80年代研究者開始展開關于關聯關系挖掘的研究，Galton[4]在研究人類身高遺傳問題時首次提出了相關的概念.Pearson[5]于1988年提出Pearson相關系數，用于刻畫最簡單的線性相關關系，此后經過一個多世紀的發展，線性相關系數有了較為完整的理論基礎和廣泛的應用領域.1959年Renyi[6]給出了關聯依賴度量需滿足的公理化性質，此后研究者基于此公理化要求提出多種形式的關聯度量.2011年《Science》雜志上Reshef等人[7]通過網格劃分估計概率估計互信息，提出能識別線性和非線性共存的復雜關系度量——最大信息系數(maximal information coefficient， MIC).1936年典型相關分析[8](canonical correlation analysis, CCA)被提出用于刻畫變量組間的線性關系，通過同時尋找2個隨機向量的線性投影確定相關關系.CCA只能識別簡單的線性關系，對于復雜的非線性關系，研究者們分別提出了核典型相關分析[9](kernel canonical correlation analysis， KCCA)嘗試通過核映射到希爾伯特空間去識別原始空間中的非線性關系.深度典型相關分析[10](deep canonical correlation analysis， DCCA)，是通過深度神經網絡學習復雜非線性映射，以期得到變換后的線性相關關系.

而在大數據時代，數據通常以多模態形式呈現，多模態對象之間可能存在關聯性，并且研究對象具有特定的語義，想要刻畫對象之間復雜的非線性關系，通過構造方式的關聯關系發現方法往往不能遍歷所有的關系空間，從而無法合理地刻畫關聯關系.而且在人類認知事物的過程中，對已知事物的了解和學習可以對未知事物起到預測和借鑒的作用.回顧已有的關聯關系挖掘方法，都是基于某種假定構造關聯關系度量，對未知數據缺少借鑒作用.因此，本文嘗試采用學習方式來刻畫事物之間的關系，學習一種具有關聯判定能力的關聯關系學習模型.目前的關聯性分析任務主要關注2個變量(向量)之間的相互依賴關系，并且只是對經驗數據的統計分析，而學習2個對象之間關聯關系的模型尚未報道，從學習角度探索2個對象之間的關聯關系并對未知數據有判別能力的關聯學習模型值得嘗試.

類似機器學習中監督學習任務的研究思路，本文首先提出關聯學習的輸入空間、特征空間、輸出空間以及假設空間的定義，討論了關聯學習的聯合概率分布和形式化定義，根據關聯學習的概念，設計了關聯學習模型以及模型評估方法；依據形式化定義構建了二類關聯圖像數據集(two class associated image data sets, TAID)，利用卷積神經網絡提取關聯特征，然后分別用softmax函數和K近鄰算法訓練關聯判別器，提出3種關聯判別器模型：關聯圖像卷積神經網絡模型(associated image convolutional neural network discriminator, AICNN)、關聯圖像LeNet模型(associated image LeNet discriminator，AILeNet)和關聯圖像K近鄰模型(associated imageK-nearest neighbor discriminator， AIKNN)，并將3種判別器模型應用于TAID數據集進行關聯學習；最后總結了關聯判別器的可行性并指出關聯學習問題未來的研究方向.

1 關聯學習(association learning)

關聯學習研究實例對之間的關聯關系，從給定的實例對中學習一個關聯判別模型，使其能對新的輸入實例對進行關聯關系判別.

1.1 關聯學習基本概念

關聯學習任務類似監督學習[11](supervised learning)任務，參考監督學習的相關概念，本文首先給出關聯學習問題中的一些基本概念：

1) 輸入空間U.輸入變量記作U=X,Y，輸入變量的取值u=x,y,x∈X,y∈Y，u=x,y稱為實例對，x∈X，y∈Y分別為對應空間中的元素(實例).需要注意的是實例對u=x,y中的元素可以互換位置，也可能取同一空間中的元素，也即實例對有3種可能形式:u=x,x;u=x,y;u=y,y.

2) 特征空間.輸入實例對u的特征向量記作u=x,y,其中x∈Rp，y∈Rq，p和q分別為實例空間的維度.x和y的特征空間維度可以不同.

3) 輸出空間A.輸出變量記作A，可以是連續型和離散型變量.a是輸出變量的具體取值，表示實例對的關聯關系.

4) 聯合概率分布.假設關聯學習數據集具有聯合分布，即輸入與輸出變量U和A服從聯合概率分布P(U,A)，表示關聯分布函數或關聯密度函數.在關聯學習過程中，假定此聯合概率分布存在，但對于學習系統來說，聯合概率分布的具體定義和形式是未知的，約定訓練數據與測試數據依聯合概率分布P(U,A)獨立同分布產生的.

5) 假設空間F.假設空間定義為關聯判別映射的集合F={f|A=f(U)}，f是由一個參數向量決定的函數族：F={f|A=fθ(U),θ∈{〈Rp,Rq}},參數向量θ取值于所研究對象所在的歐氏空間Rp,Rq，稱為參數空間.關聯學習的目的在于從假設空間中找到最好的關聯學習判別模型.

給定關聯學習問題的相關概念，下面給出關聯學習問題的形式化定義：

定義1.給定數據集T={(u1,a1),(u2,a2),…,(uN,aN)}，其中ui=xi,yi是輸入空間中的觀測值，xi∈Rp,,yi∈Rq,ai是輸出空間中的觀測值，由輸入空間到輸出空間的映射過程稱為關聯學習.根據輸出空間的取值類型不同，關聯學習存在如下2種學習模式：

1) 如果A是連續型隨機變量，即A∈R，a為關聯強度得分，得到的映射稱為關聯度量.具體地：從給定數據集中估計一個關聯度量m:U→A，這個過程稱為關聯強度推斷.在實際問題中，m(U)∈[0,1]，0表示隨機變量X與Y的關聯強度最弱，說明兩者之間無關聯關系；1表示隨機變量X與Y的關聯強度最強，說明兩者之間存在強相關關系.

2) 如果A是離散型隨機變量，即A∈{a1,a2,…,an}，ai∈Z，稱為關聯標簽，學習到的映射稱為關聯判別器.具體地：從給定數據集中學習一個關聯判別器f:U→A，這個過程稱為關聯判別器學習.以簡單的2類實例對為例，對應的輸出空間為A∈{-1，0，1}，-1表示實例對的關聯標簽為負關聯，0表示實例對的關聯標簽為無關聯，1表示實例對的關聯標簽正關聯.

本文主要關注2類實例對的關聯判別器學習問題，不混淆情況下，文中統稱為關聯學習.如圖1所示：當給定一個訓練數據集T={(u1,a1),(u2,a2),…,(uN,aN)}，ui=xi,yi為輸入實例對，分別用不同顏色的三角形和圓形表示，通過關聯學習系統獲得關聯判別器，在關聯判別階段，當新輸入1個uN+1=xN+1,yN+1實例對時，利用學習到的關聯判別器給出輸入實例uN+1的關聯標簽aN+1.

Fig. 1 Association learning schematic diagram圖1 關聯學習示意圖

1.2 關聯學習準則

給定關聯學習的假設空間，需要考慮從假設空間中選擇最優模型的準則.

類似統計機器學習中選擇模型的標準，關聯學習模型也可以通過損失函數衡量一次模型預測的好壞，通過風險函數度量平均意義下模型預測的好壞.

1) 損失函數.衡量關聯判別器輸出和真實值之間的不一致程度的度量稱為損失函數(loss function).從假設空間F中選擇一個關聯判別器，對于給定的實例對U，判別器給出的輸出為f(U)，則損失函數記作L(f(U),A).根據不同的關聯判別模型，L可以設置不同的形式.

Fig. 2 Construct association learning data sets圖2 關聯學習數據集構建

2) 風險函數.模型的輸入、輸出(U,A)是隨機變量，遵循聯合分布P(U,A)，模型f(U)關于聯合分布P(U,A)的平均意義下的損失稱為風險函數或期望損失記作Rexp，

真實環境中關聯學習的聯合分布是未知的，風險函數中的期望值無法確定.實際中可采用經驗風險代替.

3) 經驗風險.對于上述給定的訓練數據集T={(u1,a1),(u2,a2),…,(uN,aN)}，模型f(U)關于訓練數據集的平均損失稱為經驗風險或經驗損失，記作Remp(f)：

期望風險Rexp(f)是模型關于聯合分布的期望損失，經驗損失Remp(f)是模型關于訓練樣本集的平均損失，根據大數定律，當樣本容量N趨于無窮時，經驗損失Remp(f)趨于期望損失Rexp(f).經驗損失最小化的策略認為，經驗損失最小的模型就是最優模型.根據這一策略，按照經驗損失最小化求最優化模型就是求解最優化問題：

其中F為假設空間.

本節給出關聯學習問題中的一些基本概念和模型選擇準則，接下來將對關聯學習的具體模型進行分析.

2 圖像間關聯學習模型

在人類認知事物的過程中，通常通過建立2個對象之間的聯系來分析記憶事物，復雜的關聯認知過程存在于人類的大腦神經元中，本文嘗試模擬人類聯想認知的思維過程和行為方式.在圖像識別方面，計算機對圖像的識別能力甚至已經超過了人類，因此首先研究圖像對之間的關聯關系識別過程.

2.1 圖像關聯數據集構造

本文首次提出從學習的角度挖掘關聯關系，需要將生活中的關聯問題抽象化并構造符合關聯學習定義的數據集.以動物和水果的識別過程為例，人們會認為2種動物或者2種水果的關聯性比1種動物和1種水果的強，這種關聯關系的學習過程在大腦中已經形成判斷標準，但不能抽象地表示出來.

以動物和水果之間關系識別為例，同是2種動物的稱為動物類，輸入為動物-動物實例對，標記關聯標簽為-1；同是2種水果的稱為水果類，輸入為水果-水果實例對，對應的關聯標簽為1；1種動物和1種水果的實例對稱為無關類，輸入為動物-水果或水果-動物實例對相關的關聯標簽為0.-1和1都代表實例對之間是強相關的，為了區分動物類和水果類采用不同的類別標記，這2種標記是可以互換的.數據集的構造如圖2所示：

2.2 圖像關聯數據特征提取

深度學習在圖像識別方面有著非常領先的優勢，本文采用深度學習中的卷積神經網絡提取關聯特征.LeCun[12]在1998年提出LeNet，用于解決手寫數字識別任務.之后，CNN的最基本的架構就確定為：卷積層、池化層、全連接層.深度網絡現在也已被廣泛地應用于對數據進行表征的學習中，例如深度玻爾茲曼機[13]、深度自動編碼器[14]和深度非線性前饋網絡[15]，它們在學習數據視圖的表示方面取得了很大的成功.2006年后，隨著深度學習理論的完善，尤其是逐層學習和參數微調(fine-tuning)技術的出現[16]，卷積神經網絡開始快速發展，在結構上不斷加深，各類學習和優化理論得到引入[17].自2012年的AlexNet[18]開始，各類卷積神經網絡多次成為ImageNet大規模視覺識別競賽(ImageNet large scale visual recognition challenge， ILSVRC)[19]的優勝算法，包括2014年的ZFNet[20]和2015年的ResNet[21]，以及具有很強拓展性的VGGNet[22]，其有很強的泛化能力、穩定的卷積特征和較好的表達能力.本文借鑒上述的一些經典神經網絡提取關聯數據集的特征.具體的提取方法及參數設置在實驗部分詳細介紹.

2.3 關聯判別器設計

采用卷積神經網絡得到關聯數據集的特征，采用ReLU(rectified linear unit)函數f(x)=max(0,x)作為關聯判別器的激活函數，如圖3所示：

Fig. 3 ReLU activation function圖3 ReLU激活函數

(1)

(2)

(3)

Adam優化算法基本思想是將動量梯度下降和RMSprop結合.基本步驟：

1) 初始化.vdW=0,SdW=0,vdb=0,Sdb=0.

2) 計算微分dW,db.

3) 計算動量指數加權平均數.

4) RMSprop更新，需要計算修正偏差.

2.4 關聯判別器評估

其中N′是測試樣本容量.

本文采用0-1損失函數：L(A,f(U))=f(x),f(x)={0，1|當A=f(U)時為0，當A≠f(U)時為1}進行模型評估，損失函數值越小，模型就越好.具體實驗模型評價指標為測試精度，記作val_acc，

其中N′是測試樣本容量.

3 關聯判別器應用

第1節和第2節設計了圖像間關聯學習的模型以及一些評價標準，現檢驗關聯學習的理論框架在圖像關聯數據集上的應用.圖4展示了關聯學習應用的整體模型，以2類關聯圖像數據為例學習關聯判別器的過程.

Fig. 4 Application of association learning圖4 關聯學習應用示意圖

3.1 關聯判別器應用數據集

如圖2所示，構建2類關聯圖像數據集(TAID).具體地：分別選取100種不同的水果和100種不同的動物，其中任意挑選75種水果和75種動物，將這些水果和動物組合成150個對象，對象之間兩兩組合構成22 500個訓練樣本對，剩下25種水果和25種動物組合成50個對象，對象之間兩兩組合構成2 500個測試樣本對(22500train-2500test)，訓練和測試對象種類沒有重合，對于圖片像素設置了3組不同的大小分別為64×64，128×128，256×256.

同樣的方法分別找到150種不同的水果和150種不同的動物，其中任意挑選100種水果和100種動物，將這些水果和動物組合成200個對象，對象之間兩兩組合構成40 000個訓練樣本對，剩下50種水果和50種動物組合成100個對象，對象之間兩兩組合構成10 000個測試樣本對(40000train-10000test).同樣的方法分別找到200種不同的水果和200種不同的動物，其中任意挑選150種水果和150種動物，將這些水果和動物組合成300個對象，對象之間兩兩組合構成90 000個訓練樣本對，剩下50種水果和50種動物組合成100個對象，對象之間兩兩組合構成10 000個測試樣本對(90000train-10000test)，40000train-10000test和90000train-10000test數據集只設置了64×64大小像素的圖像.

3.2 實驗設置及結果展示

首先選用4種經典的卷積神經網絡模型LeNet，AlexNet，ZFNet，ResNet，分別在TAID數據集設置的22500train-2500test,40000train-10000test,90000train-10000test的64×64維圖像進行實驗.

同時本文還提出了一個關聯圖像卷積神經網絡模型(association image CNN, AICNN)，圖5所示為模型的結構，其中不同的顏色代表模型中所使用的網絡層類型不同.用上述的數據集進行了實驗，迭代次數都為40次.對于各個模型的關聯判別精度做了一個統計，如表1所示，可以發現在本文提出的AICNN模型中3個數據集的關聯判別精度都最高，其中90000train-10000test的數據集關聯判別精度達到了0.821 7；對于其他模型實驗判別精度的結果，40000train-10000test和90000train-10000test明顯高于22500train-2500test的數據集.

Table 1 Model Discriminant Accuracy表1 模型關聯判別精度表

Fig. 5 AICNN model圖5 AICNN模型

如圖6所示，用AICNN模型在90000訓練樣本中隨機選擇22500，40000，62500，90000樣本分別進行40次迭代訓練，用相同的10000樣本測試發現90000訓練樣本關聯判別精度最高為第23次迭代的0.821 7，62500訓練樣本判別精度最高為第30次迭代的0.785 1，40000訓練樣本判別精度最高為第30次迭代的0.776 8，22500訓練樣本判別精度最高為第40次迭代的0.743 8.實驗結果表明在訓練樣本增多的情況下，模型判別效果好并且達到最高測試精度的模型迭代次數少.

在22500train-2500test樣本中，分別對64×64，128×128，256×256這3種不同像素的樣本使用LeNet模型進行了實驗，由于256×256像素樣本經過AICNN模型11層卷積訓練出現內存不足的問題，所以在LeNet模型的基礎上對模型的卷積層進行了修改如圖7所示,其中不同的顏色代表模型中所使用的網絡層類型不同.對AILeNet網絡的模型進行實驗，結果如圖8所示，在AILeNet模型實驗中256×256像素樣本迭代60次之后的判別精度最高到達了0.845 6.

Fig. 7 AILeNet model圖7 AILeNet模型

Fig. 8 Three different pixel samples test accuracy圖8 3種不同像素樣本測試精度

在對LeNet模型的改進過程中，我們分別進行了3層卷積、4層卷積、5層卷積的實驗如圖9所示，其中圖7為4層卷積模型，3層卷積和5層卷積分別為減少和增加32個3×3的卷積，3層卷積關聯判別精度為0.831 6，4層卷積關聯判別精度為0.845 6，5層卷積關聯判別精度為0.843 6，實驗結果表明在圖像像素大的情況下可以提供的關聯特征較多，并且較少的卷積層數可以使關聯判別器的判別精度變高.

Fig. 9 AILeNet test accuracy圖9 AILeNet模型實驗測試精度

從另外一個角度考慮，使用傳統的機器學習K近鄰算法，我們提出一個新的關聯圖像K近鄰(asso-ciation image KNN, AIKNN)模型.首先將22500train-2500test樣本中64×64，128×128，256×256這3種不同像素的樣本圖像使用VGG-19訓練對訓練和測試數據進行特征提取，降為1 000維向量；然后取K=9使用KNN算法進行關聯判別器訓練實驗，結果如圖10所示：256×256像素的數據集22500train-2500test測試精度為0.866 4. 2種角度的關聯判別器模型得到的關聯預測精度接近85%，說明從學習的角度挖掘關聯關系的方法值得探索.

Fig. 10 AIKNN test accuracy圖10 AIKNN模型實驗測試精度

4 總結與展望

本文提出從學習的角度研究關聯關系挖掘問題，嘗試給出關聯學習基本概念如輸入空間、特征空間、輸出空間及假設空間等，并給出關聯學習的形式化定義，評估模型的損失函數和風險函數定義.根據關聯學習的形式化定義以及模擬人類關聯認知的思維過程，構建了簡單的二類關聯圖像數據集(TAID)，并用卷積神經網絡對關聯圖像數據集進行特征提取，在此基礎上用softmax函數和K近鄰算法訓練關聯判別器，根據訓練方法的不同，分別提出AICNN，AILeNet,AIKNN這3種關聯判別模型.在測試階段ALLeNet判別器的判別精度達到0.845 6，AIKNN判別器的判別精度達到0.866 4，實驗結果初步驗證了學習角度的關聯關系挖掘的可行性.

關聯關系挖掘是大數據基礎理論研究中的重要內容之一，現有的關聯關系挖掘多是基于統計學假定的關聯強度估計，本文首次探索學習角度的關聯學習模型，為相關領域的研究者提供了一種新的研究視角.在初次研究過程中，不管是關聯學習理論基礎的搭建、數據集構建還是關聯判別模型的設計和評估函數的選擇都存在不完善之處，雖然部分實驗驗證了關聯學習的可行性，但是關于這個角度的關聯關系挖掘研究之路還很長，在后續的研究過程中將不斷充實和完善關聯學習理論與應用.

貢獻聲明：作者錢宇華提出從學習角度進行關聯關系挖掘和關聯學習的思想，并指導督促完成實驗和論文;作者張明星、成紅紅共同給出關聯學習的基本概念和形式化表達，制定實驗內容并具體操作，撰寫文章.三位作者同等貢獻，共同一作.