机器学习期末复习
机器学习期末复习
线性回归
1.根据有无标记，机器学习可以分为哪几类？
- 监督学习：有标记
- 分类、回归
- 无监督学习
- 聚类、降维
2.根据标记的数值类型，可以把监督学习分为哪两类?
➢分类：标记为离散值
➢回归：标记为连续值
3.线性模型有哪两种基本的表示形式？
一般形式：
向量形式：
4.线性模型的特点是什么？
➢ 形式简单、易于建模
➢ 可解释性
➢ 非线性模型的基础
5.线性回归是什么？它的作用和目的是什么？
线性回归的数学定义：
求出
线性回归的目的是学得一个线性模型以尽可能准确地预测实值输出标记
6.线性回归问题的数学实质是什么？或者说数学表示是什么?
7.求解线性回归问题有哪些方法？
统计学方法（解析法）：单特征、多特征
计算机优化算法（梯度下降法）
8.最小二乘法求解一维线性模型的推导过程。
9.梯度下降法是什么？请描述一下梯度下降法的步骤过程。
梯度下降法是一种经典的数值优化算法，从空间中任一给定初始点开始进行迭代。在每次迭代中，计算目标函数在当前点的梯度，并沿着与梯度方向相反的方向按照一定步长移动到下一可行点。
10.在线性模型中，梯度下降的具体迭代公式是怎样的?
用向量形式表示迭代公式：
11.按照所使用样本数量的不同，梯度下降法可以分为哪几类？它们的区别是什么(比较）？
根据所使用样本数量的不同，梯度下降法分为：
• 批量梯度下降法：每次更新用全部样本
• 随机梯度下降法：每次更新用1个样本
• Mini-batch梯度下降法：上面两种方法的结合，所有数据分割成 𝐾个mini-batches，每次迭代使用mini-batch的数据做更新
➢批量梯度下降：学习稳定性较好
➢随机提低下降：收敛速度较好
➢Mini-batch: 适合并行化设计
12.比较一下解线性回归问题的两种方法：梯度下降法和矩阵变换的统计学方法（解析解方法）
➢梯度下降
• 需要选择学习率 𝜂
• 需要迭代很多轮次
• 特征维度比较大时也运行正常
➢矩阵变换
• 不需要选择学习率 𝜂
• 不需要迭代
• 需要矩阵计算(𝑋^-1^𝑇𝑋)^-1^
• 当维度过大时计算耗时
逻辑回归
➢基于似然函数的损失函数
➢梯度下降法求解
➢多分类和类别不平衡
模型评估
➢泛化误差
在新样本上的误差
➢过拟合
过拟合：经验误差小，泛化误差大 → 特征维度太多
➢训练集/测试集的划分
➢留出法：直接划分、分层抽样
➢交叉验证法：将数据集分层采样划分为𝑘个大小相似的互斥子集。 每次用𝑘 - 1个子集的并集作为训练集，余下的子集作为测试集。最终返回𝑘个测试结果的均值
➢自助法：对大小为𝑚的数据集𝐷有放回采样𝑚次得到训练集𝐷’ ，用剩下的数据做测试集。
➢评估度量：查准率、查全率、 F1、 P-R曲线、 ROC曲线
根据模型的预测结果对样例排序，并逐个作为正例进行预测，以“假正例率”为横轴，“真正例率”为纵轴可得到ROC曲线，全称“受试者工作特征” (Receiver Operating Characteristic)
➢误差来源：偏差-方差分解
泛化误差可分解为偏差、方差之和：
➢ 偏差度量了学习算法期望预测与真实结果的偏离程度；即刻画了学习算法本身的拟合能力
➢ 方差度量了同样大小训练集的变动所导致的学习性能的变化；即刻画了数据扰动所造成的影响
集成学习
➢ 集成学习：如何产生并结合“好而不同”的个体学习器
集成学习 (ensemble learning)通过构建并结合多个学习器来完成学习任务，又称为多分类器系统（multi-classifier system）、基于委员会的学习（committee-based learning）。
同质（homogeneous）集成：个体学习器类型相同
异质（heterogeneous）集成：个体学习器类型不同
➢ 产生：
• 并行化方法： Bagging 和随机森林
并行化方法：可同时生成、个体学习器间不存在强依赖关系的方法
Bagging
算法流程：
• Step 1： 使用自助法产生数据集
• Step 2: 重复上述操作，共生成𝑇个独立的数据集
• Step 3: 利用上述各数据集训练出𝑇个学习器
• Step 4: 投票或者简单平均法决定最终分类器
基本特点
• 个体学习器不存在强依赖关系
• 并行化生成
• 自助采样法
时间复杂度低：
𝑇 × (个体学习器复杂度 + 投票/平均法结合)
从偏差-方差的角度： 降低方差，在不剪枝的决策树、神经网络等易受样本影响的学习器上效果更好
随机森林
Bagging + 决策树=随机森林
随机属性选择： 先从该结点的属性集合中随机选择𝑘个属性，再从中选择一个最优属性用于划分
随机性： 采样的随机性（自助采样法） 、属性选择的随机性（基决策树最优属性的选择）
特点：简单、容易实现、计算开销小，被誉为“代表集成学习技术水平的方法”
• 串行化方法： Boosting 和AdaBoost
串行化方法：必须串行生成、个体学习器间存在强依赖关系的方法
Boosting
Boosting是一种可将弱学习器提升为强学习器的算法
工作机制：
- 从初始训练集训练出一个基学习器， 再根据基学习器的表现对训练样本分布进行调整， 使得先前基学习器做错的训练样本在后续受到更多关注。
- 从调整样本分布后的训练集训练出下一个基学习器
- 重复进行，直至基学习器数目达到事先指定的值T
基本框架：
- 产生第一个 分类器 ℎ1(𝒙)
- 产生第二个分类器 ℎ2(𝒙) 来补足 ℎ1(𝒙)
- 找到第三个
- ………
串行：
- 每一个后续模型都会尝试纠正先前模型的错误。
- 后续模型依赖之前的模型。
- 每次调整训练数据的样本分布。
AdaBoost
AdaBoost是Boosting的代表算法。
通过“重赋权” 来实现对特定的数据分布进行学习： 依据前一个分类器的分类结果，通过调整权值，产生一个新的样本分布，使下一个分类器更多地关注错误分类的样本 。
输入输出：
基本步骤：
步骤1：初始化训练数据的起始权值分布
步骤2：对𝑇个个体学习器，依次序列化进行以下步骤
𝕀 是指示函数，后面条件满足为1，否则为0.
这里2.1大概是对Dt样本分布的数据训练得到误差最小的h.
关键点：数据权重调整（步骤2.4，分类错误的数据得到更多的关注 ）。弱分类器权重(步骤2.3，分类错误率越小的分类器在最终分类器中起的作用越大 )
Bagging和Boosting对比：
➢ 结合：平均法、投票法、学习法
平均法（用于数值型输出，有简单平均法、加权平均法等）
投票法（用于分类任务，有绝对多数投票法、相对多数投票法、加权投票法等）
学习法（用于训练数据较多的情形，代表是Stacking）
Stacking:把样本在各个个体学习器的输出当做特征，把样本的标记仍然当做标记，以此为训练数据训练出学习器。
聚类
➢“物以类聚”
无监督学习
“物以类聚” ， 即同一簇的样本尽可能彼此相似, 不同簇的样本尽可能不同。 换言之， 聚类结果的“簇内相似度” 高， 且“簇间相似度” 低。
➢原型聚类法： k-means
算法思想：初始随机给定k个簇中心，按照最邻近原则把样本点分到各个簇，然后按平均法重新计算各个簇心。 迭代直到簇心的移动小于一定阈值。
算法流程（迭代优化）：
初始化每个簇的均值向量
repeat
- 基于样本到各个簇的均值向量的距离，进行簇划分(把样本点分到各个簇)
- 计算每个簇的均值向量
until 当前均值向量均未更新
优点：简单，高效。收敛快。可解释性强。
缺点：决定k值。可能会收敛到局部最优。圆形数据效果好， 不规则数据效果差。
➢密度聚类法： DBSCAN
基本概念：
密度直达、密度可达、密度相连
簇：由密度可达关系导出的最大密度相连样本集合。
算法流程：
- 找出“邻域”参数（𝜖, 𝑀𝑖𝑛𝑃𝑡𝑠） 下所有的核心对象
- 以任一核心对象为出发点，找出由其密度可达的样本生成聚类簇，直至所有核心对象被访问过
优点：对异常值不敏感。能发现任意形状的簇。
缺点：𝜖, 𝑀𝑖𝑛𝑃𝑡𝑠 参数难以调整 。如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差。
➢层次聚类法： AGNES
层次聚类在不同层次对数据集进行划分， 形成树形的聚类结构 。
AGNES （Agglomerative Nesting）
自底向上的层次聚类：先把样本中的每一个样本看做一个初始聚类簇， 然后迭代地找出距离最近的两个聚类簇进行合并
簇间距离：最小距离、最大距离、平均距离。
算法流程：
- 初始化：把每个单一样本当成一个簇，并计算两两簇之间的距离（构建距离矩阵）
- 不断合并距离最近的两个簇，并更新距离矩阵
优点：发现层次关系。灵活定义距离。
缺点：当前类别的合并决策会影响后续的类别划分，整个过程是不可逆的。计算复杂度高。易受异常值影响。
➢性能度量：外部指标和内部指标
外部指标：将聚类结果与某个“参考模型”进行比较
S：same D：different
内部指标：直接考察聚类结果而不利用参考模型
降维
➢降维
维度灾难：维度（特征的个数） 越大， 计算复杂度越高
降维(dimension reduction)：缓解维数灾难的一个重要途径。即通过某种数学变换， 将原始高维属性空间转变为一个低维“子空间” ， 计算复杂度也随之降低。
效果：数据压缩、计算高效、隐私保护。
➢主成分分析：坐标变换，特征值分解，特征向量
主成分分析 (Principal Component Analysis, PCA) :基于线性变换的降维方法
内积：将两个向量对应元素相乘再求和 。如果向量𝑏的模为1，则内积为𝑎向𝑏所在方向的投影的长度 。
坐标变换：
特征值分解：
算法流程：
贝叶斯分类
➢ 朴素贝叶斯：贝叶斯定理（后验=先验×似然），基于后验概率做分类
先验概率：表示在实际观察事件之前对某个状态的预期
后验概率：给定某观测到特征𝒙，其属于特定类别的概率𝑃(𝑦|𝒙)
算法流程：
➢ EM 算法：存在隐变量的参数估计
基本思想：
若参数𝜃已知，则可根据训练数据推断出最优隐变量𝑧的值(E步)；
反之，若 𝑧已知，则可方便地对𝜃做极大似然估计(M步)。
算法流程：
支持向量机
➢支持向量机：间隔最大化
支持向量机(Support Vector Machine, SVM) 是一种二分类模型，其基本模型是定义在特征空间上的间隔最大的分类器 。
目标：寻找超平面，使得间隔r最大化。
软间隔：引入松弛变量𝜉𝑖 ≥ 0，允许一些样本不满足条件。
➢核技巧以解决非线性可分
动机：计算高维空间示例之间的内积复杂度高，而计算𝐾(𝒙, 𝒛)复杂度低
核技巧：在学习和预测中只定义核函数𝐾， 不显式地定义映射𝝓
Mercer定理(充分非必要)：只要一个对称函数所对应的核矩阵半正定, 则它就能作为核函数来使用。
➢序列最小化算法
- 选择两个变量𝜆𝑖和𝜆𝑗 ，固定其它变量，针对这两个变量𝜆𝑖和𝜆𝑗构建一个二次规划问题。
- SMO算法将优化问题不断分解为子问题并对子问题求解（子问题可通过解析方法求解），进而达到求解该优化问题的目的。
- 直到得到的所有变量都满足优化问题的KKT条件。
关键步骤：
（1）求解两个变量二次规划的解析方法
（2）如何选择其中的两个变量： 启发式选择
神经网络
➢神经网络：多个神经元（加权求和+激活函数）组成
神经元：
激活函数：通常情况下，默认选择ReLU， tanh也行。输出是0,1值（二分类问题），输出层选sigmoid，其他层选ReLU。
sigmoid：
tanh：
ReLu：
➢多分类问题： Softmax与交叉熵
➢神经网络的输出：前向传播
➢神经网络的训练：后向传播
梯度下降：链式法则求梯度。
强化学习介绍
➢强化学习的应用
➢顺序决策：考虑策略、值函数和模型
策略：智能体的行为方式 。从状态到动作的映射 。
确定策略、随机策略
值函数（Value function）：表征在某个策略𝜋下获得的累计总奖赏。
模型：描述环境的反馈
➢探索与利用
智能体如何选择行动 ：探索、利用
利用 (exploitation)： 基于已有的经验，选择最大化奖赏的动作
探索 (exploration)：尝试新的动作，该动作可能会带来更大的奖赏，也可能不会
权衡：
• 利用：获取暂时的奖赏最大化；可能失去潜在的更大的奖赏
• 探索：失去暂时的奖赏最大化；学习到潜在的更好的策略
马尔科夫过程
➢马尔可夫决策过程
马尔可夫决策过程 (Markov decision process, MDP) 描述了强化学习的环境规律， 几乎所有的强化学习问题都可以形式化为MDPs 。
➢状态值函数𝑉(𝑠)，动作值函数𝑞(𝑠, 𝑎)
价值函数近似
