Machine Learning

当目标函数中有不可微部分时，可使用近端梯度下降来优化（Proximal Gradient Descent） 假设目标函数如下： $$ \definecolor{energy}{RGB}{114,0,172} \definecolor{freq}{RGB}{45,177,93} \definecolor{spin}{RGB}{251,0,29} \definecolor{signal}{RGB}{18,110,213} \definecolor{circle}{RGB}{217,86,16} \definecolor{average}{RGB}{203,23,206} \definecolor{red}{RGB}{255,0,0} f(w) = g(w) + h(w) $$ 其中$g(w)$是可微凸函数，$h(w)$是不可微（或局部不可微）凸函数。 以线性回归为例， 给定$X \in \mathbb{R}^{m \times n}$, $y \in \mathbb{R}^m$， Ridge Regression的目标函数为 $$ f(\boldsymbol{w})=\underbrace{\frac{1}{2}||\boldsymbol{y}-\boldsymbol{X} \boldsymbol{w}||_{2}^{2}}_{g(\boldsymbol{w})}+\underbrace{\lambda||\boldsymbol{w}||_{2}}_{h(\boldsymbol{w})} $$ 因为$\ell_2$ norm处处可导，所以Ridge可以用SGD或GD来直接优化。但是若目标函数为Lasso，即正则化项定义为$\ell_1$ norm: $$ f(\boldsymbol{w})=\underbrace{\frac{1}{2}||\boldsymbol{y}-\boldsymbol{X} \boldsymbol{w}||_{2}^{2}}_{g(\boldsymbol{w})}+\underbrace{\lambda||\boldsymbol{w}||_{1}}_{h(\boldsymbol{w})} $$ 这里$h(w)=\lambda||\boldsymbol{w}||_{1}$在$w=0$处不可导，那么可用PGD来优化。 Proximity Operator 近端算子： 对于不可微函数$h(w)$, $h(w)$的proximity operator定义为： $$ u^* = \operatorname{prox}_{\color{signal}h}(w)=\underset{u}{\arg \min }\left(h(u)+\frac{1}{2}||u-w||_{2}^{2}\right) $$ 近端算子$\operatorname{prox}_{\color{signal}h}(w)$只和不可微凸函数$h(\cdot)$有关。 上式含义，给定一个不可微凸函数$h(\cdot)$, 给定向量$w \in \mathbb{R}^n$, 找到向量$u = u^*$, 使得公式$h(u)+\frac{1}{2}||u-w||_{2}^{2}$最小。 这个$u^* = \operatorname{prox}_{\color{signal}h}(w)$就是$h(\cdot)$在给定$w$条件下的近端算子（Proximity Operator）。$u^* = \operatorname{prox}_{\color{signal}h}(w)$要求最佳的$u^* $可以使得函数值$h(u^*)$尽可能小，同时$u^*$要尽可能接近给定的$w$。 ...

Introduction The spectral graph theory studies the properties of graphs via the eigenvalues and eigenvectors of their associated graph matrices: the adjacency matrix and the graph Laplacian and its variants. The Laplacian allows a natural link between discrete representations, such as graphs, and continuous representations, such as vector spaces and manifolds. The most important application of the Laplacian is spectral clustering that corresponds to a computationally tractable solution to the graph partitionning problem. Another application is spectral matching that solves for graph matching. ...

最大似然估计MLE 数据 $X = \{x_1, \cdots x_N\}$, 模型参数为$\theta$，Likelihood 定义为 $P(X | \theta)$：当参数为$\theta$时，观测到给定数据$X$的概率。 $$ P(X|\theta) = L(\theta | X) = P_\theta(X) \tag{1} $$ 最大似然估计 （Maximum Likelihood Estimation, MLE）: $$ \theta_{\mathrm{MLE}} = \arg \max_\theta P(X|\theta) \tag{2} $$ 最大似然估计：给定一组样本$X$，模型的参数$\theta$是研究对象。若能找到参数$\theta_{\mathrm{MLE}}$，使得样本发生的可能性最大，则此估计值$\theta_{\mathrm{MLE}}$为参数$\theta$的最大似然估计。 举例来说，如果模型是单个Gaussian Distribution下，参数为Gaussian Distribution的参数（均值$\mu$, 标准差$\Sigma$， $\theta = {\mu, \Sigma}$）. 给定一组数据$X$, 要计算$X$来自什么样的Gaussian，即：$P(\cdot | \theta) = f_\theta(\cdot) = \mathcal{N}(\cdot | \mu,\Sigma)$是一个Gaussian Distribution函数，目标为： $$ \theta_{\mathrm{MLE}} = \mu^\star, \Sigma^\star = \arg \max_{\mu,\Sigma} \sum^N_{i = 1} \log \mathcal{N}(x_i|\mu,\Sigma) \tag{3} $$ 即MLE的目标是找到最佳的高斯分布，是的从该分布中采样出数据$X$的概率最高。 ...

Mean Discrepancy (MD)均值差异 判断2个分布$p$ 和$q$是否相同。 $p$分布生成一个样本空间$\mathbb{P}$ (从$p$中采样$m$个样本) $q$分布生成一个样本空间$\mathbb{Q}$（从$q$中采样$n$个样本） 函数$f$的输入为 分布生成的样本空间 如果 $$ \begin{equation} \begin{aligned} \mathrm{mean}(f(\mathbb{P})) == \mathrm{mean}(f(\mathbb{Q})) \\ i.e., \frac{1}{m}\sum^m_{i=1}f(p_i) = \frac{1}{n}\sum^n_{i=1}f(q_i) \end{aligned} \end{equation} $$ 则$p$和$q$是同一分布。 MD can be defined as $$ \begin{equation} \begin{aligned} \mathrm{MD}&=|\mathrm{mean}(f(\mathbb{P})) -\mathrm{mean}(f(\mathbb{Q})) | \\ &= |\frac{1}{m}\sum^m_{i=1}f(p_i) - \frac{1}{n}\sum^n_{i=1}f(q_i)| \end{aligned} \end{equation} $$ Maximum Mean Discrepancy (MMD) 最大均值差异 定义 MMD: 在函数集$\mathcal{F}=\{f_1, f_2, \cdots \}$中， 找到一个函数$f^*$， 使得$|\mathrm{mean}(f^*(\mathbb{P})) -\mathrm{mean}(f^*(\mathbb{Q})) |$ 最大。 这个最大值就是两个分布之间的最大均值差异（MMD）。MMD =0 表示两个分布相同。 $$ \operatorname{MMD}[\mathcal{F}, p, q]:=\sup _{f \in \mathcal{F}}\left(\mathbf{E}_{x \sim p}[f(x)]-\mathbf{E}_{y \sim q}[f(y)]\right) $$ 其中$\mathbf{E}_{x \sim p}[f(x)]$表示分布$p$在函数$f$下的均值， $\sup$为上确界直接理解为max就好。 ...

Hilbert Space Definition 1 (Norm) Let $\mathcal{F}$ be a vector space over $\mathbb{R}$ (For example $\mathcal{F}=\mathbb{R}^n$ is a vector space). A function $||\cdot||_{\mathcal{F}}: \mathcal{F} \to [0, \inf)$ is said to be a norm on $\mathcal{F}$ if ($||\cdot||_{\mathcal{F}}$ 是一个有效norm算子要满足以下条件): For $f \in \mathcal{F}$, $||f||_{\mathcal{F}}=0$ if and only if $f=0$. (norm separates points) $|\lambda f|_{\mathcal{F}}=|\lambda||f|_{\mathcal{F}}$, $\forall \lambda \in \mathbb{R}, \forall f \in \mathcal{F}$ (positive homogeneity). $|f+g|_{\mathcal{F}} \leq|f|_{\mathcal{F}}+|g|_{\mathcal{F}}, \forall f, g \in \mathcal{F}$ (triangle inequality). 向$||\cdot||_{\mathcal{F}}$中输入任意一个向量，只要满足以上条件，那么$||\cdot||_{\mathcal{F}}$是一个valid norm operator. ...

单一状态Monte Carlo规划：多臂赌博机（Multi-armed bandits） 单一状态$s$, $k$种action（$k$个摇臂）。 在摇臂赌博机问题中，$s$每次以随机采样形式采取一种行动$a$。 例如，随机拉动第$k$个赌博机，得到的reward为$R(s, a_k)$。问下一次拉动哪个赌博机，才能获得最大Reward? 多臂赌博机问题是一种序列决策问题，这种问题需要在利用（exploitation）和探索（exploration）之间保持平衡。 利用（Exploitation）： 保证在过去决策中得到最佳回报 探索（Exploration）：寄希望在未来能够得到更大的汇报 例如， $s$摇动10次赌博机，其中第5次获得最大回报，那么下一次摇动赌博机可能选第5个赌博机，即“利用”（根据过去的最佳回报来施展下一次行为），第11次摇动的action为$a_5$。 但是摇动10次后，可能有的赌博机尚未摇动，未摇动的赌博机可能会有更大回报，即“探索”。 悔值函数 如果有$k$个赌博机， 这$k$个赌博机产生的操作序列为$X_{i,1}, X_{i,2}, \cdots (i = 1,\cdots, k)$。 在时刻$t=1,2,\cdots$, 选择第$I_t$个赌博机后，可得到的奖励为$X_{I_t,t}$, 则在$n$次操作$I_1,\cdots,I_n$后，可如下定义悔值函数： $$ R_n = \max_{i=1,\cdots,k} \sum^n_{t = 1} X_{i,t}-\sum^n_{t=1}X_{I_t, t} $$ $i$: 第$i$个赌博机 $I_t$: $t$时刻选择的赌博机 $\max_{i=1,\cdots,k} \sum^n_{t = 1} X_{i,t}$: 最理想（大）的奖励 $X_{I_t, t}$: $t$时刻选择赌博机$I_t$的reward $\sum^n_{t=1}X_{I_t, t}$: $n$次选择的总奖励。 $R_n$越大，就代表$n$次决策的结果越差。 上置信区间（Upper Confidence Bound, UCB） UCB旨在探索和利用间去的平衡 在UCB方法中，使$X_{i, T_{i}(t-1)}$ 来记录第$i$个赌博机在过去$t-1$时刻内的平均奖励，则在第$t$时刻，选择使如下具有最佳上限置信区间的赌博机： $$ I_{t}=\max_{i \in{1, \ldots, k}}\left\{\overline{X_{i, T_{i}(t-1)}}+C_{t-1, T_{i}(t-1)} \right\}. $$ 其中$I_{t}$为$t$时刻要摇的赌博机， ...

最近在看GNN/GCN的时候遇到谱聚类，学了下，做了些笔记。 本文主要参考了：[1] https://www.cnblogs.com/pinard/p/6221564.html#!comments Introduction 谱聚类是图论中的算法，主要思想是空间中距离较远的两个点之间边的权重值较低， 距离较近的两个点之间边的权重值较高， 通过对所有数据点组成的图（Graph）进行切图， 使不同子图之间边的权重和尽可能低， 子图内边的权重值的和尽可能高，从而达到聚类的目的。 基础1： 无向权重图 对于边$(v_i,v_j)$, 它的权重$w_{ij} > 0$。对于没有边的节点$v_i$和$v_j$, 他们之间的权重$w_{ij}=0$。图中的节点$v_i$, 它的度$d_i$定义为和它连接的所有边的权重之和，即： $$ d_i = \sum_{j=1}^n w_{ij} $$ 根据所有节点的度值，我们可以得到一个度矩阵$D$: $$ D=\displaystyle \left(\begin{array}{ccc}{d_{1}} & {\ldots} & {\ldots} \\\ {\ldots} & {d_{2}} & {\ldots} \\\ {\vdots} & {\vdots} & {\ddots} \\\ {\ldots} & {\ldots} & {d_{n}}\end{array}\right) ^{n\times n} $$ 是一个$n \times n$的对角阵，对角元素是每个节点的度和。 定义图的邻接矩阵为$W \in \mathbb{R}^{n \times n}$， 每个元素$W_{ij}$表示节点对$(v_i,v_j)$之间的权重。 对于$V$中的一个子节点集$A \subset V$， 定义： $$|A|=A 中的节点个数 $$ $$vol(A) = \sum_{i \in A} d_i \quad 表示A中所有节点的权重之和$$ ...

最近想好好学一学Deep Learning中的优化算法（不能一直Adam了），看了一些文献，用这篇文章做个总结笔记。 Gradient Desent(梯度下降) 目标函数$f(x)$，其中$x$为模型的待优化参数，对于每个epoch $t$, $\eta_t$表示第$t$个epoch的步长。$x_t$第$t$个epoch时的参数。 (1).梯度下降的原理：目标函数（损失函数）$f(x)$关于参数$x$的梯度是损失函数上升最快的方向。所以只要让$x$沿梯度的反方向走，就可以缩小目标函数。 (2).目标函数关于参数$x$在epoch $t$时的梯度： $$g_t = \nabla_x f(x_t)$$ (3).我们要最小化$f(x)$, 所以参数$x$需要往梯度的反方向移动： $$x_{t+1} = x_t-\eta_t g_t$$ 其中$x_{t+1}$为$t+1$时刻的参数值。 Stochastic Gradient Desent(随机梯度下降) 梯度下降存在的问题有鞍点问题以及无法找到全局最优解的问题。所以引入SGD。 首先给出无偏估计的定义，稍后会用到： 无偏估计：估计量的均值等于真实值，即具体每一次估计值可能大于真实值，也可能小于真实值，而不能总是大于或小于真实值（这就产生了系统误差）。 深度学习中，目标函数通常是训练集中各个样本损失的平均，假设一个batch的大小为$n$，那么训练这个batch的损失就是$f_{batch}(x) = \frac{\displaystyle\sum_{i=1}^{n} f_i(x)}{n}$ , 所以目标函数对$x$的梯度就是： $$\nabla f_{batch}(x) = \frac{1}{n} \displaystyle\sum_{i=1}^n \nabla f_i(x)$$ 如果使用GD来优化： $$x_{t+1} = x_{t}- \eta_t \frac{1}{n} \displaystyle\sum_{i=1}^n \nabla f_i(x) \ = x_t-\eta_t \nabla f_{batch}(x)$$ 上式可以看出，当训练样本非常大时，n也将边的非常大，那么梯度计算的计算开销就比较大。 随机梯度下降（SGD）的思想是： 以一个batch为例，这个batch中有n个样本，每个样本$i \in {1, \cdots,n}$, 每次从中随机选取一个样本来更新参数$x$。 $$x_{t+1} = x_{t}-\eta_t \nabla f_i(x)$$ 这样就更新了一个batch的参数。 对比上面两个式子可以看出SGD降低了计算复杂度。上面两个式子是等价的，因为随机梯度$\nabla f_i(x)$是对梯度$\nabla f_{batch}(x)$的无偏估计，因为： $$E_i \nabla f_i(\boldsymbol{x}) = \frac{1}{n} \sum_{i = 1}^n \nabla f_i(\boldsymbol{x}) = \nabla f_{batch}(\boldsymbol{x})$$ 符合无偏估计的定义。 ...