统计学习方法
2018-09-12 13:55:19 0 举报
AI智能生成
《统计学习方法》的读书笔记
作者其他创作
大纲/内容
第一章 概论
1.1 统计学习
1.统计学习的特点
建立在计算机和网络的基础上
以数据为研究对象,是数据驱动的学科
目的是对数据进行分析和预测
是概率论、统计学、信息论、计算理论、最优化理论和计算机科学等多个领域的交叉学科,并在发展中逐步形成独自的理论体系和方法论
2.统计学习的对象
对象是数据
基本假设:同类数据具有一定的统计规律性
3.统计学习的目的
对数据进行分析和预测
4.统计学习的方法
统计学习方法的分类
监督学习 supervised learning
基本假设
训练数据(training data)是独立同分布产生的
要学习的模型属于某个函数的集合,称为假设空间(hypothesis space)
学习方法三要素
模型的假设空间
模型Model
模型选择的准则
策略 strategy
模型学习的算法
算法 algorithm
非监督学习 unsupervised learning
半监督学习 semi-supervised learning
强化学习 reinforcement learning
5.统计学习的研究
统计学习方法 statisticcl learning
开发新的学习方法
统计学习理论 statistical learning theory
提高学习方法的效率
统计学习应用 application of statistical learning
应用
6. 统计学习的重要性
处理海量数据的有效方法
智能化的有效手段
计算机科学发展的重要组成部分
计算机科学包括 系统、计算和信息。统计学习属于信息。
1.2 监督学习
1.2.1 基本概念
1.基本空间
输入空间 input space
输入所有可能取值的集合
特征空间 feature space
不一定与输入空间相同,存在映射关系
输出空间 output space
输出所有可能取值的集合
通常远小于输入空间
2.联合概率分布
假设联合概率分布P(X,Y)的存在。
3.假设空间
模型属于输入空间到输出空间的映射的集合,这个集合就是假设空间 hypothesis space
监督学习的模型可以是
概率模型
条件概率分布P(Y|X)
非概率模型
决策函数 decision funciton Y=f(X)
1.2.2 问题的形式化
学习流程的简单介绍
1.3 统计学习三要素
1.3.1 模型:
条件概率分布
模型的假设空间定义为概率函数的集合 F={P|P(X,Y)},此时F通常是有一个参数向量决定的概率分布族:F={P|Pθ(X,Y),θ∈R },参数向量θ取值于n维欧式空间R,称为参数空间(parameter space)
决策函数
模型的假设空间定义为决策函数的集合 F={f|Y=f(X)},此时F通常是有一个参数向量决定的函数族:F={f|Y=fθ(X),θ∈R },参数向量θ取值于n维欧式空间R,称为参数空间(parameter space)
1.3.2 策略
1.损失函数和风险函数
损失函数(loss function)或代价函数(cost function)
定义
以决策函数为例
在假设空间中选取了模型f作为决策函数,此模型f的预测值与真实值Y之间的差异,用损失函数或代价函数来度量
损失函数是F(X)和Y的非负实值函数,记做 L(Y,f(X))
常用的函数分类
0-1损失函数 0-1 loss function
平方损失函数 quadratic loss function
绝对损失函数 absolute loss function
对数损失函数 logarithmic loss function 或者对数似然损失函数 log-likelihood loss function
风险函数(risk fucntion)或期望损失(expected loss)
Rexp(f) 是损失函数的期望值,也是理论上模型f关于联合分布P(X,Y)的平均意义下的损失
由于联合分布实际上未知,因此此值不可直接计算获得。
经验风险(empirical risk)或经验损失(empirical loss)
Remp(f) 是模型关于训练样本集的平均损失。
根据大数定理,当样本集无穷大时,Remp=Rexp
现实中由于样本容量有限,用Remp估计Rexp时,需要对结果进行矫正。矫正策略为
经验风险最小化
结构风险最小化
2.经验风险最小化与结构风险最小化
经验风险最小化 (empirical risk minimization ERM)
定义:经验风险最小的模型就是最优模型
极大似然估计(maximum likelihood estimation)是经验风险最小化的一个例子
当模型为条件概率分布,损失函数是对数损失函数时,经验风险最小化就等价于极大似然估计
结构风险最小化(structural risk minimization SRM)
为防止过拟合,在经验风险上增加表示模型复杂度的正则化项(regularizer)或罚项(penalty term)
贝叶斯估计中的最大后验概率估计(maximum posterior probability estimation MAP)就是结构风险最小化的一个例子
1.3.3 算法
经过上面“最小化”的过程,计算变为最优化问题。因此可以采用现有的各种最优化算法。
小结
统计学习首先要考虑的是学习什么样的模型---1.3.1模型
有了模型假设空间,接着要考虑的就是按照什么样的标准学习或选择最优模型 ---1.3.2 策略
最后考虑用什么样的计算方法求解最优模型 --- 1.3.3 算法
1.4 模型评估与模型选择
1.4.1 训练误差与测试误差
训练误差 training error
当模型Y=f(X)给定,损失函数给定时,关于训练集的损失函数
测试误差 test error
当模型Y=f(X)给定,损失函数给定时,关于测试集的损失函数
特例:当损失函数为0-1损失时,测试误差就是误差率 error rate
1.4.2 过拟合与模型选择
过拟合 over-fitting
当假设空间含有不同复杂度的模型时,就要面临模型选择(model selection)的问题。若一味追求低的训练误差,所选模型的复杂度往往会比真模型更高。这种情况称之为过拟合
模型选择
目的:防止过拟合的产生,选择复杂度适当的模型
模型选择方法
正则化
交叉验证
1.5 正则化与交叉验证
1.5.1 正则化 regularization
是结构风险最小化策略的实现(1.3.2-2)
举例:回归问题中,损失函数是平方损失,正则化项可以是参数向量的L2范数 或L1范数
正则化符合奥卡姆剃刀原理:简洁的是好的。
1.5.2 交叉验证 cross validation
如果给定样本数量足够大
将样本分为完全不同的三份,分别作为
训练集(training set)
用于训练模型
验证集(validation set)
用于模型选择
测试集(test set)
用于最终评估
如果样本数量不足
交叉验证分类
简单交叉验证
将数据分为训练集与测试集
S折交叉验证
随机将数据切分为S个互不相交的大小相同的子集,用S-1个子集做训练集,剩余的做测试集。将以上过程做S种选择重复进行,最后选出S次评价中测试误差最小的模型。
留一交叉验证
在S折交叉验证中,当S=N时(N为样本数量),称为留一交叉验证(每个数据集只有一个数据)
1.6 泛化能力
1.6.1 泛化误差
学习到的模型对未知数据预测的误差
显示中通过测试误差来评价泛化能力
公式和损失函数是一样的,只是将数据集换成了测试数据集
由于测试集的有限性,由测试集得到的评价是不可靠的
1.6.2 泛化误差上界
定义
泛化误差的概率上界的简称。 generalization error bound
通过比较两种学习方法的泛化误差上界的大小来比较它们的优劣。
性质
它是样本容量的函数
当样本容量增加时,泛化误差上届趋于0
它是假设空间容量的的函数
当假设空间容量增加时,模型就越难学习,泛化误差的上届就越大
定理
对于二类分类问题,当假设空间是有限个函数的集合时,有不等式成立。
其意义为:训练误差小的模型,其泛化误差也会小。
1.7 生成模型与判别模型
监督学习方法可以分为
生成方法 generative approach
据此学到的模型称为生成模型 generative model
根据训练集,学习联合概率分布P(X,Y),然后求出条件概率分布P(Y|X)作为预测模型
典型的生成模型有
朴素贝叶斯法
第四章
隐马尔可夫模型
第十章
特点
生成方法可以还原联合概率分布P(X,Y),判别方法不能。
生成方法的收敛速度快。
当存在隐变量时,仍可以使用生成方法学习
判别方法 discriminative approach
据此学到的模型称为判别模型 discriminative model
根据训练集,直接学习概率分布P(Y|X)或判别函数Y=f(X)作为预测的模型
典型的判别模型有
感知机
第二章
k临近法
第三章
决策树
第五章
逻辑斯蒂回归模型、最大熵模型
第六章
支持向量机
第七章
提升方法
第八章
条件随机场
第十一章
特点
学习准确率更高
可以对数据进行抽象,简化学习问题
1.8 分类问题
定义
分类问题
当输出变量Y的空间为有限个离散值时,称为分类问题
分类器 calssifier
监督学习从数据中学习一个分类模型或分类决策函数,称为分类器
分类 classification
分类器对新的数据进行预测,称为分类
类 class
分类器可能的输出,称为类。
评价分类器性能的指标
分类准确率 accuracy
对于给定的测试数据集,分类器正确分类的样本数与总样本数之比。
对于二分类问题
定义
TP
将正类预测为正类数
FN
将正类预测为负类数
FP
将负类预测为正类数
TN
将负类预测为负类数
常用评价指标是
精确率 precision
P = TP/(TP+FP)
召回率 recall
P = TP/(TP+FN)
F1值
F1 = 2TP/(2TP + FP +FN)
1.9 标注问题
定义
标注 tagging
学习一个模型,使它能够对观测序列给出标记序列作为预测。
常用方法
隐马尔可夫模型
条件随机场
应用范围
自然语言处理
信息抽取
1.10 回归问题
定义
输入与输出均为连续变量的的预测问题称为回归问题
分类
按照输入变量的个数,可以分为
一元回归
多元回归
按照输入与输出的映射关系,可以分为
线性回归
非线性回归
损失函数
最常用平方损失函数
此情况下,可用最小二乘法解决
第二章 感知机
导言
感知机是二类分类的线性分类模型
感知机是判别模型
2.1 感知机模型
定义
由输入空间到输出空间的函数 f(x)=sign(w*x+b) 称为感知机
w∈R 是权重 weight 或权重向量 weight vector
b∈R 是偏移 bias
解释
超平面分割
2.2 感知机学习策略
2.2.1 数据集的线性可分性
定义
对于给定数据集T,如果存在超平面S能够将T的正实例点与负实例点完全正确地划分到超平面的两侧,则称数据集T是线性可分数据集 linearly spearable data set
反之,称T为线性不可分
2.2.2 感知机学习策略
假设数据集线性可分
定义损失函数
自然选择是误分类点的数量,但是此值不是参数w和b的可导函数,不易优化
选择误分类点到超平面的总距离作为损失函数,为令损失函数>0,引入y值
练习:证明超平面外一点到超平面的距离公式
2.3 感知机学习算法
2.3.1 原始形式
欲令损失函数最小,采用随机梯度下降法 stochastic gradient descent
步骤
任意选取一个超平面 w0,b0
在训练集中选择数据(xi,yi)
如果yi(w*xi+b)<0,意味着分类错误
偏微分求导,可以定出梯度方向,使用学习率η作为梯度参数,对w和b进行更新
w += η * yi * xi
b += η * yi
转到第二步,直至所有数据被正确分类
因为超平面的不唯一性,当使用数据的顺序不同时,得出的超平面结果也是不一致的。
与第七章支持向量机的原始形式对应
2.3.2 算法的收敛性
定义
对于线性可分的数据集,经过有限次迭代可以得到一个将训练集正确划分的超平面
证明
看不懂
2.3.3 对偶形式
将w和b表示为实例xi和标记yi的线性组合形式,通过求解其系数而求的w和b
当w和b的初始值为0时,对误分类点(xi,yi)通过梯度下降逐步修改,设修改了n次
w = w0+ η * yi * xi
w = ∑ αi * yi * xi, αi = ni * η
ni表示为样本点(xi,yi)在更新过程中使用的次数
b = b+ η * yi
b = ∑ αi * yi, αi = ni * η
感知机模型 f(x)=sign( (∑ αi * yi * xi ) * x + b )
因为η是固定值,因此此时参数αi其实代表的是这个样本的使用次数
对偶形式本质上是学习ni,而非w
步骤
初始值 α=0, b=0
在训练集中选取(xi,yi)
如果 f(xi) * yi < 0
αi += η
b+= η * yi
转至第二步直到没有误分类函数
将α转换为w,得出超平面参数 w和b
简化
在感知机模型f(x)=sign( (∑ αi * yi * xi ) * x + b )中,训练数据集仅以内积的形式出现
为了计算方便可以预先计算样本的内积矩阵
Gram矩阵
与第七章支持向量机的对偶形式对应
问题:对偶形式的运算复杂度更低么
第三章 k近邻法
3.1 k近邻算法
3.2 k近邻模型
3.2.1 模型
单元 cell
对每个实例点,距离该点比其他点更近的所有点组成一个区域,叫做单元
推论:单元是互斥且完备的
类标记 class label
实例x的类y作为其单元所有点的类标记
3.2.2 距离度量
范数距离
3.2.3 k值的选择
k=1
最近邻法
1 < k << N
复杂度高,容易过拟合
1 << k <N
复杂度低,不精确
k= N
只有一种分类,就是样本中出现次数最多的分类
最优选择
交叉验证法
问题:没有具体说明
3.2.4 分类决策规则
多数表决 majority voting rule
在0-1损失函数下,经验风险最小等价于多数表决
3.3 k近邻法的实现
kd树 kd tree
3.3.1 构造(平衡)kd树
中位数:一组数据按大小排序,处在最中间位置的一个数或者两个数的平均值
依次选取坐标轴对空间切分,选择训练点在选定坐标轴上的中位数为切分点,小于此值的样本分到左节点,否则分到右节点
生成结果是一个二叉树
搜索效率低
3.3.2 搜索kd树
最近邻搜索
1.找到包含目标点的叶节点
从根节点出发,逐步向下访问每个节点,当测试数据X当前维的坐标小于节点的坐标,向左移动,否则向右移动,直至叶节点。
2.以此叶节点作为“当前最近点”
3. 递归向上回退,在每个节点进行以下操作
1. 如果该节点保存的实例比当前最近点距离目标点更近,则以该实例点为“当前最近点”
2. 当前最近点一定存在于该节点的一个子节点对应的区域。检查该子节点的父节点的另一子节点对应的与去是否有更近的点。
如果有,搜索更近点
如果没有,向上回退
4 当回退到根节点时,搜索结束。
k近邻搜索
在上例的基础上存储一个距离数列即可。
问题:非平衡kd树的构造方法?
最好是直接查一次树就可以找到最近邻,回退即为次近邻
凝聚层次聚类算法是否满足要求?
问题:还有其他方法么
第四章 朴素贝叶斯
导言
naive Bayes 是基于贝叶斯定理与独立条件假设的分类方法
naive Bayes 与 贝叶斯估计 Bayesianestimation 是不同的概念
4.1 朴素贝叶斯法的学习与分类
4.1.1 基本方法
样本输出记为 类标记 class label
输出空间为类标记集合
假设:样本数据集由联合概率P(X,Y)独立同分布产生
其他算法是否有此假设
朴素贝叶斯法 通过训练数据学习联合概率分布P(X,Y)
学习先验概率 P(Y=Ck)
学习条件概率分布 P(X=x|Y=Ck)
实际上,因为条件概率有指数级数量,因此直接估计是不可行的
为此引入条件独立性假设,简化计算量
没看懂为啥不可行,引入独立性假设后,运算量并没有减少啊?
得到后验概率分布P(Y|X) ,用于预测
朴素贝叶斯法实际上学习到生成数据的机制,所以属于生成模型
条件独立性假设
等价于: 用于分类的特征在类确定的条件下,都是相互独立的
公式
这一假设使简化了算法,
简化了条件概率的求解方式
牺牲了分类准确性
将条件独立性假设的公式带入贝叶斯定理公式可以得到朴素贝叶斯法的公式
4.1.2 后验概率最大化的含义
=期望风险最小化(风险函数为0-1函数)
4.2 朴素贝叶斯法的参数估计
4.2.1 极大似然估计
在朴素贝叶斯法中,学习意味着估计先验概率和条件爱你概率
最极大似然估计先验概率和条件概率
证明:和第一章的习题是完全一样的
4.2.2 学习与分类算法
步骤
1. 计算先验概率和条件概率
2. 计算实例对应各分类的后验概率
3.取最大后验概率值所对应的分类为输出
4.2.3 贝叶斯估计
当极大似然估计的先验值或条件概率为0时,会影响后验概率
什么情况下为0?为什么会影响后验概率,影响有多大?
为此在分子分母分别增加参数λ
λ=0 极大似然法
λ=1 拉普拉斯平滑 Laplace smoothing
为什么加入参数 λ 就可以避免影响?
第五章 决策树
导言
决策树的优点
可读性
分类速度快
学习步骤
特征选择
决策树的生成
决策树的修剪
5.1 决策树模型与学习
5.1.1 决策树模型
决策树 decision tree
结点 node
内部节点 internal node
叶节点 leaf node
有向边 directed edge
5.1.2 决策树与if-then规则
重要性质:互斥且完备
有且仅有一条规则覆盖每个实例
5.1.3 决策树与条件概率分布
决策树表示了给定特征条件下类的条件概率分布
这一条件概率分布定义在特征空间的一个划分partition上
将特征空间划分为互不相交的单元 cell 或 区域 regoin, 并为每个单元定义一个类的概率分布就构成了一个条件概率分布
5.1.5 决策树学习
损失函数
正则化的极大似然函数
策略是最小化损失函数
遍历所有决策树是NP问题,因此采用启发式方式
得到次优解
过拟合
减枝
常用算法
ID3
C4.5
CART
注意:与k近邻法的 kd tree 相比,决策树不一定是二叉树
5.2 特征选择
5.2.1特征选择问题
如果利用一个特征进行分类的结果与随机分类的结果没有很大差别,则称这个特征是没有分类能力的。
特征选择的准则:信息增益或信息增益比
5.2.2 信息增益
令 0*log0=0
熵 entropy H(X)
在信息论和概率统计中,熵表示随机变量不确定性的度量
定义 与 值图
当此值由数据估计(特别是极大似然估计)得到时,称为经验熵 empirical entropy
熵与方差的关系?方差的取值与熵的取值是正向关系,为什么有了方差还要提出熵的概念?
条件熵 conditional entropy H(Y|X)
条件熵表示在已知随机变量X的条件下随机变量Y的不确定性
定义
当此值由数据估计(特别是极大似然估计)得到时,称为经验条件熵 empirical conditional entropy
信息增益 information gain
表示得知特征X的信息而使类Y的信息的不确定性减少的程度
定义
特征A对训练数据集D的信息增益 g(D,A), 定义为集合D的经验熵 H(D) 与特征A给定条件下D的经验熵H(D|A)之差
一般的,熵与条件熵之差称为互信息 mutual information
5.2.3 信息增益比
问题
以信息增益作为划分训练数据集的特征,存在偏向于选择取值较多的特征的问题。
以信息增益比作为特征值可以对此问题进行校正
定义
特征A对训练数据集D的信息增益比 gR(D,A), 定义为其信息增益g(D,A)与训练数据集D关于特征A的值的熵之比
5.3 决策树的生成
5.3.1 ID3 算法
核心
在决策树的各个结点上应用信息增益准则选择特征,递归地构建决策树。
具体方法
从根节点开始,对结点计算所有可能的特征的信息增益,选择信息增益最大的特征作为结点的特征,由该特征的不同取值建立子结点;再对子结点递归的调用以上方法,直到所有特征值的信息增益均很小或没有特征可以选择为止
ID3 相当于用极大似然法进行概率模型的选择
5.3.2 C4.5 算法
用信息增益比选择特征,其他部分与ID3相同
5.4 决策树的减枝
问题
以上算法产生的决策树对样本数据分类准确,对测试数据的分类不够准确,即过拟合
过拟合产生的原因在与学习时过多的考虑了训练数据,构建出过于复杂的决策树
解决此问题的方法就是简化决策树
减枝 pruning
标准
极小化决策树整体的损失函数或代价函数
损失函数
定义
复杂度= α * |T|
用叶节点的数量 |T| 来代表复杂度
参数 α>=0 控制复杂度的影响
如何取alpha值?
损失函数的极小化等价于正则化的极大似然估计
步骤
5.5 CART算法
导言
Classification and Regression Tree 看名字就知道可以用于分类和回归
二叉树,左侧是,右侧否
同样有生成和减枝的过程
5.5.1 CART生成
1.回归树的生成
特征选择
假设已经将输入空间(特征空间)划分为M个单元{R1...RM},并且在每个单元Rm上有一个固定的输出Cm
使用平方函数作为回归树对于训练数据的经验损失
那么当单元Rm上的输出Cm是Rm内所有实例xi对应输出yi的平均值时,经验损失最小
启发式算法
思路:选择第j个变量xj和它取值s,作为切分变量 splitting variable和切分点 splitting point
R-left = { x | xj <= s }
R-right = { x | xj > s }
具体:遍历所有变量,求解最优切分点,依次构建归回树
求解最优切分点不需要求导,只要遍历每个xi即可
有一种强行将连续问题转变为离散问题求解的感觉
这样生成的回归树通常称为 最小回归二叉树 least squares regression tree
2.分类树的生成
特征选择
基尼指数 Gini coefficient
在分类问题中,假设有K个类,样本点属于第k类的概率为pk, 则基尼指数定义为
Gini(p)=∑pk(1-pk)=1-∑pk^2
由定义可知 0< Gini(p)<1
对集合D而言,基尼指数Gini(D)表示集合D的不确定性
基尼指数Gini(D,A) 表示经A=a分割后集合D的不确定性
没错,它也是经济学中衡量一个国家或地区居民收入差距的常用指标,介于0-1之间,基尼系数越大,表示不平等程度越高。
基尼指数、半熵和分类误差率的关系
曲线图接近
但是没有说明为什么要采用些这奇怪的特征(没有提及它们之间的区别)
算法
对样本集中每一个特征A,对其每个可能取值a,计算基尼指数
在以上结构中选择基尼指数最小的 { A, a },根据A=a或A!=a分为左右两个结点
注意是基尼系数最小!和之前信息增益区别,信息增益是减去熵值的,也就是熵值最小
重复以上步骤直至满足结束条件
5.5.2 CART减枝
1.减枝,形成一个子树序列
2. 在减枝的子树序列中通过交叉验证选择最优子树
第六章 逻辑回归与最大熵模型
导言
逻辑回归 logistic regression
最大熵模型 maximum entropy model
都是对数线性模型
6.1 逻辑回归模型
6.1.1 逻辑分布 logistic distribution
逻辑分布定义
随机变量X服从逻辑分布是指X具有
分布函数 F(x)
是逻辑函数
密度函数 f(x)
逻辑函数定义
logistic function
是Sigmoid函数的一种
6.1.2 二项逻辑回归模型
定义
是条件概率分布
特点
先引入定义
一个事件的几率 odds
定义为该事件发生的概率与该事件不发生的概率之比 p/(1-p)
对数几率 log odds
定义为几率的对数 log( p/(1-p) )
二项逻辑回归模型中,Y=1的对数几率是输入x的线性函数
6.1.3 模型参数估计
对于给定训练集,可以用极大似然法估计参数模型
对对数似然函数求极大值,通常参采用梯度下降和拟牛顿法
6.1.4 多项逻辑回归
定义 multi-nominal logistic regression model
二项逻辑回归的参数估计法也推广到多项逻辑回归
6.2 最大熵模型
导言
最大熵模型由最大熵原理推导实现
6.2.1 最大熵原理
最大熵原理认为,学习概率模型时,在所有可能的概率模型(分布)中,熵最大的模型是最好的模型
此处与5.2.2 最大信息增益是否冲突?
最大熵原理也可以表述为,在满足约束条件的模型集合中选取熵最大的模型。
设离散变量X的概率分布为P(X)
其熵H(P)=-∑P(x)logP(x)
熵满足不等式 0<=H(P)<=log|X|。 |X|是X的取值个数
当且仅当 X为均匀分布时右侧等号成立
几何解释
完全不懂
6.2.2 最大熵模型的定义
6.3 模型学习的最优化算法
6.3.1 改进的迭代尺度法
6.3.2 拟牛顿法
第七章 支持向量机 SVM
Support Vector Machines
Support Vector Machines
导言
7.1 线性可分支持向量机与硬间隔最大化
7.2 线性可分支持向量机与软间隔最大化
7.3 非线性支持向量机与核函数
7.4 序列最小最优化算法
附录 A 梯度下降法
描述
梯度下降法 gradient descent 或最速下降法 steepest descent 是求解无约束最优化问题的一种最常用的方法
优点是实现简单
条件
f(x) 是具有一阶连续偏导数的函数
过程描述
x取任意初值
求f(x)导数,并令x向负导数方向移动。
直到f(x)导数足够小时结束
问题
当目标函数是凸函数时,梯度下降法的解是全局最优解
速度未必很快
附录B 牛顿法和拟牛顿法
描述
牛顿法 Newton method 和拟牛顿法 quasi Newton method 也是求解无约束最优化问题的方法
优点是收敛速度快
1. 牛顿法
前置知识点
泰勒展开
定义
泰勒公式是将一个在x=x0处具有n阶导数的函数f(x)利用关于(x-x0)的n次多项式来逼近函数的方法。
海塞矩阵 Hesse matrix
定义
又译作海森矩阵、海瑟矩阵、海塞矩阵等
是一个多元函数的二阶偏导数构成的方阵,描述了函数的局部曲率。
海塞矩阵常用于牛顿法解决优化问题,利用海塞矩阵可判定多元函数的极值问题。
正定矩阵
定义
设M是n阶方阵,如果对任何非零向量z,都有zTMz> 0,其中zT 表示z的转置,就称M正定矩阵。
性质
正定矩阵的行列式恒为正
若A是正定矩阵,则A的逆矩阵也是正定矩阵
两个正定矩阵的和是正定矩阵
正实数与正定矩阵的乘积是正定矩阵
牛顿法
定义:推荐看wiki百科的解释,比书上要清楚很多,国内大部分网页推导都是错误的
https://zh.wikipedia.org/wiki/%E6%87%89%E7%94%A8%E6%96%BC%E6%9C%80%E5%84%AA%E5%8C%96%E7%9A%84%E7%89%9B%E9%A0%93%E6%B3%95
注意我们用到的是高阶情况
wiki概念相关知识点
驻点
函数的一阶导数为0的点(驻点也称为稳定点,临界点)。对于多元函数,驻点是所有一阶偏导数都为零的点。
与极值点的关系:驻点不一定是极值点,极值点也不一定是驻点
2. 拟牛顿法
3. DFP算法
4.BFGS算法
5.Broyden算法
附录C 拉格朗日对偶性
导言
通过拉格朗日对偶性将原始问题转为对偶问题,通过解对偶问题求得原始问题的解
1.原始问题
转变为极小极大值问题
2.对偶问题
极大极小值问题
3.原始问题和对偶问题的关系
定理1
若原始问题与对偶问题都有最优解,则对偶问题最优解的值小于等于原始问题最优解的值
推论1
若存在可行解使得原始问题与对偶问题值相同,则可行解为最优解。
定理2
满足一定条件的情况下有解,且原始问题与对偶问题的值相同
定理3
KKT条件
???
0 条评论
下一页