Fuzzy heterogeneous neurons for imprecise classification problems

Fuzzy Heterogeneous Neurons for Imprecise Classicati on Problems Julio J. Valdes Llus A. Belanche Rene Alquezar Seccio d'Intel  ligencia Articial. Dept. de Llenguatges i Sistemes Informatics. Universitat Politecnica de Catalunya. c/Jordi Girona Salgado 1-3 08034 Barcelona, Spain. f valdes, b elanche, alquezar g @lsi.up c.es Abstract In the classical neuron mo del, inputs are continuous real-valued quantities. However, in many imp ortant domains from the real world, ob jects are describ ed by a mixture of continuous and discrete variables, usually containing missing information and uncertainty. In this pap er, a general class of neuron mo dels accepting heterogeneous inputs in the form of mixtures of continuous (crisp and/or fuzzy) and discrete quantities admitting missing data is presented. From these, several particular mo dels can b e derived as instances and dierent neural architectures constructed with them. Such mo dels deal in a natural way with problems for which information is imprecise or even missing. Their p ossibilities in classication and diagnostic problems are here illustrated by exp eriments with data from a real world domain in the eld of environmental studies. These exp eriments show that such neurons can b oth learn and classify complex data very eectively in the presence of uncertain information. Keywords: Heterogeneous Neural Networks; Fuzzy Logic; Genetic Algorithms; Uncertainty and Missing Data. 1 Intro duction The classical neuron mo del {where inputs are continuous real-valued quantities, and net input is computed as the scalar pro duct of the input and the 1 This is the peer reviewed version of the following article: Valdés, J.; Belanche, L.; Alquézar, R. Fuzzy heterogeneous neurons for imprecise classification problems. "International journal of intelligent systems", Febrer 2000, vol. 15, núm. 3, p. 265-276, which has been published in final form at https://doi.org/10.1002/(SICI)1098-111X(200003)15:3<265::AID-INT7>3.0.CO;2I. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for SelfArchiving. weight vector{ was extended by the notion of an heterogeneous neuron intro duced in [11]. Mo del instances of this concept provide neurons accepting mixtures of real and discrete quantities (i.e. numerical and qualitative information) p ossibly also containing missing data. A second imp ortant feature of this class of mo dels is that their internal stimulation is based on a similarity or proximity relation [1] b etween the input and the weight tuples. In particular, a family of mo dels considering neuron outputs as a comp osition of a similarity function with a sigmoid-like squashing function was shown to b e a reasonable brick for constructing layered network architectures mixing heterogeneous with classical neurons. These networks were shown to b e capable to learn from non-trivial data sets with an eectiveness comparable, and sometimes b etter, than that of classical metho ds. They exhibited a remarkable robustness when information degrades due to the increasing presence of missing data. As was stated in [11 ] when discussing the general framework for heterogeneous neurons, future studies should consider more general mo dels constructed by taking into account mappings among wider classes of sets as domains and images (i.e inputs and output). The purp ose of this pap er is to consider extensions in which fuzzy sets may o ccur as part of the input. This will intro duce more exibility by accepting training processes using imprecise data, b oth in the input and the weights. This way, heterogeneous neurons of this kind may accept a mixture of real, qualitative, and fuzzy quantities, p ossibly with missing information. In what follows, a neuron of this typ e is presented and its learning capabilities are illustrated by a real world example: an environmental study {using geophysical data pro cessing{ aimed at detecting the presence of underground caves. 2 The Heterogeneous Neuron Mo del Revisited An heterogeneous neuron was dened in [11 ] as a mapping h : ^ H n ! R out  R , satisfying h (  ) = 0 (  is the empty set). Here R denotes the reals and ^ H n is a cartesian pro duct of an arbitrary numb er of source sets . Source sets may b e extended reals ^ R = R [ fX g , and/or nite sets of the form ^ O i = O i [ fX g ; ^ M i = M i [ fX g . Each of the O i has a full order relation, while the M i have not. The sp ecial symb ol X denotes the unknown element (missing information) and it b ehaves as an incomparable element w.r.t. any ordering relation. According to this denition, neuron inputs are p ossibly empty arbitrary tuples , comp osed by n elements among which there might b e reals, ordinals, nominals and missing data. A particular class of heterogeneous neurons can b e devised by considering 2 h as the comp osition of two mappings, h = f  s , such that s : ^ H n ! R 0  R and f : R 0 ! R out  R . The mapping h can b e considered as a n -ary function parameterized by a tuple ^ ~w  ^ H n representing neuron's weights, i.e. h ( ^ ~x; ^ ~w ) = f ( s ( ^ ~x; ^ ~w )). In particular, the function s represents a similarity and f a squashing non-linear function with its image in [0 ; 1]. Accordingly, the neuron is sensitive to the degree of similarity b etween its input, comp osed in general by a mixture of continuous and discrete quantities p ossibly with missing data. More precisely, s is understo o d as a similarity index , or proximity relation (transitivity considerations are put aside). That is, a binary, reexive and symmetric function s ( x; y ) with image on [0 ; 1] such that s ( x; x ) = 1 (strong reexivity). The semantics of s ( x; y ) > s ( x; z ) is that ob ject y is more similar to ob ject x than z . An instance of this mo del uses as s function Gower's similarity index [6]. This co ecient has its values in the real interval [0 ; 1] and for any two ob jects i; j given by tuples of cardinality n , is given by the expression s ij = P n k =1 g ij k  ij k P n k =1  ij k where:  g ij k is a similarity score for ob jects i; j according to their value for variable k . These scores are in the interval [0 ; 1] and are computed according to dierent schemes for numeric and qualitative variables. In particular, for a continuous variable k and any two ob jects i; j the following similarity score is used: g ij k = 1 ? j v ik ? v j k j range ( v  k ) Here, v ik denotes the value of ob ject i for variable k and range ( v  k ) = max i;j ( j v ik ? v j k j ) (see [6] for details on other kinds of variables).   ij k is a binary function expressing whether b oth ob jects are comparable or not according to their values w.r.t. variable k . It is 1 if and only if b oth ob jects have values dierent from X for variable k , and 0 otherwise. As for the activation function, a mo died version of the classical sigmoid is used, such that it maps the real interval [0 ; 1] on (0 ; 1). f ( x; p ) = ( ? p ( x ? 0 : 5) ? a ( p ) ? a ( p ) if x  0 : 5 ? p ( x ? 0 : 5)+ a ( p ) + a ( p ) + 1 otherwise 3 a ( p ) = ? 0 : 5 + p 0 : 5 2 + 4  p 2 where a ( p ) is an auxiliary function and p > 0 is a real-valued parameter controlling the curvature. 2.1 A Fuzzy Extension A step forward in generalizing the previous sp ecic mo del is a relaxation of real valued inputs, by considering more exible situations, now tolerating imprecision. According to the conceptual setting of the family of neuron mo dels studied based on similarity, it is natural to state a fuzzy extension following the same approach. Similarity relations from the p oint of view of fuzzy theory have b een dened elsewhere [8], [16]. In the present case, the situation is not that of a fuzzy similarity or proximity relation dened on real values, but a relation b etween fuzzy entities. Let F i b e a family of normalized fuzzy sets from the source set and ~ A; ~ B 2 F i two fuzzy sets. The following similarity relation is used: g ( ~ A; ~ B ) = max x (  ~ A \ ~ B ( x )) where  ~ A \ ~ B ( x ) = min (  ~ A ( x ) ;  ~ B ( x )) Clearly it is reexive in the strong sense and also symmetric. This is a proximity relation and can b e used to include extra fuzzy comp onents in Gower's similarity. Consider a collection of n f extended fuzzy sets of the form ^ F i = F i [ fX g and their cartesian pro duct ^ F n f = ^ F 1  ^ F 2  :::  ^ F n f . The resulting input set will then b e ^ H n = < ^ R n r ; ^ F n f ; ^ O n o ; ^ M n m > , where the cartesian pro ducts for the other kinds of source sets ( ^ R i ; ^ O i ; ^ M i ) are constructed in a similar straightforward way from their resp ective cardinalities n r ; n o ; n m , with ^ R 0 = ^ F 0 = ^ O 0 = ^ M o = ^ H o =  , n = n r + n f + n o + n m and n > 0. The training pro cedure for the resulting heterogeneous neuron {shown in Fig. 1{ is based on genetic algorithms ([7], [2]) and can b e devised in a natural way by extending that used for heterogeneous neurons without fuzzy inputs or weights [11]. In this extension, each fuzzy weight is characterized as a tuple of reals (instead of a single one) and this only needs a chromosome enlargement, dep ending on the chosen functional representation for fuzzy sets (trap ezoidal, Gaussian or LR). 4 ^ R n r ^ F n f ^ O n o ^ M n m h = f  s R out 2 R Figure 1: A fuzzy heterogeneous neuron. 3 An Example of Application in an Imprecise Domain An environmental investigation in the tropics dealing with the detection of underground caves using geophysical measurements made at the surface of the earth was used to exp eriment with the extended approach describ ed in the previous section. First, some words describing the problem are necessary. Karstication is a p eculiar geomorphological and hydrogeological phenomenon pro duced mostly by ro ck solution as the dominant pro cess. As a consequence, earth's surface is covered by exotic irregular morphologies, like lapiaz, closed depressions ( dolinas ), sinks, p otholes and the like, with the development of underground caves. This implies that the surface drainage network is usually p o orly develop ed or simply do es not exist at all, while vertical inltration of rain waters forms an underground drainage system where water ows through ssures, galleries and caves. The studied area is lo cated 30 km to the south of Havana City (Cuba) in the so called Havana-Matanzas Karstic Plain comp osed of p orous, fractured and heavily karstied limestones of Middle Mio cen age with abundance of a variety of clay minerals. Under the high temp eratures and humidity typical of tropical conditions, weathering pro cesses develop an overburden comp osed by reddish insoluble materials ( tera rossa ) coming from solution pro cesses on the limestones. Negative karst forms on the surface (the lapiaz, sinks, dolinas, etc.) are partially or totally covered by an overburden of variable depth. These forms often connect with caves in the underground, some of them big. Direct detection is very dicult or imp ossible and geophysical metho ds are necessary, as they are for tasks like geological mapping and construction of cross sections. 5 This is a very imp ortant problem from the p oint of view of civil engineering, geological engineering and environmental studies in general in this kind of regions. In a selected square area (340 m side), geophysical metho ds complemented with a detailed top ographic survey [10 ] were used with the purp ose of characterizing the shallower horizons of the geological section and their relation with underlying karstic phenomena. Targets were zones of intense fracture and karstication, lled depressions, overburden p o ckets and the presence of underground caves. The set of geophysical metho ds included the sp ontaneous electric p otential of earth's surface, the gamma radioactive intensity and the electromagnetic eld in the VLF region of the sp ectrum [10 ]. In particular, two dierent surveys of sp ontaneous electric p otential were p erformed, in the dry and rainy season resp ectively, since strong negative anomalies are due to inltration p otentials asso ciated with electro chemical pro cesses taking place as water inltrates into the underground via ssures and joints. These four measurements, along with the surface top ography, constitute the ve variables to b e used by the neural mo dels. The complexity of these measured geophysical elds in the area is illustrated, as an example, by the distribution of gamma ray intensity and the surface top ography. While radioactivity is highly noisy, top ography shows few features. Both are shown in Figs. 2, 3. "..\work\c4i.gnu" 15.2 12.7 10.2 7.63 5.1 0 5 10 15 20 25 30 0 5 10 15 20 25 30 Figure 2: Distribution of gamma ray intensity in the studied area. Geophysical survey metho dologies consider indep endent sets of measurements in order to account for dierent kind of errors and the natural variability of such kind of information. In order to b e considered acceptable, each survey must have an error no greater than 5% when comparing the original and the indep endent measurements. This means that the rep orted values of 6 all geophysical elds (i.e, the available data), have an inherent uncertainty which must b e considered. In the area, a gentle variation in geological conditions for b oth the b edro ck and the overburden was susp ected by geologists and also a large underground cave with a single gallery was known to exist in the central part of the area. The cave has ab out 300 meters long with cross sections ranging from less than one square meter in the narrowest part, to chamb ers having 40 meters wide and 30 meters high, reaching the surface in the form of a gorge in the b ottom of a depression. "c5irf.gnu" 0.561 0.0723 -0.416 -0.905 -1.39 0 5 10 15 20 25 30 0 5 10 15 20 25 30 Figure 3: Surface top ography of the studied area. An isolation of the dierent geophysical eld sources was necessary in order to fo cus the study on the contribution coming from underground targets, trying to minimize the inuence of b oth the larger geological structures, and the lo cal heterogeneities. According to the a priori geological ideas, each geophysical eld was assumed to b e describ ed by the following additive twodimensional mo del comp osed by trend, signal and random noise: f ( x; y ) = t ( x; y ) + s ( x; y ) + n ( x; y ) where f is the physical eld, t is the trend, s the signal, and n the random noise comp onent, resp ectively. In order to isolate an approximation of the signals pro duced by the underground target b o dies, a linear trend term t 0 ( x; y ) = c 0 + c 1 x + c 2 y was computed (by least squares) and subtracted from the original eld. The residuals r ( x; y ) = f ( x; y ) ? t 0 ( x; y ) were then ltered by direct convolution with a low pass nite-extent impulse resp onse two-dimensional lter in order to attenuate the random noise comp onent [5]. Such convolution is given by: 7 s 0 ( x; y ) = N X k 1 = ? N N X k 2 = ? N h ( k 1 ; k 2 ) r ( x ? k 1 ; y ? k 2 ) where r ( x; y ) is the residual, s 0 ( x; y ) is the signal approximation and h ( k 1 ; k 2 ) is the low-pass zero-phase shift digital lter. 4 Exp eriments In order to study the b ehavior of these neural mo dels, a comparison was made w.r.t. geological-geophysical accuracy of classication. This kind of knowledge, as well as results from previous non-sup ervised classication techniques [15] had shown the existence of two multivariate p opulations within the studied area: one representing more karstied zones with large interconnected underground cavities, and another in which karstication is not so intense. Since the hyp othesis of two hyp erspherical classes in pattern space was tenable, and the purp ose of this work is to assess the relative merits of the three considered neuron mo dels (classical, heterogeneous and fuzzy heterogeneous) in the task at hand (imprecise classication using data which are also imprecise), a network consisting of a single neuron was the architecture selected. Clearly, other multilayer layouts are p ossible and should deserve future attention, but is a go o d reference for initial comparisons. This, together with the small training set (relative to test), should make the problem much more dicult than it really is, so the dierences should b e more evident. The exp eriments were conceived in two phases as follows. In phase one, a comparison is made b etween the classical real neuron with the heterogeneous one with real inputs and weights. In a second stage, the latter is compared to the fuzzy heterogeneous neuron. Also, the exp eriments were designed following geological criteria. From this p oint of view it is known that the numb er of observable caves in any karstic area is only a small fraction of the actually existing ones, making class structure itself imprecise , a situation usual in complex problems like those from environmental studies. Moreover, there are no sharp b oundaries b etween ro ck volumes containing caves and those containing less or none. One could say that the notion of \caveness" degrades smo othly, which is another reason to use fuzzy mo dels. The training was sup ervised (in the usual mean squared error sense) by the information given by the top ographic map of a large cave present in the area, so that those surface measurement p oints lying exactly above the known cave were considered as class 1 patterns and those outside as b elonging to class 2 (the resulting cave is shown in gure 4). This pro cedure for class 8 Figure 4: The known cave b orders: see text for an explanation of what is considered as cave and what is not. Dots indicate the (approximate) lo cation of the p oints used for training. assignment was to o conservative but, otherwise, one would have b een forced to provide as output the exact caveness degree for each p oint. This value, b esides b eing very dicult to estimate, would have intro duced a strong subjective bias. The computation of this degree is precisely the task we want the mo del to p erform. Selected data from the northern half were used for training, whereas the rest was used for testing the trained network (consisting of a single neuron only). More precisely, the training set was comp osed by the 31 p oints from the northern half lo cated exactly ab ove the known cave (representing class 1), plus 32 others homogeneously distributed in the east-west sides. As test set we used the remaining 567 patterns from the whole area ( it est , train = 10%, test = 90%). 4.1 Phase 1 Here we have a classical real-valued neuron (in this study, having scalar pro duct as net input and hyp erb olic tangent as a squashing activation function). The training pro cedure for this neuron is a combination of conjugate gradient with simulated annealing [9], whereas the heterogeneous neuron is trained using a standard genetic algorithm with the following characteristics: binary-co ded values, probability of crossover: 0 : 6, probability of mutation: 0 : 01, numb er of individuals: 50, linear scaling with factor: 1 : 5, selection 9