期待値最大化（EM）は、データを分類するための一種の確率的手法です。分類子でない場合、間違っている場合は訂正してください。
このEM技術の直感的な説明は何ですか？expectationここには何があり、何が起こっているのmaximizedですか？
質問する
44629 次
8 に答える
37
EM は、モデル内の一部の変数が観測されていない場合 (つまり、潜在変数がある場合) に尤度関数を最大化するためのアルゴリズムです。
関数を最大化しようとしているだけなら、関数を最大化するために既存の機構を使用しないのはなぜでしょうか。導関数を取り、それらをゼロに設定してこれを最大化しようとすると、多くの場合、1 次条件には解がないことがわかります。モデル パラメーターを解決するには、観測されていないデータの分布を知る必要があるという、ニワトリが先か卵が先かという問題があります。ただし、観測されていないデータの分布は、モデル パラメーターの関数です。
EM は、観測されていないデータの分布を繰り返し推測し、実際の尤度関数の下限である何かを最大化してモデル パラメーターを推定し、収束するまで繰り返すことで、これを回避しようとします。
EMアルゴリズム
モデル パラメーターの値を推測することから始めます
E-ステップ: 欠損値を持つ各データポイントについて、モデル方程式を使用して、モデル パラメーターの現在の推定値と観測データを考慮して、欠損データの分布を解きます (欠損値ごとに分布を解いていることに注意してください)。値であり、期待値ではありません)。各欠損値の分布が得られたので、観測されていない変数に関する尤度関数の期待値を計算できます。モデル パラメーターの推測が正しかった場合、この予想される可能性は、観測されたデータの実際の可能性になります。パラメータが正しくない場合、それは単なる下限になります。
M ステップ: 観測されていない変数を含まない期待される尤度関数が得られたので、完全に観測された場合と同様に関数を最大化し、モデル パラメーターの新しい推定値を取得します。
収束するまで繰り返します。
于 2012-08-04T20:09:38.927 に答える
28
期待値最大化アルゴリズムを理解するための簡単なレシピを次に示します。
1- Do と Batzoglou によるこのEM チュートリアル ペーパーを読んでください。
2-頭の中にクエスチョン マークがあるかもしれません。この maths stack exchange pageの説明を見てください。
3-私が Python で書いたこのコードを見てください。これは、項目 1 の EM チュートリアル ペーパーの例を説明しています。
警告 :私は Python 開発者ではないため、コードが乱雑で最適ではない可能性があります。しかし、それは仕事をします。
import numpy as np
import math
#### E-M Coin Toss Example as given in the EM tutorial paper by Do and Batzoglou* ####
def get_mn_log_likelihood(obs,probs):
""" Return the (log)likelihood of obs, given the probs"""
# Multinomial Distribution Log PMF
# ln (pdf) = multinomial coeff * product of probabilities
# ln[f(x|n, p)] = [ln(n!) - (ln(x1!)+ln(x2!)+...+ln(xk!))] + [x1*ln(p1)+x2*ln(p2)+...+xk*ln(pk)]
multinomial_coeff_denom= 0
prod_probs = 0
for x in range(0,len(obs)): # loop through state counts in each observation
multinomial_coeff_denom = multinomial_coeff_denom + math.log(math.factorial(obs[x]))
prod_probs = prod_probs + obs[x]*math.log(probs[x])
multinomial_coeff = math.log(math.factorial(sum(obs))) - multinomial_coeff_denom
likelihood = multinomial_coeff + prod_probs
return likelihood
# 1st: Coin B, {HTTTHHTHTH}, 5H,5T
# 2nd: Coin A, {HHHHTHHHHH}, 9H,1T
# 3rd: Coin A, {HTHHHHHTHH}, 8H,2T
# 4th: Coin B, {HTHTTTHHTT}, 4H,6T
# 5th: Coin A, {THHHTHHHTH}, 7H,3T
# so, from MLE: pA(heads) = 0.80 and pB(heads)=0.45
# represent the experiments
head_counts = np.array([5,9,8,4,7])
tail_counts = 10-head_counts
experiments = zip(head_counts,tail_counts)
# initialise the pA(heads) and pB(heads)
pA_heads = np.zeros(100); pA_heads[0] = 0.60
pB_heads = np.zeros(100); pB_heads[0] = 0.50
# E-M begins!
delta = 0.001
j = 0 # iteration counter
improvement = float('inf')
while (improvement>delta):
expectation_A = np.zeros((5,2), dtype=float)
expectation_B = np.zeros((5,2), dtype=float)
for i in range(0,len(experiments)):
e = experiments[i] # i'th experiment
ll_A = get_mn_log_likelihood(e,np.array([pA_heads[j],1-pA_heads[j]])) # loglikelihood of e given coin A
ll_B = get_mn_log_likelihood(e,np.array([pB_heads[j],1-pB_heads[j]])) # loglikelihood of e given coin B
weightA = math.exp(ll_A) / ( math.exp(ll_A) + math.exp(ll_B) ) # corresponding weight of A proportional to likelihood of A
weightB = math.exp(ll_B) / ( math.exp(ll_A) + math.exp(ll_B) ) # corresponding weight of B proportional to likelihood of B
expectation_A[i] = np.dot(weightA, e)
expectation_B[i] = np.dot(weightB, e)
pA_heads[j+1] = sum(expectation_A)[0] / sum(sum(expectation_A));
pB_heads[j+1] = sum(expectation_B)[0] / sum(sum(expectation_B));
improvement = max( abs(np.array([pA_heads[j+1],pB_heads[j+1]]) - np.array([pA_heads[j],pB_heads[j]]) ))
j = j+1
于 2013-07-11T15:11:02.877 に答える
18
技術的には、「EM」という用語は少し明確ではありませんが、一般的な EM 原理のインスタンスであるガウス混合モデリング クラスター分析手法を指していると思います。
実はEMクラスター分析は分類器ではありません。クラスタリングを「教師なし分類」と考える人がいることは知っていますが、実際のクラスタ分析はまったく別のものです。
主な違い、およびクラスター分析に関して人々が常に持っている大きな誤解は、クラスター分析には「正しい解」がないということです。それは知識発見方法であり、実際には何か新しいものを見つけることを意図しています! これにより、評価が非常に難しくなります。多くの場合、参照として既知の分類を使用して評価されますが、それが常に適切であるとは限りません。所有している分類は、データの内容を反映している場合と反映していない場合があります。
例を挙げましょう。性別データを含む顧客の大量のデータセットがあります。このデータセットを「男性」と「女性」に分割する方法は、既存のクラスと比較する場合に最適です。「予測」の考え方では、これは良いことです。新しいユーザーについては、性別を予測できるようになりました。「知識発見」の考え方では、これは実際には悪いことです。なぜなら、データの新しい構造を発見したかったからです。ただし、たとえばデータを高齢者と子供に分割する方法は、男性/女性クラスに関して可能な限り悪いスコアになります。ただし、これは優れたクラスタリング結果になります (年齢が指定されていない場合)。
EMに戻ります。基本的に、データが複数の多変量正規分布で構成されていることを前提としています (特にクラスター数を固定する場合、これは非常に強い前提であることに注意してください!)。次に、モデルとモデルへのオブジェクトの割り当てを交互に改善することにより、これに対する局所的な最適モデルを見つけようとします。
分類コンテキストで最良の結果を得るには、クラスの数よりも大きいクラスターの数を選択するか、単一のクラスのみにクラスター化を適用します(クラス内に何らかの構造があるかどうかを調べるためです!)。
「車」、「バイク」、「トラック」を区別するように分類器をトレーニングするとします。データが正確に 3 つの正規分布で構成されていると仮定しても、ほとんど意味がありません。ただし、複数の種類の車(およびトラックとバイク)があると想定することもできます。したがって、これら 3 つのクラスの分類器をトレーニングする代わりに、車、トラック、バイクをそれぞれ 10 個のクラスター (または、車 10 台、トラック 3 台、バイク 3 台など) にクラスター化し、分類器をトレーニングしてこれらの 30 クラスを区別します。クラスの結果を元のクラスにマージします。Trikes など、特に分類が難しいクラスターが 1 つあることに気付く場合もあります。どちらかというと車で、どちらかというとバイクです。または、トラックというよりも特大車に近い配達用トラック。
于 2012-08-04T21:45:11.330 に答える
2
他の回答が良かったので、別の視点を提供して、質問の直感的な部分に取り組みます。
EM (Expectation-Maximization) アルゴリズムは、双対性を使用した反復アルゴリズムのクラスの変形です。
抜粋（強調鉱山）：
数学では、双対性は、一般に、概念、定理、または数学的構造を、1 対 1 の方法で、多くの場合 (常にではありませんが) 畳み込み操作によって、他の概念、定理、または構造に変換します。 A が B である場合、B の双対は A です。このような退縮には固定点 がある場合があり、A の双対は A そのものです。
通常、オブジェクトA の双対B は、ある程度の対称性または互換性を保持する何らかの方法で A に関連付けられます。たとえば、AB = const
(前の意味での) 双対性を使用する反復アルゴリズムの例は次のとおりです。
- 最大公約数のユークリッド アルゴリズムとその変形
- Gram–Schmidt Vector Basis アルゴリズムとバリアント
- 算術平均 - 幾何平均不等式とその変形
- 期待値最大化アルゴリズムとそのバリアント(情報幾何学的ビューについては、こちらも参照してください)
- (..他の同様のアルゴリズム..)
同様に、EM アルゴリズムも 2 つの二重の最大化ステップと見なすことができます。
..[EM] は、パラメータと観測されていない変数の分布の結合関数を最大化するものと見なされます。E ステップは、観測されていない変数の分布に関してこの関数を最大化します。パラメータに関するMステップ..
双対性を使用する反復アルゴリズムでは、平衡 (または固定) 収束点の明示的 (または暗黙的) 仮定があります (EM の場合、これは Jensen の不等式を使用して証明されます)。
したがって、そのようなアルゴリズムの概要は次のとおりです。
- E のようなステップ:与えられたyが一定に保持されていることに関して、最適解xを見つけます。
- M のようなステップ (デュアル):一定に保たれているx (前のステップで計算されたもの)に関して最良の解yを見つけます。
- 終了基準/収束ステップ:収束するまで (または指定された反復回数に達するまで) 、 x、yの更新された値でステップ 1、2 を繰り返します。
このようなアルゴリズムが (大域的) 最適に収束する場合、両方の意味で (つまり、x ドメイン/パラメーターと y ドメイン/パラメーターの両方で) 最適な構成が見つかったことに注意してください。ただし、このアルゴリズムは、グローバル最適ではなく、ローカル最適のみを見つけることができます。
これは、アルゴリズムの概要の直感的な説明だと思います
統計的議論とアプリケーションについては、他の回答が適切な説明を提供しています（この回答の参考文献も確認してください）
于 2015-03-03T01:22:51.580 に答える
2
受け入れられた回答は、EMを説明するまともな仕事をしているChuong EM Paperを参照しています。論文をより詳細に説明するyoutube ビデオもあります。
要約すると、シナリオは次のとおりです。
1st: {H,T,T,T,H,H,T,H,T,H} 5 Heads, 5 Tails; Did coin A or B generate me?
2nd: {H,H,H,H,T,H,H,H,H,H} 9 Heads, 1 Tails
3rd: {H,T,H,H,H,H,H,T,H,H} 8 Heads, 2 Tails
4th: {H,T,H,T,T,T,H,H,T,T} 4 Heads, 6 Tails
5th: {T,H,H,H,T,H,H,H,T,H} 7 Heads, 3 Tails
Two possible coins, A & B are used to generate these distributions.
A & B have an unknown parameter: their bias towards heads.
We don't know the biases, but we can simply start with a guess: A=60% heads, B=50% heads.
最初の試行の質問の場合、表の割合が B のバイアスと非常によく一致するため、直観的には B が生成したと思いますが、その値は推測にすぎないため、確信が持てません。
それを念頭に置いて、私はEMソリューションを次のように考えるのが好きです:
- フリップの各試行は、どのコインが最も好きかを「投票」します
- これは、各コインがその分布にどれだけ適合しているかに基づいています
- または、コインの観点からは、他のコインと比較して、この試行が見られるという高い期待があります (対数の可能性に基づく)。
- 各トライアルが各コインをどれだけ気に入っているかに応じて、そのコインのパラメーター (バイアス) の推測を更新できます。
- トライアルがコインを好きになればなるほど、コインのバイアスを更新して自分自身を反映させることができます!
- 基本的に、コインのバイアスは、すべての試行でこれらの重み付けされた更新を組み合わせることによって更新されます。これは ( maximazation ) と呼ばれるプロセスです。
これは単純化しすぎている可能性があります (または、いくつかのレベルでは根本的に間違っていることさえあります) が、これが直感的なレベルで役立つことを願っています!
于 2016-09-30T02:20:17.750 に答える
1
Zhubarb の回答で引用された Do と Batzoglou による同じ記事を使用して、Javaでその問題に対して EM を実装しました。彼の答えへのコメントは、アルゴリズムが局所最適でスタックすることを示しています。これは、パラメーター thetaA と thetaB が同じ場合、私の実装でも発生します。
以下は私のコードの標準出力で、パラメータの収束を示しています。
thetaA = 0.71301, thetaB = 0.58134
thetaA = 0.74529, thetaB = 0.56926
thetaA = 0.76810, thetaB = 0.54954
thetaA = 0.78316, thetaB = 0.53462
thetaA = 0.79106, thetaB = 0.52628
thetaA = 0.79453, thetaB = 0.52239
thetaA = 0.79593, thetaB = 0.52073
thetaA = 0.79647, thetaB = 0.52005
thetaA = 0.79667, thetaB = 0.51977
thetaA = 0.79674, thetaB = 0.51966
thetaA = 0.79677, thetaB = 0.51961
thetaA = 0.79678, thetaB = 0.51960
thetaA = 0.79679, thetaB = 0.51959
Final result:
thetaA = 0.79678, thetaB = 0.51960
以下は、問題を解決するための EM の Java 実装です (Do and Batzoglou、2008 年)。実装のコア部分は、パラメーターが収束するまで EM を実行するループです。
private Parameters _parameters;
public Parameters run()
{
while (true)
{
expectation();
Parameters estimatedParameters = maximization();
if (_parameters.converged(estimatedParameters)) {
break;
}
_parameters = estimatedParameters;
}
return _parameters;
}
以下はコード全体です。
import java.util.*;
/*****************************************************************************
This class encapsulates the parameters of the problem. For this problem posed
in the article by (Do and Batzoglou, 2008), the parameters are thetaA and
thetaB, the probability of a coin coming up heads for the two coins A and B,
respectively.
*****************************************************************************/
class Parameters
{
double _thetaA = 0.0; // Probability of heads for coin A.
double _thetaB = 0.0; // Probability of heads for coin B.
double _delta = 0.00001;
public Parameters(double thetaA, double thetaB)
{
_thetaA = thetaA;
_thetaB = thetaB;
}
/*************************************************************************
Returns true if this parameter is close enough to another parameter
(typically the estimated parameter coming from the maximization step).
*************************************************************************/
public boolean converged(Parameters other)
{
if (Math.abs(_thetaA - other._thetaA) < _delta &&
Math.abs(_thetaB - other._thetaB) < _delta)
{
return true;
}
return false;
}
public double getThetaA()
{
return _thetaA;
}
public double getThetaB()
{
return _thetaB;
}
public String toString()
{
return String.format("thetaA = %.5f, thetaB = %.5f", _thetaA, _thetaB);
}
}
/*****************************************************************************
This class encapsulates an observation, that is the number of heads
and tails in a trial. The observation can be either (1) one of the
experimental observations, or (2) an estimated observation resulting from
the expectation step.
*****************************************************************************/
class Observation
{
double _numHeads = 0;
double _numTails = 0;
public Observation(String s)
{
for (int i = 0; i < s.length(); i++)
{
char c = s.charAt(i);
if (c == 'H')
{
_numHeads++;
}
else if (c == 'T')
{
_numTails++;
}
else
{
throw new RuntimeException("Unknown character: " + c);
}
}
}
public Observation(double numHeads, double numTails)
{
_numHeads = numHeads;
_numTails = numTails;
}
public double getNumHeads()
{
return _numHeads;
}
public double getNumTails()
{
return _numTails;
}
public String toString()
{
return String.format("heads: %.1f, tails: %.1f", _numHeads, _numTails);
}
}
/*****************************************************************************
This class runs expectation-maximization for the problem posed by the article
from (Do and Batzoglou, 2008).
*****************************************************************************/
public class EM
{
// Current estimated parameters.
private Parameters _parameters;
// Observations from the trials. These observations are set once.
private final List<Observation> _observations;
// Estimated observations per coin. These observations are the output
// of the expectation step.
private List<Observation> _expectedObservationsForCoinA;
private List<Observation> _expectedObservationsForCoinB;
private static java.io.PrintStream o = System.out;
/*************************************************************************
Principal constructor.
@param observations The observations from the trial.
@param parameters The initial guessed parameters.
*************************************************************************/
public EM(List<Observation> observations, Parameters parameters)
{
_observations = observations;
_parameters = parameters;
}
/*************************************************************************
Run EM until parameters converge.
*************************************************************************/
public Parameters run()
{
while (true)
{
expectation();
Parameters estimatedParameters = maximization();
o.printf("%s\n", estimatedParameters);
if (_parameters.converged(estimatedParameters)) {
break;
}
_parameters = estimatedParameters;
}
return _parameters;
}
/*************************************************************************
Given the observations and current estimated parameters, compute new
estimated completions (distribution over the classes) and observations.
*************************************************************************/
private void expectation()
{
_expectedObservationsForCoinA = new ArrayList<Observation>();
_expectedObservationsForCoinB = new ArrayList<Observation>();
for (Observation observation : _observations)
{
int numHeads = (int)observation.getNumHeads();
int numTails = (int)observation.getNumTails();
double probabilityOfObservationForCoinA=
binomialProbability(10, numHeads, _parameters.getThetaA());
double probabilityOfObservationForCoinB=
binomialProbability(10, numHeads, _parameters.getThetaB());
double normalizer = probabilityOfObservationForCoinA +
probabilityOfObservationForCoinB;
// Compute the completions for coin A and B (i.e. the probability
// distribution of the two classes, summed to 1.0).
double completionCoinA = probabilityOfObservationForCoinA /
normalizer;
double completionCoinB = probabilityOfObservationForCoinB /
normalizer;
// Compute new expected observations for the two coins.
Observation expectedObservationForCoinA =
new Observation(numHeads * completionCoinA,
numTails * completionCoinA);
Observation expectedObservationForCoinB =
new Observation(numHeads * completionCoinB,
numTails * completionCoinB);
_expectedObservationsForCoinA.add(expectedObservationForCoinA);
_expectedObservationsForCoinB.add(expectedObservationForCoinB);
}
}
/*************************************************************************
Given new estimated observations, compute new estimated parameters.
*************************************************************************/
private Parameters maximization()
{
double sumCoinAHeads = 0.0;
double sumCoinATails = 0.0;
double sumCoinBHeads = 0.0;
double sumCoinBTails = 0.0;
for (Observation observation : _expectedObservationsForCoinA)
{
sumCoinAHeads += observation.getNumHeads();
sumCoinATails += observation.getNumTails();
}
for (Observation observation : _expectedObservationsForCoinB)
{
sumCoinBHeads += observation.getNumHeads();
sumCoinBTails += observation.getNumTails();
}
return new Parameters(sumCoinAHeads / (sumCoinAHeads + sumCoinATails),
sumCoinBHeads / (sumCoinBHeads + sumCoinBTails));
//o.printf("parameters: %s\n", _parameters);
}
/*************************************************************************
Since the coin-toss experiment posed in this article is a Bernoulli trial,
use a binomial probability Pr(X=k; n,p) = (n choose k) * p^k * (1-p)^(n-k).
*************************************************************************/
private static double binomialProbability(int n, int k, double p)
{
double q = 1.0 - p;
return nChooseK(n, k) * Math.pow(p, k) * Math.pow(q, n-k);
}
private static long nChooseK(int n, int k)
{
long numerator = 1;
for (int i = 0; i < k; i++)
{
numerator = numerator * n;
n--;
}
long denominator = factorial(k);
return (long)(numerator / denominator);
}
private static long factorial(int n)
{
long result = 1;
for (; n >0; n--)
{
result = result * n;
}
return result;
}
/*************************************************************************
Entry point into the program.
*************************************************************************/
public static void main(String argv[])
{
// Create the observations and initial parameter guess
// from the (Do and Batzoglou, 2008) article.
List<Observation> observations = new ArrayList<Observation>();
observations.add(new Observation("HTTTHHTHTH"));
observations.add(new Observation("HHHHTHHHHH"));
observations.add(new Observation("HTHHHHHTHH"));
observations.add(new Observation("HTHTTTHHTT"));
observations.add(new Observation("THHHTHHHTH"));
Parameters initialParameters = new Parameters(0.6, 0.5);
EM em = new EM(observations, initialParameters);
Parameters finalParameters = em.run();
o.printf("Final result:\n%s\n", finalParameters);
}
}
于 2014-11-22T00:03:23.333 に答える