基于多示例多標(biāo)記學(xué)習(xí)的手機(jī)游戲道具推薦*

唐　俊，周志華＋1.南京大學(xué)計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，南京2100232.軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心，南京210023

* The National Natural Science Foundation of China under Grant No. 61333014（國(guó)家自然科學(xué)基金）.

Received 2015-05，Accepted 2015-08.

CNKI網(wǎng)絡(luò)優(yōu)先出版：2015-08-13，http://www.cnki.net/kcms/detail/11.5602.TP.20150813.1552.004.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10（01）-0103-09

?

基于多示例多標(biāo)記學(xué)習(xí)的手機(jī)游戲道具推薦*

唐俊1，2，周志華1，2＋
1.南京大學(xué)計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，南京210023
2.軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心，南京210023

* The National Natural Science Foundation of China under Grant No. 61333014（國(guó)家自然科學(xué)基金）.

Received 2015-05，Accepted 2015-08.

CNKI網(wǎng)絡(luò)優(yōu)先出版：2015-08-13，http://www.cnki.net/kcms/detail/11.5602.TP.20150813.1552.004.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10（01）-0103-09

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel:＋86-10-89056056

摘要：手機(jī)游戲提供商通過(guò)在游戲中銷售虛擬道具來(lái)獲得收益。將游戲玩家日志數(shù)據(jù)中每個(gè)事件描述為一個(gè)示例，玩家對(duì)多種游戲道具的購(gòu)買狀態(tài)表示為多個(gè)標(biāo)記，從而將游戲道具推薦問(wèn)題抽象為多示例多標(biāo)記學(xué)習(xí)問(wèn)題。在此基礎(chǔ)上，將快速多示例多標(biāo)記學(xué)習(xí)算法用于手機(jī)網(wǎng)絡(luò)游戲道具推薦，并利用半監(jiān)督學(xué)習(xí)提升推薦性能。離線數(shù)據(jù)集以及實(shí)際在線手機(jī)網(wǎng)絡(luò)游戲?qū)嶒?yàn)結(jié)果表明，基于多示例多標(biāo)記學(xué)習(xí)的游戲道具推薦技術(shù)帶來(lái)了游戲營(yíng)收的顯著增長(zhǎng)。

關(guān)鍵詞：機(jī)器學(xué)習(xí)；多示例多標(biāo)記學(xué)習(xí)（MIML）；半監(jiān)督學(xué)習(xí)；推薦

1　引言

網(wǎng)絡(luò)游戲是隨著電子計(jì)算機(jī)和互聯(lián)網(wǎng)的發(fā)展與普及而進(jìn)入人們?nèi)粘Ｉ钪械囊豁?xiàng)廉價(jià)娛樂活動(dòng)。網(wǎng)絡(luò)游戲玩家通過(guò)輸入輸出設(shè)備在計(jì)算機(jī)模擬出的虛擬世界中與虛擬世界環(huán)境及其他玩家進(jìn)行互動(dòng)來(lái)獲得休閑娛樂體驗(yàn)。玩家在游戲中不但能夠通過(guò)被動(dòng)接受滿足畫面、音樂、劇情等方面的感官需求，還能夠主動(dòng)參與互動(dòng)，在虛擬世界中獲得多種平時(shí)難以獲得的體驗(yàn)。游戲總是以其獨(dú)特的表現(xiàn)形式豐富著人們的內(nèi)心世界，故也被認(rèn)為是第九項(xiàng)藝術(shù)[1]。游戲的藝術(shù)性豐富了玩家的內(nèi)心世界，而游戲的商業(yè)性則為游戲開發(fā)者帶來(lái)收益。網(wǎng)絡(luò)游戲的收費(fèi)模式主要有兩種：點(diǎn)卡收費(fèi)和道具收費(fèi)。點(diǎn)卡收費(fèi)是傳統(tǒng)的收費(fèi)方式，按照玩家登錄游戲的時(shí)長(zhǎng)計(jì)費(fèi)，時(shí)間越長(zhǎng)費(fèi)用越高。而道具收費(fèi)是指玩家免費(fèi)在游戲中進(jìn)行基本娛樂活動(dòng)，只有在需要增值服務(wù)道具時(shí)才進(jìn)行付費(fèi)。道具收費(fèi)模式由于其“免費(fèi)游戲，增值收費(fèi)”的特點(diǎn)受到廣大玩家的歡迎，因此也被絕大多數(shù)網(wǎng)絡(luò)游戲所采用。隨著手機(jī)等移動(dòng)計(jì)算設(shè)備的普及，手機(jī)網(wǎng)絡(luò)游戲也流行起來(lái)。由于移動(dòng)互聯(lián)網(wǎng)隨時(shí)隨地的特性，人們接觸網(wǎng)絡(luò)游戲的門檻大大降低，使得手機(jī)網(wǎng)絡(luò)游戲玩家群體呈業(yè)余化趨勢(shì)。業(yè)余玩家們不再投入大量時(shí)間成為游戲?qū)＜遥虼诵枰玫匾龑?dǎo)他們?nèi)ンw驗(yàn)網(wǎng)絡(luò)游戲世界。手機(jī)網(wǎng)絡(luò)游戲玩家群體的“業(yè)余化”特性是將推薦系統(tǒng)應(yīng)用到游戲道具銷售上的主要原因。

推薦系統(tǒng)是對(duì)于搜索引擎的補(bǔ)充。在這個(gè)信息過(guò)載時(shí)代，當(dāng)信息消費(fèi)者們無(wú)法用準(zhǔn)確的關(guān)鍵字來(lái)描述自己的需求時(shí)，推薦系統(tǒng)可以自動(dòng)為他們提供想要的信息。推薦系統(tǒng)如今已經(jīng)廣泛地應(yīng)用在很多互聯(lián)網(wǎng)產(chǎn)品中，如購(gòu)物網(wǎng)站淘寶、亞馬遜，社交網(wǎng)站Facebook，在線視頻網(wǎng)站Netflix、YouTube、Hulu等。應(yīng)用在這些互聯(lián)網(wǎng)產(chǎn)品中的推薦系統(tǒng)大多采用了基于用戶行為數(shù)據(jù)的協(xié)同過(guò)濾推薦算法。算法利用user-item矩陣中隱含的用戶關(guān)聯(lián)、物品關(guān)聯(lián)以及用戶物品關(guān)聯(lián)這3類信息來(lái)進(jìn)行推薦[2-3]。推薦系統(tǒng)的目標(biāo)一般有兩種：一種是給出用戶對(duì)于物品的具體評(píng)分；另一種則只需對(duì)某個(gè)用戶給出一個(gè)包含n個(gè)物品的推薦列表，即Top-n推薦。對(duì)于第一種推薦目標(biāo)，評(píng)價(jià)準(zhǔn)則一般采用均方根誤差（root mean square error，RMSE），而對(duì)于Top-n推薦，評(píng)價(jià)準(zhǔn)則主要采用準(zhǔn)確率（precision）和召回率（recall）。這兩種目標(biāo)顯然是不一致的，往往在Top-n推薦中采用一些簡(jiǎn)單的算法就能獲得更好的效果，而無(wú)需采用要求給出具體評(píng)分的推薦算法[4]?；谖锲坊蛘呋谟脩舻膮f(xié)同過(guò)濾算法是簡(jiǎn)單而有效的推薦算法[5-6]。而隱語(yǔ)義模型（latent factor model，LFM）類算法在利用user-item矩陣信息時(shí)，自然地假設(shè)存在“隱語(yǔ)義（latent factor）”，將user-item矩陣分解為user-latent矩陣和item-latent矩陣[7-8]。這樣一來(lái)，用戶和物品都可以與某個(gè)隱語(yǔ)義概念建立聯(lián)系，認(rèn)知心理學(xué)中的“典型性”概念可以為該假設(shè)提供一些理論依據(jù)[9]。當(dāng)矩陣數(shù)據(jù)并不稀疏時(shí)，LFM的效果是非常好的。當(dāng)矩陣數(shù)據(jù)比較稀疏時(shí)，將相似度矩陣分解為多個(gè)低秩矩陣的積往往可以獲得很好的Top-n推薦效果[10-11]。

用戶行為數(shù)據(jù)一般以日志形式存在，由一系列事件組成，每條事件記錄一個(gè)用戶行為。在利用用戶行為數(shù)據(jù)進(jìn)行物品推薦時(shí)，事件又可被分為顯性事件與隱性事件。顯性事件記錄了用戶的具體購(gòu)買行為，直接反映用戶對(duì)物品的喜好；而所有非顯性事件都被歸為隱性事件。

手機(jī)網(wǎng)絡(luò)游戲中的玩家行為數(shù)據(jù)與一般互聯(lián)網(wǎng)產(chǎn)品的用戶行為數(shù)據(jù)相比，有以下3個(gè)特點(diǎn)：（1）玩家行為數(shù)據(jù)中包含大量事件上下文。普通互聯(lián)網(wǎng)產(chǎn)品的事件一般僅包括用戶ID、用戶行為ID和時(shí)間戳等內(nèi)容。網(wǎng)絡(luò)游戲的事件不僅包含上述內(nèi)容，還包括事件發(fā)生環(huán)境、前置事件、后續(xù)事件等事件上下文信息。（2）玩家行為數(shù)據(jù)中包含豐富的隱性事件。玩家在游戲虛擬世界中會(huì)留下大量與道具購(gòu)買非直接相關(guān)的隱性事件記錄。（3）玩家行為數(shù)據(jù)中游戲道具數(shù)量有限。一款互聯(lián)網(wǎng)產(chǎn)品中物品數(shù)量成千上萬(wàn)，而一款網(wǎng)絡(luò)游戲中的虛擬道具數(shù)量一般為幾十或幾百。

由于傳統(tǒng)的協(xié)同過(guò)濾算法主要利用user-item矩陣進(jìn)行推薦，將其應(yīng)用在手機(jī)網(wǎng)絡(luò)游戲道具推薦系統(tǒng)中會(huì)遇到以下兩個(gè)問(wèn)題：（1）user-item矩陣中沒有事件上下文。一般為了能在推薦系統(tǒng)中利用事件上下文信息，只能通過(guò)人工添加相關(guān)的固定規(guī)則給推薦系統(tǒng)施加影響[5]。（2）user-item矩陣中不包含隱性事件信息。玩家只能通過(guò)顯性事件信息來(lái)描述，而大量隱性事件信息無(wú)法得到利用。

多示例多標(biāo)記學(xué)習(xí)（multi-instance multi-label learning，MIML）[12]是近年來(lái)提出的一種新型機(jī)器學(xué)習(xí)框架。在該框架中，一個(gè)對(duì)象用多個(gè)示例描述，對(duì)象可以同時(shí)擁有多個(gè)類別標(biāo)記，如圖1所示[13]。該框架對(duì)處理具有多義性的數(shù)據(jù)對(duì)象尤為適用，例如在圖像標(biāo)注任務(wù)中，圖像的不同區(qū)域可以表示為不同的示例（即一個(gè)特征向量），一幅圖像可以同時(shí)劃歸多個(gè)類別；在文本分類任務(wù)中，不同的章節(jié)、段落可以表示為不同的示例，一個(gè)文檔可以同時(shí)屬于多個(gè)類別。MIML已被成功應(yīng)用于圖像文本分類[13-14]、基因圖像標(biāo)注[15]、視頻標(biāo)注[16]、生態(tài)保護(hù)[17]等任務(wù)中。本文將游戲玩家日志數(shù)據(jù)中每個(gè)事件作為一個(gè)示例，玩家對(duì)于游戲道具的購(gòu)買狀態(tài)作為標(biāo)記，從而用多示例多標(biāo)記學(xué)習(xí)框架來(lái)描述手機(jī)網(wǎng)絡(luò)游戲道具推薦問(wèn)題。在此基礎(chǔ)上，本文通過(guò)快速多示例多標(biāo)記學(xué)習(xí)算法進(jìn)行道具推薦，并加入半監(jiān)督學(xué)習(xí)以獲得更好的推薦性能。該算法不僅在離線數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，還在實(shí)際手機(jī)網(wǎng)絡(luò)游戲中進(jìn)行在線實(shí)驗(yàn)。兩部分實(shí)驗(yàn)結(jié)果都表明基于多示例多標(biāo)記學(xué)習(xí)的游戲道具推薦技術(shù)給游戲營(yíng)收帶來(lái)了顯著增長(zhǎng)。

Fig.1 Multi-instance multi-label learning圖1　多示例多標(biāo)記學(xué)習(xí)

本文組織結(jié)構(gòu)如下：第2章介紹手機(jī)游戲道具推薦任務(wù)，并將其抽象為MIML問(wèn)題；第3章提出co-MIMLfast算法；第4章給出基準(zhǔn)數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果；第5章給出手機(jī)在線游戲?qū)嶒?yàn)結(jié)果；第6章是結(jié)束語(yǔ)。

2　任務(wù)描述

圖2展示了游戲日志數(shù)據(jù)的產(chǎn)生過(guò)程。當(dāng)ID為111的玩家在沙漠地圖坐標(biāo)為（12，14）的地點(diǎn)進(jìn)行了一次攻擊動(dòng)作時(shí)，一條記錄該事件的數(shù)據(jù)便被存入游戲日志中。

Fig.2 Generation of game log data圖2　游戲日志數(shù)據(jù)的產(chǎn)生

顯然該事件是一個(gè)隱性事件。該隱性事件僅僅描述了玩家進(jìn)行的一次攻擊動(dòng)作，但它仍然可能隱藏了玩家對(duì)于某件游戲道具的偏好信息。例如，該游戲中有一件名為“諸葛神弩”的武器道具，只要購(gòu)買了該道具，玩家就可以極大提高自己角色的戰(zhàn)斗力，從而輕松擊敗很多強(qiáng)大敵人。當(dāng)某玩家在游戲中對(duì)某個(gè)敵人進(jìn)行了一次攻擊動(dòng)作，卻只對(duì)敵人造成少量傷害時(shí)，該玩家就很有可能對(duì)“諸葛神弩”這件武器道具產(chǎn)生興趣。從圖3中可以看到，當(dāng)“攻擊”和“造成傷害”兩個(gè)隱性事件連續(xù)發(fā)生時(shí)，由于造成傷害的值僅為5，于是這位ID為111的玩家就有可能為了提升自己攻擊造成的傷害程度，想要購(gòu)買“諸葛神弩”這件道具。當(dāng)然，在實(shí)際玩家行為數(shù)據(jù)中包含了更多更復(fù)雜的隱性事件與游戲道具之間的關(guān)聯(lián)。

游戲提供商只能從游戲日志數(shù)據(jù)中直接觀察到某位玩家在某段時(shí)間內(nèi)經(jīng)歷的事件，以及他購(gòu)買的游戲道具信息，卻難以觀察到事件與道具購(gòu)買狀態(tài)之間的直接關(guān)聯(lián)信息（當(dāng)然一些顯而易見的簡(jiǎn)單關(guān)聯(lián)信息可以通過(guò)觀察獲得），即難以獲知是哪些事件導(dǎo)致了玩家對(duì)某道具的購(gòu)買。事件與道具購(gòu)買狀態(tài)之間的關(guān)聯(lián)信息顯然是構(gòu)建道具推薦系統(tǒng)的基礎(chǔ)。將每個(gè)事件作為一個(gè)示例，每個(gè)道具的購(gòu)買狀態(tài)作為一個(gè)類別標(biāo)記，就可以用機(jī)器學(xué)習(xí)的方法來(lái)構(gòu)建推薦系統(tǒng)。若用傳統(tǒng)的單示例機(jī)器學(xué)習(xí)算法進(jìn)行推薦，必須給每一個(gè)示例（事件）指定一個(gè)標(biāo)記（道具購(gòu)買狀態(tài)）作為訓(xùn)練樣本。這樣獲得的訓(xùn)練樣本顯然具有極大噪音，因?yàn)樵摌?biāo)記（道具購(gòu)買狀態(tài)）很可能并非由該示例（事件）“觸發(fā)”。然而，這個(gè)情景用MIML來(lái)描述卻非常自然。用游戲日志數(shù)據(jù)中玩家經(jīng)歷的事件信息來(lái)構(gòu)建“多示例”，而游戲日志數(shù)據(jù)中玩家的道具購(gòu)買情況來(lái)構(gòu)建“多標(biāo)記”，則多示例多標(biāo)記模型描述了一位經(jīng)歷了多個(gè)事件的玩家的所有道具購(gòu)買狀態(tài)。這樣一來(lái)，盡管沒有事件與道具購(gòu)買狀態(tài)之間的直接關(guān)聯(lián)信息，也可以利用事件信息來(lái)給玩家進(jìn)行道具推薦。

Fig.3 Relationship between latent events and props圖3　隱性事件與道具的關(guān)聯(lián)

3　解決方案

在手機(jī)網(wǎng)絡(luò)游戲運(yùn)營(yíng)過(guò)程中，每位玩家每天都會(huì)產(chǎn)生大量日志數(shù)據(jù)。為了充分利用這些日志數(shù)據(jù)獲得更好的推薦性能，用于游戲道具推薦的MIML算法需要能夠進(jìn)行快速處理。另一方面，手機(jī)網(wǎng)絡(luò)游戲玩家群體中存在大量免費(fèi)玩家，他們的行為數(shù)據(jù)顯然沒有標(biāo)記。將這些數(shù)據(jù)的標(biāo)記都當(dāng)作負(fù)標(biāo)記處理，就默認(rèn)了這些玩家對(duì)于所有游戲道具都不感興趣，很有可能給推薦模型的訓(xùn)練帶來(lái)負(fù)面影響。而將這些數(shù)據(jù)的標(biāo)記當(dāng)作未標(biāo)記處理，則有可能獲得更好的效果。因此用于游戲道具推薦的MIML算法需要能夠有效利用未標(biāo)記樣本。

為了滿足快速計(jì)算和有效利用未標(biāo)記樣本的需求，給出co-MIMLfast算法。

算法1 co-MIMLfast算法

輸入：標(biāo)記數(shù)據(jù)L，未標(biāo)記數(shù)據(jù)U，迭代輪數(shù)r。

訓(xùn)練：

3. for i＝1:r

9. end for

測(cè)試：對(duì)于測(cè)試樣本Xtest，它的標(biāo)記是（Xtest）與（Xtest）的交集

算法1是MIMLfast算法[18]與協(xié)同訓(xùn)練（co-training）[19]的結(jié)合，兩個(gè)基模型分別由MIMLfast算法學(xué)習(xí)獲得，并在每一輪協(xié)同訓(xùn)練過(guò)程中交換各自的預(yù)測(cè)樣本進(jìn)行學(xué)習(xí)。MIMLfast算法滿足計(jì)算速度快的要求，能夠用于大規(guī)模數(shù)據(jù)，是目前最快速的MIML算法。而且MIMLfast的優(yōu)化目標(biāo)是最小化排序錯(cuò)誤（ranking error），與Top-n推薦問(wèn)題的目標(biāo)非常貼近。協(xié)同訓(xùn)練是一種基于異議的半監(jiān)督學(xué)習(xí)算法[20-21]。與產(chǎn)生式模型、S3VM（semi-supervised support vector machine）、圖模型等幾類半監(jiān)督學(xué)習(xí)算法相比，它是一種“元學(xué)習(xí)算法”，可以與任何基學(xué)習(xí)模型進(jìn)行結(jié)合，只需外加一個(gè)交互標(biāo)記樣本的過(guò)程即可進(jìn)行半監(jiān)督學(xué)習(xí)。本文已經(jīng)確定使用MIMLfast算法進(jìn)行MIML模型的訓(xùn)練，因此利用協(xié)同訓(xùn)練進(jìn)行改造最為直接。

協(xié)同訓(xùn)練一開始應(yīng)用于多視圖的數(shù)據(jù)，后來(lái)被證明只要兩個(gè)基分類器不同（掌握不同知識(shí)），就可以以未標(biāo)記樣本為載體來(lái)互相學(xué)習(xí)傳遞知識(shí)，并學(xué)習(xí)未標(biāo)記的樣本[19，22]。算法1中利用Bootstrap方法訓(xùn)練掌握不同知識(shí)的基分類器。另外，算子MIMLfast（?）指利用MIMLfast算法在訓(xùn)練集上訓(xùn)練MIML模型。下面簡(jiǎn)單介紹MIMLfast算法的訓(xùn)練過(guò)程。

MIMLfast算法為了在優(yōu)化過(guò)程中利用不同標(biāo)記之間的聯(lián)系，先通過(guò)一個(gè)矩陣W0將原來(lái)的特征向量x映射到另一個(gè)空間里。這個(gè)空間對(duì)于各個(gè)標(biāo)記是共享的，因而這個(gè)樣本在標(biāo)記l上的分類模型為：

由于W0和wl是通過(guò)交替優(yōu)化進(jìn)行的，不同標(biāo)記之間的聯(lián)系信息就可以通過(guò)W0保存下來(lái)。為了應(yīng)對(duì)MIML模型通常面臨復(fù)雜語(yǔ)義的情形，MIMLfast為每個(gè)標(biāo)記l設(shè)計(jì)了子概念類。以標(biāo)記“蘋果”為例，擁有這個(gè)標(biāo)記的對(duì)象既有可能是一個(gè)水果，也有可能是一部手機(jī)，那么描述這兩種對(duì)象的特征向量可能就差別很大。子概念類的設(shè)計(jì)能夠讓示例與標(biāo)記更好地?cái)M合。令每個(gè)標(biāo)記的子概念類數(shù)目為K，則有：

其中，wl，k對(duì)應(yīng)了標(biāo)記l的第k個(gè)子概念類的模型。在擁有了示例層面的模型后，需要建立以包為輸入的模型。MIMLfast中采用取最大值的方法定義包在標(biāo)記l上的模型為：

有了對(duì)于包X在標(biāo)記l上的模型，則定義這個(gè)模型的優(yōu)化目標(biāo)排序錯(cuò)誤ε如下：

只要最小化ranking error，就能獲得一個(gè)好的多示例多標(biāo)記推薦模型。對(duì)于這個(gè)非凸優(yōu)化問(wèn)題的求解，MIMLfast還采用了一些特別的優(yōu)化技巧，詳情請(qǐng)參見文獻(xiàn)[18]。

4　基準(zhǔn)測(cè)試

基準(zhǔn)測(cè)試在常用的MIML數(shù)據(jù)集上進(jìn)行，包括Letter Carroll[17]、Letter Frost[17]、MSRC V2[23]、Reuters[14]、Bird Song[17]和Scene[13]，它們的基本信息見表1。

Table 1　Popular MIML data sets表1　常用的MIML數(shù)據(jù)集

該實(shí)驗(yàn)主要用于驗(yàn)證co-MIMLfast算法的有效性。對(duì)于每個(gè)數(shù)據(jù)集，每次隨機(jī)選取其中9/10的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，其余1/10的數(shù)據(jù)作為測(cè)試數(shù)據(jù)，協(xié)同訓(xùn)練的迭代輪數(shù)r＝5。最終的實(shí)驗(yàn)結(jié)果是重復(fù)隨機(jī)選取30次后的平均結(jié)果。實(shí)驗(yàn)中標(biāo)記數(shù)據(jù)與未標(biāo)記數(shù)據(jù)的比例為2∶1。實(shí)驗(yàn)結(jié)果采用MIML中常用的5個(gè)評(píng)價(jià)準(zhǔn)則，分別是Hamming Loss、One-Error、Coverage、Ranking Loss和Average Precision，其定義請(qǐng)參見文獻(xiàn)[24]。需要說(shuō)明的是，為了實(shí)驗(yàn)結(jié)果更加直觀，對(duì)表中的覆蓋率進(jìn)行了歸一化處理。除了基本的MIMLfast算法，MIMLfast with self-training算法也被用來(lái)進(jìn)行對(duì)比。Self-training作為一種最簡(jiǎn)單的半監(jiān)督學(xué)習(xí)算法，是一個(gè)很好的對(duì)比參照。

從表2中可以看出，co-MIMLfast的實(shí)驗(yàn)結(jié)果在6個(gè)常用MIML數(shù)據(jù)集上相比MIMLfast的結(jié)果都有大幅提升（加粗?jǐn)?shù)據(jù)表示，根據(jù)顯著水平為0.05的成對(duì)雙側(cè)t檢驗(yàn)，相對(duì)于MIMLfast的性能提升具有顯著性），顯示出半監(jiān)督學(xué)習(xí)的有效性。當(dāng)然，兩個(gè)分類器的集成也給實(shí)驗(yàn)效果的提升帶來(lái)了不少幫助。另外，One-Error和Ranking Loss是需要重點(diǎn)關(guān)注的評(píng)價(jià)指標(biāo)。因?yàn)樵赥op-n推薦問(wèn)題中，Ranking Loss直接反映了模型的好壞，而One-Error恰好是Top-1推薦的錯(cuò)誤率。在這兩個(gè)評(píng)價(jià)指標(biāo)上，co-MIMLfast顯著地提高了模型性能。

Table 2 Benchmark test results表2　基準(zhǔn)測(cè)試結(jié)果

5　手機(jī)網(wǎng)絡(luò)游戲?qū)嶒?yàn)

真實(shí)游戲數(shù)據(jù)實(shí)驗(yàn)首先在3個(gè)手機(jī)網(wǎng)絡(luò)游戲的離線數(shù)據(jù)集上，對(duì)比co-MIMLfast算法與各種常用協(xié)同過(guò)濾算法的推薦效果。數(shù)據(jù)集的基本信息見表3。

Table 3 Online game data sets表3　網(wǎng)絡(luò)游戲數(shù)據(jù)集

與基準(zhǔn)測(cè)試部分一樣，對(duì)于每個(gè)數(shù)據(jù)集，每次隨機(jī)選取其中9/10的標(biāo)記數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，其余1/10的標(biāo)記數(shù)據(jù)作為測(cè)試數(shù)據(jù)，協(xié)同訓(xùn)練的迭代輪數(shù)r＝5。標(biāo)記數(shù)據(jù)占整個(gè)數(shù)據(jù)集的2/3，剩下的未標(biāo)記數(shù)據(jù)只在co-MIMLfast算法中才會(huì)利用到。最終的實(shí)驗(yàn)結(jié)果是重復(fù)隨機(jī)選取30次后的平均結(jié)果。這里使用的評(píng)價(jià)準(zhǔn)則很簡(jiǎn)單，就是與網(wǎng)絡(luò)游戲道具推薦系統(tǒng)產(chǎn)品收益直接相關(guān)聯(lián)的Top-n推薦準(zhǔn)確率。推薦算法方面，常用的隨機(jī)推薦（Random）、最熱門推薦（Most-popular）、基于用戶的協(xié)同過(guò)濾（User-CF）、基于物品的協(xié)同過(guò)濾（Item-CF）和隱語(yǔ)義模型（LFM）都被用來(lái)與co-MIMLfast進(jìn)行對(duì)比。其中，LFM是目前在非稀疏數(shù)據(jù)集上表現(xiàn)最好的推薦算法，而User-CF 與Item-CF也因?yàn)槠浜?jiǎn)單有效的特性被應(yīng)用在很多互聯(lián)網(wǎng)產(chǎn)品中。關(guān)于這些算法的詳情，請(qǐng)參見文獻(xiàn)[2]。需要特別指出的是，無(wú)論是各種協(xié)同過(guò)濾算法還是co-MIMLfast算法，在實(shí)現(xiàn)時(shí)有非常多的具體細(xì)節(jié)可以修改或添加，這些固定規(guī)則的改動(dòng)有可能大大影響算法在某些具體數(shù)據(jù)集上的表現(xiàn)。本文只考慮它們的基本算法。從表4中可以看出，co-MIMLfast算法在3個(gè)手機(jī)網(wǎng)絡(luò)游戲數(shù)據(jù)集合上都表現(xiàn)出了比較明顯的優(yōu)勢(shì)。這得益于它利用了更多的數(shù)據(jù)來(lái)訓(xùn)練模型：更多的事件上下文信息、更多的隱性事件信息以及更多的未標(biāo)記信息。更多的事件上下文和隱性事件信息可以讓用戶相似度矩陣的構(gòu)建更為精準(zhǔn)，而未標(biāo)記信息則使得對(duì)于用戶分布的估計(jì)更為準(zhǔn)確。

Table 4 Precision of Top-n recommendation on game data sets表4　離線游戲數(shù)據(jù)集上Top-n推薦準(zhǔn)確率

Table 5 Time cost of model training表5　模型訓(xùn)練時(shí)間

表5給出了幾種算法的模型訓(xùn)練時(shí)間對(duì)比。從表中可以看出快速多示例多標(biāo)記學(xué)習(xí)算法在學(xué)習(xí)效率上的優(yōu)勢(shì)。

最后，選取在離線數(shù)據(jù)實(shí)驗(yàn)中表現(xiàn)較好的LFM 和co-MIMLfast兩種算法進(jìn)行線上A/B測(cè)試。A/B測(cè)試是指將用戶隨機(jī)分為數(shù)量相等的兩組，分別使用兩種產(chǎn)品，通過(guò)比較兩種產(chǎn)品的轉(zhuǎn)化率來(lái)獲悉哪個(gè)產(chǎn)品更好。該測(cè)試在蘇州某公司開發(fā)運(yùn)營(yíng)的手機(jī)網(wǎng)絡(luò)游戲“xx三國(guó)”的道具推薦系統(tǒng)中進(jìn)行，于2014年12月1日上線，測(cè)試周期為一個(gè)月。該游戲道具推薦系統(tǒng)是簡(jiǎn)單的Top-1推薦。A/B測(cè)試中，根據(jù)玩家ID的奇偶性將玩家分為兩組。一組玩家通過(guò)LFM模型進(jìn)行推薦，另一組則通過(guò)co-MIMLfast模型進(jìn)行推薦。表6展示了10月至12月連續(xù)3個(gè)月該游戲的運(yùn)營(yíng)統(tǒng)計(jì)數(shù)據(jù)。其中，“付費(fèi)確認(rèn)框彈出”指玩家在游戲道具商店中選擇想要購(gòu)買的道具后彈出的“請(qǐng)確認(rèn)將從您的手機(jī)話費(fèi)中支付xx元購(gòu)買xx游戲道具”確認(rèn)提示框，而“付費(fèi)成功”指玩家在上述提示框中點(diǎn)擊了確定按鈕?？梢钥吹?，10月至11月游戲的用戶增長(zhǎng)率與收入增長(zhǎng)率分別是15.98%與16.02%，兩者基本一致。而11月至12月游戲的用戶增長(zhǎng)率與收入增長(zhǎng)率分別是16.70%與23.28%，收入增長(zhǎng)率出現(xiàn)了較大的提升。因此，計(jì)算每用戶平均收入可知，道具推薦系統(tǒng)給這款游戲帶來(lái)了5.7%的營(yíng)收增長(zhǎng)。

Table 6 Statistics of the“xx Three Kingdoms”表6　“xx三國(guó)”運(yùn)營(yíng)數(shù)據(jù)統(tǒng)計(jì)

Table 7 Results of A/B test表7　A/B測(cè)試結(jié)果

表7給出了A/B測(cè)試的結(jié)果，其中轉(zhuǎn)化率等于付費(fèi)成功次數(shù)除以付費(fèi)確認(rèn)框彈出次數(shù)。co-MIMLfast 在A/B測(cè)試中勝出，與線下離線實(shí)驗(yàn)的實(shí)驗(yàn)結(jié)果一致，表現(xiàn)出在網(wǎng)絡(luò)游戲道具推薦上的優(yōu)勢(shì)。

6　結(jié)束語(yǔ)

手機(jī)網(wǎng)絡(luò)游戲中的玩家行為數(shù)據(jù)具有上下文信息豐富，隱性事件信息豐富等特點(diǎn)。本文的主要貢獻(xiàn)是將多示例多標(biāo)記學(xué)習(xí)（MIML）框架用于描述手機(jī)網(wǎng)絡(luò)游戲道具推薦問(wèn)題，并在實(shí)際游戲上線運(yùn)營(yíng)中測(cè)試了MIML在手機(jī)游戲道具推薦中的性能。本文設(shè)計(jì)的算法雖然并不復(fù)雜，但在離線測(cè)試和實(shí)際上線運(yùn)營(yíng)中都取得了很好的效果，顯示出MIML這一新型機(jī)器學(xué)習(xí)框架的巨大潛力。未來(lái)工作中將嘗試把MIML技術(shù)應(yīng)用到更多手機(jī)網(wǎng)絡(luò)游戲的道具推薦中，并利用MIML的關(guān)鍵示例檢測(cè)機(jī)制[25]來(lái)發(fā)現(xiàn)觸發(fā)道具購(gòu)買的具體事件，從而設(shè)計(jì)出更好的運(yùn)營(yíng)策略。

References:

[1] Liu Jin. Video game is the ninth art[EB/OL].（2012-08-27）[2015-03-13]. http://www.cflac.org.cn/ys/xwy/201208/t20120827_ 146180.html.

[2] Ricci F，Rokach L，Shapira B，et al. Recommender systems handbook[M]. New York: Springer-Verlag，2011.

[3] Breese J S，Heckerman D，Kadie C. Empirical analysis of predictive algorithms for collaborative filtering[C]//Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence，Madison，USA，1998. San Francisco，USA: Morgan Kaufmann Publishers Inc，1998: 43-52.

[4] Cremonesi P，Koren Y，Turrin R. Performance of recommender algorithms on top-n recommendation tasks[C]// Proceedings of the 4th ACM Conference on Recommender Systems，Barcelona，Spain，2010. New York，USA: ACM，2010: 39-46.

[5] Herlocker J L，Konstan J，Borchers A，et al. An algorithmic framework for performing collaborative filtering[C]//Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval，Berkeley，USA，1999. New York，USA:ACM，1999: 230-237.

[6] Sarwar B，Karypis G，Konstan J，et al. Item-based collaborative filtering recommendation algorithms[C]//Proceedings of the 10th International World Wide Web Conference，Hong Kong，China，2001. New York，USA:ACM，2001: 285-295.

[7] Chen C，Zheng L，Thomo A，et al. Comparing the staples in latent factor models for recommender systems[C]//Proceedings of the 29th Annual ACM Symposium on Applied Computing，Gyeongju，Korea，2014. New York，USA:ACM，2014: 91-96.

[8] Hofmann T. Latent semantic models for collaborative filtering[J]. ACM Transactions on Information Systems，2004，22（1）: 89-115.

[9] Cai Yi，Leung H，Li Qing，et al. Typicality-based collaborative filtering recommendation[J]. IEEE Transactions on Knowledge and Data Engineering，2014，26（3）: 766-779.

[10] Kabbur S，Ning X，Karypis G. FISM: factored item similarity models for top-n recommender systems[C]//Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，Chicago，USA，2013. New York，USA:ACM，2013: 659-667.

[11] Zheng Xiaodong，Ding Hao，Mamitsuka H，et al. Collaborative matrix factorization with multiple similarities for predicting drug-target interactions[C]//Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，Chicago，USA，2013. New York，USA:ACM，2013: 1025-1033.

[12] Zhou Zhihua，Zhang Minling，Huang Shengjun，et al. Multiinstance multi-label learning[J]. Artificial Intelligence，2012，176（1）: 2291-2320.

[13] Zhou Zhihua，Zhang Minling. Multi-instance multi-label learning with application to scene classification[C]//Advances in Neural Information Processing Systems 19: Proceedings of the 20th Annual Conference on Neural Information Processing Systems，Vancouver，Canada，Dec 4-7，2006. Cambridge，USA: MIT Press，2006: 1609-1616.

[14] Sebastiani F. Machine learning in automated text categorization[J].ACM Computing Surveys，2002，34（1）: 1-47.

[15] Li Yingxin，Ji Shuiwang，Kumar S，et al. Drosophila gene expression pattern annotation through multi-instance multilabel learning[J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics，2011，9（1）: 98-112.

[16] Xu Xinshun，Jiang Yuan，Xue Xiangyang，et al. Semi-supervised multi-instance multi-label learning for video annotation task[C]// Proceedings of the 20th ACM International Conference on Multimedia，Nara，Japan，2012. New York，USA:ACM，2012: 737-740.

[17] Briggs F，F(xiàn)ern X，Raich R. Rank-loss support instance machines for MIML instance annotation[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，Beijing，China，2012. New York，USA:ACM，2012: 534-542.

[18] Huang Shengjun，Zhou Zhihua. Fast multi-instance multi-label learning[C]//Proceedings of the 28th AAAI Conference on Artificial Intelligence，Quebec City，Canada，2014. Menlo Park，USA:AAAI，2014: 1868-1874.

[19] Wang Wei，Zhou Zhihua. Analyzing co-training style algorithms[C]//LNCS 4701: Proceedings of the 18th European Conference on Machine Learning，Warsaw，Poland，Sep 17-21，2007. Berlin，Heidelberg: Springer，2007: 454-465.

[20] Zhu Xiaojin. Semi-supervised learning literature survey，TR 1530[R]. Computer Sciences，University of Wisconsin-Madison，2006.

[21] Pise N N，Kulkarni P. A survey of semi-supervised learning methods[C]//Proceedings of the 4th International Conference on Computational Intelligence and Security，Suzhou，China，Dec 13-17，2008. Piscataway，USA: IEEE，2008: 30-34.

[22] Zhou Zhihua，Li Ming. Semi-supervised learning by disagreement[J]. Knowledge and Information Systems，2010，24（3）: 415-439.

[23] Winn J，Criminisi A，Minka T. Object categorization by learned universal visual dictionary[C]//Proceedings of the 10th IEEE International Conference on Computer Vision，Beijing，China，2005.Piscataway，USA:IEEE，2005:1800-1807.

[24] Schapire R E，Singer Y. BoosTexter: a boosting-based system for text categorization[J]. Machine Learning，2000，39（2/3）: 135-168.

[25] Li Yufeng，Hu Juhua，Jiang Yuan，et al. Towards discovering what patterns trigger what labels[C]//Proceedings of the 26th AAAI Conference on Artificial Intelligence，Toronto，Canada，2012. Menlo Park，USA:AAAI，2012: 1012-1018.

附中文參考文獻(xiàn)：

[1]劉瑾.電子游戲的第九藝術(shù)之說(shuō)[EB/OL].（2012-08-27）[2015-03-13]. http://www.cflac.org.cn/ys/xwy/201208/t20120827_ 146180.html.

TANG Jun was born in 1990. He is an M.S. candidate at Nanjing University. His research interests include machine learning，data mining and phone game，etc.

唐?。?990—），男，南京大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘，手機(jī)游戲等。

ZHOU Zhihua was born in 1973. He is a professor and Ph.D. supervisor at Nanjing University，ACM distinguished scientist，IEEE fellow and CCF fellow. His research interests include artificial intelligence，machine learning and data mining，etc.

周志華（1973—），男，南京大學(xué)教授、博士生導(dǎo)師，ACM杰出科學(xué)家，IEEE會(huì)士，CCF會(huì)士，主要研究領(lǐng)域?yàn)槿斯ぶ悄?，機(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘等。

Mobile Phone Game Props Recommendation Based on Multi-Instance Multi-Label Learning*

TANG Jun1，2，ZHOU Zhihua1，2＋

1. National Key Laboratory for Novel Software Technology，Nanjing University，Nanjing 210023，China

2. Collaborative Innovation Center of Novel Software Technology and Industrialization，Nanjing 210023，China

Abstract:Mobile phone game providers gain profits by selling virtual props in games. This paper describes an event in game log data of players as an instance and represents the states of players’prop purchases by labels，so that the game props recommendation is modeled as multi-instance multi-label learning（MIML）problem. On the basis of this abstraction，an MIMLfast algorithm is used to recommend mobile phone game props and a semi-supervised learning part is integrated to improve the performance of recommendation. The results of experiments conducted on offline data sets and a real mobile phone game show that the MIML-based game props recommendation brings a remarkable increase of game profits.

Key words:machine learning; multi-instance multi-label learning（MIML）; semi-supervised learning; recommendation

文獻(xiàn)標(biāo)志碼：A

中圖分類號(hào)：TP301

Corresponding author:＋ E-mail: zhouzh@lamda.nju.edu.cn
TANG Jun，ZHOU Zhihua. Mobile phone game props recommendation based on multi-instance multi-label learning. Journal of Frontiers of Computer Science and Technology，2016，10（1）：103-111.

doi:10.3778/j.issn.1673-9418.1505055