Can a Fuzzy Rule Extraction Find an Extremely Tiny Non-self Region?

Akira Imada

Brest State Technical University Belarus

(ANNIP’2005 – at Barcelona, Spain) 2

□ What is Fuzzy Rule Extraction?

To extract knowledge (rules) from data given.

⇓

Assume all the data are n-dimensional.

⇓ Then rules are like

IF (x_{1} is A_{1}^{k}) and ⋯ and (x_{n} is A_{n}^{k}) THEN (y_{1} is ν_{k1}) and ⋯ and (y_{m} is ν_{km}) where y_{i} is a likliness of each of m classes.

(ANNIP’2005 – at Barcelona, Spain) 3

A Zero-order Takagi-Sugeno’s Fuzzy Model

⇓ Membership functions μ_{ik}(x_{i}) = exp{−(x_{i} − w_{ik})^{2}/σ_{ik}^{2}}.

Defuzzification

y_{j}^{0} = H ; ∑ ; k=1 μ_{k}(x^{0}) · ν_{kj}/ H ; ∑ ; k=1 μ_{k}(x^{0})

where

μ_{k}(x^{0}) = n ; ∏ ; i=1 μ_{ik}(x_{i}^{0})

(ANNIP’2005 – at Barcelona, Spain) 4

□ A Fuzzy Neural Network Approach — G. Castellano and A. Fanelli (2000)

(ANNIP’2005 – at Barcelona, Spain) 5

Our Interest here

⇓

a NETWORK INTRUSION DETECTION SYSTEM

in which

we need a set of TEST-DATA to TRAIN and TEST the system with.

⇓

a consideration on such a test-data.

(ANNIP’2005 – at Barcelona, Spain) 6

So many artificial data-samples have been proposed so far.

⇓ Let’s categorize them □ Fictitious 2-D pictures of test-sample — Type I

E.g., Fisher’s IRIS Flower KDD-cup 1999/2003

⋯

(ANNIP’2005 – at Barcelona, Spain) 8

□ A visualization of IRIS data by Sammon Mapping

(ANNIP’2005 – at Barcelona, Spain) 9

□ The data from KDD challange cup 98

4,920,210 data are given

⇓

each is made up of 42 attributes of which

⇓

4-crisp + 17-binary + 6-integer + 15-real

Still infinitely large area of not-defiened possible transactions remain!

(ANNIP’2005 – at Barcelona, Spain) 10

GUCCI vs. GUCCI-made-in-Hong-Kong (Yet another from Istanbul, etc.)

□ Fictitious 2-D pictures of test-sample — Type II

Fisher’s IRIS Flower Ayara et al. KDD-cup 1999/2003 ⋯ ⋯

□ Ayara’s Random Anomaly in 8-bit Binary Universe

152 and 160 abnormal patterns out of 2^{8} = 256 search points. ⇓ Asserted that successfully trained.

□ Fictitious 2-D pictures of test-sample — Type II

Fisher’s IRIS Flower Ayara et al. KDD-cup 1999/2003 ⋯ ⋯

□ What if abnormal sample are only a few?

Still can we train the system with normal and abnormal sample?

□ Fictitious 2-D pictures of test-sample — Type III

Fisher’s IRIS Flower  Ayara et al.  None so far

KDD-cup 1999/2003 ⋯ ⋯

(ANNIP’2005 – at Barcelona, Spain) 16

□ Three of our claims.

1. Data should cover the whole universe.

⇒ We could miss crucial abnormal in no-defined area.

2. Abnormal Sample should be assumed extremely tiny. ⇒ This is of usual case.

3. Can we train the sytem only by NORMAL data?

(ANNIP’2005 – at Barcelona, Spain) 17

A sommelier who is trained only by real champagne

can tell the difference when given a bootleg or other sparkling wine?

How about Caviar? Forgery coins recognition?

(ANNIP’2005 – at Barcelona, Spain) 18

Our Goal is

to search for only a few ABNORMAL (no-self) pattern

hidden in

an enormous amount of NORMAL (self) patterns

by

training using only NORMAL patterns □ A test-sample – A tiny-flat-island-in-a-huge-lake

• Lake ⇒ n-D Hypercube where x_{i} ∈ [−1, 1] (i = 1, …, n)

• Island ⇒ x_{i} ∈ [−a, a] (a < 1).

— We can control the complexity by changing the size.

(ANNIP’2005 – at Barcelona, Spain) 20

□ From a fitness landscape point of view □ A Needle in a Haystack

A schematic skecth on fictitious 2D-space

The original Hinton & Nowlan’s Needle:

• A-needle ⇒ Only one configuration of 20 bits of binary string. ⋆ We don’t know where the needle locates, but God knows.

• Haystack ⇒ 2^{20} − 1 search points □ How can we train the detector?

Can we train it with most likely haystack points?

(ANNIP’2005 – at Barcelona, Spain) 23

□ How difficult?

• Random Search

2^{20} = 1, 048, 576

• Lifetime Learning – Baldwin Effect (Hinton & Nowlan 1993)

□ Random Search

⇓

Placebo ⇒ Criteria of Comparison □ We have attacked this problem with lately reported approaches

• Artificial Immune System

• Evolutionary Computation

• Fuzzy Rule

• Data-mining Technique

• etc each of which claims very SUCCESSFUL.

□ When a species of IRIS flower is normal then are others abnormal?

E.g., Kim & Bentley (2001) claimed

assuming one family of IRIS is abnormal while other two normal

⇓ TP (Successful Detection Rate) reached 100% FP (False Alarm Rate) was only 1%.

(ANNIP’2005 – at Barcelona, Spain) 27

□ A snapshot of our ongoing works An immune approach — Constant-sized hyper-shpere Detectors

(ANNIP’2005 – at Barcelona, Spain) 28

□ A result in 2-D space

(ANNIP’2005 – at Barcelona, Spain) 29

□ What if top area shrinks to zero?

(ANNIP’2005 – at Barcelona, Spain) 30

□ Alas! As dimension grows...

□ Yet another snapshot A Fuzzy Rule approach — Can a fuzzy rule find an island?

⇓

How many rules we need? (MMMMMM ⋯ M)

⇓

IF {x_{1} is Middle}, ⋯, and {x_{20} is Middle} THEN no-self.

(ANNIP’2005 – at Barcelona, Spain) 32

□ Island in the 6-D lake

Fairly large island (x_{i} ∈ [0.25, 0.75]) vs. Small island (x_{i} ∈ [0.45, 0.55])

⇓

(ANNIP’2005 – at Barcelona, Spain) 33

□ Training with Non-self

(ANNIP’2005 – at Barcelona, Spain) 34

□ Training with Self

(ANNIP’2005 – at Barcelona, Spain) 35

□ To detct island

(ANNIP’2005 – at Barcelona, Spain) 36

A result of an evolution M ⇓ While usually we have huge NORMAL samples,

we don’t know many ABNORMAL samples (when we know them it’s too late)

⇓

Can training be performed only by using NORMAL samples?

⇓

a-needle or tiny-island

as test-data to design a network intrusion detector.

(ANNIP’2005 – at Barcelona, Spain) 38

□ Conclusion

Results have not been wonderful at all AS THEY CLAIMED. ⇓ Worse than Placebo experiment? Or, experiments have sometimes reversed our expectations. We now are negative more or less, but still want to be neutral.