خوارزمية EM هي أداة مفيدة لنمذجة البيانات عند تعظيم احتمال "على الجبهة" من خلال التمايز غير ممكن. التكتل هو أحد المهام حيث تأتي هذه الخوارزمية للإنقاذ. تقدم المقالة استنتاجًا عامًا لخوارزمية EM للتجميع.

مهمة

العديد من النقاط $X= \{ x_i, i\in1..N \}$ بحاجة إلى تقسيمها إلى $K$ عناقيد المجموعات.

فكرة الحل

نقوم بتكوين نموذج احتمالي لتوزيع النقاط عبر المجموعات. دعونا نجد معلمات النموذج التي يكون احتمال مراقبة المجموعة لها $X$ أقصى. باستخدام هذه المعلمات ، سنتمكن من تحديد المجموعة التي تنتمي إليها النقطة الأكثر احتمالًا. $x$ .

نموذج البيانات

نقدم سلسلة من الرموز المستعارة من الدورة .

$p(x)$ - احتمالية ملاحظة نقطة $x$ .

$p(X) = \prod_{i=1}^{N}p(x_i)$ - احتمالية ملاحظة الكثيرين $X$ .

$p_j (x) = \varphi(x; \theta_j)$ - احتمالية تلبية نقطة $x$ في كتلة $j$ . يتم توزيع هذا التوزيع بواسطة معلمة (أو ناقل معلمة) $\theta_j$ خاص بالكتلة $j$ .

$w_j$ - احتمال الكتلة $j$ ، بمعنى آخر. احتمال أن تنتمي نقطة مختارة عشوائيًا إلى مجموعة $j$ . تشير النقطة المختارة عشوائيًا بالضبط إلى كتلة ، لذلك $\sum_{j=1}^K w_j = 1$ .

من التعريفات أعلاه يتبع ذلك $p(x) = \sum_{j=1}^K w_j p_j(x) = \sum_{j=1}^K w_j \varphi(x; \theta_j)$ ، بمعنى آخر. توزيع النقاط على غرار مزيج من توزيعات الكتلة.

ونتيجة لذلك ، النموذج الاحتمالي لمجموعة النقاط $X$ :

p (X) = \prod_{i = 1}^{N} (\sum_{j = 1}^{K} w_{j} φ (x_{i}; θ_{j}))

$p(X) = \prod_{i=1}^{N}\left(\sum_{j=1}^K w_j \varphi(x_i; \theta_j)\right)$

بحث المعلمات

معلمات النموذج $w$ و $\theta$ ، كما هو موضح أعلاه ، يجب أن يوفر أقصى احتمال لبياناتنا:

w, θ = argmax p (X) = argmax \log p (X) = {argmax}_{w, θ} \sum_{i = 1}^{N} \log (\sum_{j = 1}^{K} w_{j} φ (x_{i}; θ_{j}))

$w, \theta = \textrm{argmax} \ p(X) = \textrm{argmax} \ \log p(X) = \textrm{argmax}_{w, \theta} \sum_{i=1}^{N} \log \left(\sum_{j=1}^K w_j \varphi(x_i; \theta_j)\right)$

يتداخل المجموع تحت علامة اللوغاريتم مع حل المشكلة بشكل تحليلي. حدود $\sum_{j=1}^K w_j = 1$ (, TensorFlow PyTorch).

L :=   log p(X)
while log p(X)  :
     L  log p(X)
    w, theta = argmax L

, $\log p(X)$ , . $\mathcal{L}$ :

$\mathcal{L}$ : "" , $\log p(X)$ .
$w$ $\theta$ , $\mathcal{L}$ .

, "" , .

$\mathcal{L}$

\log p (X) = \sum_{i = 1}^{N} \log (\sum_{j = 1}^{K} w_{j} φ (x_{i}; θ_{j}))

$\log p(X) = \sum_{i=1}^{N} \log \left(\sum_{j=1}^K w_j \varphi(x_i; \theta_j)\right)$

. $g_i$ $x_i$ :

g_{i} (j) \equiv p (быть в кластере j | это точка i)

$g_i(j) \equiv p(\textrm{ } \ j| \textrm{ } \ i)$

\sum_{i = 1}^{N} \log (\sum_{j = 1}^{K} w_{j} φ (x_{i}; θ_{j})) = \sum_{i = 1}^{N} \log (\sum_{j = 1}^{K} \frac{g_{i} (j)}{g_{i} (j)} w_{j} φ (x_{i}; θ_{j}))

$\sum_{i=1}^{N} \log \left(\sum_{j=1}^K w_j \varphi(x_i; \theta_j)\right) =\sum_{i=1}^{N} \log \left(\sum_{j=1}^K \frac{ g_i(j) }{ g_i(j) } w_j \varphi(x_i; \theta_j)\right)$

. :

\log (\sum_{i} q_{i} x_{i}) \geq \sum_{i} q_{i} \log x_{i}

$\log \left(\sum_i q_i x_i \right) \geq \sum_i q_i \log x_i$

, $q_i$ $1$ .

$g_i(j)$ : $\sum_{j=1}^K g_i(j) = 1$ . :

\sum_{i = 1}^{N} \log (\sum_{j = 1}^{K} \frac{g_{i} (j)}{g_{i} (j)} w_{j} φ (x_{i}; θ_{j})) \geq \sum_{i = 1}^{N} \sum_{j = 1}^{K} g_{i} (j) \log (\frac{w_{j} φ (x_{i}; θ_{j})}{g_{i} (j)})

$\sum_{i=1}^{N} \log \left(\sum_{j=1}^K \frac{ g_i(j) }{ g_i(j) } w_j \varphi(x_i; \theta_j)\right) \geq \sum_{i=1}^{N} \sum_{j=1}^K g_i(j) \log \left(\frac{ w_j \varphi(x_i; \theta_j) }{ g_i(j) }\right)$

L (g, w, θ) \equiv \sum_{i = 1}^{N} \sum_{j = 1}^{K} g_{i} (j) \log (\frac{w_{j} φ (x_{i}; θ_{j})}{g_{i} (j)})

$\mathcal{L}(g, w, \theta) \equiv \sum_{i=1}^{N} \sum_{j=1}^K g_i(j) \log \left(\frac{ w_j \varphi(x_i; \theta_j) }{ g_i(j) }\right)$

$\mathcal{L}$ (E-)

$\mathcal{L}(g, w, \theta)$ $\log p(X)$ . $w$ $\theta$ , $\mathcal{L}$ $g$ .

$\log p(X)$ $\mathcal{L}$ , , :

\log p (X) - L (g, w, θ) = \sum_{i = 1}^{N} \log p (x_{i}) - \sum_{i = 1}^{N} \sum_{j = 1}^{K} g_{i} (j) \log (\frac{w_{j} φ (x_{i}; θ_{j})}{g_{i} (j)}) =

$\log p(X) - \mathcal{L}(g, w, \theta) = \sum_{i=1}^N \log p(x_i) - \sum_{i=1}^{N} \sum_{j=1}^K g_i(j) \log \left(\frac{ w_j \varphi(x_i; \theta_j) }{ g_i(j) }\right)=$

= \sum_{i = 1}^{N} (\log p (x_{i}) \sum_{j = 1}^{K} g_{i} (j) - \sum_{j = 1}^{K} g_{i} (j) \log \frac{w_{j} φ (x_{i}; θ_{j})}{g_{i} (j)}) = \sum_{i = 1}^{N} \sum_{j = 1}^{K} g_{i} (j) \log \frac{p (x_{i}) g_{i} (j)}{w_{j} φ (x_{i}; θ_{j})}

$= \sum_{i=1}^N \left(\log p(x_i) \sum_{j=1}^K g_i(j) - \sum_{j=1}^K g_i(j) \log \frac{w_j \varphi(x_i; \theta_j)}{g_i(j)} \right) = \sum_{i=1}^N \sum_{j=1}^K g_i(j) \log \frac{p(x_i) g_i(j)}{w_j \varphi(x_i; \theta_j)}$

, $j$ :

p (j | x_{i}) = \frac{φ (x_{i}; θ_{j}) w_{j}}{p (x_{i})}

$p(j|x_i) = \frac{\varphi(x_i; \theta_j) w_j}{p(x_i)}$

\sum_{i = 1}^{N} \sum_{j = 1}^{K} g_{i} (j) \log \frac{p (x_{i}) g_{i} (j)}{w_{j} φ (x_{i}; θ_{j})} = \sum_{i = 1}^{N} \sum_{j = 1}^{K} g_{i} (j) \log \frac{g_{i} (j)}{p (j | x_{i})} = \sum_{i = 1}^{N} E_{g_{i}} \frac{g_{i}}{p (j | x_{i})}

$\sum_{i=1}^N \sum_{j=1}^K g_i(j) \log \frac{p(x_i) g_i(j)}{w_j \varphi(x_i; \theta_j)} = \sum_{i=1}^N \sum_{j=1}^K g_i(j) \log \frac{g_i(j)}{p(j|x_i)}= \sum_{i=1}^N \mathbb{E}_{g_i} \frac{g_{i}}{p(j|x_i)}$

: . - ( KL-) "" .

, $\log p(X)$ $\mathcal{L}$ — KL-:

\log p (X) - L (g, w, θ) = \sum_{i = 1}^{N} K L (g_{i} | | p (j | x_{i}))

$\log p(X) - \mathcal{L}(g, w, \theta) = \sum_{i=1}^N KL(g_i || p(j|x_i))$

KL- , , — KL- . : KL- , — . $g_i(j)$ $p(j|x_i)$ :

g_{i} (j) = p (j | x_{i}) = \frac{w_{j} φ (x_{i}; θ_{j})}{p (x_{i})}

$g_i(j) = p(j|x_i) = \frac{w_j \varphi(x_i; \theta_j)}{p(x_i)}$

$g_i(j)$ $\mathcal{L}$ $\log p(X)$ .

$\mathcal{L}$ (M-)

: . :

$g$ ثابت؛
المعلمات $w$ و $\theta$ تخضع للتحسين.

تبسيط قبل التحسين $\mathcal{L}$ :

L (g, θ) = \sum_{i = 1}^{N} (\sum_{j = 1}^{K} g_{i} (j) \log \frac{w_{j} p (x_{i}; θ_{j})}{g_{i} (j)}) =

$\mathcal{L}(g, \theta) = \sum_{i=1}^N\left( \sum_{j=1}^K g_i(j) \log \frac{w_j p(x_i; \theta_j)}{g_i(j)} \right) =$

= \sum_{i = 1}^{N} \sum_{j = 1}^{K} g_{i} (j) \log (w_{j} p (x_{i}; θ_{j})) - \sum_{i = 1}^{N} \sum_{j = 1}^{K} g_{i} (j) \log g_{i} (j)

$= \sum_{i=1}^N \sum_{j=1}^K g_i(j) \log \left( w_j p(x_i; \theta_j) \right) -\sum_{i=1}^N \sum_{j=1}^K g_i(j) \log g_i(j)$

المصطلح الثاني مستقل عن المعلمات $w$ و $\theta$ وبالتالي ، سنقوم بتحسين المصطلح الأول فقط:

w, θ = {argmax}_{w, θ} \sum_{i = 1}^{N} \sum_{j = 1}^{K} g_{i} (j) \log (w_{j} φ (x_{i}; θ_{j}))

$w, \theta = \textrm{argmax}_{w, \theta}\sum_{i=1}^N \sum_{j=1}^K g_i(j) \log \left( w_j \varphi(x_i; \theta_j) \right)$

نحن نحلل لوغاريتم المنتج في مجموع اللوغاريتمات ونحصل على:

w = {argmax}_{w} \sum_{i = 1}^{N} \sum_{j = 1}^{K} g_{i} (j) \log w_{j}, при условии \sum_{j = 1} w_{j} = 1

$w = \textrm{argmax}_{w}\sum_{i=1}^N \sum_{j=1}^K g_i(j) \log w_j, \textrm{ }\sum_{j=1} w_j = 1$

θ_{j} = argmax \sum_{i = 1}^{N} g_{i} (j) \log φ (x_{i}; θ_{j})

$\theta_j = \textrm{argmax} \sum_{i=1}^N g_i(j) \log \varphi (x_i; \theta_j)$

يتم حل المشكلة الأولى عن طريق طريقة مضاعفة Lagrange. نتيجة:

w_{j} = \frac{1}{N} \sum_{i = 1}^{N} g_{i} (j)

$w_j = \frac{1}{N} \sum_{i=1}^N g_i(j)$

يعتمد حل المشكلة الثانية على نوع توزيع الكتلة المحدد $\varphi (x_i; \theta_j)$ . كما ترى ، بالنسبة للحل الخاص به ، لم يعد عليك التعامل مع المجموع تحت علامة اللوغاريتم ، وبالتالي ، على سبيل المثال ، للتوزيعات الغوسية ، يمكن كتابة الحل بشكل تحليلي.

مجموع

اكتشفنا جوهر تكرارات خوارزمية EM للتجميع ، وشاهدنا كيف يتم اشتقاق صيغها بطريقة عامة.

خوارزمية EM للتجميع

مهمة

فكرة الحل

نموذج البيانات

بحث المعلمات

L\mathcal{L}

L\mathcal{L}(E-)

L\mathcal{L}(M-)

مجموع

More articles:

$\mathcal{L}$

$\mathcal{L}$ (E-)

$\mathcal{L}$ (M-)