في عام 1998 ، نشرت لورانس بيج وسيرجي برين وراجيف موتواني وتيري فينوغراد مقالًا بعنوان "تصنيف ترتيب تصنيف الصفحات: ترتيب الطلب على الويب" ، الذي وصف خوارزمية تصنيف الصفحات الشهيرة الآن ، والتي أصبحت أساس Google. بعد أقل من عقدين بقليل ، أصبحت Google عملاقًا ، وعلى الرغم من أن خوارزميةها تطورت بقوة ، إلا أن PageRank لا تزال "رمزًا" لخوارزميات تصنيف Google (على الرغم من أن قلة قليلة فقط من الناس يمكنها حقًا معرفة مقدار الوزن الذي تستغرقه هذه الخوارزمية اليوم) .
من وجهة نظر نظرية ، من المثير للاهتمام أن نلاحظ أن أحد التفسيرات القياسية لخوارزمية تصنيف الصفحات يعتمد على مفهوم بسيط ولكنه أساسي لسلاسل ماركوف. من المقال سنرى أن سلاسل Markov هي أدوات فعالة لنمذجة العشوائية التي يمكن أن تكون مفيدة لأي عالم بيانات. على وجه الخصوص ، سوف نجيب على مثل هذه الأسئلة الأساسية: ما هي سلاسل ماركوف ، وما هي الخصائص الجيدة التي يمتلكونها ، وما الذي يمكن عمله بمساعدتهم؟
مراجعة قصيرة
في القسم الأول ، نقدم التعريفات الأساسية اللازمة لفهم سلاسل ماركوف. في القسم الثاني ، نعتبر الحالة الخاصة لسلاسل ماركوف في مساحة دولة محدودة. في القسم الثالث ، ندرس بعض الخصائص الأولية لسلاسل Markov ونوضح هذه الخصائص بالعديد من الأمثلة الصغيرة. أخيرًا ، في القسم الرابع ، نربط سلاسل Markov بخوارزمية PageRank ونرى بمثال مصطنع كيف يمكن استخدام سلاسل Markov لتصنيف عقد الرسم البياني.
المذكرة. يتطلب فهم هذا المنشور معرفة أساسيات الاحتمال والجبر الخطي. على وجه الخصوص ، سيتم استخدام المفاهيم التالية: الاحتمال الشرطي ، eigenvector ، وصيغة الاحتمال الكاملة .
ما هي سلاسل ماركوف؟
المتغيرات العشوائية والعمليات العشوائية
قبل تقديم مفهوم سلاسل ماركوف ، دعونا نتذكر بإيجاز المفاهيم الأساسية ، ولكن المهمة لنظرية الاحتمالات.
أولاً ، خارج لغة الرياضيات ،
المتغير العشوائي X هو الكمية التي تحددها نتيجة لظاهرة عشوائية. قد تكون النتيجة رقم (أو "تشابه رقم" ، على سبيل المثال ، ناقلات) أو أي شيء آخر. على سبيل المثال ، يمكننا تعريف المتغير العشوائي كنتيجة لفافة يموت (رقم) أو كنتيجة لإرتكاب عملة معدنية (ليس رقمًا ، ما لم نعين ، على سبيل المثال ، "النسر" كـ 0 ، ولكن "ذيول" كـ 1). نذكر أيضًا أن مساحة النتائج المحتملة لمتغير عشوائي يمكن أن تكون منفصلة أو مستمرة: على سبيل المثال ، متغير عشوائي عادي مستمر ، ومتغير Poisson العشوائي منفصل.
علاوة على ذلك ، يمكننا تعريف
عملية عشوائية (تسمى أيضًا stochastic) على أنها مجموعة من المتغيرات العشوائية المفهرسة بالمجموعة T ، والتي تشير غالبًا إلى نقاط مختلفة في الوقت (في ما يلي سوف نفترض هذا). الحالتان الأكثر شيوعًا: يمكن أن تكون T عبارة عن مجموعة من الأرقام الطبيعية (عملية عشوائية مع وقت منفصل) ، أو مجموعة من الأرقام الحقيقية (عملية عشوائية مع وقت مستمر). على سبيل المثال ، إذا ألقينا عملة معدنية كل يوم ، فسنقوم بتعيين عملية عشوائية مع وقت منفصل ، وستحدد القيمة المتغيرة دائمًا لخيار ما في البورصة عملية عشوائية مع وقت مستمر. يمكن أن تكون المتغيرات العشوائية في نقاط زمنية مختلفة مستقلة عن بعضها البعض (مثال مع إرم عملة معدنية) ، أو يكون لها نوع من التبعية (مثال مع قيمة الخيار) ؛ بالإضافة إلى ذلك ، يمكن أن يكون لديهم مساحة حالة مستمرة أو منفصلة (مساحة النتائج المحتملة في كل لحظة من الزمن).
أنواع مختلفة من العمليات العشوائية (منفصلة / مستمرة في الفضاء / الوقت).ماركوف الملكية وسلسلة ماركوف
هناك عائلات معروفة من العمليات العشوائية: العمليات الغوسية ، عمليات بواسون ، نماذج الانحدار الذاتي ، نماذج المتوسط المتحرك ، سلاسل ماركوف ، وغيرها. كل حالة من هذه الحالات الفردية لها خصائص معينة تسمح لنا باستكشافها وفهمها بشكل أفضل.
واحدة من الخصائص التي تبسط إلى حد كبير دراسة عملية عشوائية هي خاصية Markov. إذا شرحناها بلغة غير رسمية للغاية ، فإن خاصية Markov تخبرنا أنه إذا علمنا القيمة التي حصلت عليها بعض العمليات العشوائية في وقت معين من الوقت ، فلن نتلقى أي معلومات إضافية حول السلوك المستقبلي للعملية ، وجمع معلومات أخرى حول ماضيها. بلغة رياضية أكثر: في أي وقت من الأوقات ، يعتمد التوزيع المشروط للحالات المستقبلية لعملية ما مع حالات سابقة وحالية معينة على الحالة الحالية فقط ، وليس على الحالات السابقة (
خاصية نقص الذاكرة ). عملية عشوائية مع خاصية Markov تسمى
عملية Markov .
تعني خاصية Markov أننا إذا كنا نعرف الحالة الحالية في وقت معين من الوقت ، فلن نحتاج إلى أي معلومات إضافية حول المستقبل ، تم جمعها من الماضي.بناءً على هذا التعريف ، يمكننا صياغة تعريف "سلاسل Markov المتجانسة ذات الوقت المنفصل" (يشار إليها فيما يلي بالبساطة ، وسنسميها "سلاسل Markov").
سلسلة Markov هي عملية Markov مع وقت منفصل ومساحة منفصلة للدولة. لذلك ، سلسلة Markov هي سلسلة منفصلة من الحالات ، كل منها مأخوذة من مساحة دولة منفصلة (محددة أو غير محدودة) ، ترضي خاصية Markov.
رياضيا ، يمكننا أن نشير إلى سلسلة ماركوف على النحو التالي:
حيث تأخذ العملية في كل لحظة من الزمن قيمها من مجموعة منفصلة E ، مثل هذه
ثم تشير خاصية Markov إلى أن لدينا
لاحظ مرة أخرى أن هذه الصيغة الأخيرة تعكس حقيقة أنه بالنسبة للتسلسل الزمني (أين أنا الآن والمكان الذي كنت فيه من قبل) ، يعتمد توزيع احتمال الحالة التالية (حيث سأكون التالي) على الحالة الحالية ، ولكن ليس على الحالات السابقة.
المذكرة. في هذا المقال التمهيدي ، قررنا التحدث فقط عن سلاسل ماركوف البسيطة المتجانسة مع وقت منفصل. ومع ذلك ، هناك أيضًا سلاسل ماركوف غير متجانسة (معتمدة على الوقت) و / أو سلاسل زمنية مستمرة. في هذه المقالة ، لن نفكر في هذه الاختلافات في النموذج. تجدر الإشارة أيضًا إلى أن التعريف المذكور أعلاه لخاصية Markov مبسط للغاية: يستخدم التعريف الرياضي الحقيقي مفهوم التصفية الذي يتجاوز بكثير معرفتنا التمهيدية بالنموذج.
نحن نميز ديناميات العشوائية لسلسلة ماركوف
في القسم الفرعي السابق ، تعرفنا على الهيكل العام المقابل لأي سلسلة من ماركوف. دعونا نرى ما نحتاج إليه لتعيين "مثيل" محدد لهذه العملية العشوائية.
أولاً ، نلاحظ أن التحديد الكامل لخصائص العملية العشوائية مع وقت منفصل لا يلبي خاصية Markov يمكن أن يكون أمرًا صعبًا: قد يعتمد توزيع الاحتمالات في وقت معين على لحظة واحدة أو أكثر في الماضي و / أو المستقبل. كل هذه التبعيات الزمنية الممكنة يمكن أن تعقد إنشاء تعريف للعملية.
ومع ذلك ، بسبب خاصية Markov ، فإن ديناميات سلسلة Markov بسيطة للغاية. وبالفعل نحتاج إلى تحديد جانبين فقط:
توزيع الاحتمال الأولي (بمعنى ، توزيع الاحتمالات في الوقت n = 0) ، يُشار إليه بـ
مصفوفة احتمالية الانتقال (والتي تعطينا الاحتمالات بأن الحالة في الوقت n + 1 هي الحالة التالية لحالة أخرى في الوقت n لأي زوج من الحالات) ،
إذا كان هذان الجانبان معروفين ، فإن ديناميكيات (الاحتمالية) الكاملة للعملية محددة بوضوح. وفي الواقع ، يمكن بعد ذلك حساب احتمال أي نتيجة للعملية بشكل دوري.
مثال: افترض أننا نريد أن نعرف احتمال أن يكون للحالات الثلاث الأولى من العملية قيم (s0 ، s1 ، s2). وهذا هو ، نريد حساب الاحتمال
نطبق هنا صيغة الاحتمال الكلي ، التي تنص على أن احتمال الحصول على (s0 ، s1 ، s2) يساوي احتمال الحصول على s0 أول مرة من احتمال الحصول على s1 ، نظرًا لأننا سبق أن حصلنا على s0 أضعاف احتمال الحصول على s2 مع الأخذ في الاعتبار حقيقة أن وصلنا في وقت سابق من أجل s0 و s1. رياضيا ، يمكن كتابة هذا باسم
ثم يتم الكشف عن التبسيط ، الذي يحدده افتراض ماركوف. وفي الواقع ، في حالة السلاسل الطويلة ، نحصل على احتمالات مشروطة بشدة للحالات الأخيرة. ومع ذلك ، في حالة سلاسل Markov ، يمكننا تبسيط هذا التعبير من خلال الاستفادة من حقيقة ذلك
الحصول على هذا الطريق
نظرًا لأنها تميز الديناميات الاحتمالية للعملية تمامًا ، يمكن حساب العديد من الأحداث المعقدة فقط على أساس توزيع الاحتمال الأولي q0 ومصفوفة احتمال الانتقال p. تجدر الإشارة أيضًا إلى وصلة أساسية أخرى: التعبير عن توزيع الاحتمالات في الوقت n + 1 ، معبراً عنه فيما يتعلق بتوزيع الاحتمالات في الوقت n
سلاسل ماركوف في المساحات المحدودة للدولة
مصفوفة وتمثيل الرسم البياني
نفترض هنا أن المجموعة E بها عدد محدود من الحالات المحتملة N:
بعد ذلك ، يمكن وصف توزيع الاحتمال الأولي بأنه
متجه صف q0 بالحجم N ، ويمكن وصف احتمالات الانتقال بأنها مصفوفة p بالحجم N بواسطة N ،
تكمن ميزة هذا الترميز في أنه إذا قمنا بالإشارة إلى توزيع الاحتمال في الخطوة n بواسطة ناقل الخطوط qn بحيث يتم تحديد مكوناته
ثم يتم الحفاظ على العلاقات مصفوفة بسيطة
(هنا لن نفكر في الدليل ، لكن من السهل جدًا إعادة إنتاجه).
إذا قمنا بضرب متجه الصف على اليمين ، والذي يصف توزيع الاحتمال في مرحلة زمنية معينة ، بمصفوفة احتمالية الانتقال ، فسنحصل على توزيع الاحتمال في المرحلة التالية.لذلك ، كما نرى ، فإن انتقال توزيع الاحتمالات من مرحلة معينة إلى المرحلة التالية يتم تعريفه ببساطة على أنه الضرب الصحيح لمتجه صف صف احتمالات الخطوة الأولية بواسطة المصفوفة p. بالإضافة إلى ذلك ، هذا يعني أن لدينا
يمكن تمثيل ديناميكيات العشوائية لسلسلة Markov في مساحة حالة محدودة كرسومات بيانية موجهة طبيعية بحيث تكون كل عقدة من الرسم البياني حالة ، ولكل زوج من الحالات (ei ، ej) توجد حافة تنتقل من ei إلى ej إذا كانت p (ei، ej) )> 0. ثم ستكون قيمة الحافة هي نفس الاحتمال p (ei ، ej).
مثال: قارئ موقعنا
دعونا توضيح كل هذا مع مثال بسيط. النظر في السلوك اليومي للزائر وهمية إلى الموقع. كل يوم لديه 3 حالات ممكنة: القارئ لا يزور الموقع في ذلك اليوم (N) ، القارئ يزور الموقع ، لكنه لا يقرأ المنشور بالكامل (V) ، والقارئ يزور الموقع ويقرأ منشورًا كاملاً (R). لذلك ، لدينا مساحة الدولة التالية:
لنفترض ، في اليوم الأول ، أن هذا القارئ لديه فرصة بنسبة 50٪ للوصول إلى الموقع فقط وفرصة بنسبة 50٪ بزيارة الموقع وقراءة مقال واحد على الأقل. المتجه الذي يصف توزيع الاحتمال الأولي (ن = 0) ثم يبدو كما يلي:
تخيل أيضًا أنه يتم ملاحظة الاحتمالات التالية:
- عندما لا يزور القارئ يومًا ما ، يكون هناك احتمال بنسبة 25٪ بعدم زيارته في اليوم التالي ، واحتمال بنسبة 50٪ فقط لزيارته و 25٪ لزيارته وقراءة المقال
- عندما يزور القارئ الموقع في يوم من الأيام ، لكنه لا يقرأ ، فإن لديه فرصة بنسبة 50 ٪ لزيارته مرة أخرى في اليوم التالي وعدم قراءة المقال ، وفرصة بنسبة 50 ٪ للزيارة والقراءة
- عندما يزور القارئ ويقرأ مقالة في نفس اليوم ، فهناك فرصة بنسبة 33 ٪ لعدم تسجيل الدخول في اليوم التالي (آمل ألا يكون لهذا المنشور مثل هذا التأثير!) ، وفرصة بنسبة 33 ٪ فقط لتسجيل الدخول إلى الموقع و 34 ٪ من زيارة المقال وقراءته مرة أخرى
ثم لدينا مصفوفة الانتقال التالية:
من القسم الفرعي السابق ، نعلم كيف نحسب لهذا القارئ احتمال كل ولاية في اليوم التالي (ن = 1)
يمكن تمثيل الديناميات الاحتمالية لسلسلة ماركوف بيانيا على النحو التالي:
عرض تقديمي على شكل رسم بياني لسلسلة ماركوف ، يصور سلوك الزائر المبتكر للموقع.خصائص سلاسل ماركوف
في هذا القسم ، سنتحدث فقط عن بعض الخصائص أو الخصائص الأساسية لسلاسل Markov. لن ندخل في التفاصيل الرياضية ، لكننا سنقدم نظرة عامة مختصرة على النقاط المهمة التي يجب دراستها لاستخدام سلاسل Markov. كما رأينا ، في حالة مساحة الدولة المحدودة ، يمكن تمثيل سلسلة ماركوف كرسم بياني. في المستقبل ، سوف نستخدم التمثيل الرسومي لشرح بعض الخصائص. ومع ذلك ، لا تنس أن هذه الخصائص لا تقتصر بالضرورة على حالة مساحة الدولة المحدودة.
التحلل ، الدورية ، لا رجعة فيه ، والاسترداد
في هذا القسم الفرعي ، لنبدأ بالعديد من الطرق الكلاسيكية لتمييز حالة أو سلسلة ماركوف بأكملها.
أولاً ، نذكر أن سلسلة Markov غير
قابلة للتحلل إذا كان من الممكن الوصول إلى أي ولاية من أي دولة أخرى (ليس من الضروري ذلك في خطوة واحدة من الزمن). إذا كانت مساحة الولاية محدودة ويمكن تمثيل السلسلة كرسم بياني ، فيمكننا القول إن الرسم البياني لسلسلة ماركوف غير القابل للانحلال مرتبط بشدة (نظرية الرسم البياني).
شكل توضيحي لخاصية عدم التعرض (عدم الاختزال). لا يمكن تقصير السلسلة الموجودة على اليسار: من 3 أو 4 لا يمكننا الدخول إلى 1 أو 2. يمكن تقصير السلسلة الموجودة على اليمين (تتم إضافة حافة واحدة): يمكن الوصول إلى كل ولاية من أي دولة أخرى.يكون للولاية فترة k إذا ، عند مغادرتها ، بالنسبة لأي عودة إلى هذه الحالة ، يكون عدد خطوات الوقت هو مضاعف k (k هو أكبر مقسوم مشترك لجميع أطوال مسارات العودة الممكنة). إذا كانت k = 1 ، فيقولون أن الحالة غير دورية ، وأن سلسلة Markov بأكملها تكون غير
دورية إذا كانت جميع حالاتها غير دورية. في حالة سلسلة ماركوف غير القابلة للاختزال ، يمكننا أن نذكر أيضًا أنه إذا كانت إحدى الحالات غير فعالة ، فإن كل الحالات الأخرى تكون أيضًا غير دورية.
شكل توضيحي للخاصية الدورية. تكون السلسلة على اليسار دورية بعلامة k = 2: عند مغادرة أي ولاية ، فإن الرجوع إليها يتطلب دائمًا عدد الخطوات مضاعفة 2. السلسلة على اليمين لها فترة 3.لا يمكن
التراجع عن الحالة إذا كان هناك احتمال غير صفري عند مغادرة الولاية ، ألا نعود إليها أبدًا. بالمقابل ، تعتبر الدولة
قابلة للإرجاع إذا علمنا أنه بعد مغادرة الولاية ، يمكننا العودة إليها في المستقبل بالاحتمال 1 (إذا لم تكن قابلة للإلغاء).
شكل توضيحي لخاصية الإرجاع / عدم الرجوع. تحتوي السلسلة الموجودة على اليسار على الخصائص التالية: 1 و 2 و 3 غير قابلة للإلغاء (عند مغادرة هذه النقاط ، لا يمكننا أن نكون متأكدين تمامًا من أننا سنعود إليها) ولدينا فترة 3 و 4 و 5 قابلة للإرجاع (عند مغادرة هذه النقاط ، نحن متأكدون تمامًا في يوم من الأيام سوف نعود إليهم) ولدينا فترة 2. السلسلة على اليمين بها ضلع آخر ، مما يجعل السلسلة بأكملها قابلة للإرجاع وفترة زمنية غير منتظمة.بالنسبة لحالة العودة ، يمكننا حساب متوسط وقت العودة ، وهو
وقت العودة المتوقع عند مغادرة الولاية. لاحظ أنه حتى احتمال العائد هو 1 ، هذا لا يعني أن وقت الإرجاع المتوقع محدود. لذلك ، من بين جميع حالات العودة ، يمكننا التمييز بين
حالات العودة الإيجابية (مع وقت عودة متوقع محدد) وحالات
عودة صفر (مع وقت عودة غير محدود متوقع).
التوزيع الثابت ، والسلوكيات الهامشية والرجولية
في هذا القسم الفرعي ، ننظر في الخصائص التي تميز بعض جوانب الديناميات (العشوائية) الموصوفة في سلسلة ماركوف.
يسمى توزيع الاحتمال π على مساحة الدولة E
التوزيع الثابت إذا كان يرضي التعبير
منذ أن لدينا
ثم التوزيع الثابت يرضي التعبير
بحكم التعريف ، توزيع الاحتمالات الثابتة لا يتغير مع مرور الوقت. أي إذا كان التوزيع الأولي q ثابتًا ، فسيكون هو نفسه في جميع المراحل اللاحقة من الوقت. إذا كانت مساحة الحالة محدودة ، فيمكن تمثيل p كمصفوفة ، و π كمتجه للصف ، ثم نحصل على
يعبر هذا مرة أخرى عن حقيقة أن توزيع الاحتمال الثابت لا يتغير مع مرور الوقت (كما نرى ، فإن مضاعفة توزيع الاحتمالات على اليمين بواسطة p يسمح لنا بحساب توزيع الاحتمالات في المرحلة التالية من الوقت). ضع في اعتبارك أن سلسلة Markov التي لا يمكن تعويضها لها توزيع احتمالي ثابت إذا وفقط إذا كانت إحدى حالاتها ذات عائد إيجابي.
خاصية أخرى مثيرة للاهتمام تتعلق بتوزيع الاحتمالات الثابتة هي على النحو التالي. إذا كانت السلسلة ذات عائد إيجابي (أي أن هناك توزيعًا ثابتًا فيها) وفترة غير منتظمة ، فبغض النظر عن الاحتمالات الأولية ، يتقارب توزيع احتمالية السلسلة حيث تميل الفواصل الزمنية إلى ما لا نهاية: يقولون إن السلسلة لها
توزيع محدود ، وهذا ليس شيئًا آخر ، كتوزيع ثابت. بشكل عام ، يمكن كتابتها مثل هذا:
, : ( ) .
,
— , . , , «», . , f(.), E ( , , ). , ( ). n-
f E, ( ),
, , ( ). :
, , .
. , , .
, , R ( « »). , : , , ? , .
, m(R,R). , R,
, m(R,R) m(N,R) m(V,R). :
, 3 3 m(N,R) = 2.67, m(V,R) = 2.00 m(R,R) = 2.54. R 2.54. R ( N R V R).
, , . , :
p, 1. , :
., π( R ) = 1/m(R,R), , ( ).
, , ( ). , , , π(N) , , π(V) , , , π® , . , , , () :
3 (, ) ().: PageRank
PageRank! , , PageRank, , , . , .
-
PageRank : ( , , , - ) ?
, PageRank . , . , , (, , , ). .
: — , ( , ), . , ( ), « » . , ( ) , .
PageRank : ( , , ). PageRank.
, . , - 7 , 1 7, .
. , «» ( « »), : K ( K ) 1/K. :
0.0 ".". , , , . , ,
من خلال القيام بذلك ، نحصل على قيم PageRank التالية (قيم التوزيع الثابتة) لكل صفحةقيم تصنيف الصفحات المحسوبة على سبيل المثال لدينا من 7 صفحات.ثم ترتيب PageRank لهذا الموقع الصغير هو 1> 7> 4> 2> 5 = 6> 3.
النتائج
النتائج الرئيسية لهذا المقال:- العمليات العشوائية عبارة عن مجموعات من المتغيرات العشوائية التي يتم فهرستها غالبًا بمرور الوقت (تشير المؤشرات غالبًا إلى وقت منفصل أو مستمر)
- بالنسبة لعملية عشوائية ، تعني خاصية Markov أنه بالنسبة لتيار معين ، لا يعتمد احتمال المستقبل على الماضي (تسمى هذه الخاصية أيضًا "نقص الذاكرة")
- سلسلة Markov المنفصلة هي عمليات عشوائية مع مؤشرات زمنية منفصلة ترضي خاصية Markov
- ( , …)
- PageRank ( ) -, ; ( , , , )
, , . , , ( , , ), ( - ), ( ), ( ), .
, , , , . , , .