The capacity of monotonic functions

✍ Scribed by Joseph Sill

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 897 KB
• Volume: 86
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(98)00016-x

✦ Synopsis

We consider the class M of monotonically increasing binary output functions. M has considerable practical significance in machine learning and pattern recognition because prior inform&ion often suggests a monotonic relationship between input and output variables. The decision boundaries of monotonic classifiers are compared and contrasted with those of linear classifiers. M is shown to have a VC dimension of DC), meaning that the VC bounds cannot guarantee generalization independent of input distribution. We demonstrate that when the input distribution is taken into account, however, the VC bounds become useful because the annealed VC entropy of M is modest for many distributions. Techniques for estimating the capacity and bounding the annealed VC entropy of M given the input distribution are presented and implemented.