| We propose an automatic feature discovery method that helps solve the feature identification problem: given samples described by a large number of original features, find a series of features that are linear combinations of the original features so that the error rate is reduced. We assume a "data-rich" problem domain: we have access to an indefinitely large number of labeled samples. We use error clusters to guide the search. Our algorithm proceeds as follows: given a small number of features, find clusters of errors and project one tight error cluster into the null space of the current feature mapping. In the null space, find a separating hyperplane for the samples in the error cluster and accept this as the new feature. We conduct large scale experiments using Linear Discriminant Analysis to find separating hyperplanes in a document image content extraction framework. We use four manual features to initialize the algorithm, and the algorithm proceeds to find an additional ten. These 14 features achieve an error rate of 13.8%, nearly matching a set of 28 manually chosen features with an error rate of 13.6%. The 14 features also outperform a Principal Component Analysis-chosen set with 14 features and an error rate of 15.4%. We prove a sufficient condition: if the data is Gaussian distributed with equal covariance matrices for both classes, the Bhattacharyya bound is guaranteed to decrease. Thus we conclude that our algorithm can be competitive with both PCA and manual search. |
