OpenRaiser/Intern-Atlas huggingface dataset:
An Empirical Analysis of NMT-Derived Interlingual Embeddings and their Use in Parallel Sentence Identification
Venue: arXiv cs.CL 2017
Year: 2017

End-to-end neural machine translation has overtaken statistical machine translation in terms of translation quality for some language pairs, specially those with large amounts of parallel data. Besides this palpable improvement, neural networks provide several new properties. A single system can be trained to translate between many languages at almost no additional cost other than training time. Furthermore, internal representations learned by the network serve as a new semantic representation of words -or sentences- which, unlike standard word embeddings, are learned in an essentially bilingual or even multilingual context. In view of these properties, the contribution of the present work is two-fold. First, we systematically study the NMT context vectors, i.e. output of the encoder, and their power as an interlingua representation of a sentence. We assess their quality and effectiveness by measuring similarities across translations, as well as semantically related and semantically unrelated sentence pairs. Second, as extrinsic evaluation of the first point, we identify parallel sentences in comparable corpora, obtaining an F1=98.2% on data from a shared task when using only NMT context vectors. Using context vectors jointly with similarity measures F1 reaches 98.9%.
Diagonal RNNs in Symbolic Music Modeling
Venue: arXiv cs.NE 2017
Year: 2017

In this paper, we propose a new Recurrent Neural Network (RNN) architecture. The novelty is simple: We use diagonal recurrent matrices instead of full. This results in better test likelihood and faster convergence compared to regular full RNNs in most of our experiments. We show the benefits of using diagonal recurrent matrices with popularly used LSTM and GRU architectures as well as with the vanilla RNN architecture, on four standard symbolic music datasets.
Online Degree-Bounded Steiner Network Design
Venue: arXiv cs.DS 2017
Year: 2017

We initiate the study of degree-bounded network design problems in the online setting. The degree-bounded Steiner tree problem { which asks for a subgraph with minimum degree that connects a given set of vertices { is perhaps one of the most representative problems in this class. This paper deals with its well-studied generalization called the degree-bounded Steiner forest problem where the connectivity demands are represented by vertex pairs that need to be individually connected. In the classical online model, the input graph is given online but the demand pairs arrive sequentially in online steps. The selected subgraph starts off as the empty subgraph, but has to be augmented to satisfy the new connectivity constraint in each online step. The goal is to be competitive against an adversary that knows the input in advance. We design a simple greedy-like algorithm that achieves a competitive ratio of O(log n) where n is the number of vertices. We show that no (randomized) algorithm can achieve a (multiplicative) competitive ratio o(log n); thus our result is asymptotically tight. We further show strong hardness results for the group Steiner tree and the edge-weighted variants of degree-bounded connectivity problems. Fourer and Raghavachari resolved the online variant of degree-bounded Steiner forest in their paper in SODA'92. Since then, the natural family of degree-bounded network design problems has been extensively studied in the literature resulting in the development of many interesting tools and numerous papers on the topic. We hope that our approach in this paper, paves the way for solving the online variants of the classical problems in this family of network design problems.
Performance of Optimal Data Shaping Codes
Venue: arXiv cs.IT 2017
Year: 2017

Data shaping is a coding technique that has been proposed to increase the lifetime of flash memory devices. Several data shaping codes have been described in recent work, including endurance codes and direct shaping codes for structured data. In this paper, we study information-theoretic properties of a general class of data shaping codes and prove a separation theorem stating that optimal data shaping can be achieved by the concatenation of optimal lossless compression with optimal endurance coding. We also determine the expansion factor that minimizes the total wear cost. Finally, we analyze the performance of direct shaping codes and establish a condition for their optimality.
Coordinating Collaborative Chat in Massive Open Online Courses
Venue: arXiv cs.CY 2017
Year: 2017

An earlier study of a collaborative chat intervention in a Massive Open Online Course (MOOC) identified negative effects on attrition stemming from a requirement for students to be matched with exactly one partner prior to beginning the activity. That study raised questions about how to orchestrate a collaborative chat intervention in a MOOC context in order to provide the benefit of synchronous social engagement without the coordination difficulties. In this paper we present a careful analysis of an intervention designed to overcome coordination difficulties by welcoming students into the chat on a rolling basis as they arrive rather than requiring them to be matched with a partner before beginning. The results suggest the most positive impact when experiencing a chat with exactly one partner rather than more or less. A qualitative analysis of the chat data reveals differential experiences between these configurations that suggests a potential explanation for the effect and raises questions for future research.
A lower bound on the 2-adic complexity of Ding-Helleseth generalized cyclotomic sequences of period $p^n$
Venue: arXiv cs.IT 2017
Year: 2017

Let $p$ be an odd prime, $n$ a positive integer and $g$ a primitive root of $p^n$. Suppose $D_i^{(p^n)}=\{g^{2s+i}|s=0,1,2,\cdots,\frac{(p-1)p^{n-1}}{2}\}$, $i=0,1$, is the generalized cyclotomic classes with $Z_{p^n}^{\ast}=D_0\cup D_1$. In this paper, we prove that Gauss periods based on $D_0$ and $D_1$ are both equal to 0 for $n\geq2$. As an application, we determine a lower bound on the 2-adic complexity of a class of Ding-Helleseth generalized cyclotomic sequences of period $p^n$. The result shows that the 2-adic complexity is at least $p^n-p^{n-1}-1$, which is larger than $\frac{N+1}{2}$, where $N=p^n$ is the period of the sequence.
Ubergraphs: A Definition of a Recursive Hypergraph Structure
Venue: arXiv cs.DM 2017
Year: 2017

Partly in service of exploring the formal basis for Georgetown University's AvesTerra database structure, we formalize a recursive hypergraph data structure, which we call an ubergraph.
1D Modeling of Sensor Selection Problem for Weak Barrier Coverage and Gap Mending in Wireless Sensor Networks
Venue: arXiv cs.DS 2017
Year: 2017

In this paper, we first remodel the line coverage as a 1D discrete problem with co-linear targets. Then, an order-based greedy algorithm, called OGA, is proposed to solve the problem optimally. It will be shown that the existing order in the 1D modeling, and especially the resulted Markov property of the selected sensors can help design greedy algorithms such as OGA. These algorithms demonstrate optimal/efficient performance and have lower complexity compared to the state-of-the-art. Furthermore, it is demonstrated that the conventional continuous line coverage problem can be converted to an equivalent discrete problem and solved optimally by OGA. Next, we formulate the well-known weak barrier coverage problem as an instance of the continuous line coverage problem (i.e. a 1D problem) as opposed to the conventional 2D graph-based models. We demonstrate that the equivalent discrete version of this problem can be solved optimally and faster than the state-of-the-art methods using an extended version of OGA, called K-OGA. Moreover, an efficient local algorithm, called LOGM, is proposed to mend barrier gaps due to sensor failure. In the case of m gaps, LOGM is proved to select at most 2m-1 sensors more than the optimal while being local and implementable in distributed fashion. We demonstrate the optimal/efficient performance of the proposed algorithms via extensive simulations.
Computability in the Lattice of Equivalence Relations
Venue: arXiv cs.CC 2017
Year: 2017

We investigate computability in the lattice of equivalence relations on the natural numbers. We mostly investigate whether the subsets of appropriately defined subrecursive equivalence relations -for example the set of all polynomial-time decidable equivalence relations- form sublattices of the lattice.
OCRAPOSE II: An OCR-based indoor positioning system using mobile phone images
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we propose an OCR (optical character recognition)-based localization system called OCRAPOSE II, which is applicable in a number of indoor scenarios including office buildings, parkings, airports, grocery stores, etc. In these scenarios, characters (i.e. texts or numbers) can be used as suitable distinctive landmarks for localization. The proposed system takes advantage of OCR to read these characters in the query still images and provides a rough location estimate using a floor plan. Then, it finds depth and angle-of-view of the query using the information provided by the OCR engine in order to refine the location estimate. We derive novel formulas for the query angle-of-view and depth estimation using image line segments and the OCR box information. We demonstrate the applicability and effectiveness of the proposed system through experiments in indoor scenarios. It is shown that our system demonstrates better performance compared to the state-of-the-art benchmarks in terms of location recognition rate and average localization error specially under sparse database condition.
Perfect Half Space Games
Venue: arXiv cs.GT 2017
Year: 2017

We introduce perfect half space games, in which the goal of Player 2 is to make the sums of encountered multi-dimensional weights diverge in a direction which is consistent with a chosen sequence of perfect half spaces (chosen dynamically by Player 2). We establish that the bounding games of Jurdziński et al. (ICALP 2015) can be reduced to perfect half space games, which in turn can be translated to the lexicographic energy games of Colcombet and Niwiński, and are positionally determined in a strong sense (Player 2 can play without knowing the current perfect half space). We finally show how perfect half space games and bounding games can be employed to solve multi-dimensional energy parity games in pseudo-polynomial time when both the numbers of energy dimensions and of priorities are fixed, regardless of whether the initial credit is given as part of the input or existentially quantified. This also yields an optimal 2-EXPTIME complexity with given initial credit, where the best known upper bound was non-elementary.
ConvNet-Based Localization of Anatomical Structures in 3D Medical Images
Venue: arXiv cs.CV 2017
Year: 2017

Localization of anatomical structures is a prerequisite for many tasks in medical image analysis. We propose a method for automatic localization of one or more anatomical structures in 3D medical images through detection of their presence in 2D image slices using a convolutional neural network (ConvNet). A single ConvNet is trained to detect presence of the anatomical structure of interest in axial, coronal, and sagittal slices extracted from a 3D image. To allow the ConvNet to analyze slices of different sizes, spatial pyramid pooling is applied. After detection, 3D bounding boxes are created by combining the output of the ConvNet in all slices. In the experiments 200 chest CT, 100 cardiac CT angiography (CTA), and 100 abdomen CT scans were used. The heart, ascending aorta, aortic arch, and descending aorta were localized in chest CT scans, the left cardiac ventricle in cardiac CTA scans, and the liver in abdomen CT scans. Localization was evaluated using the distances between automatically and manually defined reference bounding box centroids and walls. The best results were achieved in localization of structures with clearly defined boundaries (e.g. aortic arch) and the worst when the structure boundary was not clearly visible (e.g. liver). The method was more robust and accurate in localization multiple structures.
Remote Document Encryption - encrypting data for e-passport holders
Venue: arXiv cs.CR 2017
Year: 2017

We show how any party can encrypt data for an e-passport holder such that only with physical possession of the e-passport decryption is possible. The same is possible for electronic identity cards and driver licenses. We also indicate possible applications. Dutch passports allow for 160 bit security, theoretically giving sufficient security beyond the year 2079, exceeding current good practice of 128 bit security. We also introduce the notion of RDE Extraction PIN which effectively provides the same security as a regular PIN. Our results ironically suggest that carrying a passport when traveling abroad might violate export or import laws on strong cryptography.
CALF: Categorical Automata Learning Framework
Venue: arXiv cs.FL 2017
Year: 2017

Automata learning is a technique that has successfully been applied in verification, with the automaton type varying depending on the application domain. Adaptations of automata learning algorithms for increasingly complex types of automata have to be developed from scratch because there was no abstract theory offering guidelines. This makes it hard to devise such algorithms, and it obscures their correctness proofs. We introduce a simple category-theoretic formalism that provides an appropriately abstract foundation for studying automata learning. Furthermore, our framework establishes formal relations between algorithms for learning, testing, and minimization. We illustrate its generality with two examples: deterministic and weighted automata.
A Distributed Scheduling Algorithm to Provide Quality-of-Service in Multihop Wireless Networks
Venue: arXiv cs.NI 2017
Year: 2017

Control of multihop Wireless networks in a distributed manner while providing end-to-end delay requirements for different flows, is a challenging problem. Using the notions of Draining Time and Discrete Review from the theory of fluid limits of queues, an algorithm that meets delay requirements to various flows in a network is constructed. The algorithm involves an optimization which is implemented in a cyclic distributed manner across nodes by using the technique of iterative gradient ascent, with minimal information exchange between nodes. The algorithm uses time varying weights to give priority to flows. The performance of the algorithm is studied in a network with interference modelled by independent sets.
A multi-method simulation of a high-frequency bus line using AnyLogic
Venue: arXiv cs.AI 2017
Year: 2017

In this work a mixed agent-based and discrete event simulation model is developed for a high frequency bus route in the Netherlands. With this model, different passenger growth scenarios can be easily evaluated. This simulation model helps policy makers to predict changes that have to be made to bus routes and planned travel times before problems occur. The model is validated using several performance indicators, showing that under some model assumptions, it can realistically simulate real-life situations. The simulation's workings are illustrated by two use cases.
$β$-expansion: A Theoretical Framework for Fast and Recursive Construction of Polar Codes
Venue: arXiv cs.IT 2017
Year: 2017

In this work, we introduce $β$-expansion, a notion borrowed from number theory, as a theoretical framework to study fast construction of polar codes based on a recursive structure of universal partial order (UPO) and polarization weight (PW) algorithm. We show that polar codes can be recursively constructed from UPO by continuously solving several polynomial equations at each recursive step. From these polynomial equations, we can extract an interval for $β$, such that ranking the synthetic channels through a closed-form $β$-expansion preserves the property of nested frozen sets, which is a desired feature for low-complex construction. In an example of AWGN channels, we show that this interval for $β$ converges to a constant close to $1.1892 \approx 2^{1/4}$ when the code block-length trends to infinity. Both asymptotic analysis and simulation results validate our theoretical claims.
How Long It Takes for an Ordinary Node with an Ordinary ID to Output?
Venue: arXiv cs.DC 2017
Year: 2017

In the context of distributed synchronous computing, processors perform in rounds, and the time-complexity of a distributed algorithm is classically defined as the number of rounds before all computing nodes have output. Hence, this complexity measure captures the running time of the slowest node(s). In this paper, we are interested in the running time of the ordinary nodes, to be compared with the running time of the slowest nodes. The node-averaged time-complexity of a distributed algorithm on a given instance is defined as the average, taken over every node of the instance, of the number of rounds before that node output. We compare the node-averaged time-complexity with the classical one in the standard LOCAL model for distributed network computing. We show that there can be an exponential gap between the node-averaged time-complexity and the classical time-complexity, as witnessed by, e.g., leader election. Our first main result is a positive one, stating that, in fact, the two time-complexities behave the same for a large class of problems on very sparse graphs. In particular, we show that, for LCL problems on cycles, the node-averaged time complexity is of the same order of magnitude as the slowest node time-complexity. In addition, in the LOCAL model, the time-complexity is computed as a worst case over all possible identity assignments to the nodes of the network. In this paper, we also investigate the ID-averaged time-complexity, when the number of rounds is averaged over all possible identity assignments. Our second main result is that the ID-averaged time-complexity is essentially the same as the expected time-complexity of randomized algorithms (where the expectation is taken over all possible random bits used by the nodes, and the number of rounds is measured for the worst-case identity assignment). Finally, we study the node-averaged ID-averaged time-complexity.
Study of Anomaly Detection Based on Randomized Subspace Methods in IP Networks
Venue: arXiv cs.IT 2017
Year: 2017

In this paper we propose novel randomized subspace methods to detect anomalies in Internet Protocol networks. Given a data matrix containing information about network traffic, the proposed approaches perform a normal-plus-anomalous matrix decomposition aided by random subspace techniques and subsequently detect traffic anomalies in the anomalous subspace using a statistical test. Experimental results demonstrate improvement over the traditional principal component analysis-based subspace methods in terms of robustness to noise and detection rate.
Positive Semidefiniteness and Positive Definiteness of a Linear Parametric Interval Matrix
Venue: arXiv cs.NA 2017
Year: 2017

We consider a symmetric matrix, the entries of which depend linearly on some parameters. The domains of the parameters are compact real intervals. We investigate the problem of checking whether for each (or some) setting of the parameters, the matrix is positive definite (or positive semidefinite). We state a characterization in the form of equivalent conditions, and also propose some computationally cheap sufficient\,/\,necessary conditions. Our results extend the classical results on positive (semi-)definiteness of interval matrices. They may be useful for checking convexity or non-convexity in global optimization methods based on branch and bound framework and using interval techniques.
Geant4 Maintainability Assessed with Respect to Software Engineering References
Venue: arXiv cs.SE 2017
Year: 2017

We report a methodology developed to quantitatively assess the maintainability of Geant4 with respect to software engineering references. The level of maintainability is determined by combining a set of metrics values whose references are documented in literature.
SLAM with Objects using a Nonparametric Pose Graph
Venue: arXiv cs.CV 2017
Year: 2017

Mapping and self-localization in unknown environments are fundamental capabilities in many robotic applications. These tasks typically involve the identification of objects as unique features or landmarks, which requires the objects both to be detected and then assigned a unique identifier that can be maintained when viewed from different perspectives and in different images. The \textit{data association} and \textit{simultaneous localization and mapping} (SLAM) problems are, individually, well-studied in the literature. But these two problems are inherently tightly coupled, and that has not been well-addressed. Without accurate SLAM, possible data associations are combinatorial and become intractable easily. Without accurate data association, the error of SLAM algorithms diverge easily. This paper proposes a novel nonparametric pose graph that models data association and SLAM in a single framework. An algorithm is further introduced to alternate between inferring data association and performing SLAM. Experimental results show that our approach has the new capability of associating object detections and localizing objects at the same time, leading to significantly better performance on both the data association and SLAM problems than achieved by considering only one and ignoring imperfections in the other.
Genetic Algorithm Based Floor Planning System
Venue: arXiv cs.NE 2017
Year: 2017

Genetic Algorithms are widely used in many different optimization problems including layout design. The layout of the shelves play an important role in the total sales metrics for superstores since this affects the customers' shopping behaviour. This paper employed a genetic algorithm based approach to design shelf layout of superstores. The layout design problem was tackled by using a novel chromosome representation which takes many different parameters to prevent dead-ends and improve shelf visibility into consideration. Results show that the approach can produce reasonably good layout designs in very short amounts of time.
Understanding the Mechanisms of Deep Transfer Learning for Medical Images
Venue: arXiv cs.CV 2017
Year: 2017

The ability to automatically learn task specific feature representations has led to a huge success of deep learning methods. When large training data is scarce, such as in medical imaging problems, transfer learning has been very effective. In this paper, we systematically investigate the process of transferring a Convolutional Neural Network, trained on ImageNet images to perform image classification, to kidney detection problem in ultrasound images. We study how the detection performance depends on the extent of transfer. We show that a transferred and tuned CNN can outperform a state-of-the-art feature engineered pipeline and a hybridization of these two techniques achieves 20\% higher performance. We also investigate how the evolution of intermediate response images from our network. Finally, we compare these responses to state-of-the-art image processing filters in order to gain greater insight into how transfer learning is able to effectively manage widely varying imaging regimes.