دانلود تحقیق تاریخچه و علل ایجاد مفهوم ابهام کولموگروف

تاریخچه ایجاد مفهوم ابهام کولموگروف (Kolmogorov Complexity )
در ابتدای سال 1964 آقای سولومونف ( Solomonoff ) ریاضیدانی که در زمینه هوش مصنوعی تحقیقاتی را انجام میداد نتیجه گرفت که هر مسئله در اصول استنتاح ریاضی قابل مدل کردن به صورت تخمین یک دنباله باینری با طول به اندازه کافی بزرگ می باشد ، او فرض کرد که تمامی اطلاعات مورد نیاز مساله در داخل دنباله وجود دارد و سپس با این فرض احتمال زیر را برای یک رشته x تعریف کرد :
که p ها ، همه برنامه هایی هستند که رشته x را تولید می کنند .
این که این تعریف چه رابطه ای با مفهوم مساله پیدا می کند بعدها مشخص خواهد شد .

مشکل آنجا بود که در بسیاری موارد این جمع واگرا بوده و قابل محاسبه نبود .
در 1965 آقای کولموگروف ریاضیدان مشهور ، که زمینه اصلی کارش تئوری اطلاعات بود با ارائه یک مقاله ابهام را با دیدی متفاوت تعریف کرده و نشان داد که چطور این تعریف از ابهام با نظریات مطرح در باب تئوری اطلاعات رابطه پیدا میکند .

اینکه اشیاء در واقعیت طبیعی به دو صورت ساده و پیچیده وجود دارند بر کسی پوشیده نیست اما سئوال این است که برای توصیف یک شیئ چه راههایی همگرا هستند .

کار اصلی این دو ریاضیدان این بود که با الگو گرفتن از نظریات ریاضی الگوریتمها ، آزادی و بی قیدی این مساله را محدود کرده و با ارائه یک نعریف غیر قابل تغییر از ابهام ، راه را برای توصیف یک شی باز کردند .
شاید مهمترین مشوق کولموگروف برای کار روی این نظریه ، تلاش برای فرموله کردن یک دنباله تصادفی بود او توانست به راحتی بین تعریف خود از ابهام یک متغیر تصادفی و میزان تصادفی بودن رشته ارتباط برقرار کند و بسیاری از نظرات مطرح بالخصوص در مورد دنباله های نامحدود را پایه گذاری کند .
ایده های کولموگروف توسط دانشجویان و بقیه اساتید پیگیری شد ( در مورد تصادفی بودن ) بخصوص مارتین لوف که تصور کولموگروف را از تئوری مجموعه ها به توزیع های احتمالات تسری داد و روشن شد که اگر p یک توزیع احتمال ساده در یک مجموعه محدود A باشد ، می توانیم عنصر x عضو این مجموعه را تصادفی تعریف کنیم اگر ابهام کولموگروف که تعریف آن خواهد آمد ، خیلی نزدیک به باند بالایی خود – log p(x) باشد .

در واقع تعریف قبلی کولموگروف یک حالت خاص از این تعریف به حساب می آید که توزیع p در مجموعه A یکنواخت فرض شود .
تحقیقاتی که در ادامه نظریات کولموگروف مطرح شد و سبب تکمیل این مباحث گردید بصورت عملی به سه بخش تقسیم میشود ؛ مفهوم ابهام (Complexity) ، تصادفی بودن (Randomness) و اطلاعات ( Information) .
در بحث ابهام و در ادامه تعریف ابهام کولموگروف ، بعدها توسط آقای لوین مفهوم ، Prefix Complexity تعریف شد که دارای خصوصیات برجسته ای بود این تعریف برای غلبه و حل بعضی مسائل تکنیکی در تئوری اطلاعات معرفی شد و بطور مثال فقدان تقارن در تعریف اطلاعات ( به مفهوم کولموگروف ) و تئوری تصادفی بودن الگوریتمی را تصحیح و تکامل داد .

این بحث سبب ایجاد کاربردهای عملی شد که دو روش MDL (Rissanen`s minimum description length) و MML (Wallace`s minimum message length) در تخمین متغیرها ، از اهم آنهاست .

در مفهوم نصادفی بودن ، که با تعربف ابهام کولموگروف نزدیکی زیادی دارد ، تحقیقات به طور جدی ادامه یافت و نظریات وسیعی بالخصوص در مورد دنباله های نامحدود مطرح گردید اگر چه سبب شد که این روند بیشتر کاربرد تئوریک یافته و از مصارف عملی دور گردد .

در مفهوم اطلاعات ، پس از این که کولموگروف اطلاعات متقابل را اینطور تعریف کرد که I(X; Y) = K(y) – K(y/x) اما با این تعریف برخی ویژگیهای اصلی اطلاعات مانند تقارن مشکل داشتند که در تعریف آقای لوین ، تصحیح شد با این تعریف ‌ I(X; Y) = K(y) – K(y/x, k(x)) تحقیقات بعدی در این مفهوم در الگوریتمهای MML‌ و MDL بروز یافت.

& تعریف Kolmogorov Complexity سه رشته باینری روبرو را در نظر بگیرید : هر سه دارای 24 بیت می باشند با این تفاوت که رشته اول را می توان یک رشته باینری با بیتهای 1 در جایگاه زوج و صفر در جایگاه فرد دانست ، رشته سوم یک رشته باینری است که بیت I ام آن 1 است اگر و فقط اگر در بسط باینری I تعداد فردی یک وجود داشته باشد ، اما در مورد رشته دوم هیچ چیز نمیتوان گفت مگر آنکه برای توصیف آن تک تک بیت ها آورده شود .

اگر f یک تابع ( یک UTM‌ ) باشد و p‌ رشته ورودی این ماشین ، در اینصورت به ازای هر رشته x ، ابهام کولموگروف آن (Kolmogorov Complexity‌ )‌ به صورت طول کوتاهترین برنامه ای کهx را توصیف می کند تعریف میشود .

در مورد اینکه UTM (Universal Turing Machine) چه ویژگیهایی وجود دارد سخن بسیار است ‌، این یک ماشین محاسبه گر در حالت کلی است که می تواند در حالت خاص یک فشرده ساز اطلاعات باشد .

نکته مهم در این جاست که f ‌به معنای ریاضی قابل محاسبه نمی باشد ، یعنی نمی توان انتظار جایگذاری یک رابطه ریاضی صریح به جای آن داشت .

در کتاب های پیشرفته ریاضیات این نوع توابع حالت خاصی از یک قضیه به شمار میروند که به Berry Paradox Theorem مشهور است ، این قضیه با یک فرض جواب دارد و آن اینکه خروجی این توابع توصیف کننده یک رشته باشند .با فرض گفته شده ، این قضیه می گوید که برای توصیف یک رشته حتما یک تابع با خصوصیت دلخواه ما وجود دارد ، اما قابل محاسبه نیست و از این روست که f را Semi-Computable گویند .

آقای Alan Turing‌ در تحقیق مشهور خود در مورد مساله عدم تداوم (Halting Problem) نشان داد که هیچ محاسبه گری وجود ندارد که بصورت زیر عمل کند: اگر یک برنامه دیگر به عنوان ورودی آن قرار گیرد ، در صورتیکه احتمالا ورودی متوقف شود خروجی TRUE‌ و در غیر آن FALSE‌ ایجاد شود .

& ذکر خصوصیات و چند رابطه مشهور شاید یکی از مهمترین ویژگیهای این نوع از تعریف ابهام بر خلاف تعریف آنتروپی که وابسته به توزیع احتمال متغیر تصادفی بود ، این است که این تعریف ، از توزیع احتمال متغیر x مستقل است .اما آنچه معروف به خاصیت Universality‌ در مورد ابهام کولموگروف است این است که این تعریف از ابهام ، حتی از تابع عملگر روی رشته ورودی (UTM)‌ ، نیز مستقل است ( با در نظر گرفتن یک ثابت جمع شونده ) یعنی اگر f و g دو ماشین محاسبه گر باشند به ازای هر رشته x ، یک ثابت C وجود دارد بطوریکه Cf(x) ≤ Cg(x) + cg با دانستن این رابطه دیگر لزومی نیست که در پیداکردن ابهام یک رشته ، محاسبه گر آن را بدانیم زبرا تفاوت به ازای هر ماشین محاسب تنها در یک ثابت خواهد بود به همین دلیل به جای Cf(x) ، C(x) بکار می بریم و ثابت را در همه نامساوی ها و قضایا کنار ابهام ، منظور می کنیم .

برخی دیگر از ویژگیهای این تعریف عبارتند از : 1) : این ویژگی بدین خاطر است که در بدترین حالت خروجی و ورودی برنامه یکی است در اینصورت کمترین بیت لازم برای توصیف X برابر طول رشته خواهد بود .

2) : بدیهی است که تعداد بیتهای لازم برای شرح یک تابع مشخص از رشته x ، نمیتواند از بیتهای لازم برای شرح خود رشته بیشتر باشد ( با فرض معلوم بودن h ) .

در حالت خاص این ویژگی می توان گفت که 3) : بدیهی است که در بدترین حالت یعنی زمانی که متغیر y‌ هیچ گونه ارتباطی به x ندارد ، تعداد کمترین بیت برای شرح x از مقدار لازم برای توصیف خود رشته در غیاب y نمیتواند بیشتر باشد .

4) : یکی از سئوالات مهم در این تعریف این است که اگر بخواهیم رشته تشکیل شده از پشت سر هم قرار دادن xy را توصیف کنیم در کمترین حالت به چند بیت نیازمندیم آیا می توان گفت که با این تعریف از ابهام تنها کافی است کمترین توصیف هر یک را جداگانه محاسبه و حاصل را با هم جمع کنیم ؟

جواب خیر است اما چرا ؟

اگر فرض کنیم که ‌ p و q دوبرنامه باشند که g(p)=x و g(q)=y‌ می خواهیم در اصل p و q‌ را توامان با هم کد کنیم طوری که در خروجی جداسازی آنها امکان پذیر باشد اگر کدینگ ما بصورت ساده pq باشد آنگاه نمیتوانیم بفهمیم کجا رشته p تمام و رشته q شروع میشود و این یعنی اتلاف اطلاعات .

بنابرابن ناگزیر به اضافه کردن چند بیت برای حل این مشکل هستیم ، در واقع راههای گوناگونی وجود دارد که اتفاقا هر یک نیز نامساوی متفاوتی ایجاد می کند .

بطور مثال اگر عدد طبیعی n مبین طول رشته p باشد آنگاه کدینگ (0n1pq) به معنای n صفر ، یک 1 و سپس رشته pq میتواند مشکل ما را حل کند .

در یک شکل دیگر میتوان از کدینگ دوبل با یک نشانه در انتها استفاده کرد مثلا اگر n =1010 باشد آنگاه رشته اضافه شده 11 00 11 00 01 انتخاب گردد که بااین شیوه نیز میتوان مساله را حل نمود البته در ازای تعداد بیت بیشتر ، که در این مثال به اندازه 2 log2C(x) بیت اضافه کرده ایم پس با این کدینگ داریم : میتوانیم مثلا بصورت abs(n) n p q) ) که نوعی از کدینگ دوبل است ، استفاده کنیم که باز داریم : و به همین ترتیب انواع کدینگ های مشابه می توانند رشته مورد نظر را توصیف کنند و هر یک نیز نامساوی را تکمیل می نمایند ، و این از آن جهت مهم است که ما را در نهایت به مفهوم تصادفی بودن نزدیک می کند .

5) مفهوم تصادفی بودن رشته ای که قابل فشرده شدن نیست ، یا نمی توان هیچ شرح کوتاهی برای آن جست رشته تصادفی نام می گیرد طبق قضیه رشته x تصادفی به مفهوم کولموگروف است اگر به ازای هر n ، (که n ‌ برابر طول رشته x‌ است ) داشته باشیم : n ≥ C(x) اثبات می شود که اگر x یک عنصر از مجموعه محدود A باشد ، ابهام آن نمیتواند خیلی بزرگتر از log(abs(A)) باشد که این مقدار حد بالایی ابهام شناخته می شود ، حال x تصادفی است اگر ابهام آن به باند بالایی خود که در بالا اشاره شد تا حد امکان نزدیک باشد و این همان رابطه نزدیک ابهام یک متغیر و میزان تصادفی بودن آن است .

در مورد این رابطه قضایای زیادی وجود دارد که می توان به بعضی اشاره کرد : - اگر رشته X=(x1 x2 x3 …) یک رشته تصادفی باشد آنگاه می بایست : این قضیه بدین معناست که در این رشته ها نسبت صفر و یک تقریبا برابر است .

- و نیز اثبات می شود که اگر رشته X ، یک رشته تصادفی ( برنولی 0.5 ) باشد آنگاه یعنی احتمال اینکه رشته مورد نظر ، به اندازه بیش از k بیت فشرده شود ، کمتر از دو به توان –k است که دقیقا همان چیزی است که در ذهن نیز تداعی می کند .

- نیز اثبات می شود که بین ابهام یک رشته تصادفی و طولانی ترین زیر رشته داخلی از صفر در درون آن رابطه وجود دارد که با فرض C(x) = abs(x) = n و x = u 0 2logn v بدست آمده است .

طبق این قضیه می توان نشان داد که رشته های تصادفی می توانند دارای رشته های نسبتا طولانی صفر نیز باشند .

6) مفهوم اطلاعات یکی از ویژگیهای مهم این است که : که n= max { abs(x) abs(y) } و نیز طبق تعریف قدیمی اطلاعات متقابل داریم : I(X;Y) = C(y) – C(y/x) با این دو فرض اثبات می شود که : و این همان عدم تقارن بحث شده در مفهوم اطلاعات است که با تعریف Prefix-free Complexity برطرف شد .

& چند مثال از محاسبه ابهام کولموگروف برای ایجاد تصور دقیق تر نسبت به موضوع چند مثال کوتاه آورده می شود .

الف ) یک رشته n تایی صفر K (000…/n) = C ب ) n بیت اول بسط عدد پی K (pi1 pi2 … /n) = C ج ) یک تصویر با قابلیت فشرده شدن به اندازه 0.66 K (picture/n) ≤ n/3 + C د) یک عدد صحیح مانند n‌ [Log n] + C K (n) ≤ و ) یک رشته باینری n ‌ بیتی با k تا 1 می خواهیم ببینیم که یک رشته باینری با k بیت 1 را چقدر می توان فشرده کرد ، واضح است که برای توصیف یک چنین رشته ای کافی است اولا k‌ را بدانیم و در ثانی تعداد رشته های k تایی در این رشته ، این دو فاکتور می توانند به طور منحصر بفرد چنین رشته ای را بوجود بیاورند .

برای توصیف k به فرم کدینگ دوبل به 2 log k و برای توصیف تعداد رشته های k ‌ تایی که برابر است با به لگاریتم این مقدار بیت نیازمندیم ، عدد ثابت c نیز همواره منظور می شود .

در حالت کلی می توان به طریق مشابه اثبات کرد که ابهام کولموگروف یک رشته مانند x در نامساوی زیر صدق میکند.