OpenRaiser/Intern-Atlas huggingface dataset:
Myrmics: Scalable, Dependency-aware Task Scheduling on Heterogeneous Manycores
Venue: arXiv cs.DC 2016
Year: 2016

Task-based programming models have become very popular, as they offer an attractive solution to parallelize serial application code with task and data annotations. They usually depend on a runtime system that schedules the tasks to multiple cores in parallel while resolving any data hazards. However, existing runtime system implementations are not ready to scale well on emerging manycore processors, as they often rely on centralized structures and/or locks on shared structures in a cache-coherent memory. We propose design choices, policies and mechanisms to enhance runtime system scalability for single-chip processors with hundreds of cores. Based on these concepts, we create and evaluate Myrmics, a runtime system for a dependency-aware, task-based programming model on a heterogeneous hardware prototype platform that emulates a single-chip processor of 8 latency-optimized and 512 throughput-optimized CPUs. We find that Myrmics scales successfully to hundreds of cores. Compared to MPI versions of the same benchmarks with hand-tuned message passing, Myrmics achieves similar scalability with a 10-30% performance overhead, but with less programming effort. We analyze the scalability of the runtime system in detail and identify the key factors that contribute to it.
Modeling and Analysis of SCMA Enhanced D2D and Cellular Hybrid Network
Venue: arXiv cs.IT 2016
Year: 2016

Sparse code multiple access (SCMA) has been recently proposed for the future wireless networks, which allows non-orthogonal spectrum resource sharing and enables system overloading. In this paper, we apply SCMA into device-to-device (D2D) communication and cellular hybrid network, targeting at using the overload feature of SCMA to support massive device connectivity and expand network capacity. Particularly, we develop a stochastic geometry based framework to model and analyze SCMA, considering underlaid and overlaid mode. Based on the results, we analytically compare SCMA with orthogonal frequency-division multiple access (OFDMA) using area spectral efficiency (ASE) and quantify closed-form ASE gain of SCMA over OFDMA. Notably, it is shown that system ASE can be significantly improved using SCMA and the ASE gain scales linearly with the SCMA codeword dimension. Besides, we endow D2D users with an activated probability to balance cross-tier interference in the underlaid mode and derive the optimal activated probability. Meanwhile, we study resource allocation in the overlaid mode and obtain the optimal codebook allocation rule. It is interestingly found that the optimal SCMA codebook allocation rule is independent of cellular network parameters when cellular users are densely deployed. The results are helpful in the implementation of SCMA in the hybrid system.
Partitioning sparse graphs into an independent set and a forest of bounded degree
Venue: arXiv cs.DM 2016
Year: 2016

An $({\cal I},{\cal F}_d)$-partition of a graph is a partition of the vertices of the graph into two sets $I$ and $F$, such that $I$ is an independent set and $F$ induces a forest of maximum degree at most $d$. We show that for all $M<3$ and $d \ge \frac{2}{3-M} - 2$, if a graph has maximum average degree less than $M$, then it has an $({\cal I},{\cal F}_d)$-partition. Additionally, we prove that for all $\frac{8}{3} \le M < 3$ and $d \ge \frac{1}{3-M}$, if a graph has maximum average degree less than $M$ then it has an $({\cal I},{\cal F}_d)$-partition.
Relating Strong Spatial Cognition to Symbolic Problem Solving --- An Example
Venue: arXiv cs.AI 2016
Year: 2016

In this note, we discuss and analyse a shortest path finding approach using strong spatial cognition. It is compared with a symbolic graph-based algorithm and it is shown that both approaches are similar with respect to structure and complexity. Nevertheless, the strong spatial cognition solution is easy to understand and even pops up immediately when one has to solve the problem.
Multiple Human Tracking in RGB-D Data: A Survey
Venue: arXiv cs.CV 2016
Year: 2016

Multiple human tracking (MHT) is a fundamental task in many computer vision applications. Appearance-based approaches, primarily formulated on RGB data, are constrained and affected by problems arising from occlusions and/or illumination variations. In recent years, the arrival of cheap RGB-Depth (RGB-D) devices has {led} to many new approaches to MHT, and many of these integrate color and depth cues to improve each and every stage of the process. In this survey, we present the common processing pipeline of these methods and review their methodology based (a) on how they implement this pipeline and (b) on what role depth plays within each stage of it. We identify and introduce existing, publicly available, benchmark datasets and software resources that fuse color and depth data for MHT. Finally, we present a brief comparative evaluation of the performance of those works that have applied their methods to these datasets.
Why is Compiling Lifted Inference into a Low-Level Language so Effective?
Venue: arXiv cs.AI 2016
Year: 2016

First-order knowledge compilation techniques have proven efficient for lifted inference. They compile a relational probability model into a target circuit on which many inference queries can be answered efficiently. Early methods used data structures as their target circuit. In our KR-2016 paper, we showed that compiling to a low-level program instead of a data structure offers orders of magnitude speedup, resulting in the state-of-the-art lifted inference technique. In this paper, we conduct experiments to address two questions regarding our KR-2016 results: 1- does the speedup come from more efficient compilation or more efficient reasoning with the target circuit?, and 2- why are low-level programs more efficient target circuits than data structures?
Sparsely Connected and Disjointly Trained Deep Neural Networks for Low Resource Behavioral Annotation: Acoustic Classification in Couples' Therapy
Venue: arXiv cs.LG 2016
Year: 2016

Observational studies are based on accurate assessment of human state. A behavior recognition system that models interlocutors' state in real-time can significantly aid the mental health domain. However, behavior recognition from speech remains a challenging task since it is difficult to find generalizable and representative features because of noisy and high-dimensional data, especially when data is limited and annotated coarsely and subjectively. Deep Neural Networks (DNN) have shown promise in a wide range of machine learning tasks, but for Behavioral Signal Processing (BSP) tasks their application has been constrained due to limited quantity of data. We propose a Sparsely-Connected and Disjointly-Trained DNN (SD-DNN) framework to deal with limited data. First, we break the acoustic feature set into subsets and train multiple distinct classifiers. Then, the hidden layers of these classifiers become parts of a deeper network that integrates all feature streams. The overall system allows for full connectivity while limiting the number of parameters trained at any time and allows convergence possible with even limited data. We present results on multiple behavior codes in the couples' therapy domain and demonstrate the benefits in behavior classification accuracy. We also show the viability of this system towards live behavior annotations.
Fast Reconstruction Algorithm for Perturbed Compressive Sensing Based on Total Least-Squares and Proximal Splitting
Venue: arXiv cs.SY 2016
Year: 2016

We consider the problem of finding a sparse solution for an underdetermined linear system of equations when the known parameters on both sides of the system are subject to perturbation. This problem is particularly relevant to reconstruction in fully-perturbed compressive-sensing setups where both the projected measurements of an unknown sparse vector and the knowledge of the associated projection matrix are perturbed due to noise, error, mismatch, etc. We propose a new iterative algorithm for tackling this problem. The proposed algorithm utilizes the proximal-gradient method to find a sparse total least-squares solution by minimizing an l1-regularized Rayleigh-quotient cost function. We determine the step-size of the algorithm at each iteration using an adaptive rule accompanied by backtracking line search to improve the algorithm's convergence speed and preserve its stability. The proposed algorithm is considerably faster than a popular previously-proposed algorithm, which employs the alternating-direction method and coordinate-descent iterations, as it requires significantly fewer computations to deliver the same accuracy. We demonstrate the effectiveness of the proposed algorithm via simulation results.
A two-stage learning method for protein-protein interaction prediction
Venue: arXiv cs.LG 2016
Year: 2016

In this paper, a new method for PPI (proteinprotein interaction) prediction is proposed. In PPI prediction, a reliable and sufficient number of training samples is not available, but a large number of unlabeled samples is in hand. In the proposed method, the denoising auto encoders are employed for learning robust features. The obtained robust features are used in order to train a classifier with a better performance. The experimental results demonstrate the capabilities of the proposed method. Protein-protein interaction; Denoising auto encoder;Robust features; Unlabelled data;
High Throughput Neural Network based Embedded Streaming Multicore Processors
Venue: arXiv cs.AR 2016
Year: 2016

With power consumption becoming a critical processor design issue, specialized architectures for low power processing are becoming popular. Several studies have shown that neural networks can be used for signal processing and pattern recognition applications. This study examines the design of memristor based multicore neural processors that would be used primarily to process data directly from sensors. Additionally, we have examined the design of SRAM based neural processors for the same task. Full system evaluation of the multicore processors based on these specialized cores were performed taking I/O and routing circuits into consideration. The area and power benefits were compared with traditional multicore RISC processors. Our results show that the memristor based architectures can provide an energy efficiency between three and five orders of magnitude greater than that of RISC processors for the benchmarks examined.
Natural Scene Character Recognition Using Robust PCA and Sparse Representation
Venue: arXiv cs.CV 2016
Year: 2016

Natural scene character recognition is challenging due to the cluttered background, which is hard to separate from text. In this paper, we propose a novel method for robust scene character recognition. Specifically, we first use robust principal component analysis (PCA) to denoise character image by recovering the missing low-rank component and filtering out the sparse noise term, and then use a simple Histogram of oriented Gradient (HOG) to perform image feature extraction, and finally, use a sparse representation based classifier for recognition. In experiments on four public datasets, namely the Char74K dataset, ICADAR 2003 robust reading dataset, Street View Text (SVT) dataset and IIIT5K-word dataset, our method was demonstrated to be competitive with the state-of-the-art methods.
Watch What You Just Said: Image Captioning with Text-Conditional Attention
Venue: arXiv cs.CV 2016
Year: 2016

Attention mechanisms have attracted considerable interest in image captioning due to its powerful performance. However, existing methods use only visual content as attention and whether textual context can improve attention in image captioning remains unsolved. To explore this problem, we propose a novel attention mechanism, called \textit{text-conditional attention}, which allows the caption generator to focus on certain image features given previously generated text. To obtain text-related image features for our attention model, we adopt the guiding Long Short-Term Memory (gLSTM) captioning architecture with CNN fine-tuning. Our proposed method allows joint learning of the image embedding, text embedding, text-conditional attention and language model with one network architecture in an end-to-end manner. We perform extensive experiments on the MS-COCO dataset. The experimental results show that our method outperforms state-of-the-art captioning methods on various quantitative metrics as well as in human evaluation, which supports the use of our text-conditional attention in image captioning.
Unsupervised Learning of Predictors from Unpaired Input-Output Samples
Venue: arXiv cs.LG 2016
Year: 2016

Unsupervised learning is the most challenging problem in machine learning and especially in deep learning. Among many scenarios, we study an unsupervised learning problem of high economic value --- learning to predict without costly pairing of input data and corresponding labels. Part of the difficulty in this problem is a lack of solid evaluation measures. In this paper, we take a practical approach to grounding unsupervised learning by using the same success criterion as for supervised learning in prediction tasks but we do not require the presence of paired input-output training data. In particular, we propose an objective function that aims to make the predicted outputs fit well the structure of the output while preserving the correlation between the input and the predicted output. We experiment with a synthetic structural prediction problem and show that even with simple linear classifiers, the objective function is already highly non-convex. We further demonstrate the nature of this non-convex optimization problem as well as potential solutions. In particular, we show that with regularization via a generative model, learning with the proposed unsupervised objective function converges to an optimal solution.
Trading Determinism for Time in Space Bounded Computations
Venue: arXiv cs.CC 2016
Year: 2016

Savitch showed in $1970$ that nondeterministic logspace (NL) is contained in deterministic $\mathcal{O}(\log^2 n)$ space but his algorithm requires quasipolynomial time. The question whether we can have a deterministic algorithm for every problem in NL that requires polylogarithmic space and simultaneously runs in polynomial time was left open. In this paper we give a partial solution to this problem and show that for every language in NL there exists an unambiguous nondeterministic algorithm that requires $\mathcal{O}(\log^2 n)$ space and simultaneously runs in polynomial time.
Acceleration of Statistical Detection of Zero-day Malware in the Memory Dump Using CUDA-enabled GPU Hardware
Venue: arXiv cs.CR 2016
Year: 2016

This paper focuses on the anticipatory enhancement of methods of detecting stealth software. Cyber security detection tools are insufficiently powerful to reveal the most recent cyber-attacks which use malware. In this paper, we will present first an idea of the highest stealth malware, as this is the most complicated scenario for detection because it combines both existing anti-forensic techniques together with their potential improvements. Second, we present new detection methods, which are resilient to this hidden prototype. To help solve this detection challenge, we have analyzed Windows memory content using a new method of Shannon Entropy calculation; methods of digital photogrammetry; the Zipf Mandelbrot law, as well as by disassembling the memory content and analyzing the output. Finally, we present an idea and architecture of the software tool, which uses CUDA enabled GPU hardware to speed-up memory forensics. All three ideas are currently a work in progress.
Natural Language Generation as Planning under Uncertainty Using Reinforcement Learning
Venue: arXiv cs.CL 2016
Year: 2016

We present and evaluate a new model for Natural Language Generation (NLG) in Spoken Dialogue Systems, based on statistical planning, given noisy feedback from the current generation context (e.g. a user and a surface realiser). We study its use in a standard NLG problem: how to present information (in this case a set of search results) to users, given the complex trade- offs between utterance length, amount of information conveyed, and cognitive load. We set these trade-offs by analysing existing MATCH data. We then train a NLG pol- icy using Reinforcement Learning (RL), which adapts its behaviour to noisy feed- back from the current generation context. This policy is compared to several base- lines derived from previous work in this area. The learned policy significantly out- performs all the prior approaches.
Demand Engineering: IP Network Optimisation Through Intelligent Demand Placement
Venue: arXiv cs.NI 2016
Year: 2016

Traffic engineering has been used in IP and MPLS networks for a number of years as a tool for making more efficient use of capacity by explicitly routing traffic demands where there is available network capacity that would otherwise be unused. Deployment of traffic engineering imposes an additional layer of complexity to network design and operations, however, which has constrained its adoption for capacity optimisation. The rise of Software Defined Networks has renewed interest in the use of traffic engineering approaches leveraging centralised network controllers for capacity optimisation. We argue that future networks can realise the network optimisation benefits of traffic engineering without incurring additional network complexity through closer coupling between the network and the applications and services using the network. This can be achieved through leveraging a network- and traffic-aware controller to directly influence where applications and services site or locate service instances, i.e. which implicitly impacts the paths that the applications or services traffic demands take through the network. We call this technique Demand Engineering. Demand Engineering has the additional benefit of providing an admission control capability, i.e. which can provide an assurance that network SLAs can be met. In this paper we describe the concept of Demand Engineering, give examples of its use and present simulation results indicating its potential benefits. We also compare demand engineering to traffic engineering.
A Unified Framework for Analyzing Closed Queueing Networks in Bike Sharing Systems
Venue: arXiv cs.PF 2016
Year: 2016

During the last decade bike sharing systems have emerged as a public transport mode in urban short trips in more than 500 major cities around the world. For the mobility service mode, many challenges from its operations are not well addressed yet, for example, how to develop the bike sharing systems to be able to effectively satisfy the fluctuating demands both for bikes and for vacant lockers. To this end, it is a key to give performance analysis of the bike sharing systems. This paper first describes a large-scale bike sharing system. Then the bike sharing system is abstracted as a closed queueing network with multi-class customers, where the virtual customers and the virtual nodes are set up, and the service rates as well as the relative arrival rates are established. Finally, this paper gives a product-form solution to the steady state joint probabilities of queue lengths, and gives performance analysis of the bike sharing system. Therefore, this paper provides a unified framework for analyzing closed queueing networks in the study of bike sharing systems. We hope the methodology and results of this paper can be applicable in the study of more general bike sharing systems.
Bio-Inspired Resource Allocation for Relay-Aided Device-to-Device Communications
Venue: arXiv cs.NI 2016
Year: 2016

The Device-to-Device (D2D) communication principle is a key enabler of direct localized communication between mobile nodes and is expected to propel a plethora of novel multimedia services. However, even though it offers a wide set of capabilities mainly due to the proximity and resource reuse gains, interference must be carefully controlled to maximize the achievable rate for coexisting cellular and D2D users. The scope of this work is to provide an interference-aware real-time resource allocation (RA) framework for relay-aided D2D communications that underlay cellular networks. The main objective is to maximize the overall network throughput by guaranteeing a minimum rate threshold for cellular and D2D links. To this direction, genetic algorithms (GAs) are proven to be powerful and versatile methodologies that account for not only enhanced performance but also reduced computational complexity in emerging wireless networks. Numerical investigations highlight the performance gains compared to baseline RA methods and especially in highly dense scenarios which will be the case in future 5G networks.
Automatic finite element implementation of hyperelastic material with a double numerical differentiation algorithm
Venue: arXiv cs.CE 2016
Year: 2016

In order to accelerate implementation of hyperelastic materials for finite element analysis, we developed an automatic numerical algorithm that only requires the strain energy function. This saves the effort on analytical derivation and coding of stress and tangent modulus, which is time-consuming and prone to human errors. Using the one-sided Newton difference quotients, the proposed algorithm first perturbs deformation gradients and calculate the difference on strain energy to approximate stress. Then, we perturb again to get difference in stress to approximate tangent modulus. Accuracy of the approximations were evaluated across the perturbation parameter space, where we find the optimal amount of perturbation being $10^{-6}$ to obtain stress and $10^{-4}$ to obtain tangent modulus. Single element verification in ABAQUS with Neo-Hookean material resulted in a small stress error of only $7\times10^{-5}$ on average across uniaxial compression and tension, biaxial tension and simple shear situations. A full 3D model with Holzapfel anisotropic material for artery inflation generated a small relative error of $4\times10^{-6}$ for inflated radius at $25 kPa$ pressure. Results of the verification tests suggest that the proposed numerical method has good accuracy and convergence performance, therefore a good material implementation algorithm in small scale models and a useful debugging tool for large scale models.
3DFS: Deformable Dense Depth Fusion and Segmentation for Object Reconstruction from a Handheld Camera
Venue: arXiv cs.CV 2016
Year: 2016

We propose an approach for 3D reconstruction and segmentation of a single object placed on a flat surface from an input video. Our approach is to perform dense depth map estimation for multiple views using a proposed objective function that preserves detail. The resulting depth maps are then fused using a proposed implicit surface function that is robust to estimation error, producing a smooth surface reconstruction of the entire scene. Finally, the object is segmented from the remaining scene using a proposed 2D-3D segmentation that incorporates image and depth cues with priors and regularization over the 3D volume and 2D segmentations. We evaluate 3D reconstructions qualitatively on our Object-Videos dataset, comparing to fusion, multiview stereo, and segmentation baselines. We also quantitatively evaluate the dense depth estimation using the RGBD Scenes V2 dataset [Henry et al. 2013] and the segmentation using keyframe annotations of the Object-Videos dataset.