优化与对偶理论笔记

来源：知乎专栏文章迁移涵盖内容：线性规划对偶理论、鞅论初步、数值最优化与KKT条件

这是一边看 mujica 同人一边写的对偶理论笔记，大部分内容来自于文再文老师的《最优化：建模、算法与理论》、周志华《机器学习》以及各类参考资料。

线性规划与对偶问题

首先介绍线性规划的例子，引入拉格朗日对偶函数与对偶问题

对偶函数在这个情境下有什么具体的含义,介绍影子价格等具体的意义,引入对偶函数有什么用

其次,讨论对偶问题与原问题之间的关系

接着，介绍线性规划问题的强对偶性,介绍互补松弛条件

1例子:线性规划

例子1，带约束的线性规划问题: min cTxs.t.Ax=bx≥0

这对应了一个实际生产之中的情景，A表示加工某种产品所需要的物资分配情况，而x表示所需要购买的原材料量，b表示实际的生产需要，c则表示原材料的成本。在销售量已经确定的情况下，所能够优化的只有成本，这就是一个带约束条件的线性规划问题。

当然原问题不一定是可以求解的,例如

min x_1

x_1=-1

x_1\ge0

明显原问题没有可行点,此时也就没有什么讨论的必要了.在接下来的情境下,都是讨论解可行且有限的情况

这种带约束的线性规划问题，我们想到将约束整合进入原函数，这就是当年对偶问题的提出者所干的那件事：

他构造了一个拉格朗日函数，将问题转化为了： L(x,s,v)=cTx+vT(Ax−b)−sTx

然后，按照优化的固有思路，考虑将拉格朗日关于x极小化，然后，我们就得到了只与u,v相关的一个对偶函数：

g(u,v)=infxL(x,u,v)=inf(−bTv+(ATv−s+c)Tx)

推到这一步，因此只要 ATv−s+c 这个向量不为零，那么就总能找到x使得这一项趋近于负无穷。

而此向量为零时，能用最小值 −bTv

因此,就得到了一个线性规划问题的对偶问题:

首先，对偶问题往往具有更好的形式，这是一个定性的描述，很难说一个问题怎么就“变好”了。我们首先举出哪个线性规划的经典例子。

原问题变成了一个让对偶函数在(A^Tv-s+c=0)情况下取到极大值g(u,v) = -b^Tv ，考虑一个变量替换y=-v

那就是：

，maxbTy,ATy=c−s，s≥0 ，而再次基础上，又可以进一步消掉s，得到

maxybTy,ATy−c≤0

而对于线性规划的对偶问题实际上也有明确的含义:

1. 标准形式

给出线性规划的标准形式： max⁡{c⊤x∣Ax≤b,x≥0}\max{ c^\top x \mid Ax \le b, x \ge 0 }max{c⊤x∣Ax≤b,x≥0}

2. 对偶形式推导

从**经济解释**推导：
每个约束看作一种资源；
yiy_iyi 表示第 i 种资源的单位价格；
目标是以最小资源成本满足生产需求： min⁡{b⊤y∣A⊤y≥c,y≥0}\min{ b^\top y \mid A^\top y \ge c, y \ge 0 }min{b⊤y∣A⊤y≥c,y≥0}

而对于新得到的对偶问题,另一个需要考虑的点就是它与原问题之间的关系,这又被称之为对偶性:

我们首先考虑弱对偶性:p^{}作为原问题的最优解,*d^{}作为对偶问题的最优解,实际上存在d^{}\lep^{*}

这样，对于所有 λ≥0 ,都有

L(x,λ,μ)=f(x)+∑i∈Iλici(x)+∑i∈Eμici(x)≤f(x),∀x

而对于两边同时对于变量x取下确界，就得到了弱对偶性对应的不等式，

g(u,v)≤p∗,p∗=infx∈Df(x) p∗ 表示条件集下的最优解。

但这样的条件较弱,需要进一步加强,也就是考虑强对偶性:也就是考虑对偶间隙为零的条件.

对于此时的线性规划问题,实际上相当"好",只要存在可行解，那么强对偶条件即满足：

对于原问题p的最优解x^与对偶问题d的最优解x^

c^Tx^=b^Ty^

这点我们可以借助Farkas引理来证明：

第一步：无对偶间隙（数值相等）

任取 ε>0\varepsilon>0ε>0，令 α=v⋆−ε\alpha=v^\star-\varepsilonα=v⋆−ε。由于 α<v⋆\alpha<v^\starα<v⋆，(i) 不可能成立（不可能存在原可行 xxx 使 c⊤x≤αc^\top x\le\alphac⊤x≤α）。于是按对当定理，(ii) 必成立：存在 yεy_\varepsilonyε 使

Ayε≤c,b⊤yε>v⋆−ε.Ay_\varepsilon\le c,\qquad b^\top y_\varepsilon>\,v^\star-\varepsilon.Ayε≤c,b⊤yε>v⋆−ε.

这说明对偶可行域非空，且

sup⁡(D)≥b⊤yε>v⋆−ε(∀ε>0).\sup(D)\ge b^\top y_\varepsilon>v^\star-\varepsilon\quad(\forall\,\varepsilon>0).sup(D)≥b⊤yε>v⋆−ε(∀ε>0).

令 ε↓0\varepsilon\downarrow0ε↓0 得 sup⁡(D)≥v⋆\sup(D)\ge v^\starsup(D)≥v⋆。再结合弱对偶 sup⁡(D)≤v⋆\sup(D)\le v^\starsup(D)≤v⋆，从而

sup⁡(D)=v⋆=inf⁡(P).\sup(D)=v^\star=\inf(P).sup(D)=v⋆=inf(P).

故**无对偶间隙**成立。

第二步：对偶最优解存在（可达性）

我们还需证明 sup⁡(D)\sup(D)sup(D) 不仅是上确界，而且在某个 y⋆y^\stary⋆ 处**达到**。为此用 Minkowski–Weyl 分解论证。

设对偶可行域是多面体

Y:={y∈Rm∣Ay≤c}.\mathcal{Y}:={y\in\mathbb{R}^m\mid Ay\le c}.Y:={y∈Rm∣Ay≤c}.

Minkowski–Weyl 告诉我们存在有限顶点集 VVV 与有限极向量（射线）集 RRR 使

Y=conv⁡(V)+cone⁡(R).\mathcal{Y}=\operatorname{conv}(V)+\operatorname{cone}(R).Y=conv(V)+cone(R).

对线性函数 b⊤yb^\top yb⊤y 在 Y\mathcal{Y}\,Y 上的上确界若有限（我们已知 sup⁡(D)=v⋆<∞\sup(D)=v^\star<\inftysup(D)=v⋆<∞），必有

b⊤d≤0,∀d∈R,b^\top d\le 0,\quad\forall\, d\in R,b⊤d≤0,∀d∈R,

否则可沿某条射线 ddd 使 b⊤(y+td)→+∞b^\top(y+td)\to +\inftyb⊤(y+td)→+∞ 与有限性矛盾。于是

sup⁡y∈Yb⊤y=sup⁡v∈conv⁡(V),d∈cone⁡(R)b⊤(v+d)=sup⁡v∈conv⁡(V)b⊤v,\sup_{y\in\mathcal{Y}} b^\top y = \sup_{v\in\operatorname{conv}(V),\ d\in\operatorname{cone}(R)} b^\top(v+d) = \sup_{v\in\operatorname{conv}(V)} b^\top v,y∈Ysupb⊤y=v∈conv(V),d∈cone(R)supb⊤(v+d)=v∈conv(V)supb⊤v,

其中最后一步用到了对所有射线 ddd 都有 b⊤d≤0b^\top d\le0b⊤d≤0。而在线性函数对**紧集** conv⁡(V)\operatorname{conv}(V)conv(V)（一个有限点集的凸包）上必然取得最大值；于是存在 v⋆∈conv⁡(V)⊂Yv^\star\in\operatorname{conv}(V)\subset\mathcal{Y}\,v⋆∈conv(V)⊂Y 使

b⊤v⋆=sup⁡(D)=v⋆.b^\top v^\star=\sup(D)=v^\star.b⊤v⋆=sup(D)=v⋆.

取 y⋆:=v⋆y^\star:=v^\stary⋆:=v⋆ 即得对偶最优解。可达性证毕。

注：也可用“基本线性规划定理”：线性函数在非空多面体上若有有限最大值，则必在某个极点处取得。与上面的分解论证等价。

第三步：互补松弛与最优性（可选但常用）

由弱对偶等式化证明可推出互补松弛：若 x⋆∈Xx^\star\in\mathcal{X}\,x⋆∈X 与 y⋆∈Yy^\star\in\mathcal{Y}\,y⋆∈Y 最优，则

x⋆⊙(c−Ay⋆)=0,y⋆⊙(b−A⊤x⋆)=0,x^\star\odot(c-Ay^\star)=0,\qquad y^\star\odot(b-A^\top x^\star)=0,x⋆⊙(c−Ay⋆)=0,y⋆⊙(b−A⊤x⋆)=0,

反之亦然（在可行前提下，互补松弛 ⇔\Leftrightarrow⇔ 最优）。这给出判别最优解的结构条件，但并非强对偶成立所必需的额外假设——它是结论的等价刻画。

随机过程（归到概率论里面）：鞅论

想必每一个试图学习鞅论的人都会遇到一个不可绕开的例子，那就是公平赌博问题。

它描述这样的一件事情：对于一个第n轮投掷硬币的情形，你可以下注金额H_n，然后你有1/2获得2H_n的金钱，并有1/2的概率失去所有,每一轮的赌博结果彼此独立。

这样看来，看似就是个普通的赌博游戏，在每轮投一块钱的时候，第n轮的收益记作

考虑第n轮的累计收益之和 S**n=∑n**k=1*X**k* ，那么的分布实际上已知，而且具有名为马氏性的良好性质。

马氏性指的是 ,它只与前一个时刻相关。

当然，这并不是我们今天所讨论的重点。关键在于，一个沉迷投硬币、输光了本金的赌徒坚信自己有一套稳赢策略，即考虑每一轮的情况决定下注额：

换算成具体的语言，就是“赢一把就睡”，每次下注都比之前翻倍直到有所收益。

那么，这样的策略能否如愿呢？一个很简单的结论就是不能，但是现实就是不把道理说明白你说服不了任何人，因此我们引入一个鞅的概念，什么是鞅？通俗来说，就是信息已知情况下的期望。已知每一次的胜负结果构成一个信息总和 { }，在已知这些信息的情况下,未来的预期就是和现在一样，期望不会增加。就称关于这个信息，在数学中一般称之为“sigma代数”，X这个随机过程是一个鞅。

当然，也可以关于自己的这个信息是一个鞅。

很显然，之前讲的一维随机游走就是一个鞅，也就是说，每次投一枚硬币，最终结果总是期望不亏不赚的。在先前信息给定的情况下的第n轮，虽然可能多或者少，但总不期望能多赚钱。

万一倍投策略是对的呢？我看最后n轮之后一直是正的啊。

别逗你martingle笑了，实际来算一下就知道怎么回事了。

考虑第n轮的累计收益是 ,

其中写成并不是因为我们喜欢，而是因为是一个鞅，而某种意义上可以看作的一个函数，毕竟每个时刻下注的金额是与先前博弈结果决定的。因此某种意义上也可以看作一个离散的求和

,这其实可以拓展为积分。但我们今天还不谈这个，我们只用知道其实关于每一次的结果构成的信息流其实是一个鞅

以下是证明过程，记得转发给你们喜欢抛硬币的朋友

第一项，由于只由决定，因此

第二项：

第三项：

因此，也就是说，任凭你采取何种策略，情况已经这样了你博弈后的钱预期不会有什么变化，也就是说，钱损失的可能性与收益的可能性是一样的。

那么我们还会问一个问题，经过若干轮后，我们似乎会有

但仔细计算就知道这个概率总是0.5,而另外0.5的概率是，债务翻番。能让你一直站在牌桌下的前提是拥有无限的资金，因此其实在这个请境内你预期也不会取得收益。

当然，这篇文章在一个叫做“从天地玄黄宇宙洪荒开始讲的人工智能”，这东西和AI看上去没有任何联系啊。

然而并非毫不相关，因为大家不算特别熟悉的随机过程就是希望能用一个简单的分布经过变换变成目标分布，而这个变换就是通过解读另一个过程，一个把“目标分布变成简单的分布”的过程（前向过程）逆推为后向过程来还原未知目标分布，而这个生成的后向过程是已知的，我们可以进行更多的采样。说的更应用一点，什么是“一张图片”？本质就是像素点的一个未知分布，通过前向、后向过程就能生成更多类似的图片，这就是 AI 生图。

而扩散过程，实际上也是增加一个小的随机变量dx,前向过程就是加一个使其变成噪声的分布，后项过程则是反过来。至于我什么时候讲，得了吧，我离散随机过程都没搞明白。

数值最优化：首先需要介绍要解决的问题，无约束优化通常可以写成这种形式：

minf(x)ci(x)=0,i∈Ecj(x)≤0,i∈I

这实际上是在一个区间 Ω 之内寻找最小值，而这个区域就是所有可行点，即满足等式与不等式约束的全部点的集合： Ω={x|ci(x)=0(i∈E),cj(x)≤0,(i∈I)}

首先引入两个概念，可行方向与线性化可行方向：

可行方向：对于某一个点x，考虑以此为出发的一系列单位方向向量d的集合 FD

∃{xk}→x,αk→0,dk→d,x=xk+αkdk,d∈FD(x)

而上述两种说法实际上也有几何意义：对于可行方向，d_k实际上就是在这一点的切向量，构成的几何实际上被称之为“切锥”

\figure{约束与切锥，来自于文再文}

因此，我们可以在此基础上得到一个最优性条件，几何最优性条件：

FD(x)∩{d|∇f(x)Td<0}=∅

这实际上说明只要所有可以进行的方向都是向上走的就可以证明此时局部极小。

然而，切锥的计算实际上是难以进行的，因此，这里给出一个相对更好计算的线性化可行方向集合

对于某一个点x，考虑以此为出发的一系列单位方向向量d的集合 FL

{d∈FL(x)|dT∇ci(x)=0,i∈E,dT∇ci(x)≤0,i∈I∩A(x)}

其中 A(x)=E∪{i∈I,ci(x)=0} 这表示在x点所有成立的等式

线性化可行方向其实就是通过约束条件梯度与下降方向内积与原不等式保持一致，表明该下降方向实际上就是所有可以保持当前x约束不等式必定方向不变的量。

我们可以证明，可行方向必然是线性可行的，但反之并不成立

那么，什么情况下线性可行方向与可行方向等价呢？这就用到线性约束资格的概念:

约束资格（Constraint Qualification, CQ）若 x∗ 是原问题的局部极小点，并且在这一点满足某个一阶约束资格（常见选项）：

LICQ：（线性无关约束资格）对于不等式约束h_i(x)与等式约束

{∇hi(x∗)|i=1,…,m}∪{∇gj(x∗)|j∈A(x∗)} 是线性无关的。

MFCQ：等式梯度线性无关：

等式约束的梯度向量 ∇hi(x∗) 线性无关；存在一个方向 d，使得：

∇hi(x∗)Td=0,i=1,…,m 且 ∇gj(x∗)Td<0,∀j∈A(x∗)

在这些 CQ 下，可行方向与线性可行方向等价：

在此基础上，我们就可以重述之前的几何最优性条件，这又被称之为KT条件。只要满足线性可行方向集合 FL 与下降方向集合交集为空集即可

当然，KT条件要想验证这是一个空集实际上很困难，对于计算机而言，找出一个反例很容易，但是遍历所有元素几乎不可能。于是接下来，介绍一个计算上更容易验证的条件，又被称之为KKT条件的约束最优化条件

KKT条件：对于拉格朗日函数 L(x,λ)=f(x)+∑i∈Eλici(x)+∑i∈Iλici(x)

对于拉格朗日函数L的最优解 x∗,λ∗

满足稳定性条件： ∇L(x∗,λ∗)=0

约束性条件： ci(x∗)=0,∀i∈E,ci(x∗)≤0,∀i∈I

对偶性条件： λi∗≥0,∀i∈I

互补松弛性条件 λ∗ci(x∗)=0,∀i∈I

与此同时， x∗ 是原问题的局部最优解

对偶性条件实际上是希望保持对偶性，拉格朗日函数的最小值必然小于等于原问题的最小值

而在互补松弛条件下，可以保证小于部分的不等式被对应的\lambda给控制

证明过程：

引理的引理：超平面分离定理

令 C,D⊂Rm 为不相交、非空、凸集，且至少一个是开集，则存在非零向量 y 与标量 α ，使得

⟨y,u⟩<α<⟨y,v⟩,∀u∈C, ∀v∈D.

这看上去是个何意味的代数表达式，但实际上如果把y看成一个法向量，说明C，D的内积必然存在差距，就相当于它们分布在一个超平面集合 S={x|yTx=0} 的两侧。

这实际上比较容易证明，就不额外叙述了

引理：Farkas引理

{d|aiTd≥0(i=1,2,⋯,m),gTd<0}=∅⇔∃λi≥0,s.t.g=∑λiai

证明：，⇒，g∉C=L(a1,a2,⋯,an) 由超平面分离定理，D={g},有平面法向量，使得

gTd<0,aiTd≥0 ,这与非空假设矛盾了。故集合为空集时，g必然在A生成的线性组合之中

⇐ ，当g写成如此的线性组合形式时，对于所有的d,使得 aiTd≥0 时， gTd≥0 也必然成立

当然，Farkas引理也可以写成矩阵的形式，两者等价

矩阵 A∈Rm×n 、向量 b∈Rm 。以下二者恰有其一成立（线性择一定理）：

(F1) ∃x∈Rns.t.Ax=b, x≥0 (F2) ∃y∈Rm,s.t.A⊤y≥0, ⟨y,b⟩<0

在此基础上，我们得到了KKT条件的证明过程：

首先局部最优点需要满足几何约束条件，在LICQ或者其它约束品性的条件下

下降方向与线性可行方向集不相交：

线性化可行方向 {d∈FL(x)|dT∇ci(x)=0,i∈E,dT∇ci(x)≥0,i∈I∩A(x)}

下降方向 {d|gTd<0}

这样，根据Farkas引理， g∗=∑i=1nλi∇ci(x),i∈I∩A(x),λi≥0

而在此基础上，考虑不等式中某些不等式的等号部分是成立的，因此考虑进行筛选：

令 λi∗=0,i∈I/A(x) , g=∑i∈I∪Eλ∗∇ci(x∗),λici=0

这也就证明了KKT条件

上述的结果也可以具有直观解释：若无法把 ∇f(x∗) 表为活跃约束梯度的非负锥与等式线性张成的“支撑组合”，那就存在方向既不破坏可行性又能降低目标，从而违背极小性；Farkas/择一定理把这两种可能二选一地分离出来。

二阶最优性条件：

首先从一阶可行方向出发。定义 线性化可行方向集合： D(x∗)={d∈Rn:∇ci(x∗)Td=0, ∀i∈E; ∇ci(x∗)Td≤0, ∀i∈A(x∗)}

其中 A(x∗)={i∈I:ci(x∗)=0

是活跃不等式约束集合。

由于 x∗ x∗ x∗ 满足 KKT 条件，有：

∇f(x∗)+∑i∈Eλi∗∇ci(x∗)+∑i∈Iλi∗∇ci(x∗)=0,λi∗≥0, λi∗ci(x∗)=0.

临界方向 d是指在一阶意义下“目标函数梯度沿该方向不再下降”的方向： ∇f(x∗)Td=0,

并且 ddd 必须满足线性化可行性条件。于是得到 临界锥（Critical Cone）：

几何上，临界锥表示那些既保持一阶可行、又在一阶近似下不改变目标函数的方向。

如果 x∗ 是局部最优点，并且满足 KKT 条件（在一定约束资格下，例如 LICQ 或 MFCQ），则必有：

且且C(x∗,λ∗)={d∈Rn:∇ci(x∗)Td=0, i∈E; ∇ci(x∗)Td=0, i∈A(x∗) 且 λi∗>0; ∇ci(x∗)Td≤0, i∈A(x∗) 且 λi∗=0; ∇f(x∗)Td=0}.

其中 L(x,λ)=f(x)+∑i∈Eλici(x)+∑i∈Iλici(x) 是拉格朗日函数。

二阶必要条件：

若 (x∗,λ∗) 满足 KKT 条件，并且对所有 d∈C(x∗,λ∗)∖{0}

有： dT∇xx2L(x∗,λ∗)d≥0,

否则若存在某方向 d∈C 使得 dT∇xx2L(x∗,λ∗)d<0 那么可以沿该方向在二阶近似下减少 f(x) 而不违反约束，这与局部最小性矛盾。因此，对局部极小点而言， Lxx 在临界锥上的二次型必须是**半正定**（非负）。

二阶充分条件

若 (x∗,λ∗) 满足 KKT 条件，并且对所有 d∈C(x∗,λ∗)∖{0}

有： dT∇xx2L(x∗,λ∗)d>0,

则 x∗ 是一个**严格局部极小点（Strict Local Minimum）**。

机器学习：聚类算法

聚类算法是我最喜欢的算法，在我心里就像mujica一样。不同于之前的决策树，线性回归，支持向量机，决策树，以及adaboost，XGboost。这些算法都需要预先告诉标签才能训练好。聚类算法不需要标签，只需要给定样本点，然后划分数据将数据聚成几类。

聚类算法干了一件什么事？其实就是把数据分成几个类，每一类都是相似的。

这句描述之所以听上去像是一句废话，是因为很多东西没讲明白。第一，怎样定义数据之间的相似性，比如说给你一百万张照片，让机器去自行发现特征，最后把数据分成猫一类狗一类。但是机器读不懂人类所熟知的特征，比如一片菜园子，有些植物是睦子米种的，有些植物是墨提斯种的，我们只知道两人在种植偏好，种植水平上存在差距。

比如说有324个采摘结果数据，包含的特征包括作物的种类，比如黄瓜，苦瓜，作物的长度，直径，重量，以及更多的特征。经过了月之森研究院的帮助下，我们提取到了20个特征，数据都是归一化好的。

现在我们需要根据这20特征对应的特征向量，每一个x_i都代表一个样本点，维度为20。我们需要将作物分成两类，一类是睦种的，另一类是mortis种的。

接下来，我们分别介绍三类聚类方法，分别是原型聚类，密度聚类，层次聚类

原型算法假设聚类结构能通过一组原型刻画。（“原型”是指样本空间中具有代表性的点），我们假设睦头种出来的黄瓜就是好，两人种出来的作物确实存在差异，所以进行分类。

基于这个假设，我们先要初始化原型，这里就是聚两个类，也就是随机挑两个样本。

接下来，我们选取与这两个作物最接近的样本 μ1,μ2 ，进行初步的归类。对于已经归一化的数据集合，此处的距离就是欧式距离

dki=||xk−μi||2 ，然后将其归类为距离最近的一类。

r1,k=1(dk1<dk2)=0(else)r2,k=1(dk2≤dk1)=0(else)

其次，需要重新计算样本的中心，我们希望样本的 μk 确实是每一个类中心的位置。实际上就是要极小化每个类中： k=1,2∑i∈Dk||xi−muk|| ,实际上就是计算每类样本的均值向量

μk=∑i=1rk,ixi∑i=1rk,i

这就是小名鼎鼎的k-means均值聚类算法，我们通过这种方法分好了黄瓜……吗？

它只是选出了最不同的两组作物。并不能说明这就是按照种植人分类的，说不定只是把月之森种的和在家里种的两类筛选出来了，毕竟这可能是更加区分作物之间的差异

我们可以通过叫睦妈妈的方式或者和长崎素世那里拿到一根肯定是小睦的黄瓜和肯定是mortis的黄瓜，将其视为原型向量。当然，就算它确实是小睦种的黄瓜，但是这不一定是最典型的符合小睦特征的黄瓜，使得我们拿这根黄瓜来作为参照，有可能错过了一些更加典型的例子。

我们按照这样的顺序，首先选取原型向量 p1,p2

依次选取其它的样本 xi ，通过到原型向量的距离 di1,di2 ，确定样本的归类，离得较近的就归类。

其次就是更新原型样本，如果新加入的这个 xi 是正例

pi′=pi+γ(xi−pi) ,原型样本离他更近

否则

pi′=pi−γ(xi−pi) ,原型样本离他更远

最终依次更新 pi=pi′

当原型变量变化足够小，或者迭代次数足够多那就发生改变

当然，这需要假设数据在高维空间的分布是一团团的，但mortis是小孩子性格，比较随性，加上人缘比较好可能会请到高人，方差比较大，最好的最烂的都是她种的。我们只能说，种的黄瓜比较多，不同的类分布的比较紧密。而且睦的性格完全没有确定下来，所以说她的体内可能还存在不止一个人格，黄瓜仙人或者什么别的老农民种地高手可能性微存。

这样，我们使用密度聚类也称为“基于密度的聚类”(density-based clustering)。此类算法假设聚类结构能通过样本分布的紧密程度来确定。通常情况下，密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇来获得最终的聚类结果。

介绍DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法）是一种基于密度的空间聚类算法。该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。

簇是满足以下性质的非空样本子集：

连接性：与密度相连

最大性：与密度可达

实际上，若为核心对象，由密度可达的所有样本组成的集合记为𝑋= 𝑥 ∈𝐷|𝑥由𝑥密度可达，则𝑋为满足连接性与最大性的簇。

算法的操作过程实际上就是以下这几步：

1首先给定一个最小包含点数N_{min}和截断距离\epsilon

2遍历每个点，检测截断距离构成的小球心内数据点的数目，如果数目大于等于最小包含点数，将其记作核心点，这个点和距离小于等于最小包含点数的点集合“临时聚类族”

3其次，合并每个临时聚类族，对于每一个临时聚类族，检测其中的点是否为核心点

如果是核心点，那么这个核心点对应的临时聚类族与当前临时聚类族合并，直到所有的点要么不在核心点，要么所有密度直达的点都在临时聚类族中，记临时聚类族为聚类族，继续遍历其它临时聚类族。

层次聚类：

顾名思义，层次聚类就是按层次进行聚类的算法，它不是一种特定的聚类结果，而是按照不同的层次生成聚类结果，这包括自下而上或者自上而下。

自下而上就是假设每个数据是单独的一类，得到一系列原始的簇

其次，计算簇与簇之间的距离，这可以选取

最小距离 dmin(Ci,Cj)=minxi∈Ci,xj∈Cjd(xi,xj)

最大距离 dmax(Ci,Cj)=maxxi∈Ci,xj∈Cjd(xi,xj)

平均距离 davg(Ci,Cj)=1NiNj∑xi∈Ci,xj∈Cjd(xi,xj)

接下来逐步遍历 Ci,Cj 之间的距离，合并两个距离最小的簇

这样一层层进行的过程，就被称之为层次聚类。

最后我们需要评价模型的性能，一般情况下，我们直接问睦和mortis，看看分得准不准确，这叫直接查看分类结果；当然，如果睦去演出去了，我们可以去让丰川家雇佣一位农业专家给出评价意见。

贝叶斯学习：贝叶斯原理在概率论中的地位无可比拟，看上去是简单的条件概率，但实际上有很深的寓意：它代表随着信息的获取，我们对事物的认知是不断深化的。

写成形式语言，就是 P(c|x)=P(x|c)P(c)P(x) ,P(c)为c的先验分布，c表示观测指标，由之前的统计数据，我们知道每一个x对应的已有观测指标的条件概率。

这是一个没什么用的形式推导，让我们来给出一个具体的例子:

我们要判断一只猫是豪猫还是耄耋，我们有一系列的指标，包括生活环境，包括体型大小，猫的种类，年龄，是否生育，流浪经历等等……

经过高人处理之后，我们得到了一系列的特征x，并且高人替我们分了一些标签。(x_i,y_i),基于此，我们需要训练出一个贝叶斯的分类器。

我们这里考虑两个分量的简单情况x_1表示家养或者流浪，x_2表示有无绝育，x_3表示是否哈气，c表示猫的好坏

1小基米的做法：朴素贝叶斯

c=1标记为豪猫，c=-1标记为坏猫，并且有前100只基米数据集。那么，新来一只猫，我们应该如何进行分类呢？

我们根据已有数据计算P(x_i|c),例如P(x_1=1|c=1)计算好猫中家养猫的概率，P(x_1=1|c=-1)计算耄耋中家养猫的概率。同理，计算其它各个分量。

小基米听不懂过于复杂的理论，它的想法就是假设每一个特征都是相互独立的，对于一只新来的小猫，根据它的特征x^0,分别计算P(x^0|c)=\Pi P(x^0_i|c)，分别带入c=1,c=-1,并分别计算P(x^0|c)P(c)

如果前者更大，就说明认为这是一只好猫能够更好的解释这只猫的现状，那就将其标记为好猫。

不过似乎还是有点问题，对于连续的变量应该如何处理？

对于全是零的变量应该如何处理？Laplace平滑项

2月半猫的做法：ODE与AODE

不对，因为流浪猫绝育的概率几乎为零，即使绝育了在自然界中也很难存活下去，这就充分说明特征之间不是独立的，月半猫指出，我们可以认为所有的特征是独依赖的，每个特征只与一个其它特征相关。

这，就是ODE（不是常微分方程的那个ODE,是One-Dependent Estimator）

P(c|x) \propto P(x|c)P(c)=P(c)\Pi_{i=1}P(x_i|c，pa_i)

SPODE：假设不同的特征之间只依赖于一个超父

例如pa_i = x_1，

P(c|x) \propto P(x|c)P(c)=P(c)\Pi_{i=1}|P(x_1|c)P(x_2|c,x_1)

同样的，分别代入c的取值，给出概率极大的c值

所以，如何选取这样的超父呢？这里有很多种方法，一方面可以一个一个试，利用实际的分类效果来看。另一方面可以采用“博采众长”的方法，用不同的超父训练多个分类器。

不过，除了这些检测结果的后验做法，还可以直接给出一些变量的衡量特征，例如以条件互信息为基础为基础的TAN算法：

其次构造完全图，不同节点之间的权重设置为 I(xi,xj|y)

构建以此图的最大带权生成树，每个节点此时就只有一个父节点，将其记作pa

3吴大师的做法：贝叶斯网

两位小辈说的很对，但是既然可以依赖于一个节点，不妨直接给定一个图来判断两者之间的依赖关系。

例如这是一张简化版的哈气图：

哈！

所以整体的概率可以表示为：

P(x_1,x_2,x_3,x_4,x_5)=P(x1)P(x_3)P(x_2|x_1,x_3)P(x_4|x_1)P(x_5|x_1,x_2,x_4)

观察这个图，我们不难发现，变量之间基本只遵从三个关系：

同父：x1,x2,x4，后两个都受到x1的影响

顺序：x3,x2,x5，x5由x2控制，x2又被x3控制

V字:x1,x3,x2，这两个变量同时影响

其次，我们要考虑变量之间的独立性，这里有一个叫道德图的东西：将所有无向图换成有向图，并且连接V字形的边，这样，我们就可以知道在这个哈气图的变量依赖关系

机器学习：集成学习

集成学习是我最喜欢的算法，它的核心思路就如同它的字面意思，根据多个学习器来进行训练。它不是某一类特定的算法，需要一些“基学习器”，例如决策树，例如贝叶斯，例如线性回归。

更具体来说，又可以分成两类，分别是Boosting和Bagging

对于Boosting方法，包括Adaboost，以及更加知名的XGboost

这些方法实际上和做题很像，我们首先会相对均匀的练习，但是我们的水平并不是均匀的，可能会有一些错误率更高，我们提高错误率高的题目的权重，这是一个不断“提升”的过程，英文名就是“boosting”

adaboost使用的是一个加性模型，对于求解二分类问题时，它是这样运行的。

首先，给定初始的数据分布 D1(x)=1m

对于第k次训练的结果，我们在这组新的分布下训练出一个训练器（）hk=L（D,Dk(x)）

这个加权实际上就是增大某类样本犯错误的代价，我们希望这些新的训练器能够弥补老训练器的不足。最终极小化的目标就是在这组权重下“犯错误的概率”，得到第k个训练器的训练效果， ϵk=Px∼Dk(hk(x)≠f(x))

根据训练效果，得到一个权重 αk=12ln(1−ϵkϵk)

最后，重新调整参数的分布，提高错误样本在训练中的比重

，，Dk+1(x)=e−αtDk(x)，if(f(x)=hk(x))eαtDk(x)，if(f(x)≠hk(x)) 乘完之后的D_{k+1}还要归一化，确保这依然是一个分布

停止条件是 ϵk>12 ,数据的比例被调整到差不多的位置了

最后 F=sign(∑i=1kαkhk)

事实上adaboost等价于最小化指数损失函数

Ex∼D[err(f(x),Ht(x)]=Ex∼D[err(f(x),Ht−1(x)+αtht)]

err(x)=e−x

当然，还可以采用更一般的结果，不仅仅处理二分类问题对应的logistic回归型log(1+exp(-f(x)H(x)))，也可以采用平方和的L2损失|x|^2

当然，像这种来自于极小化偏差的boosting方法，每一步都是极小化当前的误差。当然，是从学习器出发的。当然，我们也可以从数据出发。

有一种类似于“盲人摸象”的直观想法，有人摸到了大象的腿，生成大象是柱子，有人摸到了大象的耳朵，认为大象像蒲扇……如果他们几个人凑在一起讨论，或许就能凑出一个对于大象更全面的认识。

所以我说，古人如果学习了线性代数，指不定能开发出什么离奇的算法。

至少我们的bagging算法，实际上比盲人摸象高明不到哪里去。对于一个较大的数据集，从中有放回的抽取m个样本打包，总共分出T个数据包，然后拿这个数据包进行一轮训练，这样训练出T个训练器，然后综合各个训练器的结果进行输出。

不对，你怎么确定拿这个有放回抽样的数据集合原本的数据集是一样的，都能训练出好东西呢？事实上，这种被称之为自助法的统计方法早就出现了，而且也确实只有63.2%的数据被用上了。

但这样经过bagging，选取的都是出现频率更高的样本，这些样本出现得更多，说明它们不是“偶然”出现的，就天然降低了方差。我们还可以这剩下的数据36.8%的数据进行验证泛化性。

而训练多个样本取“平均”，不管是通过投票法处理分类问题，用简单平均处理回归问题，根据：

Var(1m∑i=1mXi)=1m2∑i=1mVar(Xi)

方差得到了减小。

接下来，我们还介绍随机森林方法：这就针对训练器进行了改变。

首先，依然是bagging操作分类数据集，其次，决策树的特征选取往往是个大问题，在此，我们放弃所谓的“最大增益原理”，对于每一个数据集D_i，随机选取k个特征，只根据这k个特征进行训练。

所以归根到底，集成学习就是通过从不同的数据集之中，通过划分，来让只能认识到数据集局限性的学习器尽可能得到兼顾。不管这种划分数据集是通过序贯得到样本，有针对性的面对错题进行训练；还是通过随机抽样，训练出多个学习器降低偏差。

更具体点来说，我们定义回归问题，采用L2平方损失时的分歧性和各个模型的泛化误差

分歧性，每个子模型和总的学习 A(hi|x)=E(hi(x)−H(x))2

各个模型的泛化误差： Ei=E(hi|x)=E(hi(x)−f(x))2

而又根据 E(H(x)−f(x))2=E((hi−f(x))2+wi(hi−H)2+2wi(hi−H)(hi−f))

第三项实际上是零，所以就有

∑i=1mwiAi=E(H(x)−f(x))2−∑i=1mwiEi

所以，每个基学习器效果不变的基础上，如果“差异”尽可能大，就能使总体训练效果更好。

我们可以使用多样性度量，其中，考虑一个二分类问题的列联表

hi=+1hi=−1hj=+1achj=−1bd

因此，我们可以得到两个分类器之间差异的统计量

例如相关系数 ρij=|ad−bc|(a+b)(a+c)(c+d)(b+d) ,Q统计量 ad−bcad+bc

AI4PDE的一些内容

1入门篇

本文当你是个真正意义上的萌新，假设你脑子一热，想去做PINNs,然后打开sci-hub发现啥都看不懂，网上问谁都不好使，你打算去知乎来碰碰运气。也巧，我写了篇文章，可以来看看。

相比于其它的公开资料，例如关于PINNs的原始文章，力求用最简单通俗，且附上案例与代码，且做到比其它互联网上的公开资料更符合零基础小白，且具有丰富的娱乐性,以至于你可以拿它配上一集ave mujica，或者一边挂明日方舟，一边来刷一下。

不要把这篇文章当成什么正经参考文献，如果可以，请阅读其它你能找到的参考资料。一些可能用到的内容将在后续内容给出，你就将这当作不知所谓的呓语就好。正文部分预计没有任何学术价值，娱乐价值倒还是不赖。

可以直接跳转到3看问题求解。

1PINNs是干什么的：

PINNs用神经网络来求解偏微分方程，这句话挺直接的，而且我们也无需赘述偏微分方程求解的意义。

当然，哪怕是一只草履虫，都很容易知道偏微分方程的四种以上求解方法，例如有限差分法，有限元方法，有限体积法，谱方法等，这将会在另一个专栏，“从零开始的计算数学”里面讲到。

PINNs就在这个等里面，它是一种用神经网络求解偏微分方程的方法。

求知欲强的草履虫应该知道，神经网络不是万能魔法，它是一个函数，用参数来表示函数。

或者，从更数学的角度来说，是从待选函数空间里面找到一个函数，使得让目标泛函极小化。

这个目标泛函，也就是把函数映射成一个数，其实就是一个对于目标的具体化。

在这个情境中，就是需要找到一个“满足偏微分方程条件”的一个函数，是基于这个准则构造一个损失函数。

这个损失函数极小化对应的将会是由方程所决定的一个函数。不过如何构造损失其实是个大问题。

2PINNs有什么优势：

答：没什么优势。

就像许多神经网络引入传统的领域一样，肥胖的城市，递给它一个，新朝的方法，来克制恐慌。而传统的方法依然占据主要优势。就比如一个最经典的热方程，PINNs的求解时间往往是十几倍，而精度往往也差不多。

所以PINN被发明出来就像是注定要烂尾的工程，只不过是大佬们拿出了打发时间，在一众博士浪费了数年青春之后毫无用处，产出几篇没用论文之后就陷入冷静的方向吗。这是浅草目前对于PINN，以及用神经网络求解偏微分方程所做出的一系列理解，当然，PINN是用来水论文的结论没错，但神经网络并不打算止步于此。

不同于传统的数学方法，基于理论自上而下的推理：这在知识日益爆炸的今天和现实纷繁复杂的情景往往是不适用的，从宏观的角度来看就是引入了一种新的思路，基于数据自下而上的推理。而我们的数据来自于方程本身，来自于随机取点，所以看上去不太像面向现实的数据，但其实也挺好了。

其次，就是它宣称能够做到的效果：面对高维问题的求解，面对复杂边界的求解，与反问题的求解挂钩。

当然，我并不了解这件事，我只知道我电脑解冒烟了都没搞明白一个热方程。这使得我觉得我应该拿出点真东西来。那么，就让我们击杀回放一下，看看电脑是怎么被那一团乱麻的数据卡冒烟的。

3简单的问题的求解，顺带梳理一下求解的步骤

首先来看一个具体的问题，一个二维的泊松方程，应该是最简单的二维方程了

，−uxx(x,y)−uyy(x,y)=0，x∈Ωu(x,y)=0,x∈∂Ω

其中区域选择一个比较好求解的 Ω=[−1,1]×[−1,1] ，也就是一个矩形区域。

根据偏微分方程求解的有关内容，我们能够一眼看出这是 u(x,y)=lnr

但是不熟悉微分方程分离变量，傅里叶变换，格林函数法等等方法的一般路过草履虫，显然没法这么做，而神经网络的求解步骤大家是熟悉的：首先收集数据点x_i,接着利用多层神经网络构造一个函数u^*，然后根据两个方程构造损失函数，利用优化方法损失函数极小，这样越小，得到的解就是原方程的的解。

按照这种思路，就可以逐渐构造PINN的网络架构：

首先是选取一系列的 {xi}i∈E⊂Ω,{xi}i∈I⊂∂Ω, 其次，就是在数据点处构造损失函数：

，−uxx(x,y)−uyy(x,y)=0，xi∈Eu(x,y)=0,xi∈I

一个很自然的想法就是极小化平方值，也就是L2范数

L(u)=∑i∈E|Δu(xi)|2+∑i∈I|u(xi)|2 方程两项分别对应微分算子与边界两项的约束条件。

最后考虑对u进行参数化，考虑一个单层的神经网络， u(x)=σ(wTx+b) ，并将其代入原函数，通过优化参数就可以得到最优的取值。在实际操作中，还可以通过增加层数等操作来将其优化。

一些参考的资料：

根本就没有，deepseek，GPT,豆包就是文章所有的信息来源，还有知乎的几个帖子，本文不具有任何权威性质。

这个链接指向一个deepxde求解，你可以找到包括不限于所有的偏微分方程求解，鉴于草履虫可能并不

lululxvi/deepxde: A library for scientific machine learning and physics-informed learninggithub.com/lululxvi/deepxde

封面来自于MujicaX明日方舟联动角色丰川祥子

2新手训练

基础的理论部分如下，下期会继续讲

面向看了四年少女乐队啥也不会赶鸭子上架去做应数研究的纯新人的PINNs入门的入门13 赞同 · 3 评论文章

本期是PINN的训练介绍，将会介绍一些训练时的心得体会：