【IT Text 自然言語処理の基礎】第8章：系列ラベリング

自然言語処理の基礎 8章 系列ラベリング 宮前明生 0

8章：系列ラベリング 目次 1. 系列ラベリングとは 2. モデル①点予測 3. モデル②線形連鎖に基づく条件付き確率場 1

1. 系列ラベリングとは 要素が一次元に並べられた系列データを入力として、ラベル列を推定する。 ● 自然言語の構造を解析するアプローチの1つ 例①品詞タグ付け 例②チャンキング…単語列から名詞句や動詞句の塊(チャンク)を推定する。 チャンク先頭はB-、先頭以外はI-をつける。(IOB2記法) 例③固有表現認識…人名や場所、組織名などの固有表現を抽出する。 ● 単語 Play Yellow Submarine Of the Beatles 品詞 動詞 固有名詞 固有名詞 前置詞 限定詞 固有名詞 チャンク B-VP B-NP I-NP B-PP B-NP I-NP 固有表現 O B-SONG I-SONG O B-ARTIST I-ARTIST 動詞句(VP: verb phrase) 名詞句(NP: noun phrase) 前置詞句(PP: prepositional phrase) 2

1. 系列ラベリングとは 系列ラベリングの定式化 入力の系列を 𝒙 = 𝑥1 , … , 𝑥𝑇 が与えられたとき、ラベリングの系列 𝒚 = 𝑦1 , … , 𝑦𝑇 を推定する問題を以下のように定式化する。 ෝ = argmax 𝑃(𝒚|𝒙) 𝒚 𝒚∈𝕐𝑻 条件付きモデル化しないと、𝕐𝑇 の要素|𝕐|𝑇 をしらみつぶしに検討す るので、計算量𝒪(|𝕐|𝑇 )が必要となる。 3

2. モデル①点予測 点予測では、ラベル𝑦1 , … , 𝑦𝑇 をそれぞれ独立していると仮定する。 𝑇 𝑃 𝒚 𝒙; 𝜃 = ෑ 𝑃 𝑦𝑡 𝒙; 𝜽 𝑦1 𝑦2 𝑦3 𝑥1 𝑥2 𝑥3 𝑡=1 ෝ = (argmax 𝑃 𝑦1 𝒙; 𝜽 , … , argmax 𝑃(𝑦𝑇 |𝒙; 𝜽)) 𝒚 𝑦1 ∈𝕐 𝑦𝑇 ∈𝕐 これは𝑇個のラベルごとに|𝕐|個の要素を検討するので、計算量は𝒪(𝑇|𝕐|)で、指 数オーダーから線形オーダーに削減される。 𝑃(𝑦𝑡 |𝒙; 𝜃)モデルの1つとして、ラベル𝑦𝑡 のスコア𝜓(𝑡, 𝒙, 𝑦𝑡 ; 𝜽)にソフトマックス 関数を用いる手法がある。スコアはニューラルネットワークなどで表現できる。 𝑒𝑥𝑝𝜓(𝑡, 𝒙, 𝑦𝒕 ; 𝜽) 𝑃 𝑦𝑡 𝒙; 𝜽 = σ𝑦`∈𝕐 𝑒𝑥𝑝𝜓(𝑡, 𝒙, 𝑦`; 𝜽) 4

2:モデル①点予測 素性関数を用いたスコア付け ニューラルネットワーク以前のスコア𝜓(𝑡, 𝒙, 𝑦𝑡 ; 𝜽)は素性関数𝑓𝑘 の重み𝑤𝑘 の和 で表現されていた。 𝐾 𝜓 𝑡, 𝒙, 𝑦𝑡 ; 𝜽 = ෍ 𝑤𝑘 𝑓𝑘 (𝑡, 𝒙; 𝑦𝒕 ) 𝑘=1 素性関数とは 入力と出力が条件を満たすときに1を返し、条件を満たさないとき0を返す。 例①単語𝑥𝑡 が’Brown’で、その品詞𝑦𝑡 が固有名詞と予測する素性関数は 𝑓1 𝑡, 𝒙; 𝑦𝒕 = 𝟏𝑥𝑡 =𝐵𝑟𝑜𝑤𝑛⋀𝑦𝑡 =𝑁𝑁𝑃 例②単語𝑥𝑡 の先頭が大文字で、その品詞𝑦𝑡 が固有名詞と予測する素性関数は 𝑓2 𝑡, 𝒙; 𝑦𝒕 = 𝟏𝑥 の先頭が大文字⋀𝑦 =𝑁𝑁𝑃 𝑡 𝑡 素性関数を生成するルールを人力で設計するのは大変だった 5

3. モデル②線形連鎖に基づく条件付き確率場 線形連鎖に基づく条件付き確率場では、点予測のモデルに加えて、ラベルの隣 接するもの同士の影響も考える。 𝑦0 スコア𝑠(𝒙, 𝒚; 𝜽)は以下のように表せる。BOS 𝑇 定式化は 𝑦2 𝑦3 𝑡=1 𝑦4 EOS 𝑇+1 𝑠 𝒙, 𝒚; 𝜽 = ෍ 𝜓(𝑡, 𝒙, 𝑦𝑡 ) + ෍ 𝜙(𝑦𝑡−1 , 𝑦𝑡 ) 𝑡=1 𝑦1 𝑥1 𝑥2 𝑥3 𝑒𝑥𝑝𝑠(𝒙, 𝒚; 𝜽) ෝ = argmax 𝑃(𝒚|𝒙) = argmax 𝒚 = argmax 𝑠(𝒙, 𝒚; 𝜽) 𝒚∈𝕐𝑻 𝒚∈𝕐𝑻 σ𝒚`∈𝕐𝑇 𝑒𝑥𝑝𝑠(𝒙, 𝒚`; 𝜽) 𝒚∈𝕐𝑻 計算量はしらみつぶしに検討すると、 𝒪(|𝕐|𝑇 )だが… 6

3. モデル②線形連鎖に基づく条件付き確率場 ラベル列のラティス（グラフ）表現 “Brown promises change”に対する、品詞の割り当てをラティス （グラフ）で表現した。 位置t-1におけるノードiと位置tにおけるノードjを結ぶエッジの重 みを𝑀𝑡,𝑖,𝑗 とすると 𝜙 𝐵𝑂𝑆, 𝑗 + 𝜓 1, 𝒙, 𝑗 (𝑡 = 1, 𝑖 = 𝐵𝑂𝑆) (1 < 𝑡 ≤ 𝑇) 𝑀𝑡,𝑖,𝑗 = ൞𝜙 𝑖, 𝑗 + 𝜓 𝑡, 𝒙, 𝑗 𝜙 𝑖, 𝐸𝑂𝑆 (𝑡 = 𝑇 + 1, 𝑖 = 𝐸𝑂𝑆) ラベル系列𝒚の全体のスコア𝑠 𝒙, 𝒚; 𝜽 は品詞 ノード𝑦1 , 𝑦2 , … , 𝑦𝑇 を経由したときのエッジ重み の和で表せる。 𝑻 𝑠 𝒙, 𝒚; 𝜽 = ෍ 𝑀𝑡,𝑖,𝑗 𝒕=𝟏 7

3. モデル②線形連鎖に基づく条件付き確率場 ビタビアルゴリズム ෝ = argmax 𝑠(𝒙, 𝒚; 𝜽) に対する、動的計画法。 𝒚 𝒚∈𝕐𝑻 位置tにおいて、BOSからノードjに至る 経路のスコアの最大値を𝑉𝑡,𝑖 とすると、 𝑀1,𝐵𝑂𝑆,𝑗 (𝑡 = 1) 𝑉𝑡,𝑖 = ቐ max 𝑉𝑡−1,𝑖 + 𝑀𝑡,𝑖,𝑗 (1 < 𝑡 ≤ 𝑇) 𝑖∈𝕐 経路のスコアの最大値は max𝑻 𝑠(𝒙, 𝒚; 𝜽) = max 𝑉𝑇,𝑖 + 𝑀𝑡,𝑖,𝑗 𝒚∈𝕐 𝑖∈𝕐 tそれぞれで、位置t-1におけるノードiと位置tにおけるノードjを結 ぶ経路の総数を検討するので、計算量は𝒪(𝑇|𝕐|2 ) 8

3. モデル②線形連鎖に基づく条件付き確率場 学習するには 負の対数尤度は、 𝑙 𝒙,𝒚 𝜽 = −𝑙𝑜𝑔𝑃 𝒚 𝒙; 𝜽 = −𝑠 𝒙, 𝒚; 𝜽 + 𝑙𝑜𝑔 ෍ exp 𝑠 𝒙, 𝒚; 𝜽 𝒚∈𝕐 これを計算した後、自動微分して、勾配を求める必要がある。 第1項はビタビアルゴリズムから求まる。 第2項は後述する前向き、後ろ向きアルゴリズムから求まる。 𝑍(𝒙; 𝜽) = σ𝒚∈𝕐𝑇 exp 𝑠 𝒙, 𝒚; 𝜽 とおく。 これも、計算量はしらみつぶしに検討すると、 𝒪(|𝕐|𝑇 )だが… 9

3. モデル②線形連鎖に基づく条件付き確率場 後ろ向きアルゴリズム 𝑇+1 𝑍 𝒙; 𝜽 = ෍ 𝒚∈𝕐𝑇 = ෍ 𝑦1 ∈𝕐 exp 𝑠 𝒙, 𝒚; 𝜽 = ෍ 𝒚∈𝕐𝑇 exp(𝑀1,𝐵𝑂𝑆,𝑦𝑇 ) ෍ 𝑦2 ∈𝕐 ෑ exp(𝑀𝑡,𝑖,𝑗 ) 𝑡=1 exp(𝑀2,𝑦1,𝑦2 ) … ෍ 𝑦𝑇 ∈𝕐 exp(𝑀𝑇,𝑦𝑇−1,𝑦𝑇 ) exp(𝑀𝑇+1,𝑦𝑇,𝐸𝑂𝑆 ) 共通因数を𝑦1 から𝑦𝑇 に向かって括り出した。 exp(𝑀𝑇+1,𝑦𝑇 ,𝐸𝑂𝑆 ) (𝑡 = 𝑇) 𝐵𝑡,𝑖 = ൞ ෍ exp(𝑀𝑡+1,𝑖,𝑗 ) 𝐵𝑡+1,𝑗 (1 ≤ 𝑡 < 𝑇) 𝑗∈𝕐 𝑍 𝒙; 𝜽 は次式で求められる 𝑍 𝒙; 𝜽 = ෍ 𝑗∈𝕐 exp(𝑀1,𝐵𝑂𝑆,𝑗 ) 𝐵1,𝑗 t、ノードiそれぞれで、|𝕐|回 exp(𝑀𝑡+1,𝑖,𝑗 ) × 𝐵𝑡+1,𝑗 を行うので、計算量は𝒪(𝑇|𝕐|2 ) コンピュータ上ではlog𝐵𝑡,𝑖 を記録しながら計算する。 10

3. モデル②線形連鎖に基づく条件付き確率場 前向きアルゴリズム 𝑇+1 𝑍 𝒙; 𝜽 = ෍ 𝒚∈𝕐𝑇 = ෍ 𝑦𝑇 ∈𝕐 exp 𝑠 𝒙, 𝒚; 𝜽 = ෍ 𝒚∈𝕐𝑇 exp(𝑀𝑇+1,𝑦𝑇,𝐸𝑂𝑆 ) ෍ ෑ exp(𝑀𝑡,𝑖,𝑗 ) 𝑦𝑇−1 ∈𝕐 𝑡=1 exp(𝑀𝑇,𝑦𝑇−1 ,𝑦𝑇 ) … ෍ 𝑦1 ∈𝕐 exp(𝑀2,𝑦1,𝑦2 ) exp(𝑀1,𝐵𝑂𝑆,𝑦1 ) 共通因数を𝑦𝑇 から𝑦1 に向かって括り出した。 exp(𝑀1,𝐵𝑂𝑆,𝑗 ) (𝑡 = 1) 𝐴𝑡,𝑗 = ቐ ෍ exp(𝑀𝑡,𝑖,𝑗 ) A𝑡−1,𝑖 (1 < 𝑡 ≤ 𝑇) 𝑖∈𝕐 𝑍 𝒙; 𝜽 は次式で求められる 𝑍 𝒙; 𝜽 = ෍ exp(𝑀𝑇+1,𝑖,𝐸𝑂𝑆 ) 𝐴 𝑇,𝑖 𝒊∈𝕐 t、ノードiそれぞれで、|𝕐|回 exp(𝑀𝑡,𝑖,𝑗 ) × 𝐴𝑡−1,𝑖 を行うので、計算量は𝒪(𝑇|𝕐|2 ) コンピュータ上ではlog𝐴𝑡,𝑖 を記録しながら計算する。 11

3. モデル②線形連鎖に基づく条件付き確率場 ラベル෦ 𝒚𝒕 がiと予測される周辺確率 BOSから位置tにおいてラベルiのノードを通過する経路上のエッジ 重みの総和は𝐴𝑡,𝑖 位置tにおいてラベルiのノードからEOSを通過する経路上のエッジ 重みの総和は𝐵𝑡,𝑖 これらを利用すると、𝑃 𝑦෥𝑡 = 𝑖 𝒙 = 𝐴𝑡,𝑖 𝐵𝑡,𝑖 𝑍 𝒙;𝜽 12

13