پیچیدگی چیست؟

بسیاری از دانشمندان معتقدند توضیح های ساده تر بهتر اند. اصل تیغ اُکام که توسط اکام در سال 1200 میلادی بیان شد در همین مورد است:" در میان فرضیات رقیب، فرضیه ای که حداقل پیش فرض ها را دارد باید انتخاب شود."اما تعریف "سادگی" خود امر ساده ای نیست. از سادگی آنتولوژیک (Ontological)گرفته (تعداد کمتر موجودیت ها) تا سادگی نحوی(Syntactic) (کم بودن تعداد پیش فرض های نظری) تعریف های زیادی ارائه شده اند اما دقیقا مشخص نیست چگونه این فرم های مختلف سادگی را باید با هم ارتباط داد. بیشتر استدلال ها در واقع برای توجیه اصل تیغ اوکام ارائه شده اند و نزدیک به سه قرن است که در مورد آن بحث می شود. استدلال ها هم در دو کمپ تقریبا مخالف هم در دو سر یک طیف قرار گرفته اند. عقلانیت پیشینی (A priori rationalism) به دنبال یافتن دلیلی پیشنی(A priori) و تجربه گرایی طبیعی (Naturalized Empiricism) به دنبال دلایل کاملا تجربی برای توجیه اصل تیغ اوکام بوده اند. در واقع هر دوی این دیدگاه ها به نتایج مبهمی برای سوالات اساسی در مورد سادگی می رسند. به طور خاص، به نظر می رسد هیچ کدام به ابزاری برای اندازه گیری اینکه توازن سادگی در برابر کفایت تجربی (Empirical adequacy) چقدر باید باشد مجهز نیستند. نظریات ساده ولی به شدت نادقیق داریم و همچنین نظریات بسیار پیچیده ولی دقیق. چگونه باید موازنه را حفظ کرد.دیدگاه های عقلانیت و تجربه گرایی بسیار سیاه و سفید به نظر می رسند. اخیرا بسیاری به نظریات احتمال و آمار روی آورده اند. این مساله در آمار به مساله "انطباق خط"(Curve fitting) قابل کاهش است. فرض کنید تعدادی نقطه از آزمایش داریم. به دنبال خطی(تابعی) هستیم که آن نقاط را تولید کند. مساله این که کدام خانواده از توابع مورد استفاده قرار گیرد به مساله انتخاب مدل (Model selection) معروف است. در انتخاب مدل فقط دقت مهم نیست بلکه سادگی هم اهمیت دارد چرا که بسیاری از داده های ما دچار نویز می شوند یا در اندازه گیری خطا وجود دارد. در غیر این صورت دچار بیش برازش (Overfitting) می شویم. بیش برازش در واقع انطباق مدل به نمونه های تصادفی ای است که نماینده نظم بزرگتری که نقاط طبق آن تولید شده اند، نیستند. سادگی روش درمان بیش برازش است!یک دلیل رها کردن روش های عقلانی/تجربی این است که بسیار مبهم اند در حالی که آماردانان روش های کمی برای مقایسه مدل ها یافته اند هرچند روش های آنها با هم متفاوت است. یکی از معیار های معروف دراین زمینه Akaike Information Criterion استAIC روشی برای اندازه گیری نسبی کیفیت یک مدل به نسبت یک مدل دیگر است. AIC بر اساس نظریه اطلاعات است: این روش میزان از رفتن اطلاعات را زمانی که یک مدل برای بازنمایی یک فرآیند تصادفی مورد استفاده قرار می گیرد، اندازه گیری می کند.فرض کنید یک مدل آماری از داریم. فرض کنید L بزرگترین مقدار تابع likelihood برای مدل باشد. همچنین فرض k تعداد پارامتر های مدل باشد. مقدار AIC به صورت زیر است:با داشتن یک مجموعه از داده ها مدل ترجیحی مدلی است که مقدار AIC آن از همه کوچیکتر باشد.هرچه تعداد پارامتر ها کمتر باشد و احتمال داده ها به فرض درستی مدل(likelihood) بیشتر باشد AIC کوچکتر و مدل انتخابی بهتری داریم.فرض کنید داده ها از یک فرآنید تصادفی ناشناخته f می آید و ما دو مدل کاندید برای بازنمایی f داریم: g1 و g2 . اگر ما f را میدانستیم میزان اطلاعات از دست رفته از انتخاب g1 برای بازنمایی (مدل کردن) f بادیورژانس کولبک لیبر (Kullback-Leiber divergence) اندازه گیری می شود و به صورت مشابه میزان اطلاعات از دست رفته از بازنمایی f با g2 برابر است با: . سپس ما مدلی را انتخاب می کنیم که کمترین از دست رفتن اطلاعات را دارد.اما مشکل این است که ما f را نمیشناسیم. Akaike نشان داد که می توان با AIC میزان از دست رفتن اطلاعات را (به صورت نمایی) تخمین زد.نحوه استفاده از AIC ساده است: فرض کنید سه مدل داریم با مقادیر AIC 100، 102 و 110. کمترین مقدار 100 است آنگاه exp((100-102)/2)=0.36 که میزان محتمل بودن مدل دوم نسبت به اول است. و سومی 0.007 محتمل تر از اولی است. حالا می توان به راحتی مدل سوم را کنار گذاشت و بین دو تای اولی به انتخاب دست زد. می توان اطلاعات بیشتری جمع آوری کرد. به گفتن این که اطلاعات بیشتری برای تمایز موجود نیست اکتفا کرد یا از یک مدل ترکیبی وزن دارد با وزن یک برای اولی و 0.36 برای دومی استفاده کرد.معیار دیگری که بسیار مورد استفاده قرار می گیرد، معیار اطلاعاتی بیزین است که بر خلاف نامش بر اساس نظریه اطلاعات نیست. مقدار آن برابر است با:که L حداکثر مقدار تابع likelihood است و k تعداد پارامتر ها و n هم تعداد نقاط داده ای است. AIC مزیت های زیادی نسبت به BIC دارد. اول آنکه AIC از اصول نظریه اطلاعات استخراج شده است و دوم آنکه BIC یک احتمال پیشینی 1/R دارد که عاقلانه نیست زیرا احتمال پیشینی باید یک تابع کاهشی از k باشد.روش های دیگری هم مانند "کوتاه ترین اندازه توضیح2" هم برای انتخاب مدل وجود دارند که کاملا از دید نظریه اطلاعات برخورد می کنند. MDL ریاضی سازی اصل تیغ اوکام است که در آن بهترین فرضیه برای یک مجموعه داده آن فرضیه ای است که منجر به بهترین فشرده سازی داده ای3می شود. به عبارت زیبا تر:اصل MDL بر اساس دیدگاه زیر است: هر نظمی در یک مجموعه داده می تواند برای فشرده سازی آن استفاده شود. یعنی: توصیف آن با تعداد نماد های کمتر از توصیف نماد به نماد آن(Grünwald, 1998)برای یافتن چنین فشرده سازی ای، ابتدا یک کد برای کار ثابت می شود که باید turing complete باشد. برنامه (در آن زبان) باید داده ها را تولید کند. طول کوتاه ترین برنامه ای که آن داده ها را تولید می کند پیچیدگی کولموگرف (Kolmogorov Complexity) داده ها نامیده می شود.اما این نظریه ریاضی یک روش عملی برای ساخت چنین برنامه ای یا طول کوتاهترین برنامه را نمی دهد.چند دلیل برای آن وجود دارد:پیچیدگی کولموگروف محاسبه ناپذیر است.پیچیدگی کولموگروف وابسته به زبان برنامه سازی است.می توان این مشکلات را با محدود کردن کد گذاری یا انتخاب کد کارا حل و فصل کرد. اما نکته مهم تر آن است که به جای "برنامه" در نظریه MDL معمولا از فرضیه های کاندید، مدل ها یا کد ها اسم برده می شود. و همین تمام بحث را به هم میچسباند!مفهوم MDL به صورت بسیار قوی با نظریه احتمال و آمار از طریق انطباق بین کد و توزیع های احتمال مرتبط است. این باعث شده برخی بر این باور باشند که MDL همان استنتاج بیزی(Bayesian Inference) است: طول کد مدل منطبق با احتمال های پیشینی و طول کد داده ها منطبق با احتمال مارجین likelihood است.دیدگاه بیزینیاگرچه دیدگاه فرکانسی به احتمال بسیار مورد استفاده قرار گرفته است اما دیدگاه فرکانسی در بسیاری مواقع غیر شهودی به نظر می رسد. مثل احتمال باران آمدن فردا، یا احتمال برنده شدن ترامپ در انتخابات بعدی.در این موارد دیدگاه شخصی (subjective) به نظر عاقلانه تر به نظر می رسد. در واقع قوانین احتمال می گویند اگر دو نفر داده های یکسانی داشته باشند و فرض های مشابهی هم داشته باشند باید به نتایج یکسانی برای احتمال فرضیاتشان برسند. از دیدگاه بیزین ها این ضعف نیست بلکه:شما نمی توانید بدون پیش فرض استدلال کنید!از طرفی دیدگاه فرکانسی ها بر این مبنا است که بدون Prior ( پیش فرض) به دنبال مدل(پارامتر ها) باشیم. در این صورت تنها راهکار برای آن ها استفاده از تابع درستنمایی (likelihood) است. تابع درستنمایی گاها به اشتباه به احتمال داده ها به شرط داشتن پارامتر ها تعبیر می شود. اما تابع درست نمایی تابعی از پارامتر ها است اما نشان دهنده میزان محتمل بودن داده ها هم با پارامتر های مختلف است. باید توجه کرد که تابع درستنمایی یک تابع احتمال بر روی پارامتر ها نیست و انتگرال آن بر روی پارامتر ها هم لزوما برابر با یک نمی شود(Bishop p22). هرگز نگویید احتمال داده ها(likelihood of data) بلکه بگویید احتمال پارامتر ها(likelihood of parameters).(Information Theory, Inference, and Learning Algorithms 29). به همین خاطر تابع درستنمایی را به صورت زیر می نویسند:به طور مثال تابع درستنمایی برای تابع چگالی پیوسته به صورت زیر است:و روش فرکانسی ها برای یافتن بهترین پارامتر ها Maximum Likelihood(ML) است. اما از دیدگاه بیزینی Prior ها مهم اند و بنابراین از روش Maximum A Posteriori(MAP) استفاده می کنند.وتخمین پارامتر ها به روش فرکانسی همان روشی است که معمولا استفاده می شود. به طور مثال هنگام انداختن یک سکه احتمال رو آمدن را به صورت یک پارامتر در نظر بگیریم بدست آوردن این پارامتر با شمردن تعداد رو ها به کل تعداد اندختن سکه ها است. اما فرض کنید تعداد داده ها کم باشد و از 10 انداختن سکه 8 تای آن رو باشد. در این صورت پارامتر برابر با 0.8 خواهد بود که شاید معقول نباشد به همین دلیل بیزین ها توصیه می کنند پیش فرض بگیریم که احتمال پارامتر برابر با 0.5 را بالاتر بگیریم و بقیه را کمتر. در این صورت احتمال Posterior تحت تاثیر Prior هم قرار می گیرد و البته مقدار Prior هر بار آپدیت میشود(توضیح بیشتر در مطلبی جداگانه).از طرفی برای هر توزیع احتمال یک تابع طول کد وجود دارد. به عبارتی برای هر توزیع احتمال P یک کد L وجود دارد که:ومعادله بالا نشان میدهد که برعکس این قضیه هم برقرار است. اصل MDL می گوید مدل هایی بهتر هستند که داده ها را در تعداد کمتری بیت منتقل می کنند. فرض کنید یک فرض اولیه H داریم و یک سری داده D . بنابراین طول کد برای انتقال آن ها برابر است با:در این H در واقع یک توزیع احتمال Prior به خود دارد که به صورت P(H) است. و L(D|H) هم متناظر است با تابع likelihood P(D|H) پس داریم:طول پیام به صورت یک بخش پارامتر و یک بخش داده تقسیم می شود. مدل های با تعداد کم پارامتر ها بلاک پارامتر کوتاهی دارند و به همین خاطر به داده ها به خوبی fit نمی شوند و بخش داده (به شرط مدل) بزرگتر است. هر چه پارامتر ها بیشتر باشد بخش مدل بزرگتر و بخش داده کوچکتر می شود. یک مقدار بهینه برای پیچدگی مدل وجود دارد که مجموع داده و مدل را به حداقل می رساند.به طور مثال برای سه فرضیه H1 ، H2 و H3 در بالا H2 بهترین مجموع طول داده و پارامتر را در خود جای داده است. زیرا مجموع طول پارامتر ها و داده به شرط پارامتر(مدل) از هر دو بهتر است.یافتن بهترین پارامتر به روش بالا دشوار است و ترجیحی به روش بیزین ندارد(Inference) در روش بیزین هم از روش های مشتق گیری یا به در صورت پیچیده شدن مساله Inference learning مانند variational bayesian method یا Gibbs sampling استفاده می شود.