Re: DM: CHAID vs. CARTŪ

[R. Bharat Rao]

At 05:55 PM 9/25/97 +0200, you wrote:
>>>>>> "Mike" == Mike Muratet <muratetm@nichols.com> writes:
>  > Organization: Nichols Research
>
>  > Ronny Kohavi wrote:
>
>  >> Since the theory says that it's impossible for one algorithm to
>  >> uniformly beat any other on generalization accuracy in 
>classification
>  >> tasks (where uniformly is for all possible target concepts), the
>  >> question is *when* (under what conditions) one algorithm is 
>better
>  >> than another, not *whether*.

The key statement is "uniformly for all possible target concepts".  In
a followup paper to the one referenced below, we showed that if you
sum uniformly over all possible target concepts, it is equivalent
to trying to learn in a uniformly random universe.  Learning in a
uniformly random universe is of course impossible.  I submit that
there are sufficient examples (viz. ourselves) that show that we do
not live in a uniformly random universe.

Both Schaffer's Conservation "Law" & Wolpert's No Free Lunch work are
v. useful if you interpret them as "no algorithm will ever completely
dominate another in all situations."  However, for a given universe
where all concepts are not uniformly equally likely, it is trivial
to show that one algorithm can have better performance that the other.
The problem lies when the NFL & Cons."Law" is interpreted by others
(not necessarily the authors) as "learning is impossible."

We introduce a measure of such learning performance in our paper (ref
below) and argue that it is much more meaningful measure of algorithm
performance that the "Laws" measure, which is shown to be defined as 0
for all situations.

Bharat

@InProceedings{RGS95,
  author =       " R. Bharat Rao, Diana Gordon, and William Spears",
  title =        "For Every Generalization Action, Is There Really 
                an Equal and Opposite Reaction?  Analysis of the 
                Conservation Law for Generalization Performance",
  pages =        "",
  booktitle =    "Proceedings of the Twelfth International Conference
                  on Machine Learning (ICML'95)",
  year =         1995,
  publisher =    "Morgan Kaufmann"
}



>
>  > Do you have a reference to the paper or book that describes such 
>a
theory?
>  > Thanks.
>
>  > Mike
>
>It seems to me the following article is a good reference on this
>point:
>
>@InProceedings{SCH94,
>  author =      "Cullen Schaffer",
>  title =       "A conservation law for generalization performance",
>  pages =       "259-265",
>  booktitle =   "Proceedings of the Eleventh International Conference
>                 on Machine Learning (ICML'94)",
>  year =        1994,
>  publisher =   "Morgan Kaufmann",
>  address =     "New Brunswick, NJ"
>}
>
>       Nicolas
>
>
R. Bharat Rao,          E-mail:bharat@scr.siemens.com [PGP WELCOME] 
Adaptive Information & Signal Processing, Siemens Corporate Research
US Mail: 755 College Road East, Princeton, NJ 08540
Phones: (609)734-6531(O) (609)734-6565(F)
<Please ask for my public key or get it from www.pgp.com keyserver.>