OpenRaiser/Intern-Atlas huggingface dataset:
Patterns and Rewrite Rules for Systematic Code Generation (From High-Level Functional Patterns to High-Performance OpenCL Code)
Venue: arXiv cs.DC 2015
Year: 2015

Computing systems have become increasingly complex with the emergence of heterogeneous hardware combining multicore CPUs and GPUs. These parallel systems exhibit tremendous computational power at the cost of increased programming effort. This results in a tension between achieving performance and code portability. Code is either tuned using device-specific optimizations to achieve maximum performance or is written in a high-level language to achieve portability at the expense of performance. We propose a novel approach that offers high-level programming, code portability and high-performance. It is based on algorithmic pattern composition coupled with a powerful, yet simple, set of rewrite rules. This enables systematic transformation and optimization of a high-level program into a low-level hardware specific representation which leads to high performance code. We test our design in practice by describing a subset of the OpenCL programming model with low-level patterns and by implementing a compiler which generates high performance OpenCL code. Our experiments show that we can systematically derive high-performance device-specific implementations from simple high-level algorithmic expressions. The performance of the generated OpenCL code is on par with highly tuned implementations for multicore CPUs and GPUs written by experts
A behavioural approach to obstacle avoidance for mobile manipulators based on distributed sensing
Venue: arXiv cs.RO 2015
Year: 2015

A reactive obstacle avoidance method for mobile manipulators is presented. The objectives of the developed algorithm are twofold. The first one is to find a trajectory in the configuration space of a mobile manipulator so as to follow a given trajectory in the task space. The second objective consists in locally adjusting the trajectory in the configuration space in order to avoid collisions with potentially moving obstacles and self-collisions in unstructured and dynamic environments. The perception is exclusively based on a set of proximity sensors distributed on the robot mechanical structure and visual information are not required. Thanks to the adoption of this kind of proximity distributed perception, the approach does not require a 3D model of the robot and allows the real-time collision avoidance without the need of a sensorized environment. To achieve the features cited above, a behaviour-based technique known as Null-Space-Based (NSB) approach has been adopted with some modifications.On one hand, the concept of a total pseudo-energy based on the information from the distributed sensors has been introduced. On the other hand, a method to combine different tasks has been proposed to guarantee the smoothness of the realtime trajectory adjustments. Another significant feature of the method is the strict coordination between the base and the arm exploiting the redundant degrees of freedom, that is a relevant topic in mobile manipulation.
Efficient batchwise dropout training using submatrices
Venue: arXiv cs.NE 2015
Year: 2015

Dropout is a popular technique for regularizing artificial neural networks. Dropout networks are generally trained by minibatch gradient descent with a dropout mask turning off some of the units---a different pattern of dropout is applied to every sample in the minibatch. We explore a very simple alternative to the dropout mask. Instead of masking dropped out units by setting them to zero, we perform matrix multiplication using a submatrix of the weight matrix---unneeded hidden units are never calculated. Performing dropout batchwise, so that one pattern of dropout is used for each sample in a minibatch, we can substantially reduce training times. Batchwise dropout can be used with fully-connected and convolutional neural networks.
Bandwidth Efficient and Rate-Matched Low-Density Parity-Check Coded Modulation
Venue: arXiv cs.IT 2015
Year: 2015

A new coded modulation scheme is proposed. At the transmitter, the concatenation of a distribution matcher and a systematic binary encoder performs probabilistic signal shaping and channel coding. At the receiver, the output of a bitwise demapper is fed to a binary decoder. No iterative demapping is performed. Rate adaption is achieved by adjusting the input distribution and the transmission power. The scheme is applied to bipolar amplitude shift keying (ASK) constellations with equidistant signal points and it is directly applicable to two-dimensional quadrature amplitude modulation (QAM). The scheme is implemented by using the DVB-S2 low-density parity-check (LDPC) codes. At a frame error rate of 1e-3, the new scheme operates within less than 1 dB of the AWGN capacity 0.5log2(1+SNR) at any spectral efficiency between 1 and 5 bits/s/Hz by using only 5 modes, i.e., 4-ASK with code rate 2/3, 8-ASK with 3/4, 16-ASK and 32-ASK with 5/6 and 64-ASK with 9/10.
A TDOA technique with Super-Resolution based on the Volume Cross-Correlation Function
Venue: arXiv cs.IT 2015
Year: 2015

Time Difference of Arrival (TDOA) is widely used in wireless localization systems. Among the enormous approaches of TDOA, high resolution TDOA algorithms have drawn much attention for its ability to resolve closely spaced signal delays in multipath environment. However, the state-of-art high resolution TDOA algorithms still have performance weakness on resolving time delays in a wireless channel with dense multipath effect, as well as difficulties in implementation for their high computation complexity. In this paper, we propose a novel TDOA algorithm with super resolution based on a multi-dimensional cross-correlation function: the Volume Cross-Correlation Function (VCC). The proposed TDOA algorithm has excellent time resolution capability in multipath environment, and it also has a much lower computational complexity. Because our algorithm does not require priori knowledge about the waveform or power spectrum of transmitted signals, it has great potential of usage in various passive wireless localization systems. Numerical simulations is also provided to demonstrate the validity of our conclusion.
Gaussian Process Models for HRTF based Sound-Source Localization and Active-Learning
Venue: arXiv cs.SD 2015
Year: 2015

From a machine learning perspective, the human ability localize sounds can be modeled as a non-parametric and non-linear regression problem between binaural spectral features of sound received at the ears (input) and their sound-source directions (output). The input features can be summarized in terms of the individual's head-related transfer functions (HRTFs) which measure the spectral response between the listener's eardrum and an external point in $3$D. Based on these viewpoints, two related problems are considered: how can one achieve an optimal sampling of measurements for training sound-source localization (SSL) models, and how can SSL models be used to infer the subject's HRTFs in listening tests. First, we develop a class of binaural SSL models based on Gaussian process regression and solve a \emph{forward selection} problem that finds a subset of input-output samples that best generalize to all SSL directions. Second, we use an \emph{active-learning} approach that updates an online SSL model for inferring the subject's SSL errors via headphones and a graphical user interface. Experiments show that only a small fraction of HRTFs are required for $5^{\circ}$ localization accuracy and that the learned HRTFs are localized closer to their intended directions than non-individualized HRTFs.
Simulation in the Call-by-Need Lambda-Calculus with Letrec, Case, Constructors, and Seq
Venue: arXiv cs.LO 2015
Year: 2015

This paper shows equivalence of several versions of applicative similarity and contextual approximation, and hence also of applicative bisimilarity and contextual equivalence, in LR, the deterministic call-by-need lambda calculus with letrec extended by data constructors, case-expressions and Haskell's seq-operator. LR models an untyped version of the core language of Haskell. The use of bisimilarities simplifies equivalence proofs in calculi and opens a way for more convenient correctness proofs for program transformations. The proof is by a fully abstract and surjective transfer into a call-by-name calculus, which is an extension of Abramsky's lazy lambda calculus. In the latter calculus equivalence of our similarities and contextual approximation can be shown by Howe's method. Similarity is transferred back to LR on the basis of an inductively defined similarity. The translation from the call-by-need letrec calculus into the extended call-by-name lambda calculus is the composition of two translations. The first translation replaces the call-by-need strategy by a call-by-name strategy and its correctness is shown by exploiting infinite trees which emerge by unfolding the letrec expressions. The second translation encodes letrec-expressions by using multi-fixpoint combinators and its correctness is shown syntactically by comparing reductions of both calculi. A further result of this paper is an isomorphism between the mentioned calculi, which is also an identity on letrec-free expressions.
A Scalable, Linear-Time Dynamic Cutoff Algorithm for Molecular Simulations of Interfacial Systems
Venue: arXiv cs.DC 2015
Year: 2015

This master thesis introduces the idea of dynamic cutoffs in molecular dynamics simulations, based on the distance between particles and the interface, and presents a solution for detecting interfaces in real-time. Our dynamic cutoff method (DCM) exhibits a linear-time complexity as well as nearly ideal weak and strong scaling. The DCM is tailored for massively parallel architectures and for large interfacial systems with millions of particles. We implemented the DCM as part of the LAMMPS open-source molecular dynamics package and demonstrate the nearly ideal weak- and strong-scaling behavior of this method on an IBM BlueGene/Q supercomputer. Our results for a liquid/vapor system consisting of Lennard-Jones particles show that the accuracy of DCM is comparable to that of the traditional particle-particle particle- mesh (PPPM) algorithm. The performance comparison indicates that DCM is preferable for large systems due to the limited scaling of FFTs within the PPPM algorithm. Moreover, the DCM requires the interface to be identified every other MD timestep. As a consequence, this thesis also presents an interface detection method which is (1) applicable in real time; (2) parallelizable; and (3) scales linearly with respect to the number of particles.
DAG-width and circumference of digraphs
Venue: arXiv cs.DM 2015
Year: 2015

We prove that every digraph of circumference $l$ has DAG-width at most $l$ and this is best possible. As a consequence of our result we deduce that the $k$-linkage problem is polynomially solvable for every fixed $k$ in the class of digraphs with bounded circumference. This answers a question posed in \cite{bangTCS562}. We also prove that the weak $k$-linkage problem (where we ask for arc-disjoint paths) is polynomially solvable for every fixed $k$ in the class of digraphs with circumference 2 as well as for digraphs with a bounded number of disjoint cycles each of length at least 3. The case of bounded circumference digraphs is open. Finally we prove that the minimum spanning strong subdigraph problem is NP-hard on digraphs of DAG-width at most 5.
FEEBO: An Empirical Evaluation Framework for Malware Behavior Obfuscation
Venue: arXiv cs.CR 2015
Year: 2015

Program obfuscation is increasingly popular among malware creators. Objectively comparing different malware detection approaches with respect to their resilience against obfuscation is challenging. To the best of our knowledge, there is no common empirical framework for evaluating the resilience of malware detection approaches w.r.t. behavior obfuscation. We propose and implement such a framework that obfuscates the observable behavior of malware binaries. To assess the framework's utility, we use it to obfuscate known malware binaries and then investigate the impact on detection effectiveness of different $n$-gram based detection approaches. We find that the obfuscation transformations employed by our framework significantly affect the precision of such detection approaches. Several $n$-gram-based approaches can hence be concluded not to be resilient against this simple kind of obfuscation.
The Hardness of Approximation of Euclidean k-means
Venue: arXiv cs.CC 2015
Year: 2015

The Euclidean $k$-means problem is a classical problem that has been extensively studied in the theoretical computer science, machine learning and the computational geometry communities. In this problem, we are given a set of $n$ points in Euclidean space $R^d$, and the goal is to choose $k$ centers in $R^d$ so that the sum of squared distances of each point to its nearest center is minimized. The best approximation algorithms for this problem include a polynomial time constant factor approximation for general $k$ and a $(1+ε)$-approximation which runs in time $poly(n) 2^{O(k/ε)}$. At the other extreme, the only known computational complexity result for this problem is NP-hardness [ADHP'09]. The main difficulty in obtaining hardness results stems from the Euclidean nature of the problem, and the fact that any point in $R^d$ can be a potential center. This gap in understanding left open the intriguing possibility that the problem might admit a PTAS for all $k,d$. In this paper we provide the first hardness of approximation for the Euclidean $k$-means problem. Concretely, we show that there exists a constant $ε> 0$ such that it is NP-hard to approximate the $k$-means objective to within a factor of $(1+ε)$. We show this via an efficient reduction from the vertex cover problem on triangle-free graphs: given a triangle-free graph, the goal is to choose the fewest number of vertices which are incident on all the edges. Additionally, we give a proof that the current best hardness results for vertex cover can be carried over to triangle-free graphs. To show this we transform $G$, a known hard vertex cover instance, by taking a graph product with a suitably chosen graph $H$, and showing that the size of the (normalized) maximum independent set is almost exactly preserved in the product graph using a spectral analysis, which might be of independent interest.
Locating a Tree in a Phylogenetic Network in Quadratic Time
Venue: arXiv cs.DS 2015
Year: 2015

A fundamental problem in the study of phylogenetic networks is to determine whether or not a given phylogenetic network contains a given phylogenetic tree. We develop a quadratic-time algorithm for this problem for binary nearly-stable phylogenetic networks. We also show that the number of reticulations in a reticulation visible or nearly stable phylogenetic network is bounded from above by a function linear in the number of taxa.
On the Potential of Bluetooth Low Energy Technology for Vehicular Applications
Venue: arXiv cs.NI 2015
Year: 2015

With the increasing number of sensors in modern vehicles, using an Intra-Vehicular Wireless Sensor Network (IVWSN) is a possible solution for the automotive industry to address the potential issues that arise from additional wiring harness. Such a solution could help car manufacturers develop vehicles that have better fuel economy and performance, in addition to supporting new applications. However, which wireless technology for IVWSNs should be used for maximizing the aforementioned benefits is still an open issue. In this paper, we propose to use a new wireless technology known as Bluetooth Low Energy (BLE) and highlight a new architecture for IVWSN. Based on a comprehensive study which encompasses an example application, it is shown that BLE is an excellent option that can be used in IVWSNs for certain applications mainly due to its good performance and low-power, low-complexity, and low-cost attributes.
A State Estimation and Malicious Attack Game in Multi-Sensor Dynamic Systems
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, the problem of false information injection attack and defense on state estimation in dynamic multi-sensor systems is investigated from a game theoretic perspective. The relationship between the Kalman filter and the adversary can be regarded as a two-person zero-sum game. Under which condition both sides of the game will reach the Nash equilibrium is investigated in the paper. The multi-sensor Kalman filter system and the adversary are supposed to be rational players. The Kalman filter and the adversary have to choose their respective subsets of sensors to perform system state estimation and false information injection. It is shown how both sides pick their strategies in order to gain more and lose less. The optimal solutions are achieved by solving the minimax problem. Numerical results are also provided in order to illustrate the effectiveness of the derived optimal strategies.
Convergence of gradient based pre-training in Denoising autoencoders
Venue: arXiv cs.LG 2015
Year: 2015

The success of deep architectures is at least in part attributed to the layer-by-layer unsupervised pre-training that initializes the network. Various papers have reported extensive empirical analysis focusing on the design and implementation of good pre-training procedures. However, an understanding pertaining to the consistency of parameter estimates, the convergence of learning procedures and the sample size estimates is still unavailable in the literature. In this work, we study pre-training in classical and distributed denoising autoencoders with these goals in mind. We show that the gradient converges at the rate of $\frac{1}{\sqrt{N}}$ and has a sub-linear dependence on the size of the autoencoder network. In a distributed setting where disjoint sections of the whole network are pre-trained synchronously, we show that the convergence improves by at least $τ^{3/4}$, where $τ$ corresponds to the size of the sections. We provide a broad set of experiments to empirically evaluate the suggested behavior.
Evaluating Matrix Circuits
Venue: arXiv cs.CC 2015
Year: 2015

The circuit evaluation problem (also known as the compressed word problem) for finitely generated linear groups is studied. The best upper bound for this problem is $\mathsf{coRP}$, which is shown by a reduction to polynomial identity testing. Conversely, the compressed word problem for the linear group $\mathsf{SL}_3(\mathbb{Z})$ is equivalent to polynomial identity testing. In the paper, it is shown that the compressed word problem for every finitely generated nilpotent group is in $\mathsf{DET} \subseteq \mathsf{NC}^2$. Within the larger class of polycyclic groups we find examples where the compressed word problem is at least as hard as polynomial identity testing for skew arithmetic circuits.
Primal Dual Affine Scaling on GPUs
Venue: arXiv cs.NA 2015
Year: 2015

Here we present an implementation of Primal-Dual Affine scaling method to solve linear optimization problem on GPU based systems. Strategies to convert the system generated by complementary slackness theorem into a symmetric system are given. A new CUDA friendly technique to solve the resulting symmetric positive definite subsystem is also developed. Various strategies to reduce the memory transfer and storage requirements were also explored.
A New DNA-Based Approach of Generating Key-dependent ShiftRows Transformation
Venue: arXiv cs.CR 2015
Year: 2015

The use of key-dependent shiftRows can be considered as one of the applied methods for altering the quality of a cryptographic algorithm. This article describes one approach for changing the ShiftRows transformation employed in the algorithm AES. The approach employs methods inspired from DNA processes and structure which depended on the key while the parameters of the created new ShiftRows have characteristics identical to those of the original algorithm AES in addition to increase its resistance against attacks. The proposed new ShiftRows were tested for coefficient correlation for dynamic and static independence between the input and output. The NIST Test Suite tests were used to test the randomness for the block cipher that used the new transformation.
Automata and rational expressions
Venue: arXiv cs.FL 2015
Year: 2015

This text is an extended version of the chapter 'Automata and rational expressions' in the AutoMathA Handbook that will appear soon, published by the European Science Foundation and edited by JeanEricPin.
Towards zero-configuration condition monitoring based on dictionary learning
Venue: arXiv cs.CV 2015
Year: 2015

Condition-based predictive maintenance can significantly improve overall equipment effectiveness provided that appropriate monitoring methods are used. Online condition monitoring systems are customized to each type of machine and need to be reconfigured when conditions change, which is costly and requires expert knowledge. Basic feature extraction methods limited to signal distribution functions and spectra are commonly used, making it difficult to automatically analyze and compare machine conditions. In this paper, we investigate the possibility to automate the condition monitoring process by continuously learning a dictionary of optimized shift-invariant feature vectors using a well-known sparse approximation method. We study how the feature vectors learned from a vibration signal evolve over time when a fault develops within a ball bearing of a rotating machine. We quantify the adaptation rate of learned features and find that this quantity changes significantly in the transitions between normal and faulty states of operation of the ball bearing.
A Predictive System for detection of Bankruptcy using Machine Learning techniques
Venue: arXiv cs.LG 2015
Year: 2015

Bankruptcy is a legal procedure that claims a person or organization as a debtor. It is essential to ascertain the risk of bankruptcy at initial stages to prevent financial losses. In this perspective, different soft computing techniques can be employed to ascertain bankruptcy. This study proposes a bankruptcy prediction system to categorize the companies based on extent of risk. The prediction system acts as a decision support tool for detection of bankruptcy Keywords: Bankruptcy, soft computing, decision support tool
Numerical simulation of skin transport using Parareal
Venue: arXiv cs.CE 2015
Year: 2015

In-silico investigation of skin permeation is an important but also computationally demanding problem. To resolve all scales involved in full detail will not only require exascale computing capacities but also suitable parallel algorithms. This article investigates the applicability of the time-parallel Parareal algorithm to a brick and mortar setup, a precursory problem to skin permeation. The C++ library Lib4PrM implementing Parareal is combined with the UG4 simulation framework, which provides the spatial discretization and parallelization. The combination's performance is studied with respect to convergence and speedup. It is confirmed that anisotropies in the domain and jumps in diffusion coefficients only have a minor impact on Parareal's convergence. The influence of load imbalances in time due to differences in number of iterations required by the spatial solver as well as spatio-temporal weak scaling is discussed.
A new hybrid metric for verifying parallel corpora of Arabic-English
Venue: arXiv cs.CL 2015
Year: 2015

This paper discusses a new metric that has been applied to verify the quality in translation between sentence pairs in parallel corpora of Arabic-English. This metric combines two techniques, one based on sentence length and the other based on compression code length. Experiments on sample test parallel Arabic-English corpora indicate the combination of these two techniques improves accuracy of the identification of satisfactory and unsatisfactory sentence pairs compared to sentence length and compression code length alone. The new method proposed in this research is effective at filtering noise and reducing mis-translations resulting in greatly improved quality.