一種基于最大值損失函數(shù)的快速偏標記學習算法

周　瑜　賀建軍,　顧　宏　張俊星

1(大連理工大學電子信息與電氣工程學部　遼寧大連　116024)2(大連民族大學信息與通信工程學院　遼寧大連　116600)(yuzhou829@sina.com)

一種基于最大值損失函數(shù)的快速偏標記學習算法

周瑜1賀建軍1,2顧宏1張俊星2

1(大連理工大學電子信息與電氣工程學部遼寧大連116024)2(大連民族大學信息與通信工程學院遼寧大連116600)(yuzhou829@sina.com)

摘要在弱監(jiān)督信息條件下進行學習已成為大數(shù)據(jù)時代機器學習領域的研究熱點，偏標記學習是最近提出的一種重要的弱監(jiān)督學習框架,主要解決在只知道訓練樣本的真實標記屬于某個候選標記集合的情況下如何進行學習的問題，在很多領域都具有廣泛應用.最大值損失函數(shù)可以很好地描述偏標記學習中的樣本與候選標記間的關系，但是由于建立的模型通常是一個難以求解的非光滑函數(shù)，目前還沒有建立基于該損失函數(shù)的偏標記學習算法.此外，已有的偏標記學習算法都只能處理樣本規(guī)模比較小的問題，還沒看到面向大數(shù)據(jù)的算法.針對以上2個問題，先利用凝聚函數(shù)逼近最大值損失函數(shù)中的max(·)將模型的目標函數(shù)轉換為一個光滑的凹函數(shù)，然后利用隨機擬牛頓法對其進行求解，最終實現(xiàn)了一種基于最大值損失函數(shù)的快速偏標記學習算法.仿真實驗結果表明，此算法不僅要比基于均值損失函數(shù)的傳統(tǒng)算法取得更好的分類精度，運行速度上也遠遠快于這些算法，處理樣本規(guī)模達到百萬級的問題只需要幾分鐘.

關鍵詞偏標記學習；最大值損失函數(shù)；凝聚函數(shù)；弱監(jiān)督學習；分類精度

在傳統(tǒng)分類技術中，通常需要通過一個樣本的真實標記信息準確給定的訓練樣本集來訓練分類器，而在很多實際問題中，準確確定樣本的真實標記信息是很困難或者需要付出很大代價的.例如在醫(yī)療診斷中，醫(yī)生通過一個病人的癥狀(如關節(jié)疼、發(fā)燒、血沉高)，往往可以判斷他得了哪幾種疾病(可能是風濕性關節(jié)炎或布氏桿菌病)，而很難確定具體是哪種疾病，在利用傳統(tǒng)分類技術構造疾病診斷的預測算法時，這類數(shù)據(jù)需要被排除在外，而其實這類數(shù)據(jù)對于縮小疾病的可能范圍往往是非常重要的；再如，在利用眾籌的方式標注訓練數(shù)據(jù)時，由于標注人員個人素質(zhì)的差異，標注的結果往往會不一致，在傳統(tǒng)的分類算法中，這種不一致的數(shù)據(jù)往往會被舍棄，其實，雖然標注結果不一致，但是也已經(jīng)縮小了類別的可能范圍，所以這類數(shù)據(jù)也是有用的.偏標記集學習(partial label learning[1-3]，也稱learning from candidate labeling sets[4]ambiguous label learning[5]，superset label learning[6])，就是研究這類數(shù)據(jù)(即不能準確確定訓練樣本的真實標記而只知道它屬于類別標記集合的某一子集)的分類問題的一種新機器學習框架.由于偏標記學習是對傳統(tǒng)分類技術的一個擴展，放松了構造訓練集的條件，因此它與傳統(tǒng)分類技術一樣具有廣闊的應用空間，可以解決圖像處理[7]、文本挖掘[8]、醫(yī)療診斷[9]等領域的各種實際問題.

1模型建立

(1)

p(Yi|xi,W)=

(2)

可以看出，以上2個似然函數(shù)都假設樣本xi的候選標記集Yi中的每個標記都對似然函數(shù)p(Yi|xi,W)具有一樣的貢獻，這將導致最大化p(Yi|xi,W)時，與Yi中的各個元素對應的潛變量同時取得最大值，因此這2個似然函數(shù)本質(zhì)是假定了Yi的所有元素都是xi的真實標記，這與偏標記學習框架描述的“樣本的候選標記中有且只有一個標記是樣本的真實標記”的概念是不一致的.本文將定義一種新的似然函數(shù)：

(3)

該似然函數(shù)本質(zhì)上把是真實標記的概率最大的候選標記作為樣本的真實標記.由于概率模型中似然函數(shù)與參數(shù)模型中的損失函數(shù)本質(zhì)上是一樣的，而文獻[2]的理論分析表明，最大值損失較均值損失更符合偏標記學習的實際情況，因此由式(3)定義的似然函數(shù)也要優(yōu)于由式(1)(2)定義的似然函數(shù).

(4)

凝聚函數(shù)(aggregate function)

(5)

(6)

因此，對于有限正整數(shù)m，當l→+∞時，Gl(x)能單調(diào)一致地逼近G(x).根據(jù)式(6)描述的關系，我們可以得到2個關系式：

(7)

(8)

(9)

顯然，新目標函數(shù)Z(W)不僅可以一致地逼近式(4)，而且還是一個光滑函數(shù).

(10)

(11)

(12)

(13)

(14)

2模型求解

由于目標函數(shù)Z(W)是一個凹函數(shù)，因此很多常用的優(yōu)化方法都可以用來求其最大值點.本文將建立2種模型求解方法，對于樣本規(guī)模比較小的問題采用阻尼牛頓法來求解，對于樣本規(guī)模比較大的問題將利用隨機擬牛頓法來建立一種快速求解方法.

2.1阻尼牛頓法

阻尼牛頓法的迭代公式如下：

(15)

2.2隨機擬牛頓法

為了處理大數(shù)據(jù)問題，本文擬采用文獻[17]提出的隨機擬牛頓法來建立一種快速模型求解方法.為了便于描述，我們將式(9)(10)描述的最大值問題變換為最小值問題來求解：

(16)

(17)

(18)

(19)

(20)

其中,S，SH為隨機選取的訓練數(shù)據(jù)集D的子集.

隨機擬牛頓法[17]的迭代為

(21)

其中,αk為步長，αk的選取會對算法的收斂速度有一定的影響，本文采用與文獻[17]一樣的定義方式，即αk=βk(β為事先給定的常數(shù))；Ht為海森矩陣的近似矩陣，通過與有限儲存擬牛頓方法(limited-memory Broyden-Fletcher-Goldfarb-Shanno Broyden, L-BFGS)[18]中一樣的方法來求得.算法1、算法2給出了隨機擬牛頓法的算法流程圖，關于該方法的詳細描述見文獻[17].

算法1. 隨機擬牛頓法的算法流程.

輸出: W.

② fork=1,2,…,K-1

⑤ ifk≤2L

⑦ else

⑧ 根據(jù)算法2計算Ht；

⑩ end if

算法2. 海森矩陣Ht的計算流程.

輸出: Ht.

② forj=t-min{t,M}+1,…,t

③ 計算ρj=1；

⑤ end for；

⑥ Ht=H.

3仿真實驗

本文的主要創(chuàng)新在于使用了最大值似然函數(shù)和建立了面向大數(shù)據(jù)問題的快速偏標記學習算法，因此，下面將分別從這2個方面驗證所建算法的性能.為了便于區(qū)分，在下面的仿真實驗中我們用PLLOG-Max表示本文建立的基于最大值似然函數(shù)的偏標記學習算法，PLLOG-Max-DN表示基于阻尼牛頓法求解的算法，PLLOG-Max-SQN表示基于隨機擬牛頓法求解的算法.

3.1驗證最大值似然函數(shù)對算法性能的影響

為了驗證最大值似然函數(shù)對算法性能的影響，我們先將PLLOG-Max-DN算法與CLPL算法[2]以及使用由式(1)(2)定義的2種均值似然函數(shù)所建立的算法(分別簡記為PLLOG-Naive，PLLOG-Average算法)進行了比較.對于PLLOG-Average算法，也是采用阻尼牛頓法對模型進行求解的；對于PLLOG-Naive算法，由于目標函數(shù)不是一個凸(或凹)函數(shù)，因此采用文獻[19]提出的CCCP算法對其進行求解，這2個算法的其他推導過程都是與PLLOG-Max-DN算法一樣的.PLLOG-Max-DN，PLLOG-Naive，PLLOG-Average算法都只有一個需要給定的模型參數(shù)，即正則化項的系數(shù)ρ，在本節(jié)的仿真實驗中，ρ是通過在訓練集上利用3折交叉驗證法選取得到的，CLPL算法的所有參數(shù)都是按照文獻[2]的建議設置的.我們在5個UCI數(shù)據(jù)集[20]和2個真實偏標記學習數(shù)據(jù)集[3]上對這4個算法進行了比較，這7個數(shù)據(jù)集的詳細信息如表1所示：

Table 1　The Data Sets for Validating the Performance of Max-likelihood Based Algorithm

由于UCI數(shù)據(jù)集是標準的傳統(tǒng)分類數(shù)據(jù)集，我們采用了2個控制參數(shù)p，r來把它們變換為了偏標記數(shù)據(jù)集，其中p表示偏標記樣本(即|Yi|>1)在整個樣本集中的比例，r表示偏標記樣本的除真實標記以外的候選標記個數(shù)，即r=|Yi|-1.變換過程如下：對于給定的每一對參數(shù)(p,r)，先從原始的UCI數(shù)據(jù)集中隨機選取pn個樣本(n為樣本總數(shù))，然后對于每一個被選取的樣本，隨機地從它的真實標記以外的類別標記中選取r個與真實標記一起構成該樣本的候選標記.表2給出了4個算法在由不同的控制參數(shù)(p,r)生成的數(shù)據(jù)集上的預測精度，每個數(shù)據(jù)集上的結果都是5次10折交叉驗證的平均結果.表2中黑體顯示的是PLLOG-Max-DN，PLLOG-Naive，PLLOG-Average三個算法中最好的結果，下劃線表示的是PLLOG-Max-DN算法和CLPL算法之間相比最好的結果.可以看出，就PLLOG-Max-DN，PLLOG-Naive，PLLOG-Average三個算法相比，PLLOG-Max-DN算法在生成的45個控制數(shù)據(jù)集中的33個上取得了最好的結果，PLLOG-Naive算法在10個數(shù)據(jù)集上取得了最好結果，而PLLOG-Average算法只在2個數(shù)據(jù)集上取得了最好結果，而且對于那些沒有取得最好結果的數(shù)據(jù)集，PLLOG-Max-DN算法的結果也基本與最好結果相差很少，這就表明最大值似然函數(shù)要優(yōu)于其他2種均值似然函數(shù)；而PLLOG-Max-DN和CLPL算法相比，PLLOG-Max-DN算法在45個控制數(shù)據(jù)集中的29個上取得了最好的結果，CLPL算法在16個上取得了最好結果，而且其中在6個上是以微弱的優(yōu)勢勝出，因此PLLOG-Max-DN算法要優(yōu)于CLPL算法.

Table 2　The Accuracy of Each Algorithm on the UCI Data Sets

表3給出了4個算法在2個真實數(shù)據(jù)集上的預測精度，遺憾的是PLLOG-Max-DN算法只在一個數(shù)據(jù)集上取得了最好的結果，主要原因是BirdSong數(shù)據(jù)集是從一個多標記學習問題中采集的，可能BirdSong數(shù)據(jù)集中的一部分樣本的候選標記本身都是樣本的真實標記，從而影響了算法的性能.

Table 3　　　The Accuracy of Each Algorithm on the Real-world

3.2驗證快速模型求解算法的性能

本節(jié)將在5個規(guī)模比較大的UCI數(shù)據(jù)集上對本文建立的快速偏標記學習算法PLLOG-Max-SQN的性能進行評估，這些UCI數(shù)據(jù)集的詳細信息如表4所示.

Table 4　　　The UCI Data Sets for Validating the Performance

表5給出了PLLOG-Max-SQN算法按照以上的參數(shù)設定方法在各個UCI數(shù)據(jù)集上的平均預測精度和計算時間，由于目前還沒有其他的快速偏標記學習算法，因此只將PLLOG-Max-SQN算法與我們建立的PLLOG-Max-DN算法進行了比較，這2個算法的結束條件是PLLOG-Max-SQN的迭代次數(shù)是2n3(n訓練樣本個數(shù))，PLLOG-Max-DN的迭代次數(shù)是100次，所有結果都是在CPU主頻為2.5 GHz、內(nèi)存為8 GB的筆記本電腦上運行得到的.

從表5可以看出，2個算法的預測精度基本都相當，但是計算時間上PLLOG-Max-SQN算法要遠遠快于PLLOG-Max-DN算法.為了進一步明確2個算法的預測精度之間究竟有無明顯差距，我們利用5%顯著性水平的t檢驗方法對2個算法在各個數(shù)據(jù)集上的結果進行了分析，結果表明除在2個控制數(shù)據(jù)集Shuttle(p=0.6,r=1)，Connect4(p=0.6,r=1)上PLLOG-Max-DN算法比PLLOG-Max-SQN算法的精度略高以外，在其他的16個控制數(shù)據(jù)集上，這2個算法的結果在統(tǒng)計意義上是一樣的.

Fig. 1　　　The performance of PLLOG-Max-SQN algorithm on Letter data set when varying the value of 　　　each parameter.圖1　每個參數(shù)取不同值時PLLOG-Max-SQN算法在Letter數(shù)據(jù)集上的性能

DataSetsAlgorithmClassificationAccuracy∕%(RunningTime∕min)r=1r=3p=0.3p=0.6p=0.3p=0.6LetterPLLOG-Max-SQN75.12(0.22)75.08(0.20)75.20(0.22)75.30(0.21)PLLOG-Max-DN74.84(4.14)75.35(4.20)74.91(4.13)75.59(4.35)ShuttlePLLOG-Max-SQN92.34(0.22)92.06(0.22)92.30(0.22)92.18(0.22)PLLOG-Max-DN92.54(1.17)92.48(1.44)92.51(1.12)92.37(1.44)Connect4PLLOG-Max-SQN64.49(0.23)64.03(0.23)PLLOG-Max-DN64.99(0.78)63.85(0.86)CovtypePLLOG-Max-SQN59.81(1.77)60.16(1.72)59.99(1.72)59.37(1.73)PLLOG-Max-DN60.17(32.64)60.14(34.48)60.18(32.79)59.65(37.29)Poker-handPLLOG-Max-SQN50.11(4.84)50.21(4.81)50.08(4.78)50.12(4.72)PLLOG-Max-DN50.11(31.42)50.21(32.05)50.08(31.58)50.12(31.74)

4結束語

損失函數(shù)的設計體現(xiàn)了算法關于學習框架本質(zhì)的刻畫，是影響算法泛化性能的關鍵因素之一.最大值損失函數(shù)可以較均值損失函數(shù)更好地描述偏標記學習框架下的樣本與標記之間的關系，但是由于最大值損失函數(shù)是一個非光滑函數(shù)，導致建立模型的目標函數(shù)通常也是一個難于求解的非光滑函數(shù)，針對這個問題，本文通過引入凝聚函數(shù)，將基于最大值損失函數(shù)的偏標記學習模型的目標函數(shù)轉換成了一種易于求解的光滑凹函數(shù).此外，針對已有算法不能處理大數(shù)據(jù)的問題，本文通過引入隨機擬牛頓法對模型進行求解，建立一種快速偏標記學習算法，可以有效處理大數(shù)據(jù).考慮到本文建立的算法是一種線性算法，有時不能很好地處理非線性問題，下一步我們將嘗試以支持向量機或者高斯過程模型為建模工具，建立一種基于核方法的快速偏標記學習算法.

參考文獻

[1]Zhang Minling. Research on partial label learning[J]. Journal of Data Acquisition & Processing, 2015, 30(1): 77-87 (in Chinese)(張敏靈. 偏標記學習研究綜述[J]. 數(shù)據(jù)采集與處理, 2015, 30(1): 77-87)

[2]Cour T, Sapp B, Taskar B. Learning from partial labels[J]. Journal of Machine Learning Research, 2011, 12: 1501-1536

[3]Zhang Minling. Disambiguation-free partial label learning[C]Proc of the 14th SIAM Int Conf on Data Mining. Philadelphia, PA: SIAM, 2014: 37-45

[4]Luo J, Orabona F. Learning from candidate labeling sets[C]Advances in Neural Information Processing Systems. Montreal: Neural Information Processing System Foundation, 2010: 1504-1512

[5]Hüllermeier E, Beringer J. Learning from ambiguously labeled examples[J]. Intelligent Data Analysis, 2006, 10(5): 419-439

[6]Liu L, Dietterich T. A conditional multinomial mixture model for superset label learning[C]Advances in Neural Information Processing Systems. Montreal: Neural Information Processing System Foundation, 2012: 557-565

[7]Zeng Z, Xiao S, Jia K, et al. Learning by associating ambiguously labeled images[C]Proc of the 26th IEEE Int Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2013: 708-715

[8]Grandvalet Y, Bengio Y. Learning from partial labels with minimum entropy, 2004s-28[R]. Montreal: Center for Interuniversity Research and Analysis of Organizations, 2004

[9]Fung G, Dundar M, Krishnapuram B, et al. Multiple instance learning for computer aided diagnosis[C]Advances in Neural Information Processing Systems. Cambridge, MA: MIT Press, 2007: 425-432

[10]Grandvalet Y. Logistic regression for partial labels[C]Proc of the 9th Int Conf on Information Processing and Management of Uncertainty in Knowledge-Based Systems. Annecy, Haute-Savoie: Institute for the Physics and Mathematics of the Universe (IPMU), 2002: 1935-1941

[11]Jin R, Ghahramani Z. Learning with multiple labels[C]Advances in Neural Information Processing Systems. Montreal: Neural Information Processing System Foundation, 2002: 897-904

[13]Nguyen N, Caruana R. Classification with partial labels[C]Proc of the 14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: Association for Computing Machinery, 2008: 381-389

[14]Li C, Zhang J, Chen Z. Structured output learning with candidate labels for local parts[C]Proc of the European Conf on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECMLPKDD 2013). Berlin: Springer, 2013

[15]Li X. An aggregate function method for nonlinear programming[J]. Science in China Series A-Mathematics, 1991, 34(12): 1467-1473

[16]Horn R, Johnson C. Topics in Matrix Analysis[M]. Cambridge, UK: Cambridge University Press, 1991: 239-297

[17]Byrd R, Hansen S, Nocedal J, et al. A stochastic quasi-Newton method for large-scale optimization[OL]. [2015-02-18]. http:arxiv.orgpdf1401.7020v2.pdf

[18]Nocedal J, Wright S. Numerical Optimization[M]. 2nd ed. Berlin: Springer, 1999: 195-204

[19]Yuille A, Rangarajan A. The concave-convex procedure[J]. Neural Computation, 2003, 15(4): 915- 936

[20]Bache K, Lichman M. UCI machine learning repository[OL]. 2013 [2015-03-10]. http:archive.ics.uci.eduml

Zhou Yu, born in 1982. PhD candidate. Her research interests include machine learning and data mining.

He Jianjun, born in 1983. PhD and lecturer. His research interests include machine learning and pattern recognition.

Gu Hong, born in 1961. Professor and PhD supervisor. His research interests include machine learning, big data and bioinformatics.

Zhang Junxing, born in 1969. PhD and professor. His research interests include data mining and speech signal processing.

A Fast Partial Label Learning Algorithm Based on Max-loss Function

Zhou Yu1, He Jianjun1,2, Gu Hong1, and Zhang Junxing2

1(FacultyofElectronicInformationandElectricalEngineering,DalianUniversityofTechnology,Dalian,Liaoning116024)2(CollegeofInformationandCommunicationEngineering,DalianNationalitiesUniversity,Dalian,Liaoning116600)

AbstractIn the age of big data, learning with weak supervision has become one of the hot research topics in machine learning field. Partial label learning, which deals with the problem where each training example is associated with a set of candidate labels among which only one label corresponds to the ground-truth, is an important weakly-supervised machine learning frameworks proposed recently and can be widely used in many real world tasks. The max-loss function may be used to accurately capture the relationship between the partial labeled sample and its labels. However, since the max-loss function usually brings us a nondifferentiable objective function difficult to be solved, it is rarely adopted in the existing algorithms. Moreover, the existing partial label learning algorithms can only deal with the problem with small-scale data, and rarely can be used to deal with big data. To cure above two problems, this paper presents a fast partial label learning algorithm with the max-loss function. The basic idea is to transform the nondifferentiable objective to a differentiable concave function by introducing the aggregate function to approximate the max(·) function involved in the max-lass function, and then to solve the obtained concave objective function by using a stochastic quasi-Newton method. The experimental results show that the proposed algorithm can not only achieve higher accuracy but also use shorter computing time than the state-of-the-art algorithms with average-loss functions. Moreover, the proposed algorithm can deal with the problems with millions samples within several minutes.

Key wordspartial label learning; max-loss function; aggregate function; weakly-supervised learning; classification accuracy

收稿日期：2015-03-26；修回日期：2015-07-13

基金項目：國家自然科學基金項目(61503058,61374170,61502074,U1560102)；高等學校博士學科點專項科研基金項目(20120041110008)；中央高校基本科研業(yè)務費專項資金項目(DC201501055,DC201501060201)

通信作者：顧宏(guhong@dlut.edu.cn)

中圖法分類號TP391

This work was supported by the National Natural Science Foundation of China (61503058,61374170,61502074,U1560102), the Research Fund for the Doctoral Program of Higher Education of China (20120041110008), and the Fundamental Research Funds for the Central Universities (DC201501055,DC201501060201).