7 Papers & Radios | 南大提出全新演化算法EAMC；中科院等首用图卷积解决语义分割

机器之心&ArXiv Weekly Radiostation

参与：杜伟，楚航，罗若天

本周的重要论文有两篇，其一是南京大学人工智能学院研究助理卞超在本公众号进行线上分享的 AAAI 2020 研究论文，其二是中科院自动化所联合北京中医药大学另辟蹊径，以图卷积网络解决语义分割问题。

目录：

1. An Efficient Evolutionary Algorithm for Subset Selection with General Cost Constraints
2. SciPy 1.0: fundamental algorithms for scientific computing in Python
3. RNA Secondary Structure Prediction By Learning Unrolled Algorithms
4. Proving the Lottery Ticket Hypothesis: Pruning is All You Need
5. Joint Commonsense and Relation Reasoning for Image and Video Captioning
6. PIQA: Reasoning about Physical Commonsense in Natural Language
7. Graph-FCN for image semantic segmentation
8. ArXiv Weekly Radiostation：NLP、CV、ML更多精选论文（附音频）。

论文 1：An Efficient Evolutionary Algorithm for Subset Selection with General Cost Constraints

• 作者：Chao Bian、Chao Feng、Chao Qian、Yang Yu
• 论文链接：http://www.lamda.nju.edu.cn/qianc/aaai20-eamc-final.pdf

摘要：这周五，机器之心邀请了南京大学人工智能学院研究助理卞超通过线上分享的方式介绍他们入选 AAAI 2020 的研究论文《An Efficient Evolutionary Algorithm for Subset Selection with General Cost Constraints》。本文将对这项研究成果进行介绍。

子集选择问题是一个 NP-hard 问题，并且具有很多应用场景，比如最大覆盖率、影响力最大化和传感器放置。该问题的目标是从 n 个元素中，选择满足约束 c 的一个子集（且该子集的大小不超过 B），使得目标函数 f 的值最大。针对这类问题，现有的代表性算法有广义贪心算法和 POMC。广义贪心算法耗时较短，但是受限于它的贪心行为，其找到的解质量往往一般；POMC 作为随机优化算法，可以使用更多的时间来找到质量更好的解，但是其缺乏多项式的运行时间保证。

为此，这篇 AAAI 2020 论文提出了一个高效的演化算法 EAMC。通过优化一个整合了 f 和 c 的代理函数，它可以在多项式时间内找到目前已知最好的近似解。研究者还在最大覆盖率、影响力最大化和传感器等任务上进行了实验，结果表明该算法的表现优于广义贪心算法。

算法 3 描述了 EAMC 的执行过程。从空集 0^n 开始（行 1），不断尝试改善每个 bin 中的解的 g 值（行 2-21）。

推荐：这篇论文提出了一种新的演化算法 EAMC，能更高效地解决一般约束下的子集选择问题。

论文 2：SciPy 1.0: fundamental algorithms for scientific computing in Python

• 作者：Pauli Virtanen 、Ralf Gommers 等
• 论文链接：https://www.nature.com/articles/s41592-019-0686-2

摘要：作为科学计算中的中流砥柱，SciPy 从 2001 年到现在已经走过了十九个年头，它为最优化、积分、微分方程等各种数值计算提供了完整的流程，也为科研分析人员提供了最好用与高效的开源库。SciPy 是一个面向 Python 的开源科学计算库。自 2001 年首次发布以来，SciPy 已经成为 Python 语言中科学算法的行业标准。该项目拥有超过 800 个独特的代码贡献者，数以千计的相关开发包，和超过 150,000 个依赖存储库以及每年数以百万计的下载量。在下述简介中，会概述 SciPy 1.0 的功能和开发实践，并着重阐述一些最新的技术发展与更新。

2 月 3 日，SciPy 的维护者在 Nature Methods 上发表了一篇论文，其回顾了 SciPy 发展的里程碑与关键技术。并借助 SciPy 1.0 这个成熟的象征，展现了当前科学计算以及未来发展方向都是什么样的。

Nature Methods 回顾了 SciPy 发展的里程碑和关键技术。

自 2001 年发布 0.1 版本到 2017 年推出 1.0 版本，SciPy 发展过程中的一些里程碑式事件。

推荐：走过 19 年，每年千万下载量，这篇文章带读者走进科学计算开源库 SciPy 的前世今生。

论文 3：RNA Secondary Structure Prediction By Learning Unrolled Algorithms

• 作者：Xinshi Chen、Yu Li、Ramzan Umarov、Xin Gao、Le Song
• 论文链接：https://openreview.net/pdf?id=S1eALyrYDH

摘要：这篇论文提出的端到端深度学习模型 E2Efold 可用于预测 RNA 二级结构，该模型能有效地考虑这个问题中的固有约束条件。E2Efold 的核心思想是直接预测 RNA 碱基配对矩阵，并能使用一个展开式算法进行约束编程以作为深度架构强制执行约束的模板。研究者在基准数据集进行了大量实验，E2Efold 取得了优越的表现：相比于之前的最佳算法，它能预测得到显著更优的结构（尤其是对于假结结构）；同时在推理时间方面，E2Efold 能与之前最快的算法相媲美。

实验中使用的两个基准数据集：ArchiveII 和 RNAStralign。

基于 ArchiveII 的无再训练的实验结果。

基于 RNAStralign 的实验结果。

推荐：本文要介绍的这篇 ICLR 2020 论文提出了一种用于预测 RNA 二级结构的端到端深度学习模型 E2Efold。

论文 4：Proving the Lottery Ticket Hypothesis: Pruning is All You Need

• 作者：Eran Malach、Gilad Yehudai、Shai Shalev-Shwartz、and Ohad Shamir
• 论文链接：https://arxiv.org/pdf/2002.00585.pdf

摘要：Frankle 和 Carbin 在 2018 年提出的彩票假说表明，一个随机初始化的网络包含一个小的子网络，这个子网络在进行单独地训练时，其性能能够与原始网络匹敌。在本文中，研究者证明了一个更有力的假说（正如 Ramanujan 等人在 2019 年所猜想的那样），即对于每个有界分布和每个带有有界权重的目标网络来说，一个具有随机权重的充分过参数化神经网络包含一个具有与目标网络几乎相同准确率的子网络，并且无需任何进一步的训练。

这条定理看上去就比较复杂，论文中的证明概览及附录中的完整过程都非常硬核。

定理 3.2 表示，对于任意数据分布，如果随机特征模型能实现非常小的损失值，那么它就能找到一个剪枝神经元的子网络（neuron-subnetwork），并实现相同的损失。这表明剪枝神经元能和随机特征模型相媲美。

推荐：研究者表明：「从根本上来说，剪枝随机初始化的神经网络与优化权重值一样重要。」

论文 5：Joint Commonsense and Relation Reasoning for Image and Video Captioning

• 作者：Jingyi Hou、Xinxiao Wu、Xiaoxun Zhang 等
• 论文链接：https://wuxinxiao.github.io/assets/papers/2020/C-R_reasoning.pdf

摘要：这篇论文是北京理工大学和阿里合作的一篇关于利用对象之间的关系进行图像和视频描述 (image caption/video caption) 的论文。大多数现有方法严重依赖于预训练的对象及其关系的检测器，因此在面临诸如遮挡，微小物体和长尾类别等检测挑战时可能效果不佳。

在本文中，研究者提出了一种联合常识和关系推理的方法 (C-R Reasoning)，该方法利用先验知识进行图像和视频描述，而无需依赖任何目标检测器。先验知识提供对象之间的语义关系和约束，作为指导以建立概括对象关系的语义图，其中一些对象之间的关系是不能直接从图像或视频中获得。特别是，本文的方法是通过常识推理和关系推理的迭代学习算法交替实现的，常识推理将视觉区域嵌入语义空间以构建语义图，关系推理用于编码语义图以生成句子。作者在几个基准数据集上的实验验证了该方法的有效性。

以生成视频描述为例展示 C-R Reasoning 方法。

C-R reasoning 迭代执行示意图。

算法。

推荐：这篇论文并不是聚焦于常识知识和常识推理本身，而是联合常识和关系推理使得图像和视频描述中那些「难以捉摸」，「并非直接可见」的物体或关系现形，使得描述更加精准。

论文 6：PIQA: Reasoning about Physical Commonsense in Natural Language

• 作者：Yonatan Bisk、Rowan Zellers、Ronan Le Bras 等
• 论文链接：https://arxiv.org/pdf/1911.11641.pdf

摘要：「在不使用刷子涂眼影的情况下，我应该用棉签还是牙签？」类似这种需要物理世界常识的问题对现今的自然语言理解系统提出了挑战。虽然最近的预训练模型 (如 BERT) 在更抽象的如新闻文章和百科词条这种具有丰富文本信息的领域问答方面取得了进展，但在更现实的领域，由于报导的偏差，文本本质上是有限的，类似于「用牙签涂眼影是一个坏主意」这样的事实很少得到直接报道。人工智能系统能够在不经历物理世界的情况下可靠地回答物理常识问题吗？是否能够捕获有关日常物品的常识知识，包括它们的物理特性、承受能力以及如何操纵它们。

在本文中，研究者介绍了一个关于物理常识推理任务和相应的基准数据集 PIQA（Physical Interaction：Question Answering）进行评估。虽然人类应对这一数据集很容易 (95% 的准确率)，但是大型的预训模型很难 (77%)。作者分析了现有模型所缺乏的知识为未来的研究提供了重要的机遇。

PIQA 数据样本示例。

PIQA 数据集示意（左边的问答更侧重于物体的属性，右边的问答从技术角度而言都是对的，但是侧重于更方便可取）。

通过常识概念看 RoBERTa 对物理世界的理解（左）；『water』,『spoon』,『freeze』的最常见替换词（右）。

推荐：本篇论文提出的任务非常新颖，物理常识更注重于物体的物理属性，且 PIQA 数据集偏向于非典型性物理常识，不能直接从已有的文本库中得到答案。

论文 7：Graph-FCN for image semantic segmentation

• 作者：Yi Lu、Yaran Chen、Dongbin Zhao 等
• 论文链接：https://arxiv.org/pdf/2001.00335.pdf

摘要：使用深度学习执行语义分割在图像像素分类方面取得了巨大进步。但是，深度学习提取高级特征时往往忽略了局部位置信息（local location information），而这对于图像语义分割而言非常重要。

为了避免上述问题，来自中科院自动化所、北京中医药大学的研究者们提出一个执行图像语义分割任务的图模型 Graph-FCN，该模型由全卷积网络（FCN）进行初始化。首先，通过卷积网络将图像网格数据扩展至图结构数据，这样就把语义分割问题转换成了图节点分类问题；然后，使用图卷积网络解决图节点分类问题。研究者称，这是首次将图卷积网络用于图像语义分割的尝试。该方法在 VOC 数据集上获得了有竞争力的 mIOU 性能，相比原始 FCN 模型有 1.34% 的性能提升。

Graph-FCN 架构图。

FCN 结构示意图。本研究使用 FCN-16s 作为基础模型对节点标注进行初始化。

Graph-FCN 和 FCN-16s 的性能对比情况。

推荐：在这篇论文中，来自中科院自动化所和北京中医药大学的研究者另辟蹊径，提出用图卷积网络解决语义分割问题。

ArXiv Weekly Radiostation

机器之心联合由楚航、罗若天发起的ArXiv Weekly Radiostation，在 7 Papers 的基础上，精选本周更多重要论文，包括NLP、CV、ML领域各10篇精选，并提供音频形式的论文摘要简介，详情如下：

本周 10 篇 NLP 精选论文是：

1. A Survey on Knowledge Graphs: Representation, Acquisition and Applications. (from Erik Cambria, Philip S. Yu)

2. Generalizing meanings from partners to populations: Hierarchical inference supports convention formation on networks. (from Noah D. Goodman, Adele E. Goldberg, Thomas L. Griffiths)

3. CoTK: An Open-Source Toolkit for Fast Development and Fair Evaluation of Text Generation. (from Minlie Huang)

4. Conversations with Documents. An Exploration of Document-Centered Assistance. (from Maarten de Rijke, Ryen W. White)

5. Improving Domain-Adapted Sentiment Classification by Deep Adversarial Mutual Learning. (from Hongyuan Zha)

6. Deep segmental phonetic posterior-grams based discovery of non-categories in L2 English speech. (from Xunying Liu)

7. Citation Text Generation. (from Noah A. Smith)

8. On the interaction between supervision and self-play in emergent communication. (from Abhinav Gupta, Joelle Pineau)

9. Exploring Structural Inductive Biases in Emergent Communication. (from Abhinav Gupta)

10. Rapid Adaptation of BERT for Information Extraction on Domain-Specific Business Documents. (from Jimmy Lin)

本周 10 篇 CV 精选论文是：

1.Geocoding of trees from street addresses and street-level images. (from Pietro Perona)

2. Visual Concept-Metaconcept Learning. (from Joshua B. Tenenbaum)

3. Analyzing the Dependency of ConvNets on Spatial Information. (from Bernt Schiele)

4. Deep-Geometric 6 DoF Localization from a Single Image in Topo-metric Maps. (from Tinne Tuytelaars)

5. Towards High Performance Human Keypoint Detection. (from Dacheng Tao)

6. Analysis of Gender Inequality In Face Recognition Accuracy. (from Kevin W. Bowyer)

7. Global Texture Enhancement for Fake Face Detection in the Wild. (from Jiaya Jia, Philip Torr)

8. Monocular 3D Object Detection with Decoupled Structured Polygon Estimation and Height-Guided Depth Estimation. (from Xiaogang Wang)

9. Multi-Channel Attention Selection GANs for Guided Image-to-Image Translation. (from Philip H.S. Torr, Nicu Sebe)

10. Four Principles of Explainable AI as Applied to Biometrics and Facial Forensic Algorithms. (from P. Jonathon Phillips)

本周 10 篇 ML 精选论文是：

1. Learning Fine Grained Place Embeddings with Spatial Hierarchy from Human Mobility Trajectories. (from Toru Shimizu)

2. LUNAR: Cellular Automata for Drifting Data Streams. (from Francisco Herrera)

3. A Tutorial on Learning With Bayesian Networks. (from David Heckerman)

4. Forecasting Industrial Aging Processes with Machine Learning Methods. (from Klaus-Robert Müller)

5. Decoupling Learning Rates Using Empirical Bayes Priors. (from Guido Imbens)

6. Robust saliency maps with decoy-enhanced saliency score. (from William Stafford Noble)

7. Boosting Simple Learners. (from Noga Alon, Elad Hazan)

8. Towards a Fast Steady-State Visual Evoked Potentials (SSVEP) Brain-Computer Interface (BCI). (from Lei Zhang, Xian-Sheng Hua, Cuntai Guan)

9. Exploratory Machine Learning with Unknown Unknowns. (from Zhi-Hua Zhou)

10. On Positive-Unlabeled Classification in GAN. (from Dacheng Tao)

点击阅读原文，查看 ArXiv Weekly Radiostation 全部图文内容。