نظریه اطلاعات در قلب ارتباطات ایجاد شد. زمانی که شما بخواهید پیامی را از یک منبع A به یک مقصد B برسانید همیشه این سوال وجود دارد که بهترین روش برای ارسال اطلاعات چیست. فرض کنید می خواهیم یک سری متون را از A به B برسانیم. اگر بخواهیم هر کاراکتر را به صورت باینری در بیاوریم. در این صورت مثلا برای زبان فارسی نیاز به 5 بیت برای 32 حرف داریم. بنابراین یک کلمه سه حرفی نیاز به 15 بیت برای انتقال دارد. شانون به عنوان یک ریاضیدان و مهندس برق به دنبال راهی برای بهینه تر کردن این ارسال بود. اگرچه چند بیت اضافی شاید خیلی مهم بنظر نرسد اما در آن زمان بیت به بیت برای شبکه های اولیه بسیار پرهزینه بود و از طرفی حتی امروزه هم انتقال بهینه اطلاعات با حجم بسیار زیاد اطلاعات و نیز تعداد بسیار زیاد کاربران بسیار مهم است. هرچند باید دانست کاربردهای نظریه اطلاعات از انتقال اطلاعات بسیار فراتر می رود.
چیزی که شانون متوجه شد این بود که در یک کانال ارتباطی همه نمادها(مثلا کاراکتر های زبان) با یک احتمال ظاهر نمی شوند. برخی احتمال بیشتری دارند مثل e و برخی با احتمال کمتری ظاهر می شوند مثل z. بنابراین این دو کاراکتر حاوی "اطلاعات" یکسانی نیستند! اما "اطلاعات" چیست؟
بیایید با یک مثال دیگر ادامه دهیم. فرض کنید شما خانه ای وسط صحرای بزرگ آفریقا دارید. شما معمولا نیازی به چک کردن اخبار هواشناسی ندارید هر چند هواشناسی برای منطقه شما هم پیش بینی ای دارد. اما این پیش بینی به درد شما نمی خورد شما تقریبا همیشه می دانید که فردا آفتابی و گرم است. همچنین اگر در قطب زندگی کنید همیشه هوا سرد و زمستانی است. اما اگر به یکباره هواشناسی پیش بینی کند که یک سرمای بی سابقه وارد صحرای بزرگ آفریقا می شود شما بسیار "تعجب" می کنید. این خبر حاوی اطلاعات بسیار زیادی است چون احتمال رخ دادن آن در وسط صحرا بسیار پایین است. هرقدر رویدادی غیرمنتظره تر باشد حاوی اطلاعات بیشتری است! پس اطلاعات با احتمال رویداد مرتبط است. (اطلاعات رویداد X را با I(X) نشان می دهیم.)
اما این چه نوع ارتباطی است؟ اول اینکه اگر احتمال یک اتفاق صددرصد باشد آن رویداد قطعی و دانستن آن چیزی به ما اضافه نمی کند پس اطلاعات آن صفر است. پس
همچنین اگر دو رویداد از هم مستقل باشند مثلا دو رویداد احتمال آفتابی شدن هوا برای فردا(X) و احتمال برد تیم مورد علاقه(Y) در نظر بگیرید، دانستن آنها با هم فقط اطلاعات شما را به صورت خطی اضافه می کند. چون اطلاع از هیچ کدام باعث کم و زیاد شدن اطلاع در مورد دیگری نمی شود. یعنی:
اما می دانیم که احتمال دو رویداد مستقل صرفا حاصلضرب احتمال آن دو رویداد است:
پس:
و
تنها تابعی که این خاصیت را دارد توابع لگاریتمی هستند. یعنی تمام توابعی به صورت زیر:
اما ثابت k را چگونه تعیین کنیم. چون احتمال ها همگی بین صفر و یک هستند لگاریتم منفی می شود پس k را باید منفی کنیم که آن را خنثی کند. پس K=-1 می گیریم. پس فرمول اطلاعات به صورت زیر می شود:
اگر پایه لگاریتم را 2 بگیریم. واحد اطلاعات بیت می شود. یعنی اگر احتمال رویدادی 50 درصد باشد اطلاعات آن یک بیت است.
اما معمولا ما فقط اطلاعاتِ یک حالتِ یک رویداد مثلا "آفتابی بودن" یا "بارانی بودن" رویدادِ "هوای فردا" را نمی خواهیم بلکه اطلاعات کل آن رویداد را می خواهیم. به عبارتی ما به دنبال متوسط اطلاعات برای همه پیش آمدهای ممکن بر اساس احتمال رخ دادنشان هستیم. برای این کار میانگین وزن دار می گیریم:
این میانگین اطلاعات را آنتروپی می نامند. پس آنتروپی میانگین اطلاعات یک رویداد است. دوباره به مثال هواشناسی بر میگردیم. اگر شما وسط صحرای آفریقا باشید هواشناسی در کل برای شما اطلاعات زیادی ندارد چرا که با احتمال تقریبا قطعی فردا آفتابی است و با احتمال بسیار بسیار کم بارانی(فعلا فرض کنید فقط دو حالت داریم، اگر تعداد حالت ها بیشتر باشد به راحتی می توان تعمیم داد) در این صورت چیزی مثل این مورد را داریم:
اما اگر شما وسط کلرادو زندگی می کنید حتی ممکن است وسط تابستان بارانی شود یا در وسط زمستان یک روز آفتابی گرم داشته باشید. هوا تقریبا مانند یک سکه که شیر و خط می آید است. هواشناسی اطلاعات زیادی برای شما خواهد داشت و چک کردن مرتب آن بسیار مفید است. در این حالت بیشترین آنتروپی را داریم.
می توان برای دو حالت شکل زیر را رسم کرد:
اکنون که می دانیم تعریف دقیق ریاضی اطلاعات چیست به بحث انتقال داده ها بر میگردیم. Z حاوی اطلاعات بیشتری است چون با احتمال کمتری ظاهر می شود و e با احتمال بیشتری ظاهر می شود پس اطلاعات کمتری دارد. کدینگ بهینه زمانی اتفاق می افتد که بیت کمتری برای کاراکتری استفاده شود که با احتمال بیشتری می آید و حاوی اطلاعات کمتری است و بیت بیشتر برای کاراکتری که کمتر اتفاق می افتد و اطلاعات بیشتری دارد. اما سوالی که پیش می آید این است چطور می توان یک کدینگ داشت که اندازه بیت ها برای حالت های مختلف متفاوت باشد؟ روش های زیادی برای این کار هست اما یک روش ساده prefix coding است. در این روش می توان دنباله ای از بیت ها داشت که به صورت یکتا قابل دیکد کردن باشند. جدول زیر یک مثال از آن را نشان می دهد
به این صورت ما به طور متوسط برای هر کاراکتر نه 5 بیت بلکه به اندازه آنتروپی کاراکتر ها که از 5 بیت کمتر است خرج می کنیم. شانون پس از محاسبه پی برد که آنتروپی کاراکتر های انگلیسی 2.62 بیت است.
اما شانون چگونه محاسبه کرد که احتمال هر کاراکتر در زبان انگلیسی چقدر است؟ پاسخ بسیار ساده است و همان کاری است که هر شخص دیگری هم انجام می دهد. محاسبه بر اساس فرکانس حضور کاراکتر ها در یک حجم قابل قبول از متون انگلیسی.
در مورد کاراکترهای زبان این کار البته ساده است و می توان گفت به واقعیت نزدیک است. اما محاسبه احتمال یک توزیع احتمال همیشه به این سادگی ها نیست. مثلا در مدلسازی زبان (language modeling) شما به دنبال محاسبه احتمال یک دنباله از کلمات هستید. به این ترتیب شما می توانید با داشتن یک رشته کلمه بعدی آن را پیش بینی کنید. زمانی که مساله یک کلمه یا دوکلمه (2-grams) است باز هم می توان از روش های شمارش و فرکانس استفاده کرد اما بیشتر از آن به علت کم بودن منابع زبانی (هرقدر هم که متن جمع کنید کافی نخواهد بود) محاسبات دقیق نخواهد بود. مثلا سه کلمه "گوسفند شاخدار آبی" از "کتاب سیب بار" محتمل تر است چون اولی حداقل دارای ساختار گرامری درستی است اما در هیچ متنی هم پیدا نمی شود پس احتمال آن به غلط صفر محاسبه می شود و ما روشی برای ترجیح اولی بر دومی بر اساس شمارشِ صرف نداریم.
این وظیفه مدلسازی زبان (language modeling) است. در این جا نمی خواهیم وارد موضوع مدلسازی زبان شویم. در این حالت فرض کنید که مثلا زبان انگلیسی دارای یک توزیع احتمال ناشناخته p به صورت زیر است:
توزیع احتمال p ناشناخته است اما می توان مدل توزیع احتمال های دیگری مانند q را یافت و سعی کرد تا جای ممکن آن را به p شبیه کرد. اما چگونه بدانیم که q چقدر خوب است. چون q شناخته شده است یعنی یک فرمول مشخص برای آن وجود دارد(یک فرمول ریاضی یا برنامه ای که آن را محاسبه می کند) پس قابل محاسبه است و بنابراین می توان اطلاعات آن را برای هر نمونه دنباله کلمات محاسبه کنیم. به عبارتی با داشتن فرمول اطلاعات طول کدینگ هر ورودی زبان را داریم. می دانیم که نمی توانیم p را داشته باشیم اما به جای p یک تخمین از p داریم که بر روی یک مجموعه بزرگ از متن ها قابل شمارش و محاسبه است. این تخمین از p به همان صورت قبل یعنی با شمارش محاسبه می شود. حالا اگر بخواهیم میانگین کدینگ خود را که بر اساس q است را بر اساس تخمین p به عنوان احتمال رخداد هر نمونه حساب کنیم چیزی شبیه به زیر خواهیم داشت:
این دقیقا شبیه به فرمول آنتروپی است با این تفاوت که کدزنی را با مدل پیشنهادی q انجام می دهیم اما میانگین را بر روی مدل هدف تخمین p محاسبه کرده ایم. مشخص است که زمانی این مقدار بهینه است که باشد(زیرا اگر دو توزیع با هم برابر باشند کدینگ بر اساس فراوانی هر حالت محاسبه شده است). در هر حالت دیگری باید تلاش کنیم q را تا جای ممکن به p نزدیک تر کنیم تا به آنتروپی p برسیم که بهینه ترین کد برای ورودی هایمان است. مقدار بالا به cross-entropy مشهور است. پس می توان گفت:
یعنی دو مدل p و q دارای یک اختلاف هستند. اگر p را ندانیم مجبوریم با q کدینگ را انجام دهیم و یک هزینه اضافی برای کدینگ به واحد بیت بپردازیم که خود اسم خاصی دارد:
که به انحراف کلبک لیبر معروف است. می توان این مقدار را به صورت ساده تر زیر نوشت:
واضح است که این اختلاف بیتی همیشه بزرگتر از صفر است چرا که در بهترین حالت مدل شما q دقیقا با مدل واقعی داده ها p همخوانی دارد و هیچ بیت اضافی لازم نیست بپردازید. اما بدترین حالت چه است؟
دقت کنید که ما تمام این کارها را کردیم تا طول کد بهینه را کاهش دهیم. در حالتی که ما مثلا احتمال هر کاراکتر را برابر با بقیه می دانیم هیچ فشرده سازی نداریم. در این حالت احتمال ها برابر با یکدیگر و برابر با:
است که N تعداد همه حالت ها(کاراکتر ها) است. آنتروپی در این حالت بیشینه است:
که کاملا منطقی به نظر می رسد. اگر 32 کاراکتر داریم تعداد کاراکتر بهینه log(32)=5 است. پس همیشه:
بنابراین در بدترین حالت q پیشنهادی ما بدترین مدل است یعنی مدلی که هیچ ترجیحی بین نمونه هایش ندارد. این توزیع همان توزیع یکنواخت است. پس(u توزیع یکنواخت است):
در مدلسازی زبان از معیاری به نام perplexity استفاده می شود که میزان خوب بودن یک مدل را نشان می دهد. Perplexity همان cross-entropy است. با این تفاوت که به توان دو میرسد:
به عبارتی perplexity طول متوسط همه حالت ها را نشان می دهد. هر قدر perplexity پایین تر باشد نشان دهنده cross entropy پایین تر و در نتیجه کدینگ بهتر q از p است.
