跳转至

考点

考前提醒:

  • 特别注意对数底的问题, 有一些对数的底是2, 有一些是e, 有一些是10
  • 特别注意在线性回归和神经网络中, 不要忘记截距, 特别容易忘
  • 不要忘记计算器

重要程度:

  • 超级重要: ☢️
  • 重要: ⚠️
  • 一般: ♻️
  • 不重要: 🗑️
  • 超级不重要: 🏴‍☠️
  • 预处理
  • 线性回归
    • ⚠️梯度下降权重公式: \(w_{i+1}=w_i-a_i\frac{df}{dw}(w_i)\), 对于普通梯度下降, 小批量梯度下降, 随机梯度下降, 计算梯度的方法有所不同, 用于计算梯度的数据点分别为: 全部, 随机选一小部分, 随机选一个, 梯度计算公式分别为\(\sum_{j=1}^n(w_i^Tx^{(j)}-y^{(j)})x^{(j)}\), \(\sum_{j\in B_j}^n(w_i^Tx^{(j)}-y^{(j)})x^{(j)}\), \((w_i^Tx^{(j)}-y^{(j)})x^{(j)}\), 在计算资源需求和更快收敛之间权衡
    • ⚠️批量梯度下降复杂度分析: 其闭式解为\(w=(x^Tx)^{-1}x^Ty\), \(x^Tx\)的复杂度是\(nk^2\), 转置矩阵的复杂度为\(k^3\), 所以时间复杂度是\(O(nk^2+k^3)\), 空间复杂度是\(O(nk+k^2)\)
    • ♻️选择学习率大小: \(\alpha_i=\frac{\alpha}{n\sqrt{i}}\). 注意这个学习率是每一步都会变化的, 越到后面越小. 学习率太小converge too slowly; 太大can diverge
    • ⚠️正则化, 重点关注L2, 其误差函数中的\(\alpha\)控制的是模型的复杂度, 防止过拟合, L1和L2的差别是L1会让某些特征直接消失; 还有注意一下岭回归的的损失函数, 第二项用于控制模型的复杂度, 较大的\(\lambda\)倾向于让参数减小, 降低复杂度
    • ♻️️似然函数表示的是属于1或者0的概率, \(p(y_i|x_i; w)=\sigma(w^Tx_i)^{y_i}[1-\sigma(w^Tx)]^{1-y_i}\), 对于整个训练集的点都计算似然函数, 然后取对数, 得到对数似然函数, 越大越好; 对对数似然函数取反得到交叉熵误差函数, 越小越好.
    • ⚠️给出逻辑函数, 样本点, 权重, 计算它属于哪一个类, 如给出分水岭是0.5, 给出权重向量, 和一些样本点, 计算这些样本点属于哪一个类别
    • ♻️对数损失似然损失函数, 注意那里的\(p\)是是否等于\(1\)的概率
  • 最邻近
  • 朴素贝叶斯
    • ☢️使用朴素贝叶斯算法进行预测
    • ⚠️数值属性朴素贝叶斯进行预测, 注意, 计算条件概率的时候, 要计算该条件下的均值和标准差
    • ⚠️处理缺失值问题, 新样本中某些属性缺失, 不要在计算p(E|yes)和计算p(E|no)的时候包括那个缺失值的属性, 如没有outlook则不要包含\(p(outlook|yes)\)和\(p(outlook|no)\); 表中的某些属性值缺失, 则不要将缺失值纳入计数, 如在yes下, outlook列中有一个缺失值, 则直接跳过, 不用管.
    • ♻️处理零频问题, 使用拉普拉斯, \(P(E_i|yes)=(count(E_i)+1)/(count(yes)+m)\), 零频的时候\(count(E_i)\)应该是等于\(0\)的, \(m\)是属性可能取值的数量
  • 评估
    • ♻️混淆矩阵计算, T字开头代表正确预测, P字打底代表结果是1, 准度是(TP+TN)/(TP+TN+FP+FN), 注意它本身不是性能衡量指标, 只是一个工具
    • ⚠️计算准度的方法, 包括stratification, repeated hold out, cross validation, grid search, leave one out这些有啥含义, 为啥要用
  • 决策树
    • ☢️信息熵, 信息增益的计算, 特别注意, fx-82系列计算器上没有\(log_2\), 需要使用换底公式\(log_2(x)=\frac{\log(x)}{\log(2)}\), 主要就是一个熵和一个条件熵的计算
    • ☢️如何选择最优属性, 熵越小, 纯度越高, 选择的应该是信息增益最大的属性

  • 集成学习

    • ♻️如何计算集成学习模型的错误率, 大概会有\(1-(1-1/n)^m\)的样本会被抽样到新的训练集中
    • ⚠️Bagging如何进行抽样
    • ♻️随机森林思想, 和Bagging差不多, 多了一个特征, 换汤不换药

    • ☢️Adaboost进行预测, 能够计算错误率(初始错误率为\(1/n\)), 基分类器的权重, 归一化后/前的样本集权重

      特别注意

      课件上的例子中计算基分类器权重的时候使用的是以\(10\)为底的对数, 这是错误的, 应该是自然对数, 因为对于\(\beta_t\)求导的时候产生的结果中是自然对数. 相关链接.

  • 支持向量机

    • ♻️给定决策边界, 计算边际距离, 套公式
    • ⚠️理解拉格朗日函数: 拉格朗日函数结合了约束条件\(y_i(\boldsymbol{w}\cdot \boldsymbol{x_i}+b)\geq 1\)和目标\(\frac{1}{2}||\boldsymbol{w}||^2\), 最小化目标就是最大化拉格朗日函数, \(max \{L(\boldsymbol{w}, b, \boldsymbol{\lambda})\}=max \sum_{i=1}^N\lambda_i-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_j\boldsymbol{x_i}\cdot\boldsymbol{x_j}\), 其中, 最后有两个点积, 第一个是两个训练向量的类的点击, 后面是两个训练向量特征的点积
    • ☢️给出拉格朗日乘数和支持向量计算决策边界, 系数矩阵的解为\(\boldsymbol{w}=\sum_{i=1}^N\lambda_iy_i\boldsymbol{x_i}\)
    • ⚠️软边界和硬边界: 约束条件变为\(y_i(\boldsymbol{w}\cdot \boldsymbol{x_i}+b)\geq 1-\xi_i\), 目标函数变为\(\frac{1}{2}||\bm{w}||^2+C\sum \xi_i\), \(C\)越大, 说明对于点分类越严格
    • ♻️核方法如何简化点积计算, 相当于上面拉格朗日方程中的\(\bm{x_i}\cdot\bm{x_j}\)的计算会大大简化
  • 降维
    • ⚠️计算最佳主成分数量, 两种方法, 一种minimum percentage, 另一种elbow method(看图说话)
    • ⚠️如何通过奇异值分解确定主成分, 看里面的例子, 取奇异值矩阵对角线的左上角部分对应的主成分
    • ☢️压缩率计算, 原来\(n\times m\)的矩阵经过奇异值分解变成三个矩阵, 大小分别是\(n\times k\), \(k\times k\), \(m\times k\), 所以新新占有空间为\(k(1+m+n)\), 压缩率为\(k(1+m+n)/(n\times m)\), \(k\)就是主成分的数量, 对于样本数量非常大的情况下, \(m+1\)可以忽略不计, 变为\(k/m\)
  • 神经网络
    • ☢️感知机学习过程, 权重更新公式\(\bm{w}^{new}=\bm{w}^{old}+e\bm{x}^T\), \(e=t-a\), \(t\)为目标输出(\(0\)或\(1\)), \(a\)为实际输出(\(0\)或\(1\)), \(\bm{x}\)为输入向量; 同时还要调整截距, \(b^{new}=b^{old}+e\). 一般来说, 便于计算, 顶多一个Epoch. 结束条件是所有的样本都被正确分类or训练达到最大次数. 特别提醒, 计算一定要按照课件上的框架来, 很容易算错
    • ♻️为什么神经网络往往有多层: 在现实世界中, 问题往往不是线性可分的, 通过感知机可以实现与门, 或门, 与非门, 通过这些门的组合能够得到更加复杂的边界
    • ☢️前向传播, 给出一张网络的图, 计算最后的输出. 使用的是sigmoid函数, \(y=1/(1+e^{-x})\), 这个函数记住
    • ☢️反向传播, \(w_{pq}(t+1)=w_{pq}(t)+\Delta w_{pq}\), 其中\(\Delta w_{pq}=\eta\cdot \delta_q\cdot o_p\). 根据\(q\)的不同, 有两个版本的反向传播公式, 若\(q\)是输出层神经元, 则\(\delta_q=(t_q-o_q)f'(z_q)\), 若\(q\)是隐藏层神经元, 则\(\delta_q=f'(z_q)\sum_i w_{qi}\delta_i\), 其中\(f'(z_q)=o_q(1-o_q)\), \(\eta\)是学习率, \(z_q\)是\(q\)神经元激活函数处理前的输出, \(f(z_q)=o_q\). 此外, 截距的更新公式为\(\theta_q(t+1)=\theta_q(t)+\eta\cdot \delta_q\), 注意, 在计算前面神经元新权重的时候, 使用的\(w_qi\)是旧的权重, 不是新的权重
    • ♻️训练方式: 标准的方法是每轮都会一个接一个把所有的样本过一遍神经网络. 其他方法有: a. 每一轮都对样本进行随机排序; b. 增大错误率高的样本出现的几率; c. 小批量轮次, 以N为单位输入样本, 取得它们的累积错误率, 然后一梭子反向传播
    • ♻️感知机能够实现什么门, 感知机能够实现与门, 或门, 与非门, 但是不能实现异或门
    • ⚠️神经元的数量. 从较小的网络开始, 慢慢训练较大的网络, 直到准度不再升高
    • ⚠️学习率大小. 学习率太小, 收敛很慢, 学习率太大, 可能造成震荡, 正确的做法是随着训练轮次的增加, 减少学习率
    • ♻️Dropout. 每次反向迭代的时候, 随机选择部分神经元, 将其输出设置为\(0\)表示丢弃
    • ♻️动量, 减少震荡的发生, 增大学习率, 方法是引入之前梯度更新的累积量, \(\Delta w_{pq}=\eta\cdot \delta_q\cdot o_p+\mu (w_{pq}(t)-w_{pq}(t-1))\)
    • ♻️权重初始化策略. 在-1->1内随机初始化或者从正态分布中随机采样, 标准差是\(\sigma=\sqrt{\frac{2}{N_{in}+N_{out}}}\), 其中\(N_{in}\)是输入神经元的数量, \(N_{out}\)是输出神经元的数量, 注意, 这里的输入输出神经元不是整个神经网络的输入输出神经元, 是相对于当前层神经元来说的上一层/下一层神经元, 当前层神经元就是权重/截距待更新的神经元
    • ♻️Softmax: 假设输出为独热编码, 则输出向量的值\((o_1, ..., o_n)\)可以通过softmax函数转换为概率, \(p_i=\frac{e^{o_i}}{\sum_j e^{o_i}}\), 例子简单看下
    • ⚠️梯度消失, 记得之前计算错误率\(\delta_q\)的时候, \(f(z_q)'=o_q(1-o_q)\), \(o_q=f(z_q)\), 经过激活函数激活后, \(o_q\)可能会非常接近\(0\)或者\(1\), 导致计算出来的\(\Delta w_{pq}\)很小, 导致传播过程中梯度消失, 收敛变慢, 解决的方法是使用残差
    • ⚠️计算卷积结果, 给你一个3*3的卷积核, 计算卷积结果, 特征图中为零的部分说明是没有特征, 明显大于0的部分说明有特征
    • ♻️CNN的超参数: CNN的超参数主要有两个, 一个是stride, 步长, 可用来控制特征图的大小; 一个是padding, 用来处理图像的边缘区域, 防止边缘的特征丢失. receptive field输入图像上的某个区域, 这个区域能够影响特征图中的某个元素.
    • ⚠️池化: 主要有两种方式, 一种是最大池化, 选择区域中的最大值, 一种是平均池化. 一般来说, 如果图像是白底黑字, 则使用平均池化, 如果是黑底白字, 则使用最大池化
    • 🗑️其他神经网络: 大概率不会考很多, 大题不可能考CNN, RNN, Transformer. 所以, 可以随便翻一下, 过一眼结束了, 还有CNN注意一下卷积怎么算, 还有Max/Average Pooling怎么得到特征图的
  • 聚类
    • ♻️给出两个簇中所有点的坐标, 计算簇的距离, 考虑single link, complete link, averge link, 分别是距离最小, 最大, 平均
    • ☢️K-means聚类如何分簇
    • ⚠️选取初始质心的方法, 无非三种方法, 选择离当前质心最远的点, 随机选取点但有最小SSE, 使用K-means++算法
    • ⚠️解决空簇问题: 使用上面选择初始质心的方法, 除了SSE. 选择SEE较高的簇, 从中选择一个起始点
    • ⚠️解决离群问题: a. 在聚类开始之前移除outliers; b. 在聚类之后移除对SSE贡献异常大的点(优先)
    • ♻️GMM算法如何进行分簇, 要知道正态分布的概率密度函数\(f(x)=\frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{(x-\mu)^2}{2\sigma^2}}\), 然后才能计算每个点属于特定正态分布的概率, 注意每个分布的权重, 点属于某个分布的概率为\(p(distribution\ j|x_i, \theta)=\frac{w_jp(x_i|\theta_j)}{w_1p(x_i|\theta_1)+w_2p(x_i|\theta_2)}\), 然后新的权重为\(\mu_1=\sum_{i=1}^n x_i\frac{p(distribution\ 1|x_i, \theta)}{\sum_{i=1}^n p(distribution\ 1|x_i, \theta)}\)
    • ♻️聚合式算法如何进行分簇, 首先每个点当作一个簇, 然后慢慢合并距离最近的两个簇, 直到变成一整个簇, 看一下例子就行, 注意一下那个distance matrix
    • ☢️DBSCAN算法如何分簇, 把core point, border point, noise point, MinPts, Eps的理念搞搞懂, 特别注意, MinPts是包括自己的; a. 任何两个核心点, 若在各自对方的Eps内, 属于同一个簇; b. 任何边界点放在与其相关联的核心点所属的簇中; c. 噪声点抛弃
    • ⚠️如何选择Eps和MinPts, 和elbow method很像, 画出一个点到\(k\)个最近邻居的距离图
    • ☢️计算凝聚度/分离度, 很简单, 但是很重要, 看清楚是不是平方距离
    • ♻️计算轮廓系数, 对于一个点, 一个簇, 整个聚类, 计算轮廓系数有不同, 越接近1越好, ai表示的是凝聚度, bi表示的分离度, ai越小越好, bi越大越好, \(s_i=\frac{b_i-a_i}{max(a_i, b_i)}\)
    • ♻️相似度矩阵是啥
    • ⚠️如何选择簇的数量: 选择SSE的拐点对应的簇的数量, 选择轮廓系数的最大值对应的簇数量
  • 马尔可夫链
  • 强化学习
    • ♻️智能体: 在每一个时间步, 智能体接受状态和奖励, 执行动作. 环境接受动作, 更新状态, 发出新的奖励
    • ♻️折扣因子是啥, 表示对未来的重视程度, 较高的\(\gamma\)对应更关注长期回报
    • ⚠️两种价值函数, Bellman方程, 最优Q值函数, state-value函数衡量的是当前的状态在遵循Policy的预期累积回报; action-value函数是在当前状态下采取行动后遵循Policy的预期累积回报
    • ⚠️最优Q函数和Bellman方程: 最优Q函数就是在所有可能的Policy中, 最大的预期累积回报. 最优Q函数遵循Bellman方程, Q*等于即时回报和将来回报乘以折扣因子, \(Q^*(s, a) = \mathbb{E}_{s' \sim \mathcal{E}} \left[ r + \gamma \max_{a'} Q^*(s', a') \,|\, s, a \right]\)
    • ⚠️Q学习算法, 核心思想是维护一张Q表, 每次迭代都会对某个Q值进行增量更新(使用Bellman方程), 最终得到的Q表中的所有值近似收敛于最佳Q值
    • ⚠️深度Q学习算法, 这里只考虑状态是连续的, 但是动作不是连续的(因为输出的动作概率预测是离散的), 核心思想是维护一个Q网络, 使用和目标Q值之间的差作为损失函数\(L = \left( r + \gamma \max_{a'} Q_w(s', a') - Q_w(s, a) \right)^2\), 输入状态, 给出所有动作的可能性. 在每轮迭代中, 利用\(\epsilon\)调控探索/利用选择动作, 并维护一个记忆池打破和时间的相关性, 从记忆池中均匀采样然后反向传播更新Q网络的权重. 为了防止目标Q值计算的不稳定, 我们引入一个目标Q网络, 使用目标Q网络来评估选择的动作, 而使用原始Q网络选择动作, 这个目标Q网络和原始Q网络的差异是目标Q网络在一段时间内会保持不变, 但是原始Q网络是每次迭代结束都会改变的, 损失函数变为\(L=(r+\gamma Q_{\hat{w}}(s', argmax_{a'}Q_w(s', a')) - Q_w(s, a))^2\)

其他

如何评估一个模型, 从以下几点出发:

  • 能否有效可视化?
  • 是否具有良好的可解释性?
  • 能否很好的处理过拟合?
  • 训练时间是否长? 消耗的计算资源是否多?
  • 是否需要很大的数据集?
  • 是否能够/需要降维?
  • 能够处理不同大小/形状/密度的簇?