并行繪制系統(tǒng)中基于多響應(yīng)隨機(jī)森林的負(fù)載估計

段思羽，賈文娟

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

0 引言

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

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

1 算法綜述

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

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

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

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

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

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

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

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

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

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

2.1 特征選取

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

圖1 三個繪制節(jié)點下的劃分模式

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

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

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

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

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

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

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

3 實驗

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

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

實驗結(jié)果對比：

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

4 結(jié)語

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