有关级联分类器的一些事实，在科学文章中很少认真考虑。

哈勃！今天，我们将再次讨论认可。即，关于诸如级联分类器的简单识别器模型。该级联被用于Viola和Jones的流行方法中，他们已经在Habré上写过很多次（例如，here，here和here）。可悲的是，尽管文章很多，但没人认真研究级联分类器。不仅在哈布雷（Habré），而且在科学界。尽管级联分类器看起来很简单，但仍有很多陷阱和有趣的功能。因此，我们很想与您分享我们的知识。所以，如果有兴趣，欢迎来猫。

级联分类器是一个非常简单的模型。它由几个连续的级别组成，每个级别都可以表示为一个二进制分类器。被调查的先例被馈送到第一级的输入，然后逐级“旅行”。如果分类器在下一级别将先例识别为否定词，则级联的其余分类器将不再对其进行分析。这种简单的模型在Viola and Jones方法[1]出版后变得很流行，如上所述，该模型用于提供高性能。但这仅仅是为了这个吗？它只是一个级联分类器吗？让我们弄清楚！

我们将以对我们来说新的格式在Habré上构建今天的文章。我们将选择一些陈述，这些陈述将详细揭示甚至在某处进行反驳。因此，让我们开始吧！

Viola and Jones方法中的级联分类器仅用于加速对象检测器的操作

在第一页的原始文章[1]中，有这样一个短语：

本文的第三个主要贡献是一种在级联结构中连续组合更复杂的分类器的方法，该方法通过将注意力集中在图像的有希望的区域上来显着提高检测器的速度。

的确，Viola和Jones的原始方法旨在搜索图像中的对象。此外，通过使用二元分类器的滑动窗口方法解决了检测问题，该二元分类器以不同的比例应用于研究图像的每个点。在检测阶段所研究数据的不平衡（在研究的每个图像中没有所需对象的“空”区域，比带有对象的区域多数百万甚至数十亿倍）促使使用级联-一种机制，可让您快速切断“空”区域。

但这是关于使用已经训练有素的分类器。现在转到分类器训练过程。事实证明，样本失衡存在着完全相同的问题：否定示例的数量比肯定示例的数量大很多倍（数百万甚至数十亿倍）。但是由于其体系结构，级联的每个新级别都通过AdaBoost方法进行了训练，而不是在整个负面训练样本中进行训练，而仅在级联先前级别的有限错误中进行了训练！这使您可以在均衡且有限的样本上运行AdaBoost训练机！

如您所见，在Viola和Jones方法中使用级联分类器会发生两次：

1. 它使您可以轻松地训练分类器，自然避免了“无限”训练集的问题；
2. 它可以在物体检测期间快速裁剪“空白”区域，从而实现较高的平均生产率。

好吧，让我们继续研究经典的层叠，然后转向性能问题。

考虑到这一点，级联分类器是一种加速工具。

让我们再次回到级联目的的问题，但另一方面。如果从数学上看级联分类器，您会发现级联是强分类器的联合形式（每个分类器都可以表示为线性的属性组合）：

$$

$$Cascade\left(x\right)=\prod_{i=1}^{N}\left[S_i\left(x\right)>0\right], \\ S\left(x\right)=\left[\sum_{t=1}^{T}{\alpha_t\cdot h_t\left(x\right)}>0\right],$$

哪里 $$$\left[\bullet\right]$-指示器功能。

在可用属性数量有限的情况下（实际上，在追逐性能时，这通常是正常情况），强分类器的合取形式比单个线性分类器具有更大的表达能力。如果您想象一个简单的示例，即特征空间由两个元素组成，并且以这些特征的坐标表示的正负对象位于下图（绿色对象为正对象，红色对象为负对象），则这很容易理解。显然，没有这样的线性分类器可以正确地划分此样本。但是，由四个级别组成的级联将可以保证完成此任务。


因此，在有限数量的特征条件下，除了提高生产率之外，级联分类器的使用还提供了比单个线性分类器更大的表达能力。

级联分类器可提供始终如一的高性能，可轻松用于实时识别系统

如上所述，由于“空”区域的快速筛选，级联方案使您可以实现高性能，因为它们的数量比包含对象的区域的数量大几个数量级。 “空”区域的处理时间与带有物体的区域的处理时间相差数倍（与级联的长度-级联的数量成比例）。

由于包含对象的区域的数量因图像而异，因此每帧的处理时间也不同。由于帧上带有对象的区域比没有对象的区域少得多的事实，因此测量的处理时间差异不是数十倍，而是百分之几十，这在工业识别系统中还是很重要的。

因此，级联分类器在不同图片中的操作时间可能会显着变化。因此，当对分类器的性能进行认真的测量时，应平均和最坏的情况下对运行时间进行测量。使用级联分类器时，请始终为此类暂时的“不一致”做好准备。

在我们的实践中，由于平均和最坏情况下级联操作时间的显着差异，我们已经面临严重的问题。作为收费公路自动化项目的一部分，我们解决了识别汽车类型的问题，其中主要的子任务之一是对轮对计数的问题。当然，我们使用Viola和Jones方法检测单个框架上的车轮。由于车轮的可变性很大（请参见下图），训练有素的级联相当长（20个级别）。我们观看了与每个帧的不同处理时间相关的现场令人不快的问题，这严重地阻止了我们实时构建识别系统。


然后我们将经典的级联分类器的想法发展为成熟的决策树，为这种决策树开发了独特的学习技术（请记住有必要提出一种算法来使我们避免与``无尽''训练集相关的问题）。该算法的细节可以在我们的科学工作中找到[3]。在这里，我们只报告一些事实：

1. 训练树中最长的路径由6个强分类器组成（训练树分类器的方案如下图所示）。
2. 与先前训练的级联相比，训练有素的树分类器提供了更好的工作质量。这是合乎逻辑的，并且是基于这样的事实，即树状级联的表达能力（合取-分离的形式）高于级联的表达能力（合取形式）。
3. 在最坏的情况下，训练有素的树分类器严重地绕过了级联，几乎没有平均损失。

下表列出了级联和树分类器的数值比较。


因此，如果您真的想在识别系统中实时使用级联分类器，那么请务必记住与平均和最坏情况下的工作速度相关的功能。

级联的分类器训练技术是如此明显，以至于没有什么值得严重困扰的。

哦，这可能是与级联分类器相关的最困难的主题之一。最重要的是，在我们遇到的所有文章中，对级联学习过程的描述如此粗糙，肤浅，并且没有适当证明级联学习算法的有效性。通常，级联学习算法如下所示：

1. 确定错误识别所占份额的价值（$$$F$）用于整个级联。
2. 确定真实认可份额的价值（$$$d$）和错误识别的分数（$$$f \lt F$）的每个识别级别。
3. 确定验证样本以诚实评估最终分类器的质量指标。
4. 训练级联的每个新级别（我们记得，已针对所有可用的肯定示例以及当前级联的假阳性错误进行了训练），以便其性能 $$$d_i$和 $$$f_i$没有比给出的更糟，那就是 $$$d_i>d$和 $$$f_i \lt f$。顺便说一下，确保这些指标本身的过程也引起了极大的兴趣。
5. 将新训练的水平添加到级联中，并在验证样本中评估其质量指标。如果错误识别率小于目标$$$F$，然后完成训练。否则，请转到步骤4以学习新的级联。

如果由于上述算法的训练 $$$K$级联，那么您可以估算出正确识别级联所占份额的平均复杂度，如下所示：

$$

$$N=n_1+\sum_{i=2}^{K}\left(n_i\prod_{j=2}^{i}p_j\right),\\ D=\prod_{i=1}^{K}d_i,$$

哪里 $$$n_i$-复杂性 $$$i$级联水平 $$$p_i$-计算概率 $$$i$级别级联，以及 $$$d_i$-分享正确的认可 $$$i$级联。

如您所见，级联的复杂性不参与所提出的训练算法，因此，当然不能称其为有效性能。同时，我们可以肯定的是，全世界的科学家都坚信学习算法对于有效级联的重要性，以下是Paul Viola和Michael Jones [4]的一篇文章的引用：

The overall training process involves two types of tradeoffs. In most cases classifiers with more features will achieve higher detection rates and lower false positive rates. At the same time classifiers with more features require more time to compute. In principle one could define an optimization framework in which
– the number of classifier stages,
– the number of features, $$$n_i$, of each stage,
– the threshold of each stage
are traded off in order to minimize the expected number of features $$$N$given a target for $$$F$and $$$D$. Unfortunately finding this optimum is a tremendously difficult problem.

有趣的是，我们在2016年对相关文献的回顾表明，当时没有适用于级联分类器的有效训练算法。顺便说一句，那时Smart Engines解决了这个问题。我们研究了以下功能，具体取决于第一类检测错误（$$$E_1$），第二种检测错误（$$$E_2$）和中等难度（$$$N$）：

$$

$$F\left(E_1,\ {\ E}_2,\ N\right)=\ {\ \beta_1\cdot\ E}_1+\ \beta_2\cdot E_2+\ \ \beta_3\cdot N.$$

参数选择 $$$\beta_1$， $$$\beta_2$和 $$$\beta_3$，设置第一类和第二类错误的相对成本以及所得检测器的复杂性。此外，在训练级联分类器的过程中，使用贪婪算法来枚举每个级别的参数，以获得使所选功能最大化的级联。对已开发算法的详细描述超出了本文的范围，但是我们始终可以通过提供书目链接[5]与您（我们的读者）共享该算法。

结论

总结一下我们所说的一切，以级联分类器模型为例，我们想得出以下结论：

1. 几乎不可能完成将所有必要细节都完整描述的科学工作。
2. 重新阅读科学文章，认真考虑其中提出的模型的性质和局限性，这非常有用，即使乍一看似乎文章中的所有内容都是“咀嚼的”。
3. 即使研究模型是20年前提出的，也总会有值得进行科学研究的地方。

如果本文中提供的材料有用，并且我们随时准备在评论中进行富有成果的讨论，我们将感到非常高兴。

谢谢。