------ SOM ----------- Describe the parameters for training SOMs, what would happen if you used extreme values and how to select the right parameter value. * (random seed) * map size * learning rate: how far should the unit be drawn to the selected input vector * neighborhood radius (sigma): How many neighbors should be drawn with the best matching unit * number of iterations Difference between SOM and other clustering methods * goal is to visualize the data and get information out of it * don't forecast directly, use data to continue calculations What is ”Magnification factor”, why is it there, and how can it be used/is useful * some areas of the space may be represented by a lot of units, others by none / only a few * reason: more training data there --> pulling more units to that area * useful, because it gives detailed information about very dense areas Explanation of the SOM learning algorithm. What is the main difference between SOM and other clustering methods. What is the complexity of the training (in O-notation) 1. select random input vector 2. calculate activation function for all weight vectors 3. select best matching weight vector (highest activation function, lowest distance) 4. pull winner and his neighbors to selected input vector 5. start over, when not reached closing criterion Name and explain 4 different SOM visualizations and explain them / what do they show. * Class distribution (pie charts) * Component planes * Metro lanes * Neighborhood Graphs * cluster connections Name and explain 2 quality measurements for SOM and describe two examples for each. When can the qe of a unit be high, but the mqe small? * Quantization errors * Topology violations (data close in input space far away in output space) - neighborhood graphs - topographic error (% of data samples, where second-best matching is not neighboring best matching) - topographic product: mean of mismatching in ranking of k closest weight vectors (distortion) in input and output vectors Explain the rationale for picking the size of the SOM and its impact on subsequent parameter setting (neighborhood rate, learning rate) How sensitive are these parameter settings, which aspects need to be considered, what is the impact of picking a wrong setting? Explain the reason for the following characteristics of the SOM training process, how they can be detected, how they can be used/interpreted during data analysis: a) magnification factors * see above * detected: with density visualization b)border effect * outliers are located at the borders / edges of the map - they can be detected by looking through this units which are (maybe even far away from the rest) in the corners --> help getting to know the data, maybe finding outliers which could be eliminated (e.g. wrong data like age 435 - typing errors) a) What are topology violations and why is it impossibly have a map without them. * data items close in the input space - not close to each other in the output space * so many parameters mapped onto a 2d visualization b) Describe two visualisations for analyzing topology violations. * neighborhood graphs * ?? * topographic error c) How can topology violations be avoided? ----- general ------- What is self organisation? Properties? Name 2 Examples * Process, where a global order results from an initially disorder system by local interactions between components. * Spontaneously (not directed or controlled by any agent or subsystem) --> Rules * Towards attractor (equilibrium - Ausgeglichenheit) Properties: * Strong dynamically non-linearity (often involving positive/negative feedback) * Multiple interactions * Complex (elements interlinked by many & constantly chaning relations) * Self-referring: behavior has impact on the system and future behavior * Autonomous Examples: * Cellular Automata * Mulit Agent Systems * Swarm Intelligence (Ant Colognize Optimization, Swarm Particle Optimization) What is the difference between a complex and a complicated system? * complicated: needs expertise and expirience - designed to have a relative high certainty of outcome repitition (e.g. sending rocket in space) * complex: based on relations, self-organizing and evolution --> expertise/expirience is welcome, but not neccessary. ------- Cellular Automata (CA) ----------- Calculate 7 steps for 01011 with the rule that a cell survives if exactly 1 cell in the neighbourhood is alive.. 01011 1100111 111111011 11000010111 1111001001011 110011101100111 11111101011111011 01011 110001 10010111 1111100001 100000100111 11100011110001 1000101000010111 111011011001100001 Calculate 6 steps for 01011 with the rule that a cell survives if exactly 2 cells in the neighbourhood are alive (neighbourhood = cell itself and its two neighbours) 01011 00111 00101 00010 00000 00000 00000 Gosper glider gun? * From Game of Life (cellular automata in 2d, where rules are with moores neighborhood: if dead and 3 neighbors alive --> switch to alive; if alive and not 2 or 3 neighbors alive --> switch to dead) --> a "gun", which generates new elements, which "fly away" 3 types of rules in CA * explicit (defining next state for every possible situation) * totalistic (next state defined by sum of neighbors) --> GoL * legal (subset of explicit, where only some rules are needed --> also their symmetric sibling are valid) Name 2 examples of problems that CA are often applied to. * simulating complex sytems with simple rules (e.g. traffic) --> Nagel-Schreckenberg!! * generating (pseudo) random numbers * cryptography Name and explain properties of cellular automata. * finite and discrete cell states * all cells have identical properties and transition rules * Describe Nagel–Schreckenberg model * simulate traffic * rules: 1. accelerate by 1 2. break if necessary 3. slow down randomly by 1 4. move ------- Genetic Algorithms (GA) ------- Name 3 genetic operators that are used in Genetic Algorithms * (Selection) * Pairing * Crossover * Mutating What is genetic algorithm. * an algorithm which is designed to optimize by learning --> e.g. maximize yield, minimize effort (Travelling Salesman) 1. Start population 2. Selection 3. Pairing / Mating 4. Crossover 5. Mutating 6. if not stopping --> jump to 2 What is gray coding. * like binary coding, but between every increase only 1 bit changes --> e.g. one is 01, two is 11, three is 10 * hemming distance between one iteration is always 1 What problems can be solved with Genetic algorithms * Maximization problems (e.g. maximize yield, minimze effort --> travelling salesman) * combinational problem (Travelling salesman) * subset selection * model finding Why is diversity an issue, and how can it be controlled? * without diversity we would get stuck in local optimum * too much diversity leads to ??? no ending??? * control: by mating and selection ------- Ant Colony Optimization (ACO) ------- Which types of problems can be solved with Ant Colony System. * building of geometrically complex mounds * finding shortest path to food sources Name one extension of Ant Colony System and explain which shortages it tries to eliminate. * Ant Colony System * idea: reduce effort for exploring new ways ------- Agent Sytems (Multi Agent Systems - MAS) ----------- Name and explain properties of agent-based-system. * Autonomous! capable of acting independently, exhibiting control over internal state. * Flexibility * Reactivity * Pro-activity * Social ability Explain the different layers of agent communication. * Message Semantics: What does each message mean? * Message Syntax: How is each message expressed? * Interaction Protocol: How are conversations structured * Transport protocol: How are messages actually sent and received? ------- Other crap ---------- Incremental Grid Growing a) Motivation for Incremental Grid Growing * SOM has fixed size * no support for discovering hierarchical structures b) Shortcomings of SOMs that can be solved with Incremental Grid Growing. * Strong differences in shape and density of input vector distribution c) How Incremental Grid Growing works * start with 4 units * add units where mapping error is highest * check if connections are still valid and if new ones should be added