pattern classification and recognition

Cellular Automata Machine For Pattern Recognition : 

Cellular Automata Machine For Pattern Recognition Pradipta Maji1 Niloy Ganguly 2 Sourav Saha1 Anup K Roy1 P Pal Chaudhuri 1 1 Department of Computer Science & Technology , Bengal Engineering College ( D . U ) , Howrah , West Bengal , India 711103 2Department of Business Administration , Indian Institute of Social Welfare and Business Management , Calcutta , West Bengal , India 700073

The Problem : 

The Problem Pattern Recognition - Study how machines can learn to distinguish patterns of interest Conventional Approach - Compares input patterns with each of the stored patterns learn A Comic Sans MS CA Research Group (BECDU)

The Problem : 

The Problem A Comic Sans MS CA Research Group (BECDU)

The Problem : 

The Problem No of Mismatch = 3 CA Research Group (BECDU)

The Problem : 

The Problem No of Mismatch = 9 CA Research Group (BECDU)

The Problem : 

The Problem Time to recognize a pattern - Proportional to the number of stored patterns ( Too costly with the increase of number of patterns stored ) Solution - Associative Memory Modeling CA Research Group (BECDU)

The Problem : 

The Problem Time to recognize a pattern - Proportional to the number of stored patterns ( Too costly with the increase of number of patterns stored ) Solution - Associative Memory Modeling CA Research Group (BECDU)

Associative Memory : 

Associative Memory Entire state space - Divided into some pivotal points. State close to pivot - Associated with that pivot. Time to recognize pattern-Independent of number of stored patterns. CA Research Group (BECDU)

Associative Memory : 

Associative Memory Two Phase : Learning and Detection Time to learn is higher Driving a car Difficult to learn but once learnt it becomes natural CA Research Group (BECDU)

Associative Memory (Hopfield Net) : 

Associative Memory (Hopfield Net) Densely connected Network - Problems to implement in Hardware Solution - Cellular Automata (Sparsely connected machine) - Ideally suitable for VLSI application CA Research Group (BECDU)

Cellular Automata : 

Cellular Automata VLSI Domain India under Prof. P Pal Chaudhuri Late 80’s - Work at Indian Institute of Technology Kharagpur Late 90’s - Work at Bengal Engineering College Deemed University, Calcutta Book - Additive Cellular Automata Vol I, IEEE Press CA Research Group (BECDU)

Cellular Automata : 

Cellular Automata A computational Model with discrete cells updated synchronously 2 - State 3-Neighborhood CA Cell CA Research Group (BECDU)

Cellular Automata : 

Cellular Automata Combinational Logic can be of 256 types each type is called a rule CA Research Group (BECDU)

State Transition Diagram : 

State Transition Diagram CA Research Group (BECDU)

Generalized Multiple Attractor CA : 

Generalized Multiple Attractor CA The State Space of GMACA – Models an Associative Memory CA Research Group (BECDU)

Generalized Multiple Attractor CA : 

Generalized Multiple Attractor CA CA Research Group (BECDU) Pivot Points Dist =3 Dist =1 The state transition diagram breaks into disjoint attractor basin Each attractor basin of CA should contain one and only one pattern to be learnt in its attractor cycle The hamming distance of each state with its attractor is less than that of other attractors.

Synthesis of GMACA Reverse Engineering Technique : 

Synthesis of GMACA Reverse Engineering Technique Phase I: Random Generation of a set of directed Graph Patterns to be learnt P1 = 0000 P2 = 1111 Number of bits of noise = 1 CA Research Group (BECDU) 1 0

Synthesis of GMACA Reverse Engineering Technique : 

Synthesis of GMACA Reverse Engineering Technique Phase II: State transition table from Graph Basin 1 0100 1000 0001 0010 0000 CA Research Group (BECDU)

Synthesis of GMACA Reverse Engineering Technique : 

Synthesis of GMACA Reverse Engineering Technique Phase II: State transition table from Graph CA Research Group (BECDU)

Synthesis of GMACA Reverse Engineering Technique : 

Synthesis of GMACA Reverse Engineering Technique Phase III: GMACA rule vector from State transition table CA Research Group (BECDU) Basin 1 Basin 2

Synthesis of GMACA Reverse Engineering Technique : 

Synthesis of GMACA Reverse Engineering Technique Phase III: GMACA rule vector from State transition table CA Research Group (BECDU) Basin 1 Basin 2

Synthesis of GMACA Reverse Engineering Technique : 

Synthesis of GMACA Reverse Engineering Technique Phase III: GMACA rule vector from State transition table CA Research Group (BECDU) Basin 1 Basin 2 1 0 1 0 1 0 1 0 Rule 232

Synthesis of GMACA Reverse Engineering Technique : 

Synthesis of GMACA Reverse Engineering Technique Phase III: GMACA rule vector from State transition table CA Research Group (BECDU) Basin 1 Basin 2 0/1? Collision

Synthesis of GMACA Reverse Engineering Technique : 

Synthesis of GMACA Reverse Engineering Technique Phase III: GMACA rule vector from State transition table CA Research Group (BECDU) 0/1? Collision Less the number of collision better the design. Design Objective : Design GMACA so that there is minimum number of collision during rule formation Simulated Annealing to attain the design

Simulated Annealing Program Mutation Technique - 1 : 

Objective Reduce Collision Increment of Cycle Length Simulated Annealing Program Mutation Technique - 1

Simulated Annealing Program Increment of Cycle Length : 

Simulated Annealing Program Increment of Cycle Length 0/1?

Simulated Annealing Program Increment of Cycle Length : 

Simulated Annealing Program Increment of Cycle Length 0

Simulated Annealing Program Mutation Technique - 2 : 

Reduction of Cycle Length Simulated Annealing Program Mutation Technique - 2

Simulated Annealing Program Decrement of Cycle Length : 

Simulated Annealing Program Decrement of Cycle Length 0/1?

Simulated Annealing Program Decrement of Cycle Length : 

Simulated Annealing Program Decrement of Cycle Length 1

Performance of GMACA Based Pattern Recognizer : 

Memorizing Capacity Evolution Time Identification / Recognition Complexity Performance of GMACA Based Pattern Recognizer

Memorizing Capacity : 

Memorizing Capacity Conclusion : GMACA have much higher capacity than Hopfield Net

Evolution Time : 

Evolution Time

Identification / Recognition Complexity : 

Identification / Recognition Complexity Cost of Computation for Recognition / Identification - Constant

Achievements : 

Achievements 1.Cellular Automata - A powerful machine in designing the pattern recognition tool 2.Storage Capacity of CA - Higher than Hopfield Net 3.A clever reverse engineering technique is employed to design Cellular Automata based Associative Memory

Publications : 

Publications Study of Non-Linear Cellular Automata For Pattern Recognition To be published in IEEE Transaction, Man, Machine and Cybernetics, Part - B Generalized Multiple Attractor Cellular Automata(GMACA) Model for Associative Memory Niloy Ganguly, Pradipta Maji, Biplab k Sikdar and P Pal Chaudhuri To be published in International Journal for Pattern Recognition and Artificial Intelligence Error Correcting Capability of Cellular Automata Based Associative Memory, IEEE Transaction, Man, Machine and Cybernetics, Part - A

Thank you : 

Thank you Niloy Ganguly n_ganguly@hotmail.com http://ppc.becs.ac.in