修 士 学 位 論 文
題 名
隠 れ マ ル コ フ モ デ ル に よ る 英 文 品 詞 タ グ 付 け のGPUを 用 い た 並 列
化 の 新 手 法
指 導 教 員 福 永 力 教 授
平 成 30年 2月 8日 提 出
首都大学東京大学 院
理 工 学 研 究 科 数 理 情 報 科 学
学修番号16878330
氏 名 藤 森 祐 太
専 攻
学 位論 文 要 旨(修 士(理 学))
論文著者名 藤森 祐太
論 文 題 名 隠 れ マ ル コ フモ デ ル に よ る英 文 品詞 タ グ付 けのGPUを 用 い た並 列 化 の新 手 法
当 研 究 室 で は 現 在 主 に 自 然 言 語 処 理 に 関 す る ア ル ゴ リ ズ ム を 並 列 処 理 す る こ と に よ り高 速 化 す る こ と を 研 究 し て い る 。 自 然 言 語 処 理 と は 、 自 然 言 語 に 対 す る コ ン ピ ュ ー タ 操 作 の こ
と で あ る 。 私 が 現 在 取 り組 ん で い る の は 、 自 然 言 語 処 理 の1つ で あ る 品 詞 タ グ 付 け を 高 速 化 す る こ と で あ る 。 品 詞 タ グ 付 け と は 、 あ る 文 を 構 成 し て い る 各 単 語 に 対 し て 適 切 と推 測 さ れ る 品 詞 の タ グ を 付 与 す る 処 理 の こ と で あ る 。 例 え ば 、
"Iboughtthisbook
."→"1[代 名 詞]bought[動 詞]this[形 容 詞]book[名 詞]."
の よ う な 処 理 を す る こ と で あ る 。 こ の 例 で は 簡 単 の た め 扱 え る 品 詞 を4種 類 に 限 定 し た 。 本 研 究 で は 品 詞 タ グ 付 け をGPUと い う演 算 装 置 を 使 っ て 並 列 化 す る 手 法 を 考 え た 。GPU は 多 数 の 演 算 コ ア を 持 ち 、 並 列 な 演 算 に 特 化 し て い る な ど の 特 徴 が あ る 。 実 装 はCUDAと い うNVIDIA社 のGPUを 使 っ た 並 列 コ ン ピ ュ ー テ ィ ン グ 向 け の 統 合 開 発 環 境 を 使 用 し た 。 CUDAを 使 用 す る 際 に 重 要 な 概 念 と し て 以 下 に 示 す ス レ ッ ド ・ブ ロ ッ ク ・グ リ ッ ド と い う
も の が あ る 。
● ス レ ッ ド:GPU上 の プ ロ グ ラ ム を 実 行 す る 最 小 単 位 。
● ブ ロ ッ ク:何 個 か の ス レ ッ ド を ま と め た も の 。
● グ リ ッ ド:全 て の ブ ロ ッ ク を ま と め た も の 。
ま た 、CUDAで は ス レ ッ ド の 並 列 は 通 常32個 の ま と ま りで 動 作 し 、 こ れ をWarpと 呼 ぶ 。 品 詞 タ グ 付 け は 与 え ら れ た 文 に 対 す る 最 適 な 品 詞 を 推 測 す る 処 理 な の で 、 与 え ら れ た 単 語 列 を κ=(Xl,X2,…JXT)と し 品 詞 タ グ 列 をy=(yl,γ2,...,γT)と す る と 実 際 に 求 め た い の は 以 下 の 式 に な る 。 た だ しyは 可 能 な す べ て の 品 詞 列 の 組 み 合 わ せ の 集 合 で あ る 。
argmaxP(YlX)
y∈Y
こ の 式 の 解 法 の1つ に 隠 れ マ ル コ フ モ デ ル(HiddenMarkovModel;HMM)を 利 用 し た 方 法 が あ る 。HMMと は 観 測 で き な い 隠 れ 状 態 が あ り、 さ ら に マ ル コ フ 性 を 仮 定 し た 確 率 モ デ ル で あ る 。 品 詞 タ グ 付 け の 場 合 、 隠 れ 状 態 は 品 詞 列 、 マ ル コ フ 性 はytはy亡 一1に 、 κtはytの み に 依 存 す る も の と し てHMMを 扱 う。 す る と 求 め る 式 は 次 の よ う に 表 さ れ る 。
・・鷺 ・XP(ylX)一 ・・§器aXロP([y・1y,一,)p(Xtlyt)
HMMに よ る最 適 な ラベ ル 列 の 推 定 を 効 率 よ く求 め るた め に 、 動 的 計 画 法 の 一 種 で あ る Viterbiア ル ゴ リズ ム を使 う方 法 が あ る。Viterbiア ル ゴ リズ ム は 以 下 の 式 を与 え られ た 単 語
列 の最 初 の 単 語 か ら最 後 の 単 語 ま で 、 す べ て の 品 詞)うに 対 して 行 う。
v[t・yj]一 澗 蚤
1{v[t‑1'yi]+1・9(P(yjlyi)p(x・lyj))}
yjは 今 見 て い る 単 語 の 品 詞 を 、 γiは1つ 前 の 単 語 の 品 詞 を 表 す 。v[t,yj]は 亡番 目 の 単 語 の 品
詞 がyjで あ る と した場 合 の 単 語1番 目か ら亡番 目 ま で の 部 分 系 列 の 最 大 値 を表 す 。 ま た 上 式 の 更 新 と 同 時 に最 大 値 を 与 え たy1を 記 録 して お く こ とで 、 亡がTに な る ま で 更 新 し た と き に αrgmαx{v[T,Yj]}を 求 め て そ こ か ら記 録 を 参 照 す る こ と で 品 詞 列 が 求 め ら れ る 。
Viterbiア ル ゴ リズ ム を複 数 の 文 の 集 合 に対 して使 用 す る場 合 に お い て 、CUDAに よ る並 列 化 の 手 法 と して 以 下 の3つ を考 え た 。 た だ し1と2の 手 法 は 当 研 究 室 に在 籍 して い た 日 高 敬 介 が 提 案 した 手 法 で あ る[1]。
‑⊥0乙3
文 並 列:1つ の 文 に 対 す るViterbiア ル ゴ リ ズ ム の 処 理 を1つ の ス レ ッ ドで 行 う手 法 。 ノ・イ ブ リ ッ ド並 列:1つ の ブ ロ ッ ク に1つ の 文 を 対 応 さ せ 、 そ の ブ ロ ッ ク の 中 の1つ の
ス レ ッ ドに1つ の 品 詞yjに お け るv[t,yj]の 更 新 を 行 わ せ る 手 法 。
本 研 究 手 法:1つ の ブ ロ ッ ク に1つ の 品 詞yjを 対 応 さ せ 、 そ の ブ ロ ッ ク の 中 の1つ の ス レ ッ ド に1つ の 文 のv[t,yj]の 更 新 を 行 わ せ る 手 法 。
2,3の 手 法 の イ メ ー ジ 図 を 以 下 に 示 す 。
ハ イ プ リ ツ ド 本研 究手法
口 ・プ・・ク
■ ・スレ・ド
3つ の 並 列 手 法 の 実 行 時 間 を比 較 した グ ラ フ を 以 下 に 示 す 。結 果 と して本 研 究 手 法 が 全 て の 文 の 集 合 に対 して 最 も高 速 に動 作 し た。 ま た逐 次 処 理 よ り約13倍 高 速 に 動 作 した 。 本 研 究 手 法 が 高 速 に 動 作 した 理 由 と して ブ ロ ッ ク の 中 の ス レ ッ ドの数 を32の 倍 数 に設 定 出 来 た
こ とが 挙 げ られ る。
並列手 法 の実行 時間 比較 デ ー タ に 使 用 し た も の は 、 ペ ン シ
arnル バ ニ ア 大 学 発 のPennTreebank
Projectが3年 間 分 の ウ ォ ー ル ス ト
柵 リ ー トジ ャ ー ナ ル 紙 か ら 抜 き 出 し
ZJ;u
l、。
ll{1
■.■.1.ll
?昌
1ス ト ノ タナ イズ
邑 突並 到 ・ノ ノ)ノ1■3昼 案 隼 去
た い く つ か の 記 事 に 対 し て 適 切 な 品 詞 を 付 与 し た も の で あ る 。
No.OO〜No.24の25セ ク シ ョ ン に 分 割 さ れ て い てNo.16〜24セ ク シ ョ ン
を 学 習 デ ー タ にNo.00〜15セ ク シ ョ ン を テ ス トデ ー タ に 使 用 し た 。 サ イ ズ1がNo.00、 サ イ ズ2が No.00‑01、 サ イ ズ4がNo.OO‑03、
サ イ ズ8がNo.OO‑07、 サ イ ズ16が No.OO‑15に 対 応 して い る 。
[1]日 高 敬 介 「英 文 品 詞 タ グ付 け に お け るViterbiア ル ゴ リズ ム のGPUに よ る並 列 化 」 首 都 大 学 東 京 理 工 学 研 究 科 数 理 情 報 科 学 専 攻(2017)
目次
1序 論
1.1 1.2 1.3 2
2.1
研究背景 研究内容 本論文の構成
GPUとCUDA GPU
2.1.1GPU概 要
2.1.2GPUの 構 造 2.2CUDA
2.2.1 2.2.2 2.2.3 2.2.4 2.2.5
CUDA概 要 プ ロ グ ラム 構 造
ス レ ッ ド ・ ブ ロ ッ ク ・ グ リ ッ ド
フリ一モ
ワメ
品 詞 タ グ 付 け 3.2
3.3 4並 列 手 法
3品 詞 タ グ 付 け 、 隠 れ マ ル コ フ モ デ ル 3.1
隠 れ マ ル コ フ モ デ ル Viterbiア ル ゴ リ ズ ム
222223334445567789
4.1文 並 列 4.2
4.3提 案 手 法 5実 験
ハ イ ブ リ ッ ド並 列
5.1
5.2実 行 環 境 5.2.1
5.2.2
5.3結 果 と 考 察
6結 論 ・展 望
748
使 用 した デ ー タ
6.1 6.2
謝 辞
ハ ー ド ウ エ ア ソ フ ト ウ ェ ア
△冊ニゴロ士口糸 望展
参考文献
011467778877888111111111122222
1序 論 1.1研 究 背 景
当 研 究 室 で は 現 在 主 に 自然 言 語 処 理 に 関 す る ア ル ゴ リズ ム を 並 列 処 理 す る こ と に よ り高 速 化 す る こ と を研 究 して い る。自然 言 語 処 理 とは 、自然 言 語 に対 す る コ ン ピ ュ ー タ 操 作 の こ とで あ る。 自然 言 語 と は、人 間 同士 が コ ミュ ニ ケ ー シ ョ ン を と る際 に使 用 され る言 語 の こ とで あ る。自然 言 語 処 理 の 応 用 例 と して 身 近 な もの で は 、翻 訳 ソ フ トや検 索 エ ン ジ ン な どが 挙 げ られ る。 私 が 現 在 取 り組 ん で い るの は 、 自然 言 語 処 理 の1つ で あ る品 詞 タ グ付 け を高 速 化 す る こ とで あ る。品 詞 タ グ付 け と は、あ る文 を構 成 して い る各 単 語 に対 して 適 切 と推 測 され る 品 詞 の タ グ を付 与 す る処 理 の こ とで あ る。 品 詞 タ グ付 け は例 え ば翻 訳 す る際 に利 用 さ れ る。 した が っ て 、品 詞 タ グ 付 け の 高 速 化 が 翻 訳 の 高 速 化 に つ な が る。
品 詞 タ グ付 け を行 う手 法 と して 隠 れ マ ル コ フ モ デ ル と い う確 率 モ デ ル を利 用 す る方 法 が あ る。 ま た 、 隠 れ マ ル コ フ モ デ ル を用 い て 品 詞 タ グ付 け を 行 う際 に 、Viterbiア ル ゴ リズ ム とい う動 的 計 画 法 を利 用 した 効 率 的 な 品 詞 の 推 測 方 法 が あ る。 本 研 究 で は品 詞 タ グ付 け を 隠 れ マ ル コ フ モ デ ル を用 い て 行 い 、 そ の 際 に使 用 す るViterbiア ル ゴ リズ
ム を高 速 化 す る こ と を 目的 とす る。
1.2研 究 内 容
GPUを 使 った 並 列 化 を行 う こ と に よ り、 品 詞 タ グ付 け の 処 理 の 高 速 化 を試 み た 。 本 研 究 の 先 行 研 究 と して 、 当研 究 室 に在 籍 して い た 日高 敬 介 の研 究 が 挙 げ られ る[1]。 日 高 敬 介 が 考 案 した2つ の並 列 手 法 と筆 者 が 本 研 究 で 提 案 した並 列 手 法 の 合 計3手 法 を 実 装 し、 品 詞 タ グ付 け の 実 行 速 度 の比 較 を行 っ た 。
1.3本 論 文 の 構 成
本 論 文 の 構 成 に つ い て 説 明 す る 。2章 で は 、GPU(GraphicsProcessingUnit)とGPU
の 統 合 開 発 環 境 で あ るCUDA(ComputeUnifiedDeviceArchitecture)に つ い て 説 明 す る 。3章 で は 、 品 詞 タ グ 付 け と 隠 れ マ ル コ フ モ デ ル とViterbiア ル ゴ リ ズ ム に つ い て 説 明 す る 。4章 で は 、GPUを 利 用 し た 品 詞 タ グ 付 け の 並 列 化 の 手 法 に つ い て 述 べ る 。5章 で は 、 実 際 に4章 で 述 べ た 並 列 手 法 を 用 い て 品 詞 タ グ 付 け を 行 っ た 結 果 と考 察 を 述 べ る 。
2GPUとCUDA
本 章 で はGPUとCUDAに つ い て 述 べ る[1〜4]。
2.1GPU
こ の 節 で は 主 にGPUに つ い て 述 べ る 。
2.1.1GPU概 要
GPUと は 、 本 来 は グ ラ フ ィ ッ ク ス に 関 連 す る 処 理 の み を 行 う 演 算 装 置 で あ る 。 映 像 の 高 画 質 化 に よ っ て 膨 大 に な っ た グ ラ フ ィ ッ ク ス 処 理 に 対 応 す る た め に 開 発 さ れ た 。 GPUの 特 徴 と し て 、CPUよ り も 多 数 の 演 算 コ ア を 持 つ こ と が 挙 げ ら れ る 。 ま た 画 像 の 各 画 素 に 対 す る 処 理 は 独 立 に 行 え る た め 、 並 列 な 演 算 に 特 化 し て い る の も1つ の 特 徴 で あ る 。 こ れ ら の 特 徴 を 生 か し て 、GPUを グ ラ フ ィ ッ ク ス 処 理 以 外 の 一 般 的 な 用 途 に 利 用 し よ う と い う と い う 試 み の こ と をGPGPU(GeneralPurposecomputingon
GraphicsProcessingUnit)と い う 。
2.1.2
●
GPUの 構 造
GPUの 主 な シ ス テ ム の 概 略 を 説 明 す る た め に 、NVIDIA社 と い う ア メ リ カ 合 衆 国 カ リ フ ォ ル ニ ア 州 サ ン タ ク ラ ラ を 所 在 地 と す る 半 導 体 メ ー カ ー が 作 成 し たGPU を 搭 載 し て い る グ ラ フ ィ ッ ク ボ ー ドの 概 略 図 を 図1と し て 以 下 に 示 す 。 グ ラ フ ィ
ッ ク ボ ー ド にGPUとDRAMが 搭 載 さ れ て お り、GPUの 中 に はGigaThread EngineとSM(StreamingMultiprocessor)が 搭 載 さ れ て い る 。
グ ラ フ ィ ッ ク ボ ー ド
GPU
GigaThreadEngine
DRAM
図1NVIDIAGPUア ー キ テ ク チ ャ の 概 略 図
図1を 構 成 し て い る 各 要 素 の 説 明 を す る 。
●DRAM
メ モ リ 部 分 。 グ ラ フ ィ ッ ク ボ ー ド の 基 板 上 に 設 置 し て あ る 。す べ て のSMか ら ア ク セ ス 可 能 な メ モ リ。
●GigaThreadEngine
処 理 を 各SMに 割 り振 り実 行 さ せ る機 構 。GPUチ ッ プ 内 に 設 置 し て あ る 。
●SM(StreamingMultiprocessor)
計 算 を 行 う プ ロ セ ッ サ 部 分 に 相 当 す る も の 。GPUチ ッ プ 内 に あ る 。SMの 数 は 機 種 に よ っ て 異 な る 。本 研 究 に 使 用 し たGPUで あ るNVIDIAGeForceGTXTITAN
Xで は24個 搭 載 さ れ て い る 。SMの 内 部 構 造 は 主 にCUDAコ ア と レ ジ ス タ と シ ェ ア ー ド メ モ リ か ら構 成 さ れ て お り、CUDAコ ア に つ い て の 説 明 は 以 下 の よ うで あ
る(レ ジ ス タ と シ ェ ア ー ドメ モ リ に つ い て は2.2.5で 説 明 す る)。
◆CUDAコ ア
演 算 装 置 で あ り、計 算 を 行 う 最 小 単 位 。SP(StreamingProcessor)と も 呼 称 さ れ る 。 機 種 に よ っ て1つ のSMに 入 っ て い るCUDAコ ア の 数 が 異 な る 。 本 研 究 に お い て 使 用 し たGPUで あ るNVIDIAGeForceGTXTITANXに は1 個 のSMに128個 のCUDAコ ア が 搭 載 さ れ て い る 。
2.2CUDA
こ の 節 で は 主 にCUDAに つ い て 述 べ る 。
2.2.1CUDA概 要
CUDAと は 、2006年11月 にNVIDIA社 が 発 表 し たGPUを 使 っ た 並 列 コ ン ピ ュ ー テ ィ ン グ 向 け の 統 合 開 発 環 境 で あ る。CUDAはNVIDIA社 自 身 が 開 発 し たGPUに の み 対 応 し て い る 。 ま た プ ロ グ ラ ミ ン グ 言 語 はCやC++やFortranに 対 応 し て い る 。
2.2.2プ ロ グ ラ ム 構 造
CUDAの プ ロ グ ラ ム はCPU側 とGPU側 に 分 け る こ と が で き る 。CPU側 の こ と を ホ ス ト、GPU側 の こ と を デ バ イ ス と 呼 ぶ 。 ま た 、CPUとGPUは そ れ ぞ れ 専 用 の メ モ リ 領 域 を 持 っ て い る の で 、 デ バ イ ス 側 で プ ロ グ ラ ム を 動 作 さ せ る に は 必 要 な デ ー タ を あ ら か じ め ホ ス ト側 か ら 転 送 し て お く必 要 が あ る 。 ま た 、GPUで 実 行 さ れ る プ ロ グ ラ ム を カ ー ネ ル と 呼 び 、 ホ ス ト側 で 起 動 を か け て 、 デ バ イ ス 側 で 動 作 す る 。 カ ー ネ ル は ソ ー ス コ ー ド の 中 で̲910bal̲を つ け て 宣 言 す る 。
CUDAプ ロ グ ラ ム の 一 般 的 な 処 理 の 流 れ は 以 下 の よ う に な る 。
① デ バ イ ス 側 で 使 用 す る デ ー タ の 分 の メ モ リ を あ ら か じ め 確 保 す る 。
② デ ー タ を ホ ス ト メ モ リ か ら デ バ イ ス メ モ リ に 転 送 す る 。
③ カ ー ネ ル を 呼 び 出 し、 デ バ イ ス メ モ リ に 格 納 さ れ て い る デ ー タ を 使 っ て 処 理 を 行 う 。
④ デ ー タ を デ バ イ ス メ モ リ か ら ホ ス トメ モ リ に 転 送 す る 。
⑤ デ バ イ ス メ モ リ を 解 放 す る 。
上 記 の プ ロ グ ラ ム の 流 れ に お い て 、① と② の 処 理 を ホ ス ト側 で 行 い 、③ と④ の 処 理 を デ バ イ ス 側 で 行 い 、⑤ の 処 理 を ホ ス ト側 で 行 う。 こ の よ う にCUDAの プ ロ グ ラ ム はCPU 側 とGPU側 に 分 け て 処 理 を 行 う 。
2.2.3ス レ ッ ド ・ブ ロ ッ ク ・グ リ ッ ド
CUDAで プ ロ グ ラ ミ ン グ す る に あ た り必 要 と な っ て く る概 念 で あ る ス レ ッ ド、 ブ ロ ッ ク 、 グ リ ッ ド に つ い て 説 明 す る 。
● ス レ ツ ド
デ バ イ ス 上 の プ ロ グ ラ ム を 実 行 す る 最 小 単 位 。 各 ス レ ッ ド は 非 同 期 に 動 作 す る 。
● ブ ロ ッ ク
何 個 か の ス レ ッ ド を ま と め た も の 。 何 個 に 設 定 す る か は プ ロ グ ラ ミ ン グ す る 人 が 指 定 す る こ と が で き る 。
● グ リ ッ ド
全 て の ブ ロ ッ ク を ま と め た も の 。 ブ ロ ッ ク の 数 を 何 個 に 設 定 す る か は プ ロ グ ラ ミ ン グ す る 人 が 指 定 す る こ と が で き る 。
ソ フ ト ウ ェ ア とノ・一 ド ウ ェ ア の 対 応 と し て は 、 ス レ ッ ド はCUDAコ ア に 、 ブ ロ ッ ク はSMに 、 グ リ ッ ドは デ バ イ ス に 対 応 し て い る 。 カ ー ネ ル 関 数 を 実 行 す る場 合 は 、 ブ ロ ッ ク 内 の ス レ ッ ドの 数 と グ リ ッ ド 内 の ブ ロ ッ ク の 数 を あ ら か じ め 指 定 し て お く。
2.2.4ワ ー プ
ス レ ッ ド は 並 列 に 動 作 す る と 述 べ た が 、 設 定 し た ス レ ッ ドの す べ て が 並 列 に 動 作 す る の で は な く32ス レ ッ ド毎 に 動 作 す る 。 こ の32ス レ ッ ドの ま と ま り の こ と を ワ ー プ と 言 う。 ブ ロ ッ ク の 中 に 複 数 の ス レ ッ ド を 設 定 し た 場 合 は ワ ー プ 単 位 に 分 割 さ れ て 処 理 さ れ る 。 例 え ば1つ の ブ ロ ッ ク に256個 の ス レ ッ ド を 設 定 し た 場 合 は256/32=8回
に 分 け て 実 行 さ れ る 。 だ か ら ブ ロ ッ ク の 中 の ス レ ッ ドの 数 は32の 倍 数 に な る よ う に 設 定 し た ほ う が 無 駄 な く ス レ ッ ド を 扱 え る 。 ま た 実 際 に プ ロ グ ラ ム を 動 か す と き の イ メ
ー ジ は 図2の よ う に な っ て い る。
1ス レ ツ ド1
1ス レ ツ ド1
一一32ス レ ッ ド
=‑32ス レ ッ ド
図2ワ ー プ の イ メ ー ジ 図
2.2.5メ モ リ
CUDAで は 様 々 な 特 徴 を 持 っ た 多 種 多 様 な メ モ リ を 扱 う こ と が で き る 。 こ こ で は 本 研 究 で 使 用 し た プ ロ グ ラ マ ブ ル な メ モ リ4種 類 の 説 明 を す る 。
● グ ロ ー バ ル メ モ リ
GPUチ ッ プ の 外 部 のDRAM内 に あ り、 す べ て の ス レ ッ ドか ら ア ク セ ス す る こ と が で き る メ モ リ 空 間 。 ア ク セ ス 速 度 は 遅 い 。
● コ ン ス タ ン トメ モ リ
GPUチ ッ プ の 外 部 のDRAM内 に あ り、 す べ て の ス レ ッ ドか ら ア ク セ ス す る こ と が で き る 読 み 込 み 専 用 の メ モ リ 空 間 。 キ ャ ッ シ ュ が 効 く た め 、 グ ロ ー バ ル メ モ リ よ
り も 高 速 に ア ク セ ス で き る 。 ソ ー ス コ ー ドの 中 で̲constant̲と 宣 言 し て 利 用 す る 。
● シ ェ ア ー ド メ モ リ
GPUチ ッ プ 内 に あ り、 各SMに 割 り当 て ら れ て い る メ モ リ空 間 。 高 速 に ア ク セ ス で き 、 ブ ロ ッ ク 内 の ス レ ッ ド の デ ー タ 共 有 に 使 用 さ れ る 。
● レ ジ ス タ
GPUチ ッ プ 内 に あ り、 各 ス レ ッ ド に 割 り 当 て ら れ て い る メ モ リ空 間 。CUDAコ ア に 最 も 近 い と こ ろ に 配 置 さ れ て い る た め 、 最 も 高 速 に ア ク セ ス す る こ と が で き る 。 カ ー ネ ル 関 数 で 使 用 す る 変 数 の た め の 領 域 と し て 利 用 す る 。 各 ス レ ッ ド で 独 立 な の で 共 有 は で き な い 。
CUDAを 通 し て 見 え る メ モ リ の 階 層 構 造 の 概 略 図 を 図3と し て 以 下 に 示 す 。
ホ ス ト
グ リ ッ ド
ブ ロ ッ ク
ス レ ツ ド ス レ ツ ド
ブ ロ ッ ク
シ ェ ア ー ドメ モ リ
レ ジス タ
曹
レジ ス タ
‡ ス レ ツ ド ス レ ツ ド
凸 L」
…
L4L
ブ ロ ッ ク
シ ェ ア ー ドメ モ リ
レジ ス タ レジ ス タ
ス レ ツ ド ス レ ツ ド
グ ロ ー バ ル メ モ リ
コ ン ス タ ン トメ モ リ
図3CUDAメ モ リ階 層 概 略 図([1]よ り引 用)
3品 詞 タ グ 付 け 、 隠 れ マ ル コ フ モ デ ル
本 章 で は 品 詞 タ グ付 け と隠 れ マ ル コ フモ デ ル につ い て述 べ る[5][6]。
3.1品 詞 タ グ 付 け
品 詞 タ グ 付 け と は 、 あ る 文 を 構 成 し て い る 各 単 語 に 品 詞 の タ グ を 付 与 す る 処 理 の こ と で あ る 。 例 え ば 、
̀̀Iboughtthisbook."
と い う 英 文 の 入 力 に 対 して
"1[代 名 詞]b
ought[動 詞]this[形 容 詞]book[名 詞]."
の よ う な 処 理 を す る こ と で あ る 。 こ の 例 で は 簡 単 の た め 扱 え る 品 詞 を 名 詞 、 代 名 詞 、動 詞 、 形 容 詞 の4種 類 に 限 定 し た 。
品 詞 タ グ 付 け は 系 列 ラ ベ リ ン グ 問 題 の1種 で あ る。系 列 ラ ベ リ ン グ 問 題 と は 、系 列 と 呼 ば れ る い く つ か の 要 素 が 並 べ ら れ た も の が 与 え ら れ た 時 に 、 そ れ に 最 適 な ラ ベ ル 列
を 予 測 す る 問 題 で あ る 。 品 詞 タ グ 付 け の 場 合 、 系 列 が 単 語 列 、 ラ ベ ル 列 が 品 詞 タ グ 列 に あ た る 。
こ こ で 、"Iboughtthisbook."の"book"に つ い て 考 え る 。 こ の 英 文 で は"book"が 名 詞 と し て 登 場 し て い る の は 、直 前 の 単 語 の 品 詞 が 形 容 詞 で あ る こ と が 関 係 し て い る 。 も し 仮 に 直 前 の 単 語 の 品 詞 が 名 詞 で あ っ た 場 合 は 動 詞 に な る 可 能 性 が 高 く な る と 思 わ れ る 。
こ の よ う に あ る 単 語 の 品 詞 は 直 前 の 単 語 の 品 詞 に 依 存 し て い る 。 次 の 節 で 説 明 す る 隠
れ マ ル コ フモ デ ル は この よ うな依 存 関 係 を考 慮 した モ デ ル に な っ て い る。
3.2隠 れ マ ル コ フ モ デ ル
系 列 ラ ベ リ ン グ 問 題 の 解 法 の1つ に 隠 れ マ ル コ フ モ デ ル(HiddenMarkovModel)
[5][6]を 利 用 し た 方 法 が あ る 。 簡 単 の た め こ れ 以 降 隠 れ マ ル コ フ モ デ ル はHMMと 表 記 す る 。HMMは 隠 れ 状 態 を 持 ち 、 さ ら に マ ル コ フ 性 を 仮 定 し た 確 率 モ デ ル で あ る 。 隠 れ 状 態 と は 観 測 で き な い 状 態 の こ と で あ り、 品 詞 タ グ 付 け に お い て は 品 詞 列 に 相 当 す る 。 ま た マ ル コ フ 性 と は 、 将 来 の 事 象 が 現 在 状 態 に だ け 依 存 して お り、過 去 の 状 態 に は 依 存 し な い 特 性 の こ と で あ る 。
HMMを 品 詞 タ グ 付 け に 利 用 す る 場 合 を 考 え る 。 系 列 に あ た る 単 語 列 をxニ (Xl,X2,…,XT)と し 、 ラ ベ ル 列 に 当 た る 品 詞 タ グ 列 をyニ(yl,γ2,...,yT)と す る 。 マ ル コ フ 性 よ り、 γtはγt‑1に 、 κtはγtの み に 依 存 し て 決 ま る と 仮 定 す る 。 す る とπとγの 同 時 確 率 P(x,y)は 次 の よ う に 表 さ れ る;
P(x,y)ニP(xTIYT)P(γTly,̲1)...P(xi1Yi)P(γ,1y,) ニHZ .,P(Xtlyt)P(iyt1γt̲1)...(A).
簡 単 の た め 、 品 詞 タ グ 列 の 左 端 に ス タ ー ト地 点 を 意 味 す る 特 別 な 変 数 γoが あ る と仮 定 し た 。
実 際 にHMMを 使 っ て 品 詞 タ グ 付 け を 行 う の に は2つ の ス テ ッ プ が あ る 。1つ 目 は パ ラ メ ー タ を 推 定 す る ス テ ッ プ で あ る 。 パ ラ メ ー タ と は 式(A)のP(Xt1γt)とP(yt1γt ‑1)の
こ と で あ る 。P(Xtlyt)の こ と を 出 現 確 率 、P(iyt1γt‑1)の こ と を 遷 移 確 率 と 呼 ぶ 。 こ れ ら の パ ラ メ ー タ は 、 あ ら か じ め 単 語 列 に 対 し て 適 切 な 品 詞 タ グ 列 が 付 与 さ れ て い る 文 の 集 合 で あ る 訓 練 デ ー タ に 以 下 の 式 を 適 用 し て 推 定 さ れ る;
P([y・1γi‑・)一脳 讐 雛 憲 回摯
P(x・1yi)‑yiで あ鍔 錨 現回竺
2つ 目 の ス テ ッ プ は 復 号 化 の ス テ ッ プ で あ る。 復 号 化 と は 、 新 た な 単 語 列xが 与 え ら れ た と き に1つ 目 の ス テ ッ プ で 学 習 し たHMMの モ デ ル を 用 い て 品 詞 タ グ 列 を 推 測 す る こ と で あ る 。 こ れ はP(ylx)を 最 大 に す る 品 詞 タ グ 列yを 求 め る こ と、 つ ま り
argmaxP(YIX)
y∈y
を 求 め る こ と に 相 当 す る 。 た だ し、Yは 可 能 な す べ て の 品 詞 列 の 組 み 合 わ せ の 集 合 を 表 し 、argmaxは こ の 式 に お い て はP(γlx)の 値 を 最 人 に す るyの 要 素yを 表 す 。 こ こ で ベ イ
γ∈Y
ズ の 定 理 を 使 う と、 上 式 の 条 件 付 き 確 率 は
P(x,γ) P(ylx)ニP(
x)
と な り、 ま たP(x)はyと は 関 係 が な い こ と を 考 慮 す る と、 実 際 は argmaxP(X,y)
y∈y
を 求 め る こ と に な る 。 こ の 同 時 確 率 は1つ 目 の ス テ ッ プ で 学 習 し た パ ラ メ ー タ を 利 用 し て 求 め る こ と が 出 来 る 。
3.3Viterbiア ル ゴ リズ ム
3.2節 で 説 明 した復 号 化 を そ の ま ま直 接 計 算 して 求 め るの は あ ま り現 実 的 で は な い。
な ぜ な ら可 能 な 品 詞 タ グ列 の 数 が 膨 大 だ か らで あ る。例 え ば、本 研 究 で 用 い た 品 詞 の種 類 数 は45※ で あ るの で 、 仮 に与 え られ た単 語 列 の単 語 の 数 が10個 で あ った とす る とタ グ付 けす る こ とが 可 能 な 品 詞 タ グ列 は4510に な っ て しま う。そ こで 復 号 化 の 計 算 を 効 率 的 に行 うア ル ゴ リズ ム が 必 要 に な っ て く る。
そ の 問 題 を解 決 す る方 法 と して 、Viterbiア ル ゴ リズ ム[5][6]を 復 号 化 に利 用 す る方 法 が あ る。Viterbiア ル ゴ リズ ム は動 的 計 画 法 の一 種 で あ り、HMMに よ る最 も確 率 が 高 い ラベ ル 列 の 推 定 を効 率 よ く行 う こ とが で き る。Viterbiア ル ゴ リズ ム は2つ の ス テ
ッ プ か ら構 成 され て い る。
1つ 目 の ス テ ップ で は 、以 下 の 式 を入 力 系 列 の 最 初 の 単 語 か ら最 後 の 単 語 ま で 、す べ て の 品 詞 に 対 して 計 算 す る。
v[t・yj]一 罵{v[亡 一1・ γi]+1・9(P(yjlγi)p(x・1yj))}…(B) hp[t・yj]一 駕x{"[亡 一 ・・yi]+1・9(P(yjlγi)p(・ ・1yj))}…(c)
亡は入 力 系 列 の 何 番 目 の 単 語 か を 表 す 。yjは 今 見 て い る単 語 の 品詞 を表 す 。 γiは1つ 前 の 単 語 の 品 詞 を 表 す 。v[t,yj]は 亡番 目 の 単 語 の 品 詞 がyjで あ る と し た 場 合 の 、 単 語1番 目 か らt番 目 ま で の 部 分 系 列 の 最 大 値 を 表 す 。bp[t,yj]はv[t,yj]を 最 大 に す る 品 詞 γiを保 存 す る た め の も の で あ る 。1つ 目 の ス テ ッ プ の イ メ ー ジ を 図4で 示 す 。
1[名 詞]
緊,ノ で・,ゲ
∵、 ∵ 11,
bought[名 詞]
婦轍 this[名 詞] 擬 妻 book[名 詞]
1[代 名 詞]
、‑l!
ぐ?' 父,'
,数 塀
響謄1
￡/ ・装
v[4,名 詞]
=‑0 .5
・・月bought[代 名 詞]調 ・
1[動 詞] bought[動 詞]
働 グ
撫
んthis[代 名 詞]1≒,'
い,'f'
＼)く、' '〜'、'
〃'1へ
縦1 ,'獄
"/'・1 7"
book[代 名 詞]
∵ ン' 分'戴
〃 遠
v[4,代 名 詞]
=‑3 .0
this[動 詞]
1[形 容 詞]
book[動 詞] v[4,動 詞]
=‑1 .5
bought[形 容 詞]… 一一this[形 容 詞]「 一一一一一book[形 容 詞] v[4,形 容 詞]
=‑8 .0
図41つ 目 の ス テ ッ プ の イ メ ー ジ 図 。 左 か ら右 へ 進 む 。
※ 実 験 に 使 用 し た コ ー パ ス は、 ペ ン シ ル バ ニ ア 大 学 発 のPennTreebankProjectが 作 成 し た も の で あ り、 こ の コ ー パ ス が 品 詞 の 種 類 数45で 品 詞 タ グ 付 け が さ れ て い た 。
図4に つ い て 説 明 す る。 図4に お け る細 い 実 線 の矢 印 は式(C)を 計 算 した 結 果 得 られ た bp[t,yj】 に 格 納 さ れ て い る 品 詞 γ̀を示 し て る 。 点 線 の 矢 印 は 、 式(C)の 計 算 の と き の 比 較 対 象 の 品 詞 す べ て を 表 し て い る 。 例 え ば 、 細 い 実 線 の 矢 印 が1[名 詞]を 始 点 と し て bought[代 名 詞]を 終 点 と し て 描 か れ て い る と い う こ と は 、 式(C)を 計 算 し た 結 果 得 ら れ た 品 詞 が 名 言司・つ ま りhp[2,代 名 言司1一 名 詞 を 表 し て い る こ と に な る(t‑2な の はb・ught が2番 目の 単 語 だ か らで あ る)。 ま た 太 い 実 線 の矢 印 の 先 に あ る数 値 は、 最 後 の 単 語 に 対 して 式(B)を 適 用 した 結 果 の 具 体 的 な数 値 を表 して い る。
2つ 目 の ス テ ップ で は 、 以 下 の 式 を す べ て の 品 詞yjに 対 して 行 う。
γTニargmαx{v[T,γ1]}
Tは 入 力 系 列 の 最 後 の 単 語 の 位 置 を 表 す 。 γTはTの 位 置 に あ る 単 語 に タ グ 付 け し た 品 詞 を 表 す 。 こ の 式 を 使 っ て 、 文 全 体 の 系 列 の 中 で 一 番 大 き い 値 を 持 つ 品 詞 を 求 め る 。 次 に 以 下 の 式 をtニT‑1,T‑2,…,1に 対 して 適 用 す る こ と で す べ て の 位 置 の 単 語 の 品 詞 を 求 め る 。
γ亡二bp[t,yt+1]
2つ 目 の ス テ ッ プ の イ メ ー ジ を 図5で 示 す 。赤 線 が 計 算 の 結 果 推 定 さ れ た 品 詞 列 を 表 し て い る 。
1[名 詞]
薫 … 彦 bought[名 詞] this[名 詞] 、book[名 詞]■ ■ レ v[4,名=‑0 詞]
蓼 「 一フ .5
翌＼ 為
発x滋 1[代 名 詞]
泌
、鱗
、',、 レ
bought[代 名 詞]
ト
球轍繍 細1撫蟹
り ≒ ・7
this[代 名 詞] book[代 名 詞]■ ⇒ v[4,代=‑3名 詞]
liヨ1 .0
熟
ノ1ぐ1
、 犠"
〃みハ識
7奪
父 1[動 詞] k一林 ヤフ bought[動 詞] this[動 詞] 6二騒テ
' book[動 詞]̲ v[4勧 詞]
ニ ー1.5
黙AGA 〃L̲̲一̲一ゐ獄プ 、覧
L蚤鯨
＼
1[形 容 詞] P, bought[形 容 詞] this[形 容 詞] book[形 容 詞]̲̲7 L v[4形=‑8容 詞]
.0
畢
1[代 名 詞]bought[動 詞]this[形 容 詞]book[名 詞].
図52つ 目 の ス テ ッ プ の イ メ ー ジ 図 。 右 か ら左 へ 進 む 。
4並 列 手 法
本 章 で はViterbiア ル ゴ リズ ム のCUDAに よ る並 列 化 の 手 法 を 説 明 す る。た だ し4.1 で 説 明 す る文 並 列 と4.2で 説 明 す るハ イ ブ リ ッ ド並 列 は 当 研 究 室 に在 籍 して い た 日高
敬 介 が 提 案 した 手 法 で あ る。 詳 し くは[1]を 参 照 。
4.1文 並 列
文 並 列 で は 、1つ の 文 に 対 す るViterbiア ル ゴ リ ズ ム の 処 理 をCUDAの1つ の ス レ ッ ドで 行 う手 法 で あ る 。 こ れ は 、各 文 は 独 立 で あ る と い う文 の 独 立 性 を 利 用 し た 手 法 で あ る 。
ま た2.2.2節 で 説 明 し た よ う に 、CUDAを 使 う場 合 は あ ら か じ め デ バ イ ス メ モ リ の 確 保 や デ バ イ ス 上 で の 計 算 に 必 要 な デ ー タ を デ バ イ ス 側 に 転 送 し て お く必 要 が あ る 。 3.3節 で 説 明 し たViterbiア ル ゴ リ ズ ム の 式 に 従 う と、 確 保 し て お くべ き 変 数 と し て バ ッ ク ポ イ ン タhpが あ り、 転 送 す べ き デ ー タ と し て 入 力 系 列xと 遷 移 確 率P(yj1γi)と 出 現 確 率P(Xtlyj)が あ る 。CUDAを 使 っ て 文 並 列 を 行 う際 に は そ れ ぞ れ の 変 数 を 以 下 の 表1
に 示 す よ う に 配 置 し た 。
表1文 並 列 の メ モ リ配 置
遷 移確 率 出現確 率 入 力 系 列
バ ックポ イ ン タ
コ ン ス タ ン トメ モ リ グ ロ ー バ ル メ モ リ グ ロ ー バ ル メ モ リ グ ロ ー バ ル メ モ リ
4.2ハ イ ブ リ ッ ド並 列
ハ ・fブリ ッ ド並 列 は 文 の 独 立 性 に加 えて 品 詞 の独 立 性 を利 用 した 並 列 手 法 で あ る。
品 詞 の独 立 性 につ い て 説 明 す る た め に以 下 の擬 似 コ ー ドを示 す 。
for(t‑1;t<入 力 系 列 長;t++) for(j‑0;j<品 詞 種 類 数;j++)
for(i‑0;i〈 品 詞 種 類 数;i++) 最 大 値 を 更 新;
こ の コ ー ド はViterbiア ル ゴ リ ズ ム の1つ 目 の ス テ ッ プ を 簡 略 化 し た も の で あ る 。1つ 目 のfor文 は 入 力 系 列 の ど の 位 置 の 単 語 か を 決 定 す る も の で あ る 。2つ 目 のfor文 は 今 見 て い る 位 置 の 単 語 の 品 詞 を 決 定 す る も の で あ る 。3つ 目 のfor文 は 今 見 て い る 位 置 の 単 語 の1つ 前 の 位 置 の 単 語 の 品 詞 を 決 定 す る も の で あ る 。 品 詞 の 独 立 性 と は 、 こ の コ ー ドに お け る2つ 目 のfor文 の 処 理 は 並 列 処 理 の 観 点 か ら独 立 に 行 え る と い う も の で
あ る。 こ の 品 詞 の 独 立 性 を 以 下 の 図6に 示 す 。
ll[名 詞]1… 一"bought[名 言司]
//
ll[動 詞]1'"'
'ノ'
ll[形容 詞]1
ll[代 名 詞]1
⇒l
l[動詞]匠
''
ll[升多容 言司]1'
bought[代 名 詞]
"
⇒
ll[名 詞]k 、
Il[動 詞]ト ー⇒b・ught[動 詞]
ll[形 容 詞]ト"
ll[名 詞]k 、
、
、
oL[代 名言司]ド:
ん
・＼ ll[動 言司]ト 、、 ＼こ＼ 愚＼
'・ミ
1[升多容 言司] bought[形 容 詞]
一
こ の順 番 で 行 わ な くて も、 各 品 詞 ご と に独 立 に 求 め る こ と が 出 来 る 図6:Viterbiア ル ゴ リズ ム に お け る 品 詞 の 独 立 性図6に つ い て 説 明 す る 。 こ の 図 は 第3.3節 の 図4に お け る"1"と"bought"の 間 に 行 わ れ る 処 理 を 表 し て い る 。 細 い 実 線 の 矢 印 は 、 図4と 同 じ で3.3の 式(C)を 計 算 し た 結 果 得 ら れ たhp[t,yj]に 格 納 さ れ て い る 品 詞 γtを表 し て い る 。 点 線 の 矢 印 は 、 式(C)の 計 算 の と き の 比 較 対 象 の 品 詞 す べ て を 表 し て い る 。 式(C)に よ っ て 、 最 大 と な るγごを 求 め る 計 算 、 つ ま り、 こ の 細 い 実 線 と 点 線 の4本 の 中 か ら 細 い 実 線 を 求 め る 計 算 を して い る 。 そ し て 、 本 来 な ら ば 太 い 実 線 の 矢 印 の 順 番 に し た が っ て 、 つ ま りbought[名 詞]→
bought[代 名 詞]→bought[動 詞]→bought[形 容 詞]の 順 で 、そ れ ぞ れ の 品 詞 に 対 す る細 い 実 線 を 求 め る 計 算 を 式(C)に し た が っ て 行 う が 、 こ の 処 理 は 各 品 詞 で 独 立 に 行 え る と い う の がViterbiア ル ゴ リ ズ ム に お け る 品 詞 の 独 立Jl生で あ る 。 こ の 計 算 は 太 い 実 線 の 矢 印 の 前 後 で 独 立 し て お り、 太 い 実 線 の 矢 印 の 前 で 計 算 し た 結 果 が 次 の 計 算 に 影 響 を 及 ぼ す こ と は な い 。 し た が っ て 、太 い 実 線 の 矢 印 の 順 番 通 り に 計 算 し な くて も正 常 な 数 値 を 得 る こ と が で き る 。
ハ イ ブ リ ッ ド並 列 と は 、2つ の 独 立 性 を 利 用 し て 、1つ の ブ ロ ッ ク に1つ の 文 を 対 応 さ せ 、 そ の ブ ロ ッ ク の 中 の1つ の ス レ ッ ド に1つ の 品 詞yjに お け るv[t,yj]の 更 新 を 行 わ せ る 手 法 で あ る 。 ハ イ ブ リ ッ ド並 列 の イ メ ー ジ を 以 下 の 図7に 示 す 。
ハ イ ブ リ ッ ド並 列
[=]:ブ ・ック ス レ ツ ド
図7ハ イ ブ リ ッ ド並 列 の イ メ ー ジ 図
CUDAを 使 っ て ノ・イ ブ リ ッ ド並 列 を 行 う際 に は 注 意 点 が あ る 。 そ れ は1つ の 文 に 関 わ る 処 理 を 複 数 の ス レ ッ ドで 行 う こ と に な る の で 、変 数"匡)・j]が 複 数 の ス レ ッ ド で 共 有 の 変 数 に な っ た こ と で あ る 。 そ の 結 果 、v[t,yj]に 対 し て 各 ス レ ッ ド が 値 を 更 新 す る処 理 と値 を 読 み 込 む 処 理 の 両 方 を行 う こ と に な っ た 。つ ま り、各 ス レ ッ ドは そ れ ぞ れ 非 同 期 に 動 くた め デ ー タ競 合 が 起 こ る可 能 性 が あ る。 そ こ で 共 有 して い る変 数 に対 す る書 き 込 み と読 み 取 りの タ イ ミ ン グ を ブ ロ ッ ク内 の ス レ ッ ド問 で 合 わ せ る 同 期 の処 理 が 必 要 に な る 。 こ の 問 題 を 解 決 す る た め に 、 シ ェ ア ー ドメ モ リ に 共 有 変 数 で あ るv[t,yj]を 配 置 し 、CUDAの ブ ロ ッ ク 内 バ リ ア 関 数 で あ る̲syncthreadsOを シ ェ ア ー ドメ モ リ の 変 数 更 新 の 前 後 に 用 い る 。 シ ェ ア ー ド メ モ リ の 使 用 例 を 以 下 に 示 す 。
処 理1
̲syncthreadsO;
処 理2
処 理2を 行 う前 に 処 理1が 対 象 の ブ ロ ッ ク の 中 の 全 ス レ ッ ド で 終 了 し て い る 必 要 が あ る 場 合 に 、 こ の よ う に̲syncthreadsOを 使 う こ と で ブ ロ ッ ク の 中 の 全 ス レ ッ ドで 同 期 を 取 る こ と が 出 来 る 。 ノ・イ ブ リ ッ ド並 列 を 使 う と き は 、 従 来 のViterbiア ル ゴ リ ズ ム 内 のv[t,yj]の 更 新 と 読 込 の 処 理 の 問 に ̲syncthreadsOを 挿 入 す る こ と で ス レ ッ ド問 の 同 期 を実 現 で き る。
ま た 、・・イ ブ リ ッ ド並 列 をCUDAで 使 う場 合 の 各 変 数 の メ モ リ配 置 は 以 下 の表2に 従 う。 文 並 列 と 同 様 の メ モ リ配 置 に 加 え て シ ェ ア ー ド メ モ リ に"[ち)ヶ]を 配 置 し て い る 。
表2:ハ イ ブ リ ッ ド並 列 の メ モ リ配 置
変 数 遷移 確 率
出現確 率 入 力 系 列
バ ックポ イ ンタ
V
メ モ リ
コ ン ス タ ン トメ モ リ グ ロ ー バ ル メ モ リ グ ロ ー バ ル メ モ リ グ ロ ー バ ル メ モ リ シ ェ ア ー ドメ モ リ
4.3提 案 手 法
提 案 手 法 は 、 ハ イ ブ リ ッ ド並 列 に お い て 各 ス レ ッ ドが 行 っ て い る 処 理 と 同 じ処 理 を ス レ ッ ド に 行 わ せ る が 、 そ の ス レ ッ ド の 配 置 を 変 更 し た も の で あ る 。ハ イ ブ リ ッ ド並 列 で は 、 ブ ロ ッ ク に1つ の 文 を 対 応 さ せ 、 そ の ブ ロ ッ ク の 中 の ス レ ッ ドの1つ に 品 詞 を1 つ 対 応 さ せ て い た 。 提 案 手 法 で は 、1つ の ブ ロ ッ ク に1つ の 品 詞 を 対 応 さ せ 、 そ の 中 の ス レ ッ ドの1つ に 文 を1つ 対 応 さ せ て い る 。ハ イ ブ リ ッ ド並 列 と の 対 比 図 を 以 下 の 図8 に 示 す 。
ハ イ ブ リ ッ ド並 列 提 案手 法
文1
団
■囲■圏
団
■匪國圏 圏
■匪■国
[=コ ・ブ・ック ⊂=】 ・スレッド 図8:提 案 手 法 の イ メ ー ジ 図
ハ イ ブ リ ッ ド並 列 と の 相 違 点 と し て 、v[t ,yj]の 処 理 の 仕 方 が変 わ っ て い る。ハ イ ブ リ
ッ ド並 列 で は 、"匡)ウ]は 各 ブ ロ ッ ク の 中 で の ス レ ッ ドの 問 で の 共 有 変 数 で あ っ た が 、提 案 手 法 で は各 ブ ロ ッ ク を ま た い だ ス レ ッ ドの 問 で の 共 有 変 数 に な っ て い る。 そ れ に 伴 い 、各 変 数 の配 置 の 仕 方 、各 ス レ ッ ドで の 同 期 の 取 り方 が 変 わ っ て い る。ハ イ ブ リ ッ ド 並 列 で はv[t,yj]は シ ェ ア ー ドメ モ リ に 配 置 し て い た が 、提 案 手 法 で はv[t,yj]は ブ ロ ッ ク
を ま た い で の 共 有 変 数 な の で グ ロ ー バ ル メ モ リ に 配 置 す る こ と に な る 。 ま た ハ イ ブ リ ッ ド 並 列 で は ブ ロ ッ ク 内 の ス レ ッ ド の 同 期 を ブ ロ ッ ク 内 バ リ ア 関 数 で あ る
̲̲syncthreadsOを 使 っ て と っ て い た が 、 提 案 手 法 で は ブ ロ ッ ク を ま た い で の ス レ ッ ド の 同 期 を 取 る 必 要 が あ る が 、 そ れ を 可 能 とす る バ リ ア 関 数 が 提 供 さ れ て い な い 。 。 そ こ で 、提 案 手 法 の カ ー ネ ル 関 数 を1つ の 単 語 が 進 む た び に 終 了 さ せ る こ と と 、v[亡,yj]を 更 新 用 と読 込 用 の2つ 用 意 す る こ とで 同 期 を と って い る。
実 際 に ど の よ う に して 同期 を と っ て い る か を以 下 に説 明 す る。1つ 目 の 変 更 と して 、 以 下 の 擬 似 コ ー ドの よ うに、単 語 の位 置 に 関 す るfor文 の 中 に提 案 手 法 の カ ー ネ ル 関 数
を 入 れ て 単 語 の 位 置 が1つ 進 む た び に カ ー ネ ル 関数 を 終 了 させ る よ うに す る。 な お 、 for文 のtは 入 力 系 列 の文 の 中 で 最 大 の 単 語 数 を もつ もの に 合 わ せ て 設 定 す る。 入 力 系 列 の 中 で 最 大 の 単 語 数 を 最 大 入 力 系 列 長 と呼 称 す る。
for(t‑1;t<最 大 入 力 系 列 長;t++) /*提 案 手 法 開 始*/
提 案 手 法(t) /*提 案 手 法 終 了*/
図8の 文1を 例 と す る と 、 同 期 を と る べ き ス レ ッ ド は 、 名 詞 を 担 当 し て い る ブ ロ ッ ク の 文1、 代 名 詞 を 担 当 し て い る別 の ブ ロ ッ ク の 文1、 形 容 詞 を 担 当 し て い る さ ら に 別 の ブ ロ ッ ク の 文1、 お よ び 動 詞 を 担 当 し て い る4番 目 の ブ ロ ッ ク の 文1の 計4つ に な る 。 そ こ で 、 こ の 擬 似 コ ー ドの よ う に 次 の 単 語 へ と進 む と き に カ ー ネ ル 関 数 を 終 了 さ せ る こ と に よ り、 ブ ロ ッ ク を ま た い で 配 置 さ れ て い る文1の 問 で の バ リ ア 関 数 と 同 じ機 能 を 実 現 し て い る 。つ ま り、 あ る ス レ ッ ド が 今 見 て い る 位 置 の 単 語 に 関 す る 更 新 が 終 わ っ た と し て も 、次 の 位 置 の 単 語 に は 進 ま せ ず 、他 の す べ て 別 ブ ロ ッ ク に あ る ス レ ッ ドの 更 新 処 理 が 終 わ る ま で 待 機 さ せ る 。 こ れ に よ り、例 え ば 名 詞 を 担 当 し て い る ブ ロ ッ ク の 文
1が2番 目 の 単 語 の 処 理 を 行 っ て い る の に 、 代 名 詞 を 担 当 し て い る ブ ロ ッ ク の 文1が3 番 目 の 単 語 の 処 理 を し て い る と い う状 況 に な ら な い よ う に し て い る 。 こ の よ う に す る
こ と で 、 ブ ロ ッ ク を ま た い だ ス レ ッ ド の 間 で 共 有 し て い る 文 す べ て 、 例 え ば 図8に お け る 文1の み な ら ず 文2、 文3、 文4に お い て も 、 見 て い る 単 語 の 位 置 を 合 わ せ る こ と が で き る 。
ま た 、1つ 目 の 変 更 に 加 え て2つ 目 の 変 更 と し て 、v[t,yj]と 同 じ 役 割 を 果 た す 変 数 vn[t,yj]を 用 意 し て 、 部 分 系 列 の 最 大 値 の 更 新 式 を 以 下 の よ う に 変 更 す る 。
V[t・yj]一 羅{vn[亡 一 ・・lyi]+1・9偽1γ ∂P(κ ・1切}(亡 が 奇 数 の 胎) vn[t・yj]一 羅{り[t‑・ ・yi]+1・9(P(yjly・)P(・ ・lyj))}(亡が 騰 の 場 合)
亡が 奇 数 で あ る か 偶 数 で あ る か に よ っ てv[t,yj]とvn[t,yj】 が 更 新 用 と 読 み 込 み 用 の 役 割 を 入 れ 替 え る よ う に し て い る 。 例 え ぼ 亡が 偶 数 の と き に は ワ[亡,)引の 値 を も と に し て 更 新 を し て 、vn[t,yj]に そ の 更 新 結 果 を 書 き 込 み 、 亡が 奇 数 の と き に は 逆 にvn[亡,yj]の 値 を も と に し て 更 新 を し て 、v[t,yj]に そ の 更 新 結 果 を 書 き 込 む よ う に し て い る 。v[t,yj]を 更 新 用 と読 み 込 み 用 の2つ に し た 理 由 は 、 更 新 後 のv[t,yj]の 値 を 読 み 込 む ス レ ッ ド を 無 く す た め で あ る。各 ス レ ッ ドは非 同 期 に動 作 す る の で 、あ る ス レ ッ ドが更 新 の 処 理 を 終 え た 後 に読 込 を 開 始 す るス レ ッ ドが 存 在 す る場 合 が あ る 。 そ の よ う な場 合 に も処 理 結 果 に 間 違 い が 起 こ ら な い よ う に す る 必 要 が あ る 。 そ の た め に は 、v[t,yj]は1つ で は 不 十 分 で あ り、2つ 用 い る こ と で 対 処 し た 。 ま た そ の よ う な 問 題 へ の 対 応 と し て は 、 読 み 込 む 文 の 単 語 の 長 さ と 同 じ数 の レ[亡,)ヶ】を 用 意 し て も十 分 で あ る が 、メ モ リ の 節 約 の た め に 最 低 限 の2つ に し た 。
以 上 の よ う に 、 カ ー ネ ル 関 数 を 単 語 の 位 置 が 進 む た び に 終 了 さ せ る こ と と、v[t,yj]を 更 新 用 と読 み 込 み 用 の2つ 用 意 す る こ と で 、 ブ ロ ッ ク を ま た い だ ス レ ッ ドの 問 で 同 期
を と る こ と が 実 現 で き る 。 ま た 提 案 手 法 の 場 合 、 各 変 数 の メ モ リ配 置 は 以 下 の 表3の よ う に な る 。vn[t,yj]が 新 た な 変 数 と し て 追 加 さ れ 、v[t,yj]とvn[t,yj】 を グ ロ ー バ ル メ モ リ に 配 置 し て い る 。
表3提 案 手 法 の メ モ リ配 置
遷 移確 率 出現確 率 入力 系列
バ ックポ イ ンタ
V vn
コ ン ス タ ン トメ モ リ グ ロ ー バ ル メ モ リ グ ロ ー バ ル メ モ リ グ ロ ー バ ル メ モ リ グ ロ ー バ ル メ モ リ グ ロ ・一 バ ル メ モ リ
5実 験
本 章 で は 、HMM及 びViterbiア ル ゴ リ ズ ム を 利 用 し た 品 詞 タ グ 付 け の 実 行 時 間 を 1:逐 次 処 理 、2:文 並 列 、3:ノ ・イ ブ リ ッ ド並 列 、4:提 案 手 法
の4つ の 手 法 で 比 較 す る 。 手 法1の 逐 次 処 理 はCPUの み を 用 い て お り、 並 列 化 は 行 っ て い な い 。 手 法2,3,4は い ず れ も第4章 で 説 明 し た 手 法 で あ り、 そ れ ぞ れGPUを 用 い た 並 列 化 を 行 っ て い る 。
5.1使 用 し た デ ー タ
品 詞 タ グ 付 け を 行 う デ ー タ は 、 比 較 の た め 先 行 研 究[1]と 同 じ デ ー タ を 利 用 し た 。 具 体 的 に はTreebank‑3[7]と い う デ ー タ で あ り、ペ ン シ ル バ ニ ア 大 学 発 のPennTreebank Projectが3年 間 分 の ウ ォ ー ル ス ト リ ー トジ ャ ー ナ ル 紙 の98,732個 の 記 事 か ら2,499個
の 記 事 を 抜 き 出 し た も の を 使 用 し た 。 デ ー タ は 単 語 ご と に 適 切 な 品 詞 が 付 与 さ れ て お り、 全 部 で25個 のNo.00か らNo.24の セ ク シ ョ ン に 分 割 さ れ て い て る 。 こ の う ち No.16〜24の セ ク シ ョ ン を 、HMMの モ デ ル に よ る遷 移 確 率 と 出 現 確 率 の 学 習 用 に 用 い た 。 そ し てNo.00か らNo.15の セ ク シ ョ ン を 、 実 際 に 品 詞 列 の 推 測 を 行 う際 の テ ス ト デ ー タ と し て 用 い た 。テ ス トデ ー タ に は そ の 中 に 含 ま れ る 文 の 数 に ほ ぼ 比 例 す る 「サ イ ズ 番 号 」 を 与 え た 。 具 体 的 に は セ ク シ ョ ン の 範 囲 がNo.00だ け の も の は サ イ ズ 番 号 を 1と し 、No.00〜NO.01の も の は 番 号 を2、No.00〜No.03の も の は 番 号 を4、No.00〜No.07 の も の は 番 号 を8、No.00〜No.15の も の は 番 号 を16と し た 。 テ ス トデ ー タ の サ イ ズ 番 号 と セ ク シ ョ ン の 範 囲 と 含 ま れ る 文 の 数 の 対 応 表 を 以 下 の 表4に 示 す 。
表4:テ ス トデ ー タ サ イ ズ ・セ ク シ ョ ンNo・ 文 の 数 の 対 応 表
61⊥(∠481⊥
No.00セ ク シ ョ ン
No.00〜No.01セ ク シ ョ ン No.00〜No.03セ ク シ ョ ン No.00〜No.07セ ク シ ョ ン No.00〜No.15セ ク シ ョ ン
1,918 3,875 7,320 15,633 31,166
5.2実 行 環 境
実 行 環 境 に 関 して も使 用 した デ ー タ と 同 じ よ うに 、 比 較 の た め 先 行 研 究[1]と 同 じ環 境 を使 用 した 。
5.2.1ハ ー ド ゥ ェ ァ CPU:IntelCorei7‑5820K RAM:16.OGB
GPU:NVIDIAGeForceGTXTITANX
