Lecture II: complex Networks - KTH

Lecture II: complex Networks - KTH

Lecture VI: Adaptive Systems Zhixin Liu Complex Systems Research Center , Academy of Mathematics and Syst ems Sciences, CAS In the last lecture, we talked about Game Theory An embodiment of the complex interactions among individuals Nash equilibrium Evolutionarily

stable strategy In this lecture, we will talk about Adaptive Systems Adaptation To adapt: to change oneself to conform to a new or changed circumstance. What we know from the new circumstance? Adaptive estimation, learning, identification How to do the corresponding response?

Control/decision making Why Adaptation? Uncertainties always exist in modeling of practical systems. Adaptation can reduce the uncertainties by using the system information. Adaptation is an important embodiment of human intelligence. Framework of Adaptive Systems Environment sy s sy

m te co ro nt l co nt ro l st e m

system control system system control control Two levels of adaptation Individual: learn and adapt

Population level Death of old individuals Creation of new individuals Hierarchy Some Examples Adaptive control systems adaptation in a single agent Iterated prisoners dilemma adaptation among agents

Some Examples Adaptive control systems adaptation in a single agent Iterated prisoners dilemma adaptation among agents Adaptation In A Single Agent Environment ut wt system control

yt Information wt ut Dynamical System yt Information= prior+ posterior =I0+I1 I0 = prior knowledge about the system I1 = posterior knowledge about the system ={u0,u1,ut, y0,y1,,yt} (Observations)

The posterior information can be used to reduce the uncertainties of the system. Uncertainty Model External Uncertainty External uncertainty: noise/disturbance Internal uncertainty:

Parameter uncertainty Signal uncertainty Functional uncertainty Internal Uncertainty Adaptation To adapt: to change oneself to conform to a new or changed circumstance. What we know from the new circumstance? Adaptive estimation, learning, identification

How to do the corresponding response? Control/decision making Adaptive Estimation Adaptive Estimation Adaptive estimation: parameter or structure estimator, which can be updated based on the on-line observations. t Adaptive Estimator

e + ut System yt Example: In the parametric case, the parameter estimator can be obtained by minimizing certain prediction error:

t arg min certain prediction error Adaptive Estimation Parameter estimation Consider the following linear regression model: : unknown parameter vector : regression vector : noise sequence Remark Linear regression model may be nonlinear. Linear system can be translated into linear regression model.

Least Square (LS) Algorithm 1795, Gauss, least square algorithm The number of functions is greater than that of the unknown parameters. The data contain noise. Minimize the following prediction error: t

J t ( ) yi 1 t i 0 2 Recursive Form of LS Recursive Form of LS: where Pt is the following estimation covariance matrix A basic problem: Recursive Form of LS Assumption 1: 1) The noise sequence

and there exists a constant 2) The regression vector is a martingale difference sequence, , such that is an adaptive sequence, i.e., Theorem (T.L. Lai & C.Z. Wei) Under the above assumption, if the following condition holds then the LS has the strong consistency. Weighted Least Square Minimize the following prediction error:

Recursive form of WLS: Self-Convergence of WLS Take the weight with as follows: . Theorem Under Assumption 1, for any initial value and any regression vector , will converge to some vector almost surely. Lei Guo, 1996, IEEE TAC

Adaptation To adapt: to change oneself to conform to a new or changed circumstance. What we know from the new circumstance? Adaptive estimation, learning, identification How to do the corresponding response? Control/decision making Adaptive Control Adaptive Control

Adaptive Control: a controller with adjustable parameters (or structures) together with a mechanism for adjusting them. Adaptive Estimator u y Plant r Adaptive Controller r

Robust Control Model = Nominal +Ball r Can not reduce uncertainty! Adaptive Control An example Consider the following linear regression model: Where a and b are unknown parameters, yt , ut, and wt are the outp ut, input and white noise sequence. Objective: design a control law to minimize the follo wing average tracking errors

Adaptive Control If (a,b) is known, we can get the optimal controller: Certainty Equivalence Principle: If (a,b) is unknown, the taken as Replace the unknown parameters in a nonadaptive controller by its online estimate adaptive controller can be Adaptive control If (a,b) is unknown, the adaptive controller can be taken as

with where (at,bt) can be obtained by LS: Adaptive Control The closed-loop system: Theoretical Problems a) Stability: b) Optimality: Theoretical Obstacles Controller Closed-loop system

Estimation Data Theoretical Obstacles 1) The closed-loop system is a very complicated nonlinear stochastic dynamical system. 2) No useful statistical properties, like stationarity or independency of the system signals are available. 3) No properties of (at, bt) are known a priori. Theorem Assumption: 1) The noise sequence and there exists a constant

2) The regression vector 3) is a martingale difference sequence, , such that is an adaptive sequence, i.e., is a deterministic bounded signal. Theorem Under the above assumptions, the closed-loop system is stable and optimal. Lei Guo, Automatica, 1995 Some Examples Adaptive control systems adaptation in a single agent

Iterated prisoners dilemma adaptation among agents Prisoners Dilemma The story of prisoners dilemma Player: two prisoners Action: {cooperation, Defect} Payoff matrix Prisoner B C Prisoner A D

C (3,3) (0,5) D (5,0) (1,1) Prisoners Dilemma No matter what the other does, the best

choice is D. (D,D) is a Nash Equilibrium. But, if both choose D, both will do worse than if both select C Prisoner B C Prisoner A D C (3,3) (0,5)

D (5,0) (1,1) Iterated Prisoners Dilemma The individuals: Meet many times

Can recognize a previous interactant Remember the prior outcome Strategy: specify the probability of cooperation and defect based on the history P(C)=f1(History) P(D)=f2(History) Strategies Tit For Tat cooperating on the first time, then repeat opponent's last choice. Player A C D D C C C C C D D D D C

Player B D D C C C C C D D D D C Tit For Tat and Random - Repeat opponent's last choice skewed by random setting.* Tit For Two Tats and Random - Like Tit For Tat except that opponent must make the sam e choice twice in a row before it is reciprocated. Choice is skewed by random setting.* Tit For Two Tats - Like Tit For Tat except that opponent must make the same choice twice in row before it is reciprocated.

Naive Prober (Tit For Tat with Random Defection) - Repeat opponent's last choice (ie Tit F or Tat), but sometimes probe by defecting in lieu of cooperating.* Remorseful Prober (Tit For Tat with Random Defection) - Repeat opponent's last choice (i e Tit For Tat), but sometimes probe by defecting in lieu of cooperating. If the opponent defe cts in response to probing, show remorse by cooperating once.* Naive Peace Maker (Tit For Tat with Random Co-operation) - Repeat opponent's last choic e (ie Tit For Tat), but sometimes make peace by co-operating in lieu of defecting.* True Peace Maker (hybrid of Tit For Tat and Tit For Two Tats with Random Cooperation) Cooperate unless opponent defects twice in a row, then defect once, but sometimes make peace by cooperating in lieu of defecting.* Random - always set at 50% probability Strategies Tit For Tat cooperating on the first time, then repeat opponent's last choice. Player A C D D C C C C C D D D D C

Player B D D C C C C C D D D D C Tit For Tat and Random - Repeat opponent's last choice skewed by random setting.* Tit For Two Tats and Random - Like Tit For Tat except that opponent must make the sam e choice twice in a row before it is reciprocated. Choice is skewed by random setting.* Tit For Two Tats - Like Tit For Tat except that opponent must make the same choice twice in row before it is reciprocated.

Naive Prober (Tit For Tat with Random Defection) - Repeat opponent's last choice (ie Tit F or Tat), but sometimes probe by defecting in lieu of cooperating.* Remorseful Prober (Tit For Tat with Random Defection) - Repeat opponent's last choice (i e Tit For Tat), but sometimes probe by defecting in lieu of cooperating. If the opponent defe cts in response to probing, show remorse by cooperating once.* Naive Peace Maker (Tit For Tat with Random Co-operation) - Repeat opponent's last choic e (ie Tit For Tat), but sometimes make peace by co-operating in lieu of defecting.* True Peace Maker (hybrid of Tit For Tat and Tit For Two Tats with Random Cooperation) Cooperate unless opponent defects twice in a row, then defect once, but sometimes make peace by cooperating in lieu of defecting.* Random - always set at 50% probability Strategies

Always Defect Always Cooperate Grudger (Co-operate, but only be a sucker once) - Cooperate until the opponent defects. Then always defect unforgivingly. Pavlov (repeat last choice if good outcome) - If 5 or 3 points scored in the last ro und then repeat last choice. Pavlov / Random (repeat last choice if good outcome and Random) - If 5 or 3 p oints scored in the last round then repeat last choice, but sometimes make rand

om choices.* Adaptive - Starts with c,c,c,c,c,c,d,d,d,d,d and then takes choices which have gi ven the best average score re-calculated after every move. Gradual - Cooperates until the opponent defects, in such case defects the total number of times the opponent has defected during the game. Followed up by tw o co-operations. Suspicious Tit For Tat - As for Tit For Tat except begins by defecting. Soft Grudger - Cooperates until the opponent defects, in such case opponent is punished with d,d,d,d,c,c. Customised strategy 1 - default setting is T=1, P=1, R=1, S=0, B=1, always cooperate unless sucker (ie 0 points scored). Customised strategy 2 - default setting is T=1, P=1, R=0, S=0, B=0, always pla y alternating defect/cooperate. Iterated Prisoners Dilemma Which strategy can thrive/what is the good

strategy? Robert Axelrod, 1980s A computer round-robin tournament The first round The second round AXELROD R. 1987. The evolution of strategies in the iterated Prisoners' Dilemma. In L. Davis, editor, Genetic Algorithms and Simulated Annealing. Morgan Kaufmann, Los Altos, CA. Characters of good strategies Goodness: never defect first First round: the first eight strategies with goodness Second round: fourteen strategies with goodness in the

first fifteen strategies Forgiveness: may revenge, but the memory is short. Grudger is not s strategy with forgiveness Goodness and forgiveness is a kind of collective behavior. For a single agent, defect is the best strategy. Evolution of the Strategies

Evolve good strategies by genetic algorithm (GA) Some Notations in GA String: the individuals, and it is used to represent t he chromosome in genetics. Population: the set of the individuals Population size: the number of the individuals Gene: the elements of the string

E.g., S 1011, where 1 0 1 1 are called ge nes. Fitness: the adaptation of the agent for the circum stance From Jing Hans PPT How GA works? Represent the solution of the problem by chromosome, i.e., the string Generate some chromosomes as the initial solution randomly

According to the principle of Survival of the Fittest , the chromosome with high fitness can reproduce, then by crossover and mutation the new generation can be generated. The chromosome with the highest fitness may be the solution of the problem. From Jing Hans PPT Natural Selection

GA Create new generation crossover mutation choose an initial population determine the fitness of each individual perform selection

repeat perform crossover perform mutation determine the fitness of each individual perform selection until some stopping criterion applies From Jing Hans PPT Some Remarks On GA

The GA search the optimal solution from a set of solution, rather than a single solution The search space is large: {0,1}L GA is a random algorithm, since selection, crossover and mutation are all random operations. Suitable for the following situation:

There is structure in the search space but it is not wellunderstood The inputs are non-stationary (i.e., the environment is changing) The goal is not global optimization, but finding a reasonably good solution quickly Evolution of Strategies By GA Each chromosome represents one strategy The strategy is deterministic and it is determined by the previous moves.

E.g., the strategy is determined by one step history, then there are four cases of history Player I C D D C Player II D D C C The number of the possible strategies is 2*2*2*2=16. TFT: F(CC)=C, F(CD)=D, F(DC)=C, F(DD)=D Always cooperate: F(CC)=F(CD)=F(DC)=F(DD)=C Always defect: F(CC)=F(CD)=F(DC)=F(DD)=D

Evolution of the Strategies Strategies: use the outcome of the three previous moves to deter mine the current move. The possible number of the histories is 4*4*4=64. Player I CCC CCD CDC CDD DCC DCD DDD DDD Player II CCC CCC CCC CCC CCC CCC DDC DDD

C C C C C C C C C C

C C C C C D D D

D D D D D D The initial premises is three hypothetical move. The length of the chromosome is 70. The total number of strategies is 2701021.

Evolution of good strategy Five steps of evolving good strategies by GA An initial population is chosen. Each individual is run in the current environment to determine its effectiveness. The relatively successful individual are selected to have more

offspring. The successful individuals are randomly paired off to produce two offspring per mating. Crossover: way of constructing the chromosomes of the two offspring from the chromosome of two parents. Mutation: randomly changing a very small proportion of the Cs to Ds and vice versa. New population are generated. Evolution of the Strategies Some parameters: The population size in each generation is 20. Each game consists of 151 moves. Each of them meet eight representatives, and this made about 24,000 moves per

generation. A run consists of 50 generation Forty runs were conducted. Results The median member is as successful as TFT Most of the strategies is resemble TFT Some of them have the similar patterns as TFT

Do not rock the boat: continue to cooperate after the mutual coope ration Be provocable: defect when the other player defects out of the blu e Accept an apology: continue to cooperate after cooperation has b een restored Forget: cooperate when mutual cooperation has been restored aft er an exploitation Accept a rut: defect after three mutual defections What is a good strategy? TFT

is a good strategy? Tit For Two Tats may be the best strategy in t he first round, but it is not a good strategy in t he second round. Good strategy depends on other strategies, i.e., environment. Evolutionarily stable strategy Evolutionarily stable strategy (ESS) Introduced by John Maynard Smith and George R. Price in 1973

ESS means evolutionarily stable strategy, that is a strategy such that, if all member of the population adopt it, then no mutant strategy could invade the population under the influence of natural selection. John Maynard Smith, Evolution and the Theory of Games ESS is robust for evolution, it can not be invaded by mutation. Definition of ESS A strategy x is an ESS if for all y, y x, such that x U ((1 ) x y ) y U ((1 ) x y )

holds for small positive. ESS in IPD Tit For Tat can not be invaded by the wiliness strategies, such as always defect. TFT can be invaded by goodness strategies, such as always cooperate, Tit For Two Tats and

Suspicious Tit For Tat Tit For Tat is not a strict ESS. Always Cooperate can be invaded by Always Defect. Always Defect is an ESS. Other Adaptive Systems Complex adaptive system John Holland, Hidden Order, 1996 Examples: stock market, social insect, ant colonies, biosphere, brain, immune system, cell , developing embryo,

Evolutionary algorithms genetic algorithm, neural network, References Lei Guo, Self-convergence of weighted least-squares with applications to stochas tic adaptive control, IEEE Trans. Automat. Contr., 1996, 41(1): 79-89. Lei Guo, Convergence and logarithm laws of self-tuning regulators, 1995, Autom atica, 31(3): 435-450. Lei Guo, Adaptive systems theory: some basic concepts, methods and results, Jo urnal of Systems Science and Complexity, 16(3): 293-306. Drew Fudenberg, Jean Tirole, Game Theory, The MIT Press, 1991.

AXELROD R. 1987, The evolution of strategies in the iterated Prisoners' Dilem ma. In L. Davis, editor, Genetic Algorithms and Simulated Annealing. Morgan Kau fmann, Los Altos, CA. Richard Dawkins, The Selfish Gene, Oxford University Press. John Holland, Hidden Order, 1996. Adaptation in games Adaptation in a single agent Summary In these six lectures, we have talked about: Complex Networks Collective Behavior of MAS Game Theory Adaptive Systems

Summary In these six lectures, we have talked about: Complex Networks: Topology Collective Behavior of MAS Game Theory Adaptive Systems Three concepts Average path length l 2 d ij

N ( N 1) i j where dij is the shortest distance between i and j. Clustering Coefficient C= ShortC (average number of path triangles length centered at node i i) number of triples centered at node i Large clustering coefficient Degree distribution

P(k)=probability that the randomly chosen node i has exactl Power law degree distribution y k neighbors Regular Graphs Regular graphs: graphs where each vertex has the same number of neighbors. Examples:

complete graph ring graph

lattice Random Graph ER random graph model G(N,p) Given N nodes Add an edge between a randomly-selected pair of nodes wi th probability p Homogeneous nature: each node has roughly the same

number of edges Small World Networks WS model Introduce pNK/2 long-range edges A few long-range links are sufficient to decrease l, but will not significantly change C. Scale Free Networks Some observations A breakthrough: Barabsi & Albert, 1999, Science Generating process of BA model: 1) Starting with a network with m0 nodes

2) Growth: at each step, we add a new node with m(mm0) edges tha t link the new node to m different nodes already present in the net work. 3) Preferential attachment: When choosing the nodes to which the new nodes connects, we assume that the probability that a new node will be connected to node i on the degree ki of node i, such th at Summary In these six lectures, we have talked about: Complex Networks: Topology Collective Behavior of MAS: More is different Game Theory Adaptive Systems Multi-Agent System (MAS) MAS

Many agents Local interactions between agents Collective behavior in the population level More is different.---Philp Anderson, 1972 e.g., Phase transition, coordination, synchronization, consensus, c lustering, aggregation, Examples:

Physical systems Biological systems Social and economic systems Engineering systems Vicsek Model Neighbors: N i (t ) { j : xi (t ) x j (t ) r} Position: xi (t 1) xi (t ) v(cos i (t 1), sin i (t 1))

Heading: sin (t ) j j N (t ) i i (t 1) arctan cos ( t )

j j N i (t ) Theorem 2 (Jadbabaie et al. , 2003) Joint connectivity of the neighbor graphs on each time interval [th, (t+1)h] with h >0 Synchronization of the linearized V icsek model Related result: J.N.Tsitsiklis, et al., IEEE TAC, 1984 Theorem 7

High Density Implies Synchronization For any given system parameters v 0 and r 0, when the number of agnets n is large, the Vicsek model will synchronize al most surely. This theorem is consistent with the simulation result. Theorem 8 High density with short distance interaction log n rn o(1), n Let velocity satisfy

16 o( rn ), and the r6 n vn O n 3 / 2 . log n Then for large population, the MAS will synchronize almost surely. Soft Control

U(t) y(t) Key points: Different from distributed control approach. Intervention to the distributed system Not to change the local rule of the existing agents

Add one (or a few) special agent called shill based on the syst em state information, to intervene the collective behavior; The shill is controlled by us, but is treated as an ordinary agent by all other agents. Shill is not leader, not leader-follower type. Feedback intervention by shill(s). This page is very important! From Jing Hans PPT Leader-Follower Model Ordinary agents Information agents

Key points: Not to change the local rule of the existing agents. Add some (usually not very few) information agents called leaders, to control or intervene the MAS; But the existing agents treated them as ordinary agents. The proportion of the leaders is controlled by us (If the number of leaders is small, then connectivity may not be guaranteed). Open-loop intervention by leaders.

Summary In these six lectures, we have talked about: Complex Networks: Topology Collective Behavior of MAS: More is different Game Theory: Interactions Adaptive Systems Definition of Nash Equilibrium Nash Equilibrium (NE): A solution concept of a game

(N, S, u) : a game Si: strategy set for player i : set of strategy profiles : payoff function s-i: strategy profile of all players except player i A strategy profile s* is called a Nash equilibrium if ui ( si* , s*i ) ui ( i , s*i ), i where i is any pure strategy of the player i. Definition of ESS A strategy x is an ESS if for all y, y x, such that x U ((1 ) x y ) y U ((1 ) x y )

holds for small positive. Summary In these six lectures, we have talked about: Complex Networks: Topology Collective Behavior of MAS: More is different Game Theory: Interactions Adaptive Systems: Adaptation Other Topics Self-organizing criticality Earthquakes, fire, sand pile model, Bak-Sneppen model

Nonlinear dynamics chaos, bifurcation, Artificial life Tierra model, gene pool, game of life, Evolutionary dynamics genetic algorithm, neural network,

Complex systems Not a mature subject No unified framework or universal methods

Recently Viewed Presentations

  • Program Planning

    Program Planning

    Simple behaviors - Simple task performed by the robot (fan stops when sensor activated) Basic behaviors - Single commands to the robot (turn on a motor) ... Program Design. Identify all inputs and outputs in the Motors and Sensors Setup...
  • Implemention Tool Kit

    Implemention Tool Kit

    How do you define and measure student outcomes in your school? Purpose. ... Over the last six years Lakemba Public School has worked assiduously to build on their performance and development processes, to build the professional capacity of the teachers...
  • Understanding The RCRA Corrective Action Program Terms 'SMWU ...

    Understanding The RCRA Corrective Action Program Terms 'SMWU ...

    UNDERSTANDING THE RCRA CORRECTIVE ACTION PROGRAM TERMS ' SWMU' & 'AOC' by David M. Buxbaum, Counsel Southern Regional Environmental Office
  • Firmament: Fast, Centralized Cluster Scheduling at Scale Ionel

    Firmament: Fast, Centralized Cluster Scheduling at Scale Ionel

    uses min-cost max-flow (MCMF) optimization. MCMF guarantees optimal task placements for a given scheduling policy. Flow Network. Directed graph whose arcs carry flow from source nodes to a sink node. All such flow must be drained into the sink node.
  • History 7 - Folsom Cordova Unified School District

    History 7 - Folsom Cordova Unified School District

    [W]orld history in this period can be a bewildering catalog of names, places, and events that impacted individual societies, while the larger patterns that affected the world are lost. To avoid this, the focus must be on questions that get...
  • Latin American Revolutions - Cabarrus County Schools

    Latin American Revolutions - Cabarrus County Schools

    Latin American countries are still mostly agricultural. Industrial develop needed. Patron of the hacienda provided homes, land, necessities, and protection for the peons. Patron ruler and judge for the peons. Peons worked for the patron. Patron kept peons in debt...
  • AMA Data Model Edward Birrane Edward.Birrane@jhuapl.edu 443-778-7423 We

    AMA Data Model Edward Birrane [email protected] 443-778-7423 We

    ADM attempts to formalize the AMA data/autonomy model. AMA/ADM/AMP Interactions. Separate the data specification from its encoding. Use AMP specification to define how to compactly encode ADM items. ADMs Schemas will define logical models.
  • Skull Bones - Mrs. Percy's Website

    Skull Bones - Mrs. Percy's Website

    Mental foramen- blood vessels and nerves to chin-Rami - 2 uprights from body-Mandibular notch- superior rami-Coronoid process-insertion of temporalis muscle (anterior)-Mandibular condyle - articulates with temporal bone at TMJ (posterior)-Mandibular foramina- medial surface of rami, nerves to lower teeth (novacaine...