[發(fā)明專利]并行處理機(jī)器學(xué)習(xí)決策樹訓(xùn)練

有效

• 申請(qǐng)?zhí)枺?/td>: 201110443208.7
• 申請(qǐng)日: 2011-12-14
• 公開（公告）號(hào): CN102566981A
• 公開（公告）日: 2012-07-11
• 發(fā)明（設(shè)計(jì)）人: M·菲諾齊奧;R·E·摩爾;R·M·蓋斯;J·肖頓
• 申請(qǐng)（專利權(quán)）人: 微軟公司
• 主分類號(hào): G06F9/38
• 分類號(hào): G06F9/38;G06N5/00
• 代理公司: 上海專利商標(biāo)事務(wù)所有限公司 31100
• 代理人: 蔡悅

技術(shù)領(lǐng)域

本發(fā)明涉及用于決策樹訓(xùn)練的機(jī)器學(xué)習(xí)，更具體地，本發(fā)明涉及利用包括多個(gè)圖形處理單位(GPU)的平行處理流水線來(lái)生成決策樹。

背景技術(shù)

在機(jī)器學(xué)習(xí)中，決策樹是資源密集處理的結(jié)果，通過(guò)決策樹，計(jì)算系統(tǒng)處理非常大的示例集。這些示例被用于構(gòu)建問(wèn)題樹，這些問(wèn)題被用于最終在運(yùn)行時(shí)對(duì)輸入數(shù)據(jù)進(jìn)行分類。通常，在決策樹的訓(xùn)練期間使用的示例越多，運(yùn)行時(shí)結(jié)果就越準(zhǔn)確。習(xí)慣上，用于處理數(shù)百萬(wàn)至數(shù)十億計(jì)的示例的方案將使用聯(lián)網(wǎng)的基于中央處理單元(CPU)的計(jì)算設(shè)備的大規(guī)模群集。然而，這類方案是昂貴的并且容易受到不可靠性的影響。例如，要求額外的組件和連接以便將基于CPU的計(jì)算設(shè)備群集連網(wǎng)在一起，這創(chuàng)建了額外的可能故障的點(diǎn)。另外，由于基于CPU的計(jì)算設(shè)備群集通常被分布在不同區(qū)域，因此需要額外的勞力來(lái)維護(hù)這些群集，這增加了運(yùn)行成本。

發(fā)明內(nèi)容

提供本發(fā)明內(nèi)容以便以簡(jiǎn)化的形式介紹將在以下具體實(shí)施方式中進(jìn)一步描述的一些概念。本發(fā)明內(nèi)容并不旨在標(biāo)識(shí)所要求保護(hù)主題的關(guān)鍵特征或必要特征，也不旨在用于限制所要求保護(hù)主題的范圍。此外，所要求保護(hù)的主題不限于解決在本發(fā)明的任一部分中提及的任何或所有缺點(diǎn)的實(shí)現(xiàn)。

此處所公開的各實(shí)施例涉及通過(guò)基于圖形處理單元(GPU)的機(jī)器學(xué)習(xí)來(lái)生成決策樹。例如，公開的一個(gè)實(shí)施例提供一種用于生成包括組織在多個(gè)層級(jí)中的多個(gè)節(jié)點(diǎn)的決策樹。決策樹由包括多個(gè)處理塊的并行處理流水線來(lái)生成。每個(gè)處理塊包括共享一個(gè)存儲(chǔ)器塊的多個(gè)圖形處理單元(GPU)。此外，并行處理流水線的每個(gè)GPU共享一個(gè)全局存儲(chǔ)器。該方法包括，對(duì)于決策樹的每個(gè)層級(jí)：在并行處理流水線的每個(gè)GPU處對(duì)示例集中的每個(gè)示例執(zhí)行針對(duì)特征集中的一個(gè)特征的特征測(cè)試。該方法還包括在每個(gè)存儲(chǔ)器塊處累積由共享存儲(chǔ)器塊的多個(gè)GPU處理的對(duì)每個(gè)示例執(zhí)行的每個(gè)特征測(cè)試的結(jié)果。該方法還包括，將累積的結(jié)果從每個(gè)存儲(chǔ)器塊寫入到全局存儲(chǔ)器，以生成對(duì)于層級(jí)中的每個(gè)節(jié)點(diǎn)的特征的直方圖，并且對(duì)于層級(jí)中的每個(gè)節(jié)點(diǎn)，根據(jù)直方圖將具有最低熵的特征分配給該節(jié)點(diǎn)。

附圖說(shuō)明

圖1示出了本公開的計(jì)算系統(tǒng)的一個(gè)實(shí)施例。

圖2示出了包括用于決策樹訓(xùn)練的多個(gè)分層對(duì)象平面的深度圖的示例。

圖3顯示了用于累積特征測(cè)試結(jié)果的非未優(yōu)化策略的示例。

圖4顯示了用于累積特征測(cè)試結(jié)果的優(yōu)化策略的示例。

圖5顯示了用于生成決策樹的方法的實(shí)施例。

圖6顯示了用于增強(qiáng)示例集的信號(hào)強(qiáng)度以降低決策樹中的特征的熵的方法的實(shí)施例。

具體實(shí)施方式

本描述涉及用于決策樹訓(xùn)練的機(jī)器學(xué)習(xí)。更具體地，本描述涉及利用包括多個(gè)圖形處理單元(GPU)的并行處理流水線來(lái)生成決策樹。例如，較繁重的操作或集中占用大部分時(shí)間用于機(jī)器學(xué)習(xí)的操作可由并行處理流水線并行執(zhí)行。此外，具有諸如從同一圖像中選擇的像素之類的共享的屬性的示例可由并行處理流水線的處理塊內(nèi)的GPU并行處理，以便利用被處理塊的各GPU共享的本地存儲(chǔ)器。具體來(lái)說(shuō)，在將累積的結(jié)果寫入全局存儲(chǔ)器之前，對(duì)各示例執(zhí)行的特征測(cè)試的結(jié)果可被累積在本地化的存儲(chǔ)器中。通過(guò)在將累積的結(jié)果寫入較慢的全局存儲(chǔ)器之前將特征測(cè)試結(jié)果累積在較快的本地存儲(chǔ)器中，可減少若干全局存儲(chǔ)器寫入操作。相應(yīng)地，決策樹訓(xùn)練時(shí)間可被顯著地縮短。

此外，在一些應(yīng)用中，基于GPU的并行處理流水線可被實(shí)現(xiàn)在本地化的或非分布式的平臺(tái)中，該平臺(tái)允許單個(gè)機(jī)器以一小部分的成本并以比分布式的基于CPU的計(jì)算設(shè)備群集更高的穩(wěn)定性來(lái)執(zhí)行決策樹訓(xùn)練。在一個(gè)特定示例中，決策樹訓(xùn)練在單個(gè)相對(duì)不昂貴的機(jī)器上執(zhí)行，而不是在遠(yuǎn)程數(shù)據(jù)中心中的大規(guī)模的昂貴的機(jī)器群集上執(zhí)行，因?yàn)楹笳咴诖嬖趩?wèn)題時(shí)非常難以調(diào)試。然而，可以理解的是，一個(gè)或多個(gè)基于GPU的并行處理流水線可被實(shí)現(xiàn)在分布式或聯(lián)網(wǎng)的設(shè)備群集配置中，而不違背本公開的范圍。

圖1示意性地顯示了可被配置成執(zhí)行機(jī)器學(xué)習(xí)操作以生成或訓(xùn)練決策樹的計(jì)算系統(tǒng)100的實(shí)施例。以簡(jiǎn)化形式示出了計(jì)算系統(tǒng)100。在一個(gè)示例中，計(jì)算系統(tǒng)100使用統(tǒng)一計(jì)算設(shè)備架構(gòu)(CUDA)。然而，可以理解，可使用其他計(jì)算機(jī)架構(gòu)而不背離本發(fā)明的范圍。在不同實(shí)施例中，計(jì)算系統(tǒng)100可采用大型計(jì)算機(jī)、服務(wù)器計(jì)算機(jī)、桌面計(jì)算機(jī)等的形式。

計(jì)算系統(tǒng)100可包括邏輯子系統(tǒng)102、數(shù)據(jù)保持子系統(tǒng)104、顯示子系統(tǒng)106和輸入子系統(tǒng)108。計(jì)算系統(tǒng)100可任選地包括未在圖1中示出的其它組件。