نام‌اش را به خاطر ندارم. سال دوم راه‌نمایی بود. کلاس حرفه و فن. معلم تازه‌ای که به جای آقای موثق (که این هم ماجراها برای خود دارد) آمده بود. یادم نیست چه کاره بود. شاید پزشک یا چیزی در آن حدود. نام‌اش را نیز به خاطر نمی‌آورم. به نظرم جوان (یا میان‌سال) قد بلندی بود با اداهای خاص خودش. به نظرم آدم بدی نمی‌آمد. البته درست یادم نیست.
به هر حال …
به خاطر می‌آورم روزی داشت برای‌مان صحبت می‌کرد که علم چقدر تخصص‌ای است و مردم روی مسایل خیلی جزیی‌ای کار میکنند و از این حرف‌ها. می‌گفت یکی از دوستان‌اش (یا شاید هم یک بابایی به طور کلی!) هست که دکترای‌اش را روی پوست تخم مرغ گرفته است! باور کنید، همین را گفت! و باور نمی‌کنید که ما چقدر خندیدیم. کلاس منفجر شد. تاثیر این حرف (و میزان تخصص!) آن‌قدر زیاد بود که الان بعد از n سال (و محض اطلاع، n به طرز قابل قبول‌ای بیش از ۵ سال است) هنوز آن شرایط را به خاطر دارم. دکترای پوست تخم مرغ؟! هه!
شما هم خندیدید؟ به نظرتان مسخره است که آدم برود دکترای‌اش را درباره‌ی پوست تخم مرغ بگیرد؟!
متاسفانه باید اعلام کنم که اگر این روزها کس‌ای چنین چیزی به‌ام بگوید، ازش می‌پرسم راجع به چه چیز پوست تخم مرغ‌داری پژوهش می‌کنی. موضوع به آن کلی‌ای که معنا ندارد!!!
دی‌شب در راه بازگشت به خانه داشتم فکر می‌کردم که مساله‌ی زیر چقدر جالب است:
فرض کنید دو تا دوست‌دختر دارید! هر کدام اخلاق خاص خودشان را دارند و [طبیعتا] اخلاق‌شان خیلی بگیر نگیر دارد. بعضی وقت‌ها حال‌شان خوب است و سر کیف‌اند و حسابی شما را خوش‌حال میکنند و بعضی وقت‌ها حال‌تان را می‌گیرند (خب، البته همه‌ی آدم‌ها این‌طوری نیستند. بعضی‌ها حتما و بدون تامل حال‌تان را می‌گیرند. اندک موردی هم دیده شده است که در بیشتر مواقع این‌کار را نمی‌کند. بگذریم …). شما دوست دارید بیش‌ترین لذت ممکن را از رابطه‌تان ببرید. در نتیجه بهتر است با دختری دوست باشید که به طور متوسط شما را بیشتر خوش‌حال می‌کند.
اما مشکل این است که شما نمی‌دانید کدام یک بهتر است. بعضی وقت‌ها این بهتر است، بعضی وقت‌ها آن. اما به هر حال یکی‌شان به طور متوسط بهتر است که البته شما نمی‌دانید کدام. کاری که می‌توانید بکنید این است که مدتی با این دوست باشید و بعد ببینید به طور متوسط چقدر خوش‌حال شده‌اید، بعد بروید سراغ دیگری و ببینید به طور متوسط چقدر خوش‌حال بوده‌اید و در نهایت این دو متوسط را مقایسه کنید و بعد از آن بچسبید به آن‌ای که متوسط بالاتری دارد.
این روش یک عیب دارد. شما خیلی راحت نمی‌توانید متوسط وضعیت شخص‌ای را خیلی راحت در بیاورید. با دو سه تجربه نمی‌تواند نظری در مورد شخص داد. بیست تجربه چطور است؟ بد نیست، اما باز هم کافی نیست. در واقع همیشه احتمال خطا در قضاوت‌تان وجود دارد. پس نمی‌توان به صرف چند تجربه‌ی بهتر با یکی، دیگری را به کل رد کرد چون ممکن است به طور اتفاقی این چند نمونه تجربه با یکی بهتر از دیگری در آمده باشد ولی واقعیت (متوسط واقعی!) برعکس باشد.
سوال این است: چطوری باید با دوست دخترهای‌تان قرار بگذارید تا در نهایت «اون به‌تره» را پیدا کنید؟ یا به عبارت دیگر، راه حل با کم‌ترین تاسف چیست؟ (regret minimization problem!)
البته این مساله کمینه در جوامع آکادمیک این‌قدر عملی مطرح نمی‌شود. در واقع صورت اصلی‌ی این مساله به نام n-armed bandit معروف است و هیچ ربطی به مسایل ناموسی ندارد. اما اساس هر دوی‌شان یکی است.
خب! همه‌ی این‌ها که چه؟ آها! ملت سال‌ها است روی این مساله (و تغییرات‌اش) کار کرده‌اند و هنوز هم کار میکنند. در واقع فکر کنم بشود روی چنین مساله‌ای دکترا گرفت (البته طبیعتا با یک سری تغییرات). تازه به نظر شخصی‌ام (من معمولا نظرات‌ام شخصی‌اند!)، این مساله‌ی جالب‌ای است و درباره‌اش کار کردن بامزه.
پوستِ تخم مرغ دیگر، نه؟!
ضدخاطرات 
من فکر نمی کنم آدم ها تا این اندازه شبیه دستمال کاغذی باشند که بتوانیم هر کدام شان را خواستیم تجربه کنیم و بعد دور بیاندازیم. اگر این گونه باشد که وجدان و تعهد در یک رابطه ی دوستی بی ارزش می شوند.
دوست دختر هم جز مسایل ناموسی است؟
به ری‌را: تفسیر این مثال به دستمال کاغذی و دور انداختن و غیره به نظرم زیادی شدید و تند است و نه من از آن استفاده کرده‌ام و نه قصدم آن بوده است. شاید عبارت «تلاش برای شناخت» دقیق‌تر باشد. برای شناختن آدم‌ها و پیداکردن مناسب‌ترین فرد (شما که منکر چنین لزومی نیستید؟) و هم‌چنین ساختن رابطه‌ی دوستی نیاز به شناخت طرف مقابل داریم. شناخت نیز با تجربه به دست می‌آید و این تجربه خطاپذیر است. همه‌ی حرف آن مثال در این است که این مساله راحت حل نمی‌شود و از نظر تئوری مساله‌ی دشواری است.
به آیدا: اممم … اگر ناموسی نباشد، شبه‌ناموسی که هست!
فکر کنم داوطلبان کار و تحقیق در این رشته زیاد باشند 🙂
ولی بدون شک پوست تخم مرغ نیست. اهمیت این موضوع را تعداد بیشتری درک میکنند.
پسران این مرز و بوم این مقطع علمی رو به طور مادر زادی احتمالا در دوران پر افتخار جنینی می گذرانند :دی
آگاهان می گویند برخی حتی تبحر خاصی در گزینش یک دوست دختر از بین 4 یا بیشتر را هم دارند.!
به شانه بسر: نمی‌دانم، اما فکر نکنم خیلی هم زیاد باشد. به هر حال این مساله پنجاه سال است درست و حسابی حل نشده. شاید مشکل این است که کس‌ای این‌طوری که من تعریف کردم مساله را باز نمی‌کند! (;
به آهو: فکر نکنم خیلی بهتر از بقیه‌ی پسران عالم باشند. بگذریم که به هر حال دختران و پسران با هم تکامل یافته‌اند و کم و بیش از ابزارهای قابل مقایسه‌ای (ولی نه یک‌سان) برخوردارند.
این مسئله‌ی n-armed bandit که احیاناً آن مسئله‌ی n-army معروف نیست؟ وقت‌داری یک‌کم درباره‌ی این مسئله بتوضیحی؟
اممم… به نظرم هم مسئله را باید بیشتر باز کرد، هم به راه‌حل‌های دیگری که متصور است فکر کرد. این تجربه تجربه‌ی خاصی است و باید راه‌حل‌های آن در موارد مختلف تاحدودی شخصی‌سازی شود. 🙂
how abt if u set the proposal topic to «regret minimization problem for finding the most energizer Partner, regardless the sex of the buddy»?
?then..would there be any scholarship or grant
if so, i’m the Volunteer
D:
fek konam khoshhal nashid age har 2 dokhtar ham gheire shoma pesare morede azmayeshi dashte bashand?che niazi be in kar ast vaghti mitoonid ba yeki be ham bezanid va ba dygray bemanid gozinesh oghada ham sakht nis,dokhtarha ham faghat baraye sargarm kardane shoma nistan ke haletoono khob konan in ye rabeteye ensanie rabeteye 2 adam va ba in taryf nemishe ke tarafetoon khoobe age haletoono khob kone!in toosyf bacheganas .az shoma entezare bishtar az in miraft.agar ravabetetoono bar in bana mizaryd ke taraf haletoono khob kone!khob haminam pish miad ke motevaset va average begyryd…!va natoonid entekhanb konid .agar az mozee khodkhahitoon biayn pain va bar mabnaye avatef bana bezaryd onvaght hich vaght sedaghat va rastyo ke mabnaye har rabeteyie kenar nemizaryd
به محسن مومنی: متاسفانه مساله‌ی n-army را نمی‌شناسم. در نتیجه نمی‌دانم همین است یا نه. اما n-armed bandit مساله‌ی معروف‌ای است و احتمالا معروف‌ترین نام به کار رفته برای این مساله.
این مساله این‌گونه تعریف می‌شود:
قمارخانه‌ای را در نظر بگیرید که در آن ماشین‌اش هست که n دست‌گیره دارد. هر کدام از دست‌گیره‌ها را که بکشید مقداری سود یا ضرر می‌کنید (یعنی یا کمی پول به شما می‌دهد یا کمی پول ازتان می‌خواهد). این مقدار تصادفی است و در طول زمان تغییر می‌کند. یعنی اگر یک دست‌گیره را دو بار بکشید، مقدار سود یا ضررتان یک‌سان نیست.
اینک فرض کنیم که متوسط سود (یا ضرر – اگر منفی باشد) هر دست‌گیره مقدار ثابت‌ای است که البته بر شما دانسته نیست (اما متوسط سود دست‌گیره‌های متفاوت یک‌سان نیستند). توجه کنید که تنها متوسط ثابت است و نه مقداری که از هر بار کشیدن دست‌گیره به دست می‌آید.
حال هدف این است که دست‌گیره‌ها را طوری بکشید که در نهایت بیش‌ترین سود ممکن را ببرید.
از آن‌جا که شما نمی‌دانید متوسط سود هر دست‌گیره چقدر است، پس باید سعی کنید تخمین‌ای از آن سود به دست آورید. اما توجه کنید که اگر خیلی بخواهید تخمین‌تان دقیق باشد، ممکن است سود ناشی از کشیدن دست‌گیره‌ی دیگری را که متوسط به‌تری دارد از دست بدهید. برعکس، اگر بخواهید دست‌گیره‌های دیگر را زیاد آزمایش کنید، تخمین‌تان دقت‌اش کم می‌شود و ممکن است دست‌گیره‌ای را که واقعا بهتر است از دست بدهید.
این صورت‌ای از مساله است. مساله فرم‌های دیگری هم دارد. مثلا متوسط سود هر دست‌گیره ثابت نیست اما توزیع تصادفی‌ی هر دست‌گیره را می‌دانید (در واقع مشکل دیگر تخمین متوسط نیست، موضوع این است که از کدام دست‌گیره باید استفاده کنید). و یا مثلا حالت‌ای که سود هر دست‌گیره به پارامترهای دیگری هم بستگی دارد (مثلا وضعیت آب و هوا!). و حالت‌های دیگر …
به Rahil: شاید! به هر حال می‌شود تغییرش داد و شاید هم هم‌چنان پول‌ای برای پرداخت باقی بماند. (;
به رکسانا:
۱) لطفا پاسخ‌ام به کامنت ری‌را را بخوانید. احتمالا روشن‌گر است.
۲) من به کس‌ای توصیه نکرده‌ام که این‌گونه دوستان‌اش را پیدا کند. لطفا به آن «فرض کنید …» ابتدای پاراگراف مورد نظر دوباره توجه کنید. وقتی چنان چیزی ابتدای توصیف چیزی می‌آید، یک مساله با شرایط خاصِ خودش تعریف می‌شود.
۳) اگر به نوشته دقت کنید، من به کس‌ای توصیه نکرده‌ام این‌گونه زندگی کند، بلکه تنها یک شرایط خاص را -که با عبارت «فرض کنید …» توصیف می‌شود- تحلیل (و البته تنها کیفی) کرده‌ام. تحلیل شرایط معادل توصیه‌ی اخلاقی نیست.
۴) معیار شما برای انتخاب یک فرد چیست؟ چطوری به شناخت فرد مقابل می‌رسید؟ روابط انسانی بدون صرف وقت معنادار است؟ آن وقت صرف‌شده برای چه صرف می‌شود؟ لطفا توضیح دهید.
۵) اینکه شما به این نتیجه رسیده‌اید که من از موضع خودخواهی به این نتایج رسیده‌ام اشتباه است. گویا متاسفانه نتوانسته‌ام در این نوشته منظور خودم را به درستی برسانم (و منظورم تنها چیزی که نبود، توصیه‌ی اخلاقی برای روابط صحیح انسانی بود).
۶) لطفا پنگلیش کامنت نگذارید. خواندن‌اش سخت است – مخصوصا وقتی راست‌چین نشان داده می‌شود.
چه بسیار جالب بود! سولو به نظرم برای اجتناب از تداوم دعواهای جنسیتی، بی خیال پیشرفت علم شو و بگذار ملت کارشان را بکنند و محققان هم با همان قمارخانه خودشان سرگرم باشند ؛)
من یکی که سرم گیج رفت!!!
میگم انقدر تجزیه تحلیل کردن زیاد هم خوب نیست ها از من گفتن بود.
به حمیدرضا: شاید برای همین است که می‌گویند پژوهش در ایران نهادین نیست! از یک طرف که بروی به قبای دین برمی‌خورد، از طرف دیگر به قبای سنت، از طرف دیگر نیز به روابط انسانی توهین می‌شود و طرف نهایی نیز اوستا-کار مکانیک یا برق‌کار به‌اش برمی‌خورد اگر بگویی دست‌گاه‌ای که می‌سازی کج است. (البته این حرف‌ام کمی شوخی بود!).
به بی‌تا: من‌ام شنیده بودم چنین چیزی را. می‌گویند در مورد عشق و این حرف‌ها بهتر است زیاد به معشوق فکر نکنی (البته دلیل‌اش را معمولا نمی‌گویند). به هر حال چشم … ! (;
خوب امیر مسعود جان اون یکم فرآیندی که با هم از دکتر نادر یاد گرفتیم می گفت اگر سیگنالت یقینی یا دترمینیستیک!! نباشه نمی تونی ممان هاشو ثابت فر ض کنی.در مورد دخترها ( یا پسر ها!! بهشون بر نخوره) و کلا انسان ها که یکمی زیادی غیر یقینی هستن نمیشه میانگینشون (تازه رو حساب کرد مگه اینکه مشاهداتت بی نهایت باشه که اونم امکان پذیر نیست فکر کنم برای همینه که از درس فرآیند ها تصادفی هم سخت ترن.
به محمد: لازمه‌اش یقینی‌بودن سیگنال نیست. سیگنال اگر غیرایستا (non-stationary) باشد نمی‌توان ممان‌های‌اش را ثابت فرض کرد، وگرنه فرض stationary بودن (یا wide-sense stationary) کافی است والبته فرض غیرمعمول‌ای هم نیست.
اما حرف‌ات درست است. دنیای واقعی معمولا پیچیده‌تر از مدل‌هایی است که علم با آن سر و کار دارد. مدل‌ها ساده‌ترند و در نتیجه دقت‌شان کم‌تر است. اما از طرف دیگر ممکن است اگر شانس داشته باشیم قابل تحلیل باشند و بتوانیم چیزهایی در موردشان بگوییم. آن وقت می‌توانیم با تقریب در مورد دنیای واقعی نیز حرف بزنیم.
به هر حال کار دیگری نمی‌شود کرد. به‌ترین وسیله‌ای که در اختیار داریم همین علم است – که البته بعضی وقت‌ها هم بد جواب نمی‌دهد (مثلا فیزیک نیوتونی دقیق نیست، اما با آن می‌توانیم هواپیما بسازیم. یا مدل‌های مداری استاندارد، سیگنال را به صورت موج در نظر نمی‌گیرد اما باز هم می‌توان بسیاری از مدارات الکترونیک را با استفاده از همان مدل‌ها تحلیل کرد و برای بچه‌ها اسباب‌بازی ساخت!).
آها … تا یادم نرفته بگویم برای این مساله‌ی bandit، اگر مدل احتمالی را بدانیم (در واقع joint distribution) دیگر لازم نیست فرض‌ای مثل iid بودن بکنیم. یعنی با دانستن joint distribution هم مساله قابل حل است.
از مدل‌های ما است. در واقع کاربرد مدل‌ها هم همین است که دنیای واقعی را با تقریب توصیف کنند. تقریب‌ای که دقت را کم می‌کند اما در عوض مساله را تا حدی ساده می‌کند که بتوان در موردش چیزی گفت.
به سولوژن(!): فکر کنم معروف‌ترین اسم به کار رفته در مورد این مسئله multi-armed bandit باشه.
و در ضمن دقت کن که تمام ایده‌هایی که حداقل من می‌شناسم در باره‌ی این مسئله، یه فرض اساسی در باره‌ی infinite horizon بودن دارند که خُب…خیلی با چند سال فرق داره، حتی از دیدگاه مهندسی.
یعنی اصولا وقتی زمان explore کردن‌ت قابل صرف نظر در برابر زمان exploit کردن‌ت نیست، و تازه معمولا راه برگشتی هم -معمولا- وجود نداره، فکر کنم خیلی راه نامعقول‌تری نباشه سراغ مثلا اونی رفتن که از اسمش بیشتر خوشم میاد. وقتی که این همه مقایسه‌شون سخت‌ه که مجبوری با کلی ارفاق با multiarmed bandit مدل‌ش کنی، شاید بهتر باشه که انتخاب کنی.
اصولا زحمت برای بالا بردن دقت از یه جایی به طور وحشتناکی با شیب تندی می‌ره بالا (اگه اصولا از یه حدی بتونه بالاتر بره).
و خُب…طبعا همه‌ی این حرفا در مورد یه مسئله‌ی انسانی‌ه، و الا که خود مسئله‌ی اصلی رو یه بار که رفتیم لاس‌وگاس(!!) با تمام پس‌اندازمون – اعم از ارز(!) و دانش (!!!) – به طور کاملا اکسپریمنتال حل می‌کنیم :دی
مسائلی مثل k-armed bandit و البته مسائلی مثل مساله یافتن دوست دختر بهینه تا زمانی جالب به نظر می رسند که خواص محیطی که پسر داستان ما در اون قرار داره (محیط در اینجا فقط شامل دو دختر میشه) با گذشت زمان تغییر نکنه و به اصطلاح stationary باشه. اما اگر سایر agent های محیط (دخترها) خاصیت یادگیری و تطبیق داشته باشن اونوقت ما به روشهای یادگیری نیاز داریم که هیچ وقت متوقف نشن. یعنی یه جورایی همیشه باشد در حال یادگیری باشیم. مثلا اگر بعد از n مرحله به این نتیجه رسیدیم که دختر A دختر بهینه است، ممکن است رفتار ما با دختر B باعث بشه که بهد از گذشت مدت زمانی دختر B بهینه بشه! پس الگوریتم یادگیری هیچ وقت نباید متوقف بشه. اما سوال اینجاست که در این صورت مساله exploration vs. exploitation را در یک محیط non-stationary چه جوری handle کنیم؟
you`ve forgotten very important point.Your mood.its just you, and what are you looking for ,in a moment
آره درست میگی ایستا بودن برای پیدا کردن ممان کافیه 🙂 ولی فکر نکنم آدما ایستا هم باشن :))
ضمنا اگر joint distribution رو داشتیم که دیگه خیلی وضعمون خوب بود. کلا این نگاه خیلی خنده داره و این مساله پیچیده تر از اونیه که با این محاسبات قابل حل باشه. البته الگوریتم های هوشمند بیولوژیکی مثل اون چیزایی که خودمون باهاش فکر می کنیم از پسش بر میان ولی نه همیشه 😉
From UTS sessions: «never choose a contraversial example to exaplain something of non-controversial nature. People will miss the point!»
عجب بحث جالب توجهی بوده و من غافل بودم. یه کم مثال ها رو عوض می کردین هم به جایی بر نمی خورد . نه؟ مثلا یه تجدید نظر در جنس مثال ها خیال خیلی ها رو راحت می کرد.
Ay Polygamist
this is actually an interesting variant of the multi-armed bandit problem, since there’s a cost associated to switching! let’s say, you’re allowed to get back to a girl at most k times; what’s the optimal algorithm in this case?
به آرش: بله! multi-armed bandit نام معروف‌تری است از n-armed و … . در مورد نوع ساختار نتایج باید بگویم که روش‌ای که به طور ضمنی اشاره کردم، نتیجه‌اش asymptotical نیست، بلکه finite-sample است. در واقع کران‌ای برای regret می‌دهد که خوش‌فرم است و اگر اشتباه نکنم، فرم کران‌اش بهینه است (و البته نه الزاما ثابت‌های‌اش). به طور مشخص‌تر منظورم الگوریتم UCB1 است و مقاله‌ی Auer.
به آرش دیگر: بله! حرف‌تان کاملا درست است. در اینجا فرض شده است که توزیع پاداش iid است. هدف‌ام از این مثال توصیه‌ی یک راه‌حل برای یک مساله‌ی واقعی نبود، بلکه نشان‌دادن اینکه یک مساله‌ی ریز چقدر می‌تواند جزییات داشته باشد بود و البته کمی شوخی‌کردن. یک مساله‌ی دیگری که این وسط اهمیت دارد (جدا از non-stationary بودن یا adversarial بودن طرف مقابل (که البته دومی به احتمال زیاد اولی را نتیجه می‌دهد)، این است که هیچ مفهوم حالت‌ای در نظر نگرفته‌ام. انسان‌ها در شرایط مختلف یک‌جور رفتار نمی‌کنند.
به zita: بله! در نظر نگرفته‌ام. به توضیح‌ای که به «آرش دیگر» داده‌ام مراجعه کنید.
به محمد: و البته باز هم مساله‌ی ساده‌ای نبود. اما یک سوال اساسی برای‌ام پیش می‌آید: منظورت از الگوریتم‌های هوشمند بیولوژیکی چیست و چرا آن‌ها می‌توانند از پس این جور سوال‌ها (حداقل بعضی وقت‌ها) بر بیاید؟ آیا آن‌ها از ریاضی‌ی دیگری استفاده میکنند؟
به آزاد: آن توصیه بستگی دارد به هدف شخص.
به «از زندگی»: سعی می‌کنم دفعه‌ی بعد برعکس بنویسم که عدالت در مجموع وبلاگ رعایت شده باشد.
به یکی از چهارنفر: نه! نیستم!
به محمد: جالب شد! دقیقا چه چیزهایی را می‌دانیم؟ می‌دانیم که توزیع پاداش هر کدام iid است، ولی توزیع را نمی‌شناسیم. در ضمن هر بار تعویض انتخاب یک بازو باعث دریافت هزینه‌ی ثابت‌ای می‌شود. هدف هم بیشینه‌کردن پاداش متوسط (با افق بی‌نهایت) است. درست فهمیده‌ام؟ (چون بیشینه k بار استفاده کردن هر بازو کمی مساله را به نظرم عجیب می‌کند در حالت افق نامحدود و پاداش متوسط. اگر پاداش discounted باشد یا افق محدود باشد (مثلا به M حرکت) برای‌ام قابل فهم است.)
مرسی! از این كه مراعات عدالت را می كنید سپاسگزارم
سلااااااااااااااااااااااااااااااااااااااااااااااااااااااااااااام
كسی با من رفیق میشه
همه مثال ها رو خوندم و خیلی جالب بود ، اما در آخر حق با اون دوستمونه که گفته هوش بیولوژیکی خیلی بهتر و سریعتر از پس این مسدله بخصوص ( کمینگی تاسف در انتخاب دوست دختر / پسر ) بر میاد .
یکی از دلایلش اینه که همونطور که سولوین گفته مدل ها همه واقعیت نیستند .
در این مورد بخصوص توصیه من اینه که جز اونایی که در این زمینه متخصصن بقیه به همون هوش بیولوژیکی خودشون اکتفا کنن .