OpenRaiser/Intern-Atlas huggingface dataset:
Using Reinforcement Learning to Validate Empirical Game-Theoretic Analysis: A Continuous Double Auction Study
Venue: arXiv cs.AI 2016
Year: 2016

Empirical game-theoretic analysis (EGTA) has recently been applied successfully to analyze the behavior of large numbers of competing traders in a continuous double auction market. Multiagent simulation methods like EGTA are useful for studying complex strategic environments like a stock market, where it is not feasible to solve analytically for the rational behavior of each agent. A weakness of simulation-based methods in strategic settings, however, is that it is typically impossible to prove that the strategy profile assigned to the simulated agents is stable, as in a Nash equilibrium. I propose using reinforcement learning to analyze the regret of supposed Nash-equilibrium strategy profiles found by EGTA. I have developed a new library of reinforcement learning tools, which I have integrated into an extended version of the market simulator from our prior work. I provide evidence for the effectiveness of our library methods, both on a suite of benchmark problems from the literature, and on non-equilibrium strategy profiles in our market environment. Finally, I use our new reinforcement learning tools to provide evidence that the equilibria found by EGTA in our recent continuous double auction study are likely to have only negligible regret, even with respect to an extended strategy space.
Discordant voting processes on finite graphs
Venue: arXiv cs.DM 2016
Year: 2016

We consider an asynchronous voting process on graphs which we call discordant voting, and which can be described as follows. Initially each vertex holds one of two opinions, red or blue say. Neighbouring vertices with different opinions interact pairwise. After an interaction both vertices have the same colour. The quantity of interest is T, the time to reach consensus , i.e. the number of interactions needed for all vertices have the same colour. An edge whose endpoint colours differ (i.e. one vertex is coloured red and the other one blue) is said to be discordant. A vertex is discordant if its is incident with a discordant edge. In discordant voting, all interactions are based on discordant edges. Because the voting process is asynchronous there are several ways to update the colours of the interacting vertices. Push: Pick a random discordant vertex and push its colour to a random discordant neighbour. Pull: Pick a random discordant vertex and pull the colour of a random discordant neighbour. Oblivious: Pick a random endpoint of a random discordant edge and push the colour to the other end point. We show that E(T), the expected time to reach consensus, depends strongly on the underlying graph and the update rule. For connected graphs on n vertices, and an initial half red, half blue colouring the following hold. For oblivious voting, E(T) =n^2/4 independent of the underlying graph. For the complete graph K_n, the push protocol has E(T)= Theta(n log(n)), whereas the pull protocol has E(T)= Theta(2^n). For the cycle C_n all three protocols have E(T) = Theta(n^2). For the star graph however, the pull protocol has E(T)=O(n^2), whereas the push protocol is slower with E(T) = Theta(n^2 log(n)). The wide variation in E(T) for the pull protocol is to be contrasted with the well known model of synchronous pull voting, for which E(T) = O(n) on many classes of expanders.
Evidence of Online Performance Deterioration in User Sessions on Reddit
Venue: arXiv cs.SI 2016
Year: 2016

This article presents evidence of performance deterioration in online user sessions quantified by studying a massive dataset containing over 55 million comments posted on Reddit in April 2015. After segmenting the sessions (i.e., periods of activity without a prolonged break) depending on their intensity (i.e., how many posts users produced during sessions), we observe a general decrease in the quality of comments produced by users over the course of sessions. We propose mixed-effects models that capture the impact of session intensity on comments, including their length, quality, and the responses they generate from the community. Our findings suggest performance deterioration: Sessions of increasing intensity are associated with the production of shorter, progressively less complex comments, which receive declining quality scores (as rated by other users), and are less and less engaging (i.e., they attract fewer responses). Our contribution evokes a connection between cognitive and attention dynamics and the usage of online social peer production platforms, specifically the effects of deterioration of user performance.
On the Sample Complexity of End-to-end Training vs. Semantic Abstraction Training
Venue: arXiv cs.LG 2016
Year: 2016

We compare the end-to-end training approach to a modular approach in which a system is decomposed into semantically meaningful components. We focus on the sample complexity aspect, in the regime where an extremely high accuracy is necessary, as is the case in autonomous driving applications. We demonstrate cases in which the number of training examples required by the end-to-end approach is exponentially larger than the number of examples required by the semantic abstraction approach.
BinderCracker: Assessing the Robustness of Android System Services
Venue: arXiv cs.CR 2016
Year: 2016

In Android, communications between apps and system services are supported by a transaction-based Inter-Process Communication (IPC) mechanism. Binder, as the cornerstone of this IPC mechanism, separates two communicating parties as client and server. As with any client-server model, the server should not make any assumption on the validity (sanity) of client-side transaction. To our surprise, we find this principle has frequently been overlooked in the implementation of Android system services. In this paper, we demonstrate the prevalence and severity of this vulnerability surface and try to answer why developers keep making this seemingly simple mistake. Specifically, we design and implement BinderCracker, an automatic testing framework that supports parameter-aware fuzzing and has identified more than 100 vulnerabilities in six major versions of Android, including the latest version Android 6.0, Marshmallow. Some of the vulnerabilities have severe security implications, causing privileged code execution or permanent Denial-of-Service (DoS). We analyzed the root causes of these vulnerabilities to find that most of them exist because system service developers only considered exploitations via public APIs. We thus highlight the deficiency of testing only on client-side public APIs and argue for the necessity of testing and protection on the Binder interface - the actual security boundary. Specifically, we discuss the effectiveness and practicality of potential countermeasures, such as precautionary testing and runtime diagnostic.
Cardiac Motion Analysis by Temporal Flow Graphs
Venue: arXiv cs.CV 2016
Year: 2016

Cardiac motion analysis from B-mode ultrasound sequence is a key task in assessing the health of the heart. The paper proposes a new methodology for cardiac motion analysis based on the temporal behaviour of points of interest on the myocardium. We define a new signal called the Temporal Flow Graph (TFG) which depicts the movement of a point of interest over time. It is a graphical representation derived from a flow field and describes the temporal evolution of a point. We prove that TFG for an object undergoing periodic motion is also periodic. This principle can be utilized to derive both global and local information from a given sequence. We demonstrate this for detecting motion irregularities at the sequence, as well as regional levels on real and synthetic data. A coarse localisation of anatomical landmarks such as centres of left/right cavities and valve points is also demonstrated using TFGs.
On Multiple-Input Multiple-Output OFDM with Index Modulation for Next Generation Wireless Networks
Venue: arXiv cs.IT 2016
Year: 2016

Multiple-input multiple-output orthogonal frequency division multiplexing with index modulation (MIMO-OFDM-IM) is a novel multicarrier transmission technique which has been proposed recently as an alternative to classical MIMO-OFDM. In this scheme, OFDM with index modulation (OFDM-IM) concept is combined with MIMO transmission to take advantage of the benefits of these two techniques. In this paper, we shed light on the implementation and error performance analysis of the MIMO-OFDM-IM scheme for next generation 5G wireless networks. Maximum likelihood (ML), near-ML, simple minimum mean square error (MMSE) and ordered successive interference cancellation (OSIC) based MMSE detectors of MIMO-OFDM-IM are proposed and their theoretical performance is investigated. It has been shown via extensive computer simulations that MIMO-OFDM-IM scheme provides an interesting trade-off between error performance and spectral efficiency as well as it achieves considerably better error performance than classical MIMO-OFDM using different type detectors and under realistic conditions.
A Radix Representation for each van der Waerden number $W(r, k)$ with $r$ colors: Why $\log_{r}W(r, k) < k^{2}$ is true whenever $k$ is the number of terms in the arithmetic progression
Venue: arXiv cs.DM 2016
Year: 2016

Here we show that by expressing a van der Waerden number $W(r, k)$ by its radix polynomial representation, it not only is possible to locate each proper subset on $\mathbb{R}$ in which the van der Waerden number lies, but also to show that conditions exist for which the logarithm of the van der Waerden number necessarily is bounded above by the square of the number of terms $k$ in the arithmetic progression. Furthermore we also use the method to find a mathematical expression or formula for the ratio of two "consecutive" van der Waerden numbers of the kind $W(r, k)$, $W(r, k + 1)$.
Towards Better Analysis of Deep Convolutional Neural Networks
Venue: arXiv cs.CV 2016
Year: 2016

Deep convolutional neural networks (CNNs) have achieved breakthrough performance in many pattern recognition tasks such as image classification. However, the development of high-quality deep models typically relies on a substantial amount of trial-and-error, as there is still no clear understanding of when and why a deep model works. In this paper, we present a visual analytics approach for better understanding, diagnosing, and refining deep CNNs. We formulate a deep CNN as a directed acyclic graph. Based on this formulation, a hybrid visualization is developed to disclose the multiple facets of each neuron and the interactions between them. In particular, we introduce a hierarchical rectangle packing algorithm and a matrix reordering algorithm to show the derived features of a neuron cluster. We also propose a biclustering-based edge bundling method to reduce visual clutter caused by a large number of connections between neurons. We evaluated our method on a set of CNNs and the results are generally favorable.
Nested Lattice Codes for Vector Perturbation Systems
Venue: arXiv cs.IT 2016
Year: 2016

Vector perturbation is an encoding method for broadcast channels in which the transmitter solves a shortest vector problem in a lattice to create a perturbation vector, which is then added to the data before transmission. In this work, we introduce nested lattice codes into vector perturbation systems, resulting in a strategy which we deem matrix perturbation. We propose design criteria for the nested lattice codes, and show empirically that lattices satisfying these design criteria can improve the performance of vector perturbation systems. The resulting design criteria are the same as those recently proposed for the Compute-and-Forward protocol.
Extreme-scale Multigrid Components within PETSc
Venue: arXiv cs.MS 2016
Year: 2016

Elliptic partial differential equations (PDEs) frequently arise in continuum descriptions of physical processes relevant to science and engineering. Multilevel preconditioners represent a family of scalable techniques for solving discrete PDEs of this type and thus are the method of choice for high-resolution simulations. The scalability and time-to-solution of massively parallel multilevel preconditioners can be adversely effected by using a coarse-level solver with sub-optimal algorithmic complexity. To maintain scalability, agglomeration techniques applied to the coarse level have been shown to be necessary. In this work, we present a new software component introduced within the Portable Extensible Toolkit for Scientific computation (PETSc) which permits agglomeration. We provide an overview of the design and implementation of this functionality, together with several use cases highlighting the benefits of agglomeration. Lastly, we demonstrate via numerical experiments employing geometric multigrid with structured meshes, the flexibility and performance gains possible using our MPI-rank agglomeration implementation.
Termination Analysis of Probabilistic Programs through Positivstellensatz's
Venue: arXiv cs.PL 2016
Year: 2016

We consider nondeterministic probabilistic programs with the most basic liveness property of termination. We present efficient methods for termination analysis of nondeterministic probabilistic programs with polynomial guards and assignments. Our approach is through synthesis of polynomial ranking supermartingales, that on one hand significantly generalizes linear ranking supermartingales and on the other hand is a counterpart of polynomial ranking-functions for proving termination of nonprobabilistic programs. The approach synthesizes polynomial ranking-supermartingales through Positivstellensatz's, yielding an efficient method which is not only sound, but also semi-complete over a large subclass of programs. We show experimental results to demonstrate that our approach can handle several classical programs with complex polynomial guards and assignments, and can synthesize efficient quadratic ranking-supermartingales when a linear one does not exist even for simple affine programs.
Observing and Recommending from a Social Web with Biases
Venue: arXiv cs.DB 2016
Year: 2016

The research question this report addresses is: how, and to what extent, those directly involved with the design, development and employment of a specific black box algorithm can be certain that it is not unlawfully discriminating (directly and/or indirectly) against particular persons with protected characteristics (e.g. gender, race and ethnicity)?
The Manifold Particle Filter for State Estimation on High-dimensional Implicit Manifolds
Venue: arXiv cs.RO 2016
Year: 2016

We estimate the state a noisy robot arm and underactuated hand using an Implicit Manifold Particle Filter (MPF) informed by touch sensors. As the robot touches the world, its state space collapses to a contact manifold that we represent implicitly using a signed distance field. This allows us to extend the MPF to higher (six or more) dimensional state spaces. Earlier work (which explicitly represents the contact manifold) only shows the MPF in two or three dimensions. Through a series of experiments, we show that the implicit MPF converges faster and is more accurate than a conventional particle filter during periods of persistent contact. We present three methods of sampling the implicit contact manifold, and compare them in experiments.
Implementation of $hp$-adaptive discontinuous finite element methods in Dune-Fem
Venue: arXiv cs.MS 2016
Year: 2016

In this paper we describe generic algorithms and data structures for the implementation of $hp$-adaptive discontinuous finite element methods in the Dune-Fem library. Special attention is given to the often tedious and error-prone task of transferring user data during adaptation. Simultaneously, we generalize the approach to the restriction and prolongation of data currently implemented in Dune-Fem to the case of $p$- and $hp$-adaptation. The dune-fem-hpdg module described in this paper provides an extensible reference implementation of $hp$-adaptive discontinuous discrete function spaces. We give details on its implementation and the extended adaptive interface. As proof of concept we present the practical realization of an $hp$-adaptive interior penalty method for elliptic problems.
About the Structure of the Integer Cone and its Application to Bin Packing
Venue: arXiv cs.DS 2016
Year: 2016

We consider the bin packing problem with $d$ different item sizes and revisit the structure theorem given by Goemans and Rothvoß[6] about solutions of the integer cone. We present new techniques on how solutions can be modified and give a new structure theorem that relies on the set of vertices of the underlying integer polytope. As a result of our new structure theorem, we obtain an algorithm for the bin packing problem with running time $|V|^{2^{O(d)}} \cdot enc(I)^{O(1)}$, where $V$ is the set of vertices of the integer knapsack polytope and $enc(I)$ is the encoding length of the bin packing instance. The algorithm is fixed parameter tractable, parameterized by the number of vertices of the integer knapsack polytope $|V|$. This shows that the bin packing problem can be solved efficiently when the underlying integer knapsack polytope has an easy structure, i.e. has a small number of vertices. Furthermore, we show that the presented bounds of the structure theorem are asymptotically tight. We give a construction of bin packing instances using new structural insights and classical number theoretical theorems which yield the desired lower bound.
End to End Learning for Self-Driving Cars
Venue: arXiv cs.CV 2016
Year: 2016

We trained a convolutional neural network (CNN) to map raw pixels from a single front-facing camera directly to steering commands. This end-to-end approach proved surprisingly powerful. With minimum training data from humans the system learns to drive in traffic on local roads with or without lane markings and on highways. It also operates in areas with unclear visual guidance such as in parking lots and on unpaved roads. The system automatically learns internal representations of the necessary processing steps such as detecting useful road features with only the human steering angle as the training signal. We never explicitly trained it to detect, for example, the outline of roads. Compared to explicit decomposition of the problem, such as lane marking detection, path planning, and control, our end-to-end system optimizes all processing steps simultaneously. We argue that this will eventually lead to better performance and smaller systems. Better performance will result because the internal components self-optimize to maximize overall system performance, instead of optimizing human-selected intermediate criteria, e.g., lane detection. Such criteria understandably are selected for ease of human interpretation which doesn't automatically guarantee maximum system performance. Smaller networks are possible because the system learns to solve the problem with the minimal number of processing steps. We used an NVIDIA DevBox and Torch 7 for training and an NVIDIA DRIVE(TM) PX self-driving car computer also running Torch 7 for determining where to drive. The system operates at 30 frames per second (FPS).
Supervised Incremental Hashing
Venue: arXiv cs.CV 2016
Year: 2016

We propose an incremental strategy for learning hash functions with kernels for large-scale image search. Our method is based on a two-stage classification framework that treats binary codes as intermediate variables between the feature space and the semantic space. In the first stage of classification, binary codes are considered as class labels by a set of binary SVMs; each corresponds to one bit. In the second stage, binary codes become the input space of a multi-class SVM. Hash functions are learned by an efficient algorithm where the NP-hard problem of finding optimal binary codes is solved via cyclic coordinate descent and SVMs are trained in a parallelized incremental manner. For modifications like adding images from a previously unseen class, we describe an incremental procedure for effective and efficient updates to the previous hash functions. Experiments on three large-scale image datasets demonstrate the effectiveness of the proposed hashing method, Supervised Incremental Hashing (SIH), over the state-of-the-art supervised hashing methods.
A Survey of Motion Planning and Control Techniques for Self-driving Urban Vehicles
Venue: arXiv cs.RO 2016
Year: 2016

Self-driving vehicles are a maturing technology with the potential to reshape mobility by enhancing the safety, accessibility, efficiency, and convenience of automotive transportation. Safety-critical tasks that must be executed by a self-driving vehicle include planning of motions through a dynamic environment shared with other vehicles and pedestrians, and their robust executions via feedback control. The objective of this paper is to survey the current state of the art on planning and control algorithms with particular regard to the urban setting. A selection of proposed techniques is reviewed along with a discussion of their effectiveness. The surveyed approaches differ in the vehicle mobility model used, in assumptions on the structure of the environment, and in computational requirements. The side-by-side comparison presented in this survey helps to gain insight into the strengths and limitations of the reviewed approaches and assists with system level design choices.
Joint Semantic Segmentation and Depth Estimation with Deep Convolutional Networks
Venue: arXiv cs.CV 2016
Year: 2016

Multi-scale deep CNNs have been used successfully for problems mapping each pixel to a label, such as depth estimation and semantic segmentation. It has also been shown that such architectures are reusable and can be used for multiple tasks. These networks are typically trained independently for each task by varying the output layer(s) and training objective. In this work we present a new model for simultaneous depth estimation and semantic segmentation from a single RGB image. Our approach demonstrates the feasibility of training parts of the model for each task and then fine tuning the full, combined model on both tasks simultaneously using a single loss function. Furthermore we couple the deep CNN with fully connected CRF, which captures the contextual relationships and interactions between the semantic and depth cues improving the accuracy of the final results. The proposed model is trained and evaluated on NYUDepth V2 dataset outperforming the state of the art methods on semantic segmentation and achieving comparable results on the task of depth estimation.