زنجیره‌ مارکوف؛‌ ریاضیات عجیبی که همه‌چیز را پیش‌بینی می‌کند

چند بار باید یک دسته کارت را بُر بزنید تا واقعاً ورق‌ها تصادفی شوند؟ چقدر اورانیوم یا پلوتونیوم برای ساختن یک بمب لازم است؟ گوگل چطور حدس می‌زند شما دقیقاً دنبال کدام صفحه‌اید؟ و اصلاً چگونه می‌شود کلمه‌ی بعدی در یک جمله را پیش‌بینی کرد؟

پاسخ این سؤال‌ها همگی به یک ایده برمی‌گرد: زنجیره‌ی مارکوف.

داستان از یک دعوای عجیب در روسیه‌ی تزاری شروع شد. ریاضیدانی به نام پاول نکراسوف ادعا کرد که تصمیمات مردم ناشی از «اراده‌ی آزاد» است، اما رقیبش آندری مارکوف نشان داد که حتی رویدادهای کاملاً وابسته هم می‌توانند الگوهای قابل پیش‌بینی داشته باشند. او مدلی ساخت که در آن، آینده فقط به وضعیت فعلی بستگی داشت، نه به کل تاریخچه.

ایده‌ی مارکوف که می‌تواند همه‌چیز را پیش‌بینی می‌کند،‌ دنیا را منفجر کرد؛ سفری شگفت‌انگیز که از تحلیل آماری شعرهای روسی شروع شد، از آزمایشگاه‌های فوق‌سری پروژه‌ی منهتن عبور کرد و به هسته‌ی اصلی الگوریتم PageRank گوگل رسید. اما این «زنجیره» چطور توانست تمام این دنیاهای به‌ظاهر بی‌ربط را به هم متصل کند و امروز، چگونه به هوش مصنوعی قدرت می‌دهد تا کلمه‌ی بعدی شما را حدس بزند؟

و البته، پاسخ دقیق به آن سؤال اول: برای یک بازی منصفانه، واقعاً چند بار باید کارت‌ها را بُر بزنیم؟ پاسخ دقیق‌تر از آن چیزی است که فکرش را می‌کنید.

سال ۱۹۰۵، روسیه‌ی تزاری در تب‌وتاب انقلاب بود. گروه‌های سوسیالیست علیه تزار قیام کرده بودند و جامعه به دو قطب متخاصم تقسیم شده بود. این شکاف آن‌قدر عمیق بود که حتی به دنیای خشک ریاضیات هم کشیده شد.

در یک سو پاول نکراسوف ملقب به «تزار احتمالات» ایستاده بود؛ فردی عمیقاً مذهبی و طرف‌دار سرسخت تزار که از جایگاه قدرتمندش استفاده می‌کرد تا استدلال کند که ریاضیات می‌تواند «اراده‌ی آزاد» و خواست خدا را توضیح دهد.

در سوی دیگر رقیب فکری او، آندری مارکوف ملقب به «آندری خشمگین» قرار داشت. مارکوف آتئیست و سوسیالیست بود و اصلاً نمی‌توانست افرادی را که در ریاضیات، «دقیق» نبودند، تحمل کند و از نظرش، نکراسوف سردسته‌ی آن‌ها بود. مارکوف باور داشت ریاضی هیچ ربطی به اراده‌ی آزاد یا مذهب ندارد و علناً کارهای نکراسوف را «سوءاستفاده از ریاضیات» می‌خواند.

موضوع جدال آن‌ها، قانونی بود که در دو قرن گذشته پایه و اساس نظریه‌ی احتمالات به‌شمار می‌رفت: قانون اعداد بزرگ.

این قانون را با یک مثال ساده‌ی پرتاب سکه درک می‌کنید. اگر ۱۰ بار سکه‌ای را بالا بیندازید، ممکن است ۶ بار «شیر» و ۴ بار «خط» بیاید (نسبت ۶۰/۴۰). این نتیجه با چیزی که انتظار داریم (۵۰/۵۰) فاصله دارد. اما اگر به پرتاب سکه ادامه دهید، مثلاً ۱۰۰ بار، نتیجه چیزی شبیه ۵۱ شیر و ۴۹ خط خواهد شد. هرچه تعداد پرتاب‌ها بیشتر شود، میانگین نتایج به مقدار موردانتظار (۵۰/۵۰) نزدیک‌تر و نزدیک‌تر می‌شود.

حالا وضعیتی را در نظر بگیرید که رویدادها به‌هم‌ وابسته باشند؛ مثلاً از گروهی می‌خواهیم قیمت کالایی را حدس بزنند. اگر هر کس نظرش را جداگانه روی کاغذ بنویسد، تخمین‌ها پراکنده می‌شود و میانگین عددی نزدیک به ارزش واقعی کالا خواهد بود.

اینجا بود که نکراسوف وارد شد. او به آمارهای اجتماعی مثل تعداد ازدواج‌ها یا نرخ جرم و جنایت نگاه کرد و دید که این آمارها سال‌به‌سال تقریباً ثابت هستند و از قانون اعداد بزرگ پیروی می‌کنند. او از این مشاهده نتیجه‌گیری عجیبی کرد: چون این آمارها از قانون اعداد بزرگ تبعیت می‌کنند، پس رویدادهای زیربنایی آن‌ها (یعنی تصمیم افراد برای ازدواج یا ارتکاب جرم) باید مستقل باشند. از نظر او، این استقلال همان «اراده‌ی آزاد» بود و ریاضیات آن را اثبات می‌کرد!

استدلال نکراسوف، مارکوف را شدیداً به خشم آورد. به نظر او، این تفسیر نوعی تحریف علم بود؛ پس تصمیم گرفت نکراسوف را برای همیشه ساکت کند. نقشه‌اش این بود که ثابت کند که حتی رویدادهای وابسته هم می‌توانند از قانون اعداد بزرگ پیروی کنند.

مارکوف به سراغ یکی از شاهکارهای ادبیات روسیه، یعنی شعر اوژن اونگین اثر الکساندر پوشکین رفت. او ۲۰,۰۰۰ حرف اول شعر را برداشت (بدون احتساب فاصله‌ها و نقطه‌گذاری) و آن‌ها را شمرد: ۴۳درصد حروف صدادار (V) و ۵۷درصد بی‌صدا (C) بودند.

اگر حروف مستقل بودند، شانس اینکه دو حرف صدادار پشت‌سرهم بیایند (V,V) به‌این‌ترتیب محاسبه می‌شد: ۴۳٪ × ۴۳٪ ≈ ۱۸٫۵٪

اما وقتی مارکوف متن را بررسی کرد، دید که حروف صدادار دوتایی فقط ۶درصد مواقع رخ داده‌اند! این نشان می‌داد که حروف به شدت به هم وابسته‌اند.

حالا بخش اصلی کار: مارکوف یک «ماشین پیش‌بینی» ساده ساخت. تصور کنید او دو دایره کشید، مدلی شامل دو حالت («صدادار» V و «بی‌صدا» C) و پیکان‌هایی که نشان می‌دادند از هر حالت با چه احتمالی به حالت دیگری می‌رویم.

• او محاسبه کرد که اگر در حالت «صدادار» باشیم، شانس اینکه حرف بعدی باز هم صدادار باشد چقدر است: از تقسیم ۶درصد بر ۴۳درصد به عدد حدود ۱۳درصد رسید.
• چون مجموع احتمالات خروجی یک حالت باید ۱۰۰درصد باشد، پس شانس رفتن از صدادار به بی‌صدا برابر ۸۷درصد بود.
• همین محاسبات را برای حالت «بی‌صدا» هم تکرار کرد.

سپس مارکوف سیستم خود را به راه انداخت: از یک حرف تصادفی شروع کرد و بر اساس احتمالات محاسبه‌شده، حرف بعدی را «تولید» کرد و این فرایند را هزاران بار تکرار نمود. نتیجه شگفت‌انگیز بود: پس از مدتی، نسبت حروف تولید شده توسط این مدل دقیقاً به همان ۴۳ درصد صدادار و ۵۷ درصد بی‌صدا همگرا شد.

مارکوف پیروز شده بود. او سیستمی کاملاً وابسته ساخته بود (یک زنجیره‌ی رویدادها) که همچنان از قانون اعداد بزرگ پیروی می‌کرد. بنابراین مشاهده‌ی همگرایی در آمارهای اجتماعی مثل ازدواج اصلاً ثابت نمی‌کند که تصمیمات مردم مستقل یا ناشی از «اراده‌ی آزاد» است.

مارکوف در پایان مقاله‌اش، تیر خلاص را به رقیبش زد: «بنابراین، برای احتمالات نیازی به اراده‌ی آزاد نیست. در واقع، حتی نیازی به استقلال هم نیست.»

زنجیره‌ی ماکوف باید دنیای علم را منفجر می‌کرد، اما در آن زمان، تقریباً «هیچ‌کس متوجه‌اش نشد». حتی خود مارکوف هم اهمیتی به این موضوع نداد و گفت: «من فقط به مسائل تحلیل محض علاقه‌مندم.» او نمی‌دانست که این شکل جدید از احتمالات، قرار است نقشی کلیدی در یکی از مهم‌ترین تحولات قرن بیستم ایفا کند.

صبح روز ۱۶ ژوئیه ۱۹۴۵، ایالات متحده اولین بمب اتمی جهان یعنی «گجت» (Gadget) را در صحرای نیومکزیکو منفجر کرد. این انفجار که معادل ۲۵ هزار تن TNT بود، از حدود ۶ کیلوگرم پلوتونیوم نیرو می‌گرفت و اوج پروژه‌ی فوق‌سری منهتن بود: جایی که ذهن‌های درخشانی چون جی. رابرت اوپنهایمر، جان فون نویمان و ریاضی‌دان لهستانی، استانیسلاو اولام، کنار هم ایستادند.

کار بمب اتمی بر اساس «واکنش زنجیره‌ای» پیش می‌رود: یک نوترون به هسته‌ی یک اتم «شکافت‌پذیر» (مانند اورانیوم-۲۳۵ یا پلوتونیوم) برخورد می‌کند، هسته می‌شکافد، انرژی آزاد می‌کند و مهم‌تر از آن، ۲ یا ۳ نوترون جدید آزاد می‌شوند.

اگر به طور متوسط بیش از یکی از این نوترون‌های جدید به هسته‌های دیگر برخورد کنند، واکنش به‌صورت نمایی رشد می‌کند و انفجار رخ می‌دهد. حالا سؤال کلیدی این بود که دقیقاً چقدر از این ماده‌ی گران‌بها و کمیاب لازم است تا واکنش به مرز «بحرانی» برسد؟ پاسخ به رفتار تریلیون‌ها نوترون در حال حرکت بستگی داشت.

این مسئله تاحدی فریبنده بود. تعداد کل حالت‌های ممکن برای چیدمان ۵۲ کارت، عددی نجومی است (۵۲ فاکتوریل، یعنی ۸ با ۶۷ صفر جلوی آن). حل این مسئله به روش تحلیلی کلافه‌کننده به‌نظر می‌رسید.

ناگهان جرقه‌ای در ذهن اولام زده شد: «چه می‌شود اگر به‌جای محاسبه، صدها بار بازی کنم و فقط بشمارم که چند بار برده‌ام؟» طبق آمار اگر هزار بار بازی کنید و ۳۰ بار ببرید، می‌توانید با اطمینان خوبی بگویید شانس برد حدود ۳درصد است.

جان فون نویمان بلافاصله قدرت این ایده را تشخیص داد اما مشکل کلیدی ماجرا را هم دید: بازی‌های سالیتر از هم مستقل هستند و نتیجه‌ی یک بازی روی بازی بعدی تأثیر ندارد. اما رفتار نوترون‌ها این‌طور نیست. رفتار یک نوترون به مکانش و کاری که قبلاً انجام داده وابسته است.

فون نویمان متوجه شد که صرفاً نمی‌توانند نتایج تصادفی را نمونه‌برداری کنند؛ بلکه باید یک زنجیره‌ی کامل از رویدادها را مدل‌سازی کنند. گروه دقیقاً به چیزی نیاز داشت که آندری مارکوف اختراع کرده بود: یک زنجیره‌ی مارکوف.

فون نویمان و اولام یک زنجیره‌ی مارکوف برای نوترون‌ها طراحی کردند. حالت اولیه را یک نوترون در حال حرکت در هسته‌ی شکافت‌پذیر در نظر گرفتند تا گذارها (اتفاقات ممکن) به ترتیب زیر تعریف شود:

• نوترون به اتمی برخورد کرده و پراکنده می‌شود؛ یعنی برمی‌گردد به فاز «در حال حرکت»
• نوترون از سیستم خارج شده یا جذب ماده‌ی دیگری می‌شود: زنجیره در همان شاخه پایان می‌یابد
• نوترون به هسته پلوتونیوم برخورد کند و شکافت رخ دهد: این اتفاق، ۲ یا ۳ زنجیره‌ی مارکوف جدید را آغاز می‌کند

البته احتمالات این گذارها ثابت نبود و به انرژی و موقعیت نوترون بستگی داشت. بعد گروه این مدل را روی اولین کامپیوترهای الکترونیکی مانند ENIAC اجرا کرد. کامپیوتر هزاران بار این شبیه‌سازی را تکرار کرد و هر بار، «ضریب تکثیر (K)» را اندازه گرفت: یعنی به طور متوسط هر نوترون چند نوترون جدید تولید می‌کند.

• اگر میانگین K کمتر از ۱ بود، واکنش فروکش می‌کرد و می‌مرد.
•  اگر K مساوی ۱ بود، واکنش پایدار می‌ماند (مثل یک رآکتور هسته‌ای).
• اگر K بزرگ‌تر از ۱ بود، واکنش به‌صورت نمایی رشد می‌کرد (مسیر بمب).

آن‌ها راهی آماری برای حل معادلاتی پیدا کرده بودند که تحلیلی‌شان غیرممکن به‌نظر می‌رسید. اولام، به یاد عمویش و کازینوی معروف موناکو، نام این رویکرد را روش مونت-کارلو (Monte Carlo Method) گذاشت. این روش، که ترکیبی از ایده‌ی نمونه‌گیری آماری اولام و قدرت محاسباتی فون نویمان بود، به‌سرعت به ابزاری کلیدی در فیزیک، مهندسی و محاسبات مالی تبدیل شد.

زنجیره‌های مارکوف بار دیگر در دهه‌ی ۱۹۹۰، در مکانی غیرمنتظره، احیا شدند: اینترنت. با انفجار وب در اواسط دهه‌ی ۹۰، مشکل جدیدی به‌وجودآمد: چطور در این دریای اطلاعات چیزی را پیدا کنیم؟ در آن زمان موتورهای جستجوی اولیه مثل یاهو (Yahoo) وجود داشتند. یاهو پادشاه اینترنت بود، اما نقطه‌ضعفی اساسی داشت.

برای درک کیفیت، به سراغ کتابخانه‌ها می‌رویم. در کتاب‌های قدیمی کتابخانه، کارتی وجود داشت که تاریخ‌های تحویل کتاب روی آن مهر می‌خورد. اگر کتابی را برمی‌داشتید که پر از مهر بود، می‌فهمیدید که «این کتاب خوبی است.» مهرها نقش «تأیید» یا «رأی» را داشتند.

در دانشگاه استنفورد، دو دانشجوی دکترا به نام‌های سرگِی برین و لری پیج، تصمیم گرفتند همین ایده را در وب پیاده کنند. آن‌ها گفتند هر «لینک» از صفحه‌ای به صفحه‌ی دیگر، مانند یک رأی یا تأیید است، البته صفحاتی که خودشان لینک‌های باکیفیتی دریافت کرده‌اند، «رأی» باارزش‌تری می‌دهند.

رضا سلطانی کردشولی

تاریخچه کامل اینترنت: از آزمایشگاه‌های جنگ سرد تا دهکده‌ جهانی و وب ۳

مطالعه '27

برین و پیج متوجه شدند که می‌توانند کل شبکه‌ی وب را به‌عنوان یک زنجیره‌ی مارکوف غول‌پیکر مدل کنند. حالت‌ها: تمام صفحات وب در اینترنت. گذارها: لینک‌های بین صفحات. آن‌ها همچنین استعاره‌ی دیگری را هم مطرح کردند؛ «موج‌سوار تصادفی» (Random Surfer) که در اینترنت سرگردان است.

فرض کنید یک اینترنت کوچک با چهار صفحه داریم: A، B، C و D.

• صفحه‌ی A فقط به B لینک می‌دهد.
• صفحه‌ی B به A و C لینک می‌دهد.
• صفحه‌ی C به A لینک می‌دهد.
• صفحه‌ی D به B لینک می‌دهد.

اگر موج‌سوار از صفحه‌ی A شروع کند، روی لینک آن کلیک می‌کند و به B می‌رود، از B ممکن است به A یا C برود، از C دوباره به A برگردد، و این چرخه ادامه یابد.

پس از مدتی، اگر حساب کنیم او چند درصد از وقتش را در هر صفحه گذرانده، می‌بینیم بیشتر زمانش در حلقه‌ی A–B–C صرف می‌شود و صفحه‌ی D سهم ناچیزی دارد. چون گرچه به B لینک می‌دهد، اما هیچ صفحه‌ی مهمی به D لینک نداده است.

 نسبت زمانی که موج‌سوار در هر صفحه می‌گذراند، همان امتیاز PageRank آن صفحه محسوب می‌شود. اینجا باید دو مسئله روشن می‌شد:

اول، آیا می‌شد این سیستم را فریب داد؟ مثلاً من ۱۰۰ صفحه‌ی اسپم بسازم که همگی به سایت من لینک بدهند؟ پاسخ «نه» بود. چون هیچ صفحه‌ی باکیفیتی به آن ۱۰۰ صفحه‌ی اسپم لینک نداده، موج‌سوار تصادفی ما هرگز به آن‌ها نمی‌رسد که بخواهد روی لینکشان کلیک کند. پس رأی آن‌ها اصلاً شمرده نمی‌شود.

دوم مشکل «گیرافتادن»: چه می‌شد اگر موج‌سوار به صفحه‌ای می‌رسید که هیچ لینک خروجی نداشت یا در یک حلقه‌ی کوچک (مثل A-B-C) برای همیشه گیر می‌افتاد؟

سال ۱۹۹۸، آن‌ها موتور جستجوی خود را راه‌اندازی کردند و نامش را Google گذاشتند. گوگل یاهو را نابود کرد، نه با بازاریابی، بلکه با فناوری برتر. در قلب این الگوریتم میلیارددلاری، همان ایده‌ی قدیمی آندری مارکوف نهفته بود.

در دهه‌ی ۱۹۴۰، کلود شانون، ریاضی‌دان و مهندس آمریکایی که بعدها «پدر نظریه‌ی اطلاعات» لقب گرفت، دوباره به ایده‌ی اصلی مارکوف یعنی پیش‌بینی متن بازگشت اما کار را یک‌قدم جلوتر برد.

The head and in frontal attack on an English writer that the character of this...

البته جمله در کل بی‌معنی بود، اما تکه‌های چهار یا پنج کلمه‌ای آن مثل حمله به یک نویسنده‌ی انگلیسی، کاملاً معنی‌دار به نظر می‌رسیدند. شانون فهمید که هرچه کلمات قبلی بیشتری را در نظر بگیرید، پیش‌بینی شما برای کلمه‌ی بعدی بهتر می‌شود.

این دقیقاً همان کاری است که قابلیت «تکمیل خودکار» در ایمیل یا موتور جست‌وجو انجام می‌دهد. هسته‌ی اصلی مدل‌های زبانی بزرگ امروزی (LLMs مثل ChatGPT) هم بر همین ایده‌ی زنجیره‌های مارکوف بنا شده است. آن‌ها پیش‌بینی می‌کنند که محتمل‌ترین «توکن» (کلمه یا بخشی از کلمه) بعدی، باتوجه‌به رشته‌ی توکن‌های قبلی چیست.

مثلاً در جمله‌ی «ساختار... سلول»، اگر مدل قبلاً کلماتی مانند «خون» و «میتوکندری» را دیده باشد، مکانیزم «توجه» به این کلمات وزن بیشتری می‌دهد و می‌فهمد که منظور از «سلول»، سلول بیولوژیکی است، نه سلول زندان.

باوجود تمام این موفقیت‌ها، زنجیره‌های مارکوف همه‌جا کار نمی‌کنند. نقطه‌ی ضعف اصلی آن‌ها، سیستم‌هایی هستند که حلقه‌ی بازخورد (Feedback Loop) دارند.

در زنجیره‌های مارکوف، فرض کلیدی این است که حالت بعدی فقط به وضعیت فعلی بستگی دارد. اما در بسیاری از پدیده‌های واقعی، خروجی امروز بر ورودی فردا اثر می‌گذارد. این یعنی سیستم، خودش رفتار خودش را تغییر می‌دهد.

نگرانی جدی از جایی ناشی می‌شود که مدل‌های آینده با داده‌هایی آموزش ببینند که مدل‌های گذشته ساخته‌اند و به‌تبع حلقه‌ای بسته شکل بگیرد: مدلی که از محصولات خودش یاد می‌گیرد. در این وضعیت، یک «حالت پایدار کسل‌کننده» ایجاد می‌شود و به‌تدریج تنوع زبانی و خلاقیت کاهش می‌یابد و مدل شروع می‌کند به «تکرار خودش». در اصطلاح فنی، این همان حلقه بازخورد داده‌ای است؛ مدلی که دُم خودش را می‌بلعد.

برای درک روشن‌ترِ مفهوم بازخورد، مثال تغییرات اقلیمی را در نظر بگیرید. وقتی غلظت افزایش پیدا می‌کند، دمای زمین بالا می‌رود. هوای گرم‌تر بخار آب بیشتری در خود نگه می‌دارد و بخار آب نیز خودش یکی از گازهای گلخانه‌ای مؤثر است.

بنابراین، افزایش دما باعث افزایش بخار آب می‌شود، و بخار آبِ بیشتر دوباره دمای زمین را بالاتر می‌برد. این حلقه بازخورد مثبت یکی از دلایل اصلی دشواری پیش‌بینی دقیق آب‌وهواست؛ چون در آن، خود نتیجه (گرما) به ورودی جدیدی برای فرایند تبدیل می‌شود.

قدرت زنجیره‌ی مارکوف به خاصیت «بی‌حافظه» (Memoryless) بودن آن برمی‌گردد. برای بسیاری از سیستم‌های پیچیده (مثل رفتار نوترون‌ها یا موج‌سوار وب)، لازم نیست تمام تاریخچه‌ی بلندمدت را بدانید؛ فقط دانستن حالت فعلی کافی است تا گذار بعدی را پیش‌بینی کنید. همین ساده‌سازی، تحلیل پدیده‌هایی را ممکن می‌کند که در نگاه اول بی‌نهایت پیچیده به نظر می‌رسند.

حالا بیایید به سؤال ابتدای مقاله بازگردیم: چند بار باید یک دسته کارت را بُر بزنیم تا کارت‌ها واقعاً تصادفی شوند؟ اگر از روش «بُر زدن ریفلی» (Riffle Shuffle) استفاده کنید؛ یعنی دسته‌ی کارت را به دو نیم تقسیم کرده و کارت‌ها را در هم ببافید؛ عدد جادویی هفت بار است.

تحقیقات ریاضی نشان داده است که پس از ۷ بار شافل ریفلی، توزیع کارت‌ها به اندازه‌ی کافی به «توزیع یکنواخت» نزدیک می‌شود. این یعنی شانس ظاهرشدن هر چیدمان خاصی (مثلاً همه‌ی آس‌ها پشت‌هم) تقریباً با شانس ظاهرشدن هر چیدمان به‌هم‌ریخته‌ی دیگری برابر می‌شود. در این نقطه، دسته کارت «تصادفی» در نظر گرفته می‌شود.

جالب است بدانید که اگر از آن روش ساده‌تر استفاده کنید که در آن فقط بخشی از کارت‌ها را برمی‌دارید و روی بقیه می‌گذارید، باید بیش از دو هزار بار این کار را تکرار کنید تا به همان میزان تصادفی‌بودن برسید.

و به‌این‌ترتیب، دعوای دو ریاضی‌دان روس بر سر اراده‌ی آزاد، به ابزاری تبدیل شد که ساخت بمب اتم را ممکن کرد، اینترنت را سامان داد، پایه‌های هوش مصنوعی را بنا نهاد و حتی به ما گفت که برای یک بازی منصفانه، دقیقاً چند بار باید کارت‌ها را بُر بزنیم.