Uses of Information Theory - Computerphile
ฝัง
- เผยแพร่เมื่อ 28 พ.ค. 2024
- Looking at some real world uses of information theory with Dr Tim Muller
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
"If you use Log 2, you're a computer scientist. If you use Log 10, you're an engineer."
If you use natural log, you're a physicist
what if you use ln?
@@tpobrienjr space cadet intellectual.
@@tpobrienjr then you're a biologist
@@tpobrienjr mathematician? - unless you study the general thing. Then you'd use base b
Sean said that you learn a quarter of the dataset with 1 of the 4 dice results revealed. Later on he points out you learned roughly 2.6 bits of information, out of 10.3. 2.6 divided by 10.3 is 0.252... or almost exactly a quarter. Sounds like Sean was right! Maybe just not expressing the answer in a way that Tim expected.
Yes, because case 1: log_2(6*6*6*6) = log_2(6^4) = 4*log_2(6)
and case 2: log_2(6*6*6) = log_2(6^3) = 3*log_2(6)
So one the difference is exactly a quarter.
@@pirmelephant The entropy of the information is not the information itself, you don't learn a quarter of the information.
@@Geezon Yes that's true. I just wanted to show that you learn exactly a quarter of the entropy and not a only almost exactly a quarter.
@@pirmelephant Still not true.
Every increment of one bit doubles the amount of information. So 2.6 bits is not 0.252% of 10.3 bits. Remember, there was a log calculation in there, so linearity is out the window.
@@luxhey When told the value of the first die, you do in fact learn 25% of the information. Bits of entropy = information. The number of possibilities isn't the information. If I told you that an mp4 of Back to the Future was 2 GB, and I gave you a 500 MB sample equating to the first 1/4 of the movie, you do in fact have 1/4 of the information.
The number of possible arrangements of the bits went from 2^(2* 10^9) to 2^(5*10^6) when I gave you the first 1/4 of the movie, but your reasoning would suggest that we learned basically none of the information
We owe so much to the work of Turing and Shannon! In the satellite world discussion of the Shannon limit of information throughout is part of our daily life in optimising power, bandwidth and error correction codes!
Having a coffee machine on his own desk is truly a proof that Dr Tim is a very smart man.
My favourite Dr Muller video so far! Really helps me with designing some solid k-anonymous data sets.
9:15 you say "that's not quite right" that you've learned a quarter of the information but then go on to say that the entropy before is log2(6*6*6*6)=4log2(6), after the entropy is log2(6*6*6)=3log2(6), so I'd argue its kinda right... Unless I'm missing something?
Good point. I'd like someone smarter to clarify
@@thishandleistaken. The point was that it wasn't a set of 4 reduced to 3 by learning one of the dice values, it was a set of 1296 (all possible outcomes) reduced to 216 (possible outcomes for the other 3 dice). 1080 possibilities being removed is not 25% of 1296 it's 5/6th or ~83%.
@@thishandleistaken. Every increment of one bit doubles the amount of information. So 2.6 bits is not 0.252% of 10.3 bits. Remember, there was a log calculation in there, so linearity is out the window.
"A quarter of entropy" is right, but that's not a quarter of information. Think of it like this: how much time does it take to brute-force a 6 bit password compared to an 8 bit one? It's not 25% less, it's 4x less.
You can massively increase the entropy of the four words if you use more than one language or use names and brands and not just dictionary words
👇Useful intuition from 9:20
The information of an observation is the (log of) the factor by which the space of possibilities was reduced upon seeing that observation.
I have the exact same coffee machine, the auto off is very annoying, especially if it switches off just as you walk up to it to make a cup
You can change the duration it stays on before turning off
Drug addict.
@@TomTheDutchyIt isn’t about the settings I guess but the life itself being ill-timed sometime 🤷🏻♂️
Question: when you select your "random" words as a human and pick the xkcd method of four words, how does the hacker algorithm know that it's a human chosen so it limits the words to what words you know/would use/the wildest combination of words that have never before seen connections less than random? How does cracking the password get faster in practice for the hacker? How does he know it's words over random characters and four words of specific length to combine? Can he snoop the size of the password? I know the cracker can just try to combine every possible 4 words, but does that make it more plausible to crack the password in real life? I understand that in math theory they are not equivalent to this video, but does your password get cracked because of this? Or does some website actually not protect the passwords adequately and they just get leaked instead of cracked?
Actually, the hacker doesn't know that the password was chosen from human words. But, because brute forcing all the possible length/characters is so expensive (in terms of bits of work), the hacker might begin with a dictionary attack, then use some modifications of that same attack, like combinations of words, and finally pure brute force, like AAA, AAB and so on. So, trying to answer your question, it is faster because you try the word guessing technique before classical brute force attack.
Of course, a little bit of social engineering might help...
The diceware method uses a very long list of words. This list is very long when compared with the number of words that a person can think of just off the top of their head. Thus a shorter list of more common words will suffice - or starting with only those more common words before trying the rest of the list, which in such a case will hit a match quicker.
This all assumes the least one cracker using the assumption that diceware was used for generating the password.
Is there some kind of measure of information utility that would allow us to mathematically distinguish between the two cases "we know die 1" and "we know dice 1 and 2 are the same"?
Not a specialist in the field but you could look at the entropy of projections of the distribution onto sub-selections of dice.
In practice this could mean having a lower bound for the entropy of each individual dice, another bound for the distributions of each pair of dice, another for each triplet etc.
In the given example if you know dice 1 the distribution of that dice will have no entropy.
If, however, you only know that dice 1 and 2 have the same result the individual dice would not see an entropy reduction at all.
In both cases the pair of dice 1 and 2 together will be subject of an entropy reduction by 1/2.
So using that metric the 2nd distribution would perform better than the first distribution.
What's your name? - Same as grandpa's. - And what's your grandpa's name? - Same as mine!
How much does misspelled words increase entropy?
Not very much.
Algorithms are adept at shuffling character order.
What if I use words for password from different laguages? Would it somehow increase the strenght?
Glad to hear you got better pens for future videos. The scratching noise doesn't bother me quite as much as the lack of legibility. As others too have pointed out, blue ink from a dried-out pen on blue-ruled paper is a bit hard to read.
Do you get black Sharpies in the UK? I'm a fan-and believe me, it's _not_ because of Trump!
Ok, but just as comparation, have all diferent values. How that change the possibilitys? I will try to calculate that, but! I'm still want to know if i'm right
fanstastic thanks made my day
What about increasing the number of languages used in the passphrase? Wouldn't that drastically increase the entropy again?
If you know as many words in a second language using both would increase the entropy by 1 bit per word, I would not consider that a drastic improvement.
It should be considered that the 11 bit per word entropy already assumes that you are only working with about 2000 possible words anyways so you could also just increase the selection of English words.
At the end of the day the limiting factor is the given person's capacity to remember a password well, even though the words were chosen at random.
The strategy of building a small story as a mnemonic device might suffer a bit, if the words randomly switch languages.
@@entropie-3622 How many languages are there on this planet? How would an attacker know which languages are being used? Do I have to know a language in order to use a word in a passphrase? Let's say my passphrase consists of 5 words, from 5 different languages. So which word lists do you pick?
@@nahco3994 Obviously if you could use any language that exists it will increase entropy quite a lot but for most people it will decrease their capacity to memorize the password quite a lot as well.
If you just want a secure password not caring about the ability to memorize it (usually because you are using a password manager) it will always be best to just use a completely random string of characters.
If you care about the ability to memorize the password most people will be restricted to 1 or maybe 2 foreign languages that they know well enough.
Relying on the idea that the attacker will not be able to guess the used languages is usually not a good approach to security. Generally a password should be chosen in a way so that it is secure even if the attacker knows the distribution that was used to create it.
Cant you post-process some edge sharpening on the blue channel to help with the pen?
I did have a play with that but the papers stripes were extremely close to the blue and by the time I isolated it his arms/hands looked a very strange colour indeed. Decided to live with it and buy some new pens for future! Apologies for how terribly feint they are, originally bought them because they seemed quieter than other pens and we get complaints about pen squeak -Sean
So you can derive Information Theory from Probability Theory by taking the log to base 2? 🤔
The paper looks like musical staff but then I noticed it has 6 lines too close to each other. What is this paper for?
This is traditional computing printer paper. It has been around for 50 years or more. It helps someone to read long text prints, in the past often computer code print outs.
"Eyeline" tractor-feed paper.
Can someone explain why the xkcd format is 11 bits per word?
I would guess that there is an assumption that there are about 2000 "common English words" to choose from uniformly at random.
‘’Courage taught me no matter how bad a crisis gets ... any sound investment will eventually pay off."
I propose anyone who can to solve these 3 chess problems problems:
1 - Is it possible in a chess engine, like STOCKFISH NNUE or Google's ALPHA ZERO to translate their machine learned parameters into a HUMAN INTELIGIBLE ALGORITHM (as simplified as it can get) on how to best evaluate a chess position/choose the best move?
2 - Can you mathmatically prove that there's a maximum number of parameters a chess engine must have to play a perfect game (always play the move that leads to the faster check mate OR maintains a drawing position ( or NOT LOSING NOR WINNING within the range of the next 50 moves, as todays chess rules)?
3- If there's such a maximum number of parameter, can you find it?
I'm a mediocre chess player and inthusiast, so that would be nice if you guys made a video about those questions. Thank you in advance!
james grime on the sister channel numberphile, has a video on chess games. thing is that you have more posibile moves as the games goes further, until you hit a maximum and number starts to drop. theoretically, all posibile moves can be simulated, programmed, and chosen best move in any case based on 'weights' as in language models.
Intuitively, conditional entropy appears when you are solving a sudoku or a minesweeper game.
I don't get it, but it sounds neat
My Magnifica S also startles people when it auto cleans.
Anyhow, even after doing my phd in signal processing in the edge of information theory (using stiff nonlinear ODEs in particle filters), I still find it very confusing. It requires such a different way of thinking.
It's pretty simply actually: if the people aren't used to the behaviour of your coffee machine, the sudden onset of sound can come as a surprise. Doesn't really take a PhD to understand, but whatever
It was 1/4 of the entropy. why did the guy correct him?
It wasn't though. For every increment of 1 bit, the amount of information doubles. Remember we did a log calculation, so linearity is gone.
Very relevant, I was studying information theory
xkcd 538 shows us that strong passwords don't help in all circumstances.
Classic example of Theory != Real World
His conclusion is incorrect because not every disease is equally probable and thus the information gain can not be compared to dice rolling. But very interesting nonetheless.
How package managers solve dependencies?
Direct Acyclic Graphs
@@code-dredd thanks alot,
i just wanted videos for it.
@@meguellatiyounes8659 There's at least one in this channel, but you have to search. Might need to look at Git videos, which rely on the same data structure.
KL divergence my friend
I was thinking, hmm familiar accent… apparently he did his master at the same university as I’m currently working, haha.
This isn't the running channel.
0 belongs before 1, not after 9.
if you calculate entropy in n bits, then bit is 2 options, so its 2 on n combinations, not your set size on n.
My passwords are made up of only invisible Unicode control characters
permutations
For those questioning why it isn't 25% learned from knowing one die. The question isn't what is the entropy of the information learned.
Knowing one die isn't 1/4 of the information, it removes 5/6 of the total possibilities for 4 dice rolls.
You learned 1/6 of the possible values for the one die but the other 3 dice have 216 combinations, from the set of 1296 possibilities of all 4 dice.
So you learned about 83% - by discarding 1080 possibilities of the 4 dice.
"Information" in this context is the same as entropy, no one uses the term "information" to describe "number of possibilities".
It seems to just have been an oversight of the lecturer trying to steer the conversation to the "number of possibilities" view of things somewhat disregarding Brady's correct intuition.
Crypto wallet recovery phrases like Metamask are a whole bunch of random words together
Nf3
you can acquire information.
but it may not be useful
This makes me wonder: Is information theory all about entropy? Is there anything else to learn in this field?
We don't know what we don't know. It wasn't until the recent discoveries in modern cryptography that a new application for prime numbers was found, since the difficulty of trying to find prime factors lies at the foundation.
Sads me that likes were 128 and dislikes were 2, and I would have to un-power-of-two them to like this video :(
Algorithm.
The password doesn't have entropy. The method for generating the password had a lot of entropy.
The video is 3 minutes old but there is a comment 4 minutes old. Sus.
sussy
Google has negative latency, dontcha know
how much information is in consecutive uniform numbers, ie, sum of log (1->n)
can you derive the real gamma function from the sum of discrete (integer) logarithm sequence
but the left side p_i is always the same (1), but right side is always +1 to the previous
what is that measurement then
what is log(x+y)=log(x)+?, or log(n+1)=log(n)+?
then the logsum will be something of the form of n*log(1) + (n-1)*log(?) + .... as +1 composite
My password is WomanManCameraTV
... and the last 5 digits of Pi.
Mine is *********************
Guys seriously buy some new pe.... oh.
He didn't say whether the die were 6-sided. Why would he assume they were 6-sided?
There r actually 95 different password enterable chars (including the space).
Please don't use these type of papers again. They are very unreadable.
Entropy = nonsense
What do you mean?
@@HapChandler876 Meaning, they failed their thermodynamics and/or information theory course! 🤣
@@HapChandler876 Perhaps "nonsense" in the sense that entropy represents possibility space, which could be equated to noise; useless information; nonsense.
4th :O
First ✌
Second too lol
3rd 😴
5th!!! Bye