Is there any result showing that models (say SVM, Neural-Net, kNN, etc) will have difficulty in learning "rare" instances/tail phenomena?

  • I think you accepted an answer too quickly -- it's a good answer, but there could be more possibilities out there as well. – usul Aug 8 at 8:35
  • @usul thanks for the comment. Do you have any further suggestion? Would be happy to hear additional thoughts. – Daniel Aug 8 at 14:13
up vote 10 down vote accepted

In the classic PAC learning (i.e., classification) model, rare instances are not a problem. This is because the learner's test points are assumed to come from the same distribution as the training data. Thus, if a region of space is so sparse as to be poorly represented in the training sample, its probability of appearing during the test phase is low.

You'll need a different learning model, which explicitly looks at type-I and type-II errors, or perhaps some combined precision-recall score. Here again, I don't think there are any results indicating that a specific class of algorithms is particularly poorly suited for this task, but I could be wrong.

The closest I can think of is sensitivity to outliers --- AdaBoost is known to have this property, for example.

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.