Mathematical Musings
Robert Aumann
که اصلا دکتراش رو در زمینه نظریه گره ها گرفته. بعدا به خاطر کارهایی که در نظریه بازی ها انجام داد، نوبل اقتصاد گرفت.
و یکی دو نفر دیگه که اون ها هم عموما در زمینه نظریه بازی ها کار کردند.
که اصلا دکتراش رو در زمینه نظریه گره ها گرفته. بعدا به خاطر کارهایی که در نظریه بازی ها انجام داد، نوبل اقتصاد گرفت.
و یکی دو نفر دیگه که اون ها هم عموما در زمینه نظریه بازی ها کار کردند.
این بزرگوار خیلی آدم عجیبیه از نظر من. یادمه که من همین طوری خیلی اتفاقی از ویکی پدیا پیداش کردم وقتی داشتم در مورد فرض rationality و اینا تحقیق میکردم. بعد که زندگی نامه و ایناشو خوندم دیدم نه پسر واقعا آدم جالبیه یک یهودی مخلص 🙂
و الان فهمیدم برنده جایزه نوبل.
الان که رفتم دیدم پشمام چقدر یه زمانی تو نظریه بازی ها عمیق شده بودم.
این پست من بود که قبلا راجع بهش نوشته بودم:
https://news.1rj.ru/str/SingularThinker/31
و الان فهمیدم برنده جایزه نوبل.
الان که رفتم دیدم پشمام چقدر یه زمانی تو نظریه بازی ها عمیق شده بودم.
این پست من بود که قبلا راجع بهش نوشته بودم:
https://news.1rj.ru/str/SingularThinker/31
Telegram
Singular Thinker
آقای Robert Aumman که در تصویر مشاهده میکنید سال 1930 در خانوادهای یهودی در شهر فرانکفورت آلمان بدنیا اومد و در 8 سالگی دو هفته قبل از "شب بلورین" یا "شب شیشههای شکسته" (شروع حملهی نازیها به یهودیان) به آمریکا سفر میکند. دورهی لیسانس رو در رشتهی…
❤6
Google Gemini:
Free Pro Plan for Students.
Free for 1 year. Get unlimited chats, image uploads, and quiz generations with more access to our 2.5 Pro model, Deep Research, and Audio Overviews, plus 2 TB of storage. Just for Students. Offer ends 9 December 2025.
https://gemini.google/tw/students/#:~:text=Google%20Gemini%3A,plus%202%20TB%20of%20storage.
پ.ن: نمیدونم واسه دانشگاه های ایران هم کار میکنه یا نه.
@SingularThinker
Free Pro Plan for Students.
Free for 1 year. Get unlimited chats, image uploads, and quiz generations with more access to our 2.5 Pro model, Deep Research, and Audio Overviews, plus 2 TB of storage. Just for Students. Offer ends 9 December 2025.
https://gemini.google/tw/students/#:~:text=Google%20Gemini%3A,plus%202%20TB%20of%20storage.
پ.ن: نمیدونم واسه دانشگاه های ایران هم کار میکنه یا نه.
@SingularThinker
Gemini
Gemini - 深獲學生喜愛的 Google AI 學習好夥伴
從寫作業的好幫手，到製作影片的小助理，Gemini 在校園內外都是你的得力助手。訂閱 Google AI Pro 方案，即可享有更多 Gemini 功能，立即開始免費試用！
❤2
Singular Thinker
نمیدونم موفق بودم که پیام اصلی کار رو بدون وارد شدن به جزئیات ارائه کنم یا نه ولی این طوری در نظر بگیرید که برای فهمیدن اینکه آیا داده شما ساختارمند هست یا نه و به طور بالقوه میتونه Generalization خوبی داشته باشه یا نه ایده آندره اس این بود که بیایم ببینیم…
User-unfriendly introduction to "user-friendly introduction to PAC-Bayes bounds"
1/n
خب بحث رو ازینجا شروع کنیم که به طور سنتی وقتی شما n تا مشاهده/نمونه از n تا متغییر تصادفی مستقل و هم توزیع (iid) داری که توزیعشون رو نمیدونی علم آمار و احتمال یه سری ابزار در اختیارت قرار میده که یه چیزایی بتونی در مورد میانگین این n تا مشاهده و امید ریاضی اون متغییرهای تصادفی بگی.
اون چیزی که به طور معمول به اکثر ماها تو دانشگاه تدریس میکردن قانون اعداد بزرگ بوده که میگه آقا میانگین این n تا مشاهده(realization) از متغییرهای هم توزیع و مستقل به امیدریاضی اون متغییرهای تصادفی میل میکنه، البته با کمی تساهل.(اینجا دیگه وارد تفاوت نسخه قوی و ضعیفش نشدم و بعدشم شرط وجود امید ریاضی همیشه برقرار نیست.تو تصویر فرق نسخه ضعیف و قوی رو میبینید.)
جالبه که به قول امیررضا تو این کلیپ قانون اعداد بزرگ جایی از احتمالات هست که ما از دنیای انتزاعی که ساختیم بیرون میایم و میتونیم بریم آزمایش انجام بدیم اما یه بدی ای که قانون اعداد بزرگ داره اینه که مثل وعده بهشت دادن در آخرته، حالا اون دنیا رو کی دیده اصلا؟ اینجا هم همینه ماجرا.
اون حدی که روی n میگیریم و میلش میدیم به بی نهایت باعث میشه تحلیل ما مجانبی/حدی باشه. و هر وقت شما به بی نهایت رسیدی برای ما دست تکون بده یه بوقم بزن .
ولی حالا یه سری ابزارهای دیگه هم هست که میشه ازشون استفاده کرد و تحلیل غیرمجانبی/حدی ارائه کرد و بهشون میگن concentration inequalities یا ناتساوی های تمرکزی. در واقع به کمک این ناتساوی ها میشه انحراف میانگین از امیدریاضی رو به طور کمی برای هر تعداد متغییر تصادفی دلخواه اندازه گیری کنیم.(قبلا یه مقدار راجع به همین چیزا تو این پیام صحبت کردم و اینم لینک مقاله ای که دارم در موردش تو پیام صحبت میکنم.)
بگذریم خلاصه، این ناتساوی ها ابزار دست کسایی هستن که learning theory کار میکنن. شما معمولا هر جایی وارد بحث های نظری یادگیری ماشین میشی که میخوای یه کران بالا برای خطا اثبات کنی معمولا از این ابزار استفاده میکنی و حقیقتش اینه که استفاده ازش خیلی سخت نیست. مثلا فرض کن که شما میخوای یه مسئله طبقه بندی دوتایی رو حل بکنی و بهت n تا نمونه مستقل و هم توزیع به همراه طبقه مربوطه هر کدوم دادن و گفتن که بفرما و یه طبقه بند برای ما بساز که بتونه هر عکس جدیدی که از همون توزیع بیاد رو تا حد خوبی به صورت درست طبقه بندی کنه.
شما هم میای میگی خیلی خب من میام اول یه کلاسی از توابع رو در نظر میگیرم مثلا توابع چند جمله ای از درجه p و بعد یه جوری یه تابعی رو مدلسازی میکنم که عکس رو بگیره و طبقه اون عکس رو برگردونه و حالا باید اون ضرایب اون چندجمله ای و یا به اصطلاح پارامترهای مدل رو طوری پیدا کنم که خطا کمینه بشه. یعنی اینکه یه تابع خطا تعریف میکنم در راحت ترین حالت اگه طبقه بند پیشنهادی تابع من با طبقه اصلی اون عکسه یکی بود خطام صفره در غیر این صورت خطام یکه. بعد شما میگی خب میرم یه مسئله بهینه سازی حل میکنم که پارامترهای مدلم رو طوری پیدا کنم که میانگین خطام بر حسب n تا داده ای که دارم رو کمینه کنم.(به این الگوریتم میگن ERM که مخفف empirical risk minimization عه)
خب تا اینجا خیلی هم عالی، خسته هم نباشید. ولی یکی پیدا میشه میگه اقا این چیزی که شما حل کردی و پیدا کردی و اون چیزی که ما گفتیم که یکی نبود. شما پارامترهایی رو پیدا کردی که خطای کمینه رو برای این n تا مشاهده ای که بهت دادیم رو داره(با فرض این که شما بهینه سازیت رو درست حل کردی) ولی من ازت خواستم خطای کمینه روی هر عکسی که ازون توزیع میاد داشته باشه نه صرفا برای n تا عکس خاص.
به عبارت دیگه، از کجا معلوم که پارامترهای مدل شما صرفا نیومده یه سری اطلاعات در مورد همون n تا عکس خاص رو حفظ نکرده باشه به جای اینکه یه سری اطلاعات در مورد توزیع شرطی E[Y|X] یاد گرفته باشه. اینجاست که مفهوم حفظ کردن (memorization) در مقابل تعمیم پذیری (generalization) مطرح میشه.
آیا لزومی داره که اگر مدلی برای n تا عکس خوب کار کنه برای هر عکسی از همون توزیع هم خوب کار کنه؟ جوابش اینه که والا حلوای تن تنانی تا نخوری ندانی. اینجا هم تا زمانی که ثابت نکنی نه.
حالا چی رو دوست داری ثابت کنی؟ میخوای ثابت کنی که اگر تو بیای و بر حسب n تا مشاهده از متغییرهای مستقل و هم توزیع پارامترهایی رو پیدا کنی که میانگین خطا رو واسه این n تا مشاهده کمینه کنن، اون پارامتر امید ریاضی خطای کمی هم خواهد داشت برای هر مشاهده جدیدی که از همون توزیع بیاد.
اینجاست که میشه دید پس احتمالا باید از ناتساوی های تمرکزی استفاده کنیم.
اما ادامه اش باشه برای متن بعدی چون همین طوریش حس میکنم که خیلی زیاد حرف زدم.
#note #learning_theory
@SingularThinker
1/n
خب بحث رو ازینجا شروع کنیم که به طور سنتی وقتی شما n تا مشاهده/نمونه از n تا متغییر تصادفی مستقل و هم توزیع (iid) داری که توزیعشون رو نمیدونی علم آمار و احتمال یه سری ابزار در اختیارت قرار میده که یه چیزایی بتونی در مورد میانگین این n تا مشاهده و امید ریاضی اون متغییرهای تصادفی بگی.
اون چیزی که به طور معمول به اکثر ماها تو دانشگاه تدریس میکردن قانون اعداد بزرگ بوده که میگه آقا میانگین این n تا مشاهده(realization) از متغییرهای هم توزیع و مستقل به امیدریاضی اون متغییرهای تصادفی میل میکنه، البته با کمی تساهل.(اینجا دیگه وارد تفاوت نسخه قوی و ضعیفش نشدم و بعدشم شرط وجود امید ریاضی همیشه برقرار نیست.تو تصویر فرق نسخه ضعیف و قوی رو میبینید.)
جالبه که به قول امیررضا تو این کلیپ قانون اعداد بزرگ جایی از احتمالات هست که ما از دنیای انتزاعی که ساختیم بیرون میایم و میتونیم بریم آزمایش انجام بدیم اما یه بدی ای که قانون اعداد بزرگ داره اینه که مثل وعده بهشت دادن در آخرته، حالا اون دنیا رو کی دیده اصلا؟ اینجا هم همینه ماجرا.
اون حدی که روی n میگیریم و میلش میدیم به بی نهایت باعث میشه تحلیل ما مجانبی/حدی باشه. و هر وقت شما به بی نهایت رسیدی برای ما دست تکون بده یه بوقم بزن .
ولی حالا یه سری ابزارهای دیگه هم هست که میشه ازشون استفاده کرد و تحلیل غیرمجانبی/حدی ارائه کرد و بهشون میگن concentration inequalities یا ناتساوی های تمرکزی. در واقع به کمک این ناتساوی ها میشه انحراف میانگین از امیدریاضی رو به طور کمی برای هر تعداد متغییر تصادفی دلخواه اندازه گیری کنیم.(قبلا یه مقدار راجع به همین چیزا تو این پیام صحبت کردم و اینم لینک مقاله ای که دارم در موردش تو پیام صحبت میکنم.)
بگذریم خلاصه، این ناتساوی ها ابزار دست کسایی هستن که learning theory کار میکنن. شما معمولا هر جایی وارد بحث های نظری یادگیری ماشین میشی که میخوای یه کران بالا برای خطا اثبات کنی معمولا از این ابزار استفاده میکنی و حقیقتش اینه که استفاده ازش خیلی سخت نیست. مثلا فرض کن که شما میخوای یه مسئله طبقه بندی دوتایی رو حل بکنی و بهت n تا نمونه مستقل و هم توزیع به همراه طبقه مربوطه هر کدوم دادن و گفتن که بفرما و یه طبقه بند برای ما بساز که بتونه هر عکس جدیدی که از همون توزیع بیاد رو تا حد خوبی به صورت درست طبقه بندی کنه.
شما هم میای میگی خیلی خب من میام اول یه کلاسی از توابع رو در نظر میگیرم مثلا توابع چند جمله ای از درجه p و بعد یه جوری یه تابعی رو مدلسازی میکنم که عکس رو بگیره و طبقه اون عکس رو برگردونه و حالا باید اون ضرایب اون چندجمله ای و یا به اصطلاح پارامترهای مدل رو طوری پیدا کنم که خطا کمینه بشه. یعنی اینکه یه تابع خطا تعریف میکنم در راحت ترین حالت اگه طبقه بند پیشنهادی تابع من با طبقه اصلی اون عکسه یکی بود خطام صفره در غیر این صورت خطام یکه. بعد شما میگی خب میرم یه مسئله بهینه سازی حل میکنم که پارامترهای مدلم رو طوری پیدا کنم که میانگین خطام بر حسب n تا داده ای که دارم رو کمینه کنم.(به این الگوریتم میگن ERM که مخفف empirical risk minimization عه)
خب تا اینجا خیلی هم عالی، خسته هم نباشید. ولی یکی پیدا میشه میگه اقا این چیزی که شما حل کردی و پیدا کردی و اون چیزی که ما گفتیم که یکی نبود. شما پارامترهایی رو پیدا کردی که خطای کمینه رو برای این n تا مشاهده ای که بهت دادیم رو داره(با فرض این که شما بهینه سازیت رو درست حل کردی) ولی من ازت خواستم خطای کمینه روی هر عکسی که ازون توزیع میاد داشته باشه نه صرفا برای n تا عکس خاص.
به عبارت دیگه، از کجا معلوم که پارامترهای مدل شما صرفا نیومده یه سری اطلاعات در مورد همون n تا عکس خاص رو حفظ نکرده باشه به جای اینکه یه سری اطلاعات در مورد توزیع شرطی E[Y|X] یاد گرفته باشه. اینجاست که مفهوم حفظ کردن (memorization) در مقابل تعمیم پذیری (generalization) مطرح میشه.
آیا لزومی داره که اگر مدلی برای n تا عکس خوب کار کنه برای هر عکسی از همون توزیع هم خوب کار کنه؟ جوابش اینه که والا حلوای تن تنانی تا نخوری ندانی. اینجا هم تا زمانی که ثابت نکنی نه.
حالا چی رو دوست داری ثابت کنی؟ میخوای ثابت کنی که اگر تو بیای و بر حسب n تا مشاهده از متغییرهای مستقل و هم توزیع پارامترهایی رو پیدا کنی که میانگین خطا رو واسه این n تا مشاهده کمینه کنن، اون پارامتر امید ریاضی خطای کمی هم خواهد داشت برای هر مشاهده جدیدی که از همون توزیع بیاد.
اینجاست که میشه دید پس احتمالا باید از ناتساوی های تمرکزی استفاده کنیم.
اما ادامه اش باشه برای متن بعدی چون همین طوریش حس میکنم که خیلی زیاد حرف زدم.
#note #learning_theory
@SingularThinker
Telegram
Probability Theory & Statistics
❤3
User-unfriendly introduction to "user-friendly introduction to PAC-Bayes bounds"
2/n
چیزی که باهاش متن قبلی رو تموم کردیم این بود که برای مدل یادگیری ماشینیمون میخوایم یه گارانتی(کران بالا) برای امید ریاضی خطا مدل مون در بیاریم و خیالمون رو راحت کنیم ولی شاید این نکته برای شما یه خورده عجیب به نظر برسه چون در عمل خیلی استفاده نمیشه. چرا؟ چون اثبات چنین کران بالایی در حالت کلی کار سختی به حساب میاد که با هم تو ادامه این متن میریم ببینیم که چرا این طوریه.
اما یه کاری که تو یادگیری ماشین در عمل به جای این کار میکنن اینه که شما میای و مجموعه دادگانت رو حداقل دو قسمت میکنی.
یه قسمتی رو برای آموزش یا همون بدست آوردن پارامترهای مدلت استفاده میکنی و از قسمت دیگه برای ارزیابی یا تست کردن مدل استفاده میکنی و این طوری عملا یه برآورد نااریبی از امیدریاضی خطات داری و طبیعتا دوباره طبق قانون اعداد بزرگ هر چی تعداد دادگان مجموعه تستت بیشتر باشه تخمین امیدریاضی ات دقیقتر میشه.
آآماا مشکل روش اول چیه که مجبور میشیم بریم سراغ این روش و عملا دیتاهای با ارزشمون رو تقسیم کنیم؟ چرا از همه اش برای آموزش استفاده نکنیم؟
نکته اینجاست که میشه به سادگی با در نظرگرفتن یه تابع دلخواه از مجموعه توابع چندجمله ای از درجه p که داشتیم
خیلی راحت بیایم و یه کران بالای خوشگل برای خطای بدست بیاریم و برای این کار کافیه که از Hoeffding Lemma و Chernoff's inequality استفاده کنیم.( برای اطلاعات بیشتر بخش ۱.۱.۲ این مقاله آموزشی که اسمشو رو عنوان متن هم گذاشتم ببینید.)
خب پس مشکل چیه؟ تو که میگی خیلی ساده است دو تا ناتساوی داری و تو کمتر از یه صفحه یه کران بالا در میاری، پس اسکل کردی مارو؟ د نه د. مشکل اینجاست که گفتم این کران بالای خطا برای پارامتری کار میکنه که از قبل فیکس شده باشه و به مجموعه دادگانت مرتبط نباشه. اگه پارامترهات خودش وابسته باشه به مشاهداتت دیگه شرط مستقل بودن متغییرهای تصادفی ای که براشون میای از این ناتساوی های تمرکزی استفاده میکین رو نقض میکنی. و سردردت ندم وقتی تو آمار و احتمال شنیدی متغییرهای تصادفی داری که بهم وابسته ان دستات رو بذار رو گوشات تا میتونی جیغ بزن و زیگزاگی راه برو حتی اگه نمیدی دونی چرا :)))
پس حالا یعنی چه کنیم؟ برای اینکه بتونیم چیز معناداری برای خطای پارامترهای حاصل از ERM بدست میاد به جای در نظر گرفتن یه پارامتر خاص و بدست آوردن یه کران بالا برای اون باید بدبین باشیم و کران بالای خطا برای بدترین پارامتر تو مجموعه پارامترهامون رو پیدا کنیم و حالا مطمئنیم که خطای پارامتر ERM قطعا ازون کمتره.
ولی اینجاست که مشکل وارد میشه که این در حالت کلی کار آسونی نیست. میتونی تصور کنی که چند تا تابع چند جمله ای از درجه p داریم؟ بی نهایت تا.
حالا باید حساب کنیم کران بالا برای بدترین تابع چقدره؟ چطوری حساب کنیم؟ در حالت کلی ایده سر راستی نداریم.
يه راه اینه که اگر مجموعه توابعی که اون اول انتخاب کردیم محدود بود بیایم جمع بزنیم خطاهای تک تک اون تابع ها رو و بعد یه کران بالا در بیاریم.خب مشکلش چیه؟
نکته اینه که به کران بالات به صورت خطی با سایز مجموعه تابع هات مرتبطه و این یعنی باختی. چون که اگه سایز مجموعه تابع های ممکنت رو کوچیک بکنی درسته تو جمع خیلی چیزی رو از دست نمیدی ولی از اون طرف میشه حدس زد که خطای هر کدوم ازون ها در حالت کلی میتونه بزرگ باشه و از طرف دیگه اگه سایز مجموعه تابع هات رو بزرگ کنیی یه عدد خیلی بزرگ به خاطر جمع روی همه این توابع تو کران بالات داری که عملا کران بالات یه عدد خیلی بزرگ و غیرقابل استفاده میشه.
در زندگی عادی و به طور روزمره همین طور که اصن تو مثال قبلی هم دیدیم ما اصن تعداد توابعون غالبا نامحدوده و این فرض محدود بودن تخیلی محسوب میشه. پس باید یه فکری به حال این داستان بکنیم.
ازین جا به بعد دو تا راه داریم یا بر اینکه از الگوریتم ERM استفاده کنیم اصرار بکنیم و سختی درآوردن کران بالا در حالت نامحدود رو به جون بخریم یا رویکردمون رو عوض کنیم و بگیم حالا کی گفته ERM وحی منزله شاید چیز دیگه ای هم باشه که خوب باشه. راه اول راهی بود که Vapnik و Chervonenkis میرن و شروع میکن با اضافه کردن یه سری فرضیاتی (نامعقول) به مسئله فرض محدود بودن فضای پارامترها رو تخفیف میدن و اینجاست که VC-dim برای اندازه گیری میزان پیچیدگی فضای پارامترها متولد میشه. که بعدها تبدیل به Radamacher complexity میشه و ...
اما این قصه پیچیدگی های فنی داره که مشکل آفرینه. یعنی یا یه سری فرضیاتی داره که محقق شدنی نیست و اگه در حالت کلی هم داره چیزی میگه اون چیز اونقدر پیچیده و انتزاعیه که در عمل نمیشه حسابش کرد.
#note #learning_theory
@SingularThinker
2/n
چیزی که باهاش متن قبلی رو تموم کردیم این بود که برای مدل یادگیری ماشینیمون میخوایم یه گارانتی(کران بالا) برای امید ریاضی خطا مدل مون در بیاریم و خیالمون رو راحت کنیم ولی شاید این نکته برای شما یه خورده عجیب به نظر برسه چون در عمل خیلی استفاده نمیشه. چرا؟ چون اثبات چنین کران بالایی در حالت کلی کار سختی به حساب میاد که با هم تو ادامه این متن میریم ببینیم که چرا این طوریه.
اما یه کاری که تو یادگیری ماشین در عمل به جای این کار میکنن اینه که شما میای و مجموعه دادگانت رو حداقل دو قسمت میکنی.
یه قسمتی رو برای آموزش یا همون بدست آوردن پارامترهای مدلت استفاده میکنی و از قسمت دیگه برای ارزیابی یا تست کردن مدل استفاده میکنی و این طوری عملا یه برآورد نااریبی از امیدریاضی خطات داری و طبیعتا دوباره طبق قانون اعداد بزرگ هر چی تعداد دادگان مجموعه تستت بیشتر باشه تخمین امیدریاضی ات دقیقتر میشه.
آآماا مشکل روش اول چیه که مجبور میشیم بریم سراغ این روش و عملا دیتاهای با ارزشمون رو تقسیم کنیم؟ چرا از همه اش برای آموزش استفاده نکنیم؟
نکته اینجاست که میشه به سادگی با در نظرگرفتن یه تابع دلخواه از مجموعه توابع چندجمله ای از درجه p که داشتیم
خیلی راحت بیایم و یه کران بالای خوشگل برای خطای بدست بیاریم و برای این کار کافیه که از Hoeffding Lemma و Chernoff's inequality استفاده کنیم.( برای اطلاعات بیشتر بخش ۱.۱.۲ این مقاله آموزشی که اسمشو رو عنوان متن هم گذاشتم ببینید.)
خب پس مشکل چیه؟ تو که میگی خیلی ساده است دو تا ناتساوی داری و تو کمتر از یه صفحه یه کران بالا در میاری، پس اسکل کردی مارو؟ د نه د. مشکل اینجاست که گفتم این کران بالای خطا برای پارامتری کار میکنه که از قبل فیکس شده باشه و به مجموعه دادگانت مرتبط نباشه. اگه پارامترهات خودش وابسته باشه به مشاهداتت دیگه شرط مستقل بودن متغییرهای تصادفی ای که براشون میای از این ناتساوی های تمرکزی استفاده میکین رو نقض میکنی. و سردردت ندم وقتی تو آمار و احتمال شنیدی متغییرهای تصادفی داری که بهم وابسته ان دستات رو بذار رو گوشات تا میتونی جیغ بزن و زیگزاگی راه برو حتی اگه نمیدی دونی چرا :)))
پس حالا یعنی چه کنیم؟ برای اینکه بتونیم چیز معناداری برای خطای پارامترهای حاصل از ERM بدست میاد به جای در نظر گرفتن یه پارامتر خاص و بدست آوردن یه کران بالا برای اون باید بدبین باشیم و کران بالای خطا برای بدترین پارامتر تو مجموعه پارامترهامون رو پیدا کنیم و حالا مطمئنیم که خطای پارامتر ERM قطعا ازون کمتره.
ولی اینجاست که مشکل وارد میشه که این در حالت کلی کار آسونی نیست. میتونی تصور کنی که چند تا تابع چند جمله ای از درجه p داریم؟ بی نهایت تا.
حالا باید حساب کنیم کران بالا برای بدترین تابع چقدره؟ چطوری حساب کنیم؟ در حالت کلی ایده سر راستی نداریم.
يه راه اینه که اگر مجموعه توابعی که اون اول انتخاب کردیم محدود بود بیایم جمع بزنیم خطاهای تک تک اون تابع ها رو و بعد یه کران بالا در بیاریم.خب مشکلش چیه؟
نکته اینه که به کران بالات به صورت خطی با سایز مجموعه تابع هات مرتبطه و این یعنی باختی. چون که اگه سایز مجموعه تابع های ممکنت رو کوچیک بکنی درسته تو جمع خیلی چیزی رو از دست نمیدی ولی از اون طرف میشه حدس زد که خطای هر کدوم ازون ها در حالت کلی میتونه بزرگ باشه و از طرف دیگه اگه سایز مجموعه تابع هات رو بزرگ کنیی یه عدد خیلی بزرگ به خاطر جمع روی همه این توابع تو کران بالات داری که عملا کران بالات یه عدد خیلی بزرگ و غیرقابل استفاده میشه.
در زندگی عادی و به طور روزمره همین طور که اصن تو مثال قبلی هم دیدیم ما اصن تعداد توابعون غالبا نامحدوده و این فرض محدود بودن تخیلی محسوب میشه. پس باید یه فکری به حال این داستان بکنیم.
ازین جا به بعد دو تا راه داریم یا بر اینکه از الگوریتم ERM استفاده کنیم اصرار بکنیم و سختی درآوردن کران بالا در حالت نامحدود رو به جون بخریم یا رویکردمون رو عوض کنیم و بگیم حالا کی گفته ERM وحی منزله شاید چیز دیگه ای هم باشه که خوب باشه. راه اول راهی بود که Vapnik و Chervonenkis میرن و شروع میکن با اضافه کردن یه سری فرضیاتی (نامعقول) به مسئله فرض محدود بودن فضای پارامترها رو تخفیف میدن و اینجاست که VC-dim برای اندازه گیری میزان پیچیدگی فضای پارامترها متولد میشه. که بعدها تبدیل به Radamacher complexity میشه و ...
اما این قصه پیچیدگی های فنی داره که مشکل آفرینه. یعنی یا یه سری فرضیاتی داره که محقق شدنی نیست و اگه در حالت کلی هم داره چیزی میگه اون چیز اونقدر پیچیده و انتزاعیه که در عمل نمیشه حسابش کرد.
#note #learning_theory
@SingularThinker
arXiv.org
User-friendly introduction to PAC-Bayes bounds
Aggregated predictors are obtained by making a set of basic predictors vote according to some weights, that is, to some probability distribution.
Randomized predictors are obtained by sampling...
Randomized predictors are obtained by sampling...
👍3
User-unfriendly introduction to "user-friendly introduction to PAC-Bayes bounds"
3/3
اما اون راه حل دوم چیه؟ اونجا جاییه که PAC-Bayes Bounds در سال 1997-8 متولد شدن. این کرانها با یه تغییر رویکرد اساسی نسبت به رویکرد ERM بوجود میان. یعنی شما به جای اینکه دنبال یه پارامتر خاصی بگردی و بعد کران بالای خطا برای طبقه بند با استفاده از اون پارامتر پیدا بکنی میگی چی میشه اگه من یه توزیع احتمالی روی مجموعه پارامترها داشته باشم و بیایم برای یه نمونه از اون توزیع کران خطا پیدا کنم. اینجاست که مشخص میشه چرا اسم Bayes رو میذارن رو این روش. دیگه از آمار فراوانی گرایانه خارج میشیم و وارد آمار بیزی میشیم. دیگه پارامترهای مدل قطعی یا deterministic نیستند و خودشون تصادفی هستند و دارن از یه تابع توزیعی میان که حالا خوبیش اینه که کنترلش دست ماست. و این طوریه که این باندها متولد میشن.
و اسپویلر آلرت⚠️:این کران های بالا در خیلی از موارد قابل محاسبه و قابل قبول هستند
3/3
اما اون راه حل دوم چیه؟ اونجا جاییه که PAC-Bayes Bounds در سال 1997-8 متولد شدن. این کرانها با یه تغییر رویکرد اساسی نسبت به رویکرد ERM بوجود میان. یعنی شما به جای اینکه دنبال یه پارامتر خاصی بگردی و بعد کران بالای خطا برای طبقه بند با استفاده از اون پارامتر پیدا بکنی میگی چی میشه اگه من یه توزیع احتمالی روی مجموعه پارامترها داشته باشم و بیایم برای یه نمونه از اون توزیع کران خطا پیدا کنم. اینجاست که مشخص میشه چرا اسم Bayes رو میذارن رو این روش. دیگه از آمار فراوانی گرایانه خارج میشیم و وارد آمار بیزی میشیم. دیگه پارامترهای مدل قطعی یا deterministic نیستند و خودشون تصادفی هستند و دارن از یه تابع توزیعی میان که حالا خوبیش اینه که کنترلش دست ماست. و این طوریه که این باندها متولد میشن.
و اسپویلر آلرت⚠️:این کران های بالا در خیلی از موارد قابل محاسبه و قابل قبول هستند
👍2
Singular Thinker
نمیدونم موفق بودم که پیام اصلی کار رو بدون وارد شدن به جزئیات ارائه کنم یا نه ولی این طوری در نظر بگیرید که برای فهمیدن اینکه آیا داده شما ساختارمند هست یا نه و به طور بالقوه میتونه Generalization خوبی داشته باشه یا نه ایده آندره اس این بود که بیایم ببینیم…
میدونم توضیح دادن ریاضی با متن کار خیلی جالبی نیست ولی صرفا چون این PAC-Bayes boundsها به نظرم خیلی موضوع جالبی بود و یه دید باحالی به مسائل میداد خواستم یه تیزر طور برم و توصیه کنم که User-friendly introduction to PAC-Bayes bounds
از آقا Pierre Alquier رو بخونید و لذتشو ببرید. (حداقل فصل اولش رو)
یه مشکلی که من موقع تحصیل ارشدم داشتم این بود که کسایی که یادگیری ماشین تدریس میکردن مفاهیم نظری رو مسلط نبودن و بنابراین خوب هم تدریسش نمیکردن و اصن من نمیدونستم که این چیزا چین و برای همین کلی سوال داشتم که اصن نمیدونستم باید کجا دنبال جوابش بگردم.
تو شریف فک کنم کمی اوضاع بهتر باشه و یه سری درس تئوری تدریس بشه هنوز.
خلاصه هدف این بود که سر نخ کنجکاوی بدم و گرنه میدونم خیلی سخته دنبال کردن یه متن برای فهمیدن یه سری معادله.
از آقا Pierre Alquier رو بخونید و لذتشو ببرید. (حداقل فصل اولش رو)
یه مشکلی که من موقع تحصیل ارشدم داشتم این بود که کسایی که یادگیری ماشین تدریس میکردن مفاهیم نظری رو مسلط نبودن و بنابراین خوب هم تدریسش نمیکردن و اصن من نمیدونستم که این چیزا چین و برای همین کلی سوال داشتم که اصن نمیدونستم باید کجا دنبال جوابش بگردم.
تو شریف فک کنم کمی اوضاع بهتر باشه و یه سری درس تئوری تدریس بشه هنوز.
خلاصه هدف این بود که سر نخ کنجکاوی بدم و گرنه میدونم خیلی سخته دنبال کردن یه متن برای فهمیدن یه سری معادله.
👍2
Singular Thinker
User-unfriendly introduction to "user-friendly introduction to PAC-Bayes bounds" 1/n خب بحث رو ازینجا شروع کنیم که به طور سنتی وقتی شما n تا مشاهده/نمونه از n تا متغییر تصادفی مستقل و هم توزیع (iid) داری که توزیعشون رو نمیدونی علم آمار و احتمال یه سری ابزار…
داشتم میدیدم این چیزایی که دیشب نوشتم واقعا مدیوم و مدل انتقالش user-friendly نبود اصلا😂 تبدیلشون کردم به user-unfriendly :)))
Please RT - Open PhD position in my group at the Donders Center for Neuroscience, Radboud University.
We're looking for a PhD candidate interested in developing theories of learning in neural networks.
Applications are open until October 20th.
Info: https://www.ru.nl/en/working-at/job-opportunities/phd-position-theory-of-learning-in-artificial-and-biologically-inspired-neural-networks
🔗 Alessandro Ingrosso (@ai_ngrosso)
#phd_position
@SingularThinker
We're looking for a PhD candidate interested in developing theories of learning in neural networks.
Applications are open until October 20th.
Info: https://www.ru.nl/en/working-at/job-opportunities/phd-position-theory-of-learning-in-artificial-and-biologically-inspired-neural-networks
🔗 Alessandro Ingrosso (@ai_ngrosso)
#phd_position
@SingularThinker
www.ru.nl
Job opportunity expired | Radboud University
Thank you for your interest in working at Radboud University. We are no longer taking applications for this job.
👍7❤1
Singular Thinker
Please RT - Open PhD position in my group at the Donders Center for Neuroscience, Radboud University. We're looking for a PhD candidate interested in developing theories of learning in neural networks. Applications are open until October 20th. Info: ht…
دیسلایک راجع به این پوزیشن خاصه که گذاشتم یا اعتراض به اینکه چرا پوزیشن میذارم؟🤔چون من نمیشناختم طرفو ولی دیدم توییت کرده ددلاینشم ۸ روز دیگه است گفتم بفرستم.
پ.ن: خلاصه اگه چیزی میدونید به ما هم بگید. من دوست دارم بازخورد بگیرم از شمایی که براتون مهمه و ریاکت میذارید. اگه خواستید لینک ناشناسم هست به هر حال.
پ.ن: خلاصه اگه چیزی میدونید به ما هم بگید. من دوست دارم بازخورد بگیرم از شمایی که براتون مهمه و ریاکت میذارید. اگه خواستید لینک ناشناسم هست به هر حال.
❤9
Singular Thinker
داشتم میدیدم این چیزایی که دیشب نوشتم واقعا مدیوم و مدل انتقالش user-friendly نبود اصلا😂 تبدیلشون کردم به user-unfriendly :)))
YouTube
Pierre Alquier (ESSEC) - PAC Bayes: introduction and overview
Abstract: The PAC-Bayesian theory provides tools to understand the accuracy of Bayes-inspired algorithms that learn probability distributions on parameters. This theory was initially developed by McAllester about 20 years ago, and applied successfully to…
Forwarded from a pessimistic researcher (Kc)
Internship in AI @ MPI
——————————————
🌍 Ready for a transformative summer in Germany? Apply NOW for the CaCTüS Internship! 🇩🇪🌞
CaCTüS (Computation & Cognition Tübingen Summer Internship) is a fully funded, 3-month research internship taking place in summer 2026, hosted by the Max Planck Institute for Biological Cybernetics, the Tübingen AI Center and us.
🌱 Why CaCTüS? You’ll dive into groundbreaking projects in hashtag#MachineLearning, hashtag#TheoreticalNeuroscience, hashtag#BehavioralExperiments, and hashtag#DataAnalysis, surrounded by experts in hashtag#Tübingen and hashtag#Stuttgart, Germany.
https://www.projects.tuebingen.mpg.de/
——————————————
🌍 Ready for a transformative summer in Germany? Apply NOW for the CaCTüS Internship! 🇩🇪🌞
CaCTüS (Computation & Cognition Tübingen Summer Internship) is a fully funded, 3-month research internship taking place in summer 2026, hosted by the Max Planck Institute for Biological Cybernetics, the Tübingen AI Center and us.
🌱 Why CaCTüS? You’ll dive into groundbreaking projects in hashtag#MachineLearning, hashtag#TheoreticalNeuroscience, hashtag#BehavioralExperiments, and hashtag#DataAnalysis, surrounded by experts in hashtag#Tübingen and hashtag#Stuttgart, Germany.
https://www.projects.tuebingen.mpg.de/
💅4