段思羽，賈文娟

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610000）

0 引言

大型實(shí)時(shí)繪制系統(tǒng)中為解決單個(gè)GPU無(wú)法流暢顯示的問(wèn)題，通常采用的分配任務(wù)方法主要有：①靜態(tài)劃分任務(wù)[1]，即每一幀以同樣的方式劃分任務(wù)，很難適應(yīng)動(dòng)態(tài)變化的繪制場(chǎng)景；②基于幀間相關(guān)性劃分任務(wù)[1]，根據(jù)前一幀負(fù)載分布情況來(lái)調(diào)整下一幀任務(wù)分配，這種方法在場(chǎng)景產(chǎn)生突變的情況下不能得到良好的效果。這些方法都有一個(gè)共同的缺點(diǎn)——不能在某一幀繪制前準(zhǔn)確的知道負(fù)載分布情況。

如果可以估計(jì)當(dāng)前要繪制的一幀在屏幕空間中負(fù)載的大致分布情況，就能夠比較容易的劃分任務(wù)。對(duì)于某一幀，我們能夠得到繪制場(chǎng)景相關(guān)的一系列特征X=X1，X2，…，Xm，Xm+1，Xm+2，…，Xm+k，其中X1～Xm為繪制場(chǎng)景特征，Xm+1～Xm+k為劃分位置特征。本文假設(shè)并行繪制系統(tǒng)的繪制節(jié)點(diǎn)數(shù)N固定，基于屏幕空間劃分任務(wù)的模式固定，旨在用機(jī)器學(xué)習(xí)模型估計(jì)出每個(gè)子節(jié)點(diǎn)的負(fù)載Y=Y1，Y2，…，YN。這是一個(gè)多響應(yīng)的回歸問(wèn)題，考慮到隨機(jī)森林適合處理高維數(shù)據(jù)的回歸問(wèn)題，并且抗過(guò)擬合的能力強(qiáng)，采用多響應(yīng)的隨機(jī)森林（MRF）[2]作為預(yù)測(cè)負(fù)載的模型。另外，由于繪制系統(tǒng)中采集的數(shù)據(jù)分布并不均衡，本文借鑒了數(shù)據(jù)增強(qiáng)（Data Augmentation）[4]的方法對(duì)隨機(jī)森林算法中抽取Bootstrap的方法進(jìn)行了改進(jìn)。

1 算法綜述

1.1 多響應(yīng)隨機(jī)森林

由Breiman[4]等人提出的隨機(jī)森林是由多棵樹集成的學(xué)習(xí)器，可用作回歸數(shù)據(jù)的預(yù)測(cè)?；貧w樹框架由四個(gè)部分組成：①是否為一個(gè)二進(jìn)制（或分裂）問(wèn)題，通過(guò)一系列預(yù)測(cè)因子劃分空間。通過(guò)根據(jù)這些分割而創(chuàng)建的子空間被稱為節(jié)點(diǎn)。沒(méi)有任何后代節(jié)點(diǎn)的節(jié)點(diǎn)是葉子結(jié)點(diǎn)。②節(jié)點(diǎn)純度的衡量，通常與樣本響應(yīng)的方差有關(guān)。③節(jié)點(diǎn)劃分函數(shù)φ(s，t)，可以用于評(píng)估每個(gè)節(jié)點(diǎn)t的每個(gè)分割位置s，最佳的分割位置是最優(yōu)化φ，即所得到的子節(jié)點(diǎn)中的響應(yīng)分布在所有競(jìng)爭(zhēng)分裂中是最同質(zhì)的，同質(zhì)性通過(guò)雜質(zhì)測(cè)量評(píng)估。

在單響應(yīng)數(shù)據(jù)集中，用xij和yi分別表示預(yù)測(cè)因子和響應(yīng)?？紤]包含數(shù)據(jù)集子集的節(jié)點(diǎn)t，我們的目標(biāo)是將t分為兩個(gè)子節(jié)點(diǎn)，做節(jié)點(diǎn)tL和有節(jié)點(diǎn)tR，設(shè)j是連續(xù)或有序分類預(yù)測(cè)因子的索引。允許的分割點(diǎn)位置是在tL=i∈t:xij≤c，tR=i∈t:xij>c范圍內(nèi)的順序在所有可能的值上產(chǎn)生不同的tL，tR；對(duì)于無(wú)序分類預(yù)測(cè)變量，允許所有分類為不相交的類別子集。節(jié)點(diǎn)的純度衡量依據(jù)平方和其中μ(t)是節(jié)點(diǎn)t中y的平均值。此時(shí)分割函數(shù)為：

考慮多個(gè)響應(yīng)的數(shù)據(jù)，鑒于響應(yīng)之間的預(yù)期依賴性，可以通過(guò)同時(shí)分析所有響應(yīng)來(lái)實(shí)現(xiàn)解釋性和預(yù)測(cè)性增益。簡(jiǎn)單起見，我們假設(shè)響應(yīng)數(shù)量相同，預(yù)測(cè)因子是“基線”變量，不隨k變化。將回歸樹擴(kuò)展到多個(gè)響應(yīng)所需的只是修改分割函數(shù)。一個(gè)自然的公式是用協(xié)方差加權(quán)模擬代替節(jié)點(diǎn)純度測(cè)量：

這里η表示表征所描述的協(xié)方差結(jié)構(gòu)的參數(shù)。使用（2）根據(jù)（1）創(chuàng)建多響應(yīng)分割函數(shù)。對(duì)多響應(yīng)回歸樹的每個(gè)葉子節(jié)點(diǎn)的預(yù)測(cè)值是該葉子節(jié)點(diǎn)中的數(shù)據(jù)響應(yīng)的平均值。

1.2 數(shù)據(jù)增強(qiáng)

豐富的高質(zhì)量數(shù)據(jù)是偉大的機(jī)器學(xué)習(xí)模型的關(guān)鍵。但是良好的數(shù)據(jù)不會(huì)在樹上生長(zhǎng)，而稀缺性會(huì)阻礙模型的發(fā)展。解決缺乏數(shù)據(jù)的一種方法是數(shù)據(jù)增強(qiáng)（Data Augmentation）。程序化數(shù)據(jù)增強(qiáng)的智能方法可以將訓(xùn)練集的大小增加10倍或更多。更好的是，模型通常會(huì)更加健壯（并防止過(guò)度擬合），并且由于更好的訓(xùn)練集，甚至可以更簡(jiǎn)單。有許多方法可以增加數(shù)據(jù)。最簡(jiǎn)單的方法包括添加噪聲并對(duì)現(xiàn)有數(shù)據(jù)應(yīng)用轉(zhuǎn)換。插補(bǔ)和尺寸縮減可用于在數(shù)據(jù)集的稀疏區(qū)域中添加樣本。更先進(jìn)的方法包括基于動(dòng)態(tài)系統(tǒng)或進(jìn)化系統(tǒng)的數(shù)據(jù)模擬。

大多數(shù)機(jī)器學(xué)習(xí)分類算法對(duì)數(shù)據(jù)的不平衡敏感。讓我們考慮一個(gè)乳腺癌數(shù)據(jù)集極端的例子：假設(shè)我們有10個(gè)惡性樣本和90個(gè)良性樣本。已經(jīng)在這樣的數(shù)據(jù)集上訓(xùn)練和測(cè)試的機(jī)器學(xué)習(xí)模型現(xiàn)在可以預(yù)測(cè)所有樣本的“良性”并且仍然獲得非常高的準(zhǔn)確度。不平衡的數(shù)據(jù)集會(huì)將預(yù)測(cè)模型偏向更常見的數(shù)據(jù)。

為了防止過(guò)擬合，讓模型更加魯棒性，可針對(duì)不平衡的數(shù)據(jù)采用數(shù)據(jù)增強(qiáng)的方法進(jìn)行改進(jìn)。

2 實(shí)現(xiàn)細(xì)節(jié)

2.1 特征選取

本文通過(guò)一個(gè)繪制幀的信息 X_1，X_2，…，X_m，以及某一劃分軸位 X_（m+1），X_（m+2），…，X_（m+k），預(yù)測(cè)得到每個(gè)節(jié)點(diǎn)的負(fù)載大小Y_1，…，Y_N。其中X_（1～m）根據(jù)繪制場(chǎng)景中影響繪制時(shí)間的因素決定，例如視點(diǎn)位置、視點(diǎn)朝向、光源信息等；X_（m+1～m+k）表示所有劃分軸相對(duì)屏幕原點(diǎn)的坐標(biāo)位置。以三個(gè)繪制節(jié)點(diǎn)為例，基于屏幕空間劃分任務(wù)的模式固定如圖1所示，屏幕的高和寬分別為W、H，用兩條劃分軸即可分割屏幕，此時(shí)有特征 X_（m+1）和 X_（m+2）；此時(shí)響應(yīng)值為三個(gè)節(jié)點(diǎn)的繪制時(shí)間。

圖1 三個(gè)繪制節(jié)點(diǎn)下的劃分模式

2.2 機(jī)器學(xué)習(xí)模型

對(duì)于此回歸問(wèn)題首先想到的方案是用繪制幀信息和子屏幕位置坐標(biāo)分別預(yù)測(cè)同一幀不同子窗口的繪制時(shí)間，此方案可以運(yùn)用原始的單響應(yīng)回歸森林模型來(lái)擬合數(shù)據(jù)。然而這個(gè)方案有一下幾個(gè)缺點(diǎn)：①采集訓(xùn)練數(shù)據(jù)時(shí)，同一幀對(duì)于每種劃分的每個(gè)窗口都要采集數(shù)據(jù)，導(dǎo)致數(shù)據(jù)集數(shù)量很龐大；②估計(jì)一幀的負(fù)載分布需要對(duì)每個(gè)子窗口都預(yù)測(cè)一次，效率變低；③數(shù)據(jù)集中有大量的數(shù)據(jù)繪制幀信息特征是相同的，原始隨機(jī)森林模型不能很好地處理這種情狂，導(dǎo)致預(yù)測(cè)準(zhǔn)確性下降。

以三個(gè)繪制結(jié)點(diǎn)為例，單響應(yīng)方法對(duì)同一幀的一種分布需要采集3條數(shù)據(jù)；若采用多響應(yīng)回歸森林，所需的數(shù)據(jù)量就會(huì)變?yōu)樵瓉?lái)的1/3，同理在估計(jì)負(fù)載分布時(shí)，使用模型預(yù)測(cè)的次數(shù)也將變?yōu)樵瓉?lái)的1/3。在效率提高的同時(shí)，準(zhǔn)確性也得以保障。

2.3 不平衡數(shù)據(jù)處理

通過(guò)對(duì)繪制場(chǎng)景中大規(guī)模采集的數(shù)據(jù)進(jìn)行分析，我們發(fā)現(xiàn)數(shù)據(jù)的分布很不均衡，每一幀的繪制時(shí)間y分布從 10ms～170ms，其中絕大部分?jǐn)?shù)據(jù)分布在10ms～50ms之間。然而我們更期望將繪制時(shí)間大的幀有良好的預(yù)測(cè)能力。用這樣不平衡的數(shù)據(jù)訓(xùn)練得出的模型容易出現(xiàn)過(guò)擬合的現(xiàn)象，欠缺對(duì)數(shù)量少的數(shù)據(jù)的預(yù)測(cè)能力。

隨機(jī)森林中使用了bagging[6]的方法，每棵樹的訓(xùn)練數(shù)據(jù)為隨機(jī)有放回的從原始數(shù)據(jù)集中抽取數(shù)量與原始數(shù)據(jù)集相同的數(shù)據(jù)作為訓(xùn)練集，此方法會(huì)使每棵樹的訓(xùn)練數(shù)據(jù)中有約2/3的數(shù)據(jù)被選中從而更偏向于一些數(shù)據(jù)，但整體上來(lái)看并未對(duì)某些數(shù)據(jù)有所側(cè)重。為了使我們的模型更側(cè)重于繪制時(shí)間大的數(shù)據(jù)，借鑒等人He Kaiming[7]處理不平衡數(shù)據(jù)的方法中Label Shuffling的類別平衡策略，我們針對(duì)隨機(jī)森林中bagging的步驟進(jìn)行了改進(jìn)。步驟如下：首先對(duì)原始數(shù)據(jù)集按照響應(yīng)值的大小進(jìn)行排序；然后計(jì)算每個(gè)區(qū)間的數(shù)據(jù)數(shù)量，并得到數(shù)據(jù)最多的那個(gè)區(qū)間的數(shù)據(jù)條數(shù)，更具這個(gè)最多的數(shù)據(jù)數(shù)量，對(duì)每個(gè)區(qū)間都產(chǎn)生一個(gè)隨機(jī)排列的列表；然后用每個(gè)區(qū)間的列表中的數(shù)對(duì)各自區(qū)間的數(shù)據(jù)數(shù)求余，得到一個(gè)索引值，從此區(qū)間中選取數(shù)據(jù)，生成此區(qū)間的隨機(jī)列表；然后把所有區(qū)間的隨機(jī)列表連在一起，做Random Shuffling，得到最后的數(shù)據(jù)集，用這個(gè)數(shù)據(jù)集進(jìn)行訓(xùn)練。此過(guò)程如圖2所示。

圖2 選取訓(xùn)練數(shù)據(jù)過(guò)程

3 實(shí)驗(yàn)

本文研究的目的在于準(zhǔn)確高效地估計(jì)繪制幀的負(fù)載分布情況，實(shí)驗(yàn)針對(duì)四個(gè)繪制結(jié)點(diǎn)的情況進(jìn)行負(fù)載分布估計(jì)，與單響應(yīng)方法的效果做對(duì)比。

實(shí)驗(yàn)場(chǎng)景：實(shí)驗(yàn)場(chǎng)景包含LLL算法、SSAO算法等繪制算法；所采集的繪制信息特征有311維（包括視點(diǎn)位置、視點(diǎn)朝向、光源位置等），劃分軸信息有3維。

實(shí)驗(yàn)結(jié)果對(duì)比：

對(duì)于同一條漫友路徑下采集的訓(xùn)練集，分別用單響應(yīng)和多響應(yīng)回歸森林的模型做實(shí)驗(yàn)。其中單響應(yīng)的訓(xùn)練集包含數(shù)據(jù)80，000條、多響應(yīng)的訓(xùn)練集包含數(shù)據(jù)20，000條。對(duì)比預(yù)測(cè)偏差Biass=abs(Yi-Y‘i)，以及對(duì)所有數(shù)據(jù)的預(yù)測(cè)時(shí)間。單響應(yīng)模型的預(yù)測(cè)最大偏差為5.25ms，多響應(yīng)的預(yù)測(cè)最大偏差為3.23ms；對(duì)所有數(shù)據(jù)的預(yù)測(cè)時(shí)間單響應(yīng)情況下為10.0min，多響應(yīng)情況下為7.8min。本文采用的模型在準(zhǔn)確性和效率上均有明顯優(yōu)勢(shì)。

4 結(jié)語(yǔ)

本文使用多響應(yīng)隨即森林模型，并結(jié)合數(shù)據(jù)增強(qiáng)的方法，提出一種可以根據(jù)當(dāng)前幀的信息預(yù)測(cè)某一劃分方式下的負(fù)載分布的方法。打破了“當(dāng)前幀繪制之前無(wú)法得到負(fù)載分布”的假設(shè)，在預(yù)測(cè)準(zhǔn)確性和效率上都有良好的效果。此方法為下一步在并行繪制系統(tǒng)中實(shí)時(shí)繪制做準(zhǔn)備，在保證預(yù)測(cè)準(zhǔn)確性的情況下，未來(lái)將繼續(xù)研究如何利用學(xué)習(xí)模型所預(yù)測(cè)的分布進(jìn)行調(diào)度。