OpenRaiser/Intern-Atlas huggingface dataset:
Hydra: a C++11 framework for data analysis in massively parallel platforms
Venue: arXiv cs.MS 2017
Year: 2017

Hydra is a header-only, templated and C++11-compliant framework designed to perform the typical bottleneck calculations found in common HEP data analyses on massively parallel platforms. The framework is implemented on top of the C++11 Standard Library and a variadic version of the Thrust library and is designed to run on Linux systems, using OpenMP, CUDA and TBB enabled devices. This contribution summarizes the main features of Hydra. A basic description of the overall design, functionality and user interface is provided, along with some code examples and measurements of performance.
CSWA: Aggregation-Free Spatial-Temporal Community Sensing
Venue: arXiv cs.LG 2017
Year: 2017

In this paper, we present a novel community sensing paradigm -- {C}ommunity {S}ensing {W}ithout {A}ggregation}. CSWA is designed to obtain the environment information (e.g., air pollution or temperature) in each subarea of the target area, without aggregating sensor and location data collected by community members. CSWA operates on top of a secured peer-to-peer network over the community members and proposes a novel \emph{Decentralized Spatial-Temporal Compressive Sensing} framework based on \emph{Parallelized Stochastic Gradient Descent}. Through learning the \emph{low-rank structure} via distributed optimization, CSWA approximates the value of the sensor data in each subarea (both covered and uncovered) for each sensing cycle using the sensor data locally stored in each member's mobile device. Simulation experiments based on real-world datasets demonstrate that CSWA exhibits low approximation error (i.e., less than $0.2 ^\circ$C in city-wide temperature sensing task and $10$ units of PM2.5 index in urban air pollution sensing) and performs comparably to (sometimes better than) state-of-the-art algorithms based on the data aggregation and centralized computation.
Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models
Venue: arXiv cs.DS 2017
Year: 2017

Motivated by Internet advertising applications, online allocation problems have been studied extensively in various adversarial and stochastic models. While the adversarial arrival models are too pessimistic, many of the stochastic (such as i.i.d or random-order) arrival models do not realistically capture uncertainty in predictions. A significant cause for such uncertainty is the presence of unpredictable traffic spikes, often due to breaking news or similar events. To address this issue, a simultaneous approximation framework has been proposed to develop algorithms that work well both in the adversarial and stochastic models; however, this framework does not enable algorithms that make good use of partially accurate forecasts when making online decisions. In this paper, we propose a robust online stochastic model that captures the nature of traffic spikes in online advertising. In our model, in addition to the stochastic input for which we have good forecasting, an unknown number of impressions arrive that are adversarially chosen. We design algorithms that combine a stochastic algorithm with an online algorithm that adaptively reacts to inaccurate predictions. We provide provable bounds for our new algorithms in this framework. We accompany our positive results with a set of hardness results showing that our algorithms are not far from optimal in this framework. As a byproduct of our results, we also present improved online algorithms for a slight variant of the simultaneous approximation framework.
Hidden Markov Random Field Iterative Closest Point
Venue: arXiv cs.CV 2017
Year: 2017

When registering point clouds resolved from an underlying 2-D pixel structure, such as those resulting from structured light and flash LiDAR sensors, or stereo reconstruction, it is expected that some points in one cloud do not have corresponding points in the other cloud, and that these would occur together, such as along an edge of the depth map. In this work, a hidden Markov random field model is used to capture this prior within the framework of the iterative closest point algorithm. The EM algorithm is used to estimate the distribution parameters and the hidden component memberships. Experiments are presented demonstrating that this method outperforms several other outlier rejection methods when the point clouds have low or moderate overlap.
Budget-Constrained Multi-Armed Bandits with Multiple Plays
Venue: arXiv cs.LG 2017
Year: 2017

We study the multi-armed bandit problem with multiple plays and a budget constraint for both the stochastic and the adversarial setting. At each round, exactly $K$ out of $N$ possible arms have to be played (with $1\leq K \leq N$). In addition to observing the individual rewards for each arm played, the player also learns a vector of costs which has to be covered with an a-priori defined budget $B$. The game ends when the sum of current costs associated with the played arms exceeds the remaining budget. Firstly, we analyze this setting for the stochastic case, for which we assume each arm to have an underlying cost and reward distribution with support $[c_{\min}, 1]$ and $[0, 1]$, respectively. We derive an Upper Confidence Bound (UCB) algorithm which achieves $O(NK^4 \log B)$ regret. Secondly, for the adversarial case in which the entire sequence of rewards and costs is fixed in advance, we derive an upper bound on the regret of order $O(\sqrt{NB\log(N/K)})$ utilizing an extension of the well-known $\texttt{Exp3}$ algorithm. We also provide upper bounds that hold with high probability and a lower bound of order $Ω((1 - K/N)^2 \sqrt{NB/K})$.
A Design-Time/Run-Time Application Mapping Methodology for Predictable Execution Time in MPSoCs
Venue: arXiv cs.DC 2017
Year: 2017

Executing multiple applications on a single MPSoC brings the major challenge of satisfying multiple quality requirements regarding real-time, energy, etc. Hybrid application mapping denotes the combination of design-time analysis with run-time application mapping. In this article, we present such a methodology, which comprises a design space exploration coupled with a formal performance analysis. This results in several resource reservation configurations, optimized for multiple objectives, with verified real-time guarantees for each individual application. The Pareto-optimal configurations are handed over to run-time management which searches for a suitable mapping according to this information. To provide any real-time guarantees, the performance analysis needs to be composable and the influence of the applications on each other has to be bounded. We achieve this either by spatial or a novel temporal isolation for tasks and by exploiting composable NoCs. With the proposed temporal isolation, tasks of different applications can be mapped to the same resource while with spatial isolation, one computing resource can be exclusively used by only one application. The experiments reveal that the success rate in finding feasible application mappings can be increased by the proposed temporal isolation by up to 30% and energy consumption can be reduced compared to spatial isolation.
Beagle: Automated Extraction and Interpretation of Visualizations from the Web
Venue: arXiv cs.HC 2017
Year: 2017

"How common is interactive visualization on the web?" "What is the most popular visualization design?" "How prevalent are pie charts really?" These questions intimate the role of interactive visualization in the real (online) world. In this paper, we present our approach (and findings) to answering these questions. First, we introduce Beagle, which mines the web for SVG-based visualizations and automatically classifies them by type (i.e., bar, pie, etc.). With Beagle, we extract over 41,000 visualizations across five different tools and repositories, and classify them with 86% accuracy, across 24 visualization types. Given this visualization collection, we study usage across tools. We find that most visualizations fall under four types: bar charts, line charts, scatter charts, and geographic maps. Though controversial, pie charts are relatively rare in practice. Our findings also indicate that users may prefer tools that emphasize a succinct set of visualization types, and provide diverse expert visualization examples.
Empirical model for combinatorial data center network switch design
Venue: arXiv cs.NI 2017
Year: 2017

Data centers require high-performance network equipment that consume low power and support high bandwidth requirements. In this context, a combinatorial approach was proposed to design data center network (DCN) equipment from a library of components in \cite{infocom}. This library includes power splitter, wavelength multiplexers, reconfigurable add-drop multiplexers and optical amplifiers. When interconnecting optical components, it must be ensured that the resultant network supports specified target bit-error-rates (typically, at most $10^{-12}$). This paper reports experiment conducted on component interconnections and their computed bit-error-rates. From the experimental analysis, it was observed that the desired objective can be decided by considering a zeroth-order threshold for optical power at the receiver and before the amplifier. This paves way for the theoretical evaluation of several other such designs using this empirically derived model.
Deep Matching Autoencoders
Venue: arXiv cs.CV 2017
Year: 2017

Increasingly many real world tasks involve data in multiple modalities or views. This has motivated the development of many effective algorithms for learning a common latent space to relate multiple domains. However, most existing cross-view learning algorithms assume access to paired data for training. Their applicability is thus limited as the paired data assumption is often violated in practice: many tasks have only a small subset of data available with pairing annotation, or even no paired data at all. In this paper we introduce Deep Matching Autoencoders (DMAE), which learn a common latent space and pairing from unpaired multi-modal data. Specifically we formulate this as a cross-domain representation learning and object matching problem. We simultaneously optimise parameters of representation learning auto-encoders and the pairing of unpaired multi-modal data. This framework elegantly spans the full regime from fully supervised, semi-supervised, and unsupervised (no paired data) multi-modal learning. We show promising results in image captioning, and on a new task that is uniquely enabled by our methodology: unsupervised classifier learning.
Automata in the Category of Glued Vector Spaces
Venue: arXiv cs.FL 2017
Year: 2017

In this paper we adopt a category-theoretic approach to the conception of automata classes enjoying minimization by design. The main instantiation of our construction is a new class of automata that are hybrid between deterministic automata and automata weighted over a field.
The signature of robot action success in EEG signals of a human observer: Decoding and visualization using deep convolutional neural networks
Venue: arXiv cs.HC 2017
Year: 2017

The importance of robotic assistive devices grows in our work and everyday life. Cooperative scenarios involving both robots and humans require safe human-robot interaction. One important aspect here is the management of robot errors, including fast and accurate online robot-error detection and correction. Analysis of brain signals from a human interacting with a robot may help identifying robot errors, but accuracies of such analyses have still substantial space for improvement. In this paper we evaluate whether a novel framework based on deep convolutional neural networks (deep ConvNets) could improve the accuracy of decoding robot errors from the EEG of a human observer, both during an object grasping and a pouring task. We show that deep ConvNets reached significantly higher accuracies than both regularized Linear Discriminant Analysis (rLDA) and filter bank common spatial patterns (FB-CSP) combined with rLDA, both widely used EEG classifiers. Deep ConvNets reached mean accuracies of 75% +/- 9 %, rLDA 65% +/- 10% and FB-CSP + rLDA 63% +/- 6% for decoding of erroneous vs. correct trials. Visualization of the time-domain EEG features learned by the ConvNets to decode errors revealed spatiotemporal patterns that reflected differences between the two experimental paradigms. Across subjects, ConvNet decoding accuracies were significantly correlated with those obtained with rLDA, but not CSP, indicating that in the present context ConvNets behaved more 'rLDA-like' (but consistently better), while in a previous decoding study with another task but the same ConvNet architecture, it was found to behave more 'CSP-like'. Our findings thus provide further support for the assumption that deep ConvNets are a versatile addition to the existing toolbox of EEG decoding techniques, and we discuss steps how ConvNet EEG decoding performance could be further optimized.
Physical Layer Authentication for Mission Critical Machine Type Communication using Gaussian Mixture Model based Clustering
Venue: arXiv cs.NI 2017
Year: 2017

The application of Mission Critical Machine Type Communication (MC-MTC) in wireless systems is currently a hot research topic. Wireless systems are considered to provide numerous advantages over wired systems in e.g. industrial applications such as closed loop control. However, due to the broadcast nature of the wireless channel, such systems are prone to a wide range of cyber attacks. These range from passive eavesdropping attacks to active attacks like data manipulation or masquerade attacks. Therefore it is necessary to provide reliable and efficient security mechanisms. Some of the most important security issues in such a system are to ensure integrity as well as authenticity of exchanged messages over the air between communicating devices. In the present work, an approach on how to achieve this goal in MC-MTC systems based on Physical Layer Security (PHYSEC) is presented. A new method that clusters channel estimates of different transmitters based on a Gaussian Mixture Model is applied for that purpose. Further, an experimental proof-of-concept evaluation is given and we compare the performance of our approach with a mean square error based detection method.
An introduction to approximate computing
Venue: arXiv cs.PL 2017
Year: 2017

Approximate computing is a research area where we investigate a wide spectrum of techniques to trade off computation accuracy for better performance or energy consumption. In this work, we provide a general introduction to approximate computing. Also, we propose a taxonomy to make it easier to discuss the merits of different approximation techniques. Our taxonomy emphasizes the expected cost of tackling approximate computing across the entire system stack. We conclude by discussing the unique opportunities as well as challenges of nondeterministic approximate computing.
Joint Power Control and Beamforming for Uplink Non-Orthogonal Multiple Access in 5G Millimeter-Wave Communications
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we investigate the combination of two key enabling technologies for the fifth generation (5G) wireless mobile communication, namely millimeter-wave (mmWave) communications and non-orthogonal multiple access (NOMA). In particular, we consider a typical 2-user uplink mmWave-NOMA system, where the base station (BS) equips an analog beamforming structure with a single RF chain and serves 2 NOMA users. An optimization problem is formulated to maximize the achievable sum rate of the 2 users while ensuring a minimal rate constraint for each user. The problem turns to be a joint power control and beamforming problem, i.e., we need to find the beamforming vectors to steer to the two users simultaneously subject to an analog beamforming structure, and meanwhile control appropriate power on them. As direct search for the optimal solution of the non-convex problem is too complicated, we propose to decompose the original problem into two sub-problems that are relatively easy to solve: one is a power control and beam gain allocation problem, and the other is an analog beamforming problem under a constant-modulus constraint. The rational of the proposed solution is verified by extensive simulations, and the performance evaluation results show that the proposed sub-optimal solution achieve a close-to-bound uplink sum-rate performance.
SparCE: Sparsity aware General Purpose Core Extensions to Accelerate Deep Neural Networks
Venue: arXiv cs.DC 2017
Year: 2017

Deep Neural Networks (DNNs) have emerged as the method of choice for solving a wide range of machine learning tasks. The enormous computational demands posed by DNNs have most commonly been addressed through the design of custom accelerators. However, these accelerators are prohibitive in many design scenarios (e.g., wearable devices and IoT sensors), due to stringent area/cost constraints. Accelerating DNNs on these low-power systems, comprising of mainly the general-purpose processor (GPP) cores, requires new approaches. We improve the performance of DNNs on GPPs by exploiting a key attribute of DNNs, i.e., sparsity. We propose Sparsity aware Core Extensions (SparCE)- a set of micro-architectural and ISA extensions that leverage sparsity and are minimally intrusive and low-overhead. We dynamically detect zero operands and skip a set of future instructions that use it. Our design ensures that the instructions to be skipped are prevented from even being fetched, as squashing instructions comes with a penalty. SparCE consists of 2 key micro-architectural enhancements- a Sparsity Register File (SpRF) that tracks zero registers and a Sparsity aware Skip Address (SASA) table that indicates instructions to be skipped. When an instruction is fetched, SparCE dynamically pre-identifies whether the following instruction(s) can be skipped and appropriately modifies the program counter, thereby skipping the redundant instructions and improving performance. We model SparCE using the gem5 architectural simulator, and evaluate our approach on 6 image-recognition DNNs in the context of both training and inference using the Caffe framework. On a scalar microprocessor, SparCE achieves 19%-31% reduction in application-level. We also evaluate SparCE on a 4-way SIMD ARMv8 processor using the OpenBLAS library, and demonstrate that SparCE achieves 8%-15% reduction in the application-level execution time.
Generation of unstructured meshes in 2-D, 3-D, and spherical geometries with embedded high resolution sub-regions
Venue: arXiv cs.CG 2017
Year: 2017

We present 2-D, 3-D, and spherical mesh generators for the Finite Element Method (FEM) using triangular and tetrahedral elements. The mesh nodes are treated as if they were linked by virtual springs that obey Hooke's law. Given the desired length for the springs, the FEM is used to solve for the optimal nodal positions for the static equilibrium of this spring system. A 'guide-mesh' approach allows the user to create embedded high resolution sub-regions within a coarser mesh. The method converges rapidly. For example, in 3-D, the algorithm is able to refine a specific region within an unstructured tetrahedral spherical shell so that the edge-length factor $l_{0r}/l_{0c} = 1/33$ within a few iterations, where $l_{0r}$ and $l_{0c}$ are the desired spring length for elements inside the refined and coarse regions respectively. One use for this type of mesh is to model regional problems as a fine region within a global mesh that has no fictitious boundaries, at only a small additional computational cost. The algorithm also includes routines to locally improve the quality of the mesh and to avoid badly shaped 'slivers-like' tetrahedra.
Towards Deep Learning Models for Psychological State Prediction using Smartphone Data: Challenges and Opportunities
Venue: arXiv cs.LG 2017
Year: 2017

There is an increasing interest in exploiting mobile sensing technologies and machine learning techniques for mental health monitoring and intervention. Researchers have effectively used contextual information, such as mobility, communication and mobile phone usage patterns for quantifying individuals' mood and wellbeing. In this paper, we investigate the effectiveness of neural network models for predicting users' level of stress by using the location information collected by smartphones. We characterize the mobility patterns of individuals using the GPS metrics presented in the literature and employ these metrics as input to the network. We evaluate our approach on the open-source StudentLife dataset. Moreover, we discuss the challenges and trade-offs involved in building machine learning models for digital mental health and highlight potential future work in this direction.
Dimensionality Reduction on Grassmannian via Riemannian Optimization: A Generalized Perspective
Venue: arXiv cs.CV 2017
Year: 2017

This paper proposes a generalized framework with joint normalization which learns lower-dimensional subspaces with maximum discriminative power by making use of the Riemannian geometry. In particular, we model the similarity/dissimilarity between subspaces using various metrics defined on Grassmannian and formulate dimen-sionality reduction as a non-linear constraint optimization problem considering the orthogonalization. To obtain the linear mapping, we derive the components required to per-form Riemannian optimization (e.g., Riemannian conju-gate gradient) from the original Grassmannian through an orthonormal projection. We respect the Riemannian ge-ometry of the Grassmann manifold and search for this projection directly from one Grassmann manifold to an-other face-to-face without any additional transformations. In this natural geometry-aware way, any metric on the Grassmann manifold can be resided in our model theoreti-cally. We have combined five metrics with our model and the learning process can be treated as an unconstrained optimization problem on a Grassmann manifold. Exper-iments on several datasets demonstrate that our approach leads to a significant accuracy gain over state-of-the-art methods.
An $O^*(1.84^k)$ Parameterized Algorithm for the Multiterminal Cut Problem
Venue: arXiv cs.DS 2017
Year: 2017

We study the \emph{multiterminal cut} problem, which, given an $n$-vertex graph whose edges are integer-weighted and a set of terminals, asks for a partition of the vertex set such that each terminal is in a distinct part, and the total weight of crossing edges is at most $k$. Our weapons shall be two classical results known for decades: \emph{maximum volume minimum ($s,t$)-cuts} by [Ford and Fulkerson, \emph{Flows in Networks}, 1962] and \emph{isolating cuts} by [Dahlhaus et al., \emph{SIAM J. Comp.} 23(4):864-894, 1994]. We sharpen these old weapons with the help of submodular functions, and apply them to this problem, which enable us to design a more elaborated branching scheme on deciding whether a non-terminal vertex is with a terminal or not. This bounded search tree algorithm can be shown to run in $1.84^k\cdot n^{O(1)}$ time, thereby breaking the $2^k\cdot n^{O(1)}$ barrier. As a by-product, it gives a $1.36^k\cdot n^{O(1)}$ time algorithm for $3$-terminal cut. The preprocessing applied on non-terminal vertices might be of use for study of this problem from other aspects.