ذكر خصوصيات پايه و چند نامساوي مشهور

مثالهايي از محاسبه اين ابهام در چند مورد

رابطه بين ابهام كولموگروف و آنتروپي يك متغير تصادفي

احتمال جامع و رابطه آن با ابهام كولموگروف

بعضي از كاربردهاي عملي و تئوري اين مفهوم

& تاريخچه ايجاد مفهوم ابهام كولموگروف (Kolmogorov Complexity )

درابتداي سال 1964 آقاي سولومونف ( Solomonoff ) رياضيداني كه در زمينه هوشمصنوعي تحقيقاتي را انجام ميداد نتيجه گرفت كه هر مسئله در اصول استنتاحرياضي قابل مدل كردن به صورت تخمين يك دنباله باينري با طول به اندازهكافي بزرگ مي باشد ، او فرض كرد كه تمامي اطلاعات مورد نياز مساله در داخلدنباله وجود دارد و سپس با اين فرض احتمال زير را براي يك رشته x تعريفكرد :

كه p ها ، همه برنامه هايي هستند كه رشته x را توليد مي كنند .

اينكه اين تعريف چه رابطه اي با مفهوم مساله پيدا مي كند بعدها مشخص خواهد شد. مشكل آنجا بود كه در بسياري موارد اين جمع واگرا بوده و قابل محاسبهنبود .

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

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

شايد مهمترين مشوق كولموگروف برايكار روي اين نظريه ، تلاش براي فرموله كردن يك دنباله تصادفي بود اوتوانست به راحتي بين تعريف خود از ابهام يك متغير تصادفي و ميزان تصادفيبودن رشته ارتباط برقرار كند و بسياري از نظرات مطرح بالخصوص در مورددنباله هاي نامحدود را پايه گذاري كند .

ايده هاي كولموگروف توسطدانشجويان و بقيه اساتيد پيگيري شد ( در مورد تصادفي بودن ) بخصوص مارتينلوف كه تصور كولموگروف را از تئوري مجموعه ها به توزيع هاي احتمالات تسريداد و روشن شد كه اگر p يك توزيع احتمال ساده در يك مجموعه محدود A باشد ،مي توانيم عنصر x عضو اين مجموعه را تصادفي تعريف كنيم اگر ابهامكولموگروف كه تعريف آن خواهد آمد ، خيلي نزديك به باند بالايي خود – logp(x) باشد .

در واقع تعريف قبلي كولموگروف يك حالت خاص از اين تعريف به حساب مي آيد كه توزيع p در مجموعه A يكنواخت فرض شود .

تحقيقاتيكه در ادامه نظريات كولموگروف مطرح شد و سبب تكميل اين مباحث گرديد بصورتعملي به سه بخش تقسيم ميشود ؛ مفهوم ابهام (Complexity) ، تصادفي بودن(Randomness) و اطلاعات ( Information) .

در بحث ابهام و در ادامهتعريف ابهام كولموگروف ، بعدها توسط آقاي لوين مفهوم ، Prefix Complexityتعريف شد كه داراي خصوصيات برجسته اي بود اين تعريف براي غلبه و حل بعضيمسائل تكنيكي در تئوري اطلاعات معرفي شد و بطور مثال فقدان تقارن در تعريفاطلاعات ( به مفهوم كولموگروف ) و تئوري تصادفي بودن الگوريتمي را تصحيح وتكامل داد .

اين بحث سبب ايجاد كاربردهاي عملي شد كه دو روش MDL(Rissanen`s minimum description length) و MML (Wallace`s minimummessage 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 در تحقيق مشهور خود در مورد مساله عدم تداوم (HaltingProblem) نشان داد كه هيچ محاسبه گري وجود ندارد كه بصورت زير عمل كند:اگر يك برنامه ديگر به عنوان ورودي آن قرار گيرد ، در صورتيكه احتمالاورودي متوقف شود خروجي 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 در نامساوي زير صدق ميكند.