엔트로피의 컴퓨터 과학 정의는 무엇입니까?
저는 최근에 제 대학에서 데이터 압축 과정을 시작했습니다. 그러나 컴퓨터 과학에 적용되는 "엔트로피"라는 용어의 사용은 다소 모호합니다. 내가 말할 수있는 한, 그것은 대략 시스템이나 구조의 "무작위성"으로 해석됩니다.
컴퓨터 과학 "엔트로피"의 올바른 정의는 무엇입니까?
엔트로피는 다른 의미를 가질 수 있습니다.
컴퓨팅에서 엔트로피는 암호화 또는 임의 데이터가 필요한 기타 용도로 사용하기 위해 운영 체제 또는 응용 프로그램에서 수집 한 임의성입니다. 이 임의성은 종종 마우스 움직임과 같은 기존의 하드웨어 소스 또는 특별히 제공된 임의성 생성기에서 수집됩니다.
정보 이론에서 엔트로피는 랜덤 변수와 관련된 불확실성의 척도입니다. 이 문맥에서 그 자체로 용어는 일반적으로 메시지에 포함 된 정보를 일반적으로 비트와 같은 단위로 예상되는 값의 의미에서 정량화하는 Shannon 엔트로피를 나타냅니다. 마찬가지로, Shannon 엔트로피는 랜덤 변수의 값을 모를 때 누락 된 평균 정보 콘텐츠의 척도입니다.
데이터 압축의 엔트로피
데이터 압축의 엔트로피는 압축 알고리즘에 입력하는 데이터의 임의성을 나타낼 수 있습니다. 엔트로피가 많을수록 압축률이 낮아집니다. 즉, 텍스트가 무작위 일수록 압축 할 수 있습니다.
Shannon의 엔트로피는 모든 통신에서 가능한 최상의 무손실 압축에 대한 절대 한계를 나타냅니다. 인코딩 할 메시지를 독립적이고 동일하게 분포 된 무작위 변수의 시퀀스로 취급하는 Shannon의 소스 코딩 정리는 한계에서 가장 짧은 길이의 평균 길이를 보여줍니다. 주어진 알파벳으로 메시지를 인코딩하는 가능한 표현은 대상 알파벳의 기호 수의 로그로 나눈 엔트로피입니다.
제가 가장 좋아하는 정의는 좀 더 실용적인 초점을두고있는 훌륭한 책 The Pragmatic Programmer : From Journeyman to Master by Andrew Hunt and David Thomas의 1 장에서 찾을 수 있습니다 .
소프트웨어 엔트로피
소프트웨어 개발은 거의 모든 물리적 법칙으로부터 자유롭지 만 엔트로피는 우리를 강타합니다. 엔트로피는 시스템에서 "장애"의 양을 나타내는 물리학 용어입니다. 불행히도 열역학 법칙은 우주의 엔트로피가 최대로 향하는 경향이 있음을 보장합니다. 소프트웨어에서 장애가 증가하면 프로그래머는이를 "소프트웨어 부패"라고 부릅니다.
소프트웨어 부패에 기여할 수있는 많은 요인이 있습니다. 가장 중요한 것은 프로젝트에서 작업중인 심리학 또는 문화 인 것 같습니다. 하나의 팀이라도 프로젝트의 심리학은 매우 섬세 할 수 있습니다. 최고의 계획과 최고의 사람들에도 불구하고 프로젝트는 평생 동안 여전히 파멸과 부패를 경험할 수 있습니다. 그러나 엄청난 어려움과 끊임없는 좌절에도 불구하고 무질서에 대한 자연의 경향과 성공적으로 싸우고 꽤 잘 나온 다른 프로젝트가 있습니다.
...
...
깨진 창문.
상당한 시간 동안 수리하지 않은 채로 깨진 창문 하나는 건물의 주민들에게 건물에 대해 신경 쓰지 않는 힘이 있다는 느낌 인 버림받은 느낌을 불어 넣습니다. 그래서 또 다른 창문이 깨집니다. 사람들은 쓰레기를 버리기 시작합니다. 낙서가 나타납니다. 심각한 구조적 손상이 시작됩니다. 상대적으로 짧은 시간에 건물을 고치려는 주인의 욕구를 넘어 건물이 훼손되고 버림 감이 현실이된다.
"Broken Window Theory"는 뉴욕과 다른 주요 도시의 경찰서가 큰 물건을 차단하기 위해 작은 물건을 단속하도록 고무 시켰습니다. 작동합니다. 깨진 창문, 낙서 및 기타 작은 위반 사항을 맨 위에 유지하면 심각한 범죄 수준이 감소했습니다.
팁 4
깨진 창문으로 살지 마십시오
"깨진 창"(잘못된 디자인, 잘못된 결정 또는 잘못된 코드)을 수리하지 않고 그대로 두지 마십시오. 발견되는 즉시 수정하십시오. 제대로 고칠 시간이 부족하면 탑승하세요. 문제가되는 코드를 주석 처리하거나 "구현되지 않음"메시지를 표시하거나 대신 더미 데이터를 대체 할 수 있습니다. 추가 손상을 방지하고 상황을 파악하기 위해 조치를 취하십시오.
출처 : http://pragprog.com/the-pragmatic-programmer/extracts/software-entropy
(출처 : mit.edu )
에서 멕시코의 대학
엔트로피의 정보 이론적 개념은 물리적 개념의 일반화입니다. 엔트로피를 설명하는 방법에는 여러 가지가 있습니다. 랜덤 변수의 랜덤 성의 척도입니다. 또한 랜덤 변수 또는 확률 적 프로세스에 포함 된 정보의 양에 대한 척도입니다. 또한 메시지를 압축 할 수있는 양의 하한이기도합니다. 마지막으로 값을 결정하기 위해 임의의 엔티티에 대해 질문해야하는 예 / 아니오 질문의 평균 수입니다.
확률 계산을위한 샘플 애플리케이션의 엔트로피 방정식 :
그것은 그 값의 확률과 그 확률의 로그를 곱한 rv의 모든 값에 대한 합입니다 (즉, p (x) logp (x)). 이 방정식은 정보 속성의 첫 번째 원칙에서 파생 될 수 있습니다.
나는 항상 Shannon Entropy의 의미에서 엔트로피를 만났습니다.
에서 http://en.wikipedia.org/wiki/Information_entropy :
정보 이론에서 엔트로피는 랜덤 변수와 관련된 불확실성의 척도입니다. 이 문맥에서 그 자체로 용어는 일반적으로 메시지에 포함 된 정보를 일반적으로 비트와 같은 단위로 예상되는 값의 의미에서 정량화하는 Shannon 엔트로피를 나타냅니다. 마찬가지로, Shannon 엔트로피는 확률 변수의 값을 알지 못할 때 누락 된 평균 정보 콘텐츠의 척도입니다.
압축 및 정보 이론의 관점에서 소스의 엔트로피는 소스의 심볼이 전달할 수있는 평균 정보 양 (비트 단위)입니다. 비공식적으로 말하면 상징이있을 가능성이 높을수록 그 모양이 더 놀라움을 가져옵니다.
소스는 두 심볼 말하자면이있는 경우 A와 B, 그들이 똑같이 가능성, 다음 각 기호가 전달하는 정보 (한 비트)의 같은 양. 같은 가능성이있는 4 개의 심볼이있는 소스는 심볼 당 2 비트를 전달합니다.
소스는 세 개의 문자가있는 경우 더 흥미로운 예를 들어, A, B,과 C, 처음 두가 아마로 세 번째 배있는 곳, 그 다음 세 번째는 더 놀라운 미만 가능성도있다. 아래 계산 된대로이 소스에 대한 순 엔트로피는 1.52입니다.
엔트로피를 "평균 놀라움"으로 계산합니다. 여기서 각 기호의 "놀라움"은 확률과 확률의 음의 이진 로그를 곱한 값입니다.
binary
symbol weight probability log surprise
A 2 0.4 -1.32 0.53
B 2 0.4 -1.32 0.53
C 1 0.2 -2.32 0.46
total 5 1.0 1.52
이진 로그의 음수는 (물론) 0과 1 (배타적) 사이의 값의 로그가 음수이기 때문에 사용됩니다.
다음은 정보 이론의 엔트로피 에 대한 훌륭한 대체 설명입니다 .
엔트로피는 예측과 관련된 불확실성 의 척도입니다 .
또한 엔트로피를 초기 예측을 한 후 결과를 얻는다면 얼마나 놀랐 는지 설명 할 수 있습니다 .
99 %의 시간 동안 머리를, 1 %의 시간 동안 꼬리를주는 구부러진 동전이 있다고 가정 해 봅시다. 꼬리를 얻을 확률은 1 % 밖에되지 않기 때문에 실제로 꼬리를 얻는다면 매우 놀랄 것입니다. 다른 한편으로, 우리가 이미 우위를 차지할 확률이 99 %이기 때문에 우위가 있다고해도 그리 놀라운 일은 아닙니다.
lets assume that we have a function called Surprise(x) that would give us the amount of surprise for each outcome; then we can average the amount of surprise on a probability distribution. This average amount of surprise could also be used as a measure for how uncertain we are. This uncertainty is called entropy.
Super SIMPLE definition
The word entropy can be defined in one sentence:
"The amount of information needed to describe a system."
Imagine for an example the expansion of the universe: From the beginning, all matter was collected in a small point before the big bang, so we could have described the system with "all matter is within one point." While today significantly more information is required to describe the system (the Universe, that is), one would need to describe all planetary positions, their movement, what's on them etc.. In terms of information theory, the definition also works: E.g: The more letters you add to a password (the system), the more information is needed to describe the password. Then you can measure it in different units, eg bits or characters, like "hello" = 5 characters entropy = 40 bits of entropy (if charsize is 8 bits).
From this also comes that the more information you have the more ways you can arrange that information in. If you have 40 bits there are 2^40 different ways they can be arranged. If we are talking passwords here then the more possible arrangements of the information (bits) the longer it is going to take cracking (with brute force or dictionary attacks).
In simpler words, Entropy defines randomness. It’s more like how unpredictable something is. In more technical words, “In computing, entropy is the randomness collected by an operating system or application for use in cryptography or other uses that require random data. This randomness is often collected from hardware sources, either pre-existing ones such as mouse movements or specially provided randomness generators.” as defined by wikipedia.
One can now easily conclude the meaning of entropy in respect to a file as the measurement of the how much disordered the bytes are in a file. There are various units used for defining entropy like nat, shannon or hartley. Well, most common unit used is Shannon. The range of values a file’s entropy must come in as per Shannon’s algorithm is 0 to 8. So, when the entropy value is zero, one can say the outcome is certain. On contrary, when the entropy value is 8, the outcome is most unpredictable it could be. The formula given by Shannon to measure randomness in outcome of events is:
Entropy = ∑ pi log(1/pi)
where i is the event with probability pi.
This equation will always result in between 0 to 8.
For more information, go through the link: https://www.talentcookie.com/2016/02/file-entropy-in-malware-analysis/
entropy refers to the extent where a software is reshaped occasionally basing on customer requirements hence the cost for reshaping it to meet customer reqrments becomes maximum.
Entropy is like a hash code for virus researchers as well. Less entropy you get, it would mean that it is likely encrypted or compressed code which could be potentially be a virus.
A standard binary would have a higher entropy than a compressed or encrypted one.
Entropy has many meanings typically in Computer Science. It depends on the context. In security entropy means how much randomality you place, for instance when you generate a private key many applications ask you to move the mouse around to generate entropy. This generates entropy by taking the "human" element of randomality and adds it to the hashing process of generating the key.
Now there is also a defnition for software engineering of entropy. This definition represents out of date code, or code that has had many developers writing it. Typically used in reference to when it is near time to refactor your software project. "The code for this project has an enourmous amount of entropy because many of the individuals who maintained it are not on the project currently".
Here is a third example usage that I remembered too. In the topic of simulated annealing (as far as computer science is concerned), entropy is described as how much decay has happened during the evaluation of the algorithm.
I guess to answer your question though, there is not a concrete definition of the word 'entropy' except for the ones that you can find in a dictionary. How computer science tends to apply that term depends on the context of the term being used and what it is being applied to.
It's easy to make a big deal out of entropy. To my mind it is a pretty simple and useful concept.
Basically it quantifies what, on average, you will learn from an event, like flipping a coin, taking a branch instruction, or indexing an array.
Like a comparison operation in the middle of a search algorithm has a certain probability P of taking one branch, and 1-P of taking the other.
Suppose P is 1/2, as it is in a binary search. Then if you take that branch, you know 1 bit more than you did before, because log(2/1), base 2, is 1. On the other hand, if you take the other branch you also learn 1 bit.
To get the average amount of information you will learn, multiply what you learn on the first branch times the probability you take that branch, plus what you learn on the second branch times the probability of that branch.
1/2 times 1 bit, plus 1/2 times 1 bit, is 1/2 bit plus 1/2 bit, or total 1 bit of entropy. That's what you can expect to learn on average from that decision.
On the other hand, suppose you are doing linear search in a table of 1024 entries.
On the first == test, the probability of YES is 1/1024, so the entropy of YES at that decision is
1/1024 times log(1024/1)
or 1/1024 * 10 = about 1/100 bit.
So if the answer is YES, you learn 10 bits, but the chance of that is about 1 in a thousand.
On the other hand, NO is much more likely. It's entropy is
1023/1024 * log(1024/1023)
or roughly 1 times roughly zero = about zero.
Add the two together, and on average you will learn about 1/100 of a bit on that decision.
That's why linear search is slow. The entropy (how much you can expect to learn) at each decision is too small, since you're going to have to learn 10 bits to find the entry in the table.
Entropy in computer science commonly refers to how random a string of bits is. The following question is about making that precise:
How do I compute the approximate entropy of a bit string?
간단히 말해서, 언어로 된 기호의 확률을 안다면, 언어로 된 기호의 평균 정보 내용을 계산할 수 있습니다.
또는
언어의 엔트로피는 언어에서 평균 기호의 정보 내용을 측정 한 것입니다.
공정한 동전을 고려하십시오.
두 개의 기호가 있으며 각각 확률이 1/2이므로 엔트로피는 다음과 같이 계산됩니다.
h =-(1 / 2 * log1 / 2 + 1 / 2 * log1 / 2) = 1
사람들이 엔트로피 wrt CS의 열역학적 정의를 오용한다고 들었습니다.
예를 들어 엔트로피는이 시스템에서 확실히 증가하고 있습니다.
그들이 의미하는 바는이 코드가 점점 더 나 빠지고 있다는 것입니다!
참고 URL : https://stackoverflow.com/questions/510412/what-is-the-computer-science-definition-of-entropy
'Nice programing' 카테고리의 다른 글
| Firebase 용 Cloud Functions-결제 계정이 구성되지 않음 (0) | 2020.11.24 |
|---|---|
| Log4Net : RollingFileAppender에 롤링 날짜로 최대 백업 파일 설정 (0) | 2020.11.24 |
| 회귀 모델에서 스크리닝 (다중) 공선 성 (0) | 2020.11.24 |
| 웹 서버로서의 Amazon EC2? (0) | 2020.11.24 |
| 파일이 유효한 UTF-8인지 확인하는 방법은 무엇입니까? (0) | 2020.11.24 |