What happens when there are a lot of features

For discriminative structural prediction, the system might have quite a lot of feature templates. Do more features increase overfitting, or do they reduce the accuracy given limited training data because they make the model harder to converge? This appears to be an interesting research question.

I doubt whether the maximum entropy (log-linear) methods and the perceptron algorithm will be the same, but my work has been primarily focused on the perceptron learning.

I have two observations:
1. Some preliminary results by online learning show that more features can reduce the accuracy on the first training iteration, but "catch up" with more iterations.
2. When the number of features reach certain levels, additional features will not help further improve the accuracy. The added features may not be good enough, but it still looks possible that a system does have a capacity for features - at least with limited examples. This means that many subsets of features can do as well as all the features.

The following statement is absolutely true for the perceptron, but not necessarily true for maximum entropy learning algorithms:

A very specific feature will increase overfitting. One extreme example here is using the complete output as a feature. Such features will be sufficient to make the training converge, for they remember the output for each training input. However, it is apparently useless when testing. A more detailed example might be the feature [word trigram and current tag] for tagging.