计算方法（下）

Posted on Edited on In
Symbols count in article: 8.2k Reading time ≈ 7 mins.
一些杂记

Part 4

Graph spectrum

  • 定义

称\(A(G)\)为\(G\)的邻接矩阵，\(D(G)\)为\(G\)的度数矩阵，\(L = D-A\)为\(G\)的拉普拉斯矩阵

  • 二分图

对于二分图\(G\)，如果\(\lambda\)是\(A(G)\)的一个特征值，且重数为\(k\)，那么\(-\lambda\)也是\(A(G)\)的重数为\(k\)的特征值

注意到\(A(G)\)是实对称矩阵，不需要区分代数重数和几何重数

考虑把\(A\)分块为\(\begin{bmatrix} O&B \\ B^T&O\end{bmatrix}\)，那么不难验证\(\binom{x}{y}\)和\(\binom{x}{-y}\)分别是\(\pm \lambda\)的特征向量，并且根据这个性质，如果\(\lambda\)有\(k\)个线性无关的向量，那么\(-\lambda\)也有

设\(A(G)\)的特征值为\(\lambda_1 \geq \lambda_2 \geq ... \geq \lambda_n\)，并且\(\lambda_i = -\lambda_{n-i+1}\)，那么\(G\)为二分图

注意到对奇数\(k\)，\(tr(A^k) = \sum \lambda^k = 0\)，而\(tr(A^k)\)表示所有点经过\(k\)条边后回到自身的方案数的和

  • 一般图

\(\deg_{avg}(G) \leq \lambda_{max}(A(G)) \leq \deg_{max}(G) = \Delta(G)\)

设\(x\)为对应的特征向量，并且\(i = \arg \max x_j\)那么\(\lambda x_i = (Ax)_i = \sum_{j} A_{ij} x_j \leq (\sum_{j} A_{ij}) x_i = deg_i(G) x_i \leq \Delta(G) x_i\)

  • 拉普拉斯矩阵

不难注意到：\(1\)是\(L(G)\)的特征向量，对应的特征值为\(0\)

根据\(x^TLx = \sum_{ij \in E} (x_i - x_j)^2\)，我们有\(L(G) \geq 0\)

设\(L(G)\)的特征值为\(\lambda_1 \leq \lambda_2 ... \leq \lambda_n\)，那么\(G\)连通当且仅当\(\lambda_2 > 0\)

进一步，\(0\)作为特征值的重数实际上揭示了\(G\)的连通分量的数量

首先对连通情况作证明：如果不连通，那么至少\(L(G) = diag\{L_1(G), L_2(G)\}\)，从而0至少有2个线性无关的特征向量

反之，如果连通，如果\(Lx = 0\)，那么\(x^T L x = \sum_{ij} (x_i - x_j)^2 = 0\)，由于连通，因此\(x\)的任意分量相同，故\(x = c 1\)

如果\(G\)有\(k\)个连通分量，那么\(L(G) = diag\{L_1(G), L_2(G), ..., L_k(G)\}\)，其中\(L_1(G), ..., L_k(G)\)是\(k\)个连通分量对应的子图，根据连通的结论，\(L(G)\)中\(0\)的代数重数恰好为\(k\)，如果代数重数为\(k\)，那么\(G\)也只能有\(k\)个连通分量

Perron-Frobenius Theorem

设\(A\)为非负，不可约且非周期的矩阵，那么

  • \(A\)的最大特征值的重数为1
  • 对应的特征向量中，每个维度都是非零且同号的
  • \(|\lambda_i| < \lambda_1\)

Random Walk

考虑随机游走，记\(X_t\)为时间\(t\)随机游走所处状态的概率，那么，存在一个转移矩阵使得\(X_{t+1} = X_t P\)

  • 定义

对于有限的马尔可夫链，如果其对应的有向图是强连通的，那么称其为不可约的

对于马尔可夫链，定义状态\(i\)的周期为\(period(i) := \gcd\{t:P_{i,i}^t > 0\}\)，如果状态\(i\)的周期为\(1\)，那么称其为非周期的，如果所有的状态都是非周期的，那么称该马尔可夫链是非周期的

  • 马尔可夫链基本定理

对于有限，不可约，非周期的马尔可夫链

  • 存在且仅存在一个稳态分布\(\pi\)
  • 无论\(p_0\)如何，一定有\(\lim_{t \to \infty} p_t \to \pi\)
  • \(\pi(i) = 1/ h_i\)，其中\(h_i = \mathbb{E}[H_i]\)，而\(H_i := \min\{t \geq 1 | X_t = i, X_0 = i\}\)
  • 无向图的讨论

在无向图里面，转移矩阵一般认为是\(AD^{-1}\)（也即均匀从邻居中选出一个）

那么，\(p_{t+1} = (AD^{-1})p_t\)，因此\(p_t = (AD^{-1})^t p_0\)

不难验证，\(\pi = \frac{1}{2m}(deg(1), ..., deg(n))\)是\(AD^{-1}\)的一个特征向量，从而是一个稳态分布

在无向图内，不可约即连通图，非周期即非二分图，因此我们有

  • 对于有限连通非二分图，都有\(p_t \to \pi\)

对于二分图，我们则可以考虑每个点以\(1/2\)的概率停留，以\(1/2\)的概率进行随机游走（相当于每个点加一个自环）

转移矩阵写为\(p_{t+1} = (\frac{1}{2}I + \frac{1}{2}AD^{-1})p_t\)

  • 对\(d-\)正则图的分析

在\(d-\)正则图中，\(\lambda_2(AD^{-1}) < 1\)描述了图的连通性，\(\lambda_{n}(AD^{-1}) > -1\)描述了图的非周期性

根据这个思路，我们定义\(\lambda = \min\{1 - \lambda_2, 1 - |\lambda_n|\}\)为谱间隔

随机游走的\(\epsilon-\)混合时间最多为\(\frac{1}{\lambda} \log (n / \epsilon)\)

其中\(\epsilon-\)混合时间定义为最小的整数\(t\)，使得\(||p_t - \pi||_1 \leq \epsilon, \forall p_0\)

直观上来说，混合时间就是说，过了这个时间之后，我们不再能区分是从哪个点出发

证明：取一组标准正交特征向量\(v_1,v_2,...,v_n\)，其中\(v_1 = \pi\)，对应的特征值为\(1 = \alpha_1 \geq \alpha_2 ... \alpha_n \geq -1\)（这个假设是不失一般性的，留作习题）

\(||p_t - \pi||_2^2 = c_2^2 \alpha_2^{2t} + ... + c_n^2 \alpha_n^{2t} \leq (c_2^2 + ... + c_n^2) (1 - \lambda)^{2t} \leq ||p_0||_1 (1-\lambda)^{2t} = (1-\lambda)^{2t}\)

其中用到了\(||p_0||_2^2 \leq ||p_0||_1\)

Resistance network

  • 定义

在一张无向图\(G\)上，每条边上有一个电阻\(r_e\)，之后每条边需要流过方向电流\(i_e(i_{uv} =-i_{vu})\)

对于每条边，我们也称其具有电导率\(w_e = 1/r_e\)

对于每个顶点，则有电势\(\phi_v\)和一个对于每个节点，统计总流入电流的量\(b_v\)

  • 假设

一般的，我们要求如下定律满足：

基尔霍夫定律：\(\sum_{vu \in E} i_{vu} = b_v, \forall v \in V\)

欧姆定律：\(\phi(u) - \phi(v) = i_{uv}r_{uv}\)，加权形式下为\(w_{uv}(\phi(u) - \phi(v)) = i_{uv}\)

合并上两式，我们得到\(b_v = \deg(v) \phi(v) - \sum_{vu \in E} w_{uv} \phi(u)\)，其中\(\deg(v)\)是\(w\)的加权的和

此时有，\(b = L \phi\)，当然\(L\)是加权的拉普拉斯矩阵

  • 推导

（假设网络是连通的）

设\(L = \sum \lambda_i v_i v_i^T\)，其中\(\lambda_1 \leq \lambda_2 \leq ...\)并且\(v_1, v_2, ..., v_n\)为正交标准基

存在向量\(\phi\)使得\(L \phi = b\)的充要条件为\(b \perp 1\)

首先，我们证明\(L \phi \perp 1\)，由于\(1\)在\(L\)的零空间中，这个事实不难证明

反之，令\(\phi = L^{\ddagger} b\)，其中\(L^{\ddagger} = \sum_{i \geq 2} \lambda_i^{-1} v_iv_i^{T}\)

根据上述知识，\(L \phi = b\)的全体解集形如\(\{L^{\ddagger} b + c\mathbb{1}: c\in R\}\)

在固定某个点的电势后，将有唯一的解

  • 等效电阻

定义\(s,t\)之间的等效电阻\(R_{eff}(s, t) := \phi(s) - \phi(t)\)，其中\(\phi\)满足\(L \phi = b_{st}\)，\(b_{st}\)是只在\(s\)上分量为1，在\(t\)上分量为-1的向量（相当于从s流入1的电流，从t流出1的电流的电阻）

注意到\(\phi = L^{\ddagger} b_{st}\)，又\(b_{st}^T \phi = \phi(s) - \phi(t)\)，因此\(R_{eff}(s, t) = b_{st}^T L^{\ddagger} b_{st}\)

  • 电势能

定义电势能为：\(\mathscr{E}(i) := \sum_e i_e^2 r_e = \sum_e w_e[\phi(u) - \phi(v)]^2 = \phi^T L \phi\)

根据上面的式子，不难看出\(\mathscr{E}(i) = \phi^T b = b^T \phi = b^T L^{\ddagger} b = R_{eff}(s, t)\)（其中\(i\)为\(s\)到\(t\)的单位电流）

\(\mathscr{E}(i) = R_{eff}(s, t) \leq \mathscr{E}(f)\)，其中\(f\)是任意的\(s-t\)流

对于任意流优化\(\mathscr{E}(f)\)，这是一个凸问题，电势能满足极值条件

如果\(r \geq r'\)，那么\(R_{eff, r}(s, t) \geq R_{eff, r'}(s, t)\)

不难想象，证明则利用电势能作为桥梁

\(R_{eff}(a, b) + R_{eff}(b, c) \geq R_{eff}(a, c)\)

将\(a\)到\(b\)的单位电流和\(b,c\)的单位电流组合以下，就得到了一个\(a\)到\(c\)的流，根据上面的不等式即可证明

  • 电阻网络与随机游走

碰撞时间：定义随机变量\(H_{uv} := \min\{t \geq 1 | X_1 = u, X_t = v\}\)，之后定义碰撞时间\(h_{uv} := \mathbb{E}[H_{u, v}]\)

返程时间：\(C_{u, v} := h_{u, v} + h_{v, u}\)

我们把无向图看作是所有边\(r_e = 1\)的电阻网络，那么\(C_{s,t} = 2m R_{eff}(s, t)\)

不难想象，考虑\(h_{*, t} = (h_{1, t}, ..., h_{t, t})\)，这些碰撞时间存在一些关系，用矩阵写出来为\(d_v = (L h_{*, t})_v, \forall v \neq t\)

对于第\(t\)行，我们需要特殊考虑，注意到\(L \phi = b\)有解当且仅当\(b \perp 1\)，因此我们希望构造一个\(d'\)，使得\(d' \perp 1\)

取\(d' = -\sum_{i \neq t} d_i = d_t - 2m\)即可，这个时候可以保证方程组有解

这个时候，观察到\(L(h_{*, t} - h_{*, s}) = 2m b_{st}\)，而\(R_{eff}(s, t)\)则对应的是\(L \phi = b_{st}\)

稍作说明，就可以得到所需的结论

Part 5

Linear Programming

一般的，形如 \[ \begin{aligned} & \max c^T x \\ &s.t.\; Ax \leq b \end{aligned} \] 形式的优化问题称为线性规划

其中，\(Ax \leq b\)称为约束条件，\(c^T x\)为目标函数

可以证明，上面的形式和下面的形式是可以互相转化的 \[ \begin{aligned} & \max c^T x \\& s.t. Ax \leq b, x \geq 0 \end{aligned} \]

  • 顶点

\(Ax \geq b\)实际上是一堆半空间的交，此时，可行解的空间构成一个polytope

对于polytope \(P = \{x:Ax \leq b\}\)，我们可以定义顶点，下面关于顶点的3种定义互相等价

  1. 边角点：\(x\)为边角点，当且仅当不存在\(y \neq 0\)使\(x+y \in P\)并且\(x - y \in P\)
  2. 极值点：\(x\)为极值点，当且仅当存在\(c\)使得，\(c^Tx > c^T x', \forall x' \neq x \in P\)
  3. 基本解：记\(x\)在约束条件\(Ax \leq b\)取到等于的对应行的矩阵为\(A^{=}x = b^=\)，如果\(\rank(A^=)\)满秩，则称\(x\)是一个基本解

一般情况下，顶点可能是指数级别的

Weak Duality

  • 对偶问题

对于一个特定的线性规划：

记\(A = (A_1, A_2, ..., A_m)^T = (A_1', A_2',...,A_n')\)

即\(A_1, ..., A_m\)为行向量，\(A_1', ..., A_n'\)为列向量 \[ \begin{aligned} & \max c_1x_1 + c_2x_2 + ... +c_nx_n \\s.t. &\;A_1^T x\leq b_1, A_2^T x \leq b_2, ..., A_m^T x \leq b_m \\ &\;x_1, x_2,...,x_n \geq 0 \end{aligned} \] 我们定义其对偶问题为 \[ \begin{aligned} &\min b_1y_1 + b_2y_2 + ... + b_my_m \\s.t. &\; (A_1')^Ty_1 \geq c_1, ..., (A_n')^Ty_n \geq c_n \\&\;y_1, ..., y_m \geq 0 \end{aligned} \] 用矩阵形式给出，也就是 \[ \begin{aligned} &\max c^T x && \min b^Ty \\s.t.&\;Ax \leq b &s.t.&\;A^Ty \geq c \\ &\;x \geq 0 &&\;y \geq 0 \end{aligned} \]

  • 弱对偶性定理

对于任何最大化LP中的可行解\(x\)，与对偶的最小化LP中的可行解\(y\)，都有\(c^T x \leq b^T y\)

证明：\(c^T x \leq (y^T A) x = y^T(Ax) \leq y^T b = b^T y\)

上述定理告诉我们，如果\(c^T x^* = b^T y^*\)，那么\(x^*, y^*\)为最优解

  • 强对偶性定理

如果最大化LP中存在最优解\(x^*\)，那么最小化LP中存在最优解\(y^*\)，并且\(c^T x^* = b^T y^*\)

  • 互补松弛条件

考查弱对偶性中的取等条件：\(c^T x \leq (y^T A) x = y^T(Ax) \leq y^T b = b^T y\)

\(c^T x \leq (y^T A) x\)取到等号，当且仅当要么\(x_i = 0\)，要么\((y^T A)_i = c_i\)

\(y^T(Ax) \leq y^T b\)取到等号，当且仅当要么\(y_j = 0\)，要么\((Ax)_j = b_j\)

Minimax Theorem

\(\max_x \min_y x^T Ay = \min_x \max_y x^T Ay\)

其中，\(\sum x_i = \sum y_i = 1, x_i, y_i \geq 0\)

\(\max_x \min_y x^T A y = \max_x \min_j (x^T A)_j\)，而后者可以写为一个线性规划： \[ \begin{aligned} & \max_x t \\ s.t. &\; x^T A \geq t \bf{1} \\ &\; \sum x_i = 1 \\ &\; x \geq 0 \end{aligned} \] 这个线性规划的对偶问题为（下面的\(\min t\)实际上对应了原问题中的\(\sum x_i = 1\)） \[ \begin{aligned} &\min_y t \\ s.t. &\; Ax \leq t \bf{1} \\ &\; \sum y_i = 1 \\ &\; y \geq 0 \end{aligned} \] 而这个问题的最优解恰好就是\(\min_y \max_x x^T Ay\)

弱对偶性定理实际上告诉我们\(\max_x \min_y x^T A y \leq \min_y \max_x x^T A y\)

根据强对偶性定理，两者可以取到等号

Multiplicative weight update

  • 背景

考虑这么一个问题，有\(n\)个人在工作，其中第\(i\)个人在第\(T\)天会产生\(l_i^{(t)}\)的价值（价值不一定是非负数），我们希望找到工作的最好的一个人，也即使得\(\sum l_i^{(t)}\)最大的\(i\)

不过，我们加上下面的限制：你需要在每一天选择一个人工作，但是你只能知道在\(1, 2, ..., T-1\)天所有人的工作价值

注意：这里的人是抽象的人，并不一定要满足某种特殊的规律，\(l_i^{(t)}\)可以是符合经验的，可以是随机的，甚至可以是对抗你的算法的

  • MWU算法

我们考虑给每个人一个权重，如果一个人某一天生产的价值为正数，那么他的权重相应程度增加，也即

固定参数\(\eta \leq 1/2\)，对于每个人定义一个初始权重\(w_i^{(1)} = 1, \forall 1 \leq i \leq n\)

之后，对于每天进行如下的决策

  1. 以\(p_i^{(t)} = w_i^{(t)} / (\sum_{i=1}^n) w_i^{(t)}\)选择第\(i\)个人
  2. 之后得到人们第\(T\)天的表现
  3. 更新权重，\(w_i^{(T+1)} = w_i^{(T)} * (1 - \eta l_i^{(T)})\)
  • MWU定理

假设\(l_i^{(t)} \in [-1, +1], \forall i, t\)，并且\(l_*\)是表现最好的人，那么MWU算法的期望价值满足

\(\sum_{t=1}^T \langle l^{(t)}, p^{(t)} \rangle \leq \sum_{t=1}^ T l_*^{(t)} + \eta \sum_{t=1}^T |l_*^{(t)}| + \ln n / \eta\)

证明：我们来考虑\(\Phi^{(t)} = \sum_{t=1}^n w_i^{(t)}\)进行上下界的估计

上界：\(\Phi^{(t+1)} = \sum_{i=1}^n w_i^{(t)} - \eta \langle l^{(t)}, w^{(t)} \rangle = \Phi^{(t)} (1-\eta \langle l^{(t)}, p^{(t)}\rangle) \leq \Phi^{(t)} e^{-\eta \langle l^{(t)}, p^{(t)}\rangle}\)

下界：\(\Phi^{(t)} = \sum_{i=1}^n w_i^{(t)} \geq w_*^{(t)} = \prod_{i=1}^T (1-\eta l_*^{(i)}) \geq (1-\eta)^{\sum_{\geq 0} l_*^{(t)}} (1+\eta)^{-\sum_{<0} l_*^{(t)}}\)

这里用到了\(1 - \eta x \geq (1-\eta)^x, x\in [0,1]\)以及\(1-\eta x \geq (1+\eta)^x, x \in [-1,0]\)

结合上下界进行整理就可以得到结论

因此，我们的价值离最优解最多相差\(\eta T + \ln n / \eta\)，取\(\eta = \sqrt{\ln n / T}\)，这个量级差不多是\(O(\sqrt{T \ln n})\)的

此时，平均每天的遗憾为\(\sqrt{\ln n / T}\)，当\(T\)足够大时，遗憾将趋于0

  • 使用MWU定理证明Minimax Theorem

略