一致性公式证明

首先，假设存在两个不同的聚类假设$f^1$和$f^2$，它们在两个视角上的聚类结果分别为 y 1 ∈ { − 1 , + 1 } n y^1\in\{-1,+1\}^n y1∈{−1,+1}n和 y 2 ∈ { − 1 , + 1 } n y^2\in\{-1,+1\}^n y2∈{−1,+1}n。

证明一致性不等式：

​ P ( f 1 ≠ f 2 ) ≥ max ⁡ { P e r r ( f 1 ) , P e r r ( f 2 ) } P(f^1\ne f^2)\ge\max\{P_{\mathrm{err}}(f^1), P_{\mathrm{err}}(f^2)\} P(f1=f2)≥max{Perr​(f1),Perr​(f2)}

其中$P_{\mathrm{err}}(f)$表示假设$f$的误差概率，即：

​ $$P_{\mathrm{err}}(f)={\mathbb{E}}_{(x,y)\sim D}[f(x)\ne y]$$

其中$(x,y)$表示数据点和其标签，$D$表示数据的分布。假设我们从$D$中采样$m$个数据点$(x_1,y_1),\dots ,(x_m,y_m)$，构成训练集$S=\{(x_1,y_1),\dots ,(x_m,y_m)\}$。

使用训练集$S$学习得到聚类假设$f_S$，我们定义训练误差$P_{\mathrm{err}}(f_S)$为：

​ $$P_{\mathrm{err}}(f_S)=\frac{1}{m}\sum _{i=1}^{m}1(f_S(x_i)\ne y_i)$$

其中$1(A)$表示当命题$A$为真时取值为$1$，否则取值为$0$。

然后定义一个指示器函数$I(S)$来判断训练误差是否落在某个区间之内。具体来说，对于给定的常数$\delta \ge 0$和$ϵ>0$，我们定义：

​ $$I(S)=\{\begin{array}{ll}1& \text{if }{P}_{\mathrm{err}}(f_S)-P_{\mathrm{err}}(f)>ϵ\\ 0& \text{otherwise}\end{array}$$

其中$f$表示最优聚类假设，即：

​ f = a r g m i n g ∈ { − 1 , + 1 } n P e r r ( g ) f=\mathrm{argmin}_{g\in\{-1,+1\}^n}P_{\mathrm{err}}(g) f=argming∈{−1,+1}n​Perr​(g)

接下来，我们定义两个独立的随机变量序列$X_1^1,X_2^1,\dots ,X_n^1$和$X_1^2,X_2^2,\dots ,X_n^2$，它们分别表示假设$f^1$和$f^2$在两个视角上的聚类结果是否相同。

每个随机变量的取值为$0$或$1$，其中$1$表示相同，$0$表示不相同。

然后，定义：

​ $$X_i^j=\{\begin{array}{ll}1& \text{if }{y}_i^1=y_i^2\\ 0& \text{otherwise}\end{array}$$

利用Hoeffding不等式来估计随机变量$X_i^j$的样本平均值与其期望之间的差异。根据Hoeffding不等式，对于任意$ϵ>0$，有：

​ $$P\left(\left|\frac{1}{n}\sum _{i=1}^n{X}_i^j-\mathbb{E}[X_i^j]\right|>ϵ\right)\le 2\exp (-2n{ϵ}^2)$$

注意到$\mathbb{E}[X_i^j]=P(y_i^1=y_i^2)$，这个概率可以通过样本外估计得到。

事实上，假设从分布$D$中采样$m$个独立同分布的数据点$(x_1,y_1),\dots ,(x_m,y_m)$构成验证集$V=\{(x_1,y_1),\dots ,(x_m,y_m)\}$，则相同的概率可以估计为：

​ $$\hat{P}(y_i^1=y_i^2)=\frac{1}{m}\sum _{i=1}^{m}1(y_i^1=y_i^2)$$

在估计$\hat{P}(y_i^1=y_i^2)$时，通过将训练得到的聚类结果应用到验证集$V$上来进行。

具体来说，对于每一个数据点$(x_i,y_i)\in V$，我们选择$f^1(x_i)$和$f^2(x_i)$中相同的那一个作为其聚类结果，然后计算相同的数据点占比。

注意到由于是将训练得到的聚类结果应用到验证集上，因此估计出来的$\hat{P}(y_i^1=y_i^2)$实际上是有偏的（即估计结果的期望不等于真实值），但是可以证明这个偏差是可以控制的。

不难发现，当$n$充分大时，两个随机变量序列的样本平均值与其期望之间的差异会逐渐变小，即$\left|\frac{1}{n}{\sum }_{i=1}^n{X}_i^j-\mathbb{E}[X_i^j]\right|$的概率收敛于$0$。

同时，当训练误差与最优误差之差$\Delta =P_{\mathrm{err}}(f_S)-P_{\mathrm{err}}(f)$大于$ϵ$时，指示器函数$I(S)$的取值为$1$，否则为$0$。因此，我们可以将一致性不等式表示为：

​ $$P(X-f^1\ne X-f^2)\ge \max \left\{\frac{1}{2}\exp (-2n{ϵ}^2)-\Delta ,P_{\mathrm{err}}(f^1)-P_{\mathrm{err}}(f^2)-2ϵ\right\}$$

其中$\Delta =P_{\mathrm{err}}(f_S)-P_{\mathrm{err}}(f)$表示训练误差与最优误差之差，$ϵ$是控制误差幅度的常数。这个不等式就是我们想要证明的一致性不等式。