OpenRaiser/Intern-Atlas huggingface dataset:
Analyzing Big Datasets of Genomic Sequences: Fast and Scalable Collection of k-mer Statistics
Venue: arXiv cs.DC 2018
Year: 2018

Distributed approaches based on the map-reduce programming paradigm have started to be proposed in the bioinformatics domain, due to the large amount of data produced by the next-generation sequencing techniques. However, the use of map-reduce and related Big Data technologies and frameworks (e.g., Apache Hadoop and Spark) does not necessarily produce satisfactory results, in terms of both efficiency and effectiveness. We discuss how the development of distributed and Big Data management technologies has affected the analysis of large datasets of biological sequences. Moreover, we show how the choice of different parameter configurations and the careful engineering of the software with respect to the specific framework under consideration may be crucial in order to achieve good performance, especially on very large amounts of data. We choose k-mers counting as a case study for our analysis, and Spark as the framework to implement FastKmer, a novel approach for the extraction of k-mer statistics from large collection of biological sequences, with arbitrary values of k. One of the most relevant contributions of FastKmer is the introduction of a module for balancing the statistics aggregation workload over the nodes of a computing cluster, in order to overcome data skew while allowing for a fully exploitation of the underly- ing distributed architecture. We also present the results of a comparative experimental analysis showing that our approach is currently the fastest among the ones based on Big Data technologies, while exhibiting a very good scalability. We provide evidence that the usage of technologies such as Hadoop or Spark for the analysis of big datasets of biological sequences is productive only if the architectural details and the peculiar aspects of the considered framework are carefully taken into account for the algorithm design and implementation.
Efficient Parallel Self-Assembly Under Uniform Control Inputs
Venue: arXiv cs.CG 2018
Year: 2018

We prove that by successively combining subassemblies, we can achieve sublinear construction times for "staged" assembly of micro-scale objects from a large number of tiny particles, for vast classes of shapes; this is a significant advance in the context of programmable matter and self-assembly for building high-yield micro-factories.The underlying model has particles moving under the influence of uniform external forces until they hit an obstacle; particles bond when forced together with a compatible particle. Previous work considered sequential composition of objects, resulting in construction time that is linear in the number N of particles, which is inefficient for large N. Our progress implies critical speedup for constructible shapes; for convex polyominoes, even a constant construction time is possible. We also show that our construction process can be used for pipelining, resulting in an amortized constant production time.
Higher-dimension Tensor Completion via Low-rank Tensor Ring Decomposition
Venue: arXiv cs.NA 2018
Year: 2018

The problem of incomplete data is common in signal processing and machine learning. Tensor completion algorithms aim to recover the incomplete data from its partially observed entries. In this paper, taking advantages of high compressibility and flexibility of recently proposed tensor ring (TR) decomposition, we propose a new tensor completion approach named tensor ring weighted optimization (TR-WOPT). It finds the latent factors of the incomplete tensor by gradient descent algorithm, then the latent factors are employed to predict the missing entries of the tensor. We conduct various tensor completion experiments on synthetic data and real-world data. The simulation results show that TR-WOPT performs well in various high-dimension tensors. Furthermore, image completion results show that our proposed algorithm outperforms the state-of-the-art algorithms in many situations. Especially when the missing rate of the test images is high (e.g., over 0.9), the performance of our TR-WOPT is significantly better than the compared algorithms.
Sensors, SLAM and Long-term Autonomy: A Review
Venue: arXiv cs.CV 2018
Year: 2018

Simultaneous Localization and Mapping, commonly known as SLAM, has been an active research area in the field of Robotics over the past three decades. For solving the SLAM problem, every robot is equipped with either a single sensor or a combination of similar/different sensors. This paper attempts to review, discuss, evaluate and compare these sensors. Keeping an eye on future, this paper also assesses the characteristics of these sensors against factors critical to the long-term autonomy challenge.
Multi-Stage JavaScript
Venue: arXiv cs.PL 2018
Year: 2018

Multi-stage languages support generative metaprogramming via macros evaluated in a process preceding the actual interpretation or compilation of the program in which they are used. Macros update the source of their hosting program by emitting code that takes their place in the file, while their code may also be produced, fully or partially, by nested macros. All macros at the same nesting belong to the same stage, with the outer stage collecting the macros affect-ing only the main program. We extended JavaScript with staging annotations and implemented them in Spider Monkey, emitting pure JavaScript code as the final outcome of stage computation. We discuss how the original Spider Monkey system is minimally affected with extensions in the syntax, parser and internal AST structures, and the addition of an unparser, a staging loop, some library functions and a debugger backend component for AST inspection. Since stages have a generative metaprogramming role we do not foresee any interplay with the browser DOM, and thus there is no reason to repeat their evalua-tion on every page load. Hence, such JavaScript extensions are meant only for development-time, emitting pure JavaScript code that can be run in any browser. Finally, to enable debugging stages in any browser we implemented a pure JavaScript client, communicating with the extended Spider Monkey, and offering the necessary AST display and unparsing that a browser debugger does not provide.
Logical rules as fractions and logics as sketches
Venue: arXiv cs.LO 2018
Year: 2018

In this short paper, using category theory, we argue that logical rules can be seen as fractions and logics as limit sketches.
Teaching DevOps in Corporate Environments: An experience report
Venue: arXiv cs.SE 2018
Year: 2018

This paper describes our experience of training a team of developers of an East-European phone service provider. The training experience was structured in two sessions of two days each conducted in different weeks with a gap of about fifteen days. The first session was dedicated to the Continuous Integration Delivery Pipeline, and the second on Agile methods. We summarize the activity, its preparation and delivery and draw some conclusions out of it on our mistakes and how future session should be addressed.
Encoding Spatial Relations from Natural Language
Venue: arXiv cs.CL 2018
Year: 2018

Natural language processing has made significant inroads into learning the semantics of words through distributional approaches, however representations learnt via these methods fail to capture certain kinds of information implicit in the real world. In particular, spatial relations are encoded in a way that is inconsistent with human spatial reasoning and lacking invariance to viewpoint changes. We present a system capable of capturing the semantics of spatial relations such as behind, left of, etc from natural language. Our key contributions are a novel multi-modal objective based on generating images of scenes from their textual descriptions, and a new dataset on which to train it. We demonstrate that internal representations are robust to meaning preserving transformations of descriptions (paraphrase invariance), while viewpoint invariance is an emergent property of the system.
Shannon entropy for intuitionistic fuzzy information
Venue: arXiv cs.AI 2018
Year: 2018

The paper presents an extension of Shannon fuzzy entropy for intuitionistic fuzzy one. Firstly, we presented a new formula for calculating the distance and similarity of intuitionistic fuzzy information. Then, we constructed measures for information features like score, certainty and uncertainty. Also, a new concept was introduced, namely escort fuzzy information. Then, using the escort fuzzy information, Shannon's formula for intuitionistic fuzzy information was obtained. It should be underlined that Shannon's entropy for intuitionistic fuzzy information verifies the four defining conditions of intuitionistic fuzzy uncertainty. The measures of its two components were also identified: fuzziness (ambiguity) and incompleteness (ignorance).
Seq2RDF: An end-to-end application for deriving Triples from Natural Language Text
Venue: arXiv cs.CL 2018
Year: 2018

We present an end-to-end approach that takes unstructured textual input and generates structured output compliant with a given vocabulary. Inspired by recent successes in neural machine translation, we treat the triples within a given knowledge graph as an independent graph language and propose an encoder-decoder framework with an attention mechanism that leverages knowledge graph embeddings. Our model learns the mapping from natural language text to triple representation in the form of subject-predicate-object using the selected knowledge graph vocabulary. Experiments on three different data sets show that we achieve competitive F1-Measures over the baselines using our simple yet effective approach. A demo video is included.
Per-decision Multi-step Temporal Difference Learning with Control Variates
Venue: arXiv cs.LG 2018
Year: 2018

Multi-step temporal difference (TD) learning is an important approach in reinforcement learning, as it unifies one-step TD learning with Monte Carlo methods in a way where intermediate algorithms can outperform either extreme. They address a bias-variance trade off between reliance on current estimates, which could be poor, and incorporating longer sampled reward sequences into the updates. Especially in the off-policy setting, where the agent aims to learn about a policy different from the one generating its behaviour, the variance in the updates can cause learning to diverge as the number of sampled rewards used in the estimates increases. In this paper, we introduce per-decision control variates for multi-step TD algorithms, and compare them to existing methods. Our results show that including the control variates can greatly improve performance on both on and off-policy multi-step temporal difference learning tasks.
Formalisation in Constructive Type Theory of Barendregt's Variable Convention for Generic Structures with Binders
Venue: arXiv cs.PL 2018
Year: 2018

We introduce a universe of regular datatypes with variable binding information, for which we define generic formation and elimination (i.e. induction /recursion) operators. We then define a generic alpha-equivalence relation over the types of the universe based on name-swapping, and derive iteration and induction principles which work modulo alpha-conversion capturing Barendregt's Variable Convention. We instantiate the resulting framework so as to obtain the Lambda Calculus and System F, for which we derive substitution operations and substitution lemmas for alpha-conversion and substitution composition. The whole work is carried out in Constructive Type Theory and machine-checked by the system Agda.
A Single Shot Text Detector with Scale-adaptive Anchors
Venue: arXiv cs.CV 2018
Year: 2018

Currently, most top-performing text detection networks tend to employ fixed-size anchor boxes to guide the search for text instances. They usually rely on a large amount of anchors with different scales to discover texts in scene images, thus leading to high computational cost. In this paper, we propose an end-to-end box-based text detector with scale-adaptive anchors, which can dynamically adjust the scales of anchors according to the sizes of underlying texts by introducing an additional scale regression layer. The proposed scale-adaptive anchors allow us to use a few number of anchors to handle multi-scale texts and therefore significantly improve the computational efficiency. Moreover, compared to discrete scales used in previous methods, the learned continuous scales are more reliable, especially for small texts detection. Additionally, we propose Anchor convolution to better exploit necessary feature information by dynamically adjusting the sizes of receptive fields according to the learned scales. Extensive experiments demonstrate that the proposed detector is fast, taking only $0.28$ second per image, while outperforming most state-of-the-art methods in accuracy.
Towards Classification of Lightweight Formal Methods
Venue: arXiv cs.SE 2018
Year: 2018

The use of lightweight formal methods (LFM) for the development of industrial applications has become a major trend. Although the term "lightweight formal methods" has been used for over ten years now, there seems to be no common agreement on what "lightweight" actually means, and different communities apply the term in all kinds of ways. In this paper, we explore the recent trends in the use of LFM, and establish our opinion that cost-effectiveness is the driving force to deploy LFM. Further, we propose a simple framework that should help to classify different LFM approaches and to estimate which of them are most cost-effective for a certain software engineering project. We demonstrate our framework using some examples.
Arcades: A deep model for adaptive decision making in voice controlled smart-home
Venue: arXiv cs.LG 2018
Year: 2018

In a voice-controlled smart-home, a controller must respond not only to user's requests but also according to the interaction context. This paper describes Arcades, a system which uses deep reinforcement learning to extract context from a graphical representation of home automation system and to update continuously its behavior to the user's one. This system is robust to changes in the environment (sensor breakdown or addition) through its graphical representation (scale well) and the reinforcement mechanism (adapt well). The experiments on realistic data demonstrate that this method promises to reach long life context-aware control of smart-home.
The em-convex rewrite system
Venue: arXiv cs.LO 2018
Year: 2018

We introduce and study em (or "emergent"), a lambda calculus style rewrite system inspired from dilations structures in metric geometry. Then we add a new axiom (convex) and explore its consequences. Although (convex) forces commutativity of the infinitesimal operations, Theorems 6.2, 8.9 and Proposition 8.7 appear as a lambda calculus style version of Gleason and Montgomery-Zippin solution to the Hilbert 5th problem.
Analysis of Nederlof's algorithm for subset sum
Venue: arXiv cs.DS 2018
Year: 2018

We show that Nederlof's algorithm [Information Processing Letters, 118 (2017), 15-16] for constructing a proof that the number of subsets summing to a particular integer equals a claimed quantity is flawed because: 1) its consistence is not kept; 2) the proposed recurrence formula is incorrect.
Goal-oriented Trajectories for Efficient Exploration
Venue: arXiv cs.LG 2018
Year: 2018

Exploration is a difficult challenge in reinforcement learning and even recent state-of-the art curiosity-based methods rely on the simple epsilon-greedy strategy to generate novelty. We argue that pure random walks do not succeed to properly expand the exploration area in most environments and propose to replace single random action choices by random goals selection followed by several steps in their direction. This approach is compatible with any curiosity-based exploration and off-policy reinforcement learning agents and generates longer and safer trajectories than individual random actions. To illustrate this, we present a task-independent agent that learns to reach coordinates in screen frames and demonstrate its ability to explore with the game Super Mario Bros. improving significantly the score of a baseline DQN agent.
Scalable Recommender Systems through Recursive Evidence Chains
Venue: arXiv cs.IR 2018
Year: 2018

Recommender systems can be formulated as a matrix completion problem, predicting ratings from user and item parameter vectors. Optimizing these parameters by subsampling data becomes difficult as the number of users and items grows. We develop a novel approach to generate all latent variables on demand from the ratings matrix itself and a fixed pool of parameters. We estimate missing ratings using chains of evidence that link them to a small set of prototypical users and items. Our model automatically addresses the cold-start and online learning problems by combining information across both users and items. We investigate the scaling behavior of this model, and demonstrate competitive results with respect to current matrix factorization techniques in terms of accuracy and convergence speed.
Encoding Motion Primitives for Autonomous Vehicles using Virtual Velocity Constraints and Neural Network Scheduling
Venue: arXiv cs.RO 2018
Year: 2018

Within the context of trajectory planning for autonomous vehicles this paper proposes methods for efficient encoding of motion primitives in neural networks on top of model-based and gradient-free reinforcement learning. It is distinguished between 5 core aspects: system model, network architecture, training algorithm, training tasks selection and hardware/software implementation. For the system model, a kinematic (3-states-2-controls) and a dynamic (16-states-2-controls) vehicle model are compared. For the network architecture, 3 feedforward structures are compared including weighted skip connections. For the training algorithm, virtual velocity constraints and network scheduling are proposed. For the training tasks, different feature vector selections are discussed. For the implementation, aspects of gradient-free learning using 1 GPU and the handling of perturbation noise therefore are discussed. The effects of proposed methods are illustrated in experiments encoding up to 14625 motion primitives. The capabilities of tiny neural networks with as few as 10 scalar parameters when scheduled on vehicle velocity are emphasized.
Minutia Texture Cylinder Codes for fingerprint matching
Venue: arXiv cs.CV 2018
Year: 2018

Minutia Cylinder Codes (MCC) are minutiae based fingerprint descriptors that take into account minutiae information in a fingerprint image for fingerprint matching. In this paper, we present a modification to the underlying information of the MCC descriptor and show that using different features, the accuracy of matching is highly affected by such changes. MCC originally being a minutia only descriptor is transformed into a texture descriptor. The transformation is from minutiae angular information to orientation, frequency and energy information using Short Time Fourier Transform (STFT) analysis. The minutia cylinder codes are converted to minutiae texture cylinder codes (MTCC). Based on a fixed set of parameters, the proposed changes to MCC show improved performance on FVC 2002 and 2004 data sets and surpass the traditional MCC performance.
Towards a Context-Aware IDE-Based Meta Search Engine for Recommendation about Programming Errors and Exceptions
Venue: arXiv cs.SE 2018
Year: 2018

Study shows that software developers spend about 19% of their time looking for information in the web during software development and maintenance. Traditional web search forces them to leave the working environment (e.g., IDE) and look for information in the web browser. It also does not consider the context of the problems that the developers search solutions for. The frequent switching between web browser and the IDE is both time-consuming and distracting, and the keyword-based traditional web search often does not help much in problem solving. In this paper, we propose an Eclipse IDE-based web search solution that exploits the APIs provided by three popular web search engines-- Google, Yahoo, Bing and a popular programming Q & A site, Stack Overflow, and captures the content-relevance, context-relevance, popularity and search engine confidence of each candidate result against the encountered programming problems. Experiments with 75 programming errors and exceptions using the proposed approach show that inclusion of different types of context information associated with a given exception can enhance the recommendation accuracy of a given exception. Experiments both with two existing approaches and existing web search engines confirm that our approach can perform better than them in terms of recall, mean precision and other performance measures with little computational cost.
Combining SLAM with muti-spectral photometric stereo for real-time dense 3D reconstruction
Venue: arXiv cs.CV 2018
Year: 2018

Obtaining dense 3D reconstrution with low computational cost is one of the important goals in the field of SLAM. In this paper we propose a dense 3D reconstruction framework from monocular multispectral video sequences using jointly semi-dense SLAM and Multispectral Photometric Stereo approaches. Starting from multispectral video, SALM (a) reconstructs a semi-dense 3D shape that will be densified;(b) recovers relative sparse depth map that is then fed as prioris into optimization-based multispectral photometric stereo for a more accurate dense surface normal recovery;(c)obtains camera pose that is subsequently used for conversion of view in the process of fusion where we combine the relative sparse point cloud with the dense surface normal using the automated cross-scale fusion method proposed in this paper to get a dense point cloud with subtle texture information. Experiments show that our method can effectively obtain denser 3D reconstructions.
Tight Typings and Split Bounds
Venue: arXiv cs.PL 2018
Year: 2018

Multi types---aka non-idempotent intersection types---have been used to obtain quantitative bounds on higher-order programs, as pioneered by de Carvalho. Notably, they bound at the same time the number of evaluation steps and the size of the result. Recent results show that the number of steps can be taken as a reasonable time complexity measure. At the same time, however, these results suggest that multi types provide quite lax complexity bounds, because the size of the result can be exponentially bigger than the number of steps. Starting from this observation, we refine and generalise a technique introduced by Bernadet & Graham-Lengrand to provide exact bounds for the maximal strategy. Our typing judgements carry two counters, one measuring evaluation lengths and the other measuring result sizes. In order to emphasise the modularity of the approach, we provide exact bounds for four evaluation strategies, both in the lambda-calculus (head, leftmost-outermost, and maximal evaluation) and in the linear substitution calculus (linear head evaluation). Our work aims at both capturing the results in the literature and extending them with new outcomes. Concerning the literature, it unifies de Carvalho and Bernadet & Graham-Lengrand via a uniform technique and a complexity-based perspective. The two main novelties are exact split bounds for the leftmost strategy---the only known strategy that evaluates terms to full normal forms and provides a reasonable complexity measure---and the observation that the computing device hidden behind multi types is the notion of substitution at a distance, as implemented by the linear substitution calculus.