A New VC Dimension Based on Probability

Abstract

This paper proposes a new definition of VC dimension based on probability. The VC dimension is the most important parameter to evaluate the learning ability of a hypothesis set. However, in many actual problems, the origin VC dimension is always too large to use. And there always exists a paradox between the size of hypothesis set and the range of confidence interval. This paper solves these problems by taking the information of data set and probability into consideration. We propose a new definition of VC dimension based on probability and gives a stronger VC bound.