الاستدلال على عالَم متغيّر

تصف الشبكة البايزية عالَمًا يبقى ساكنًا. وأكثر العوالم ليست كذلك. فأنت تراقب مريضًا أو سوقًا أو طريقًا من خلال أجهزة استشعار مشوَّشة متقطّعة، والشيء الذي يعنيك يظلّ يتحرّك بينما تنظر إليه. وهذا المقال عن العُدّة اللازمة لذلك، وعن موضع واحد يعطي فيه النهج البديهي جوابًا خاطئًا في صمت.

أ. فرضيتان

اقسم المتغيّرات إلى حالة $\mathbf{X}_t$، وهي صحيحة لكنها مخفية، وشواهد $\mathbf{E}_t$، وهي ما ترصده. والصعوبة أن $P(\mathbf{X}_t \mid \mathbf{X}_{0:t-1})$ له مجموعة آباء تنمو أبدًا. وفرضيّتان تحدّانها.

تقول فرضية ماركوف إن الحالة الراهنة لا تتوقّف على التاريخ إلا من خلال الحالة السابقة، $\mathbf{P}(\mathbf{X}_t \mid \mathbf{X}_{0:t-1}) = \mathbf{P}(\mathbf{X}_t \mid \mathbf{X}_{t-1})$. وتقول فرضية ماركوف للاستشعار إن القراءة الراهنة لا تتوقّف إلا على الحالة الراهنة. وكلتاهما دعوى عن حسن اختيار متغيّر الحالة، لا عن العتاد: فإن كانت قراءة الأمس لا تزال تُخبر عن قراءة اليوم بعدما عُلمت حالة اليوم، فالحالة ينقصها شيء، والإصلاح أن تُثريها.

ومثال راسل ونورفيغ حارس أمن تحت الأرض يريد أن يعرف هل تمطر السماء، ولا قرينة لديه إلا هل يصل المدير بمظلّة:

$$\begin{array}{ll} P(R_0) = \langle 0.5,\ 0.5 \rangle & \\[4pt] P(r_t \mid r_{t-1}) = 0.7 & P(r_t \mid \lnot r_{t-1}) = 0.3 \\[4pt] P(u_t \mid r_t) = 0.9 & P(u_t \mid \lnot r_t) = 0.2 \end{array}$$

فالمطر يدوم، والمظلّة وكيل لا بأس به لكنه غير تامّ. وبوضع الفرضيتين يتحلّل التوزيع المشترك على تاريخ كامل إلى توزيع قبليّ ونموذج انتقال ونموذج استشعار:

$$P(\mathbf{X}_{0:t}, \mathbf{E}_{1:t}) = P(\mathbf{X}_0) \prod_{i=1}^{t} P(\mathbf{X}_i \mid \mathbf{X}_{i-1})\, P(\mathbf{E}_i \mid \mathbf{X}_i).$$

فثلاثة عوامل صغيرة تصف الآن تاريخًا أيّ طول كان. ولكل سؤال جواب - اجمع التواريخ التي توافقه - وذلك الجواب يكلّف $2^t$، ولهذا السبب وُجد بقيّة هذا المقال.

ب. الترشيح والتنبّؤ والتنعيم

الترشيح يحتفظ باعتقاد عن الآن. وهو تعاود واحد، يُجرى تنبّؤًا ثم تحديثًا: ادفع الاعتقاد عبر نموذج الانتقال، ثم اضربه في إمكان المشاهدة الجديدة وعيّر. والاعتقاد شعاع ثابت الحجم، فيستطيع عميل أن يُجري هذا إلى الأبد.

في اليوم 1 تظهر المظلّة. ونموذج الانتقال المتناظر يترك التوزيع القبلي المنتظم عند $\langle 0.5, 0.5 \rangle$، ويعطي التحديث

$$\mathbf{P}(R_1 \mid u_1) = \alpha \langle 0.9, 0.2 \rangle \langle 0.5, 0.5 \rangle = \alpha \langle 0.45, 0.10 \rangle = \langle 0.818,\ 0.182 \rangle .$$

وفي اليوم 2 يهبط التنبّؤ إلى $\langle 0.627, 0.373 \rangle$ - فخطوة نحو المستقبل تكلّف يقينًا في هذه السلسلة - ثم ترفعه مظلّة ثانية إلى $\langle 0.883, 0.117 \rangle$.

والتنبّؤ هو التعاود نفسه من غير تحديث. تابع من غير مظلّات أخرى فيضمحلّ الاعتقاد $0.818 \to 0.627 \to 0.551 \to 0.520 \to \cdots \to 0.5$، مرتخيًا إلى التوزيع المستقرّ للسلسلة. وليس ذلك اضمحلالًا عدديًا؛ بل هو النموذج يصدُق. فالشواهد هي الشيء الوحيد الذي يُبقي الاعتقاد بعيدًا عن تلك النقطة الثابتة، ولكل متنبّئ أفقٌ لا يقول بعده شيئًا.

والتنعيم يحسّن تقديرًا سابقًا بشواهد لاحقة، بقسم الشواهد عند اللحظة التي تهمّك وإجراء تعاود ثانٍ رجوعًا. وللّيوم 1 تكون الرسالة التراجعية

$$\mathbf{P}(u_2 \mid R_1) = (0.9 \times \langle 0.7, 0.3 \rangle) + (0.2 \times \langle 0.3, 0.7 \rangle) = \langle 0.69,\ 0.41 \rangle,$$

وتركيبها مع الرسالة التقدّمية يرفع اليوم 1 من $0.818$ إلى $\langle 0.883, 0.117 \rangle$. والأثر الرجعيّ يفيد فعلًا: فمظلّة اليوم 2 تجعل المطر أرجح في اليوم 2، ولأن المطر يدوم انعكس ذلك رجوعًا. ولاحظ أن $\langle 0.69, 0.41 \rangle$ لا يبلغ مجموعه واحدًا، ولا ينبغي له - فهو إمكان لا توزيع. وتخزين المرور التقدّمي والكنس رجوعًا ينعّم متتالية كاملة في $O(t)$، وتلك هي الخوارزمية التقدّمية-التراجعية.

في ما يلي، لكل يوم عمودان لا عمود واحد: الاعتقاد بعد خطوة التنبّؤ، ثم الاعتقاد بعد خطوة التصحيح. وبذلك يصير القول إن أحد النصفين يكلّف يقينًا في هذا النموذج وإن الآخر يستردّه شكلًا في الصورة لا جملةً تُصدَّق. حرّك مؤشّر الأفق لترى أسبوعًا بلا رصد يرتخي نحو التوزيعة المستقرّة، وشغّل المرور الخلفي لترى اليوم الأول يصعد من 0.818 إلى 0.883 بفضل مظلّة لم يكن قد رآها بعد.

ج. المتتالية الأرجح سؤال مغاير

يجيب التنعيم عن «هل كانت السماء تمطر في اليوم 2؟». وسؤال «ماذا حدث؟» ليس السؤال نفسه بحبيبة أدقّ، والاختصار الطبيعي - نعّم كل خطوة وخذ الفائز عند كلٍّ منها - خاطئ.

خذ متتالية المشاهدات ذات الأيام الثلاثة لا مظلّة، مظلّة، لا مظلّة. لا يوجد إلا ثمانية تواريخ، فاسردها:

$$\begin{array}{lll} \text{dry, dry, dry} & 0.0314 & 40.2\% \\ \text{dry, rain, dry} & 0.0259 & 33.2\% \\ \text{rain, rain, dry} & 0.0076 & 9.7\% \\ \text{dry, rain, rain} & 0.0076 & 9.7\% \\ \text{rain, rain, rain} & 0.0022 & 2.8\% \\ \text{others} & & 4.4\% \end{array}$$

وتنعيم اليوم 2 يجمع كل تاريخ أمطرت فيه السماء: $0.332 + 0.097 + 0.097 + 0.028 = 0.554$، فاليوم 2 وحده أرجح أن يكون ممطرًا منه أن يكون جافًّا. لكن المتتالية الأرجح هي جافّ، جافّ، جافّ. وكلاهما صحيح. فالمطر في اليوم 2 يجمع الـ$0.554$ من أربعة تواريخ منفصلة، ليس أيّ منها قويًّا بذاته، بينما يركّز التفسير الجافّ كلّه $40.2\%$ في تفسير واحد. فالهوامش تجمع على المسارات؛ وأفضل مسار لا يفعل.

والإصلاح هو تعاود فيتربي، وهو الترشيح بتغيير واحد - إذ يصير الجمع على الحالة السابقة أعظمًا:

$$\mathbf{m}_{1:t+1} = \mathbf{P}(\mathbf{e}_{t+1} \mid \mathbf{X}_{t+1}) \max_{x_t} \Big( \mathbf{P}(\mathbf{X}_{t+1} \mid x_t)\, m_{1:t}(x_t) \Big),$$

مع مؤشّر راجع عند كل خطوة يسجّل أيّ سلف فاز، لأن الرسالة تعطي احتمال أفضل مسار لا المسار نفسه. وعلى متتالية الأيام الخمسة مظلّة، مظلّة، لا مظلّة، مظلّة، مظلّة يعيد مطر، مطر، جفاف، مطر، مطر: فمظلّة واحدة غائبة تكسر سلسلة من المطر، لكن ليس لأكثر من يوم، لأن نموذج الانتقال يجعل يومًا جافًّا معزولًا أرخص من تغيّر دائم في النظام.

د. حين تكون الحالة عددًا حقيقيًا

تتبّع موضعًا بدل رمية عملة فيصير الاعتقاد كثافة، ويصير التنبّؤ تكاملًا بلا صيغة مغلقة، وقد يتغيّر شكل الاعتقاد عند كل خطوة. وعائلة واحدة تنجو: افترض نماذج خطّية بضجيج غاوسي فتبقى الخطوتان كلتاهما غاوسيتين، لأن دفع توزيع غاوسي عبر تطبيق خطّي وإضافة ضجيج يعطي توزيعًا غاوسيًا، ولأن جداء توزيعين غاوسيين غاوسيّ. فيكون الاعتقاد عندئذ موصوفًا دائمًا بمتوسّط وتباين، مهما طال تشغيل المرشّح.

وللمسيرة العشوائية يكون التحديث

$$\mu_{t+1} = \frac{(\sigma_t^2 + \sigma_x^2) z_{t+1} + \sigma_z^2 \mu_t}{\sigma_t^2 + \sigma_x^2 + \sigma_z^2}, \qquad \sigma_{t+1}^2 = \frac{(\sigma_t^2 + \sigma_x^2)\sigma_z^2}{\sigma_t^2 + \sigma_x^2 + \sigma_z^2},$$

وهو متوسّط مرجَّح يكون فيه النصيب الأكبر من الكلام لأقلّ الاثنين - التنبّؤ والمشاهدة - لايقينًا. ومع $\mu_0 = 0$ و$\sigma_0 = 1$ و$\sigma_x = 2$ و$\sigma_z = 1$ و$z_1 = 2.5$، يكون التوزيع البعدي $\mu_1 = 2.083$ مع $\sigma_1^2 = 0.833$. فالمتوسّط يقصر عن المشاهدة لأن التنبّؤ لا يزال يحمل وزنًا، وينتهي التباين دون كلا المُدخلين، وذلك هو مقصد الترشيح أصلًا.

وتحديث التباين لا يذكر المشاهدة أبدًا. فمتتالية التباينات كلّها، ومعها كسب كالمان، يمكن حسابها قبل وصول أي بيانات؛ وهي هنا تتقارب إلى $\sigma^2 \approx 0.828$ وكسب ثابت يقارب $0.828$. وثبات التباين يعني أن المرشّح تعلّم ما يسمح به الضجيج، لا أنه توقّف: فالمتوسّط يظلّ يتحرّك.

أين يضعك هذا

فرضيّتان تحوّلان تاريخًا غير محدود إلى جدولين صغيرين. وتعاود تقدّمي واحد يجيب عمّا هو صحيح الآن، والتعاود نفسه من غير شواهد يتنبّأ إلى أن يذوب في التوزيع المستقرّ، ومرور تراجعي يشتري الأثر الرجعيّ. والتاريخ الأرجح يحتاج إلى خوارزميته الخاصّة، والسبب جدير بالتذكّر كلّما راودتك فكرة تركيب جواب من فائزين عند كل بند. ومسار التدريب الاستدلال الاحتمالي عبر الزمن يحلّ كل واحد من هذه يدويًا وبالبرمجة.