48/85
附： Bellman-ford算法
49/85
附： Bellman-ford算法分析
图的任意一条最短路径既不能包含负权回路，也不会包含正权 回路，因此它最多包含|v|-1条边。 从源点s可达的所有顶点如果存在最短路径，则这些最短路径构 成一个以s为根的最短路径树。Bellman-Ford算法的迭代松弛操 作，实际上就是按顶点距离s的层次，逐层生成这棵最短路径树 的过程。 在对每条边进行第1遍松弛的时候，生成了从s出发，层次至多 为1的那些树枝。也就是说，找到了与s至多有1条边相联的那些 顶点的最短路径；对每条边进行第2遍松弛的时候，生成了第2 层次的树枝，就是说找到了经过2条边相连的那些顶点的最短路 径。因为最短路径最多只包含|v|-1条边，所以，只需要循环|v|-1 次。 略做优化：如果第k次松弛操作后，最短路径没有得到更新，显 然，后面仍然无法得到更新，可提前退出。并且，如果k<n-1， 一定不存在负环。
66/85
指数分布的无记忆性
指数函数的一个重要特征是无记忆性（遗失 记忆性，Memoryless Property）。
如果一个随机变量呈指数分布，当s,t≥0时有 P(T>s+t|T>t)=P(T>s)。即，如果T是某一元件的 寿命，已知元件使用了t小时，它总共使用至少 s+t小时的条件概率，与从开始使用时算起它使 用至少s小时的概率相等。
50/85
对偶问题
一般优化问题的Lagrange乘子法
Lagrange函数
对固定的x，Lagrange函数L(x,λ,v)为关于λ和v的 仿射函数
51/85
Lagrange对偶函数(dual function)
Lagrange对偶函数
若没有下确界，定义：
根据定义，显然有：对∀λ>0，∀v，若原优化问题 有最优值p*，则 进一步：Lagrange对偶函数为凹函数。
所有可行点的集合
最优化值
最优化解
34/85
局部最优问题
35/85
优化问题的等价问题
若 则原优化问题与以下优化问题等价
36/85
优化问题的等价问题
设函数φ是一一对应 且 则原优化问题与以下优化问题等价
37/85
优化问题的等价问题
设ψ0为严格单调递增函数 ψ1,… ,ψm满足 当且仅当u≤0 ω1,…,ωp满足 当且仅当u = 0 则原优化问题与以下优化问题等价
52/85
线性方程的最小二乘问题
原问题
Lagrange函数 Lagrange对偶函数
对L求x的偏导，带入L 对g求v的偏导
关于该问题，在支持向量机中将继续探讨
53/85
概率论
对概率的认识：P∈[0,1]
P=0
事件出现的概率为0→事件不会发生？
将位于[0,1]的函数y=f(x)看成x对应y事件的概率
如：Bernoulli分布和高斯分布
75/85
Bernoulli分布属于指数族
76/85
强调
注意在推导过程中，出现了Logistic方程！
77/85
Gaussian分布也属于指数族分布
78/85
统计参数
均值（期望，一阶） 方差（二阶） 变异系数(Coefficient of Variation)

也被称为超值峰度（excess kurtosis）。
“减3”是为了让正态分布的峰度为0。
P(Y|θ)=Π πpyi(1-p)1-yi+ (1-π)qyi(1-q)1-yi
3/85
本次目标
概率论中，掌握各种分布的性质 了解指数族分布 引出充分统计量和广义线性模型GLM的概念 了解凸集和凸优化的一般过程和概念
4/85
理解“凸优化”的四个步骤
凸集 凸函数 凸优化 对偶问题
标准差与平均数的比值称为变异系数，记为C· V
偏度Skew（三阶） 峰度Kurtosis（四阶）
79/85
偏度
在机率论和统计学中，偏度衡量实数随机变量概率 分布的不对称性。偏度的值可以为正，可以为负或 者甚至是无法定义。在数量上，偏度为负（负偏态） 就意味着在概率密度函数左侧的尾部比右侧的长， 绝大多数的值（包括中位数在内）位于平均值的右 侧。偏度为正（正偏态）就意味着在概率密度函数 右侧的尾部比左侧的长，绝大多数的值（包括中位 数在内）位于平均值的左侧。偏度为零就表示数值 相对均匀地分布在平均值的两侧，但不一定意味着 其为对称分布。
27/85
一阶可微
若函数f的定义域domf为开集，且函数f一阶 可微，则函数f为凸函数当前仅当dom为凸集， 且
如何证明？
考察割线
28/85
二阶可微
若函数f的定义域domf为开集，且函数f二阶 可微，则函数f为凸函数当前仅当dom为凸集， 且
29/85
凸函数举例
30/85
保持函数凸性的算子
38/85
优化问题的等价问题
原优化问题与以下优化问题等价
s：松弛变量
39/85
优化问题的等价问题
设 满足等式 , j=1，…p 成立，当且仅当 则原优化问题与以下优化问题等价
40/85
优化问题的等价问题
原优化问题与以下优化问题等价
41/85
凸优化问题的基本形式
பைடு நூலகம்
特殊情况：非约束凸优化问题中，f0(x)可微。 则x*为最优解当且仅当下式成立。
44/85
凸优化问题的等价形式
如何凸优化问题仅有等式约束
则x为最优解当且仅当x∈X，且存在向量v满 足
Lagrange乘子法
45/85
凸优化问题的等价形式
凸优化问题
等价于
其中
46/85
凸优化问题的等价形式
其中，fi(x)为凸函数，hj(x)为仿射函数 凸优化问题的重要性质 1、凸优化问题的可行域为凸集 2、凸优化问题的局部最优解即为全局最优解
思考：为什么？
42/85
例
43/85
凸优化问题最优解的微分条件
定理：设X为凸优化问题的可行域，f0(x)可 微。则x为最优解当且仅当下式成立。
如何解释？
62/85
泊松分布
63/85
均匀分布
64/85
指数分布
65/85
指数分布
其中λ > 0是分布的一个参数，常被称为率参数（rate parameter）。即每单位时间内发生某事件的次数。指数分布的 区间是[0,∞)。 如果一个随机变量X呈指数分布，则可以写作： X~ Exponential（λ）。 指数分布可以用来表示独立随机事件发生的时间间隔，比如旅 客进机场的时间间隔、软件更新的时间间隔等等。 许多电子产品的寿命分布一般服从指数分布。有的系统的寿命 分布也可用指数分布来近似。它在可靠性研究中是最常用的一 种分布形式。
重点：用凸优化的思想解释最小二乘问题 为支持向量机SVM提供理论保证
5/85
仿射集(Affine set)
直线
y=θx1 + (1-θ)x2, θ∈R
线段
y=θx1 + (1-θ)x2, θ∈[0,1]
定义：过集合C内任意两点的直线均在集合 C内，则称集合C为仿射集。 仿射集的例子：直线、平面、超平面
古典概型
排列组合
概率密度函数Probability Density Function 累计分布函数
54/85
分布
复习各种常见分布本身的统计量 在复习各种分布的同时，重温积分、Taylor 展式等前序知识 常见分布是可以完美统一为一类分布的
55/85
两点分布
56/85
二项分布 Bernoulli distribution
超平面：Ax=b
6/85
仿射包
仿射包：包含集合C的最小仿射集。
仿射维数：仿射包的维数。
三角形的仿射维数为2 线段的仿射维数为1 球的仿射维数为3
7/85
仿射包
8/85
凸集
集合C内任意两点间的线段均在集合C内， 则称集合C为凸集。
9/85
仿射集和凸集的关系
因为仿射集的条件比凸集的条件强，所以， 仿射集必然是凸集。
凸优化与概率初步
邹博
2014年10月19日
历史遗留问题
Ax的偏导
跳表查询时间复杂度下限
f (k ) k N
1 k 1 k
1 k
1 f ' (k ) N k N ln N 2 k
EM中参数θ是未知的确定量
2/85
EM的推导
将观测变量记做Y，待估计参数记做θ(π，p， q) P(y|θ)=Σz P(y,z|θ)= ΣzP(z|θ)P(y|z, θ) =P(z=0|θ)P(y|z=0, θ)+P(z=1|θ)P(y|z=1, θ) =πpy(1-p)1-y+ (1-π)qy(1-q)1-y 应用极大似然估计
25/85
支撑超平面
设集合C，x0为C边界上的点。若存在a≠0， 满足对任意x∈C，都有 成立，则称 超平面 为集合C在点x0处的支 撑超平面。 凸集边界上任意一点，均存在支撑超平面。 若一个闭的非中空集合，在边界上的任意一 点存在支撑超平面，则该集合为凸集。
26/85
凸函数
若函数f的定义域domf为凸集，且满足
凸优化问题
等价于
还记得s的称谓吗？
带负权的有向图求给定两点间的最短路径
47/85
附：带负权的最短路径Bellman-ford算法