Decision stump: decision tree with just one decision.

Edited by author 04-23-2001 12:42 PM
I also thing this is an elegant idea, though I'm not very familiar with error correcting codes. I like the fact that this approach is a unifying one, but it is not clear to me what ideas belong to the authors and what can be attributed to the original work by Dietterich & Bakiri. I believe this paper's additions are the use of loss functions.

I take issue with the paper's use of the term epsilon in Theorem 1 without defining it until 2 pages later, as far as I can see.

In their experiments, they first talk about using the AdaBoost learning algorithm, and using "decision stumps" as the base learner. What are decision stumps?

hi,
ELEGANT idea I must say. the idea of being able to look at the m class in a m-fold prediction task as an error correcting code is frankly just too cool for me. The only problem is the paper says nothing about the difficulty of the problems constructed now and just mentions in passing that high values of rho would imply more difficult problems.

As error correcting codes are usually designed taking in to consideration the kind of errors that the underlying channel introduces, it would be interesting to look at the design of codes for multi-class learning problem by analysing the error characteristics of a given base algorithm over the simple encoding first.. meaning.

assume that the columns are binary representations of 0, 1,2 ..m-1
and then see if there are any particular kind of errors are prevalent, and then use that criterion to come up with a better code.

also certain codes (whatever be the minimum distance) could makes the transformed problem harder.

sameer

I contacted one of the authors (Dr. Schapire) and he said Table 2 and 3 are ok. The figures should be labeled as mentioned below. He also placed a new corrected version on his web page:
http://www.research.att.com/~schapire/publist.html

Please notice that figures 4 and 7 do not agree with Table 2. Assuming Table 2 is correct, the plots in figure 4 should be labeled (from left to right): dense, complete, one-vs-all, all-pairs, sparse (it should be dense instead of one-vs-all and so on). Figure 7 should be labeled according to this modification. The same thing happens for the SVM results. In figure 5, "complete" and "all-pairs" should be swapped (one-vs-all, dense and sparse are ok). Figure 6 should be modified accordingly.

A minor thing is that in page 137 (below figure 5), the errors are slightly different from the ones shown in Table 2 (72% appears as 72.9% in Table 2, 47.1 as 47.2, 39.6 as 39.7 and 27.5 as 27.8).

Edited by author 04-19-2001 02:13 AM
I would like to mention that section 5 - Analysis of Generalization Error… (page 125-133) will not be discussed during the talk on Monday. I would be happy discussing it here.

If someone wants to understand the techniques adopted in section 5, it is probably more efficient to initially read a paper which discusses the concepts in a simpler scenario, as [Schapire, 1998], for example.