对分（Dichotomy）、增长函数（Growth Function）、突破点（Break Point）、VC维（Vapink-Chervonenkis Dimension）是计算学习理论中非常重要的概念，也是机器学习的基石。可以说如果不理解计算学习理论，那就不能从根本上理解机器学习。

机器学习最基本的问题是二分类和回归，在这里我们讨论的是二分类的问题。我们知道有很多二分类的模型，我们把这些模型称为分类器，常见的分类器有下面几种：

详情可以参考《快乐机器学习》这本书，或者林轩田老师的机器学习基石课程。

如果一种操作能把正负样点线性分开，我们就把这种操作称为对分。一种对分其实就是线性二分类的一种分类方式。一种模型可以有若干种对分方式。我们把模型能产生对分的种类的数量定义为这种分类器的增长函数。增长函数和样本点的数量有关系，显然，样本点越多，对分的方式越多，增长函数就越大。直观上，我们感觉有 n n n个点，就有 2 n 2^n 2n中对分方式，因为对于二分类，每个点有2中可能的取值，总共有 2 n 2^n 2n中组合总数。但是实际上，很多组合是线性不可分的，因此真实情况下，在n比较小的时候，能满足增长函数等于 2 n 2^n 2n；随着n增大，增长函数将小于 2 n 2^n 2n。

常见的二分类问题增长函数如下表所示： 以一维感知机为例我们可以用下图表示增长函数 d h ( n ) d_h(n) dh​(n)和指数函数 f ( n ) f(n) f(n)之间的关系。 我们可以看到，在 n < = 2 n mK(N)