Ентропија (теорија информација)

Two bits of entropy: In the case of two fair coin tosses, the information entropy in bits is the base-2 logarithm of the number of possible outcomes; with two coins there are four possible outcomes, and two bits of entropy. Generally, information entropy is the average amount of information conveyed by an event, when considering all possible outcomes.

У теорији информације, ентропија је мера неодређености придружена случајној променљивој. У овом контексту, обично се мисли на Шенонову ентропију, која квантификује очекивану вредност информације садржане у поруци, обично у јединицама као што су бити. Еквивалентно, Шенонова ентропија је мера просечног информационог садржаја који се пропушта када се не зна вредност случајне променљиве. Концепт је увео Клод Шенон у свом чувеном раду из 1948. године „Математичка теорија комуникација“.

Шенонова ентропија представља апсолутну границу најбоље могуће компресије без губитака било какве комуникације, под извесним ограничењима: ако третирамо поруке да су кодоване као низ независних случајних променљивих са истом расподелом, прва Шенонова теорема показује да, у граничном случају, средња дужина најкраће могуће репрезентације за кодовање порука у датом алфабету је њихова ентропија подељена са логаритмом броја симбола у циљном алфабету.

Једно бацање фер новчића носи ентропију од једног бита. Два бацања - два бита. Брзина ентропије за новчић је један бит по бацању. Међутим, ако новчић није фер, тада је неодређеност мања (ако бисмо морали да се кладимо на исход наредног покушаја, вероватно ћемо се кладити на чешћи резултат), па је и Шенонова ентропија мања. Математички, једно бацање новчића (фер или не) представља Бернулијев експеримент, а његова ентропија дата је бинарном ентропијском функцијом. Низ бацања новчића са две главе имаће нулту ентропију, јер су исходи потпуно предвидљиви. Брзина ентропије текста на енглеском је од 1 до 1,5 бита по слову, односно од 0,6 до 1,3 бита по слову, према проценама базираним на експериментима.

The measure of information entropy associated with each possible data value is the negative logarithm of the probability mass function for the value:

$S=-\sum _{i}P_{i}\log {P_{i}}$.

When the data source has a lower-probability value (i.e., when a low-probability event occurs), the event carries more "information" ("surprisal") than when the source data has a higher-probability value. The amount of information conveyed by each event defined in this way becomes a random variable whose expected value is the information entropy. Generally, entropy refers to disorder or uncertainty, and the definition of entropy used in information theory is directly analogous to the definition used in statistical thermodynamics. The concept of information entropy was introduced by Claude Shannon in his 1948 paper "A Mathematical Theory of Communication".

The basic model of a data communication system is composed of three elements, a source of data, a communication channel, and a receiver, and – as expressed by Shannon – the "fundamental problem of communication" is for the receiver to be able to identify what data was generated by the source, based on the signal it receives through the channel. The entropy provides an absolute limit on the shortest possible average length of a lossless compression encoding of the data produced by a source, and if the entropy of the source is less than the channel capacity of the communication channel, the data generated by the source can be reliably communicated to the receiver (at least in theory, possibly neglecting some practical considerations such as the complexity of the system needed to convey the data and the amount of time it may take for the data to be conveyed).

Information entropy is typically measured in bits (alternatively called "shannons") or sometimes in "natural units" (nats) or decimal digits (called "dits", "bans", or "hartleys"). The unit of the measurement depends on the base of the logarithm that is used to define the entropy.

The logarithm of the probability distribution is useful as a measure of entropy because it is additive for independent sources. For instance, the entropy of a fair coin toss is 1 bit, and the entropy of m tosses is m bits. In a straightforward representation, log₂(n) bits are needed to represent a variable that can take one of n values if n is a power of 2. If these values are equally probable, the entropy (in bits) is equal to this number. If one of the values is more probable to occur than the others, an observation that this value occurs is less informative than if some less common outcome had occurred. Conversely, rarer events provide more information when observed. Since observation of less probable events occurs more rarely, the net effect is that the entropy (thought of as average information) received from non-uniformly distributed data is always less than or equal to log₂(n). Entropy is zero when one outcome is certain to occur. The entropy quantifies these considerations when a probability distribution of the source data is known. The meaning of the events observed (the meaning of messages) does not matter in the definition of entropy. Entropy only takes into account the probability of observing a specific event, so the information it encapsulates is information about the underlying probability distribution, not the meaning of the events themselves.

Дефиниција

Шенон је дефинисао ентропију $H$ дискретног извора без меморије (дискретне случајне променљиве) $X$ над коначним алфабетом $Z=\{z_{1},z_{2},\dots ,z_{m}\}$ на следећи начин. Прво се додели свакој вероватноћи $p$ неког догађаја њена количина информације $I(p)=-\log _{2}p$. Тада је ентропија по симболу дефинисана као очекивана вредност (математичко очекивање) количине информација

$H_{1}=\sum _{z\in Z}p_{z}\cdot I(p_{z})=-\sum _{z\in Z}p_{z}\cdot \log _{2}p_{z}$,

Нека је $z\in Z$, тада је $p_{z}=P(X=z)$ вероватноћа да се догоди симбол $z$ из алфабета, или еквивалентно

$(1)\qquad H_{1}=-\sum _{i=1}^{m}p_{i}\cdot \log _{2}p_{i}$,

За граничну вредност $\lim _{p_{i}\rightarrow 0}p_{i}\cdot \log _{2}p_{i}$ се може показати да је нула. Према томе, сабирци са вероватноћом једнаком нули не доприносе укупном збиру (тј. ентропији).

Ентропија $H_{n}$ за речи $w$ дужине $n$ је дата са

$H_{n}=-\sum _{w\in Z^{n}}p_{w}\cdot \log _{2}p_{w}$,

где је $p_{w}=P(X=w)$ вероватноћа да ће се догодити реч $w$. Ентропија $H$ је тада гранична вредност:

$(2)\qquad H=\lim _{n\to \infty }{\frac {H_{n}}{n}}$.

Ако су симболи статистички независни, тада $H_{n}=nH_{1}$ за свако $n$, као и $H=H_{1}$.

Интерпретација

Ентропија представља меру просечног информационог садржаја по симболу извора који представља неки систем или информациону секвенцу. У теорији информација, као мера за количину информације у некој поруци може послужити колико се променила вероватноћа догађаја под утицајем те поруке. На пример, ако за време лета временска прогноза за сутрашњи дан најави 30° C, то нам неће донети много информација, јер не садржи ништа неочекивано. Међутим, ако се иста таква прогноза догоди зими, то представља потпуно неочекивану вест и самим тим садржи много информација. Под информацијом се може сматрати и мера уклоњене несигурности. Што се више симбола прими од извора, добијамо више информација и опада несигурност око онога шта је могло бити послато.

Дефиниција информационог садржаја се може на следећи начин описати: ако се деси догађај чија је вероватноћа $p_{i}$, тада је кроз то изабран један конкретан догађај из хипотетичког скупа од ${\tfrac {1}{p_{i}}}$ једнако вероватних догађаја. Да би се ови догађаји међусобно разликовали, потребно им је доделити $\log _{2}\left({\tfrac {1}{p_{i}}}\right)=-\log _{2}(p_{i})$ бита. Ова вредност представља количину информације једног одређеног догађаја у битима. Када се количина информације сваког догађаја пондерише са вероватноћом истог догађаја, и када се саберу (тј. пронађе се математичко очекивање количине информације), добијамо средњу или очекивану количину информације по симболу.

Јединица Шенон дефинише количину информације коју садржи порука о догађају са вероватноћом $p=0,5$. На пример, саопштење о томе да је метални новчић пао на одређену страну доноси информацију од 1 Шенона. Или, ако на пријемној страни бинарног телекомуникационог система, чији је сигнал састављен од биполарних импулса константне амплитуде, меримо поларност долазећих импулса, и ако је вероватноћа појављивања позитивних и негативних амплитуда једнака, онда сваки импулс носи информацију од 1 Шенона. Међутим, ако вероватноће појављивања позитивних и негативних амплитуда нису једнаке, онда један импулс доноси пријемнику неку другу количину информација која није 1 Шенон. Треба разликовати појам бинарни дигит, скраћено бит, од појма Шенон. Бит је само носилац информације и физички је представљен импулсом који може да има два стања. У зависности од вероватноће појављивања стања, бит може да доноси пријемнику већу или мању количину информација. Само кад су вероватноће појављивања два стања код бита једнаке, онда бит носи количину информације од 1 Шенона.

Види још

• Ентропија

Литература

• Arndt, C. (2004), Information Measures: Information and its Description in Science and Engineering, Springer, ISBN 978-3-540-40855-0
• Cover, T. M., Thomas, J. A. (2006), Elements of information theory, 2nd Edition. Wiley-Interscience. ISBN 0-471-24195-4.
• Gray, R. M. (2011), Entropy and Information Theory, Springer.
• MacKay, David J. C.. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
• Martin, Nathaniel F.G. & England, James W. (2011). Mathematical Theory of Entropy. Cambridge University Press. ISBN 978-0-521-17738-2. CS1 одржавање: Употреба параметра аутори (веза)
• Shannon, C.E., Weaver, W. (1949) The Mathematical Theory of Communication, Univ of Illinois Press. ISBN 0-252-72548-4
• Stone, J. V. (2014), Chapter 1 of Information Theory: A Tutorial Introduction, University of Sheffield, England. ISBN 978-0956372857.

Спољашње везе

• Hazewinkel Michiel, ур. (2001). „Entropy”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104. 
• Introduction to entropy and information on Principia Cybernetica Web
• Entropy an interdisciplinary journal on all aspects of the entropy concept. Open access.
• Description of information entropy from "Tools for Thought" by Howard Rheingold
• A java applet representing Shannon's Experiment to Calculate the Entropy of English
• Slides on information gain and entropy
• An Intuitive Guide to the Concept of Entropy Arising in Various Sectors of Science – a wikibook on the interpretation of the concept of entropy.
• Network Event Detection With Entropy Measures, Dr. Raimund Eimann, University of Auckland, PDF; 5993 kB – a PhD thesis demonstrating how entropy measures may be used in network anomaly detection.
• Rosetta Code repository of implementations of Shannon entropy in different programming languages.
• "Information Theory for Intelligent People". Short introduction to the axioms of information theory, entropy, mutual information, Kullback–Liebler divergence, and Jensen–Shannon distance.
• Online tool for calculating entropy (plain text)
• Online tool for calculating entropy (binary)