算法笔记

ChuanXin · 发表于 2022-2-15 22:00

树模型：

ID3通过对分裂特征计算信息增益来选择分裂节点，有个很大的弊端就是：唯一值多的特征更容易成为分裂节点，比较极端情况，唯一标志分类label的特征，数据通过这个特征算出来的信息增益很大，而这种分裂是没意义的，也就是过拟合，没有泛化能力。
C4.5通过对分裂特征计算信息增益率来选择分裂节点，信息增益除以分裂信息熵。
xgboost，boosting方法，回归树的目标函数是MSE，分类树一般也是交叉熵，通过拟合前面树的残差去构造新树，在选择分裂节点和分裂规则时候，遍历每个特征，在遍历每个特征值去分裂，计算出分裂增益损失，使我们的目标函数最小。贪心算法能达到全局最优解，近似算法，是对特征值取分位数，以分位点作为划分点，去算增益损失。
- XGBoost论文阅读 - 知乎 (zhihu.com)
lightGBM，在xgb基础上做了性能优化。
- 深入理解LightGBM - 知乎 (zhihu.com)
- 主要是在筛选特征和划分规则时候，用得直方图算法，对一个连续特征先进行离散化，也即是比较细得分桶，这样再来算分裂增益，有多少个桶就只算多少次，不用在遍历每个值去计算了，类似xgb里面得近似算法。
- 在存储时候也只需要存储离散化后得8位整形值，而xgb既需要用32位得浮点数存特征值，还需要用32位得浮点数去存索引，相比之下，lightGBM大大减小了存储量。
- 单边梯度采样，目的是为减小数据量，且不影响精度，具体做法是，对要分裂得特征值按绝对值排序，然后选值较大得topN个数据，其它得数据随机选少量，但是在这少量得数据乘以一个常数，这样模型会更关注这部分数据，这样来减小原数据分布得改变带来得差异。
- 类别特征做了特殊处理，不在用one-hot编码，而是处理成连续值，先计算每个分类得label得均值，再排序，然后算每个值得分裂增益。容易过拟合，所以也做了一些正则化和约束。
- 特征捆绑
  - 主要是降维，使特征更加稠密
  - 选择哪些特征捆绑：特征越互斥（特征不同时为非0值），越能捆绑在一起，具体是构造一个加权无向图，跟特征互斥程度、互斥相关的特征数有关，构造完后去遍历每个特征，分配特征包，使总体互斥程度最大。
  - 捆绑方法：主要是能解决原始特征能够分离出来，因为直方图算法，可以使不同特征值分配到不同桶中，这就提供了一种思路是，给特征增加偏置，比如特征a是（0，10），b（0，10），b增加偏置10，b为（10，20），就能跟a分到不同的桶中去了。

双塔DSSM

优点：
- 速度快：能从大规模候选集中找到满足条件得子集
- 准确性：毕竟是有监督，精度不会差
缺点：
- 精度有损：user侧特征和item侧特征信息分离，只在最后做内积得时候才交互，可能原本强相关得交互特征，经过多层非线性网络，已经变得识别度很低了，最后才交互，可能就走样了，表达不出来交互信息了
优化：
- 增加SENet：给特征embedding动态加权，通过小权重抑制噪音或者无效低频特征，通过大权重增大重要特征影响得目的。所以在特征传到最后做内积的时候，因为前面已经过滤了噪音或无效特征，相当于增强了重要特征的交互。

AUC和GAUC

AUC：
- 计算：一种是ROC曲线与x、y轴围成的面积，直观的意义就是正样本预测值大于负样本预测值的概率，所以计算公式是，正样本有M个，负样本有N个，在所有正样本和负样本对比的排列组合中，一共有M*N，而正样本预测的概率值大于负样本预测的概率值的情况共有Q种情况，所有AUC = Q / M*N
- 意义：衡量整体排序的精确度，这个精度各个不同用户的结果会互相干扰
GAUC：
- 计算：每个用户的auc，然后加权平均，权重一般设为用户的点击次数
- 意义：更细粒度的精度，更关注一个用户对不同item的排序能力。

L1和L2

抽象出得问题：正则化项小于某个值得条件下，原目标函数最小。
L1为什么比L2更容易产生稀疏解：从图像来说，L1正则化项是一个菱形，L2正则化项是圆，目标函数更容易跟L1正则化项交点在坐标轴上。从导数得角度看，只要满足，L1正则化项得系数大于原目标函数在0处得导数得绝对值，在0处就可能是最优解。

W & D
优点：wide侧的记忆能力，deep侧的泛化能力
实施细节：wide的记忆能力在于，跟目标比较直接的强相关的特征，这部分特征可以放在wide侧；值比较少的离散特征也可以放在wide侧，因为这部分离散特征信息比较集中；而在deep侧，特征会全部丢进去，离散特征embedding化，保证特征不要太稀疏。

为什么深度学习对稀疏特征不友好？
特征太稀疏，每个样本训练只有极少数的参数能够更新，导致收敛很慢；
对于值特别多的离散特征，one-hot后维度太大，导致整个模型的参数规模巨大，对算力开销太大；
所以通过embedding化使稀疏特征跟上层网络隔离。

样本优化trick
依据样本的label（正、负样本），依据样本的来源（真实样本、人工样本），依据样本的优化方式（样本增强、样本采样）
负样本：

引入随机未展现得负样本，在全局样本里选取，消除bias（user-->data-->model-->user）
正样本某些特征用默认值替换后，变成负样本，增强模型对这部分特征得关注
可以将用户点击得样本，前面得样本当作负样本，比如点击了样本a，往前再拿两个浏览的样本当作负样本
对负样本降采样，核心思想是对热门物品进行采样，但又需要控制一个比例，避免过度打压，

f是展现频率，a是给定的频率阈值。

排序分数比较高的负样本进行过滤，对都是正样本或者都是负样本的用户进行过滤

正样本：

可以对打分比较低的正样本进行过滤
对流量质量进行分层，选取优质流量的正样本作为正样本

DCN算法

结构：交叉网络+深度网络
主要优势：交叉网络使得特征能够进行高阶交叉，不同于深度得高维非线性交叉，拟合能力更强
交叉网络计算（核心点）

DCN-M
在DCN基础上，改善了交叉网络，参数矩阵化，增强拟合能力。

阿里巴巴DIN
1、attention 机制，主要针对id类特征（用户行为序列）
2、对每一个id进行分配权重，这个权重也是一个网络生成得，输入分两部分，一部分是用户历史行为序列得embedding和物品得embedding，另一部分是二者得外积的向量，然后通过激活函数输出一个权重值
3、激活函数的优化

最后祝大家新年快乐，财源广进，节节高升~

		自动登录	找回密码
密码			立即注册

算法笔记

本帖子中包含更多资源