分类 机器学习 下的文章

首先我们知道KL散度具有不对称性,一般我们称$D_{KL}(p||q) = \mathbb E_{p(x)} \frac {p(x)} {q(x)}$为正向KL散度,$D_{KL}(q||p) = \mathbb E_{q(x)} \frac {q(x)} {p(x)}$为反向KL散度。

关于这两种散度之间的区别,这篇博客讲的很清楚了,包括正向KL散度的zero avoiding和反向KL散度的zero forcing。

那么现在问题在于,为什么现在deep learning RL更喜欢用反向KL散度呢(GRPO)?我个人的理解:正向KL散度zero avoiding会让学习的q分布更趋向于一般化,而反向散度的zero forcing会让q的概率分布在p的那些峰值上。以LLM的next token prediction为例,假设下一个token的prob logits有两个峰值分别是a和b,然后其他token(记为c)的预测概率接近于0。

如果使用正向KL散度优化,即使c的预测概率接近于0,但是由于$p(c) \neq 0$,所以分母$q(c) \neq 0$,当vocab大小非常大时(现在的词表基本都在5w, 15w),a和b能分到的prob也不算高(并且这里没有约束$q(c)$的数值大小,所以$q(c)$完全可以取很大的值从而降低KL散度,这并不是我们想要的),因此模型q在采样时还是容易采样到那些c token。

如果使用反向KL散度进行优化,$p(c) \rightarrow 0$,那么$q(c) \rightarrow 0$,约束了$q(c)$的数值大小,所以优化得到的分布会给a,b更大的prob,从而在q采样时更容易取到p分布对应的那些高概率token。

回到RL的目的,应用KL散度是为了约束策略更新后的模型与原始模型的距离,即两个模型的行为尽可能保持一致,而行为取决于logits和采样方法,采样方法一致的情况下,自然是希望logits尽可能相同,那么反向KL散度相对来说就更合适一点(因为它倾向于模仿p分布里的那些高概率的token,而高概率的token也是更容易被采样的)

以上是一个偏直觉的理解~

摘要

SVM是神经网络兴起之前最常用的机器学习分类器,本篇主要介绍SVM的具体实现,包括硬间隔/软间隔、合页损失函数。PPT参考https://www.bilibili.com/video/BV1zq4y1g74J/?spm_id_from=333.788&vd_source=6e11e901eb83e70a9bb55225ac28b9d9

SVM推导

SVM一般用于解决数据的二分类问题,对于高维数据,就是找到一个超平面将两类数据分开。以二维平面为例,就是找到一条直线作为分割线。

当然有时候我们无法找到理想直线将两类数据分离,这个时候就需要用到非线性SVM,通过核函数将数据点映射到高维空间,以期望在高维空间找到一个超平面分离数据。

image-20230709104533915

SVM的思想不仅是找到一个分割直线,它还希望这条直线离两类数据都尽可能远,也就是最大小下图中的$margin$。

image-20230709104825169

$margin(W,b)$与直线参数$W,b$有关,形式化表示可以写成:

$$ max \space margin(W,b)=max\mathop{min}\limits_{i=1,2,...N} \frac{1}{||W||_2}|W^TX^{(i)}+b| $$

$margin$的表达式为什么是直接将数据点$X^{(i)}$带入直线(高维数据时其实是超平面,但是为了描述方便之后都用直线方程替代)方程然后除以W的L2范数?推导如下,首先写出某个数据点到直线的距离方程,距离可以表达成W和数据点向量之间的点积除以W的模。假设$x^{(0)}$是平面上的一点(所以$W^TX^{(0)}+b=0$),那么距离H就可以表示为:

$$ \begin{aligned} H &= |\frac{W}{||W||_2}(X^{(i)}-X^{(0)})|\\ &= |\frac{1}{||W||_2}(W^TX^{(i)}-W^TX^{(0)})|\\ &= |\frac{1}{||W||_2}(W^TX^{(i)}+b)| \end{aligned} $$

image-20230709105549162

除了满足最大$margin$外,我们还希望这个超平面可以正确分割数据点,我们将数据点的标签标为1或-1,那么如果直线可以正确分类,那么满足以下两个条件:

image-20230709110437048

进一步将优化问题转变成以下条件:

image-20230709110531551

为了简化问题,我们将离直线最近的数据点$X^{(i)}$离直线的距离$|(W^TX^{(i)}+b)|$约束到1,那么优化问题就变成了下图,并且添加了一个约束条件。之所以可以这么优化,是因为对于原来的$margin$,$W,b$同时扩大N倍,都不会影响margin的结果,所以这里可以扩大(缩小)两者的值,使$|(W^TX^{(i)}+b)|$约束到1,从而简化问题

注意,这里的$X^{(i)}$是离直线最近的那个数据点,所以可以把$margin$的min脱掉

image-20230709110840827

合并约束条件得到以下优化条件:

image-20230709111411569

将max转换成min,得到:

image-20230709111525424

进一步写成矩阵相乘的形式,并通过拉格朗日乘子法优化,这里约束条件是不等式,满足KKT条件。数据点在边界上时$\lambda$不等于0,存在约束;如果不在边界上则不存在约束。具体可查阅KKT条件相关知识。

这里引入1/2不会影响结果,但是可以方便之后的求导运算

image-20230709111644213

对上图中的L求导,得到最优解。此时W可以表示为边界上各个数据点的线性组合,这些数据点$X^{(j)}$就被称为支持向量

image-20230709111852303

SVM的损失函数

我们回过头看SVM需要优化的那个拉格朗日函数,其实它和神经网络中的损失函数很像,第一项相当于W的L2正则化项,第二项则是”损失函数“。

image-20230709112110624

上述的SVM是硬间隔SVM,因为它的损失函数要求SVM直线对于每个数据点都分类正确,然而实际上会出现不可分的情况。那么这个时候就需要对优化函数进行修正,从而得到软间隔SVM。

image-20230709112358327

通过添加$\xi$,使约束条件放开。同时也将$\xi$的常数倍加入损失函数优化,从而尽可能找到一个小的间隔$\xi$。

image-20230709112419232

合并约束条件,我们可以得到以下结果。这个时候我们已经可以看到Hinge loss的身影了。

image-20230709113135754

把约束项合并到损失函数中,就可以得到软间隔SVM最终的损失函数形态。第一项是损失函数,第二项是W的正则化项。

image-20230709114151469

而第一项就是我们熟知的Hinge Loss,合页损失函数。

image-20230709114258657

背景

一般来说在训练时会将数据分为两部分,一部分用于训练,另一部分用于验证。这会引起以下几点问题:

  • 首先数据的切割是人为/随机的,不同切割可能会导致模型的不同精度。或者说人为切割的验证集有可能偏离了真实分布
  • 其次训练数据被分为两部分,验证集不参与训练,网络的数据来源缩水了,影响训练效果。虽然最后会将所有训练数据都丢入模型中来评估测试集,但是在这之前评估模型或者说模型调参还是只能使用一部分的训练数据

基本概念

K是一个指定的数字。执行K折交叉验证时,首先会将数据划分成(大致)相等的K个部分,每部分叫做一个。每次选取其中一个折作为验证集,由其他K-1个折作为训练集训练模型,训练好的模型用验证集评估正确性。

换句话说,K折交叉验证将会产生K个模型,最后得到的精度将是这K个模型精度的均值

交叉验证一般用于评估模型的泛化性能,也可以使用带交叉验证的网格搜索确定超参数

image-20230328104210900

优缺点

  • K折交叉验证的精度结果反映了模型对数据集中的所有样本都有较好的泛化性
  • 通过对数据的多次划分,提供了模型对于训练集选择的敏感性信息。即反映了数据在最好/最坏情况下模型的表现情况。
  • 交叉验证使数据使用更高效,K越大时,训练集的占比可以更大。更多的数据自然可以得到更精确的模型。

sklearn

from sklearn.model_selection import cross_val_score
from sklearn.datasets import load_iris
from sklearn.linear_model import LogisticRegression

iris = load_iris()
logreg = LogisticRegression(max_iter=1000)

scores = cross_val_score(logreg, iris.data, iris.target)
print("Cross-validation scores: {}".format(scores))

分层K折交叉验证 .etc

分层K折交叉验证

分层K折交叉验证保证了每个折中类别的比例和整个数据集中的相同。比如该数据集中90%的样本是A类,10%的样本是B类。那么K折中的每一折都是符合A占90%,B占10%。

分层K折避免这种情况发生:某一折里只包含A类的样本,导致验证精度很差,无法给出分类器的整体性能

随机K折交叉验证

为了避免标准K折交叉验证中折内类别比例异常的情况,还可以使用随机K折交叉验证。

kfold = KFold(n_splits=3, shuffle=True, random_state=0)
print("Cross-validation scores:\n{}".format(
    cross_val_score(logreg, iris.data, iris.target, cv=kfold))

留一法交叉验证

留一法可以看作是每折只有单个样本的K折交叉验证.

from sklearn.model_selection import LeaveOneOut
loo = LeaveOneOut()
scores = cross_val_score(logreg, iris.data, iris.target, cv=loo)
print("Number of cv iterations: ", len(scores))
print("Mean accuracy: {:.2f}".format(scores.mean()))

打乱划分交叉验证

每次划分为训练集采样train_size个点,为测试集(或者说验证集)采样test_size个点.将这种方法重复n_iter次.

image-20230328110830120

from sklearn.model_selection import ShuffleSplit
shuffle_split = ShuffleSplit(test_size=.5, train_size=.5, n_splits=10)
scores = cross_val_score(logreg, iris.data, iris.target, cv=shuffle_split)
print("Cross-validation scores:\n{}".format(scores))

打乱划分交叉验证允许在训练集和测试集大小之外指定迭代次数.也可以允许每次迭代仅使用部分数据.对于二次采样大型数据的试验比较有效.

分组交叉验证

有时候数据是分组的,比如每个人有多个数据.那么测试集中的数据最好是整组出现的,不应该出现测试集中某个人的数据出现在训练集中,这会影响对模型的泛化能力的评估.

image-20230328111504785

from sklearn.model_selection import GroupKFold
# create synthetic dataset
X, y = make_blobs(n_samples=12, random_state=0)
# assume the first three samples belong to the same group,
# then the next four, etc.
groups = [0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 3]
scores = cross_val_score(logreg, X, y, groups=groups, cv=GroupKFold(n_splits=3))
print("Cross-validation scores:\n{}".format(scores))

基本概念

K折交叉验证用于评估一个模型的泛化性能,那么网格搜索通过调参来提高模型的泛化性能.

简单的网格搜索实现

提前划分好训练集和测试集,简单通过两个for循环寻找最佳参数,评估效果直接使用模型自带的score.

# naive grid search implementation
from sklearn.svm import SVC
X_train, X_test, y_train, y_test = train_test_split(
    iris.data, iris.target, random_state=0)
print("Size of training set: {}   size of test set: {}".format(
      X_train.shape[0], X_test.shape[0]))

best_score = 0

for gamma in [0.001, 0.01, 0.1, 1, 10, 100]:
    for C in [0.001, 0.01, 0.1, 1, 10, 100]:
        # for each combination of parameters, train an SVC
        svm = SVC(gamma=gamma, C=C)
        svm.fit(X_train, y_train)
        # evaluate the SVC on the test set
        score = svm.score(X_test, y_test)
        # if we got a better score, store the score and parameters
        if score > best_score:
            best_score = score
            best_parameters = {'C': C, 'gamma': gamma}

print("Best score: {:.2f}".format(best_score))
print("Best parameters: {}".format(best_parameters))

验证集的引进

上节实现的简单网格搜索存在一个致命问题:将用来调整参数的测试集用于评估模型的好坏!

换句话说,我们是在测试集上选择出来的最佳参数,整个参数不能保证对于新数据也work well.所以需要引入一组新数据.那么数据总共就被分为三份:

  • 用于训练模型的训练集
  • 用于调整超参数的验证集
  • 用于评估模型的测试集

测试集模型训练阶段从未见过,只在评估时使用.

验证集用来衡量训练集训练出来的模型好坏

最后评估时,模型会选择表现最好的超参,用训练集+验证集重新训练,再用测试集进行评估.这一步主要是充分利用验证集数据.

from sklearn.svm import SVC
# split data into train+validation set and test set
X_trainval, X_test, y_trainval, y_test = train_test_split(
    iris.data, iris.target, random_state=0)
# split train+validation set into training and validation sets
X_train, X_valid, y_train, y_valid = train_test_split(
    X_trainval, y_trainval, random_state=1)
print("Size of training set: {}   size of validation set: {}   size of test set:"
      " {}\n".format(X_train.shape[0], X_valid.shape[0], X_test.shape[0]))

best_score = 0

for gamma in [0.001, 0.01, 0.1, 1, 10, 100]:
    for C in [0.001, 0.01, 0.1, 1, 10, 100]:
        # for each combination of parameters, train an SVC
        svm = SVC(gamma=gamma, C=C)
        svm.fit(X_train, y_train)
        # evaluate the SVC on the validation set
        score = svm.score(X_valid, y_valid)
        # if we got a better score, store the score and parameters
        if score > best_score:
            best_score = score
            best_parameters = {'C': C, 'gamma': gamma}

# rebuild a model on the combined training and validation set,
# and evaluate it on the test set
svm = SVC(**best_parameters)
svm.fit(X_trainval, y_trainval)
test_score = svm.score(X_test, y_test)
print("Best score on validation set: {:.2f}".format(best_score))
print("Best parameters: ", best_parameters)
print("Test set score with best parameters: {:.2f}".format(test_score))

带交叉验证的网格搜索

上一节中人为分出了测试集\训练集\验证集,这钟方法对于数据的划分也比较敏感.因此可以在划分训练集/验证集时使用交叉验证,更好的评估模型的泛化能力.

for gamma in [0.001, 0.01, 0.1, 1, 10, 100]:
    for C in [0.001, 0.01, 0.1, 1, 10, 100]:
        # for each combination of parameters,
        # train an SVC
        svm = SVC(gamma=gamma, C=C)
        # perform cross-validation
        scores = cross_val_score(svm, X_trainval, y_trainval, cv=5)
        # compute mean cross-validation accuracy
        score = np.mean(scores)
        # if we got a better score, store the score and parameters
        if score > best_score:
            best_score = score
            best_parameters = {'C': C, 'gamma': gamma}
# rebuild a model on the combined training and validation set
svm = SVC(**best_parameters)
svm.fit(X_trainval, y_trainval)

image-20230328113803191

GridSearchCV 热图可视化

from sklearn.model_selection import GridSearchCV
from sklearn.svm import SVC
param_grid = {'C': [0.001, 0.01, 0.1, 1, 10, 100],
              'gamma': [0.001, 0.01, 0.1, 1, 10, 100]}
grid_search = GridSearchCV(SVC(), param_grid, cv=5,
                          return_train_score=True)
                          
X_train, X_test, y_train, y_test = train_test_split(
    iris.data, iris.target, random_state=0)
grid_search.fit(X_train, y_train)

scores = np.array(results.mean_test_score).reshape(6, 6)

# plot the mean cross-validation scores
mglearn.tools.heatmap(scores, xlabel='gamma', xticklabels=param_grid['gamma'],
                      ylabel='C', yticklabels=param_grid['C'], cmap="viridis")

image-20230328114043350

不同的交叉验证策略

嵌套交叉验证

在交叉验证的网格搜索中,我们使用交叉验证来完成训练集/验证集的划分,测试集的划分我们还是手动的.嵌套交叉验证让我们测试集的划分也使用交叉验证.这会使结果更合理,当然需要训练模型的个数也upup~(比如36个模型超参数组合,嵌套交叉验证都是5折,那就需要训练900个模型)

param_grid = {'C': [0.001, 0.01, 0.1, 1, 10, 100],
              'gamma': [0.001, 0.01, 0.1, 1, 10, 100]}
scores = cross_val_score(GridSearchCV(SVC(), param_grid, cv=5),
                         iris.data, iris.target, cv=5)
print("Cross-validation scores: ", scores)
print("Mean cross-validation score: ", scores.mean())

基本概念

t-SNE(t-distributed stochastic neighbor embedding)是用于降维的一种机器学习算法,由 Laurens van der Maaten 等在08年提出。

t-SNE 是一种非线性降维算法,非常适用于高维数据降维到2维或者3维,进行可视化。该算法可以将对于较大相似度的点,t分布在低维空间中的距离需要稍小一点;而对于低相似度的点,t分布在低维空间中的距离需要更远。

tips1:TSNE将数据点之间的相似性转换为联合概率,并试图最小化低维嵌入和高维数据的联合概率之间的Kullback-Leibler差异。t-SNE的成本函数不是凸的,即使用不同的初始化,我们可以获得不同的结果。

tips2:如果特征数量非常多,强烈建议使用另一种降维方法(例如,对于密集数据使用PCA或对于稀疏数据使用TruncatedSVD)将尺寸数量减少到合理的数量(例如50个)。这将抑制一些噪声并加快样本之间成对距离的计算。

tips3:sklearn TSNE 源码

tips4:t-SNE 原理及Python实例 - 知乎 (zhihu.com)

优缺点

优点:

  • 对于不相似的点,用一个较小的距离产生较大的梯度来排斥区分。
  • 这种排斥不会无限大(梯度中分母),避免不相似的点距离太远。

缺点:

  • 主要用于可视化,很难用于其他目的。比如测试集合降维,因为他没有显式的预估部分,不能在测试集合直接降维;比如降维到10维,因为t分布偏重长尾,1个自由度的t分布很难保存好局部特征,可能需要设置成更高的自由度。
  • t-SNE倾向于保存局部特征,对于本征维数(intrinsic dimensionality)本身就很高的数据集,是不可能完整的映射到2-3维的空间(映射存在信息损失)
  • t-SNE没有唯一最优解,且没有预估部分。如果想要做预估,可以考虑降维之后,再构建一个回归方程之类的模型去做。但是要注意,t-sne中距离本身是没有意义,都是概率分布问题
  • 训练太慢。有很多基于树的算法在t-sne上做一些改进

算法流程

  • 首先在高维空间,将样本之间的距离转换成概率分布.

$$ P_{j|i}=\frac {exp(-||x_i-x_j||^2/2\sigma^2)}{\sum_{k \neq i} exp(-||x_i-x_k||^2/2\sigma^2)} $$

  • 在低维空间寻找类似的概率分布,并使用KL散度衡量高维空间/低维空间两概率分布的相似度.

image-20230327172920621

  • 使用梯度下降最小化所有数据点上的KL散度总和

    $$ C = \sum_i KL(P_i||Q_i)=\sum_i \sum_j p_{j|i} \log {\frac {p_{j|i}}{q_{j|i}} } $$

  • 对 C 求偏导数(每个样本)获得每次更新的方向

sklearn

  • n_components : tsne最终降维的维度
  • init : 初始化方法,可以使用pca or random
from sklearn.manifold import TSNE
tsne=TSNE(n_components=1,init='pca', random_state=501)
down_X = tsne.fit_transform(X) # train and get embadding