5 Soft computing.pdf

Semester 1, 2016/2017 4th Year Networks Engineering Department College of Engineering University of Al-Iraqia E-MAIL: [email protected] LECTURE1: INTRODUCTION BY DR. BARAA MUNQITH ALBAKER SOFT COMPUTING I (SCI) SE431  Introduction to Fuzzy Logic  Introduction to Evolutionary Computatio...

Semester 1, 2016/2017 4th Year Networks Engineering Department College of Engineering University of Al-Iraqia E-MAIL: [email protected] LECTURE1: INTRODUCTION BY DR. BARAA MUNQITH ALBAKER SOFT COMPUTING I (SCI) SE431  Introduction to Fuzzy Logic  Introduction to Evolutionary Computations  Applications.  Learning Algorithms.  Multi-layer ANNs topologies and characteristics.  Concept and Types of ANNs.  Biological and Artificial NNs.  Neural Networks (NNs)  Soft Computing Basics  Outlines:  Studying the concepts and algorithms involved in neural networks, as a part of soft computing, to provide solutions to real world problems.  Aim: Aim and Outlines of the Course Course Notes L. Fausett. Fundamentals of Neural Networks: Architectures, Algorithms, and Applications. 1st Edition, Prentice Hall, 1994. J. R. Jang, C. Sun, and E. Mizutani. Neuro-Fuzzy and Soft Computing: A Computational Approach to Learning and Machine Intelligence. 1st Edition, Prentice Hall, 1997. A. Konar. Artificial Intelligence and Soft Computing: Behavioral and Cognitive Modeling of the Human Brain. 1st Edition, CRC Press, 1999. F. O. Karray and C. W. Silva. Soft Computing and Intelligent Systems Design: Theory, Tools and Applications. 1st Edition Addison-Wesley, 2004. J. Fodor and R. Fuller (Eds.). Advances in Soft Computing, Intelligent Robotics and Control. Springer, 2014.       Reference Material  Final exam: 60 %  Midterm Exam: 20 %  One/two quizzes: 10 %  Teamwork assignment: 5 %  Weekly homework assignments: 5 % Evaluation Method   Computing, Genetic Computing and Probabilistic Computing. One multidisciplinary system as the fusion of the fields of Fuzzy Logic, Neuro- imprecision. the human mind to reason and learn in an environment of uncertainty and An emerging approach for computing which parallel the remarkable ability of  Zadeh defines SC as:  Used to develop intelligent machines known as computational intelligence.  A new multidisciplinary field to construct new generation of AI  Initiated by Lotfi Zadeh in 1981. SC: Basics Not Modeled or no solution exists. Too difficult to obtain mathematical model or not practical.   which are: Needs for SC are to model and enable solutions to real world problems, 1. 2. 3. 4. 5. 6. Take decisions. Inference from previous situations experienced. Expertise in an area. Adapt to changing environment. Learn to do better. Social behavior of collective intelligence.  Key-Points to be considered:  Needs for SC and Its Key-Points  Approximate: similar to real one but not the same.  Uncertainty: not sure that features (belief) of the model are same as that of the entity.  Imprecision: model features (quantity) are not the same as real ones but close. resemblance with human like decision making. approximate reasoning and partial truth to achieve close  Aim is to exploit the tolerance for imprecision, uncertainty, human mind.  The idea behind soft computing is to model cognitive behavior of SC: Idea & Aim  Low cost  Reflects the human mind.  Uses ambiguous and noisy data  Well suited for real world problems where ideal models are not present.  Tolerant to imprecision, uncertainty, partial truth, and approximation.  Soft Computing  High cost for solution  Requires full truth.  Often requires a lot of computation time.  Works well for simple problems.  Precise modelling and analysing to yield precise and accurate results.  Hard Computing (Conventional) Techniques for Problem Solving  New sciences are still merging into SC.  What comprises SC has not yet been reached.  Soft computing is still growing and developing  Swarm Intelligence.  Genetic Algorithm. EC NN SC PR FL  Evolutionary Computation (EC) and Probabilistic Reasoning (PR): Used for Systematic random search and optimization.  Neural Networks (NN): Recognizes patterns, used for learning and adaptation.  Fuzzy Logic (FL): Reasoning and Imprecision. Incorporates human. knowledge representation via fuzzy rules. Core Components of SC Fuzzy Inference systems Neural Networks Neuro+ Fuzzy Computing DerivativeFree Optimizing = Soft Computing Core Components of SC (Cont.’d) Character Recognizer… As an Example train with known problem to acquire knowledge. Supervised and Unsupervised are very popular Feed Forward (Single layer and Multi layer) Recurrent.    Architecture:   NN adopt various learning mechanisms   Structure: large number of highly interconnected processing elements (neurons) working together.  Artificial Neural network: information processing paradigm (model) inspired by biological nervous systems, such as our brain  NN are simplified models of the biological neuron system. Neural Networks   Comprising genetic algorithms, evolutionary programming, etc.  Comprising ant colony optimization and particle swarm optimization. Swarm intelligence  Evolutionary algorithms  Mostly involve optimization algorithms such as: biological evolution  General term for several computational techniques inspired by Evolutionary Computation Probabilistic logic.   A proposition P has a truth value  0 or 1 in two-value system,  element of a set X in multi-value system,  Range over the fuzzy subsets of X in fuzzy logic. Multi-value logic systems, and   It contains as special cases, not only the classical two-value logic:  Everything, including truth, is a matter of degree.  It is an extension of multi-valued logic:  Fuzzy logic is the logic underlying approximate, rather than exact modes of reasoning. Fuzzy Logic Automotive Systems and Manufacturing Robotics Machine Learning Handwriting, Speech and Vision Recognition Systems Signal Processing Image Processing and data compression Game Playing Optimization Decision-Support Systems Control and Power Systems, etc.           SC Applications A hierarchical structure for an intelligent machine: An Example Semester 1, 2016/2017 4th Year Networks Engineering Department College of Engineering University of Al-Iraqia E-MAIL: [email protected] LECTURE2: NN FUNDAMENTALS BY DR. BARAA MUNQITH ALBAKER SOFT COMPUTING I (SCI) SE431 L. Fausett. Fundamentals of Neural Networks: Architectures,  Algorithms, and Applications. 1st Edition, Prentice Hall, 1994. Course Notes presented by Assist. Lect. Suphian M. Tariq  Reference Material of Lecture2 Development History of Soft Computing (SC) used for knowledge representation via fuzzy If – Then rules.  Hybridization of these three creates a successful synergic effect.  Used for evolutionary computation and optimization  Genetic Algorithms  Used for learning and adaptation  Neural Networks   Fuzzy Logic Set Core Components of SC simplified manner. (capability of thinking, remembering, and problem solving) in a  Neural network is an attempt to model the functionality of the brain  Neural Morphic system  Connectionist models  Biological computers or Electronic Brains.  Parallel distributed processing models models were previously called:  Artificial neural networks (ANN) or simply Neural Networks (NN) NN: Basics  The term ANN and its connections are typically used to distinguish them from biological networks of neurons of living organism NN: Basics (Cont.’d)  Recent interest in neural networks is due to the interest in building parallel computers and the discovery of powerful network learning algorithms.  Hopfield, in 1982-1987, examined the computational power of a model system of two– state neurons operating with organized symmetric connections and feedback connectivity. The inclusion of feedback connectivity distinguished them from perceptron–line networks. Moreover, graded–response neurons were used to demonstrate the power and speed of these Networks.  Minskey and Paert, in 1969, studied the capabilities and limitations of Perceptrons and concluded that many interesting problems could never be solved by Perceptron networks.  Rosenblatt, in 1961, solved simple pattern recognition problems using Perceptrons.  First attempt to understand and stimulate biological computations (artificial neuron) was by McCulloch & Pitts in 1943, who modeled biological neurons as logical decision elements described by a two–valued state variables (ON, OFF) and organized into logical decision networks that could compute simple Boolean functions. Development History of Neural Networks  Business… etc.  Speech production and recognition,  Medicine,  Control problems,  Pattern recognition,  Signal processing, NN: Application Areas  If the combined signal into the nucleus is strong enough, it activates the firing of neuron which produces an output signal. combines signals from many other neurons through input paths called dendrites  Nucleus: is a simple processing unit which receives and Biological Neural Network synapse is the junction between the axon of the neuron and the dendrites   Note: Weights in ANN ≡ synaptic strength in biological Networks synoptic strength is modified when the brain is learning. of signal transferred depends on the synaptic strength of the junction. This  The transmission across the junction is chemical in nature and the amount of the other neurons. Axon: The path of the output signal  Biological Neural Network  Each neuron applies an action function (usually nonlinear) to its net input (sum of weighted input signals) to determine its output signal.  Each connection link has an associated weight which, in a typical neural net, multiplies the signal received.  Signals are passed between neurons over connection links.  Information processing occurs at many simple elements called neurons.  Artificial neural networks have been developed as generalizations of mathematical models of human cognition or neural biology, based on the following assumptions:  An artificial neural network is an information processing system that has certain performance common with biological neural networks. ANN… Based on Biological NN Pattern of connections between the neurons. Method of determining the weights on the connections.  Activation function.   Training /Learning Algorithm   Architecture NN… Characteristics  Fault tolerance.  Distributed memory.  Ease of constriction & learning.  Abstraction & solving problem with noisy data.  capacity of generalization.  capacity for adaptation "learning rather programming“.  Parallelism. NN… Properties The output vectors (a1, a2, a3, …. , an) are assigned to the input vectors. The functions are to be represented by a network.   Learn procedures are to be used for determining the weights.  After the weights have been learned and the network becomes available, it can be used as desired.   Network weights (w1, w2, w3, …) are to be selected in such away that the network represents the given function and the selected topology.  A topology is to be selected for the network. The input vectors (e1 , e2, e3, …. , en) are present,   A logical function to be represented is given. NN… General Development Procedure Else correct the weights according to a suitable correction formula and then  continue with step 2. If Oj = aj then continue with step 2   Step4: Compare Oj with the destination vector aj ,  Step3: Calculate the output vector Oj with the current weights.  Step2: Select a random input vector ej.  Step1: Set random numbers for all weights. NN Weights… General Learning Procedure Weights are changed according to a formula (e.g. the delta-rule). if the output is unequal to a. This learning method can be compared to     (weights are stored, else forgotten). output calculated with the changed weights is better than the previous one With the help of an evaluation function one can ascertain whether the through random numbers. Correct final vector is not specified, but instead the weights are changed  Unsupervised learning (also called reinforcement learning) regulates them accordingly in the learning procedure. learning under a teacher, who knows the contents to be learned and At every step the system is informed about the exact output vector.   Supervised learning Types of Learning features in the input patterns. The system learns on its own by discovering and adapting to the structural the network. No teacher is present, the expected or desired output is not presented to through random numbers. Correct final vector is not specified, but instead the weights are changed  Neighborhood of the input pattern. Probability pattern, with which the permissible input pattern is offered. Weights change themselves at every learning step. The change is based on:  Self-Organization learning     Unsupervised learning Types of Learning (Cont.’d) NN with two layers of weights weighted interconnects links between the neurons.  Number of layers in the net can be defined to be the number of layers of  The input unit is not counted as a layer, because they perform no computation.  NN are classified as single layer and multilayer. NN Typical Architectures One layer of connection weights.  Typical single-layer net with input units are fully connected to output units output unit, from which the response of the net can be read.  It has an input unit, which receives signals from the outside world, and an  Single-Layer Net trained to perform correctly at all. (3-layered NN)  In some cases, it is possible to solve a problem that a single-layer net can not be training may be more difficult.  Multilayer nets can solve more complicated problems than single-layer nets, but between the input units and the output units.  It is a net with one or more layers (levels) of nodes which is called hidden units Multi-Layer Net Semester 1, 2016/2017 4th Year Networks Engineering Department College of Engineering University of Al-Iraqia E-MAIL: [email protected] LECTURE4: NN LEARNING ALGORITHMS BY DR. BARAA MUNQITH ALBAKER SOFT COMPUTING I (SCI) SE431 L. Fausett. Fundamentals of Neural Networks: Architectures,  Algorithms, and Applications. 1st Edition, Prentice Hall, 1994. Course Notes presented by Assist. Lect. Suphian M. Tariq  Reference Material of Lecture4  Some developers do not use a bias weight, but instead use a fixed threshold θ for the activation function. In this case,  Mathematical formula: (both with same user-defined AF)  Increasing the bias increases the net input to the unit.  A bias acts exactly as a weight on a connection from a unit whose activation is always 1. Biases Vs. Thresholds… A review 𝑏+ 𝑖 𝑥𝑖 𝑤𝑖 = 0 Decision boundary is the boundary between the region where yin>0 and the region where yin0. i.e. Support (A)= {x| μA(x)>0}  Core: The core of a fuzzy set A is the set of all points x in X such that μA(x)=1 i.e. core (A)= {x| μA(x)=1} Characteristics of a Membership Function in FL(Cont.’d)  Normality: A fuzzy set A is normal if its core is nonempty. i.e. At least one x with μA(x)=1 then it is normal.  Crossover Point: A cross over point in fuzzy set A is the x with μA(x)=0.5 i.e. crossover (A)= {x| μA(x)=0.5}  Bandwidth: For a normal & convex fuzzy set BandWidth(A)=|x2-x1|, where x2 & x1 are crossover points.  Height: The height of a Fuzzy set A is height = Support (A)|x ∈X μA(x)  Fuzzy Singleton: A fuzzy set whose support is a single point in X with μA(x)=1. 9 3/31/2017 Fuzzy Sets: Example1 – Imprecision  Note: Words are used to capture imprecise notation, loose concepts or perceptions. Fuzzy Sets: Example2 – Sets Overlapping  Note: Overlapping of the sets reflecting the real world more accurately than using a traditional approach. 10 3/31/2017 Fuzzy Set with Discrete Universes- Example3  Fuzzy set A = “sensible number of children”  X = {0, 1, 2, 3, 4, 5, 6} (discrete universe)  A = {(0,.1), (1,.3), (2,.7), (3, 1), (4,.6), (5,.2), (6,.1)}, Or, Fuzzy Set with Discrete Universes- Example4 Fuzzy set A = Numbers close to 1 11 3/31/2017 Fuzzy Set with Continuous Universes- Example5 Fuzzy set B = Age about 50 years old X = Set of positive real numbers (continuous) B = {(x, μB(x)) | x in X} μB(x)=f(x) As a summary, Crisp Vs. Fuzzy Set - Example6 Classification of students eligibility for a basketball team, as: A. Tall Students: above 1.8m B. Not Tall Students: under 1.8m Draw the graphic interpretation of degree of truth using Crisp and Fuzzy logic. 12 3/31/2017 Homework1 Note: Make any assumptions as required. A. Consider the following membership functions: i. Define set A, ii. Compute the following characteristics of the Fuzzy set A: Core, Support, Normality, Crossover points, Bandwidth, and height. iii. Show whether Set A is a Fuzzy Singleton or not B. Consider a universal space V consisting of integer numbers from 1 to 20. i. Describe a set of prime numbers in the space V. ii. Describe a set in the set of part (i) defined by Small_Number, that has unsharp boundaries and can be characterized by a function [0,1] to each element of part (i). iii. Draw the graphical interpretation of Fuzzy Sets of parts i and ii (prime and Small_Number) iv. For each membership function of Sets of part i and ii, Find the following characteristics: Core, Support, Normality, Crossover points, Bandwidth, and height. Fuzzy Boundary Vs. Crisp Boundary  Note: Fuzzy means from precision to imprecision. 13 3/31/2017 Fuzzy Boundary Vs. Crisp Boundary(Cont.’d)  Crisp Set ⊆ Fuzzy Set (Crisp is a special case of a Fuzzy)  Note: Fuzzy means from precision to imprecision. Fuzzy Sets: Operations 14 3/31/2017 Fuzzy Sets: Operations (Cont.’d) Subset: Fuzzy Sets: Operations (Cont.’d) 15 3/31/2017 Set theory, Logic and Boolean: Concept and Notation Properties of Fuzzy Sets 16 3/31/2017 Properties of Fuzzy Sets (Cont.’d) Properties of Fuzzy Sets (Cont.’d) 17 3/31/2017 Finite & Infinite Universal Space  Universal Sets can be finite or infinite.  Finite Universal Set, consists of a specific number of different elements.  E.g. Week = { Sun, Mon, Tue, Wed, Thr, Fri, Sat }; i.e. Week is finite of 7 elements Baghdad= { c | c is a capital city of Iraq }  Infinite Universal Set, consists of an endless number of elements.  E.g. Integer_Positive_Number= { I : I >= 0 } Empty and Universal Sets  For the Universal Set X = {xi} = { 1 , 2 , 3 , … , 12 }  Universal Set: Contains elements with ones membership values.  The Universal Fuzzy set A in set X is defined as A = { {1,1} , {2,1} , {3,1}, … , {12,1} }  Empty Set: Contains elements with zeros membership values.  Let Set B is an Empty Set in set X, defined by B = { {1,0} , {2,0} , {3,0}, … , {12,0} } 18 3/31/2017 Equality and Comparability  Equality: Two Fuzzy Sets are equal if their members with their membership values are equal. I.e. For Sets A and B; Sets are equal iff ∀x ∈ X, A = B. Example1: W= { {Sun,0.1} , {Mon,1}, {Tue,0} }; Y = { {Sun,0.1} , {Mon,1} , {Tue,0} }  Since ∀x ∈ X, A = B; therefore A equals B  Comparability: Two Fuzzy Sets are comparable if one set is a subset of the other set.  I.e.: For sets A and B; then sets are comparable if condition A⊂B or B⊂A holds. Example2: C= { {Sun,1} , {Mon,0}, {Tue,1} }; D = { {Sun,1} , {Mon,1} , {Tue,1} }  Since C is a subset of D, thus C is comparable to D Example3: E= { {Sun,0.1} , {Mon,1}, {Tue,0} }; F = { {Sun,0} , {Mon,0.9} , {Tue,0.1} }  Since E is neither a subset of F nor F is a subset of E, thus sets not comparable Fuzzy Operations: Example1, Inclusion For the given Fuzzy sets: A = { {1,1} , {2,0.8} , {3,0.7}, {4,0.4} , {5,0.2} , {6,0.1} , {7,0} , {8,0} , {9,0} , {10,0} , {11,0} , {12,0} } and B = { {1,1} , {2,1} , {3,0.9}, {4,0.6} , {5,0.4} , {6,0.3} , {7,0.2} , {8,0.1} , {9,0} , {10,0} , {11,0} , {12,0} } Then, apparently A is contained in B and the Fuzzy inclusion of A and B is graphically interpreted as shown: 19 3/31/2017 Fuzzy Operations: Example2, Complement For the given Fuzzy set: A = { {1,1} , {2,1} , {3,0.9}, {4,0.6} , {5,0.4} , {6,0.3} , {7,0.2} , {8,0.1} , {9,0} , {10,0} , {11,0} , {12,0} } Therefore, NotA = Ac = { {1,0} , {2,0} , {3,0.1} , {4,0.4} , {5,0.6}, {6,0.7} , {7,0.8} , {8,0.9} , {9,1} , {10,1} , {11,1} , {12,1} } Fuzzy Operations: Example3, Union For the given Fuzzy sets: A = { {1,1} , {2,1} , {3,0.9}, {4,0.6} , {5,0.4} , {6,0.3} , {7,0.2} , {8,0.1} , {9,0} , {10,0} , {11,0} , {12,0} } and B = { {1,0} , {2,0} , {3,0}, {4,0.2} , {5,0.5} , {6,0.8} , {7,1} , {8,1} , {9,0.7} , {10,0.4} , {11,0.1} , {12,0} } Therefore Union(A , B) = max(A , B) = { {1,1} , {2,1} , {3,0.9}, {4,0.6} , {5,0.5} , {6,0.8} , {7,1} , {8,1} , {9,0.7} , {10,0.4} , {11,0.1} , {12,0} } 20 3/31/2017 Fuzzy Operations: Example4, Intersection For the given Fuzzy sets: A = { {1,1} , {2,1} , {3,0.9}, {4,0.6} , {5,0.4} , {6,0.3} , {7,0.2} , {8,0.1} , {9,0} , {10,0} , {11,0} , {12,0} } and B = { {1,0} , {2,0} , {3,0}, {4,0.2} , {5,0.5} , {6,0.8} , {7,1} , {8,1} , {9,0.7} , {10,0.4} , {11,0.1} , {12,0} } Therefore Intersection(A , B) = min(A , B) = { {1,0} , {2,0} , {3,0}, {4,0.2} , {5,0.4} , {6,0.3} , {7,0.2} , {8,0.1} , {9,0} , {10,0} , {11,0} , {12,0} } Fuzzy Operations: Example5, Intersection in 3D Suppose we have a Fuzzy set F normalized on a universe of integers {1, 2, 3, 4, 5}, and a Fuzzy set D normalized on a universe of integers {1, 2, 3, 4}. Where, F and D are defined by: Resultant intersection in 3-D: Note: 3-D applies when Fuzzy sets are from two different universes. 21 3/31/2017 Mathematical Formulation& Parameterization of 1-D Membership Functions a) Triangular Membership Functions (MFs):  Specified by three parameters {a, b, c}:  Alternative expression using min and max, Triangle (x; 20, 60, 80) Note:  The parameters {a, b, c} with a < b < c determine the x coordinates of the three corners of the triangular.  Used extensively, especially in real-time implementations.  MFs are composed of straight line segments  Not smooth at the corners. Mathematical Formulation& Parameterization of 1-D Membership Functions(Cont.’d) b) Trapezoidal MFs:  Specified by four parameters {a, b, c, d}:  alternative expression using min and max, Trapezoid (x; 10, 20, 60, 95) Note:  The parameters {a, b, c, d} with a < b