梯度下降

梯度下降法是一种常用的一阶优化方法，是求解无约束优化问题方法之一。

原理：考虑无约束优化问题$$\min_x f(x)$$，其中$f(x)$为连续可微函数，若能构造一个序列$x^0,x^1,x^2,…$满足$$f(x^{t+1}) < f(x^t),\ t=0,1,2…$$

对偶问题

再来看不等式约束优化问题：

$$
\begin{aligned}
&\min\limits_{x} \ f(x)\\
&s.t.\ \ h_i(x)=0,\ i=1,2,…,m\\
&g_j(x) \leq 0,\ j=1,2,…,n\\
\end{aligned}
$$

定义Lagrange如下：
$$
L(x,\lambda,\mu)=f(x)+\sum\limits_{i=1}^m\lambda_ih_i(x)+\sum\limits_{j=1}^n\mu_jg_j(x)
$$

在优化理论中，目标函数 f(x) 会有多种形式：

拉格朗日乘子法

拉格朗日乘子法（Lagrange multipliers）是一种寻找多元函数在一组约束下的极值的方法。通过引入拉格朗日乘子，可将有$d$个变量与$k$个约束条件的最优化问题转化为具有$d+k$个变量的无约束优化问题求解

基本的拉格朗日乘子法就是求函数$f(x_1,x_2,…)$在$g(x_1,x_2,…)=0$的约束条件下的极值的方法。主要思想是将约束条件与原函数联系在一起，使能配成与变量数量相等的等式方程，从而求得原函数极值的各个变量的解。

例子：假设需要求极值的目标函数为$f(x)$，约束条件为$\phi(x,y)=M$

主动学习与半监督

假设我们有训练样本集$D_l={ (x_1,y_1),(x_2,y_2),…,(x_l,y_l) }$，l个样本的类别标记已知，称为有标记（labeled）；此外还有$D_u={ x_1,x_2,…,x_u },l \ll u$，这u个样本样本的类别标记未知，称为未标记的unlabeled样本。

若直接使用之前一直介绍的监督学习，则仅有$D_l$能用于构建模型，剩余的未标记样本都浪费了；另一方面远小于u数量的标记样本往往由于训练样本不足，学得模型的泛化能力往往不佳。

范数

• $L_0$范数表示向量中非零元素的个数：$\mid\mid x \mid\mid_0 = count(x_i) while x_i \neq 0$

使用这个范数希望参数的大部分元素是0（稀疏数据），通过最优化范数，可以寻找最优稀疏特征，不过这个范数的最优问题是NP难度。

• $L_1$范数表示向量中每个元素绝对值的和：$\mid\mid x \mid\mid_1=\sum_{i=1}^n \mid x_i \mid$

k近邻学习

k近邻（k-Nearest Neighboor，KNN）是一种常用的监督学习方法：给定测试样本，基于某种距离距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个训练样本的信息对本样本进行预测。分类学习中通常使用投票法，少数服从多数；回归学习中则使用平均法。通常为了体现出靠近的距离指标，在分类学习与回归学习中使用加权法，越靠近样本的权值越大。

给定测试样本x，若其最近邻样本为z，则最近邻分类器出错的概率就是x与z类别标记不同的概率：$P(err)=1-\sum\limits_{c \in y}P(c \mid x)P(c \mid z)$

机器学习可以根据样本是否有标签分类为有监督学习与无监督学习，前面介绍的基本都是有监督学习。无监督学习中，目标通过对无标记训练样本的学习来揭示数据的内在性质及规律。

聚类试图将数据集中的样本划分为若干个通常不相交的子集，每个子集称为一个簇（cluster）。通过这样的划分，每个簇可能对应与一些潜在的类别。这些类别两两不相交，并起来是整个数据集，聚类的结果就是产生一个标签结果序列。

个体集成

集成学习通过构建并结合多个学习器来完成学习任务，先产生一组个体学习器，再用某种策略把他们结合起来。个体学习器通常由一个现有的学习算法从训练数据产生。

同质集成：个体全是相同类型的学习器，称为基学习器

异质集成：个体可以是不同的学习器，称为组件学习器

根据个体学习器的生成方式，目前的集成学习方法大致分为两大类，即个体学习器间存在强依赖关系、必须串行生成的序列化方法Boosting；以及不存在强依赖关系，可同时生成的并行化方法Bagging和随机森林。