Please enable JavaScript.

Coggle requires JavaScript to display documents.

统计学习 (模型 (支持向量机 SVM p110 (线性可分SVM p111 (对偶算法 dual algorithm p118…

- - - - 二类分类问题，且所有数据点线性可分（存在一条直线可以分割不同类别的数据）
      - 找到正确划分数据的，使分割带最宽的w*x + b = 0
        （凸二次规划问题 convex quadratic programming）
      - 函数间隔／几何间隔（正则化的函数间隔）
      - 只依赖于最靠近分离超平面的数据点，称之为support vector，不需要海量数据训练，但必须提供关键的数据点
      - 凸优化 convex optimization p114
        
        http://www.hanlongfei.com/%E5%87%B8%E4%BC%98%E5%8C%96/2015/09/25/cmu-10725-optimization/
      - 对偶算法 dual algorithm p118
        
        应用拉格朗日对偶性，求解对偶问题来得到原始问题的最优解
        
        对偶问题更容易求解，而且自然引入核函数，进而推广到非线性分类问题
        
        构建拉格朗日函数 - 对每一个不等式约束引进拉格朗日乘子
        
        先求L(w,b,a)对w，b的极小，再求对a的极大
        
        对偶形式：分类决策函数只依赖于输入x和训练样本输入的内积
        
        a必须大于0. 最优w和b只依赖于训练数据中ai大于0的数据点xi，称为support vector
    - - 对每个样本点引入一个松弛变量，使得
        同时支付一个代价，使目标函数变为
        即如下凸二次规划
      - 对偶形式
      - 合页损失函数 hinge loss function
        
        线性SVM学习的另一种解释：最小化
        第一项是经验损失
        分类正确时为0，否则为1-yi(w*xi + b)
        
        不仅要求分类正确，确信度也要足够高时损失才为0，对学习有更高的要求
    - - :question:kernel trick
        
        基本思想
        
        将非线性问题变换为线性问题求解。例如定义N个核（landmark），将原数据X转换成到各个核的远近程度的线性组合
        
        将欧式空间的输入X映射到高维甚至无穷维的特征空间（希尔伯特空间）
        以线性问题方式在特征空间求解
        在学习与预测中，只定义核函数，不显示定义映射函数
        
        正定核 p134
        
        常用核函数
        
        多项式核函数 polynomial kernel function
        
        高斯核函数 Gaussian kernel function
        
        字符串核函数 string kernel function
        （定义在离散数据集合上，如字符串集合。用于文本分类、信息检索、生物信息学等方面）
        相同子串越多越相似，核函数值就越大，可由动态规划快速计算
        
        径向基核函数机器学习实战p110
        
        最小的训练错误率并不对应最小的支持向量数目
        
        可以牺牲线性核函数的错误率来换取分类速度的提高
      - 分类决策函数
        
        :question:如何选择合适的核函数？
    - - 将大优化问题分解为多个小优化问题求解，求解时间短很多
      - 目标：求出一系列的alpha和b，再计算权重向量w并得到分隔超平面
      - 原理：每次循环中选择两个alpha进行优化（为了保证约束不被打破）。一旦找到一对合适的alpha就增大其中一个并减小另一个。
        合适条件为：1）两个alpha都必须在间隔边界之外，2）两个alpha还没有进行过区间化处理或者不在边界上
      - 每次只优化两个alpha值来加快SVM训练速度，优化参考 Improvements to Platt's SMO Algorithm for SVM Classifier Design
    - - A Comparison of Methods for Multiclass Support Vector Machine
    - - 原始估计梯度求解器 Primal Estimated sub-Gradient Solver
      - 使用随机梯度下降方法来解决SVM所定义的优化问题，迭代次数之取决于用户要求的精度，和数据集大小无关
      - 从训练数据集随机挑选一些样本点加入待处理列表，按序判断分类是否正确。
        忽略正确分类的点，将错误分类的样本点加入待更新集合。处理完毕后按照错分样本更新权重向量
  - - - k太小，approximation error小，estimation error大，对噪声点更敏感
      - k太大，approximation error大，estimation error小，使模型简化
      - 通常采用cross validation选取最优k值
    - - 欧氏距离
      - Minkowski距离
      - Manhattan距离
    - - kd tree p57
        
        对k维空间中的实例点进行存储及快速检索的二叉树形数据结构
        
        适用于数据量远大于空间维数的情况
        当二者接近时效率骤降如线性扫描
        
        创建：
        
        构造根结点，选择x(1)为坐标轴，以所有数据在该轴上数值的中位数切分出两个子区域
        
        根结点包含落在切分面上的数据点
        
        重复切分步骤，在深度为j的节点选择x(l)为轴，l = (j mod k) + 1
        
        重复直到切分出的两个子区域都没有节点
        
        搜索：
        
        从根出发找出包含目标点的叶结点
        
        以此叶结点为当前最近点
        
        递归地向上回退，在每个节点：
        3.a 若该点保存的数据点离目标更近，重置该节点为当前最近点
        3.b 当前最近点一定存在于该节点一个子节点对应点区域，检查另一个子节点的区域是否覆盖更近的区域，若覆盖则搜索该子节点
  - - - improved iterative scaling p104
        
        设当前参数向量为w = (w0,w1,w2,...wn)
        重复寻找w+d = (w0+d0,w1+d1,...wn+dn)使模型的对数似然函数值增大，直到找到最大值
      - 拟牛顿法 BFGS p106
  - - - 初始化所有点为同一个簇，将其一分为二（k=2的kmeans分类），
        然后选择能更大程度降低SSE的一半继续切分，直到满足给定的k个簇
    - - 分布式聚类算法，可以取得初始的k个簇再运行kmeans算法
  - - - 引入一个常量以保证不会出现0概率，否则会影响后验概率的计算
      - 很多太小的概率相乘会导致下溢出，结果近似成0。可以通过对乘积取自然对数避免下溢出或浮点数舍入导致对误差
      - 单调性相同所以可以替换
  - - - ID3 p78
        
        相当于极大似然法进行概率的选择
        
        用最大info gain选择特征
      - C4.5
        
        用最大info gain ratio选择特征
        
        info gain ratio可以避免训练数据经验熵的差异带来的误差
      - Classification And Regression Tree
        
        给定输入随机变量X的条件下输出随机变量Y的条件概率分布的学习方法
        
        基于训练数据生成决策树，要尽量大，特征选择：回归用least squares，分类用gini index最小化
        
        用验证数据集给树剪枝并依据最小cost选择最优子树
        
        CART生成
        
        :question:回归树机器学习实战p162
        
        遍历每个特征j的每个可能取值s（训练数据集中出现过的值）将数据二元切分，
        对左右两份数据分别求误差（方差之和var(Y)*X.size，引入数据集size来惩罚切出的大数据集）然后相加，
        找到最优的j和s使得切分后两份数据的误差之和最小，但如果一下情况则不切分并返回数据集的Y的均值为叶结点：
        
        进行切分前所有数据的y值都相等
        
        即使最优切分的误差减小也不明显
        
        切出的数据集太小
        
        分类树
        
        用gini index选择特征，同时决定该特征的最优切分点的值
        
        :question:CART剪枝 p88 机器学习实战p170
        
        降低决策树复杂度来防止过拟合
        
        后剪枝
        
        递归地，如果合并两个叶结点后误差会下降，则合并之
        
        预剪枝
        
        回归树算法中提前停止切分的判断条件即为预剪枝
      - 剪枝以防过度拟合
        
        将决策树的节点数加入cost function以惩罚过长的树
        
        正则化的极大似然
        
        只考虑父子节点之间cost的差值，因此可以用动态规划的算分实现
      - 模型树机器学习实战p174
        
        把叶结点设置为分段线性函数来代替取均值
        
        预测准确度更高，可解释性强于回归树
      - R2值比较模型好坏
        
        NumPy.corrcoef(yHat, y, rowvar=0)
        
        越接近1越好
    - - information gain，通过熵entropy衡量
      - information gain ratio = info gain／训练数据的经验熵H(D)
  - - - 平方误差为矩阵写法为对w求导得到使其等于0解出w为
      - 只有X存在逆矩阵时才能用，通过det(X.T * X) == 0判断是否存在逆矩阵
    - - 给待预测点附近每个点赋予一定的权重
      - 使用核函数来对附近的点赋予更高的权重
        k过小会overfitting，k过大会underfitting
      - 会增加计算量，对每个点做预测时都必须使用整个数据集
    - - ridge regression
        
        用于处理特征多于数据样本数的情况，也用于在估计中加入偏差以得到更好的估计
        
        通过lambda来限制所有w之和，能够减少不重要的参数，称该技术为shrinkage
        
        岭回归就是在矩阵上加一个lambda*x使矩阵非奇异从而可以对矩阵求逆，x为一个mxm的单位矩阵。回归系数的计算变为
      - lasso 机器学习实战p152
        
        普通的最小二乘法在约束下会得到与岭回归一样的公式
        
        lasso的约束变为
      - 前向逐步回归机器学习实战p152
        
        贪心算法：每一步都尽可能减少误差（选择对某个权重增加或减少一个很小的值）
        
        算法
        
        对数据高斯分布标准化，在每次迭代中：
        
        遍历所有特征
        
        对每个特征增大或减小相应权重（很小的改变量）得到新权重矩阵
        
        用新的权重矩阵计算预测误差，记录使误差最小的权重矩阵
        
        收集每次迭代中最优的权重矩阵并返回
  - - - 包含该物品的数据占所有数据的百分比
    - - 关联规则A -> B在所有包含A的数据中占的百分比
    - - 一个频繁物品集合的所有子集都必须是频繁的，因此一旦一个集合被认为不频繁就可以不用计算以该集合为子集的频繁度，从而减少计算量
      - 一个频繁物品集合有多个可能的关联因果规则A->B，如果一个物品B为结果的confidence太低，任何包含B为结果的规则都confidence太低
  - - - 通过node link链接来连接相似元素
      - FP树存储item集的出现频率，子集会共享树的部分路径，当集合间完全不同时才分叉
      - 结点上存储单个item及其在序列中的出现次数
      - 构建过程机器学习实战p230
        
        第一遍扫描数据集统计各item出现频率，去掉不满足最小support的item
        
        第二遍只扫描频繁item集
        
        构建一个头指针表来指向每个item类型的第一个元素及存储出现总数
        
        逐条读取item集，按以下规则将所有item加入FP树中
        2.1 将items按照出现频率从高到低排序，然后逐个如下加入FP树
        2.2 从FP树的根结点（代表空集）开始，如果当前结点的子结点中已经存在该item，对其结点的计数加一
        2.3 否则新建一个子结点并连接到头指针表中该元素对应链表的尾端
      - 查找频繁item集机器学习实战p234
        
        抽取条件模式基
        
        对头指针表中的每一个item找到对应的条件模式基conditional pattern base - 以该元素项为结尾的路径集合，即所有可能的前缀路径及其出现数量。
        遍历该item在头指针表中的链表，每个链表结点在FP树中的前缀路径即为要找的前缀路径
        
        创建条件FP树 :question:
        https://blog.csdn.net/Bone_ACE/article/details/46669699
        https://www.cnblogs.com/pinard/p/6307064.html
        https://www.cnblogs.com/ybjourney/p/4851540.html
        
        对每一个频繁item创建一个条件FP树
- - - - 综合多个模型的输出，将弱学习方法提升成强学习方法，选举出的结果准确性更高，
        泛化错误率低，易编码，广泛适用于大部分分类器，无需参数调整
      - 对outlier数据敏感
      - 弱分类器数量过多时可能在不好的数据集上出现过度拟合，使错误率升高，在好的数据集上会达到一个稳定值
    - - 如何在每一轮训练中改变训练数据的概率分布或权值？
        
        提高那些被上一轮弱分类器错判的样本的权值，降低被正确分类的样本的权值
      - 如何将弱分类器组合成强分类器？
        
        加权多数表决，加大分类误差率低的分类器的权值，减小错误率高的分类器的权值
        
        最流行的弱分类器：单层决策树 decision stump
    - - 初始化训练数据权值分布 D1 = (w11, w12, w13, ..., w1N)
        
        对m = 1,2,...,M :question:如何决定M的值？
        2.1. 使用具有权值分布Dm的训练数据学习得到分类器Gm(x): X -> {-1,+1}
        2.2. 计算Gm(x)在训练数据上的分类误差率Em
        2.3. 计算Gm(x)的权值（这里是自然对数）
        2.4. 更新训练数据的权值分布
        若正确分类更新为若错误分类更新为
        （被错误分类的样本的权值将会放大，在下一轮学习中起到更大的作用）
        
        构建基本分类器的线性组合
    - - 最终分类器的训练误差
        说明可以在每一轮学习中选取适当的Gm使得Zm最小，从而使训练误差下降最快
      - 二类分类问题的训练误差界
        说明AdaBoost的训练误差是以指数速度下降的
    - - 因为学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数，就可以简化复杂度
- - - - 监督学习
        
        已知观测序列及对应的状态序列，直接用极大似然法估计隐马尔可夫模型的参数
        
        状态序列通常很难获得
      - 非监督学习
        
        Baum-Welch算法
        
        将观测序列作为观测数据，状态序列作为不可观测的隐变量，
        可以用EM算法估计隐马尔可夫模型的参数
        
        参数估计 p198
        
        所有T之前时刻的任一时刻从状态i转到状态j的概率之和，比上任一时刻处于状态i的概率之和
        
        在T及其之前所有时刻，处于状态j的概率之和（观测O在该时刻的值ot必须是k），比上在T及之前所有时刻处于状态j的概率之和
        
        初始概率分布就是该状态在第一时刻出现的概率
      - 给定模型lambda和观测O，在时刻t处于状态qi的概率记为
      - 给定模型lambda和观测O，在时刻t处于状态qi且在时刻t+1处于状态qj的概率记为
    - - 近似算法
        
        在每一时刻t选择最可能出现的状态，从而得到一个状态序列
        
        计算简单，但不能保证预测序列整体是最有可能但状态序列
      - 维特比算法
        
        用动态规划求解概率最大路径
        
        从时刻1开始，递推地计算在时刻t状态为i的各条部分路径的最大概率，即为最佳路径。从终结点倒推逐步求得前一结点，组成最优状态序列
- - - - 要学习的条件概率分布或决策函数
    - - cost function
        
        0-1 loss function
        
        1 if Y != f(X), else 0
        
        quadratic loss function
        
        (Y - f(X))^2
        
        absolute loss function
        
        |T - f(X)|
        
        logarithmic loss function
        
        -logP(Y|X)
      - 经验风险／损失
        
        f(X)对于训练数据集的平均损失
        
        当样本亮趋于无穷时，经验风险趋于期望风险
        但通常样本量有限，所以不应用经验风险估计期望风险
        
        经验风险最小化
        empirical risk minimization ERM
        
        最大似然估计
        maximum likelihood estimation
        
        需要大量样本，否则可能过度拟合
        
        结构风险最小化
        structural risk minimization
        
        防止过度拟合，等价于正则化
        
        在经验风险上加上表示模型复杂度的正则化项(regularizer)或罚项(penalty term)
        惩罚复杂模型，倾向简单模型
        
        对训练数据和未知数据都有较好预测
        
        最大后验概率估计(maximum posterior probability estimation, MAP)
      - cost-sensitive learning 机器学习实战p134
        
        通过对TP, TN, FP, FN定义cost，使训练算法倾向于代价较小的模型
    - - 训练误差与测试误差
      - 过度拟合与模型选择
      - 正则化
        
        通过惩罚算法复杂度来倾向于经验损失和算法复杂度同时小的模型
      - 交叉验证
        
        k-fold cross validation
        
        把数据分成k份，每次用k-1份训练，另一份测试，
        重复k次取平均测试误差最小的模型
      - 泛化能力
        
        模型对未知数据的预测能力
        
        泛化误差上界
      - 模型类型
        
        生成模型 generative model
        
        从数据学习联合概率分布P(X,Y)，然后求出条件概率分布P(Y|X), P(Y|X) = P(X,Y) / P(X)
        
        给定输入X来产生输出Y，典型：朴素贝叶斯，隐马尔可夫模型
        
        可以还原出联合概率分布P(X,Y)，收敛速度更快，适用于隐变量
        
        判别方法 discriminative model
        
        从数据直接学习决策函数f(X)或条件概率分布P(Y|X)作为预测模型
        
        关心对给定的X，应该预测什么样的输出Y，典型：决策树，k近邻，感知机，逻辑回归，SVM，最大熵等
        
        不能还原出联合概率分布P(X,Y)，准确率更高，
        可对数据进行抽象，定义并使用特征，因此简化学习问题
        
        分类模型 classification
        
        precision
        
        TP / (TP + FP)
        
        recall
        
        TP / (TP + FN)
        
        F1
        
        precision和recall的调和均值
        
        2/F1 = 1/Precision + 1/Recall
        
        标注问题 tagging
        
        输出Y是一个标注序列
        
        用于NLP，信息抽取。典型：隐马尔可夫模型，条件随机场
        
        回归问题 regression
        
        常用平方损失函数，如最小二乘法least squares
      - 随机梯度下降
        
        每次仅用一个样本点来更新回归参数，可以在新样本到来时在线增量式地更新模型，因此是一种在线学习算法
- - - - 把数据映射到使数据点方差最大的方向，然后找到方差次大的方向，以此类推。各方向之间必须正交
        然后只保留方差最大的前几个方向，从而降维
    - - 从噪声数据中抽取相关特征，将高维数据映射到低维空间
      - Latent Semantic Analysis
      - 中间的矩阵只有对角元素有非零值，为奇异值Singular Value，惯例是从大到小排列，在某个数量过后的奇异值都为0，表示对应的数据是噪声或冗余
      - 一般保留奇异值平方和达到90%总和的奇异值
      - Collaborative Filtering 机器学习实战p260
        
        相似度
        
        欧氏距离
        
        Pearson Correlation
        
        cosine similarity
        
        一般选择基于item的相似度计算，因为user数量可能远大于item数量
        
        用最小均方根误差Root Mean Squared Error衡量推荐算法的误差
        
        cold start问题
        
        缺乏数据时如何给出正确推荐？