Advanced Topics in Artificial Intelligence
Bùi Thế Duy - Bộ môn Mạng và TTMT
1 6/22/2006
Some topics in AI course Fuzzy logics z Neural Networks z Genetic Algorithms z
Bùi Thế Duy - Bộ môn Mạng và TTMT
2 6/22/2006
Fuzzy logics z
Ideas – Human beings often need to deal with input that is not in precise or numerical form.
Bùi Thế Duy - Bộ môn Mạng và TTMT
3 6/22/2006
Fuzzy logics Fuzzy sets – Zadeh (1965) developed a fuzzy set theory that allows concepts that do not have welldefined sharp boundaries. – Classic sets: an object full member or full non-member – Fuzzy sets: partial membership z
membership function
Bùi Thế Duy - Bộ môn Mạng và TTMT
4 6/22/2006
Fuzzy logics “if x is A” is partially satisfied if the object x (usually crisp value x) is partial membership of the fuzzy set z “if-then” rules z When the “if” condition is partially satisfied, the conclusion of a fuzzy rule is drawn based on the degree to which the condition is satisfied z
Bùi Thế Duy - Bộ môn Mạng và TTMT
5 6/22/2006
Fuzzy logics Membership functions
Bùi Thế Duy - Bộ môn Mạng và TTMT
6 6/22/2006
Fuzzy rule-based system (FRBS) if (x1 is I1,k) and (x2 is I2,k) and ... and (xn is In,k) then y is Ok (k = 1..m)
m: number of fuzzy rules x1, x2, ..., xn: inputs I1,k , I2,k, ..., In,k corresponding fuzzy sets (membership functions µIi,k) y: output (Ok - corresponding fuzzy set, membership function µOk) Bùi Thế Duy - Bộ môn Mạng và TTMT
7 6/22/2006
Fuzzy rule-based system (FRBS) Example: If CurrentTemp is High and FanSpeed is VeryLow then IncreaseFanSpeed is VeryHigh
Bùi Thế Duy - Bộ môn Mạng và TTMT
8 6/22/2006
Fuzzy rule-based system (FRBS) z
z
Because a crisp value can be partial membership of several fuzzy sets, it activates a number of fuzzy rules to some degree The extent to which the k-th rule is activated is calculated as: αk = µ I1,k (x1) ^ µ I2,k (x2) ^ ::: ^ µ In,k (xn)
z
The inferencing membership value of the output y is calculated as:
µinf Ok = αk ^ µ Ok (y) min is usually used for ^ Bùi Thế Duy - Bộ môn Mạng và TTMT
9 6/22/2006
Fuzzy rule-based system (FRBS) z
z
The total membership value of the output y is calculated by the compositional rule of inference as:
max is usually used for ˅
Bùi Thế Duy - Bộ môn Mạng và TTMT
10 6/22/2006
Fuzzy rule-based system (FRBS) Defuzzication methods: Center of Area (COA), Center of Maximum (COM), and Mean of Maximum (MOM) z COA: z
Bùi Thế Duy - Bộ môn Mạng và TTMT
11 6/22/2006
Genetic Algorithms z
Ideas: – Natural Evolutional process
Bùi Thế Duy - Bộ môn Mạng và TTMT
12 6/22/2006
Genetic Algorithms Search algorithms based on the process of natural evolution and survival of the fittest in the biological world (Goldberg, 1989). z While traditional optimization techniques search for an optimal solution from a single point, GAs search from a population of solutions z
Bùi Thế Duy - Bộ môn Mạng và TTMT
13 6/22/2006
Genetic Algorithms Initialize the population Evaluate initial population Repeat Perform competitive selection Apply genetic operators to generate new solutions Evaluate solutions in the population Until some convergence criteria is satisfied Bùi Thế Duy - Bộ môn Mạng và TTMT
14 6/22/2006
Neural Networks z
Ideas: – Human brain organization – Human neural networks
Bùi Thế Duy - Bộ môn Mạng và TTMT
15 6/22/2006
Neural Networks z
z
also known as Artificial Neural Networks (ANNs), Connectionist Models, and Parallel Distributed Processing (PDP) Models "Artificial Neural Networks' are massively parallel interconnected networks of simple (usually adaptive) elements and their hierarchical organizations which are intended to interact with the objects of the real world in the same way as biological nervous systems do." -- T. Kohonen
Bùi Thế Duy - Bộ môn Mạng và TTMT
16 6/22/2006
Neural Networks z z z z
z
A number of very simple, neuron-like processing elements called units, PEs, or nodes A number of weighted, directed connections between pairs of units Weights may be positive or negative real values Local processing in that each unit computes a function based on the outputs of a limited number of other units in the network Each unit computes a simple function of its input values, which are the weighted outputs from other units.
Bùi Thế Duy - Bộ môn Mạng và TTMT
17 6/22/2006
Neural Networks Perceptron: Simplest "interesting" class of neural networks z Feedforward Neural Nets: z
– Backpropagation Learning – Gradient of E
Bùi Thế Duy - Bộ môn Mạng và TTMT
18 6/22/2006