パターン認識論 #10

パターン認識論 第10回 伊藤彰則 1

順序を見ない系列の認識 ◦長さの異なる系列の認識 ◦ 全体としてどういうパターンかが知りたい ◦ 系列内のパターンの順序は重要でない ◦例： ◦ 話者認識（誰がしゃべっているか） ◦ 言語認識（書かれた言語が何語か） ◦ トピック認識（文書の話題は何か） ◦ 環境認識（センサ時系列情報から環境推 定） 2

考え方 ◦可変長の系列 𝑋 = 𝑥1 , … , 𝑥𝑇 1. 可変長の系列から、固定長の特徴ベクトルを計 算⇒固定次元の識別手法を適用 2. 系列の各要素を評価して統合する 1. 確率の統合 log 𝑃 (𝑋|𝜔) = σ𝑘 log 𝑃 (𝐱𝑘 |𝜔) 2. 結果の統合（多数決など） 3

単純ベイズ(Naïve Bayes) 識別器 ◦確率を使って識別を行う ◦ データ𝑋 = 𝑥1 , … , 𝑥𝑇 がクラス𝜔1 , 𝜔2 のどちら かに属する ◦ データは独立と仮定する 𝑃(𝑋|𝜔𝑘 ) = ෑ 𝑃(𝑥𝑖 |𝜔𝑘 ) 𝑖 𝑃(𝑋|𝜔𝑘 )𝑃(𝜔𝑘 ) 𝑃(𝜔𝑘 |𝑋) = σ𝑘 𝑃(𝑋|𝜔𝑘 )𝑃(𝜔𝑘 ) arg max 𝑃(𝜔𝑘 |𝑋) = arg max 𝑃(𝜔𝑘 ) ෑ 𝑃(𝑥𝑖 |𝜔𝑘 ) 𝑘 𝑘 𝑖 4

単純ベイズ(Naïve Bayes) 識別器 ◦ 例：メールを通常メールとスパムメールに分 ける ◦ 通常メールの単語列𝑇𝑈 とスパムメールの単語列𝑇𝑆 を用意する ◦ それぞれからUnigramモデル𝑈𝑈 , 𝑈𝑆 を学習 ◦ 各単語の出現が独立だと仮定したモデル ◦ テストデータ𝑇に対して𝑃 𝑇 𝑈𝑈 , 𝑃(𝑇|𝑈𝑆 ) を計算 ◦ 確率の大きい方に識別 5

Unigram確率 ◦ 単語列において、単語の出現が互いに独立だと仮 定したモデル ◦ 𝑃(𝑊) = 𝑃 𝑤1 , … , 𝑤𝑛 = ς𝑖 𝑃(𝑤𝑖 ) ◦ 特定のデータ𝐶のunigramモデル ◦ 𝑃 𝑊 𝐶 = ς𝑖 𝑃 𝑤𝑖 𝐶 = ς𝑖 𝑁(𝑤𝑖 |𝐶) 𝑁(𝐶) ◦ 確率の平滑化 ◦ すべての単語について確率が0にならないようにする ◦ 例えば 𝑃 𝑊 = ς𝑖 𝑁 𝑤𝑖 +𝜖 𝑁+𝑉𝜖 ◦ 𝑁は総単語数、𝑉は語彙サイズ、𝜖 > 0は定数 6

単純ベイズ(Naïve Bayes) 識別器 ◦ 確率の平滑化をしないと、たまたまあるク ラスの文書にしか出現しない単語があれば、 その単語の出現で全てが決まる ◦ カテゴリーデータ（単語など）ではなく実 数データであってもよい ◦ 特徴量の各次元を独立に適当な確率分布で モデル化する ◦ 単一正規分布の場合は全次元を対角共分散の多次 元正規分布でモデル化することと等価 7

正規分布による単純ベイズ ◦クラス𝜔𝑘 の学習データ 𝑋1𝑘 , … , 𝑋𝑁𝑘 (𝑖,𝑘) (𝑖,𝑘) 𝑘 𝑋𝑖 = (𝑥1 , … , 𝑥𝑛 ) ◦分布 𝑛 𝑁(𝑋|𝛍𝑘 , Σ𝑘 ) = ෑ 𝑗=1 1 (𝑥𝑗 − 𝜇𝑗𝑘 )2 exp − 2 2𝜎𝑗𝑘 2 2𝜋𝜎𝑗𝑘 8

演習 天気を見て遊ぶかどうか決めるデータ ◦ http://www.inf.ed.ac.uk/teaching/courses/inf2b/learnSlides/inf2b12learnlec06.pdf Outlook sunny sunny overcast rainy rainy rainy overcast sunny sunny rainy sunny overcast overcast rainy Temperature hot hot hot mild cool cool cool mild cool mild mild mild hot mild Humidity high high high high normal normal normal high normal normal normal high normal high Windy FALSE TRUE FALSE FALSE FALSE TRUE TRUE FALSE FALSE FALSE TRUE TRUE FALSE TRUE Play NO NO YES YES YES NO YES NO YES YES YES YES YES NO 9

• http://www.inf.ed.ac.uk/teaching/courses/inf2b/learnSlides/inf2b12-

演習 ◦このデータからPlayを予測する単純ベ イズ識別モデルを作成して、学習デー タ自体を識別したとき、識別率は 100%になるか。ならない場合はどの データが誤るかを示せ。 ◦ コンピュータを使っても、手計算でもよい ◦ 各データに対してYesとNoの確率を計算す る 10

Bag of Words ◦文章の種類（トピック）の認識 ◦ 内容を理解せずに統計だけから認識したい ◦ 文章の長さはデータによってまちまち ◦単語の出現頻度から認識する ◦ 文章 𝑇 での単語 𝑤1 , … , 𝑤𝑉 の出現頻度𝑁(𝑤𝑖 |𝑇) 特徴ベクトル𝑋(𝑇) = (𝑁(𝑤1 |𝑇), … , 𝑁(𝑤𝑉 |𝑇))/𝑁(𝑇) 𝑁(𝑇) = ෍ 𝑁(𝑤𝑖 |𝑇) 𝑖 11

Bag of Words A A B B C D ABCDEF C X Xは固定長のベクトルなので、固定 長パターンと同じ手法で学習・識別 が可能 12

ベクトルに対するBoW ◦ベクトル系列 x1,...,xT ◦ベクトルをクラスタリングによって K 個のクラスタに分類 ベクトル量子化 → xt ⇒ ct∈{1,2,...,K} (VQ) x1 x2 xT 1 3 6 X 123456 13

確率の統合による方法 ◦考え方は単純ベイズ識別と同じ ◦ 系列 𝑊 = 𝑤1 , … , 𝑤𝑇 ◦ 確率モデル 𝑃(𝑤|𝜔) ◦ 全体の確率 𝑃(𝑊|𝜔) = ෑ 𝑃(𝑤𝑘 |𝜔) 𝑘 ◦確率モデルに何を使うか ◦ 連続値ベクトル：GMM ◦ シンボル：離散確率、トピックモデル 14

GMM xk 𝑃(𝐱𝑘 |𝜔) １つの時系列パターンに異なる部 分パターンが含まれる場合には、 GMMの異なる分布でそれを表現 できる GMMで計算した確率 log 𝑃 (𝑋|𝜔) = ෍ log 𝑃 (𝐱 𝑘 |𝜔) = ෍ log ෍ 𝜆𝑛 𝑁(𝐱 𝑘 ; 𝛍𝑖 , 𝚺𝑖 ) 𝑘 𝑘 𝑖 形式としては単純ベイズ識別と同じ 15

UBMを使う認識 ◦特に照合問題に使われる ◦ この入力が特定のパターンに属しているか どうかを当てる ◦ 話者照合など ◦問題点 ◦ 𝑃(𝐱𝑘 |𝜔) だけを使うと，「パターン自体の 出現しやすさ」が考慮されない 16

UBMを使う認識 𝑃(𝐱𝑘 |𝜔) ◦ 全パターンを表現するGMM 𝑃(𝐱 𝑘 |𝑈) ◦ Universal Background Model (UBM) ◦ 全パターンから学習する ◦ 特定のパターンを表現するGMM 𝑃(𝐱𝑘 |𝜔) ◦ UBMを初期値として学習する ◦ あるパターンのクラスωのスコア 𝑆(𝐱𝑘 |𝜔) = log 𝑃 (𝐱𝑘 |𝜔) − log 𝑃 (𝐱𝑘 |𝑈) ◦ これにしきい値を適用して，大きければ照合成功 17

結果の統合 一部分だけを見てパターンが識別できる場合 固定長の系列に対してパターン認識を行い、 得られた複数の結果を統合 A A B A A A A ・多数決 ・各パターンの頻度からBoWと同様の方法 18

トピックモデル 文書（など）のモデル化 ◦ 文書の中に複数のトピック（話題）が含まれ、 それぞれの話題から単語が生成されるという 考え方 ◦ 単語や文書をトピックへの重みのリストとし て表現できる ◦ 単語間、文書間の距離が計算できる→検索 ◦ 単語や文書のクラスタリングができる 19

Latent Semantic Analysis (LSA, 潜在意味解析) ◦文書のトピック認識などのために、文 書自体を比較的低次元のベクトルで表 現する手法 ◦ 文書𝐷𝑗 での単語𝑤𝑖 の出現頻度 𝑓𝑖𝑗 = 𝑁(𝑤𝑖 |𝐷𝑗 ) 1 ≤ 𝑖 ≤ 𝑁𝑉 , 1 ≤ 𝑗 ≤ 𝑁𝐷 ◦ 文書―頻度行列 𝑓11 𝑋= ⋮ 𝑓𝑁𝑉 1 … ⋱ ⋯ 𝑓1𝑁𝐷 ⋮ 𝑓𝑁𝑉 𝑁𝐷 20

文書―頻度行列 𝑓11 𝑋= ⋮ 𝑓𝑁𝑉 1 … ⋱ ⋯ 𝑓1𝑁𝐷 𝒕1𝑇 ⋮ = (𝒅1 , … , 𝒅𝑁𝐷 ) = ⋮ 𝒕𝑇𝑁𝑉 𝑓𝑁𝑉 𝑁𝐷 𝒕𝑖 : 単語𝑤𝑖 を表現する𝑁𝐷 次元ベクトル 𝒅𝑗 : 文書𝐷𝑗 を表現する𝑁𝑉 次元ベクトル 「どんな文書にどのくらい出現するか」で単語の意味を規定する 「どんな単語がどのくらい出現するか」で文書の意味を規定する ただし𝑋は非常にスパース（ほとんどの要素が0）→非効率 21

特異値分解(SVD) ◦行列𝑋 ∈ 𝑅 𝑉×𝑁𝐷 に対して 𝑋 = 𝑈Σ𝑉 𝑇 ◦𝑈は𝑁𝑉 × 𝑁𝑉 の直交行列 (𝑈𝑈𝑇 = 𝑈𝑇 𝑈 = 𝐼) ◦ 𝑈 = (𝒖1 , … , 𝒖𝑉 ) 𝒖𝑘 : 𝑤𝑘 の単語ベクトル ◦𝑉は𝑁𝐷 × 𝑁𝐷 の直交行列(𝑉𝑉 𝑇 = 𝑉 𝑇 𝑉 = 𝐼) ◦ 𝑉 = (𝒗1 , … , 𝒗𝑁𝐷 ) 𝒗𝑘 : 𝐷𝑘 の文書ベクトル ◦Σはおおむね対角な𝑁𝑉 × 𝑁𝐷 行列 ◦ 対角成分は「特異値」 22

特異値分解(SVD) 𝑁𝐷 文書数 𝑁𝑉 語彙サイズ X X 単語ベクトル U ＝ ＝ 文書ベクトル U Σ Σ VT VT 23

SVDによる次元圧縮 ◦𝑋は𝑁𝑉 × 𝑁𝐷 行列 ◦SVD: 𝑋 = 𝑈Σ𝑉 𝑇 ◦ 𝑈は𝑁𝑉 × 𝑁𝑉 行列、𝑉は𝑁𝐷 × 𝑁𝐷 行列 𝑇 ◦SVDによる圧縮： 𝑋 ≈ 𝑈𝐾 𝛴𝐾 𝑉𝐾 ◦ 𝐾 ≤ min 𝑁𝑉 , 𝑁𝐷 ◦ Σ𝐾 は𝐾 × 𝐾の対角行列で、対角成分はΣの特 異値のうち大きい𝐾個 ◦ 𝑈は𝑁𝑉 × 𝐾行列、𝑉は𝐾 × 𝑁𝐷 行列 24

LSA 単語ベクトル・文書ベクトルともに𝐾次元に次元圧縮 • 単語や文書がベクトル化できるので、距離の計測やクラスタ リングが可能になる 𝑁𝐷 文書数 𝐾 𝐾 𝑁𝑉 語彙サイズ X ≈ U K ΣK VKT 𝐾 25

単語集合から文書ベクトル を求める 𝑁𝐷 文書数 𝐾 𝐾 𝑁𝑉 語彙サイズ X ≈ U K 新しいBoW ΣK-1 ΣK VKT 𝐾 比較できる UKT ≈ 26

Probabilistic LSA (PLSA) LSAの確率モデル版 ◦ 文書𝐷での単語出現確率 𝑃(𝑤|𝐷) = ෍ 𝑃 𝑤 𝑧𝑘 𝑃(𝑧𝑘 |𝐷) 𝑘 ◦ 𝑧𝑘 は「話題」 ◦ 話題の個数は任意に決める ◦ 話題は観測できないので、EMアルゴリズム で推定 27

PLSAの生成モデル ◦ 文書𝐷1 , … , 𝐷𝑀 ◦ それぞれの文書で話題の確率分布𝑃(𝑧𝑘 |𝐷𝑚 )が 決まっている(1 ≤ 𝑘 ≤ 𝐾) ◦ 話題によって単語出現確率分布𝑃(𝑤𝑖 |𝑧𝑘 )が決 まっている(1 ≤ 𝑖 ≤ 𝑉) ◦ 文書が決まると確率分布 𝑃 𝑤 𝐷 = ෍ 𝑃 𝑤 𝑧𝑘 𝑃 𝑧𝑘 𝐷 𝑘 によって単語を生成 28

PLSAの推定 𝑟−1 𝑃 𝑧 𝐷 (𝑟−1) 𝑃 𝑤 𝑧 𝑃 𝑧 𝑤, 𝐷 (𝑟) ← σ𝑧 ′∈𝑍 𝑃 𝑤 𝑧 ′ 𝑟−1 𝑃 𝑧 ′ 𝐷 (𝑟−1) (𝑟) σ 𝑁 𝑤 𝐷 𝑃 𝑧 𝑤, 𝐷 𝐷 𝑃 𝑤 𝑧 (𝑟) ← σ𝑤 ′ σ𝐷 𝑁 𝑤 𝐷 𝑃 𝑧 𝑤, 𝐷 (𝑟) (𝑟) σ 𝑁 𝑤′ 𝐷 𝑃 𝑧 𝑤′, 𝐷 ′ 𝑤 𝑃 𝑧 𝐷 (𝑟) ← σ𝑧 ′ σ𝑤 ′ 𝑁 𝑤′ 𝐷 𝑃 𝑧 𝑤′, 𝐷 (𝑟) 29

Latent Dirichlet Allocation (LDA) PLSAに事前分布を入れたもの ◦確率分布のパラメータ（この場合は話 題や単語の生成確率）自体がある確率 分布に従って生成されていると仮定 ◦パラメータの分布（事前分布）と、学 習データが与えられたときの分布（事 後分布）を推定 ◦推定にはモンテカルロシミュレーショ ンなどを利用 30