ML——CEM

Summary

CE 方法逐步更新采样分布 $Q$，使其更接近目标分布 $P^*$，从而最小化两者之间的交叉熵
这一过程不仅有助于找到最优解，还能够在高维和复杂问题中有效地进行优化
注：在工业实践中，CEM 方法很容易使用

交叉熵基础定义

Cross Entropy 方法中的 “Cross Entropy” 这个名字来源于信息论中的一个概念
- 在信息论中，交叉熵（Cross Entropy）是用来衡量两个概率分布之间的差异的一个指标，通常用于评估一个概率模型对真实数据分布的拟合程度
给定两个概率分布 $P$ 和 $Q$，其中 $P$ 代表真实的概率分布，而 $Q$ 代表模型预测的概率分布，那么 $P$ 和 $Q$ 之间的交叉熵定义为：
$$ H(P, Q) = -\sum_x P(x) \log Q(x) $$
这里的 $H(P, Q)$ 就是 $P$ 相对于 $Q$ 的交叉熵。当 $Q$ 完美地匹配 $P$ 时，即 $P=Q$，交叉熵达到最小值，此时等于 $P$ 的熵 $H(P)$
- 如果 $Q$ 与 $P$ 不同，那么交叉熵会比 $P$ 的熵大，表示了额外的信息损失或误差

交叉熵损失函数

在优化和机器学习领域，交叉熵经常被用作损失函数，特别是在分类任务中，比如使用神经网络进行图像分类
在这种情况下， $P$ 通常是样本的真实标签分布（例如，对于二分类问题，正类可以表示为 [1, 0]，负类为 [0, 1]），而 $Q$ 是模型预测的概率分布
通过最小化交叉熵损失函数，可以训练模型更好地拟合训练数据

交叉熵方法名字的来源

Cross Entropy 方法本身是一种用于优化和采样的算法，它最初是从稀有事件模拟中发展出来的
- 该方法通过迭代地从候选解集中采样，并根据这些样本计算出一个精英集的概率分布，然后利用这个分布来指导下一步的采样过程
在这个过程中，算法实际上是在尝试最小化目标分布（最优解的分布）和当前采样分布之间的交叉熵，因此得名“Cross Entropy 方法”
- 这种方法能够有效地解决一些复杂的优化问题，尤其是在高维空间中寻找最优解的问题

交叉熵方法的核心思想

在 Cross Entropy (CE) 方法中，最小化目标分布 $P^*$ （最优解的分布）和当前采样分布 $Q$ 之间的交叉熵是一个核心思想
这个过程可以通过以下步骤来理解：

定义目标

首先定义目标是找到一个分布 $Q$，使得 $Q$ 尽可能接近目标分布 $P^*$
- 这里 $P^*$ 通常是一个难以直接求解的分布，因为它对应于所有可能解中的最优解

交叉熵作为度量

使用交叉熵 $H(P^*, Q)$ 作为度量 $P^*$ 和 $Q$ 之间差异的标准，交叉熵定义为：
$$ H(P^*, Q) = -\sum_x P^*(x) \log Q(x) $$
这里 $x$ 表示解空间中的一个点， $P^*(x)$ 是 $x$ 属于最优解的概率，而 $Q(x)$ 是 $x$ 被当前采样分布选中的概率

精英集的选择

在 CE 方法中，我们并不直接计算 $P^*$，而是通过迭代过程逐步逼近 $P^*$
每一步，我们从当前的分布 $Q$ 中随机采样一组解，然后选择表现最好的一部分解（称为精英集）
假设我们采样了 $N$ 个解，并选择了其中表现最好的 $N_e$ 个解作为精英集

更新分布

接下来，基于精英集来更新分布 $Q$
目标：希望新的 $Q$ 更好地拟合精英集中的解
- 这可以通过计算精英集的统计特性（如均值和协方差）来实现
如果 $Q$ 是一个高斯分布，我们可以计算精英集的均值 $\mu_e$ 和协方差矩阵 $\Sigma_e$，并用它们来更新 $Q$ 的参数：
$$ \mu_{\text{new}} = \frac{1}{N_e} \sum_{i=1}^{N_e} x_i \\
\Sigma_{\text{new}} = \frac{1}{N_e} \sum_{i=1}^{N_e} (x_i - \mu_{\text{new}})(x_i - \mu_{\text{new}})^T $$

重复迭代

上述过程构成了 CE 方法的一个迭代步骤。我们重复执行采样、选择精英集和更新分布的过程，直到 $Q$ 收敛到一个接近 $P^*$ 的分布，或者满足某个停止条件（如达到最大迭代次数或分布变化小于某个阈值）

最小化交叉熵的直观解释

通过选择精英集并更新分布，CE 方法实际上是在逐步减少 $P^*$ 和 $Q$ 之间的交叉熵
这是因为每次迭代后，新的分布 $Q$ 更加集中在那些表现好的解上，从而更接近 $P^*$
从数学上看，选择精英集并更新分布的过程可以看作是在最小化 $P^*$ 和 $Q$ 之间的 KL 散度（Kullback-Leibler divergence），而 KL 散度与交叉熵密切相关：
$$ D_{\text{KL}}(P^* | Q) = H(P^*, Q) - H(P^*) $$
由于 $H(P^*)$ 是常数，最小化 $D_{\text{KL}}(P^* | Q)$ 等价于最小化 $H(P^*, Q)$

ML——AUC和GAUC

本文介绍AUC和GAUC

参考链接

图解AUC和GAUC-知乎

编程实现

AUC计算的3种实现方法

# encoding=utf8
from sklearn.metrics import roc_auc_score

## 实现1：O(Nlog(N))
def calculate_auc1(labels, predictions):
    # 将预测结果和真实标签按照预测结果从大到小的顺序进行排序
    sorted_predictions = [l for _, l in sorted(zip(predictions, labels), reverse=True)]
    print(sorted_predictions)
    # 统计正样本和负样本的数量
    positive_count = sum(labels)
    negative_count = len(labels) - positive_count

    neg_found_count = 0
    pos_gt_neg_count = 0
    # 计算正样本大于负样本的数量之和
    for label in sorted_predictions:
        if label == 1:
            pos_gt_neg_count += negative_count - neg_found_count
        else:
            neg_found_count += 1

    # 计算AUC
    auc = 1.0 * pos_gt_neg_count / (positive_count * negative_count)

    return auc

## 实现2：O(N^2)
def calculate_auc2(labels, predictions):
    pos_indexes = [i for i in range(len(labels)) if labels[i] == 1]
    neg_indexes = [i for i in range(len(labels)) if labels[i] == 0]
    p = len(pos_indexes)
    n = len(neg_indexes)

    pos_gt_neg_count = 0
    for i in pos_indexes:
        for j in neg_indexes:
            if predictions[i] > predictions[j]:
                pos_gt_neg_count += 1
            elif predictions[i] == predictions[j]:
                pos_gt_neg_count += 0.5
    return pos_gt_neg_count/(p*n)

## 实现3：O(Nlog(N))
def calculate_auc3(labels, predictions):
    # 将预测结果和真实标签按照预测结果从小到大的顺序进行排序，注意：排序是从小到大
    sorted_predictions = [[p,l] for p, l in sorted(zip(predictions, labels))]
    print(sorted_predictions)
    # 统计正样本和负样本的数量
    positive_count = sum(labels)
    negative_count = len(labels) - positive_count
    # 统计正样本的序号和，注意：序号从1开始
    positive_count_indexes_sum = sum([i+1 for i in range(len(sorted_predictions)) if sorted_predictions[i][1] == 1])
    return (positive_count_indexes_sum - 0.5*positive_count*(positive_count+1))/(positive_count*negative_count)
    pass

# 真实标签
labels = [1, 1, 0, 0, 1, 1]
# 预测结果
predictions = [0.2, 0.8, 0.3, 0.4, 0.5, 0.6]

# 计算AUC
auc1 = calculate_auc1(labels, predictions)
print("AUC1:", auc1)

# 计算AUC
auc2 = calculate_auc2(labels, predictions)
print("AUC2:", auc2)

# 计算AUC
auc3 = calculate_auc3(labels, predictions)
print("AUC3:", auc3)

# 调用官方库计算AUC
auc = roc_auc_score(labels, predictions)
print("AUC:", auc)

SQL实现

详情见：深入理解AUC
推导思路：
- 统计每个正样本大于负样本的概率（排在该正样本后面的负样本数/总的负样本数）
- 对所有正样本的概率求均值
整体推导流程：
$$
\begin{align}
AUC &= \frac{1}{N_+} \sum_{j=1}^{N_+}\frac{(r_j - j)}{N_-} \\
&= \frac{\sum_{j=1}^{N_+}r_j - N_+(N_+ + 1)/2}{N_+N_-} \\
&= \frac{\sum_{j =1}^{N_+} r_j - N_+(N_+ + 1)/2}{N_+ N_-}
\end{align}
$$
- 注意：以上公式是在按照预估值从大到小排序后的基础上计算的，实际应用上述公式时需要先排序
- 公式符号说明：对于第 $j$ 个正样本 ，假定其排序定义为 $r_j$，则在这个正样本之前共有 $(r_j-1)$ 个样本，其中有 $(j - 1)$ 个正样本，$(r_j-j)$ 个负样本，此时该正样本的预估值大于负样本的概率为：$\frac{(r_j - j)}{N_-}$

SQL实现

select
    (ry - 0.5*n1*(n1+1))/n0/n1 as auc
from(
    select
        sum(if(y=0, 1, 0)) as n0,
        sum(if(y=1, 1, 0)) as n1,
        sum(if(y=1, r, 0)) as ry
    from(
        select y, row_number() over(order by score asc) as r
        from(
            select y, score
            from some.table
        )A
    )B
)C

SQL实现（分场景+pcoc实现）

select 
    scene,
    (ry - 0.5*n1*(n1+1))/n0/n1 as auc,
    n1/(n1+n0) as ctr,
    pctr,
    pctr/(n1/(n1+n0)) as pcoc,
from(
    select 
        scene,
        sum(if(y=0, 1, 0)) as n0,
        sum(if(y=1, 1, 0)) as n1,
        sum(if(y=1, r, 0)) as ry,
        avg(score) as pctr
    from(
        select scene, score, y, row_number() over(partition by scene order by score asc) as r
        from(
            select scene, y, score
            from some.table
        )A
    )B
)C

ML——HMM-MEMM-CRF

本文主要区分隐马尔可夫模型(HMM),最大熵马尔可夫模型(MEMM),和条件随机场(CRF)

HMM

生成式模型
有向图模型,贝叶斯网络

模型描述

模型参数: $\lambda = (A, B, \pi)$
- A为状态转移矩阵
- B为观测概率矩阵
- $\pi$ 为初始状态概率向量
HMM对

假设

观测序列之间独立
当前状态仅仅依赖于上一个状态

问题

概率计算问题: 给定模型 $\lambda = (A, B, \pi)$ 和观测序列 $O=(o_{1}, o_{2},,,o_{n})$，计算在给定模型下观测序列出现的概率 $P(O|\lambda)$
学习问题: 已知观测序列 $O=(o_{1}, o_{2},,,o_{n})$，估计模型参数 $\lambda = (A, B, \pi)$，使得在该模型下观测序列出现的概率 $P(O|\lambda)$ 最大.(极大似然法,EM算法)
预测问题(解码问题): 给定模型 $\lambda = (A, B, \pi)$ 和观测序列 $O=(o_{1}, o_{2},,,o_{n})$，求状态序列 $I=(i_{1}, i_{2},,,i_{n})$，使得 $P(I|O;\lambda)$ 最大,(维特比算法)

序列标注问题

序列标注问题是已知观测序列 $O=(o_{1}, o_{2},,,o_{n})$，求状态序列 $I=(i_{1}, i_{2},,,i_{n})$，使得 $P(I|O)$ 最大
实际上序列标注问题包括学习问题和预测问题两个问题:
- 学习问题: 根据观测序列确定模型参数 $\lambda = (A, B, \pi)$，极大似然法或EM算法(EM算法会同时估计得到最优状态序列(隐变量))
- 预测问题: 根据模型参数和观测序列确定最优状态序列 $I=(i_{1}, i_{2},,,i_{n})$，维特比算法

优点

算法成熟
效率高, 模型简单, 容易训练

缺点

序列标注问题中,当前状态(标注)往往不仅仅和前一个状态相关,还可能和观察序列相关(这里指的是整个序列)
也就是说每个状态可能还与整个观察序列的(除了当前观察值以外的)其他观察值(观察序列上下文)相关

MEMM

判别式模型
有向图模型,贝叶斯网络

假设

当前状态仅依赖于上一状态和当前观测值(或所有观测值)
(问题: 为什么有些书上画出的图是当前状态依赖上一状态和所有观测值?,这里应该是当前观测值和所有观测值两种情况都是MEMM,<<百面>>画的是所有观测值的情况)

问题

MEMM似乎只用于序列标注,也就是在已知观测序列的情况下,寻找最优的状态序列
有其他应用的话再添加

序列标注问题

用于序列标注时,一般也包括两个问题: 学习问题和预测问题
- 学习问题: 根据观测序列确定模型参数(每条边的(概率)值和初始状态?)
- 预测问题: 根据模型和观测序列确定维特比算法

优点

解决了观测独立性问题(观测独立性是只当前观测序列只与当前状态相关)[问题: 在MEMM中并不关心观测序列由谁影响,而是关心观测序列如何影响了状态序列]

缺点

标签偏置(labeling bias)问题
- MEMM中概率最大路径往往容易出现在转移少的状态中
- MEMM归一化在加和函数 $\sum$ 计算内部,而CRF的归一化在加和函数 $\sum$ 的外部,这使得MEMM只会关注加和函数[原始建模问题概率值 $(y_{1…n}|x_{1…n})$ ]的局部特征,而不是的整体特征,所以MEMM存在偏置问题
比HMM复杂

CRF

判别式模型
无向图模型,马尔可夫网络

假设

当前状态仅依赖于上一状态和当前观测值(或所有观测值)
(问题: 为什么有些书上画出的图是当前状态依赖上一状态和所有观测值?,这里应该是当前观测值和所有观测值两种情况都是线性CRFs,<<百面>>画的是所有观测值的情况)
与MEMM的区别就是无向图模型与有向图模型的区别

问题

序列标注问题

优点

模型复杂,能建模更多可能的特征
全局归一化(这里与MEMM的区别是,MEMM归一化在加和函数[原始建模问题概率值 $(y_{1…n}|x_{1…n})$ ] $\sum$ 计算内部,而CRF的归一化在加和函数[原始建模问题概率值 $(y_{1…n}|x_{1…n})$ ] $\sum$ 的外部)

缺点

模型复杂,速度慢

ML——主动学习-半监督学习-直推学习

主动学习(Active Learning), 半监督学习(Semi-Supervised Learning)与直推学习(Transductive Learning)
半监督学习又称为归纳学习(Inductive Learning)

补充知识

“开放世界”假设

学得的模型能适用于训练过程中从未观察到的数据
也就是说:测试集未知

“封闭世界”假设

学得的模型仅仅能适用于训练过程中观察到的未标记样本
也就是说:测试集就是训练时观察到的未标记数据

相同点

都是用于解决有少量标注数据和海量未标注数据的问题的算法
都是迭代扩充标记数据集的算法:
- 每次迭代时添加如一部分新的标记数据(由未标记数据标记产生的)

不同点

主动学习

主动学习添加了专家知识(人工确认或者打标签),每次迭代时加入的新的标记数据都是由专家打出来的标签
半监督学习和直推学习都是全自动的(无需人工干预),主动学习是半自动的

半监督学习与直推学习

直推学习将当前的为标签数据看成是最终的测试数据
半监督学习和主动学习的测试集都是未知数据
半监督学习是基于”开放世界”假设的
直推学习是基于”封闭世界”假设的

总结

总体概览

表格概览

学习算法	是否需要专家知识(人工)	是否具有泛化性
半监督学习	否	是(“开放世界”假设)
主动学习	是	是(“开放世界”假设)
直推学习	否	不具有,测试集是已知的未标记数据(“封闭世界假设”)

ML——MCMC采样

本文介绍MCMC采样法和他的两个常用方法:MH(Metropolis-Hastings)采样法和Gibbs采样法
马尔可夫蒙特卡罗(Markov Chain Monte Carlo, MCMC)采样法

对于高维空间中的随机向量,拒绝采样和重要性采样经常难以找到合适的参考分布,容易导致采样效率低下(样本的接受概率太小或者重要性权重太低),此时可以考虑马尔可夫蒙特卡罗采样法(MCMC)
MCMC中常见的有两种,MH(Metropolis-Hastings)采样法和Gibbs采样法

MCMC概述

马尔可夫蒙特卡罗(Markov Chain Monte Carlo, MCMC)采样法可分为两个部分(两个MC)描述

蒙特卡罗法

蒙特卡罗法(Monte Carlo)是指: 基于采样的数值型近似求解方法

马尔可夫链

又称离散时间马尔可夫链(discrete-time Markov chain，缩写为DTMC),或者马氏链

马尔可夫链(Markov Chain)是指: 状态空间中经过从一个状态到另一个状态的转换的随机过程, 该随机过程满足马尔可夫性
马尔可夫性(Markov property)是指: 当一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态；换句话说，在给定现在状态时，它与过去状态（即该过程的历史路径）是条件独立的，那么此随机过程即具有马尔可夫性质。具有马尔可夫性质的过程通常称之为马尔可夫过程
- 马尔可夫性的简单理解: “无记忆性”: 下一状态的概率分布只能由当前状态决定，在时间序列中它前面的事件均与之无关

MCMC基本思想

针对采样的目标分布,构造一个马尔可夫链 ，使得该马尔可夫链的平稳分布就是目标分布
从任何一个初始状态出发,沿着马尔可夫链进行状态转移,直到马尔可夫链收敛(到达平稳状态)
继续在马尔可夫链上进行状态转移,收敛后继续采样得到的样本就是原始目标分布的样本
- burn-in处理 : 现实应用中,我们需要丢弃收敛前的样本,只保留收敛后的样本
- burn-in 原意为”老化,定型”之意,在这里表示我们只取后面马氏链定型(收敛)后采样得到的样本
- 假设采样到收敛用了n次采样,那么服从原始分布的k个样本为 $(x^{n+1}, x^{n+2},,,, x^{n+k})$ 有时候为了得到近似独立的样本,可以间隔每r次再取出其中一个样本 $(x^{n+r}, x^{n+2r},,,, x^{n+kr})$
- 真正独立同分布的k个样本可用多条k条不同的收敛后的马氏链得到,不同马氏链采样得到的样本是独立同分布的
核心: 马尔可夫链的构造 ，也就是确定马尔可夫链的状态转移概率

常见的MCMC方法

MH(Metropolis-Hastings)采样法

对于原始目标分布 $p(x)$
选择一个参考条件分布 $q(x^{\star}|x)$，定义接受概率 $A(x,x^{\star})$：
- (注意这里是参考条件分布,因为是马尔可夫链,所以每个状态都由上一个状态转移而来,需要定义的参考分布应该是条件分布,不是一般拒绝采样中的普通参考分布)
  $$
  A(x,x^{\star}) = min\left ( 1, \frac{p(x^{\star})q(x|x^{\star})}{p(x)q(x^{\star}|x)} \right )
  $$
MH采样法构建满足平稳分布就是目标分布 $p(x)$ 的秘诀就是让每次采样时,当前状态以一定概率停留在上一状态
- 与拒绝采样对应: 接受意味着跳转到下一状态,拒绝意味着停留在当前状态

采样过程

随机选取初始样本x^{0}
for t = 1,2,3,…:
- 参考条件分布采样 $x^{\star} \sim q(x^{star}|x^{t-1})$
- 均匀分布采样 $u \sim U(0,1)$
- 判断是否接受: 如果 $u < A(x^{t-1}, x^{\star})$，则接受,令: $x^{t} = x^{\star}$，否则拒绝,令: $x^{t}=x^{t-1}$
burn-in处理 : 丢弃采样到平稳分布前的样本, 只保留平稳分布后的样本即为服从原始分布 $p(x)$ 的样本
- 假设采样到收敛用了n次采样,那么服从原始分布的k个样本为 $(x^{n+1}, x^{n+2},,,, x^{n+k})$ 有时候为了得到近似独立的样本,可以间隔每r次再取出其中一个样本 $(x^{n+r}, x^{n+2r},,,, x^{n+kr})$
- 真正独立同分布的k个样本可用多条k条不同的收敛后的马氏链得到,不同马氏链采样得到的样本是独立同分布的
采样次数一般来说是凭经验选择一个足够大的值,现实是现实可以使用一些参数变化量这类的指标来判断采样是否收敛,参考NLP——LLDA的Gibbs采样实现

与拒绝采样的区别

MH采样基于拒绝采样来逼近平稳分布
拒绝采样中: 如果样本某一步被拒绝,那么该步不会产生新的样本,需要重新对当前步进行采样
MH中: 每一步都会产生一个样本,被拒绝后,就令当前样本和上一个样本相同即可
- 因为这里是为了使得每个状态的转出概率等于转入概率,所以拒绝就意味着当前采样步骤状态不跳转
- MH采样法最核心的思想就是一定概率停留在上一个状态来实现对马尔可夫链的构建的

MH采样法正确性证明

MH采样法构造的马尔可夫链(状态转移概率矩阵)是正确的吗?
细致平稳条件 ，如果非周期的马氏链的状态转移矩阵P和分布 $\pi(x)$ 满足下面的式子对任意的 $i,j$ 都成立:
$$\pi(x^{i})P_{ij} = \pi(x^{j})P_{ji}$$
- 上式为细致平稳分布条件(detailed balance condition)
- 其中 $\pi(x)$ 为马氏链的平稳分布,在这里等于我们的原始分布 $p(x)$
证明 $\pi(x)$ 为马氏链的平稳分布:
$$
\begin{align}
\sum_{i=1}^{\infty}\pi(x^{i})P_{ij} = \sum_{i=1}^{\infty}\pi(x^{j})P_{ji} = \pi(x^{j})\sum_{i=1}^{\infty}P_{ji} = \pi(x^{j}) \\
=> \pi(x) P = \pi(x)
\end{align}
$$
- 由于 $\pi(x)$ 为方程 $\pi(x) P = \pi(x)$ 的解,所以 $\pi(x)$ 是状态转移矩阵P对应的马氏链的平稳分布
在MH采样法中
- 参考条件分布函数本对应状态转移矩阵的一个元素, $q(x^{i}|x^{j}) = P_{ij}$ (注意: 实际上一般不相等)
- 但是很难构造这样方便采样的函数,于是我们使用一个接受率来修正 $q(x^{i}|x^{j})\alpha(x^{j}, x^{i}) = P_{ij}$
  - $\alpha(x^{j}, x^{i})$ 表示从 $x^{j}$ 跳转到 $x^{i}$ 的接受率, 其值可如下求得:
    $$
    \begin{align}
    \pi(x^{i}) P_{ij} &= \pi(x^{j})P_{ji} \\
    \pi(x^{i}) q(x^{j}|x^{i})\alpha(x^{i}, x^{j}) &= \pi(x^{j})q(x^{i}|x^{j})\alpha(x^{j}, x^{i})
    \end{align}
    $$
- 显然,直接取:
  $$
  \begin{align}
  \alpha(x^{i}, x^{j}) &= \pi(x^{j})q(x^{i}|x^{j})\\
  \alpha(x^{j}, x^{i}) &= \pi(x^{i})q(x^{j}|x^{i})\\
  \end{align}
  $$
- 即可
但是由于 $\alpha(x^{j}, x^{i})$ 一般来说太小,所以我们考虑将 $\alpha(x^{j}, x^{i})$ 和 $\alpha(x^{i}, x^{j})$ 同时扩大M倍,使得其中大的那个为1,即可得到最大的接受率
- 使用原始接受率的方法称为一般MCMC方法
- 使用扩大M被接受率的方法称为MCMC的改进方法: MH方法
改进后的接受率为从 $x^{i}$ 跳转到 $x^{j}$ 的接受率:
$$
\begin{align}
A(x^{i}, x^{j}) = min\left ( 1, \frac{p(x^{j})q(x^{i}|x^{j})}{p(x^{i})q(x^{j}|x^{i})} \right )
\end{align}
$$
- 理解:
  $$
  \begin{align}
  p(x^{j})q(x^{i}|x^{j}) &> p(x^{i})q(x^{j}|x^{i})时: A(x^{i}, x^{j}) = 1 \\
  p(x^{j})q(x^{i}|x^{j}) &< p(x^{i})q(x^{j}|x^{i})时: A(x^{i}, x^{j}) = \frac{p(x^{j})q(x^{i}|x^{j})}{p(x^{i})q(x^{j}|x^{i})}
  \end{align}
  $$
在MH中表现为从 $x$ 跳转到 $x^{\star}$ 的接受率:
$$
A(x,x^{\star}) = min\left ( 1, \frac{p(x^{\star})q(x|x^{\star})}{p(x)q(x^{\star}|x)} \right )
$$

Gibbs采样法

Gibbs采样是MH采样法的一个特例,每次只更新样本的一个维度

针对维度很高的多维向量,同时采样多个维度难度较高,且接受率很小
使用Gibbs采样每次采样一个维度可以解决这个问题

准备

求得已知其他维度下,每一维度的条件概率 $p(x_{i}|x_{1},,,x_{i-1}, x_{i+1},,,x_{d})$

采样过程

随机选择初始状态 $x^{0} = (x_{1}^{0}, x_{2}^{0}, x_{3}^{0},,,, x_{d}^{0})$
for t = 1,2,3,…:
- 基于前一次产生的样本: $x^{t-1} = (x_{1}^{t-1}, x_{2}^{t-1}, x_{3}^{t-1},,,, x_{d}^{t-1})$，依次采样和更新每个维度的值,即依次按照:
  - $x_{1}^{t} \sim p(x_{1}|x_{2}^{t-1},,,x_{d}^{t-1})$
  - $x_{2}^{t} \sim p(x_{2}|x_{1}^{t}, x_{3}^{t-1},,,x_{d}^{t-1})$
  - $x_{i}^{t} \sim p(x_{i}|x_{1}^{t},,,x_{i-1}^{t}, x_{i+1}^{t-1},,,x_{d}^{t-1})$
  - $x_{d}^{t} \sim p(x_{d}|x_{1}^{t}, x_{2}^{t},,,x_{d-1}^{t})$
- 得到新的一个样本: $x^{t} = (x_{1}^{t}, x_{2}^{t}, x_{3}^{t},,,, x_{d}^{t})$
burn-in处理 : 丢弃采样到平稳分布前的样本, 只保留平稳分布后的样本即为服从原始分布 $p(x)$ 的样本
- 假设采样到收敛用了n次采样,那么服从原始分布的k个样本为 $(x^{n+1}, x^{n+2},,,, x^{n+k})$，有时候为了得到近似独立的样本,可以间隔每r次再取出其中一个样本 $(x^{n+r}, x^{n+2r},,,, x^{n+kr})$
- 真正独立同分布的k个样本可用多条k条不同的收敛后的马氏链得到,不同马氏链采样得到的样本是独立同分布的
- 注意: 采样完成部分维度生成的中间样本如 $(x_{1}^{t},,,x_{i-1}^{t}, x_{i}^{t}, x_{i+1}^{t-1},,,x_{d}^{t-1})$ 是不能作为最终样本的,因为他们之间(同一轮次的多个中间样本)相互依赖性太强,不具有独立同分布的(虽然完全采样完成的也不能视为具有独立同分布,但是可近似的认为是独立同分布的)
采样次数一般来说是凭经验选择一个足够大的值,现实是现实可以使用一些参数变化量这类的指标来判断采样是否收敛,参考NLP——LLDA的Gibbs采样实现

ML——参数化模型与非参数化模型

本文介绍非参数化模型（Non-parametric models）和参数化模型（Parametric models）

参数化模型

定义

参数化模型指的是那些依赖于固定数量参数的模型，这些参数可以通过训练数据学习得到。参数化模型的特点是一旦参数确定，模型的复杂度也就固定了

举例

参数化模型的例子包括线性回归、逻辑回归、支持向量机（SVM）和神经网络等

非参数化模型

定义

非参数化模型则不对模型形式做出严格的假设，也不依赖于固定数量的参数。这类模型通常具有更大的灵活性，可以根据数据的复杂性来适应模型的复杂度

举例

非参数化模型的例子包括高斯过程回归、决策树、k-最近邻（k-NN）算法、核方法以及各种基于模型的集成方法如随机森林和提升树（Boosting Trees）等

其他说明

尽管神经网络可以拥有大量的参数，使得它们具有高度的灵活性和强大的表达能力，但这些特点并不使其成为非参数化模型。非参数化模型指的是不对模型形式做出严格假设的模型，其参数的数量和模型的复杂度可以随着数据量的增加而增加。因此，即使神经网络在实际应用中可以非常复杂，它们仍然是基于固定参数数量的参数化模型
神经网络越来越复杂，现在参数量已经非常大，实际上可以看做是非参数模型？

ML——最小二乘与梯度下降

本文持续更新，主要总结各种与最小二乘和梯度下降相关的优化方法

最小二乘与最小均方误差的区别

最小二乘法

二乘也就是平方的意思，故又称最小平方法(英文全称Least Square Method, LSM或者LS)
是一种数学优化技术
通过最小化误差的平方和寻找数据的最佳函数匹配
- 为什么最小化误差平方和可以得到最佳函数匹配呢？
  - 可以证明，只要误差是服从正太分布的，最小化误差平法和就能匹配到最佳函数(这个高斯证明过)
  - 可以证明，误差的确是服从正太分布的，细节可以参考为什么正太分布如此常见
  - 中心极限定理说了，在适当的条件下，大量相互独立随机变量的均值经适当标准化后依分布收敛于正态分布
    - 适当的条件包括三个要素:
      - 独立
      - 随机
      - 相加
    - 误差满足上面三个要素
  - 综上所述，最小二乘法(最小化误差平法和)可以的到最佳函数匹配
最小二乘法通过求导，并令导数为0，直接求得误差平方和(损失函数的一种)取最小值时的参数
公式:
$$\theta^{\star} = \mathop{\arg\min}_\theta L(x) = \sum_i^{m}(y_i-f(x_i;\theta))^2$$

加权最小二乘法

加权最小二乘中每个样本的误差前面会乘上相应的权重,然后再求和
$$\theta^{\star} = \mathop{\arg\min}_\theta L(x) = \sum_i^{m}w_i(y_i-f(x_i;\theta))^2$$

最小化均方误差

最小二乘（Least Square, LS）问题是这样一类优化问题，目标函数是若干项的平方和
LS的一种更复杂也更灵活的变形: 加权最小二乘根据实际问题考虑每个求和项的重要程度，即为每一项加权值w
均方误(Mean Square Error, MSE)是一种加权最小二乘，它的权值是对应项的概率
$$\theta^{\star} = \mathop{\arg\min}_\theta L(x) = \sum_i^{m}\frac{1}{m}(y_i-f(x_i;\theta))^2 = \frac{1}{m}\sum_i^{m}(y_i-f(x_i;\theta))^2$$

周志华的解释

基于均方误差最小化来进行模型求解的方法称为最小二乘法 ——《机器学习》(周志华著)
- 理解：周志华的意思应该是把均方误差与误差平方和视为一个东西，也就是说各项的权重相同，所以感觉这里定义其实是比较模糊的，不用太在意最小二乘法与最小化均方误差法的定义

总结

三者可以理解为相同的表达式,其中
- 最小二乘法(LSM), 权重为1, 每个样本相同
- 最小均方误差(MSE), 权重为 $\frac{1}{m}$，每个样本相同
- 加权最小二乘 ，权重为自定义的值, 每个样本可以不同
最小均方误差(MSE) 是一种 加权最小二乘 ，他的权重为样本的概率, 每个样本出现的概率相等, 就都乘以 $\frac{1}{m}$ 即可

梯度下降与梯度上升

意义

为什么需要梯度下降或者梯度上升,而不是用直接对目标函数求导得到最优解?

几点说明

对于凸函数而言:
- 通过函数(损失函数等)对参数求导,令其导数为0,的确可以解得损失函数的最小(最大)值点对应的参数
对于非凸函数而言:
- 相同的方法可能只能得到极值点,而不是最小(最大)值点
- 但此时梯度下降法也不能找到最优点
无论是梯度下降函数直接推到求解目标函数最优解,我们都需要求目标函数的导数,并且需要确保目标函数可导,不然是不能用这些方法的

几点原因

有时候目标方程(令导数为0后得到的方程)很复杂,求导数为0的参数的解(根)很难
- 包括时间和空间两方面可能面临困难
- 比如大矩阵的乘法,大矩阵的逆等
- 求某一点的梯度一般是比较容易的(只要求出导数后将对应点的数值带入即可)
  - 这里与求导数为0的解难度不一样,在求出函数导数后,求某一点的梯度仅仅需要带入该点的值,而求导数为0的解需要的是很难的解题过程,甚至可能找不到解
有时候目标方程很奇怪,之前我们没见过,需要我们写新的代码教会计算机如何直接求解函数的根
- 直接使用梯度下降的话是计算机可以理解的
- 梯度下降法不用重新写代码来教给计算机

梯度下降

梯度下降是最小化目标函数
- $\theta=\theta-\lambda\frac{\partial L(\theta)}{\partial\theta}$
- $\lambda$ 为步长
- 每轮迭代沿着负梯度方向移动

梯度上升

梯度上升是最大化目标函数
- $\theta=\theta+\lambda\frac{\partial L(\theta)}{\partial\theta}$
- $\lambda$ 为步长
- 每轮迭代验证正梯度方向移动

梯度下降(上升)法与最小二乘法

最小二乘法

最小二乘法是一种通过最小化误差的平方和寻找数据的最佳函数匹配的数学优化技术
与最小二乘法并列的是最小话误差的三次方或者四次方等方法
- 这里的三次方和和四次方和只是为了和二次方和作对比，实践中很少遇到这样的优化技术

梯度下降(上升)法

梯度下降(上升)法的目标是通过迭代(每次朝着最优方向，即梯度下降最快方向前进)不断逼近能使得目标函数最小(最大)时的最优参数值的方法
梯度下降(上升)是一种迭代法，也就是通过更新参数不停的逼近最优点，可以用来解决各种各样的问题(包括最小二乘问题，最小化误差三次方和等)
- 这里最小二乘问题可以理解为用最小二乘法(最小化误差平法和)来寻找最佳函数的问题

总结

最小二乘法与梯度下降(上升)法不在一个维度，不能对比

最小二乘法

目标：找到(或者逼近)最优函数，使得该函数能最拟合已知数据
方法：最小化误差平方和

梯度下降(上升)法

目标：找到(或者逼近)最优参数，使得该参数能最小化(最大化)目标函数
方法：是通过沿梯度方向迭代更新参数

ML——模型的方差与偏差

本文讲解机器学习中模型的方差偏差关系

偏差与方差的定义

方差：模型的预测值之间的离散程度
偏差：模型整体的预测值与真实值的偏离程度

正则化与方差和偏差

参考博客：https://www.cnblogs.com/qkloveslife/p/9885500.html

总结

$\lambda$ 为正则化系数
当 $\lambda$ 很小时，模型处于“高方差”状态，“训练误差”很小，“交叉验证误差”较大
当 $\lambda$ 很大时，模型处于“高偏差”状态，“训练误差”和“交叉验证误差”都很大

集成学习与方差和偏差

参考博客：https://blog.csdn.net/xmu_jupiter/article/details/47314927

总结

集成学习分两类

平均方法：例如随机森林， Bagging methods。在平均方法中，系统分别去建立多个基分类器，分类器之间没有任何联系。然后在分类或者回归阶段，各个分类器根据测试数据给出自己的答案，然后系统根据各个分类器给出的结果去综合出最后的结果，比如可以使投票的形式
提升方法：例如梯度提升决策树GBDT，AdaBoost。在提升方法中，系统模型在训练过程中会先后建立一系列分类器，这些分类器单个可能是弱分类器，但是组合起来就成为一个强分类器
Stacking方法：
- 单层Stacking（普通Stacking）：降低方差，类似于bagging（因为类似于集成了多个模型投票，属于平均方法）
- 多层Stacking：同时降低方差和偏差，每层上有平均方法，多层之间是提升方法
- 方差与偏差、Bagging、Boosting、Stacking【实用机器学习5.1-5.4】

不同类别的偏差与方差

平均方法尝试去降低模型的方差
- 从统计学的视角看，多个样本均值的方差小于单个样本的方差，具体地样本均值的方差= $\sigma_{\text{mean}} = \frac{\sigma^2}{n}$，其中 $n$ 为样本数量
- 所以平均方法通常比其任何一个基分类器效果好
而提升方法尝试去降低模型的偏差

ML——样本不均衡问题处理

参考链接：
- 一文解决样本不均衡（全）

样本不均衡问题描述

问题描述：机器学习中的样本不均衡问题，是指在分类任务中不同类别的训练样例数量存在显著差异的情况
场景：包括金融欺诈检测、医疗诊断、网络入侵检测等领域

样本不均衡的影响

模型偏向性 ：模型倾向于预测label为多数类，因为这样做可以最大化准确率，即使对少数类的预测几乎总是错误的
过拟合风险 ：由于少数类样本数量少，模型容易过拟合这些样本，导致模型在新数据上泛化性差
总结：样本不均衡带来的根本影响是模型会学习到训练集中样本比例的这种先验性信息，以致于实际预测时就会对多数类别有侧重（可能导致多数类精度更好，而少数类比较差）通过解决样本不均衡，可以减少模型学习样本比例的先验信息，以获得能学习到辨别好坏本质特征的模型

哪些情况下需要解决样本不均衡问题

评估指标

不能使用：准确率（Accuracy）
建议使用：F1分数、精确率（Precision）、召回率（Recall）和AUC等

解决样本不均衡的方法

数据层面的方法

过采样（Over-sampling） ：通过增加少数类样本的数量来缓解不均衡问题。常见的方法包括：
- 随机过采样 ：简单地复制少数类样本，容易导致过拟合
- 数据增强（Data Augmentation） ：通过变换现有样本生成新的样本，适用于图像（翻转，拉伸等）、文本等数据类型
- SMOTE（Synthetic Minority Over-sampling Technique） ：通过在少数类样本间插值生成新的合成样本，一定程度上可以避免过拟合，但生成的数据置信度也存在问题
- ADASYN（Adaptive Synthetic Sampling） ：通过生成少数类别样本改善不均衡问题，与传统的过采样技术（如SMOTE）相比，ADASYN更注重类间距离和局部密度，尤其是对于少数类中的困难样本或噪声敏感区域，它可以更加精细地调整采样策略，详情可参考：不平衡学习的自适应合成采样方法ADASYN（Matlab代码实现）
欠采样（Under-sampling） ：通过减少多数类样本的数量来达到平衡。常用的方法有：
- 随机欠采样 ：随机删除多数类样本，但可能丢失重要信息
- Tomek Links ：移除位于类别边界附近的样本对，有助于清理噪声
- ENN（Edited Nearest Neighbors Rule） ：移除与最近邻居类别不同的样本
- NearMiss ：选择与少数类样本最接近的多数类样本
组合采样 ：结合过采样和欠采样的方法

模型层面的方法

成本敏感学习（Cost-sensitive Learning） ：为不同类别的错误分配不同的固定权重，使模型更加关注少数类的预测
集成学习（Ensemble Learning） ：使用集成学习的方法降低过拟合问题（比如多个模型进行投票或加权平均）

损失函数层面

损失函数优化 ：比如使用Focal Loss等

异常检测

异常检测（Anomaly Detection） ：将少数类视为异常点（特别是少数类样本非常稀少的情况），使用异常检测算法进行识别，常见的异常检测算法通常包括统计方法、距离检测（K近邻方法）、聚类方法（K-Means）、分类模型（one-class SVM）、自编码器、孤立森林等
- 其中K近邻方法可以用于回归或者分类场景，还可以直接用于异常检测（距离过大的点认为是异常）
- K-Means方法作异常检测时，原理聚类中心的样本视为异常值
- 自编码器方法：通过训练一个自编码器来重建数据，重建误差大的数据点被视为异常点
- 孤立森林（Isolation Forest）：通过随机挑选特征、随机挑选分割点构建多棵孤立树，在所有孤立树中的平均路径长度的数据点被视为异常点（孤立森林的核心思想是异常点通常更容易被孤立，即在随机分割数据空间时，异常点往往比正常点更快地被单独分隔出来）

实践建议

评估指标的选择 ：在不均衡数据集上，不能使用准确率（Accuracy），建议使用均衡指标（F1-Score，AUC等）
模型选择 ：选择对不均衡数据的适应性较好的模型，如决策树和随机森林等，可以多使用一些简单的模型，再进行Bagging来减少过拟合
具体情况具体分析，很多时候不需要特别的进行处理，另外如果真的进行采样，会导致预估均值有偏差，在CTR等对预估绝对值有要求的场景中，还需要校准

ML——求解无约束最优化问题的优化方法

本文介绍求解无约束最优化问题的优化方法：梯度下降法(Gradient Descent)、牛顿法(Newton’s Method)和拟牛顿法(Quasi-Newton Methods)

共轭梯度法也是一种无约束的参数优化方法，详情见ML——共轭梯度法和最速下降法

无约束参数优化方法概览

目标

$$
\begin{align}
\theta^{\star} = \mathop{\arg\max}_{\theta}L(\theta)
\end{align}
$$

直接法

使用直接法需要满足两个条件

$L(\theta)$ 为关于 $\theta$ 的凸函数
$\nabla L(\theta)=0$ 有解析解(又名闭式解，指的是有限个常见运算的组合给出的形式)

求解

目标函数直接对参数求导后令目标函数导数为0: $$\nabla L(\theta)=0$$

迭代法

包括梯度下降法和牛顿法，牛顿法又可以拓展为拟牛顿法

梯度下降法

更详细的说明参考ML——最小二乘与梯度下降中的介绍

梯度下降法通过每次迭代沿着梯度下降最快的方向(梯度的负方向)前进一个 $\Delta \theta$ 长度
$\Delta \theta$ 为步长 $\alpha$ (参数)乘以梯度的模(变化率)的方法，实现对极大(小)值的一步步逼近

牛顿法

数学中的牛顿法

牛顿法的本质是求函数值 $f(x)$ 为零($f(x)=0$)时参数(自变量 $x$)的值
本质上说，牛顿法是用逼近的方法来解方程的一种方法

算法流程

对于确定的方程 $f(x)=0$，我们的目标是求解自变量 $x$ 的值
1.初始值定义为 $x=x_{0}$
2.牛顿法通过迭代每次从当前点 $(x=x_k,y=f(x_k))$ 沿着斜率 $f’(x) = \frac{\partial f(x)}{\partial x}$ 出发做一条直线，并求出其表达式 $y-f(x_k) = (x-x_k)\cdot f’(x)$
3.求出该直线与x轴的交点 $x_{k+1}=x_{k}-\frac{f(x_{k})}{f’(x_{k})}$
4.设置下一次迭代的点为 $x=x_{k+1}$
5.重复2到4，直到斜率小于某个阈值 $\epsilon$ 时停止迭代
6.迭代停止时 $x=x_{k+1}$ 就是方程的近似解
迭代过程图示化如下：
迭代公式推导
上述迭代流程中迭代公式 $x_{k+1}=x_{k}-\frac{f(x_{k})}{f{}’(x_{k})}$ 的推导如下：

最优化方法中的牛顿法

最优化方法的目标是学习函数 $f(\theta)$ 的极小/大值(若 $f(\theta)$ 是凸函数，则为最小/大值)
可以证明，目标函数(凸函数)取最优点(最大/小值)时，目标函数的导数 $\frac{\partial f(\theta)}{\partial \theta}=0, 其中\theta=\theta^{\star}$
基于这个事实，在知道目标函数的导数 $f{}’(\theta)=\frac{\partial f(\theta)}{\partial \theta}$ 的表达式后，我们可以列出方程 $f{}’(\theta)=0$
- 此时方程的解 $\theta^{\star}$ 就是原始目标函数的最优解
解上述方程 $\frac{\partial f(\theta)}{\partial \theta}=0$ 时我们即可使用数学中的牛顿法

算法流程

具体算法步骤与数学中的算法流程小节一致，不同的地方在于此时迭代公式变为 $\theta_{k+1}=\theta_{k}-\frac{f{}’(\theta_{k})}{f{}’{}’(\theta_{k})}$
在具体的实现中，我们一般会直接推导出每一步的迭代公式，按照公式迭代即可得到最优解

迭代公式推导

根据上述事实，此时我们的目标函数为 $f(\theta)$，目标方程方程为 $f{}’(\theta)=0$
此时迭代公式为$$\theta_{k+1}=\theta_{k}-\frac{f{}’(\theta_{k})}{f{}’{}’(\theta_{k})}$$
当参数数量不止一个时， $\theta$ 表示一个向量，此时迭代公式为$$\theta_{k+1}=\theta_{k}-H_{k}^{-1}\nabla_{\theta}f(\theta_{k})$$
- 其中 $H_{k}^{-1}$ 为海森矩阵 $H_{k}$ 的逆, $H_{k}=H(\theta_{k})$
- $H_{k}^{-1}$ 和 $\frac{1}{f{}’{}’(\theta_{k})}$ 分别是多维和一维参数时目标函数的二阶导
- 海森矩阵是目标函数对参数的二阶导数， $H(\theta)=\left [ \frac{\partial^{2}f}{\partial \theta^{i}\partial \theta^{j}} \right ]_{n\times n}$
推导步骤和上面的数学中的迭代公式推导一致

牛顿法与梯度下降法的一种简单推导方法

用泰勒展开来推导,详情待更新(参考<<百面>>P149)

迭代法的思想

最小化目标函数
$$
\begin{align}
\delta_{t} &= \mathop{\arg\min}_{\delta}L(\theta_{t} + \delta) \\
\theta_{t+1} &= \theta_{t} + \delta_{t} \\
\end{align}
$$
注意,如果这里是max最大化目标函数的话,对应的是梯度上升法,此时后面推导的步骤中加入L2正则项时为了使得 $\left | \delta \right |_{2}^{2}$ 的值最小,正则项的权重应该为负数,这样整体目标函数最大时正则项才能取得最小值,最终推导得到的结果也将变成梯度上升的表达式,($\alpha > 0$ 时对应的参数迭代公式变成加好而不是减号)
但是实际上最大化目标函数可以价格负号转变为最小化目标函数,所以其实掌握最小化目标函数的优化方法即可

一阶法——梯度下降法

对目标函数在 $L(\theta_{t} + \delta)$ 处做一阶泰勒展开
$$
\begin{align}
L(\theta_{t} + \delta) = L(\theta_{t}) + \nabla L(\theta_{t})^{T}\delta \\
\end{align}
$$
由于上式在 $\delta$ 非常小时才成立，所以我们一般加上加入L2正则项（L2正则项可以保证 $\delta$ 的值不会太大),为了保证 $\left | \delta \right |_{2}^{2}$ 的值最小,要求 $\alpha > 0$，才能保证目标函数最小时正则项也对应最小 (梯度上升法中要求 $\alpha < 0$ 或者需要在正则项前面的系数加上负号,才能保证目标函数最大时正则项最小)
$$
\begin{align}
L(\theta_{t} + \delta) = L(\theta_{t}) + \nabla L(\theta_{t})^{T}\delta + \frac{1}{2\alpha}\left | \delta \right |_{2}^{2} \\
\end{align}
$$
直接对上式求导=0得
$$
\begin{align}
\delta_{t} &= \mathop{\arg\min}_{\delta}L(\theta_{t} + \delta) \\
&= \mathop{\arg\min}_{\delta}(L(\theta_{t}) + \nabla L(\theta_{t})^{T}\delta + \frac{1}{2\alpha}\left | \delta \right |_{2}^{2}) \\
&= -\alpha \nabla L(\theta_{t})
\end{align}
$$
于是梯度下降法的更新表达式为
$$
\begin{align}
\theta_{t+1} &= \theta_{t} + \delta_{t} \\
&= \theta_{t} - \alpha \nabla L(\theta_{t})
\end{align}
$$

二阶法——牛顿迭代法

对目标函数在 $L(\theta_{t} + \delta)$ 处做二阶泰勒展开
$$
\begin{align}
L(\theta_{t} + \delta) = L(\theta_{t}) + \nabla L(\theta_{t})^{T}\delta + \frac{1}{2}\delta^{T}\nabla^{2}L(\theta_{t})\delta \\
\end{align}
$$
直接对上式求导=0得
$$
\begin{align}
\delta_{t} &= \mathop{\arg\min}_{\delta}L(\theta_{t} + \delta) \\
&= \mathop{\arg\min}_{\delta}(L(\theta_{t}) + \nabla L(\theta_{t})^{T}\delta + \frac{1}{2}\delta^{T}\nabla^{2}L(\theta_{t})\delta) \\
&= -\nabla^{2} L(\theta_{t})^{-1} \nabla L(\theta_{t}) \\
&= -H(\theta_{t})^{-1}\nabla L(\theta_{t}) \\
\end{align}
$$
于是梯度下降法的更新表达式为
$$
\begin{align}
\theta_{t+1} &= \theta_{t} + \delta_{t} \\
&= \theta_{t} - \nabla^{2} L(\theta_{t})^{-1} \nabla L(\theta_{t})
\end{align}
$$

比较梯度下降法与牛顿法

一般来说，牛顿法收敛速度快
- 一种解释是梯度下降法用一次平面去拟合局部区域牛顿法是用二次曲面去拟合局部区域 ，所以后者能得到更好的拟合效果，迭代的方向也就越精确
- 另一种解释是梯度下降只能看到当前目标函数的下降方向，牛顿法可以看到当前当前目标函数的下降方向，同时还能看到一阶导数的变化趋势，所以拟合更快
梯度下降法中有个超参数 $\alpha$
- 牛顿法中海森矩阵的逆在迭代过程中不断减小，可以起到逐步减小步长的效果(这里的步长与梯度下降中的 $\alpha$ 步长不一样,梯度下降中的 $\alpha$ 是超参数,表示每次向着负梯度移动的长度,而牛顿法中没有超参数)
- 为了防止震荡,这个步长 $\alpha$ 也可以随着迭代次数不断减小
梯度下降法可能造成震荡
- 越接近最优值时，步长 $\alpha$ 应该不断减小，否则会在最优值附近来回震荡
- <<统计学习方法>>第一版附录A中, $\alpha$ 是不断变化的,能保证不会造成震荡
牛顿法在多变量时需要求海森矩阵H的逆,比较复杂,时间和空间上有要求,不如梯度下降法来的容易

拟牛顿法

解决牛顿法求取海森矩阵 $H$ 的逆 $H^{-1}$ 时比较耗时间的难题
用一个近似矩阵 $B$ 代替海森矩阵 $H$ 的逆 $H^{-1}$
不同算法近似矩阵 $B$ 的计算有差异
常见的拟牛顿法：BFGS,L-BFGS和OWL-QN等
- <<统计学习方法>>中讲解了三个拟牛顿算法: DFP,BFGS和Broyden类算法

总结

归纳自<<统计学习方法>>

相同迭代公式

目标函数为 $f(\theta)$，最优化方法的终极目标是求 $f(\theta)$ 的最大值点(或极大值点)
目标函数的一阶导数
- 参数一维时为: $f{}’(\theta)=\frac{\partial f(\theta)}{\partial \theta}$
- 参数多维时为: $\nabla f(\theta)$
目标函数的二阶导数
- 参数一维时为: $f{}’{}’(\theta)$
- 参数多维时为:(海森矩阵) $H(\theta)=\left [ \frac{\partial^{2}f}{\partial \theta^{i}\partial \theta^{j}} \right ]_{n\times n}$
梯度下降法,牛顿法和拟牛顿法的迭代参数均可表示为下面的迭代形式:
$$\theta_{k+1}=\theta_{k}+\lambda_{k}p_{k}$$
均通过一阶导数 $\left | \nabla f(\theta) \right |<\epsilon$ 为收敛判断条件
- 在<<统计学习方法>>中,梯度下降法还可以通过 $\left | \theta_{k+1}-\theta_{k+} \right |<\epsilon$ 或 $\left | f(\theta_{k+1})-f(\theta_{k+}) \right |<\epsilon$ 来判断收敛

梯度下降法

$p_{k}=\nabla f(x)$
$\lambda_{k}$ 是步长,满足
$$f(\theta_{k}+\lambda_{k}p_{k})=\min_{\lambda \geq 0}f(\theta_{k}+\lambda p_{k})$$

牛顿法

$p_{k}=-H_{k}^{-1}\nabla f(\theta)$
$\lambda_{k}=1$ 是固定长度的,详情见数学中的牛顿法的推导,每次迭代到斜率与横轴的交点
$$\lambda_{k}=1$$

拟牛顿法

核心思想是找一个容易计算的近似矩阵(可以迭代计算,而不是每次重新计算逆矩阵的矩阵)替代原始牛顿法中的海森矩阵 $H$ ($B$)或者海森矩阵的逆矩阵 $H^{-1}$ ($G$)

DFP算法

使用 $G_{k}$ 逼近海森矩阵的逆矩阵 $H^{-1}$
$p_{k}=-G_{k}\nabla f(\theta)$
- 关于 $G_{k}$ 的计算:
  - 初始化 $G(0)$ 为正定对称矩阵
  - $G_{k+1}=G_{k}+\frac{\delta_{k}\delta_{k}^{T}}{\delta_{k}^{T}y_{k}}-\frac{G_{k}y_{k}y_{k}^{T}G_{k}}{y_{k}^{T}G_{k}y_{k}}$
    - $\delta_{k}=\theta_{k+1}-\theta_{k}$
    - $y_{k}=\nabla f(\theta_{k+1})-\nabla f(\theta_{k})$
$\lambda_{k}$ 是步长,满足
$$f(\theta_{k}+\lambda_{k}p_{k})=\min_{\lambda \geq 0}f(\theta_{k}+\lambda p_{k})$$

BFGS算法

使用 $B_{k}$ 逼近海森矩阵 $H_{k}$
$p_{k}=-B_{k}^{-1}\nabla f(\theta)$
- 关于 $B_{k}$ 的计算:
  - 初始化 $B(0)$ 为正定对称矩阵
  - $B_{k+1}=B_{k}+\frac{y_{k}y_{k}^{T}}{y_{k}^{T}\delta_{k}}-\frac{B_{k}\delta_{k}\delta_{k}^{T}B_{k}}{\delta_{k}^{T}B_{k}\delta_{k}}$
    - $\delta_{k}=\theta_{k+1}-\theta_{k}$
    - $y_{k}=\nabla f(\theta_{k+1})-\nabla f(\theta_{k})$
$\lambda_{k}$ 是步长,满足
$$f(\theta_{k}+\lambda_{k}p_{k})=\min_{\lambda \geq 0}f(\theta_{k}+\lambda p_{k})$$

Broyden类算法(Broyden’s algorithm)

使用 $G_{k}$ 逼近海森矩阵的逆矩阵 $H^{-1}$
在BFGS中取 $G^{BFGS}=B^{-1}$
利用DFP和BFGS二者的线性组合选择合适的海森矩阵的逆矩阵 $H^{-1}$ 的替代矩阵
$$G_{k+1}=\alpha G^{DFP}+(1-\alpha)G^{BFGS}$$
可以证明 $G$ 此时是正定的
$0\leq \alpha \leq 1$
这样得到的一类拟牛顿法都称为Broyden类算法

Joe Zhou

Stay Hungry. Stay Foolish.

GitHub E-Mail