عمليات ماركوف ونماذج الاستشعار

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

الحالة والشواهد

اقسم المتغيّرات قسمين.

• $\mathbf{X}_t$ هي الحالة عند اللحظة $t$: ما هو صحيح فعلًا، وما لا تستطيع رصده.
• $\mathbf{E}_t$ هي الشواهد عند اللحظة $t$: ما تبلّغ عنه أجهزة استشعارك. والمشاهدة هي $\mathbf{E}_t = \mathbf{e}_t$.

يُقطَّع الزمن خطواتٍ ذات مقدار ثابت، فيعدّ $t$ الشرائح لا الثواني. والفترة اختيار نمذجة؛ والخوارزميات لا تعنيها.

عالَم المظلّة

مثال راسل ونورفيغ صغير عن قصد. أنت حارس أمن في منشأة تحت الأرض. تريد أن تعرف هل تمطر السماء اليوم، وصلتك الوحيدة بالعالم الخارجي أن ترى المدير يصل كل صباح بمظلّة أو من غيرها. فـ$R_t$ (مطر اليوم) هي الحالة، و$U_t$ (مظلّة اليوم) هي الشواهد، والمسألة كلّها استدلال على متغيّر مخفيّ من وكيل عنه.

$$\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}$$

اقرأ هذه الكتل الثلاث توزيعًا قبليًا ونموذج انتقال ونموذج استشعار. فالمطر يدوم: يتبع اليومَ الممطر يومٌ ممطر آخر باحتمال $0.7$. والمدير مؤشّر لا بأس به لكنه غير تامّ: يحمل المظلّة في $90\%$ من الأيام الممطرة، وفي $20\%$ من الأيام الجافّة أيضًا.

فرضيتان

التاريخ ليس محدود الطول، فـ$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}).$$

فرضية ماركوف للاستشعار. تتوقّف القراءة الراهنة على الحالة الراهنة وحدها:

$$\mathbf{P}(\mathbf{E}_t \mid \mathbf{X}_{0:t}, \mathbf{E}_{0:t-1}) = \mathbf{P}(\mathbf{E}_t \mid \mathbf{X}_t).$$

وكلتاهما دعوى عن الحالة، لا عن الفيزياء ولا عن العتاد. فإن كانت قراءة الأمس لا تزال تخبرك بشيء عن قراءة اليوم بعدما عُلمت حالة اليوم، فمتغيّر حالتك ينقصه شيء.

متى كانت الفرضية خاطئة، فوسّع الحالة. إن كان مطر اليوم يتوقّف فعلًا على اليومين السابقين، فأمامك إصلاحان. إمّا أن ترفع رتبة النموذج، فتجعل $R_t$ يتوقّف على $R_{t-1}$ و$R_{t-2}$؛ وإمّا أن تُبقيه من الرتبة الأولى وتُثري الحالة، فتضيف $\mathit{Season}_t$ أو $\mathit{Pressure}_t$ حتى تمرّ التبعيّة الزائدة عبر متغيّر لا عبر الزمن. والثاني أفضل عادةً، لأنه دعوى عن العالم لا رقعة.

ونفترض كذلك أن العملية مستقرّة: أي أن نموذجَي الانتقال والاستشعار هما نفساهما عند كل خطوة. وهذا ما يتيح لجدولين صغيرين وصف تاريخ أيّ طول كان. والاستقرار غير السكون - فالعالم يتغيّر، أما القوانين فلا.

التوزيع المشترك

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

$$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).$$

ثلاثة عوامل تصف تاريخًا أيّ طول كان، وذلك هو المكسب كلّه.

مثال محلول: احتمال تاريخ واحد

افرض أن السماء أمطرت في اليومين كليهما وأن المظلّة ظهرت فيهما كليهما. بقراءة مدخلة واحدة من كل عامل:

$$\begin{aligned} P(r_1, r_2, u_1, u_2) &= \underbrace{\textstyle\sum_{r_0} P(r_1 \mid r_0) P(r_0)}_{0.7 \times 0.5 + 0.3 \times 0.5 \,=\, 0.5} \times P(u_1 \mid r_1) \times P(r_2 \mid r_1) \times P(u_2 \mid r_2) \\ &= 0.5 \times 0.9 \times 0.7 \times 0.9 \\ &= 0.2835 . \end{aligned}$$

ولمّا كان لكل تاريخ احتمال، فلكل سؤال عن العالم جواب: اجمع التواريخ التي توافقه. وذلك صحيح ويائس في آنٍ - فعددها $2^t$. والدرس التالي في عدم تعدادها.

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

الأسئلة الأربعة

كل ما يفعله بقيّة هذا المسار يندرج في أربع مهامّ.

• الترشيح: $\mathbf{P}(\mathbf{X}_t \mid \mathbf{e}_{1:t})$، أي الاعتقاد عن الآن بمعلومية كل ما مضى. وهذا ما يحتفظ به عميل يعمل.
• التنبّؤ: $\mathbf{P}(\mathbf{X}_{t+k} \mid \mathbf{e}_{1:t})$ لأجل $k > 0$، أي الاعتقاد عن حالة مستقبلية.
• التنعيم: $\mathbf{P}(\mathbf{X}_k \mid \mathbf{e}_{1:t})$ لأجل $k < t$، أي تقدير أفضل لحالة سابقة، يُصنع بأثر رجعيّ.
• التفسير الأرجح: $\operatorname*{argmax}_{\mathbf{x}_{1:t}} P(\mathbf{x}_{1:t} \mid \mathbf{e}_{1:t})$، أي التاريخ الوحيد الذي يفسّر المشاهدات أحسن تفسير.

وتشترك الثلاثة الأولى في تعاودٍ واحد. أما الرابعة، وهذا ما يخدع، فلا.

قبل الاختبار

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