漫談Clustering(3):Gaussian Mixture Model
21191 ワード
転載:http://blog.pluskid.org/?p=39
漫談Clustering(3):Gaussian Mixture Model
by pluskid, on 2009-02-02, in Machine Learning
192 comments
本文は「漫談Clusteringシリーズ」の4編目で、本シリーズの他の文章を参照してください.
前回はk-meansでクラスタリングする方法についてお話ししましたが、今回はもう一つのポピュラーなアルゴリズム:Gaussian Mixture Model(GMM)についてお話しします.実際、GMMはk-meansに似ていますが、GMMはいくつかの確率密度関数を学習しています(したがって、GMMはclusteringのほかにdensity estimationにもよく使われています).簡単に言えば、k-meansの結果は、各データ点がassignからそのうちの1つのclusterに、GMMはこれらのデータ点がassignから各clusterに、ソフトウェアassignmentとも呼ばれます.
1つの確率を得るには多くのメリットがあります.その情報量は簡単な結果よりも多いからです.例えば、私はこの確率をscoreに変換して、アルゴリズムが自分で得たこの結果の把握を表すことができます.私は同じタスクに対して、複数の方法で結果を得ることができて、最後に最大の結果を「把握」することができます.もう1つの一般的な方法は、疾患診断のような場所では、機械が見分けやすい状況(罹患しているか、罹患していない確率が高い)を自動的に区別することができるが、見分けにくい状況、例えば49%の確率で罹患し、51%の確率で正常であり、50%の閾値を簡単に使用して患者を「正常」と診断すれば、リスクは非常に大きいので、機械が自分の結果を把握していない場合は、「コメントを拒否する」として、経験のある医師にこの任務を残して解決します.
くだらないことをたくさん言いましたが、GMMに戻る前に、もう少し話しましょう.機械であれ人間であれ、学習の過程は「帰納」の過程と見なすことができ、帰納する際にはいくつかの仮定の前提条件が必要であることを知っています.例えば、水の中で泳いでいるやつが魚だと知られた後、「同じ場所で生活しているのは同じものだ」という仮定を使うと、「水の中を泳いでいるのは魚ばかりだ」という結論をまとめた.もちろんこの過程は完全に「本能」であり、よく考えなければ、自分がどのように「魚を知っている」のか分からない.もう一つの注目すべき点は、このような仮定が必ずしも完全に正しいわけではなく、いつもこのような欠陥があると言えるので、エビ、亀、ダイバーを魚と見なす可能性があります.前提仮定を修正することでこの問題を解決できると思います.例えば、「同じ場所に住んでいて、同じ服を着ているのは同じものだ」という仮定に基づいて、水の中に鱗が生えているのは魚だと結論しました.しかし、これはまだ問題があります.鱗のない魚が今またあなたから排除されているからです.
この問題では、機械学習は人間と同じ問題に直面しており、機械学習では、一つの学習アルゴリズムにも前提仮定があり、ここでは「帰納偏執(bias)」と呼ばれている(biasという英語語は機械学習と統計に他にも多くの意味がある).例えば線形回帰は、与えられたデータ点にできるだけよくフィットする関数を探すことを目的とし、その帰納偏執は「要求を満たす関数は線形関数でなければならない」である.帰納偏執のない学習アルゴリズムはある意味では役に立たない.まるで帰納能力のない人のように、初めて魚を見たとき、それは魚だと言った人がいた.次は別の魚を見た.彼はそれも魚だとは知らなかった.2匹の魚にはいつもいくつかの場所が違うからだ.あるいは同じ魚でも、川の中の違うところで見て、あるいはただ見た時間が違うだけで、彼にも違うと思われます.彼は帰納できないので、主な矛盾を抽出することができず、副次的な要素を無視することができず、すべての条件が完全に同じであることを要求するしかありません.しかし、哲学者は私たちに言ったことがあります.世界には何も同じものはありません.だからこの人は比類のない強い記憶力を持っていても、何の知識も学べない.
この問題は機械学習において「オーバーフィット(Overfitting)」と呼ばれ、例えば前の回帰の問題で、「線形関数」という帰納偏執を取り除くと、N個の点に対して、私たちはいつもN-1次多項式関数を構築して、あるN個の点を完璧に通過させることができ、あるいは私がN-1回より大きい多項式関数を使うと、私は無限に多くの条件を満たす関数を構築することができます.特定の分野の問題が与えられたデータの個数に常に上限があると仮定すれば、私は十分なNを取って、1つの(あるいは無限の複数の)「スーパー関数」を得ることができて、この分野のすべての問題をfitすることができます.しかし、この「スーパー関数」は役に立ちますか?学習の目的(通常)が既存のものを解釈するのではなく、そこから知識をまとめ、新しいものに応用できることに気づくと、結果は明らかになる.
帰納偏執がないか,帰納偏執が広すぎるとOverfittingを招くが,もう一つの極端である過大な帰納偏執を制限することも問題である:データ自体が線形でなければ,線形関数での回帰を強行することは通常良い結果を得ることができない.難点はまさにこの間に平衡点を探すことだ.しかし、ここでは機械に比べて大きな利点があります.人間は通常、独立したシステムやモデルで問題を処理することはなく、毎日各ソースから大量の情報を取得し、様々な手段で統合処理を行い、まとめられたすべての知識を統一的に記憶することができます.有機的に組み合わせて特定の問題を解決することができます.ここの「有機」という言葉はとても面白くて、理論をする人はいつもいろいろなモデルを提出することができて、しかもこれらのモデルはすべて厳格な理論の基礎があって所望の目的を達成することができることを保証して、しかしほとんどのモデルはすべてそんなにいくつかの“パラメータ”(例えばK-meansの中のk)があって、通常パラメータがどの値を取るのがもっと良いことを説明する理論がなくて、モデルの実際の効果は通常パラメータが最適値を取ったかどうかと大きく関係しており、ここで「有機」はすべてのモデルのパラメータが自動的に最適値を取ったと見なすことができると思います.また,進展は大きくないが,コンピュータ分野においても統一的な知識システムを構築することが期待されている(例えば,語意網はこのような試みである).
くだらない話はやっと終わって、GMMに戻りました.私たちの前の議論に従って、流行のアルゴリズムとして、GMMはきっとそれ自身のかなり体面の帰納が偏っているに違いない.実はその仮定は非常に簡単で、その名の通り、Gaussian Mixture Modelは、データがMixture Gaussian Distributionに従うと仮定し、言い換えれば、データは数個のGaussian Distributionから生成されたものと見なすことができる.実際,K‐meansとK‐medoidsの2つの論文で用いた例は,3つのGaussian分布からランダムに選択されたものである.実際,中心極限の定理からGaussian分布(ノーマル分布とも呼ばれる)という仮定は妥当であることが分かるが,それ以外にGaussian分布は計算上もいくつかの良い性質を持っているため,異なる布で勝手にXX Mixture Modelを構築することができるが,GMMが最も流行している.また,Mixture Model自体も実際には任意に複雑になり,Modelの個数を増やすことで任意に連続確率密分布に近づけることができる.
各GMMは
個のGaussian分布からなり、各Gaussianは「Component」と呼ばれ、これらのComponentは線形に加算されてGMMの確率密度関数を構成する.
漫談Clustering(3):Gaussian Mixture Model
by pluskid, on 2009-02-02, in Machine Learning 192 comments 
本文は「漫談Clusteringシリーズ」の4編目で、本シリーズの他の文章を参照してください.前回はk-meansでクラスタリングする方法についてお話ししましたが、今回はもう一つのポピュラーなアルゴリズム:Gaussian Mixture Model(GMM)についてお話しします.実際、GMMはk-meansに似ていますが、GMMはいくつかの確率密度関数を学習しています(したがって、GMMはclusteringのほかにdensity estimationにもよく使われています).簡単に言えば、k-meansの結果は、各データ点がassignからそのうちの1つのclusterに、GMMはこれらのデータ点がassignから各clusterに、ソフトウェアassignmentとも呼ばれます.
1つの確率を得るには多くのメリットがあります.その情報量は簡単な結果よりも多いからです.例えば、私はこの確率をscoreに変換して、アルゴリズムが自分で得たこの結果の把握を表すことができます.私は同じタスクに対して、複数の方法で結果を得ることができて、最後に最大の結果を「把握」することができます.もう1つの一般的な方法は、疾患診断のような場所では、機械が見分けやすい状況(罹患しているか、罹患していない確率が高い)を自動的に区別することができるが、見分けにくい状況、例えば49%の確率で罹患し、51%の確率で正常であり、50%の閾値を簡単に使用して患者を「正常」と診断すれば、リスクは非常に大きいので、機械が自分の結果を把握していない場合は、「コメントを拒否する」として、経験のある医師にこの任務を残して解決します.
くだらないことをたくさん言いましたが、GMMに戻る前に、もう少し話しましょう.機械であれ人間であれ、学習の過程は「帰納」の過程と見なすことができ、帰納する際にはいくつかの仮定の前提条件が必要であることを知っています.例えば、水の中で泳いでいるやつが魚だと知られた後、「同じ場所で生活しているのは同じものだ」という仮定を使うと、「水の中を泳いでいるのは魚ばかりだ」という結論をまとめた.もちろんこの過程は完全に「本能」であり、よく考えなければ、自分がどのように「魚を知っている」のか分からない.もう一つの注目すべき点は、このような仮定が必ずしも完全に正しいわけではなく、いつもこのような欠陥があると言えるので、エビ、亀、ダイバーを魚と見なす可能性があります.前提仮定を修正することでこの問題を解決できると思います.例えば、「同じ場所に住んでいて、同じ服を着ているのは同じものだ」という仮定に基づいて、水の中に鱗が生えているのは魚だと結論しました.しかし、これはまだ問題があります.鱗のない魚が今またあなたから排除されているからです.
この問題では、機械学習は人間と同じ問題に直面しており、機械学習では、一つの学習アルゴリズムにも前提仮定があり、ここでは「帰納偏執(bias)」と呼ばれている(biasという英語語は機械学習と統計に他にも多くの意味がある).例えば線形回帰は、与えられたデータ点にできるだけよくフィットする関数を探すことを目的とし、その帰納偏執は「要求を満たす関数は線形関数でなければならない」である.帰納偏執のない学習アルゴリズムはある意味では役に立たない.まるで帰納能力のない人のように、初めて魚を見たとき、それは魚だと言った人がいた.次は別の魚を見た.彼はそれも魚だとは知らなかった.2匹の魚にはいつもいくつかの場所が違うからだ.あるいは同じ魚でも、川の中の違うところで見て、あるいはただ見た時間が違うだけで、彼にも違うと思われます.彼は帰納できないので、主な矛盾を抽出することができず、副次的な要素を無視することができず、すべての条件が完全に同じであることを要求するしかありません.しかし、哲学者は私たちに言ったことがあります.世界には何も同じものはありません.だからこの人は比類のない強い記憶力を持っていても、何の知識も学べない.
この問題は機械学習において「オーバーフィット(Overfitting)」と呼ばれ、例えば前の回帰の問題で、「線形関数」という帰納偏執を取り除くと、N個の点に対して、私たちはいつもN-1次多項式関数を構築して、あるN個の点を完璧に通過させることができ、あるいは私がN-1回より大きい多項式関数を使うと、私は無限に多くの条件を満たす関数を構築することができます.特定の分野の問題が与えられたデータの個数に常に上限があると仮定すれば、私は十分なNを取って、1つの(あるいは無限の複数の)「スーパー関数」を得ることができて、この分野のすべての問題をfitすることができます.しかし、この「スーパー関数」は役に立ちますか?学習の目的(通常)が既存のものを解釈するのではなく、そこから知識をまとめ、新しいものに応用できることに気づくと、結果は明らかになる.
帰納偏執がないか,帰納偏執が広すぎるとOverfittingを招くが,もう一つの極端である過大な帰納偏執を制限することも問題である:データ自体が線形でなければ,線形関数での回帰を強行することは通常良い結果を得ることができない.難点はまさにこの間に平衡点を探すことだ.しかし、ここでは機械に比べて大きな利点があります.人間は通常、独立したシステムやモデルで問題を処理することはなく、毎日各ソースから大量の情報を取得し、様々な手段で統合処理を行い、まとめられたすべての知識を統一的に記憶することができます.有機的に組み合わせて特定の問題を解決することができます.ここの「有機」という言葉はとても面白くて、理論をする人はいつもいろいろなモデルを提出することができて、しかもこれらのモデルはすべて厳格な理論の基礎があって所望の目的を達成することができることを保証して、しかしほとんどのモデルはすべてそんなにいくつかの“パラメータ”(例えばK-meansの中のk)があって、通常パラメータがどの値を取るのがもっと良いことを説明する理論がなくて、モデルの実際の効果は通常パラメータが最適値を取ったかどうかと大きく関係しており、ここで「有機」はすべてのモデルのパラメータが自動的に最適値を取ったと見なすことができると思います.また,進展は大きくないが,コンピュータ分野においても統一的な知識システムを構築することが期待されている(例えば,語意網はこのような試みである).
くだらない話はやっと終わって、GMMに戻りました.私たちの前の議論に従って、流行のアルゴリズムとして、GMMはきっとそれ自身のかなり体面の帰納が偏っているに違いない.実はその仮定は非常に簡単で、その名の通り、Gaussian Mixture Modelは、データがMixture Gaussian Distributionに従うと仮定し、言い換えれば、データは数個のGaussian Distributionから生成されたものと見なすことができる.実際,K‐meansとK‐medoidsの2つの論文で用いた例は,3つのGaussian分布からランダムに選択されたものである.実際,中心極限の定理からGaussian分布(ノーマル分布とも呼ばれる)という仮定は妥当であることが分かるが,それ以外にGaussian分布は計算上もいくつかの良い性質を持っているため,異なる布で勝手にXX Mixture Modelを構築することができるが,GMMが最も流行している.また,Mixture Model自体も実際には任意に複雑になり,Modelの個数を増やすことで任意に連続確率密分布に近づけることができる.
各GMMは
個のGaussian分布からなり、各Gaussianは「Component」と呼ばれ、これらのComponentは線形に加算されてGMMの確率密度関数を構成する.
由于在对数函数里面又有加和，我们没法直接用求导解方程的办法直接求得最大值。为了解决这个问题，我们采取之前从 GMM 中随机选点的办法：分成两步，实际上也就类似于 K-means 的两步。
- 估计数据由每个 Component 生成的概率（并不是每个 Component 被选中的概率）：对于每个数据
来说，它由第 
个 Component 生成的概率为 其中 
，并且 
也顺理成章地可以估计为 
。
- 重复迭代前面两步，直到似然函数的值收敛为止。
当然，上面给出的只是比较“直观”的解释，想看严格的推到过程的话，可以参考 Pattern Recognition and Machine Learning 这本书的第九章。有了实际的步骤，再实现起来就很简单了。Matlab 代码如下：
（Update 2012.07.03：如果你直接把下面的代码拿去运行了，碰到 covariance 矩阵 singular 的情况，可以参见这篇文章。）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
function varargout = gmm(X, K_or_centroids)
% ============================================================
% Expectation-Maximization iteration implementation of
% Gaussian Mixture Model.
%
% PX = GMM(X, K_OR_CENTROIDS)
% [PX MODEL] = GMM(X, K_OR_CENTROIDS)
%
% - X: N-by-D data matrix.
% - K_OR_CENTROIDS: either K indicating the number of
% components or a K-by-D matrix indicating the
% choosing of the initial K centroids.
%
% - PX: N-by-K matrix indicating the probability of each
% component generating each point.
% - MODEL: a structure containing the parameters for a GMM:
% MODEL.Miu: a K-by-D matrix.
% MODEL.Sigma: a D-by-D-by-K matrix.
% MODEL.Pi: a 1-by-K vector.
% ============================================================
threshold = 1e-15;
[N, D] = size(X);
if isscalar(K_or_centroids)
K = K_or_centroids;
% randomly pick centroids
rndp = randperm(N);
centroids = X(rndp(1:K), :);
else
K = size(K_or_centroids, 1);
centroids = K_or_centroids;
end
% initial values
[pMiu pPi pSigma] = init_params();
Lprev = -inf;
while true
Px = calc_prob();
% new value for pGamma
pGamma = Px .* repmat(pPi, N, 1);
pGamma = pGamma ./ repmat(sum(pGamma, 2), 1, K);
% new value for parameters of each Component
Nk = sum(pGamma, 1);
pMiu = diag(1./Nk) * pGamma' * X;
pPi = Nk/N;
for kk = 1:K
Xshift = X-repmat(pMiu(kk, :), N, 1);
pSigma(:, :, kk) = (Xshift' * ...
(diag(pGamma(:, kk)) * Xshift)) / Nk(kk);
end
% check for convergence
L = sum(log(Px*pPi'));
if L-Lprev < threshold
break;
end
Lprev = L;
end
if nargout == 1
varargout = {Px};
else
model = [];
model.Miu = pMiu;
model.Sigma = pSigma;
model.Pi = pPi;
varargout = {Px, model};
end
function [pMiu pPi pSigma] = init_params()
pMiu = centroids;
pPi = zeros(1, K);
pSigma = zeros(D, D, K);
% hard assign x to each centroids
distmat = repmat(sum(X.*X, 2), 1, K) + ...
repmat(sum(pMiu.*pMiu, 2)', N, 1) - ...
2*X*pMiu';
[dummy labels] = min(distmat, [], 2);
for k=1:K
Xk = X(labels == k, :);
pPi(k) = size(Xk, 1)/N;
pSigma(:, :, k) = cov(Xk);
end
end
function Px = calc_prob()
Px = zeros(N, K);
for k = 1:K
Xshift = X-repmat(pMiu(k, :), N, 1);
inv_pSigma = inv(pSigma(:, :, k));
tmp = sum((Xshift*inv_pSigma) .* Xshift, 2);
coef = (2*pi)^(-D/2) * sqrt(det(inv_pSigma));
Px(:, k) = coef * exp(-0.5*tmp);
end
end
end
関数が返すPxは
の行列であり、の各々について、この行列の
行の中で最大の確率値に対応するそのComponentがの属するclusterであれば、完全なクラスタリング方法を実現することができる.最初の例では、GMMの結果は次のとおりです.
以前K-meansが与えた結果に比べて、ここの結果はもっとよく、左下角の比較的まばらなclusterは少し遠くまで走った.もちろん、この問題はもともとMixture Gaussian Distributionが生成したデータが完全に存在するため、GMM(グローバル最適解を求めることができれば)は明らかにこの問題に対して最善のモデリングを行うことができる.
また,上記の解析からGMMとK-meansの反復解法は非常に似ている(いずれもEMアルゴリズムに遡ることができ,次回は詳細に紹介する)ため,K-meansと同様の問題もある--常にグローバル最適化が保証されていないが,運が悪く,悪い初期値を取ると,悪い結果が得られる可能性がある.K-meansの場合、私たちは通常一定の回数を繰り返して最高の結果を取りますが、GMMの反復ごとの計算量はK-meansよりもずっと大きく、K-means(繰り返して最適値を取った)で大まかな結果を得るのがもっと流行しています.そしてこれを初期値として(K-meansで得られたcentroidsをgmm関数に入力すればよい)、GMMで細かく反復する.
私たちが最初に議論したように、GMMが得た結果(Px)は、データポイントのlabelだけでなく、データポイントがlabelごとにマークされる確率を含んでおり、実際には非常に有用な情報であることが多い.最後に,GMM自体はモデルにすぎず,ここで与えた反復法は唯一の解法ではないことを指摘する必要がある.興味のある学生は自分で関連資料を探すことができます.
Tags: Clustering, Unsupervised Learning
192 comments to漫談Clustering(3):Gaussian Mixture Model
