Problem Set2

docx

School

Georgia Institute Of Technology *

*We aren’t endorsed by this school

Course

7641

Subject

Computer Science

Date

Feb 20, 2024

Type

docx

Pages

Uploaded by AdmiralWaterBuffalo3874

Problem Set 2 1 ． To design an appropriate encoding for the language with symbols A, B, and C, we can use variable-length codes based on the probabilities of each symbol. In this case, the probability distribution is as follows: P(A)=0.5 P(B)=0.25 P(C)=0.25 A common approach is to assign shorter codes to more probable symbols. One widely used method is Huffman coding. Let's construct a Huffman tree to determine the codes: Create nodes for each symbol (A, B, C) with their probabilities. Repeatedly combine the nodes with the lowest probabilities until there's only one node left, which represents the entire code. Huffman Tree: Copy code (0.5) / \ (A:0.5) \ (0.5) / \ (B:0.25) (C:0.25) Codes: A: 0 B: 10 C: 11 So, the Huffman codes for the symbols are A: 0, B: 10, and C: 11. Now, let's calculate the entropy of this signal. The entropy (H) is given by: H=−∑Pi ⋅ log2(Pi) where Pi is the probability of symbol i. Using the given probabilities: H=−(0.5 ⋅ log 2(0.5)+0.25 ⋅ log 2 (0.25)+0.25 ⋅ log 2 (0.25)) Now, compute the values and sum them up to get the entropy in bits. The logarithms are typically base 2 in information theory. H=−(0.5 ⋅ (−1)+0.25 ⋅ (−2)+0.25 ⋅ (−2))

H=0.5+0.5+0.5 H=1.5bits So, the entropy of this signal is 1.5 bits. 2. Show that the K-means procedure can be viewed as a special case of the EM algorithm applied to an appropriate mixture of Gaussian densities model. Mixture of Gaussian Densities Model In the EM algorithm, one common application is to fit a mixture of Gaussian densities model to the data. The model assumes that the data is generated from a mixture of several Gaussian distributions, each characterized by a mean and a covariance matrix. E-step (Expectation Step) In the E-step of the EM algorithm, the algorithm computes the probability that each data point belongs to each of the Gaussian components. These probabilities are often referred to as "responsibilities." M-step (Maximization Step) In the M-step, the algorithm updates the parameters (means and covariances) of the Gaussian components based on the responsibilities computed in the E-step. K-means as a Special Case Now, let's consider the special case where we have a mixture of spherical Gaussians (i.e., each component has a diagonal covariance matrix with equal variances along the dimensions). In this case, the EM algorithm simplifies, and the responsibilities become binary (either 0 or 1). Connection to K-means In the specific case of a mixture of spherical Gaussians, the responsibilities in the E-step effectively become "hard" assignments, indicating which cluster each data point belongs to with certainty. This is exactly what happens in the K-means algorithm, where each data point is assigned to the cluster with the nearest centroid. In other words, the K-means algorithm can be seen as a special case of the EM algorithm for a mixture of spherical Gaussians, where the responsibilities are "hard" assignments. 7. Consider the following simple grid-world problem. (Actions are N, S, E, W and are deterministic.) Our goal is to maximize the following reward: ● 10 for the transition from state 6 to G ● 10 for the transition from state 8 to G ● 0 for all other transitions S 2 3 4 5 6 7 8 G

a. Draw the Markov Decision Process associated to the system. b. Compute the value function for each state for iteration 0, 1, 2 and 3 with γ=0.8 a. Markov Decision Process (MDP): States: {S, 2, 3, 4, 5, 6, 7, 8, G} Actions: {N, S, E, W} Transitions: From S, all actions lead to state 2. From 2, N leads to S, and other actions lead to state 5. From 3, all actions lead to state 6. From 4, all actions lead to state 5. From 5, N leads to 2, S leads to 4, and E leads to 6. From 6, all actions lead to G. From 7, all actions lead to state 8. From 8, all actions lead to G. From G, all actions lead to G. Rewards: Transition from 6 to G has a reward of 10. Transition from 8 to G has a reward of 10. All other transitions have a reward of 0. S - 2 - 3 | | | 4 - 5 - 6 | | 7 - 8 – G b. Iteration 0: V0(S)=V0(2)= V0(3)= V0(4)= V0(5)= V0(6)= V0(7)= V0(8)=0 V0(6)=V0(G)=10 Iteration 1: V1(S)=max(0+0.8V0(2),0+0.8V0(3),0+0.8V0(4)) V1(2)=max(0+0.8V0(S),0+0.8V0(5)) V1(3)=0+0.8V0(6) V1(4)=max(0+0.8V0(5)) V1(5)=max(0+0.8V0(2),0+0.8V0(4),0+0.8V0(6))

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

V1(6)=10+0.8V0(G) V1(7)=max(0+0.8V0(8)) V1(8)=10+0.8V0(G) V1(G)=10

Related Documents

Mid term.docx

2..png

3..png

Team Consulting Project - Instructions v2 (1).docx

MGMT-104-HW1.docx

2023w2-mt1:mt1-p5 exam solution.docx

05_pytorch_going_modular.md

two_layer_nn.pdf

Assignment 6 Analyze Skilled Dialogue and an IEP Meeting.pdf

midterm1-23w-soln.pdf

DAD 220 3-2 Table Joins.pdf

midterm1-23w.pdf

Recommended textbooks for you

Operations Research : Applications and Algorithms

Computer Science

ISBN:9780534380588

Author:Wayne L. Winston

Publisher:Brooks Cole

C++ Programming: From Problem Analysis to Program...

Computer Science

ISBN:9781337102087

Author:D. S. Malik

Publisher:Cengage Learning

Systems Architecture

Computer Science

ISBN:9781305080195

Author:Stephen D. Burd

Publisher:Cengage Learning

Programming Logic & Design Comprehensive

Computer Science

ISBN:9781337669405

Author:FARRELL

Publisher:Cengage

COMPREHENSIVE MICROSOFT OFFICE 365 EXCE

Computer Science

ISBN:9780357392676

Author:FREUND, Steven

Publisher:CENGAGE L

SEE MORE TEXTBOOKS

Recommended textbooks for you

Operations Research : Applications and Algorithms
Computer Science
ISBN:9780534380588
Author:Wayne L. Winston
Publisher:Brooks Cole
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
Systems Architecture
Computer Science
ISBN:9781305080195
Author:Stephen D. Burd
Publisher:Cengage Learning
Programming Logic & Design Comprehensive
Computer Science
ISBN:9781337669405
Author:FARRELL
Publisher:Cengage
COMPREHENSIVE MICROSOFT OFFICE 365 EXCE
Computer Science
ISBN:9780357392676
Author:FREUND, Steven
Publisher:CENGAGE L