hirohirohirohirosのブログ

地方国立大学に通う情報系学部4年

はじめてのパターン認識 第4章 確率モデル 後半 まとめ

2次識別関数と線形識別関数

 第4章前半で誤り率最小基準のベイズの識別境界は
\begin{align}
f_{ij}(\boldsymbol{x}) = \boldsymbol{x}^T\boldsymbol{S}\boldsymbol{x} + 2\boldsymbol{c}^T\boldsymbol{x} + F = 0
\end{align}

となることを述べた.これは2次曲面となることから,これを2次識別関数という.

 2クラスの共分散行列が等しい,つまり

\begin{align}
\sum_i = \sum_j = \sum
\end{align}

が成り立っている場合, \boldsymbol{S}=0となるため,識別境界は

\begin{align}
f_{ij}(\boldsymbol{x}) =  2\boldsymbol{c}^T\boldsymbol{x} + F = 0
\end{align}

と線形識別関数となる.

 さらに, \sum = σ\boldsymbol{I}のように,二つのクラスの共分散行列が等しく,同じ等方性分散を持っており,かつクラスの事前確率が等しい P(C_i) = P(C_j)が成り立つという制約を追加すると,

\begin{align}
f_{ij}(\boldsymbol{x}) &=  2\boldsymbol{c}^T\boldsymbol{x} + F \\
&= 2(\boldsymbol{\mu}_j^T\sum_j^{-1} - \boldsymbol{\mu}_i^T\sum_i^{-1})\boldsymbol{x} + \boldsymbol{\mu}_i^T\sum_i^{-1}\boldsymbol{\mu}_i - \boldsymbol{\mu}_j^T\sum_j^{-1}\boldsymbol{\mu}_j \\
&+ \log |\frac{\sum_i}{\sum_j}| - 2\log \frac{P(C_i)}{P(C_j)} \\
&= 2(\boldsymbol{\mu}_j^T\sum^{-1} - \boldsymbol{\mu}_i^T\sum^{-1})\boldsymbol{x} + \boldsymbol{\mu}_i^T\sum^{-1}\boldsymbol{\mu}_i - \boldsymbol{\mu}_j^T\sum^{-1}\boldsymbol{\mu}_j \\
&+ \log |\frac{\sum}{\sum}| - 2\log \frac{P(C_i)}{P(C_j)} \\
&= 2σ^{-1}(\boldsymbol{\mu}_j^T - \boldsymbol{\mu}_i^T)\boldsymbol{x} + σ^{-1}(\boldsymbol{\mu}_i^T\boldsymbol{\mu}_i - \boldsymbol{\mu}_j^T\boldsymbol{\mu}_j) = 0
\end{align}

となる.さらに,最後の式を変形すると,

\begin{align}
2σ^{-1}(\boldsymbol{\mu}_j^T - \boldsymbol{\mu}_i^T)\boldsymbol{x} + σ^{-1}(\boldsymbol{\mu}_i^T\boldsymbol{\mu}_i - \boldsymbol{\mu}_j^T\boldsymbol{\mu}_j)  &= 0 \\
2(\boldsymbol{\mu}_j^T - \boldsymbol{\mu}_i^T)\boldsymbol{x} + \boldsymbol{\mu}_i^T\boldsymbol{\mu}_i - \boldsymbol{\mu}_j^T\boldsymbol{\mu}_j &= 0 \\
 (\boldsymbol{x} - \boldsymbol{\mu}_i)^T(\boldsymbol{x} - \boldsymbol{\mu}_i) - (\boldsymbol{x} - \boldsymbol{\mu}_j)^T(\boldsymbol{x} - \boldsymbol{\mu}_j) &= 0 \\
 (\boldsymbol{x} - \boldsymbol{\mu}_i)^T(\boldsymbol{x} - \boldsymbol{\mu}_i) &=  (\boldsymbol{x} - \boldsymbol{\mu}_j)^T(\boldsymbol{x} - \boldsymbol{\mu}_j)
\end{align}

が成り立つ.これは,入力ベクトルと二つの平均ベクトルとのユークリッド距離が小さな方のクラスに識別される.

 本書実行例4.4の例は上記の内容の具体例となっており,理解に大変役立つ.

確率モデルパラメータの最尤推定

 真の分布パラメータθを持つ確率モデルf(x|θ)で表す.N個のデータの同時確率分布は,

\begin{align}
f(\boldsymbol{x}_1, ..., \boldsymbol{x}_N|\boldsymbol{θ}) = \Pi f(\boldsymbol{x}_i|\boldsymbol{θ})
\end{align}

と書ける.ここで,

\begin{align}
L(\boldsymbol{θ}) = f(\boldsymbol{x}_1, ..., \boldsymbol{x}_N|\boldsymbol{θ})
\end{align}

と表す.この確率モデルのパラメータを求める方法に,尤度を最大にするパラメータを見つけることがある.起こった事象はもっとも起こる確率の高い事象がによって起こされたと言えるためである.

 これは最尤推定法と呼ばれる.最尤推定法では尤度関数L(θ)をパラメータで微分し,0とおいて解くことで求められる.確率分布関数は対数を取った方が微分しやすいため,尤度関数の対数を取った対数尤度関数が良く用いられる.

 1変数の正規分布最尤推定法で平均値を求める.

\begin{align}
L(\mu, σ^2) &= f(x_1, ..., x_N|\mu, σ^2) = \Pi \frac{1}{\sqrt{2\pi}σ}\exp(\frac{(x_i - \mu)^2}{2σ^2}) \\
&= (2\piσ^2)^{-\frac{N}{2}}\exp(-\frac{1}{2σ^2}\sum (x_i - \mu)^2) \\
\log L(\mu, σ^2) &= \frac{N}{2}\log (2\pi) -\frac{N}{2}\log σ^2 -\frac{1}{2σ^2}\sum (x_i - \mu)^2
\end{align}

平均値の最尤推定法を求めるためにμで微分し0とおくと,

\begin{align}
\frac{\partial \log L(\mu, σ^2)}{\partial \mu} = \frac{1}{σ^2}\sum(x_i - \mu) &= 0 \\
\widehat \mu &= \frac{1}{N}\sum x_i
\end{align}

となる.これは算術平均の式である.正規分布の真の平均値は,最尤推定法で求めると各データの平均値になる事が分かる.

Atcoder 灰diff埋め ARC021~ARC040 振り返り

ARC035 A - 高橋くんと回文【AC】

 "*"という文字は任意の文字に置き換えられるとしたとき,Sは回文であるか求める問題です.
 SとSを反転した文字列を左から順に一文字ずつペアとして見ていきます.全ての文字のペアについて,同じ文字であるか"*"が含まれているとき,これは回文です.逆に文字が異なるかつどちらも"*"でない文字ペアが一つでもあったときこれは回文ではありません.
 SとSを反転した文字列について一文字ずつペアを作る過程でzip関数を使っています.これをfor文で使う事で複数のイテラブルオブジェクトを同時に取得することが出来ます.こうすることで,SとSを反転した文字列を一度に取得することが出来て便利です.
 これと同じ事は例えばfor i in range(len(S))としてs = S[i] r = S[::-i-1]としてもできます.

S = input()
for s, r in zip(S, S[::-1]):
    if s != r and "*" not in [s, r]:
        print("NO")
        break
else:
    print("YES")

Atcoder ABC251 振り返り

AからCまでを8分50秒で解くことで1806位パフォ1103になりました.レートも緑まであと5なので頑張ります.

A - Six Characters【AC】

 与えられる文字列は1から3であり,全て6の約数です.繰り返す回数は6/len(s)で求められます.

s = input()
print(s*(6//len(s)))
B - At Most 3 (Judge ver.)【AC】

 全探索して良い整数を探します.3個以下の重りを選ぶので,1個の場合,2個の場合,3個の場合で場合分けしそれぞれの場合で全探索します.良い整数はダブる可能性がありますが,set型を使う事でダブりを考慮せずカウントすることが出来ます.

N, W = map(int, input().split())
A = [int(i) for i in input().split()]
ans = set()

for i in range(N):
    if A[i] <= W:
        ans.add(A[i])

for i in range(N-1):
    for j in range(i+1, N):
        if A[i] + A[j] <= W:
            ans.add(A[i] + A[j])

for i in range(N-2):
    for j in range(i+1, N-1):
        for z in range(j+1, N):
            if A[i] + A[j] + A[z] <= W:
                ans.add(A[i] + A[j] + A[z])

print(len(ans))
C - Poem Online Judge【AC】

 最高得点を記録するTという変数を用意します.入力される得点tに対し,t>Tならそのポエムは最優秀賞候補になります.しかし,同じポエムが以前に存在していたらそれはオリジナルではないため,最優秀賞にはなり得ません.そのチェックをpoemというset型で行います.
 s in poemで同じポエムが以前に存在しているか確認してます.set型のinは計算量O(1)なので高速です.

N = int(input())
poem = set()
T = 0
ans = 1

for i in range(N):
    s, t = input().split()
    t = int(t)
    if s in poem:
        continue
    if t > T:
        ans = i+1
        T = t

    poem.add(s)
print(ans)

はじめてのパターン認識 第4章 確率モデル 前半 まとめ

確率モデル

 学習データの分布を予測する時に,確率モデルを仮定して,学習データからその統計量を推定するパラメトリックモデルと,特定の確率モデルを仮定せずに学習データその物を用いてデータの分布を表現するノンパラメトリックモデルがある.

 ノンパラメトリックモデルには,ヒストグラム法,kNN法,パルツェン密度推定法がある.パラメトリックモデルの代表例である正規分布について述べる.

正規分布

 1次元の正規分布関数は

\begin{align}
N(x|\mu, σ^2) = \frac{1}{\sqrt{2\pi}σ}\exp(-\frac{(x-\mu)^2}{2σ^2})
\end{align}

で定義される.

 d個の要素を持つベクトルである,d次元の多次元正規分布関数は

\begin{align}
N(\boldsymbol{x}|\boldsymbol{\mu}, \sum) = \frac{1}{(2\pi)^{\frac{d}{2}}|\sum|^{\frac{1}{2}}}\exp(-\frac{1}{2}(\boldsymbol{x} - \boldsymbol{\mu})^T\sum^{-1}(\boldsymbol{x} - \boldsymbol{\mu}))
\end{align}

で定義される.多次元正規分布も1次元の場合と同じように平均ベクトル \boldsymbol{\mu}と共分散行列 \sumの二つのパラメータで分布の形が決まる.

 正規分布関数の指数部は任意の点xと平均ベクトルμとの距離

\begin{align}
d(\boldsymbol{x}, \boldsymbol{\mu}) = \sqrt{(\boldsymbol{x} - \boldsymbol{\mu})^T\sum^{-1}(\boldsymbol{x} - \boldsymbol{\mu})}
\end{align}

を表しており,これをマハラノビス距離という.ユークリッド距離を共分散行列で割り算する形になっているので,分布の広がり方を考慮に入れた距離となる.

正規分布から導かれる識別関数

正規分布の識別規則

 i番目のクラスの条件付き確率が正規分布

\begin{align}
p(\boldsymbol{x}|C_i) = \frac{1}{(2\pi)^{\frac{d}{2}}|\sum_i|^{\frac{1}{2}}}\exp(-\frac{1}{2}(\boldsymbol{x} - \boldsymbol{\mu})^T\sum_i^{-1}(\boldsymbol{x} - \boldsymbol{\mu}))
\end{align}

となっていると仮定する.このときのベイズの誤り率最小識別規則を満たす識別関数を求める.事後確率は

\begin{align}
P(C_i|\boldsymbol{x}) &= \frac{p(\boldsymbol{x}|C_i)P(C_i)}{p(\boldsymbol{x})} \\
&\propto \frac{p(C_i)}{(2\pi)^{\frac{d}{2}}|\sum_i|^{\frac{1}{2}}}\exp(-\frac{1}{2}(\boldsymbol{x} - \boldsymbol{\mu})^T\sum_i^{-1}(\boldsymbol{x} - \boldsymbol{\mu}))
\end{align}

と変形出来る.2行目は1行目に比例する形である. p(\boldsymbol{x})が1行目の分母にあるが,全てのクラスiに共通して現れるので,識別関数を求める場合省略可能である.

 この式の対数を取ると

\begin{align}
\log P(C_i) - \frac{d}{2}\log(2\pi) - \frac{1}{2}\log|\sum_i| - \frac{1}{2}(\boldsymbol{x} - \boldsymbol{\mu}_i)^T\sum^{-1}_i(\boldsymbol{x} - \boldsymbol{\mu}_i)
\end{align}

となる.各クラスに共通して現れる項は先ほどと同様に省略できる.この式はクラスの事後確率から導いて求めた式であるため,誤り率を表すためには符号を反転させれば良い.このように変形すると,事後確率から導かれる評価値は

\begin{align}
g_i(\boldsymbol{x}) = (\boldsymbol{x} - \boldsymbol{\mu}_i)^T\sum_i^{-1}(\boldsymbol{x} - \boldsymbol{\mu}_i) + \log|\sum_i| - 2\log P(C_i)
\end{align}

となる.識別クラスとして,この評価値の最も小さなクラスを選択すれば,誤り率最小基準のベイズの識別規則が得られる.

\begin{align}
識別クラス = \arg min_i g_i(\boldsymbol{x})
\end{align}

識別境界

 クラス間の識別境界は2クラスの事後確率が等しくなる点の軌跡となる.つまりクラスi, jの評価値の差が0になる点の軌跡であるため,

\begin{align}
f_{ij}(\boldsymbol{x}) &= g_i(\boldsymbol{x}) - g_j(\boldsymbol{x}) \\
&=  (\boldsymbol{x} - \boldsymbol{\mu}_i)^T\sum_i^{-1}(\boldsymbol{x} - \boldsymbol{\mu}_i) + \log|\sum_i| - 2\log P(C_i) \\
&-  (\boldsymbol{x} - \boldsymbol{\mu}_j)^T\sum_j^{-1}(\boldsymbol{x} - \boldsymbol{\mu}_j) - \log|\sum_j| - 2\log P(C_j) \\
&= \boldsymbol{x}^T(\sum_i^{-1} - \sum_j^{-1})\boldsymbol{x} + 2(\boldsymbol{\mu}_j^T\sum_j^{-1} - \boldsymbol{\mu}_i^T\sum_i^{-1})\boldsymbol{x} \\
&+ \boldsymbol{\mu}_i^T\sum_i^{-1}\boldsymbol{\mu}_i - \boldsymbol{\mu}_j^T\sum_j^{-1}\boldsymbol{\mu}_j + \log |\frac{\sum_i}{\sum_j}| - 2\log \frac{P(C_i)}{P(C_j)} = 0
\end{align}

となる. \sum_i^{-1} - \sum_j^{-1}は行列であるため

\begin{align}
\boldsymbol{S} = \sum_i^{-1} - \sum_j^{-1}
\end{align}

 \boldsymbol{\mu}_j^T\sum_j^{-1} - \boldsymbol{\mu}_i^T\sum_i^{-1}も行列であるため
\begin{align}
 \boldsymbol{c}^T = \boldsymbol{\mu}_j^T\sum_j^{-1} - \boldsymbol{\mu}_i^T\sum_i^{-1}
\end{align}
 \boldsymbol{\mu}_i^T\sum_i^{-1}\boldsymbol{\mu}_i - \boldsymbol{\mu}_j^T\sum_j^{-1}\boldsymbol{\mu}_j + \log |\frac{\sum_i}{\sum_j}| - 2\log \frac{P(C_i)}{P(C_j)}スカラーであるため

\begin{align}
\boldsymbol{F} = \boldsymbol{\mu}_i^T\sum_i^{-1}\boldsymbol{\mu}_i - \boldsymbol{\mu}_j^T\sum_j^{-1}\boldsymbol{\mu}_j + \log |\frac{\sum_i}{\sum_j}| - 2\log \frac{P(C_i)}{P(C_j)}
\end{align}

と代入すると,

\begin{align}
f_{ij}(\boldsymbol{x}) = \boldsymbol{x}^T\boldsymbol{S}\boldsymbol{x} + 2\boldsymbol{c}^T\boldsymbol{x} + F = 0
\end{align}

となる.これは二次曲面となる.

統計学入門 第4章 練習問題 後半 解答まとめ

4.5

 向かい合って座るパターンは2通りであるが,隣り合って座るパターンは4通りある.よって,前者が15組で後者が30組だから隣り合って座る方を好むという推論には問題がある.

4.6

 目の和が9になる場合に(3,3,3)という3つ同じ数字の並びがあるが,目の和が10になる場合にはそのような並びはなく,(3,3,4)のような2つ同じ数字を含む並びしか存在しない.このような数字の並びは(3,3,4), (3,4,3), (4,3,3)と3パターンの並びがある.それに対して(3,3,3)はこの1パターンしか存在せず,3倍出やすさが異なるため,起こる確率は等しいと言えない.

4.7

i)

 ベイズの定理から,

\begin{align}
P(C|A) = \frac{P(C)P(A|C)}{P(C)P(A|C)+P(C^c)P(A|C^c)}
\end{align}

が成り立つ.これに, P(A|C)=0.95, P(C)=0.005, P(C^c)=0.995, P(A|C^c)=0.05を代入すれば,
\begin{align}
P(C|A) &= \frac{0.005*0.95}{0.005*0.95 + 0.995*0.05} \\
&= 0.0872\\
\end{align}

となる.正答率95%の検査であっても,ガンの発症確率が0.5%しかなければ,検査で陽性と審査されても本当に陽性である確率は8.7%しかないことが分かる.

ii)

\begin{align}
P(C|A) &= \frac{P(C)P(A|C)}{P(C)P(A|C)+P(C^c)P(A|C^c)} \\
&= \frac{0.005*R}{0.005*R+0.995*(1-R)} \geq 0.9 \\
\frac{5R}{995 - 990R} &\geq 0.9 \\
5R &\geq 895.5 - 891R \\
R &\geq \frac{895.5}{896} \\
R &\geq 0.99944
\end{align}

陽性と結果が出たときに,本当にガンが発症している確率を90%以上にしたかったら,正答率を99.944%以上にしないといけないことになってしまう事が分かる.

統計学入門 第4章 練習問題 前半 解答まとめ

4.1 ド・メレの問題

i)

 サイコロを4回投げ,6が少なくとも1回出る確率は(1-6が1回も出ない確率)である.6が1回も出ない確率は (\frac{5}{6})^4 = 0.482である.よって少なくとも1回出るのに賭けるべきである.

ii)

 (6, 6)が1回も出ない確率は (\frac{35}{36})^24 = 0.509である..よって1回も出ない方に賭けるべきである.

4.2

 2個のサイコロを投げて,その和が12になる確率は \frac{1}{36}である.n回投げて少なくとも1回は12が出る確率は 1-(\frac{35}{36})^nである.これが0.9を超えるのは,
\begin{align}
1-(\frac{35}{36})^n &> 0.9 \\
0.1 &> (\frac{35}{36})^n \\
n &> \log_{\frac{35}{36}}0.1 \\
n &> 81.73
\end{align}
よって82回以上投げれば90%の確率で目の和が12になる.

4.3

 30C15となる.pythonには組み合わせの計算にscipyというモジュールのcomb関数がある.

答えは155117520通りである.

4.4

 同じ誕生日の人が存在しない確率は \frac{365}{365}\frac{364}{365}...\frac{365-r+1}{365}である.これを変形すると (1 - \frac{0}{365})(1 - \frac{1}{365})(1-\frac{2}{365})...(1 - \frac{r-1}{365})となる.

 これをプログラムに書き起こし,rの値を変えたときの結果を載せる.

この結果から,60人の集団の中で同じ誕生日のペアが一つ以上存在する確率は99%を超えることが分かる.

機械学習を解釈する技術 5章 まとめ

ICE

 4章でやったPDは特徴量と予測値の平均的な関係を見る指標であった.それに対し,ICEは平均を取らず,一つ一つのデータに対して特徴量と予測値の関係を見る指標である.平均を取らず,一つ一つのデータに対して見ていくので値がブレやすく,関係を安定的に確認することが難しいという問題点がある.しかし,PDでは捉えられない特徴量と予測値の関係があるため,ICEは使われる.まず,PDでは捉えられない関係とは何かを考える.

PDで捉えられない関係

 例として,飲食店の顧客満足度を予測するモデルについて考える.料理の量という特徴量があった時,顧客が学生のような若い年齢だった場合,量が増えるほど顧客満足度が上がると考えられる.しかし,顧客が高年齢だった場合,量が増えても顧客満足度は上がらないと考えられる.このようなケースでは,料理の量と顧客満足度の平均的な関係を見てしまうと,年齢という特徴量の違いによる顧客満足度の変化が打ち消されてしまい,正しい関係を見ることが出来ない.

 このように,見たい特徴量と予測値の関係が他の属性によって異なる場合,PDで平均的な関係を捉えることは不可能です.よって,データごとや属性ごとに関係を見る必要がある.

ICEの数式表現

 PDの数式表現は

\begin{align}
\widehat{PD}_j(x_j) = \frac{1}{N}\sum \widehat f(x_j, x_{i, :j})
\end{align}

となる.ここで, \widehat f()は学習済みモデル, x_{i, :j} = (x_{i, 1}, ..., x_{i, j-1}, _{i, j+1}, ..., x_{i, J})はデータiに対するj番目の特徴量を除いたベクトルを表す.

 PDは \frac{1}{N}を掛けることで平均を取っているが,ICEは平均を取らないため,数式表現は

\begin{align}
\widehat{ICE}_{i, j}(x_j) = \widehat f(x_j, x_{i, :j})
\end{align}

となる.

ICEの利点

 ICEはPDの個々で見たバージョンになるので,PDの利点はICEの利点になる.具体的には,どのような機械学習モデルにもICEが適用できたり,特徴量と目的変数の非線形名関係を確認することが出来る.さらに,PDとは異なりICEは特徴量の交互作用を捉えることが出来る.

 しかし,これまでの指標と同じようにICEは因果関係を表すものではないことに注意する.さらに,PDでは平均を取っていたのに対しICEでは平均を取らないため値が安定しないことに注意する.また,データの実際の特徴量の値から大きく離れた部分では,安定しづらいため,実際の値の近くで解釈するように気をつける必要がある.

実データでの分析

 4章と同じデータで分析する.4章で紹介したように,sklearnの引数kindをindvidualにすることでICEが計算される.

scikit-learn.org

 

また,bothとするとPDとICEが両方表示される.コードも4章で紹介したコードと同じものを使い,引数のみを書き換える.

この関数を動かし,グラフを表示してみる.

 薄い線が各データのICEであり,太い線がPDである.4章と同じようにFoodCourtが増えるほど生き残る確率が低くなることが分かる.薄い線のICEで多くの線がそのような傾向を示しており,その平均であるPDもそのような傾向が見られる.

 逆に,このような傾向が見られない,FoodCourtが増えるほどPDが高くなるデータも見られることが分かる.このようなデータに対して他の特徴量を見ることによって新しい事が分かるかもしれない.ICEの分析によって新しい観点からの分析も進めることが可能である.