优化与对偶理论笔记
来源：知乎专栏文章迁移 涵盖内容：线性规划对偶理论、数值最优化与KKT条件
这是一边看 mujica 同人一边写的对偶理论笔记，大部分内容来自于文再文老师的《最优化：建模、算法与理论》、周志华《机器学习》以及各类参考资料。
线性规划与对偶问题
首先介绍线性规划的例子，引入拉格朗日对偶函数与对偶问题
对偶函数在这个情境下有什么具体的含义,介绍影子价格等具体的意义,引入对偶函数有什么用
其次,讨论对偶问题与原问题之间的关系
接着，介绍线性规划问题的强对偶性,介绍互补松弛条件
1例子:线性规划
例子1，带约束的线性规划问题:
$$
min c^\top x,s.t.Ax=b,x≥0
$$
这对应了一个实际生产之中的情景，A表示加工某种产品所需要的物资分配情况，而x表示所需要购买的原材料量，b表示实际的生产需要，c则表示原材料的成本。在销售量已经确定的情况下，所能够优化的只有成本，这就是一个带约束条件的线性规划问题。
当然原问题不一定是可以求解的,例如
$$ \min x_1\
x_1=-1\
x_1\ge0 $$
明显原问题没有可行点,此时也就没有什么讨论的必要了.在接下来的情境下,都是讨论解可行且有限的情况
对于例子1这种带约束的线性规划问题，我们想到将约束整合进入原函数，这就是当年对偶问题的提出者所干的那件事：构造了一个拉格朗日函数，将问题转化为
\(L(x,s,v)=c^\top x+v^\top(Ax−b)−s^\top x\)
然后，按照优化的固有思路，考虑将拉格朗日关于x极小化，然后，我们就得到了只与u,v相关的一个对偶函数：
推到这一步，因此只要 \(A^\top v−s+c\) 这个向量不为零，那么就总能找到x使得这一项趋近于负无穷。
而此向量为零时，能用最小值\(−b^\top v\)
因此,就得到了一个线性规划问题的对偶问题: $$ \min_v -b^\top v,\ s.t. A^\top v+c =s\ s\ge0 $$ 原问题变成了一个让对偶函数在(A^Tv-s+c=0)情况下取到极大值g(u,v) = -b^Tv ，考虑一个变量替换y=-v
那就是：
\(\max_{y}b^\top y,A^\top y=c−s，s≥0\) ，而再次基础上，又可以进一步消掉s，得到
$$ \max_yb^\top y,A^\top y−c≤0 $$ 这么一通操作到底是为了干什么呢？
首先，对偶问题往往具有更好的形式，这是一个定性的描述，很难说一个问题怎么就“变好”了。
我们首先举出哪个线性规划的经典例子。
而对于线性规划的对偶问题实际上也有明确的含义:
给定线性规划的标准形式： $$ \max{ c^\top x \mid Ax \le b, x \ge 0 } $$
每个约束看作一种资源； \(y_i\)表示第 i 种资源的单位价格； 目标是以最小资源成本满足生产需求：\(\min\{ b^\top y \mid A^\top y \ge c, y \ge 0 \}\)
虽然这个新的问题确实依然是有意义的，但它是不是有道理的呢？ 而对于新得到的对偶问题,另一个需要考虑的点就是它与原问题之间的关系,这又被称之为对偶性: 我们首先考虑弱对偶性:\(p^{*}\)作为原问题的最优解,\(d^{*}\)作为对偶问题的最优解,实际上存在\(d^* \le p^{*}\)
这样，对于所有 λ≥0 ,都有
$$ L(x,λ,μ)=f(x)+\sum_{i∈I}λ_ic_i(x)+\sum_{i∈E}μ_ic_i(x)≤f(x),\forall x $$ 而对于两边同时对于变量x取下确界，就得到了弱对偶性对应的不等式： $$ g(u,v)≤p^∗\ p^∗=\inf_{x\in D}f(x) $$ p∗ 表示条件集下的最优解。
但这样的条件较弱,需要进一步加强,也就是考虑强对偶性:也就是考虑对偶间隙为零的条件.
对于此时的线性规划问题,实际上相当"好",只要存在可行解，那么强对偶条件即满足：
对于原问题p的最优解\(x^*\)与对偶问题d的最优解\(x^*\)
\(c^\top x^*=b^\top y^*\)
这点我们可以借助Farkas引理来证明：
第一步：无对偶间隙（数值相等）
任取 \(\varepsilon>0\)，令 \(\alpha=v^\star-\varepsilon\)。由于\(\alpha<v^\star\)，(i) 不可能成立（不可能存在原可行x使得\(c^\top x\le\alpha\)）。 于是按对当定理，(ii) 必成立：存在 \(y_\varepsilon\) 使
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)\)不仅是上确界，而且在某个 \(y^{\star}\)处**达到**。为此用 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,
否则可沿某条射线 d 使 \(b^\top(y+td)\to +\infty\)与有限性矛盾。于是
supy∈Yb⊤y=supv∈conv(V),d∈cone(R)b⊤(v+d)=supv∈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。而在线性函数对紧集 $\(\operatorname{conv}(V)\)\(（一个有限点集的凸包）上必然取得最大值；于是存在\)v^\star\in\operatorname{conv}(V)\subset\mathcal{Y}$ 使
b⊤v⋆=sup(D)=v⋆.
$$ b^\top v^\star=\sup(D)=v^\star. $$.
取 \(y^\star:=v^\star\)即得对偶最优解。可达性证毕。
注：也可用“基本线性规划定理”：线性函数在非空多面体上若有有限最大值，则必在某个极点处取得。与上面的分解论证等价。
第三步：互补松弛与最优性（可选但常用）
由弱对偶等式化证明可推出互补松弛：若 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\) 最优）。这给出判别最优解的结构条件，但并非强对偶成立所必需的额外假设——它是结论的等价刻画。
数值最优化：首先需要介绍要解决的问题，无约束优化通常可以写成这种形式：
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)=∑xi,xj;c∈YP(xi,xj|c)logP(xi,xj|c)P(xi|c)P(xj|c) 计算互信息
其次构造完全图，不同节点之间的权重设置为 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