OpenRaiser/Intern-Atlas huggingface dataset:
Graph Partitioning with Acyclicity Constraints
Venue: arXiv cs.DS 2017
Year: 2017

Graphs are widely used to model execution dependencies in applications. In particular, the NP-complete problem of partitioning a graph under constraints receives enormous attention by researchers because of its applicability in multiprocessor scheduling. We identified the additional constraint of acyclic dependencies between blocks when mapping computer vision and imaging applications to a heterogeneous embedded multiprocessor. Existing algorithms and heuristics do not address this requirement and deliver results that are not applicable for our use-case. In this work, we show that this more constrained version of the graph partitioning problem is NP-complete and present heuristics that achieve a close approximation of the optimal solution found by an exhaustive search for small problem instances and much better scalability for larger instances. In addition, we can show a positive impact on the schedule of a real imaging application that improves communication volume and execution time.
Unsupervised Action Proposal Ranking through Proposal Recombination
Venue: arXiv cs.CV 2017
Year: 2017

Recently, action proposal methods have played an important role in action recognition tasks, as they reduce the search space dramatically. Most unsupervised action proposal methods tend to generate hundreds of action proposals which include many noisy, inconsistent, and unranked action proposals, while supervised action proposal methods take advantage of predefined object detectors (e.g., human detector) to refine and score the action proposals, but they require thousands of manual annotations to train. Given the action proposals in a video, the goal of the proposed work is to generate a few better action proposals that are ranked properly. In our approach, we first divide action proposal into sub-proposal and then use Dynamic Programming based graph optimization scheme to select the optimal combinations of sub-proposals from different proposals and assign each new proposal a score. We propose a new unsupervised image-based actioness detector that leverages web images and employs it as one of the node scores in our graph formulation. Moreover, we capture motion information by estimating the number of motion contours within each action proposal patch. The proposed method is an unsupervised method that neither needs bounding box annotations nor video level labels, which is desirable with the current explosion of large-scale action datasets. Our approach is generic and does not depend on a specific action proposal method. We evaluate our approach on several publicly available trimmed and un-trimmed datasets and obtain better performance compared to several proposal ranking methods. In addition, we demonstrate that properly ranked proposals produce significantly better action detection as compared to state-of-the-art proposal based methods.
A Genetic Programming Approach to Designing Convolutional Neural Network Architectures
Venue: arXiv cs.NE 2017
Year: 2017

The convolutional neural network (CNN), which is one of the deep learning models, has seen much success in a variety of computer vision tasks. However, designing CNN architectures still requires expert knowledge and a lot of trial and error. In this paper, we attempt to automatically construct CNN architectures for an image classification task based on Cartesian genetic programming (CGP). In our method, we adopt highly functional modules, such as convolutional blocks and tensor concatenation, as the node functions in CGP. The CNN structure and connectivity represented by the CGP encoding method are optimized to maximize the validation accuracy. To evaluate the proposed method, we constructed a CNN architecture for the image classification task with the CIFAR-10 dataset. The experimental result shows that the proposed method can be used to automatically find the competitive CNN architecture compared with state-of-the-art models.
Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound
Venue: arXiv cs.IT 2017
Year: 2017

We introduce synchronization strings as a novel way of efficiently dealing with synchronization errors, i.e., insertions and deletions. Synchronization errors are strictly more general and much harder to deal with than commonly considered half-errors, i.e., symbol corruptions and erasures. For every $ε>0$, synchronization strings allow to index a sequence with an $ε^{-O(1)}$ size alphabet such that one can efficiently transform $k$ synchronization errors into $(1+ε)k$ half-errors. This powerful new technique has many applications. In this paper, we focus on designing insdel codes, i.e., error correcting block codes (ECCs) for insertion deletion channels. While ECCs for both half-errors and synchronization errors have been intensely studied, the later has largely resisted progress. Indeed, it took until 1999 for the first insdel codes with constant rate, constant distance, and constant alphabet size to be constructed by Schulman and Zuckerman. Insdel codes for asymptotically large or small noise rates were given in 2016 by Guruswami et al. but these codes are still polynomially far from the optimal rate-distance tradeoff. This makes the understanding of insdel codes up to this work equivalent to what was known for regular ECCs after Forney introduced concatenated codes in his doctoral thesis 50 years ago. A direct application of our synchronization strings based indexing method gives a simple black-box construction which transforms any ECC into an equally efficient insdel code with a slightly larger alphabet size. This instantly transfers much of the highly developed understanding for regular ECCs over large constant alphabets into the realm of insdel codes. Most notably, we obtain efficient insdel codes which get arbitrarily close to the optimal rate-distance tradeoff given by the Singleton bound for the complete noise spectrum.
The use of controlled vocabularies in requirements engineering activities: a protocol for a systematic literature review
Venue: arXiv cs.SE 2017
Year: 2017

Context: The Evidence-Based Software Engineering (EBSE) paradigm and the planning phase of a systematic literature review. Objective: A protocol to do a systematic literature review with detailed information about the processes suggested by several guidelines in the field of evidence-based software engineering. Method: An analisys of recent systematic literature reviews published in world leading journals, plus the use of two renowned guidelines and a textbook to sinthetise a formal plan (the protocol). Results: The validated protocol Conclusions: We found that most of the published systematic reviews lack on reporting the protocol, or it is weak. There is a lack of tool support to develop formal protocols. Although a protocol, like a plan, must have the flexibility to adapt to unforeseen situations, its objective is that the actual activities should resemble as far as possible of those already planned. Therefore, it is a difficult balance to achieve and, researchers must be careful not to introduce alterations that could become threats to the validity of the entire work.
Achieving Adaptation for Adaptive Systems via Runtime Verification: A Model-Driven Approach
Venue: arXiv cs.SE 2017
Year: 2017

Self-adaptive systems (SASs) are capable of adjusting its behavior in response to meaningful changes in the operational con-text and itself. The adaptation needs to be performed automatically through self-managed reactions and decision-making processes at runtime. To support this kind of automatic behavior, SASs must be endowed by a rich runtime support that can detect requirements violations and reason about adaptation decisions. Requirements Engineering for SASs primarily aims to model adaptation logic and mechanisms. Requirements models will guide the design decisions and runtime behaviors of sys-tem-to-be. This paper proposes a model-driven approach for achieving adaptation against non-functional requirements (NFRs), i.e. reliability and performances. The approach begins with the models in RE stage and provides runtime support for self-adaptation. We capture adaptation mechanisms as graphical elements in the goal model. By assigning reliability and performance attributes to related system tasks, we derive the tagged sequential diagram for specifying the reliability and performances of system behaviors. To formalize system behavior, we transform the requirements model to the corresponding behavior model, expressed by Label Transition Systems (LTS). To analyze the reliability requirements and performance requirements, we merged the sequential diagram and LTS to a variable Discrete-Time Markov Chains (DTMC) and a variable Continuous-Time Markov Chains (CTMC) respectively. Adaptation candidates are characterized by the variable states. The optimal decision is derived by verifying the concerned NFRs and reducing the decision space. Our approach is implemented through the demonstration of a mobile information system.
HAlign-II: efficient ultra-large multiple sequence alignment and phylogenetic tree reconstruction with distributed and parallel computing
Venue: arXiv cs.DC 2017
Year: 2017

Multiple sequence alignment (MSA) plays a key role in biological sequence analyses, especially in phylogenetic tree construction. Extreme increase in next-generation sequencing results in shortage of efficient ultra-large biological sequence alignment approaches for coping with different sequence types. Distributed and parallel computing represents a crucial technique for accelerating ultra-large sequence analyses. Based on HAlign and Spark distributed computing system, we implement a highly cost-efficient and time-efficient HAlign-II tool to address ultra-large multiple biological sequence alignment and phylogenetic tree construction. After comparing with most available state-of-the-art methods, our experimental results indicate the following: 1) HAlign-II can efficiently carry out MSA and construct phylogenetic trees with ultra-large biological sequences; 2) HAlign-II shows extremely high memory efficiency and scales well with increases in computing resource; 3) HAlign-II provides a user-friendly web server based on our distributed computing infrastructure. HAlign-II with open-source codes and datasets was established at http://lab.malab.cn/soft/halign.
KRC: KnowInG crowdsourcing platform supporting creativity and innovation
Venue: arXiv cs.CY 2017
Year: 2017

The deep financial and economic crisis, which still characterizes these years, requires searching for tools in order to enhance knowledge sharing, creativity and innovation. The Internet is one of these tools that represents a practically infinite source of resources. In this perspective, the KnowInG project, funded by the STC programme MED, is aimed at developing the KnowInG Resource Centre (KRC), a sociotechnical system that works as a multiplier of innovation. KRC was conceived as a crowdsourcing platform allowing people, universities, research centres, organizations and companies to be active actors of creative and innovation processes from a local to a transnational level.
OctNetFusion: Learning Depth Fusion from Data
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we present a learning based approach to depth fusion, i.e., dense 3D reconstruction from multiple depth images. The most common approach to depth fusion is based on averaging truncated signed distance functions, which was originally proposed by Curless and Levoy in 1996. While this method is simple and provides great results, it is not able to reconstruct (partially) occluded surfaces and requires a large number frames to filter out sensor noise and outliers. Motivated by the availability of large 3D model repositories and recent advances in deep learning, we present a novel 3D CNN architecture that learns to predict an implicit surface representation from the input depth maps. Our learning based method significantly outperforms the traditional volumetric fusion approach in terms of noise reduction and outlier suppression. By learning the structure of real world 3D objects and scenes, our approach is further able to reconstruct occluded regions and to fill in gaps in the reconstruction. We demonstrate that our learning based approach outperforms both vanilla TSDF fusion as well as TV-L1 fusion on the task of volumetric fusion. Further, we demonstrate state-of-the-art 3D shape completion results.
A simulated annealing approach to optimal storing in a multi-level warehouse
Venue: arXiv cs.AI 2017
Year: 2017

We propose a simulated annealing algorithm specifically tailored to optimise total retrieval times in a multi-level warehouse under complex pre-batched picking constraints. Experiments on real data from a picker-to-parts order picking process in the warehouse of a European manufacturer show that optimal storage assignments do not necessarily display features presumed in heuristics, such as clustering of positively correlated items or ordering of items by picking frequency. In an experiment run on more than 4000 batched orders with 1 to 150 items per batch, the storage assignment suggested by the algorithm produces a 21\% reduction in the total retrieval time with respect to a frequency-based storage assignment.
An Achilles' Heel of Term-Resolution
Venue: arXiv cs.LO 2017
Year: 2017

Term-resolution provides an elegant mechanism to prove that a quantified Boolean formula (QBF) is true. It is a dual to Q-resolution (also referred to as clause-resolution) and is practically highly important as it enables certifying answers of DPLL-based QBF solvers. While term-resolution and Q-resolution are very similar, they're not completely symmetric. In particular, Q-resolution operates on clauses and term-resolution operates on models of the matrix. This paper investigates what impact this asymmetry has. We'll see that there is a large class of formulas (formulas with "big models") whose term-resolution proofs are exponential. As a possible remedy, the paper suggests to prove true QBFs by refuting their negation ({\em negate-refute}), rather than proving them by term-resolution. The paper shows that from the theoretical perspective this is indeed a favorable approach. In particular, negation-refutation can p-simulates term-resolution and there is an exponential separation between the two calculi. These observations further our understanding of proof systems for QBFs and provide a strong theoretical underpinning for the effort towards non-CNF QBF solvers.
Survey Research in Software Engineering: Problems and Strategies
Venue: arXiv cs.SE 2017
Year: 2017

Background: The need for empirical investigations in software engineering is growing. Many researchers nowadays, conduct and validate their solutions using empirical research. Survey is one empirical method which enables researchers to collect data from a large population. Main aim of the survey is to generalize the findings. Aims: In this study we aim to identify the problems researchers face during survey design, and mitigation strategies. Method: A literature review as well as semi-structured interviews with nine software engineering researchers were conducted to elicit their views on problems and mitigation strategies. The researchers are all focused on empirical software engineering. Results: We identified 24 problems and 65 strategies, structured according to the survey research process. The most commonly discussed problem was sampling, in particular the ability to obtain a sufficiently large sample. To improve survey instrument design, evaluation and execution recommendations for question formulation and survey pre-testing were given. The importance of involving multiple researchers in the analysis of survey results was stressed. Conclusions: The elicited problems and strategies may serve researchers during the design of their studies. However, it was observed that some strategies were conflicting. This shows that it is important to conduct a trade-off analysis between strategies.
On Resource-bounded versions of the van Lambalgen theorem
Venue: arXiv cs.CC 2017
Year: 2017

The van Lambalgen theorem is a surprising result in algorithmic information theory concerning the symmetry of relative randomness. It establishes that for any pair of infinite sequences $A$ and $B$, $B$ is Martin-Löf random and $A$ is Martin-Löf random relative to $B$ if and only if the interleaved sequence $A \uplus B$ is Martin-Löf random. This implies that $A$ is relative random to $B$ if and only if $B$ is random relative to $A$ \cite{vanLambalgen}, \cite{Nies09}, \cite{HirschfeldtBook}. This paper studies the validity of this phenomenon for different notions of time-bounded relative randomness. We prove the classical van Lambalgen theorem using martingales and Kolmogorov compressibility. We establish the failure of relative randomness in these settings, for both time-bounded martingales and time-bounded Kolmogorov complexity. We adapt our classical proofs when applicable to the time-bounded setting, and construct counterexamples when they fail. The mode of failure of the theorem may depend on the notion of time-bounded randomness.
DyVEDeep: Dynamic Variable Effort Deep Neural Networks
Venue: arXiv cs.NE 2017
Year: 2017

Deep Neural Networks (DNNs) have advanced the state-of-the-art in a variety of machine learning tasks and are deployed in increasing numbers of products and services. However, the computational requirements of training and evaluating large-scale DNNs are growing at a much faster pace than the capabilities of the underlying hardware platforms that they are executed upon. In this work, we propose Dynamic Variable Effort Deep Neural Networks (DyVEDeep) to reduce the computational requirements of DNNs during inference. Previous efforts propose specialized hardware implementations for DNNs, statically prune the network, or compress the weights. Complementary to these approaches, DyVEDeep is a dynamic approach that exploits the heterogeneity in the inputs to DNNs to improve their compute efficiency with comparable classification accuracy. DyVEDeep equips DNNs with dynamic effort mechanisms that, in the course of processing an input, identify how critical a group of computations are to classify the input. DyVEDeep dynamically focuses its compute effort only on the critical computa- tions, while skipping or approximating the rest. We propose 3 effort knobs that operate at different levels of granularity viz. neuron, feature and layer levels. We build DyVEDeep versions for 5 popular image recognition benchmarks - one for CIFAR-10 and four for ImageNet (AlexNet, OverFeat and VGG-16, weight-compressed AlexNet). Across all benchmarks, DyVEDeep achieves 2.1x-2.6x reduction in the number of scalar operations, which translates to 1.8x-2.3x performance improvement over a Caffe-based implementation, with < 0.5% loss in accuracy.
On the Glitch Phenomenon
Venue: arXiv cs.IT 2017
Year: 2017

The Principle of the Glitch states that for any device which makes a discrete decision based upon a continuous range of possible inputs, there are inputs for which it will take arbitrarily long to reach a decision. The appropriate mathematical setting for studying this principle is described. This involves defining the concept of continuity for mappings on sets of functions. It can then be shown that the glitch principle follows from the continuous behavior of the device.
Two Stream LSTM: A Deep Fusion Framework for Human Action Recognition
Venue: arXiv cs.CV 2017
Year: 2017

In this paper we address the problem of human action recognition from video sequences. Inspired by the exemplary results obtained via automatic feature learning and deep learning approaches in computer vision, we focus our attention towards learning salient spatial features via a convolutional neural network (CNN) and then map their temporal relationship with the aid of Long-Short-Term-Memory (LSTM) networks. Our contribution in this paper is a deep fusion framework that more effectively exploits spatial features from CNNs with temporal features from LSTM models. We also extensively evaluate their strengths and weaknesses. We find that by combining both the sets of features, the fully connected features effectively act as an attention mechanism to direct the LSTM to interesting parts of the convolutional feature sequence. The significance of our fusion method is its simplicity and effectiveness compared to other state-of-the-art methods. The evaluation results demonstrate that this hierarchical multi stream fusion method has higher performance compared to single stream mapping methods allowing it to achieve high accuracy outperforming current state-of-the-art methods in three widely used databases: UCF11, UCFSports, jHMDB.
Software Defined Networking Enabled Wireless Network Virtualization: Challenges and Solutions
Venue: arXiv cs.NI 2017
Year: 2017

Next generation (5G) wireless networks are expected to support the massive data and accommodate a wide range of services/use cases with distinct requirements in a cost-effective, flexible, and agile manner. As a promising solution, wireless network virtualization (WNV), or network slicing, enables multiple virtual networks to share the common infrastructure on demand, and to be customized for different services/use cases. This article focuses on network-wide resource allocation for realizing WNV. Specifically, the motivations, the enabling platforms, and the benefits of WNV, are first reviewed. Then, resource allocation for WNV along with the technical challenges is discussed. Afterwards, a software defined networking (SDN) enabled resource allocation framework is proposed to facilitate WNV, including the key procedures and the corresponding modeling approaches. Furthermore, a case study is provided as an example of resource allocation in WNV. Finally, some open research topics essential to WNV are discussed.
A General Framework for Multi-vehicle Cooperative Localization Using Pose Graph
Venue: arXiv cs.RO 2017
Year: 2017

When a vehicle observes another one, the two vehicles' poses are correlated by this spatial relative observation, which can be used in cooperative localization for further increasing localization accuracy and precision. To use spatial relative observations, we propose to add them into a pose graph for optimal pose estimation. Before adding them, we need to know the identities of the observed vehicles. The vehicle identification is formulated as a linear assignment problem, which can be solved efficiently. By using pose graph techniques and the start-of-the-art factor composition/decomposition method, our cooperative localization algorithm is robust against communication delay, packet loss, and out-of-sequence packet reception. We demonstrate the usability of our framework and effectiveness of our algorithm through both simulations and real-world experiments using three vehicles on the road.
Supporting Navigation of Outdoor Shopping Complexes for Visually-impaired Users through Multi-modal Data Fusion
Venue: arXiv cs.CV 2017
Year: 2017

Outdoor shopping complexes (OSC) are extremely difficult for people with visual impairment to navigate. Existing GPS devices are mostly designed for roadside navigation and seldom transition well into an OSC-like setting. We report our study on the challenges faced by a blind person in navigating OSC through developing a new mobile application named iExplore. We first report an exploratory study aiming at deriving specific design principles for building this system by learning the unique challenges of the problem. Then we present a methodology that can be used to derive the necessary information for the development of iExplore, followed by experimental validation of the technology by a group of visually impaired users in a local outdoor shopping center. User feedback and other experiments suggest that iExplore, while at its very initial phase, has the potential of filling a practical gap in existing assistive technologies for the visually impaired.