تاريخچه و علل ايجاد مفهوم ابهام كولموگروف

واضح آرشیو وب فارسی:سایت دانلود رایگان: تعاريف اوليه ابهام كولموگروف
ذكر خصوصيات پايه و چند نامساوي مشهور
مثالهايي از محاسبه اين ابهام در چند مورد
رابطه بين ابهام كولموگروف و آنتروپي يك متغير تصادفي
احتمال جامع و رابطه آن با ابهام كولموگروف
بعضي از كاربردهاي عملي و تئوري اين مفهوم
& تاريخچه ايجاد مفهوم ابهام كولموگروف (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 در نامساوي زير صدق ميكند.

این صفحه را در گوگل محبوب کنید

[ارسال شده از: سایت دانلود رایگان]

[مشاهده در: www.freedownload.ir]

[تعداد بازديد از اين مطلب: 1310]