Discovering the Relationship between Generalization and Uncertainty by Incorporating Complexity of Classification

The generalization ability of a classifier learned from a training set is usually dependent on the classifier's uncertainty, which is often described by the fuzziness of the classifier's outputs on the training set. Since the exact dependency relation between generalization and uncertainty of a classifier is quite complicated, it is difficult to clearly or explicitly express this relation in general. This paper shows a specific study on this relation from the viewpoint of complexity of classification by choosing extreme learning machines as the classification algorithms. It concludes that the generalization ability of a classifier is statistically becoming better with the increase of uncertainty when the complexity of the classification problem is relatively high, and the generalization ability is statistically becoming worse with the increase of uncertainty when the complexity is relatively low. This paper tries to provide some useful guidelines for improving the generalization ability of classifiers by adjusting uncertainty based on the problem complexity.