面试 学习

• 深度学习
  • 1. 过拟合
  • 2. 常见模型
  • 3. 调参技巧
  • 4. RNN
  • 5. CNN
• 机器学习
  • 优化方法
  • 线性模型
  • 决策树
  • SVM
  • 贝叶斯
  • 集成
  • 聚类
  • 降维与度量学习
  • 半监督
  • 概率图
• 机器学习数据

深度学习

1. 过拟合

1. 正则化（模型复杂度，结构化风险、方差），降维
2. 早停
3. data augmentation
4. dropout
5. Batch normalization权重伸缩不变性（$\frac{\partial Norm(\lambda Wx)}{\partial x} = \frac{\partial Norm(Wx)}{\partial x}$，$\frac{\partial Norm(\lambda Wx)}{\partial \lambda W} = \frac{1}{\lambda}\cdot \frac{\partial Norm(Wx)}{\partial W}$）（先归一化，后“恢复”。原因是归一化后函数值位于sigmoid中间，没法提供非线性功能，因此需要“恢复”）
6. 具体的：决策树剪枝、松弛变量。。。

2. 常见模型

1. Lenet
2. alexnet(relu,dropout)
3. VGG($3\times 3$,deep)
4. googlenet
   • average-pooling,多个loss-梯度消失，叠加结构
   • BN，$3\times 3$代替$5\times 5$
   • $3\times 1$，$1\times 3$代替$3\times 3$，减少通道
   • inception+res
5. DenceNet
   • 多个block相连，每个block内部卷积层两两相连
   • 重用了特征，channel相应的减少（=12），减少了参数
   • 减缓梯度消失
6. ResNet
   • v1:conv->BN->ReLU
   • v2:BN->ReLU->conv（保持恒等映射，先归一化，得到结果直接相加）
   • ResNeXt:横向拓展，64channel -> 4channel*32
   • WRN：增加block的channel，减少block个数
7. GAN
   • 判别器最优时，loss函数转换为$P_r$、$P_g$的JS散度，梯度为0。（$P_r$与$P_g$的支撑集是高维空间的低维流形时，重叠部分测度为0的概率为1）
8. MobileNet
   • 原始卷积：$H\cdot W\cdot M \to H\cdot W\cdot N$，卷积核$k\cdot k\cdot M\cdot N$，计算量$k\cdot k\cdot M\cdot N\cdot H\cdot W$
   • depthwise：$H\cdot W\cdot M \to H\cdot W\cdot M$，卷积核$k\cdot k\cdot 1\cdot 1$，计算量$k\cdot k\cdot M\cdot H\cdot W$
   • pointwise：$H\cdot W\cdot M \to H\cdot W\cdot N$，卷积核$1\cdot 1\cdot M\cdot N$，计算量$M\cdot N\cdot H\cdot W$

3. 调参技巧

1. 数据 aug, 样本比例
2. 初始化, xaiver
3. batchsize, iter
4. 预训练, clip, lr(sgd, momentun, adam)
5. dropout, bn, weight_decay
6. 画图, tr/te曲线

4. RNN

5. CNN

• CNN发展趋势：
  • 传统问题新发展：物体检测、视频检测、RGBD检测、instance segmentation（RoiAlign，双线性插值，浮点数，每格子取四点）；
  • 数据标注：1、GAN：图像，机器翻译（生成翻译句子，判别人翻译还是机器翻译）；2、对偶学习（强化学习的一种，MSRA利用部分标注数据和大量未标注数据训练）：中文到英文翻译，英文到中文，判断两句中文相似程度，得到反馈，不需要英文标注。关键点在于两个模型闭环，互相提供反馈。
  • 模型压缩：量化（0-255表示32bit浮点数），二进制神经网络。
  • 数据+知识：AAAI2017利用物理知识判断轨迹。

机器学习

优化方法

• 梯度下降：一阶，局部最优，终点时慢，之字形
• 牛顿：$x=x_k-g_kH_k^{-1}$二阶，速度快，复杂度高（海森矩阵求逆），没有步长不保证稳定下降（非二次型函数）
• 阻尼牛顿：$x=min(x_k-\lambda_kg_kH_k^{-1})$，迭代时进行一维搜索
• 拟牛顿：构造正定对称矩阵近似海森矩阵的逆（割线方程，DFP，L-BFGS（$D_k$占内存，用向量替换进行近似计算））
• 坐标下降：简单（没有梯度）
• 拉格朗日：带约束的最优化
• 共轭梯度点击：根据公式$x_{i+1}=x_i+\lambda_i d_i$依次构造共轭方向组$d_i$，$d_0=\Delta f(x_0)$，在一维方向上搜索极小值$\lambda $

线性模型

• 指数簇：$p(y,\eta)=b(y)exp[\eta^TT(y)-a(\eta)]$
• 线性回归–高斯分布–最小二乘
• 逻辑回归–伯努利01分布$p(y,\eta)=\phi^y(1-\phi)^{1-y}$–sigmoid–log损失
  • 描述：假设数据符合伯努利01分布，在指数簇的推导下得到sigmoid函数，通过极大化似然函数得到log损失函数，通过SGD求解，将数据二分类。
  • 特点：概率，噪声鲁棒性，求解简单；特征空间大，缺失值，多类特征（？）
  • 离散化特征：计算速度快，离散后特征增加表达能力强，异常值鲁棒性，区间值更稳定。
• 广义线性模型，指数簇分布
• 核函数：$w^Tw->\beta_n\beta_mK(x_n,x_m), w^Tz_n->\beta_mK(x_m,x_n)$

决策树

• 过程：在某个节点，遍历所有属性，根据特定的划分准则将当前的样本子集进行划分。如果子集都是同一类，则标为叶节点，输出值为当前类；如果特征为空，标记为叶节点，输出值为实例数最多的那一类。
• C4.5修正：
  1. 对连续值进行划分（m个特征，生成m-1个划分，每个点为相邻值的均值）；
  2. 信息增益率；
  3. 缺失值：1、如何计算划分准则：仅考虑有值的进行计算，并乘以系数；2、如何划分：将样本划入所有子节点，每个样本权重均分。
• CART修正：
  1. 每个节点二分类，意味着每种属性的所有二分类基尼系数都要计算（连续值排序划分）
  2. 支持回归树，划分准则为均方误差最小
• 划分准则：信息熵、信息增益↑、信息增益率↑、基尼系数↓ $\begin{cases} Ent(D) = - \sum_{k=1}^{y}p_klog_2p_k \\ Gain(D,a) = Ent(D) - \sum_{v=1}^V\frac{\arrowvert D^v\arrowvert}{\arrowvert D\arrowvert}Ent(D^v) \\ Gain\_ratio(D,a) = Gain(D,a)/-\sum_{v=1}^V\frac{\arrowvert D^v\arrowvert}{\arrowvert D\arrowvert}log_2\frac{\arrowvert D^v\arrowvert}{\arrowvert D\arrowvert} \\ Gini\_index(D,a) = \sum_{v=1}^V\frac{\arrowvert D^v\arrowvert}{\arrowvert D\arrowvert}(1-\sum_{k=1}^yp_k^2) \end{cases}$
• 剪枝，连续与缺失值
• 特点：直观，非线性，相互作用；过拟合，无排序

SVM

• 对偶问题，KKT $\begin{cases} min f(x) \\ s.t. h_i(x)=0 \\ s.t. g_j(x)\leq 0 \end{cases}$ $\begin{cases} g_j(x)\leq 0 \\ \mu_j(x)\geq 0 \\ \mu_jg_j(x)= 0 \end{cases}$
• 区别：损失函数、稀疏性（噪声、缺失）、正则项、距离&概率
• 特点：特征空间大，非线性，相互作用；样本多效率低
• 核函数：线性不可分，用来计算高维空间内积（不需知道如何映射），核矩阵半正定。只要w能表示成$\phi(x)$的线性组合
• SMO算法：选取使对应样本间隔最大的变量$\alpha_i$$\alpha_j$，固定其他参数。用$\alpha_j$表示$\alpha_i$，得到关于$\alpha_i$的单变量二次规划问题，求解。选取所有支持向量求平均得到b。

贝叶斯

• MLE&MAP：频率&贝叶斯，正则项&先验估计
• 拉普拉斯平滑：避免未出现项预测为0
• EM：对含有隐变量的模型进行极大似然估计：估计隐变量的期望，最大化似然参数

集成

• Boosting：基学习器训练完后，根据其表现对样本重新调整，使错误得到更多关注
• Bagging：对样本采样训练新的基学习器，总结果投票或平均
• stacking：初级学习器的输出作为新的输入特征，训练次级学习器
• 多样性度量
• adaboost：$h_t$纠正$H_{t-1}$的错误，使$l_{exp}(H_{t-1}+h_t \vert D)$最小化，得到新的分布$D_{t+1}$，重新赋值或重采样
• RF：随机选取样本、特征，生成决策树，测试时投票，特征重要性（袋外数据测试，特征加噪声测试，下降大则重要）
• GBDT：boosting，回归树，损失函数为均方误差和指数损失。
  • 回归任务：1、每轮迭代时计算每个样本的损失函数的负梯度，2、根据所有样本和梯度生成该轮的CART树，3、在树的每个节点线性搜索找分割点，使最小化损失函数，得到这一轮的生成树；4、所有生成树相加。
  • 分类任务：回归树，每一轮建k棵树，样本得到k个输出（每个样本在每一棵树上对应唯一一个叶子节点输出），通过softmax计算概率值，得到残差（概率值的差）。预测时所有概率值累加（？）
  • 特点：回归树、boosting、串行；异常值
  • 离散特征：样本通过GBDT产生特征，每棵树每个叶节点结果形成向量（是否落在该节点）([1,0,0,1,0])，后续加入逻辑回归学习
  • 调参：高lr，树的个数，调树参数（深度，最小分裂节点数，subsample），（xgboost调正则项），降lr，增树
• Xgboost：
  • 1、基学习器；2、 一阶二阶展开，自定义；3、正则项，叶子节点数与节点分数L2；
  • loss由n个样本求和转换成T个节点求和，二元函数求极值，每个节点loss仅与该节点样本的一阶二阶导数相关。
  • 节点切分：该节点所有样本按特征值排序，线性搜索切分，切割点为增益最大的点；样本过多时，近似切分，根据特征分位数找切割点。（近似切分，一个集合，给定x，rank(w)，d，找到使rank(w)满足d的切分点）
  • 学习率（一次迭代后，叶子节点乘系数，削减影响，增加后面的学习空间）
  • 缺失值：假设缺失值在右，升序排列，计算左边，取极大值分割；反之依然；再取极大值。
  • 特征并行化：按特征值排序，存储在block中，一次计算可重用；
  • 非连续内存读取：1、预先将所有数据加载到buffer中；2、选择大小合适的block—size
  • block在硬盘上存储：1、先压缩再存储，载入后解压；2、存储在多个磁盘，线程交替读取
• lightGBM：
  • histogram：特征离散化（int8离散值，分裂增益O(k*feat)，单树精度下降-正则化），做差加速
  • leaf-wise：全局查找分裂点：对所有节点求梯度，排序，选取topN（权重1）和后面的随机采样（权重减少），查找每个特征的最佳分割点。（采样增加泛化性）
  • 稀疏特征捆绑：1、特征分开组成bundle：计算特征间相关性（或非零元素个数），由大到小排序，根据冲突数量判断加入已知bundle或新建bundle；2、同一bundle特征合并：特征加偏移放入histogram的不同桶。
  • 分类类别特征：不需独热编码（基数越大越不平衡），O(klogk)类别划分两个子集，根据相关性排序划分。

聚类

• 性能度量
  • 外部指标：考虑两个簇划分，两个样本是否属于同一个簇。Jaccard$\frac{a}{a+b+c}$；FMI$\sqrt{\frac{a}{a+b}\times \frac{a}{a+b}}$；rand指数$\frac{2(a+d)}{m(m-1)}$
  • 内部指标：DB指数（簇内平均距离/簇中心距离）
• 距离度量：1、有序特征。闵可夫斯基距离$(\sum {(x_i-x_j)^p})^{1/p}$；2、无序特征。VDM$(\sum{\frac{m_{u,a,i}}{m_{u,a}} - \frac{m_{u,b,i}}{m_{u,b}}})^p$。m_{u,a,i}表示第i簇中属性u取值为a的样本数目。
• kmeans（耗时；依赖于k、初始化；异常点；局部最优）
  • kmeans++（选取最远点为初始化点），ISODATA（不常使用，方差大时分裂，距离近时合并）
• 高斯混合模型：由k个高斯模型加权和组成，计算$x_i$由第j个高斯混合成分生成的后验概率
  • 步骤 $\begin{cases} P_M(x)=\sum\alpha_iP(x\vert\mu_i,\Sigma_i) \\ \gamma_{ji} \text{:$x_i$由第j个高斯混合成分生成的概率} \\ \lambda_j = argmax(\gamma_{ji}) \end{cases}$
  • EM算法：E，计算$\gamma_{ji}$；M，最大化似然函数，更新$\alpha_i$，$\mu_i$，$\Sigma_i$

降维与度量学习

• KD-tree：k维空间构造二叉搜索树，方便最近邻检索
  • 生成：选取方差较大的维度，选取中位数作为划分点，迭代生成树。（搜索时会有误差）
  • 搜索：依次查询找到叶节点；叶节点找到最近距离，回溯，判断兄弟节点是否有更近点，递归。

半监督

• 生成式方法：假设样本由高斯混合模型生成，最大化后验概率，无标记样本看做缺失参数，用EM求解
  • $argmax \Sigma_{i=1}^{N} p(y=j\vert \theta=i, x)\cdot p(\theta=i\vert x)$
  • EM算法：E，计算$\gamma_{ji}$；M，最大化似然函数，更新$\alpha_i$，$\mu_i$，$\Sigma_i$
• TSVM：对未标记进行各种可能的指派，找到间隔最大化的超平面
  • 用$D_l$训练svm，并对$D_u$预测$\hat y$
  • 初始化权重$C_l>C_u$，一起训练SVM，在$D_u$中选择最可能出错的异类样本（松弛变量）$\xi_1+\xi_2>2$，交换，重新训练，增加$C_u$
  • $C_l=C_u$时停止
  • 类别不平衡

概率图

• HMM：2变量，3参数
• MRF：极大团
• CRF：多个变量给定观测值后的条件概率建模

机器学习数据

• 数据清洗
  • 分析数据：画图，清洗异常点、噪音
  • 缺失值：1、较少，则删除；2、数据均匀，均值、中位数代替；3、插值，找个类似样本（数据分层后插值）；4、其他特征建模预测？？
  • 异常值：算法是否敏感（基于距离的敏感）；同缺失值
• 数据转换
  • 标准化：统一量纲；加速收敛
  • 独热编码
  • 连续值二值化
• 数据降维
  • 消除相关性，减少冗余，减小噪声
  • PCA：标准化（减均值），协方差矩阵特征值分解
• 特征选择（维数灾难，去除冗余减少难度）
  • 过滤式：考虑特征相关性。特征自身方差大（有差异性）；皮尔逊系数（$E((X-\mu_X)\cdot (Y-\mu_Y))/\sigma_X\sigma_Y$协方差除以标准差，特征之间相关性）；卡方检验（相关性）；互信息（引入Y使得X熵的变化）
  • 包装式：根据目标函数选择特征。每次选择若干特征，或剔除。
  • 嵌入式：特征选择与训练同时。正则化（选择W的非零特征）；树模型训练
• 模型选择
  • 评估方法：k-fold、留出法（要分层采样）、自主法（有放回采样，63.2%，适合数据少）
  • 性能度量：混淆矩阵，查准率，查全率，PRC，ROC，AUC（ROC不受正负样本比例影响）

  • TP	FN
    FP	TN

  • 偏差与方差