群体智慧--复杂网络上的最佳共识形成

Xiaofan Wang xfwang@sjtu.edu.cn 天地交而万物通 上下交而其志同 2011上海复杂系统论坛 Complex Networks & Control Lab, SJTU SOCIAL LEARNING IN COMPLEX NETWORKS What is social learning? (Consensus on the true state)  Our recent researches (Pinning, Similarity‐based, Chaos) Social learning algorithms (Bayesian + Consensus) 我的在线历程 2000 2005 2006 2010 2011 你所关注的人数 =？ 你的粉丝数 围脖上所有关注的人数 =！ 围脖上所有的粉丝数 汪小帆老师 90 关注 4761 粉丝 任志强汪小帆 09.7-10.3: Twitter上的2亿6千万条信息 ¾ 极度不均匀：50%的信息来自0.05%的精英 ¾ 并非很社会：用户更愿意发帖而不是跟帖 ¾ 高度同质化：名人跟名人、媒体跟媒体 ¾ 两步信息流：媒体产生的一半的信息是经 由“草根”意见领袖扩散的 ¾ 不同生命期：媒体信息最短命，视频和音乐等最长命 人肉搜索为何百发百中？ Complex Networks & Control Lab, SJTU 教育医疗等却为何如此难以形成最佳共识？ 围脖上的意见领袖对粉丝的影响力有多大？ 热门话题、名人堂。。。 群体智慧：大众比精英更聪明！ Galton, Nature, 1907 ¾ Private signals ¾ Network structure ¾ Update rules Observing Communicating Updating Beliefs Social Learning Process 1 2 3 一致性：能否形成共识？ 最优性：是否最佳共识？ 可控性：能否引导共识？ Complex Networks & Control Lab, SJTU Case study: Who is singing? State space True state Private signal Likelihood function Network structure , ,0 ( ) 1, ( ) 1i t k i t k k μ θ μ θ≤ ≤ =∑ , ( *) 1i tμ θ → Belief Complex Networks & Control Lab, SJTU { }1 2, , , nθ θ θΘ = L *θ ∈Θ i ts ( | ) 1i s l s θ =∑ ( , )G V E= ‹观察到真实状态产生的充分信号 ‹不存在与真实状态等价的观测状态 ‹ 对真实状态的初始信念为正 Bayesian Learning： A Single Agent Case ( )t→∞*( ) 1Ptμ θ → 1 1 1 1 1 ( | ) ( )( ) ( | ) ( ) t t t t t t l ss m s θ μ θμ θ μ θ ++ + + + =� Complex Networks & Control Lab, SJTU Observationally equivalent states Agent i is called an indiscriminative agent *: , ( | ) ( | ) for all i i ii i il s l s s Sθ θ θ θ θ∗∃ ∈Θ ≠ = ∈ Complex Networks & Control Lab, SJTU ¾ Each agent should know the global structure of the network ¾ Each agent tries to deduce the information of every other agent Bayesian Social Learning: Network Case Computation burden + high complexity Complex Networks & Control Lab, SJTU ( | ) ( )( | ) ( ) l ss m s θ μ θμ θ = 人肉搜索有效克服了这两个困难！ Consensus Algorithm Consensus , 1 , ,( ) ( ) i i t ii i t ij j t j N a a Complex Networks & Control Lab, SJTU μ θ μ θ μ θ+ ∈ = + ∑ （ ） , ,( )i t j tμ θ μ θ− →（ ） 0 , ( )i tμ θ → 0 , ( *) 1i tμ θ → θ∀ ∈Θ θ∀ ∈Θ *θ θ∀ ≠ Social Learning = Best Consensus Consensus Algorithm Consensus , ,0 1( )i t j jN μ θ μ θ→ ∑ （） Consensus Algorithm Consensus , 1 , ,( ) ( ) i i t ii i t ij j t j N a a Complex Networks & Control Lab, SJTU μ θ μ θ μ θ+ ∈ = + ∑ （ ） , ,( )i t j tμ θ μ θ− →（ ） 0 , ( )i tμ θ → 0 , ( *) 1i tμ θ → θ∀ ∈Θ θ∀ ∈Θ *θ θ∀ ≠ Social Learning = Best Consensus Consensus Algorithm Consensus , ,0 1( )i t j jN μ θ μ θ→ ∑ （） Consensus Algorithm Consensus , 1 , ,( ) ( ) i i t ii i t ij j t j N a a Complex Networks & Control Lab, SJTU μ θ μ θ μ θ+ ∈ = + ∑ （ ） , ,( )i t j tμ θ μ θ− →（ ） 0 , ( )i tμ θ → 0 , ( *) 1i tμ θ → θ∀ ∈Θ θ∀ ∈Θ *θ θ∀ ≠ Social Learning = Best Consensus Consensus Algorithm Consensus , ,0 1( )i t j jN μ θ μ θ→ ∑ （） Consensus Algorithm Consensus , 1 , ,( ) ( ) i i t ii i t ij j t j N a a Complex Networks & Control Lab, SJTU μ θ μ θ μ θ+ ∈ = + ∑ （ ） , ,( )i t j tμ θ μ θ− →（ ） 0 , ( )i tμ θ → 0 , ( *) 1i tμ θ → θ∀ ∈Θ θ∀ ∈Θ *θ θ∀ ≠ Social Learning = Best Consensus Consensus Algorithm Consensus , ,0 1( )i t j jN μ θ μ θ→ ∑ （） θ∀ ∈Θ Bayesian vs. Consensus Consensus/ Synchronization Bayesian Learning N e t w o r k C o m p l e x i t y Rationality Just average, but not necessarily true! Demand strict!Boundedly Rational Learning We se ek Complex Networks & Control Lab, SJTU , i j t j N μ θ ∈ ∑ （ ） , 1 ( )i tμ θ+ = θ∀ ∈Θ , 1 1 ,( ) ( | ) ( ) i i i t t i t i tm s l s θ θ μ θ+ + ∈Θ = ∑ Bayesian Consensus [Jadbbaie, Sandroni, and Tahbaz-saleh 2010] 1 , , 1 ( | ) ( ) ( ) i i t i t i i t t l s m s θ μ θ+ + iia ij a+ Bayesian+ Consensus Complex Networks & Control Lab, SJTU (e) There is no other state that is observationally equivalent to the true state from the point of all agents in the network. The Wisdom of Crowds (a) The social network is strongly connected; (b) All agents have strictly positive self-reliances; (c) There exists an agent with positive prior belief on the true state; * , ( ) 1i tμ θ → 1 , 1 , , , 1 ( | )( ) ( ) ( ) i i i t i t ii i t ij j ti j Ni t t l sa a m s θμ θ μ θ μ θ++ ∈+ = + ∑ （ ） with probability one Complex Networks & Control Lab, SJTU θ∀ ∈Θ 1. Uninformed agents: those who can’t observe their  private signals; 2. Similarity-based communication: two agents are neighbors only if they have similar beliefs; 3. Chaos in social learning with multiple true states Our recent works Complex Networks & Control Lab, SJTU Uninformed agents Remark: Jadbabaie’s model Consensus l n= 0l = Social learning with uninformed agents Informed agents 1 , 1 , , , 1 ( | )( ) ( ) , 1, 2, , ( ) i i i t i t ii i t ij j ti j Ni t t l sa a i l m s θμ θ μ θ μ θ++ ∈+ = + =∑ L（ ） , 1 , ,( ) ( ) , 1, , i i t ii i t ij j t j N a a i l nμ θ μ θ μ θ+ ∈ = + = +∑ L（ ） Complex Networks & Control Lab, SJTU (e) There is no state that is observationally equivalent to the true state from the point of all informed agents in the network. Social learning with uninformed agents Suppose that (a) The social network is strongly connected; (b) There exists at least one informed agent and all self-reliance of informed agents are strictly positive; (c) There exists at least one agent with positive prior belief on the true state; , ( *) 1i tμ θ → Complex Networks & Control Lab, SJTU In a power-law network with tunable exponent 2.1γ = 10γ = Social learning with uninformed agents Heterogeneous Homogeneous N=1000, two states, two signals {H, T}                    Prior beliefs: uniform distribution in [0,1],   aii=0.5 Complex Networks & Control Lab, SJTU Similarity Breeds Connection: Homophily Principle in Sociology Complex Networks & Control Lab, SJTU { }, ,( ) :i j t i tN t j V rμ μ= ∈ − ≤ ( ) ( ) ( )( ) ( )1, 1 , ,( ), 1 |1 ( ) i i t i t i t j ti j N ti i t t p s N t m s θμ θ μ θ μ θ++ ∈+ ⎛ ⎞= +⎜ ⎟⎜ ⎟⎝ ⎠ ∑ Neighbors of agent i Update rule Social learning with similarity-based communication Confidence radius Complex Networks & Control Lab, SJTU r = 0.3 r = 0.1 r = 0.02 容忍差异才能一致 N=100, 20 discriminative agents,  80 indiscriminative agents Two states, two signals {H, T} Prior beliefs: random distribution in [0,1] Originally connect Complex Networks & Control Lab, SJTU Differences Between Tight and Loose Cultures: A 33-Nation Study If one were to order all mankind to choose the best set of rules in the world, each group would, after due consideration, choose its own customs; each group regards its own as being the best by far. ---Herodotus Complex Networks & Control Lab, SJTU ScMichele J. Gelfand, et al.ience27 May 2011: Vol. 332 no. 6033 pp. 1100-1104 The Wisdom of Crowds The larger the group， the smaller the confidence radius needed for asymptotic learning. Complex Networks & Control Lab, SJTU The larger the group, the smaller the proportion of discriminative agents needed for asymptotic learning. The Wisdom of Crowds Discriminative agents Indiscriminative agents Complex Networks & Control Lab, SJTU 2 r 2 r Feasible region Belief update without losing old neighbors Connectivity preserve strategy Social learning with similarity-based communication Connectivity preserve Hideki Ando et al. IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 15, NO. 5, 1999 r = 0.3 r = 0.1 r = 0.02 ¾ Under the connectivity preserved strategy, asymptotic learning can  be achieved only if the initial network is connected Social learning with similarity-based communication Complex Networks & Control Lab, SJTU Different communities might have different underlying true states Social learning with multiple true states Complex Networks & Control Lab, SJTU A connected network with two groups with two underlying true states respectively. Social learning with multiple true states Signals received by  agents 6‐10 are  generated by Signals received by  agents 1‐5 are  generated by Three states                     Two signals {H,T}Prior beliefs: 1/3 Complex Networks & Control Lab, SJTU { }1 2 3, ,θ θ θ 2( | )l s θ 1( | )l s θ Belief evolution of agents in group A1Belief evolution of agents in group A1 Belief evolution of agents in Group A2Belief evolution of agents in Group A2 Social learning with multiple true states Complex Networks & Control Lab, SJTU 0.33500.33380.1481Group 2 0.19370.30190.1999Group 1 State 3State 2State 1 Social learning with multiple true states Largest Lyapunov exponents Complex Networks & Control Lab, SJTU 0.90930.74260.6915Group 0.92360.73200.7251Group StateStateState Hurst exponents H • New adaptive social learning model • Methods for misinformation dynamics • Models for belief manipulation …… What’s next? Complex Networks & Control Lab, SJTU Complex Networks & Control Lab, SJTU Xiaofan Wang  Shanghai Jiao Tong University xfwang@sjtu.edu.cn