Teori informasi adalah studi matematika tentang kuantifikasi, penyimpanan, dan komunikasi informasi. Bidang ini didirikan dan diformalkan oleh Claude Shannon pada tahun 1940-an, meskipun kontribusi awal telah dilakukan pada tahun 1920-an melalui karya Harry Nyquist dan Ralph Hartley. Teori informasi berada di persimpangan antara teknik elektronika, matematika, statistik, ilmu komputer, neorobiologi, fisika, dan teknik elektro.
Salah satu ukuran kunci dalam teori informasi adalah entropi. Entropi mengukur jumlah ketidakpastian yang terlibat dalam nilai variabel acak atau hasil dari proses acak. Misalnya, mengidentifikasi hasil lemparan koin yang adil (yang memiliki dua hasil yang sama mungkin) memberikan informasi yang lebih sedikit (entropi lebih rendah, lebih sedikit ketidakpastian) daripada mengidentifikasi hasil dari lemparan dadu (yang memiliki enam hasil yang sama mungkin). Beberapa ukuran penting lainnya dalam teori informasi adalah informasi saling, kapasitas saluran, eksponen kesalahan, dan entropi relatif. Subbidang penting dari teori informasi meliputi pemampatan sumber, teori kompleksitas algoritmik, teori informasi algoritmik, dan keamanan berdasarkan informasi.
Aplikasi dari topik fundamental teori informasi termasuk pemampatan data (misalnya untuk file ZIP), dan deteksi dan koreksi kesalahan saluran (misalnya untuk DSL). Dampaknya telah sangat penting bagi kesuksesan misi Voyager ke luar angkasa, penemuan compact disc, kelayakan ponsel pintar, dan pengembangan Internet dan kecerdasan buatan. Teori juga telah diterapkan dalam berbagai bidang lain, termasuk inferensi statistik, kriptografi, neorobiologi, persepsi, pemrosesan sinyal, linguistik, evolusi dan fungsi kode molekuler (bioinformatika), fisika termal, dinamika molekuler, lubang hitam, komputasi kuantum, pengambilan informasi, deteksi plagiarisme, pengenalan pola, deteksi anomali, analisis musik, penciptaan seni, desain sistem pengambilan gambar, studi luar angkasa, dimensi ruang, dan epistemologi.
Pandangan umum
Teori informasi mempelajari transmisi, pemrosesan, ekstraksi, dan pemanfaatan informasi. Secara abstrak, informasi dapat dipikirkan sebagai penyelesaian ketidakpastian. Dalam kasus komunikasi informasi melalui saluran berisik, konsep abstrak ini diformalkan pada tahun 1948 oleh Claude Shannon dalam sebuah makalah berjudul Teori Komunikasi Matematika, di mana informasi dipikirkan sebagai himpunan pesan yang mungkin, dan tujuannya adalah untuk mengirim pesan-pesan ini melalui saluran berisik, dan memiliki penerima merekonstruksi pesan dengan probabilitas kesalahan rendah, meskipun ada noise saluran. Hasil utama Shannon, teorema pengkodean saluran berisik, menunjukkan bahwa, dalam batas penggunaan saluran yang banyak, tingkat informasi yang dapat dicapai secara asimtotik sama dengan kapasitas saluran, sebuah jumlah yang hanya tergantung pada statistik saluran di mana pesan-pesan dikirim.
Teori pengodean berkaitan dengan menemukan metode eksplisit, yang disebut kode, untuk meningkatkan efisiensi dan mengurangi tingkat kesalahan komunikasi data melalui saluran berisik hingga mendekati kapasitas saluran. Kode-kode ini dapat secara kasar dibagi menjadi teknik kompresi data (pengodean sumber) dan teknik koreksi kesalahan (pengodean saluran). Dalam kasus terakhir, dibutuhkan bertahun-tahun untuk menemukan metode-metode yang bekerja yang dibuktikan oleh karya Shannon.
Kelas ketiga dari kode-kode teori informasi adalah algoritma kriptografi (baik kode maupun sandi). Konsep, metode, dan hasil dari teori pengodean dan teori informasi secara luas digunakan dalam kriptografi dan kriptanalisis, seperti larangan unit.
Kuantitas informasi ini didasarkan pada teori probabilitas dan statistik, di mana informasi yang terkuantifikasi biasanya dijelaskan dalam istilah bit. Teori informasi seringkali berkaitan dengan pengukuran informasi dari distribusi yang terkait dengan variabel acak. Salah satu pengukuran paling penting disebut entropi, yang membentuk dasar dari banyak pengukuran lainnya. Entropi memungkinkan pengukuran dari informasi dalam satu variabel acak.
Konsep lain yang berguna adalah informasi bersama yang didefinisikan pada dua variabel acak, yang menggambarkan informasi yang sama antara variabel tersebut, yang dapat digunakan untuk menggambarkan korelasi mereka. Kuantitas pertama adalah properti distribusi probabilitas dari variabel acak dan memberikan batasan pada tingkat di mana data yang dihasilkan oleh sampel independen dengan distribusi yang diberikan dapat dikompres dengan andal. Yang terakhir adalah properti dari distribusi bersama dari dua variabel acak, dan merupakan tingkat maksimum komunikasi yang andal melintasi saluran berisik dalam batas blok panjang, ketika statistik saluran ditentukan oleh distribusi bersama.
Pemilihan basis logaritma dalam rumus berikut menentukan satuan entropi informasi yang digunakan. Satuan umum informasi adalah bit atau shannon, berdasarkan logaritma biner. Satuan lain termasuk nat, yang didasarkan pada logaritma alami, dan digit desimal, yang didasarkan pada logaritma umum.
Dalam apa yang akan saya jelaskan berikut, ekspresi dalam bentuk p log p dianggap sama dengan nol ketika p = 0. Hal ini dibenarkan karena lim p → 0 + p log p = 0 untuk setiap basis logaritma.
Entropi dari sumber informasi
Berdasarkan fungsi massa probabilitas dari suatu sumber, entropi Shannon H, dalam satuan bit per simbol, didefinisikan sebagai nilai harapan dari konten informasi dari simbol-simbol.
Jumlah informasi yang disampaikan oleh satu simbol sumber individu x i dengan probabilitas p i dikenal sebagai informasi diri atau kejutan, I ( p i ). Kuantitas ini didefinisikan sebagai:
I ( p i ) = − log 2 ( p i )
Simbol yang kurang mungkin memiliki kejutan yang lebih besar, artinya keberadaannya memberikan lebih banyak informasi. Entropi H adalah rata-rata tertimbang dari kejutan semua simbol yang mungkin dari distribusi probabilitas sumber:
H (X) = EX [I (x)] = ∑ i p i I (p i) = − ∑ i p i log 2 (p i)
Secara intuitif, entropi H (X) dari variabel acak diskrit X adalah ukuran dari jumlah ketidakpastian yang terkait dengan nilai X ketika hanya distribusinya yang diketahui. Entropi yang tinggi menunjukkan hasil yang lebih merata didistribusikan, membuat hasil lebih sulit diprediksi.
Sebagai contoh, jika seseorang mentransmisikan 1000 bit (0 dan 1), dan nilai masing-masing bit ini diketahui oleh penerima (memiliki nilai tertentu dengan pasti) sebelum transmisi, tidak ada informasi yang ditransmisikan. Namun, jika setiap bit secara independen dan sama mungkinnya untuk menjadi 0 atau 1, 1000 shannon informasi (lebih sering disebut sebagai bit) telah ditransmisikan.
Sifat kunci dari entropi adalah bahwa entropi maksimal ketika semua pesan dalam ruang pesan memiliki probabilitas yang sama. Untuk sumber dengan n simbol yang mungkin, di mana pi = 1 / n untuk semua i, entropi diberikan oleh:
H ( X ) = log 2 ( n )
Nilai maksimum ini mewakili keadaan yang paling tidak terduga. Untuk sumber yang mengeluarkan rangkaian N simbol yang independen dan identik didistribusikan (i.i.d.), total entropi pesan adalah N ⋅ H bit. Jika simbol data sumber didistribusikan secara identik tetapi tidak independen, entropi dari pesan dengan panjang N akan lebih kecil dari N ⋅ H.
Unit
Pilihan basis logaritma dalam rumus entropi menentukan unit entropi yang digunakan:
Logaritma basis-2 (seperti yang ditunjukkan dalam rumus utama) mengukur entropi dalam bit per simbol. Unit ini terkadang disebut shannon untuk menghormati Claude Shannon. Logaritma alami (basis e) mengukur entropi dalam nat per simbol. Ini sering digunakan dalam analisis teoretis karena menghindari kebutuhan konstan penskalaan (seperti ln 2) dalam derivasi. Basis lain juga memungkinkan. Logaritma basis-10 mengukur entropi dalam digit desimal, atau hartleys, per simbol. Logaritma basis-256 mengukur entropi dalam byte per simbol, karena 28 = 256.
Fungsi Entropi Binari
Kasus khusus entropi informasi untuk variabel acak dengan dua hasil (percobaan Bernoulli) adalah fungsi entropi biner. Ini biasanya dihitung menggunakan logaritma basis-2, dan unitnya adalah shannon. Jika satu hasil memiliki probabilitas p, yang lain memiliki probabilitas 1 - p. Entropi diberikan oleh:
H b ( p ) = - p log 2 p - ( 1 - p ) log 2 ( 1 - p )
Fungsi ini digambarkan dalam plot di atas, mencapai maksimum 1 bit ketika p = 0,5, yang sesuai dengan ketidakpastian tertinggi.
Entropi bersama dari dua variabel acak diskrit X dan Y hanyalah entropi dari pasangan mereka: (X, Y). Ini berarti bahwa jika X dan Y independen, maka entropi bersama mereka adalah jumlah entropi individu mereka.
Contohnya, jika (X, Y) mewakili posisi seorang bidak catur - X baris dan Y kolom, maka entropi bersama dari baris bidak dan kolom bidak akan menjadi entropi dari posisi bidak tersebut.
H (X, Y) = E X, Y [ - log p (x, y) ] = - Σ x, y p (x, y) log p (x, y)
Meskipun notasi yang mirip, entropi bersama sebaiknya tidak dikacaukan dengan cross-entropy.
Entropi kondisional atau ketidakpastian kondisional dari X diberikan variabel acak Y (juga disebut sebagai kebingungan X tentang Y) adalah rata-rata entropi kondisional atas Y:
H (X | Y) = E Y [ H (X | y)] = - Σ y ∈ Y p (y) Σ x ∈ X p (x | y) log p (x | y) = - Σ x, y p (x, y) log p (x | y).
Karena entropi dapat dikondisikan pada variabel acak atau pada variabel acak itu menjadi nilai tertentu, perhatian harus diambil agar tidak bingung antara kedua definisi entropi kondisional ini, yang pertama lebih umum digunakan. Sifat dasar dari bentuk entropi kondisional ini adalah bahwa:
H (X | Y) = H (X, Y) - H (Y).
Informasi mutual mengukur jumlah informasi yang dapat diperoleh tentang satu variabel acak dengan mengamati yang lain. Ini penting dalam komunikasi di mana itu dapat digunakan untuk memaksimalkan jumlah informasi yang dibagikan antara sinyal yang dikirim dan diterima. Informasi mutual dari X relatif terhadap Y diberikan oleh:
I (X; Y) = E X, Y [SI (x, y)] = Σ x, y p (x, y) log p (x, y) p (x) p (y)
di mana SI (Informasi Mutual Spesifik) adalah informasi mutual titik demi titik. Sifat dasar dari informasi mutual adalah bahwa:
I (X; Y) = H (X) - H (X | Y).
Yaitu, dengan mengetahui Y, kita dapat menghemat rata-rata I(X; Y) bit dalam encoding X dibandingkan dengan tidak mengetahui Y. Informasi mutual bersifat simetris:
I (X; Y) = I (Y; X) = H (X) + H (Y) - H (X, Y).
Informasi mutual dapat diungkapkan sebagai rata-rata divergensi Kullback-Leibler (keuntungan informasi) antara distribusi probabilitas posterior X diberikan nilai Y dan distribusi sebelumnya pada X:
I (X; Y) = E p (y) [D KL (p (X | Y = y) ‖ p (X)).
Dengan kata lain, ini adalah ukuran seberapa besar, secara rata-rata, distribusi probabilitas pada X akan berubah jika kita diberikan nilai Y. Ini sering dihitung ulang sebagai divergensi dari hasil perkalian dari distribusi margin ke distribusi bersama aktual:
I (X; Y) = D KL (p (X, Y) ‖ p (X) p (Y)).
Informasi mutual erat kaitannya dengan uji rasio log-likelihood dalam konteks tabel kontingensi dan distribusi multinomial dan dengan uji χ2 Pearson: informasi mutual dapat dianggap sebagai statistik untuk menilai kemandirian antara sepasang variabel, dan memiliki distribusi asimtotik yang ditentukan dengan baik.
Divergensi Kullback-Leibler (atau ganjaran informasi) adalah cara untuk membandingkan dua distribusi: distribusi probabilitas "benar" p(X), dan distribusi probabilitas sembarang q(X). Jika kita menyusutkan data dengan asumsi q(X) adalah distribusi yang mendasari data, padahal sebenarnya p(X) adalah distribusi yang benar, divergensi Kullback-Leibler adalah jumlah tambahan rata-rata bit per data yang diperlukan untuk kompresi. Dengan demikian, divergensi ini didefinisikan sebagai jumlah x di X-p(x) log q(x) - jumlah x di X-p(x) log p(x) = jumlah x di X p(x) log p(x)/q(x).
Meskipun kadang-kadang digunakan sebagai 'metrik jarak', divergensi KL bukanlah metrik sejati karena tidak simetris dan tidak memenuhi ketentuan ketidaksetaraan segitiga (membuatnya menjadi semi-kuasimetrik). Interpretasi lain dari divergensi KL adalah "kejutan tidak perlu" yang diperkenalkan oleh suatu prior dari kebenaran: anggaplah sebuah bilangan X akan diambil secara acak dari himpunan diskrit dengan distribusi probabilitas p(x). Jika Alice mengetahui distribusi yang sebenarnya p(x), sementara Bob percaya (memiliki prior) bahwa distribusi tersebut adalah q(x), maka Bob akan lebih terkejut daripada Alice, rata-rata, saat melihat nilai X. Divergensi KL adalah nilai ekspektasi (objektif) dari keheranan Bob (subjektif) dikurangi keheranan Alice, diukur dalam bit jika logaritma berbasis 2. Dengan cara ini, sejauh mana prior Bob "salah" bisa diukur dalam hal seberapa "tidak perlu terkejutnya" diperkirakan akan membuatnya.
Informasi Terarah, I (X n → Y n), adalah sebuah pengukuran teori informasi yang mengukur aliran informasi dari proses acak X n = {X 1, X 2, ..., X n} ke proses acak Y n = {Y 1, Y 2, ..., Y n}. Istilah informasi terarah diciptakan oleh James Massey dan didefinisikan sebagai:
I (X n → Y n) ≜ ∑ i = 1 n I (X i; Y i | Y i−1),
di mana I (X i; Y i | Y i−1) adalah informasi timbal balik bersyarat I (X 1, X 2, ..., X i; Y i | Y 1, Y 2, ..., Y i−1).
Berbeda dengan informasi timbal balik, informasi terarah tidak simetris. I (X n → Y n) mengukur bit informasi yang ditransmisikan secara kausal dari X n ke Y n. Informasi Terarah memiliki banyak aplikasi dalam masalah di mana kausalitas memainkan peran penting seperti kapasitas saluran dengan umpan balik, kapasitas jaringan diskrit tanpa memori dengan umpan balik, perjudian dengan informasi samping kausal, kompresi dengan informasi samping kausal, pengaturan komunikasi kontrol real-time, dan dalam fisika statistik.
Kuantitas informasi teoretis penting lainnya meliputi entropi Rényi dan entropi Tsallis (generalisasi dari konsep entropi), entropi diferensial (generalisasi dari kuantitas informasi ke distribusi kontinu), dan informasi timbal balik bersyarat. Selain itu, informasi pragmatis telah diusulkan sebagai ukuran seberapa banyak informasi yang telah digunakan dalam membuat keputusan.
Posting Komentar