Exercise 02

Question 1

Suppose we have a simplified language with:

• Three vowels : $a,i\text{and}u$
• Three consonants: $p,t\text{and}k$ Let $X$ map consonants $\{p,t,k\}$ to range $R_X=\{1,2,3\}$ Let $Y$ map vowels $\{a,i,u\}$ to range $R_Y=\{1,2,3\}$. Suppose we estimated the joint PMF for vowel and consonant co-occurrences within syllables, as given below.

$$P(x,y)=\begin{array}{cccc}x\backslash y& 1& 2& 3\\ 1& \frac{1}{16}& \frac{3}{8}& \frac{1}{16}\\ 2& \frac{1}{16}& \frac{3}{16}& 0\\ 3& 0& \frac{3}{16}& \frac{1}{16}\end{array}$$

Calculate the following :

$$P(x,y)=\begin{array}{ccccc}x\backslash y& 1& 2& 3& P(x)\\ 1& \frac{1}{16}& \frac{3}{8}& \frac{1}{16}& \frac{1}{2}\\ 2& \frac{1}{16}& \frac{3}{16}& 0& \frac{1}{4}\\ 3& 0& \frac{3}{16}& \frac{1}{16}& \frac{1}{4}\\ P(y)& \frac{1}{8}& \frac{3}{4}& \frac{1}{8}& 1\end{array}$$

Entropies H(X) and H(Y)

$$\begin{array}{rl}H(X)& =-\sum _{i=1}^{m}P(x_i){\log }_{2}P(x_i)\\ & =-(\frac{1}{8}{\log }_2\frac{1}{8}+\frac{3}{4}{\log }_2\frac{3}{4}+\frac{1}{8}{\log }_2\frac{1}{8})\\ & =1.061\end{array}$$ $$\begin{array}{rl}H(Y)& =-\sum _{i=1}^{m}P(y_i){\log }_{2}P(y_i)\\ & =-(\frac{1}{2}{\log }_2\frac{1}{2}+\frac{1}{4}{\log }_2\frac{1}{4}+\frac{1}{4}{\log }_2\frac{1}{4})\\ & =1.5\end{array}$$

Joint entropy H(X, Y ) :

$$\begin{array}{rl}H(X,Y)& =-\sum _{x\in {\mathcal{R}}_X}\sum _{y\in {\mathcal{R}}_Y}P(x,y)\log P(x,y)\\ & =-(\frac{1}{16}{\log }_2\frac{1}{16}+\frac{3}{8}{\log }_2\frac{3}{8}+\frac{1}{16}{\log }_2\frac{1}{16}+\frac{1}{16}{\log }_2\frac{1}{16}+\frac{3}{16}{\log }_2\frac{3}{16}+\frac{3}{16}{\log }_2\frac{3}{16}+\frac{1}{16}{\log }_2\frac{1}{16})\\ & =2.436\end{array}$$

Conditional entropies H(X|Y ) and H(Y|X)

$$\begin{array}{rl}H(X|Y)& =H(X,Y)-H(Y)\\ & =2.436-1.5\\ & =0.936\end{array}$$ $$\begin{array}{rl}H(Y|X)& =H(X,Y)-H(X)\\ & =2.436-1.061\\ & =1.375\end{array}$$

Mutual information I(X; Y )

$$\begin{array}{rl}I(X;Y)& =H(X)-H(X|Y)\\ & =1.061-0.936\\ & =0.125\end{array}$$

Question 2

As a data scientist in a telecommunication company, your task is to analyse a customer dataset to predict whether a customer will terminate his/her contract. The dataset consists of around 8000 customer records, each consisting of one binary dependent variable $Y$ , indicating whether the customer terminates the contract $(Y=1)$ or not $(Y=0)$, and 19 independent variables, which include the customer’s information, e.g., age, subscription plan, extra data plan, etc., and consumer behaviour such as the average number of calls and hours per week. Since your boss needs some actionable insights to retain customers, you decided to use interpretable machine learning methods. Design your interpretable machine learning method by answering the following questions:

You have implemented a feature selection algorithm based on mutual information to select the most informative features from the 19 independent variables. To validate the implementation of your mutual information calculation function, you use a small subset of the data to calculate mutual information manually. You select one independent variable subscription plan, denoted as $S$, which takes two values, $S\in \{1,2\}$. Please use the following Probability Mass Function table:

$$\begin{array}{ccc}p(S,Y)& S=1& S=2\\ Y=0& \frac{2}{12}& \frac{5}{12}\\ Y=1& \frac{2}{12}& \frac{3}{12}\end{array}$$

Calculate :

$$\begin{array}{cccc}p(S,Y)& S=1& S=2& p(Y)\\ Y=0& \frac{2}{12}& \frac{5}{12}& \frac{7}{12}\\ Y=1& \frac{2}{12}& \frac{3}{12}& \frac{5}{12}\\ p(S)& \frac{4}{12}& \frac{8}{12}& 1\end{array}$$

Entropy $H(S)$ .

$$\begin{array}{rl}H(S)& =-\sum _{i=1}^{m}P(s_i){\log }_{2}P(s_i)\\ & =-(\frac{4}{12}{\log }_2\frac{4}{12}+\frac{8}{12}{\log }_2\frac{8}{12})\\ & =0.918\end{array}$$

Entropy $H(Y)$.

$$\begin{array}{rl}H(Y)& =-\sum _{i=1}^{m}P(y_i){\log }_{2}P(y_i)\\ & =-(\frac{7}{12}{\log }_2\frac{7}{12}+\frac{5}{12}{\log }_2\frac{5}{12})\\ & =0.982\end{array}$$

Joint entropy H(S,Y) :

$$\begin{array}{rl}H(S,Y)& =-\sum _{s\in {\mathcal{R}}_s}\sum _{y\in {\mathcal{R}}_Y}P(s,y)\log P(s,y)\\ & =-(\frac{2}{12}{\log }_2\frac{2}{12}+\frac{5}{12}{\log }_2\frac{5}{12}+\frac{2}{12}{\log }_2\frac{2}{12}+\frac{3}{12}{\log }_2\frac{3}{12})\\ & =1.89\end{array}$$

Conditional entropy H(S|Y) :

$$\begin{array}{rl}H(S|Y)& =H(S,Y)-H(Y)\\ & =1.89-0.982\\ & =0.908\end{array}$$

Conditional entropy H(Y|S):

$$\begin{array}{rl}H(Y|S)& =H(S,Y)-H(S)\\ & =1.89-0.918\\ & =0.972\end{array}$$

Mutual information I(S; Y) :

$$\begin{array}{rl}I(S;Y)& =H(S)-H(S|Y)\\ & =0.918-0.908\\ & =0.01\end{array}$$

After applying your algorithm, you selected two variables:

• Extra data plan $E$, which is a binary random variable that indicates whether the customer subscribes to the extra data plan $(E=1)$ or not $(E=0)$.
• Averaged hours used per week $H$, which is a continuous random variable. You then built a logistic regression model to classify customers into low risk or high risk of terminating the contract. The fitted model is:

$$\log \left(\frac{p}{1-p}\right)=-0.77+0.23H-1.18E$$

1. Given a customer x who has the extra data plan $(E=1)$ and spent on average 0.5 hours per week, calculate the odds and the probability that the customer will terminate the contract $(Y=1|x)$.

$$\begin{array}{rl}\log \left(\frac{p}{1-p}\right)& =-0.77+(0.23\cdot 0.5)-(1.18\cdot 1)\\ & =-1.835\\ \log \left(\frac{p}{1-p}\right)& =-1.835\\ \frac{p}{1-p}& =e^{-1.835}\\ \frac{p}{1-p}& =0.159\\ p& =\frac{0.159}{1+0.159}\\ p& =\frac{0.159}{1.159}\\ p& \approx 0.137\end{array}$$

Question 3

As a machine learning expert for an AI cybersecurity company, your task is to design an automated network intrusion detection system. You have collected a large number of records of network activities. Each record includes the log information about network activity, such as protocol types, duration, number of failed logins, which are random variables, denoted as $\mathbf{X}=[X_1,X_2,\dots ,X_n]$. Each record also includes a binary random variable Y called label that was labelled by cybersecurity experts as intrusions $(Y=1)$ or normal connections $(Y=0)$. Answer the following questions about Feature Selection Based on Mutual Information.

• Explain to your colleague, who knows nothing about information theory, the concept of mutual information. Ans - Mutual information measures the amount of information that one random variable provides about another. It quantifies how much knowing one variable reduces uncertainty about the other. High mutual information indicated string dependence between variables, while low mutual information suggests independence.
• Explain the loop in the pseudocode of Table 1.

$$\begin{array}{rl}1.& \text{Initialize: Set }F\leftarrow X\text{ and }S\leftarrow \varnothing \\ 2.& \text{Select }{f}_{\text{max}}=\arg \underset{X_i\in X}{\max }I(Y;X_i)\\ 3.& \text{Update }F\leftarrow F\setminus \{f_{\text{max}}\},S\leftarrow \{f_{\text{max}}\}\\ 4.& \text{Repeat until }|S|=K:\\ 5.& \text{Select }{f}_{\text{max}}=\arg \underset{X_i\in F}{\max }\left(I(Y;X_i)-\sum _{X_s\in S}I(X_s;X_i)\right)\\ 6.& \text{Update }F\leftarrow F\setminus \{f_{\text{max}}\},S\leftarrow S\cup \{f_{\text{max}}\}\end{array}$$

Ans - The two lines in the loop are used to select $K$ features. In this loop, we find the feature fmax which achieves the maximum mutual information $I$ among all the remaining independent variables in set $F$. However, some features may be highly correlated with each other, hence selecting them will increase the number of features without improving the prediction. Therefore, we make sure that there is minimal redundancy between the candidate feature $X_i$ and the set of selected features $S$. That’s exactly what the second term on the RHS achieves in line 5. We then add this feature into the set $S$ and subtract it from set $F$, and repeat until we got $K$ features.

Question 4

A company wants to classify whether a customer will purchase a product ($Y$ = Yes) or not ($Y$ = No) based on categorical features. You have access to the following dataset:

Age Group	Income Level	Prior Purchase	Purchase (Y)
Young	Low	No	No
Young	Low	Yes	No
Young	High	No	Yes
Middle-aged	Low	No	No
Middle-aged	High	No	Yes
Senior	Low	No	No
Senior	High	Yes	Yes
Senior	High	No	Yes

• Calculate the entropy of the target variable $Y$.

$$\begin{array}{rl}H(Y)& =-\sum _{i=1}^{m}P(y_i){\log }_{2}P(y_i)\\ & =-(\frac{4}{8}{\log }_2\frac{4}{8}+\frac{4}{8}{\log }_2\frac{4}{8})\\ & =1\end{array}$$

• Compute the information gain for splitting on the feature “Prior Purchase.”
  • For Prior Purchase = Yes : [No, Yes] $Entropy(Y|PP=Yes)=-(0.5){\log }_2(0.5)-(0.5){\log }_2(0.5)=1$
  • For Prior Purchase = No : [No, Yes, No, Yes, No, Yes] $Entropy(Y|PP=No)=-(0.5){\log }_2(0.5)-(0.5){\log }_2(0.5)=1$

$$\begin{array}{rl}WeightedEntropy& =\frac{6}{8}\cdot 1.0+\frac{2}{8}\cdot 1.0=1.0\\ IG(Y,PP)& =H(Y)-WeightedEntropy\\ & =1.0-1.0\\ & =0\end{array}$$

• If you were to build a decision tree, which feature would be the best root node? Justify your answer. The best root node should have the highest information gain. “Income Level” has maximal IG, so it should be selected as the root node.
• Discuss how overfitting can be avoided in decision trees and suggest techniques to improve generalization.
  • Pruning : Remove branches that add little classification value. Use a validation set to find how much to prune.
  • Limiting Depth : Restrict maximum depth of the tree. Use a validation set to find when to stop growing the tree.
  • Applying ensemble methods : Use bagging or boosting.