OpenRaiser/Intern-Atlas huggingface dataset:
ConvPoint: Continuous Convolutions for Point Cloud Processing
Venue: arXiv cs.CV 2020
Year: 2020

Point clouds are unstructured and unordered data, as opposed to images. Thus, most machine learning approach developed for image cannot be directly transferred to point clouds. In this paper, we propose a generalization of discrete convolutional neural networks (CNNs) in order to deal with point clouds by replacing discrete kernels by continuous ones. This formulation is simple, allows arbitrary point cloud sizes and can easily be used for designing neural networks similarly to 2D CNNs. We present experimental results with various architectures, highlighting the flexibility of the proposed approach. We obtain competitive results compared to the state-of-the-art on shape classification, part segmentation and semantic segmentation for large-scale point clouds.
Scalable Planning with Deep Neural Network Learned Transition Models
Venue: arXiv cs.AI 2020
Year: 2020

In many real-world planning problems with factored, mixed discrete and continuous state and action spaces such as Reservoir Control, Heating Ventilation, and Air Conditioning, and Navigation domains, it is difficult to obtain a model of the complex nonlinear dynamics that govern state evolution. However, the ubiquity of modern sensors allows us to collect large quantities of data from each of these complex systems and build accurate, nonlinear deep neural network models of their state transitions. But there remains one major problem for the task of control -- how can we plan with deep network learned transition models without resorting to Monte Carlo Tree Search and other black-box transition model techniques that ignore model structure and do not easily extend to mixed discrete and continuous domains? In this paper, we introduce two types of nonlinear planning methods that can leverage deep neural network learned transition models: Hybrid Deep MILP Planner (HD-MILP-Plan) and Tensorflow Planner (TF-Plan). In HD-MILP-Plan, we make the critical observation that the Rectified Linear Unit transfer function for deep networks not only allows faster convergence of model learning, but also permits a direct compilation of the deep network transition model to a Mixed-Integer Linear Program encoding. Further, we identify deep network specific optimizations for HD-MILP-Plan that improve performance over a base encoding and show that we can plan optimally with respect to the learned deep networks. In TF-Plan, we take advantage of the efficiency of auto-differentiation tools and GPU-based computation where we encode a subclass of purely continuous planning problems as Recurrent Neural Networks and directly optimize the actions through backpropagation. We compare both planners and show that TF-Plan is able to approximate the optimal plans found by HD-MILP-Plan in less computation time...
The Information Complexity of Learning Tasks, their Structure and their Distance
Venue: arXiv cs.LG 2020
Year: 2020

We introduce an asymmetric distance in the space of learning tasks, and a framework to compute their complexity. These concepts are foundational for the practice of transfer learning, whereby a parametric model is pre-trained for a task, and then fine-tuned for another. The framework we develop is non-asymptotic, captures the finite nature of the training dataset, and allows distinguishing learning from memorization. It encompasses, as special cases, classical notions from Kolmogorov complexity, Shannon, and Fisher Information. However, unlike some of those frameworks, it can be applied to large-scale models and real-world datasets. Our framework is the first to measure complexity in a way that accounts for the effect of the optimization scheme, which is critical in Deep Learning.
Semantic Graph Convolutional Networks for 3D Human Pose Regression
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we study the problem of learning Graph Convolutional Networks (GCNs) for regression. Current architectures of GCNs are limited to the small receptive field of convolution filters and shared transformation matrix for each node. To address these limitations, we propose Semantic Graph Convolutional Networks (SemGCN), a novel neural network architecture that operates on regression tasks with graph-structured data. SemGCN learns to capture semantic information such as local and global node relationships, which is not explicitly represented in the graph. These semantic relationships can be learned through end-to-end training from the ground truth without additional supervision or hand-crafted rules. We further investigate applying SemGCN to 3D human pose regression. Our formulation is intuitive and sufficient since both 2D and 3D human poses can be represented as a structured graph encoding the relationships between joints in the skeleton of a human body. We carry out comprehensive studies to validate our method. The results prove that SemGCN outperforms state of the art while using 90% fewer parameters.
Simple dynamic word embeddings for mapping perceptions in the public sphere
Venue: arXiv cs.CY 2020
Year: 2020

Word embeddings trained on large-scale historical corpora can illuminate human biases and stereotypes that perpetuate social inequalities. These embeddings are often trained in separate vector space models defined according to different attributes of interest. In this paper, we develop a unified dynamic embedding model that learns attribute-specific word embeddings. We apply our model to investigate i) 20th century gender and ethnic occupation biases embedded in the Corpus of Historical American English (COHA), and ii) biases against refugees embedded in a novel corpus of talk radio transcripts containing 119 million words produced over one month across 83 stations and 64 cities. Our results shed preliminary light on scenarios when dynamic embedding models may be more suitable for representing linguistic biases than individual vector space models, and vice-versa.
Uniform Input-to-State Stability for Switched and Time-Varying Impulsive Systems
Venue: arXiv cs.SY 2020
Year: 2020

We provide a Lyapunov-function-based method for establishing different types of uniform input-to-state stability (ISS) for time-varying impulsive systems. The method generalizes to impulsive systems with inputs the well-established philosophy of assessing the stability of a system by reducing the problem to that of the stability of a scalar system given by the evolution of the Lyapunov function on the system trajectories. This reduction is performed in such a way so that the resulting scalar system has no inputs. Novel sufficient conditions for ISS are provided, which generalize existing results for time-invariant and time-varying, switched and nonswitched, impulsive and nonimpulsive systems in several directions.
Doodle to Search: Practical Zero-Shot Sketch-based Image Retrieval
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we investigate the problem of zero-shot sketch-based image retrieval (ZS-SBIR), where human sketches are used as queries to conduct retrieval of photos from unseen categories. We importantly advance prior arts by proposing a novel ZS-SBIR scenario that represents a firm step forward in its practical application. The new setting uniquely recognizes two important yet often neglected challenges of practical ZS-SBIR, (i) the large domain gap between amateur sketch and photo, and (ii) the necessity for moving towards large-scale retrieval. We first contribute to the community a novel ZS-SBIR dataset, QuickDraw-Extended, that consists of 330,000 sketches and 204,000 photos spanning across 110 categories. Highly abstract amateur human sketches are purposefully sourced to maximize the domain gap, instead of ones included in existing datasets that can often be semi-photorealistic. We then formulate a ZS-SBIR framework to jointly model sketches and photos into a common embedding space. A novel strategy to mine the mutual information among domains is specifically engineered to alleviate the domain gap. External semantic knowledge is further embedded to aid semantic transfer. We show that, rather surprisingly, retrieval performance significantly outperforms that of state-of-the-art on existing datasets that can already be achieved using a reduced version of our model. We further demonstrate the superior performance of our full model by comparing with a number of alternatives on the newly proposed dataset. The new dataset, plus all training and testing code of our model, will be publicly released to facilitate future research
Density-friendly Graph Decomposition
Venue: arXiv cs.DS 2020
Year: 2020

Decomposing a graph into a hierarchical structure via $k$-core analysis is a standard operation in any modern graph-mining toolkit. $k$-core decomposition is a simple and efficient method that allows to analyze a graph beyond its mere degree distribution. More specifically, it is used to identify areas in the graph of increasing centrality and connectedness, and it allows to reveal the structural organization of the graph. Despite the fact that $k$-core analysis relies on vertex degrees, $k$-cores do not satisfy a certain, rather natural, density property. Simply put, the most central $k$-core is not necessarily the densest subgraph. This inconsistency between $k$-cores and graph density provides the basis of our study. We start by defining what it means for a subgraph to be locally-dense, and we show that our definition entails a nested chain decomposition of the graph, similar to the one given by $k$-cores, but in this case the components are arranged in order of increasing density. We show that such a locally-dense decomposition for a graph $G=(V,E)$ can be computed in polynomial time. The running time of the exact decomposition algorithm is $O(|V|^2|E|)$ but is significantly faster in practice. In addition, we develop a linear-time algorithm that provides a factor-2 approximation to the optimal locally-dense decomposition. Furthermore, we show that the $k$-core decomposition is also a factor-2 approximation, however, as demonstrated by our experimental evaluation, in practice $k$-cores have different structure than locally-dense subgraphs, and as predicted by the theory, $k$-cores are not always well-aligned with graph density.
Sampling, Intervention, Prediction, Aggregation: A Generalized Framework for Model-Agnostic Interpretations
Venue: arXiv cs.LG 2020
Year: 2020

Model-agnostic interpretation techniques allow us to explain the behavior of any predictive model. Due to different notations and terminology, it is difficult to see how they are related. A unified view on these methods has been missing. We present the generalized SIPA (sampling, intervention, prediction, aggregation) framework of work stages for model-agnostic interpretations and demonstrate how several prominent methods for feature effects can be embedded into the proposed framework. Furthermore, we extend the framework to feature importance computations by pointing out how variance-based and performance-based importance measures are based on the same work stages. The SIPA framework reduces the diverse set of model-agnostic techniques to a single methodology and establishes a common terminology to discuss them in future work.
A Survey of Distributed Consensus Protocols for Blockchain Networks
Venue: arXiv cs.CR 2020
Year: 2020

Since the inception of Bitcoin, cryptocurrencies and the underlying blockchain technology have attracted an increasing interest from both academia and industry. Among various core components, consensus protocol is the defining technology behind the security and performance of blockchain. From incremental modifications of Nakamoto consensus protocol to innovative alternative consensus mechanisms, many consensus protocols have been proposed to improve the performance of the blockchain network itself or to accommodate other specific application needs. In this survey, we present a comprehensive review and analysis on the state-of-the-art blockchain consensus protocols. To facilitate the discussion of our analysis, we first introduce the key definitions and relevant results in the classic theory of fault tolerance which help to lay the foundation for further discussion. We identify five core components of a blockchain consensus protocol, namely, block proposal, block validation, information propagation, block finalization, and incentive mechanism. A wide spectrum of blockchain consensus protocols are then carefully reviewed accompanied by algorithmic abstractions and vulnerability analyses. The surveyed consensus protocols are analyzed using the five-component framework and compared with respect to different performance metrics. These analyses and comparisons provide us new insights in the fundamental differences of various proposals in terms of their suitable application scenarios, key assumptions, expected fault tolerance, scalability, drawbacks and trade-offs. We believe this survey will provide blockchain developers and researchers a comprehensive view on the state-of-the-art consensus protocols and facilitate the process of designing future protocols.
Stability-Preserving, Time-Efficient Mechanisms for School Choice in Two Rounds
Venue: arXiv cs.GT 2020
Year: 2020

We address the following dynamic version of the school choice question: a city, named City, admits students in two temporally-separated rounds, denoted $\mathcal{R}_1$ and $\mathcal{R}_2$. In round $\mathcal{R}_1$, the capacity of each school is fixed and mechanism $\mathcal{M}_1$ finds a student optimal stable matching. In round $\mathcal{R}_2$, certain parameters change, e.g., new students move into the City or the City is happy to allocate extra seats to specific schools. We study a number of Settings of this kind and give polynomial time algorithms for obtaining a stable matching for the new situations. It is well established that switching the school of a student midway, unsynchronized with her classmates, can cause traumatic effects. This fact guides us to two types of results, the first simply disallows any re-allocations in round $\mathcal{R}_2$, and the second asks for a stable matching that minimizes the number of re-allocations. For the latter, we prove that the stable matchings which minimize the number of re-allocations form a sublattice of the lattice of stable matchings. Observations about incentive compatibility are woven into these results. We also give a third type of results, namely proofs of NP-hardness for a mechanism for round $\mathcal{R}_2$ under certain settings.
Mutual information for low-rank even-order symmetric tensor estimation
Venue: arXiv cs.IT 2020
Year: 2020

We consider a statistical model for finite-rank symmetric tensor factorization and prove a single-letter variational expression for its asymptotic mutual information when the tensor is of even order. The proof applies the adaptive interpolation method originally invented for rank-one factorization. Here we show how to extend the adaptive interpolation to finite-rank and even-order tensors. This requires new nontrivial ideas with respect to the current analysis in the literature. We also underline where the proof falls short when dealing with odd-order tensors.
Towards Analyzing Semantic Robustness of Deep Neural Networks
Venue: arXiv cs.CV 2020
Year: 2020

Despite the impressive performance of Deep Neural Networks (DNNs) on various vision tasks, they still exhibit erroneous high sensitivity toward semantic primitives (e.g. object pose). We propose a theoretically grounded analysis for DNN robustness in the semantic space. We qualitatively analyze different DNNs' semantic robustness by visualizing the DNN global behavior as semantic maps and observe interesting behavior of some DNNs. Since generating these semantic maps does not scale well with the dimensionality of the semantic space, we develop a bottom-up approach to detect robust regions of DNNs. To achieve this, we formalize the problem of finding robust semantic regions of the network as optimizing integral bounds and we develop expressions for update directions of the region bounds. We use our developed formulations to quantitatively evaluate the semantic robustness of different popular network architectures. We show through extensive experimentation that several networks, while trained on the same dataset and enjoying comparable accuracy, do not necessarily perform similarly in semantic robustness. For example, InceptionV3 is more accurate despite being less semantically robust than ResNet50. We hope that this tool will serve as a milestone towards understanding the semantic robustness of DNNs.
Planar graphs have bounded queue-number
Venue: arXiv cs.DM 2020
Year: 2020

We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath, Leighton and Rosenberg from 1992. The key to the proof is a new structural tool called layered partitions, and the result that every planar graph has a vertex-partition and a layering, such that each part has a bounded number of vertices in each layer, and the quotient graph has bounded treewidth. This result generalises for graphs of bounded Euler genus. Moreover, we prove that every graph in a minor-closed class has such a layered partition if and only if the class excludes some apex graph. Building on this work and using the graph minor structure theorem, we prove that every proper minor-closed class of graphs has bounded queue-number. Layered partitions have strong connections to other topics, including the following two examples. First, they can be interpreted in terms of strong products. We show that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Similar statements hold for all proper minor-closed classes. Second, we give a simple proof of the result by DeVos et al. (2004) that graphs in a proper minor-closed class have low treewidth colourings.
Fast multipole networks
Venue: arXiv cs.MA 2020
Year: 2020

Two prerequisites for robotic multiagent systems are mobility and communication. Fast multipole networks (FMNs) enable both ends within a unified framework. FMNs can be organized very efficiently in a distributed way from local information and are ideally suited for motion planning using artificial potentials. We compare FMNs to conventional communication topologies, and find that FMNs offer competitive communication performance (including higher network efficiency per edge at marginal energy cost) in addition to advantages for mobility.
Combinatorial constructions of intrinsic geometries
Venue: arXiv cs.CG 2020
Year: 2020

A generic method for combinatorial constructions of intrinsic geometrical spaces is presented. It is based on the well known inverse sequences of finite graphs that determine (in the limit) topological spaces. If a pattern of the construction is sufficiently regular and uniform, then the notions of metric, geodesic and curvature can be defined in the space as the limits of their finite versions in the graphs. This gives rise to consider the graphs with metrics as finite approximations of the geometry of the space. On the basis of simple and generic examples, several nonstandard and novel notions are proposed for the Foundations of Geometry. They may be considered as a subject of a critical discussion.
Deep Learning Inversion of Electrical Resistivity Data
Venue: arXiv cs.CV 2020
Year: 2020

The inverse problem of electrical resistivity surveys (ERSs) is difficult because of its nonlinear and ill-posed nature. For this task, traditional linear inversion methods still face challenges such as suboptimal approximation and initial model selection. Inspired by the remarkable nonlinear mapping ability of deep learning approaches, in this article, we propose to build the mapping from apparent resistivity data (input) to resistivity model (output) directly by convolutional neural networks (CNNs). However, the vertically varying characteristic of patterns in the apparent resistivity data may cause ambiguity when using CNNs with the weight sharing and effective receptive field properties. To address the potential issue, we supply an additional tier feature map to CNNs to help those aware of the relationship between input and output. Based on the prevalent U-Net architecture, we design our network (ERSInvNet) that can be trained end-to-end and can reach a very fast inference speed during testing. We further introduce a depth weighting function and a smooth constraint into loss function to improve inversion accuracy for the deep region and suppress false anomalies. Six groups of experiments are considered to demonstrate the feasibility and efficiency of the proposed methods. According to the comprehensive qualitative analysis and quantitative comparison, ERSInvNet with tier feature map, smooth constraints, and depth weighting function together achieve the best performance.
Deep Learning without Weight Transport
Venue: arXiv cs.LG 2020
Year: 2020

Current algorithms for deep learning probably cannot run in the brain because they rely on weight transport, where forward-path neurons transmit their synaptic weights to a feedback path, in a way that is likely impossible biologically. An algorithm called feedback alignment achieves deep learning without weight transport by using random feedback weights, but it performs poorly on hard visual-recognition tasks. Here we describe two mechanisms - a neural circuit called a weight mirror and a modification of an algorithm proposed by Kolen and Pollack in 1994 - both of which let the feedback path learn appropriate synaptic weights quickly and accurately even in large networks, without weight transport or complex wiring.Tested on the ImageNet visual-recognition task, these mechanisms outperform both feedback alignment and the newer sign-symmetry method, and nearly match backprop, the standard algorithm of deep learning, which uses weight transport.
Elucidating image-to-set prediction: An analysis of models, losses and datasets
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we identify an important reproducibility challenge in the image-to-set prediction literature that impedes proper comparisons among published methods, namely, researchers use different evaluation protocols to assess their contributions. To alleviate this issue, we introduce an image-to-set prediction benchmark suite built on top of five public datasets of increasing task complexity that are suitable for multi-label classification (VOC, COCO, NUS-WIDE, ADE20k and Recipe1M). Using the benchmark, we provide an in-depth analysis where we study the key components of current models, namely the choice of the image representation backbone as well as the set predictor design. Our results show that (1) exploiting better image representation backbones leads to higher performance boosts than enhancing set predictors, and (2) modeling both the label co-occurrences and ordering has a slight positive impact in terms of performance, whereas explicit cardinality prediction only helps when training on complex datasets, such as Recipe1M. To facilitate future image-to-set prediction research, we make the code, best models and dataset splits publicly available at: https://github.com/facebookresearch/image-to-set.