基于線性回歸的現(xiàn)代競(jìng)技水平估計(jì)算法對(duì)比研究

基于線性回歸的現(xiàn)代競(jìng)技水平估計(jì)算法對(duì)比研究

0研究結(jié)論與仿真分析得分系統(tǒng)計(jì)算并排名運(yùn)動(dòng)員的競(jìng)爭(zhēng)水平，這在競(jìng)技項(xiàng)目中起著重要作用。例如，體育和游戲。首先，統(tǒng)一衡量比賽得分的水平，提高或降低比賽的競(jìng)爭(zhēng)水平，有助于評(píng)估運(yùn)動(dòng)員的實(shí)力，激發(fā)運(yùn)動(dòng)員的動(dòng)力。其次，排名可以為活動(dòng)組織者組織種子選擇，使比賽安排更合理。最后，運(yùn)動(dòng)員可以通過(guò)排名直觀地了解運(yùn)動(dòng)員，提高比賽的觀賞植物。目前，等級(jí)分制、elo評(píng)分和真正的低分評(píng)分系統(tǒng)等已經(jīng)廣泛使用。盡管,評(píng)價(jià)圍棋棋手水平的方法很多,但都存在一些缺陷,并且各種方法評(píng)價(jià)結(jié)果并不一致,因此職業(yè)圍棋選手并無(wú)公認(rèn)、統(tǒng)一的排名.在圍棋強(qiáng)國(guó)中日韓,段位用來(lái)評(píng)價(jià)棋手水平已有很長(zhǎng)歷史,但各國(guó)評(píng)段標(biāo)準(zhǔn)不一、采用終生制,且同等段位選手難以比較.我國(guó)棋院在國(guó)內(nèi)棋手中采用等級(jí)分制,以勝局為計(jì)算基準(zhǔn),不考慮棋手自身和對(duì)手的競(jìng)技水平.此外,韓國(guó)棋院從2009年開(kāi)始采用基于Elo算法的評(píng)分系統(tǒng),其效果要優(yōu)于此前的使用的“分紅”評(píng)分系統(tǒng),但新棋手進(jìn)入評(píng)分系統(tǒng)時(shí)評(píng)分的初始化和Elo算法參數(shù)化以及“通縮”現(xiàn)象的處理等都需要手動(dòng)和經(jīng)驗(yàn).這些排名方法的結(jié)果差別較大,難以比較,因此排名的可靠性分析和合理的評(píng)價(jià)方法對(duì)優(yōu)化排名方法、衡量排名結(jié)果有重要意義.目前,國(guó)內(nèi)針對(duì)排名方法和評(píng)價(jià)體系的研究還很少.本文提出基于TrueSkill模型的圍棋棋手水平的貝葉斯學(xué)習(xí)方法并引入排名的可靠性分析方法.TrueSkill評(píng)分系統(tǒng)是微軟研究院為多人、多團(tuán)隊(duì)在線游戲的玩家水平匹配而開(kāi)發(fā)一種概率圖模型,在多標(biāo)簽多分類(lèi)和計(jì)算廣告中點(diǎn)擊率的預(yù)測(cè)上有不錯(cuò)的性能.棋手水平服從正態(tài)分布N(μ,σ2),根據(jù)學(xué)習(xí)得到的水平μ和穩(wěn)定性σ,提出兩種排名方法.作者在訓(xùn)練模型時(shí)采用隨機(jī)輸入,多次迭代的方法,使得模型能后向傳播,增強(qiáng)了對(duì)以往比賽結(jié)果的利用.為了評(píng)估各個(gè)排名結(jié)果的可靠性,本文通過(guò)仿真數(shù)據(jù)和比賽數(shù)據(jù)對(duì)排名的可靠性、時(shí)效性、穩(wěn)定性以及準(zhǔn)確性四個(gè)方面進(jìn)行了對(duì)比分析.實(shí)驗(yàn)結(jié)果表明,TrueSkill和Elo算法的排名結(jié)果均體現(xiàn)出較好的可靠性,兩種排名也有較強(qiáng)線性相關(guān)性,但淘汰賽制的仿真數(shù)據(jù)上TrueSkill要優(yōu)于Elo.1評(píng)估系統(tǒng)評(píng)分系統(tǒng)量化描述事物本質(zhì)的某種特征性質(zhì)并排名.等級(jí)分制、Elo評(píng)分和TrueSkill評(píng)分系統(tǒng)都計(jì)算選手的“能力”值反映其競(jìng)技水平.1.1職業(yè)高爾夫球場(chǎng)成績(jī)積分賽和等級(jí)分制規(guī)定特定賽事和特定比賽勝負(fù)得分,累加選手各項(xiàng)賽事得分.職業(yè)網(wǎng)球聯(lián)賽(ATP)和中國(guó)圍棋等級(jí)分制都采用這種靜態(tài)的評(píng)估系統(tǒng),評(píng)分的更新會(huì)出現(xiàn)非平滑現(xiàn)象.1.2elo評(píng)分系統(tǒng)Elo評(píng)分是根據(jù)選手過(guò)去成績(jī)來(lái)計(jì)算選手目前相對(duì)水平的一種評(píng)分系統(tǒng).Elo評(píng)分系統(tǒng)由美國(guó)物理學(xué)教授ArpadElo于1959年提出,最初是用于計(jì)算國(guó)際象棋比賽中的棋手的相對(duì)水平.Elo評(píng)分系統(tǒng)假設(shè)棋手贏得比賽的期望結(jié)果是選手當(dāng)前評(píng)分差距的函數(shù),選手的Elo評(píng)分的更新與實(shí)際結(jié)果和期望結(jié)果的偏差成比例.1.2.1elo評(píng)分的相關(guān)分析選手A戰(zhàn)勝選手B的概率,即預(yù)期結(jié)果為EA=γAγA+γB=10RA/40010RA/400+10RB/400=11+10-(RA-RB)/400EA=γAγA+γB=10RA/40010RA/400+10RB/400=11+10?(RA?RB)/400(1)EB=1-EA(2)式中:RA、RB分別為棋手A和B的Elo評(píng)分.當(dāng)RA=RB時(shí),EA=EB=0.5,即比賽的期望結(jié)果為平局.當(dāng)棋手A領(lǐng)先B的Elo等級(jí)分越多時(shí),A戰(zhàn)勝B的概率越大,反之亦然.1.2.2sa的規(guī)定比賽結(jié)束后,棋手A的Elo評(píng)分應(yīng)更新為:R′A=RA+K(SA-EA)(3)其中SA為比賽的實(shí)際結(jié)果,在雙人游戲中,SA規(guī)定如下:SA={1當(dāng)棋手A贏B?0.5當(dāng)比賽為平局?0其它.K為調(diào)節(jié)參數(shù),控制評(píng)分更新的幅度.通常,對(duì)于新選手采用較高的K值,隨比賽增加而逐漸減小K.1.2.3評(píng)分更新韓國(guó)棋院從2009年1月開(kāi)始采用由TaeilBai改進(jìn)的Elo評(píng)分系統(tǒng)作為新的世界職業(yè)圍棋棋手的排名系統(tǒng).針對(duì)圍棋棋手以往比賽的結(jié)果,TaeilBai改進(jìn)了Elo算法在圍棋棋手排名上的應(yīng)用.TaeilBai選用γ=10R/800,在評(píng)分更新時(shí)增加了權(quán)重w對(duì)比賽重要程度的衡量,以及在棋手失利的情況下添加調(diào)節(jié)因子ɑ來(lái)防止棋手得分過(guò)度減少而造成通縮(所有棋手的平均得分要低于歷史的情形).新的職業(yè)棋手的水平初始化:設(shè)棋手比賽次數(shù)為n,對(duì)手的評(píng)分為Ri,獲勝的比賽次數(shù)為nw,失敗的次數(shù)為nl,那么棋手的評(píng)分R為:R={1nn∑i=1Ri+150nw-150n1當(dāng)n＜5時(shí);1nn∑i=1Ri+1666(Νwn-0.5)當(dāng)5≤n＜9時(shí);1nn∑i=1Ri+1170當(dāng)9≤n＜30且nw=n時(shí);1nn∑i=1Ri-1170當(dāng)9≤n＜30且n1=n時(shí);1nn∑i=1Ri+nw當(dāng)9≤n＜30且0＜nw＜n時(shí).當(dāng)n≥30時(shí),棋手不再作為臨時(shí)選手,可以直接應(yīng)用Elo計(jì)算他們的評(píng)分.1.3促進(jìn)促進(jìn)單次博弈TrueSkill評(píng)分是基于以往比賽結(jié)果的貝葉斯在線學(xué)習(xí)的一種評(píng)分系統(tǒng).TrueSkill評(píng)分系統(tǒng)由微軟研究院開(kāi)發(fā),并成功應(yīng)用于Xbox的多用戶在線對(duì)戰(zhàn)平臺(tái).在團(tuán)隊(duì)競(jìng)技中團(tuán)隊(duì)人數(shù)不等的情況下,只需少量比賽,就能推斷出每個(gè)選手的真實(shí)水平.在本文中,我們考慮TrueSkill模型在雙人博弈中的應(yīng)用.1.3.1單次運(yùn)行時(shí),各有側(cè)重、分次充放電的判定TrueSkill評(píng)分系統(tǒng)假設(shè)選手水平s服從正態(tài)分布,即P(s)=N(s;μ,σ2),其中μ代表選手的真實(shí)水平,σ是對(duì)選手具有水平μ的不確定性的度量.在比賽中選手的發(fā)揮p應(yīng)在真實(shí)水平s附近波動(dòng),即P(p|s)=N(s,β2),其中β是定值,適用于所有選手,衡量選手發(fā)揮的起伏變化.1.3.2種新的并無(wú)回應(yīng)函數(shù),即a和b的作用分別為pa和pb,a和pb,p時(shí)a和pb,p時(shí)有p、pb的指示函數(shù),a和pb我們希望根據(jù)過(guò)往比賽結(jié)果r來(lái)計(jì)算水平s的后驗(yàn)分布P(s|r),由貝葉斯定理有:Ρ(s|r)=Ρ(r|s)Ρ(s)∫Ρ(r|s)Ρ(s)ds(4)其中:Ρ(s)=n∏i=1Ν(si;μi,σi2).假設(shè)選手A和B的發(fā)揮分別為pA和pB,定義d為選手發(fā)揮的差距:P(d|p)=Ι(d=pA-pB)其中I(x)為指示函數(shù),當(dāng)x為真時(shí),I(x)=1;當(dāng)x為假時(shí),I(x)=0.每場(chǎng)比賽結(jié)果的概率在給定d的條件下為:Ρ(r|d)={r=A勝∶Ι(d>ε),r=B勝∶Ι(d<-ε),r=平局∶Ι(|d|<ε).由此得到聯(lián)合分布為P(r,d,p,s)=P(r|d)P(d|p)P(p|s)P(s)(5)由公式(5)計(jì)算邊緣分布P(r|s)=∫∫P(r|d)P(d|p)P(p|s)dpdd(6)根據(jù)公式(4)、公式(6)和P(s)得到P(s|r),以上所有的概率分布用factor圖表示如圖1.1.3.3消息傳遞算法TrueSkill運(yùn)用消息傳遞算法來(lái)推導(dǎo)后驗(yàn)分布.由于消息2是一個(gè)階梯函數(shù)而導(dǎo)致d節(jié)點(diǎn)成為非高斯分布,標(biāo)準(zhǔn)的消息傳遞算法就無(wú)法運(yùn)用.TrueSkill使用了ExpectationPropagation(Minka,2001)算法,即對(duì)非高斯分布進(jìn)行矩匹配來(lái)近似成高斯分布,以期望再運(yùn)用消息傳遞算法.在圖2中消息傳遞算法為:1)消息沿著虛線箭頭從上往下傳遞;2)用EP算法計(jì)算消息2,并結(jié)合消息1,更新d的邊緣分布;3)消息沿著實(shí)線箭頭從下往上傳遞.每場(chǎng)比賽后,我們把學(xué)習(xí)到的分布P(s)=N(s;μ,σ2)作為下一場(chǎng)比賽相應(yīng)選手的先驗(yàn)分布,從而能夠通過(guò)一定數(shù)量的比賽,學(xué)習(xí)到選手的真實(shí)水平.1.3.4基于真實(shí)skell模型的二通道計(jì)算定義Ascending(xi)、Descending(xi)分別為xi的升序和降序排列集合,Position(xi|D)為集合D中元素xi的位置.棋手總數(shù)為M,棋手i比賽數(shù)是Ni,Ranki表示棋手i的排名,其中i,Ranki∈{1,…,M}.由TrueSkill模型,σ作為μ的不確定性的度量,由此可以考慮兩種排名方法,分別是Top-1和Top-2排名:(1)Top-1:Ascending(Ranki)={1,2,…,M}.(7)其中:Ranki=Position(μi|Descending(μk)),i,k∈{1,…,M}.(2)Top-2:Ascending(Ranki)={1,2,…,M}.(8)其中:λi=μi-3σi,Ranki=Position(λi|Descending(λk)),i,k∈{1,…,M}.2評(píng)估體系的比較和評(píng)估2.1elo和tableskll算法評(píng)分更新的實(shí)現(xiàn)等級(jí)分制實(shí)現(xiàn)簡(jiǎn)單,能體現(xiàn)出比賽的重要性,但選手得分卻不隨選手水平和對(duì)手水平變化而變化.這一方面導(dǎo)致年輕選手等級(jí)分增長(zhǎng)緩慢,因此很難進(jìn)入高水平賽事,從而又影響到自身等級(jí)分的增加.另一方面,評(píng)分更新有較大波動(dòng)性.Elo和TrueSkill算法評(píng)分更新的大小由選手水平的差距決定,年輕棋手能較快地獲得真實(shí)水平的評(píng)分.Elo通常用于雙人對(duì)弈,參數(shù)調(diào)節(jié)需要經(jīng)驗(yàn),只用單個(gè)數(shù)字表示選手能力.TrueSkill最初應(yīng)用于多人多團(tuán)隊(duì)游戲,通過(guò)學(xué)習(xí)自動(dòng)得到棋手水平的概率分布.Elo和TrueSkill評(píng)分系統(tǒng)都被認(rèn)為具有濾波特性,即評(píng)分的更新只有前向傳播.本文將比賽結(jié)果進(jìn)行隨機(jī)排序,并仿真一定次數(shù)直到評(píng)分值收斂,增強(qiáng)了評(píng)分的平滑性.2.2排名結(jié)果應(yīng)符合以下條件排名的評(píng)價(jià)方法對(duì)衡量排名的可靠性、改進(jìn)排名方法有重要意義.作者認(rèn)為排名可靠應(yīng)滿足以下幾種基本性質(zhì):①客觀性,排名結(jié)果應(yīng)能符合客觀事實(shí);②時(shí)效性,排名的意義在于衡量選手目前的競(jìng)技狀態(tài);③穩(wěn)定性,棋手評(píng)分應(yīng)有較好的區(qū)分度;④準(zhǔn)確性,對(duì)比賽結(jié)果預(yù)測(cè)率反映排名的合理性.針對(duì)這四種性質(zhì),結(jié)合文獻(xiàn)提出的區(qū)分度度量方法,本文設(shè)計(jì)了評(píng)估評(píng)分系統(tǒng)性能的實(shí)驗(yàn)集.1k名7-1,2,9#為7.13.2段位和世界比賽冠軍數(shù)量是通用評(píng)價(jià)圍棋棋手所取得成就的方法,反映了棋手的競(jìng)技水平.定義Dani∈{1,2,…,9}為棋手i的段位.則k名棋手的段位期望和標(biāo)準(zhǔn)偏差為:Er(i),r(i+k-1)=i+k-1∑iDani(9)Sr(i),r(i+k-1)=√∑(Dani-Er(i),r(i+k-1))2k-1(10)2固定時(shí)間相比于段位和冠軍這種終生榮譽(yù),排名應(yīng)具有時(shí)效性.本實(shí)驗(yàn)選低段位、無(wú)冠軍而排名高的棋手進(jìn)行分析.3免排名頻繁波動(dòng)高水平棋手之間和低水平棋手之間區(qū)分度應(yīng)高于中檔棋手,區(qū)分度越高排名之間的距離越分散,避免排名頻繁波動(dòng).對(duì)于M個(gè)棋手,區(qū)分度的計(jì)算為:D=Μ-1∑i=1√(Vi+1-Vi)2+1√2Μ2-2Μ-1(11)其中:Vi=Μ×(1-|V′i-V′1|V′1-V′Μ),V′為原指標(biāo)值,在Elo中為R,Top-1中為μ以及Top-2中為λ(1.3.4節(jié)).4elo算法中2.2elo算法中a和b的整比較Elo和TrueSkill對(duì)未來(lái)比賽的預(yù)測(cè)準(zhǔn)確率.根據(jù)公式(1)即可計(jì)算Elo算法中棋手A戰(zhàn)勝B的概率.對(duì)于TrueSkill模型:Ρ(pA-pB>0)=Φ(μA-μB√σ2A+σ2B+2β2)(12)3真實(shí)skll的排名結(jié)果本文使用兩組數(shù)據(jù)來(lái)對(duì)比測(cè)試TrueSkill和韓國(guó)棋院官方排名的性能.第一組是8選手模擬淘汰賽的結(jié)果,用來(lái)驗(yàn)證系統(tǒng)實(shí)現(xiàn)的正確性.第二組是從1970年到2012年的5023場(chǎng)職業(yè)棋手高水平比賽的結(jié)果.通過(guò)該數(shù)據(jù),本文使用TrueSkill計(jì)算了比賽中出現(xiàn)的421位選手的競(jìng)技水平評(píng)估值并分別用1.3.4節(jié)的Top-1和Top-2排名方法排序.通過(guò)對(duì)比分析TrueSkill排名結(jié)果、韓國(guó)棋院官方排名以及訓(xùn)練集中參賽數(shù)大于19的所有120名職業(yè)棋手的段位,逐一評(píng)估了TrueSkill排名方法的客觀性、時(shí)效性、穩(wěn)定性和準(zhǔn)確性.3.1基于隨機(jī)抽樣的仿真分析實(shí)驗(yàn)采用的第一組數(shù)據(jù)是人工設(shè)計(jì)的模擬仿真數(shù)據(jù),如圖2所示,為8個(gè)選手A,B,…,H參加模擬淘汰賽的結(jié)果.Elo算法中初始化選手得分為2000,K=32,γ=10R/400,表1統(tǒng)計(jì)了排名結(jié)果.由表1,Top-1、Top-2中冠軍選手A排名最高,亞軍E次之.折戟于4強(qiáng)的棋手C和G雖然勝率和比賽場(chǎng)次相同,由于前者輸給了冠軍棋手,故棋手C排名第3.同樣,棋手B、F、D、H排名依次下降.而Elo和贏率并不能在有限的比賽信息下對(duì)選手做出排名.本文在訓(xùn)練模型時(shí),采用隨機(jī)抽樣的迭代算法,使得TrueSkill避免了濾波的特性,對(duì)以前比賽結(jié)果的利用更為充分,在不考慮時(shí)間特性的排名需求中表現(xiàn)更好.3.2職業(yè)大力比賽設(shè)計(jì)數(shù)據(jù)來(lái)自中國(guó)棋院在線,截止于2012年10月12日(包括段位、冠軍).比賽結(jié)果包括應(yīng)氏杯、三星杯、富士通杯、春蘭杯、豐田杯、LG杯、BC信用卡杯、中環(huán)杯、農(nóng)心杯以及中國(guó)職業(yè)圍棋甲級(jí)聯(lián)賽等5023場(chǎng)比賽,共421名棋手.TrueSkill模型的參數(shù)都初始化為μi=0,σi=1,βi=1,εi=0.2,其中i∈{1,M}.4基于兩種排名方法的排名結(jié)果當(dāng)棋手比賽數(shù)Ni≥20時(shí),σ2i<0.2,共120名棋手.對(duì)此120名棋手利用1.3.4節(jié)中的兩種排名方法排名,Top-1和Top-2的前30名結(jié)果如表2所示.4.1模型1:第100次迭代如圖3所示,分別迭代1、2、3、4、5、15、25、50、100、1000次,選取1000次結(jié)果為基準(zhǔn),其中第100次迭代分別與第1000次迭代均值和421∑i=1μi與方差和421∑i=1σ2i的差值均小于10-3,此時(shí)模型收斂.4.2網(wǎng)絡(luò)相關(guān)性4.2.1計(jì)算結(jié)果算首一致率由于韓國(guó)棋院只提供了排名的前60名棋手,本文只計(jì)算首一致率,即q=x0.4Μ,其中:x表示前40%排名共同出現(xiàn)棋手人數(shù),M表示總棋手人數(shù).結(jié)果如表3所示,說(shuō)明三種排名對(duì)于一流棋手認(rèn)同比較一致.4.2.2elo與table-1、to-2的相關(guān)分析計(jì)算韓國(guó)排名、Top-1和Top-2之間的斯皮爾曼等級(jí)相關(guān)系數(shù)r,如表3所示,根據(jù)相關(guān)系數(shù)判斷變量間相關(guān)密切程度的標(biāo)準(zhǔn),Elo分別與Top-1和Top-2顯著相關(guān),這表明Elo與TrueSkill排名對(duì)棋手水平的排列順序具有比較強(qiáng)的一致性.Top-1和Top-2斯皮爾曼等級(jí)相關(guān)系數(shù)達(dá)到0.8991為高度相關(guān),這兩種排名有很強(qiáng)的線性相關(guān)性.4.3根據(jù)真負(fù)錄結(jié)果分析4.3.1率pi與水平ito-1合作的關(guān)系勝率和對(duì)手水平是自身實(shí)力的決定性因素.圖4描述了勝率pi與水平μi(Top-1名次)之間的關(guān)系,勝率高的棋手排名高的概率大.實(shí)驗(yàn)3.1仿真數(shù)據(jù)中,如表1所示,相同勝率的棋手,μ值的大小受對(duì)手水平影響.4.3.2和table-2的比較參賽數(shù)越多,對(duì)一個(gè)棋手水平的認(rèn)識(shí)越清晰.在合理的排名體系中,應(yīng)考慮棋手水平的穩(wěn)定性.TrueSkill算法中觀測(cè)數(shù)據(jù)越多,σ越小,學(xué)習(xí)到的μ值越準(zhǔn)確.從圖5中,在初期棋手只需少量比賽就能讓?duì)掖蠓鶞p小,而隨比賽數(shù)的增加σ開(kāi)始變化緩慢.如圖6所示,在Top-2排名中,棋手排名根據(jù)參賽數(shù)有一個(gè)上界,隨參賽數(shù)增加上界減小速率越來(lái)越小,棋手Top-2排名高的概率逐漸增大.由此,比賽數(shù)對(duì)σ和Top-2的影響隨比賽數(shù)的增加而減小,使得排名逐漸回歸到μ值上.4.4職業(yè)期望比較TrueSkill和Elo排名方法均能基本反映棋手的段位情況.如表2,在前30名中,Top-1和Top-2里9段棋手比例都將近70%,而Elo也超過(guò)60%.由3.2節(jié)公式(9)和(10),如表4所示,Top-1、Top-2和Elo中段位期望最高的棋手均排名前20,段位期望基本隨排名下降而減小.4.5范廷3.5表1:能力能力TrueSkill相比于段位和冠軍這種終生榮譽(yù)更具時(shí)效性.此前沒(méi)有獲得過(guò)世界冠軍的年輕棋手范廷鈺3段在兩種排名中均為前10.對(duì)于這種“反?！爆F(xiàn)象,一方面是由于棋手在高水平比賽中有較高的勝率,其中范廷鈺勝率73.3%排名第1.另一方面因?yàn)槲覈?guó)圍棋升段規(guī)則較為嚴(yán)格,尤其對(duì)剛剛參加世界比賽的年輕棋手而言.而在本文完