一種改進(jìn)的基于社團(tuán)發(fā)現(xiàn)的貝葉斯眾包模型＊

吳昌錢， 洪 欣

（1.泉州信息工程學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，福建 泉州362000；2.華僑大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，福建 泉州362000）

眾包是基于人工計(jì)算的智能計(jì)算的重要研究內(nèi)容，目前已有的眾包平臺包括Turk，Crouw－Flower和Clickworker等.這些眾包平臺通過人工方式對圖片或者文檔等內(nèi)容進(jìn)行標(biāo)記，然后利用標(biāo)記的數(shù)據(jù)對機(jī)器學(xué)習(xí)的算法進(jìn)行訓(xùn)練，從而進(jìn)行圖片或者文檔的分類或者排名［1］.對群體標(biāo)簽進(jìn)行聚集的最簡單的方法是采用多數(shù)投票等啟發(fā)式方法，然而啟發(fā)式方法沒有對每個工人標(biāo)記數(shù)據(jù)的可靠性進(jìn)行差別對待.為了解決上述問題，研究人員在對群體標(biāo)簽進(jìn)行聚集時考慮了每個工人的可靠性不同，提出了相應(yīng)的概率模型.概率模型可以對每個工人的準(zhǔn)確性進(jìn)行建模，但是仍然忽略了工人的評價偏好或者傾向.對于每一個工人，對應(yīng)著一個融合矩陣，該融合矩陣中的每一行表達(dá)了用戶將某個真實(shí)標(biāo)簽標(biāo)記為不同標(biāo)簽的概率.在眾包中，工人的評價傾向可以通過融合矩陣得到，將融合矩陣融入到標(biāo)簽聚集過程的模型有［2］，這些模型與啟發(fā)式模型相比具有更高的準(zhǔn)確性.基于融合矩陣的眾包模型將每個工人的融合矩陣視為潛在變量，用融合矩陣作為用戶的畫像.

在基于融合矩陣的眾包模型中，由于標(biāo)簽數(shù)量眾多，使得融合矩陣非常大.同時，工人的標(biāo)記往往服從冪率分布［3］，即僅僅以小部分工人標(biāo)記了大量數(shù)據(jù)，而大量的工人往往只標(biāo)記了少量數(shù)據(jù)，這使得融合矩陣的數(shù)據(jù)是稀疏的.此外，眾多的工人使得大量的融合矩陣計(jì)算耗時耗力.在基于融合矩陣的眾包模型中，BCC（Bayesian Classification Combination）模型［2］是目前性能最好的模型，但是仍面臨上述問題.

1 貝葉斯眾包模型

在眾包模型中，假設(shè)K個工人將N個對象劃分為S個可能的類別.令ti為對象i的真實(shí)類別，用c，j≤S）表示工人k將真實(shí)類別為c的對象標(biāo)記為j的概率，表示工人k對對象i進(jìn)行的標(biāo)記，C為所有觀測到的標(biāo)簽集合.BCC模型［2］的因子圖如圖1所示，下面具體闡述該模型的含義.

BCC模型假設(shè)對象i的真實(shí)類別ti通過參數(shù)為p的分類分布中產(chǎn)生，即

其中p為所有對象中每個類別的比例向量，Cat（·）為分類分布.工人k對對象i進(jìn)行的標(biāo)記是通過參數(shù)為的分類分布產(chǎn)生的，即

假設(shè)參數(shù)p和π符合共軛Dirichlet先驗(yàn)分布p～Dir（p｜α）和，那么公式（4）可轉(zhuǎn)化為如下公式：

2 基于社團(tuán)的貝葉斯眾包模型

2.1 模型的描述

本文通過引入工人社團(tuán)對BCC模型［2］進(jìn)行了擴(kuò)展，基于社團(tuán)的貝葉斯眾包模型的因子圖如圖2所示.

本文將K個工人劃分為M 個社團(tuán)，每個社團(tuán)m包含一個潛在的融合矩陣π（m）.用m（k）表示工人k所屬的社團(tuán)，那么m（k）通過參數(shù)為h的分類分布中產(chǎn)生，即

其中h為所有工人中每個社團(tuán)的工人數(shù)量比例.對于社團(tuán)m，其融合矩陣π（m）的第c行的對數(shù)概率向量為.對于所有的類別c，對應(yīng)用sofamax操作符進(jìn)行標(biāo)準(zhǔn)化得到相應(yīng)的指數(shù)表達(dá)式，那么和滿足如下關(guān)系：

該模型與BCC模型的區(qū)別在于：BCC模型中，每個用戶有一個融合矩陣，且不同用戶的融合矩陣是相互獨(dú)立的，而本文的社團(tuán)模型強(qiáng)制每個社團(tuán)中的用戶的融合矩陣是相同的.當(dāng)指定類別c時，用戶k的評價向量s（k）c與k所屬社團(tuán)m（k）的評價值向量相關(guān)，其關(guān)系為多元高斯分布：

其中超參數(shù)ν為社團(tuán)融合矩陣的等方逆方差.根據(jù)公式（8），可以從s（k）c推導(dǎo)出相應(yīng)的標(biāo)準(zhǔn)化指數(shù)表達(dá)π（k）c，即

2.2 模型的推導(dǎo)

下面描述如何應(yīng)用基于社團(tuán)的貝葉斯模型進(jìn)行眾包模型的推導(dǎo).假設(shè)所有工人對于所有對象的標(biāo)簽集合C是已知的，眾包模型的目的是推導(dǎo)出模型中參數(shù)θ＝ ｛s（m），π（m），s（k），π（k），t，p｝的后驗(yàn)分布.為了實(shí)現(xiàn)上述目的，本文在給定C的條件下，應(yīng)用貝葉斯規(guī)則計(jì)算參數(shù)θ的聯(lián)合后驗(yàn)分布：

在（11）中，參數(shù)h的先驗(yàn)分布為參數(shù)為α的Dirichlet分布，的先驗(yàn)分布為均值為μ逆方差為θ的多元高斯分布.如果假設(shè)C中的標(biāo)簽是獨(dú)立產(chǎn)生的，那么公式（5）所示的參數(shù)的聯(lián)合后驗(yàn)分布模型可改寫為：

為了計(jì)算每個參數(shù)的近似間隔分布，本文應(yīng)用［3］提出的消息傳遞算法.為了發(fā)現(xiàn)工人中的最優(yōu)社團(tuán)個數(shù)，本文應(yīng)用最大間隔似然模型選擇標(biāo)準(zhǔn)，該方法的描述公式如下：

對于（13）所示的最大間隔似然優(yōu)化，可以在包含M個值的離散集合上采用簡單的線搜索方法進(jìn)行.

3 實(shí)驗(yàn)結(jié)果與分析

3.1 數(shù)據(jù)集與評價指標(biāo)

本文采用兩個公開的眾包數(shù)據(jù)集CF①https：／／sites.google.com／site／crowdscale2013／shared－task.和ARJ［4］.CF數(shù)據(jù)集是CrowdFlower在2013年開放任務(wù)挑戰(zhàn)中的一部分.CF包含1 960個工人對98 980個問題的569 375個情感分析判斷.其中問題通過Tweets的形式提出，工人對問題的判斷反應(yīng)了用戶在討論天氣時的情感，判斷的類別為5類.此外，該數(shù)據(jù)集包含了300個問題以及相應(yīng)的1 720個正確的情感判斷，這些正確的判斷涉及461個用戶.在ARJ數(shù)據(jù)集中，工人通過人工方式判斷給定的查詢／應(yīng)答集合中是否涉及成人信息，判斷結(jié)果為2分類.ARJ數(shù)據(jù)集包含了148個工人對307個問題的24 704個判斷.

本實(shí)驗(yàn)通過準(zhǔn)確性和NLPD兩個指標(biāo)對算法的性能進(jìn)行評估.準(zhǔn)確性為結(jié)果中正確結(jié)果的數(shù)量與所有正確結(jié)果的比例.NLPD（Negative Log Probability Density）考慮了預(yù)測標(biāo)簽的分布的不確定性，令qi＝ ｛qi，1，…，qi，j｝為對象i的預(yù)測類別分布，那么 NLPD的計(jì)算公式如下：

3.2 對比算法

將本文提出的基于社團(tuán)的貝葉斯眾包模型記為CBCC，與如下算法進(jìn)行實(shí)驗(yàn)對比：

（1）BCC（Bayesian Classifier Combination）［2］：BCC算法的具體描述見第2小節(jié).

（2）EM（Expectation Maximization）［5］：EM 算法認(rèn)為對象的標(biāo)簽與工人的融合矩陣是一個聯(lián)合分布，通過期望最大化算法對預(yù)測值進(jìn)行估計(jì).

（3）MV（Majority Voting）［6］：MV方法是在群體中達(dá)成一致的一種啟發(fā)式方法，認(rèn)為每個對象的標(biāo)簽為所有工人的投票的加權(quán)和的最大值.MV方法的假設(shè)是所有的工人都是可靠的.

3.3 實(shí)驗(yàn)與結(jié)果分析

首先，實(shí)驗(yàn)通過CF和ARJ兩個數(shù)據(jù)集對比了4種算法的準(zhǔn)確性，實(shí)驗(yàn)結(jié)果分別如圖3和4所示.圖中的橫軸為預(yù)測結(jié)果中返回的標(biāo)記個數(shù)，縱軸為算法的準(zhǔn)確性.在CF數(shù)據(jù)集中，當(dāng)標(biāo)記數(shù)量小于100時，BCC算法的準(zhǔn)確性最低，EM和MV算法的準(zhǔn)確性相近并且優(yōu)于BCC算法，本文提出的CBCC算法的準(zhǔn)確性是最高的；當(dāng)標(biāo)記數(shù)量大于100時，BCC算法的準(zhǔn)確性優(yōu)于EM和MV算法，但是仍低于CBCC算法.然后，實(shí)驗(yàn)分析了CBCC算法在返回的結(jié)果個數(shù)為900個的情況下的結(jié)果分布.從圖5中可以看出，CBCC算法在CF算法下的準(zhǔn)確率為99%，在ARJ算法下的準(zhǔn)確率為98%.此外，在這兩個數(shù)據(jù)集中，預(yù)測結(jié)果集中分布在對角線上，這表明大多數(shù)的預(yù)測是準(zhǔn)確的，而錯誤預(yù)測的分布是比較均勻的.

最后，實(shí)驗(yàn)對比了4種算法在兩個數(shù)據(jù)集下的準(zhǔn)確性和NLPD，實(shí)驗(yàn)結(jié)果如表1所示.在準(zhǔn)確性對比中，CBCC算法在兩個數(shù)據(jù)集下的準(zhǔn)確性都是最好的，而BCC算法次之.在NLPD的對比中，CBCC算法的值都是最小的，BCC算法次之.這表明CBCC算法的性能是最優(yōu)的.

4 結(jié)束語

本文將所有的工人按照相似性劃分為若干社團(tuán)，每個社團(tuán)中的所有工人采用相同的融合矩陣.在眾包模型參數(shù)的計(jì)算中，采用貝葉斯后驗(yàn)分布方法進(jìn)行推導(dǎo)，應(yīng)用消息傳遞算法計(jì)算每個參數(shù)的近似間隔分布，并且應(yīng)用最大間隔似然模型選擇工人集合中的最優(yōu)社團(tuán)數(shù)量.實(shí)驗(yàn)表明，本文提出的基于社團(tuán)的貝葉斯眾包模型與其他相關(guān)研究相比在降低了算法的復(fù)雜度同時也提高了算法的準(zhǔn)確性.

表1 算法在不同數(shù)據(jù)集下的性能對比Tab.1 performance comparison of different data sets

［1］丁宇，車萬翔，劉挺，等.基于眾包的詞匯聯(lián)想網(wǎng)絡(luò)的獲取和分析［J］.中文信息學(xué)報，2013，27（3）：100－106.

［2］KIM H C，GHAHRAMANI Z.Bayesian classifier combination［C］／／International Conference on Artificial Intelligence and Statistics，2012：619－627.

［3］WELINDER P，BRANSON S，PERONA P，et al.The multidimensional wisdom of crowds［C］／／Advances in Neural Information Processing Systems，2010：2 424－2 432.

［4］KRISTAN J，SUFFOLETTO B.Using online crowdsourcing to understand young adult attitudes toward expert－authored messages aimed at reducing hazardous alcohol consumption and to collect peer－authored messages［J］.Translational Behavioral Medicine，2013，11（2）：1－8.

［5］GAO X A，BACHRACH Y，KEY P，et al.Quality expectation－variance tradeoffs in crowdsourcing contests［C］.AAAI，2012：38－44.

［6］TRAN－THANH L，VENANZI M，ROGERS A，et al.Efficient budget allocation with accuracy guarantees for crowdsourcing classification tasks［C］／／Proceedings of the 2013International Conference on Autonomous Agents and Multi－Agent Systems，2013：901－908.

［7］周俊梅，蔣文江.基于單方程計(jì)量經(jīng)濟(jì)模型的貝葉斯分析［J］.湘潭大學(xué)自然科學(xué)學(xué)版，2013，35（2）：119－122.