在没有测试集的情况下计算测试误差
在没有测试集的情况下计算测试误差
Computing the Testing Error without a Testing Set
摘要
深度神经网络（DNN）彻底改变了计算机视觉。 现在，我们的DNN在许多问题上都取得了最佳的（性能）结果，其中包括目标识别，面部表情分析和语义分割等。 然而，实现最佳结果的DNN的设计并非易事，而且大多是通过试错来完成的。 也就是说，研究人员通常会设计许多DNN的架构（即拓扑），然后在多个数据集上对其进行测试。 但是，不能保证所选的DNN在实际应用中会表现良好。 可以使用测试集来估计训练集和测试集之间的性能差距，但是要避免过度拟合测试数据几乎是不可能的。 使用隔离的测试集可能会解决此问题，但这需要不断更新数据集，这是一项非常昂贵的尝试。在这里，我们推导出了一种算法，用于估计不需要任何测试集的训练和测试之间的性能差距。 具体来说，我们推导出了许多持久性拓扑度量，这些度量可确定何时DNN可以学习推广到看不见的样本。这样，即使我们无法访问这些样本，我们也可以计算出DNN的测试误差。 我们在多个网络和数据集上提供了大量的实验验证，以证明该方法的可行性。
1. 引言
深度神经网络（DNN）是能够识别输入变量 x x x和输出变量 y y y之间的复杂非线性映射 f ( . ) f(.) f(.)的算法，即 f ( x ) = y f(x)=y f(x)=y。 每个DNN由其独特的拓扑和损失函数定义。
给定一个精心策划的数据集，其中包含 n n n个样本， X = { x i , y i } n i = 1 X = \{x_i,y_i\}_ n^{i= 1} X={xi,yi}ni=1，我们可以使用DNN查找函数映射 f ( x i ) = y i f(x_i)=y_i f(xi)=yi的估计。 让我们将估计的映射函数称为 f ^ ( . ) \hat{f}(.) f^(.)。 当使用不同的DNN和数据集时，将获得不同的估计值 f ^ j ( . ) \hat{f}_j(.) f^j(.)。
使用诸如此类的数据集来训练DNN很有成果。 直到最近，DNN在无数艰巨的任务中都取得了相当大的进步。
不幸的是，当使用独立的，看不见的图像时，我们通常不知道估计的映射函数 f ^ j ( . ) \hat{f}_j(.) f^j(.)在实际应用中将如何执行。
解决此问题的经典方法是使用一个测试集，图1（a，底部）。 这种方法的问题在于，在许多情况下，测试集对我们是可见的，因此，我们一直在修改DNN的拓扑，直到它在该测试集上起作用为止。 这意味着我们过度拟合了测试数据，并且通常来说，对于真正看不见的样本，我们的算法可能不是最佳算法。
图1：（a）我们不使用任何测试样本在任何计算机视觉问题上计算任何深度神经网络（DNN）的测试性能1（顶部）; 标记和未标记的样本都是没有必要的。 这与传统计算机视觉方法形成鲜明对比，传统计算机视觉方法使用选定的测试数据集（底部）来计算模型性能。 （b）我们的算法（x轴）针对训练与测试性能（y轴）之间的性能差距∆ρ给出的持久代数拓扑概要（ The persistent algebraic topological summary）
(
λ
∗
,
µ
∗
)
(λ^∗,µ^ ∗)
(λ∗,µ∗)。
要解决此问题，我们可以使用隔离（sequestered）的数据集。这意味着第三方拥有一个我们从未见过的测试数据集，而我们只能知道我们每几个月对该数据集执行一次的性能如何。 虽然这确实告诉我们我们的算法在以前看不见的样本上的性能如何，但我们只能偶尔获得此估计。而且，重要的是，我们需要依靠其他人来维护和更新此隔离测试集。 许多这样的隔离数据集不会持续很长时间，因为维护和更新它们是一项非常昂贵的工作。
在本文中，我们介绍一种解决这些问题的方法。 具体来说，我们推导了一种算法，该算法可以准确估计我们的训练和测试错误之间的性能差距，而无需任何测试数据集，图1（a，顶部）。 这意味着我们无需访问任何带标签或未带标签的数据。 相反，我们的算法将为您提供在独立的，看不见的样本的DNN性能的准确估计。
我们的关键思想是获得一组拓扑概要，这些概要测量跨计算机视觉问题的DNN属性的持久拓扑图。 持久拓扑已被证明与分类中的泛化误差相关，并且是理论上研究和解释DNN属性的一种方法。 我们提出的假设是，泛化误差是网络内部工作的函数，此处由网络的功能拓扑表示并通过拓扑概要进行描述。 我们建议对这个函数进行回归，并仅在训练数据上评估测试性能。
图1（b）展示了一个例子。 在此图中， x x x轴显示了DNN的持久拓扑度量的线性组合。 此图中的 y y y轴是在多个计算机视觉问题上使用这些DNN时的性能差距。 从该图中可以看出，我们提出的拓扑概要与DNN的性能差距之间存在线性关系。 这意味着了解我们的拓扑概要的价值与了解DNN在隔离的数据集上的性能一样好，但没有上述任何缺点–无需依赖独立的团队来收集，管理和更新测试集。
我们从一组在DNN上执行的持久性拓扑度量的推导开始（第2节），然后使用它来推导我们的算法（第3节）。 我们讨论了有关DNN和计算机视觉问题的相关工作（第4节）和大量的实验评估，包括目标识别，面部表情分析和语义分割（第5和第6节）。
2. 拓扑概要
DNN的特征是结构（即定义和训练计算图的方式）及功能（即其组件在特定输入下的实际响应）。 我们将重点放在后者上。
为此，我们在拓扑空间上定义DNN。 然后计算该空间的一组精简的描述符，称为拓扑概要，它们是度量网络特性的重要参数。 例如，一个网络功能拓扑的一个概要可用于检测过度拟合并执行早停。
设 A A A为一个集合。 一个抽象的简单复合体 S S S是表示 V ( A ) V(A) V(A)的顶点的集合，以及称为单形的 V ( A ) V(A) V(A)的子集集合，这些单形在子集操作下是封闭的，即，如果 σ ∈ ψ σ∈ψ σ∈ψ和 ψ ∈ A ψ∈A ψ∈A，则 σ ∈ A σ∈A σ∈A。
一个单形 σ σ σ的维数是 ∣ σ ∣ − 1 |σ| −1 ∣σ∣−1，其中 ∣ ⋅ ∣ |·| ∣⋅∣表示基数。 尺寸为 n n n的单形称为一个n-单形。一个0单形由单个顶点实现，一个1单形由连接两个顶点的线段（即边）实现，一个2单形是连接三个顶点的实心三角形，依此类推。
令 M = ( A , ν ) M=(A,ν) M=(A,ν)表示一个度量空间-集合 A A A与度量 ν ν ν的关联。给定距离 ϵ \epsilon ϵ，VietorisRips复形是一个抽象的简单复合体，它包含由所有成对的元素 a i , a j ∈ A a_i,a_j∈A ai,aj∈A所组成的所有单形
ν ( a i , a j ) < ϵ (1) \nu\left(a_{i}, a_{j}\right)<\epsilon\tag{1} ν(ai,aj)<ϵ(1)
对于一些小的 ϵ > 0 \epsilon>0 ϵ>0，并且 i ≠ j i\neq j i=j。
通过考虑一系列可能的距离， { ϵ 0 , ϵ 1 , … ϵ k , … ϵ n } \left\{\epsilon_{0}, \epsilon_{1}, \ldots \epsilon_{k}, \ldots \epsilon_{n}\right\} {ϵ0,ϵ1,…ϵk,…ϵn}，其中 0 < ϵ 0 ≤ ϵ 1 ≤ ⋯ ≤ ϵ k ≤ ⋯ ≤ ϵ n 0<\epsilon_{0} \leq \epsilon_{1} \leq \cdots \leq \epsilon_{k} \leq \cdots \leq \epsilon_{n} 0<ϵ0≤ϵ1≤⋯≤ϵk≤⋯≤ϵn，Vietoris-Rips过滤产生一个简单复合体的集合， S = { S 0 , S 1 , … , S k , … , S n } \mathcal{S}=\left\{S_{0}, S_{1}, \ldots, S_{k}, \ldots, S_{n}\right\} S={S0,S1,…,Sk,…,Sn}，在图2所示的多个规模上。
图2 给定一个度量空间，Vietoris-Rips滤波通过连接比预定义距离
ϵ
\epsilon
ϵ更近的点来创建简单复形的嵌套序列。通过变化
ϵ
\epsilon
ϵ，我们计算这些单子中的持久性（腔）。我们在一个这样的拓扑空间中定义了一个DNN，以计算其特性的信息性数据，该特性与其在测试数据上的性能相关。
我们对这些复形在不同规模上的持久拓扑特性感兴趣。 为此，我们计算了 p t h p^{th} pth-持久同构群（persistent homology groups）和Betti数 β p β_p βp，这给了我们这些群的排序。这意味着Betti数可计算一个拓扑对象的腔数。2
在DNN中，例如，我们可以研究其功能拓扑在训练过程中的变化，如图3所示。 首先，我们计算DNN中在每一个迭代周期中每个节点与其他节点之间的相关性。 即使网络的计算图中没有实际的边或路径连接，也将高度相关的节点（即它们的相关性高于阈值）定义为已连接。 这些连接定义了一个具有多个腔体的简单复合体。这些腔由Betti数给出。 我们知道，低维Betti数（即 β 1 β_1 β1和 β 2 β_2 β2）的动态对于偏差-方差问题（即泛化与记忆问题）是有益的。 类似地，已经表明，这些持久性同构度量可用于将数据作为功能空间中的点进行研究和解释，从而有可能学习和优化定义在数据上的估计 f j ( . ) f_j(.) fj(.)。
图3 从DNN计算拓扑概要的概述。 我们首先定义网络中的一组节点
A
A
A。 通过计算这些节点之间的相关性，我们将网络投影到度量空间
(
A
,
ν
)
(A,ν)
(A,ν)中，通过Vietoris-Rips过滤从拓扑空间中获得一组简单复合体。 在这组简单复合体上的持久同构性会导致一个持久图，可以从中直接计算拓扑度量。
3. 算法
召回 X = { x i , y i } i = 1 n \mathcal{X}=\left\{\mathbf{x}_{i}, \mathbf{y}_{i}\right\}_{i=1}^{n} X={xi,yi}i=1n是标记训练样本的集合，样本数为 n n n。
令 a i a_i ai是DNN中特定输入 x i x_i xi的特定节点的**值。 将样本向量 x i x_i xi通过网络 ( i = 1 , … , n ) (i=1, \ldots, n) (i=1,…,n)传递，使我们能够计算每对节点的** ( a p , a q ) (a_p,a_q) (ap,aq)之间的相关性，这定义了我们的Vietoris-Rips复合体的度量 ν ν ν。公式地，
ν p q = ∑ i = 1 n ( a p i − a p ‾ ) ( a q i − a q ‾ ) ζ a p ζ a q (2) \nu_{p q}=\sum_{i=1}^{n} \frac{\left(a_{p i}-\overline{a_{p}}\right)\left(a_{q i}-\overline{a_{q}}\right)}{\zeta_{a_{p}} \zeta_{a_{q}}}\tag{2} νpq=i=1∑nζapζaq(api−ap)(aqi−aq)(2)
其中， a ‾ \overline{a} a和 ζ a \zeta_{a} ζa指的是 X \mathcal{X} X上的均值和标准差。
我们使用持久图表示持久同构性的结果。 在我们的持久性图中，每个点具有一组成对的正实数 P = { ( ϵ d i , ϵ b i ) ∣ ( ϵ d i , ϵ b i ) ∈ R × R , i = 1 , … C } P=\left\{\left(\epsilon_{d}^{i}, \epsilon_{b}^{i}\right) \mid\left(\epsilon_{d}^{i}, \epsilon_{b}^{i}\right) \in \mathbb{R} \times \mathbb{R}, i=1, \ldots C\right\} P={(ϵdi,ϵbi)∣(ϵdi,ϵbi)∈R×R,i=1,…C}，其中 ϵ \epsilon ϵ的下标 b b b和 d d d表示Vietoris-Rips过滤中空腔 i i i的生死距离， C C C是空腔总数。
一个度量空间 ( A , ν ) (A,ν) (A,ν)的过滤是遵循以下规则的复合体的嵌套子序列： S 0 ⊆ S 1 ⊆ ⋯ ⊆ S n = S S_{0} \subseteq S_{1} \subseteq \cdots \subseteq S_{n}=\mathcal{S} S0⊆S1⊆⋯⊆Sn=S。 因此，这种过滤实际上是定义 k k k维同构组的持久图的原因。 这是通过计算 k k k维同构性特征的创建和删除来完成的。 反过来，这使我们能够计算寿命同构特征（lifespan homological feature）。
基于此持久性图，我们将腔的生命定义为该图中的平均时间（即持久性）。公式地，
λ
=
1
C
∑
i
=
1
C
(
ϵ
d
i
−
ϵ
b
i
)
(3)
\lambda=\frac{1}{C} \sum_{i=1}^{C}\left(\epsilon_{d}^{i}-\epsilon_{b}^{i}\right)\tag{3}
λ=C1i=1∑C(ϵdi−ϵbi)(3)
同样，我们将其中年定义为持久性的平均密度。 公式地，
μ
=
1
C
∑
i
=
1
C
ϵ
d
i
+
ϵ
b
i
2
(4)
\mu=\frac{1}{C} \sum_{i=1}^{C} \frac{\epsilon_{d}^{i}+\epsilon_{b}^{i}}{2}\tag{4}
μ=C1i=1∑C2ϵdi+ϵbi(4)
最后，我们定义了从这些拓扑概要到训练误差与测试误差之间的差值的线性函数映射，
g
(
λ
,
μ
;
c
)
=
Δ
^
ρ
(5)
g(\lambda, \mu ; \mathbf{c})=\widehat{\Delta} \rho\tag{5}
g(λ,μ;c)=Δ
ρ(5)
其中
Δ
^
ρ
\widehat{\Delta} \rho
Δ
ρ是我们对训练和测试误差之间差值的估计，
g
(
λ
,
μ
;
c
)
=
c
1
λ
+
c
2
μ
+
c
3
g(\lambda, \mu ; \mathbf{c})=c_{1} \lambda+c_{2} \mu+c_{3}
g(λ,μ;c)=c1λ+c2μ+c3，其中
c
i
∈
R
+
c_{i} \in \mathbb{R}^{+}
ci∈R+，而且
c
=
(
c
1
,
c
2
,
c
3
)
T
\mathbf{c}=\left(c_{1}, c_{2}, c_{3}\right)^{T}
c=(c1,c2,c3)T，如图1(b)所示。
根据以上结果，我们可以估算出测试误差，而无需任何测试数据，即
ρ
^
test
=
ρ
train
−
Δ
^
ρ
(6)
\hat{\rho}_{\text {test}}=\rho_{\text {train}}-\widehat{\Delta} \rho\tag{6}
ρ^test=ρtrain−Δ
ρ(6)
其中
ρ
train
\rho_{\text {train}}
ρtrain是在训练
X
\mathcal{X}
X期间计算的训练误差。
给定一个实际的测试数据集
Z
=
{
x
i
,
y
i
}
n
+
1
m
\mathcal{Z}=\left\{\mathbf{x}_{i}, \mathbf{y}_{i}\right\}_{n+1}^{m}
Z={xi,yi}n+1m，我们可以计算出我们估计的测试误差的精度，即
Error
=
∣
ρ
test
−
ρ
^
test
∣
(7)
\text { Error }=\left|\rho_{\text {test}}-\hat{\rho}_{\text {test}}\right|\tag{7}
Error =∣ρtest−ρ^test∣(7)
其中， ρ test \rho_{\text {test}} ρtest是在 Z \mathcal{Z} Z上计算的测试误差。
提出算法的伪代展示在算法1中。
3.1 算法复杂度
令二项式系数 p = ( N + 1 n + 1 ) p=\left(\begin{array}{l}N+1 \\ n+1\end{array}\right) p=(N+1n+1)是一个简单复形 S S S的 n n n个单形的数量（例如，在图2中所示的Vietoris-Rips滤波过程中生成的）。 为了计算 S S S上 n n n阶的持久同构性，必须计算 rank ( ∂ n + 1 ) \operatorname{rank}\left(\partial_{n+1}\right) rank(∂n+1)，其中 ∂ n + 1 ∈ R p × q \partial_{n+1} \in \mathbb{R}^{p \times q} ∂n+1∈Rp×q， p p p是n单形的数量， q q q是 ( n + 1 ) (n+1) (n+1)-单形的数量。 这具有多项式复杂度 O ( q a ) , a > 1 O\left(q^{a}\right), a>1 O(qa),a>1。
幸运的是，在算法1中，我们只需要计算一阶的持久同构性。 另外，由Vietoris-Rips过滤产生的简单复合体通常非常稀疏。 这意味着对于典型的DNN， n n n-单形的数量远低于上面定义的二项式系数。 实际上，我们发现10,000是 A A A的基数的合理上限。这是因为我们通过考虑DNN的拓扑结构约束来定义节点。具体而言，一个节点 a i a_i ai是一个随机变量，其值等于其对应卷积层中滤波器的平均输出。 具有随机变量使我们能够在算法1中定义相关性和度量空间。 根据经验，我们发现以这种方式定义节点是鲁棒的，并且具有类似的特性，例如。 即使随机选择了一个滤波器子集，也可以找到高相关性。 对于较小的玩具网络，以前的证据支持以这种方式定义的功能拓扑对于确定DNN中的过拟合是有益的。
最后，对于我们分析中最广泛的网络之一VGG16，计算持久同构性和拓扑概要 λ λ λ和 µ µ µ所需的时间分别为5分钟15秒。 这对应于算法1的单次迭代（迭代 k k k次的for循环），不包括训练，在单个2.2 GHz Intel Xeon CPU上进行的时间。
-
令 ρ t r a i n ρ_{train} ρtrain和 t e s t _{test} test分别是使用训练和测试集计算的算法的性能； ρ ^ t e s t \hat{ρ}_{test} ρ^test是在没有任何测试数据的情况下计算出的估计测试误差。 性能指标可以是分类精度，F1得分，交并比（IoU）等。 ↩︎
-
如果两个对象在每个维度上都具有相同数量的腔（孔），则它们在拓扑上是等效的。 例如，一个甜甜圈和一个咖啡杯在拓扑上是等效的，因为它们都有一个二维腔，一个是在甜甜圈的整体和另一个是在杯子的手柄中。另一方面，圆环（定义为两个圆的乘积， S 1 × S 1 S^1×S^1 S1×S1）具有两个孔，因为它是空心的。 因此，圆环在拓扑上不同于甜甜圈和咖啡杯。 ↩︎