3

What is the worst classier that learns badly in practical problems?

Edit: Especially bad on test data..

Thanks

Betamoo
  • 273
  • 2
  • 6
  • Mathematically speaking, in binary classification, knowing the worst is equivalent to knowing the best. If you know the best you reverse the rule and it becomes the worst. Why do you want the worst rule ? what do you mean by worst ? – robin girard Jan 05 '11 at 17:07

2 Answers2

9

Consider the binary case. If you don't know the proportions of the two classes, then the worst you can do is to flip a fair coin in each case: the expected error rate is $1/2$. If you do know the proportions, and the smaller of the two is $p$, say, then you should always classify objects in that category: the expected error rate is $1-p \gt 1/2$. (However, it could be argued that this procedure is not worse. After observing it sufficiently long, you would notice its error rate is significantly greater than $1/2$ and then you would have the option of negating it--that is, assigning the opposite classification--and that would have an error rate of only $p \lt 1/2$.)

whuber
  • 281,159
  • 54
  • 637
  • 1,101
  • +1 If you wanted a straw man, that would indeed be a good one! – Dikran Marsupial Jan 04 '11 at 21:25
  • @Dikran You have read my answer as it was intended: tongue in cheek. It's amusing to try to think of anything that could be worse and somewhat amusing to think of more sophisticated attempts that, in the end, haven't performed any better than a coin flip! – whuber Jan 04 '11 at 22:11
  • 1
    I am curious if one can do even _worse_ than a coin flip in the case of unknown proportions of classes, but it seems probably not. – shabbychef Jan 05 '11 at 01:07
  • I suspect it is possible to make a classifier that is worse than coin flipping by using an overly complex model (such as an ANN with a large hidden layer) and too little data. While it will out-perform coin flipping on the training set, it may well be worse on the test set. AFAIK, there is no guarantee that an overfit model won't be arbitrarily bad on the test set. – Dikran Marsupial Jan 05 '11 at 09:07
  • I would say flipping a coin is the best you can do when the information you have is not related with the classification you want to make. Hence there are worst things to do ? – robin girard Jan 05 '11 at 13:18
  • 1
    In addition to Dikran, the worst classifer I can imagine would be a classifier trained on a small amount of data which performs sometimes better and sometimes worse than random so that the negation is not possible, i.e. the is quality systematically unpredictable (but this seems ridiculous, so I'll stick with whuber). – mlwida Jan 05 '11 at 14:06
  • 1
    @steffen I think you're right: complete unpredictability can be worse than random. There is a difference! But although there is no probability model available, we can analyze this situation with game theory. It's you *vs* the classifier. Assume the classifier is out to get you: it will do its worst. What is your optimal strategy? The answer, in the absence of any other information, is to flip the coin: that guarantees you won't lose more than half the time in the long run. What ruins this analysis is the eternal hope that *our* classifier is actually good, so we rarely use this strategy. – whuber Jan 05 '11 at 14:23
7

It is usually the statistician using the classifier that is the problem (for picking the wrong tool for the particular problem at hand, or for using it incorrectly). The "no free lunch" theorems show there is no a-priori distinction between classifiers (which works best/worst depends on the data), so I'd say there isn't a worst classifier in a general sense. However, some classifiers are easier to shoot yourself in the foot with than others, in which case, I would nominate artificial neural networks (the over-fit very easily and need proper architecture selection and none of the solutions to such problems are reliable).

Dikran Marsupial
  • 46,962
  • 5
  • 121
  • 178
  • 1
    Hah! I think my proposal is worse than yours :-). – whuber Jan 04 '11 at 21:18
  • The no-free lunch theorem suggest that there will be problems where it works well and other algorithms dont! ;-P – Dikran Marsupial Jan 04 '11 at 21:21
  • Thank you. Do you have a favorite reference or references to these NFL theorems? – whuber Jan 04 '11 at 22:09
  • The original papers were by David Wolpert, there are some references and info at http://www.no-free-lunch.org/ . "no free lunch for the sandwich" would be a favourite reference, but only because of the title ;o) – Dikran Marsupial Jan 04 '11 at 22:51