机器学习基础

决策树

• 决策树的构造准则
• 信息增益
  • 数据集D中，K个类别的熵 \(H(D)\)
  • 某个特征对于数据集D的条件熵\(H(D|A)\)​​,取出所有包含特征A的样本子集\(D_i\)​​，然后计算样本子集中的第k类样本\(D_{ik}\)​​的条件熵
  • 信息增益\(g(D,A) = H(D)-H(D|A)\)​
  • 信息增益：当前样本集合的熵与包含某个特征A的样本集合的上熵的差值
• 信息增益率
  • \(g_R(D,A) = g(D,A)/H_A(D)\)​​​
  • \(g(D,A)\)表示数据集D中特征A的信息增益
  • \(H_A(D)\)​​表示数据集D中A的信息熵
• 基尼指数
  • 表示数据纯度

GBDT

• 采用决策树作为弱分类器的梯度提升算法，通常是CART
• 分类树，每个节点设定一个分类结果
• 回归树，每个节点的结果，可以表示为当前节点所有数据的平均
• \(Loss=f(x)+|w|\)
• 损失函数包含两项，第一项为了降低偏差，第二项通过正则化的手段，降低模型的复杂度，控制方差
• GBDT中会给每个样本赋值
• N个函数拟合一批数据，每个函数拟合的是上一批数据的残差：\(y-f(x)\)​ ，这个残差也可以表示为负梯度
• 每个函数是怎么拟合的？
• 假设拟合每个函数使用的是，决策树，那么如何构建决策树呢？
  • 给定一批数据\((x_1,y_1),(x_2,y_2),(x_3,y_3),..,(x_n,y_n)\)​ ，需要通过信息增益，信息增益比，或基尼系数等指标选定一个特征，用于构建子树，随后，当前这批数据会被分割成若若干份，随后使用相同的办法，对继续构建树

XGBoost

• xgboost是gbdt的一种工程实现，建模时，考虑了正则项（叶子节点的个数，以及叶子节点的预测值
• 可以支持多种类型的分类器

HMM

• 是对含有隐状态（BIEOS）的马尔科夫链建模的生成模型

• 观测序列中各个状态仅仅取决于它对于的隐状态

• 当前转态仅与前一个状态有关
• 考虑了隐状态之间的转移以及以及隐状态到观测转态的输出概率
• 是一种对隐状态和观测状态序列的联合概率分布建模的生成式模型
• 状态转移矩阵，\(N*N\)的矩阵
• 观测概率矩阵，\(N*M\)​​的矩阵
• 训练过程
• 有隐状态的，使用极大似然估计，计算参数
  • 状态转移矩阵
  • \(a_{ij}=P(i_{t+1}|i_t)\)​
  • \(b_{ij} = P(o_t|i_t)\)​
• 序列标注过程（解码过程）
• 在给定观测序列，找出一条隐状态序列，给定一个句子，预测出每个词的词性
  • 维特比解码
  • 状态转移方程：当前时刻的转态=前一时刻的转态 x 转移概率 x 发射概率
    • 定义当前状态 为前t个时刻的观测序列并且状态为q_i
• 缺陷
• 某个观测结果只受当前状态影响，而CRF可以让某个观测结果受到多个隐状态的影响

CRF

• 建立条件随机场

• 定义一个特征函数集合，每个特征函数都是以句子s，位置i，位置i的标签，位置i-1的标签作为输入

• 为每个特征函数赋予一个权重，针对每一个标注序列，对所有特征函数加权求和

一些其他性质

• 可以用当前时刻的标签和前一时刻的标签构成特征函数，加上对应的权重来表征HMM中的转移概率
  • 当然可以建立多的关联
• 可以用当前时刻的标签与当前时刻标签所对应的特征构建特征函数，加上权重来表示HMM中的发射概率
• HMM 只能使用局部特征，转移概率只依赖前一时刻和当前时刻，发射概率只依赖当前时刻，CRF 能使用更加全局的特征，例如词性标注问题中，如果句子末尾出现问号“？”，则句首第一个词是动词的概率更高。
  • 序列标注（词性标注）任务中，隐状态就是BIESO，而每一个字符就是观测结果
• HMM 中的概率具有一定的限制条件，如0到1之间、概率和为1等，而 CRF 中特征函数对应的权重大小没有限制，可以为任意值
• CRF是判别模型，HMM是生成模型，计算方式不同
  • 生成模型
  • \(P(X,Y)=P(X|Y)*P(Y)\)​
  • $ P(Y|X)=P(X,Y)|P(X)$​​
    • \(P(X)\)​​应该是观测概率，即字符串概率
    • \(P(X,Y)\)​​是联合概率，即字符串与标注结果的概率
  • 判别模型
  • 直接对\(P(Y|X)\)​​建模
• LSTM+CRF中
  • 观测序列与隐状态之间所构建的发射概率表现为lstm对输入序列编码的过程
  • 隐状态之间的转移概率表现为\(N*N\)​的转移概率矩阵的学习过程。
  • 标签个数为N，长度为T的序列可能有\(N^T\)种路径的可能
  • 最终的损失函数由两部分组成，发射概率与转移概率,本质还是计算路径概率，通过动态规划算法降低复杂度，并用最大似然估计优化

PCA

• 最大方差理论

• 找到数据中的主要成分，并用这些主要成分表征原始数据，实现降维的目的

  • 投影后的方差越大，保留的数据信息就越多
  • 投影后的方差就是协方差的矩阵的特征值

• 最小平方差

KNN

• kd树
• 选择某一个维度，按照这个维度数值的大小进行排序根据排序的结果确定中位数，按照中位数将他们划分为左右两个部分，然后选择下一个维度，按照相同的方法进行区间划分
• kd树搜索
• 给定一个目标节点，判断该目标节点在kd树中叶子节点的位置，并计算目标节点与该叶子节点的距离作为最近的距离，一次回溯到父节点，并判断父节点是否需要更新最近距离，并判断另外一个子节点是否在最近的范围内，如果是，则更新，否则继续向上回溯。

开放性问题

• 如何刷单？
• 谷歌“风控”