The Nonpolynomiality of the Number of Similarities for Random Training Sets

In this paper an additional argument is provided in favor of the probabilistic approach to knowledge extraction using the similarity operation (the VKF method) through the nonpolynomiality of the number of all candidates. More specifically, two results about such nonpolynomiality are proved for random training sets generated by Bernoulli trials. In the case of dense lattice, it is proved that the probability of appearance of a large sublattice that is isomorphic to Boolean algebra in the lattice of candidates tends to unity as the size of the set increases. For a lattice of medium density, a slightly modified Sakurai’s argument about the nonpolynomiality of the mean number of candidates is reproduced.