当前课程知识点:运筹学 > 6. 图与⽹络分析 > 6.7 指派问题 > 课程学习方法2
现在问题又来了
你要达到我们说的这个过程的话
你怎么样来做这件事呢
实际上
基本的方法我们就要选择一个
含有待定参数的一个函数
我们就管它叫f ^x
这个X是我们
对应的样本的自变量
那再加上一个θ
这个θ就是我们说的待定参数
通过调整这个待定参数θ
就可以使得
这个函数的形态发生一些变化
这个基本是可用的方法
因为你不能说在整个的这个
函数空间里去找
这个函数空间
你们学过数学分析的知道
有对无穷的度量阿列夫(ℵ)
这个大的就不可能的
你连在这个数轴去找都找不到
更何况这函数空间是ℵ
对应的是ℵ2的话
这么大的空间去找是不太可能的事情
但是
我有了一个对应的一个θ
参数去调整的时候
就会使得
对应的这个函数里面
会得到一个可以
达到我们预想效果的函数
这里我举一个例子
大家一定学过像这种
通过调整参数
来达到逼近程度
这个大家现在接触非常多了
比如说现在
这个能力很强的
深度神经网络
包括支持向量机等等
它都是通过调整参数
里面的用的一些
后面会看到的基函数的方式
来通过不同参数的调整 使函数形态
发生了一些变化
甚至更古老一点
大家可以知道
比如说傅里叶变换
咱们对应的傅里叶级数也是一样的情况
通过一系列的三角函数
通过前面它的对应的取值的变化
它们之间的求和之后
也会改变最后目标函数
对应的函数拟合的形态
甚至其实可以用三角函数
来拟合方波这样
对应的函数出来的
那么在这个过程中的时候
我们要极小化这种误差
对误差的度量也会有对应的要求
那么我们常用的就是这个
p范数的方式
这个p可以取任意的方式
常用的有几种
比如说1范数的时候
那么它所度量的就是
每一个样本里面
对应我预测的这个
和y值之间对应的这个绝对值的
这个对应的情况 然后
对所有的样本求和
这是p1范数
2范数大家更熟了
这个对应的就是这个平方
然后
它这个2范数跟我们
整个这个空间里面的距离的
(在直觉上)最接近的
当然还可以求无穷范数
也就在所有的误差里面
最大的那个误差
把它单独挑出来
这都可以作为一个
还有其它的分数范数都可以
这个都可以做选择的
就可以作为
我们说刚才说过的
在样本上误差的一个度量方式
那有了它之后
那么所有的刚才说过的
问题归属
就变成这样一个问题
最终要解决的
大家可以看到
这个θ就是我们对应的
咱们改变 具有待定参数的
这个函数f ^X这个参数里面
这个θ的取值
它实际上来说是没有任何约束的
就它怎么取都行
这个没有给它加上约束条件
然后通过改变普通的θ
就可以使得这个函数的形态
可以发生变化
使得在所有的样本上
跟我预报的y值之间的对应的
p范数的
这个衡量的误差达到最小化
可以看到这么一个过程
大家可以看到这个对应的公式
那么这个实际上本质来说是
求解什么一个问题
就是连续变量的一个
无约束的优化问题
大家可以看到这里面
没有其他的任何的约束条件
无约束
什么叫约束条件
我们后面在马上要进入到的
线性规划规划里面
也会给出严格的定义
现在大家可以广泛地
理解一下它这个含义
那么对应来说
由于对样本误差的
度量的方式不同 大家可以看到
这里会存在一些比较复杂的情况
比如说这里就有平方项了
那肯定会存在一些非线性的一些情况
在里面或者更一般的情况
好 这是第一种情况
我们看到这个
就是我们解决
一个实际问题里面
所带来的
数学上或者用这个数学公式
来表示的一个实实在在的
需要求解的一个规划问题
但是光做到这点是不够的
那么实际来说的话往往
比如说我举个例子
比如说我们用无穷范数
来描述这个优化问题
那么这个时候大家可以看到
也就是说 在N个样本里面
我要找到
就是这个采样里面的N个样本里面的
跟我这个对应的
这个y值就是这个
样本里面值
最大的那个值里面的
让它最小化
最大的那个都最小化了
这也是一个对应的这个范数
但是衡量这个值要保证
它一定是绝对值
这种这个无穷范数在去
做度量的时候
那么这个优化目标带来一个
比较大的问题
这个问题是什么
跟咱们
上一节里面的一般性方法
带来问题是一样的
就是这个目标函数式的求导是很麻烦的
那为什么求导麻烦
就引出一个 值得我们关注的问题
因为什么 因为这个刚才说过了
咱们求解问题的一般性思路是什么
是找方向
沿着方向去做
这个搜索找到一个步长
那么求导
如果不容易去求
那我们对这个问题来说
我就不太容易找到哪个方向
才是使得我们目标函数进一步改善
但是这个问题
居然很特殊
特殊到什么程度
它可以做为一个简化
不叫简化...一个转化
一定记住这个词“转化”
这个“转化”
就用到了
我们刚才说过的
如果你知道一些
对应运筹学的模型的知识的时候
这种转化变得很重要
你看 它和下面这个问题
为了克服目标函数不可导的困难
转化成下面这么一个连续变量
有约束的一个优化问题
然后怎么叫连续变量 大家看
这个里面就是 对于
在这个N个样本中
我所有的
跟我这个目标函数的
对应的目标函数
要求的估计出的函数
跟我们实际的这个值之间的误差
为了使这个绝对值去掉之后
我们知道它一定最后下来
它要么≥-λ ≤λ
它是有边界的
负的边界也好
正的边界也好
但是不管怎么样
在这个所有边界里面
所有最大的那个边界里面
我仍然让它最小化
也就说我把它
对应这个边界限制是λ之后
我让它做λ最小
这个问题和上面这个问题
实际上大家可以看到它是完全等价的
一个问题
那你为什么要把它化成这个问题
这个问题化完之后最大的好处在哪
我们马上再来 就说
特别是当我们把这个
要估计的这个有参数的f(X)
和这个参数θ之间
表示成线性函数的时候
什么是线性函数 就是我把f(X)
是可以写成这个φ
这个φ是一种基函数
它的线性组合
这种我们叫可加性模型
这个太多了
比如说咱们现在可以看到
绝大多数用的神经网络里面
包括支持向量机里面
它的形式都是这种形式
那么这里面
比如说φ我们熟悉的
比如说在别的课堂
你遇到过我们用高斯核函数
那么下来
每个高斯核函数之间的线性组合
那当然这里我用到多少高斯核函数之后
就可以得到我们对应的一个期望的
拟合的一个f(X)出来
那么写成是这个决策变量θ
就是这个待定函数θ
这个线性函数的时候
大家再重新看一下
我们这个有约束的连续变量优化问题
这里面
对这个θ来说
它的约束条件是线性的
目标函数值
当然也是线性的
所以
这个问题就转化成一个 这个优化问题
就变成一个线性规划问题
这个转化的意义可就大了
这个非常大了
因为你可以看到
当我们采用这个
无穷范数来去刻画这个优化问题的时候
带来所谓的不可导的一个困难
但是因为我们有了线性规划对应的知识
我们把它转化成
等效的线性规划模型的时候
这个问题的求解就变得极其容易
我们在后面的线规划的课程里面
会给大家介绍对应求解这样
线性规划问题的一个一般性的方法
就是单纯形法
这个方法的效率非常高
当然还存在它理论上的一些问题
这都是后话
我们慢慢的给大家就讲
那是高到什么程度呢
就是如果真是客观中这样的一个问题
我们转换完之后
哪怕这个问题里面
你选择这个基函数的数量哪怕是
成百上千甚至以十万级做这个做计量的
这个问题
那么转化成线性规划之后
它的求解速度用我们现在这个
计算机的效率
也在一秒钟之内可能就能完成
所以效率是非常高的
所以可以看到
就是因为有这样的知识
有了对应的我们
线性规划这样的模型特点
以及对应求解的高效算法
我们是可以把
实际里面用无穷范数去表示
这种优化问题不好解决的问题
也可以很好的解决掉
-作业-绪论
-2.1 ⼀般模型和标准模型
--作业-线性规划模型
-2.2 低维问题图解法及其向⾼维的推⼴
--作业-低维问题的图解法
--2.2.5 凸集
--作业-高维问题及其性质
-2.3 单纯形算法
--作业-单纯形算法1
--作业-单纯形算法2
--作业-单纯形算法3
-2.4 对偶性与对偶算法
--作业-对偶性与对偶算法1
--作业-对偶性与对偶算法2
-2.5 灵敏度分析
-3.1 整数线性规划的数学模型
--整数线性规划概述
--作业-整数规划概述
-3.2 割平⾯法
--作业-割平面法
-3.3 分枝定界法
--作业-分枝定界法
-3.4 0-1变量的作⽤
--作业-0-1变量的作用
-4.1 动态规划基本概念
-4.2 最优性原理
-4.3 建模与求解
-4.4 典型应⽤问题
-4.5 不定期动态规划问题
-作业-动态规划
-5.1 基础知识
--作业-非线性规划基础知识
-5.2 ⼀维搜索
--作业-一维搜索
-5.3 ⽆约束优化
--作业-无约束优化
-5.4 约束优化
--作业-约束优化
-5.5 简约梯度法
--简约梯度法
-5.6 拉格朗⽇对偶
--拉格朗日对偶
-6.1 基础知识
--作业-图与网络基础知识
-6.2 最⼩⽀撑树问题
--作业-最小支撑树问题
-6.3 最短路问题
--作业-最短路问题
-6.4 最⼤流问题
--作业-最大流问题
-6.5 最⼩费⽤流问题
--作业-最小费用流问题
-6.6 运输问题
--作业-运输问题
-6.7 指派问题
--作业-指派问题