استخدام حدسي لطرق مونت كارلو مع سلاسل ماركوف

هل هو سهل؟ لقد حاولت

قام أليكسي كوزمين ، مدير تطوير البيانات والعمل في DomKlik ، وهو محاضر في علوم البيانات في Netology ، بترجمة مقال بقلم Rahul Agarwal حول كيفية عمل طرق Monte Carlo مع سلاسل Markov لحل المشكلات المتعلقة بمساحة الدولة الكبيرة.

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

لكن من الصعب فهم MCMC. في كل مرة أقرأ فيها عن هذه الطرق ، لاحظت أن جوهر MCMC مخفي في الطبقات العميقة للضوضاء الرياضية ، ومن الصعب التعرّف على هذا الضجيج. اضطررت لقضاء ساعات طويلة في فهم هذا المفهوم.

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

لذلك دعونا نبدأ. تتكون MCMC من فترتين: سلاسل مونت كارلو وماركوف. دعنا نتحدث عن كل منهم.

مونتي كارلو

في أبسط المصطلحات ، يمكن تعريف طرق مونت كارلو بأنها محاكاة بسيطة.

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

سلاسل ماركوف

نظرًا لأن مصطلح MCMC يتكون من جزأين ، فلا تزال بحاجة إلى فهم سلاسل سلاسل Markov . ولكن قبل الانتقال إلى سلاسل Markov ، دعنا نتحدث قليلاً عن خصائص Markov.

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

تشير خاصية Markov إلى أنه بالنسبة لعملية معينة تكون في الحالة X _n في لحظة معينة من الزمن ، فإن الاحتمال X _{n + 1} = k (حيث k هو أي من الحالات M التي يمكن أن تذهب إليها العملية) يعتمد فقط على ما هو هذا الشرط في الوقت الراهن. وليس حول كيفية وصولها إلى حالتها الحالية.
من الناحية الرياضية ، يمكننا كتابة هذا في شكل الصيغة التالية:

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

عملية تسمى خاصية Markov تسمى عملية Markov. لماذا تعتبر سلسلة ماركوف مهمة؟ بسبب توزيعها الثابت.

ما هو التوزيع الثابت؟

سأحاول شرح التوزيع الثابت عن طريق حسابه للمثال أدناه. افترض أن لديك عملية Markov لسوق الأوراق المالية ، كما هو موضح أدناه.

لديك مصفوفة احتمالية انتقال تحدد احتمال الانتقال من الحالة X _i إلى X _j .

مصفوفة احتمال الانتقال ، Q

في مصفوفة الاحتمال العابر Q ، يكون احتمال أن تكون الحالة التالية "ثور" ، بالنظر إلى الحالة الحالية لـ "bull" = 0.9 ؛ احتمال أن تكون الحالة التالية "هبوطية" إذا كانت الحالة الحالية "ثور" = 0.075. و هكذا.

حسنًا ، لنبدأ مع حالة معينة. سيتم تعيين حالتنا بواسطة المتجه [الثور ، الدب ، الركود]. إذا بدأنا بحالة "هبوطية" ، فسيكون المتجه مثل هذا: [0،1،0]. يمكننا حساب توزيع الاحتمالات للحالة التالية عن طريق ضرب متجه الحالة الحالي بمصفوفة احتمال الانتقال.

لاحظ أن الاحتمالات تضيف ما يصل إلى 1.

يمكن العثور على التوزيع التالي للحالات بواسطة الصيغة:


و هكذا. في النهاية ، ستصل إلى حالة ثابتة تستقر فيها الدولة:


بالنسبة لمصفوفة احتمال الانتقال Q الموصوفة أعلاه ، يكون التوزيع الثابت s هو

يمكنك الحصول على توزيع ثابت بالشفرة التالية:

Q = np.matrix([[0.9,0.075,0.025],[0.15,0.8,0.05],[0.25,0.25,0.5]]) init_s = np.matrix([[0, 1 , 0]]) epsilon =1 while epsilon>10e-9:    next_s = np.dot(init_s,Q)    epsilon = np.sqrt(np.sum(np.square(next_s - init_s)))    init_s = next_s print(init_s) ------------------------------------------------------------------ matrix([[0.62499998, 0.31250002, 0.0625  ]]) 

يمكنك أيضًا البدء من أي دولة أخرى - تحقيق نفس التوزيع الثابت. قم بتغيير الحالة الأولية في الكود إذا كنت تريد التأكد من ذلك.

يمكننا الآن الإجابة على سؤال حول سبب أهمية التوزيع الثابت.

التوزيع الثابت مهم لأنه يمكن استخدامه لتحديد احتمال وجود نظام في حالة معينة بشكل عشوائي.

على سبيل المثال ، يمكننا القول أنه في 62.5٪ من الحالات ، سيكون السوق في حالة "صعودية" ، و 31.25٪ في حالة "هبوطية" و 6.25٪ في حالة ركود.

حدسي ، يمكنك أن ترى هذا كأنه يتجول بشكل عشوائي حول السلسلة.


المشي عشوائي

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

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

الآن ننتقل مباشرة إلى النظر في أساليب MCMC.

ما هي طرق مونت كارلو مع سلاسل ماركوف (MCMC)

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


فكر ...

تتيح لك MCMC الاختيار من بين أي توزيع احتمالي. هذا مهم بشكل خاص عندما تحتاج إلى اختيار من التوزيع الخلفي.

يوضح الشكل نظرية بايز.

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

افترض أن H تأخذ فقط 3 قيم:

p (D) = p (H = H1) .p (D | H = H1) + p (H = H2) .p (D | H = H2) + p (H = H3) .p (D | H = H3)

في هذه الحالة ، يسهل حساب p (D). ولكن ماذا لو كانت قيمة H مستمرة؟ هل سيكون من الممكن حساب ذلك بسهولة ، خاصة إذا أخذ H القيم اللانهائية؟ للقيام بذلك ، لا بد من حل متكامل لا يتجزأ.

نريد أن نجعل اختيار عشوائي من التوزيع الخلفي ، ولكن نريد أيضًا اعتبار p (D) ثابتًا.

ويكيبيديا كتب ما يلي :

أساليب مونت كارلو مع سلاسل ماركوف هي فئة من الخوارزميات لأخذ العينات من توزيع الاحتمالات ، بناءً على بناء سلسلة ماركوف ، والتي يكون للتوزيع الثابت الشكل المطلوب. ثم يتم استخدام حالة السلسلة بعد سلسلة من الخطوات كاختيار من التوزيع المطلوب. تتحسن جودة العينات مع زيادة عدد الخطوات.

لنلقِ نظرة على مثال. لنفترض أنك تحتاج إلى عينة من توزيع النسخة التجريبية . كثافته:


حيث C هو ثابت التطبيع. في الواقع ، هذه بعض دالة α و β ، لكنني أريد أن أوضح أنه ليس هناك حاجة لعينة من توزيع النسخة التجريبية ، لذلك سوف نأخذها بشكل ثابت.

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

تجعل أساليب MCMC الحياة أسهل من خلال توفير خوارزميات يمكنها إنشاء سلسلة Markov لها توزيع بيتا كتوزيع ثابت ، بالنظر إلى أنه يمكننا الاختيار من توزيع موحد (وهو بسيط نسبيًا).

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

إحدى خوارزميات MCMC هي خوارزمية متروبوليس هاستينغز.

خوارزمية متروبوليس هاستينغز

الحدس:

إذن ما هو الغرض؟

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

لذلك ، على سبيل المثال ، نود أن نقضي ضعف الوقت على قمة تلة يبلغ ارتفاعها 100 متر عن تلة مجاورة يبلغ طولها 50 متراً. من الجيد أن نتمكن من القيام بذلك حتى لو كنا لا نعرف المرتفعات المطلقة للنقاط على السطح: كل ما تحتاج إلى معرفته هو المرتفعات النسبية. على سبيل المثال ، إذا كان أعلى التل A أعلى مرتين من أعلى التل B ، فإننا نرغب في قضاء ضعف الوقت في A أكثر من B.

هناك مخططات أكثر تعقيدًا لاقتراح أماكن وقواعد جديدة لاعتمادها ، ولكن الفكرة الرئيسية هي كما يلي:

1. اختر موقعًا جديدًا "مقترحًا".
2. تعرف على كيفية مقارنة هذا الموقع بأعلى أو أقل مع الموقع الحالي.
3. البقاء في مكانك أو الانتقال إلى مكان جديد مع احتمال يتناسب مع ارتفاعات الأماكن.

الغرض من MCMC هو الاختيار من بعض توزيع الاحتمالات دون الحاجة إلى معرفة ارتفاعها الدقيق في أي وقت (لا حاجة لمعرفة C).
إذا تم إعداد عملية "التجول" بشكل صحيح ، فيمكنك التأكد من تحقيق هذه التناسب (بين الوقت الذي يقضيه وارتفاع التوزيع) .

الخوارزمية:

الآن دعونا نحدد ونصف المهمة بعبارات أكثر رسمية. دع s = (s1 ، s2 ، ... ، sM) هو التوزيع الثابت المطلوب. نريد إنشاء سلسلة Markov مع هذا التوزيع الثابت. نبدأ بسلسلة ماركوف التعسفي مع M- الدول مع مصفوفة الانتقال P ، بحيث يمثل pij احتمال الانتقال من الحالة i إلى j.

حدسيًا ، نحن نعرف كيفية تجوال سلسلة ماركوف ، ولكن سلسلة ماركوف لا تحتوي على التوزيع الثابت المطلوب. تحتوي هذه السلسلة على بعض التوزيع الثابت (الذي لا نحتاج إليه). هدفنا هو تغيير الطريقة التي نتجول فيها حول سلسلة Markov بحيث يكون للسلسلة التوزيع الثابت المطلوب.

للقيام بذلك:

1. ابدأ بالحالة الأولية العشوائية i.
2. قم باختيار الحالة المفترضة الجديدة بشكل عشوائي من خلال النظر في احتمالات الانتقال في الصف الخاص بمصفوفة النقل P.
3. احسب مقياسًا يسمى احتمال القرار ، والذي تم تعريفه على أنه: aij = min (sj.pji / si.pij ، 1).
4. الآن إرم عملة معدنية ، والتي تهبط على سطح النسر مع احتمال aij. إذا سقط النسر ، اقبل العرض ، أي ، انتقل إلى الحالة التالية ، وإلا ، رفض العرض ، أي ، تبقى في الحالة الحالية.
   
5. كرر عدة مرات.
   

بعد عدد كبير من الاختبارات ، سوف تتقارب هذه السلسلة ويكون لها توزيع ثابت. ثم يمكننا استخدام حالات السلسلة كعينة من أي توزيع.

من خلال القيام بذلك لأخذ عينات من التوزيع التجريبي ، تكون المرة الوحيدة التي عليك فيها استخدام كثافة الاحتمال هي البحث عن احتمال اتخاذ قرار. للقيام بذلك ، قسِّم sj على si (أي ، تم إلغاء ثابت التطبيع C).

اختيار بيتا

ننتقل الآن إلى مشكلة أخذ العينات من التوزيع التجريبي.

توزيع بيتا هو توزيع مستمر على [0،1] ويمكن أن يحتوي على قيم لانهائية في [0،1]. افترض أن سلسلة Markov التعسفية P مع حالات لا حصر لها على [0،1] تحتوي على مصفوفة انتقال P بحيث pij = pji = كل العناصر في المصفوفة.

لا نحتاج إلى Matrix P ، كما سنرى لاحقًا ، لكنني أريد أن يكون وصف المشكلة أقرب ما يكون إلى الخوارزمية التي اقترحناها.

• ابدأ بالحالة الأولية العشوائية التي حصلت عليها من توزيع موحد في (0،1).
• حدد حالة مفترضة جديدة بشكل عشوائي من خلال النظر في احتمالات الانتقال في الصف التاسع من مصفوفة الانتقال P. لنفترض أننا اخترنا حالة أخرى Unif (0،1) كحالة مفترضة j.
• احسب التدبير ، الذي يسمى احتمالية اتخاذ القرار:

مما يبسط إلى:

منذ pji = pij ، وأين

• الآن إرم عملة معدنية. مع احتمال aij سيسقط النسر. إذا سقط النسر ، فعليك قبول العرض ، أي الانتقال إلى الحالة التالية. خلاف ذلك ، يجدر رفض العرض ، أي ، البقاء في نفس الحالة.
• كرر الاختبار عدة مرات.

كود:

حان الوقت للانتقال من النظرية إلى الممارسة. سنكتب نموذجنا التجريبي في بيثون.

 impo rt rand om # Lets define our Beta Function to generate s for any particular state. We don't care for the normalizing constant here. def beta_s(w,a,b): return w**(a-1)*(1-w)**(b-1) # This Function returns True if the coin with probability P of heads comes heads when flipped. def random_coin(p): unif = random.uniform(0,1) if unif>=p: return False else: return True # This Function runs the MCMC chain for Beta Distribution. def beta_mcmc(N_hops,a,b): states = [] cur = random.uniform(0,1) for i in range(0,N_hops): states.append(cur) next = random.uniform(0,1) ap = min(beta_s(next,a,b)/beta_s(cur,a,b),1) # Calculate the acceptance probability if random_coin(ap): cur = next return states[-1000:] # Returns the last 100 states of the chain 

قارن النتائج مع توزيع بيتا الفعلي.

 impo rt num py as np import pylab as pl import scipy.special as ss %matplotlib inline pl.rcParams['figure.figsize'] = (17.0, 4.0) # Actual Beta PDF. def beta(a, b, i): e1 = ss.gamma(a + b) e2 = ss.gamma(a) e3 = ss.gamma(b) e4 = i ** (a - 1) e5 = (1 - i) ** (b - 1) return (e1/(e2*e3)) * e4 * e5 # Create a function to plot Actual Beta PDF with the Beta Sampled from MCMC Chain. def plot_beta(a, b): Ly = [] Lx = [] i_list = np.mgrid[0:1:100j] for i in i_list: Lx.append(i) Ly.append(beta(a, b, i)) pl.plot(Lx, Ly, label="Real Distribution: a="+str(a)+", b="+str(b)) pl.hist(beta_mcmc(100000,a,b),normed=True,bins =25, histtype='step',label="Simulated_MCMC: a="+str(a)+", b="+str(b)) pl.legend() pl.show() plot_beta(0.1, 0.1) plot_beta(1, 1) plot_beta(2, 3) 

كما ترون ، فإن القيم تشبه إلى حد بعيد توزيع بيتا. وهكذا ، وصلت شبكة MCMC إلى حالة ثابتة

في التعليمة البرمجية أعلاه ، أنشأنا عينة تجريبية ، ولكن نفس المفهوم ينطبق على أي توزيع آخر نريد أن نحقق منه.

النتائج

لقد كانت وظيفة رائعة. مبروك إذا قرأته حتى النهاية.

في الأساس ، يمكن أن تكون أساليب MCMC معقدة ، لكنها توفر لنا مرونة كبيرة. يمكنك الاختيار من أي وظيفة توزيع باستخدام التحديد من خلال MCMC. عادة ، يتم استخدام هذه الأساليب لأخذ عينات من التوزيعات الخلفية.

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

من المحررين

• بالطبع بايثون للعمل مع البيانات
• دورة تعلم الآلة عبر الإنترنت
• دورة عبر الإنترنت " BIG DATA from scratch "