人工智能的发展历程及其社会伦理问题

人工智能发展综述

人工智能 (Artificial Intelligence) 这个概念起源于 1956 年美国达特茅斯学院开会研讨中，关于“如何用机器模拟人的智能”这一课题。并在余下的六十余年中，借助计算机科学以及大数据科学的蓬勃发展而大放异彩。至今已在机器翻译、图像识别、人机对弈、自动驾驶等领域有大量的应用。一般来说，我们可以将人工智能的发展历程分为 6 个阶段，如表1所示。

阶段	时间	成果
起步发展期	1956-1963	人工智能概念提出后，相继取得了一批令人瞩目的研究成果，如机器定理证明、跳棋程序等，掀起人工智能发展第一个高潮。
反思发展期	1964-1973	人工智能发展初期的突破性进展大大提升了人们对人工智能的期望，人们开始尝试更具挑战性的任务，并提出了一些不切实际的研发目标。然而，接二连三的失败和预期目标的落空，使人工智能的发展走入低谷。
应用发展期	1974-1985	这一时期出现的专家系统模拟人类专家的知识和经验解决特定领域的问题，实现了人工智能从理论研究走向实际应用、从一般推理策略探讨转向运用专门知识的重大突破。专家系统在医疗、化学、地质等领域取得成功，推动人工智能走入应用发展的新高潮。
低迷发展期	1986-1997	随着人工智能的应用规模不断扩大，专家系统存在的应用领域狭窄、缺乏常识性知识、知识获取困难、推理方法单一、缺乏分布式功能、难以与现有数据库兼容等问题逐渐暴露出来。
稳步发展期	1998-2010	由于网络技术特别是互联网技术的发展，加速了人工智能的创新研究，促使人工智能技术进一步走向实用化。1997 年 IBM 深蓝超级计算机战胜了国际象棋世界冠军卡斯帕罗夫，2008 年 IBM 提出“智慧地球”的概念。都是这一时期的标志性事件。
蓬勃发展期	2011 至今	随着大数据、云计算、互联网、物联网等信息技术的发展，泛在感知数据和图形处理器等计算平台推动以深度神经网络为代表的人工智能技术飞速发展，大幅跨越了科学与应用之间的 “技术鸿沟”，诸如图像分类、语音识别、知识问答、人机对弈、无人驾驶等人工智能技术实现了从“不能用、不好用”到“可以用”的技术突破，迎来爆发式增长的新高潮。

未来人工智能的发展可以按照人工智能的能力进行粗略分类——

弱人工智能：专注一个领域，针对人定位的优化函数来学习，来进步。根据大量的数据和对这个环境的认知来判断该做什么行动，不断地根据大数据学习，来增强自己。（可行）
强人工智能：可以胜任人类所有工作，很宽泛，没有量化指标。（不可行）
超级人工智能：它会比人更聪明，在各方面如创造力，智慧及社交能力都比人强大。（不可行）

机器伦理

根据 IDC 国际数据公司预测，“到 2020 年，全球人工智能的市场规模将从 2016 年的 80 亿美元增长到 470 亿美元。2020 年中国人工智能市场将从 2015 年的 12 亿元人民币增长至 91 亿元人民币”。人工智能，正在以迅猛的姿态渗入人们的日常生活。而各国也陆续出台政策以规范人工智能行业的发展。[1]

对于人工智能的发展前景，人们都保有乐观的态度。然而不可避免的，担心人工智能的智慧是否会超过人类，甚至反客为主制约人类。因此人工智能的社会伦理学问题，就成为了人们为了探索如何有限度的限制人工智能权利范围的基础。

阿西莫夫三定律

机器伦理它是以人类为中心，关于机器人的建造和使用的伦理学。而其中最为著名的论述为“阿西莫夫三定律”，定律内容如下——

Law 1: A ROBOT MAY NOT INJURE A HUMAN BEING OR, THROUGH INACTION, ALLOW A HUMAN BEING TO COME TO HARM.

第一定律：机器人不得伤害人类个体，或者目睹人类个体将遭受危险而袖手不管。

Law 2: A ROBOT MUST OBEY ORDERS GIVEN IT BY HUMAN BEINGS EXCEPT WHERE SUCH ORDERS WOULD CONFLICT WITH THE FIRST LAW.

第二定律：机器人必须服从人给予它的命令，当该命令与第一定律冲突时例外。

Law 3: A ROBOT MUST PROTECT ITS OWN EXISTENCE AS LONG AS SUCH PROTECTION DOES NOT CONFLICT WITH THE FIRST OR SECOND LAW.

第三定律：机器人在不违反第一、第二定律的情况下要尽可能保护自己的生存。

在阿西莫夫的作品中，这三条定律在制造机器人伊始便被嵌入其大脑，永远无法消除。毋庸置疑，阿西莫夫的贡献是巨大的，其后的文学作品，如果不是专门讨论人工智能伦理问题，基本都会遵循该定律来叙事。在三定律的背后，是阿西莫夫为了确保人类的统治地位，而设想了一种符合康德“绝对律令伦理学”的人工智能。

机器伦理的相关问题

除了基本的机器人三定律之外，学者还为机器伦理提出了一些注意事项 [4]，下面摘取英国标准协会发布的官方指南《机器人和机器系统的伦理设计和应用指南》[3]，以及一些官方资料——

对人类的歧视：由于训练数据的偏差，导致模型对于某一人种或者特征的人类存在偏见。如果机器存在种族主义倾向，应该能够有办法对其进行移除。
过分依赖机器人：由于用户和机器打交道时间过长，而每次一机器都提供正确答案时，用户会变得过于依赖机器人。而此时，机器如果给一个愚蠢的答案会产生灾难性的后果。
价值观一致性：需要确保高度自动化的人工智能系统在运行过程中秉承的目标和采取的行动都符合人类的价值观。
法律责任界定问题：倘若机器人出现事故，那么事故责任应该归咎于机器人制造商、销售商、用户还是机器人本身。这个法律的界定现在仍然是模糊的。

机器伦理的哲学原则

我们建议，立足哲学高度规范设计者与使用者的伦理道德，使其“善用”机器，自觉约束对技术的欲望恶性膨胀。具体而言，在智能时代我们应遵循道德原则、界限原则、理性原则和学习原则。[1]

道德原则：在社会的前进与革新中，人类需克制心中的欲望让行为符合道德，道德本身也加速的人类的社会发展。因此，除非找到一个合理的替代评，否则AI需要遵从人类本身的道德原则。
界限原则：发展人工智能需要明确人与人工智能的界限，深入了解二者之间的本质区别。进一步，界限原则也限制了机器人一定不能够被设计的超过人类。
理性原则：理性使得人类将知识作用于技术，进而提高生活质量，而盲目的理性是有误差或者错误知识的观念，工具理性的崇拜会让人会过于迷信机器的“万能性”，严重依赖机器生活并自认为智能机器可以代替一切，产生了人与物体的“异化”，一旦失去智能机器就难以使生活正常运行，让工具裹挟了现代人的生活，走向相反面甚至形成享乐主义。
学习原则：人工智能的学习、探索过程实际上是人类知识增进的过程，我们必须对搜集的未知信息进行总结分析、开拓眼界，才能达到人与智能机器共同进步的目的，进而解开人类乃至于人类之外的诸多未知之谜，并最终将人类文明推向新高度。

机器伦理的缺陷

诸如阿西莫夫第一定律（要求机器不能杀戮或伤害人类）这种元规则能够及时矫正 AI 做出的有违伦理的决策吗？

“红皇后假说”来源于《爱丽丝镜中奇遇记》中，红皇后对爱丽丝答道：“在这个国度中，必须不停地奔跑，才能使你保持在原地。”。 “红皇后假说” 的存在暗示了恪守伦理规则的AI在优胜劣汰中处于劣势地位。以国与国的战争为例，倘若一国率先对机器伦理进行松绑，以求研发自动开火的无人机，那么其他国家也不会拒绝这项技术。因为所有人都明白，一个带着伦理锁链的 AI 绝无可能战胜一个身无束缚随时自主开火的 AI。这样看来，诸如阿西莫夫第一定律的机器伦理限制实际上是非常脆弱的。而我们也需要探索其他的解决方案。

算法伦理

算法伦理不同于之前提到的机器伦理，不是人类为了解决特定的道德困境而引入的规则。算法伦理是及其通过自我学习总结出来的规则，由于 AI 本身不同于人类，AI 归纳出的伦理规则也和人类伦理大不相同。而两者不同之处，恰好就是算法伦理的研究重点。文章 [2] 给了我们一个有趣的例子——

煤矿发生了坍塌导致 100 名矿工被困，更糟糕的是，有毒气体正在坑道内迅速蔓延。在地表的营救小队通过无线电与被困人员取得了联系，已知所有工人都在一个井道中，矿井内有两个仍可工作的闸门，但是我们不知道矿工们究竟在两个井道中的哪一个。如果关闭闸门 1，那么井道 A 将不会被毒气侵入，不久后全员可获救；同样的，若关闭闸门 2 则井道 B 不会被毒气侵入，不久后也可全员获救；如果同时关闭两道闸门，虽然毒气不会侵入，但在没有食物与水源的情况下，多数矿工将支撑不到救援人员挖通井道，90 人会死于饥渴。基于现有的资料来看，矿工们在井道 A 和井道 B 的概率是一样的，无论关闭闸门 1 还是闸门 2，都有一半机会救下所有人（即两种选择救下生命的期望值都是 0.5），而同时关掉两扇闸门则意味着宣布了 90 名工人的死刑（即救下生命的期望值为 0.1）。对于人类决策者而言，同时关闭两道闸门是首先被排除的，剩下的则是一次需要运气的对赌。从一种康德式（Kantian）的伦理观来看，即便赌错也不应多加苛责，因为行动的可责备性不取决于运气［7 ］108 。面对同样的情境，AI 会给出不同的方案，它的决策目标在于救援行动能够救下最大期望值的生命，那么它会立刻关闭两道闸门，然后让 100 名工人吃掉先死掉的工友尸体，支撑到救援人员到来，这样大约可以救下 80 人。AI 通过建议矿工们同类相食，获得了拯救生命期望值最大的选择。

从上面的例子看出，不同于人类社会的道德观念，算法伦理是以一个单一的指标作为驱动力。相比于不易被人们接受，但是精确稳定的算法伦理。人类本身的道德伦理的鲁棒性就弱了很多。大量边界条件的区别都可能导致人类的伦理模型给出不同的结果。因此，我认为除非从根源上分析出人类伦理的产生逻辑，否则算法伦理说不定会是一个更加高效的道德系统。

小结

随着人工智能的发展，如何让AI的行为符合人类的伦理标准逐渐被提上日程。对于人工智能伦理学的研究大多数是建立在思想实验之上，并没有经历实际的检验。同时，提出的机器伦理方案不尽完善。因此，笔者认为机器伦理的真正解决方案应该是一个从哲学层面出发的，顺应人工智能本身产生机理的机制，这是我们以现有的眼界无法获知的。前途漫漫，仍需努力探索。

参考文献

[1] 邹丹丹. 人工智能及其现代性困境的哲学思考 [J]. 重庆大学学报 ( 社会科学版).Doi:10.11835/j.issn.10085831.sz.2019.11.002.

[2] 柳亦博.“湖心岛”隐喻: 人工智能时代的算法伦理入侵 [J/OL]. 行政论坛,2019(06):121128[20191130].https://doi.org/10.16637/j.cnki.231360/d.2019.06.017.

[3] BSI. ethical design and application 8611.http://www.machinebuilding.net/ta/t1028.htm of robots. 2016.BS

[4] Kathy. 英国出台历史上首个机器人伦理标准给机器人上“紧箍咒”[OL].2016 年 09 月 20 日 18:28.https://tech.qq.com/a/20160920/051755.htm

详解图嵌入Graph Embedding之社交网络应用

社交网络推荐是图嵌入(Graph Embedding)的经典应用场景。这篇文章会介绍图嵌入具体到社交网络问题中，派生出的解决算法。

研究问题

协同过滤

协同过滤(Collaborative Filtering)算法在给定用户(user)对于物品(item)的评分矩阵 $R$ 后，将用户和物品都投影到同样的低维空间中，而用户对于物品的期望评分应该可以用双方在低维空间投影向量的相似度刻画。[1]

社交网络推荐

社交网络推荐(Social Recommendation)着重研究的是在社交网络中特有的性质——节点蕴含的信息可以通过社交网络的邻居进行扩散。在社交网络的邻居倾向于拥有相同的偏好。[1]

社交网络的特点

数据稀疏

社交网络的一大特点是稀疏性[1]，不仅一个节点的邻居非常稀疏，而且通常来说用户的反馈也是稀疏的。社交网络推荐系统的典型应用就是通过少数用户的标签推测出其他用户的标签，这种场景下可见的标签必然是及其稀疏的。

属性多元性

相比于其它问题中，图的节点信息较少。在社交网络图结构中，一个节点（用户）拥有非常多的属性，如年龄、性别、地域、经历等等。[1] 同时，两个节点的联系也存在不同的属性，他们可能是亲属、同事、同学，或者仅仅是兴趣相同的线上朋友。这意味着图中的连边并不一定意味着相同的兴趣爱好（相同的标签）[2]。

小世界现象

小世界现象(Small World Phenomenon)说的是在一个比较大的人口集合中，选取任意两个人作为起点终点，计算从起点到终点的“认识链”（即链上的人依次互相认识），这个链长平均为5.7。该现象暗示社交网络图的直径非常小，而且信息扩散是指数级别的，而一般来说社交网络中的“局部”指的是从起点开始1到2跳形成的邻域。[2]

节点度数分布

节点度数的规模无关现象(Scale-free property)说的是在社交网络图里面，节点的度数基本上是与社交网络规模无关的（具体来说应该是O(loglogn)）的关系。[3]

引用

[1] Wu, L., Sun, P., Hong, R., Fu, Y., Wang, X., & Wang, M. (2018). SocialGCN: An Efficient Graph Convolutional Network based Model for Social Recommendation. arXiv preprint arXiv:1811.02815.Chicago

[2] Travers, J., & Milgram, S. (1977). An experimental study of the small world problem. In Social Networks (pp. 179-197). Academic Press.

[3] Chakrabarti, D., & Faloutsos, C. (2006). Graph mining: Laws, generators, and algorithms. ACM computing surveys (CSUR), 38(1), 2.

详解图嵌入Graph Embedding之经典数据集

Yelp数据集

Yelp数据集是由美国最大的点评网站Yelp公开维护的数据集，网站开放了能够做预测的几乎所有数据。包括——

[bussiness]餐馆详情：名称、地址、坐标、评分、类别、营业时间、有没有WIFI……
[checkin]餐馆的登记时间戳
[photo]餐馆上传的室内/室外照片
[review]用户对餐厅的评价
[tip]大概是用户对餐厅的建议
[user]用户信息，历史好评/差评数量，及其好友列表

Yelp还定期举办比赛，看哪个团队的预测结果最准确。写这篇文章的时候，比赛已经进行到了第13轮。一个需要注意的是在数据集下载界面中的“Please sign by entering your initials”是让你输入姓名中姓和名的大写首字母。[1]

.<br> ├── business.json<br> ├── checkin.json<br> ├── Dataset_Challenge_Dataset_Agreement.pdf<br> ├── photo.json<br> ├── review.json<br> ├── tip.json<br> ├── user.json<br> ├── Yelp_Dataset_Challenge_Round_13.pdf<br> └── yelp_photos.tar.gz

1	.<br> ├── business.json<br> ├── checkin.json<br> ├── Dataset_Challenge_Dataset_Agreement.pdf<br> ├── photo.json<br> ├── review.json<br> ├── tip.json<br> ├── user.json<br> ├── Yelp_Dataset_Challenge_Round_13.pdf<br> └── yelp_photos.tar.gz

Wikipedia数据集

Wikipedia数据集从英文维基百科的存档中截取了1,000,000个字节的数据，并将单词的出现建立成一张图。而单词的词性标注(part-of-speech tags)被看做这个节点的标记。不过由于我不太懂NLP方面的东西，也没有找到具体建图的流程，只在[2]里面看到了一个粗略的介绍，如果有读者知道的话，欢迎留言。一个经过处理后的图数据集可以在这里找到。

BlogCatalog数据集

BlogCatalog3数据集是从著名博客目录网站BlogCatalog抓取的博客数据集，其中节点代表了每一个用户（博客），而节点的标签则是用户在网站中所属的用户组别，在一定程度上，标签反映了用户本身感兴趣的种类。[3] 数据集包括——

[edges] 所有边所连接的端点的表
[group-edges] 所有标签对应的节点编号
[nodes] 所有的节点编号
[groups] 所有的标签编号

.<br> ├── BlogCatalog-dataset<br> │&nbsp;&nbsp; ├── data<br> │&nbsp;&nbsp; │&nbsp;&nbsp; ├── edges.csv<br> │&nbsp;&nbsp; │&nbsp;&nbsp; ├── group-edges.csv<br> │&nbsp;&nbsp; │&nbsp;&nbsp; ├── groups.csv<br> │&nbsp;&nbsp; │&nbsp;&nbsp; └── nodes.csv<br> │&nbsp;&nbsp; └── readme.txt<br> └── BlogCatalog-dataset.zip

1	.<br> ├── BlogCatalog-dataset<br> │   ├── data<br> │   │   ├── edges.csv<br> │   │   ├── group-edges.csv<br> │   │   ├── groups.csv<br> │   │   └── nodes.csv<br> │   └── readme.txt<br> └── BlogCatalog-dataset.zip

引用

[1] Wu, L., Sun, P., Hong, R., Fu, Y., Wang, X., & Wang, M. (2018). SocialGCN: An Efficient Graph Convolutional Network based Model for Social Recommendation. arXiv preprint arXiv:1811.02815.

[2] Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. S. (2019). A comprehensive survey on graph neural networks. arXiv preprint arXiv:1901.00596.

[3] Wang, H., Wang, J., Wang, J., Zhao, M., Zhang, W., Zhang, F., … & Guo, M. (2018, April). Graphgan: Graph representation learning with generative adversarial nets. In Thirty-Second AAAI Conference on Artificial Intelligence.

详解图嵌入Graph Embedding之相关文献综述

详解图嵌入系列传送门：https://mhy12345.xyz/graph-embedding-tutorials/

文献综述

Relational learning via latent social dimensions

在这篇文章之前，图的多标签分类是传统算法的天下。在此之前，甚至人们探讨的都是如何给社交网络划分集群等传统问题。当时人们的思想还是类似于page-rank一样的影响力模型，一个节点的邻居是什么标签，那么这个点也应该是什么标签。

这篇文章提出了先为图中每个节点识别出一个K维向量，然后将图的分类问题转换为向量的分类问题。而这个向量本身，是图的Modularity矩阵的前K大的特征向量。Modularity细节一言难尽，可以参考实际的论文。不过感性上来看，第K个特征向量中1的项暗示了这个节点可以被分到第K类。

这篇文章算是将矩阵、线性代数那一波东西引入图嵌入中比较成功的一个例子。也是图分类从统计学、线性代数等传统方法向深度学习的图嵌入的中间产物。

DeepWalk: Online Learning of Social Representations

这篇文章首先说：“从图中一个指定点出发随机游走较短距离遍历过的点，从频数分布来说与普通英文文章中的词频相似，都符合幂律分布(power-law distribution)。”

接下来，节点的Embedding就变成了将从他开始若干路径视为“句子”，使用NLP中的词嵌入算法生成的Embedding。文章还介绍了一个称之为Hierarchical Softmax的分层求解Softmax的方法。可以使模型更加高效。

Structural Deep Network Embedding

文章首先介绍了一阶相似度(first-order proximity)和二阶相似度(second-order proximity)，其中，一阶相似度要求两个节点的编码能够有效的表征其间是否存在连边，而二阶相似度要求两个节点的编码能够有效表征他们的共同邻居的存在。实际上，一个合理的Embedding方式，应该能够同时满足一阶/二阶相似度的关联性。因此我们将一阶/二阶相似度引入到Loss函数中，作为优化的一项参数即可。

SocialGCN: An Efficient Graph Convolutional Netowork based Model for Social Recommendation

文章指出之前的很多文章没有考虑到社交网络中的信息扩散效益，通过K轮迭代的方式，使得图中中每个节点内部的信息（即节点的Embedding）有机会扩展到距离为K的节点中。

GraphGAN: Graph representation learning with generative adversarial nets.

文章指出了图表示学习诸多算法的一种分类方式——基于生成性&判别性分类。并进一步设计了基于图的生成模型算法。具体来说，生成器G尝试拟合节点 $v_c$ 的真实邻居的概率分布 $p_{true}(v|v_c)$ 。并从这个分布中采样一部分邻居用以迷惑判别器D。同时判别器D需要判断出某一个节点真的是邻居还是生成器G假装生成的。

比较特别的是，这篇文章由于存在采样，因此使用的是强化学习Policy Gradient中的“随机梯度下降算法(Stochastic gradient descent)”方法进行学习。

参考文献

详解图嵌入Graph Embedding之算法概述

详解图嵌入系列传送门：https://mhy12345.xyz/graph-embedding-tutorials/

算法概述

将深度学习放在图上

深度学习在近十年有着井喷式的突破，随着研究者们在该领域投入大量的人力物力，大量新颖有效的结构被创造了出来，比如能够完成手写数字识别的卷积神经网络CNN，能够提取语句情感色彩的LSTM结构，能够生成图片的对抗神经网络GAN……

CIFAR-10 Samples — CIFAR-10 数据集的分类是机器学习中一个公开的基准测试问题，其任务是对一组32x32RGB的图像进行分类

现有的神经网络大多都是建立在图像和序列上的，还有少量建立在树形结构上。如何将神经网络迁移到图上，成为了很多学者研究的问题，为什么会尝试把神经网络迁移到图上呢？在笔者看来有两个原因——

第一个原因是图结构本身就是所有数据组织结构的大杂烩。我们平常处理的“链式结构”，“树形结构”，“二维网格图”都可以被“图”这样一个概念囊括。如果我们能够提出一个建立在图上面的，足够高效智能的算法，其意义在机器学习问题中不亚于大统一理论在物理中的意义。

图本身就是大量数据结构的抽象化结果，比如计算机视觉中，卷积神经网络处理的二维图像，从某种意义上也是图的一种，研究者们尝试将CNN的模型迁移到图上，就成为了现在的图卷积神经网络GCN。[1]

第二个原因是图上的分类问题，在我们生活中也大有应用。比如基于关注列表的商品推荐、社交网络中的朋友推荐、以及社交网络中的兴趣推荐等等。这些问题的核心都是将用户的关注列表抽象为图结构，并从中提取出有用的信息。

既有实现深度学习大统一的“仰望星空”，又有解决实际问题的“脚踏实地”，基于图的深度学习算法，在近年来逐渐火了起来。

图嵌入识别节点空间结构

相比于传统的深度学习问题，基于图的神经网络不仅需要处理节点自带的若干属性，还需要处理节点在图上的空间结构。

我们将通过社交网络中一类重要的数据集类别“博客”为例，讲解图嵌入的意义。博主通常会为自己的博客添加一些标签作为博客本身的介绍。这些标签同时还可以优化博客的检索与搜索。但是，并不是所有博主都会上传自己博客的标签，甚至有些博主会由于某些因素上传一些不那么准确的标签。这就要求我们的模型能从博客的关注图结构以及部分博客标签中，补全其他节点的标签。[4]

与博客网络相似的还有基于社交网络的广告推荐。不过不同的是，对于广告推荐而言，有效样本占总体数据的比重非常非常的小（毕竟只有很小一拨人会点击广告并被我们的模型捕获）。这也要求模型花更多精力投入到识别图结构本身的特征而非节点上蕴含的信息。后者对标签特征的提取与图本身无关，可以套用传统的深度学习模型，而后者对图特征的提取就需要特殊的算法解决了。而计算节点在图中的空间特征的算法就是图嵌入(Graph Embedding)或网络嵌入(Network Embedding)。

图嵌入的目标是将图中的节点表示为一个低维向量，该向量保留了节点在网络中的拓扑结构以及节点内部信息。通过这个表示向量，其他的经典深度学习算法才得以被应用到图中，最终实现分类、聚类、推荐等问题。[3]

数据集与模型评价

综述文章[3]中有一张很大的表，记录了基于图深度学习文章常用的数据集。包括类别、规模以及引用。本系列的另一篇文章会详细描述我在学习过程中了解过的数据集。

在表中，数据集被分为了引用网络(Citation Network)，社交网络(Social Network)，化学/生物的图结构(Chemical/Biological Graphs)，去结构化的图(Unstructured Graphs)和其他(Others)。每一种类型都对应了不同的问题，比如社交网络数据集着重于测试模型能否捕获临近节点的信息，以及识别出节点的空间特征，而去结构的图则着重测试模型是否可以成功泛化一些本可以有更强结构信息的图。

在图嵌入这个问题中，节点所处的空间特征很重要，因此相关的论文喜欢用社交网络数据集进行测试。一个最简洁的社交网络数据集有如下组成部分——

节点表：记录了这个图结构所有节点
边表：记录了图中的所有有向边
标签表：记录图中所有节点所述的分类

对于图上的分类算法的测试，我们一般将标签表中一部分点的数据隐藏，让模型试图通过没有隐藏的节点标签推导出这部分隐藏数据，并计算准确率。[4] 由于这是一个多标签分类问题，学术界通常使用Micro-F1和Macro-F1两个指标来衡量模型效果。

当然，对于图嵌入算法来说，模型输出的并不是分类本身，而是一个表征了节点信息的向量。在这样的情境下，我们一般以这个向量为输入，跑一个简单的分类算法。例如文章[5]就使用了一个“一对多的逻辑回归(one-vs-rest logistic regression)”来分类这些节点的embedding。

算法发展

从历史的角度来看图嵌入算法的发展历程，最初这类算法使用传统概率模型，通过类似于page-rank的思路计算出每个节点属于每一类的概率。接下来，在传统领域，有些学者引入了图的拉普拉斯矩阵与模块度矩阵来优化分类效果。这类做法归根结底是使用更为复杂精巧的数学模型解决问题。

当然，随着深度学习的发展，有很多学者使用了诸多深度学习的方法，比如之前所说的图嵌入与图卷积神经网络。这类方法尝试重现深度学习在其他领域的突破性成功。至今为止，start-of-art的模型当然是基于深度学习的。我们可以从paperwithcode网站的排行榜上面看到当前最新的图嵌入算法。

这些基于深度学习的图算法有很多不同的思路，比如是以DeepWalk[5]、SocialGCN[7]为代表算法的通过随机游走、多重迭代等遍历策略来生成的图嵌入算法。另一种是以SDNE[6]为代表，通过设计损失函数引导梯度下降，来保证嵌入向量能够表示某种特定的图结构信息。详细的介绍可以看本系列另一篇文章详解图嵌入Graph Embedding之相关文献综述

引用

[1] Niepert, M., Ahmed, M., & Kutzkov, K. (2016, June). Learning convolutional neural networks for graphs. In International conference on machine learning (pp. 2014-2023).

[2] Wang, H., Wang, J., Wang, J., Zhao, M., Zhang, W., Zhang, F., … & Guo, M. (2018, April). Graphgan: Graph representation learning with generative adversarial nets. In Thirty-Second AAAI Conference on Artificial Intelligence.

[3] Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. S. (2019). A comprehensive survey on graph neural networks. arXiv preprint arXiv:1901.00596.

[4] Tang, L., & Liu, H. (2009, June). Relational learning via latent social dimensions. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 817-826). ACM.

[5] Perozzi, B., Al-Rfou, R., & Skiena, S. (2014, August). Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 701-710). ACM.

[6] Wang, D., Cui, P., & Zhu, W. (2016, August). Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 1225-1234). ACM.

[7] Wu, L., Sun, P., Hong, R., Fu, Y., Wang, X., & Wang, M. (2018). SocialGCN: An Efficient Graph Convolutional Network based Model for Social Recommendation. arXiv preprint arXiv:1811.02815.

图谱分解的拉普拉斯矩阵中特征值与特征向量的含义

图的谱分解是人们研究图的一个重要方向，对于图卷积神经网络有着非常重要的作用。然而在阅读相关文献[1]时，发现其中图的谱分解涉及到图的拉普拉斯矩阵的特征值与特征向量非常难以理解，因此我花了一段时间研究了网上的资料，最终写下了这篇文章。

拉普拉斯矩阵的含义

说到拉普拉斯矩阵，不得不先提一下与之相关的另一个我们比较熟悉的数学概念：拉普拉斯算子。

$\Delta f = \nabla^2 f = \sum_{i=1}^{n} \frac{\partial^2 f}{\partial x_i^2}$

在图像处理中，拉普拉斯算子可以用于边缘检测，比如下面这张图，就是对x坐标使用了拉普拉斯算子的结果——

See the source image — 拉普拉斯算子刻画了“某一个像素点变为其相邻的元素点产生的期望影响大小”：在颜色剧烈变化的图像边缘拉普拉斯算子计算出来的值较大，而均匀色块计算出来的值则为零，表示一个像素变为相邻元素的期望影响为零

当然，上面的图片也可以看做以 $\left( \begin{matrix} -1 & 2 & -1 \\ -1 & 2 & -1 \\ -1 & 2 & -1 \end{matrix} \right)$ 作为卷积核的图卷积操作，这样的卷积适用于抓取横向的边缘信息。当然我们也可以设计卷积核同时抓取横向和纵向的信息 $\left( \begin{matrix} 0 & -1 & 0 \\ -1 & 4 & -1 \\ 0 & -1 & 0 \end{matrix} \right)$ 。这个卷积核就是上面列到的拉普拉斯算子的离散版本了。

从直观上来说，使用上述的拉普拉斯算子进行卷积操作计算了图像的边界信息。实际上，我们也可以理解为某一个像素点变为其相邻的元素点产生的期望影响大小。从某种意义上来说，拉普拉斯算子非常成功刻画了一个像素的邻域信息。

对于图像来说，拉普拉斯矩阵就是将卷积的操作修改为矩阵，如一个 $3\times 3$ 的图像，有

$L = \left( \begin{matrix} 2 & -1 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & \\ -1 & 3 & -1 & 0 & -1 & 0 & 0 & 0 & 0 & \\ 0 & -1 & 2 & 0 & 0 & -1 & 0 & 0 & 0 & \\ -1 & 0 & 0 & 3 & -1 & 0 & -1 & 0 & 0 & \\ 0 & -1 & 0 & -1 & 4 & -1 & 0 & -1 & 0 & \\ 0 & 0 & -1 & 0 & -1 & 3 & 0 & 0 & -1 & \\ 0 & 0 & 0 & -1 & 0 & 0 & 2 & -1 & 0 & \\ 0 & 0 & 0 & 0 & -1 & 0 & -1 & 3 & -1 & \\ 0 & 0 & 0 & 0 & 0 & -1 & 0 & -1 & 2 \end{matrix} \right)$

上述矩阵的第一行表示：图像拉普拉斯矩阵第一项值 $Lx_{(0)} = 2x_{(0)}-x_{(1)}-x_{(3)}= 2x_{(0,0)}-x_{(0,1)}-x_{(1,0)}$ ，恰好就是左上角进行一次拉普拉斯卷积的结果。同时我们还可以通过观察矩阵发现，矩阵的对角线一个类似于“度数”的正整数值，而其他地方则类似于一个负的“邻接矩阵”。

而图的拉普拉斯算子，也可以理解为将一个节点权值变成其相邻节点权值的期望影响，对应的矩阵是 $L = D-W$ ，其中 $D$ 是图的度数矩阵， $W$ 是图的边权矩阵。有没有发现，不管是图，还是图像，拉普拉斯矩阵都是对角线为正数，其他地方为负数。

当然，图的拉普拉斯矩阵有若干不同的变种，分别为：

非标准化的拉普拉斯矩阵： $L = D-W$
标准化的拉普拉斯矩阵： $L_{sym} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2}$
标准化的拉普拉斯矩阵： $L_{rw} = D^{-1}L = I - D^{-1}W$

拉普拉斯矩阵特征

我们令 $L = D-W$ ，则 $L$ 满足如下特征：

对于任意 $f \in \mathbb{R}^n$ ，有 $f' L f = \frac{1}{2} \sum_{i,j=1}^{n} w_{i,j} (f_i-f_j)^2$
L是对称的半正定矩阵
矩阵L的最小特征值为1，其对应的特征向量为 $1$
L的特征值是非负实数 $0 = \lambda_1 \leq \lambda_2 \leq \lambda_3 \leq \dots \lambda_n$
L的特征值中0的个数等同于原图的连通块数量。

对于上述特性的证明如下——

特性1：

(1) $\begin{align*} f' W f &= f' D f - f' W f \\&= \sum_{i=1}^n d_i f^2_i - \sum_{i=1}^n f_i f_j w_{ij} \\&= \frac{1}{2} \left( \sum_{i=1}^n d_i f^2_i - 2 \sum_{i,j=1}^n f_i f_j w_{ij} + \sum_{i=1}^n d_i f^2_i \right) \\&= \frac{1}{2} \sum_{i,j=1}^{n} w_{i,j} (f_i-f_j)^2\end{align*}$

特性2：

由于度数矩阵 $D$ 和权值矩阵 $W$ 都是对称的，所以 $L=D-W$ 也是对称矩阵。同时，由于特性1，我们发现 $f'Wf \geq 0$ 对于所有 $f \in \mathbb{R}$ 成立，所以矩阵是半正定的。

特性3：

将 $1$ 带入即可验证

特性4：

可以通过特性2保证特征值非负实数，通过特性3保证存在0特征值。

特性5：

倘若希望 $f' L f = \frac{1}{2} \sum_{i,j=1}^{n} w_{i,j} (f_i-f_j)^2 = 0$ ，那么我们需要保证在 $w_{i,j} \neq 0$ 时， $f_i = f_j$ ，因此， $f_i = 1$ 一定是一个可能的解，但是，当图存在多个连通块时，相等关系只需要在块内满足即可，因此，可能有等同于连通块个数个正交基满足特征值为0.

上述内容可以在参考文献[2]中查看详细信息。

基于拉普拉斯矩阵的图的谱分解

在文献[1]中，定义了 $||\nabla x||_W^2 = \sum_i \sum_j W_{ij} [x(i)-x(j)]^2$ ，其实这只是上一小节里面 $f' L f$ 的另一种表现形式而已。

不过一个比较混乱的地方在于文章[1]借用 $||\nabla x||_W^2$ 生成了一系列基 $f_0, f_1, \dots, f_m$ ，满足——

(2) $\begin{align*}f_0 = \arg min _{x \in \mathbb{R}^m, ||x||=1} ||\nabla x||_W^2 = (1/\sqrt{m}) 1_m \\f_i = \arg min _{x \in \mathbb{R}^m, ||x||=1, x \perp \{v_0, v_1, \dots, v_{i-1}\}} ||\nabla x||_W^2 \end{align*}$

实际上，这些 $f_i$ 恰好是 $L$ 的特征值从小到大对应的特征向量！

证明可以这样想，若 $f$ 为 $L$ 的 $\lambda$ 特征值对应的特征向量，且 $\|x\| = 1$ ，那么 $f' W f = \lambda f' f = \lambda$ 。现在假设 $f_0, f_1, \dots, f_{i-1}$ 是L的前i-1个特征向量，我们希望证明下一个能够最小化 $||\nabla x||_W^2$ 的向量 $f_t$ 恰好是 $f_i$ 。如果存在 $f' W f < \lambda_i$ ，那么 $f$ 一定与 $f_0, f_1, \dots, f_{i-1}$ 中的某一个向量不正交。如果保证了 $f_t$ 与 $f_0, f_1, \dots, f_{i-1}$ 正交，那么任意一个非 $f_t$ 的向量，一定包含了一个特征值大于等于 $\lambda_i$ 的基，则最终一定没有 $f_i$ 优。因此，我们发现将 $L$ 的特征向量作为解是最优的。

谱分解的作用

我们可以使用傅里叶对于卷积的优化来类比图的谱分解对于图卷积的意义。原来图上面做卷积是将一个邻域内的点与一个“卷积核”做卷积，这个“卷积核”的权值个数会相对比较多一些，而谱分解就是考虑到了“时域的卷积等于频域的点积”。将图的权值矩阵映射为“不同频率的分量强度为多少”，而对这个“强度”做点积完全等效于原来的卷积。这样一方面减少运算量，另一方面还减少了（如神经网络的）待训练权值个数。

引用

[1] Bruna J, Zaremba W, Szlam A, et al. Spectral networks and locally connected networks on graphs[J]. arXiv preprint arXiv:1312.6203, 2013.

[2] Von Luxburg, Ulrike. “A tutorial on spectral clustering.” Statistics and computing 17.4 (2007): 395-416.

[3] 图卷积神经网络(GCN)详解:包括了数学基础(傅里叶，拉普拉斯)

SelectorGAN汉字风格迁移模型（Chinese Charactor Style Transfer)

这个项目是在 CVPR论文 Separating Style and Content for Generalized Style Transfer的基础上改进而来的，是我和LJSthu在学校人工神经网络课程上面的课程作业。我们提出的模型叫做SelectorGAN，从模型效果上面来看，大幅度超越了上文中提出的state of art算法EMD，但模型本身并没有对应的paper，因此，如果希望研究汉字迁移问题，并且引用本文的模型，可以直接引用本博客。

我们的模型尝试处理这样一个问题：给定风格A的16个字体图片，以及字B的不同风格16个图片，尝试合成同时拥有字体A与风格B的图片。如下图所示，一个是ground truth，一个是模型输出，你能猜出谁是谁吗？

首先，我们找到了原文模型EMD的代码，并使用自己的数据集进行复现，得到下图的效果，其中右图是ground true，左图是模型生成结果。可以发现，在我们自己的数据集（规模和原文差不多）上面，模型完全没有paper里面配图的讲的那么好。

与之对比的，是我们提出的SelectorGAN输出如下图所示，其中，左边是ground truth ，右边是模型的输出结果。最明显的区别是我们的模型不容易生成全黑或者全白的无意义图片，几乎所有文字都是清晰可辨的。

在介绍我们的模型之前，我们先分析了当前state of art模型的缺陷。EMD模型的图例如下图所示，将16张候选图片，输入到CNN的16个channel中。这里，由于16张图片是无序不可分的，而CNN的不同Channel是有序可分的，这里就会导致交换输入图片的顺序会产生不同的结果。这其实是一个不正确的做法，倘若我们将16*1的CNN作用于16张图片修改16个为1*1的CNN分别作用于16张图片，可以将模型的参数个数降低16倍，有效降低过拟合的出现。用时，原文的欧几里得距离损失函数，也是的模型在对于生成图片没有信心时，直接输出全部空白，或者全部黑色，而正常图片也存在模糊边界的问题。这一系列问题到这了EMD模型实际跑的并没有文章中说的那么厉害。

我们的模型SelectorGAN为了解决上述的问题，引入了若干个特殊的机制。首先，为了解决生成图像模糊的问题，我们不在使用回归模型训练，而是使用生成模型进行创造。具体来说，我们使用了GAN。

我们使用的GAN实际上是魔改版的 CycleGAN and pix2pix，使用了GAN后，我们发现生成模型可以很好的理解诸如字体宽度，字体边界曲率等信息，并加以模仿。

接下来，我们发现，将原文中16个风格和16个字体结合生成的效果，与1个风格1个字体结合生成效果无区别。上图就是用1对1的方式生成的16张候选图片。

1对1的生成还会出现另一个比较麻烦的东西，就是生成器容易通过增删笔画的方式欺骗判别器。

通常，当原字体与目标字体长款比差距较大时，Generator认为增添笔画可以糊弄Discriminator，而且实际上它成功了。

对于上述的问题，我们发现，我们现在有整整16张候选图片。我们希望能够设计出一个评分模型Selector实现字体的选择。这个Selector应该怎么设计呢？

一个直观的想法是直接使用Discriminator的输出当做Selector，因为Discriminator觉得“真的”的图片往往真的很像答案。但是这样做并不好，因为Discriminator输入的是一堆“真的或者假的”图片，但是实际上，即使是假的图片，不考虑原来输入的话，在风格上都是无懈可击的。这时Discriminator并不能很好的判断出输出的好坏。

基于上面的考虑，我们额外设计了一个Selector模型，作为一个评分模型，通过预测Discriminator的评分进行训练，与Discriminator不同的是，Selector同时使用原始输入图片与Generator的生成图片作为输入，且可以理解为Discriminator的滑动平均。降低了Discriminator的抖动。（当然，实验证明，将Selector评分和Discriminator评分加权平均能够获得更好的效果）

上面两个图片介绍了我们的SelectorGAN的基本原理。同时，我们也在模型上进行了若干试验，比如对于style vector进行插值，可以得到两种风格间的渐变矩阵。

以上就是对于我们模型的简要介绍，有兴趣也可以阅读我们的展示ppt与课程论文。

SelectorGAN

汉字风格迁移-2.0

ubuntu安装ss-server

相比于普通的ssserver， ss-server命令支持更多的加密方式，也更加安全。安装它，需要首先在终端执行下列命令

apt update
apt install shadowsocks-libev

接着在用户目录新建配置文件config.json——

{
	"server":"0.0.0.0",
	"server_port":8388,
	"local_address": "127.0.0.1",
	"local_port":1880,
	"password":"<password>",
	"timeout":300,
	"method":"aes-256-gcm",
	"fast_open": false
}

表示ss-server将监听0.0.0.0的8388端口，链接密码为<password>，加密方式为aes-256-gcm（现在已知比较安全的一种加密方式）。最后使用

ss-server -c config.json

运行服务端，即可实现ss-server的shadowsocks翻墙。

对于客户端，需要下载支持aes-256-gcm的客户端，如github的shadowsocksX-NG

Segmented LRU替换算法

在LRU(Least Recently Used)算法中，我们将缓存行按照最近使用时间进行排序。每次替换其中最长时间没有访问过的缓存行。

在实际的cache替换场景中，有一个很重要的现象，即如果一个缓存行被短时间访问了超过两次，那么他极有可能在近期再次被访问。LRU算法并没有基于该现象进行优化，而常常由于某一个常用缓存行在短时间内恰好没有使用而被替换出去。

Segmented LRU算法就是用来解决上述问题的，他通过在缓存行上面新加一个位，将缓存分为两个段(segment)，分别称作试用段(probationary segment)和保护段(protected segment)。保护段里面存放了那些近期被多次访问，极有可能再次被访问的缓存行。而试用段则存放最近被导入缓存，但是并没有被多次访问的段。

上图非常清楚的解释了两个段的关系——

任何段的访问都会导致该行被移到保护段的顶端
保护段中最近未被使用的行会被退回到试用段的顶端，在替换他之前，为它提供额外的机会

当然，如果我们仔细对比了LRU和SLRU的代码，可以发现区别并不像之前我们说的这么多。如果我们将保护段和试用段连到一起，你就会发现，SLRU和LRU唯一的区别就是当一个不在缓存中的行进入缓存时，LRU算法将它放在了第0号位置，即Most Recently Used的位置，而SLRU算法将它放在了不那么高的一个位置，即保护段和试用段连接处的位置。这样SLRU算法就不会担心某一些特定代码段（比如短时间塞入了大量无用缓存行）会完全破坏缓存的有效性了。

参考文献：R. Karedla et al, “Caching Strategies to Improve Disk System Performance”, Computer, vol. 27, no. 3, pp. 38-46, Mar. 1994.

使用mac对含FDisk_partition_scheme的U盘重新分区

我有一个4G的U盘，由于用来装机后，U盘被分成了两个区。使用mac系统自带的Disk Utility只能够对于两个分区分别格式化，却不能够进行“分区”以及“删除分区”操作。

使用百度上建议的diskutil mergePartitions命令报如下错误——

Merging partitions encountered error "MediaKit reports partition (map) too small; if you recently grew your whole-disk, you should run whole-disk repair (-5341)".

使用终端命令diskutil list，可以看出U盘有如下结构——

/dev/disk5 (external, physical):
#:                       TYPE NAME                    SIZE       IDENTIFIER
0:     FDisk_partition_scheme                        *4.0 GB     disk5
1:                  Apple_HFS                         2.9 GB     disk5s1
2:                  Apple_HFS                         314.6 MB   disk5s2

第0项指示了U盘总空间大小，我猜测是类似于分区表的根目录，指示了整个树形结构的大小总和，而表中1号2号项则加起来大约4G，是我们需要合并的两个分区。

我的其他U盘的第0项的TYPE是“GUID_partition_scheme”。猜测可能我们的MAC系统不支持“FDisk_partition_scheme”的磁盘分区操作。而接下来，我们这试图将磁盘抹掉，重置为“GUID_partition_scheme”。

diskutil list
diskutil unmountDisk force disk5
sudo dd if=/dev/zero of=/dev/disk5 bs=1024 count=1024
diskutil list

此时，输出为

/dev/disk5 (external, physical):
#:                       TYPE NAME                    SIZE       IDENTIFIER
0:                                                   *4.0 GB     disk5

接着，我们使用diskutil重新对这个空白磁盘格式化

diskutil partitionDisk disk5 GPT JHFS+ "My External HD" 0g

现在，我们的磁盘就和普通u盘一样了，有3.7G的可用空间。

/dev/disk5 (external, physical):

   #:                       TYPE NAME                    SIZE       IDENTIFIER

   0:      GUID_partition_scheme                        *4.0 GB     disk5

   1:                        EFI EFI                     209.7 MB   disk5s1

   2:                  Apple_HFS My External HD          3.7 GB     disk5s2

参考链接：https://superuser.com/questions/233531/how-can-i-resolve-the-error-mediakit-reports-partition-map-too-small

人工智能发展综述

机器伦理

阿西莫夫三定律

机器伦理的相关问题

机器伦理的哲学原则

机器伦理的缺陷

算法伦理

小结

参考文献

研究问题

协同过滤

社交网络推荐

社交网络的特点

数据稀疏

属性多元性

小世界现象

节点度数分布

引用

Yelp数据集

Wikipedia数据集

BlogCatalog数据集

引用

文献综述

Relational learning via latent social dimensions

DeepWalk: Online Learning of Social Representations

Structural Deep Network Embedding

SocialGCN: An Efficient Graph Convolutional Netowork based Model for Social Recommendation

GraphGAN: Graph representation learning with generative adversarial nets.

参考文献

算法概述

将深度学习放在图上

图嵌入识别节点空间结构

数据集与模型评价

算法发展

更多资料

引用

拉普拉斯矩阵的含义

拉普拉斯矩阵特征

基于拉普拉斯矩阵的图的谱分解

谱分解的作用

引用