分类目录归档：数学

机器学习中的玻尔兹曼分布——最小代价和极大似然.

发表于由

看了一些机器学习的论文，我一直有一个困惑：有的文章训练时写的公式是最小化代价函数，有的文章训练时写的是一个跟自然对数有关的概率分布，这是为什么？经过一番学习，终于有了答案。在这个过程中，还有一个意外收获：那就是著名的逻辑斯第函数的由来。

物理上和统计上的玻尔兹曼分布

热平衡在物理学领域通常指温度在时间或空间上的稳定。在统计学习中，如果我们将需要学习的模型看成高温物体，将学习的过程看成一个降温达到热平衡的过程，最终模型的能量将会收敛为一个分布，并且在全局极小能量上下波动。这个过程称为“模拟退火”。而模型能量收敛到的分布称为玻尔兹曼分布（Boltzmann Distribution）。

在物理学中，玻尔兹曼分布，也称为吉布斯分布（Gibbs Distribution），描述了一个粒子系统处于各种状态的概率，其表达式如下：

F(state) \propto \exp{(-\frac{E}{kT})}

其中E是状态能量，kT是玻尔兹曼常数$k$与热力学温度T的乘积。

在统计学中，玻尔兹曼分布给出了一个系统在特定状态能量和系统温度下的概率分布：

p_i = \frac{\exp{(-E_i /kT)}}{\sum_{j=1}^M \exp{(-E_j /kT)}}

其中p_i是状态$i$出现的概率，E_i是状态能量，k是玻尔兹曼常数，T是系统的温度，M是系统的状态数量（系统状态是离散的，有限的；找到了一点高中物理原子的电子跃迁的感觉，那状态也是离散的！！！）。所以说，统计学中玻尔兹曼分布的使用是受到了物理中热力学的启发。

从玻尔兹曼分布的定义，我们可以发现系统的两个不同状态的概率之比仅与系统能量有关：

\frac{F(state2)}{F(state1)} = \exp{(\frac{E_1 - E_2}{kT})}

这个比值被称为玻尔兹曼因子（Boltzmann Factor）。

玻尔兹曼机

定义

玻尔兹曼分布在机器学习模型的设计中被广泛采用，我们就从玻尔兹曼机（Boltzmann Machine）说起。

玻尔兹曼机是一个对称连接的神经网络。它用于决定系统的状态是开（1）还是关（0）。玻尔兹曼机可以看成一个通过无向有权边全连接的网络。这个网络的能量函数定义为

E = - (\sum_{i < j} w_{ij} s_i s_j + \sum_i \theta_i s_i)

其中

  • w_{ij}是连接节点$i$和$j$的权重。
  • s_i是节点$i$的状态，且s_i \in \{0, 1\}。
  • \theta_i是节点i的在全局能量函数中的偏倚。也就是说-\theta_i是节点i的激活阈值。

单个节点$i$的能量定义为

E_i = \theta_i + \sum_j w_{ij}s_j

继续阅读 →

Cramer-Rao下界

发表于由

在参数估计和统计中，Cramer-Rao界限（Cramer-Rao bound, CRB）或者Cramer-Rao下界（CRLB），表示一个确定性参数的估计的方差下界。命名是为了纪念Harald Cramer和Calyampudi Radhakrishna Rao。这个界限也称为Cramer-Rao不等式或者信息不等式。

它的最简单形式是：任何无偏估计的方差至少大于Fisher信息的倒数。一个达到了下界的无偏估计被称为完全高效的（fully efficient）。这样的估计达到了所有无偏估计中的最小均方误差（MSE，mean square error），因此是最小方差无偏（MVU，minimum variance unbiased）估计。

给定偏倚，Cramer-Rao界限还可以用于确定有偏估计的界限。在一些情况下，有偏估计方法的结果可能方差和均方差都小于无偏估计的Cramer-Rao下界。

继续阅读 →

线性回归与贝叶斯推理——漫谈机器学习

发表于由

1. 从观察出发——回归问题

在统计学中，我们认为一个变量是服从某种理想分布的，称为理想变量。而为了获得理想变量的值，我们需要去观察这个世界，并得到观察数据，称为观察变量。观察变量与理想变量之间的函数关系被称为观察模型。

设观察数据为x_i \in R^p，理想数据为y_i \in R，观察模型为线性模型

y_i = x_i^T \beta + \eta_i
\tag{1}

其中\beta \in R^p为参数向量，\eta_i \in R是独立同分布的随机变量。在应用中，\eta_i代表观察噪声。且通常假定它服从正态（高斯）分布：

\eta_i \sim N(0, \sigma^2)
\tag{2}

上面的观察模型可以引出两个问题：

  1. 已知理想和观察变量y_i,x_i，求模型参数\beta,\sigma。这被称为参数估计（Paremeter Estimation）问题。
  2. 已知观察变量x_i和模型参数\beta,\sigma，求理想变量y_i。这被称为回归（Regression）问题。如果观察模型是线性的，例如(1)，则称为线性回归问题。

回归的概念非常宽泛，它泛指研究一组变量和另一组变量之间的关系的统计分析方法。考虑变量和参数之间的对称性，不难发现，参数估计也是回归问题。

2. 参数估计——也是回归问题

在统计学习中，参数估计是一个学习样本所蕴含信息的过程。而学习的结果，就是观察模型（包括最优参数）。

继续阅读 →

线性约束最优化问题的Frank-Wolfe方法

发表于由

在无约束最优化问题的基础上，我们可以进一步来求解约束最优化问题。约束最优化问题的一般形式为：
$$
\begin{aligned}
&\min f(x) \\
&s.t. \quad g_i(x)\ge0, i=1,...,m
\end{aligned}
$$

先考虑$g_i(x)$均为线性函数的情况，此时问题与线性规划的约束条件相同，仅仅是目标函数变成了非线性的。我们可以用泰勒展开对目标函数进行近似，将它线性化。将$f(x)$在$x_k$处展开，有
$$
f(x)\approx f(x_k) + \nabla f(x_k)^T(x-x_k)
$$
故原问题近似于
$$
\begin{aligned}
&\min f(x)\approx f(x_k) + \nabla f(x_k)^T(x-x_k) \\
&s.t.\quad x \in S
\end{aligned}
$$
其中$S$为线性约束构成的可行域。去掉常量后，问题可以写为
$$
\begin{aligned}
&\min f(x)\approx \nabla f(x_k)^Tx \\
&s.t.\quad x \in S
\end{aligned}
$$
设此问题的最优解为$y_k$，则直观上$d_k=y_k-x_k$ 应当为原问题的可行下降方向。沿着此方向做一维搜索则可进行一次迭代。为了防止一维搜索的结果超出可行域，我们限制步长$0\leq\lambda\leq1$。注意到线性规划的可行域为凸集，由于$x_k$和$y_k$均为可行点，它们确定的连线均在可行域中。限制步长$0\leq\lambda\leq1$保证了一维搜索的结果在可行域中。

Frank-Wolfe算法的步骤总结如下：

  1. 选择初值。初始点$x_0\in S$，给定允许误差$\epsilon>0$，令$k=0$。
  2. 求解近似线性规划：$$ \begin{aligned}&\min \nabla f(x_k)^Tx \\ &s.t.\quad x \in S\end{aligned}$$ 得最优解$y_k$。
  3. 构造可行下降方向。令$d_k=y_k-x_k$。若$||\nabla f(x_k)^Td_k \leq \epsilon||$，停止计算，输出$x_k$；否则，转4。
  4. 进行一维搜索：$$\min_{0\leq \lambda \leq 1} f(x_k+\lambda d_k)$$得步长$\lambda_k$。令$$x_{k+1}=x_k+\lambda_k d_k \\ k \leftarrow k+1 $$，转2。

Frank-Wolfe方法将线性约束最优化问题转化为一系列线性规划问题和一维搜索问题求解。可以证明，当$f$具有连续一阶偏导数，且可行域$S$有界，Frank-Wolfe方法是收敛的。

无约束最优化方法学习笔记

发表于由

这一段时间学习优化理论中的一些经典方法，写下一些要点和体会，帮助自己和有需要的人理解最优化方法。

１.基础知识

首先来看无约束最优化问题：
\begin{equation}
\min f(x)
\end{equation}
其中函数 $f:R^n\rightarrow R$.求解此问题的方法方法分为两大类：最优条件法和迭代法。

所谓的最优条件法，是指当函数存在解析形式，能够通过最优性条件求解出显式最优解。对于无约束最优化问题，如果$f(x)$在最优点$\bar{x}$附近可微，那么$\bar{x}$是局部极小点的必要条件为：
\begin{equation}
\nabla f(\bar{x})=0
\end{equation}

我们常常就是通过这个必要条件去求取可能的极小值点，再验证这些点是否真的是极小值点。当上式方程可以求解的时候，无约束最优化问题基本就解决了。实际中，这个方程往往难以求解。这就引出了第二大类方法：迭代法。

迭代法，也称为“搜索”法，主要思想是通过简单的运算构造点列，逐渐逼近问题的最优解。这里说的“点”是多维空间中的点，也称为“向量”。还有少部分算法通过构造点的集合来逼近问题的最优解，如单纯形调优法。

用于求解无约束最优化问题的方法可以分为解析法和直接法两大类。解析法在构造迭代公式的过程中往往使用了泰勒展开来作近似或者推导，因此迭代步骤中含有梯度$\nabla f(x)$或黑塞(Hessian)矩阵$\nabla^2f(x)$，在问题的解析形态较好的情况下使用往往能获得比较快的收敛速度。而直接法则从物理角度思考如何递推，不会用到梯度或者黑塞矩阵，它对问题的解析形态几乎没有要求，只要能计算出函数值即可。当然，它的收敛速度往往难于保证。
继续阅读 →