Μερικές φορές μετράμε την πληροφορία σε χαρακτήρες, όπως όταν μετράμε το μήκος ενός e-mail. Άλλες φορές την μετράμε (την πληροφορία, πονηρούλη!) σε ψηφία, όπως ένας τηλεφωνικός αριθμός. Στη θεωρία της πληροφορίας, έχουμε συμφωνήσει να την μετράμε σε bits. Τα bits όπως ξέρεις, παίρνουν τιμές \(0\) ή \(1\) οπότε αν πάρουμε για παράδειγμα \(3\) bits, μπορούμε να δημιουργήσουμε \(8\) διαφορετικές μεταθέσεις (\(000\), \(001\), \(010\), \(011\), \(100\), \(101\), \(110\), \(111\)) και κατά συνέπεια να κωδικοποιήσουμε οποιονδήποτε ακέραιο από το \(1\) μέχρι το \(8\). Άρα όταν μιλάμε για έναν «3-bit αριθμό», εννοούμε έναν ακέραιο στο εύρος από \(1\) μέχρι \(8\).
Ας υποθέσουμε ότι ρίχνεις ένα νόμισμα \(1.000.000\) φορές και σημειώνεις τα διαδοχικά αποτελέσματα. Αν θέλεις να επικοινωνήσεις τα αποτελέσματα σε κάποιον άλλο, πόσα bits θα χρειαστούν; Σε ένα δίκαιο νόμισμα, τα δύο πιθανά αποτελέσματα συμβαίνουν με ίσες πιθανότητες και γι’ αυτό, κάθε ριξιά θέλει \(1\) bit πληροφορίας για να μεταδοθεί. Για να στείλουμε όλα τα αποτελέσματα, θέλουμε \(1.000.000\) bits.
Τι συμβαίνει όμως όταν το νόμισμα είναι μαγικό και μεροληπτεί υπέρ των γραμμάτων ώστε να έρχονται \(3\) στις \(4\) φορές, ενώ η κορόνα μόνο \(1\) στις \(4\); Τότε θα μπορούμε να μεταδώσουμε όλα τα αποτελέσματα μέσα σε \(811.300\) bits κατά προσέγγιση. Όχι, δεν το έβγαλα απ’ το μυαλό μου το νούμερο αλλά θα δούμε παρακάτω τον τύπο από τον οποίο προέκυψε. Το νούμερο αυτό όμως αφήνει να εννοηθεί ότι το αποτέλεσμα κάθε ριξιάς του νομίσματος απαιτεί \(0,8113\) bits για να μεταδοθεί. Πώς όμως θα μεταδώσεις ένα τέτοιο αποτέλεσμα μέσα σε λιγότερο από \(1\) bit όταν η μόνη διαθέσιμη γλώσσα διαθέτει μόνο άσσους και μηδενικά; Προφανώς, δεν μπορείς. Αν όμως θέλεις να μεταδόσεις μια ολόκληρη ακολουθία από αποτελέσματα και γνωρίζεις ότι τα αποτελέσματα αυτά είναι προϊόν μεροληψίας, μπορείς να χρησιμοποιήσεις την γνώση σου για την άνιση κατανομή ώστε να επιλέξεις έναν πιο αποδοτικό κώδικα. Κοινώς, όταν υπάρχει μεροληψία στα αποτελέσματα του νομίσματος, τα αποτελέσματα περιέχουν λιγότερη πληροφορία απ’ ότι ένα αμερόληπτο σύνολο αποτελεσμάτων, γι’ αυτό και απαιτούνται λιγότερα bits για να μεταδοθούν.
Ας δούμε ένα παράδειγμα. Αυτή τη φορά, το μαγικό μας νόμισμα μεροληπτεί πολύ και η πιθανότητα να έρθει κορώνα είναι \(\frac{1}{1000}\) και για γράμματα \(\frac{999}{1000}\). Στο \(1.000.000\) ριξιές, περιμένουμε να δούμε περίπου \(1.000\) κορώνες. Αντί λοιπόν να μεταδώσουμε όλα τα αποτελέσματα, μπορούμε να μεταδώσουμε μόνο το πόσες κορώνες είχαμε και μπορούμε με ασφάλεια να συμπεράνουμε ότι τα υπόλοιπα είναι γράμματα. Κάθε ριξιά έχει μια συγκεκριμένη θέση στην ακολουθία: έναν αριθμό ανάμεσα στο \(1\) και στο \(1.000.000\). Το να κωδικοποιήσουμε τις απόλυτες θέσεις των κορωνών στην ακολουθία, απαιτούνται \(20\) bits για κάθε κορώνα (\(\log _{2}1000000=19.931568569\)). Άρα, αν μεταδώσουμε \(1.000\) \(20\)-bit αριθμούς, ο παραλήπτης θα γνωρίζει τα ακριβή αποτελέσματα των \(1.000.000\) ριξιών, χρησιμοποιώντας μόνο \(20.000\) bits.
Μπορούμε όμως και καλύτερα! Το να κωδικοποιούμε τις απόλυτες θέσεις των κορωνών στην ακολουθία των αποτελεσμάτων, απαιτεί \(20\) bits για κάθε κορώνα και μπορούμε να μεταδώσουμε τις κορώνες με οποιαδήποτε σειρά. Αν συμφωνήσουμε όμως να μεταδώσουμε τις κορώνες σε σειρά, από την αρχή ως το τέλος, τότε αντί να κωδικοποιήσουμε τις απόλυτες θέσεις τους, μπορούμε απλά να κωδικοποιήσουμε την απόστασή τους από την επόμενη κορώνα, κάτι που απαιτεί λιγότερα bits. Για παράδειγμα, αν οι πρώτες \(4\) κορώνες τύχουν στις θέσεις \(502, 1609, 2454\) και \(2607\), τότε η κωδικοποίησή τους ως «απόσταση από την επόμενη κορώνα» θα είναι \(502, 1107, 845, 153\). Κατά μέσο όρο, η απόσταση μεταξύ δύο κορωνών θα είναι γύρω στις \(1.000\) ριξιές. Μόνο σε ακραίες περιπτώσεις η απόσταση θα ξεπερνάει τις \(4.000\) ριξιές. Αριθμοί από το \(1\) μέχρι το \(4.000\) μπορούν να κωδικοποιηθούν μέσα σε \(12\) bits. (Υπάρχει ειδική πατέντα για να χειριστούμε περιπτώσεις που η απόσταση ξεπερνάει τις \(4.000\) θέσεις αλλά δεν θα το αναλύσουμε εδώ). Με αυτή λοιπόν την λίγο πιο φιλοσοφημένη μέθοδο, μια ακολουθία ενός εκατομμυρίου ριξιών που περιέχει περίπου \(1.000\) κορώνες, μπορεί να μεταδοθεί μέσα σε \(12.000\) bits κατά μέσο όρο. Κατά συνέπεια, κάθε ριξιά χρειάζεται μόλις \(0,012\) bits για να μεταδοθεί.
Μπορούμε να εφεύρουμε μια ακόμα πιο έξυπνη κωδικοποίηση; Ποιο είναι το όριο του πόσο αποδοτική μπορεί να είναι μια κωδικοποίηση; Το όριο φαίνεται να είναι τα \(0,0114\) bits για κάθε ριξιά, άρα είμαστε αρκετά κοντά στην βέλτιστη απόδοση. Το ξέρω, πολλά αυθαίρετα νούμερα, αλλά εμπιστεύσου με! Όσο προχωράς, τόσο θα δένουν όλα μεταξύ τους.
Μέχρι τώρα είδαμε παραδείγματα βασισμένα σε fixed-length κωδικοποίηση, όπως ότι \(12\)-bit αριθμοί κωδικοποιούν τιμές από το \(1\) μέχρι το \(4.000\). Συχνά μπορούμε να βελτιώσουμε την απόδοσή μας όταν τα απαιτούμενα bits έχουν την δυνατότητα να μεταβάλλονται. Ας το δούμε όμως σε ένα παράδειγμα:
Υποθέτουμε ότι αντί να ρίχνουμε νόμισμα, ρίχνουμε ένα οχτάπλευρο ζάρι. Ας ονομάσουμε τις πλευρές με γράμματα, από το A ως το H (λατινικοί χαρακτήρες). Για να κωδικοποιήσουμε έναν αριθμό ανάμεσα στο \(1\) και στο \(8\) (ή ανάμεσα στο \(0\) και στο \(7\) για τους προγραμματιστές μας), χρειάζονται \(3\) bits, οπότε χίλιες ριξιές ενός ζαριού χρειάζονται \(3.000\) bits για να μεταδοθούν. Τώρα υπέθεσε ότι το ζάρι γίνεται κι αυτό μαγικό και μεροληπτεί με συγκεκριμένο τρόπο: οι πιθανότητες να ρίξουμε A είναι \(\frac{1}{2}\), οι πιθανότητες για το B είναι \(\frac{1}{4}\), για το C \(\frac{1}{8}\), για το D \(\frac{1}{16}\), για το E \(\frac{1}{32}\), για το F \(\frac{1}{64}\), ενώ για τα G και H οι πιθανότητες είναι \(\frac{1}{128}\) έκαστο. Πρέπει να σιγουρευτούμε ότι το σύνολο των πιθανοτήτων ισούται με 1, αλλιώς η κατανομή των πιθανοτήτων είναι λάθος:
\[\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{16}+\frac{1}{32}+\frac{1}{64}+\frac{1}{128}+\frac{1}{128}=1\]
Ας φτιάξουμε τώρα μια κωδικοποίηση ιδανική για την συγκεκριμένη κατανομή πιθανοτήτων. Αν ρίξουμε το ζάρι και πάρουμε A, θα μεταδώσουμε ένα απλό \(0\). Αν πάρουμε B, θα μεταδώσουμε ένα \(1\) ακολουθούμενο από ένα \(0\), που θα γράφεται \(10\). Αν πάρουμε C, η κωδικοποίηση θα είναι \(11\) ακολουθούμενο από ένα \(0\), δηλαδή \(110\). Ομοίως, θα χρησιμοποιήσουμε το \(1110\) για το D, το \(11110\) για το E, το \(111110\) για το F, το \(1111110\) για το G και το \(1111111\) για το H. Παρατήρησε ότι ο κωδικός για το A είναι τόσο μικρός που χρειάζεται μόλις ένα bit για να μεταδοθεί. Οι κωδικοί για τα G και H απαιτούν \(7\) bits έκαστο, που είναι πολύ περισσότερα από τα \(3\) bits που θα απαιτούνταν για να μεταδοθεί μια ριξιά αν το ζάρι ήταν δίκαιο. Τα G και τα H όπως έρχονται με πολύ μικρή πιθανότητα οπότε η ανάγκη να χρησιμοποιήσουμε τόσα πολλά bits είναι σπάνια. Κατά μέσο όρο, θα χρειαζόμαστε λιγότερα από \(3\) bits. Μπορούμε εύκολα να υπολογίσουμε τον μέσο όρο του πλήθους των bits που απαιτούνται για να μεταδοθεί μια ριξιά. Είναι το σύνολο των απαιτούμενων αριθμών bits για να μεταδοθεί κάθε ένα από τα οχτώ πιθανά αποτελέσματα μιας ριξιάς, διαιρεμένο με την πιθανότητα να έρθει αυτό το αποτέλεσμα:
\[\frac{1}{2}+\frac{2}{4}+\frac{3}{8}+\frac{4}{16}+\frac{5}{32}+\frac{6}{64}+\frac{7}{128}+\frac{7}{128}=1.984\]
Άρα τα αποτελέσματα \(1.000\) ριξιών του ζαριού μπορούν να μεταδοθούν μέσα σε μόλις \(1.984\) bits αντί για \(3.000\). Αυτή η απλή κωδικοποίηση μεταβλητού μήκους είναι η ιδανική κωδικοποίηση για την συγκεκριμένη κατανομή πιθανοτήτων. Γενικά πάντως, η κατανομή των πιθανοτήτων δεν είναι τόσο ξεκάθαρη οπότε η ιδανική κωδικοποίηση είναι αρκετά πιο περίπλοκη.
Στο προηγούμενο παράδειγμα, χρησιμοποιήσαμε ένα ζάρι με οκτώ πλευρές. Αφού το \(8\) είναι δύναμη του \(2\), η πιο αποδοτική κωδικοποίηση για μια ομοιόμορφη κατανομή πιθανοτήτων είναι εύκολο να υπολογιστεί: \(\log_{2}8=3\) bits. Για την κωδικοποίηση μεταβλητού μήκους, γράψαμε επακριβώς το μοτίβο που πρόκειται να μεταδοθεί για κάθε πλευρά του ζαριού κι έτσι ήμασταν σε θέση να μετρήσουμε τον αριθμό των bits που απαιτούνται.
Η θεωρία της πληροφορίας μας παρέχει μια φόρμουλα για να καθορίζουμε τον αριθμό των απαιτούμενων bits σε μια βέλτιστη κωδικοποίηση ακόμα κι αν δεν γνωρίζουμε ποια είναι η κωδικοποίηση. Ας σκεφτούμε αρχικά τις ομοιόμορφες κατανομές πιθανοτήτων όπου ο αριθμός των πιθανών αποτελεσμάτων δεν είναι δύναμη του \(2\). Ας υποθέσουμε ότι έχουμε ένα απλό ζάρι με έξι πλευρές. Ο αριθμός των bits που απαιτείται για να μεταδώσουμε το αποτέλεσμα μιας ριξιάς του εξάπλευρου ζαριού είναι \(\log_{2}6=2,58\). Για μια ακόμη φορά, δεν μπορούμε να μεταδώσουμε μια σκέτη ριξιά σε λιγότερα από 3 bits, αλλά μια αλληλουχία τέτοιων ριξιών μπορεί να μεταδοθεί χρησιμοποιώντας \(2,58\) bits κατά μέσο όρο. Η βέλτιστη κωδικοποίηση σε αυτή την περίπτωση είναι λίγο περίπλοκη αλλά ας δούμε μια προσέγγιση που είναι σχετικά απλή και έχει καλύτερη απόδοση από τα \(3\) bits/ριξιά. Αντί να παίρνουμε κάθε ριξιά ξεχωριστά, μπορούμε να μαζεύουμε τριάδες. Οι πιθανές αλληλουχίες τριών συνεχόμενων ριξιών είναι \(6^{3}=216\). Χρησιμοποιώντας \(8\) bits, μπορούμε να κωδικοποιήσουμε έναν αριθμό ανάμεσα στο \(0\) και στο \(255\), άρα τα αποτελέσματα από \(3\) συνεχόμενες ριξιές μπορούν να χωρέσουν σε \(8\) bits και αφήνουν και λίγο χώρο ελεύθερο. Βλέπουμε πως ήδη γλιτώσαμε \(1\) bit μιας και αν έπρεπε να κωδικοποιήσουμε κάθε ριξιά ξεχωριστά (με κάθε ριξιά να χρειάζεται \(3\) bits), θα χρειαζόμασταν \(9\) bits.
Από πλευράς πιθανοτήτων, κάθε πιθανή τιμή ενός εξάπλευρου ζαριού έρχεται με ίσες πιθανότητες \(P=\frac{1}{6}\). Η θεωρία της πληροφορίας μας λέει ότι ο ελάχιστος αριθμός bits που απαιτούνται για να κωδικοποιήσουμε μια ριξιά είναι \(-\log _{2}P=2,58\). Αν κοιτάξεις πίσω στο παράδειγμα με το οχτάπλευρο ζάρι, θα δεις ότι στην ιδανική κωδικοποίηση που περιγράψαμε, τα bits που απαιτούνταν για να κωδικοποιήσουμε κάθε πλευρά ήταν ίσα με \(-\log _{2}P\). Ας δούμε τώρα πώς μπορούμε να εφαρμόσουμε αυτή την φόρμουλα σε μια κατανομή πιθανοτήτων που δεν είναι ομοιόμορφη αλλά μεροληπτεί υπέρ κάποιων τιμών. Έστω \(x\) μια μεταβλητή που παίρνει τις τιμές που πρόκειται να κωδικοποιήσουμε (π.χ για ένα εξάπλευρο ζάρι, θα ισχύει ότι \(x\in \left \{ 1,2,3,4,5,6 \right. \left. \right \}\)) και έστω \(P(x)\) η πιθανότητα αυτής της τιμής να έρθει. Ο αναμενόμενος αριθμός bits για να κωδικοποιήσουμε μια τιμή είναι ο ισοσταθμισμένος μέσος όρος των αριθμών bits που απαιτούνται για να κωδικοποιηθεί κάθε πιθανή τιμή, όπου η στάθμιση είναι η πιθανότητα αυτής της τιμής:
\[\sum_{x}^{.}P\left ( x \right )\times -\log _{2}P\left ( x \right )\]
Τώρα μπορούμε να πάμε πίσω στην αρχή που μιλήσαμε για το νόμισμα στο οποίο η κορόνα έρχεται \(1\) στις \(4\) φορές και τα γράμματα \(3\) στις \(4\). Είχαμε πει ότι για να μεταδοθεί το αποτέλεσμα κάθε ριξιάς αυτού του νομίσματος, απαιτούνται \(0,8113\) bits αλλά δεν εξηγήσαμε το πώς προέκυψε αυτό το νούμερο. Όπως σωστά φαντάζεσαι, προέκυψε από την παραπάνω φόρμουλα:
\[\frac{1}{4} \times -\log_{2}\frac{1}{4} \quad + \quad \frac{3}{4} \times -\log_{2}\frac{3}{4}=0.8113 \quad \text {bits}\]
Λέμε ότι ένα δίκαιο νόμισμα παράγει περισσότερη πληροφορία διότι χρειάζεται ένα ολόκληρο bit για να μεταδοθεί το αποτέλεσμα μιας ριξιάς:
\[\frac{1}{2} \times -\log_{2}\frac{1}{2} \quad + \quad \frac{1}{2} \times -\log_{2}\frac{1}{2}=1 \quad \text {bit}\]
Το κλειδί για να αποκτήσουμε μια βασική διαίσθηση του \(-P\log P\) για να υπολογίζουμε το μέγεθος της πληροφορίας, είναι να κατανοήσουμε την σχέση ανάμεσα στον αριθμό των μηνυμάτων που πρόκειται να κωδικοποιηθούν και στις πιθανότητές τους. Αν θέλουμε να κωδικοποιήσουμε οποιαδήποτε τιμή επιλέγοντας ανάμεσα σε \(8\) πιθανές τιμές, χρειαζόμαστε \(3\) bits γιατί \(\log _{2}8=3\). Φυσικά θεωρούμε ότι κατανομή των πιθανοτήτων είναι ομοιόμορφη.
Ο εναλλακτικός τρόπος να το εκφράσουμε είναι ο εξής: η πιθανότητα να έρθει μια συγκεκριμένη τιμή είναι \(\frac{1}{8}\) και \(-\log _{2} \frac{1}{8}\) άρα χρειαζόμαστε \(3\) bits για να μεταδώσουμε οποιαδήποτε απ’ αυτές τις τιμές. Αλγεβρικά, \(\log _{2}n=-\log _{2}\frac{1}{n}\), άρα οι δύο προσεγγίσεις είναι αντίστοιχες, όταν η κατανομή των πιθανοτήτων είναι ομοιόμορφη. Το πλεονέκτημα της δεύτερης προσέγγισης είναι ότι όταν η κατανομή των πιθανοτήτων δεν είναι ομοιόμορφη και δεν μπορούμε απλά να μετρήσουμε των αριθμό των τιμών, το περιεχόμενο της πληροφορίας μπορεί ακόμα να εκφραστεί ως πιθανότητες.
Κάποιες φορές περιγράφουμε σπάνια γεγονότα ως γεγονότα που «κουβαλάνε» μεγάλο αριθμό bits πληροφορίας. Για παράδειγμα, στην περίπτωση που ένα νόμισμα έρχεται κορόνα μόνο \(1\) φορά στις \(1.000\) ριξιές, το σήμα που λέει ότι «ήρθε κορόνα» χρειάζεται \(10\) bits. Πώς όμως γίνεται αυτό, αφού το αποτέλεσμα κάθε ριξιάς του νομίσματος μπορεί να περιγραφεί με μόλις \(1\) bit; Το κλειδί είναι ότι μεταδίδουμε το πότε ένα σπάνιο γεγονός έχει συμβεί. Χρησιμοποιώντας την μέθοδο μετρήματος των μηνυμάτων, αν μια τιμή έρχεται \(1\) στις \(1.000\) σε μια ομοιόμορφη κατανομή, τότε υπάρχουν άλλες \(999\) πιθανές τιμές, όλες το ίδιο πιθανές, οπότε το να μεταδώσουμε μια οποιαδήποτε τιμή θέλει όντως \(10\) bits.
Σε ένα νόμισμα υπάρχουν μόνο δύο πιθανές τιμές. Η θεωρία της πληροφορίας μας λέει να λαμβάνουμε υπ’ όψιν κάθε τιμή ξεχωριστά. Αν μια συγκεκριμένη τιμή έρχεται με πιθανότητες \(P\), θεωρούμε ότι προέρχεται από μια ομοιόμορφη κατανομή τιμών όταν υπολογίζουμε την πληροφορία που περιέχει. Το μέγεθος αυτών των τιμών θα είναι \(\frac{1}{P}\) στοιχεία. Έτσι, ο αριθμός των bits που απαιτούνται για να κωδικοποιήσουμε μια τιμή από αυτό το υποθετικό σύνολο τιμών, είναι \(\log _{2}P\). Από την στιγμή που η πραγματική κατανομή που θέλουμε να κωδικοποιήσουμε δεν είναι ομοιόμορφη, παίρνουμε τον ισοσταθμισμένο μέσο όρο του (βάση εκτιμήσεων) περιεχομένου της πληροφορίας κάθε τιμής (κορόνα και γράμματα για την περίπτωση του νομίσματος), ισοσταθμισμένο με την πιθανότητα \(P\) να έρθει αυτή η τιμή. Η θεωρία της πληροφορίας μας λέει ότι η βέλτιστη κωδικοποίηση δεν μπορεί να πάει πέρα απ’ αυτό. Έτσι, με αυτό το νόμισμα ακραίας μεροληψίας, έχει τα παρακάτω:
\(P\) (κορόνα) \(=\frac{1}{1000}\), άρα η κορόνα χρειάζεται \(-\log _{2}\frac{1}{1000}=9.96578\) bits για να κωδικοποιηθεί
\(P\) (γράμματα) \(=\frac{999}{1000}\), άρα τα γράμματα χρειάζονται \(-\log _{2}\frac{999}{1000}=0.00144\) bits για να κωδικοποιηθούν
Ο μέσος όρος των bits που απαιτούνται είναι:
\[\sum_{x}^{.}P\left ( x \right )\times -\log _{2}P\left ( x \right )\]
\[=\frac{1}{1000}\times 9.96578 \quad + \quad \frac{999}{1000}\times 0.00144 \quad = \quad 0.01141\]
Άρα χρειαζόμαστε \(0.01141\) bits για να κωδικοποιήσουμε κάθε ριξιά του νομίσματος. Όσο και να θέλουμε, δεν μπορούμε να την κωδικοποιήσουμε σε λιγότερα bits… ή τουλάχιστον αυτό λέει η θεωρία της πληροφορίας!
Recent Comments