OpenRaiser/Intern-Atlas huggingface dataset:
Ground Control to Major Tom: the importance of field surveys in remotely sensed data analysis
Venue: arXiv cs.CY 2018
Year: 2018

In this project, we build a modular, scalable system that can collect, store, and process millions of satellite images. We test the relative importance of both of the key limitations constraining the prevailing literature by applying this system to a data-rich environment. To overcome classic data availability concerns, and to quantify their implications in an economically meaningful context, we operate in a data rich environment and work with an outcome variable directly correlated with key indicators of socioeconomic well-being. We collect public records of sale prices of homes within the United States, and then gradually degrade our rich sample in a range of different ways which mimic the sampling strategies employed in actual survey-based datasets. Pairing each house with a corresponding set of satellite images, we use image-based features to predict housing prices within each of these degraded samples. To generalize beyond any given featurization methodology, our system contains an independent featurization module, which can be interchanged with any preferred image classification tool. Our initial findings demonstrate that while satellite imagery can be used to predict housing prices with considerable accuracy, the size and nature of the ground truth sample is a fundamental determinant of the usefulness of imagery for this category of socioeconomic prediction. We quantify the returns to improving the distribution and size of observed data, and show that the image classification method is a second-order concern. Our results provide clear guidance for the development of adaptive sampling strategies in data-sparse locations where satellite-based metrics may be integrated with standard survey data, while also suggesting that advances from image classification techniques for satellite imagery could be further augmented by more robust sampling strategies.
Do two parties represent the US? Clustering analysis of US public ideology survey
Venue: arXiv cs.OH 2018
Year: 2018

Recent surveys have shown that an increasing portion of the US public believes the two major US parties adequately represent the US public opinion and think additional parties are needed. However, there are high barriers for third parties in political elections. In this paper, we aim to address two questions: "How well do the two major US parties represent the public's ideology?" and "Does a more-than-two-party system better represent the ideology of the public?". To address these questions, we utilize the American National Election Studies Time series dataset. We perform unsupervised clustering with Gaussian Mixture Model method on this dataset. When clustered into two clusters, we find a large centrist cluster and a small right-wing cluster. The Democratic Party's position (estimated using the mean position of the individuals self-identified with the parties) is similar to that of the centrist cluster, and the Republican Party's position is between the two clusters. We investigate if more than two parties represent the population better by comparing the Akaike Information Criteria for clustering results of the various number of clusters. We find that additional clusters give a better representation of the data, even after penalizing for the additional parameters. This suggests a multiparty system represents of the ideology of the public better.
An Introduction to Cyber Peacekeeping
Venue: arXiv cs.CY 2018
Year: 2018

Peacekeeping is a noble and essential activity, helping to bring peace to conflict torn areas and providing security to millions of people around the world. Peacekeepers operate in all domains of war: buffer zones on land, no fly zones in the air and ensuring free passage at sea. With the emergence of cyberspace as a domain of war, questions on the role of peacekeeping in this domain naturally arise. There is extensive research around the topic of cyber warfare, but surprisingly little on how to restore and maintain peace in its aftermath. This is a significant gap which needs addressing. We begin by providing an overview of peacekeeping, describing its overarching goals and principles, using the United Nations model as a reference. We then review existing literature on cyber peacekeeping. The paper progresses to discuss the question of whether cyber peacekeeping is needed, and if so, if it is a plausible concept. We explore some ideas on how cyber peacekeeping could be performed and the challenges cyber peacekeepers will face, before making suggestions on where future work should be focused.
The interconnection of quadratic droop voltage controllers is a Lotka-Volterra system: implications for stability analysis
Venue: arXiv cs.SY 2018
Year: 2018

This paper studies the stability of voltage dynamics for a power network in which nodal voltages are controlled by means of quadratic droop controllers with nonlinear AC reactive power as inputs. We show that the voltage dynamics is a Lotka-Volterra system, which is a class of nonlinear positive systems. We study the stability of the closed-loop system by proving a uniform ultimate boundedness result and investigating conditions under which the network is cooperative. We then restrict to study the stability of voltage dynamics under a decoupling assumption (i.e., zero relative angles). We analyze the existence and uniqueness of the equilibrium in the interior of the positive orthant for the system and prove an asymptotic stability result.
Deep Illumination: Approximating Dynamic Global Illumination with Generative Adversarial Network
Venue: arXiv cs.GR 2018
Year: 2018

We present Deep Illumination, a novel machine learning technique for approximating global illumination (GI) in real-time applications using a Conditional Generative Adversarial Network. Our primary focus is on generating indirect illumination and soft shadows with offline rendering quality at interactive rates. Inspired from recent advancement in image-to-image translation problems using deep generative convolutional networks, we introduce a variant of this network that learns a mapping from Gbuffers (depth map, normal map, and diffuse map) and direct illumination to any global illumination solution. Our primary contribution is showing that a generative model can be used to learn a density estimation from screen space buffers to an advanced illumination model for a 3D environment. Once trained, our network can approximate global illumination for scene configurations it has never encountered before within the environment it was trained on. We evaluate Deep Illumination through a comparison with both a state of the art real-time GI technique (VXGI) and an offline rendering GI technique (path tracing). We show that our method produces effective GI approximations and is also computationally cheaper than existing GI techniques. Our technique has the potential to replace existing precomputed and screen-space techniques for producing global illumination effects in dynamic scenes with physically-based rendering quality.
Iterative Detection for Orthogonal Precoding in Doubly Selective Channels
Venue: arXiv cs.IT 2018
Year: 2018

Ultra-reliable wireless communication links require the utilization of all diversity sources of a wireless communication channel. Hadani et al. propose a two dimensional discrete symplectic Fourier transform (DSFT) as orthogonal pre-coder for a time-frequency modulation scheme. In this paper we explore \emph{general} orthogonal precoding (OP) and its performance in time- and frequency-selective channels. We show that iterative parallel interference cancellation (PIC) and iterative channel estimation methods can be used for the detection of OP. A scalar signal model for OP transmission is obtained by PIC. Based on this signal model, we can prove that all constant modulus sequences, e.g. the DSFT basis functions or Walsh-Hadamard sequences, lead to the same performance for OP. We validate our receiver structure by numerical link level simulations of a vehicle-to-vehicle communication link with a relative velocity of $0\ldots200\,\text{km/h}$. We demonstrate that OP achieves a gain of about $4.8\,\text{dB}$ if compared to orthogonal frequency division multiplexing at a bit error rate of $10^{-4}$. Our performance results for coded OP are the best results for a fully documented receiver architecture, published so far.
Permissive Finite-State Controllers of POMDPs using Parameter Synthesis
Venue: arXiv cs.LO 2018
Year: 2018

We study finite-state controllers (FSCs) for partially observable Markov decision processes (POMDPs) that are provably correct with respect to given specifications. The key insight is that computing (randomised) FSCs on POMDPs is equivalent to - and computationally as hard as - synthesis for parametric Markov chains (pMCs). This correspondence allows to use tools for parameter synthesis in pMCs to compute correct-by-construction FSCs on POMDPs for a variety of specifications. Our experimental evaluation shows comparable performance to well-known POMDP solvers.
Topology Adaptive Graph Convolutional Networks
Venue: arXiv cs.LG 2018
Year: 2018

Spectral graph convolutional neural networks (CNNs) require approximation to the convolution to alleviate the computational complexity, resulting in performance loss. This paper proposes the topology adaptive graph convolutional network (TAGCN), a novel graph convolutional network defined in the vertex domain. We provide a systematic way to design a set of fixed-size learnable filters to perform convolutions on graphs. The topologies of these filters are adaptive to the topology of the graph when they scan the graph to perform convolution. The TAGCN not only inherits the properties of convolutions in CNN for grid-structured data, but it is also consistent with convolution as defined in graph signal processing. Since no approximation to the convolution is needed, TAGCN exhibits better performance than existing spectral CNNs on a number of data sets and is also computationally simpler than other recent methods.
Speeding up Context-based Sentence Representation Learning with Non-autoregressive Convolutional Decoding
Venue: arXiv cs.NE 2018
Year: 2018

Context plays an important role in human language understanding, thus it may also be useful for machines learning vector representations of language. In this paper, we explore an asymmetric encoder-decoder structure for unsupervised context-based sentence representation learning. We carefully designed experiments to show that neither an autoregressive decoder nor an RNN decoder is required. After that, we designed a model which still keeps an RNN as the encoder, while using a non-autoregressive convolutional decoder. We further combine a suite of effective designs to significantly improve model efficiency while also achieving better performance. Our model is trained on two different large unlabelled corpora, and in both cases the transferability is evaluated on a set of downstream NLP tasks. We empirically show that our model is simple and fast while producing rich sentence representations that excel in downstream tasks.
Weight Initialization of Deep Neural Networks(DNNs) using Data Statistics
Venue: arXiv cs.LG 2018
Year: 2018

Deep neural networks (DNNs) form the backbone of almost every state-of-the-art technique in the fields such as computer vision, speech processing, and text analysis. The recent advances in computational technology have made the use of DNNs more practical. Despite the overwhelming performances by DNN and the advances in computational technology, it is seen that very few researchers try to train their models from the scratch. Training of DNNs still remains a difficult and tedious job. The main challenges that researchers face during training of DNNs are the vanishing/exploding gradient problem and the highly non-convex nature of the objective function which has up to million variables. The approaches suggested in He and Xavier solve the vanishing gradient problem by providing a sophisticated initialization technique. These approaches have been quite effective and have achieved good results on standard datasets, but these same approaches do not work very well on more practical datasets. We think the reason for this is not making use of data statistics for initializing the network weights. Optimizing such a high dimensional loss function requires careful initialization of network weights. In this work, we propose a data dependent initialization and analyze its performance against the standard initialization techniques such as He and Xavier. We performed our experiments on some practical datasets and the results show our algorithm's superior classification accuracy.
Almost Optimal Stochastic Weighted Matching With Few Queries
Venue: arXiv cs.DS 2018
Year: 2018

We consider the {\em stochastic matching} problem. An edge-weighted general (i.e., not necessarily bipartite) graph $G(V, E)$ is given in the input, where each edge in $E$ is {\em realized} independently with probability $p$; the realization is initially unknown, however, we are able to {\em query} the edges to determine whether they are realized. The goal is to query only a small number of edges to find a {\em realized matching} that is sufficiently close to the maximum matching among all realized edges. This problem has received a considerable attention during the past decade due to its numerous real-world applications in kidney-exchange, matchmaking services, online labor markets, and advertisements. Our main result is an {\em adaptive} algorithm that for any arbitrarily small $ε> 0$, finds a $(1-ε)$-approximation in expectation, by querying only $O(1)$ edges per vertex. We further show that our approach leads to a $(1/2-ε)$-approximate {\em non-adaptive} algorithm that also queries only $O(1)$ edges per vertex. Prior to our work, no nontrivial approximation was known for weighted graphs using a constant per-vertex budget. The state-of-the-art adaptive (resp. non-adaptive) algorithm of Maehara and Yamaguchi [SODA 2018] achieves a $(1-ε)$-approximation (resp. $(1/2-ε)$-approximation) by querying up to $O(w\log{n})$ edges per vertex where $w$ denotes the maximum integer edge-weight. Our result is a substantial improvement over this bound and has an appealing message: No matter what the structure of the input graph is, one can get arbitrarily close to the optimum solution by querying only a constant number of edges per vertex. To obtain our results, we introduce novel properties of a generalization of {\em augmenting paths} to weighted matchings that may be of independent interest.
Modular Labelled Sequent Calculi for Abstract Separation Logics
Venue: arXiv cs.LO 2018
Year: 2018

Abstract separation logics are a family of extensions of Hoare logic for reasoning about programs that manipulate resources such as memory locations. These logics are "abstract" because they are independent of any particular concrete resource model. Their assertion languages, called propositional abstract separation logics (PASLs), extend the logic of (Boolean) Bunched Implications (BBI) in various ways. In particular, these logics contain the connectives $*$ and $-\!*$, denoting the composition and extension of resources respectively. This added expressive power comes at a price since the resulting logics are all undecidable. Given their wide applicability, even a semi-decision procedure for these logics is desirable. Although several PASLs and their relationships with BBI are discussed in the literature, the proof theory and automated reasoning for these logics were open problems solved by the conference version of this paper, which developed a modular proof theory for various PASLs using cut-free labelled sequent calculi. This paper non-trivially improves upon this previous work by giving a general framework of calculi on which any new axiom in the logic satisfying a certain form corresponds to an inference rule in our framework, and the completeness proof is generalised to consider such axioms. Our base calculus handles Calcagno et al.'s original logic of separation algebras by adding sound rules for partial-determinism and cancellativity, while preserving cut-elimination. We then show that many important properties in separation logic, such as indivisible unit, disjointness, splittability, and cross-split, can be expressed in our general axiom form. Thus our framework offers inference rules and completeness for these properties for free. Finally, we show how our calculi reduce to calculi with global label substitutions, enabling more efficient implementation.
A Massively Parallel Algorithm for the Approximate Calculation of Inverse p-th Roots of Large Sparse Matrices
Venue: arXiv cs.DC 2018
Year: 2018

We present the submatrix method, a highly parallelizable method for the approximate calculation of inverse p-th roots of large sparse symmetric matrices which are required in different scientific applications. We follow the idea of Approximate Computing, allowing imprecision in the final result in order to be able to utilize the sparsity of the input matrix and to allow massively parallel execution. For an n x n matrix, the proposed algorithm allows to distribute the calculations over n nodes with only little communication overhead. The approximate result matrix exhibits the same sparsity pattern as the input matrix, allowing for efficient reuse of allocated data structures. We evaluate the algorithm with respect to the error that it introduces into calculated results, as well as its performance and scalability. We demonstrate that the error is relatively limited for well-conditioned matrices and that results are still valuable for error-resilient applications like preconditioning even for ill-conditioned matrices. We discuss the execution time and scaling of the algorithm on a theoretical level and present a distributed implementation of the algorithm using MPI and OpenMP. We demonstrate the scalability of this implementation by running it on a high-performance compute cluster comprised of 1024 CPU cores, showing a speedup of 665x compared to single-threaded execution.
Deciding Confluence and Normal Form Properties of Ground Term Rewrite Systems Efficiently
Venue: arXiv cs.FL 2018
Year: 2018

It is known that the first-order theory of rewriting is decidable for ground term rewrite systems, but the general technique uses tree automata and often takes exponential time. For many properties, including confluence (CR), uniqueness of normal forms with respect to reductions (UNR) and with respect to conversions (UNC), polynomial time decision procedures are known for ground term rewrite systems. However, this is not the case for the normal form property (NFP). In this work, we present a cubic time algorithm for NFP, an almost cubic time algorithm for UNR, and an almost linear time algorithm for UNC, improving previous bounds. We also present a cubic time algorithm for CR.
Asymptotic degree distributions in large (homogeneous) random networks: A little theory and a counterexample
Venue: arXiv cs.SI 2018
Year: 2018

In random graph models, the degree distribution of an individual node should be distinguished from the (empirical) degree distribution of the graph that records the fractions of nodes with given degree. We introduce a general framework to explore when these two degree distributions coincide asymptotically in large homogeneous random networks. The discussion is carried under three basic statistical assumptions on the degree sequences: (i) a weak form of distributional homogeneity; (ii) the existence of an asymptotic (nodal) degree distribution; and (iii) a weak form of asymptotic uncorrelatedness. We show that this asymptotic equality may fail in homogeneous random networks for which (i) and (ii) hold but (iii) does not. The counterexample is found in the class of random threshold graphs. An implication of this finding is that random threshold graphs cannot be used as a substitute to the Barabási-Albert model for scale-free network modeling, as has been proposed by some authors. The results can also be formulated for non-homogeneous models by making use of a random sampling procedure over the nodes.
CrescendoNet: A Simple Deep Convolutional Neural Network with Ensemble Behavior
Venue: arXiv cs.LG 2018
Year: 2018

We introduce a new deep convolutional neural network, CrescendoNet, by stacking simple building blocks without residual connections. Each Crescendo block contains independent convolution paths with increased depths. The numbers of convolution layers and parameters are only increased linearly in Crescendo blocks. In experiments, CrescendoNet with only 15 layers outperforms almost all networks without residual connections on benchmark datasets, CIFAR10, CIFAR100, and SVHN. Given sufficient amount of data as in SVHN dataset, CrescendoNet with 15 layers and 4.1M parameters can match the performance of DenseNet-BC with 250 layers and 15.3M parameters. CrescendoNet provides a new way to construct high performance deep convolutional neural networks without residual connections. Moreover, through investigating the behavior and performance of subnetworks in CrescendoNet, we note that the high performance of CrescendoNet may come from its implicit ensemble behavior, which differs from the FractalNet that is also a deep convolutional neural network without residual connections. Furthermore, the independence between paths in CrescendoNet allows us to introduce a new path-wise training procedure, which can reduce the memory needed for training.
Prophet Secretary for Combinatorial Auctions and Matroids
Venue: arXiv cs.DS 2018
Year: 2018

The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items because of their applications in mechanism design. The most important of these generalizations are to matroids and to combinatorial auctions (extends bipartite matching). Kleinberg-Weinberg \cite{KW-STOC12} and Feldman et al. \cite{feldman2015combinatorial} show that for adversarial arrival order of random variables the optimal prophet inequalities give a $1/2$-approximation. For many settings, however, it's conceivable that the arrival order is chosen uniformly at random, akin to the secretary problem. For such a random arrival model, we improve upon the $1/2$-approximation and obtain $(1-1/e)$-approximation prophet inequalities for both matroids and combinatorial auctions. This also gives improvements to the results of Yan \cite{yan2011mechanism} and Esfandiari et al. \cite{esfandiari2015prophet} who worked in the special cases where we can fully control the arrival order or when there is only a single item. Our techniques are threshold based. We convert our discrete problem into a continuous setting and then give a generic template on how to dynamically adjust these thresholds to lower bound the expected total welfare.