OpenRaiser/Intern-Atlas huggingface dataset:
Input-to-State Stability of Periodic Orbits of Systems with Impulse Effects via Poincaré Analysis
Venue: arXiv cs.SY 2018
Year: 2018

In this paper we investigate the relation between robustness of periodic orbits exhibited by systems with impulse effects and robustness of their corresponding Poincaré maps. In particular, we prove that input-to-state stability (ISS) of a periodic orbit under external excitation in both continuous and discrete time is equivalent to ISS of the corresponding 0-input fixed point of the associated \emph{forced} Poincaré map. This result extends the classical Poincaré analysis for asymptotic stability of periodic solutions to establish orbital input-to-state stability of such solutions under external excitation. In our proof, we define the forced Poincaré map, and use it to construct ISS estimates for the periodic orbit in terms of ISS estimates of this map under mild assumptions on the input signals. As a consequence of the availability of these estimates, the equivalence between exponential stability (ES) of the fixed point of the 0-input (unforced) Poincaré map and ES of the corresponding orbit is recovered. The results can be applied naturally to study the robustness of periodic orbits of continuous-time systems as well. Although our motivation for extending classical Poincaré analysis to address ISS stems from the need to design robust controllers for limit-cycle walking and running robots, the results are applicable to a much broader class of systems that exhibit periodic solutions.
Nonparametric Composite Hypothesis Testing in an Asymptotic Regime
Venue: arXiv cs.IT 2018
Year: 2018

We investigate the nonparametric, composite hypothesis testing problem for arbitrary unknown distributions in the asymptotic regime where both the sample size and the number of hypotheses grow exponentially large. Such asymptotic analysis is important in many practical problems, where the number of variations that can exist within a family of distributions can be countably infinite. We introduce the notion of \emph{discrimination capacity}, which captures the largest exponential growth rate of the number of hypotheses relative to the sample size so that there exists a test with asymptotically vanishing probability of error. Our approach is based on various distributional distance metrics in order to incorporate the generative model of the data. We provide analyses of the error exponent using the maximum mean discrepancy (MMD) and Kolmogorov-Smirnov (KS) distance and characterize the corresponding discrimination rates, i.e., lower bounds on the discrimination capacity, for these tests. Finally, an upper bound on the discrimination capacity based on Fano's inequality is developed. Numerical results are presented to validate the theoretical results.
A Flexible High-Bandwidth Low-Latency Multi-Port Memory Controller
Venue: arXiv cs.AR 2018
Year: 2018

Multi-port memory controllers (MPMCs) have become increasingly important in many modern applications due to the tremendous growth in bandwidth requirement. Many approaches so far have focused on improving either the memory access latency or the bandwidth utilization for specific applications. Moreover, the application systems are likely to require certain adjustments to connect with an MPMC, since the MPMC interface is limited to a single-clock and single data-width domain. In this paper, we propose efficient techniques to improve the flexibility, latency, and bandwidth of an MPMC. Firstly, MPMC interfaces employ a pair of dual-clock dual-port FIFOs at each port, so any multi-clock multi-data-width application system can connect to an MPMC without requiring extra resources. Secondly, memory access latency is significantly reduced because parallel FIFOs temporarily keep the data transfer between the application system and memory. Lastly, a proposed arbitration scheme, namely window-based first-come-first-serve, considerably enhances the bandwidth utilization. Depending on the applications, MPMC can be properly configured by updating several internal configuration registers. The experimental results in an Altera Cyclone FPGA prove that MPMC is fully operational at 150 MHz and supports up to 32 concurrent connections at various clocks and data widths. More significantly, achieved bandwidth utilization is approximately 93.2% of the theoretical bandwidth, and the access latency is minimized as compared to previous designs.
Domain Adaptation Using Adversarial Learning for Autonomous Navigation
Venue: arXiv cs.CV 2018
Year: 2018

Autonomous navigation has become an increasingly popular machine learning application. Recent advances in deep learning have also resulted in great improvements to autonomous navigation. However, prior outdoor autonomous navigation depends on various expensive sensors or large amounts of real labeled data which is difficult to acquire and sometimes erroneous. The objective of this study is to train an autonomous navigation model that uses a simulator (instead of real labeled data) and an inexpensive monocular camera. In order to exploit the simulator satisfactorily, our proposed method is based on domain adaptation with adversarial learning. Specifically, we propose our model with 1) a dilated residual block in the generator, 2) cycle loss, and 3) style loss to improve the adversarial learning performance for satisfactory domain adaptation. In addition, we perform a theoretical analysis that supports the justification of our proposed method. We present empirical results of navigation in outdoor courses with various intersections using a commercial radio controlled car. We observe that our proposed method allows us to learn a favorable navigation model by generating images with realistic textures. To the best of our knowledge, this is the first work to apply domain adaptation with adversarial learning to autonomous navigation in real outdoor environments. Our proposed method can also be applied to precise image generation or other robotic tasks.
Investigating the Impact of Data Volume and Domain Similarity on Transfer Learning Applications
Venue: arXiv cs.CV 2018
Year: 2018

Transfer learning allows practitioners to recognize and apply knowledge learned in previous tasks (source task) to new tasks or new domains (target task), which share some commonality. The two important factors impacting the performance of transfer learning models are: (a) the size of the target dataset, and (b) the similarity in distribution between source and target domains. Thus far, there has been little investigation into just how important these factors are. In this paper, we investigate the impact of target dataset size and source/target domain similarity on model performance through a series of experiments. We find that more data is always beneficial, and model performance improves linearly with the log of data size, until we are out of data. As source/target domains differ, more data is required and fine tuning will render better performance than feature extraction. When source/target domains are similar and data size is small, fine tuning and feature extraction renders equivalent performance. Our hope is that by beginning this quantitative investigation on the effect of data volume and domain similarity in transfer learning we might inspire others to explore the significance of data in developing more accurate statistical models.
Weighted p-bits for FPGA implementation of probabilistic circuits
Venue: arXiv cs.ET 2018
Year: 2018

Probabilistic spin logic (PSL) is a recently proposed computing paradigm based on unstable stochastic units called probabilistic bits (p-bits) that can be correlated to form probabilistic circuits (p-circuits). These p-circuits can be used to solve problems of optimization, inference and also to implement precise Boolean functions in an "inverted" mode, where a given Boolean circuit can operate in reverse to find the input combinations that are consistent with a given output. In this paper we present a scalable FPGA implementation of such invertible p-circuits. We implement a "weighted" p-bit that combines stochastic units with localized memory structures. We also present a generalized tile of weighted p-bits to which a large class of problems beyond invertible Boolean logic can be mapped, and how invertibility can be applied to interesting problems such as the NP-complete Subset Sum Problem by solving a small instance of this problem in hardware.
Simulated Autonomous Driving on Realistic Road Networks using Deep Reinforcement Learning
Venue: arXiv cs.AI 2018
Year: 2018

Using Deep Reinforcement Learning (DRL) can be a promising approach to handle various tasks in the field of (simulated) autonomous driving. However, recent publications mainly consider learning in unusual driving environments. This paper presents Driving School for Autonomous Agents (DSA^2), a software for validating DRL algorithms in more usual driving environments based on artificial and realistic road networks. We also present the results of applying DSA^2 for handling the task of driving on a straight road while regulating the velocity of one vehicle according to different speed limits.
Scientific Polarization
Venue: arXiv cs.SI 2018
Year: 2018

Contemporary societies are often "polarized", in the sense that sub-groups within these societies hold stably opposing beliefs, even when there is a fact of the matter. Extant models of polarization do not capture the idea that some beliefs are true and others false. Here we present a model, based on the network epistemology framework of Bala and Goyal ["Learning from neighbors", \textit{Rev. Econ. Stud.} \textbf{65}(3), 784-811 (1998)], in which polarization emerges even though agents gather evidence about their beliefs, and true belief yields a pay-off advantage. The key mechanism that generates polarization involves treating evidence generated by other agents as uncertain when their beliefs are relatively different from one's own.
A Multimodal Corpus of Expert Gaze and Behavior during Phonetic Segmentation Tasks
Venue: arXiv cs.HC 2018
Year: 2018

Phonetic segmentation is the process of splitting speech into distinct phonetic units. Human experts routinely perform this task manually by analyzing auditory and visual cues using analysis software, which is an extremely time-consuming process. Methods exist for automatic segmentation, but these are not always accurate enough. In order to improve automatic segmentation, we need to model it as close to the manual segmentation as possible. This corpus is an effort to capture the human segmentation behavior by recording experts performing a segmentation task. We believe that this data will enable us to highlight the important aspects of manual segmentation, which can be used in automatic segmentation to improve its accuracy.
Trajectory Optimization for Curvature Bounded Non-Holonomic Vehicles: Application to Autonomous Driving
Venue: arXiv cs.RO 2018
Year: 2018

In this paper, we propose a trajectory optimization for computing smooth collision free trajectories for nonholonomic curvature bounded vehicles among static and dynamic obstacles. One of the key novelties of our formulation is a hierarchal optimization routine which alternately operates in the space of angular accelerations and linear velocities. That is, the optimization has a two layer structure wherein angular accelerations are optimized keeping the linear velocities fixed and vice versa. If the vehicle/obstacles are modeled as circles than the velocity optimization layer can be shown to have the computationally efficient difference of convex structure commonly observed for linear systems. This leads to a less conservative approximation as compared to that obtained by approximating each polygon individually through its circumscribing circle. On the other hand, it leads to optimization problem with less number of constraints as compared to that obtained when approximating polygons as multiple overlapping circles. We use the proposed trajectory optimization as the basis for constructing a Model Predictive Control framework for navigating an autonomous car in complex scenarios like overtaking, lane changing and merging. Moreover, we also highlight the advantages provided by the alternating optimization routine. Specifically, we show it produces trajectories which have comparable arc lengths and smoothness as compared to those produced with joint simultaneous optimization in the space of angular accelerations and linear velocities. However, importantly, the alternating optimization provides some gain in computational time.
Generalized Degrees of Freedom of the Symmetric Cache-Aided MISO Broadcast Channel with Partial CSIT
Venue: arXiv cs.IT 2018
Year: 2018

We consider the cache-aided MISO broadcast channel (BC) in which a multi-antenna transmitter serves $K$ single-antenna receivers, each equipped with a cache memory. The transmitter has access to partial knowledge of the channel state information. For a symmetric setting, in terms of channel strength levels, partial channel knowledge levels and cache sizes, we characterize the generalized degrees of freedom (GDoF) up to a constant multiplicative factor. The achievability scheme exploits the interplay between spatial multiplexing gains and coded-multicasting gain. On the other hand, a cut-set-based argument in conjunction with a GDoF outer bound for a parallel MISO BC under channel uncertainty are used for the converse. We further show that the characterized order-optimal GDoF is also attained in a decentralized setting, where no coordination is required for content placement in the caches.
Revisit Sparse Polynomial Interpolation based on Randomized Kronecker Substitution
Venue: arXiv cs.SC 2018
Year: 2018

In this paper, a new reduction based interpolation algorithm for black-box multivariate polynomials over finite fields is given. The method is based on two main ingredients. A new Monte Carlo method is given to reduce black-box multivariate polynomial interpolation to black-box univariate polynomial interpolation over any ring. The reduction algorithm leads to multivariate interpolation algorithms with better or the same complexities most cases when combining with various univariate interpolation algorithms. We also propose a modified univariate Ben-or and Tiwarri algorithm over the finite field, which has better total complexity than the Lagrange interpolation algorithm. Combining our reduction method and the modified univariate Ben-or and Tiwarri algorithm, we give a Monte Carlo multivariate interpolation algorithm, which has better total complexity in most cases for sparse interpolation of black-box polynomial over finite fields.
Holoscopic 3D Micro-Gesture Database for Wearable Device Interaction
Venue: arXiv cs.HC 2018
Year: 2018

With the rapid development of augmented reality (AR) and virtual reality (VR) technology, human-computer interaction (HCI) has been greatly improved for gaming interaction of AR and VR control. The finger micro-gesture is one of the important interactive methods for HCI applications such as in the Google Soli and Microsoft Kinect projects. However, the progress in this research is slow due to the lack of high quality public available database. In this paper, holoscopic 3D camera is used to capture high quality micro-gesture images and a new unique holoscopic 3D micro-gesture (HoMG) database is produced. The principle of the holoscopic 3D camera is based on the fly viewing system to see the objects. HoMG database recorded the image sequence of 3 conventional gestures from 40 participants under different settings and conditions. For the purpose of micro-gesture recognition, HoMG has a video subset with 960 videos and a still image subset with 30635 images. Initial micro-gesture recognition on both subsets has been conducted using traditional 2D image and video features and popular classifiers and some encouraging performance has been achieved. The database will be available for the research communities and speed up the research in this area.
Sockeye: A Toolkit for Neural Machine Translation
Venue: arXiv cs.CL 2018
Year: 2018

We describe Sockeye (version 1.12), an open-source sequence-to-sequence toolkit for Neural Machine Translation (NMT). Sockeye is a production-ready framework for training and applying models as well as an experimental platform for researchers. Written in Python and built on MXNet, the toolkit offers scalable training and inference for the three most prominent encoder-decoder architectures: attentional recurrent neural networks, self-attentional transformers, and fully convolutional networks. Sockeye also supports a wide range of optimizers, normalization and regularization techniques, and inference improvements from current NMT literature. Users can easily run standard training recipes, explore different model settings, and incorporate new ideas. In this paper, we highlight Sockeye's features and benchmark it against other NMT toolkits on two language arcs from the 2017 Conference on Machine Translation (WMT): English-German and Latvian-English. We report competitive BLEU scores across all three architectures, including an overall best score for Sockeye's transformer implementation. To facilitate further comparison, we release all system outputs and training scripts used in our experiments. The Sockeye toolkit is free software released under the Apache 2.0 license.
Network Intell: Enabling the Non-Expert Analysis of Large Volumes of Intercepted Network Traffic
Venue: arXiv cs.CR 2018
Year: 2018

In criminal investigations, telecommunication wiretaps have become a common technique used by law enforcement. While phone-based wiretapping is well documented and the procedure for their execution are well known, the same cannot be said for Internet taps. Lawfully intercepted network traffic often contains a lot of encrypted traffic making it increasingly difficult to find useful information inside the traffic captured. The advent of Internet-of-Things further complicates the process for non-technical investigators. The current level of complexity of intercepted network traffic is close to a point where data cannot be analysed without supervision of a digital investigator with advanced network knowledge. Current investigations focus on analysing all traffic in a chronological manner and are predominately conducted on the data contents of the intercepted traffic. This approach often becomes overly arduous when the amount of data to be analysed becomes very large. In this paper, we propose a novel approach to analyse large amounts of intercepted network traffic based on network metadata. Our approach significantly reduces the duration of the analysis and also produces an insight view of analysing results for the non-technical investigator. We also test our approach with a large sample of network traffic data.
The View from the Other Side: The Border Between Controversial Speech and Harassment on Kotaku in Action
Venue: arXiv cs.OH 2018
Year: 2018

In this paper, we use mixed methods to study a controversial Internet site: The Kotaku in Action (KiA) subreddit. Members of KiA are part of GamerGate, a distributed social movement. We present an emic account of what takes place on KiA who are they, what are their goals and beliefs, and what rules do they follow. Members of GamerGate in general and KiA in particular have often been accused of harassment. However, KiA site policies explicitly prohibit such behavior, and members insist that they have been falsely accused. Underlying the controversy over whether KiA supports harassment is a complex disagreement about what "harassment" is, and where to draw the line between freedom of expression and censorship. We propose a model that characterizes perceptions of controversial speech, dividing it into four categories: criticism, insult, public shaming, and harassment. We also discuss design solutions that address the challenges of moderating harassment without impinging on free speech, and communicating across different ideologies.
Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning
Venue: arXiv cs.NE 2018
Year: 2018

Deep artificial neural networks (DNNs) are typically trained via gradient-based learning algorithms, namely backpropagation. Evolution strategies (ES) can rival backprop-based algorithms such as Q-learning and policy gradients on challenging deep reinforcement learning (RL) problems. However, ES can be considered a gradient-based algorithm because it performs stochastic gradient descent via an operation similar to a finite-difference approximation of the gradient. That raises the question of whether non-gradient-based evolutionary algorithms can work at DNN scales. Here we demonstrate they can: we evolve the weights of a DNN with a simple, gradient-free, population-based genetic algorithm (GA) and it performs well on hard deep RL problems, including Atari and humanoid locomotion. The Deep GA successfully evolves networks with over four million free parameters, the largest neural networks ever evolved with a traditional evolutionary algorithm. These results (1) expand our sense of the scale at which GAs can operate, (2) suggest intriguingly that in some cases following the gradient is not the best choice for optimizing performance, and (3) make immediately available the multitude of neuroevolution techniques that improve performance. We demonstrate the latter by showing that combining DNNs with novelty search, which encourages exploration on tasks with deceptive or sparse reward functions, can solve a high-dimensional problem on which reward-maximizing algorithms (e.g.\ DQN, A3C, ES, and the GA) fail. Additionally, the Deep GA is faster than ES, A3C, and DQN (it can train Atari in ${\raise.17ex\hbox{$\scriptstyle\sim$}}$4 hours on one desktop or ${\raise.17ex\hbox{$\scriptstyle\sim$}}$1 hour distributed on 720 cores), and enables a state-of-the-art, up to 10,000-fold compact encoding technique.
An Experimental Evaluation of a Bounded Expansion Algorithmic Pipeline
Venue: arXiv cs.DS 2018
Year: 2018

Previous work has suggested that the structural restrictions of graphs from classes of bounded expansion--locally dense pockets in a globally sparse graph--naturally coincide with common properties of real-world networks such as clustering and heavy-tailed degree distributions. As such, fixed-parameter tractable algorithms for bounded expansion classes may offer a promising framework for network analysis where other approaches have struggled to scale. However, there has been little work done in implementing and evaluating the performance of these structure-based algorithms. To this end we introduce CONCUSS, a proof-of-concept implementation of a generic algorithmic pipeline for classes of bounded expansion. In particular, we focus on using CONCUSS for subgraph isomorphism counting (also called motif or graphlet counting), which has been used extensively as a tool for analyzing biological and social networks. Through a broad set of experiments we first evaluate the interactions between implementation/engineering choices at multiple stages of the pipeline and their effects on overall run time. From there, we establish viability of the bounded expansion framework by demonstrating that in some scenarios CONCUSS achieves run times competitive with a popular algorithm for subgraph isomorphism counting that does not exploit graph structure. Finally, we empirically identify two particular ways in which future theoretical advances could alleviate bottlenecks in the algorithmic pipeline.
No truthful mechanism can be better than $n$ approximate for two natural problems
Venue: arXiv cs.GT 2018
Year: 2018

This work gives the first natural non-utilitarian problems for which the trivial $n$ approximation via VCG mechanisms is the best possible. That is, no truthful mechanism can be better than $n$ approximate, where $n$ is the number of agents. The problems are the min-max variant of shortest path and (directed) minimum spanning tree mechanism design problems. In these procurement auctions, agents own the edges of a network, and the corresponding edge costs are private. Instead of the total weight of the subnetwork, in the min-max variant we aim to minimize the maximum agent cost.