.
H Θεωρία πληροφορίας είναι τμήμα των εφαρμοσμένων μαθηματικών και ασχολείται με την ποσοτικοποίηση της πληροφορίας. Η θεωρία της πληροφορίας αναπτύχθηκε από τον Κλοντ Σάνον για να βρει τα θεμελιώδη όρια της επεξεργασίας σήματος σε εφαρμογές όπως η συμπίεση δεδομένων και η αξιόπιστη αποθήκευση και μεταφορά δεδομένων. Από τη θεμελίωση της έχει διευρυνθεί ώστε να βρει εφαρμογές σε πολλούς άλλους τομείς, όπως στην επαγωγική στατιστική, στην επεξεργασία φυσικής γλώσσας, στην κρυπτογραφία, στα δίκτυα εκτός των δικτύων επικοινωνίας - όπως και στη νευροβιολογία,[1] στην εξέλιξη[2] και τη λειτουργία[3] μοριακών κωδικών στην οικολογία, στη θερμική φυσική, στους κβαντικούς υπολογιστές, στην ανίχνευση λογοκλοπής και σε άλλες μορφές ανάλυσης δεδομένων.[4]
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 θεωρία της πληροφορίας είναι μία ευρεία και «βαθιά» θεωρία, με εξίσου ευρείες και «βαθιές» εφαρμογές, όπου ανάμεσα τους βρίσκεται και ο καίριος τομέας της Θεωρίας κωδικοποίησης.
Η Θεωρία της κωδικοποίησης ασχολείται βρίσκοντας ξεκάθαρες μεθόδους-κωδικες για να αυξήσει την απόδοση και να μειώσει τα σφάλματα δικτύου της επικοινωνίας των δεδομένων από ένα θορυβώδες κανάλι για να πλησιάσει το όριο που ο Σάνον απέδειξε ότι είναι το μέγιστο δυνατό για ένα τέτοιο κανάλι. Αυτοί οι κώδικες μπορούν να υποδιαιρεθούν σε συμπίεση δεδομένων και σε ανίχνευση και διόρθωση σφαλμάτων. Στην τελευταία αυτή περίπτωση πήρε πολλά χρόνια για να βρεθούν οι μέθοδοι,που ο Σάνον δουλεψε,αποδεικνύοντας ότι είναι εφικτές. Μιας τρίτης τάξεως κώδικες της θεωρίας της πληροφορίας είναι οι κρυπτογραφικοί αλγόριθμοι (κώδικες και αποκρυπτογραφήματα). Οι έννοιες, οι μέθοδοι και τα αποτελέσματα από τη Θεωρία Κωδικοποίησης και τη Θεωρία της Πληροφορίας χρησιμοποιούνται ευρέως στην Κρυπτογραφία και στην Κρυπτανάλυση.
Η Θεωρία της Πληροφορίας χρησιμοποιείται επίσης στην Ανάκτηση Πληροφοριών, συλλογή πληροφοριών, στα τυχερά παιχνίδια, στην στατιστική, ακόμα και στην σύνθεση μουσικής.
Ιστορική Αναδρομή
Το ορόσημο γεγονός που καθιέρωσε τον επιστημονικό κλάδο της θεωρίας της πληροφορίας και τον έφερε σε άμεση παγκόσμια προσοχή ήτανε η δημοσίευση του Κλοντ Σάνον,με τίτλο “ 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 χρησιμοποίησε παρόμοιες ιδέες σαν κομμάτι μιας στατιστικής ανάλυσης για το “σπάσιμο” των αλγορίθμων κρυπτογράφησης των Γερμανών κατά τον Δεύτερο Παγκόσμιο πόλεμο. Πολλά από τα μαθηματικά ″πίσω″ από την θεωρία της πληροφορίας αναπτύχθηκαν για το πεδίο της θερμοδυναμικής από τον Λούντβιχ Μπόλτσμαν και Josiah Willard Gibbs. Οι σχέσεις μεταξύ πληροφορίας-θεωρητικής εντροπίας και της θερμοδυναμικής εντροπίας, συμπεριλαμβανομένων των σημαντικών συνεισφορών του Rolf Landauer τη δεκαετία του 1960, διερευνώνται στο άρθρο «Entropy in thermodynamics and information theory»
Στην επαναστατική και πρωτοποριακή εργασία, η οποία είχε ολοκληρωθεί στα Bell Labs στα τέλη του 1944, ο Σάνον για πρώτη φορά εισήγαγε το ποσοτικό και ποιοτικό μοντέλο επικοινωνίας ως μια στατιστική διαδικασία που στηρίζεται η θεωρία της πληροφορίας, εισάγοντας τον ισχυρισμό ότι: “το θεμελιώδες πρόβλημα της επικοινωνίας είναι αυτό της αναπαραγωγής σε ένα σημείο, είτε ακριβώς είτε κατά προσέγγιση, ενός μηνύματος που επιλέχτηκε σε ένα άλλο σημείο” .
Με αυτό κατέληξαν στις επινοήσεις,
της Εντροπίας πληροφοριών και της Redundancy (ο αριθμός των δυαδικών ψηφίων που χρησιμοποιούνται για την μετάδοση ενός μηνύματος μείον τον αριθμό των δεκαδικών ψηφίων της πραγματικής πληροφορίας σε ένα μήνυμα) μιας πηγής, και τη σημασία της μέσω του θεωρήματος του πηγαίου κώδικα
στην κοινή πληροφορία και τη χωρητικότητα καναλιού ενός θορυβώδους καναλιού, συμπεριλαμβανομένης και της υπόσχεσης για τέλεια, χωρίς απώλειες επικοινωνία που δίνεται από το θεώρημα του θορυβώδους καναλιού.
στο πρακτικό αποτέλεσμα του νόμου Shannon-Hartley για τη χωρητικότητα του καναλιού ενός Gaussian καναλιού, καθώς επίσης
στο bit- ένας νέος τρόπος οπτικής για την πιο θεμελιώδη μονάδα πληροφοριών.
Ποσότητες πληροφορίας
Η Θεωρία της πληροφορίας βασίζεται στη θεωρία πιθανοτήτων και στη στατιστική. Οι σημαντικότερες ποσότητες της πληροφορίας είναι η εντροπία, η πληροφορία σε μία τυχαία μεταβλητή, και η κοινή πληροφορία: η ποσότητα από κοινού της πληροφορίας ανάμεσα σε δύο τυχαίες μεταβλητές. Η πρότερη ποσότητα υποδεικνύει το πόσο εύκολα συμπιέζονται τα δεδομένα μηνύματος ενώ η τελευταία χρησιμοποιείται για να διαπιστωθεί το ποσοστό της επικοινωνίας δια μέσου ενός καναλιού μετάδοσης.
Η επιλογή της βάσης του λογαρίθμου στη φόρμουλα που επακολουθεί καθορίζει το σύνολο της πληροφορίας της εντροπίας που χρησιμοποιήθηκε. Η συνηθέστερη μονάδα της πληροφορίας είναι το Bit, βασιζόμενο στον δυαδικό λογάριθμο(log2 n) . Άλλες μονάδες συμπεριλαμβανομένου του nat, το οποίο βασίζεται στον φυσικό λογάριθμο (λογάριθμος με βαση το e), και στο hartley ή ban το οποίο βασίζεται στον κοινό λογάριθμο (λογάριθμος με βάση το 10).
Σ´ αυτά που ακολουθούν, η έκφραση της μορφής p \log p \, θεωρείται συμβατικά να είναι ίση με 0 όταν p=0..Αυτό δικαιολογείται επειδή \lim_{p \rightarrow 0+} p \log p = 0 για οποιαδήποτε λογαριθμική βάση.
Εντροπία
Entropy of a Bernoulli trial as a function of success probability, often called the binary entropy function, H_\mathrm{b}(p). The entropy is maximized at 1 bit per trial when the two possible outcomes are equally probable, as in an unbiased coin toss.
Η εντροπία, H, μιας διακριτής τυχαίας μεταβλητής X είναι ένα μέτρο της ποσότητας της αβεβαιότητας που σχετίζεται με τη τιμή του X. Ας υποθέσουμε ότι μεταδίδονται 1000 bits (τα δυαδικά ψηφία 0 και 1). Εάν αυτά (bits) είναι γνωστά πριν από την μετάδοση (δηλαδή μια συγκεκριμένη τιμή με απόλυτη πιθανότητα), η λογική προστάζει ότι καμία πληροφορία δεν έχει μεταδοθεί. Αν, ωστόσο, κάθε 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 στην κωδικοποίηση του Χ , από ότι αν το Υ είναι άγνωστο.
Η κοινή πληροφορία είναι συμμετρική:
\(I(X;Y) = I(Y;X) = H(X) + H(Y) - H(X,Y).\,\)
Η κοινή πληροφορία μπορεί να εκφραστεί ως η «μέση απόκλιση» του Kullback–Leibler ανάμεσα στην μεταγενέστερη κατανομή πιθανότητας του Χ δεδομένης της τιμής του Υ και την προγενέστερη κατανομή στο Χ:
\(I(X;Y) = \mathbb E_{p(y)} [D_{\mathrm{KL}}( p(X|Y=y) \| p(X) )].\)
Με άλλα λόγια, αυτή είναι μια μέτρηση του πόσο πολύ , κατά μέσο όρο, η κατανομή της πιθανότητας στο Χ θα αλλάξει αν η τιμή του Υ είναι δεδομένη. Αυτό συνήθως επαναπροσδιορίζεται ως η απόκλιση από το γινόμενο της οριακής κατανομής επί την πραγματική κοινή κατανομή:
\(I(X; Y) = D_{\mathrm{KL}}(p(X,Y) \| p(X)p(Y)).\)
Η κοινή πληροφορία είναι άρρηκτα συνδεδεμένη με το log-likelihood ratio test (ένα στατιστικό τεστ που χρησιμοποιείται για να συγκρίνει τη φόρμα δυο μοντέλων) στα πλαίσια των πινάκων ενδεχομένων και της πολυωνυμικής κατανομής και στο στατιστικό \(x^2\) -test του 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 των πρότερων απο την αληθεια
Μια άλλη ερμηνεία της απόκλισης του Kullback-Leibler είναι αυτή: ας υποθέσουμε ότι ένας αριθμός X πρόκειται να επιλεχθεί απο ένα διακριτό σύνολο με την κατανομή της πιθανότητας p(X). Αν η Αλίκη ξέρει την πραγματική κατανομή p(X) ενώ ο Βασίλης πιστεύει οτι η κατανομή είναι q(X), τότε ο Βασίλης μπορει να είναι πιο έκπληκτος απο την Αλίκη, κατά μέσο όρο, βλέποντας την τιμή του X. Η απόκλιση του Kullback-Leibler είναι η αντικειμενική αναμενόμενη τιμή απο του Βασίλη την κατάπληξη μείον την κατάπληξη της Αλίκης, μετρημένη σε bit αν ο λογάριθμος είναι στην βάση 2. Έτσι, ο βαθμός στον οποίο πιστεύει ο Βασίλης είναι "λάθος", αυτό μπορεί να ποσοτικοποιηθεί με όρους του κατα πόσο είναι αναμενόμενο να τον κάνει "άσκοπα έκπληκτο".
Άλλες ποσότητες
Άλλες σημαντικές ποσότητες της θεωρίας πληροφοριών συμπεριλαμβάνουν, την εντροπία Renyi (μια γενίκευση της εντροπίας), την διαφορική εντροπία (μια γενίκευση απο ποσότητες πληροφορίας σε συνεχόμενες κατανομές) και την κοινή υπο συνθήκη πληροφορία.
Θεωρία Κωδίκοποίησης
A picture showing scratches on the readable surface of a CD-R. Music and data CDs are coded using error correcting codes and thus can still be read even if they have minor scratches using error detection and correction.
Η θεωρία κωδικοποίησης είναι από τις σημαντικότερες και πιο άμεσες εφαρμογές της θεωρίας πληροφορίας. Μπορεί να υποδιαιρεθεί σε θεωρία πηγαίου κώδικα και σε θεωρία κωδικοποίησης καναλιού. Χρησιμοποιώντας μία στατιστική περιγραφή για δεδομένα, η θεωρία της πληροφορίας προσδιορίζει τον αριθμό των bits που χρειάζεται για να περιγραφούν τα δεδομένα, ο οποίος είναι η εντροπία πληροφορίας της πηγής.
Συμπίεση δεδομένων:Υπάρχουν δύο αναπτύγματα για το πρόβλημα της συμπίεσης:
lossless data compression: τα δεδομένα πρέπει να αναδομηθούν ακριβώς
Lossy compression: κατανεμημένα bits χρειάζονται για να αναδομηθούν τα δεδομένα, μέσα σε ένα καθορισμένο επίπεδο πιστότητας μετρημένο από μία παραμορφωμένη συνάρτηση. Αυτό το υποσύνολο της θεωρίας της πληροφορίας λέγεται θεωρία παραμόρφωσης-τιμής.
Κώδικες διόρθωσης σφαλμάτων: Ενώ η συμπίεση δεδομένων αφαιρεί όσο περιττολογία είναι δυνατόν, ένας κώδικας διόρθωσης σφαλμάτων προσθέτει ακριβώς το σωστό είδος του πλεονασμού που χρειάζεται για να μεταδοθούν τα δεδομένα αποτελεσματικά και έμπιστα στο θορυβώδες κανάλι.
Αυτή η "διαίρεση" της θεωρίας κωδικοποίησης σε συμπίεση και μετάδοση δικαιολογείται από τα θεωρήματα πληροφορίας μετάδοσης, ή από τα θεωρήματα διαχωρισμού πηγής-καναλιού που δικαιολογούν την χρήση των 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 – είναι το πρωταρχικό κίνητρο της θεωρίας πληροφοριών. Όπως ο οποιοσδήποτε που έχει χρησιμοποιήσει ένα τηλέφωνο (σταθερό ή κινητό) ξέρει, ωστόσο, ότι τέτοια κανάλια συχνά αποτυγχάνουν να παράγουν ακριβή ανακατασκευή ενός σήματος: θόρυβο, περιόδους σιγής και άλλες μορφές φθοράς σήματος συχνά μειώνουν την ποιότητα. Πόση πληροφορία κάποιος μπορεί να ελπίζει να μεταδώσει μέσω ενός θορυβώδους (ή αλλιώς ημιτελούς) καναλιού; Θεωρούμε τη διαδικασία επικοινωνίας μέσω ενός διακριτού καναλιού. Ένα απλό μοντέλο της διαδικασίας δίνεται παρακάτω:
Comm Channel
Εδώ το Χ παριστάνει το σύνολο των μηνυμάτων που μεταδίδονται και Υ το σύνολο των εισερχόμενων μηνυμάτων στη μονάδα του χρόνου μέσω του καναλιού μας. Έστω p(y|x) η συνάρτηση της δεσμευμένης πιθανότητας κατανομής του Υ δεδομένου του Χ. Θα θεωρήσουμε την p(y|x) εγγενή σταθερή ιδιότητα του επικοινωνιακού μας καναλιού (που αντιπροσωπεύει τη φύση του θορύβου του καναλιού μας). Τότε η κοινή κατανομή του Χ και Υ είναι εντελώς καθορισμένη από το κανάλι μας και από την επιλογή της f(x) , η οριακή κατανομή των μηνυμάτων που διαλέγουμε να στείλουμε μέσω του καναλιού. Κάτω από αυτούς τους περιορισμούς θα θέλαμε να μεγιστοποιήσουμε το ρυθμό της πληροφορίας ή του σήματος , που μπορούμε να μεταδίδουμε μέσω του καναλιού. Η κατάλληλη μέτρηση για αυτό είναι η κοινή πληροφορία και αυτή η μέγιστη κοινή πληροφορία καλείται Χωρητικότητα καναλιού και δίνεται από τον τύπο:
\(C = \max_{f} I(X;Y).\!\)
Αυτή η χωρητικότητα έχει την ακόλουθη ιδιότητα που σχετίζεται με τη μετάδοση μιας πληροφορίας σε ρυθμό R (όπου R είναι συνήθως bits ανά σύμβολο). Για οποιοδήποτε ρυθμό πληροφορίας R<C και σφάλμα κώδικα ε>0, για ένα αρκετά μεγάλο Ν, υπάρχει ένας κώδικας μήκους Ν και ρυθμού ≥ R και ένας αλγόριθμος αποκωδικοποίησης τέτοιος ώστε η μέγιστη πιθανότητα ενός τετραγωνικού σφάλματος να είναι ≤ ε. Είναι πάντα πιθανό να μεταδοθεί με αυθαίρετα μικρό τετραγωνικό σφάλμα. Επιπροσθέτως για οποιοδήποτε ρυθμό R>C , είναι απίθανο να μεταδοθεί με αυθαίρετα μικρό τετραγωνικό σφάλμα. Η κωδικοποίηση καναλιού ασχολείται με το να βρει σχετικά βέλτιστους κώδικες που μπορούν να χρησιμοποιηθούν για να μεταδώσουν δεδομένα μέσω ενός θορυβώδους καναλιού με ένα μικρό σφάλμα κωδικοποίησης και ένα ρυθμό κοντά στη χωρητικότητα του καναλιού.
Χωρητικότητα συγκεκριμένων μοντέλων καναλιού
Ένα συνεχόμενο ανάλογο επικοινωνίας κανάλι υποκείμενο στον θόρυβο Gaussian Ένα δυαδικό συμμετρικό κανάλι(ΔΣΚ) διασταυρωμένο με την πιθανότητα p είναι μία δυαδική είσοδος, το δυαδικό κανάλι εξόδου το οποίο αντιστρέφει την είσοδο με πιθανότητα p. Το ΔΣΚ έχει χωρητικότητα 1 - H_\mathrm{b}(p) bits ανά κανάλι σε χρήση όπου H_\mathrm{b} είναι η δυαδική συνάρτηση εντροπίας στον λογάριθμο με βάση 2:
Binary symmetric channel
Ένα δυαδικό κανάλι διαγραφής(ΔΚΔ) με διαγραφόμενη πιθανότητα p είναι μια δυαδική είσοδος,τριαδικό κανάλι εξόδου. Οι πιθανές έξοδοι του καναλιού είναι 0,1 και ένα τρίτο σύμβολο 'e' που ονομάζεται διαγραφή (erasure). Το σύμβολο αυτό συμβολίζει την ολοκληρωτική απώλεια της πληροφορίας για ένα bit εισόδου. Η χωρητικότητα ενός ΔΚΔ ειναι 1-p bits ανά χρήση καναλιού.
Binary erasure channel
Παραπομπές
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, Michael Dean (1998) Organization of the ABCR gene: analysis of promoter and splice junction sequences, Gene 215:1, 111-122
David R. Anderson (November 1, 2003). «Some background on why people in the empirical sciences may want to better understand the information-theoretic methods» (pdf). Ανακτήθηκε στις 2010-06-23.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
