跳转至

2020级答案

《数据科学与工程数学基础》笔试试卷  2022.9

学院:数据科学与工程学院  考试形式:闭卷  所需时间:120分钟

考生姓名:_  学号:_  专业:__  任课教师:黄定江

题目 总分
满分 14 12 13 13 13 12 12 11 100
得分
阅卷人

一、(14分)

已知矩阵

\[\boldsymbol{M} = \begin{pmatrix} 1 & 0 \\ -2 & 3 \\ 0 & 1 \end{pmatrix}\]

(1) 计算矩阵 \(\boldsymbol{M}\)\(1\) 范数;

(2) 计算矩阵 \(\boldsymbol{M}\)\(2\) 范数;

(3) 证明:对任意 \(\boldsymbol{A}\in\mathbb{R}^{m\times n}\),由

\[\|\boldsymbol{A}\|_{m_\infty} := \max_{1\leq i\leq m,1\leq j\leq n}|a_{ij}|\]

定义的 \(\|\cdot\|_{m_\infty}\)\(\mathbb{R}^{m\times n}\) 上的(广义)矩阵范数。

答案

(1)

\(\|\boldsymbol{M}\|_1=\max\{1+|-2|,3+1\}=4\) (3分)

(2)\(\boldsymbol{M}^\top \boldsymbol{M}=\begin{pmatrix}2&2\\2&4\end{pmatrix}\)

\(\lambda_{max}(\boldsymbol{M}^\top \boldsymbol{M})=14\)

\(\|\boldsymbol{M}\|_2=\sqrt{14}\) (4分)

(3)非负性:显然

\[\|\boldsymbol{A}\|_{m_\infty} := \max_{1\leq i\leq m,1\leq j\leq n}|a_{ij}| \geq 0\]

而且仅当 \(\boldsymbol{A}=0\) 时,\(\|\boldsymbol{A}\|_{m_\infty}=0\)(2分)

齐次性:

\[\|c \cdot \boldsymbol{A}\|_{m_\infty} := \max_{1\leq i\leq m,1\leq j\leq n}|c \cdot a_{ij}| = c \max_{1\leq i\leq m,1\leq j\leq n}|a_{ij}| = c\|\boldsymbol{A}\|_{m_\infty}\]

(2分)

三角不等式:考虑 \(\|\boldsymbol{A} + \boldsymbol{B}\|_{m_\infty}\),因为

\[|a_{ij} + b_{ij}| \leq |a_{ij}| + |b_{ij}| \leq \max_{1\leq i\leq m,1\leq j\leq n}|a_{ij}| + \max_{1\leq i\leq m,1\leq j\leq n}|b_{ij}|\]

所以

\[\max_{1\leq i\leq m,1\leq j\leq n} |a_{ij} + b_{ij}| \leq \max_{1\leq i\leq m,1\leq j\leq n}|a_{ij}| + \max_{1\leq i\leq m,1\leq j\leq n}|b_{ij}|\]

\(\|\boldsymbol{A} + \boldsymbol{B}\|_{m_\infty} \leq \|\boldsymbol{A}\|_{m_\infty} + \|\boldsymbol{B}\|_{m_\infty}\) (3分)


二、(12分)

已知矩阵

\[\boldsymbol{M} = \begin{pmatrix} 1 & -1 & 0 \\ 2 & 4 & 1 \\ 4 & 2 & 1 \end{pmatrix}\]

(1) 求矩阵 \(\boldsymbol{M}\) 的零空间;

(2) 求向量 \(\boldsymbol{x}=(1,1,1)^{\top}\) 在矩阵 \(\boldsymbol{M}\) 的列空间上的正交投影;

(3) 利用Householder变换,将非零向量 \(\boldsymbol{x}=(1,1,1)^{\top}\) 变为标准向量 \(\boldsymbol{e}_1=(0,1,0)^{\top}\)\(\sqrt{3}\) 倍,请写出这个Householder变换矩阵。

答案

(1)零空间为 \(span\{(1,1,-6)^T\}\) (3分)

(2)列空间为 \(span\{(1,2,4)^T,(-1,4,2)^T\}\),若记

\[\boldsymbol{A} = \begin{pmatrix} 1 & -1 \\ 2 & 4 \\ 4 & 2 \end{pmatrix}\]

故正交投影为 \(\boldsymbol{A}(\boldsymbol{A}^\top \boldsymbol{A})^{-1} \boldsymbol{A}^\top \boldsymbol{x} = (1/3,2/3,4/3)^\top\) (4分)

(3)

\[w=\frac{x-\alpha e_{1}}{\|x-\alpha e_{1}\|_{2}}\]

则,由 \(H = (I-2ww^{\top})\) 可得:

\[\boldsymbol{H} = \begin{pmatrix} \frac{2-\sqrt{3}}{3-\sqrt{3}} & \frac{1}{\sqrt{3}} & -\frac{1}{3-\sqrt{3}} \\ \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{3}} \\ -\frac{1}{3-\sqrt{3}} & \frac{1}{\sqrt{3}} & \frac{2-\sqrt{3}}{3-\sqrt{3}} \end{pmatrix}\]

(5分)


三、(13分)

矩阵

\[\boldsymbol{A} = \begin{pmatrix} 3 & 2 & 2 \\ 2 & 3 & -2 \end{pmatrix}\]

(1) 计算矩阵 \(\boldsymbol{A}\) 的SVD分解;

(2) 假设 \(\boldsymbol{B}\) 是一个 \(n \times d\) 的矩阵,矩阵 \(\boldsymbol{M}\)\((n+d) \times (n+d)\) 定义为

\[\boldsymbol{M}=\begin{pmatrix} \boldsymbol{O} & \boldsymbol{B}^\top \\ \boldsymbol{B} & \boldsymbol{O} \end{pmatrix}\]

显然 \(\boldsymbol{M}\) 是对称矩阵。请证明矩阵 \(\boldsymbol{M}\) 的对角化会产生 \(\boldsymbol{B}\) 的奇异值分解所需要的所有信息。

答案

(1)易计算

\[\boldsymbol{A}\boldsymbol{A}^\top=\begin{pmatrix} 17 & 8 \\ 8 & 17 \end{pmatrix}\]

求得其特征值为 \(25,9\)。对应的特征向量分别为 \((1/\sqrt{2},1/\sqrt{2})^\top, (-1/\sqrt{2},1/\sqrt{2})^\top\),因此,

\[\boldsymbol{U} =\begin{pmatrix} 1/\sqrt{2} & -1/\sqrt{2} \\ 1/\sqrt{2} & 1/\sqrt{2} \end{pmatrix}\]

(4分)

\(\boldsymbol{A}^\top \boldsymbol{U}\)\(\boldsymbol{V}\) 的关系可直接计算出

\[\boldsymbol{V} =\begin{pmatrix} 1/\sqrt{2} & -1/3\sqrt{2} & -2/3 \\ 1/\sqrt{2} & 1/3\sqrt{2} & 2/3 \\ 0 & -4/3\sqrt{2} & 1/3 \end{pmatrix}\]

(3分)

(2)\(\boldsymbol{B}\) 的奇异值分解所需要的信息为 \(\boldsymbol{B}^T \boldsymbol{B}\) 的特征向量和 \(\boldsymbol{B}\boldsymbol{B}^T\) 的特征向量,以及对应的特征值。现假设对应于特征值为 \(\lambda^2(\lambda>0)\)\(\boldsymbol{B}^T \boldsymbol{B}\) 的特征向量为 \(\boldsymbol{x}_1(\|\boldsymbol{x}_1\|_2=1)\)\(\boldsymbol{B}\boldsymbol{B}^T\) 的特征向量为 \(\boldsymbol{x}_2(\|\boldsymbol{x}_2\|_2=1)\)。因此,\(\boldsymbol{B}^T \boldsymbol{B}\boldsymbol{x}_1 = \lambda^2 \boldsymbol{x}_1\) 以及 \(\boldsymbol{B}\boldsymbol{B}^T \boldsymbol{x}_2 = \lambda^2 \boldsymbol{x}_2\)。故

\[(\boldsymbol{B}\boldsymbol{B}^T)\boldsymbol{B}\boldsymbol{x}_1 = \lambda^2 \boldsymbol{B}\boldsymbol{x}_1\]

所以存在 \(k\) 使得 \(\boldsymbol{B}\boldsymbol{x}_1=k\boldsymbol{x}_2\)。由于 \(\|\boldsymbol{x}_1\|_2=\|\boldsymbol{x}_2\|_2=1\),可得 \(k=\lambda\),即 \(\boldsymbol{B}\boldsymbol{x}_1 = \lambda \boldsymbol{x}_2\)。同理有 \(\boldsymbol{B}^T \boldsymbol{x}_2 = \lambda \boldsymbol{x}_1\)(3分)

下面证明 \(\boldsymbol{x}=\begin{pmatrix} \boldsymbol{x}_1 \\ \boldsymbol{x}_2 \end{pmatrix}\) 是矩阵 \(\boldsymbol{M}\) 的特征值为 \(\lambda\) 的特征向量。易计算

\[\boldsymbol{M}\boldsymbol{x} = \begin{pmatrix} 0 & \boldsymbol{B}^\top \\ \boldsymbol{B} & 0 \end{pmatrix} \begin{pmatrix} \boldsymbol{x}_1 \\ \boldsymbol{x}_2 \end{pmatrix}= \begin{pmatrix} \boldsymbol{B}^T \boldsymbol{x}_2 \\ \boldsymbol{B}\boldsymbol{x}_1 \end{pmatrix} =\lambda \begin{pmatrix} \boldsymbol{x}_1 \\ \boldsymbol{x}_2 \end{pmatrix}\]

因此,\(\boldsymbol{B}\) 的奇异值分解信息包含在 \(\boldsymbol{M}\) 的对角化过程中。 (3分)


四、(13分)

完成下列函数求导或梯度:

(1) 求激活函数 \(\sigma(x)=\dfrac{1}{1+e^{-x}}\) 的导数;

(2) 求函数 \(f(\boldsymbol{X}) = \operatorname{Tr}(\boldsymbol{X}^{-1})\)\(\boldsymbol{X}\) 的梯度,其中 \(\boldsymbol{X} \in \mathbb{R}^{m\times n}\)

(3) 若非奇异矩阵 \(\boldsymbol{A} \in \mathbb{R}^{n \times n}\)\(\boldsymbol{x} \in \mathbb{R}^{n \times 1}\)\(\boldsymbol{y} \in \mathbb{R}^{n \times 1}\),求函数 \(f(\boldsymbol{A}) = \boldsymbol{y}^\top \boldsymbol{A}^{-1} \boldsymbol{x}\)\(\boldsymbol{A}\) 的梯度。

答案

(1)\(\sigma'(x)=\dfrac{e^{-x}}{(1+e^{-x})^2}=\sigma(x)(1-\sigma(x))\) (4分)

(2)因为

\[ \begin{aligned} 0=dI=d(\boldsymbol{X}\boldsymbol{X}^{-1})&= d\boldsymbol{X}\boldsymbol{X}^{-1}+\boldsymbol{X}d\boldsymbol{X}^{-1}\\ \boldsymbol{X}d\boldsymbol{X}^{-1}&=-d\boldsymbol{X}\boldsymbol{X}^{-1}\\ d\boldsymbol{X}^{-1}&=-\boldsymbol{X}^{-1}d\boldsymbol{X}\boldsymbol{X}^{-1} \end{aligned} \]

所以

\[ \begin{aligned} d\operatorname{Tr}(\boldsymbol{X}^{-1}) &= \operatorname{Tr}(d\boldsymbol{X}^{-1})\\ &= \operatorname{Tr}(-\boldsymbol{X}^{-1}d\boldsymbol{X}\boldsymbol{X}^{-1})\\ &= \operatorname{Tr}(-(\boldsymbol{X}^{-1})^{2}d\boldsymbol{X}) \end{aligned} \]

\[ \begin{aligned} \frac{\partial \operatorname{Tr}(\boldsymbol{X}^{-1})}{\partial \boldsymbol{X}} = -(\boldsymbol{X}^{-T})^{2} \end{aligned} \]

(5分)

(3)

\[ \begin{aligned} df(\boldsymbol{A}) &= \operatorname{Tr}(d\boldsymbol{y}^\top \boldsymbol{A}^{-1}\boldsymbol{x})\\ &= \operatorname{Tr}(\boldsymbol{y}^\top d\boldsymbol{A}^{-1}\boldsymbol{x})\\ &= \operatorname{Tr}(-\boldsymbol{y}^\top \boldsymbol{A}^{-1}d\boldsymbol{A}\boldsymbol{A}^{-1}\boldsymbol{x})\\ &= \operatorname{Tr}(-\boldsymbol{A}^{-1}\boldsymbol{x}\boldsymbol{y}^\top \boldsymbol{A}^{-1}d\boldsymbol{A}) \end{aligned} \]

同理,求得其梯度。 (4分)


五、(13分)

计算和证明以下问题:

(1) 同时抛2颗骰子,事件 \(A,B,C\) 分别表示为

(A) 仅有一个骰子是3

(B) 至少一个骰子是4

(C) 骰子上点数总和为7

试计算事件 \(A,B,C\) 发生后所提供的信息量;

(2) 证明联合熵和条件熵有如下关系:

\[H(X,Y) = H(X) + H(Y\mid X)\]

答案

(1)\(H_A=-\log \dfrac{5}{18}\)\(H_B=-\log \dfrac{1}{6}\)\(H_C=-\log \dfrac{1}{2}\) (6分)

(2)

\[ \begin{aligned} H(X,Y)&=\mathbb{E}(\log\frac{1}{p(xy)})\\ &=\mathbb{E}(\log\frac{1}{p(x)p(y|x)})\\ &=\mathbb{E}(\log\frac{1}{p(x)}+\log\frac{1}{p(y|x)})\\ &=\mathbb{E}(\log\frac{1}{p(x)})+\mathbb{E}(\log\frac{1}{p(y|x)})\\ &=H(X)+H(Y|X) \end{aligned} \]

(7分)


六、(12分)

求解以下问题:

(1) 假设总体 \(X \sim N\left(\mu, \sigma_0^{2}\right)\)\(\sigma_0^{2}\) 已知),\(X_{1}, X_{2}, \ldots, X_{n}\) 为来自总体 \(X\) 的样本,由过去的经验和知识,我们可以确定 \(\mu\) 的取值比较集中在 \(\hat{\mu}\) 附近,离 \(\hat{\mu}\) 越远,\(\mu\) 取值的可能性越小,于是我们假定 \(\mu\) 的先验分布为正态分布

\[\pi(\mu)=\frac{1}{\sqrt{2 \pi \hat{\sigma}^{2}}} \exp \left[-\frac{1}{2 \hat{\sigma}^{2}}\left(\mu-\hat{\mu}\right)^{2}\right] \quad (\hat{\mu}, \hat{\sigma} \text{已知})\]

\(\mu\) 的后验概率分布。

(2) 假设总体 \(X \sim P(\lambda)\)\(X_{1}, X_{2}, \ldots, X_{n}\) 为来自总体 \(X\) 的样本,假定 \(\lambda\) 的先验分布为伽玛分布 \(\Gamma(\alpha, \beta)\),求 \(\lambda\) 的后验期望估计(泊松分布的分布律:\(P(X=k) = \frac{e^{-\lambda} \lambda^k}{k!}\),泊松分布的期望为 \(\lambda\);伽马分布的概率密度函数:\(f(x ; \alpha, \beta)=\frac{x^{\alpha-1} e^{-\beta x} \beta^{\alpha}}{\Gamma(\alpha)}\),伽马分布的期望为 \(\alpha/\beta\))。

答案

(1)样本分布密度为

\[ q(\mathbf{x} \mid \mu)=\frac{1}{\sigma_0^{n}(2 \pi)^{n / 2}} \exp \left[-\frac{1}{2 \sigma_0^{2}} \sum_{i=1}^{n}\left(x_{i}-\mu\right)^{2}\right] \]

于是后验密度函数为

\[ h(\mu \mid \mathbf{x})=\frac{q(\mathbf{x} \mid \mu) \cdot \pi(\mu)}{f_{\mathbf{x}}(\mathbf{x})}=\frac{q(\mathbf{x} \mid \mu) \cdot \pi(\mu)}{\int_{-\infty}^{+\infty} q(\mathbf{x} \mid \mu) \cdot \pi(\mu) d \mu} \]
\[ \propto \exp \left[-\frac{1}{2 \sigma_0^{2}} \sum_{i=1}^{n}\left(x_{i}-\mu\right)^{2}\right] \cdot \exp \left[-\frac{1}{2 \hat{\sigma}^{2}}\left(\mu-\hat{\mu}\right)^{2}\right] \]

化简得

\[ h(\mu \mid \mathbf{x}) \propto \exp \left[-\frac{(\mu-t)^{2}}{2 \eta^{2}}\right] \]

其中 \(t=\dfrac{\frac{n}{\sigma_0^{2}} \bar{x}+\frac{1}{\sigma_{\mu}^{2}} \hat{\mu}}{\frac{n}{\sigma_0^{2}}+\frac{1}{\hat{\sigma}^{2}}}\)

\(\eta^{2}=\dfrac{1}{\frac{n}{\sigma_0^{2}}+\frac{1}{\sigma_{\mu}^{2}}}\),于是

\[ \mu \mid \mathbf{x} \sim N\left(\frac{\frac{n}{\sigma_0^{2}} \bar{x}+\frac{1}{\sigma_{\mu}^{2}} \hat{\mu}}{\frac{n}{\sigma_0^{2}}+\frac{1}{\hat{\sigma}^{2}}}, \frac{1}{\frac{n}{\sigma_0^{2}}+\frac{1}{\sigma_{\mu}^{2}}}\right) \]

(6分)

(2)因为 \(\lambda\) 的先验密度函数 \(\pi(\lambda)\) 为伽玛分布 \(\Gamma(\alpha, \beta)\),即

\[ \pi(\lambda) \propto \lambda^{\alpha-1} e^{-\beta \lambda} \]

样本分布密度函数为:

\[ q(\mathbf{x} \mid \lambda)=\frac{\lambda^{\sum_{i=1}^{n} x_{i}}}{x_{1} ! x_{2} ! \ldots x_{n} !} e^{-n \lambda} \propto \lambda^{\sum_{i=1}^{n} x_{i}} e^{-n \lambda} \]

所以

\[ h(\lambda \mid \mathbf{x}) \propto \lambda^{\alpha+\sum_{i=1}^{n} x_{i}-1} e^{-(\beta+n) \lambda} \]

\[ \lambda \mid \mathbf{x} \sim \Gamma\left(\alpha+\sum_{i=1}^{n} x_{i}, \beta+n\right) \]

\(\lambda\) 的后验期望估计为

\[ \hat{\lambda}=\frac{\alpha+\sum_{i=1}^{n} x_{i}}{\beta+n}=\frac{n}{\beta+n} \bar{x}+\frac{\beta}{\beta+n} \frac{\alpha}{\beta} \]

它是样本均值 \(\bar{x}\) 和先验分布 \(\Gamma(\alpha, \beta)\) 的均值 \(\frac{\alpha}{\beta}\) 的加权平均。 (6分)


七、(12分)

求证下列与凸集或凸函数相关的问题:

(1) 证明:设 \(f: \mathbb{R}^{n} \rightarrow \mathbb{R}^{m}\) 是仿射变换,即 \(f(\boldsymbol{x})=\boldsymbol{A}\boldsymbol{x}+\boldsymbol{b}\)\(\boldsymbol{A} \in \mathbb{R}^{m \times n}\)\(\boldsymbol{b} \in \mathbb{R}^{m}\),则凸集在 \(f\) 下的像是凸集:

\[S \subseteq \mathbb{R}^{n} \text{ 为凸集} \Rightarrow f(S) \stackrel{\text{def}}{=}\{f(\boldsymbol{x}) \mid \boldsymbol{x} \in S\} \text{ 为凸集}\]

(2) 判定函数 \(f(x)=\max(\|\boldsymbol{A}\boldsymbol{x}+\boldsymbol{b}\|_2,\|\boldsymbol{x}^\top \boldsymbol{x}\|_1)\)\(\boldsymbol{A}\in \mathbb{R}^{m\times n}, \boldsymbol{x}\in \mathbb{R}^{n}, \boldsymbol{b}\in \mathbb{R}^m\) 是否为凸函数,并说明理由。

答案

(1)令 \(\boldsymbol{y}_1, \boldsymbol{y}_2\) 表示在像集合中的任意两个点,它们的原象分别为 \(\boldsymbol{x}_1, \boldsymbol{x}_2\)。因此,

\(\boldsymbol{y}_1=\boldsymbol{A}\boldsymbol{x}_1+\boldsymbol{b}\)

\(\boldsymbol{y}_2=\boldsymbol{A}\boldsymbol{x}_2+\boldsymbol{b}\)

因此,有

\[(1-\lambda)\boldsymbol{y}_1+\lambda\boldsymbol{y}_2=\boldsymbol{A}((1-\lambda)\boldsymbol{x}_1 + \lambda \boldsymbol{x}_2)+\boldsymbol{b}\]

故得证。 (6分)

(2)由仿射函数的任意范数为凸函数可知 \(\|\boldsymbol{A}\boldsymbol{x}+\boldsymbol{b}\|_2\) 为凸函数,另外 \(\|\boldsymbol{x}^\top \boldsymbol{x}\|_1\) 为欧几里得范数的平方,显然为凸函数。根据逐点取最大值具有保凸性,可知 \(f(x)\) 是凸函数。 (6分)


八、(11分)

考虑优化问题

\[\min_{\boldsymbol{x}} \boldsymbol{x}^{\mathrm{T}} \boldsymbol{W} \boldsymbol{x}\]

其中 \(\boldsymbol{W} \in S_+^{n}\) 是对称半正定矩阵。

(1) 求出在任意点 \(\boldsymbol{x} = (x_1,x_2,\cdots,x_n)^\top\) 处沿负梯度方向迭代的最佳步长 \(\alpha\)

(2) 若对上述优化问题增加约束条件

\[x_{i}^{2}=1, \quad i=1, \cdots, n\]

请写出此时约束优化问题的拉格朗日函数 \(L(\boldsymbol{x},\boldsymbol{\lambda})\),并计算出约束优化问题的拉格朗日对偶函数。

答案

(1)可求得 \(f(\boldsymbol{x}) = \boldsymbol{x}^{\mathrm{T}} \boldsymbol{W} \boldsymbol{x}\) 的梯度为 \(2\boldsymbol{W}\boldsymbol{x}\)。因此,为寻求得最佳步长,需求解

\[ \min_{\boldsymbol{x}} (\boldsymbol{x} - 2\alpha \boldsymbol{W}\boldsymbol{x})^{\mathrm{T}} \boldsymbol{W}(\boldsymbol{x} - 2\alpha \boldsymbol{W}\boldsymbol{x}) \]

(2分)

求极值可得:

\[\alpha = \frac{\boldsymbol{x}^\top \boldsymbol{W}^2 \boldsymbol{x}}{2\boldsymbol{x}^\top \boldsymbol{W}^3 \boldsymbol{x}}\]

(3分)

(2)若增加约束条件,可得Lagrange函数为

\[ L(\boldsymbol{x}, \boldsymbol{\nu})=\boldsymbol{x}^{\mathrm{T}} \boldsymbol{W} \boldsymbol{x}+\sum_{i=1}^n \nu_i\left(x_i^2-1\right) \]
\[ =\boldsymbol{x}^{\mathrm{T}}(\boldsymbol{W}+\operatorname{diag}(\boldsymbol{\nu})) \boldsymbol{x}-\mathbf{1}^{\mathrm{T}} \boldsymbol{\nu} \]

(3分)

\(\boldsymbol{x}\) 求极小得到Lagrange对偶函数

\[ \begin{aligned} g(\boldsymbol{\nu}) &=\inf _{\boldsymbol{x}} \boldsymbol{x}^{\mathrm{T}}(\boldsymbol{W}+\operatorname{diag}(\boldsymbol{\nu})) \boldsymbol{x}-\mathbf{1}^{\mathrm{T}} \boldsymbol{\nu} \\ &= \begin{cases}-\mathbf{1}^{\mathrm{T}} \boldsymbol{\nu} & \boldsymbol{W}+\operatorname{diag}(\boldsymbol{\nu}) \succeq \mathbf{0} \\ -\infty & \text{其他情况}\end{cases} \end{aligned} \]

(3分)