Introduction to Complexity: Shannon Information Part 2 Complexity Explorer Greek English

Introduction to Complexity: Shannon Information Part 2YouTube↗ IA↗(long shot)
Science & Technology 6.5K views 3 likes 0 dislikes 13 Sep 2018

Complexity Explorer 36.4K subscribers United States YouTube↗

Σε αυτό το βίντεο θα σας δείξω πώς να υπολογίζετε το Περιεχόμενο Πληροφορίας του Shannnon.

In this video I'm going to show you how to compute Shannon information content.

Κατ' αρχήν, ας δούμε την αναλογία ανάμεσα στην Εντροπία του Boltzmann και στην Πληροφορία του Shannon.

First let's look at the analogy betweeen Boltzmann entropy and Shannon information.

O Shannon πήρε την ιδέα για το να χαρακτηρίζει την πληροφορία, από τη Στατιστική Μηχανική του Boltzmann.

Shannon got his idea for characterizing information from the statistical mechanics of Boltzmann.

Θυμηθείτε ότι ορίσαμε την έννοια της "μικροκατάστασης", ως μία λεπομερή διαμόρφωση των συστατικών μερών ενός συστήματος.

So, recall that we defined the notion of a "microstate" as some detailed configuration of the system components---

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

so, in the example of the slot machine, that would be one configuration of the slot machine windows, such as

όπως π.χ. "μήλο, αχλάδι, κεράσι" - και μία "μακροκατάσταση" είναι μία ομάδα ή συλλογή από μικροκαταστάσεις,

"apple, pear, cherry"---and a "macrostate" was some collection or set of microstates, such as

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

"all three the same" or, "exactly one apple", and the entropy, S, assumes that all microstates are equally probable

Να ξανά και εξίσωση, χαραγμένη ακόμη και στην επιτύμβια πλάκα του Boltzmann (!) - που λέει ότι η εντροπία μιας συγκεκριμένης μακροκατάστασης,

and here was the equation, engraved on Boltzmann's tomb, that says that the entropy of a particular macrostate

είναι ίση με k, τη σταθερά Boltzmann, επί τον log του W. Εδώ με τον όρο "λογάριθμος" (log) ο Boltzmann

was equal to k, Boltzmann's constant, times the log of W. Here this log---"l-o-g"---he used this to mean

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

the natural log, and W was the number of microstates corresponding to this macrostate.

Η σταθερά k διαμορφώθηκε ώστε να αποδοθούν μονάδες στη σχέση αυτή. Συχνά μετριέται σε Joules ανά Kelvin, αλλά για τους

K just gave us a way of assigning units, measured often in Joules per Kelvin, but for our purposes that

σκοπούς του μαθήματος, θα υποθέσουμε ότι το k ισούται με 1. Αυτό γίνεται συχνά σε υπολογισμούς της εντροπίας,

k is equal to 1---let's just assume that---people actually do that to compute entropy sometimes,

και μας δίνει την εντροπία σε διαφορετικές μονάδες, αλλά μπορούμε να το χρησιμοποιούμε για να συγκρίνουμε εντροπίες μεταξύ τους.

and it just gives us the entropy in different units, but we can use it to compare entropies.

Έτσι, για παράδειγμα, ας δούμε τον "κουλοχέρη" μας.

So, for example, let's look back at our slot machine.

Θυμηθείτε το κουίζ μας, όπου ρωτάγαμε πόσες μικροκαταστάσεις αντιστοιχούν στην μακροκατάσταση "νικώ", με τα

Remember our quiz, where we asked you how many microstates give rise to the "win" macrostate,

"τρία ίδια φρούτα", και αυτές ήταν 5, και πόσες μικροκαταστάσεις αντιστοιχούν στη μακροκατάσταση "χάνω",

"all three the same", and that was 5, and how many microstates give rise to the "lose" macrostate,

και αυτές ήταν 120, άρα σύμφωνα με την εξίσωση του Boltzmann, εάν υποθέσουμε ότι το k, η σταθερά του Boltzmann,

and that was 120, so according to Boltzmann, if we assume that k, the Boltzmann constant, is 1, then

είναι 1, τότε παίρνουμε ότι η εντροπία S αυτής της μακροκατάστασης, ας την πούμε S της "μακροκατάστασης-νίκης", είναι ίση με το

we get S of this macrostate, let's call this S of the win macrostate, is equal to the natural

φυσικό λογάριθμο του 5, που είναι περίπου 1,61, και η S της "μακροκατάστασης-ήττας" είναι ίση με το φυσικό λογάριθμο του 120, που είναι περίπου 4,79,...

log of 5, which is about 1.61, and the S of lose is equal to the natural log of 120, which is about 4.79---

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

and the reason Boltzmann used the natural log here was to get this in a certain range of numbers,

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

so usually we're talking about systems with a huge number of microstates that give rise to particular macrostates,

και ο φυσικός λογάριθμος ήταν ένας τρόπος να μικρύνουν αυτοί οι πολύ μεγάλοι αριθμοί.

and the natural log was the way of scaling those very large numbers.

Δε χρειάζεται να ανησυχείτε για τις λεπτομέρειες πάνω σ' αυτά, αλλά μπορείτε να δείτε ότι η πληροφορία - λάθος,

But you don't have to worry about the details of that, but you can see that the information---I'm sorry,

η εντροπία κατά Boltzmann της μιας μακροκατάστασης είναι πολύ μικρότερη από την

the Boltzmann entropy of this macrostate is much smaller than the Boltzmann entropy

εντροπία κατά Boltzmann της άλλης μακροκατάστασης, κάτι που προβλέπαμε και διαισθητικά.

of this macrostate, which was our intuition.

Τώρα, για να επιστρέψουμε στην αναλογία που έχουμε δει, η πληροφορία κατά Shannon μιας μικροκατάστασης, είναι ένα μήνυμα -

Now, returning to our analogy, the Shannon information version of a microstate is a message---

ένα σύμβολο, ένας αριθμός, μια λέξη - και η πληροφορία κατά Shannon μιας μακροκατάστασης είναι

a symbol, number, or word---and the Shannon information version of a macrostate was a message source,

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

which is a collection or set of possible messages, with some probability for sending each possible message.

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

Now, just as we did for Boltzmann entropy, we're going to assume here that all the messages are equally probable,

ορίζοντας ως Μ τον αριθμό των μηνυμάτων.

with M being the number of messages.

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

Now, we can define H, the Shannon information content of a message source,

είναι ίσο με το λογάριθμο με βάση 2 του Μ, δηλαδή με το λογάριθμο με βάση 2, του αριθμού των μηνυμάτων.

as being equal to the log base 2 M, that is, the log base 2 of the number of messages.

Ο λογάριθμος με βάση το 2, μας επιτρέπει να μετρήσουμε το περιεχόμενο πληροφορίας σε bits-ανά-μήνυμα.

The log base 2 allows us to measure the information content in bits-per-message.

Ας πάρουμε το παράδειγμα ενός μωρού 1 έτους, που λέει μόνο "ντα-ντα-ντα-ντα", άρα εδώ έχουμε ένα μόνο μήνυμα,

Here's our example of our 1-year-old, who only says "da da da da", so there's only one message here,

και το περιεχόμενο πληροφορίας κατά Shannon είναι ίσο με το λογάριθμο, με βάση 2, του 1.

and our Shannon information content is equal to the log, base 2, of 1.

Όμως, 2 υψωμένο στη μηδενική κάνει 1, άρα το περιεχόμενο πληροφορίας εδώ είναι 0, που το προβλέπαμε και διαισθητικά -

Well, 2 raised to the 0th power is 1, so the information content is 0, which went with our intuition---

δεν υπάρχει εδώ καμιά μη προβλεψιμότητα, δεν υπάρχει καμιά έκπληξη.

there's no unpredictability, there's no surprise. Now,

Τώρα, ας υποθέσουμε ότι αντί για "ντα-ντα-ντα", το μωρό μας λέει "ντα-μπα-μα", δηλαδή τρία μηνύματα.

suppose now that instead of "da da da", our baby said "da ba ma", that is three messages,

Σε αυτήν την περίπτωση, ο Μ θα ήταν ίσος με 3, και το Η θα ήταν ίσο με το λογάριθμο με βάση 2 του 3, το οποίο,

so if that were the case, then M would be equal to 3, and H would be equal to log base 2 of 3, which,

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

according to my calculator, is 1.58. So, that gives us quite a bit more information content than

από ό,τι όταν υπάρχει μόνο ένα μήνυμα.

when there's only one message.

Στο παράδειγμά μας με το "αμερόληπτο" νόμισμα και το "κορώνα ή γράμματα", υπάρχουν δύο μηνύματα,

Our example with a fair coin, heads or tails, there's two messages,

έτσι το Η ενός αμερόληπτου νομίσματος ισούται με το λογάριθμο με βάση 2 του 2, που ισούται με 1,

so H of a fair coin is equal to the log base 2 of 2, which equals 1,

άρα το περιεχόμενο πληροφορίας εδώ ισούται με 1, το οποίο είναι πάντοτε το περιεχόμενο πληροφορίας

so the information content here is 1, which is always the information content

όποτε έχουμε μόνο δύο ενδεχόμενα, "κορώνα" και "γράμματα" ή "0" και "1", "ναι" ή "όχι", με ίση πιθανότητα.

if we have two choices, heads or tails, 0 or 1, with equal probability.

Ένα ακόμη παράδειγμα αυτής της μορφής, είναι το περιεχόμενο πληροφορίας ενός "αμερόληπτου" ζαριού. Εδώ ο Μ είναι 6 - υπάρχουν 6 πιθανά μηνύματα, ένα για κάθε πλευρά του ζαριού,

One more example of this kind, the information content of a fair die is equal to, well here M equals 6---there's 6 possible messages, one for each side of the die,

άρα το Η ισούται με το λογάριθμο με βάση 2 του 6, που ισούται περίπου με 2,58 (bits -"τμήματα" πληροφορίας).

so it's equal to the log, base 2, of 6, which is approximately equal to 2.58, and that's in bits.

Αργότερα, θα σας πω λίγο περισσότερα, ως προς το τι σημαίνει αυτό,

So I'll tell you a little bit more, later on, what exactly this represents, in terms of

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

coding or computer memory, but for now it goes along with our intuition that this has the highest information content

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

so far that we've seen because there's 6 different messages.

Τώρα θα γράψω έναν πιο γενικό μαθηματικό τύπο.

Well now I'm gonna write down a more general formula.

Στον προηγούμενο τύπο, υποθέταμε ότι όλα τα μηνύματα είναι ισοπίθανα,

For the previous formula, we were assuming that all messages have equal probability,

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

but most often that's not the case, there's different messages with different probabilities---

έχουμε δηλ. ένα "μεροληπτικό" νόμισμα ή, πιο ρεαλιστικά, έχουμε ένα άτομο που μιλάει και οι λέξεις που

we have a biased coin, or, more realistically, we have a person who's talking and the words that

βγαίνουν από το στόμα του δεν θα είναι ίσης πιθανότητας.

come out of their mouth are not going to be equally probable.

Ένας πιο γενικός μαθηματικός τύπος - και αυτός είναι ο τύπος που πραγματικά έδωσε ο Shannon - λέει ότι:

A more general formula---and this is the formula that Shannon actually wrote down---says,

έστω Μ ο αριθμός των πιθανών μηνυμάτων. Θα αποδώσουμε μία τιμή πιθανότητας σε

let M be the number of possible messages, and we're going to assign a probability

κάθε μήνυμα. Έτσι θα συμβολίσουμε την πιθανότητα του i-μηνύματος, ενός δηλαδή από τα Μ μηνύματα,

to each message. So we'll call the probability of message i, that's one of the M messages,

με p με δείκτη i - αυτό είναι απλά ένα όνομα για την πιθανότητα που αποδίδεται στο μήνυμα i - και

p, sub i---this is just a name for a probability given to message i---and Shannon's

ο τύπος του Shannon λέει ότι η πιθανότητα αυτής της πηγής μηνυμάτων - αυτό είναι το σύμβολο της άθροισης -

formula said the probability of this message source---well, this is a summation symbol,

είναι αυτή, δηλαδή αθροίζουμε όλους τους διαφορετικούς - για κάθε τιμή του i -

this says we're going to sum up all of the different---for each message i, all the way up to the total

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

number of messages, this log-2 of the probability, times the probability. So this is like taking a weighted average,

σταθμισμένη μέση τιμή, ως πρός την πιθανότητα. Βάζουμε το πρόσημο μείον επειδή όλες αυτές οι πιθανότητες είναι κλάσματα κάτω του 1,

weighted by probability, and we put a minus sign out here because these probabilities are all fractions,

και ο λογάριθμος ενός τέτοιου κλάσματος είναι αρνητικός. Οπότε βάζουμε μείον

and the log of a fraction is going to be negative, so we put the minus sign out here

για να αντισταθμίσουμε αυτό το μείον. Θα το δείτε αυτό σε κάποια παραδείγματα.

to counteract that negative, so you'll see that in a couple of examples.

Τώρα, αν δεν καταλαβαίνετε αυτόν τον τύπο, κάντε υπομονή. Θα σας δείξω πώς δουλεύει στην πράξη.

Now, if you don't understand this formula, just be patient, because I'll show you how it works in practice.

Ας υποθέσουμε τώρα ότι έχουμε ένα "μεροληπτικό" νόμισμα.

Let's assume now that we have a biased coin,

και ότι η πιθανότητα για "κορώνα", δεν είναι πια 1/2, αλλά ας πούμε ότι είναι 0,6, ενώ η πιθανότητα για "γράμματα" είναι 0,4.

and that the probability of heads is no longer 1/2, but let's say that it's .6, and the probability of tails is .4.

Οπότε, ποιο είναι το περιεχόμενο πληροφορίας αυτού;

Ok, what is the information content of this?

Ας γράψουμε το μαθηματικό τύπο: το Η, το περιεχόμενο πληροφορίας του "μεροληπτικού" νομίσματος,

So, let's wright down our formula, H, the information content of the biased coin,

είναι ίσο με μείον το άθροισμα των δύο όρων, που εδώ είναι

is equal to minus the sum of the two components here, which is .6

0,6 επί τον λογάριθμο με βάση 2 του 0,6, συν 0,4 επί τον λογάριθμο με βάση 2 του 0,4, που στο κομπιουτεράκι μου

times log base 2 of .6, plus .4 times log base 2 of .4, which, on my calculator,

βγαίνει περίπου ίσο με 0,971 "κομμάτια πληροφορίας". Άρα, έχουμε μικρότερο περιεχόμενο πληροφορίας, από ό,τι στο αμερόληπτο νόμισμα.

approximately .971 bits. So this is lower information content than the fair coin,

το οποίο είχε περιεχόμενο πληροφορίας ίσο με 1 bit - "κομμάτι", και αυτό φυσικά γιατί εδώ το νόμισμα είναι πιο προβλέψιμο -

which had information content of 1 bit, and that's because, of course, this is more predictable---

είναι πιο πιθανό να έρθει "κορώνα" από ό,τι "γράμματα".

heads is more likely to come up than tails.

Τώρα θα κάνω κάτι πιο γενικό και θα εξετάσω ένα παράδειγμα περιεχομένου πληροφορίας ενός κειμένου.

Well now I can do something a little more general and look at an example of text information content.

Ας υποθέσουμε ότι έχω ένα κείμενο. Το ερώτημα είναι: ποιο είναι το περιεχόμενο πληροφορίας αυτού του κειμένου;

So suppose that I have a text, my question is what is the information content of this text?

Υπάρχουν, στην πράξη, διάφοροι τρόποι για να το υπολογίσουμε αυτό, και οι άνθρωποι

There's actually a number of ways to calculate that, and people do

υπολογίζουν το περιεχόμενο πληροφορίας ενός κειμένου, π.χ. ως ένα μέτρο της πολυπλοκότητας αυτού, αλλά

calculate the information content of text, as a measure of its complexity, for exampe, but

αυτό που θα κάνω εγώ θα είναι να εξετάσω τη συχνότητα των διαφόρων λέξεων

the way that I'm going to do it is to look at the frequency of the different words

ως ένα μέτρο της πιθανότητάς τους. Για κάθε λέξη, θα γράψω τη λέξη,

as a measure of their probability. For each word, I'm going to write down the word,

τη συχνότητά της, και κατόπιν, αυτό που θα ονομάσω τη "σχετική της συχνότητα".

its frequency, and then, what I'm going to call its relative frequency.

Οπότε, ας δούμε τι γίνεται: η λέξη "να"εμφανίζεται δύο φορές, στο "να ζεις ή να μην ζεις", αλλά υπάρχουν 6 λέξεις συνολικά,

So let's see... the word "to" appears twice, "to be or not to be", but there's 6 words altogether,

οπότε θα ονομάσω τη σχετική συχνότητα της λέξης αυτής 2/6, άρα μέσα στις 6 λέξεις

so I'm going to call its relative frequency 2/6, so out of the 6 words

αυτή εμφανίζεται 2 φορές. Το "ζεις" εμφανίζεται επίσης 2 φορές, το "ή" εμφανίζεται 1, το "μην" επίσης μία.

it appears twice. "Be" appears twice also, "or" appears once, "not" appears once...

Θα καταστήσουμε αυτές τις σχετικές πιθανότητες, πιθανότητες των λέξεων, κι έτσι μπορούμε να πούμε ότι το περιεχόμενο πληροφορίας

we'll make these relative frequencies their probabilities so we can say that the information content

αυτού του κειμένου είναι ίσο με: μείον το άθροισμα των όρων που αντιστοιχούν σε κάθε μήνυμα,

of this text is equal to minus, and now we're going to sum up for each message,

δηλαδή, για κάθε λέξη, την πιθανότητά της επί το λογάριθμο με βάση 2 της πιθανότητας,

that is, each word, its probability times the log base 2 of its probability,

και θα το υπολογίζουμε αυτό για κάθε λέξη.... Και το άθροισμα είναι τελικά ίσο με 1,9.

and we're going to do that for each word... and that's approximately equal to 1.9.

Συνεπώς, αυτός είναι ένας τρόπος να υπολογίζουμε το περιεχόμενο πληροφορίας ενός τμήματος κειμένου - θα δούμε λίγο περισσότερα

So this is a way of calculating the information content of a piece of text---we'll see a little bit more

πάνω σε αυτό, στις Ασκήσεις.

on that in the exercises.

Υπότιτλοι από την κοινότητα Amara.org

Subtitles by the Amara.org community