OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Evolutionary Methods for Game Agent Optimisation: Model-Based is Best
Venue: arXiv cs.AI 2019
Year: 2019

This paper introduces a simple and fast variant of Planet Wars as a test-bed for statistical planning based Game AI agents, and for noisy hyper-parameter optimisation. Planet Wars is a real-time strategy game with simple rules but complex game-play. The variant introduced in this paper is designed for speed to enable efficient experimentation, and also for a fixed action space to enable practical inter-operability with General Video Game AI agents. If we treat the game as a win-loss game (which is standard), then this leads to challenging noisy optimisation problems both in tuning agents to play the game, and in tuning game parameters. Here we focus on the problem of tuning an agent, and report results using the recently developed N-Tuple Bandit Evolutionary Algorithm and a number of other optimisers, including Sequential Model-based Algorithm Configuration (SMAC). Results indicate that the N-Tuple Bandit Evolutionary offers competitive performance as well as insight into the effects of combinations of parameter choices.
Trainable Associative Memory Neural Networks in a Quantum-Dot Cellular Automata
Venue: arXiv cs.ET 2019
Year: 2019

Quantum-dot cellular automata (QCAs) offer a diffusive computing paradigm with picosecond transmission speed, making them an ideal candidate for moving diffusive computing to real-world applications. By implementing a trainable associative memory neural network into this substrate, we demonstrate that high-speed, high-density associative memory is feasible through QCAs. The presented design occupies $415\text{nm}^2$ per neuron, which translates to circa $240 \text{ billion neurons/cm}^2$, or $28\text{GB/cm}^2$ of memory storage, offering a real possibility for large-scale associative memory circuits. Results are presented from simulation, demonstrating correct working behaviour of the associative memory in single neurons, two-neuron and four-neuron arrays.
On Fast Matrix Inversion via Fast Matrix Multiplication
Venue: arXiv cs.SC 2019
Year: 2019

Volker Strassen first suggested an algorithm to multiply matrices with worst case running time less than the conventional $\mathcal{O}(n^3)$ operations in 1969. He also presented a recursive algorithm with which to invert matrices, and calculate determinants using matrix multiplication. James R. Bunch & John E. Hopcroft improved upon this in 1974 by providing modifications to the inversion algorithm in the case where principal submatrices were singular, amongst other improvements. We cover the case of multivariate polynomial matrix inversion, where it is noted that conventional methods that assume a field will experience major setbacks. Initially, the author and others published a presentation of a fraction free formulation of inversion via matrix multiplication along with motivations, however analysis of this presentation was rudimentary. We hence provide a discussion of the true complexities of this fraction free method arising from matrix multiplication, and arrive at its limitations.
Antenna Placement and Performance Tradeoffs with Hand Blockage in Millimeter Wave Systems
Venue: arXiv cs.IT 2019
Year: 2019

The ongoing commercial deployment of millimeter wave systems brings into focus a number of practical issues in form factor user equipment (UE) design. With wavelengths becoming smaller, antenna gain patterns becoming directional, and link budgets critically dependent on beamforming, it becomes imperative to use a number of antenna modules at different locations of the UE for good performance. While more antennas/modules can enhance beamforming array gains, it comes with the tradeoff of higher component cost, power consumption of the associated radio frequency circuitry, and a beam management overhead in learning the appropriate beam weights. Thus, the goal of a good UE design is to provide robust spherical coverage corresponding to good array gains over the entire sphere around the UE with a low beam management overhead, complexity, and cost. The scope of this paper is to study the implications of two popular commercial millimeter wave UE designs (a face and an edge design) on spherical coverage. We show that analog beam codebooks can result in good performance for both the designs, and the edge design provides a better tradeoff in terms of robust performance (with hand blockage), beam management overhead, implementation complexity from an antenna placement standpoint and cost.
High-order curvilinear hybrid mesh generation for CFD simulations
Venue: arXiv cs.GR 2019
Year: 2019

We describe a semi-structured method for the generation of high-order hybrid meshes suited for the simulation of high Reynolds number flows. This is achieved through the use of highly stretched elements in the viscous boundary layers near the wall surfaces. CADfix is used to first repair any possible defects in the CAD geometry and then generate a medial object based decomposition of the domain that wraps the wall boundaries with partitions suitable for the generation of either prismatic or hexahedral elements. The latter is a novel distinctive feature of the method that permits to obtain well-shaped hexahedral meshes at corners or junctions in the boundary layer. The medial object approach allows greater control on the "thickness" of the boundary-layer mesh than is generally achievable with advancing layer techniques. CADfix subsequently generates a hybrid straight sided mesh of prismatic and hexahedral elements in the near-field region modelling the boundary layer, and tetrahedral elements in the far-field region covering the rest of the domain. The mesh in the near-field region provides a framework that facilitates the generation, via an isoparametric technique, of layers of highly stretched elements with a distribution of points in the direction normal to the wall tailored to efficiently and accurately capture the flow in the boundary layer. The final step is the generation of a high-order mesh using NekMesh, a high-order mesh generator within the Nektar++ framework. NekMesh uses the CADfix API as a geometry engine that handles all the geometrical queries to the CAD geometry required during the high-order mesh generation process. We will describe in some detail the methodology using a simple geometry, a NACA wing tip, for illustrative purposes. Finally, we will present two examples of application to reasonably complex geometries proposed by NASA as CFD validation cases.
Identifying Barriers to Adoption for Rust through Online Discourse
Venue: arXiv cs.HC 2019
Year: 2019

Rust is a low-level programming language known for its unique approach to memory-safe systems programming and for its steep learning curve. To understand what makes Rust difficult to adopt, we surveyed the top Reddit and Hacker News posts and comments about Rust; from these online discussions, we identified three hypotheses about Rust's barriers to adoption. We found that certain key features, idioms, and integration patterns were not easily accessible to new users.
Transformed $\ell_1$ Regularization for Learning Sparse Deep Neural Networks
Venue: arXiv cs.CV 2019
Year: 2019

Deep neural networks (DNNs) have achieved extraordinary success in numerous areas. However, to attain this success, DNNs often carry a large number of weight parameters, leading to heavy costs of memory and computation resources. Overfitting is also likely to happen in such network when the training data are insufficient. These shortcomings severely hinder the application of DNNs in resource-constrained platforms. In fact, many network weights are known to be redundant and can be removed from the network without much loss of performance. To this end, we introduce a new non-convex integrated transformed $\ell_1$ regularizer to promote sparsity for DNNs, which removes both redundant connections and unnecessary neurons simultaneously. To be specific, we apply the transformed $\ell_1$ to the matrix space of network weights and utilize it to remove redundant connections. Besides, group sparsity is also employed as an auxiliary to remove unnecessary neurons. An efficient stochastic proximal gradient algorithm is presented to solve the new model at the same time. To the best of our knowledge, this is the first work to utilize a non-convex regularizer in sparse optimization based method to promote sparsity for DNNs. Experiments on several public datasets demonstrate the effectiveness of the proposed method.
Network-Coding Solutions for Minimal Combination Networks and Their Sub-networks
Venue: arXiv cs.IT 2019
Year: 2019

Minimal multicast networks are fascinating and efficient combinatorial objects, where the removal of a single link makes it impossible for all receivers to obtain all messages. We study the structure of such networks, and prove some constraints on their possible solutions. We then focus on the combination network, which is one of the simplest and most insightful network in network-coding theory. Of particular interest are minimal combination networks. We study the gap in alphabet size between vector-linear and scalar-linear network-coding solutions for such minimal combination networks and some of their sub-networks. For minimal multicast networks with two source messages we find the maximum possible gap. We define and study sub-networks of the combination network, which we call Kneser networks, and prove that they attain the upper bound on the gap with equality. We also prove that the study of this gap may be limited to the study of sub-networks of minimal combination networks, by using graph homomorphisms connected with the $q$-analog of Kneser graphs. Additionally, we prove a gap for minimal multicast networks with three or more source messages by studying Kneser networks. Finally, an upper bound on the gap for full minimal combination networks shows nearly no gap, or none in some cases. This is obtained using an MDS-like bound for subspaces over a finite field.
Intelligent Intersection: Two-Stream Convolutional Networks for Real-time Near Accident Detection in Traffic Video
Venue: arXiv cs.CV 2019
Year: 2019

In Intelligent Transportation System, real-time systems that monitor and analyze road users become increasingly critical as we march toward the smart city era. Vision-based frameworks for Object Detection, Multiple Object Tracking, and Traffic Near Accident Detection are important applications of Intelligent Transportation System, particularly in video surveillance and etc. Although deep neural networks have recently achieved great success in many computer vision tasks, a uniformed framework for all the three tasks is still challenging where the challenges multiply from demand for real-time performance, complex urban setting, highly dynamic traffic event, and many traffic movements. In this paper, we propose a two-stream Convolutional Network architecture that performs real-time detection, tracking, and near accident detection of road users in traffic video data. The two-stream model consists of a spatial stream network for Object Detection and a temporal stream network to leverage motion features for Multiple Object Tracking. We detect near accidents by incorporating appearance features and motion features from two-stream networks. Using aerial videos, we propose a Traffic Near Accident Dataset (TNAD) covering various types of traffic interactions that is suitable for vision-based traffic analysis tasks. Our experiments demonstrate the advantage of our framework with an overall competitive qualitative and quantitative performance at high frame rates on the TNAD dataset.
Learning From Less Data: A Unified Data Subset Selection and Active Learning Framework for Computer Vision
Venue: arXiv cs.CV 2019
Year: 2019

Supervised machine learning based state-of-the-art computer vision techniques are in general data hungry. Their data curation poses the challenges of expensive human labeling, inadequate computing resources and larger experiment turn around times. Training data subset selection and active learning techniques have been proposed as possible solutions to these challenges. A special class of subset selection functions naturally model notions of diversity, coverage and representation and can be used to eliminate redundancy thus lending themselves well for training data subset selection. They can also help improve the efficiency of active learning in further reducing human labeling efforts by selecting a subset of the examples obtained using the conventional uncertainty sampling based techniques. In this work, we empirically demonstrate the effectiveness of two diversity models, namely the Facility-Location and Dispersion models for training-data subset selection and reducing labeling effort. We demonstrate this across the board for a variety of computer vision tasks including Gender Recognition, Face Recognition, Scene Recognition, Object Detection and Object Recognition. Our results show that diversity based subset selection done in the right way can increase the accuracy by upto 5 - 10% over existing baselines, particularly in settings in which less training data is available. This allows the training of complex machine learning models like Convolutional Neural Networks with much less training data and labeling costs while incurring minimal performance loss.
Learning Graph Embedding with Adversarial Training Methods
Venue: arXiv cs.LG 2019
Year: 2019

Graph embedding aims to transfer a graph into vectors to facilitate subsequent graph analytics tasks like link prediction and graph clustering. Most approaches on graph embedding focus on preserving the graph structure or minimizing the reconstruction errors for graph data. They have mostly overlooked the embedding distribution of the latent codes, which unfortunately may lead to inferior representation in many cases. In this paper, we present a novel adversarially regularized framework for graph embedding. By employing the graph convolutional network as an encoder, our framework embeds the topological information and node content into a vector representation, from which a graph decoder is further built to reconstruct the input graph. The adversarial training principle is applied to enforce our latent codes to match a prior Gaussian or Uniform distribution. Based on this framework, we derive two variants of adversarial models, the adversarially regularized graph autoencoder (ARGA) and its variational version, adversarially regularized variational graph autoencoder (ARVGA), to learn the graph embedding effectively. We also exploit other potential variations of ARGA and ARVGA to get a deeper understanding on our designs. Experimental results compared among twelve algorithms for link prediction and twenty algorithms for graph clustering validate our solutions.
File System in Data-Centric Computing
Venue: arXiv cs.OS 2019
Year: 2019

The moving computation on the edge or near to data is the new trend that can break the bandwidth wall and to unleash the power of next generation NVM or SCM memory. File system is the important OS subsystem that plays the role of mediator between the user-space application and storage device. The key goal of the file system is to represent the file abstraction and to build the files' namespace. In the current paradigm the file system needs to copy the metadata and user data in the DRAM of the host with the goal to access and to modify the user data on the host side. The DAX approach doesn't change the concept but to build the way to bypass the page cache via the direct access to file's content in persistent memory. Generally speaking, for the case of data-centric computing, the file system needs to solve the opposite task not to copy data into page cache but to deliver the processing activity near data on the storage device side.
Sheaves: A Topological Approach to Big Data
Venue: arXiv cs.LG 2019
Year: 2019

This document develops general concepts useful for extracting knowledge embedded in large graphs or datasets that have pair-wise relationships, such as cause-effect-type relations. Almost no underlying assumptions are made, other than that the data can be presented in terms of pair-wise relationships between objects/events. This assumption is used to mine for patterns in the dataset, defining a reduced graph or dataset that boils-down or concentrates information into a more compact form. The resulting extracted structure or set of patterns are manifestly symbolic in nature, as they capture and encode the graph structure of the dataset in terms of a (generative) grammar. This structure is identified as having the formal mathematical structure of a sheaf. In essence, this paper introduces the basic concepts of sheaf theory into the domain of graphical datasets.
Coding Techniques for Future Wi-Fi
Venue: arXiv cs.IT 2019
Year: 2019

Future wireless applications such as high definition video streaming, wireless cloud radio access networks, and cellular data offload are bandwidth-hungry, which highlights the need for Wi-Fi links exceeding 1 Gb/s. This article discusses coding schemes and, in particular, the use of Low-Density Parity-Check (LDPC) codes as Forward Error Correction (FEC) in future Wi-Fi standards. Moreover, we consider advanced design strategies such as root-check LDPC structures, computer-aided design for short blocks and high-performance decoding algorithms with low latency. We then conclude the article with a discussion of FEC challenges for future Wi-FI applications.
Adaptive Fusion for RGB-D Salient Object Detection
Venue: arXiv cs.CV 2019
Year: 2019

RGB-D salient object detection aims to identify the most visually distinctive objects in a pair of color and depth images. Based upon an observation that most of the salient objects may stand out at least in one modality, this paper proposes an adaptive fusion scheme to fuse saliency predictions generated from two modalities. Specifically, we design a two-streamed convolutional neural network (CNN), each of which extracts features and predicts a saliency map from either RGB or depth modality. Then, a saliency fusion module learns a switch map that is used to adaptively fuse the predicted saliency maps. A loss function composed of saliency supervision, switch map supervision, and edge-preserving constraints is designed to make full supervision, and the entire network is trained in an end-to-end manner. Benefited from the adaptive fusion strategy and the edge-preserving constraint, our approach outperforms state-of-the-art methods on three publicly available datasets.
An Empirical Study of Speculative Concurrency in Ethereum Smart Contracts
Venue: arXiv cs.DC 2019
Year: 2019

We use historical data to estimate the potential benefit of speculative techniques for executing Ethereum smart contracts in parallel. We replay transaction traces of sampled blocks from the Ethereum blockchain over time, using a simple speculative execution engine. In this engine, miners attempt to execute all transactions in a block in parallel, rolling back those that cause data conflicts. Aborted transactions are then executed sequentially. Validators execute the same schedule as miners. We find that our speculative technique yields estimated speed-ups starting at about 8-fold in 2016, declining to about 2-fold at the end of 2017, where speed-up is measured using either gas costs or instruction counts. We also observe that a small set of contracts are responsible for many data conflicts resulting from speculative concurrent execution.
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
Venue: arXiv cs.DS 2019
Year: 2019

We investigate the time-complexity of the All-Pairs Max-Flow problem: Given a graph with $n$ nodes and $m$ edges, compute for all pairs of nodes the maximum-flow value between them. If Max-Flow (the version with a given source-sink pair $s,t$) can be solved in time $T(m)$, then an $O(n^2) \cdot T(m)$ is a trivial upper bound. But can we do better? For directed graphs, recent results in fine-grained complexity suggest that this time bound is essentially optimal. In contrast, for undirected graphs with edge capacities, a seminal algorithm of Gomory and Hu (1961) runs in much faster time $O(n)\cdot T(m)$. Under the plausible assumption that Max-Flow can be solved in near-linear time $m^{1+o(1)}$, this half-century old algorithm yields an $nm^{1+o(1)}$ bound. Several other algorithms have been designed through the years, including $\tilde{O}(mn)$ time for unit-capacity edges (unconditionally), but none of them break the $O(mn)$ barrier. Meanwhile, no super-linear lower bound was shown for undirected graphs. We design the first hardness reductions for All-Pairs Max-Flow in undirected graphs, giving an essentially optimal lower bound for the $\textit{node-capacities}$ setting. For edge capacities, our efforts to prove similar lower bounds have failed, but we have discovered a surprising new algorithm that breaks the $O(mn)$ barrier for graphs with unit-capacity edges! Assuming $T(m)=m^{1+o(1)}$, our algorithm runs in time $m^{3/2 +o(1)}$ and outputs a cut-equivalent tree (similarly to the Gomory-Hu algorithm). Even with current Max-Flow algorithms we improve state-of-the-art as long as $m=O(n^{5/3-\varepsilon})$. Finally, we explain the lack of lower bounds by proving a $\textit{non-reducibility}$ result. This result is based on a new quasi-linear time $\tilde{O}(m)$ $\textit{non-deterministic}$ algorithm for constructing a cut-equivalent tree and may be of independent interest.
Curriculum Model Adaptation with Synthetic and Real Data for Semantic Foggy Scene Understanding
Venue: arXiv cs.CV 2019
Year: 2019

This work addresses the problem of semantic scene understanding under fog. Although marked progress has been made in semantic scene understanding, it is mainly concentrated on clear-weather scenes. Extending semantic segmentation methods to adverse weather conditions such as fog is crucial for outdoor applications. In this paper, we propose a novel method, named Curriculum Model Adaptation (CMAda), which gradually adapts a semantic segmentation model from light synthetic fog to dense real fog in multiple steps, using both labeled synthetic foggy data and unlabeled real foggy data. The method is based on the fact that the results of semantic segmentation in moderately adverse conditions (light fog) can be bootstrapped to solve the same problem in highly adverse conditions (dense fog). CMAda is extensible to other adverse conditions and provides a new paradigm for learning with synthetic data and unlabeled real data. In addition, we present three other main stand-alone contributions: 1) a novel method to add synthetic fog to real, clear-weather scenes using semantic input; 2) a new fog density estimator; 3) a novel fog densification method to densify the fog in real foggy scenes without using depth; and 4) the Foggy Zurich dataset comprising 3808 real foggy images, with pixel-level semantic annotations for 40 images under dense fog. Our experiments show that 1) our fog simulation and fog density estimator outperform their state-of-the-art counterparts with respect to the task of semantic foggy scene understanding (SFSU); 2) CMAda improves the performance of state-of-the-art models for SFSU significantly, benefiting both from our synthetic and real foggy data. The datasets and code are available at the project website.