Re: On combinatorial explosions (Re: Fuzzy Pattern Recognition)

Rainer Holve (holve@forwiss.de)
Sat, 6 Jun 1998 20:57:57 +0200 (MET DST)

Bob Dalton writes:

> Neither Coombs or Holve provides a reference for [Bellman] and the
> binary tree representation. It might be important.

the term "Curse of dimensionality" orginates from [Bellman,1961] and adresses a
common problem of nonlinear modelling techniques.

I don't know, who really introduced the idea of a hierarchical structure of
low-dimensional rulebases the first time, the oldest reference I recall is
[Brown et.al, 1994]. However, it does not give any hint, how the rules for such
a structure could be determined from data (i.e. learning, pattern recognition).
This gave the motivation for my approach (see
http://www.forwiss.uni-erlangen.de/~rrholve/papers.html). The reqired
references are given at the end of this mail.

> Coombs and Andrews, IEEE Trans. Fuzzy Sys 6:1, pp 1-11, 1998 say
> otherwise, i. e. that the "curse of dimensionality" is no more.

> Reading the Coombs paper, I can see how the exponentiality is addressed,
> but what I don't see is how the fidelity of the implications of the
> original (exponential) rulebase is retained: i. e. how the mn "new"
> rules imply the same thing the m^n "old" rules implied.

Hmm, I think the m*n "new" rules can't imply the same thing as the m^n "old"
ones. For example, I don't see how a traditional rulebase like


X
---|---
N | P
|
------- Y
|
P | N
___|___

can be modelled with single input-single output rules.
Coombs and Andrews surround this problem by the second constraint, which
basically says that the function to be modelled has to be monoton in each
input. The given example of the truck backer upper neatly fits this
requirement, but one might ask how many real world problems exist, that fit
into this form. Actually, I doubt that the basis of the approach, namely the
eqivalence of

(a^b)->c and (a->c)v(b->c)

in classical logic is transferable to fuzzy logic in the straight forward way,
the authors do. It depends on how the fuzzy implication is defined, doesn't it?

Regards
Rainer

@InProceedings{brownetalb95,
author = "M. Brown and K. M. Bossley and D. J. Mills and Harris
C. J.",
address = "Yokohama",
booktitle = "Proc.\ IEEE Int.\ Conf.\ on Fuzzy Systems 1995",
pages = "2139--2146",
title = "High Dimensional Neurofuzzy Systems: Overcoming the
Course of Dimensionality",
year = "1995",
}

@Book{bellman61adaptive,
author = "R. E. Bellman",
title = "Adaptive Control Processes",
publisher = "Princeton University Press",
address = "Princeton, NJ",
year = "1961",
}

############################################################################
This message was posted through the fuzzy mailing list.
(1) To subscribe to this mailing list, send a message body of
"SUB FUZZY-MAIL myFirstName mySurname" to listproc@dbai.tuwien.ac.at
(2) To unsubscribe from this mailing list, send a message body of
"UNSUB FUZZY-MAIL" or "UNSUB FUZZY-MAIL yoursubscription@email.address.com"
to listproc@dbai.tuwien.ac.at
(3) To reach the human who maintains the list, send mail to
fuzzy-owner@dbai.tuwien.ac.at
(4) WWW access and other information on Fuzzy Sets and Logic see
http://www.dbai.tuwien.ac.at/ftp/mlowner/fuzzy-mail.info
(5) WWW archive: http://www.dbai.tuwien.ac.at/marchives/fuzzy-mail/index.html