2018S2

Problem 1

Consider solving numerically a system of first-order linear ordinary differential equations

$$\frac{\mathrm{d}{x}_i}{\mathrm{d}t}(t)=\sum _{j=1}^n{a}_{i,j}(t)x_j(t),t\ge 0\text{\hspace{1em}(dagger)}$$

on a set of $n$ real functions of a real independent variable $t$,

$$x_i(t),i=1,2,\cdots ,n,$$

where $a_{i,j}(t)$ is the $i,j$ component of an $n\times n$ coefficient matrix $\mathbf{A}(t)$. Let $h>0$ be the step size used in the numerical methods. Suppose that the numerical solution is computed from initial values

$$x_i(0)\in \mathbb{R},i=1,2,\cdots ,n.$$

Assume that matrix $\mathbf{A}(t)$ has $n$ distinct eigenvalues for any $t$. Answer the following questions.

1. Suppose that $\mathbf{A}(t)$ is a constant matrix ${\mathbf{A}}_0$, which is independent of $t$. Answer a necessary and sufficient condition for the eigenvalues of ${\mathbf{A}}_0$ to satisfy

$$\forall i=1,2,\cdots ,n,\underset{t\to \infty }{\lim }{x}_i(t)=0,$$

for any initial value.

2. Answer a recurrence formula to solve Eq. ($†$) by the forward Euler method. In addition, express the order of the local truncation error by big O notation of the step size $h$.

3. Suppose that Eq. ($†$) is solved by the forward Euler method. The obtained approximation of $x_i(kh)$ is expressed as $X_i(k)$, where $k$ is a non-negative integer to express the step number of the method. Suppose that $\mathbf{A}(t)$ is a constant matrix ${\mathbf{A}}_0$, which is independent of $t$. Answer a necessary and sufficient condition for the eigenvalues of ${\mathbf{A}}_0$ to satisfy

$$\forall i=1,2,\cdots ,n,\underset{k\to \infty }{\lim }{X}_i(k)=0,$$

for any initial value.

4. Give an advantage of the backward Euler method compared to the forward Euler method with a brief explanation.

5. Compare the computational complexity of one step to solve Eq. ($†$) by the forward Euler method with that by the backward Euler method, by using big O notation of $n$. Assume that the computational complexity to read each $a_{i,j}(t)$ is $O(1)$.

---

考虑对一个一阶线性常微分方程组进行数值求解：

$$\frac{\mathrm{d}{x}_i}{\mathrm{d}t}(t)=\sum _{j=1}^n{a}_{i,j}(t)x_j(t),t\ge 0\text{\hspace{1em}(dagger)}$$

在一组关于实数独立变量 $t$ 的 $n$ 个实函数上，

$$x_i(t),i=1,2,\cdots ,n,$$

其中 $a_{i,j}(t)$ 是 $n\times n$ 系数矩阵 $\mathbf{A}(t)$ 的 $i,j$ 分量。令 $h>0$ 为数值方法中使用的步长。假设数值解是从初始值

$$x_i(0)\in \mathbb{R},i=1,2,\cdots ,n.$$

计算得出的。假设矩阵 $\mathbf{A}(t)$ 对于任何 $t$ 都有 $n$ 个不同的特征值。回答以下问题。

1. 假设 $\mathbf{A}(t)$ 是与 $t$ 无关的常数矩阵 ${\mathbf{A}}_0$。回答 ${\mathbf{A}}_0$ 的特征值满足

$$\forall i=1,2,\cdots ,n,\underset{t\to \infty }{\lim }{x}_i(t)=0,$$

的必要和充分条件。

2. 用前向欧拉法回答求解方程 ($†$) 的递推公式。此外，用大 O 记号表示步长 $h$ 的局部截断误差的阶数。

3. 假设用前向欧拉法求解方程 ($†$)。所得的 $x_i(kh)$ 的近似值表示为 $X_i(k)$，其中 $k$ 是表示方法的步数的非负整数。假设 $\mathbf{A}(t)$ 是与 $t$ 无关的常数矩阵 ${\mathbf{A}}_0$。回答 ${\mathbf{A}}_0$ 的特征值满足

$$\forall i=1,2,\cdots ,n,\underset{k\to \infty }{\lim }{X}_i(k)=0,$$

的必要和充分条件。

4. 简要说明后向欧拉法相比前向欧拉法的一个优势。

5. 比较用大 O 记号表示的，前向欧拉法和后向欧拉法求解方程 ($†$) 的一步计算复杂度。假设读取每个 $a_{i,j}(t)$ 的计算复杂度为 $O(1)$。

---

Problem 2

Let $V$ be a finite set of symbols denoting variables, $F_0$ a finite set of constant symbols, $F_2$ a finite set of binary function symbols, and $T$ the set of terms constructed from symbols in $V$, $F_0$, and $F_2$. Let $G$ be a finite set of rewrite rules of the form $x\to c$ or of the form $x\to f(y,z)$, where $x,y,z\in V$, $c\in F_0$ and $f\in F_2$, and each $x\in V$ appears in the left-hand side of exactly one rewrite rule in $G$. For $\alpha ,\beta \in T$, the relation $\alpha \Rightarrow \beta$ is defined as follows:

$$\beta \text{ is obtained by applying a rule }x\to \gamma (\gamma \text{ is }c\text{ or }f(y,z))\text{ in }G\text{ to one occurrence of }x\in V\text{ in }\alpha \text{ and replacing the occurrence with }\gamma .$$

The relation ${\Rightarrow }^{\ast }$ is defined as the reflexive and transitive closure of $\Rightarrow$, and the relation ${\leftrightarrow }^{\ast }$ is defined as the reflexive, transitive and symmetric closure of $\Rightarrow$.

Answer the following questions.

1. Show that if $\alpha ,\beta \in T$ and $\alpha {\leftrightarrow }^{\ast }\beta$, then there exists $\delta \in T$ such that $\alpha {\Rightarrow }^{\ast }\delta$ and $\beta {\Rightarrow }^{\ast }\delta$.

2. Give an algorithm that judges $\alpha {\leftrightarrow }^{\ast }\beta$ for $\alpha ,\beta \in T$, and explain its correctness.

For $\alpha \in T$ and $w\in \{L,R{\}}^{\ast }$, the operation $\alpha .w\in T$ that extracts a sub term of $\alpha$ is inductively defined as follows:

$$\alpha .ϵ=\alpha$$ $$\alpha .Lw=\{\begin{array}{ll}{\alpha }_1.w& \text{if }\alpha =f({\alpha }_1,{\alpha }_2)\\ \text{undefined}& \text{otherwise}\end{array}$$ $$\alpha .Rw=\{\begin{array}{ll}{\alpha }_2.w& \text{if }\alpha =f({\alpha }_1,{\alpha }_2)\\ \text{undefined}& \text{otherwise}\end{array}$$

Here $ϵ$ is an empty word. For $\alpha ,\beta \in T$, the relation $\alpha \approx \beta$ is then defined as follows:

$$\text{for any }{\alpha }^{\prime },{\beta }^{\prime }\in T\text{ and }w\in \{L,R{\}}^{\ast },\text{ if }\alpha {\leftrightarrow }^{\ast }{\alpha }^{\prime }\text{ and }\beta {\leftrightarrow }^{\ast }{\beta }^{\prime },\text{ and }{\alpha }^{\prime }.w\text{ and }{\beta }^{\prime }.w\text{ are both defined and their first symbols belong to }{F}_0\cup F_2,\text{ then those symbols are identical.}$$

Answer the following question:

3. Give an algorithm that judges $\alpha \approx \beta$ for $\alpha ,\beta \in T$, and explain its correctness.

---

设 $V$ 为表示变量的有限符号集，$F_0$ 为有限常量符号集，$F_2$ 为二元函数符号的有限集，$T$ 为由 $V$、$F_0$ 和 $F_2$ 中的符号构成的项的集合。设 $G$ 为重写规则的有限集合，形式为 $x\to c$ 或 $x\to f(y,z)$，其中 $x,y,z\in V$，$c\in F_0$，$f\in F_2$，且每个 $x\in V$ 仅出现在一个重写规则的左侧。对于 $\alpha ,\beta \in T$，关系 $\alpha \Rightarrow \beta$ 定义如下：

$$\beta \text{ 是通过在 }G\text{ 中应用规则 }x\to \gamma (\gamma \text{ 是 }c\text{ 或 }f(y,z))\text{ 到 }\alpha \text{ 中的一个 }x\in V\text{ 发生的，并用 }\gamma \text{ 替换出现的 }x。$$

关系 ${\Rightarrow }^{\ast }$ 定义为 $\Rightarrow$ 的自反和传递闭包，关系 ${\leftrightarrow }^{\ast }$ 定义为 $\Rightarrow$ 的自反、传递和对称闭包。

回答以下问题。

1. 证明如果 $\alpha ,\beta \in T$ 且 $\alpha {\leftrightarrow }^{\ast }\beta$，那么存在 $\delta \in T$ 使得 $\alpha {\Rightarrow }^{\ast }\delta$ 且 $\beta {\Rightarrow }^{\ast }\delta$。

2. 给出一个算法来判断 $\alpha {\leftrightarrow }^{\ast }\beta$ 对于 $\alpha ,\beta \in T$，并解释其正确性。

对于 $\alpha \in T$ 和 $w\in \{L,R{\}}^{\ast }$，运算 $\alpha .w\in T$ 提取 $\alpha$ 的子项，其递归定义如下：

$$\alpha .ϵ=\alpha$$ $$\alpha .Lw=\{\begin{array}{ll}{\alpha }_1.w& \text{如果 }\alpha =f({\alpha }_1,{\alpha }_2)\\ \text{未定义}& \text{否则}\end{array}$$ $$\alpha .Rw=\{\begin{array}{ll}{\alpha }_2.w& \text{如果 }\alpha =f({\alpha }_1,{\alpha }_2)\\ \text{未定义}& \text{否则}\end{array}$$

这里 $ϵ$ 是空字。对于 $\alpha ,\beta \in T$，关系 $\alpha \approx \beta$ 定义如下：

$$\text{对于任意 }{\alpha }^{\prime },{\beta }^{\prime }\in T\text{ 和 }w\in \{L,R{\}}^{\ast },\text{如果 }\alpha {\leftrightarrow }^{\ast }{\alpha }^{\prime }\text{ 和 }\beta {\leftrightarrow }^{\ast }{\beta }^{\prime }，\text{并且}{\alpha }^{\prime }.w\text{和}{\beta }^{\prime }.w\text{都已定义且其首符号属于}{F}_0\cup F_2,\text{那么这些符号是相同的。}$$

回答以下问题：

3. 给出一个算法来判断 $\alpha \approx \beta$ 对于 $\alpha ,\beta \in T$，并解释其正确性。

---

Problem 3

Let $L(v)$ denote the set of leaves in the descendants of node $v$ in a tree, and let $p(v,w)$ denote the number of edges of the simple path from node $v$ to node $w$. For a non-leaf node $v$, ${\max }_{w\in L(v)}p(v,w)$ is called the height of $v$. Let the height of a leaf be $0$. The height of the root of a tree is called the height of the tree.

Here, we have a binary tree $T_n$ with height $n\ge 0$, in which each node $v$ must have one of the following properties.

• $v$ is a leaf.
• $v$ has only one child, and the height of $v$ is $1$.
• $v$ has two children, and the heights of the two children of $v$ differ by $1$.

Let $N_n$ denote the number of nodes in $T_n$ for $n\ge 0$. Let $r=\frac{1+\sqrt{5}}{2}$. Answer the following questions.

1. Calculate $N_5$.

2. Express $N_n$ in terms of $N_{n-1}$ and $N_{n-2}$ for $n\ge 2$.

3. Prove that $N_n\ge r^n$ for every $n\ge 0$.

4. Prove that $N_n\le r^{n+2}$ for every $n\ge 0$.

5. Consider the problem of assigning each of given $N_n$ integers to a distinct node of $T_n$. The integer assigned to each node $v$ must be no smaller than any of the integers assigned to $v$‘s children. Show an $O(r^n)$ algorithm that computes such an assignment, with a proof that the algorithm runs indeed in $O(r^n)$ time. Note that the $N_n$ integers may not be sorted in the input.

---

设 $L(v)$ 表示树中节点 $v$ 的后代中的叶子集合，$p(v,w)$ 表示从节点 $v$ 到节点 $w$ 的简单路径的边数。对于非叶子节点 $v$，${\max }_{w\in L(v)}p(v,w)$ 称为 $v$ 的高度。令叶子的高度为 $0$。树根的高度称为树的高度。

在此，我们有一个高度为 $n\ge 0$ 的二叉树 $T_n$，其中每个节点 $v$ 必须具有以下属性之一。

• $v$ 是一个叶子。
• $v$ 只有一个孩子，且 $v$ 的高度为 $1$。
• $v$ 有两个孩子，并且 $v$ 的两个孩子的高度相差 $1$。

令 $N_n$ 表示 $T_n$ 中的节点数，对于 $n\ge 0$。令 $r=\frac{1+\sqrt{5}}{2}$。回答以下问题。

1. 计算 $N_5$。

2. 用 $N_{n-1}$ 和 $N_{n-2}$ 表示 $N_n$ 对于 $n\ge 2$。

3. 证明 $N_n\ge r^n$ 对于每个 $n\ge 0$。

4. 证明 $N_n\le r^{n+2}$ 对于每个 $n\ge 0$。

5. 考虑将给定的 $N_n$ 个整数分配给 $T_n$ 的不同节点的问题。分配给每个节点 $v$ 的整数必须不小于分配给 $v$ 的孩子的任何整数。给出一个 $O(r^n)$ 算法来计算这样的分配，并证明该算法确实在 $O(r^n)$ 时间内运行。注意，输入中的 $N_n$ 个整数可能没有排序。

---

Problem 4

Answer the following questions regarding cache memory of a microprocessor with 32-bit memory-addressing.

1. Consider cache memory with a capacity of $2^{15}$ bytes and a block size of 64 bytes. The cache memory uses a full associative scheme, a two-way set-associative scheme, or a direct mapping scheme. For each of those schemes, obtain the bit length for each of a tag, an index, and an offset.

2. Consider cache memory with a capacity of 64 bytes and a block size of 8 bytes. Obtain the number of cache hits, when the hexadecimal memory addresses below are accessed by 4-byte read operations in this order, in case that the cache memory uses a full associative scheme, a two-way set-associative scheme, and a direct mapping scheme, respectively. Assume that the cache memory is empty at the beginning, and the cache block is replaced based on the LRU (Least Recently Used) algorithm.

   0x20, 0x48, 0x40, 0x4C, 0x58, 0x80, 0xB8, 0xC8, 0x40, 0x44, 0x48, 0x4C, 0x50, 0x54, 0x58, 0x30, 0x28
   

---

回答以下有关具有 32 位内存地址的微处理器缓存存储器的问题。

1. 考虑容量为 $2^{15}$ 字节、块大小为 64 字节的缓存存储器。缓存存储器使用全相联方案、二路组相联方案或直接映射方案。对于这些方案中的每一种，计算标记、索引和偏移的位长度。

2. 考虑容量为 64 字节、块大小为 8 字节的缓存存储器。当按以下顺序访问十六进制内存地址时，计算在使用全相联方案、二路组相联方案和直接映射方案的情况下，缓存命中次数。假设缓存存储器在开始时为空，并且缓存块基于 LRU（最近最少使用）算法进行替换。

   0x20, 0x48, 0x40, 0x4C, 0x58, 0x80, 0xB8, 0xC8, 0x40, 0x44, 0x48, 0x4C, 0x50, 0x54, 0x58, 0x30, 0x28
   

---

Problem 5

Denote the set of real numbers with $\mathbb{R}$ and the absolute value of a real value $w$ with $|w|$. For a $d$-dimensional real column vector $\mathbf{w}$, we write its $i$-th element as $w_i$, and define $\Vert \mathbf{w}\Vert =|w_1|+|w_2|+\cdots +|w_d|$ and $\Vert \mathbf{w}{\Vert }_2=\sqrt{w_1^2+w_2^2+\cdots +w_d^2}$. The transpose of $\mathbf{w}$ is written as ${\mathbf{w}}^{\top }$.

A vector $\mathbf{g}\in {\mathbb{R}}^d$ is a subgradient of a convex function $f$ at $\mathbf{x}\in {\mathbb{R}}^d$ if

$$\forall \mathbf{z}\in {\mathbb{R}}^d,f(\mathbf{z})\ge f(\mathbf{x})+{\mathbf{g}}^{\top }(\mathbf{z}-\mathbf{x})$$

holds. The set of subgradients of a convex function $f$ at $\mathbf{x}$, $\{\mathbf{g}\in {\mathbb{R}}^d\mid \forall \mathbf{z}\in {\mathbb{R}}^d,f(\mathbf{z})\ge f(\mathbf{x})+{\mathbf{g}}^{\top }(\mathbf{z}-\mathbf{x})\}$ is called the subdifferential of $f$ at $\mathbf{x}$, and is denoted by $\partial f(\mathbf{x})$. You may use the following facts (i), (ii), and (iii). (i) A differentiable convex function $f(\mathbf{x})$ satisfies

$$\partial f(\mathbf{x})=\{\nabla f(\mathbf{x})\},\nabla f(\mathbf{x})=\left(\begin{array}{c}\frac{\partial f(\mathbf{x})}{\partial x_1}\\ ⋮\\ \frac{\partial f(\mathbf{x})}{\partial x_d}\end{array}\right).$$

(ii) For convex functions $f_1$ and $f_2$, it holds that $\partial (f_1+f_2)(\mathbf{x})=\{{\mathbf{g}}_1+{\mathbf{g}}_2\mid {\mathbf{g}}_1\in \partial f_1(\mathbf{x}),{\mathbf{g}}_2\in \partial f_2(\mathbf{x})\}$. (iii) $0\in \partial f({\mathbf{w}}^{\ast })$ is a necessary and sufficient condition that a convex function $f(\mathbf{w})$ is minimized by $\mathbf{w}={\mathbf{w}}^{\ast }$.

Answer the following questions.

1. (a) For $f(w)=|w|$ $(w\in \mathbb{R})$, obtain $\partial f(w)$. (b) For $f(\mathbf{w})=\Vert \mathbf{w}\Vert$ $(\mathbf{w}\in {\mathbb{R}}^d)$, obtain $\partial f(\mathbf{w})$.

2. For $f(w)=\frac{1}{2}(w-z{)}^2+\beta |w|$ $(w,z\in \mathbb{R},0<\beta \in \mathbb{R})$, obtain $\partial f(w)$. Also obtain ${\mathbf{w}}^{\ast }\in \mathbb{R}$ that minimizes $f(w)$.

3. For $f(\mathbf{w})=\frac{1}{2}\Vert \mathbf{w}-\mathbf{z}{\Vert }_2^2+\beta \Vert \mathbf{w}\Vert$ $(\mathbf{w},\mathbf{z}\in {\mathbb{R}}^d,0<\beta \in \mathbb{R})$, obtain $\partial f(\mathbf{w})$. Also, assuming that $\mathbf{w}={\mathbf{w}}^{\ast }\in {\mathbb{R}}^d$ minimizes $f(\mathbf{w})$, and letting $j$ be an integer satisfying $1\le j\le d$, obtain a necessary and sufficient condition for $w_j^{\ast }=0$.

Consider the problem of predicting one dimensional real-valued label $y\in \mathbb{R}$ from a $d$-dimensional real vector $\mathbf{x}\in {\mathbb{R}}^d$. Suppose that a set of $n$ training samples

$$\{(x_i,y_i)\mid {\mathbf{x}}_i\in {\mathbb{R}}^d,y_i\in \mathbb{R},i=1,2,\dots ,n\}$$

is given where $({\mathbf{x}}_i,y_i)$ means that $y_i$ is the real-valued label of ${\mathbf{x}}_i$.

By using a $d$-dimensional parameter $\mathbf{w}\in {\mathbb{R}}^d$, define a loss function as

$$L(\mathbf{w})=\frac{1}{2n}\sum _{i=1}^n(y_i-{\mathbf{w}}^{\top }{\mathbf{x}}_i{)}^2.$$

We formulate the training of a predictor as the following optimization problem with a positive real value $\lambda$:

$${\mathbf{w}}^{\ast }=\underset{\mathbf{w}\in {\mathbb{R}}^d}{\mathrm{argmin}}\left\{L(\mathbf{w})+\lambda \Vert \mathbf{w}{\Vert }_1\right\}.$$

The following algorithm is known for obtaining the optimal solution ${\mathbf{w}}^{\ast }$. It iteratively solves the optimization problem ($†$) from an initial value ${\mathbf{w}}^{(0)}\in {\mathbb{R}}^d$ and using the step size ${\eta }_t>0$:

$${\mathbf{w}}^{(t+1)}=\underset{\mathbf{w}\in {\mathbb{R}}^d}{\mathrm{argmin}}\left\{\nabla L({\mathbf{w}}^{(t)}{)}^{\top }(\mathbf{w}-{\mathbf{w}}^{(t)})+\lambda \Vert \mathbf{w}{\Vert }_1+\frac{1}{2{\eta }_t}\Vert \mathbf{w}-{\mathbf{w}}^{(t)}{\Vert }_2^2\right\},t=0,1,2,\dots .\text{\hspace{1em}(dagger)}$$

Answer the following question.

4. Express $a\in \mathbb{R}$ using ${\eta }_t$ and $\lambda$ such that $w_j^{(t)}-{\eta }_t\frac{\partial L}{\partial w_j}({\mathbf{w}}^{(t)})\in [-a,a]$ is a necessary and sufficient condition for $w_j^{(t+1)}=0$, where $j$ is an integer satisfying $1\le j\le d$.

---

用 $\mathbb{R}$ 表示实数集，用 $|w|$ 表示实数 $w$ 的绝对值。对于 $d$ 维实数列向量 $\mathbf{w}$，我们将其第 $i$ 个元素写为 $w_i$，并定义 $\Vert \mathbf{w}\Vert =|w_1|+|w_2|+\cdots +|w_d|$ 和 $\Vert \mathbf{w}{\Vert }_2=\sqrt{w_1^2+w_2^2+\cdots +w_d^2}$。$\mathbf{w}$ 的转置写为 ${\mathbf{w}}^{\top }$。

向量 $\mathbf{g}\in {\mathbb{R}}^d$ 是凸函数 $f$ 在 $\mathbf{x}\in {\mathbb{R}}^d$ 处的一个次梯度，如果

$$\forall \mathbf{z}\in {\mathbb{R}}^d,f(\mathbf{z})\ge f(\mathbf{x})+{\mathbf{g}}^{\top }(\mathbf{z}-\mathbf{x})$$

成立。凸函数 $f$ 在 $\mathbf{x}$ 处的次梯度集合 $\{\mathbf{g}\in {\mathbb{R}}^d\mid \forall \mathbf{z}\in {\mathbb{R}}^d,f(\mathbf{z})\ge f(\mathbf{x})+{\mathbf{g}}^{\top }(\mathbf{z}-\mathbf{x})\}$ 被称为 $f$ 在 $\mathbf{x}$ 处的次微分，并用 $\partial f(\mathbf{x})$ 表示。你可以使用以下事实 (i)、(ii) 和 (iii)。 (i) 可微凸函数 $f(\mathbf{x})$ 满足

$$\partial f(\mathbf{x})=\{\nabla f(\mathbf{x})\},\nabla f(\mathbf{x})=\left(\begin{array}{c}\frac{\partial f(\mathbf{x})}{\partial x_1}\\ ⋮\\ \frac{\partial f(\mathbf{x})}{\partial x_d}\end{array}\right).$$

(ii) 对于凸函数 $f_1$ 和 $f_2$，有 $\partial (f_1+f_2)(\mathbf{x})=\{{\mathbf{g}}_1+{\mathbf{g}}_2\mid {\mathbf{g}}_1\in \partial f_1(\mathbf{x}),{\mathbf{g}}_2\in \partial f_2(\mathbf{x})\}$。 (iii) $0\in \partial f({\mathbf{w}}^{\ast })$ 是凸函数 $f(\mathbf{w})$ 由 $\mathbf{w}={\mathbf{w}}^{\ast }$ 最小化的必要且充分的条件。

回答以下问题。

1. (a) 对于 $f(w)=|w|$ $(w\in \mathbb{R})$，求 $\partial f(w)$。 (b) 对于 $f(\mathbf{w})=\Vert \mathbf{w}\Vert$ $(\mathbf{w}\in {\mathbb{R}}^d)$，求 $\partial f(\mathbf{w})$。

2. 对于 $f(w)=\frac{1}{2}(w-z{)}^2+\beta |w|$ $(w,z\in \mathbb{R},0<\beta \in \mathbb{R})$，求 $\partial f(w)$。 还要求出使 $f(w)$ 最小化的 ${\mathbf{w}}^{\ast }\in \mathbb{R}$。

3. 对于 $f(\mathbf{w})=\frac{1}{2}\Vert \mathbf{w}-\mathbf{z}{\Vert }_2^2+\beta \Vert \mathbf{w}\Vert$ $(\mathbf{w},\mathbf{z}\in {\mathbb{R}}^d,0<\beta \in \mathbb{R})$，求 $\partial f(\mathbf{w})$。 还要假设 $\mathbf{w}={\mathbf{w}}^{\ast }\in {\mathbb{R}}^d$ 最小化 $f(\mathbf{w})$，并且令 $j$ 为满足 $1\le j\le d$ 的整数，求 $w_j^{\ast }=0$ 的必要且充分的条件。

考虑从 $d$ 维实数向量 $\mathbf{x}\in {\mathbb{R}}^d$ 预测一维实值标签 $y\in \mathbb{R}$ 的问题。假设给定一组 $n$ 个训练样本

$$\{(x_i,y_i)\mid {\mathbf{x}}_i\in {\mathbb{R}}^d,y_i\in \mathbb{R},i=1,2,\dots ,n\}$$

其中 $({\mathbf{x}}_i,y_i)$ 表示 $y_i$ 是 ${\mathbf{x}}_i$ 的实值标签。

通过使用 $d$ 维参数 $\mathbf{w}\in {\mathbb{R}}^d$，定义损失函数为

$$L(\mathbf{w})=\frac{1}{2n}\sum _{i=1}^n(y_i-{\mathbf{w}}^{\top }{\mathbf{x}}_i{)}^2.$$

我们将预测器的训练表述为以下具有正实值 $\lambda$ 的优化问题：

$${\mathbf{w}}^{\ast }=\underset{\mathbf{w}\in {\mathbb{R}}^d}{\mathrm{argmin}}\left\{L(\mathbf{w})+\lambda \Vert \mathbf{w}{\Vert }_1\right\}.$$

已知以下算法用于获得最优解 ${\mathbf{w}}^{\ast }$。 它从初始值 ${\mathbf{w}}^{(0)}\in {\mathbb{R}}^d$ 开始，使用步长 ${\eta }_t>0$ 迭代求解优化问题 ($†$)：

$${\mathbf{w}}^{(t+1)}=\underset{\mathbf{w}\in {\mathbb{R}}^d}{\mathrm{argmin}}\left\{\nabla L({\mathbf{w}}^{(t)}{)}^{\top }(\mathbf{w}-{\mathbf{w}}^{(t)})+\lambda \Vert \mathbf{w}{\Vert }_1+\frac{1}{2{\eta }_t}\Vert \mathbf{w}-{\mathbf{w}}^{(t)}{\Vert }_2^2\right\},t=0,1,2,\dots .\text{\hspace{1em}(dagger)}$$

回答以下问题。

4. 用 ${\eta }_t$ 和 $\lambda$ 表示 $a\in \mathbb{R}$ 使得 $w_j^{(t)}-{\eta }_t\frac{\partial L}{\partial w_j}({\mathbf{w}}^{(t)})\in [-a,a]$ 是 $w_j^{(t+1)}=0$ 的必要且充分的条件，其中 $j$ 是满足 $1\le j\le d$ 的整数。

---

Problem 6

Consider the decomposition time of an RNA molecule. Assume that the probability density function of the decomposition time $T$ is

$$f_T(t)=\lambda e^{-\lambda t},t\ge 0,$$

where $\lambda$ is a positive real constant.

Answer the following questions.

1. Calculate the cumulative distribution function

$$F_T(t)={\int }_0^t{f}_T(x)\mathrm{d}x.$$

Also compute the median of $T$.

2. We measured the decomposition times $T_i(i=1,\dots ,n)$ of $n$ RNA molecules. Assume that the decomposition time of each RNA molecule follows the probability density function $f_T(t)$ independently and identically. Calculate the expected value and the variance of

$${\mu }_T=\frac{{\sum }_{i=1}^n{T}_i}{n}.$$

3. Let $T_{\text{max}}=\max \{T_1,\dots ,T_n\}$, which is the maximum of the measured times $T_i$ in question (2). Let $\text{Prob}(T_{\text{max}}>t)$ denote the probability that $T_{\text{max}}>t$. Give an expression for $\text{Prob}(T_{\text{max}}>t)$ in terms of $F_T(t)$.

4. Calculate the probability density function $f_{T_{\text{max}}}(t)$ of $T_{\text{max}}$, and the expected value of $T_{\text{max}}$.

---

考虑 RNA 分子的分解时间。假设分解时间 $T$ 的概率密度函数为

$$f_T(t)=\lambda e^{-\lambda t},t\ge 0,$$

其中 $\lambda$ 是正实常数。

回答以下问题。

1. 计算累积分布函数

$$F_T(t)={\int }_0^t{f}_T(x)\mathrm{d}x.$$

并计算 $T$ 的中位数。

2. 我们测量了 $n$ 个 RNA 分子的分解时间 $T_i(i=1,\dots ,n)$。假设每个 RNA 分子的分解时间独立且同分布，并服从概率密度函数 $f_T(t)$。计算

$${\mu }_T=\frac{{\sum }_{i=1}^n{T}_i}{n}.$$

的期望值和方差。

3. 令 $T_{\text{max}}=\max \{T_1,\dots ,T_n\}$，它是问题 (2) 中测量时间 $T_i$ 的最大值。设 $\text{Prob}(T_{\text{max}}>t)$ 表示 $T_{\text{max}}>t$ 的概率。用 $F_T(t)$ 表示 $\text{Prob}(T_{\text{max}}>t)$ 的表达式。

4. 计算 $T_{\text{max}}$ 的概率密度函数 $f_{T_{\text{max}}}(t)$ 以及 $T_{\text{max}}$ 的期望值。