{"id":125,"date":"2018-08-24T11:07:25","date_gmt":"2018-08-24T11:07:25","guid":{"rendered":"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=125"},"modified":"2019-01-02T06:22:28","modified_gmt":"2019-01-02T06:22:28","slug":"information-theory","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/chapter\/information-theory\/","title":{"rendered":"Information Theory"},"content":{"raw":"<div><span style=\"float: right\"><a href=\"https:\/\/youtu.be\/JRug4KC07S4\" target=\"_blank\" rel=\"noopener\"><img src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a>\r\n<\/span><\/div>\r\n<div>\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Welcome to the e-PG Pathshala Lecture Series on Machine Learning. In this module we will discuss some fundamental aspects of Information Theory which we will later on use in the discussion of many machine learning techniques.<\/p>\r\n&nbsp;\r\n\r\n<strong>Learning Objectives:<\/strong>\r\n\r\n&nbsp;\r\n\r\nThe learning objectives of this module are as follows:\r\n\r\n&nbsp;\r\n\r\n\u2022\u00a0 To understand the principles and practice of Information Theory\r\n\r\n\u2022\u00a0 To know the interpretation of probability in real life\r\n\r\n\u2022\u00a0 To acquire knowledge about information and entropy\r\n\r\n&nbsp;\r\n\r\n<strong>9.1 Information Theory -Quotes about Shannon\u2019s Concepts<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Information theory is a branch of science that deals with the analysis of a communications system for efficient and reliable transmission of information. Before we start discussing Information theory we need to know some famous quotes about Claude Shannon's ideas considered as the developer of this theory. He came up with the extraordinary idea now known as the mathematical theory of communication which was published in the Bell System Technical Journal in 1948. This landmark paper was the beginning of the branch of information theory. He proposed that the basic principles of binary or digital information can be related to fundamental physical laws. He was instrumental in shaping our digital era. Today, Shannon\u2019s theory remains the guiding foundation for the most modern, faster, more energy efficient, and more robust communication systems So<\/p>\r\n\r\n<ul>\r\n \t<li style=\"text-align: justify\">\u201dWhat is information? Sidestepping questions about meaning, Shannon showed that it is a measurable commodity\u201d.<\/li>\r\n \t<li style=\"text-align: justify\">\u201dToday, Shannon\u2019s insight help shape virtually all systems that store, process, or transmit information in digital form, from compact discs to computers, from facsimile machines to deep space probes\u201d.<\/li>\r\n \t<li style=\"text-align: justify\"><span style=\"font-size: 1em\">\u201dInformation theory has also infilitrated fields outside communications, including linguistics, psychology, economics, biology, even the arts\u201d.<\/span><\/li>\r\n<\/ul>\r\n<\/div>\r\n&nbsp;\r\n\r\n<strong>9.2 Shannon\u2019s Channel of Communication<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The communication model considered for our purpose consists of a source that generates digital information. This information needs to be sent from the source to the receiver through a channel. The channel can be noiseless where the channel transmits symbols without causing any errors. In order to use the redundant characteristics of the information output by the source and reduce the length of the transmission, data compression also called as source coding is carried out. In this case the information needs to be decompressed at the receiver end. However sometimes the channel can be noisy which causes errors in the received symbols at the destination. To reduce the errors incurred due to noise, channel coding is carried out.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-126 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-75.png\" alt=\"\" width=\"613\" height=\"304\" \/>\r\n<p style=\"text-align: justify\">Figure 9.1 shows Shannon\u2019s model of a communication channel. In this context, channel is anything that transmits or stores information such as radio link, cable, disk, CD or even a piece of paper. Considering Figure 9.1, <strong>C<\/strong> is the channel capacity, source is any source of information where <strong>H<\/strong> is considered as the information content of the source, source coder changes the information content into an efficient representation (that is data compression) where <strong>R<\/strong> is the rate of the source coder. Channel coder again changes the compressed information into an efficient representation for transmission (that is error control coding). This compressed, error coded information is then transmitted through channel C. On receiving the information it is decoded to recover from channel distortion. Now the source decoder uncompresses the information and finaaly the receiver gets the information.<\/p>\r\n&nbsp;\r\n\r\n<strong>9.2.1 Fundamental Theorems<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Maximizing the amount of information that can be transmitted over an imperfect communication channel can be based on data compression (entropy) and transmission rate (channel capacity).<\/p>\r\n&nbsp;\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Using this basic communication model, Shannon came up with two theorems, today known as Shannon\u2019s theorems.<\/p>\r\n\r\n<ul>\r\n \t<li style=\"text-align: justify\"><strong>Shannon 1<\/strong>: Error-free transmission is possible if R\u00b3H and C\u00b3R.<\/li>\r\n \t<li style=\"text-align: justify\"><strong>Shannon 2<\/strong>: Source coding and channel coding can be optimized <em>independently<\/em>, where<em> binary symbols <\/em>can be used as intermediate format assuming that the delays are arbitrarily long.<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\n<strong>9.3<\/strong>\u00a0 <strong>Information Source<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The characteristics of any information source can be specified in terms of the number of symbols n, say S1,S2,\u2026.,Sn, and the probability of occurrence of each of these symbols, P(S1), P(S2), \u2026, P(Sn) and finally the correlation between successive symbols. A stream of symbols from the sender to the receiver is generally called a message. If a source emits signals which are independent then the source is called a memoryless source.<\/p>\r\n&nbsp;\r\n\r\n<strong>9.3.1 Stochastic sources<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Let us assume that a source outputs symbols X1, X2, .... and that each symbol takes its value from an alphabet A = (a1, a2, \u2026). The model: P(X1,\u2026,XN) will be known for all combinations.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-127 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-76.png\" alt=\"\" width=\"378\" height=\"139\" \/>\r\n<div>\r\n\r\n&nbsp;\r\n\r\nSome examples are given below:\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Example 1: A text which is a sequence of symbols each taking its value from the alphabet A = (a,.....z, A, .........Z, 1,2,3....9, !,?,....)<\/p>\r\n<p style=\"text-align: justify\">Example 2: A (digitized) grayscale <em>image<\/em> is a sequence of symbols each taking its value from the alphabet A = (0,1) or A = (0, \u2026, 255).<\/p>\r\n\r\n<\/div>\r\n&nbsp;\r\n<p style=\"text-align: justify\">For such stochastic sources there are two special cases<\/p>\r\n\r\n<ul>\r\n \t<li style=\"text-align: justify\">The Memoryless Source where the value of each symbol is independent of the value of the previous symbols in the sequence.<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\nP(S1, S2, \u2026, Sn) = P(S1) . P(S2) . \u2026 .P(Sn)\r\n<ul>\r\n \t<li style=\"text-align: justify\">The Markov Source where the value of each each symbol depends only on the value of the previous one in a sequence<\/li>\r\n<\/ul>\r\n&nbsp;\r\n<p style=\"text-align: justify\">P(S1, S2, \u2026, Sn) = P(S1) .P(S2|S1) .P(S3|S2) . \u2026 . P(Sn|Sn-1) We will discuss the Markov source in detail.<\/p>\r\n&nbsp;\r\n\r\n<strong>9.3.2 The Markov Source<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">In the case of a Markov source, a symbol depends only on the previous symbol, so the source can be modelled by a state diagram. Now let us assume we have a source with an alphabet of size 3 namely A = (a,b,c).<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-128 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-77.png\" alt=\"\" width=\"680\" height=\"463\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Figure 9.4(a) shows the probabilities of transitions from a to a, b and c respectively. Note that since there is no transition from a to c the corresponding transition probability is 0. Now let us assume we have gone from state a to b. Figure 9.4(b) shows the probabilities of transitions from b to a, b, and c. In this\u00a0<span style=\"text-align: initial;font-size: 1em\">case, from b, the only transition possible is to c. That is, if we know that <\/span><em style=\"text-align: initial;font-size: 1em\">X<\/em><em style=\"text-align: initial;font-size: 1em\">k+1<\/em><span style=\"text-align: initial;font-size: 1em\"> = <\/span><em style=\"text-align: initial;font-size: 1em\">b, <\/em><span style=\"text-align: initial;font-size: 1em\">with a probabbility of 0.7, given<\/span><em style=\"text-align: initial;font-size: 1em\"> X<\/em><em style=\"text-align: initial;font-size: 1em\">k<\/em><span style=\"text-align: initial;font-size: 1em\"> =<\/span><em style=\"text-align: initial;font-size: 1em\"> a; <\/em><span style=\"text-align: initial;font-size: 1em\">we also know that<\/span><em style=\"text-align: initial;font-size: 1em\"> X<\/em><em style=\"text-align: initial;font-size: 1em\">k+2<\/em><span style=\"text-align: initial;font-size: 1em\"> can only be c.<\/span><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><span style=\"text-align: initial;font-size: 1em\">In a Markov source if all the states can be reached, the <\/span><em style=\"text-align: initial;font-size: 1em\">stationary probabilities<\/em><span style=\"text-align: initial;font-size: 1em\"> for the states can be calculated from the given transition probabilities. Stationary probabilities are the probabilities wi = <\/span><em style=\"text-align: initial;font-size: 1em\">P<\/em><span style=\"text-align: initial;font-size: 1em\">(<\/span><em style=\"text-align: initial;font-size: 1em\">X<\/em><em style=\"text-align: initial;font-size: 1em\">k<\/em> <em style=\"text-align: initial;font-size: 1em\">= a<\/em><em style=\"text-align: initial;font-size: 1em\">i<\/em><span style=\"text-align: initial;font-size: 1em\">) for any <\/span><em style=\"text-align: initial;font-size: 1em\">k<\/em><span style=\"text-align: initial;font-size: 1em\"> when <\/span><em style=\"text-align: initial;font-size: 1em\">X<\/em><em style=\"text-align: initial;font-size: 1em\">k<\/em><span style=\"text-align: initial;font-size: 1em\">-1, <\/span><em style=\"text-align: initial;font-size: 1em\">X<\/em><em style=\"text-align: initial;font-size: 1em\">k<\/em><span style=\"text-align: initial;font-size: 1em\">-2, \u2026 are not given.<\/span><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><span style=\"text-align: initial;font-size: 1em\">Markov models can be used to represent sources which have dependencies that go back more than one step by using a state diagram with several symbols in each state.<\/span><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong style=\"text-align: initial;font-size: 1em\">9.3.3 Stochastic Sources - Analysis and Synthesis<\/strong><\/p>\r\n\r\n<div>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Stochastic models can be used for <em>analysing<\/em> a source. For this purpose we need to find a model that represents the real-world source in an effective manner, and then analyse the model instead of the real world. Stochastic models can also be used for <em>synthesizing<\/em> a source. In this case we can generate random numbers sequentially to simulate the source of the Markov model.<\/p>\r\n&nbsp;\r\n\r\n<strong>Measuring Information<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Before we discuss entropy associated with information, let us understand how to measure the information contained in a message. In other words we need to know the amount of information a message carries from the sender to the receiver.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Example 1 -Imagine a person sitting in a room. Looking out through the window, she can clearly see that the sun is shining. If at this moment she receives a call from a neighbor saying \u201cIt is now daytime\u201d, does this message contain any information?<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Example 2 -A person has bought a lottery ticket. A friend calls to tell her that she has won first prize. Does this message contain any information?<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">As you can conclude, in example 1 the message carries no information while the message in example 2 carries information.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Now let us assume a binary memoryless source, for example the flip of a coin. The question is the amount of information obtained when on flipping the coin we get heads.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">If the coin is a fair coin, i.e., P(heads) = P (tails) = 0.5, as is normally the case the amount of information obtained is 1 bit. However if we already have the information that it is heads, i.e., P(heads) = 1, then the amount of information obtained is zero. The amount of information is greater than 0 and less than 1 if we have an unfair coin.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><span style=\"text-align: initial;font-size: 1em\">The information content of a message is inversely proportional to the probability of occurrence of that message. If a message is very probable, it does not contain any information. If it is very improbable, it contains a lot of information<\/span><\/p>\r\n\r\n<\/div>\r\n&nbsp;\r\n\r\n<strong>9.4.1 Self Information<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Now let us look at how Shannon viewed the information conveyed by a symbol. Assume a memoryless source with alphabet A = (<em>a<\/em>1<em>, \u2026, a<\/em><em>n<\/em>) and symbol probabilities (<em>p<\/em>1<em>, \u2026, p<\/em><em>n<\/em>). Then an important question is to find out the amount of information obtained by knowing that the next symbol is <em>a<\/em><em>i..<\/em>Shannon associated a concept called self information to find out amount of information conveyed by\u00a0<em>a<\/em><em>i.<\/em><\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-129 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-78.png\" alt=\"\" width=\"642\" height=\"511\" \/>\r\n\r\n<strong>9.4.2 Entropy<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">In order to find information about the symbols in a sequence we can <em>average<\/em> <em>over the probability over all the symbols<\/em>, given as:<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-130 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-79.png\" alt=\"\" width=\"644\" height=\"490\" \/>\r\n\r\n<img class=\"size-full wp-image-131 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-80.png\" alt=\"\" width=\"235\" height=\"125\" \/>\r\n<div>\r\n\r\n&nbsp;\r\n\r\n<strong>9.4.2.1<\/strong>\u00a0\u00a0<strong>Entropy: Three properties<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Entropy is a measurement of information. It has three basic properties. It can be shown that 0 \u00a3 <em>H<\/em> \u00a3 <em>log N<\/em>. Maximum entropy (<em>H = log N<\/em>) is reached when all symbols are equiprobable, i.e., <em>p<\/em><em>i<\/em> <em>=<\/em> 1<em>\/N<\/em>. The difference between maximum entropy and actual entropy <em>log N<\/em> <em>\u2013<\/em> <em>H<\/em> is called the <em>redundancy<\/em> of the source.<\/p>\r\n\r\n<\/div>\r\n&nbsp;\r\n\r\n<strong>9.5 Entropy for Memory and Markov Sources<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>Entropy for Memory Source<\/strong>\r\n\r\n&nbsp;\r\n\r\nAssume a block of source symbols (<em>X<\/em>1, \u2026, <em>X<\/em><em>n<\/em>) , we can define the <em>block<\/em> <em>entropy<\/em>:\r\n\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-132 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-81.png\" alt=\"\" width=\"555\" height=\"507\" \/>\r\n\r\n<strong>The Run-length Source<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Certain sources generate long <em>runs<\/em> or <em>bursts<\/em> of equal symbols. Let us look at an example<\/p>\r\n&nbsp;\r\n\r\nExample:\r\n\r\n<img class=\"size-full wp-image-133 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-82.png\" alt=\"\" width=\"453\" height=\"161\" \/>\r\n\r\n<strong>9.6 The Source Coding Theorem<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">As we have already discussed entropy is the smallest number of bits allowing error-free representation of the source. Shannon shows that source coding algorithms exist that have a unique average representation length that approaches the entropy of the source and we cannot reduce beyond this length. To understand this aspect let us consider typical sequences.<\/p>\r\n&nbsp;\r\n\r\n<strong>Typical Sequences<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">We assume a <em>long<\/em> sequence from a binary memoryless source with <em>P<\/em>(1) = <em>p<\/em>. Among n bits, there will be approximately <em>w = n .p<\/em> ones. Thus, there is <em>M<\/em> = (<em>n<\/em> <em>choose w<\/em>) such<em> typical sequences<\/em>!<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><em>Only these sequences are interesting. <\/em>All other sequences will appear with smaller probability as <em>n becomes larger<\/em>. Now we need to find out how many sequences are actually typical sequences.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-134 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-83.png\" alt=\"\" width=\"482\" height=\"351\" \/>\r\n<p style=\"text-align: justify\">bits per symbol!<\/p>\r\n<p style=\"text-align: justify\">Deriving from equation 1 by substituting w=n.p we get<\/p>\r\n<p style=\"text-align: justify\">-p log p \u2013 (1-p) log (1-p) = h(p) =H(X).<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Thus we can conclude that we need <em>H<\/em>(<em>X<\/em>) bits per symbol to code any typical sequence.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>Example \u2013Sequence<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Consider the following sequence:<\/p>\r\n<p style=\"text-align: justify\">1 2 1 2 4 4 1 2 4 4 4 4 4 4 1 2 4 4 4 4 4 4 Obtaining the probability from the sequence<\/p>\r\n<p style=\"text-align: justify\">1 four times (4\/22), 2 four times (4\/22), and 4 fourteen times (14\/22)<\/p>\r\n<img class=\"size-full wp-image-135 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-84.png\" alt=\"\" width=\"552\" height=\"275\" \/>\r\n<p style=\"text-align: justify\">The entropy H = 0.447 + 0.447 + 0.415 = 1.309 bits<\/p>\r\n<p style=\"text-align: justify\">There are 22 symbols, we need 22 * 1.309 = 28.798 (29) bits to transmit<\/p>\r\n<p style=\"text-align: justify\">Now we can consider the symbols as blocks of 12, 44 (now total symbols-11) - 12 appears 4\/11 and 44 appears 7\/11<\/p>\r\n<img class=\"size-full wp-image-136 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-85.png\" alt=\"\" width=\"414\" height=\"148\" \/>\r\n<p style=\"text-align: justify\">There are 11 symbols, we need 11 * 0.945 = 10.395 (11) bits to transmit information \u2013 that is we might be able to find patterns with less entropy<\/p>\r\n&nbsp;\r\n\r\n<strong>9.7 Using information theory<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>Entropy measures the amount of uncertainty in a probability distribution:<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Consider tossing a biased coin. If you toss the coin VERY often, the frequency of heads is, say, p, and hence the frequency of tails is 1-p. (fair coin p=0.5). Uncertainty in any actual outcome is given by entropy: Uncertainty is zero if p=0 \/ 1 and maximal if we have p=0.5.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-137 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-86.png\" alt=\"\" width=\"578\" height=\"396\" \/>\r\n<p style=\"text-align: justify\">Information theory can be used to determine how much information we gain if we disclose the value of some attribute? (for example in a decision tree). Entropy can be used as a measure of the quality of our models and as a measure of how different two probability distributions are. We will discuss these aspects later.<\/p>\r\n&nbsp;\r\n\r\n<strong>Summary<\/strong>\r\n<ul>\r\n \t<li style=\"text-align: justify\">Explained the model of communication<\/li>\r\n \t<li style=\"text-align: justify\">Outlined the sources of information<\/li>\r\n \t<li style=\"text-align: justify\">Explained entropy<\/li>\r\n \t<li style=\"text-align: justify\">Discussed source and Markov source<\/li>\r\n \t<li style=\"text-align: justify\">Discussed source and Markov source<\/li>\r\n<\/ul>\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><strong>you can view video on Information Theory<\/strong><\/td>\r\n<td><a href=\"https:\/\/youtu.be\/JRug4KC07S4\" target=\"_blank\" rel=\"noopener\"><img class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n\r\n<strong>Web Links<\/strong>\r\n<ul>\r\n \t<li>http:\/\/users.ecs.soton.ac.uk\/sqc\/EL334N\/InfThe-L3.pdf<\/li>\r\n \t<li>http:\/\/www.fi.muni.cz\/usr\/staudek\/infteo\/info-lec.pdf<\/li>\r\n \t<li>http:\/\/140.113.144.123\/lecture%20notes%20for%20channel%20capacity08.pdf<\/li>\r\n \t<li>http:\/\/www.commsys.isy.liu.se\/ITWC\/Lecture1.pdf<\/li>\r\n \t<li>http:\/\/www.icg.isy.liu.se\/courses\/tsbk01\/material\/slides\/2_BasicInformationTheor y.pps<\/li>\r\n \t<li>http:\/\/www.myoops.org\/cocw\/mit\/NR\/rdonlyres\/Electrical-Engineering-and-Computer-Science\/6-450Principles-of-Digital-Communication--- IFall2002\/7BFBEC46-0F71-48A6-8D2A-EA73F0C0BD03\/0\/L502.pdf<\/li>\r\n \t<li>http:\/\/www.greentouch.org\/?page=shannons-law-explained<\/li>\r\n \t<li>https:\/\/courses.cs.washington.edu\/courses\/cse533\/06au\/lecnotes\/lecture3.pdf<\/li>\r\n \t<li>http:\/\/www.greentouch.org\/index.php?page=shannons-law-explained<\/li>\r\n<\/ul>","rendered":"<div><span style=\"float: right\"><a href=\"https:\/\/youtu.be\/JRug4KC07S4\" target=\"_blank\" rel=\"noopener\"><img decoding=\"async\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a><br \/>\n<\/span><\/div>\n<div>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Welcome to the e-PG Pathshala Lecture Series on Machine Learning. In this module we will discuss some fundamental aspects of Information Theory which we will later on use in the discussion of many machine learning techniques.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Learning Objectives:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>The learning objectives of this module are as follows:<\/p>\n<p>&nbsp;<\/p>\n<p>\u2022\u00a0 To understand the principles and practice of Information Theory<\/p>\n<p>\u2022\u00a0 To know the interpretation of probability in real life<\/p>\n<p>\u2022\u00a0 To acquire knowledge about information and entropy<\/p>\n<p>&nbsp;<\/p>\n<p><strong>9.1 Information Theory -Quotes about Shannon\u2019s Concepts<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Information theory is a branch of science that deals with the analysis of a communications system for efficient and reliable transmission of information. Before we start discussing Information theory we need to know some famous quotes about Claude Shannon&#8217;s ideas considered as the developer of this theory. He came up with the extraordinary idea now known as the mathematical theory of communication which was published in the Bell System Technical Journal in 1948. This landmark paper was the beginning of the branch of information theory. He proposed that the basic principles of binary or digital information can be related to fundamental physical laws. He was instrumental in shaping our digital era. Today, Shannon\u2019s theory remains the guiding foundation for the most modern, faster, more energy efficient, and more robust communication systems So<\/p>\n<ul>\n<li style=\"text-align: justify\">\u201dWhat is information? Sidestepping questions about meaning, Shannon showed that it is a measurable commodity\u201d.<\/li>\n<li style=\"text-align: justify\">\u201dToday, Shannon\u2019s insight help shape virtually all systems that store, process, or transmit information in digital form, from compact discs to computers, from facsimile machines to deep space probes\u201d.<\/li>\n<li style=\"text-align: justify\"><span style=\"font-size: 1em\">\u201dInformation theory has also infilitrated fields outside communications, including linguistics, psychology, economics, biology, even the arts\u201d.<\/span><\/li>\n<\/ul>\n<\/div>\n<p>&nbsp;<\/p>\n<p><strong>9.2 Shannon\u2019s Channel of Communication<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The communication model considered for our purpose consists of a source that generates digital information. This information needs to be sent from the source to the receiver through a channel. The channel can be noiseless where the channel transmits symbols without causing any errors. In order to use the redundant characteristics of the information output by the source and reduce the length of the transmission, data compression also called as source coding is carried out. In this case the information needs to be decompressed at the receiver end. However sometimes the channel can be noisy which causes errors in the received symbols at the destination. To reduce the errors incurred due to noise, channel coding is carried out.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-126 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-75.png\" alt=\"\" width=\"613\" height=\"304\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-75.png 613w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-75-300x149.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-75-65x32.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-75-225x112.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-75-350x174.png 350w\" sizes=\"auto, (max-width: 613px) 100vw, 613px\" \/><\/p>\n<p style=\"text-align: justify\">Figure 9.1 shows Shannon\u2019s model of a communication channel. In this context, channel is anything that transmits or stores information such as radio link, cable, disk, CD or even a piece of paper. Considering Figure 9.1, <strong>C<\/strong> is the channel capacity, source is any source of information where <strong>H<\/strong> is considered as the information content of the source, source coder changes the information content into an efficient representation (that is data compression) where <strong>R<\/strong> is the rate of the source coder. Channel coder again changes the compressed information into an efficient representation for transmission (that is error control coding). This compressed, error coded information is then transmitted through channel C. On receiving the information it is decoded to recover from channel distortion. Now the source decoder uncompresses the information and finaaly the receiver gets the information.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>9.2.1 Fundamental Theorems<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Maximizing the amount of information that can be transmitted over an imperfect communication channel can be based on data compression (entropy) and transmission rate (channel capacity).<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Using this basic communication model, Shannon came up with two theorems, today known as Shannon\u2019s theorems.<\/p>\n<ul>\n<li style=\"text-align: justify\"><strong>Shannon 1<\/strong>: Error-free transmission is possible if R\u00b3H and C\u00b3R.<\/li>\n<li style=\"text-align: justify\"><strong>Shannon 2<\/strong>: Source coding and channel coding can be optimized <em>independently<\/em>, where<em> binary symbols <\/em>can be used as intermediate format assuming that the delays are arbitrarily long.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p><strong>9.3<\/strong>\u00a0 <strong>Information Source<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The characteristics of any information source can be specified in terms of the number of symbols n, say S1,S2,\u2026.,Sn, and the probability of occurrence of each of these symbols, P(S1), P(S2), \u2026, P(Sn) and finally the correlation between successive symbols. A stream of symbols from the sender to the receiver is generally called a message. If a source emits signals which are independent then the source is called a memoryless source.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>9.3.1 Stochastic sources<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Let us assume that a source outputs symbols X1, X2, &#8230;. and that each symbol takes its value from an alphabet A = (a1, a2, \u2026). The model: P(X1,\u2026,XN) will be known for all combinations.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-127 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-76.png\" alt=\"\" width=\"378\" height=\"139\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-76.png 378w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-76-300x110.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-76-65x24.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-76-225x83.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-76-350x129.png 350w\" sizes=\"auto, (max-width: 378px) 100vw, 378px\" \/><\/p>\n<div>\n<p>&nbsp;<\/p>\n<p>Some examples are given below:<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Example 1: A text which is a sequence of symbols each taking its value from the alphabet A = (a,&#8230;..z, A, &#8230;&#8230;&#8230;Z, 1,2,3&#8230;.9, !,?,&#8230;.)<\/p>\n<p style=\"text-align: justify\">Example 2: A (digitized) grayscale <em>image<\/em> is a sequence of symbols each taking its value from the alphabet A = (0,1) or A = (0, \u2026, 255).<\/p>\n<\/div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">For such stochastic sources there are two special cases<\/p>\n<ul>\n<li style=\"text-align: justify\">The Memoryless Source where the value of each symbol is independent of the value of the previous symbols in the sequence.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>P(S1, S2, \u2026, Sn) = P(S1) . P(S2) . \u2026 .P(Sn)<\/p>\n<ul>\n<li style=\"text-align: justify\">The Markov Source where the value of each each symbol depends only on the value of the previous one in a sequence<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">P(S1, S2, \u2026, Sn) = P(S1) .P(S2|S1) .P(S3|S2) . \u2026 . P(Sn|Sn-1) We will discuss the Markov source in detail.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>9.3.2 The Markov Source<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In the case of a Markov source, a symbol depends only on the previous symbol, so the source can be modelled by a state diagram. Now let us assume we have a source with an alphabet of size 3 namely A = (a,b,c).<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-128 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-77.png\" alt=\"\" width=\"680\" height=\"463\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-77.png 680w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-77-300x204.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-77-65x44.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-77-225x153.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-77-350x238.png 350w\" sizes=\"auto, (max-width: 680px) 100vw, 680px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Figure 9.4(a) shows the probabilities of transitions from a to a, b and c respectively. Note that since there is no transition from a to c the corresponding transition probability is 0. Now let us assume we have gone from state a to b. Figure 9.4(b) shows the probabilities of transitions from b to a, b, and c. In this\u00a0<span style=\"text-align: initial;font-size: 1em\">case, from b, the only transition possible is to c. That is, if we know that <\/span><em style=\"text-align: initial;font-size: 1em\">X<\/em><em style=\"text-align: initial;font-size: 1em\">k+1<\/em><span style=\"text-align: initial;font-size: 1em\"> = <\/span><em style=\"text-align: initial;font-size: 1em\">b, <\/em><span style=\"text-align: initial;font-size: 1em\">with a probabbility of 0.7, given<\/span><em style=\"text-align: initial;font-size: 1em\"> X<\/em><em style=\"text-align: initial;font-size: 1em\">k<\/em><span style=\"text-align: initial;font-size: 1em\"> =<\/span><em style=\"text-align: initial;font-size: 1em\"> a; <\/em><span style=\"text-align: initial;font-size: 1em\">we also know that<\/span><em style=\"text-align: initial;font-size: 1em\"> X<\/em><em style=\"text-align: initial;font-size: 1em\">k+2<\/em><span style=\"text-align: initial;font-size: 1em\"> can only be c.<\/span><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><span style=\"text-align: initial;font-size: 1em\">In a Markov source if all the states can be reached, the <\/span><em style=\"text-align: initial;font-size: 1em\">stationary probabilities<\/em><span style=\"text-align: initial;font-size: 1em\"> for the states can be calculated from the given transition probabilities. Stationary probabilities are the probabilities wi = <\/span><em style=\"text-align: initial;font-size: 1em\">P<\/em><span style=\"text-align: initial;font-size: 1em\">(<\/span><em style=\"text-align: initial;font-size: 1em\">X<\/em><em style=\"text-align: initial;font-size: 1em\">k<\/em> <em style=\"text-align: initial;font-size: 1em\">= a<\/em><em style=\"text-align: initial;font-size: 1em\">i<\/em><span style=\"text-align: initial;font-size: 1em\">) for any <\/span><em style=\"text-align: initial;font-size: 1em\">k<\/em><span style=\"text-align: initial;font-size: 1em\"> when <\/span><em style=\"text-align: initial;font-size: 1em\">X<\/em><em style=\"text-align: initial;font-size: 1em\">k<\/em><span style=\"text-align: initial;font-size: 1em\">-1, <\/span><em style=\"text-align: initial;font-size: 1em\">X<\/em><em style=\"text-align: initial;font-size: 1em\">k<\/em><span style=\"text-align: initial;font-size: 1em\">-2, \u2026 are not given.<\/span><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><span style=\"text-align: initial;font-size: 1em\">Markov models can be used to represent sources which have dependencies that go back more than one step by using a state diagram with several symbols in each state.<\/span><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong style=\"text-align: initial;font-size: 1em\">9.3.3 Stochastic Sources &#8211; Analysis and Synthesis<\/strong><\/p>\n<div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Stochastic models can be used for <em>analysing<\/em> a source. For this purpose we need to find a model that represents the real-world source in an effective manner, and then analyse the model instead of the real world. Stochastic models can also be used for <em>synthesizing<\/em> a source. In this case we can generate random numbers sequentially to simulate the source of the Markov model.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Measuring Information<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Before we discuss entropy associated with information, let us understand how to measure the information contained in a message. In other words we need to know the amount of information a message carries from the sender to the receiver.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Example 1 -Imagine a person sitting in a room. Looking out through the window, she can clearly see that the sun is shining. If at this moment she receives a call from a neighbor saying \u201cIt is now daytime\u201d, does this message contain any information?<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Example 2 -A person has bought a lottery ticket. A friend calls to tell her that she has won first prize. Does this message contain any information?<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">As you can conclude, in example 1 the message carries no information while the message in example 2 carries information.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Now let us assume a binary memoryless source, for example the flip of a coin. The question is the amount of information obtained when on flipping the coin we get heads.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">If the coin is a fair coin, i.e., P(heads) = P (tails) = 0.5, as is normally the case the amount of information obtained is 1 bit. However if we already have the information that it is heads, i.e., P(heads) = 1, then the amount of information obtained is zero. The amount of information is greater than 0 and less than 1 if we have an unfair coin.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><span style=\"text-align: initial;font-size: 1em\">The information content of a message is inversely proportional to the probability of occurrence of that message. If a message is very probable, it does not contain any information. If it is very improbable, it contains a lot of information<\/span><\/p>\n<\/div>\n<p>&nbsp;<\/p>\n<p><strong>9.4.1 Self Information<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Now let us look at how Shannon viewed the information conveyed by a symbol. Assume a memoryless source with alphabet A = (<em>a<\/em>1<em>, \u2026, a<\/em><em>n<\/em>) and symbol probabilities (<em>p<\/em>1<em>, \u2026, p<\/em><em>n<\/em>). Then an important question is to find out the amount of information obtained by knowing that the next symbol is <em>a<\/em><em>i..<\/em>Shannon associated a concept called self information to find out amount of information conveyed by\u00a0<em>a<\/em><em>i.<\/em><\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-129 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-78.png\" alt=\"\" width=\"642\" height=\"511\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-78.png 642w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-78-300x239.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-78-65x52.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-78-225x179.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-78-350x279.png 350w\" sizes=\"auto, (max-width: 642px) 100vw, 642px\" \/><\/p>\n<p><strong>9.4.2 Entropy<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In order to find information about the symbols in a sequence we can <em>average<\/em> <em>over the probability over all the symbols<\/em>, given as:<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-130 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-79.png\" alt=\"\" width=\"644\" height=\"490\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-79.png 644w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-79-300x228.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-79-65x49.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-79-225x171.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-79-350x266.png 350w\" sizes=\"auto, (max-width: 644px) 100vw, 644px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-131 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-80.png\" alt=\"\" width=\"235\" height=\"125\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-80.png 235w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-80-65x35.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-80-225x120.png 225w\" sizes=\"auto, (max-width: 235px) 100vw, 235px\" \/><\/p>\n<div>\n<p>&nbsp;<\/p>\n<p><strong>9.4.2.1<\/strong>\u00a0\u00a0<strong>Entropy: Three properties<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Entropy is a measurement of information. It has three basic properties. It can be shown that 0 \u00a3 <em>H<\/em> \u00a3 <em>log N<\/em>. Maximum entropy (<em>H = log N<\/em>) is reached when all symbols are equiprobable, i.e., <em>p<\/em><em>i<\/em> <em>=<\/em> 1<em>\/N<\/em>. The difference between maximum entropy and actual entropy <em>log N<\/em> <em>\u2013<\/em> <em>H<\/em> is called the <em>redundancy<\/em> of the source.<\/p>\n<\/div>\n<p>&nbsp;<\/p>\n<p><strong>9.5 Entropy for Memory and Markov Sources<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Entropy for Memory Source<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Assume a block of source symbols (<em>X<\/em>1, \u2026, <em>X<\/em><em>n<\/em>) , we can define the <em>block<\/em> <em>entropy<\/em>:<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-132 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-81.png\" alt=\"\" width=\"555\" height=\"507\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-81.png 555w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-81-300x274.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-81-65x59.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-81-225x206.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-81-350x320.png 350w\" sizes=\"auto, (max-width: 555px) 100vw, 555px\" \/><\/p>\n<p><strong>The Run-length Source<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Certain sources generate long <em>runs<\/em> or <em>bursts<\/em> of equal symbols. Let us look at an example<\/p>\n<p>&nbsp;<\/p>\n<p>Example:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-133 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-82.png\" alt=\"\" width=\"453\" height=\"161\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-82.png 453w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-82-300x107.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-82-65x23.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-82-225x80.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-82-350x124.png 350w\" sizes=\"auto, (max-width: 453px) 100vw, 453px\" \/><\/p>\n<p><strong>9.6 The Source Coding Theorem<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">As we have already discussed entropy is the smallest number of bits allowing error-free representation of the source. Shannon shows that source coding algorithms exist that have a unique average representation length that approaches the entropy of the source and we cannot reduce beyond this length. To understand this aspect let us consider typical sequences.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Typical Sequences<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">We assume a <em>long<\/em> sequence from a binary memoryless source with <em>P<\/em>(1) = <em>p<\/em>. Among n bits, there will be approximately <em>w = n .p<\/em> ones. Thus, there is <em>M<\/em> = (<em>n<\/em> <em>choose w<\/em>) such<em> typical sequences<\/em>!<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><em>Only these sequences are interesting. <\/em>All other sequences will appear with smaller probability as <em>n becomes larger<\/em>. Now we need to find out how many sequences are actually typical sequences.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-134 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-83.png\" alt=\"\" width=\"482\" height=\"351\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-83.png 482w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-83-300x218.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-83-65x47.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-83-225x164.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-83-350x255.png 350w\" sizes=\"auto, (max-width: 482px) 100vw, 482px\" \/><\/p>\n<p style=\"text-align: justify\">bits per symbol!<\/p>\n<p style=\"text-align: justify\">Deriving from equation 1 by substituting w=n.p we get<\/p>\n<p style=\"text-align: justify\">-p log p \u2013 (1-p) log (1-p) = h(p) =H(X).<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Thus we can conclude that we need <em>H<\/em>(<em>X<\/em>) bits per symbol to code any typical sequence.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>Example \u2013Sequence<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Consider the following sequence:<\/p>\n<p style=\"text-align: justify\">1 2 1 2 4 4 1 2 4 4 4 4 4 4 1 2 4 4 4 4 4 4 Obtaining the probability from the sequence<\/p>\n<p style=\"text-align: justify\">1 four times (4\/22), 2 four times (4\/22), and 4 fourteen times (14\/22)<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-135 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-84.png\" alt=\"\" width=\"552\" height=\"275\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-84.png 552w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-84-300x149.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-84-65x32.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-84-225x112.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-84-350x174.png 350w\" sizes=\"auto, (max-width: 552px) 100vw, 552px\" \/><\/p>\n<p style=\"text-align: justify\">The entropy H = 0.447 + 0.447 + 0.415 = 1.309 bits<\/p>\n<p style=\"text-align: justify\">There are 22 symbols, we need 22 * 1.309 = 28.798 (29) bits to transmit<\/p>\n<p style=\"text-align: justify\">Now we can consider the symbols as blocks of 12, 44 (now total symbols-11) &#8211; 12 appears 4\/11 and 44 appears 7\/11<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-136 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-85.png\" alt=\"\" width=\"414\" height=\"148\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-85.png 414w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-85-300x107.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-85-65x23.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-85-225x80.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-85-350x125.png 350w\" sizes=\"auto, (max-width: 414px) 100vw, 414px\" \/><\/p>\n<p style=\"text-align: justify\">There are 11 symbols, we need 11 * 0.945 = 10.395 (11) bits to transmit information \u2013 that is we might be able to find patterns with less entropy<\/p>\n<p>&nbsp;<\/p>\n<p><strong>9.7 Using information theory<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Entropy measures the amount of uncertainty in a probability distribution:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Consider tossing a biased coin. If you toss the coin VERY often, the frequency of heads is, say, p, and hence the frequency of tails is 1-p. (fair coin p=0.5). Uncertainty in any actual outcome is given by entropy: Uncertainty is zero if p=0 \/ 1 and maximal if we have p=0.5.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-137 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-86.png\" alt=\"\" width=\"578\" height=\"396\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-86.png 578w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-86-300x206.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-86-65x45.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-86-225x154.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-86-350x240.png 350w\" sizes=\"auto, (max-width: 578px) 100vw, 578px\" \/><\/p>\n<p style=\"text-align: justify\">Information theory can be used to determine how much information we gain if we disclose the value of some attribute? (for example in a decision tree). Entropy can be used as a measure of the quality of our models and as a measure of how different two probability distributions are. We will discuss these aspects later.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Summary<\/strong><\/p>\n<ul>\n<li style=\"text-align: justify\">Explained the model of communication<\/li>\n<li style=\"text-align: justify\">Outlined the sources of information<\/li>\n<li style=\"text-align: justify\">Explained entropy<\/li>\n<li style=\"text-align: justify\">Discussed source and Markov source<\/li>\n<li style=\"text-align: justify\">Discussed source and Markov source<\/li>\n<\/ul>\n<table>\n<tbody>\n<tr>\n<td><strong>you can view video on Information Theory<\/strong><\/td>\n<td><a href=\"https:\/\/youtu.be\/JRug4KC07S4\" target=\"_blank\" rel=\"noopener\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><strong>Web Links<\/strong><\/p>\n<ul>\n<li>http:\/\/users.ecs.soton.ac.uk\/sqc\/EL334N\/InfThe-L3.pdf<\/li>\n<li>http:\/\/www.fi.muni.cz\/usr\/staudek\/infteo\/info-lec.pdf<\/li>\n<li>http:\/\/140.113.144.123\/lecture%20notes%20for%20channel%20capacity08.pdf<\/li>\n<li>http:\/\/www.commsys.isy.liu.se\/ITWC\/Lecture1.pdf<\/li>\n<li>http:\/\/www.icg.isy.liu.se\/courses\/tsbk01\/material\/slides\/2_BasicInformationTheor y.pps<\/li>\n<li>http:\/\/www.myoops.org\/cocw\/mit\/NR\/rdonlyres\/Electrical-Engineering-and-Computer-Science\/6-450Principles-of-Digital-Communication&#8212; IFall2002\/7BFBEC46-0F71-48A6-8D2A-EA73F0C0BD03\/0\/L502.pdf<\/li>\n<li>http:\/\/www.greentouch.org\/?page=shannons-law-explained<\/li>\n<li>https:\/\/courses.cs.washington.edu\/courses\/cse533\/06au\/lecnotes\/lecture3.pdf<\/li>\n<li>http:\/\/www.greentouch.org\/index.php?page=shannons-law-explained<\/li>\n<\/ul>\n","protected":false},"author":3,"menu_order":9,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"class_list":["post-125","chapter","type-chapter","status-publish","hentry"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters\/125","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/users\/3"}],"version-history":[{"count":10,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters\/125\/revisions"}],"predecessor-version":[{"id":467,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters\/125\/revisions\/467"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters\/125\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/media?parent=125"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapter-type?post=125"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/contributor?post=125"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/license?post=125"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}