并行繪制系統中基于多響應隨機森林的負載估計

段思羽，賈文娟

（四川大學計算機學院，成都 610000）

0 引言

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

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

1 算法綜述

1.1 多響應隨機森林

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

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

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

這里η表示表征所描述的協方差結構的參數。使用（2）根據（1）創建多響應分割函數。對多響應回歸樹的每個葉子節點的預測值是該葉子節點中的數據響應的平均值。

1.2 數據增強

豐富的高質量數據是偉大的機器學習模型的關鍵。但是良好的數據不會在樹上生長，而稀缺性會阻礙模型的發展。解決缺乏數據的一種方法是數據增強（Data Augmentation）。程序化數據增強的智能方法可以將訓練集的大小增加10倍或更多。更好的是，模型通常會更加健壯（并防止過度擬合），并且由于更好的訓練集，甚至可以更簡單。有許多方法可以增加數據。最簡單的方法包括添加噪聲并對現有數據應用轉換。插補和尺寸縮減可用于在數據集的稀疏區域中添加樣本。更先進的方法包括基于動態系統或進化系統的數據模擬。

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

為了防止過擬合，讓模型更加魯棒性，可針對不平衡的數據采用數據增強的方法進行改進。

2 實現細節

2.1 特征選取

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

圖1 三個繪制節點下的劃分模式

2.2 機器學習模型

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

以三個繪制結點為例，單響應方法對同一幀的一種分布需要采集3條數據；若采用多響應回歸森林，所需的數據量就會變為原來的1/3，同理在估計負載分布時，使用模型預測的次數也將變為原來的1/3。在效率提高的同時，準確性也得以保障。

2.3 不平衡數據處理

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

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

圖2 選取訓練數據過程

3 實驗

本文研究的目的在于準確高效地估計繪制幀的負載分布情況，實驗針對四個繪制結點的情況進行負載分布估計，與單響應方法的效果做對比。

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

實驗結果對比：

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

4 結語

本文使用多響應隨即森林模型，并結合數據增強的方法，提出一種可以根據當前幀的信息預測某一劃分方式下的負載分布的方法。打破了“當前幀繪制之前無法得到負載分布”的假設，在預測準確性和效率上都有良好的效果。此方法為下一步在并行繪制系統中實時繪制做準備，在保證預測準確性的情況下，未來將繼續研究如何利用學習模型所預測的分布進行調度。