Θεωρία πληροφορίας

Η θεωρία πληροφορίας είναι τμήμα των εφαρμοσμένων μαθηματικών και ασχολείται με την ποσοτικοποίηση της πληροφορίας. Η θεωρία της πληροφορίας αναπτύχθηκε από τον Κλοντ Σάνον για να βρει τα θεμελιώδη όρια της επεξεργασίας σήματος σε εφαρμογές όπως η συμπίεση δεδομένων και η αξιόπιστη αποθήκευση και μετάδοση δεδομένων. Από τη θεμελίωση της έχει διευρυνθεί ώστε να βρει εφαρμογές σε πολλούς άλλους τομείς, όπως στην θεωρία πιθανοτήτων, την στατιστική, την πληροφορική, την επεξεργασία φυσικής γλώσσας, την κρυπτογραφία, στα δίκτυα εκτός των δικτύων επικοινωνίας - όπως και στη νευροβιολογία,^[1] στην εξέλιξη^[2] και τη λειτουργία^[3] μοριακών κωδικών στην οικολογία, στους κβαντικούς υπολογιστές, στην ανίχνευση λογοκλοπής και σε άλλες μορφές ανάλυσης δεδομένων.^[4]

Μία βασική ποσότητα στην θεωρία πληροφορίας είναι η εντροπία. Η εντροπία ποσοτικοποιεί την αβεβαιότητα που εμπλέκεται στην πρόβλεψη της τιμής μίας τυχαίας μεταβλητής. Για παράδειγμα, το αποτέλεσμα μίας ρίψης ενός "δίκαιου" νομίσματος (–Κορώνα ή γράμματα– δύο ισοδύναμα πιθανά αποτελέσματα) παρέχει λιγότερη πληροφορία (δηλαδή μικρή εντροπία) από τον αν θα έχει ήλιο στην Αθήνα τον επόμενο δεκαπενταύγουστο (πάλι είναι δύο πιθανά αποτελέσματα, αλλά το ενδεχόμενο του ήλιου είναι πολύ πιο πιθανό).

Τα θεμελιώδη θέματα της θεωρίας της πληροφορίας βρίσκουν εφαρμογές στην συμπίεση δεδομένων (στα αρχεία ZIP, MP3 και JPEG), και την χωρητικότητα καναλιού (στην ψηφιακή συνδρομητική γραμμή DSL). Ο τομέας είναι στην «διασταύρωση» των μαθηματικών, της στατιστικής, της επιστήμης των υπολογιστών, της φυσικής, της νευρολογίας και της ηλεκτρικής εφαρμοσμένης μηχανικής. Πολλές από τις εφαρμογές του είναι κρίσιμες για την επιτυχία των αποστολών του Βόγιατζερ στο διάστημα, την ανακάλυψη του CD, την κατασκευή των κινητών τηλεφώνων, την εξέλιξη του διαδικτύου, την επιστήμη της γλωσσολογίας και της ανθρώπινης αντίληψης, την κατανόηση των μαύρων τρυπών και πολλών ακόμη άλλων πεδίων. Σημαντικά «υπο-πεδία» της θεωρίας πληροφορίας είναι ο πηγαίος κώδικας, η χωρητικότητα καναλιού, η αλγοριθμική θεωρία πολυπλοκότητας, η αλγοριθμική θεωρία της πληροφορίας, τα στοιχεία θεωρίας της ασφάλειας, καθώς και τα μέτρα ενημέρωσης.

Επισκόπηση

Οι κύριες έννοιες της θεωρίας πληροφορίας μπορούν να γίνουν αντιληπτές λαμβάνοντας υπόψη το πιο διαδεδομένο μέσο της ανθρώπινης επικοινωνίας: τη γλώσσα. Δύο σημαντικές πλευρές μιας περιεκτικής γλώσσας είναι: Πρώτον, οι πιο κοινές ελληνικές λέξεις (όπως "το", "και", "εγώ") πρέπει να είναι συντομότερες από τις όχι τόσο κοινές λέξεις (όπως "περίτεχνος", "γενίκευση", "αμφιταλαντεύεται"), έτσι ώστε οι προτάσεις να μην είναι πολύ μεγάλες. Μια τέτοια εξισορρόπηση στο μήκος των λέξεων είναι ανάλογη με την συμπίεση δεδομένων και είναι απαραίτητο χαρακτηριστικό του πηγαίου κώδικα. Δεύτερον, αν ένα μέρος της πρότασης δεν ακούστηκε ή ακούστηκε λάθος λόγω ενός θορύβου - για παράδειγμα, ένα διερχόμενο αυτοκίνητο - ο ακροατής πρέπει να είναι ικανός να περισυλλέξει το νόημα από το υποκρυπτόμενο μήνυμα. Μία τέτοια ιδιότητα είναι τόσο σημαντική για ένα ηλεκτρονικό σύστημα επικοινωνίας όσο είναι και για την γλώσσα: Πιο σωστά, ο «σχεδιασμός» μιας τέτοιας ιδιότητας στις επικοινωνίες γίνεται χρησιμοποιώντας την έννοια της χωρητικότητας καναλιού. Ο πηγαίος κώδικας και η χωρητικότητα καναλιού είναι οι κύριες έννοιες της θεωρίας της πληροφορίας.

Σημειώστε ότι αυτές οι έννοιες δεν έχουν καμία σχέση με την σημαντικότητα των μηνυμάτων. Για παράδειγμα, μια κοινή έκφραση όπως το “Ευχαριστώ πολύ”, χρειάζεται περίπου τον ίδιο χρόνο με το να πεις ή να γράψεις την επείγουσα έκκληση “Κάλεσε ασθενοφόρο”, καθώς το τελευταίο μπορεί να είναι πιο σημαντικό και με περισσότερο νόημα. Παρόλα αυτά η θεωρία πληροφορίας, δεν λαμβάνει υπ’όψη τη σημαντικότητα του μηνύματος ή τη σημασία του, επειδή αυτά είναι ζητήματα της ποιότητας των δεδομένων και όχι από την ποσότητα και την αναγνωσιμότητα των δεδομένων, η τελευταία εκ των οποίων καθορίζεται αποκλειστικά από τις πιθανότητες.

Η θεωρία πληροφορίας γενικά θεωρείται ότι θεμελιώθηκε το 1948 από τον Κλοντ Σάνον με την εργασία του «A Mathematical Theory of Communication». Το κλασσικό παράδειγμα της θεωρίας της πληροφορίας είναι το μηχανικό πρόβλημα της μετάδοσης της πληροφορίας μέσα από έναν θορυβώδες κανάλι. Τα πιο θεμελιώδη αποτελέσματα από αυτήν την θεωρία είναι το θεώρημα του Σάνον για τον πηγαίο κώδικα, που καθιερώνει ότι, κατά μέσο όρο, ο αριθμός των δυαδικών ψηφίων (bits) που χρειάζονται για να αναπαρασταθεί το αποτέλεσμα ενός αβέβαιου γεγονότος δίνεται από την εντροπία πληροφοριών του, και από το θεώρημα του Σάνον για το θορυβώδες κανάλι μεταφοράς, το οποίο δηλώνει ότι η αξιόπιστη επικοινωνία είναι δυνατή σε θορυβώδη κανάλια με την προϋπόθεση ότι ο συντελεστής της επικοινωνίας είναι κάτω από ένα ορισμένο όριο, το οποίο ονομάζεται χωρητικότητα καναλιού. Στην πράξη μπορούμε να προσεγγίσουμε την χωρητικότητα καναλιού χρησιμοποιώντας κατάλληλα συστήματα κωδικοποίησης και αποκωδικοποίησης.

Η Θεωρία της κωδικοποίησης ασχολείται βρίσκοντας ξεκάθαρες μεθόδους-κωδικες για να αυξήσει την απόδοση και να μειώσει τα σφάλματα δικτύου της επικοινωνίας των δεδομένων από ένα θορυβώδες κανάλι για να πλησιάσει το όριο που ο Σάνον απέδειξε ότι είναι το μέγιστο δυνατό για ένα τέτοιο κανάλι. Αυτοί οι κώδικες μπορούν να υποδιαιρεθούν σε συμπίεση δεδομένων και σε ανίχνευση και διόρθωση σφαλμάτων. Στην τελευταία αυτή περίπτωση πήρε πολλά χρόνια για να βρεθούν οι μέθοδοι, που ο Σάνον δουλεψε, αποδεικνύοντας ότι είναι εφικτές. Μιας τρίτης τάξεως κώδικες της θεωρίας της πληροφορίας είναι οι κρυπτογραφικοί αλγόριθμοι (κώδικες και αποκρυπτογραφήματα). Οι έννοιες, οι μέθοδοι και τα αποτελέσματα από τη Θεωρία Κωδικοποίησης και τη Θεωρία της Πληροφορίας χρησιμοποιούνται ευρέως στην Κρυπτογραφία και στην Κρυπτανάλυση.

Η θεωρία της πληροφορίας χρησιμοποιείται επίσης στην ανάκτηση πληροφοριών, συλλογή πληροφοριών, στα τυχερά παιχνίδια, στην στατιστική, ακόμα και στην σύνθεση μουσικής.

Ιστορική αναδρομή

Το ορόσημο γεγονός που καθιέρωσε τον επιστημονικό κλάδο της θεωρίας της πληροφορίας και τον έφερε σε άμεση παγκόσμια προσοχή ήτανε η δημοσίευση του Κλοντ Σάνον, με τίτλο “A Mathematical Theory of Communication” στο επιστημονικό περιοδικό Bell System Technical Journal τον Ιούλιο και τον Οκτώβριο του 1948.

Πριν από αυτή τη δημοσίευση περιορισμένες ιδέες της θεωρίας πληροφοριών είχαν αναπτυχθεί στα εργαστήρια Bell labs, όλες υποθέτοντας γεγονότα ίσης πιθανότητας. Η δημοσίευση του Harry Nyquist το 1924, με τίτλο «Certain Factors Affecting Telegraph Speed», περιέχει ένα θεωρητικό τμήμα που ποσοτικοποιεί τη νοημοσύνη και την ταχύτητα γραμμής κατά την οποία μπορεί να μεταδοθεί από ένα σύστημα επικοινωνίας, δίνοντας την σχέση $W=K\log m$ όπου το $W$ είναι η ταχύτητα μετάδοσης της νοημοσύνης, $m$ το πλήθος των διαφορετικών επίπεδων τάσης που μπορούμεν να επιλέξουμε σε κάθε χρονικό βήμα και $K$ είναι μια σταθερά. Η δημοσίευση του Ralph Hartley το 1928 με τίτλο «Transmission of Information», χρησιμοποιεί την λέξη πληροφορία ως μια μετρήσιμη ποσότητα που αντανακλά την ικανότητα του δέκτη να ξεχωρίζει μία σειρά από σύμβολα από μία οποιαδήποτε άλλη, έτσι ποσοτικοποιεί την πληροφορία $H=\log S^{n}=n\log S$ , όπου $S$ είναι το πλήθος των πιθανών συμβόλων και $n$ ο αριθμός των συμβόλων σε μία μετάδοση. Η φυσική μονάδα πληροφοριών ήταν επομένως το δεκαδικό ψηφίο, όπου αργότερα μετονομάστηκε σε hartley προς τιμήν του ως μονάδα ή κλίμακα μέτρησης της πληροφορίας. Ο Άλαν Τούρινγκ το 1940 χρησιμοποίησε παρόμοιες ιδέες σαν κομμάτι μιας στατιστικής ανάλυσης για το “σπάσιμο” των αλγορίθμων κρυπτογράφησης των Γερμανών κατά τον Δεύτερο Παγκόσμιο πόλεμο. Πολλά από τα μαθηματικά ″πίσω″ από την θεωρία της πληροφορίας αναπτύχθηκαν για το πεδίο της θερμοδυναμικής από τον Λούντβιχ Μπόλτσμαν και Τζοσάια Γουίλαρντ Γκιμπς. Οι σχέσεις μεταξύ πληροφορίας-θεωρητικής εντροπίας και της θερμοδυναμικής εντροπίας, συμπεριλαμβανομένων των σημαντικών συνεισφορών του Rolf Landauer] τη δεκαετία του 1960, διερευνώνται στο άρθρο «Entropy in thermodynamics and information theory».

Στην επαναστατική και πρωτοποριακή εργασία, η οποία είχε ολοκληρωθεί στα Bell Labs στα τέλη του 1944, ο Σάνον για πρώτη φορά εισήγαγε το ποσοτικό και ποιοτικό μοντέλο επικοινωνίας ως μια στατιστική διαδικασία που στηρίζεται η θεωρία της πληροφορίας, εισάγοντας τον ισχυρισμό ότι:

το θεμελιώδες πρόβλημα της επικοινωνίας είναι αυτό της αναπαραγωγής σε ένα σημείο, είτε ακριβώς είτε κατά προσέγγιση, ενός μηνύματος που επιλέχτηκε σε ένα άλλο σημείο.

Με αυτό κατέληξαν στις επινοήσεις:

της εντροπίας πληροφοριών και του πλεονασμού (το πλήθος των δυαδικών ψηφίων που χρησιμοποιούνται για την μετάδοση ενός μηνύματος μείον τον αριθμό των δεκαδικών ψηφίων της πραγματικής πληροφορίας σε ένα μήνυμα) μιας πηγής, και τη σημασία της μέσω του θεωρήματος του πηγαίου κώδικα
της κοινής πληροφορίας και της χωρητικότητα καναλιού ενός θορυβώδους καναλιού, συμπεριλαμβανομένης και της υπόσχεσης για τέλεια, χωρίς απώλειες επικοινωνία που δίνεται από το θεώρημα του θορυβώδους καναλιού.
του πρακτικού αποτελέσματος του νόμου Shannon-Hartley για τη χωρητικότητα του καναλιού ενός Gaussian καναλιού, καθώς επίσης
του bit - μία καινούργια οπτική για την πιο θεμελιώδη μονάδα πληροφορίας.

Ποσότητες πληροφορίας

Η θεωρία της πληροφορίας βασίζεται στη θεωρία πιθανοτήτων και στη στατιστική. Οι σημαντικότερες ποσότητες της πληροφορίας είναι η εντροπία, η πληροφορία σε μία τυχαία μεταβλητή, και η κοινή πληροφορία: η ποσότητα από κοινού της πληροφορίας ανάμεσα σε δύο τυχαίες μεταβλητές. Η πρότερη ποσότητα υποδεικνύει το πόσο εύκολα συμπιέζονται τα δεδομένα μηνύματος ενώ η τελευταία χρησιμοποιείται για να διαπιστωθεί το ποσοστό της επικοινωνίας δια μέσου ενός καναλιού μετάδοσης.

Η επιλογή της βάσης του λογαρίθμου στη φόρμουλα που επακολουθεί καθορίζει το σύνολο της πληροφορίας της εντροπίας που χρησιμοποιήθηκε. Η συνηθέστερη μονάδα της πληροφορίας είναι το bit, βασιζόμενο στον δυαδικό λογάριθμο ( $\log _{2}$ ) . Άλλες μονάδες συμπεριλαμβανομένου του nat, το οποίο βασίζεται στον φυσικό λογάριθμο (λογάριθμος με βαση το $e$ ), και στο hartley ή ban το οποίο βασίζεται στον κοινό λογάριθμο (λογάριθμος με βάση το 10).

Σε αυτά που ακολουθούν, η έκφραση της μορφής $p\log p$ θεωρείται συμβατικά να είναι ίση με 0 όταν $p=0$ . Αυτό δικαιολογείται επειδή $\lim _{p\rightarrow 0+}p\log p=0$ σε οποιαδήποτε λογαριθμική βάση.

Εντροπία

Η εντροπία, $H$ , μιας διακριτής τυχαίας μεταβλητής $X$ είναι ένα μέτρο της ποσότητας της αβεβαιότητας που σχετίζεται με τη τιμή του $X$ . Ας υποθέσουμε ότι θέλουμε να μεταδόσουμε 1000 bits (τα δυαδικά ψηφία 0 και 1). Εάν αυτά τα bits είναι γνωστά πριν από την μετάδοση (δηλαδή έχουν συγκεκριμένη τιμή με πιθανότητα $1$ ), είναι λογικό ότι καμία πληροφορία δεν θα μεταδοθεί. Αν, ωστόσο, κάθε bit είναι ισοπίθανα και ανεξάρτητα πιθανό να είναι 0 ή 1, τότε 1000 bits (υπό την έννοια της θεωρίας της πληροφορίας) πρέπει να μεταδοθούν. Μεταξύ αυτών των δύο άκρων, η πληροφορία μπορεί να ποσοτικοποιηθεί όπως ακολουθεί. Αν $\mathbb {X}$ είναι το σύνολο από όλα τα μηνύματα $\{x_{1},\dots ,x_{n}\}$ που η τυχαία μεταβλητή $X$ μπορεί να λάβει, και $p(x)$ είναι η πιθανότητα κάποιου $x\in \mathbb {X}$ , τότε η εντροπία $H$ του $X$ ορίζεται ως:

H(X)=\mathbb {E} _{X}[I(x)]=-\sum _{x\in \mathbb {X} }p(x)\log p(x)

,

όπου το $I(x)$ είναι η «αυτό-πληροφορία», που είναι η συνεισφορά της εντροπίας σε ένα μήνυμα, και $\mathbb {E} _{X}$ είναι η αναμενόμενη τιμή. Μια σημαντική ιδιότητα της εντροπίας είναι ότι μεγιστοποιείται όταν όλα τα μηνύματα στο χώρο είναι ισοπίθανα $p(x)=1/n$ , - δηλαδή πιο απρόβλεπτα - στην οποία περίπτωση $H(X)=\log n$ .

Η ειδική περίπτωση της εντροπίας για μια τυχαία μεταβλητή με δύο ενδεχόμενα είναι η δυαδική συνάρτηση της εντροπίας, που συνήθως αναγάγεται στην λογαριθμική βάση 2

H_{\mathrm {b} }(p)=-p\log _{2}p-(1-p)\log _{2}(1-p)

.

Κοινή εντροπία

Η κοινή εντροπία δύο διακριτών μεταβλητών $X$ και $Y$ είναι απλά η εντροπία από το ζεύγος : $(X,Y)$ . Αυτό συνεπάγεται ότι αν τα $X$ και $Y$ είναι ανεξάρτητα, τότε η κοινή εντροπία είναι το άθροισμα από τις ατομικές εντροπίες. Για παράδειγμα, αν $(X,Y)$ συμβολίζει την θέση από ένα πιόνι σκακιού - $X$ η γραμμή και $Y$ η στήλη, τότε η κοινή εντροπία της γραμμής και της στήλης του πιονιού θα είναι η εντροπία της θέσης του. Πιο αυστηρά,

H(X,Y)=\mathbb {E} _{X,Y}[-\log p(x,y)]=-\sum _{x,y}p(x,y)\log p(x,y)

.

Παρά τον παρόμοιο τρόπο γραφής, η κοινή εντροπία δεν πρέπει να συγχέεται με την «διασταυρούμενη εντροπία».

Η υπό συνθήκη εντροπία

Η υπό συνθήκη εντροπία ή υπό συνθήκη αβεβαιότητα του $X$ , δεδομένης τυχαίας μεταβλητής $Y$ , είναι η μέση υπό συνθήκη εντροπία πάνω από το $Y$

H(X|Y)=\mathbb {E} _{Y}[H(X|y)]=-\sum _{y\in Y}p(y)\sum _{x\in X}p(x|y)\log p(x|y)=-\sum _{x,y}p(x,y)\log {\frac {p(x,y)}{p(y)}}

.

Επειδή η εντροπία μπορεί να εξαρτηθεί από μια τυχαία μεταβλητή ή από αυτήν την μεταβλητή που έχει μια συγκεκριμένη τιμή, χρειάζεται προσοχή ώστε να μην συγχέονται αυτοί οι δύο ορισμοί της υπό συνθήκη εντροπίας, με τον πρώτο να χρησιμοποιείται συχνότερα. Μια βασική ιδιότητα αυτού του τύπου της υπό συνθήκη εντροπίας είναι ότι

H(X|Y)=H(X,Y)-H(Y)

.

Κοινή πληροφορία (μετα-πληροφορία)

Η κοινή πληροφορία μετρά το ποσό της πληροφορίας που μπορεί να αποκτηθεί για μια τυχαία μεταβλητή παρατηρώντας μια άλλη. Είναι σημαντικό στην επικοινωνία όπου μπορεί να χρησιμοποιηθεί για να μεγιστοποιήσει την ποσότητα της πληροφορίας που μοιράζεται ανάμεσα σε σταλμένα και εισερχόμενα σήματα. Η κοινή πληροφορία του $X$ σε σχέση με το $Y$ δίνεται από

I(X;Y)=\mathbb {E} _{X,Y}[SI(x,y)]=\sum _{x,y}p(x,y)\log {\frac {p(x,y)}{p(x)\,p(y)}}

,

όπου $SI$ είναι η σημειακή κοινή πληροφορία.

Μια βασική ιδιότητα της κοινής πληροφορίας είναι ότι

I(X;Y)=H(X)-H(X|Y)

.

Με δεδομένο το $Y$ , μπορούμε να σώσουμε κατά μέσο όρο $I(X;Y)$ bits στην κωδικοποίηση του $X$ , από ότι αν το $Y$ είναι άγνωστο.

Η κοινή πληροφορία είναι συμμετρική: $I(X;Y)=I(Y;X)=H(X)+H(Y)-H(X,Y)$ .

Η κοινή πληροφορία μπορεί να εκφραστεί ως η μέση απόκλιση Kullback–Leibler ανάμεσα στην μεταγενέστερη κατανομή πιθανότητας του $X$ δεδομένης της τιμής του $Y$ και την προγενέστερη κατανομή στο $X$ : $I(X;Y)=\mathbb {E} _{p(y)}[D_{\mathrm {KL} }(p(X|Y=y)\|p(X))]$ .

Με άλλα λόγια, αυτή είναι μια μέτρηση του πόσο πολύ, κατά μέσο όρο, η κατανομή της πιθανότητας στο $X$ θα αλλάξει αν η τιμή του $Y$ είναι δεδομένη. Αυτό συνήθως επαναπροσδιορίζεται ως η απόκλιση από το γινόμενο της οριακής κατανομής επί την πραγματική κοινή κατανομή: $I(X;Y)=D_{\mathrm {KL} }(p(X,Y)\|p(X)p(Y))$ .

Η κοινή πληροφορία είναι άρρηκτα συνδεδεμένη με το log-likelihood ratio test (ένα στατιστικό τεστ που χρησιμοποιείται για να συγκρίνει τη φόρμα δυο μοντέλων) στα πλαίσια των πινάκων ενδεχομένων και της πολυωνυμικής κατανομής και στο στατιστικό $\chi ^{2}$ -τεστ του Pearson: η κοινή πληροφορία μπορεί να χρησιμοποιηθεί για τον υπολογισμό της ανεξαρτησίας μεταξύ ενός ζεύγους μεταβλητών και έχει καλά καθορισμένη ασυμπτωτική κατανομή.

Απόκλιση Kullback-Leibler

Η απόκλιση Κullback-Leibler (ή αλλιώς απόκλιση της πληροφορίας ή σχετική εντροπία) είναι ένας τρόπος για να συγκρίνεις δυο κατανομές: μια "πραγματική" κατανομή πιθανοτήτων $p(X)$ και μία αυθαίρετη κατανομή πιθανοτήτων $q(X)$ . Αν συμπιέσουμε δεδομένα με ένα τρόπο που υποθέτει ότι $q(X)$ είναι η κατανομή πίσω από κάποια δεδομένα, ενώ στην πραγματικότητα το $p(X)$ είναι η σωστή κατανομή, τότε η απόκλιση Kullback-Leibler είναι ο μέσος αριθμός επιπλέον bits ανά δεδομένο που είναι απαραίτητο για τη συμπίεση. Είναι επομένως ορισμένο

D_{\mathrm {KL} }(p(X)\|q(X))=\sum _{x\in X}-p(x)\log {q(x)}\,-\,\left(-p(x)\log {p(x)}\right)=\sum _{x\in X}p(x)\log {\frac {p(x)}{q(x)}}

.

Αν και μερικές φορές χρησιμοποιείται σαν μια μετρική απόσταση, η απόκλιση του Kullback-Leibler δεν είναι μία πραγματική μετρική εφόσον δεν είναι συμμετρική και δεν ικανοποιεί την τριγωνική ανισότητα.

Μια άλλη ερμηνεία της απόκλισης Kullback-Leibler είναι αυτή: ας υποθέσουμε ότι ένας αριθμός $X$ πρόκειται να επιλεχθεί από ένα διακριτό σύνολο με την κατανομή της πιθανότητας $p(X)$ . Αν η Αλίκη ξέρει την πραγματική κατανομή $p(X)$ ενώ ο Βασίλης πιστεύει ότι η κατανομή είναι $q(X)$ , τότε ο Βασίλης μπορεί να είναι πιο έκπληκτος από την Αλίκη, κατά μέσο όρο, βλέποντας την τιμή του $X$ . Η απόκλιση Kullback-Leibler είναι η αντικειμενική αναμενόμενη τιμή από του Βασίλη την κατάπληξη μείον την κατάπληξη της Αλίκης, μετρημένη σε bit αν ο λογάριθμος είναι στην βάση 2. Έτσι, ο βαθμός στον οποίο πιστεύει ο Βασίλης είναι "λάθος", αυτό μπορεί να ποσοτικοποιηθεί με όρους του κατά πόσο είναι αναμενόμενο να τον κάνει "άσκοπα έκπληκτο".

Άλλες ποσότητες

Άλλες σημαντικές ποσότητες της θεωρίας πληροφοριών συμπεριλαμβάνουν, την εντροπία Renyi (μια γενίκευση της εντροπίας), την διαφορική εντροπία (μια γενίκευση από ποσότητες πληροφορίας σε συνεχόμενες κατανομές) και την κοινή υπο συνθήκη πληροφορία.

Θεωρία Κωδικοποίησης

Φωτογραφία που δείχνει τα χαράγματα στην επιφάνεια ανάγνωσης ενός CD-R. Μουσική και δεδομένα κωδικοποιούνται με την χρήση κωδίκων διόρθωσης σφαλμάτων και επομένως μπορούν να διαβαστούν ακόμα και αν έχουν μικρές γρατζουνιές με μεθόδους ανίχνευσης και διόρθωσης σφαλμάτων.

Η θεωρία κωδικοποίησης είναι από τις σημαντικότερες και πιο άμεσες εφαρμογές της θεωρίας πληροφορίας. Μπορεί να υποδιαιρεθεί σε θεωρία πηγαίου κώδικα και σε θεωρία κωδικοποίησης καναλιού. Χρησιμοποιώντας μία στατιστική περιγραφή για δεδομένα, η θεωρία της πληροφορίας προσδιορίζει το πλήθος των bits που χρειάζονται για να περιγραφούν τα δεδομένα, ο οποίος είναι η εντροπία πληροφορίας της πηγής.

Συμπίεση δεδομένων: Υπάρχουν δύο ειδών προσεγγίσεις για το πρόβλημα της συμπίεσης:

Μη απωλεστική συμπίεση: μετά την συμπίεση και αποσυμπίεση, τα δεδομένα πρέπει να είναι ακριβώς τα ίδια με τα αρχικά
Απωλεστική συμπίεση: μετά την συμπίεση και αποσυμπίεση, τα δεδομένα δεν είναι τα ίδια, αλλά μπορεί να έχουν παραμορφωθεί σε κάποιον βαθμό. Το καθορισμένο επίπεδο πιστότητας συνήθως μετριέται από μία συνάρτηση. Αυτό το υποσύνολο της θεωρίας της πληροφορίας λέγεται θεωρία παραμόρφωσης-τιμής.

Κώδικες διόρθωσης σφαλμάτων: Ενώ η συμπίεση δεδομένων αφαιρεί όσο περιττολογία είναι δυνατόν, ένας κώδικας διόρθωσης σφαλμάτων προσθέτει ακριβώς το σωστό είδος του πλεονασμού που χρειάζεται για να μεταδοθούν τα δεδομένα αποτελεσματικά και έμπιστα στο θορυβώδες κανάλι.

Η πρώτη εικόνα είναι αποθηκευμένη με την μορφή SVG που είναι μία μη-απωλεστική μέθοδος. Οι επόμενες τρεις είναι αποθηκευμένες με την μορφή JPEG με μέγεθος 60%, 20% και 10% του αρχικού μεγέθους (αλλά με μεγαλύτερη παραμόρφωση).

Αυτή η "διαίρεση" της θεωρίας κωδικοποίησης σε συμπίεση και μετάδοση δικαιολογείται από τα θεωρήματα πληροφορίας μετάδοσης, ή από τα θεωρήματα διαχωρισμού πηγής-καναλιού που δικαιολογούν την χρήση των bits σαν το παγκόσμιο "νόμισμα" για την πληροφορία σε πολλές περιπτώσεις. Ωστόσο, αυτά τα θεωρήματα περιέχουν την κατάσταση όπου ένας χρήστης που μεταδίδει επιθυμεί να επικοινωνήσει με έναν χρήστη-αποδέκτη. Σε σενάρια με παραπάνω από έναν πομπούς, παραπάνω από έναν αποδέκτη (το τηλεοπτικό κανάλι) ή ενδιάμεσους "βοηθούς" (το αναμεταδιδόμενο κανάλι) ή περισσότερα γενικά δίκτυα, συμπίεση ακολουθούμενη από μετάδοση δεν μπορεί πλέον να είναι η καλύτερη δυνατή. Η θεωρία πληροφορίας δικτύου αναφέρεται σ αυτά τα μοντέλα επικοινωνίας με πολλούς συντελεστές.

Πηγαίος κώδικας

Οποιαδήποτε διαδικασία που παράγει επιτυχημένα μηνύματα μπορεί να θεωρηθεί ως μια πηγή πληροφορίας. Μια πηγή χωρίς μνήμη είναι μια στην οποία κάθε μήνυμα είναι μια ανεξάρτητη, ταυτόσημα κατανεμημένη, τυχαία μεταβλητή, ενώ οι ιδιότητες της εργοδικής θεωρίας και της στατικής διαδικασίας επιβάλλουν πιο γενικούς περιορισμούς. Όλες αυτές οι πηγές είναι στοχαστικές. Αυτοί οι όροι είναι καλά μελετημένοι στα δικά τους πεδία ανεξάρτητα από το πεδίο της θεωρίας πληροφοριών.

Ρυθμός

Ο ρυθμός της πληροφορίας είναι η μέση εντροπία για κάθε σύμβολο. Για πηγές χωρίς μνήμη, αυτό είναι απλά η εντροπία του κάθε συμβόλου, ενώ, στην περίπτωση μιας στατικής στοχαστικής διαδικασίας, ορίζεται ως

r=\lim _{n\to \infty }H(X_{n}|X_{n-1},X_{n-2},X_{n-3},\ldots )

,

δηλαδή, η υπό συνθήκη εντροπία ενός συμβόλου δεδομένων όλων των προηγούμενων συμβόλων που παράχθηκαν. Στην πιο γενική περίπτωση μιας διαδικασίας που δεν είναι απαραίτητα στατική, ο μέσος ρυθμός είναι

r=\lim _{n\to \infty }{\frac {1}{n}}H(X_{1},X_{2},\dots X_{n})

,

που είναι, το όριο της κοινής εντροπίας ανά σύμβολο. Για στατικές πηγές, αυτές οι δυο εκφράσεις δίνουν το ίδιο αποτέλεσμα. Είναι σύνηθες στην θεωρία της πληροφορίας να αναφερόμαστε στο «ρυθμό» ή την «εντροπία» μιας γλώσσας. Αυτό είναι κατάλληλο, για παράδειγμα, όταν η πηγή της πληροφορίας είναι η αγγλική πεζογραφία. Ο ρυθμός μιας πηγής πληροφορίας είναι συνδεδεμένος με τον πλεονασμό και με το πόσο καλά μπορεί να συμπιεστεί το αντικείμενο του πηγαίου κώδικα.

Χωρητικότητα καναλιού

Οι επικοινωνίες μέσω ενός καναλιού – όπως ένα καλώδιο Ethernet – είναι το πρωταρχικό κίνητρο της θεωρίας πληροφοριών. Όπως ο οποιοσδήποτε που έχει χρησιμοποιήσει ένα τηλέφωνο (σταθερό ή κινητό) ξέρει, ωστόσο, ότι τέτοια κανάλια συχνά αποτυγχάνουν να παράγουν ακριβή ανακατασκευή ενός σήματος λόγω θορύβων, περιόδους σιγής και άλλες μορφές φθοράς σήματος που συχνά μειώνουν την ποιότητα της μετάδοσης. Επομένως, γεννάται το ερώτημα, πόση πληροφορία κάποιος μπορεί να ελπίζει να μεταδώσει μέσω ενός θορυβώδους (ή αλλιώς ημιτελούς) καναλιού; Θεωρούμε τη διαδικασία επικοινωνίας μέσω ενός διακριτού καναλιού. Ένα απλό μοντέλο της διαδικασίας δίνεται παρακάτω:

Εδώ το Χ παριστάνει το σύνολο των μηνυμάτων που μεταδίδονται και Υ το σύνολο των εισερχόμενων μηνυμάτων στη μονάδα του χρόνου μέσω του καναλιού μας. Έστω $p(y|x)$ η συνάρτηση της δεσμευμένης πιθανότητας κατανομής του Υ δεδομένου του Χ. Θα θεωρήσουμε την $p(y|x)$ εγγενή σταθερή ιδιότητα του επικοινωνιακού μας καναλιού (που αντιπροσωπεύει τη φύση του θορύβου του καναλιού μας). Τότε η κοινή κατανομή του Χ και Υ είναι εντελώς καθορισμένη από το κανάλι μας και από την επιλογή της $f(x)$ , η οριακή κατανομή των μηνυμάτων που διαλέγουμε να στείλουμε μέσω του καναλιού. Κάτω από αυτούς τους περιορισμούς θα θέλαμε να μεγιστοποιήσουμε το ρυθμό της πληροφορίας ή του σήματος , που μπορούμε να μεταδίδουμε μέσω του καναλιού. Η κατάλληλη μέτρηση για αυτό είναι η κοινή πληροφορία και αυτή η μέγιστη κοινή πληροφορία καλείται χωρητικότητα καναλιού και δίνεται από τον τύπο:

C=\max _{f}I(X;Y)

.

Αυτή η χωρητικότητα έχει την ακόλουθη ιδιότητα που σχετίζεται με τη μετάδοση μιας πληροφορίας σε ρυθμό $R$ (όπου $R$ είναι συνήθως bits ανά σύμβολο). Για οποιοδήποτε ρυθμό πληροφορίας $R<C$ και σφάλμα κώδικα $\epsilon >0$ , για ένα αρκετά μεγάλο $N$ , υπάρχει ένας κώδικας μήκους $N$ και ρυθμού τουλάχιστον $R$ και ένας αλγόριθμος αποκωδικοποίησης τέτοιος ώστε η μέγιστη πιθανότητα ενός τετραγωνικού σφάλματος να είναι το πολύ $\epsilon$ . Είναι πάντα πιθανό να μεταδοθεί με αυθαίρετα μικρό τετραγωνικό σφάλμα. Επιπροσθέτως για οποιοδήποτε ρυθμό $R>C$ , είναι απίθανο να μεταδοθεί με αυθαίρετα μικρό τετραγωνικό σφάλμα. Η κωδικοποίηση καναλιού ασχολείται με το να βρει σχετικά βέλτιστους κώδικες που μπορούν να χρησιμοποιηθούν για να μεταδώσουν δεδομένα μέσω ενός θορυβώδους καναλιού με ένα μικρό σφάλμα κωδικοποίησης και ένα ρυθμό κοντά στη χωρητικότητα του καναλιού.

Χωρητικότητα συγκεκριμένων μοντέλων καναλιού

Ένα συνεχούς-χρόνου αναλογικό κανάλι επικοινωνίας που υπόκεινται σε θόρυβο κανονικής κατανομής.
Ένα δυαδικό συμμετρικό κανάλι (ΔΣΚ) με πιθανότητα σφάλματος συμβόλου $p$ είναι ένα κανάλι με δυαδική είσοδο και δυαδική έξοδο το οποίο αντιστρέφει την τιμή της εισόδου με πιθανότητα $p$ . Το ΔΣΚ έχει χωρητικότητα $1-H_{\mathrm {b} }(p)$ bits ανά χρήση του καναλιού, όπου $H_{\mathrm {b} }$ είναι η δυαδική συνάρτηση εντροπίας στον λογάριθμο με βάση 2:

Ένα δυαδικό κανάλι διαγραφής (ΔΚΔ) με πιθανότητα διαγραφής $p$ είναι ένα κανάλι με δυαδική είσοδο και τριαδικό κανάλι εξόδου. Οι πιθανές έξοδοι του καναλιού είναι 0,1 και ένα τρίτο σύμβολο $e$ που ονομάζεται διαγραφή (erasure). Το σύμβολο αυτό συμβολίζει την ολοκληρωτική απώλεια της πληροφορίας για ένα bit εισόδου. Η χωρητικότητα ενός ΔΚΔ είναι 1-p bits ανά χρήση του καναλιού.

Περαιτέρω ανάγνωση

Βιβλία

MacKay, David J. C. Information theory, inference, and learning algorithms (PDF). Cambridge: Cambridge University Press. ISBN 978-0521642989.
Cover, Thomas M.· Thomas, Joy A. (2006). Elements of information theory (2η έκδοση). Hoboken, N.J: Wiley-Interscience. ISBN 978-0471241959.

Ξένες διαλέξεις

Polyanskiy, Yury. «Information theory». MIT. Ανακτήθηκε στις 5 Νοεμβρίου 2023.
Weissman, Tsachy. «EE 376A: Information theory lecture notes» (PDF). Stanford University. Ανακτήθηκε στις 5 Νοεμβρίου 2023.
Venkatesan Guruswami· Mahdi Cheraghchi. «15-859: Information Theory and its applications in theory of computation». CMU. Ανακτήθηκε στις 5 Νοεμβρίου 2023.

Ελληνικές διαλέξεις

Λιάβας, Αθανάσιος Π. «Στοιχεία Θεωρίας Πληροφορίας» (PDF). Πανεπιστήμιο Κρήτης. Ανακτήθηκε στις 5 Νοεμβρίου 2023.
Ζορκαδης, Βασίλειος. «Θεωρία πληροφορίας και κωδικοποίησης» (PDF). Ελληνικό ανοιχτό πανεπιστήμιο. Ανακτήθηκε στις 5 Νοεμβρίου 2023.

Παραπομπές

↑ F. Rieke, D. Warland, R Ruyter van Steveninck, W Bialek, Spikes: Exploring the Neural Code. The MIT press (1997).
↑ cf. Huelsenbeck, J. P., F. Ronquist, R. Nielsen and J. P. Bollback (2001) Bayesian inference of phylogeny and its impact on evolutionary biology, Science 294:2310-2314
↑ Rando Allikmets, Wyeth W. Wasserman, Amy Hutchinson, Philip Smallwood, Jeremy Nathans, Peter K. Rogan, Thomas D. Schneider Αρχειοθετήθηκε 2012-02-04 στο Wayback Machine., Michael Dean (1998) Organization of the ABCR gene: analysis of promoter and splice junction sequences, Gene 215:1, 111-122
↑ David R. Anderson (1 Νοεμβρίου 2003). «Some background on why people in the empirical sciences may want to better understand the information-theoretic methods» (PDF). Αρχειοθετήθηκε από το πρωτότυπο (pdf) στις 23 Ιουλίου 2011. Ανακτήθηκε στις 23 Ιουνίου 2010.

[1] F. Rieke, D. Warland, R Ruyter van Steveninck, W Bialek, Spikes: Exploring the Neural Code. The MIT press (1997).

[2] . Huelsenbeck, J. P., F. Ronquist, R. Nielsen and J. P. Bollback (2001) Bayesian inference of phylogeny and its impact on evolutionary biology, Science 294:2310-2314

[3] Rando Allikmets, Wyeth W. Wasserman, Amy Hutchinson, Philip Smallwood, Jeremy Nathans, Peter K. Rogan, Thomas D. Schneider Αρχειοθετήθηκε 2012-02-04 στο Wayback Machine., Michael Dean (1998) Organization of the ABCR gene: analysis of promoter and splice junction sequences, Gene 215:1, 111-122

[4] David R. Anderson (1 Νοεμβρίου 2003). «Some background on why people in the empirical sciences may want to better understand the information-theoretic methods» (PDF). Αρχειοθετήθηκε από το πρωτότυπο (pdf) στις 23 Ιουλίου 2011. Ανακτήθηκε στις 23 Ιουνίου 2010.

[1]

[2]

[3]

[4]