一般社団法人 電子情報通信学会
THE INSTITUTE
OF ELECTRONICS,
社団法人
電子情報通信学会
INFORMATIONANDOFCOMMUNICATIONTHE
INSTITUTE
ELECTRONICS,ENGINEERS

信学技報
IEICE
Technical Report
信学技報
IBISML2018-5(2018-06)
TECHNICAL REPORTOF IEICE.

INFORMATION AND COMMUNICATION ENGINEERS

可変次数無限隠れマルコフモデル
内海慶†

持橋 大地††† デンソーアイティーラボラトリ 〒 150–0002 東京都渋谷区渋谷 2–15–1†† 統計数理研究所 〒 190–8562 東京都立川市緑町 10–3
あらまし 従来，時系列データのモデルとして隠れマルコフモデル（HMM）が広く用いられてきた．言語処理では形態素解析や品詞推定，知能化自動車分野では運転行動の分析に用いられており，その用途は多岐に渡る．品詞には高次の依存があることが知られているが，これまでは計算量やデータスパースネスの問題からほとんどの場合，1 次
からせいぜい 2 次の HMM しか用いることができなかった．本稿ではこの問題に対処するため，各時刻における次数を潜在変数として追加した無限隠れマルコフモデルの提案を行う．提案手法を用いることで，日本語，英語，中国語の品詞推定で最高精度を達成した．また，運転データの分析を行い，提案手法が連続値データにも有効である
ことを示した．
キーワード

隠れマルコフモデル，ノンパラメトリックベイズ法

Variable Order Infinite Hidden Markov Models
Kei UCHIUMI† and Daichi MOCHIHASHI††† DENSO IT LABORATORY, Shibuya 2–15–1, Shibuya-ku, Tokyo, 150–0002 Japan†† The Institute of Statistical Mathematics, Midori-cho 10–3, Tachikawa-shi, 190–8562 Japan
Abstract

Hidden Markov Models have been widely used for modeling of sequential data. For example, it is used formorphological analysis, part-of-speech induction and inference of drive behaviors in the natural language processing
and intelligent vehicles, respectively. It is known that the PoS has a higher order dependence. However, because of
calculation cost and data sparseness, first order or second order HMM is mostly used. In this paper, to attempt tosolve these problems, we propose a new novel infinite HMM which has latent variables to treat its order at each time
step. We show that the proposal outperforms conventional methods in PoS induction. As well as discrete dataset, we
also show our method can be applied to continuous sequential datasets by analyzing driving logs.
Key words Hidden Markov Models, Non-parametric Bayes

1.

た品詞を推定できることが望ましい．この目的には HMM がはじめに適しており，実際品詞推定によく用いられている [7] [8] [9]．

従来，隠れマルコフモデル（HMM）は時系列データのモデルとして広く用いられてきた．自然言語処理における形態素

HMM は，観測系列 y = {y1 , y2 , . . . , yT } が背後にある潜在変数列 s = {s1 , s2 , . . . , sT } から生成されたとする確率モデル

解析や品詞推定，知能化自動車における運転行動分析など，適である．ある位置 t の状態 st が 1 つ前の状態 st−1 のみに依存

用先は多岐に渡る．自然言語処理の基盤技術である構文解析，すると仮定した場合を 1 次 HMM と呼び，同時確率は，固有表現抽出などの教師あり学習では，多くの場合素性として単語や品詞情報を用いており [1] [2] [3] [4] [5] [6]，自然言語処

p(s, y) =

T
∏

t=1

理の応用タスクではコーパスに品詞情報が付与されているこp(yt |st )p(st |st−1 )とを前提とすることも多い．新しい言語資源にアノテーショで表される．多くの場合，HMM といえば 1 次 HMM を指し，ンを行う場合，全てを人手で行うことは難しく，予めある程度

このモデルが最も広く利用されている．しかしながら，品詞

ラベルを付与しておき，専門家によって誤った箇所を修正し推定では高次 HMM を用いると高い精度で品詞が推定できるていく方が効率が良い．

ことが報告されている [10]．このことは，品詞には高次の依存

言語は文法を持ち，品詞間には依存関係が存在する．その関係が存在しており，1 つ前の品詞を見るだけでは不十分なこため，ラベルなしの言語資源に対しても文法的な規則を考慮しとを示唆している．実データでは高次 HMM の方が適してい- 31 -

This article is a technical report without peer review, and its polished and/or extended version may be published elsewhere.

Copyright ©2018 by

—1—

IEICE

るにも関わらず，1 次の手法が用いられる理由として，以下が挙げられる．
• 真の次数が不明：対象とする言語の品詞が，いくつ前までの品詞に依存しているのかが分からない．
• 高次モデルの計算量が大きい：単純に計算した場合，次数 n に対して計算量は O(K n+1 ) となる．そのため，現実的な計算の都合から扱える次数はせいぜい 2 次程度となる．
• データスパースネスの問題：次数が高くなるにつれて，(a) 1 次 HMM

考慮すべき状態遷移の組み合わせも指数的に増大する．既存の評価データでは多数のパラメータを学習するためには十分なサイズと言えず，高次 HMM を適用しても学習がうまくいかない．
本論文では，これまで取り組まれて来なかった HMM の次数をデータから推定することに取り組む．加えて，高次化に伴う計算量を抑え，状態遷移に適切な事前分布を置くことでデー
タスパースネスの問題にも対処する．以降では，各時刻に次(b) 提案手法

数を潜在変数として持つ新たな無限 HMM [11] [12] [9] の提案を行い，品詞推定への適用で従来手法と比較して最高精度を

図 1 1 次 HMM と提案法のグラフィカルモデル

達成したことを報告する．また，連続値のデータへも適用し，ら [10] の手法では状態数は有限としているが，仮に無限とし非言語データでも有効であることを示す．

た場合，新しい状態の持つ次数は常に 0 次とされてしまうた

2.

め，無限次元へ拡張することは簡単ではない．

先行研究

我々はこの問題に対し，状態だけではなくデータの持つ次HMM を用いた品詞推定では，従来モデルを立てる際に予め数についても確率変数として扱うことで対処する．

次数と状態数を決める必要があった [7] [13]．状態については，データから HMM の状態数を推定する手法として，無限の状

3.

提案手法

態数を扱う infinite HMM が提案されている [11] [12] [14]. Beal

3. 1

生成モデル

ら [11] は状態遷移の事前分布に階層ディリクレ過程を導入す

以下に，提案手法の生成モデルを (1) に示す．図 1 の隠れることを提案している．ここでは，階層ディリクレ過程によっ

マルコフモデルと提案法のグラフィカルモデルで示すように，て，新しい状態 K + 1 への遷移確率を与えることで，データ提案法では各時刻 t での次数 nt が潜在変数として追加されてに合わせて状態数を可変にしている．Gael ら [12] のアプロー

おり，それによって局所的に高次の状態遷移を見る．

チも同様に，遷移確率の事前分布に階層ディリクレ過程を用いているが，階層ディリクレ過程の構築に Chinese Restaurantp(s, y, n) =Process ではなく，Stick-Breaking Process を用いており，加えて状態のサンプリングに Gibbs Sampling でなく動的計画法と Slice Sampling [15] を組み合わせた Beam Sampling を用いることで，高速な学習を行っている．これらの手法は，データから状態数を推定することはできるものの，データを生成したパラメータが持つ真の次数については考慮しておらず，1

T
∏

t=1

p(st |st−1, nt )p(yt |st )p(nt |st−1
nt−1
)
0
0
0

(1)

s は 状 態 列 s = {s0 , s1 , . . . , sT }，y は 観 測 系 列 y={y1 , y2 , . . . , yT }，n は各時刻の状態の次数 n = {n0 , n1 , . . . , nT }を表す．本稿では，式の簡略化のため，時刻 i の状態 si から

時刻 j の状態 sj までの状態列をまとめて，sji = {si , . . . , sj }と表記する．

次の HMM として扱う．そのため，高次の遷移に対しては新3. 2状態のサンプリング

たな状態を生成することで対処し，データが持つ本来の状態

状態数と次数の推定には，[12] らの Beam Sampling を拡張数よりも多くの状態が推定される．こうした推定結果は，高した手法を用いる．infinite HMM では考慮する状態数が無次 HMM を 1 次 HMM に展開したものであるため，モデルと限のため，そのままでは動的計画法を適用できない．そのた

しては等価であると考えられるが，多すぎる状態数は人間にめ，スライスサンプリングを導入して無限の状態を有限に制とって解釈が難しくなる．

限する．具体的には nt > 0 のとき，以下のように補助変数

高次 HMM を効率的に学習する手法として，Carter ら [10]は，入力系列に対して n-gram をヒューリスティックでバックµ ∼ Beta(a, b) を導入する．[12] では補助変数 µ の確率密度関数に一様分布を仮定しているが，本手法ではベータ分布を用いオフし，低次で近似する手法を提案している．しかし，やはりることで、より効率的に探索を行う．ベータ分布のパラメー

事前に次数を決める必要があり，データが持つ真の次数を推定

タを，a = 1, b = 1 とした場合，µ の確率密度関数は一様分布

することはできない．また，最尤となる低次の遷移確率に一となり，[12] と一致する．

意に決めてしまうため，初期状態に依存する．この他 Carter- 32 -—2—

p(µt |st0 , nt ) =t−1
I{0 < µt <= p(st |st−nt )} p (µ ; a, b)tβp(st |st−1
t−nt )DP の構築には，パラメータを陽にする Stick-breaking pro-(2)

cess（SBP）を用いるか，もしくはパラメータを積分消去してここで，pβ (µt ; a, b) は，ベータ分布の確率密度関数である．
補助変数 µ を導入した前向き確率 p(stt−nt +1 |y1t , µt1 ) を (3) に示す．

期待値を用いることにより，パラメータを陽にせず観測頻度のみを持つ Chinese restaurant process（CRP）を用いる方法が一般的である．本研究では動的計画法によるサンプリングを用いる都合，一度のサンプリングで複数の状態を新しく生成

p(stt−nt +1 |y1t , µt1 ) ∝ p(stt−nt +1 , y1t , µt1 )

(3)

∑
t−1


q×
p(st−1, µt−1) if nt = nt−1
t−nt−1 , y1
1


t−nt


µt
st−n
:pt >
=

t−1

∑

t−1
p(st−1, µt−1)p′ if nt > nt−1
t−nt−1 , y1
1
= q×

>
µ
s
:p
t
t

t−nt

∑
∑=

t−1


q
×
p(st−1, µt−1) if nt < nt−1
t−nt−1 , y11t−nt −1
st−nt :pt >µt= s

しやすい SBP を採用した．SBP では，確率分布のパラメータπ を明示的に生成する．具体的には，以下に示すようにベータ
分布からサンプルした値を用いて [0, 1] の間で棒を折り，折った棒を G0 からサンプルした点 k に立て，棒の残りについて再度ベータ分布で折り，次の位置に立てる，という工程を繰り返す．
γk ∼ Be(1, α), πk = γkt−nt−1

読みやすさのため，(3) では q = p(yt |st )pβ (µt ; a, b)，pt =
t−n

t−1
′
p(st |st−1
t−nt )，p = p(st−nt−1

G=) とした．(3) に従い状態を後ろk=1

向きに状態列をサンプリングすることで，状態の遷移確率を

3. 5

推定する．

掛けることが必要となる．各時刻のデータの次数 nt について
は，同時前向き確率を計算することで状態列と同時にサンプリングすることも可能であるが，計算の効率化のために，我々は事前に次数のみをサンプリングする．
3. 3

πk δ(θk ), θk ∼ G0 .

(7)
(8)

階層ディリクレ過程の Chinese District Process

前節で述べた SBP では，確率分布のパラメータを陽に持っている．しかし，本提案手法では状態数 K 及び次数 n についてもデータから決めるため，K n 個のパラメータを持つことになる．これは，K 及び n が大きな値になった場合，現実的ではない．そこで，CRP と同様に，SBP でもパラメータをProcess（CDP）表現 [14] を用いる．SBP において，ベータ分

データ y の確率は，∑∑
n(1 − γj )陽に持たずに観測頻度から期待値を計算する Chinese District

次数のサンプリング

p(y) =j=1

表現(3) では，各時刻 t の次数によって 1 時刻前の前向き確率を
適切に周辺化したり，事前分布となる状態の n-gram 確率を

∞
∑

k−1
∏

布からサンプルした値 γk で棒を折り，右側を折った棒の残り
p(s, y, n)とみなした場合，パラメータ πk は k − 1 番目まで右側を選び続(4)

け，k 番目で棒の左を選んだ時の確率とみなすことができる．

sで表される．時刻 t の次数 nt の事後分布は，ベイズ則より (5)棒の左側を選んだ頻度を n0 (k)，右側を選んだ頻度を n1 (k) とと表すことができ，次数が与えられた時の状態遷移確率と次した時，γk の期待値は数の事前確率を用いて，各時刻の nt をサンプリングすること

E[γk |D] =ができる．
nt ∼ p(nt |y, s, n−t )∝ p(st |n, y, s−t )p(nt |y, s−t )と表される．ここで，D は観測データを表す．CDP では，SBP(6)の棒の折る場所をベータ分布からサンプルする代わりに期待値を用いる．
Pairsley ら [14] は，CDP を隠れマルコフモデルに適用する

階層ディリクレ過程

ディリクレ過程では，何らかの基底測度 G0 を基に離散のディリクレ分布 G ∼ DP(α, G0 ) を生成する．ここで，α(> 0)
は集中度パラメータを表し，この値が大きいほど G は G0 に似たものとなる．
隠れマルコフモデルに適用する場合，各状態 st が与えられた時の次の状態 st+1 への遷移確率を考える必要がある．各状
態遷移確率ごとにディリクレ過程で遷移確率分布を生成した
場合，各分布で状態が共有されない．そのため，状態を共有するために各状態遷移ごとに G0 を共有する．具体的には，基底際に階層化を行わず，状態ごとに独立な遷移確率を生成している．しかし，これではパラメータ間で状態が共有されていない．
SBP を階層化する場合，Gk ∼ DP(α, β) の，β 自身も DPで生成される．(7) 及び (9) より，πk を構成する確率変数 γ の
))
(
(
分布は，
k
∑
γk ∼ Be αβk , α 1 −
(10)
βj
j=1

であり，γk の期待値は測度自身もディリクレ過程 G0 ∼ DP(η, H) で生成し，それを共有して次のディリクレ過程 Gk ∼ DP(α, G0 ) で各状態線遷移確率を生成する．

(9)

(5)

以降で，遷移確率及び次数の事前確率について説明する．
3. 4

1 + n0 (k)1 + α + n0 (k) + n1 (k)E[γk |D] =αβk + n0 (k)αβk:∞ + n(11)である．ここで，n は n = n0 (k) + n1 (k) とした．我々の提案手法では，この階層化した SBP の CDP 表現を用いる．

- 33 -—3—

高次の隠れマルコフモデルでは動的計画法を用いる場合でもAlgorithm 1 学習アルゴリズム
Require: y ∈ Y
1: Init S, N ∼ Uniform
2: Add ∀s, n ∈ S, N to Θ
3: for j = 1 · · · J do
4:
for s, n in randperm S, N do
5:
Remove customers of s, n from Θ
6:Draw s, n according to (5), (3)7:Add customers of s, n to Θ
8:
end for9:
Sample hyperparameters of Θ
10: end for
3. 6

O(K n ) の計算量が必要となる．加えて，提案法の場合は 1 時
刻前の次数についても周辺化を行う必要があるため，単純には計算が難しい．そのため，本研究では予測についても学習時と同様に，3. 2 で説明した Beam Sampling を用いて，100
epoch のサンプリングを行い，最初の 10 epoch をバーンイン
として除いたサンプルの精度の平均を取ることとした．ただし，パラメータの更新は行わず，訓練データから推定したものを用いる．
p(stt−nt , y0t ) =次数の事前分布∑ ∑nt−1 st−1�

次数の事前分布は，持橋ら [16] と同様に計算する．具体的には，階層ディリクレ過程の各階層に，状態がその階層から生成されるか，より高次の階層から生成されるかを表すベータ

...
��

st−nt

O(K n )

分布を導入する．導入したベータ分布を用いて，サンプル済

4.

評

みの状態列と次数の観測頻度を基に，以下のように次数の確

4. 1

トイデータによる実験率をベータ分布の期待値から計算する．

�

t−1
)
p(st−1t−nt−1 −1 , y0

(15)

価

データの次数及び状態数を推定できることを確認するため

al + ν
bi + o(12)
al + bl + ν + o i=0 ai + bi + ν + o

ここで，al は観測された l 次の状態数を，bl は l より高次の状
態数を表す．ν 及び o はベータ分布のハイパーパラメータを

生成した．


1 0

0

0 0





0 1/3 1/3 1/3 0







 0 1/2 1/2 0 0 
 0 0 1/2 1/2 0 








E =  0 0 1/2 1/2 0  , A =  0 1/2 0 1/2 0  0 1/2 0 1/2 0 
 0 1/2 1/2 0 0 
0 0 0 0 1
0 1/3 1/3 1/3 0表す．節 4. で詳細を述べるが，言語では単語が持つ品詞の曖
昧性は文脈の次数に対して指数的に減少する．ベータ分布を用いることは，この性質を表現するのに都合が良い．
3. 7p(yt |st )p(st |st−1
t−nt )に，以下に示すパラメータを用意し，そこから 500 件の系列を

l−1∏

p(nt = l|y, s−t ) =

∑

出力確率

B3−1 = (0 0 0 0 1) , B3−2 = (0 0 0 0 1) , B4−1 = (1 0 0 0 0)

出力確率 p(yt |st ) については，ディリクレ分布を事前分布とB4−2 = (1 0 0 0 0) , B4−3 = (1 0 0 0 0)

し，以下とした．

p(y|s) =nsy + ϕns + ϕ · V

E は出力確率のパラメータ，A は 1 次の遷移確率のパラメー(13)

タ，B は 2 次の遷移確率である．B3−1 は，2 つ前の状態がここで，ϕ はディリクレ分布のハイパーパラメータを，V は語

3，1 つ前の状態が 1 の時の次の状態への遷移確率を意味する．

彙数をそれぞれ表す．

500 件のデータに対して，提案手法を適用した際の推定結果を

3. 8

図 4. 1–4. 1 に示す．実験では，Beam Sampling に用いる補助

学習アルゴリズム

提案法の学習アルゴリズムを 1 に示す．提案法のサンプリ

変数 µ の確率密度関数を pβ (1/λ, λ) とし，λ = 1 とした．

ングでは，状態列と次数列を同時にサンプリングしている．そA を見て分かる通り，状態 4 へは 2 次の遷移が選ばれた時のため，観測されているのは状態 n-gram となる．(11) からのみ移ることができるように設定している．推定された 1 次

も分かるように，HDP のパラメータ更新では，サンプリングの遷移確率 4. 1 を見ると，状態 3 へはどの状態からもほぼ確されたものより低次の状態 n-gram についても更新をする必要率がゼロとなっており，2 次の遷移確率 4. 1–4. 1 から，2-1 まがある．そこで，観測された状態 n-gram を基に，確率的に低たは，4-1 という遷移が起こった際に高い確率で状態 3 へ遷移

次の n-gram についても頻度を追加する．ここでは [17] らとするパラメータが推定されている．出力確率 E から分かるよ同様に，CRP を用いる．我々の HDP 構築には CDP を用い

うに，出力シンボル 4 は状態 4 からのみ生成される．推定さているが，CDP は CRP と等価であるため，観測頻度の更新

れた出力確率 4. 1 でも，状態 3 からのみ出力シンボル 4 が生成されると推定されており，2 次の状態遷移を通じて到達されではより実装の簡単な CRP を用いた．
3. 9

る真の状態 4 と，推定されたパラメータの状態 3 が対応して状態と次数の予測

状態と次数の予測は，最尤となる次数と状態列を (14) よりいることが分かる．
4. 2

予測する．
∗

∗

n , s = argmax p(n, s, y)

品詞推定

提案手法の評価を行うために，我々は日本語，中国語，英語

(14)

n,s

のそれぞれについて品詞の推定精度を評価する．

計算量の問題で単純には計算できないため，(15) に示す通4. 2. 1

り，予測には動的計画法を用いるのが一般的である．しかし，日本語のデータセットには京大コーパス v4．0 を，中国語- 34 -

データセット—4—

(a) 出力確率(b) 1 次の遷移確率 (c) 2 つ前の状態が 0 の(a) 取り得る品詞数で見た単語の頻度 (b) 文脈に依存して品詞が決まる単語

時の 2 次の遷移確率

分布

の頻度分布

図 3 コーパス中のトークン頻度

かる．中国語でも 1 つのみの品詞を取り得る単語が高頻度となったが，2 つ，3 つの品詞を取る単語の出現頻度も日本語，
英語と比較して多くなっている．また，日本語と英語では多くても単語の取り得る品詞は 5 つ程度であるのに対し，中国語では最大 14 の品詞を取り得る単語が存在する．加えて，図(d) 2 つ前の状態が 1 の(e) 2 つ前の状態が 2 の(f) 2 つ前の状態が 3 の3(b) から分かるように，日本語と英語では次数に応じて単語時の 2 次の遷移確率が持つ品詞の曖昧性が指数的に減少している様子が見れるが，時の 2 次の遷移確率

時の 2 次の遷移確率

中国語では線形となっている．このことから，中国語の品詞
推定は日本語と英語と比較して難しいと言える．
次に，コーパス中の品詞の条件付きエントロピー (16) を図4 に示す．縦軸は条件付きエントロピーを，横軸はいくつ前の品詞まで見るかを意味する．ここで hn は n 次の品詞文脈を意味しており，n = 0 の際は文脈を見ない，すなわち品詞
unigram のエントロピーとなる．

(g) 2 つ前の状態が 1 の時の 2 次の遷移確率

図2

H(S|hn ) = −推定されたパラメータ∑p(hn )hn∑p(st = i|hn )log2 p(st = i|hn )iには Chinese Treebank 8.0 を，英語には BNC をそれぞれ用いた．BNC は A，B，C，D，E，F，G，H，J，K の 10 種類の(16)

図 4 を見ると，どの言語でも高次の文脈を見ることでエントデータからなり，それぞれのデータごとに A0，A1. . . のようにサブディレクトリに分けられている．ここでは，A0 カテゴ
リに含まれるデータを用いた．各コーパスの語彙数及び文数
を表 1 に示す．
我々は各コーパスごとに，無作為に抽出した 10000 文及び20000 文を訓練データとして，1000 文をテストデータとして使用した．
4. 2. 2

品詞の文脈依存正解とするコーパスの品詞がどの程度過去の文脈に依存しているかを調べる．各言語のコーパスで，取り得る品詞数で分けた単語の頻度分布と，文脈の次数に依存して品詞が決ま

図 4 品詞の条件付きエントロピー

る単語の頻度分布を図 3 に示す．図 3(a) の縦軸は単語の出現
頻度，横軸は単語が取り得る品詞の数を表している．図 3(b)ロピーは小さくなっており，高次の品詞遷移が存在することの横軸は次数を，縦軸はその次数で品詞が決まる（取りうる品が分かる．

詞数が 1 となる）単語の出現頻度を表す．図 3(a) より，日本

図 3 及び図 4 から，各言語について，多くの単語については語と英語では多くの単語は 1 つの品詞のみ取りうることが分品詞の文脈を見る必要はなく，一部の単語についてのみ文脈

表1

コーパス

データセット

述べ単語数 サイズ (文)に依存して品詞が決まることが分かる．表 2 に，多数の品詞を取り得る単語の例を示す．こうした単語は文脈に依存して京大コーパス 1,011,294

37,400

CTB 8.0

1,620,561

71,3694. 2. 3

BNC A0977,097

51,739

実験では，初期状態数 K = 10，出力確率のディリクレ分布

品詞が決まると考えられる．

- 35 -

実験条件—5—

のパラメータ ϕ = 0.1，遷移確率の階層ディリクレ過程の事前表3

M-1 と V-measure. iHMM1 は 1 次の，iHMM2 は 2 次の iHMM
をそれぞれ表している．

分布のハイパーパラメータ α = 1 とした．Beam Sampling の

M-1
CorpusiHMM1 iHMM2 vHMM
KC 10K 0.661 0.649 0.718
KC 20K 0.708 0.667 0.707
BNC 10K 0.591 0.619 0.707
BNC 20K 0.593 0.631 0.702
CTB 10K 0.513 0.535 0.553
CTB 20K 0.490 0.538 0.575

補助変数 µ の確率密度関数のパラメータには，京大コーパス
では λ = 10，BNC，CTB では λ = 3 を用いている．λ の値
は，各言語ごとに λ = 1, 3, 5, 10 について予備実験を行い，数値を決めた．提案手法の最大次数は N = 3 とした．また，初期状態は初期状態数 K からランダムに初期化した．学習をするにあたり，前処理として各種コーパス中で 2 桁以上の数字については桁数を保持した上で ‘＃’ に置き換えている．
いくつかの先行研究では，教師なし品詞推定と言いつつもH(C) = −辞書を用いて品詞の候補を予め制限している [7] [13]．これら
は高い品詞推定精度を報告しているが，完全に辞書なし，あるc=

いは事前知識が用いられない場合の評価はしていない．[18] では，辞書などを用いないこれらの手法を比較しており，状態
数やハイパーパラメータを調整して大規模なコーパスで学習
上記の辞書などを用いない場合の評価も行なっており，その
ただし，この場合でも状態数は正しい品詞数と一致するよう事前に与えている．
我々の評価では，上記の事前知識を一切用いていないことに注意されたい．
4. 2. 4

品詞推定の評価は，many-to-1 accuracy(M-1) と V-measure[19] を用いた．M-1 は，予測結果の状態と最も共起する正解
品詞クラスをマッピングした後の精度を意味する．V-measureはクラスタリングのための評価尺度で，クラスタ内の正解クラスの条件付きエントロピーを表す均一性 (17) と，正解クラス
に対するクラスタの条件付きエントロピーを表す完全性 (18)の調和平均で定義される．ここで，N はデータ数，n はクラ
ス数，aij はクラスタ j に属するクラス i のデータ数をそれぞれ表す．精度での評価では，正解クラスに大きな偏りがあった場合，全てのデータを単一のクラスタにまとめた時にも高い値となるが，V-measure を用いることで，正解クラスに偏りがある場合でも影響を受けずに評価を行うことができる．

if H(C, K) = 0

 1 − H(C|K)/H(C)otherwise|K| |C|
∑
∑ ack

ack
log ∑|C|N
c=1 ack
k=1 c=1
表2

言語

品詞曖昧性のある単語の例

単語 (可能な品詞数)

日本語 なり (5), な (5), の (5), あまり (5),付 (4), 得 (4), なら (4)
英語

∑|K|

k=1 acknif H(K, C) = 0|C| |K|∑∑ ack
c=1 k=1

N

k=1

(18)

otherwiseack
log ∑|K||K| ∑|C|
∑
ack
c=1

0.387
0.398
0.529
0.558
0.287
0.316

n

k=1 ack

log∑|C|

c=1 ackn

推定された状態と正解コーパスの品詞との対応は，各状態ごとに最頻となる品詞の大分類を割り当てることで行った．この際，CTB については Others という大分類に感嘆詞，オノマ
め，これらについては細分類のままとした．
提案法の数値を評価するにあたり，Gael ら [12] の Beam
Sampling をベースラインとして用いた．評価結果を表 3 に示
す．iHMM がベースラインに該当する．データセットが異なる
ため単純には比較できないが，[8] で報告されている DP-HMM
は，iHMM で状態数を予め有限とした場合に相当する．
英語，中国語では提案手法がもっとも高い M-1，VM となっている．日本語についても，M-1 については提案法が最も良い結果となった．これは提案法が 3 次の状態遷移を考慮できることからも納得できる．
実験では，2 次の iHMM までをベースラインとして用いている．3 次の iHMM の実験は計算時間の都合で行わなかった．
BNC を用いて，訓練データ 1000 文，テストデータ 1000 文を用いた学習・予測の時間を表 4 に示す．実験に用いた計算

1

H(C|K) = −

c=1

0.320
0.376
0.481
0.482
0.260
0.278

トペ，名詞修飾，外来語，句読点などがまとめられているた

推定精度

h=

n

log

0.366
0.416
0.463
0.468
0.242
0.221

 1 − H(K|C)/H(K)

H(K) = −場合の trigram の DP-HMM で約 68%の精度を達成している．

k=1


1

H(K|C) = −しても 50%程度の精度であることが報告されている．[8] では|C| ∑|K|∑ack

V-measureiHMM1 iHMM2 vHMM

(17)

機は MacBook Pro 2006（Intel Core i5 3.1Ghz, メモリ 16GB）である．計算速度では，2 次の iHMM よりも 3 次の vHMM の方が早く学習が終わっており，局所的に高次の遷移を扱うことで効率的な学習ができていることが分かる．
表 5 に，1 次の iHMM と 3 次の vHMM の推定結果の例を示す．大まかには 1 次の場合も 3 次の場合も，似た品詞の推定結果となっている．ただし，3 次の場合では「日」
，
「年」
，
「人」
などの文脈によって名詞と接尾辞となる品詞が上手く推定できている．また，「の」のように文脈によって助詞と名詞の両like(6),no(6),past(5),down(5),表 4 学習・予測に掛かる時間

round(5),following(4),opposite(4)中国語 的 (14), 和 (11), 中 (11), 得 (11),
上 (11), 是 (11), 了 (10)手法

学習＋予測時間

iHMM (n=2)

5 時間 39 分

vHMM (n=3) 49 分

- 36 -—6—

ングする．分散についても同様に，精度パラメータ τ につい方になり得る単語についても上手く推定できていた．
表5

単語
ロシア
軍
は
###
日
年女
は
推計
で
#####
人
。
##
年
から
下がり
新進党
党首
「
海部
俊樹
氏
」
の
##
％
を
久保
の
渋面
を
見る
の
は
忍びない
。

てガンマ事後分布を求め，直接 τ を式 (20) からサンプリング

日本語の解析結果の比較

vHMM の品詞
名詞
名詞
助詞
名詞
接尾辞
名詞
助詞
名詞
名詞
名詞
接尾辞
特殊
名詞
接尾辞
名詞
動詞
名詞
名詞
名詞
名詞
名詞
接尾辞
名詞
助詞
名詞
接尾辞
助詞
名詞
助詞
名詞
助詞
動詞
名詞
助詞
名詞
特殊

iHMM の品詞
名詞
名詞
助詞
名詞
名詞
名詞
助詞
名詞
助詞
名詞
名詞
特殊
名詞
名詞
助詞
名詞
名詞
名詞
特殊
名詞
名詞
名詞
名詞
助詞
名詞
名詞
助詞
名詞
助詞
名詞
助詞
動詞
助詞
特殊
動詞
特殊

する．ここでは，観測値の D 次元ベクトルの各次元が独立で

正解品詞
名詞
名詞
助詞
名詞
接尾辞
名詞
助詞
名詞
助詞
名詞
接尾辞
特殊
名詞
接尾辞
助詞
動詞
名詞
名詞
特殊
名詞
名詞
接尾辞
特殊
助詞
名詞
接尾辞
助詞
名詞
助詞
名詞
助詞
動詞
名詞
助詞
形容詞
特殊

あることを仮定し，分散については全ての状態で共通とした．
, τ, µ0 , ρ0 )p(µk |y1n , sn
)
( 1
ρ0
nk
yˆk +
µ0 , (τ (nk + ρ0 ))−1 I= N µk |n k + ρ0n k + ρ0(19)p(τ |y1n , sn
1 , µ0 , ρ0 , a0 , b0 ) = Ga(τ |an , bn )

(20)

nk D
an = a0 +
2
( n
K
∑ 1∑
b n = b0 +δ(si = k)||yi − yˆk ||2
2 i=1
k=1
)
n k ρ0+||yˆk − µ0 ||22(ρ0 + nk )5. 2

連続値データへの適用

連続値の系列データでの動作を検証するため，我々は自動車の走行ログを用いて運転行動の状態を推定した．データはロサンゼルスの市街地及び高速道路で計測したもので, データ
量及び使用した特徴量は表 6 及び表 7 の通りである. 我々のモデルでは，観測値のガウス分布の平均の事前分布に，平均0，分散 1 のガウス分布を仮定している．そのため，各特徴量について平均 0，分散 1 となるように規格化した．
提案法では，Beam Sampling を用いて状態を推定する都合
上，系列が複数必要になる．そのため，系列を 50 ごとで分割
し，113 個の系列として用いた．
初期状態数は 2 とし，最大次数は 5 として実験を行った．表8 に，獲得した状態と運転シーンを示す．各状態の例を，図 5に示す．時刻ごとの状態と次数の変化についても，図 6 に示
す．走行データの動きは，以下となっている．
（ 1 ） 駐車状態
（ 2 ） 駐車場を出て左折連続値への対応

5.

（ 3 ） 交差点を左折

本報告では，離散のデータのみを対象として評価を行った．

（ 4 ） 高速道路に乗る

しかし，提案法自体は特にデータを離散に限定していない．

（ 5 ） 高速道路を降りる(13) では，出力確率にディリクレ分布を仮定したが，連続値を（ 6 ） 交差点を右折扱う場合にはこの出力確率に連続分布を用いれば良い．デー（ 7 ） 道路を左折して駐車場に入る

タがガウス分布に従う場合は，（ 8 ） 駐車表 6 走行ログの時間と系列長p(y|s) = N (y|µ, Σ)

時間

)
(
1
1
exp − (y − µ)Σ−1 (y − µ)= √2(2π)D |Σ|

9 分 35 秒 5728とすればよく，離散値の場合と同様に直接状態列をサンプリ
ングすることでパラメータの更新を行うことができる．
5. 1

系列長 サンプリングレート

ガウス分布のパラメータ推定

出力確率にガウス分布を仮定するため，ガウス分布のパラメータについても離散の時と同様にベイズ推定を行う必要がある．サンプルされた状態列から，各状態 k のガウス分布の平均 µk の事後分布 (19) を求め，そこから直接 µk をサンプリ- 37 -

表 7 走行ログの特徴量

ID
1
2
3
4
5
6

特徴量
速度
操舵角
アクセル量
ブレーキ量
加速度センサ (X 軸)
加速度センサ (Y 軸)

100[ms]
表 8 推定された状態

状態
1
2
3
4
5,6

運転シーン
巡行
走行
カーブ
加減速
停止・徐行

—7—

価は行えていないため，比較のために同じデータセットを用いた評価を行いたい．その他，運転行動データへ適用することで，提案手法が言語のみならず連続値のデータについても適用可能であることを示した．
(a) 駐車

連続値については数値的な評価は行っていない．今後，適(b) バックで発進（方向転換）

切なタスクにおいて他の手法と比較をする必要がある．
文(c) 走行(d) 加速から巡行(e) 高速道路に進入（右カーブ）(f) 加速から巡行(g) 高速を降りる(h) 一般道との合流で減速

図5推定された状態遷移（最大次数 5）

図6

各時刻の状態と次数

市街地を走っている時と高速道路を走っている時とでは，異なる状態の傾向が得られた．次数については全体を通じてほ
とんど 1 次から 3 次までの値となっているが，状態の変化が多い時刻では 5 次のような高次の状態遷移が選ばれることが多くなった．

6.

ま と め

本稿では，次数を潜在変数として追加した可変次数無限隠れマルコフモデルの報告を行った．提案法では，必要な箇所
のみ高次化することで効率的な計算を行うことができ，データに応じた状態数と次数の両方を推定できる．加えて，従来

献[1] R. Florian, A. Ittycheriah, H. Jing and T. Zhang: “Named
entity recognition through classiﬁer combination”, CoNLL2003, pp. 168–171 (2003).
[2] H. L. Chieu and H. T. Ng: “Named entity recognition witha maximum entropy approach”, CoNLL-2003, pp. 160–163(2003).
[3] J. Hammerton: “Named entity recognition with long shortterm memory”, CoNLL-2003, pp. 172–175 (2003).
[4] T. Kudo and Y. Matsumoto: “Japanese dependency analysis
using cascaded chunking”, CoNLL-2002, pp. 1–7 (2002).
[5] T. Nakagawa: “Multilingual dependency parsing using gibbs
sampling”, CoNLL-2007 (2007).
[6] J. Hall, J. Nilsson and J. Nivre: “Single malt or blended? astudy in multilingual parser optimization”, Trends in Parsing
Technology, pp. 19–33 (2010).
[7] S. Goldwater and T. Griﬃths: “A fully bayesian approach tounsupervised part-of-speech tagging”, ACL-2017, pp. 744–
751 (2007).
[8] P. Blunsom and T. Cohn: “A hierarchical pitman-yor process
hmm for unsupervised part of speech induction”, ACL-HLT2011, Association for Computational Linguistics, pp. 865–874(2011).
[9] J. Van Gael, A. Vlachos and Z. Ghahramani: “The inﬁnite
hmm for unsupervised pos tagging”, EMNLP-2009, pp. 678–
687 (2009).
[10] S. Carter, M. Dymetman and G. Bouchard: “Exact sampling and decoding in high-order hidden markov models”,
EMNLP-CoNLL-2012, pp. 1125–1134 (2012).
[11] M. J. Beal, Z. Ghahramani and C. E. Rasmussen: “The inﬁnite hidden markov model”, NIPS-2002, pp. 577–584 (2002).
[12] J. Van Gael, Y. Saatci, Y. W. Teh and Z. Ghahramani:“Beam sampling for the inﬁnite hidden markov model”,
ICML-2008, pp. 1088–1095 (2008).
[13] Y. Goldberg, M. Adler and M. Elhadad: “Em can ﬁnd pretty
good hmm pos-taggers (when given a good start)”, ACLHLT-2008, pp. 746–754 (2008).
[14] J. Paisley and L. Carin: “Hidden markov models with stickbreaking priors”, IEEE Transactions on Signal Processing,pp. 3905–3917 (2009).
[15] R. M. Neal: “Slice sampling”, Annals of statistics, pp. 705–
741 (2003).
[16] D. Mochihashi and E. Sumita: “The inﬁnite markov model”,
NIPS-2007, pp. 1017–1024 (2007).
[17] Y. W. Teh: “A hierarchical bayesian language model basedon pitman-yor processes”, COLING-ACL-2006, pp. 985–992(2006).
[18] J. Gao and M. Johnson: “A comparison of bayesian estimators for unsupervised hidden markov model pos taggers”,
EMNLP-2008, pp. 344–352 (2008).
[19] A. Rosenberg and J. Hirschberg: “V-measure: A conditional entropy-based external cluster evaluation measure.”,EMNLP-CoNLL-2007, pp. 410–420 (2007).

では扱えなかった次数の異なるパラメータが混在するデータについても扱えることを示した．
品詞推定での評価では，従来手法を上回る推定精度を達成した．ただし，先行研究と全く同じデータセットを用いた評- 38 -—8—