التقنية

أبرز الاستخدامات الرائعة لنظرية سلسلة ماركوف

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

حسناً! … توقف لحظة ودعني أشرح لك قليلاً:

تقوم نظرية سلسة ماركوف على (المفهوم الغموض) أي أنك لن تحتاج فهم النظرية بالتفصيل لكي تتمكن من الاستفادة منها؛ ولكن يمكنك أن تستفيد منها عن طريق فهم كيفية عملها، والتي تتميز بأنها بسيطة ومفيدة في مجالات متعددة.

لذلك نقدم لكم هنا شرح بسيط ومكثف – يحتوي على كل ما تحتاج معرفته حول سلسلة ماركوف، وصولاً إلى المرحلة التي تصبح النظرية فيها بسيطة قابلة للفهم. وإن أردت أن تتعمق أكثر، يتوافر منهاج نظرية المعلومات المجاني في أكاديمية خان، (بالإضافة إلى عدة مواقع على الإنترنت أيضاً).

سلسلة ماركوف 101

كمقدمة سريعة نسألكم من هو ماركوف؟

ماركوف هو رياضي روسي، وصل إلى فكرة مفادها، أن حالة معينة (معرفة الطقس في الماضي) تقود مباشرة إلى حالة أخرى (معرف طقس الغد) معتمدة على احتمالية معينة، حيث لا تؤثر عوامل أخرى على الحالة الانتقالية. وهو من قام باختراع السلسلة والتي سميت لاحقاً باسمه.

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

في البداية ستخوض في المئات أو حتى الآلاف من المتحولات المختلفة والتي تتغير بشكل مستمر، حيث أن نظام الطقس يتسم بالتعقيد الشديد فمن المستحيل وضعه في سياقٍ محدد، على الأقل بالنسبة لنا نحن الأشخاص العلميين. ولكن يمكن تبسيط المشكلة عبر استعمال نظرية الاحتمالات.

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

ولكي نحصل على نتائج جيدة ودقيقة علينا أن نكون دقيقين جداً بتسجيل الملاحظات. وبالتالي فمن الأفضل القيام بتحليل بيانات كل ساعة بدلاً من كل يوم. ولكن هذا مجرد مثال توضيحي عن المفهوم ومن المستحيل القيام به، حسناً… فلنقل أنك تقوم بهذه الدراسة لمعلومات تعود لأكثر من 30 سنة (أي أنها ستقترب من 11000 يوم) وتقوم بحساب احتمالات الطقس ليوم الغد معتمداً على حالة الطقس لهذا اليوم. مثال، إذا كان اليوم مشمساً:

  • 50% فرصة أن يكون يوم الغد مشمس أيضاً.
  • 30% فرصة أن يكون يوم الغد غائم.
  • 20% فرصة أن يكون يوم الغد ممطراً.

الآن كرر هذا لكل حالة ممكنة للطقس. إذا كان اليوم غائم، ما هي فرصة أن يكون يوم غد مشمس، ممطر، ضباب، عواصف رعدية، عواصف برد، أعاصير ….. الخ؟ وخلال فترة قصيرة، سيتشكل لديك نظام كامل من الاحتمالات التي تمكنك من التنبؤ ليس فقط عن طقس الغد، ولكن طقس اليوم الذي يليه، والذي يليه، انطلاقاً فقط من طقس اليوم وطقس كل يوم الثلاثين سنة الماضية.

الحالة الانتقالية 

حسناً! هذا هو جوهر سلسلة ماركوف.

لديك حالة فردية (تغيرات الطقس في هذه الحالة) حيث كل حالة ممكن أن تنتقل إلى حالة أخرى (على سبيل المثال الأيام المشمسة ممكن أن تنتقل إلى أيام غائمة) وهذه الانتقالات تستند على الاحتمالات. فإذا أردت أن تتنبأ كيف هي حالة الطقس لأسبوع، يمكنك أن تستكشف الاحتمالات المختلفة على مدى سبعة أيام، وتقارن التشابه بينها لتحدد أيها الأكثر تشابهاً. وهذا ما يعرف بسلسلة ماركوف.

كيف استُخدِمَتْ سلسلة ماركوف في العالم الحقيقي

إذا أردنا أن نتوسع بالشرح لنقوم بالكشف عن بعض التطبيقات من الواقع والتي هي في متناول اليد. سوف تتفاجأ أنك كنت تستخدم سلسلة ماركوف كل الوقت من دون أن تعلم بذلك! ومنها نذكر الأمثلة التالية:

انشاء اسم من العدم

هل شاركت يوماً في لعبة الطاولة، ألعاب الفيديو والميديا، أو حتى كتابة رواية؟ سوف تتعذب بتسمية شخصياتك (على الأقل في مرحلة ما) – وصولاً إلى اللحظة التي لا تتمكن فيها التفكير بالاسم الذي تريد، غالباً ما تلجأ إلى اختيار اسم من الانترنت.-

هل تساءلت يوماً كيف تعمل محركات البحث عن هذه الأسماء؟ كما تبين، تستخدم الكثير من محركات البحث سلسلة ماركوف، لتكون واحدة من أكثر الحلول المستعملة. (بالإضافة إلى وجود خوارزميات أخرى وهي فعالة تماماً).

كل ما تحتاج إليه هو مجموعة من الأحرف حيث كل حرف لديه قائمة من الأحرف المتتابعة المحتملة مترافقة مع عدة ترجيحات. لذلك وكمثال، الحرف M لديه فرصة 60% أن يقود إلى الحرف A، والحرف A لديه فرصة 40% بأن يقود إلى الحرف I. كرر العملية على جميع الأحرف، ثم شغل الخوارزمية. للمفاجأة سينتج لديك في أغلب الأحيان اسم منطقي.

تصنيف صفحة غوغل

يعتبر ازدياد طول السلسة من الأثار الممتعة لنظرية “ماركوف”، (وهذا يدل على ازدياد حالات الانتقال) ويرسو الاحتمال على حالة معينة تتلاقى مع عدد ثابت، وهذه الاحتمالية مستقلة عن المكان الذي بدأت منه النظام.

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

markov-chain-example-google-pagerank

حقوق الصورة تعود لـ: 345Kai via Wikimedia

وتقوم غوغل بتصنيف صفحاتها بناءً على هذه الأسس. إن نظرية تصنيف الصفحات قد تم تعديلها بالفعل من نظرية سلسلة ماركوف. (يمكنك مطالعة المستوى المتقدم).

وكلما زادت احتمالية الوصول إلى صفحة الويب المحددة، سيعلو ترتيبها بين الصفحات. وذلك نتيجة لتكرار طلب الصفحة من معظم الصفحات الأخرى مما يجعلها الاحتمال الثابت الأعلى – ويفترض “جوجل” أن الصفحة الأكثر قيمة هي الصفحة التي يأتيها روابط من الصفحات الأخرى بشكل كبير، أي كلما زادت الروابط زادت قيمة الصفحة.

وبالطبع، إنها عملية منطقية ولكن أكثر تعقيداً من ذلك. لماذا موقع مثل “About.com” يملك الأفضلية الأعلى في نتائج صفحات البحث؟ اتضح أن المستخدمين يميلون للوصول إلى هذه الصفحة أثناء بحثهم في مواقع الويب. هل أثار ذلك اهتمامك؟

التنبؤ بكتابة الكلمة

تمتلك الهواتف النقالة خاصية التنبؤ للكلمات منذ عقود، ولكن هل تستطيع أن تحزر كيف صنعت هذه التنبؤات؟ إذا كنت تستعمل نظام “الأندرويد” (خيارات لوحة المفاتيح البديلة) أو نظام “IOS” (خيارات لوحة المفاتيح البديلة)، حيث أنه من المرجح أن يستخدم التطبيق سلسلة ماركوف.

ولهذا، تسأل تطبيقات لوحة المفاتيح إن كان بمقدورهم تجميع المعلومات خلال ممارستك لعادة الطباعة عليها. وكمثال على ذلك، يوجد في لوحة مفاتيح “جوجل” خاصية تدعى مشاركة القصاصات، والتي تطلب بأن “تشارك القصاصات التي تقوم بطباعتها على تطبيقات ’جوجل‘ وذلك بهدف تحسين لوحة مفاتيح ’جوجل‘”. حيث يتم تحليل الكلمات ودمجها بالمضمون إلى داخل احتمالات تطبيقات سلسلة ماركوف.

وهذا أحد الأسباب وراء طرح التطبيقات لثلاثة احتمالات أو أكثر، ويتم عادةً ترتيب الاحتمالات بشكل تنازلي. حيث أنها لا تستطيع أن تتأكد من الكلمة المراد طباعتها، ولكنها تقوم بإعطاء الاحتمال الصحيح بمعظم الأوقات.

 Subreddit Simulation

نحن ننصحك بمشاهدة هذه التجربة الرائعة التي تسمى/r/SubredditSimulator.

يضم “Subreddit Simulator” الجز الأضخم من التعليقات والعناوين من مجالات “Reddit” العديدة، وببساطة قم بإدخال وتحليل كل كلمة من كل جملة. لكي تستطيع عن طريق هذه البيانات إنتاج احتمالات، ومن ثم استخدام هذه الاحتمالات لإنتاج عناوين وتعليقات من لا شيء.

markov-chain-example-subreddit-simulator

وتصنف أغلب التعليقات والعناوين في هذه التجربة من قبل المجالات الذي أتت منه البيانات في المقام الأول، وهذا من الأشياء المثيرة للاهتمام في هذه التجربة، حيث تعتبر نوع التعليقات والعناوين من مجموعة بيانات الطعام /r/ مختلفة بشكل كبير عن مجموعة بيانات كرة القدم /r/. ويعتبر الجزء الطريف والرائع، أو لربما أكثر ما يقلق بالتجربة، أنه لا يمكن التمييز بين التعليقات والعناوين التي أُنتجت، عن تلك التي يقولها الأشخاص في الحقيقة.

هل تعلم أي من الاستخدامات الرائعة لسلسلة ماركوف؟ هل لديك سؤال لم نقم بالإجابة عنه؟

أخبرنا عن طريق التعليقات بالأسفل.

أبرز الاستخدامات الرائعة لنظرية سلسلة ماركوف
Click to comment

Leave a Reply

لن يتم نشر عنوان بريدك الإلكتروني.

الأكثر شعبية

To Top