2021S

Problem 1

In undirected graphs, a self-loop is an edge connecting the same vertex, and multi-edges are multiple edges connecting the same pair of vertices. From now on, we consider undirected graphs without self-loops and possibly with multi-edges. We say that a graph $\mathbf{G}$ is an $\mathbf{A}$-graph if a graph consisting of a single edge can be obtained from $\mathbf{G}$ by repeatedly applying the following two operations.

B-operation

When two multi-edges connect a pair of vertices, replace the multi-edges with a single edge connecting the pair of vertices.

C-operation

When one edge connects vertices $\mathbf{u}$ and $\mathbf{v}$, another edge connects $\mathbf{v}$ and $\mathbf{w}$ (where $\mathbf{u}\ne \mathbf{w}$), and there is no other edge incident to $\mathbf{v}$, remove the vertex $\mathbf{v}$ and replace the two edges with a new edge connecting $\mathbf{u}$ and $\mathbf{w}$.

Answer the following questions.

1. Let ${\mathbf{K}}_n$ be a complete graph of $\mathbf{n}$ vertices. Answer whether each of ${\mathbf{K}}_3$ and ${\mathbf{K}}_4$ is an $\mathbf{A}$-graph or not.

2. Show that every $\mathbf{A}$-graph is planar.

3. Give the maximum number of edges of an $\mathbf{A}$-graph with $\mathbf{n}$ vertices without multi-edges, with a proof. Also, give such an $\mathbf{A}$-graph attaining the maximum for general $\mathbf{n}$, with an explanation.

4. Give an $\mathbf{O}(\mathbf{m}+\mathbf{n})$-time algorithm which, given an undirected graph with $\mathbf{n}$ vertices and $\mathbf{m}$ edges as an input, determines whether it is an $\mathbf{A}$-graph or not. Explain also the graph data structures used in the algorithm for realizing $\mathbf{B}$-operations and $\mathbf{C}$-operations.

---

在无向图中，自环是连接同一顶点的边，多重边是连接同一对顶点的多条边。从现在起，我们考虑无自环且可能有多重边的无向图。我们说图 $\mathbf{G}$ 是 $\mathbf{A}$-图，如果通过重复应用以下两种操作，可以从 $\mathbf{G}$ 得到仅由一条边组成的图。

B-操作

当两条多重边连接一对顶点时，用连接该对顶点的一条边替换多重边。

C-操作

当一条边连接顶点 $\mathbf{u}$ 和 $\mathbf{v}$，另一条边连接 $\mathbf{v}$ 和 $\mathbf{w}$（其中 $\mathbf{u}\ne \mathbf{w}$），且没有其他边与顶点 $\mathbf{v}$ 相连时，移除顶点 $\mathbf{v}$ 并用一条连接 $\mathbf{u}$ 和 $\mathbf{w}$ 的新边替换这两条边。

回答以下问题。

1. 设 ${\mathbf{K}}_n$ 是 $\mathbf{n}$ 个顶点的完全图。回答 ${\mathbf{K}}_3$ 和 ${\mathbf{K}}_4$ 是否是 $\mathbf{A}$-图。

2. 证明每个 $\mathbf{A}$-图都是平面的。

3. 给出没有多重边的 $\mathbf{n}$ 个顶点的 $\mathbf{A}$-图的最大边数，并提供证明。此外，给出一个这样的 $\mathbf{A}$-图，其在一般 $\mathbf{n}$ 下达到最大值，并进行解释。

4. 给出一个 $\mathbf{O}(\mathbf{m}+\mathbf{n})$ 时间复杂度的算法，该算法给定一个有 $\mathbf{n}$ 个顶点和 $\mathbf{m}$ 条边的无向图作为输入，确定它是否是 $\mathbf{A}$-图。还要解释实现 $\mathbf{B}$-操作和 $\mathbf{C}$-操作的图数据结构。

---

Problem 2

Let $\Sigma$ be the set $\{a,b\}$ of letters. For a word $w\in {\Sigma }^{\ast }$ and two languages $L_a,L_b\subseteq {\Sigma }^{\ast }$ over $\Sigma$, we define the language $w\{a\mapsto L_a,b\mapsto L_b\}\subseteq {\Sigma }^{\ast }$ as follows, by induction on $w$.

$$ϵ\{a\mapsto L_a,b\mapsto L_b\}=\{ϵ\}$$ $$(aw)\{a\mapsto L_a,b\mapsto L_b\}=\{w_1{w}_2\mid w_1\in L_a,w_2\in w\{a\mapsto L_a,b\mapsto L_b\}\}$$ $$(bw)\{a\mapsto L_a,b\mapsto L_b\}=\{w_1{w}_2\mid w_1\in L_b,w_2\in w\{a\mapsto L_a,b\mapsto L_b\}\}$$

Here, $ϵ$ represents the empty word. For example, if $w=aba$, $L_a=\{b^n\mid n\ge 0\}$, and $L_b=\{a^n\mid n\ge 0\}$, then $w\{a\mapsto L_a,b\mapsto L_b\}=\{b^l{a}^m{b}^n\mid l,m,n\ge 0\}$. Furthermore, for languages $L,L_a,L_b\subseteq {\Sigma }^{\ast }$, we define $L\{a\mapsto L_a,b\mapsto L_b\}$ as ${\bigcup }_{w\in L}w\{a\mapsto L_a,b\mapsto L_b\}$. For example, if $L=\{a^{n}b\mid n\ge 0\}$, $L_a=\{ab\}$, and $L_b=\{a^n\mid n\ge 0\}$, then $L\{a\mapsto L_a,b\mapsto L_b\}=\{(ab{)}^m{a}^n\mid m,n\ge 0\}$.

Answer the following questions.

1. Let $L=\{(ab{)}^m{a}^n\mid m,n\ge 0\}$, $L_a=\{bb\}$, and $L_b=\{ab,a\}$. Express $L\{a\mapsto L_a,b\mapsto L_b\}$ using a regular expression.
2. Let $L^{\prime }=\{a^m{b}^n\mid m\ge n\ge 0\}$, $L_a^{\prime }=\{a^n\mid n\ge 0\}$, and $L_b^{\prime }=\{a^m{b}^m\mid m\ge 0\}$. Express $\{w\in {\Sigma }^{\ast }\mid w\{a\mapsto L_a^{\prime },b\mapsto L_b^{\prime }\}\subseteq L^{\prime }\}$ using a regular expression.
3. Let $A_0=(Q_0,\Sigma ,{\delta }_0,q_0,F_0)$, $A_1=(Q_1,\Sigma ,{\delta }_1,q_1,F_1)$, and $A_2=(Q_2,\Sigma ,{\delta }_2,q_2,F_2)$ be deterministic finite automata, and for each $i\in \{0,1,2\}$, let $L_i$ be the language accepted by $A_i$. Here, $Q_i,{\delta }_i,q_{i,0},F_i$ are the set of states, the transition function, the initial state, and the set of final states of $A_i$ ($i\in \{0,1,2\}$), respectively. Assume that the transition functions ${\delta }_i\in Q_i\times \Sigma \to Q_i$ ($i\in \{0,1,2\}$) are total. Give a non-deterministic finite automaton that accepts $L_0\{a\mapsto L_1,b\mapsto L_2\}$, with a brief explanation. You may use $ϵ$-transitions.
4. For $A_i$ and $L_i$ ($i\in \{0,1,2\}$) in question (3), give a deterministic finite automaton that accepts $\{w\in {\Sigma }^{\ast }\mid w\{a\mapsto L_i,b\mapsto L_j\}\subseteq L_k\}$, with a brief explanation.

---

令 $\Sigma$ 是字母集合 $\{a,b\}$。对于一个单词 $w\in {\Sigma }^{\ast }$ 和两个语言 $L_a,L_b\subseteq {\Sigma }^{\ast }$，我们通过对 $w$ 归纳来定义语言 $w\{a\mapsto L_a,b\mapsto L_b\}\subseteq {\Sigma }^{\ast }$。

$$ϵ\{a\mapsto L_a,b\mapsto L_b\}=\{ϵ\}$$ $$(aw)\{a\mapsto L_a,b\mapsto L_b\}=\{w_1{w}_2\mid w_1\in L_a,w_2\in w\{a\mapsto L_a,b\mapsto L_b\}\}$$ $$(bw)\{a\mapsto L_a,b\mapsto L_b\}=\{w_1{w}_2\mid w_1\in L_b,w_2\in w\{a\mapsto L_a,b\mapsto L_b\}\}$$

这里，$ϵ$ 表示空字。举例来说，如果 $w=aba$, $L_a=\{b^n\mid n\ge 0\}$, and $L_b=\{a^n\mid n\ge 0\}$，那么 $w\{a\mapsto L_a,b\mapsto L_b\}=\{b^l{a}^m{b}^n\mid l,m,n\ge 0\}$。此外，对于语言 $L,L_a,L_b\subseteq {\Sigma }^{\ast }$，我们定义 $L\{a\mapsto L_a,b\mapsto L_b\}$ 为 ${\bigcup }_{w\in L}w\{a\mapsto L_a,b\mapsto L_b\}$。例如，如果 $L=\{a^{n}b\mid n\ge 0\}$, $L_a=\{ab\}$, 和 $L_b=\{a^n\mid n\ge 0\}$，那么 $L\{a\mapsto L_a,b\mapsto L_b\}=\{(ab{)}^m{a}^n\mid m,n\ge 0\}$。

回答以下问题。

1. 令 $L=\{(ab{)}^m{a}^n\mid m,n\ge 0\}$，$L_a=\{bb\}$，和 $L_b=\{ab,a\}$。用正则表达式表示 $L\{a\mapsto L_a,b\mapsto L_b\}$。
2. 令 $L^{\prime }=\{a^m{b}^n\mid m\ge n\ge 0\}$，$L_a^{\prime }=\{a^n\mid n\ge 0\}$，和 $L_b^{\prime }=\{a^m{b}^m\mid m\ge 0\}$。用正则表达式表示 $\{w\in {\Sigma }^{\ast }\mid w\{a\mapsto L_a^{\prime },b\mapsto L_b^{\prime }\}\subseteq L^{\prime }\}$。
3. 令 $A_0=(Q_0,\Sigma ,{\delta }_0,q_0,F_0)$，$A_1=(Q_1,\Sigma ,{\delta }_1,q_1,F_1)$，和 $A_2=(Q_2,\Sigma ,{\delta }_2,q_2,F_2)$ 是确定有限自动机，并且对于每个 $i\in \{0,1,2\}$，令 $L_i$ 是 $A_i$ 接受的语言。这里，$Q_i,{\delta }_i,q_{i,0},F_i$ 是 $A_i$ 的状态集、转移函数、初始状态和终态集 ($i\in \{0,1,2\}$)，分别。假设转移函数 ${\delta }_i\in Q_i\times \Sigma \to Q_i$ ($i\in \{0,1,2\}$) 是全函数。给出一个非确定有限自动机来接受 $L_0\{a\mapsto L_1,b\mapsto L_2\}$，并简要解释。你可以使用 $ϵ$-转移。
4. 对于问题 (3) 中的 $A_i$ 和 $L_i$ ($i\in \{0,1,2\}$)，给出一个确定有限自动机来接受 $\{w\in {\Sigma }^{\ast }\mid w\{a\mapsto L_i,b\mapsto L_j\}\subseteq L_k\}$，并简要解释。

---

Problem 3

Consider bit-serial communication circuits which send and receive 5-bit information bit-by-bit in a noisy environment. The 5-bit information consists of a 2-bit start-bit signal, 2-bit payload data, and a 1-bit odd-parity signal.

The sender circuit always outputs ‘0’ in the initial state. At the beginning of a communication, the sender outputs 2-bit data ‘11’ bit-by-bit. It subsequently outputs 2-bit payload data bit-by-bit from the most significant bit. It finally outputs an odd-parity signal such that the number of ‘1’s in the sent bit sequence including the 2-bit start-bit signal, the payload data, and the parity signal itself is an odd number. After sending the parity signal, the sender circuit goes to the initial state, and it outputs ‘0’ until the next sending.

The receiver circuit has a 1-bit input A from the sender circuit, a 1-bit output B for the parity check result, and a 2-bit output for the received payload data. It obtains payload data from a received bit sequence and does the odd parity checking.

In the initial state, the receiver circuit waits for ‘1’ corresponding to the first bit of a start-bit signal. In the next clock cycle after receiving the first bit of a start-bit signal, it receives a value corresponding to the second bit of a start-bit signal. If the received value corresponding to the second bit of a start-bit signal is ‘0’, the receiver circuit judges that the first received bit ‘1’ was an error caused by a noise, and goes back to the initial state. Otherwise, in the next 2 clock cycles, it stores each value of the input A as payload data. At the next clock cycle, it receives a parity-bit, and it verifies that the number of ‘1’s in the received 5-bit sequence consisting of the 2-bit start-bit signal, the 2-bit payload data, and the parity-bit is odd. It assigns ‘1’ to the output B if the number of ‘1’s is odd, and it assigns ‘0’ otherwise. The value of the output B is always ‘0’, except in the clock cycles for receiving a parity-bit. The receiver circuit then goes to the initial state, regardless of the parity-check result.

Answer the following questions.

1. Give the state transition diagram of a Mealy-type finite state machine (FSM), consisting of 7 states, for the parity check circuit with the input A and the output B in the receiver circuit. Based on the state transition diagram, give also a corresponding state transition table and an output table by using the one-hot encoding. One-hot encoding is a method for encoding each state as a bit sequence where only one bit is ‘1’ and the other bits are ‘0’.

2. Based on the state transition table and the output table in question (1), express the output B as a Boolean expression in terms of the input A and the one-hot encoding representation of the current state of the FSM. Based on the Boolean expression, give also a corresponding gate-level circuit of the parity check circuit that outputs B, given A and the one-hot encoding representation of the current state of the FSM as inputs. You are allowed to use only 2-input AND gates, 2-input OR-gates, and NOT-gates. There is no limitation on the number of gates. You need not describe unused input signals.

3. According to the Boolean expression answered in question (2), give a CMOS transistor level circuit that outputs B, given A and the one-hot encoding representation of the current state of the FSM as inputs. You are not allowed to use more than 12 transistors. You may use the inverter mark, but the number of transistors required for the inverters must be included in the total number of transistors. You need not describe unused input signals.

---

考虑在嘈杂环境中按位发送和接收 5 位信息的位序列通信电路。5 位信息由 2 位起始信号、2 位有效载荷数据和 1 位奇校验信号组成。

发送电路在初始状态下总是输出 ‘0’。在通信开始时，发送电路按位输出 2 位数据 ‘11’。随后按位输出 2 位有效载荷数据，从最高有效位开始。最后输出一个奇校验信号，使得包括 2 位起始信号、有效载荷数据和校验信号在内的发送位序列中的 ‘1’ 的数量为奇数。发送校验信号后，发送电路进入初始状态，并在下次发送前输出 ‘0’。

接收电路从发送电路接收 1 位输入 A，输出用于校验结果的 1 位输出 B，以及用于接收的有效载荷数据的 2 位输出。它从接收的位序列中获取有效载荷数据并进行奇校验。

在初始状态下，接收电路等待与起始信号的第一位相对应的 ‘1’。在接收到起始信号的第一位后的下一个时钟周期内，它接收与起始信号的第二位相对应的值。如果接收到的与起始信号的第二位相对应的值为 ‘0’，接收电路判断第一个接收到的 ‘1’ 是由噪声引起的错误，并返回初始状态。否则，在接下来的 2 个时钟周期内，它将每个输入 A 的值存储为有效载荷数据。在下一个时钟周期内，它接收一个校验位，并验证接收的 5 位序列（包括 2 位起始信号、2 位有效载荷数据和校验位）中的 ‘1’ 的数量是否为奇数。如果 ‘1’ 的数量为奇数，则将 ‘1’ 分配给输出 B，否则分配 ‘0’。输出 B 的值总是为 ‘0’，除了接收校验位的时钟周期外。接收电路然后返回初始状态，无论校验结果如何。

回答以下问题。

1. 给出一个包含 7 个状态的 Mealy 型有限状态机（FSM）的状态转换图，用于接收电路中的校验电路，输入为 A，输出为 B。基于状态转换图，使用独热编码给出相应的状态转换表和输出表。独热编码是一种将每个状态编码为仅一个比特为 ‘1’ 而其他比特为 ‘0’ 的方法。

2. 基于问题（1）中的状态转换表和输出表，用布尔表达式表示输出 B，作为输入 A 和 FSM 当前状态的独热编码表示的函数。基于布尔表达式，给出相应的门级电路，该电路输出 B，输入为 A 和 FSM 当前状态的独热编码表示。你可以使用的门电路包括 2 输入 AND 门、2 输入 OR 门和 NOT 门。门电路数量没有限制。无需描述未使用的输入信号。

3. 根据问题（2）中回答的布尔表达式，给出一个 CMOS 晶体管级电路，该电路输出 B，输入为 A 和 FSM 当前状态的独热编码表示。你不能使用超过 12 个晶体管。你可以使用反相器标记，但反相器所需的晶体管数量必须包括在晶体管总数中。无需描述未使用的输入信号。

---

Problem 4

Let $\mathbb{R}$ be the set of real numbers. Denote by $\mathbf{T}$ the transposition operator of a vector and a matrix. When $\mathbf{w}=(w_1,w_2,\dots ,w_d{)}^{\mathbf{T}}\in {\mathbb{R}}^d$ is a $d$-dimensional column vector, the norm $\Vert \mathbf{w}{\Vert }_2$ is defined by $\Vert \mathbf{w}{\Vert }_2=\sqrt{w_1^2+w_2^2+\dots +w_d^2}$. Define the inner product of two column vectors ${\mathbf{x}}_1,{\mathbf{x}}_2\in {\mathbb{R}}^d$ as ${\mathbf{x}}_1^{\mathbf{T}}{\mathbf{x}}_2\in \mathbb{R}$. For a $d\times d$ matrix $\mathbf{A}\in {\mathbb{R}}^{d\times d}$, define $\Vert \mathbf{w}{\Vert }_{\mathbf{A}}=\sqrt{{\mathbf{w}}^{\mathbf{T}}\mathbf{Aw}}$. Let $\mathbf{tr}(\mathbf{B})$ be the trace of the matrix $\mathbf{B}$.

Consider the problem of predicting a real-valued label $y\in \mathbb{R}$ from a $d$-dimensional real vector $\mathbf{x}\in {\mathbb{R}}^d$. For learning a predictor, suppose that $n$ training samples

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

are given where $({\mathbf{x}}_i,y_i)$ means that $y_i$ is the real-valued label of ${\mathbf{x}}_i$. In addition, by using a $d$-dimensional vector ${\mathbf{w}}^{\ast }\in {\mathbb{R}}^d$ and observational noise ${ϵ}_i(i=1,2,\dots ,n)$ that is independent and identically distributed, assume the data generation process as

$$y_i={\mathbf{w}}^{\ast \mathbf{T}}{\mathbf{x}}_i+{ϵ}_i(i=1,2,\dots ,n),$$

where the expectation $\mathbb{E}[{ϵ}_i]=0$ and variance $\mathbb{V}[{ϵ}_i]={\sigma }^2>0(i=1,\dots ,n)$. Let us introduce the symbols

$$\mathbf{X}=[{\mathbf{x}}_1,\dots ,{\mathbf{x}}_n{]}^{\mathbf{T}}\in {\mathbb{R}}^{n\times d},\mathbf{Y}=[y_1,\dots ,y_n{]}^{\mathbf{T}}\in {\mathbb{R}}^n,\mathbf{e}=[{ϵ}_1,\dots ,{ϵ}_n{]}^{\mathbf{T}}\in {\mathbb{R}}^n.$$

We also use the symbol $\mathbf{\Phi }=\frac{1}{n}{\mathbf{X}}^{\mathbf{T}}\mathbf{X}\in {\mathbb{R}}^{d\times d}$ where $\mathbf{\Phi }$ is assumed to be a regular matrix. The expectation over the observational noises is expressed by ${\mathbb{E}}_{\mathbf{e}}[\cdot ]$.

We formulate the learning of a predictor $f(\mathbf{x})={\mathbf{w}}^{\mathbf{T}}\mathbf{x}$ as the following optimization problem.

$$\hat{\mathbf{w}}=\underset{\mathbf{w}\in {\mathbb{R}}^d}{\mathrm{argmin}}L(\mathbf{w})$$ $$L(\mathbf{w})=\frac{1}{2n}\sum _{i=1}^n(y_i-{\mathbf{w}}^{\mathbf{T}}{\mathbf{x}}_i{)}^2=\frac{1}{2n}\Vert \mathbf{Y}-\mathbf{Xw}{\Vert }_2^2.$$

Answer the following questions. Describe not only an answer but also the derivation process.

1. Express $\hat{\mathbf{w}}$ using $\mathbf{X},\mathbf{Y},\mathbf{\Phi }$, and $n$.

2. Suppose we wish to express ${\mathbb{E}}_{\mathbf{e}}[L(\mathbf{w})]$ in the form of $\frac{1}{2}\Vert \mathbf{w}-{\mathbf{w}}^{\ast }{\Vert }_{\mathbf{A}}^2+b$. Express the matrix $\mathbf{A}\in {\mathbb{R}}^{d\times d}$ and the positive real number $b>0$ using $\mathbf{\Phi }$ and ${\sigma }^2$.

3. Suppose we wish to express ${\mathbb{E}}_{\mathbf{e}}[L(\mathbf{w})]-{\mathbb{E}}_{\mathbf{e}}[L(\hat{\mathbf{w}})]$ in the form of $\frac{{\sigma }^2}{2n}\mathbf{tr}(\mathbf{B})$. Express the matrix $\mathbf{B}\in {\mathbb{R}}^{d\times d}$ using the matrix $\mathbf{X}$.

4. Explain what problem arises when $\mathbf{\Phi }$ is not a regular matrix and suggest a way to remedy the problem.

---

设 $\mathbb{R}$ 是实数集。用 $\mathbf{T}$ 表示向量和矩阵的转置运算符。当 $\mathbf{w}=(w_1,w_2,\dots ,w_d{)}^{\mathbf{T}}\in {\mathbb{R}}^d$ 是一个 $d$ 维列向量时，范数 $\Vert \mathbf{w}{\Vert }_2$ 定义为 $\Vert \mathbf{w}{\Vert }_2=\sqrt{w_1^2+w_2^2+\dots +w_d^2}$。定义两个列向量 ${\mathbf{x}}_1,{\mathbf{x}}_2\in {\mathbb{R}}^d$ 的内积为 ${\mathbf{x}}_1^{\mathbf{T}}{\mathbf{x}}_2\in \mathbb{R}$。对于 $d\times d$ 矩阵 $\mathbf{A}\in {\mathbb{R}}^{d\times d}$，定义 $\Vert \mathbf{w}{\Vert }_{\mathbf{A}}=\sqrt{{\mathbf{w}}^{\mathbf{T}}\mathbf{Aw}}$。设 $\mathbf{tr}(\mathbf{B})$ 为矩阵 $\mathbf{B}$ 的迹。

考虑从 $d$ 维实向量 $\mathbf{x}\in {\mathbb{R}}^d$ 预测实值标签 $y\in \mathbb{R}$ 的问题。为了学习一个预测器，假设有 $n$ 个训练样本

$$\{({\mathbf{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}}^{\ast }\in {\mathbb{R}}^d$ 和观测噪声 ${ϵ}_i(i=1,2,\dots ,n)$，假设数据生成过程为

$$y_i={\mathbf{w}}^{\ast \mathbf{T}}{\mathbf{x}}_i+{ϵ}_i(i=1,2,\dots ,n),$$

其中期望 $\mathbb{E}[{ϵ}_i]=0$ 和方差 $\mathbb{V}[{ϵ}_i]={\sigma }^2>0(i=1,\dots ,n)$. 我们引入符号

$$\mathbf{X}=[{\mathbf{x}}_1,\dots ,{\mathbf{x}}_n{]}^{\mathbf{T}}\in {\mathbb{R}}^{n\times d},\mathbf{Y}=[y_1,\dots ,y_n{]}^{\mathbf{T}}\in {\mathbb{R}}^n,\mathbf{e}=[{ϵ}_1,\dots ,{ϵ}_n{]}^{\mathbf{T}}\in {\mathbb{R}}^n.$$

我们还使用符号 $\mathbf{\Phi }=\frac{1}{n}{\mathbf{X}}^{\mathbf{T}}\mathbf{X}\in {\mathbb{R}}^{d\times d}$，假设 $\mathbf{\Phi }$ 是一个正规矩阵。观测噪声的期望用 ${\mathbb{E}}_{\mathbf{e}}[\cdot ]$ 表示。

我们将预测器 $f(\mathbf{x})={\mathbf{w}}^{\mathbf{T}}\mathbf{x}$ 的学习公式化为以下优化问题。

$$\hat{\mathbf{w}}=\underset{\mathbf{w}\in {\mathbb{R}}^d}{\mathrm{argmin}}L(\mathbf{w})$$ $$L(\mathbf{w})=\frac{1}{2n}\sum _{i=1}^n(y_i-{\mathbf{w}}^{\mathbf{T}}{\mathbf{x}}_i{)}^2=\frac{1}{2n}\Vert \mathbf{Y}-\mathbf{Xw}{\Vert }_2^2.$$

回答以下问题。描述不仅是答案，还有推导过程。

1. 用 $\mathbf{X},\mathbf{Y},\mathbf{\Phi }$ 和 $n$ 表示 $\hat{\mathbf{w}}$。

2. 假设我们希望以 $\frac{1}{2}\Vert \mathbf{w}-{\mathbf{w}}^{\ast }{\Vert }_{\mathbf{A}}^2+b$ 的形式表示 ${\mathbb{E}}_{\mathbf{e}}[L(\mathbf{w})]$。用 $\mathbf{\Phi }$ 和 ${\sigma }^2$ 表示矩阵 $\mathbf{A}\in {\mathbb{R}}^{d\times d}$ 和正实数 $b>0$。

3. 假设我们希望以 $\frac{{\sigma }^2}{2n}\mathbf{tr}(\mathbf{B})$ 的形式表示 ${\mathbb{E}}_{\mathbf{e}}[L(\mathbf{w})]-{\mathbb{E}}_{\mathbf{e}}[L(\hat{\mathbf{w}})]$。用矩阵 $\mathbf{X}$ 表示矩阵 $\mathbf{B}\in {\mathbb{R}}^{d\times d}$。

4. 解释当 $\mathbf{\Phi }$ 不是正规矩阵时会出现什么问题，并提出解决该问题的方法。