Teorya ng impormasyon

Ang Teoriya ng impormasyon ay sangay ng nilalapat na matematika at inhinyerong elektrikal na pag-aaral ng kwantipikasyon o pagsasabilang ng isang impormasyon. Ang teoriyang ito ay binuo ni Claude E. Shannon upang hanapin ang mga pundamental na hangganan sa mga operasyon ng pagpoproseso ng signal gaya ng kompresyon, pag-iimbak at pagpapadala ng datos. Simula ng pagkakalikha nito, ito ay lumawak upang humanap ng mga aplikasyon sa maraming mga iba pang sakop kabilang ang inperensiyang estadistikal, pagpoproseso ng natural na wika, kriptograpiya, mga network na iba sa mga network ng komunikasyon gaya na sa neurobiolohiya, ebolusyon  at tungkulin  ng mga kodigong molekular, seleksiyon ng modelo sa ekolohiya, thermal na pisika, pagkukwentang quantum, deteksiyon ng plagiarismo at iba pang mga anyo ng analisis ng datos.
Ang isang mahalagang sukat ng impormasyon ay tinatawag na entropiya na karaniwang inilalarawan ng aberaheng bilang ng mga bit na kailangan upang iimbak o ihatid ang isang simbolo sa isang mensahe. Ang entropiya ay nagkakwantipika ng walang katiyakan na sangkot sa paghuhula ng halaga ng isang randomang bariabulo. Halimbawa, ang pagtukoy ng kalalabasan ng isang patas na pagbaliktad ng barya(dalawang magkatumbas na malamang na kalalabasan) ay nagbibigay ng kaunting impormasyon(mas mababang entropiya) kesa sa pagtukoy ng kalalabasan mula sa pag-ikot ng isang  (anim na magkatumbas na malamang na kalalabasan).
Ang mga aplikasyon ng pundamental na mga paksa ng teoriya ng impormasyon ay kinabibilangan ng walang kawalang kompresyon ng datos(lossless data compression)(e.g. ZIP files), may kawalang kompresyon ng datos(lossy data compression) (e.g. MP3s and JPGs), at pagkokodigo ng channel (e.g. for Digital Subscriber Line (DSL)). Ang larangang ito ay nasa interseksiyon ng matematika, estadistika, agham pang-kompyuter, pisika, neurobiolohiya at inhinyeryang elektrikal. Ang epekto nito ay mahalaga sa pagtatagumpay ng mga misyong Voyager sa malalim na kalawakan, sa imbensiyon ng compact disc, pagiging posible ng mga mobile phone, pagkakabuo ng internet, pag-aaral ng linguistika at persepsiyong pang-tao, pag-unawa ng mga itim na butas at marami pang ibang mga larangan. Ang mahalagang mga pang-ilalim na larangan ng teoriya ng impormasyon ay kinabibilangan ng pagkokodigo ng pinagkunan(source coding), pagkokodigo ng channel(channel coding), teoriya ng algoritmikong kompleksidad, seguridad na impormasyon teoretiko at mga sukat ng impormasyon.

Konsepto

Ang pangunahing mga konsepto ng teoriya ng impormasyon ay mauunawaan sa pamamagitan ng pagsasaalang alang ng pinakamalawak na mga paraan ng komunikasyong pantao:wika. Ang dalawang mahalagang mga aspeto ng isang maikling wika ang sumusunod: Una, ang pinakakaraniwang mga salita(e.g., "a", "the", "I") ay dapat mas maiksi kesa sa hindi karaniwang mga salita(e.g., "roundabout", "generation", "mediocre",) upang ang mga pangungusap ay hindi maging labis na mahaba. Ang gayong pagpapalit sa haba ng salita ay analogo sa kompresyon ng datos at isang mahalagang aspeto ng pagkokodigo ng pinagkunan. Ikalawa, kung ang isang bahagi ng pangungusap ay hindi narinig o maling narinig dahil sa ingay gaya halimbawa ng pagdaan ng isang sasakyan, ang nakikinig ay dapat mabatid pa rin ang kahulugan ng saligang mensahe. Ang gayong kasaganaan ay mahalaga sa sistema ng elektronikong komunikasyon gaya ng sa wika. Ang angkop na pagtatayo ng gayong kasaganaan sa mga komunikasyon ay ginagawa sa pamamagitan ng pagkokodigo ng channel. Ang pagkokodigo ng pinagkunan at pagkokodigo ng channel ang mga pundamental na pinag-uukulan ng teoriya ng impormasyon.
Dapat maunawaan na ang mga pinag-uukulan ay walang kinalaman sa kahalagahan ng mga mensahe. Halimbawa, ang isang platitudo gaya ng "Salamat, bumalik ka ulit" ay mas mahabang sabihin o isulat kesa sa mahalagang pagsusumamo na "Tawagin ang ambulansiya!" samantalang ang huli ay mas mahalaga at mas makahulugan sa maraming mga konteksto. Gayunpaman, ang teoriya ng impormasyon ay hindi nagsasaalang alang ng kahalagahan ng mensahe o kahulugan dahil ang mga ito ay bagay ng kalidad ng datos kesa sa kantidad at pagiging mababasa ng datos na ang huli ay tanging matutukoy sa pamamagitan ng mga probabilidad.
Ang teoriya ng impormasyon ay pangkalahatang itinuturing na itinatag noong 1948 ni Claude Shannon sa kanyang seminal na akdang "A Mathematical Theory of Communication". Ang sentral na paradigm ng klasikong teoriyang impormasyon ang problemang pag-iinhinyerya ng transmisyon ng impormasyon sa ibabaw ng isang maingay na channel. Ang pinakapundamental na mga resulta ng teoriyang ito ay ang teorema ng pagkokodigo ng pinagkunan ni Shannon na nagpapatunay na sa aberahe, ang bilang ng mga bit na kailangan upang ikatawan ang resulta ng isang hindi matiyak na pangyayari ay ibinigay ng entropiya nito at ang teorema ng pagkokodigo ng maingay na channel ni Shannon na nagsasaad na ang isang maasahang komunikasyon ay posible sa ibabaw ng mga maingay na channel sa kondisyong ang rate ng komunikasyon ay nasa ilalim ng isang threshold na tinatawag na kapasidad ng channel. Ang kapasidad ng channel ay maaaring pakitunguhan sa pagsasanay sa pamamagitan ng angkop na pagkokodigo at pagdedekodigo ng mga sistema.
Ang teoriya ng impormasyon ay malapit na nauugnay sa isang koleksiyon ng puro at nilalapat na mga disiplina na inimbestigahan at napaliit sa pagsasanay na pagiinhinyerya sa ilalim ng iba't ibang mga rubric sa buong mundo sa loob ng nakaraang kalahating sigo o higit pa: mga adaptipong sistema, mga antisipatoryong sistema, intelihensiyang artipisyal, mga sistemang kompleks, cybernetika, impormatika, pagkatuto ng makina kasama ng mga agham ng mga sistema ng maraming mga deskripsiyon. Ang teoriya ng impormasyon ay isang malawak at malalim na teoriyang matematikal na may katumbas na malawak at malalim na mga aplikasyon na ang pinakamahalagang larangan ang teoriya ng pagkokodigo.
Ang teoriya ng pagkokodigo ay nauukol sa paghahanap ng mga hayagang paraang tinatawag na mga kodigo(codes) ng pagpaparami ng kaigihan at pagpapaliit ng net na kamaliang(error) rate ng komunikasyon ng datos sa ibabaw ng isang maingay ng channel tungo sa malapit sa hangganan na pinatunayan ni Shannon na ang maksimum na posible para sa channel na ito. Ang mga kodigong ito ay maaaring hatiin sa mga paraang kompresyon ng datos(source coding) at pagtutuwid ng kamalian(error correction/channel coding). Sa huling kaso, tumagal ng maraming mga tao upang hanapin ang mga paraan na napatunayan ng akda ni Shannon na posible. Ang ikatlong uri ng mga kodigo ng teoriya ng impormasyon ang mga algoritmong kriptograpiko (ang parehong mga kodig) at sipero. Ang mga konsepto, paraan at resulta mula sa teoriya ng pagkokodigo at teoriya ng impormasyon ay malawak na ginagamit sa kriptograpiya at kriptanalisis.
Ang teoriya ng impormasyon ay ginagamit rin sa pagkuha ng impormasyon, pagtitipon ng intelihensiya, pagsusugal, estadistika at kahit sa komposisyon ng musika.

Mga kantidad ng impormasyon

Ang teoriya ng impormasyon ay batay sa teoriya ng probabilidad at estadistika. Ang pinakamahalagang mga kantiad ng impormasyon ang entropiya na impormasyon sa isang randomang bariabulo, at mutual na impormasyon na halaga ng impormasyon na karaniwan sa pagitan ng dalawang mga randomang bariabulo. Ang nakaraang kantidad ay nagpapakita kung paanong madali ang datos ay masisiksik samantalang ang huli ay maaaring gamitin upang hanapin ang rate ng komunikasyon sa kahabaan ng isang channel.
Ang pagpili ng baseng logaritmiko sa sumusunod na mga pormula ay tumutukoy sa mga sukat ng entropiya ng impormasyon na ginagamit. Ang pinakakaraniwang unit ng impormasyon ang bit batay sa binaryong logaritmo. Ang iba pang mga unit ay kinabibilangan ng nat na batay sa natural na logaritmo at harley na batay sa karaniwang logaritmo.
Sa sumusunod, ang isang ekspresyon sa anyong  ay itinuturing sa konbensiyon na katumbas ng sero kapag ang i Ito ay makatwiran dahil ang  para sa anumang baseng logaritmiko.

Diberhensiyang Kullback–Leibler ng isang prior mula sa katotohanan

Ang isa pang interpretasyon ng diberhensiyang KL ay ito: ipagpalagay na ang isang bilang na X ay huhuguting randoma mula sa isang diskretong hanay na may distribusyong probabilida na p(x). Kung alam ni Alice ang totoong distribusyong p(x), samantalang si Bob ay naniniwalang(may prior) na ang distribusyon ay q(x), kung gayon, si Bob ay mas masusupresa kesa kay Alice sa aberahe sa pagkita ng halaga ng X. Ang diberhensiyang KL ang (obhektibong) inaasahang halaga ng (subhektibon) surprisal ni Bob menos ng surprisal ni Alice na sinukat ng mga bit kung ang log ay nasa baseng 2. sa paraang ito, ang lawak kung saan ang prior ni Bob ay "mali" ay maaaring ikwantipika sa mga termino kung paanong "hindi kinakailangang masurpresa" na inaasahang gawin siya.

Iba pang mga kantidad

Ang iba pang mahalagang mga kantidad na impormasyon teoretiko ay kinabibilangan ng entropiyang Rényi (na isang paglalahat ng entropiya), diperensiyal na entropiya(na paglalarawan ng mga kantidad ng impormasyon sa mga tuloy tuloy na distribusyon) at kondisyonal na mutual na impormasyon.

Teoriya ng pinagkunan

Ang anumang proseso na lumilikha ng sunod sunod na mga mensahe ay maaaring ituring na pinagkunan ng impormasyon. Ang isang walang memoryang pinagkaunan ay isa kung saan ang bawat mensahe ay independiyente magkatulad na ipinamahaging mga randomang bariabulo samantalang ang mga katangian ng ergodisidad at hindi gumagalaw ay nagtatkda ng mas pangkalahatang mga pagtatakda. Ang lahat ng gayong mga pinagkunan ay stokastiko. Ang mga terminong ito ay maiging pinag-aralan sa mga sarili nito sa labas ng teoriya ng impormasyon These terms are well studied in their own right outside information theory.

Mga gamit na intelihensiya at mga aplikasyon ng kalihiman

Ang mga konseptong impormasyon teoretiko ay lumalapat sa kriptograpiya at kriptanalisis. Ang unit ng impormasyon ni Alan Turing na ban, ay ginamit sa proyektong Ultra na bumabasg making Enigma ng Alemanyang Nazi na nagpabilis ng pagwawakas ng Ikalawang Digmaang Pandaigdig sa Europa. Mismong si Shanno ay naglarawan ng mahalagang konseptong tinatawag ngayong distansiyang unisidad. Batay sa redundansiya ng plaintext, ito ay nagtatangka na magbigay ng minimum na halaga ng ciphertext na kailangan upang masiguro ang natatanging desiperabilidad.
Ang teoriya ng impormasyon ay nagtutulak sa atin na maniwalang mas mahirap na panatilihin ang mga sikteto kesa sa unang tingin. Ang isang atakeng brutong pwersa ay maaaring bumasag ng mga sistema batay sa asymmetrikong susing mga algoritmo o sa karamihan ng karaniwang ginagamit na mga paraang ng simmetrikong susisng mga algoritmo(na minsang mga sikretong susing algoritmo) gaya ng mga blokeng sipero. Ang seguridad ng lahat ng gayong mga paraang ay kasalukuyang nagmumula sa asumpsiyon na walang alam na atake ang maaaring bumasag dito sa isang praktikal na halaga ng panahon.
Ang seguridad na impormasyon teoretiko ay tumutukoy sa mga paraan gaya ng isang beses na pad na hindi marupok sa gayong mga atakeng brutong pwersa. Sa gayong mga kaso, ang positibong kondisyonal na mutual impormasyon sa pagitan ng plaintext at ciphertext (na nakondisyon sa susi) ay maaaring sumiguro ng angkop na transmsiyon samantalang ang hindi kondisyonal na mutual impormasyon sa pagitan ng plaintext at ciphertext ay nananatiling seor na nagreresulta sa absolutong seguradong mga komunikasyon. Sa ibang salita, ang isang nakinig ng mensahe(eavesdropper) ay hindi magagawang pabutihin ang kanyang paghula ng plaintext sa pamamagitan ng pagtatamo ng kaalaman ng ciphertext ngunit hindi ng susi. Gayunpaman, gaya sa anumang ibang mga sistemang kriptograpiya, ang pag-iingat ay dapat gamit upang tamang mailapat ang kahit mga impormasyon teoretikong seguradong paraan. Ang proyektong Verona ay nagawang basagin ang mga isang beses na pad ng Unyong Soviet sanhi ng kanilang hindi angkop na paggamit ng susing materyal.