Introduction to Machine Learning Homework #2

Author： Bi_Gu
发布时间：April 11, 2023
1493 views
5 comments
5979 words
Categories：课堂笔记机器学习引论

# Introduction to Machine Learning

## Homework 2

### Problem 1

Kernel functions implicitly define some mapping function $\phi(\cdot)$ that transforms an input instance $\textbf{x}\in\mathbb{R}^{d}$ to high dimensional space $Q$ by giving the form of dot product in
$Q:K\left(\textbf{x}_{i},\textbf{x}_{j}\right)\equiv\left\langle\phi\left(\textbf{x}_{i}\right),\phi\left(\textbf{x}_{j}\right)\right\rangle$

(a) Prove that the kernel is symmetric,i.e. $K\left(\textbf{x}_{i}, \textbf{x}_{j}\right)=K\left(\textbf{x}_{j}, \textbf{x}_{i}\right).$

**Solution.**

We have that

$$
K(\textbf{x}_i,\textbf{x}_j)=\left\langle\phi(\textbf{x}_i,\textbf{x}_j)\right\rangle

=\left\langle\phi(\textbf{x}_j,\textbf{x}_i)\right\rangle=K(\textbf{x}_j,\textbf{x}_i).
$$

(b) Assume we use radial basis kernel function $K\left(\textbf{x}_{i},\textbf{x}_{j}\right)=\exp\left(-\frac{1}{2}\left\|\textbf{x}_{i}-\textbf{x}_{j}\right\|^{2}\right)$.

Thus there is some implicit unknown mapping function $\phi(\textbf{x})$. Prove that for any two input instances $\textbf{x}_{i}$ and $\textbf{x}_{j}$, the squared Euclidean distance of their corresponding points in the feature space $Q$ is less than 2, i.e. prove that $\left\|\phi\left(\textbf{x}_{i}\right)-\phi\left(\textbf{x}_{j}\right)\right\|^{2} \leq 2$.

**Solution.**

We have that

$$
\begin{aligned}
            ||\phi(\textbf{x}_i)-\phi(\textbf{x}_j)||^2&=\left\langle\phi(\textbf{x}_i),\phi(\textbf{x}_i)\right\rangle+
            \left\langle\phi(\textbf{x}_j),\phi(\textbf{x}_j)\right\rangle-2\cdot\left\langle\phi(\textbf{x}_i),\phi(\textbf{x}_j)\right\rangle
            \\&=K(\textbf{x}_i,\textbf{x}_i)+K(\textbf{x}_j,\textbf{x}_j)-2\cdot K(\textbf{x}_i,\textbf{x}_j)
            \\&=1+1-2\exp\left(-\frac{1}{2}\left\|\textbf{x}_{i}-\textbf{x}_{j}\right\|^{2}\right)\leq2.
        \end{aligned}
$$

(c) With the help of a kernel function, SVM attempts to construct a hyper-plane in the feature space $Q$ that maximizes the margin between two classes. The classification decision of any  $\textbf{x}$  is made on the basis of the sign of

$$
\langle\hat{\textbf{w}},\phi(\textbf{x})\rangle+\hat{w}_0=\sum_{i\in SV}y_i\alpha_i K\left(\textbf{x}_i,\textbf{x}\right)+\hat{w}_0=f\left(\textbf{x};\alpha,\hat{w}_0\right),
$$

where $\hat{\textbf{w}}$ and $\hat{w}_0$ are parameters for the classification hyper-plane in the feature space $Q,SV$ is the set of support vectors, and $\alpha_i$ is the coefficient for the $i$-th support vector. Again we use the radial basis kernel function. Assume that the training instances are linearly separable in the feature space $Q$, and assume that the SVM finds a margin that perfectly separates the points.

If we choose a test point $\textbf{x}_{\text{far}}$ which is far away from any training instance $\textbf{x}_i$ (distance here is measured in the original space $\mathbb{R}^d$), prove that $f(\textbf{x}_{\text{far}};\alpha, \hat{w}_0)\approx\hat{w}_0$.

**Solution.**

Since that the test point $\textbf{x}_{\text{far}}$ is far away from any training instance $\textbf{x}_i$, we have that

$$
\forall i\in SV,\ ||\textbf{x}_{\text{far}}-\textbf{x}_i||\gg 0;
$$

Therefore

$$
\begin{aligned}
            &\quad\forall i\in SV, K(\textbf{x}_{\text{far}},\textbf{x}_i)\approx 0
            \\&\Rightarrow \sum_{i\in SV}y_i\alpha_i K(\textbf{x}_{\text{far}},\textbf{x}_i)\approx 0
            \\&\Rightarrow f(\textbf{x}_{\text{far}};\alpha, \hat{w}_0)\approx\hat{w}_0.
        \end{aligned}
$$

### Problem 2

The Poisson distribution is a useful discrete distribution which can be used to model the number of occurrences of something per unit time. For example, in networking, the number of packets to arrive in a given time window is often assumed to follow a Poisson distribution. If $X$ is Poisson distributed, i.e. $X \sim \operatorname{Poisson}(\lambda)$, its probability mass function takes the following form:

$$
P(X\mid\lambda)=\frac{\lambda^x e^{-\lambda}}{X!}
$$

It can be shown that if $\mathbb{E}(X)=\lambda$. Assume now we have $n$ i.i.d. data points from Poisson $(\lambda)$ : $\mathcal{D}=\left\{X_1,\ldots,X_n\right\}$ (For the purpose of this problem, you can only use the knowledge about the Poisson and Gamma distributions provided in this problem.)

(a) Show that the sample mean $\hat{\lambda}=\frac{1}{n}\sum_{i=1}^n X_i$ is the maximum likelihood estimate (MLE) of $\lambda$ and it is unbiased $(\mathbb{E}(\hat{\lambda})=\lambda)$.

**Solution.**

**Part A.** First we prove that $\hat{\lambda}$ is the maximum likelihood estimate of $\lambda$:

Since the $n$ data points are i.i.d., we have the likelihood function to be

$$
\mathcal{L}=P(\mathcal{D}\mid\lambda)=\prod_{i=1}^n\frac{e^{-\lambda}\lambda^{X_i}}{X_i!}
        =\frac{\prod_{i=1}^ne^{-\lambda}\cdot\prod_{i=1}^n\lambda^{X_i}}{\prod_{i=1}^n X_i!}
        =\frac{e^{-n\lambda}\cdot\lambda^{\sum_{i=1}^nX_i}}{\prod_{i=1}^n X_i!}
$$

To find $\mathop{\text{argmax}}\limits_{\lambda}P(\mathcal{D}\mid\lambda)$, it is equivalent to find  $\mathop{\text{argmax}}\limits_{\lambda}\ln\big[P(\mathcal{D}\mid\lambda)\big]$, where

$$
\begin{aligned}\ln\mathcal{L}&=\sum_{i=1}^n\ln\left(\frac{e^{-\lambda}\lambda^{X_i}}{X_i!}\right)
        =\sum_{i=1}^n\left(-\lambda+\ln\lambda+\ln X_i-\ln X_i!\right)\\&=-n\lambda+\ln\lambda\sum_{i=1}^nx_i-\sum_{i=1}^n\ln X_i!\end{aligned}
$$

The maximum is at where the first derivative is zero, i.e.

$$
\frac{\partial\ln\mathcal{L}}{\partial\lambda_{\text{max}}}=-N+\frac{1}{\lambda_{\text{max}}}\sum_{i=1}^n X_i=0\Rightarrow
        \lambda_{\text{max}}=\frac{1}{n}\sum_{i=1}^nX_i=\hat{\lambda}
$$

To verify that this is maximum (rather than minimum), we take the second derivative:

$$
\frac{\partial^2\ln\mathcal{L}}{\partial\lambda^2}=\frac{\partial}{\partial\lambda}\left(-N+\frac{1}{\lambda}{\sum_{i=1}^nX_i}\right)=-\frac{1}{\lambda^2}\sum_{i=1}^nX_i<0
$$

which is always negative, so that $\hat{\lambda}$ is the only maximum.

**Part B.** Now we prove that $\hat{\lambda}$ is unbiased:

First we calculate $E[X]$ as follows

$$
\begin{aligned}E[X]&=\sum_{x\in X}xP(X=x)=\sum_{i\geq 0}^n\frac{x_i\lambda^{x_i}e^{-\lambda}}{x_i!}
            \\&=\lambda e^{-\lambda}\sum_{i\geq 1}^n\frac{\lambda^{x_{i-1}}}{x_{i-1}!}=\lambda e^{\lambda}\sum_{k\geq 0}\frac{\lambda^k}{k!}=\lambda e^{-\lambda}e^{\lambda}=\lambda;
        \end{aligned}
$$

Therefore we have that

$$
E[\hat{\lambda}]=E\left[\frac{1}{n}\sum_{i=1}^nX_i\right]=\frac{1}{n}\sum_{i=1}^nE[X_i]=\frac{1}{n}\sum_{i=1}^n\lambda=\lambda.
$$

Which means that $\hat{\lambda}$ is unbiased.

(b) Now let's be Bayesian and put a prior distribution over $\lambda$. Assuming that $\lambda$ follows a Gamma distribution with the parameters $(\alpha,\beta)$, its probability density function:

$$
p(\lambda\mid\alpha,\beta)=\frac{\beta^\alpha}{\Gamma(\alpha)}\lambda^{\alpha-1} e^{-\beta\lambda}
$$

where $\Gamma(\alpha)=(\alpha-1)!$ (here we assume $\alpha$ is a positive integer). Compute the posterior distribution over $\lambda$.

**Solution.**

We calculate the posterior distribution over $\lambda$ as follows:

$$
\begin{aligned}P(\lambda\mid y)&\propto\frac{\beta^{\alpha}\lambda^{\alpha-1}e^{-\beta\lambda}}{\Gamma(\alpha)}\cdot
    \frac{e^{-n\lambda}\lambda^{\sum_{i=1}^nX_i}}{\prod_{i=1}^nX_i!}=\frac{\beta^{\alpha}}{\Gamma(\alpha)\prod_{i=1}^nX_i!}
    \cdot\left(\lambda^{\alpha-1+\sum_{i=1}^nx_i}\cdot e^{-(n+\beta)\lambda}\right)
    \\&=P(\lambda\mid\alpha+\sum_{i}X_i,\beta+n)=\Gamma(\hat{\alpha},\hat{\beta})\end{aligned}
$$

where $\hat{\alpha}=\alpha+\sum_{i}X_i$ and $\hat{\beta}=\beta+n$.

**Solution.**

Since that

$$
\alpha>1\Rightarrow\hat{\alpha}=\alpha+\sum_{i=1}^nX_i>1
$$

We have the MAP estimation of $\lambda$ to be

$$
\frac{\hat{\alpha}-1}{\hat{\beta}}=\frac{\alpha+\sum_{i=1}^nX_i-1}{\beta+n}.
$$

### Problem 3

Using d-separation on figure 1 to discuss the following questions.
![](https://cdn.dabigu.xyz/cs182_hw2_p0.jpg)(a) Are A and B conditionally independent, given D and F?

**Solution.**

A and B **are NOT** conditionally independent. According to the follow process,
![](https://cdn.dabigu.xyz/cs182_hw2_p1.png)A and B are connected, so they are not required to be conditionally independent given D and F.

(b) $P(D\mid CEG) =?\ P(D\mid C)$

**Solution.**

**Not equal**. The equation holds iff. D and E are conditionally independent given C, and D and G are also conditionally independent given C.
![](https://cdn.dabigu.xyz/cs182_hw2_p2.png)From the figure above we know that D and E are conditionally independent given C; However,

![](https://cdn.dabigu.xyz/cs182_hw2_p3.png)From the figure above we know that D and G are **not** conditionally independent given C. Since the equation holds only when both two conditions are satisfied, we have that $P(D\mid CEG) \neq\ P(D\mid C)$.

Last modification：April 11, 2023

Support if you like my work! qwq

版权声明：若文中无特殊说明，则本文为原创文章，版权归 Bi_Gu 所有。

本文链接：https://dabigu.xyz/index.php/archives/627/

所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。
您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。

随机文章 Maths Analysis II - Homework #8 20220310 Maths Analysis II - Homework #5 20220301 Discrete Mathematics Homework #2

5 comments

Windows 10 / Google Chrome fktszwqkpy
November 25th, 2024 at 02:36 pm

你的文章让我心情愉悦，真是太棒了！ https://www.yonboz.com/video/5472.html

Reply
Windows 10 / Google Chrome qvotizckfk
November 19th, 2024 at 06:32 pm

你的文章让我感受到了生活的美好，谢谢！ http://www.55baobei.com/8IYNzwKMwm.html

Reply
Windows 10 / Google Chrome lsuhtlxknn
November 14th, 2024 at 10:33 pm

你的文章充满了欢乐，让人忍不住一笑。 http://www.55baobei.com/bBrrf4ilAU.html

Reply
Windows 10 / Google Chrome hcdqduferr
November 14th, 2024 at 05:38 pm

你的才华横溢，让人敬佩。 https://www.4006400989.com/qyvideo/6806.html

Reply
Windows 10 / Google Chrome ecuvkreguw
September 27th, 2024 at 12:13 pm

怎么收藏这篇文章？

Reply

Introduction to Machine Learning Homework #2

Bi_Gu • 2023 年 04 月 11 日

# Introduction to Machine Learning

## Homework 2

### Problem 1

(a) Prove that the kernel is symmetric,i.e. $K\left(\textbf{x}_{i}, \textbf{x}_{j}\right)=K\left(\textbf{x}_{j}, \textbf{x}_{i}\right).$

**Solution.**

We have that

$$
K(\textbf{x}_i,\textbf{x}_j)=\left\langle\phi(\textbf{x}_i,\textbf{x}_j)\right\rangle

=\left\langle\phi(\textbf{x}_j,\textbf{x}_i)\right\rangle=K(\textbf{x}_j,\textbf{x}_i).
$$

(b) Assume we use radial basis kernel function $K\left(\textbf{x}_{i},\textbf{x}_{j}\right)=\exp\left(-\frac{1}{2}\left\|\textbf{x}_{i}-\textbf{x}_{j}\right\|^{2}\right)$.

**Solution.**

We have that

$$
\langle\hat{\textbf{w}},\phi(\textbf{x})\rangle+\hat{w}_0=\sum_{i\in SV}y_i\alpha_i K\left(\textbf{x}_i,\textbf{x}\right)+\hat{w}_0=f\left(\textbf{x};\alpha,\hat{w}_0\right),
$$

**Solution.**

Since that the test point $\textbf{x}_{\text{far}}$ is far away from any training instance $\textbf{x}_i$, we have that

$$
\forall i\in SV,\ ||\textbf{x}_{\text{far}}-\textbf{x}_i||\gg 0;
$$

Therefore

### Problem 2

$$
P(X\mid\lambda)=\frac{\lambda^x e^{-\lambda}}{X!}
$$

(a) Show that the sample mean $\hat{\lambda}=\frac{1}{n}\sum_{i=1}^n X_i$ is the maximum likelihood estimate (MLE) of $\lambda$ and it is unbiased $(\mathbb{E}(\hat{\lambda})=\lambda)$.

**Solution.**

**Part A.** First we prove that $\hat{\lambda}$ is the maximum likelihood estimate of $\lambda$:

Since the $n$ data points are i.i.d., we have the likelihood function to be

To find $\mathop{\text{argmax}}\limits_{\lambda}P(\mathcal{D}\mid\lambda)$, it is equivalent to find  $\mathop{\text{argmax}}\limits_{\lambda}\ln\big[P(\mathcal{D}\mid\lambda)\big]$, where

The maximum is at where the first derivative is zero, i.e.

$$
\frac{\partial\ln\mathcal{L}}{\partial\lambda_{\text{max}}}=-N+\frac{1}{\lambda_{\text{max}}}\sum_{i=1}^n X_i=0\Rightarrow
        \lambda_{\text{max}}=\frac{1}{n}\sum_{i=1}^nX_i=\hat{\lambda}
$$

To verify that this is maximum (rather than minimum), we take the second derivative:

$$
\frac{\partial^2\ln\mathcal{L}}{\partial\lambda^2}=\frac{\partial}{\partial\lambda}\left(-N+\frac{1}{\lambda}{\sum_{i=1}^nX_i}\right)=-\frac{1}{\lambda^2}\sum_{i=1}^nX_i<0
$$

which is always negative, so that $\hat{\lambda}$ is the only maximum.

**Part B.** Now we prove that $\hat{\lambda}$ is unbiased:

First we calculate $E[X]$ as follows

Therefore we have that

$$
E[\hat{\lambda}]=E\left[\frac{1}{n}\sum_{i=1}^nX_i\right]=\frac{1}{n}\sum_{i=1}^nE[X_i]=\frac{1}{n}\sum_{i=1}^n\lambda=\lambda.
$$

Which means that $\hat{\lambda}$ is unbiased.

(b) Now let's be Bayesian and put a prior distribution over $\lambda$. Assuming that $\lambda$ follows a Gamma distribution with the parameters $(\alpha,\beta)$, its probability density function:

$$
p(\lambda\mid\alpha,\beta)=\frac{\beta^\alpha}{\Gamma(\alpha)}\lambda^{\alpha-1} e^{-\beta\lambda}
$$

where $\Gamma(\alpha)=(\alpha-1)!$ (here we assume $\alpha$ is a positive integer). Compute the posterior distribution over $\lambda$.

**Solution.**

We calculate the posterior distribution over $\lambda$ as follows:

where $\hat{\alpha}=\alpha+\sum_{i}X_i$ and $\hat{\beta}=\beta+n$.

**Solution.**

Since that

$$
\alpha>1\Rightarrow\hat{\alpha}=\alpha+\sum_{i=1}^nX_i>1
$$

We have the MAP estimation of $\lambda$ to be

$$
\frac{\hat{\alpha}-1}{\hat{\beta}}=\frac{\alpha+\sum_{i=1}^nX_i-1}{\beta+n}.
$$

### Problem 3

Using d-separation on figure 1 to discuss the following questions.
![](https://cdn.dabigu.xyz/cs182_hw2_p0.jpg)(a) Are A and B conditionally independent, given D and F?

**Solution.**

(b) $P(D\mid CEG) =?\ P(D\mid C)$

**Solution.**

Introduction to Machine Learning Homework #2

5 comments

Leave a Comment Cancel reply

《Phigros》游戏记录

使用RD Client实现Windows远程桌面

基于opencv和pyautogui的腾讯会议自动入会

Introduction to Machine Learning Homework #2

Probability and Mathematic Stastics Homework #1

Maths Analysis II - Section 9.1.1

Diary Set #0 20220214

Maths Analysis II - Homework #26 20220531

Math Analysis II - Homework #2 20220217

Maths Analysis II - Homework #8 20220310

Introduction to Machine Learning Homework #2