GEOMETRICAL AND STATISTICAL PROPERTIES OF SYSTEMS OF LINEAR INEQUALITIES WITH APPLICATIONS IN PATTERN RECOGNITION
GEOMETRICAL AND STATISTICAL PROPERTIES OF SYSTEMS OF LINEAR INEQUALITIES WITH APPLICATIONS IN PATTERN RECOGNITION
复制标题
DOI：
10.1109/pgec.1965.264137
复制
发表时间：
1965-01-01
期刊：
影响因子：
--
通讯作者：
COVER, TM
中科院分区：
文献类型：
--
作者：
COVER, TM
本文直接应用经典组合几何中的一个定理，发展了一类非线性决策曲面族的分离能力。证明了具有d个自由度的曲面族具有2维模式向量的自然分离能力，从而推广和统一了Winder等人关于超平面模式分离能力的结果。将这些思想应用到二元n立方体的顶点上，可以得到球面上、二次上和一般情况下的n个变量的非线性可分布尔函数的个数的界限。结果表明，将无限的、随机的、可分的模式向量集分开的所有曲面的集合，平均而言可以用仅有2维极端模式向量的子集来刻画。此外，定义了将已标记的模式点集上的分类推广到新的点分类的问题，发现除非训练模式的数量超过分离面集的容量，否则模糊泛化的概率很大。
This paper develops the separating capacities of families of nonlinear decision surfaces by a direct application of a theorem in classical combinatorial geometry. It is shown that a family of surfaces having d degrees of freedom has a natural separating capacity of 2d pattern vectors, thus extending and unifying results of Winder and others on the pattern-separating capacity of hyperplanes. Applying these ideas to the vertices of a binary n-cube yields bounds on the number of spherically, quadratically, and, in general, nonlinearly separable Boolean functions of n variables. It is shown that the set of all surfaces which separate a dichotomy of an infinite, random, separable set of pattern vectors can be characterized, on the average, by a subset of only 2d extreme pattern vectors. In addition, the problem of generalizing the classifications on a labeled set of pattern points to the classification of a new point is defined, and it is found that the probability of ambiguous generalization is large unless the number of training patterns exceeds the capacity of the set of separating surfaces.