DEIM Forum 2019 A4–4

バイグラムの尤度比の直接推定法における周辺分布を用いた定式化
川上賢十 ‡†

菊地真人 ‡‡†

吉田光男 ‡‡‡†

梅村恭司 ‡‡‡‡†† 豊橋技術科学大学 〒 441–8580 愛知県豊橋市天伯町雲雀ヶ丘 1–1
E-mail: ‡ k131820@edu.tut.ac.jp, ‡‡ m143313@edu.tut.ac.jp, ‡‡‡ yoshida@cs.tut.ac.jp, ‡‡‡‡ umemura@tut.jp
あらまし

尤度比の推定は，異常検知や確率的パターン認識，文脈の推定など多くのタスクで用いられている．単純な手法で尤度比を推定するには，尤度比の定義に従い，尤度比を構成する個々の確率分布を最尤推定し，その比を求めるという手法が考えられる．この手法では，まず確率分布の推定を行い，推定値の比を求めるという二段階の推定を行う事になり，推定誤差を大きくしてしまう可能性がある．そこで，尤度比を直接推定する手法が提案されている．
我々は尤度比の直接推定法を用いてバイグラムの尤度比の定式化を行う．連続な標本空間における尤度比の直接推定には，ガウス関数のような基底関数が用いられてきた．ガウス関数を基底関数に用いることで，学習データに存在しない事象の推定を行う場合，サンプリングされた要素の近傍の値を用いることで，尤度比の値を推定することが出来る．そこで，バイグラムの確率分布に対する周辺分布と考えられる，ユニグラムの確率分布を用いてバイグラムの尤度比を定式化する．この定式化により，学習データに存在しないバイグラムに対しても尤度比の推定を行う．
キーワード テキストマイニング, バイグラム, 尤度比, uLSIF
効であると考える．

1 はじめに
尤度比の推定は，異常検知や確率的パターン認識，文脈の推定など多くのタスクで用いられている [1]．尤度比は尤度関数の比で表されるため，推定を行う必要がある．単純な手法で尤度比を推定するには，尤度比の定義に従い，尤度比を構成する
個々の確率分布を最尤推定し，その比を求めるという手法が考えられる．このような尤度比を構成する個々の確率分布を推定し，その比を求める手法を間接推定と呼ぶ．しかし，この手法
では，まず確率分布の推定を行い，推定値の比を求めるという二段階の推定を行う事になり，推定誤差を大きくしてしまう可能性がある．そこで，尤度比を構成する確率分布の推定を経由せずに，尤度比を直接推定する手法が提案されている [2]．尤
度比の直接推定を用いると，確率分布の推定を介する単純な手法よりも，推定誤差が小さくなることが報告されている．
直接推定において，基底関数は尤度比の形状を表現するため

本研究では， [3] にて提案された基底関数を用いて，バイグ
ラムの尤度比を定式化する．また，バイグラムの確率分布の周辺分布と考えられるユニグラムの確率分布を用いて，バイグラ
ムの尤度比の定式化を行う．ガウス関数を基底関数に用いることで，サンプリングされた要素の近傍の値を用いる効果があり，これにより学習データに存在しないデータに対しても推定を行うことが出来る．ユニグラムの確率分布を用いることで，関数を基底関数に用いることと類似の作用をえる事を期待している．
実験には，カタカナ語の直前に出現するバイグラムの推定という単純な実験を行う．学習に使用するデータの量を変化させ，定式化したバイグラムの尤度比の推定式により，学習データに存在しないバイグラムに対して推定が行えているか，ユニグラ
ムを用いることにより性能が低下していないかを確認する．

2 関連研究に使用されるため基底関数の選択が重要である．連続分布の尤尤度比の直接推定法 [2] は，確率分布の推定を介する単純な度比に対しては，基底関数としてガウス関数よく用いられてい手法よりも，正確に推定を行うことが出来ると報告されている．

る．ガウス関数を基底関数として用いることにより，推定を行

この手法は，尤度比を構成する確率分布の推定精度を向上する

う点の近傍の情報を用いることが出来る．しかし，ガウス関数のではなく，尤度比そのものの推定誤差をコスト関数が最小にでは，確率の標本空間が離散であることを考慮することは出来なるように定式化し推定を行う．コスト関数は，観測データをない．そこで，離散分布のそれぞれの事象に独立な基底関数を用いて表現される．尤度比をパラメータと基底関数の線形和に用いる手法が提案されている [3]．

よって表現出来ると仮定する．このパラメータをコスト関数が尤度比の直接推定はこれまでは多くの研究において連続分布最小となるように決定し，尤度比の推定を行う．尤度比の直接を対象に研究されてきた．連続分布では，推定を行いたい点に推定法では，この基底関数の選択が重要となる．これまでの研おける標本を集めることが困難であるため，尤度比の直接推定

究では，ガウス関数が基底関数によく用いられてきた [4], [5]．

が有効である [4]．離散分布であっても，例えば自然言語のバイ

しかし，ガウス関数では，確率の標本空間が離散であることをグラムのような膨大な組み合わせが存在する場合や，サンプル

考慮することは出来ない．本論文では，バイグラムのような非サイズが小さい場合などにおいては十分にサンプルを集めるこ

連続な分布に着目し研究を行う．これまでの研究において，連とは困難であり，離散分布においても，尤度比の直接推定は有続分布では推定を行いたい点における標本を集めることが困難

であり，離散分布の場合は容易であるとされている．しかし，

uLSIF では r(x) と r̂(x) の二乗誤差を最小とするようにパラバイグラムのような膨大な組み合わせが存在する場合や，サン

メータの決定を行う．コスト関数 Jo (α) を以下のように定義

プルサイズが少ない場合などにおいては十分な標本を集めるこ

する．

∫
1
(r̂(x) − r(x))2 pde (x)dx2∫1=r̂(x)2 pde (x)dx2∫∫
1
r(x)2 pde (x)dx− r̂(x)pnu (x)dx +2とは困難である．よって，我々は離散分布に置いても尤度比のJ0 (α) :=直接推定は有用であると考えている．
これまでに，バイグラムの尤度比を直接推定する手法が提案されている [3]．この手法では，バイグラムの尤度比に対して直接推定可能な基底関数を提案し，それを用いて推定式の定式化を行った．また，カタカナ語の直前に出現するバイグラを推定

(4)

(5)

するという単純な実験を用により提案手法の有効性を検証した．

ここで，目的関数を最小化するパラメータ α に関わらない項

この手法では，尤度比の推定時に尤度比の分母の確率の推定値を取り除き， J(α) を定義する．
∫
1
J(α) := J0 (α) −r(x)2 pde (x)dx2にパラメータ λ を加算することで，分母の確率の値に応じて，
尤度比の推定値に補正を行っている．しかし，この手法ではバイグラムの頻度のみを使用するため，学習データに存在しないバイグラムに対しては，尤度比を推定することができない．
確率を補正する手法としてはスムージングがよく用いられる．
自然言語を対象にしたスムージングの一つとして Good–Turing
スムージング [6] が存在する．Good–Turing スムージングは自(6)ˆそして，データから確率を推定し，コスト関数の推定式 J(α)
を得る．
n
n
∑
1∑
ˆ
J(α)
:=
r̂(xi )2 p̂de (xi ) −r̂(xi )p̂nu (xi )
2 i=1
i=1

(7)

然言語の出現頻度が Zipf の法則に従う事を利用して，ゼロ頻ˆ
ここで， n はサンプルサイズである．J(α)に安定化のため l2度の出現確率を推定し，その推定値を用いて全体の確率の補正

正則化項を付加し以下の最適化問題を得る．
][
λˆminv J(α)+ αT αα∈R2を行う．また，n–gram モデルに対するスムージングに低次の(n-1)–gram を用いた手法としては，バックオフスムージング [7](8)や，その改良の Kneser–Ney スムージング [8] などが存在する．
学習データ中に存在しない n–gram に対しては，(n-1)–gram

ここで， v はパラメータの次元数である．λ は正則化パラメーの頻度や，種類数を用いて推定を行う．しかし，スムージング

タであり，データにより決定される．この最適化問題を解きパ手法では，尤度比を構成する個々の確立に対する補正を行う事

ラメータ α を決定する．この最適化問題は，制約がなく凸では出来るが，尤度比そのものに対しての補正として、効果がああるため，解析的に解くことが出来る．よって，この最適化問る方法とはかぎらない．

題にて，目的関数が最小となるパラメータ α̃ を決定する．そして，尤度比であるためパラメータが非負である必要があるた
め，uLSIF では以下のように補正を行う．

3 尤度比の直接推定
尤度比の直接推定手法には二乗誤差を用いた手法 [2]，ロジス
ティック回帰を用いた手法 [9]，カルバック・ライブラー距離を用いた手法 [10], エントロピーという条件下において最尤推定を用いた手法 [11] などが提案されている．その中で，本研究では二乗誤差を用いた手法である，unconstrained Least-Squares

Importance Fitting（uLSIF） [2] を用いて定式化を行う．uLSIF は上記の手法のうち，解析的に尤度比の直接推定を行える
唯一の手法である．本節では，uLSIF について説明を行う．

pnu (x)pde (x)る．学習により決定されるパラメータのベクトル α と基底関数のベクトル ϕ の線形和で尤度比が表現が出来ると仮定する．
尤度比の直接推定において，この基底関数の選択が重要となる．

=

v
∑
i=1

ここで， 0v は v 次元の要素が全て 0 のベクトルであり，このmax は α の全ての要素に個別に適用される．以上の手順により r(x) の推定量 r̂(x) を求める．

4 提案手法
ここでは，バイグラム “wi wj ” の出現確率を P (wi ∈ Rc , wj ∈間内の i 番目の要素を表す．P (wi ∈ Rc , wj ∈ Rc ) はバイグラ(1)

ここで x は入力で，標本空間からサンプリングされた要素であr̂(x) :=αT ϕ(x)(2)ムの出現確率であるが，定式化の簡単化のために，引数を 2 つ用いる．P (wi ∈ Rc , wj ∈ Rc ) はバイグラム “wi wj ” の出現確率を表すため P (wi ∈ Rc , wj ∈ Rc ) と P (wj ∈ Rc , wi ∈ Rc )は異なる確率を表す．また，P (wi ∈ Rc , ∗) は 1 文字目に wi をとり， 2 文字目を限定しない確率となり，つまり，2 文字目につ∑x∈Rc P (wi , x)

いて周辺化を行った確率であり，P (wi , ∗) =となる．

この定式化で使用する関数を以下のように定義する．

αi ϕi (x)(9)

Rc ) と表す．Rc は全ての文字空間を表す．また， wi は文字空推定を行う尤度比を以下のように定義する．

r(x) :=

α̂ := max(0v , α̃)(3)p(wi , wj ) := P (wi ∈ Rc , wj ∈ Rc )(10)p(wi , wj | D) := P (wi ∈ Rc , wj ∈ Rc | D)(11)

ru (wi , ∗) :=p(wi , ∗ | D)p(wi , ∗)(18)

ru (∗, wj ) :=p(∗, wj | D)p(∗, wj )(19)

p(wi , ∗) := P (wi ∈ Rc , ∗)(12)p(∗, wj ) := P (∗, wj ∈ Rc )(13)

また， ê(wi , wj ) はバイグラムとユニグラムの頻度を用いた補p(wi , ∗ | D) := P (wi ∈ Rc , ∗ | D)

(14)

正関数である．定式化では，まずユニグラムの尤度比の推定をp(∗, wj | D) := P (∗, wj ∈ Rc | D)

(15)

ラムの尤度比の真値との二乗誤差が最小となるように推定を

ここで， D は推定を行う条件を表している．実験では，カタ
カナ後の直前という条件を使用している．

p(wi , wj | D)p(wi , wj )行う．
まず，ユニグラムの尤度比 ru (wi , ∗) の推定を行う．尤度比

推定対象の尤度比を以下のように定義する．

r(wi , wj ) :=行う．そしてユニグラムの尤度比と補正関数を用いて，バイグ

ru (wi , ∗) の推定量 r̂u (wi , ∗) をパラメータ β と，基底関数 ϕuを用いて表す．

(16)r̂u (wi , ∗) := β T ϕu (wi , ∗)[3] の研究においては，バイグラムの尤度比に対して，バイグラムのみを用いた定式化が行われいる．この定式化では，学

=

vu
∑

βi′ ϕui′ (wi , ∗)

(20)
(21)

i′ =1

習データにおいて出現頻度が低いバイグラムに対して強く補正を行うことで，推定性能を向上させている．しかし，学習デー

ここで，β はベクトルであり， βi は β の i 番目の要素であタに出現しないバイグラムに対しては，推定値がゼロとなってる．同様に ϕu もベクトルであり， ϕui は ϕu の i 番目の要しまう問題がある．

素である．ここで， vu はデータに含まれるユニグラムの種類提案手法では，学習データに存在しないバイグラムに対して数であり，ベクトルの次元数でもある．現実のデータに対して推定を行うためにバイグラムの確率分布の周辺分布であるユニは，i は文字コード， vu は文字コードの種類数に対応する．

グラムの確率分布を用いることを考える．ユニグラムの独立を

ユニグラムの尤度比の推定のために以下の事象に対して独立仮定すると，バイグラムの尤度比をその周辺分布であるユニグな基底関数を定義する．

ラムを用いて以下のように表現できる．

ϕui (x, ∗) :=P (wi , wj | D)
P (wi , ∗ | D)P (∗, wj | D)=×
P (wi , wj )P (wi , ∗)P (∗, wj )1(x = wi )0otherwise(22)

このユニグラムの尤度比を用いて構成したバイグラムの尤度比

ここで，x は関数の引数で wi のような Rc の要素であり，基を補正する形式で推定値を以下のように定めた．

底関数の定義の簡単化のために使用している．この基底関数の定義により r̂u (wi , ∗) は以下のように展開することが出来る．

r̂(wi , wj ) := ê(wi , wj ) + r̂u (wi , ∗)r̂u (∗, wj )ここで， r̂u はユニグラムの尤度比の推定値であり， ê は補正

r̂u (wi , ∗) =vu∑

βi′ ϕui′ (wi , ∗)

(23)

i′ =1

関数である．まず，独立して計算可能な，ユニグラムの尤度比=βiを定式化する．基底関数には，推定する事象に対して独立な基(24)底関数を用いる．そして，推定したユニグラムの尤度比を用い

この r̂u (wi , ∗) を真の尤度比 ru (wi , ∗) の二乗誤差を最小にすて，バイグラムの尤度比全体の真値と推定値の二乗誤差が最小るように決定していく．コスト関数を以下のように定義する．

となるように，補正関数を定式化する．推定した補正関数と，ユニグラムの尤度比で構成したバイグラムの尤度比を用いて，

1∑(r̂u (wi , ∗) − ru (wi , ∗))2 p(wi , ∗)
2 i=0
vu

Ju0 (β) :=バイグラムの尤度比の推定式とする．

(25)

これを展開し，定数を除外した Ju (β) を以下のように定義する．

4. 1 定 式 化
バイグラムの尤度比の推定値を補正関数とユニグラムの尤度比を用いて以下のように定義する．

Ju (β) :=

vu
vu
∑
1∑
r̂u (wi , ∗)2 p(wi , ∗) −r̂u (wi , ∗)p(wi , ∗ | D)
2 i=1
i=1

(26)
r̂(wi , wj ) := ê(wi , wj ) + r̂u (wi , ∗)r̂u (∗, wj )(17)

これは，ユニグラムの独立を仮定することで，ユニグラムの尤度比を用いてバイグラムの尤度比を表現している．ここで， r̂uはユニグラムの尤度比の推定量である．ユニグラムの尤度比を以下ように定義する．

データから Ju (β) の推定値 Jˆu (β) を得る．
vu
vu
∑
1∑
r̂u (wi , ∗)2 p̂(wi , ∗) −r̂u (wi , ∗)p̂(wi , ∗ | D)Jˆu (β) :=
2 i=1
i=1

(27)
この二乗誤差を最小とするようにパラメータ β を決定する．

[
min
v

β∈R u

λu T
Jˆu (β) +
β β
2

]
(28)

ここで， λu は正則化パラメータであり，データから決定される．この最適化問題は β に関する二次関数であり，係数は全て非負であるため下に凸な関数である．よって最適化問題は解

ここで，x と y は関数の引数で wi のような Rc の要素であり，基底関数の定義の簡単化のために使用している．基底関数の定義により r̂(wi , wj ) は以下のようになる．

r̂(wi , wj ) == αij + U (wi , wj )

得る．

(30)

βi (p̂(wi , ∗) + λu ) = p̂(wi , ∗ | D)(31)p̂(wi , ∗ | D)p̂(wi , ∗) + λu

(32)

二乗誤差が最小となるようにパラメータ α の推定を行う．以下のようにコスト関数 J0 (α) を定義する．

J0 (α) :=

(45)

1 ∑
r(wi , wj )2 p(wi , wj )2 i,j=1
v

(33)
(34)

p̂(wi , ∗ | D)p̂(wi ∗) + λu

(46)

(35)

関わらない項である．
続いて， r̂(wi , wj ) を以下のように展開する．

また，r̂u (∗, wj ) の場合も同様に定式化すると，その推定量p̂(∗, wj | D)p̂(∗, wj ) + λu

1 ∑ T
(α ϕ(wi , wj ))2 p(wi , wj )2 i,j=1v

J0 (α) =は以下のようになる．

+
(36)

v
∑

αT ϕ(wi , wj )U (wi , wj )p(wi , wj )

i,j=1

−

定式化したユニグラムの尤度比を使用して， r̂(wi , wj ) を以v∑

αT ϕ(wi , wj )p(wi , wj | D) + C2

(47)

i,j=1

下のように表す．

1 ∑
U (wi , wj )2 p(wi , wj )2 i,j=1v

r̂(wi , wj ) = ê(wi , wj ) + U (wi , wj )U (wi , wj ) :=r̂(wi , wj )p(wi , wj | D) + C1

ここで， C1 はパラメータである α を含まないため最小化に=βir̂u (∗, wj ) =

v
∑
i,j=1

C1 :=

i′ =1

=

(44)

1 ∑
r̂(wi , wj )2 p(wi , wj )2 i,j=1−

義より r̂u (wi , ∗) は以下のようになる．

βi′ ϕui′ (wi , ∗)1 ∑(r̂(wi , wj ) − r(wi , wj ))2 p(wi , wj )2 i,j=1v=

また，この βi は常に正となり，補正は必要ない．よって，定r̂u (wi , ∗) =

(43)

v

∂ ˆ
λu T
(Ju (β) +β β) = 0
∂βi
2

vu
∑

(42)

バイグラムの尤度比の推定量 r̂(wi , wj ) と真値 r(wi , wj ) の(29)

微分した i 番目の要素に対して解くと以下のようになる．

βi =αi′ j ′ ϕi′ j ′ (wi , wj ) + U (wi , wj )i′ ,j ′ =1

析的に解くことが出来る．β で微分し，0v と置き，最適解を

∂ ˆ
λu T
(Ju (β) +β β) = 0v∂β2∑p̂(wi , ∗ | D)p̂(∗, wj | D)×p̂(wi , ∗) + λup̂(∗, wj ) + λu

(37)
(38)

C2 :=

−

v
∑

U (wi , wj )p(wi , wj | D) + C1

(48)

i,j=1

ここで，補正関数 ê(wi , wj ) をデータにより決定されるパラ
メータ α と基底関数 ϕ(wi , wj ) を用いてて表し，尤度比の推定値を以下のように表す．

r̂(wi , wj ) = αT ϕ(wi , wj ) + U (wi , wj )∑=αi′ j ′ ϕi′ j ′ (wi , wj ) + U (wi , wj )最適化に関係のない項 C2 を削除しコスト関数 J(α) を得る．

J(α) := J0 (α) − C2
(39)
(40)

i′ ,j ′ =1(49)

データから p を推定し J の推定値 Jˆ を得る．
ˆJ(α)
に安定化のために l2 正則化項を追加し，以下のような素を表す．v は変数 wi と wj が取り得る事象の数となる．実験

最小化問題を得る．
[
]
λb T
ˆ
min
J(α)
+
α α
2
α∈Rv×v

では，データに出現した文字の種類数となっている．また，αここで， λb は正則化パラメータであり，データから決定されはベクトルであり，αij は α の (i × v + j) 番目の要素を表す．

る．これは誤差関数を構成するパラメータ α を決定する最小基底関数は， [3] にて提案されている，以下の基底関数を用化問題である．このパラメータは補正関数を表現するためのパここで，ϕ はベクトルであり，ϕij は ϕ の (i × v + j) 番目の要いる．

ϕij (x, y) :=(50)

ラメータであるため αT α の正則化項があるのは妥当である．

1(x = wi , y = wj )0otherwise

そして，α は負数になっても問題がないため，制約は必要ない．

(41)

この最適化問題は， α に関する二次関数であり，係数は全て非負であるため下に凸な関数である．よって最適化問題は，解析的に解くことが出来る．α で微分し 0v×v と置き，最適解を

D はカタカナ語の直前に出現するという条件である．つまり，得る．微分した，(i × v + j) 番目の要素に対して解くと以下の

この尤度比の値が高ければ高いほど，カタカナ語の直前に出現ようになる．

しやすいバイグラムであるということになる．

∂
1(Jˆ + αT α) = 0
∂αij
2

(51)

αij p̂(wi , wj ) + U (wi , wj )p̂(wi , wj )− p̂(wi , wj | D) + αij λb = 0

αij =p̂(wi , wj | D) − U (wi , wj )p̂(wi , wj )p̂(wi , wj ) + λbr̂P roposed (wi , wj ) = max(r̃(wi , wj ), 0)r̃(wi , wj ) =(54)

U (wi , wj ) =p̂(wi , ∗ | D)p̂(∗, wj | D)×p̂(wi , ∗) + λup̂(∗, wj ) + λur̂U nigram (wi , wj ) =
(55)
(56)

尤度比は非負である必要があるため，以下のように尤度比の推定値全体に補正を行い，バイグラムの尤度比の推定式を得る．

r̂(wi , wj ) = max(r̃(wi , wj ), 0)r̃(wi , wj ) =U (wi , wj ) =(57)

p̂(wi , wj | D) − U (wi , wj )p̂(wi , wj )p̂(wi , wj ) + λb

+ U (wi , wj )p̂(wi , ∗ | D)p̂(∗, wj | D)×p̂(wi , ∗) + λup̂(∗, wj ) + λup̂(wi , ∗ | D)p̂(∗, wj | D)×p̂(wi , ∗) + λup̂(∗, wj ) + λup̂(∗, wj | D)p̂(wi , ∗ | D)×p̂(wi , ∗) + λuu
p̂(∗, wj ) + λuu（ 3 ） バイグラムのみを用いた推定r̂Bigram (wi , wj ) =p̂(wi , wj | D)p̂(wi , wj ) + λ（ 4 ） 最尤推定を用いた間接推定r̂M LE (wi , wj ) =p̂(wi , wj | D)p̂(wi , wj )（ 5 ） Simple Good-Turing を用いた間接推定

(58)
(59)

式 (58) の第一項がバイグラムとユニグラムの頻度を用いた補正関数，第二項がユニグラムのみを用いたバイグラムの尤度比である．補正関数の分子は p̂(wi , wj | D) − U (wi , wj )p̂(wi , wj )となっている．この補正関数の分子の第一項はバイグラムを用いた尤度比の分子の確率の推定値である．補正関数の分子の第二項はユニグラムを用いて表現したバイグラムの尤度比とバイグラムの尤度比の分母の確率の推定値の積であり，つまりバイグラムとユニグラムを用いて表現した尤度比の分子の確率の推定値である．これは，バイグラムのみで表現した尤度比の分子の確率の推定値と，バイグラムとユニグラムを用いて表現した
尤度比の推定値の差を取ることで補正を行っていることになる．

5 実

U (wi , wj ) =（ 2 ） ユニグラムのみを用いた推定p̂(wi , wj | D) − U (wi , wj )p̂(wi , wj )p̂(wi , wj ) + λb

+ U (wi , wj )p̂(wi , wj | D) − U (wi , wj )p̂(wi , wj )p̂(wi , wj ) + λb
+ U (wi , wj )(53)

式 (54) を式 (43) に代入すると以下のようになる．

r̃(wi , wj ) =（ 1 ） 提案手法

(52)

αij (p̂(wi , wj ) + λb ) =p̂(wi , wj | D) − U (wi , wj )p̂(wi , wj )比較手法は以下の 5 種類を用いる．

験

実験では，カタカナ語の直前に出現するバイグラムの推定という単純な実験を行う．例えば，“平方メートル” という文字列があったとすると，“メートル” がカタカナ語となり，“平方”がカタカナ語の直前に出現するバイグラムとなる．正解が明確であり，尤度比の推定性能を定量的に評価出来る実験である．
実験では，以下の尤度比を推定する．

P (wi , wj | D)
P (wi , wj )P (wi , wj ) はバイグラム “wi wj ” が出現する確率である．また，r̂SGT (wi , wj ) =p̂∗ (wi , wj | D)p̂∗ (wi , wj )ここで，p̂ は最尤推定を用いた確率の推定値であり， p̂∗ はSimple Good–Turing を用いた確率の推定値である．
提案手法は，ユニグラムとバイグラムの両方を用いた直接推定法である．それに対して，ユニグラムのみを用いた推定は，提案手法のユニグラム部分のみを取り出した手法であり，独立を仮定したユニグラムのみを用いた時の推定性能を確認する．
バイグラムのみを用いた推定は，[3] にて提案された手法である．
この手法は分母に加算された λ により補正を行い，頻度が低い
場合に推定値を低く見積もる手法である．最尤推定を用いた間接推定は，最も単純な尤度比の推定方法であり，本実験においてはベースラインに相当する．Simple Good–Turing を用いた
間接推定は，尤度比を構成する個々の確率分布の推定を補正する手法である．

5. 1 実 験 手 順
実験では，1991–1997 年の毎日新聞記事コーパス 1 を用いて，各年度に対してそれぞれ実験を行う．各年度のデータから，学
習データ，バリデーションデータ，テストデータをそれぞれ重複がないように抽出する．学習データについては，10,000 記
事，2,500 記事の大小 2 種類用意する．バリデーションデータ
とテストデータにはそれぞれ 1,000 記事を用いる．
実験は以下の手順で行う．まず，学習データとバリデーショ
1：http://www.nichigai.co.jp/sales/mainichi/mainichi-data.html (accessed 2018–12–28)

ンデータを用いて，それぞれの手法のパラメータを決定する．

表 1 学習データ 10,000 件の時のチューニングしたパラメータ

詳細については後述する．学習データと決定したパラメータをyear

用いて，テストデータに出現する全てのバイグラムに対して，

1991 0.1 0.001 0.00526 0.00495

λu

λb

λuu

λ

1992 0.1 0.001 0.00493 0.00476

尤度比の値を推定する．推定した尤度比の値を用いて，バイグ

1993 0.1 0.001 0.00895 0.05398

ラムを降順にソートし，上位からランクを付ける．上位から順1994 0.1 0.001 0.01125 0.00470に正誤判定を行い，ランク毎に再現率を算出する．正誤判定に1995 0.1 0.001 0.00956 0.00420

は，判定を行うバイグラムが，テストデータ中のカタカナ後の1996 0.1 0.001 0.99997 0.07287

直前に出現していれば正解，出現していなければ不正解とする．

1997 0.1 0.001 0.96414 0.03774

このランクと再現率を用いて，上位 10,000 件までのランク–再現率曲線をプロットする．ランク–再現率曲線は横軸にランク，

表 2 学習データ 2,500 件の時のチューニングしたパラメータyear

縦軸にそのランクにおける再現率をプロットしたグラフである．
評価にはランク–再現率曲線を用いる．再現率は以下の式で

λb

λuu

λ

1992 0.1 0.001 0.00374 0.00093

表される．

Recall =λu

1991 0.1 0.001 0.00544 0.01925
1993 0.1 0.001 0.00850 0.00475
1994 0.1 0.001 0.01308 0.01540

Number of true positive
Number of true bigrams

1995 0.1 0.001 0.00931 0.00337
1996 0.1 0.001 0.98831 0.04789

ランク–再現率曲線の下の面積（AUC）の値が大きければ大き1997 0.1 0.001 0.99979 0.00835

いほど，推定の性能が良いことになる．ランク–再現率曲線において，原点からあるランクの曲線上に位置する点を結ぶ直線

表 3 学習データ 10,000 件: AUC TOP-10000

Proposed Unigram

BigramMLE

SGTの傾きが，そのランクでの適合率の大きさに比例する．適合率yearは以下の式で表される．

1991

5236.173520.98 5232.97 3897.38 906.53

1992

5171.60

3591.00 5149.53 3831.91 781.21

1993

5111.823391.24 5109.50 3729.15 826.95

1994

5058.163376.45 5064.55 3573.85 762.20

1995

5203.723387.37 5193.74 3766.72 834.79

1996

4825.313239.57 4840.10 3396.49 815.50

1997

4997.26

3251.62 5001.48 3449.03 835.26

Precision =Number of true positive
Number of total output

5. 2 パラメータの決定
パラメータの決定は，各手法，各年度ごとに行う．このパラメータはバリデーションデータを用いて決定する．
パラメータは上位 10, 000 件までのランク–再現率曲線の面積を用いて決定する．ランク–再現率曲線の下の面積の値が大きければ大きいほど，推定の性能が良いことになる，よってこの面積が最大になるようにパラメータを決定する．
提案手法には，パラメータ λu , λb が存在する．それぞれのパラメータを 0.1 から 10−20までの間を 0.1 倍ずつ変化させ

5. 3 実 験 結 果
学習データを 10,000 件用いた場合の実験結果を表 3 に示す．
各年度において，最も性能の良い手法に対して下線が引いてある．提案手法と，バイグラムのみを用いた手法の性能が高く，あまり性能の差が無いことが分かる．学習データを 10,000 件て，その中で，AUC の面積が最大になったパラメータを用い用いた場合の 1991 年のランク–再現率曲線を図 1 に示す．提案

た．また，性能が同じになるパラメータについては，パラメー

手法と，バイグラムのみをもちいた手法のグラフがほぼ重なっ

タの値が小さい方を採用する．

ていることが分かる．ユニグラムのみを用いた推定でも，上位

また，比較手法であるユニグラムのみを用いた手法とバイグ

においては最尤推定を用いた間接推定より良い性能を示していラムのみを用いた手法にはそれぞれそれぞれパラメータ λuu , λる．最尤推定を用いた間接推定は，ほぼ直線のグラフになってが存在する．こちらは，0 から 1 までの間を 0.00001 刻みで探おり，全てのランクにおいて一定の正解率となっている．

索を行い，その中で，AUC の面積が最大となったパラメータ

学習データを 2,500 件用いた場合の実験結果を表 4 に示す．

を用いた．また，性能が同じになるパラメータについては，パ提案手法がいずれのデータにおいても，最も良い性能であるラメータの値が小さい方を採用する．

ことが分かる．学習データを 2,500 件用いた場合の 1991 年の決定したパラメータをそれぞれ表 1,2 に示す．提案手法のパ

ランク–再現率曲線を図 2 に示す．どのランクにおいても，提ラメータは何れのデータセットにおいても λu = 0.1, λb = 0.001

案手法がもっとも良い性能であることが分かる．また．ランク

3,000 件から 6,000 件までのバイグラムのみを用いた手法の性となっている．
また，実験に使用した NLTK バージョン 3.2.5 における Sim-能が低下している区間でも提案手法は安定した性能を示してい

ple Good-Turing のパラメータには，1 文字目のバイグラムのる．上位 6,000 件以降は，学習データ中に存在しないバイグラ

種数と 2 文字目のバイグラムの種数の積を用いた．

ムが出現し，バイグラムのみを用いた手法，最尤推定を用いた

2

間接推定の 2 手法では，尤度比の値がゼロとなり，推定出来てないことが分かる．そのような状況下においても，提案手法は2：https://www.nltk.org/ (accessed 2019–01–25)

ユニグラムの尤度比を推定出来ている．

習データ中に現れやすいバイグラムを上位に得ることが出来た
1.0
0.8

Recall Rate

ためではないかと考えている．

Proposed
UnigramBigramMLE
SGT

Simple Good–Turing を用いた間接推定では上位では最尤推定を用いた間接推定を超える性能を示しているが，上位 200 件を超えると，性能が悪化している．これは，Zipf の法則を用

0.6

いた，ゼロ頻度の補正を尤度比の分子と分母で個別に行っていることが問題になっているのではないかと考えている．分子の0.4

確率と分母の確率の補正を別々に行っているので，例えば学習データ 10,000 件の 1991 年のデータの場合は一度も出現しない

0.2

バイグラムの尤度比の値は 18.987 という非常に高い値になる．
0.0

0

2000

4000

Rank

6000

8000

10000

図 1 学習データ 10,000 件: 上位 10,000 件におけるランク–再現率曲これが原因で，学習データ中に存在しないバイグラムが上位に出現し，性能が悪化していると考えている．
図 2 を見ると，提案手法がもっとも良い性能であることが分
かる．学習データが 2,500 件の場合には，上位 6,000 件以降に線 (1991 年)

おいて，バイグラムのみを用いた手法と最尤推定を用いた間接表 4 学習データ 2,500 件: AUC TOP-10000

year

Proposed Unigram

BigramMLE

推定の 2 手法では分子の確率の推定値がゼロとなり，以降の尤SGT度比の推定値はゼロとなる．提案手法は，そのような場合においても，ユニグラムの確率分布を用いて推定出来ている．また，

1991

4721.273471.35 4539.07 4013.22 731.79

1992

4489.98

3421.78 4316.80 3818.86 761.07

1993

4650.66

3388.82 4503.14 3937.51 644.32

1994

4530.18

3371.54 4351.56 3774.82 612.02

から 5,000 件の間でもバイグラムのみを用いた手法と比べて，

1995

4736.463380.14 4591.47 4008.43 753.08

性能が向上していることが分かる．これは，バイグラムの尤度

1996

4398.24

3224.73 4241.56 3645.88 740.06

比に対してユニグラムを用いた定式化を行ったことにより，ユ

1997

4484.463206.43 4345.84 3778.61 683.06

ニグラムの頻度を用いた尤度比の補正が適切に行えていること

学習データにバイグラムが存在する場合，例えば上位 3,000 件を示せていると考えている．
1.0

Proposed
UnigramBigramMLE
SGT

Recall Rate

0.8
0.6

6 ま と めバイグラムの尤度比に対して，バイグラムの確率分布の周辺分布であるユニグラムの確率分布を用いた定式化を行った．連
続分布に対する直接推定では，ガウス関数を基底関数に用いることで，推定を行う点の近傍を推定に利用している．バイグラ

0.4

ムでは，その周辺分布であるユニグラムを用いることで，頻度の小さいケースの推定に効果があるのではないかと考えた．

0.2
0.0

定式化したバイグラムの尤度比の推定式を用いて，バイグラ
0

2000

4000

Rank

6000

8000

10000

図 2 学習データ 2,500 件: 上位 10,000 件におけるランク–再現率曲線 (1991 年)

ムのみを用いた手法，ユニグラムのみを用いた手法，最尤推定を用いた間接推定，Simple Good–Turing を用いた間接推定などと比較を行った．実験には，カタカナ語の直前に出現するバ
イグラムの推定という単純な実験を行った．実験の結果，学習データが小さい場合に，提案手法はバイグラムの確率分布の周5. 4 考察

図 1 を見ると，提案手法はデータが大きい場合は，バイグラ
ムのみを用いた手法とほぼ同様の性能となり，バイグラムのみ

辺分布であるユニグラムの確率分布を用いて推定を行い，最も良い性能となることを確認した．また，学習データが大きい場合においても，バイグラムのみを用いた手法と同等の性能を示していることを確認した．

を用いた手法を除く他の手法よりも良い性能を示す．これは，推定値と真値の二乗誤差を最小とするという直接推定のフレームワークが，自然言語のような離散分布のデータに対しても有効であると考えている．
また，ユニグラムのみを用いた手法でも，最尤推定を用いた
間接推定よりも，上位では良い性能を示している．これは，尤度比の分母の値に応じて補正を行うパラメータ λuu により，学文

献[1] 杉山将. 密度比推定によるビッグデータ解析. 電子情報通信学会
誌, Vol. 97, No. 5, pp. 353–358, 2014.
[2] Takafumi Kanamori, Shohei Hido, and Masashi Sugiyama.
A least-squares approach to direct importance estimation.
Journal of Machine Learning Research, Vol. 10 (Jul.), pp.
1391–1445, 2009.
[3] K. Kawakami, M. Kikuchi, M. Yoshida, and K. Umemura.

[4]

[5]

[6]
[7]

[8]

[9]

[10]

[11]

Direct Estimation of Likelihood Ratio for the Analysis ofContext. In Proceedings of the 5th International Conference on Advanced Informatics: Concept Theory and Applications, pp. 1–6, 2018.
Masashi Sugiyama, Ichiro Takeuchi, Taiji Suzuki, Takafumi Kanamori, Hirotaka Hachiya, and Daisuke Okanohara.
Least-squares conditional density estimation. IEICE Transactions on Information and Systems, Vol. E93-D, No. 3, pp.
583–594, 2010.
Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori.
Density Ratio Estimation in Machine Learning. Cambridge
University Press, Cambridge, 2012.
William A Gale. Good-Turing Smoothing Without Tears.
Journal of QuantitativeLinguistics, Vol. 2, pp. 1–24, 1995.
Slava M. Katz. Estimation of probabilities from sparse
data for the language model component of a speech recognizer. IEEE Trans. Acoustics, Speech, and Signal Processing, Vol. 35, No. 3, pp. 400–401.
R. Kneser and H. Ney. Improved backing-oﬀ for M-gram
language modeling. In 1995 International Conference on
Acoustics, Speech, and Signal Processing, pp. 181–184 vol.1,
1995.
Steﬀen Bickel, Michael Brückner, and Tobias Scheﬀer. Discriminative Learning for Diﬀering Training and Test Distributions. In Proceedings of the 24th International Conference on Machine Learning, pp. 81–88, 2007.
Masashi Sugiyama, Shinichi Nakajima, Hisashi Kashima,
Paul von Bünau, and Motoaki Kawanabe. Direct Importance Estimation with Model Selection and Its Application
to Covariate Shift Adaptation. In Proceedings of the 20th
International Conference on Neural Information Processing Systems, pp. 1433–1440, 2007.
Taiji Suzuki, Masashi Sugiyama, Jun Sese, and Takafumi
Kanamori. Approximating Mutual Information by Maximum Likelihood Density Ratio Estimation. In Proceedingsof the Workshop on New Challenges for Feature Selection in
Data Mining and Knowledge Discovery at ECML/PKDD
2008, pp. 5–20, 2008.