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

Η θεωρία πληροφορίας είναι τμήμα των εφαρμοσμένων μαθηματικών και ασχολείται με την ποσοτικοποίηση της πληροφορίας. Η θεωρία της πληροφορίας αναπτύχθηκε από τον Κλοντ Σάνον για να βρει τα θεμελιώδη όρια της επεξεργασίας σήματος σε εφαρμογές όπως η συμπίεση δεδομένων και η αξιόπιστη αποθήκευση και μεταφορά δεδομένων. Από τη θεμελίωση της έχει διευρυνθεί ώστε να βρει εφαρμογές σε πολλούς άλλους τομείς, όπως στην επαγωγική στατιστική, στην επεξεργασία φυσικής γλώσσας, στην κρυπτογραφία, στα δίκτυα εκτός των δικτύων επικοινωνίας - όπως και στη νευροβιολογία, στην εξέλιξη και τη λειτουργία μοριακών κωδικών στην οικολογία, στη θερμική φυσική, στους κβαντικούς υπολογιστές, στην ανίχνευση λογοκλοπής και σε άλλες μορφές ανάλυσης δεδομένων.
H βασική μέτρηση της πληροφορίας είναι η εντροπία πληροφοριών, η οποία συνήθως εκφράζεται με το μέσο αριθμό των bits που χρειάζονται για να αποθηκευθεί ή να μεταβιβαστεί ένα σύμβολο σε ένα μήνυμα. Η εντροπία πληροφοριών ποσοτικοποιεί την αβεβαιότητα που εμπλέκεται στην πρόβλεψη της τιμής μίας τυχαίας μεταβλητής. Για παράδειγμα, ο προσδιορισμός του αποτελέσματος από μία δίκαιη «ρίψη νομίσματος»(–Κορώνα ή γράμματα -δύο ισοδύναμα πιθανά αποτελέσματα ) παρέχει λιγότερες πληροφορίες (μικρή εντροπία) από τον προσδιορισμό του αποτελέσματος από μία  ρίψη ενός ζαριού(6 ισοδύναμα πιθανά αποτελέσματα).
Οι εφαρμογές από τα θεμελιώδη θέματα της θεωρίας της πληροφορίας περιλαμβάνουν την μη απωλεστική συμπίεση δεδομένων (ZIP files), απωλεστική συμπίεση δεδομένων (e.g. MP3s and JPEG), και την χωρητικότητα καναλιού (Ψηφιακή Συνδρομητική Γραμμή DSL). Ο τομέας είναι στην «διασταύρωση» των μαθηματικών,  της στατιστικής, της επιστήμης των υπολογιστών, της φυσικής, της νευρολογίας και της ηλεκτρικής εφαρμοσμένης μηχανικής. Οι επιπτώσεις  του είναι κρίσιμες για την επιτυχία των αποστολών του Voyager στο διάστημα, την ανακάλυψη του δίσκου lazer (cd), την υλοποίηση των κινητών τηλεφώνων, την εξέλιξη του διαδικτύου (Internet), την επιστήμη της γλωσσολογίας και της ανθρώπινης αντίληψης, την κατανόηση της Μαύρης Τρύπας και πολλών ακόμη άλλων πεδίων. Σημαντικά «υπο-πεδία» της θεωρίας πληροφορίας είναι ο πηγαίος κώδικας, η χωρητικότητα καναλιού, η αλγοριθμική θεωρία πολυπλοκότητας, η αλγοριθμική θεωρία της πληροφορίας, τα  στοιχεία θεωρίας της ασφάλειας, καθώς και τα μέτρα ενημέρωσης.

Επισκόπηση

Οι κύριες έννοιες της θεωρίας πληροφορίας μπορούν να γίνουν αντιληπτές λαμβάνοντας υπόψη το πιο διαδεδομένο μέσο της ανθρώπινης επικοινωνίας: τη γλώσσα. Δύο σημαντικές πλευρές μιας περιεκτικής γλώσσας είναι : Πρώτον, οι πιο κοινές αγγλικές λέξεις (όπως "a", "the", "I")  ) πρέπει να είναι συντομότερες από τις όχι τόσο κοινές λέξεις (όπως "roundabout", "generation", "mediocre"), έτσι ώστε οι προτάσεις να μην είναι πολύ μεγάλες. Μια τέτοια εξισορρόπηση στο μήκος των λέξεων είναι ανάλογη με την συμπίεση δεδομένων και είναι απαραίτητη πλευρά του πηγαίου κώδικα. Δεύτερον, αν ένα μέρος της πρότασης δεν ακούστηκε ή ακούστηκε λάθος λόγω ενός θορύβου -για παράδειγμα, ένα διερχόμενο αυτοκίνητο ο ακροατής πρέπει να είναι ικανός να περισυλλέξει το νόημα από το υποκρυπτόμενο μήνυμα. Μία τέτοια σθεναρότητα είναι τόσο απαραίτητη για ένα ηλεκτρονικό σύστημα επικοινωνίας όσο και για την γλώσσα: Πιο σωστά, το «χτίσιμο» μιας τέτοιας σθεναρότητας στις επικοινωνίες γίνεται με την χωρητικότητα καναλιού. Ο πηγαίος κώδικας και η χωρητικότητα καναλιού είναι οι κύριες ασχολίες της θεωρίας της πληροφορίας.
Σημειώστε ότι αυτές οι ασχολίες δεν έχουν καμία σχέση με την σημαντικότητα των μηνυμάτων. Για παράδειγμα, μια κοινή έκφραση όπως το “Ευχαριστώ πολύ ”, χρειάζεται περίπου τον ίδιο χρόνο με το να πεις ή να γράψεις την επείγουσα έκκληση “Κάλεσε ασθενοφόρο”, καθώς το τελευταίο μπορεί να είναι πιο σημαντικό και με περισσότερο νόημα. Παρόλα αυτά η θεωρία πληροφορίας, δεν λαμβάνει υπ’όψη τη σημαντικότητα του μηνύματος ή τη σημασία του, επειδή αυτά είναι ζητήματα της ποιότητας των δεδομένων και όχι από την ποσότητα και την αναγνωσιμότητα των δεδομένων, η τελευταία εκ των οποίων καθορίζεται αποκλειστικά από τις πιθανότητες.
Η θεωρία πληροφορίας γενικά θεωρείται ότι έχει θεμελιωθεί το 1948 από τον Κλοντ Σάνον κατά την δημιουργική του δουλειά «A Mathematical Theory of Communication». Το κλασσικό παράδειγμα της θεωρίας της πληροφορίας είναι το μηχανικό πρόβλημα της μετάδοσης της πληροφορίας μέσα από έναν θορυβώδες κανάλι. Τα πιο θεμελιώδη αποτελέσματα από αυτήν την θεωρία είναι το θεώρημα του Σάνον για τον πηγαίο κώδικα, που καθιερώνει ότι, κατά μέσο όρο, ο αριθμός των δυαδικών ψηφίων (bits) που χρειάζονται για να αναπαρασταθεί το αποτέλεσμα ενός αβέβαιου γεγονότος δίνεται από την εντροπία πληροφοριών του, και από το θεώρημα του Σάνον για το θορυβώδες κανάλι μεταφοράς, το οποίο δηλώνει ότι η αξιόπιστη επικοινωνία είναι δυνατή σε θορυβώδη κανάλια με την προϋπόθεση ότι ο συντελεστής της επικοινωνίας είναι κάτω από ένα ορισμένο όριο, το οποίο ονομάζεται χωρητικότητα καναλιού. Στην πράξη μπορούμε να προσεγγίσουμε την χωρητικότητα καναλιού χρησιμοποιώντας κατάλληλα συστήματα κωδικοποίησης και αποκωδικοποίησης.
Η Θεωρία της Πληροφορίας συσχετίζεται με μια συλλογή από καθαρές και εφαρμοσμένες επιστήμες  που έχουν ερευνήσει και έχουν  καταφύγει στην άσκηση της μηχανολογίας κάτω από μία πληθώρα κατηγοριών ανά τον κόσμο περισσότερο από μισό αιώνα η και παραπάνω: Προσαρμοζόμενα συστήματα,συστήματα τεχνητής νοημοσύνης, τεχνητή νοημοσύνη, πολύπλοκο σύστημα, επιστήμη συστημάτων, πληροφορική, μηχανική μάθηση, μαζί με συστήματα επιστημών. H θεωρία της πληροφορίας είναι μία ευρεία και «βαθιά» θεωρία, με εξίσου ευρείες και «βαθιές»  εφαρμογές, όπου ανάμεσα τους βρίσκεται και ο καίριος τομέας της Θεωρίας κωδικοποίησης.
Η Θεωρία της κωδικοποίησης ασχολείται βρίσκοντας ξεκάθαρες μεθόδους-κωδικες για να αυξήσει την απόδοση και να μειώσει τα σφάλματα δικτύου της επικοινωνίας των δεδομένων από ένα θορυβώδες κανάλι για να πλησιάσει το όριο που ο Σάνον απέδειξε ότι είναι το μέγιστο δυνατό για ένα τέτοιο κανάλι. Αυτοί  οι κώδικες μπορούν να υποδιαιρεθούν σε συμπίεση δεδομένων και σε ανίχνευση και διόρθωση σφαλμάτων. Στην τελευταία αυτή περίπτωση πήρε πολλά χρόνια για να βρεθούν οι μέθοδοι,που ο Σάνον δουλεψε,αποδεικνύοντας ότι είναι εφικτές. Μιας τρίτης τάξεως κώδικες της θεωρίας της πληροφορίας είναι οι κρυπτογραφικοί αλγόριθμοι (κώδικες και αποκρυπτογραφήματα). Οι έννοιες, οι μέθοδοι και τα αποτελέσματα από τη Θεωρία Κωδικοποίησης και τη Θεωρία της Πληροφορίας χρησιμοποιούνται ευρέως στην Κρυπτογραφία και στην Κρυπτανάλυση.
Η Θεωρία της Πληροφορίας χρησιμοποιείται επίσης στην Ανάκτηση Πληροφοριών, συλλογή πληροφοριών, στα τυχερά παιχνίδια, στην στατιστική, ακόμα και στην σύνθεση μουσικής.

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

Η Θεωρία της πληροφορίας βασίζεται στη θεωρία πιθανοτήτων και στη στατιστική. Οι σημαντικότερες ποσότητες της πληροφορίας είναι η εντροπία, η πληροφορία σε μία τυχαία μεταβλητή, και η κοινή πληροφορία: η ποσότητα από κοινού της πληροφορίας ανάμεσα σε δύο τυχαίες μεταβλητές. Η πρότερη ποσότητα υποδεικνύει το πόσο εύκολα συμπιέζονται τα δεδομένα μηνύματος ενώ η τελευταία χρησιμοποιείται για να διαπιστωθεί το ποσοστό της επικοινωνίας δια μέσου ενός καναλιού μετάδοσης.
Η επιλογή της βάσης του λογαρίθμου στη φόρμουλα που επακολουθεί καθορίζει το σύνολο της πληροφορίας της εντροπίας που χρησιμοποιήθηκε. Η συνηθέστερη μονάδα της πληροφορίας είναι το Bit, βασιζόμενο στον δυαδικό λογάριθμο(log₂ n) . Άλλες μονάδες συμπεριλαμβανομένου του  nat, το οποίο βασίζεται στον φυσικό λογάριθμο (λογάριθμος με βαση το e), και στο hartley ή ban το οποίο βασίζεται στον κοινό λογάριθμο (λογάριθμος με βάση το 10).
Σ´ αυτά που ακολουθούν, η έκφραση της μορφής   θεωρείται συμβατικά να είναι ίση με 0 όταν .Αυτό δικαιολογείται επειδή  για οποιαδήποτε λογαριθμική βάση.

Εντροπία

Η εντροπία, , μιας διακριτής τυχαίας μεταβλητής  είναι ένα μέτρο της ποσότητας της αβεβαιότητας που σχετίζεται με τη τιμή του .
Ας υποθέσουμε ότι μεταδίδονται 1000 bits (τα δυαδικά ψηφία 0 και 1). Εάν αυτά (bits) είναι γνωστά πριν από την μετάδοση (δηλαδή μια συγκεκριμένη τιμή με απόλυτη πιθανότητα), η λογική προστάζει ότι καμία πληροφορία δεν έχει μεταδοθεί. Αν, ωστόσο, κάθε bit είναι ισοπίθανα και ανεξάρτητα πιθανό να είναι 0 ή 1,  1000 bits (υπό την έννοια της θεωρίας της πληροφορίας) έχουν μεταδοθεί. Μεταξύ αυτών των δύο άκρων ,η πληροφορία μπορεί να ποσοτικοποιηθεί όπως ακολουθεί. Αν  είναι το σύνολο από όλα τα μηνύματα  που  μπορεί να είναι, και  είναι η πιθανότητα κάποιου , τότε η εντροπία  του  καθορίζεται :
.
( Εδώ,  είναι η «αυτό-πληροφορία» , που είναι η συνεισφορά της εντροπίας σε ένα μήνυμα, και   είναι η Αναμενόμενη τιμή ) Μια σημαντική ιδιότητα της εντροπίας είναι ότι μεγιστοποιείται όταν όλα τα μηνύματα στο χώρο είναι ισοπίθανα  , - δηλαδή πιο απρόβλεπτα -  στην οποία περίπτωση  .
Η ειδική περίπτωση της εντροπίας πληροφοριών για μια τυχαία μεταβλητή με δύο εξαγόμενα είναι η δυαδική συνάρτηση της εντροπίας , που συνήθως αναγάγεται στην λογαριθμική βάση 2 :

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

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

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

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

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

Η κοινή πληροφορία μετρά το ποσό της πληροφορίας που μπορεί να αποκτηθεί για μια τυχαία μεταβλητή παρατηρώντας μια άλλη. Είναι σημαντικό στην επικοινωνία όπου μπορεί να χρησιμοποιηθεί για να μεγιστοποιήσει την ποσότητα της πληροφορίας που μοιράζεται ανάμεσα σε σταλμένα και εισερχόμενα σήματα. Η κοινή πληροφορία του  σε σχέση με το  δίνεται από:
Όπου  είναι η σημειακή κοινή πληροφορία.
Μια βασική ιδιότητα της κοινής πληροφορίας είναι ότι
Με δεδομένο το Y , μπορούμε να σώσουμε κατά μέσο όρο  bits στην κωδικοποίηση του Χ , από ότι αν το Υ είναι άγνωστο.
Η κοινή πληροφορία είναι συμμετρική:
Η κοινή πληροφορία μπορεί να εκφραστεί ως η «μέση απόκλιση»  του Kullback–Leibler ανάμεσα στην μεταγενέστερη κατανομή πιθανότητας του Χ δεδομένης της τιμής του Υ και την προγενέστερη κατανομή στο Χ:
Με άλλα λόγια, αυτή είναι μια  μέτρηση του πόσο πολύ , κατά μέσο όρο, η κατανομή της πιθανότητας στο Χ θα αλλάξει αν η τιμή του Υ είναι δεδομένη. Αυτό συνήθως επαναπροσδιορίζεται ως η απόκλιση από το γινόμενο της οριακής κατανομής επί την πραγματική κοινή κατανομή:
Η κοινή πληροφορία είναι άρρηκτα συνδεδεμένη με το  log-likelihood ratio test (ένα στατιστικό τεστ που χρησιμοποιείται για να συγκρίνει τη φόρμα δυο μοντέλων) στα πλαίσια των πινάκων ενδεχομένων και της πολυωνυμικής κατανομής και στο στατιστικό  -test του Pearson: η κοινή πληροφορία μπορεί να χρησιμοποιηθεί για τον υπολογισμό της ανεξαρτησίας μεταξύ ενός ζεύγους μεταβλητών και έχει καλά καθορισμένη ασυμπτωτική κατανομή.

Kullback-Leibler απόκλιση

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

Η απόκλιση του Kullback-Leibler των πρότερων απο την αληθεια

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

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

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

Πηγαίος(α) Κώδικας (Θεωρία)

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

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

Κύριο άρθρο: Χωρητικότητα καναλιού
Οι επικοινωνίες μέσω ενός καναλιού – όπως ένα καλώδιο Ethernet – είναι το πρωταρχικό κίνητρο της θεωρίας πληροφοριών. Όπως ο οποιοσδήποτε που έχει χρησιμοποιήσει ένα τηλέφωνο (σταθερό ή κινητό) ξέρει, ωστόσο, ότι τέτοια κανάλια συχνά αποτυγχάνουν να παράγουν ακριβή ανακατασκευή ενός σήματος: θόρυβο, περιόδους σιγής και άλλες μορφές φθοράς σήματος συχνά μειώνουν την ποιότητα. Πόση πληροφορία κάποιος μπορεί να ελπίζει να μεταδώσει μέσω ενός θορυβώδους (ή αλλιώς ημιτελούς) καναλιού; 
Θεωρούμε τη διαδικασία επικοινωνίας μέσω ενός διακριτού καναλιού. Ένα απλό μοντέλο της διαδικασίας δίνεται παρακάτω:
Εδώ το Χ παριστάνει το σύνολο των μηνυμάτων που μεταδίδονται και Υ το σύνολο των εισερχόμενων μηνυμάτων στη μονάδα του χρόνου μέσω του καναλιού μας. Έστω  η συνάρτηση της δεσμευμένης πιθανότητας κατανομής του Υ δεδομένου του Χ. Θα θεωρήσουμε  την  εγγενή σταθερή ιδιότητα του επικοινωνιακού μας καναλιού (που αντιπροσωπεύει τη φύση του θορύβου του καναλιού μας). Τότε η κοινή κατανομή του Χ και Υ είναι εντελώς καθορισμένη από το κανάλι μας και από την επιλογή της  , η οριακή κατανομή των μηνυμάτων που διαλέγουμε να στείλουμε μέσω του καναλιού. Κάτω από αυτούς τους περιορισμούς θα θέλαμε να μεγιστοποιήσουμε το ρυθμό της πληροφορίας ή του σήματος , που μπορούμε να μεταδίδουμε μέσω του καναλιού. Η κατάλληλη μέτρηση για αυτό είναι η κοινή πληροφορία και αυτή η μέγιστη κοινή πληροφορία καλείται Χωρητικότητα καναλιού και δίνεται από τον τύπο:
                 
Αυτή η χωρητικότητα έχει την ακόλουθη ιδιότητα που σχετίζεται με τη μετάδοση μιας πληροφορίας σε ρυθμό R (όπου R είναι συνήθως bits ανά σύμβολο). Για οποιοδήποτε ρυθμό πληροφορίας R<C και σφάλμα κώδικα ε>0, για ένα αρκετά μεγάλο Ν, υπάρχει ένας κώδικας μήκους Ν και ρυθμού ≥ R και ένας αλγόριθμος αποκωδικοποίησης τέτοιος ώστε η μέγιστη πιθανότητα ενός τετραγωνικού σφάλματος να είναι  ≤ ε. Είναι πάντα πιθανό να μεταδοθεί με  αυθαίρετα μικρό τετραγωνικό σφάλμα. Επιπροσθέτως για οποιοδήποτε ρυθμό R>C , είναι απίθανο να μεταδοθεί με  αυθαίρετα μικρό τετραγωνικό σφάλμα.
Η κωδικοποίηση καναλιού ασχολείται με το να βρει  σχετικά βέλτιστους κώδικες που μπορούν να χρησιμοποιηθούν για να μεταδώσουν δεδομένα μέσω ενός θορυβώδους καναλιού με ένα μικρό σφάλμα κωδικοποίησης και ένα ρυθμό κοντά στη χωρητικότητα του καναλιού.