特徴重み付けを用いた
低・ゼロ頻度N-gramに対する尤度比の推定法
菊地 真人, 吉田 光男, 梅村 恭司（豊橋技術科学大学）※ 本資料は下記のサイトからもご覧いただけます。
DEIM 2020 F8-4(day2 p55)

http://www.ss.cs.tut.ac.jp/~kikuchi14/尤度比とは？
• 尤度比– 確率分布の比で表され、二値分類や統計検定でよく用いられる

𝑝nu 𝑥𝑟(𝑥) =𝑝de 𝑥

𝑥 は単語列や文字列などの離散要素– 尤度比 𝑟(𝑥) が大きいほど 𝑥 は確率分布 𝑝nu 𝑥 から生成されやすく、小さいほど 𝑝de 𝑥 から生成されやすい• 尤度比の実用には推定が必要– アプリケーションに影響を及ぼす重要なプロセス– 本研究では、𝑥 の観測頻度から尤度比を推定する

1

尤度比の素朴な推定法

2• 確率分布を相対頻度で求め、その比を取ること

𝑝nu 𝑥𝑟MLE (𝑥) =𝑝de 𝑥𝑓∗ 𝑥𝑝∗ 𝑥 =, ∗∈ de, nu𝑥 𝑓∗ 𝑥– 𝑓∗ 𝑥 は確率分布 𝑝∗ 𝑥 から得た 𝑥 の頻度•𝑥 𝑓de 𝑥A= 107 , 𝑓de 𝑥A = 5000,𝑓de 𝑥A𝑝de 𝑥A =𝑥 𝑓de 𝑥A
5000
=
107

𝑥 𝑓nu 𝑥A

𝑓nu 𝑥A𝑝nu 𝑥A =𝑥 𝑓nu 𝑥A
100= 410= 104, 𝑓nu 𝑥A = 100

10−2
𝑟MLE 𝑥A =5 × 10−4= 20

素朴な推定法の問題点①3• 要素 𝑥B から 𝑥D についても、推定量 𝑟MLE 𝑥 を計算
頻度𝑥𝑓de 𝑥𝑥

𝑓nu 𝑥

𝑓de 𝑥𝑥𝑟MLE 𝑥𝑓nu 𝑥𝑥A

107

5000

104

10020𝑥B

107

50

104

120𝑥C107

50

104

大差 240𝑥D107

1410400偶然かも•① 低頻度に対する推定値は変動が大きく不安定– 𝑓∗ 𝑥A と 𝑓∗ 𝑥B は大差あるが、要素 𝑥A と 𝑥B の推定値は20と等しい⇒ 頻度差を推定値に反映したい素朴な推定法の問題点①4• 要素 𝑥B から 𝑥D についても、推定量 𝑟MLE 𝑥 を計算
頻度𝑥𝑓de 𝑥𝑥•𝑓nu 𝑥𝑓de 𝑥𝑥𝑟MLE 𝑥𝑓nu 𝑥𝑥A

107

5000

10410020𝑥B

107

50104

120𝑥C

10750104

240𝑥D

107

1410400① 低頻度に対する推定値は変動が大きく不安定

差1大きく変動– 𝑓nu 𝑥B と 𝑓nu 𝑥C の差は１しかないが、推定値は20と40で大きく変動⇒ 低頻度に対する推定値をロバストにしたい素朴な推定法の問題点②5• 要素 𝑥B から 𝑥D についても、推定量 𝑟MLE 𝑥 を計算
頻度𝑥𝑓de 𝑥𝑥•𝑓nu 𝑥𝑓de 𝑥𝑥

𝑟MLE 𝑥𝑓nu 𝑥𝑥A

1075000

10410020𝑥B

10750104120𝑥C

10750104240𝑥D

1071410400② ゼロ頻度に対して有効な推定値を算出できない– 𝑓nu 𝑥D = 0 のとき、他の頻度に依らず 𝑟MLE 𝑥D = 0⇒ データにない要素に対しても、有効な推定値を与えたい

先行研究：
正則化を導入した手法 [菊地:19]

6• 確率分布の推定を経由せず、最適化の枠組みで尤度比を直接推定– 正則化パラメータ 𝜆 が推定値を低めに見積もる– 𝜆 がゼロのときは 𝑟MLE 𝑥 と等価

𝑝nu 𝑥𝑟(𝑥) =𝑝de 𝑥 + 𝜆𝑓∗ 𝑥𝑝∗ 𝑥 =, ∗∈ de, nu𝑥 𝑓∗ 𝑥
頻度𝑥𝑓de 𝑥𝑥

𝑓nu 𝑥

𝑓de 𝑥

𝑟MLE 𝑥𝑓nu 𝑥𝑥𝑟 𝑥𝑥A1075000

104

1002019.6𝑥B

107

50

104

1206.7𝑥C

10750

104

24013.3𝑥D

107

14104000※ 𝑟 𝑥 の正則化パラメータ 𝜆 = 10−5

先行研究 [菊地:19] の利点（1/2）•7

正則化パラメータ 𝜆 が低頻度に起因する問題を緩和■ 頻度の差を推定値に反映できる■ 低頻度に対する推定値をロバストにできる

𝑝nu 𝑥𝑟(𝑥) =𝑝de 𝑥 + 𝜆𝑓∗ 𝑥
𝑝∗ 𝑥 =, ∗∈ de, nu𝑥 𝑓∗ 𝑥
頻度𝑥𝑓de 𝑥𝑥

𝑓nu 𝑥

𝑓de 𝑥

𝑟MLE 𝑥𝑓nu 𝑥𝑥

𝑟 𝑥𝑥A

107

5000

104

1002019.6𝑥B

107

50

104

1206.7𝑥C

10750

104

24013.3𝑥D

107

14104000※ 𝑟 𝑥 の正則化パラメータ 𝜆 = 10−5

先行研究 [菊地:19] の利点（2/2）•8

正則化パラメータ 𝜆 が低頻度に起因する問題を緩和■ 頻度の差を推定値に反映できる■ 低頻度に対する推定値をロバストにできる

𝑝nu 𝑥𝑟(𝑥) =𝑝de 𝑥 + 𝜆𝑓∗ 𝑥𝑝∗ 𝑥 =, ∗∈ de, nu𝑥 𝑓∗ 𝑥
頻度𝑥𝑓de 𝑥𝑥

𝑓nu 𝑥

𝑓de 𝑥

𝑟MLE 𝑥𝑓nu 𝑥𝑥

𝑟 𝑥𝑥A

107

5000

104

1002019.6𝑥B

107

50

104

1206.7𝑥C

107

50

104

24013.3𝑥D

107

14104000※ 𝑟 𝑥 の正則化パラメータ 𝜆 = 10−5

先行研究 [菊地:19] の欠点•9𝑟𝑀𝐿𝐸 𝑥 と同様、ゼロ頻度の問題に対処できない■ 𝑓nu 𝑥D = 0 のとき、𝑝nu 𝑥 = 0 なので下式もゼロ

𝑝nu 𝑥𝑟(𝑥) =𝑝de 𝑥 + 𝜆𝑓∗ 𝑥
𝑝∗ 𝑥 =, ∗∈ de, nu𝑥 𝑓∗ 𝑥
頻度𝑥𝑓de 𝑥𝑥𝑓nu 𝑥

𝑓de 𝑥

𝑟MLE 𝑥𝑓nu 𝑥𝑥

𝑟 𝑥𝑥A

107

5000

1041002019.6𝑥B

107

50

104

1206.7𝑥C

10750

104

24013.3𝑥D

107

14104000※ 𝑟 𝑥 の正則化パラメータ 𝜆 = 10−5

本研究のモチベーション

10• 離散要素 𝑥 を自然言語処理で多用される N-gram とする– N個の文字や単語が連続した系列– 𝐴𝑘 1 ≤ 𝑘 ≤ 𝑁 を特徴変数とし、 𝐴𝑘 が取る値（単語や文字）を 𝑎𝑘 とする

例）単語4-gram 𝑥 = This, is, a, sentence

𝑎1 = "This"𝑎2 = "is"𝑎3 = "a"𝑎4 = "sentence"• 𝑥 はN個の特徴を持つインスタンスとも考えられる– 𝑎𝑘 の頻度が疎な点で一般のデータセットとは異なる• 研究目的：低・ゼロ頻度を同時に対処する尤度比推定の実現– 低頻度が多い状況では、出現しない要素も多いことが想定される– 未観測の要素にも何らかの対処を要する（例：未知語の処理）

ゼロ頻度の問題への簡単な対策11• 𝑎𝑘 1 ≤ 𝑘 ≤ 𝑁 の出現に独立を仮定し、 𝑎𝑘 に対する尤度比の積をとる
𝑁𝑟𝑅 𝑥 =𝑟 𝑎𝑘 = 𝑟 𝑎1 × 𝑟 𝑎2 ⋯ × 𝑟 𝑎𝑁
𝑘=1𝑟 𝑎𝑘𝑝nu 𝑎𝑘=𝑝de 𝑎𝑘 + 𝜆

正則化パラメータの導入によって低頻度にも安定した推定値を付与– 要素 𝑥 がなくても、𝑎𝑘 が出現していれば計算できる•

しかし 𝑎𝑘 の統計的独立は、実際はほとんど成立しない– 推定性能を低下させる原因– 特徴重み付け法を応用する（本研究のポイント！）提案手法• 𝑎𝑘 の独立仮定を軽減したい– ポイント１

𝐴𝑘 に対する重み 𝑊𝑘 を導入– ポイント２

𝑎𝑘 の頻度を補正（本発表では省略）
𝑁𝑟 𝑎𝑘 𝑊𝑘𝑟ours 𝑥 =𝑘=1

𝑟 𝑎𝑘 ：頻度を補正した正則化付きの推定量•

特徴重み付け法 [Jiang:18]（既存手法）を応用– 重み 𝑊𝐾 を計算するアルゴリズム– 推定への影響小な 𝐴𝑘 には小さい重み、影響大な 𝐴𝑘 には大きい重み12本研究で用いる重み付け法 CFW13• Correlation-based Feature Weighting (CFW) filter [Jiang:18]– ナイーブベイズ分類器のための手法でシンプル・高速・効果的
前提：分類に強く寄与する特徴 𝐴𝑘 は
① クラス 𝑐 ∈ 𝐶 と強い相関を持つ（maximum mutual relevance）② 他の特徴 𝐴𝑘 ′ と相関を持たない（minimum mutual redundancy）② 𝑎𝑣𝑒𝑟𝑎𝑔𝑒 𝑟𝑒𝑑𝑢𝑛𝑑𝑎𝑛𝑐𝑦

1𝐷𝑘 = 𝑁𝐼 𝐴𝑘 ; 𝐶 −𝑁−1 ′𝑁

𝑁𝐼 𝐴𝑘 ; 𝐴𝑘 ′𝑘 =1∧𝑘 ′ ≠𝑘① 𝑟𝑒𝑙𝑒𝑣𝑎𝑛𝑐𝑒𝑁𝐼 ∙ ：正規化した相互情報量– 𝐷𝑘 をシグモイド変換し、 0, 1 の範囲に収めたものを 𝑊𝑘 とする

提案手法へ CFW を応用

14• CFW は特徴とクラスが定義されていれば使用可能– 尤度比は二値分類でよく用いられる
𝑝de 𝑥 から得た要素 𝑥 はクラス 𝑐de ∈ 𝐶 に属する
𝑝nu 𝑥 から得た要素 𝑥 はクラス 𝑐nu ∈ 𝐶 に属すると考えて CFW を適用

𝑁

𝑟 𝑎𝑘 𝑊𝑘𝑟ours 𝑥 =𝑊𝑘 ∈ 0, 1

𝑘=1

𝑟 𝑎𝑘 ：頻度を補正した正則化付きの推定量• 重みの効果– 𝑊𝑘 が０に近ければ、𝑟 𝑎𝑘 𝑊𝑘 は１に近づいて 𝑟ours 𝑥 への影響小– 𝑊𝑘 が１に近ければ、𝑟 𝑎𝑘 𝑊𝑘 は 𝑟 𝑎𝑘 に近づいて 𝑟ours 𝑥 への影響大

実験の概要15• 目的：低・ゼロ頻度の両方に対する提案手法の有効性を検証– 正則化パラメータ 𝜆 と重み 𝑊𝑘 を組み合わせたときの有効性• 実験内容– 英文コーパスで固有表現（地名・人名）の左にある単語 N-gram を予測– N-gram が固有表現の左文脈 or Not を当てる
地名：直前に前置詞が現れやすいが、前置詞は他文脈にも現れやすい
人名：直前に敬称・人を表す単語（Mr., President）などが現れやすい• なぜこの実験か？
– 地名と人名は扱う文脈の性質が異なり、提案手法のふるまい分析に便利– 正解が一意に定まるため、性能を定量的に評価できる– N-gram の次数 N が大きいと低・ゼロ頻度を多く扱う

実験データと実験条件

16• データは “ウォール・ストリート・ジャーナルコーパス” から作成
– Stanford Named Entity Recognizer でコーパスに固有表現タグを付ける– コーパスから記事をランダム抽出し、訓練・開発・評価データに分配（開発・評価データは1000記事に固定）• 実験条件：3条件から一つずつ選び、その組み合わせで実験– N-gram の次数 N： 2、4、6、8、10– 訓練データのサイズ： 2500、5000、7500、10000記事– 固有表現： 地名、人名

N=10 のとき、開発・評価データに含まれる99%以上の N-gram が訓練データに現れない

尤度比推定までの流れ
１．頻度の学習– 訓練データを N-gram 𝑎1 , 𝑎2 , ⋯ , 𝑎𝑁 に分けて 𝑎𝑘 の頻度を数え上げる■ 訓練データ全体■ 条件で指定した固有表現（地名 or 人名）の左– 訓練データから重み 𝑊𝑘 を計算

２．手法のパラメータ決定（後述）３．尤度比の推定– 評価データにある N-gram 𝑥 について、学習した頻度で尤度比を推定

𝑝ne 𝑥𝑟(𝑥) =𝑝tr 𝑥

𝑝ne 𝑥 ：固有表現の左側での出現確率
𝑝tr 𝑥 ：訓練データ全体での出現確率

17

手法の評価手順（1/3）

18(1) 推定値の降順に N-gram を並び替えて順位づけ(2) N-gram の正誤判定*(3) 上位8000件についてランクー再現率曲線を描く（評価の例）
ランクN-gram

推定値

正誤1𝑥135.8

2𝑥2

18.3

3𝑥3

14.94𝑥4

13.2

5𝑥5

9.5

6𝑥6

3.6

7𝑥70.3

手法の評価手順（2/3）

19(1) 推定値の降順に N-gram を並び替えて順位づけ(2) N-gram の正誤判定*(3) 上位8000件についてランクー再現率曲線を描く* N-gramが評価データで固有表現の左に現れれば正解
ランクN-gram

推定値

正誤

1𝑥1

35.8

正2𝑥2

18.3

正3𝑥3

14.9

正4𝑥413.2

誤5𝑥59.5

誤

6𝑥6

3.6

正7𝑥70.3

誤手法の評価手順（3/3）20(1) 推定値の降順に N-gram を並び替えて順位づけ(2) N-gram の正誤判定*(3) 上位8000件についてランクー再現率曲線を描く（下の例では7件）
ランク正誤

1234567

正正

正誤

誤

正誤

再現率 =

適合率 =

あるランクまでの正解数
評価データに含まれる正解数

そのランクまでの正解数
あるランク※ グラフ上のある点と原点を結んだ直線の傾きが、その点での適合率に比例

比較手法

21

• 正則化＋重み付け（提案手法）
𝑁𝑟 𝑎𝑘 𝑊𝑘𝑟ours 𝑥 =𝑘=1

𝑊𝑘 ∈ 0, 1𝑟 𝑎𝑘 ：頻度を補正した正則化付きの推定量• 比較手法*– ベースライン： 確率分布を相対頻度で求めて比を取る（𝜆 = 0, 𝑊𝑘 = 1）
– 重み付け： 重み付けのみを導入（𝜆 = 0）

– 正則化

： 正則化のみを導入 （𝑊𝑘 = 1）

• 正則化パラメータ 𝜆 は開発データを用いて決定– 訓練データが7500、10000記事のとき 𝜆 = 10−5、それ以外は 𝜆 = 10−4
* 頻度は提案手法と同様、補正したものを使用する

ベースライン・重み付けのみの手法は低性能

22• ランクー再現率曲線（10-gram、訓練データ10000記事、地名）
Better
重みの有効性がわずかに確認できるが両手法とも低・ゼロ頻度を上手く扱えないため低性能※ 他の条件でも同様の傾向を確認

単語 𝑎𝑘 間の出現に独立を仮定しても正則化は有効に働く

23• ランクー再現率曲線（10-gram、訓練データ10000記事、地名）
Better

大幅に性能アップ！
低頻度の単語に対しても有効な推定値を計算できる※ 他の条件でも同様の傾向を確認

正則化＋重み付けが最良性能

24• ランクー再現率曲線（10-gram、訓練データ10000記事、地名）
Better

ゼロ頻度のために仮定した独立性を重みで軽減でき、低頻度も正則化で上手く扱えた⇒ 正則化と重み付けは互いに効果的※ 他の条件でも同様の傾向を確認

人名では提案手法の有効性が顕著

25• ランクー再現率曲線（10-gram、訓練データ10000記事、人名）
Better

頻度が疎な状況でも正解の約50%を発見

人名のように分類に役立つ特徴が分かりやすいとき、重み付けの有効性が高まる

重みはNの変化に対して提案手法の性能をロバストにする

26• Nを変化させた場合のF1-尺度（適合率と再現率の調和平均）– 訓練データは10000記事に固定

ほぼ一定

（地名）

（人名）

Nが十分に大きいとき、訓練データが小さくても重み付けは有効27• 訓練データのサイズを変化させた場合のF1-尺度– Nは10に固定

訓練データのサイズによらず、性能差にあまり変化なし

（地名）

（人名）

まとめ

28

• 研究目的：– 低・ゼロ頻度の N-gram に対する尤度比推定の実現• 提案手法：– 𝑎𝑘 の出現に独立を仮定し、 𝑎𝑘 の尤度比の積をとる– 独立性仮定を緩和するために特徴重み付け法を応用
𝑁𝑟 𝑎𝑘 𝑊𝑘𝑟ours 𝑥 =𝑘=1• 評価実験：– 単語N-gram が固有表現の文脈 or Not を当てる問題■ 正則化＋重み付けが、疎性の高い文脈予測に最も有効■ Nが大きくても性能低下を軽減でき、訓練データが小さくても効果的今後の課題• 課題１：特徴値 𝑎𝑘 単位の重み付けによる性能向上– 今回、使用したのは特徴変数 𝐴𝑘 への重み付け– より細かい重み付けで、微細な推定値のコントロールを可能にしたい• 課題２：N の値にロバストな推定法の実現を目指す– N が大きい（長い）ものに対しても、安心して利用できる手法の開発• 課題３：提案手法が有効に働く実用的タスクを探す– 尤度比は “二値分類の順位づけ関数” として理論的に最適 [中西:15]– 提案手法は疎性の高い特徴を持つデータセットで特に有効

中西健太郎, 田中利幸, 上田修功. 尤度比に基づく順位づけ関数による受信者操作特性曲線下面積の漸近的性質.
電子情報通信学会技術研究報告, 2015. IBISML2014-92.

29参考文献・連絡先30• スライドで引用した重要文献– 菊地真人, 川上賢十, 吉田光男, 梅村恭司. 観測頻度に基づくゆう度比の保守的な直接推定. 電子情報通信学会論文誌D, Vol. J102-D, No. 4, pp. 289-301, 2019.
– Liangxiao Jiang, Lungan Zhang, Chaoqun Li, and Jia Wu. A correlation-based
feature weighting filter for naive Bayes. IEEE Transactions on Knowledge andData Engineering, Vol. 31, No. 2, pp. 201-213, 2018.

• 研究に関するご質問など– 菊地 真人
Email: m143313 (at) edu.tut.ac.jp
Homepage: http://www.ss.cs.tut.ac.jp/~kikuchi14/index_ja.html

就活中です！！

補足１

重み 𝑊𝑘 の具体的な値31• 重み 𝑊𝑘– 値が大きいほど、特徴 𝐴𝑘 が尤度比の推定に重要– Nが大きいときに人名直前の特徴 𝐴𝑁 が尤度比推定に強く寄与※ 訓練データは10000記事

補足２

𝑎𝑘 の頻度を補正する必要性

32• 𝑎𝑘 の独立仮定を軽減したい– ポイント１

𝐴𝑘 に対する重み 𝑊𝑘 を導入– ポイント２

𝒂𝒌 の頻度を補正
𝑁𝑟 𝑎𝑘 𝑊𝑘𝑟ours 𝑥 =𝑘=1𝑟 𝑎𝑘 ：頻度を補正した正則化付きの推定量•

問題：𝑓nu 𝑎𝑘 = 0 となる 𝑎𝑘 があれば、𝑟 𝑥 の推定値がゼロになる– 【解決策】𝑎𝑘 の頻度に微小な正の値を加算補足２

補正法 - 微小な正の値を加算• 𝑓nu 𝑎2 = 0 のとき、
– 補正なし：𝑝nu 𝑎𝑘𝑟(𝑎𝑘 ) =𝑝de 𝑎𝑘 + 𝜆𝑝∗ 𝑎𝑘𝑓∗ 𝑎𝑘=𝑥 𝑓∗ 𝑎𝑘𝑁𝑟 𝑎𝑘 𝑊𝑘 = 𝑟 𝑎1 𝑊1 × 𝑟 𝑎2 𝑊2 ⋯ × 𝑟 𝑎𝑁 𝑊𝑁 = 0
𝑘=10– 補正あり：𝑝nu 𝑎𝑘𝑟(𝑎𝑘 ) =𝑝de 𝑎𝑘 + 𝜆𝑝∗ 𝑎𝑘𝑓∗ 𝑎𝑘 + 1=𝑥 𝑓∗ 𝑎𝑘 + 2𝑁𝑟 𝑎𝑘 𝑊𝑘 = 𝑟 𝑎1 𝑊1 × 𝑟 𝑎2 𝑊2 ⋯ × 𝑟 𝑎𝑁 𝑊𝑁 ≠ 0
𝑘=1

Not 0！

33

補足２比較手法

34• 正則化＋重み付け（提案手法）
𝑁𝑟 𝑎𝑘 𝑊𝑘𝑟ours 𝑥 =𝑘=1

𝑊𝑘 ∈ 0, 1𝑟 𝑎𝑘 ：頻度を補正した正則化付きの推定量• 比較手法– ベースライン*– 重み付け*– 正則化*

補正しない頻度をそのまま使用– 正則化＋重み付け*• 正則化パラメータ 𝜆 は開発データを用いて決定補足２

Nが小さいとき、地名ではあまり差が出ない• ランクー再現率曲線（2-gram、訓練データ10000記事、地名）
Better35

補足２Nが大きくなると補正が効果的

36• ランクー再現率曲線（10-gram、訓練データ10000記事、地名）
Better

補正したゼロ頻度へ正則化が有効に作用

提案手法は頻度の補正によって、全ての N-gramに０より大きい推定値を与える

補足２

人名のケースではNに依らず有効• ランクー再現率曲線（訓練データ10000記事、人名）（N=2）（N=10）

37