《复杂》

作者 梅拉妮·米歇尔 亚马逊购书链接

17世纪以来，还原论在科学中占据主导地位。将问题尽可能细分，细分到能用最佳方式将其解决，然后上升，直到最复杂的知识。

20世纪有相对论和量子力学这样伟大的发现，但也见证了还原论梦想的破灭。因为在接近人类尺度的复杂现象上无能为力。例如天气预报、生物、疾病、经济、政治、文化、现代通讯。
所以出现了混沌、系统生物学、进化经济学、网络理论。需要交叉学科（包括控制论、协同学、系统科学），才出现复杂系统科学。

背景和历史

复杂性是什么

复杂系统试图解释，在不存在中央控制的情况下，大量简单个体如何自行组织成能够产生模式、处理信息甚至能够进化和学习的整体。

一些例子

• 蚂蚁。单个行军蚁几乎没有视力、智能，但可以执行复杂的动作，形成 有“群体智能（collective intelligence）”的“超生物（superorganism）”
• 大脑。最为神秘的是，所谓 智能和意识是从不具有智能和意识的物质中涌现出来的。
• 免疫系统。相对简单的部分组成信号传递和控制的复杂行为。
• 经济。人和公司组成“简单、微观的”个体，而整个市场行为复杂且无法预测。
• 万维网。每个人都看不到网络的全貌，只是简单的发布网页，并将其链接到其它网页。

复杂网络的共性

• 复杂的集体行为。
• 信号和信息处理。都利用内部和外部的信息，同时也产生信息。
• 适应性。都通过学习和进化进行适应。

复杂系统是由大量组分组成的网络，不存在中央控制，通过简单运作规则产生出复杂的集体行为和复杂的信息处理，并通过学习和进化产生适应性。

如果系统有组织的行为不存在内部和外部的控制者或领导者，则也称之为自组织（self-organizing）。由于简单规则以难以预测的方式产生出复杂行为，这种系统的宏观行为有时也称为涌现（emergent）。
这样就有了复杂系统的另一个定义：具有涌现和自组织行为的系统。
复杂性科学的核心问题是：涌现和自组织行为是如何产生的。

动力学、混沌和预测

这里作者回顾了物理历史。亚里士多德、哥白尼、伽利略、开普勒、牛顿。
然而，两个发现打破拉普拉斯精确预测的梦想：海森堡的测不准原理和混沌
所谓混沌性指的是初始值有微小的不精确，会导致长期计算结果的巨大误差。
（自然界也有很多不混沌的现象，你只要大概知道初始值，就能预测个八九不离十。这个叫做线性系统。）

庞加莱三体问题。

逻辑斯蒂映射

$x_{t+1}=R x_t (1-x_t)$

以兔子数量为例，书上用数字说明的，这里自己用公式试着推一下。假设出生率和死亡率分别是a, b，那么t+1时间的兔子数量 $x_{t+1}=(1+a-b)x_t$，其中，a, b 还与$x_t$有关，假设这个关系是最简单的线性关系，于是 $x_{t+1}=R x_t (1-x_t)$

吸引子。

• 随着R的不同，“吸引子”数量不同。
• 随着R提高，吸引子数量提高。
• 当R大于某个无理数时，吸引子变成无穷多个

所以，逻辑斯蒂映射有三种行为

• 不动点
• 周期
• 混沌

逻辑斯蒂分叉图，就不在这里画了。
“费根鲍姆常数” 在不同的混沌系统中有一定的普适性。

混沌系统的特点

• 混沌可以来自确定性系统，无须随机源。
• 简单的确定性系统也可以混沌
• 不同的混沌系统有一定的普适共性。“混沌中的秩序”，例如费根鲍姆常数。导致混沌虽然在细节上不可预测，但在更高层面上却是可预测的。

熵。热力学第二定律是唯一区分过去和未来的基本物理定律。

麦克斯韦妖

设计一个开关，让速度快的分子可以往右走，速度慢的分子可以往左走，这样熵就减少了。麦克斯韦认为，这说明热力学第二定律不是一条定律，而是大量分子下的统计效应。

为解决这个悖论。西拉德将熵和信息联系起来，认为测量过程获取比特，这需要能量，必然产生熵。整个系统仍然遵守热力学第二定律。
重新定义信息比特的概念：通过回答是/否获得的信息。
在当时，人们基本把物理和精神过程视为完全独立，并不觉得“小妖”的智能会有热力学影响。但量子力学发现观察者的影响后，人们才意识到这一点。

班尼特证明，可以用一种巧妙的方式弄清楚分子的快慢，并且不增加熵。这套理论成为 可逆计算（reversible computing） 的基础，理论上可以进行任何计算而不耗费能量。
不是测量行为，而是擦除记忆的行为，增加熵。

历史：

• 克劳休斯 1865年定义熵。
• 玻尔兹曼 开创 统计力学，搭建了分子（微观对象，牛顿定律）和热力学（热，能量，熵）之间的桥梁。
• 香农 的 信息论 （1948年）定义了信息，证明了一个定理，定理给出了给定通道的最大传输率（信道容量，channel capacity）。香农对信息的定义是消息源的可预测性。

计算

希尔伯特提出的问题。

1. 数学是不是完备的。也就是说，是不是所有的数学命题都可以用一组有限的公理证明或证否。
2. 数学是不是一致的。也就是说，是不是可以证明的都是真命题。
3. 是不是所有命题都是数学可判定的。也就是说，是不是所有命题都有明确程序可以在有限时间内告诉我们命题的真假。

问题解决。

1. 哥德尔不完备定理：如果第二个问题的答案是“是”，那么第一个问题的答案是“否”。如果算术是一致的，那么算术中必然存在无法被证明的真命题。
2. 图灵停机问题。计算存在极限。第三个问题的答案是否定的。

进化

世间一切都是熵增过程，但是看起来生命正好相反。
以前人们觉得这是宗教的神迹。直到达尔文提出了进化论。

进化论的发展过程

• 布冯认为地球年龄远远大于圣经上说的6000年
• 拉马克
• 马尔萨斯人口论
• 亚当斯密《国富论》，给达尔文提供灵感
• 华莱士独立得出进化论思想。
• 孟德尔解释性状变异是如何产生的。
• 现代综合。认为进化是渐进的，变异是无偏好的。
• 古尔德和埃尔德雷奇

如何度量基因复杂性

• 基因 数量、碱基对数量。缺陷明显，人类碱基对数量与变形虫差不多。
• 香农熵
  缺点：等量、完全随机的碱基对，香农熵复杂度超过人类的碱基对。
• 算法信息量。定义为能够产生对事物完整描述的最短计算机程序的长度。
  缺点一样，对于完全随机的碱基对，复杂度反而高。
• 有效复杂性（effective complexity）。包含在描述中的信息量或规则集合的算法信息量。
  例如，随机序列的有效复杂性为0. 人们探索得到的物理规律，最简洁的信息量越高。
  缺点是太主观，相同的事物，对于每个人的复杂性不一样。
• 逻辑深度（logical depth）复杂性。高度有序的序列很容易构建，完全随机的序列也很容易构建，但是可发育成生物的序列就极难构建。定义为生成某个事物时需要处理的信息量（多个图灵机可以生成某个事物时，用最短的那个）。
  优点是有很好的逻辑特性，符合直觉。缺点是没有给出度量实际事物复杂性的方法，因为没有给出构造最短图灵机的方法。
• 热力学深度（thermodynamics depth）复杂性。思路同上，也是越难构造，信息量越大，不同的是构造不用图灵机而用热力学。首先确定“产生这个事物最科学合理的确定事件序列”，然后测量“物理构造所需热力源和信息源的总和”。
  例如，要确定人类基因组的热力学深度，需要列出从第一个生物到人类的所有演化事件，这样人类基因的热力学深度就远比变形虫高了。
  缺点同上，对于复杂的事物，基本算不出来热力学深度。
• 用计算能力度量复杂性。系统处理输入时的行为等同于多复杂的图灵机，以此定义复杂性。
• 统计复杂性（statistical complexity）。度量用来预测系统将来的统计行为所需的系统过去行为的最小信息量。这个复杂度与香农熵有关。
  在这个定义下，随机序列复杂性很低，因为其未来的统计行为就是“随机序列”。
• 分形维度（fractal dimension）复杂性
  解释一下分形维度。把一个几何结构沿着某个度量分为a份，最终得到b个一样的拷贝，那么维度就是$n=\log b /\log a$.例如一维线段，$n=\log 2 /\log 2$. 二维$n=\log 4 /\log 2$. 三维$n=\log 9 /\log 2$. 这里都把先划分两段，其实划分多段也一样。
  科勒曲线切开后，每个直线段是之前的1/3长，但得到4个拷贝。$n=\log 4 /\log 3$

遗传算法、蚁群算法、免疫优化算法

这个已经写了好几篇博客了，这里不写了。

元胞自动机

元胞自动机也是冯诺依曼发明的，称为“非冯诺依曼结构”
生命游戏。
生命游戏可以运行标准计算机的程序。

元胞自动机的最终状态有4种：

• 停在一个最终的图像上
• 在几个图像之间循环
• 产生看似随机的行为
• 局部结构简单，但这些结构会移动。实际上这是一种通用计算机。

因此

1. 思考自然界中的过程的正确方法是将它们视为计算。
2. 像规则110这样极为简单的规则（或“程序”）都能进行通用计算，这表明通用计算的能力在自然界中广泛存在。
3. 通用计算是自然界中计算的复杂性的上限。也就是说，自然系统或过程不可能产生出“不可计算”的行为。
4. 自然界中各种过程实现的计算在复杂程度上都几乎等价。

冯诺依曼的好处是编程语言和机器码可以毫无歧义的互相转化。

囚徒困境算法

最优策略不是纳什解，而是“善良、报复、宽恕、明确”

网络科学

关注的不是事物本身，而是他们之间的关系。
例如，生物的复杂性主要来自基因之间交互作用的复杂性。

网络思维还帮助厘清了一些看似无关的科学和技术之谜：为什么生物的生命期与它们的大小基本上遵循一个简单的函数？为什么谣言和笑话传播得如此之快？为什么电网和万维网这样大规模的复杂网络有时候非常稳健，有时候却又容易出现大范围崩溃？什么样的事件会让本来很稳定的生态群落崩溃？
这些问题看似毫不相干，网络科学家却认为答案反映了各种网络的共性。网络科学的目的就是提炼出这些共性，并以它们为基础，用共同的语言来刻画各种不同的网络。
网络科学家也希望能理解自然界中的网络是如何发展而来的，如何随时间变化的。
对网络的科学理解不仅会改变我们对各种自然和社会系统的理解，同时也会帮助我们更好地规划和更有效地利用复杂网络，包括更好的网络搜索和万维网路由算法，控制疾病传播和有组织犯罪，以及保护生态环境。

一个网络如果只有少量的长程连接，相对于节点数量来说平均路径却很短，则为 小世界网络。
小世界网络经常表现出高度的集群性。

PageRank

PageRank 数学方面的详解在另一篇博客里写过，这里不重复。

in-degree 为 k 的网页的数量正比于$k^{-2}$，其特点是

• 无尺度。例如，你绘制K=5到K=10000的图像，发现与原图像相似（自相似）
• 不是一个正态分布，这让 PageRank 效果良好
• 小世界。也就是说，相对于节点也边的数量来说，平均路径很短。
• 节点被删除时候具有稳健性（稳健性是指，仍然保持度分布多样性、平均路径很短、集群性很高）。
  这是因为随机删除节点，大概率删除的是不太重要的节点。
  如果被删除的是中心节点，性质可能变化很大。

真实的网络

• 大脑。具有小世界特征，因为既要有复杂性，又不能让大脑太大。
• 基因调控网络。
• 代谢网络。同样保证了鲁棒性。
• 流行病。例如，为了解决艾滋病传染网络，移除中心节点。不过中心节点不太容易直接找到，设计一个小算法：抽样后，让样本人群报告自己的性伴侣，重合率高的就是中心节点。
• 生态和食物网。
• 科学知识
• 技术

无尺度是如何产生的？
preferential attachment 获得新链接时，连接度高的节点比连接度低的节点更有可能得到新链接。

这里，我根据上面这句话的描述，写了个程序模拟一下看看

生成节点

n_points = 1000 # 网络中的节点个数
n_out_degrees = 20 # 每个节点的 out_degree

net = {i: np.random.randint(0, n_points, size=n_out_degrees) for i in range(n_points)}


def cal_in_degree(net):
    '''
    计算网络中每个节点的in-degree
    '''
    in_degree_list = [0] * n_points
    for i in net:
        for j in net[i]:
            in_degree_list[j] += 1
    return in_degree_list

plt.hist(cal_in_degree(net))

初始的 in-degree 显然是一个正态分布

下面迭代整个网络，迭代的原则是：in-degree 更高的节点，更有可能被指向

# 随机选取n_select个节点，然后找到他们的一度连接。放一起作为集合来抽样，获取下次迭代的 out-points
n_select = 5

net_tmp = copy.deepcopy(net)
for iter_num in range(10):
    for i in net_tmp:
        points_selected0 = np.random.randint(0, n_points, size=n_out_degrees)
        points_set1 = [points1 for points0 in points_selected0 for points1 in net[points0]] + list(points_selected0)
        points_selected1 = np.random.choice(points_set1, size=n_out_degrees)
        net_tmp[i] = points_selected1
    net = net_tmp

plt.hist(cal_in_degree(net))

对网络科学的一些审慎态度

• 无尺度分布被滥用。有些研究中用到无尺度分布假设，后来被发现其实不是。
• 导致无尺度的原因很多，未必是 preferential attachment
• 模型过度简化。所有节点都当做一样的，所有的边类型和强度也当做一样的。

连锁失效。我们已经知道，网络有鲁棒性，某个节点失效后，其工作量会转移到其它节点上。这有可能让其它节点负荷过重而失效，进而又把工作量转移到其它节点上。最终导致整个网络崩溃。
（一个小节点失效，可能导致整个网络崩溃）

比例之谜

我们研究一下生物的大小与代谢率的关系。

• 直观感觉，代谢率与体重成正比，但这显然是错的。因为照此看来，河马表皮面积是老师的2500倍，但代谢是老鼠的125000倍，恐怕河马要烧起来
• 那么，代谢率是否与表面积成正比呢？也就是说，代谢率与体重的2/3次幂成正比。（surface hypothesis）
• 实际数据表名，这个代谢率与体重的3/4成正比。（Kleiber’s law）
• 进一步的，生命与体重的关系，是一个指数1/4的幂函数
• 平均心率与体重，是一个-1/4的幂函数

代谢比例理论（Metabolic scaling theory） 上述比例来自分形结构，某种量（如代谢率）遵循幂律分布。
这个理论某种程度上具有普适性。

有一些批评：

• 四分幂定律并没有那么普适。大狗和小狗寿命差不多。有人认为2/3才是正确的回归结果。
• 比例是对的。但理论错了。

进化中的复杂性

• 前面说过，基因的表达过程是一个复杂网络。
• 基因旁边有开关蛋白质。
• 这导致生物剧烈变化是可能的
• 以前人们认为是趋同进化的现象，其实是开关造成的。
• 复杂网络的状态可能是不动点、循环、混沌。考夫曼认为，基因要同时保持活性和稳定性（不能完全是不动点、循环、混沌），所以应当在混沌的边缘

《信号与噪声》

预测

印刷机的发明，信息极大丰富，人反而未必更接近真理

• 2005年《为什么大多数发表的研究成果都是骗人的》
• 1970《未来的冲击》：尽管世界本身正在走向分化，变得更加复杂，但是人类扔会以坚持自身看法的方式使这个世界变得简单，这便是我们的防御机制。 所以“信息越多，越靠近真相”这一信条被颠覆了
• 《银河系漫游指南》：可能会出错的事情和完全不可能出错的事情，区别在于后者一旦出错，往往无法挽回

刺猬型专家和狐狸型专家

狐狸型专家的原则

• 原则1：用概率方法思考问题
• 原则2：今天的预测是你以后人生的第一个预测。
  • 一个误解是：成功的预测不会改变。当然，如果你的预测结果每天都有巨大的波动，可能是一个不好的预示：要么模型不好，要么预测对象不具有预测性
• 原则3：寻找共识。集体决策通常好于狐狸型专家培养出了一种仿效集体决策的能力：不停向自己发问。这就意味着要把很多不同类型的信息整合起来。

棒球比赛预测

一个好的棒球预测系统必须可以完成3项任务：

• 考虑影响球员表现的外在因素
• 区别对待技术和运气因素
• 了解球员的表现如何随着年龄增长而发生变化的

球探的优点是能够获得更多的信息，缺点是容易被这些信息中的噪声干扰，掺杂个人偏见
数据怪才的缺点是：数据怪才也有偏见，一个致命的偏见是：如果某项因素很难量化，那么就视为无关紧要

大多数情况下，分类的方法非常奏效。可是，一旦遇到不易分类的信息，我们通常会无视它，或者对它错误的分类

天气预测

问题1：量子层面上的不确定性

测不准原理。
天气预测中，不用考虑这个因素。因为天气预测是分子层面的。

问题2：计算复杂度

在4维空间中，有限元的分辨率加倍，计算量增加到原来的16倍

问题3：混沌理论

1. 系统是动态的。也就是说，一个时间点的动作会影响未来
2. 非线性。

地震预测

主要内容是说，地震预测中，x难以获取，所以基本用y做时间序列。
肯定很难

经济预测

预测的难处之一在于，相关的两个经济变量之间未必互为因果
经济预测者面临三大基本挑战。

1. 单纯依靠经济统计数据，很难判断起因和结果
2. 经济始终在变化。单一经济周期的经济运行状况无法被用来解释未来经济的发展
3. 经济学家以往的预测如此糟糕，所以他们预测所用的数据质量太差。

失业率是企业的信心的滞后指标，却是消费的领先指标
大数据时代，更容易把相关性当成因果律。然而，技术的进步无法掩盖人们对理论知识的缺乏。

传染病预测

预言的自我实现 报纸上“儿童孤独症”出现的概率，与发病率有极好的统计学相关性

一种agent建模方法：似乎是蒙特卡洛？模拟每个人的行为，包括文化、宗教信仰、习惯等等。

贝叶斯定理

国际象棋大赛

棋类比赛中，人与计算机都不可能计算到完全信息，所以所做的事情仍然是预测
因此，人机对战就是寻找彼此的盲点

扑克牌

财富是信号与噪音的结果
随着整体水平提高，菜鸟出局。高手也会变成被收割的菜鸟

股市

首先写了有效市场理论
然后提出了一个有亮点案例。
一个投资经理面对的决策：

1. 买入股票，并且股市上升。会成为明星投资人，享受豪车游艇。
2. 卖出股票，股灾来临。会成为天才，然而股灾中对天才的需求也是有限的。所以天才转战媒体、写书等。
3. 买入股票，股灾来临。很幸运，你的同事也犯了同样的错误，华尔街的雇佣率减到80%。意味着你有80%可能保住工作。
4. 卖出股票，股市上升。不但丢掉工作，再次被雇佣的概率微乎其微。

如果我是这位投资经理，即使股票50%概率崩盘，我也不会卖出股票。所有投资经理都是这么想的。所以大多证券公司避免“鹤立鸡群”

恐怖主义

书中介绍了一种对恐怖主义的预测模型。
这种模型参考了地震预测模型
横坐标是事件死亡人数（地震震级），纵坐标是发生频率
破窗理论实际上也是地震预测模型的推论。如果集中处理小的犯罪，那么大的犯罪也会减少。