OpenRaiser/Intern-Atlas huggingface dataset:
A Linear-time Algorithm for Orthogonal Watchman Route Problem with Minimum Bends
Venue: arXiv cs.CG 2017
Year: 2017

Given an orthogonal polygon $ P $ with $ n $ vertices, the goal of the watchman route problem is finding a path $ S $ of the minimum length in $ P $ such that every point of the polygon $ P $ is visible from at least one of the point of $ S $. In the other words, in the watchman route problem we must compute a shortest watchman route inside a simple polygon of $ n $ vertices such that all the points interior to the polygon and on its boundary are visible to at least one point on the route. If route and polygon be orthogonal, it is called orthogonal watchman route problem. One of the targets of this problem is finding the orthogonal path with the minimum number of bends as possible. We present a linear-time algorithm for the orthogonal watchman route problem, in which the given polygon is monotone. Our algorithm can be used also for the problem on simple orthogonal polygons $ P $ for which the dual graph induced by the vertical decomposition of $ P $ is a path, which is called path polygon.
Massively Multilingual Neural Grapheme-to-Phoneme Conversion
Venue: arXiv cs.CL 2017
Year: 2017

Grapheme-to-phoneme conversion (g2p) is necessary for text-to-speech and automatic speech recognition systems. Most g2p systems are monolingual: they require language-specific data or handcrafting of rules. Such systems are difficult to extend to low resource languages, for which data and handcrafted rules are not available. As an alternative, we present a neural sequence-to-sequence approach to g2p which is trained on spelling--pronunciation pairs in hundreds of languages. The system shares a single encoder and decoder across all languages, allowing it to utilize the intrinsic similarities between different writing systems. We show an 11% improvement in phoneme error rate over an approach based on adapting high-resource monolingual g2p models to low-resource languages. Our model is also much more compact relative to previous approaches.
LIKWID Monitoring Stack: A flexible framework enabling job specific performance monitoring for the masses
Venue: arXiv cs.DC 2017
Year: 2017

System monitoring is an established tool to measure the utilization and health of HPC systems. Usually system monitoring infrastructures make no connection to job information and do not utilize hardware performance monitoring (HPM) data. To increase the efficient use of HPC systems automatic and continuous performance monitoring of jobs is an essential component. It can help to identify pathological cases, provides instant performance feedback to the users, offers initial data to judge on the optimization potential of applications and helps to build a statistical foundation about application specific system usage. The LIKWID monitoring stack is a modular framework build on top of the LIKWID tools library. It aims on enabling job specific performance monitoring using HPM data, system metrics and application-level data for small to medium sized commodity clusters. Moreover, it is designed to integrate in existing monitoring infrastructures to speed up the change from pure system monitoring to job-aware monitoring.
Localization of Electrical Flows
Venue: arXiv cs.DS 2017
Year: 2017

We show that in any graph, the average length of a flow path in an electrical flow between the endpoints of a random edge is $O(\log^2 n)$. This is a consequence of a more general result which shows that the spectral norm of the entrywise absolute value of the transfer impedance matrix of a graph is $O(\log^2 n)$. This result implies a simple oblivious routing scheme based on electrical flows in the case of transitive graphs.
Scoped Extension Methods in Dynamically-Typed Languages
Venue: arXiv cs.PL 2017
Year: 2017

Context. An extension method is a method declared in a package other than the package of its host class. Thanks to extension methods, developers can adapt to their needs classes they do not own: adding methods to core classes is a typical use case. This is particularly useful for adapting software and therefore to increase reusability. Inquiry. In most dynamically-typed languages, extension methods are globally visible. Because any developer can define extension methods for any class, naming conflicts occur: if two developers define an extension method with the same signature in the same class, only one extension method is visible and overwrites the other. Similarly, if two developers each define an extension method with the same name in a class hierarchy, one overrides the other. To avoid such "accidental overrides", some dynamically-typed languages limit the visibility of an extension method to a particular scope. However, their semantics have not been fully described and compared. In addition, these solutions typically rely on a dedicated and slow method lookup algorithm to resolve conflicts at runtime. Approach. In this article, we present a formalization of the underlying models of Ruby refinements, Groovy categories, Classboxes, and Method Shelters that are scoping extension method solutions in dynamically-typed languages. Knowledge. Our formal framework allows us to objectively compare and analyze the shortcomings of the studied solutions and other different approaches such as MultiJava. In addition, language designers can use our formal framework to determine which mechanism has less risk of "accidental overrides". Grounding. Our comparison and analysis of existing solutions is grounded because it is based on denotational semantics formalizations. Importance. Extension methods are widely used in programming languages that support them, especially dynamically-typed languages such as Pharo, Ruby or Python. However, without a carefully designed mechanism, this feature can cause insidious hidden bugs or can be voluntarily used to gain access to protected operations, violate encapsulation or break fundamental invariants.
Adversarial Robustness: Softmax versus Openmax
Venue: arXiv cs.CV 2017
Year: 2017

Deep neural networks (DNNs) provide state-of-the-art results on various tasks and are widely used in real world applications. However, it was discovered that machine learning models, including the best performing DNNs, suffer from a fundamental problem: they can unexpectedly and confidently misclassify examples formed by slightly perturbing otherwise correctly recognized inputs. Various approaches have been developed for efficiently generating these so-called adversarial examples, but those mostly rely on ascending the gradient of loss. In this paper, we introduce the novel logits optimized targeting system (LOTS) to directly manipulate deep features captured at the penultimate layer. Using LOTS, we analyze and compare the adversarial robustness of DNNs using the traditional Softmax layer with Openmax, which was designed to provide open set recognition by defining classes derived from deep representations, and is claimed to be more robust to adversarial perturbations. We demonstrate that Openmax provides less vulnerable systems than Softmax to traditional attacks, however, we show that it can be equally susceptible to more sophisticated adversarial generation techniques that directly work on deep representations.
Integration of Ether Unpacker into Ragpicker for plugin-based Malware Analysis and Identification
Venue: arXiv cs.CR 2017
Year: 2017

Malware is a pervasive problem in both personal computing devices and distributed computing systems. Identification of malware variants and their families others a great benefit in early detection resulting in a reduction of the analyses time needed. In order to classify malware, most of the current approaches are based on the analysis of the unpacked and unencrypted binaries. However, most of the unpacking solutions in the literature have a low unpacking rate. This results in a low contribution towards the identification of transferred code and re-used code. To develop a new malware analysis solution based on clusters of binary code sections, it is required to focus on increasing of the unpacking rate of malware samples to extend the underlying code database. In this paper, we present a new approach of analysing malware by integrating Ether Unpacker into the plugin-based malware analysis tool, Ragpicker. We also evaluate our approach against real-world malware patterns.
ComplementMe: Weakly-Supervised Component Suggestions for 3D Modeling
Venue: arXiv cs.GR 2017
Year: 2017

Assembly-based tools provide a powerful modeling paradigm for non-expert shape designers. However, choosing a component from a large shape repository and aligning it to a partial assembly can become a daunting task. In this paper we describe novel neural network architectures for suggesting complementary components and their placement for an incomplete 3D part assembly. Unlike most existing techniques, our networks are trained on unlabeled data obtained from public online repositories, and do not rely on consistent part segmentations or labels. Absence of labels poses a challenge in indexing the database of parts for the retrieval. We address it by jointly training embedding and retrieval networks, where the first indexes parts by mapping them to a low-dimensional feature space, and the second maps partial assemblies to appropriate complements. The combinatorial nature of part arrangements poses another challenge, since the retrieval network is not a function: several complements can be appropriate for the same input. Thus, instead of predicting a single output, we train our network to predict a probability distribution over the space of part embeddings. This allows our method to deal with ambiguities and naturally enables a UI that seamlessly integrates user preferences into the design process. We demonstrate that our method can be used to design complex shapes with minimal or no user input. To evaluate our approach we develop a novel benchmark for component suggestion systems demonstrating significant improvement over state-of-the-art techniques.
Automated Assessment of Facial Wrinkling: a case study on the effect of smoking
Venue: arXiv cs.CV 2017
Year: 2017

Facial wrinkle is one of the most prominent biological changes that accompanying the natural aging process. However, there are some external factors contributing to premature wrinkles development, such as sun exposure and smoking. Clinical studies have shown that heavy smoking causes premature wrinkles development. However, there is no computerised system that can automatically assess the facial wrinkles on the whole face. This study investigates the effect of smoking on facial wrinkling using a social habit face dataset and an automated computerised computer vision algorithm. The wrinkles pattern represented in the intensity of 0-255 was first extracted using a modified Hybrid Hessian Filter. The face was divided into ten predefined regions, where the wrinkles in each region was extracted. Then the statistical analysis was performed to analyse which region is effected mainly by smoking. The result showed that the density of wrinkles for smokers in two regions around the mouth was significantly higher than the non-smokers, at p-value of 0.05. Other regions are inconclusive due to lack of large scale dataset. Finally, the wrinkle was visually compared between smoker and non-smoker faces by generating a generic 3D face model.
A combination chaotic system and application in color image encryption
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, by using Logistic, Sine and Tent systems we define a combination chaotic system. Some properties of the chaotic system are studied by using figures and numerical results. A color image encryption algorithm is introduced based on new chaotic system. Also this encryption algorithm can be used for gray scale or binary images. The experimental results of the encryption algorithm show that the encryption algorithm is secure and practical.
Pattern Generation for Walking on Slippery Terrains
Venue: arXiv cs.RO 2017
Year: 2017

In this paper, we extend state of the art Model Predictive Control (MPC) approaches to generate safe bipedal walking on slippery surfaces. In this setting, we formulate walking as a trade off between realizing a desired walking velocity and preserving robust foot-ground contact. Exploiting this formulation inside MPC, we show that safe walking on various flat terrains can be achieved by compromising three main attributes, i. e. walking velocity tracking, the Zero Moment Point (ZMP) modulation, and the Required Coefficient of Friction (RCoF) regulation. Simulation results show that increasing the walking velocity increases the possibility of slippage, while reducing the slippage possibility conflicts with reducing the tip-over possibility of the contact and vice versa.
Practically efficient methods for performing bit-reversed permutation in C++11 on the x86-64 architecture
Venue: arXiv cs.MS 2017
Year: 2017

The bit-reversed permutation is a famous task in signal processing and is key to efficient implementation of the fast Fourier transform. This paper presents optimized C++11 implementations of five extant methods for computing the bit-reversed permutation: Stockham auto-sort, naive bitwise swapping, swapping via a table of reversed bytes, local pairwise swapping of bits, and swapping via a cache-localized matrix buffer. Three new strategies for performing the bit-reversed permutation in C++11 are proposed: an inductive method using the bitwise XOR operation, a template-recursive closed form, and a cache-oblivious template-recursive approach, which reduces the bit-reversed permutation to smaller bit-reversed permutations and a square matrix transposition. These new methods are compared to the extant approaches in terms of theoretical runtime, empirical compile time, and empirical runtime. The template-recursive cache-oblivious method is shown to be competitive with the fastest known method; however, we demonstrate that the cache-oblivious method can more readily benefit from parallelization on multiple cores and on the GPU.
Using Continuous Power Modulation for Exchanging Local Channel State Information
Venue: arXiv cs.NI 2017
Year: 2017

This letter provides a simple but efficient technique, which allows each transmitter of an interference network, to exchange local channel state information with the other transmitters. One salient feature of the proposed technique is that a transmitter only needs measurements of the signal power at its intended receiver to implement it, making direct inter-transmitter signaling channels unnecessary. The key idea to achieve this is to use a transient period during which the continuous power level of a transmitter is taken to be the linear combination of the channel gains to be exchanged.
Measuring Catastrophic Forgetting in Neural Networks
Venue: arXiv cs.AI 2017
Year: 2017

Deep neural networks are used in many state-of-the-art systems for machine perception. Once a network is trained to do a specific task, e.g., bird classification, it cannot easily be trained to do new tasks, e.g., incrementally learning to recognize additional bird species or learning an entirely different task such as flower recognition. When new tasks are added, typical deep neural networks are prone to catastrophically forgetting previous tasks. Networks that are capable of assimilating new information incrementally, much like how humans form new memories over time, will be more efficient than re-training the model from scratch each time a new task needs to be learned. There have been multiple attempts to develop schemes that mitigate catastrophic forgetting, but these methods have not been directly compared, the tests used to evaluate them vary considerably, and these methods have only been evaluated on small-scale problems (e.g., MNIST). In this paper, we introduce new metrics and benchmarks for directly comparing five different mechanisms designed to mitigate catastrophic forgetting in neural networks: regularization, ensembling, rehearsal, dual-memory, and sparse-coding. Our experiments on real-world images and sounds show that the mechanism(s) that are critical for optimal performance vary based on the incremental training paradigm and type of data being used, but they all demonstrate that the catastrophic forgetting problem has yet to be solved.
Regularizing and Optimizing LSTM Language Models
Venue: arXiv cs.CL 2017
Year: 2017

Recurrent neural networks (RNNs), such as long short-term memory networks (LSTMs), serve as a fundamental building block for many sequence learning tasks, including machine translation, language modeling, and question answering. In this paper, we consider the specific problem of word-level language modeling and investigate strategies for regularizing and optimizing LSTM-based models. We propose the weight-dropped LSTM which uses DropConnect on hidden-to-hidden weights as a form of recurrent regularization. Further, we introduce NT-ASGD, a variant of the averaged stochastic gradient method, wherein the averaging trigger is determined using a non-monotonic condition as opposed to being tuned by the user. Using these and other regularization strategies, we achieve state-of-the-art word level perplexities on two data sets: 57.3 on Penn Treebank and 65.8 on WikiText-2. In exploring the effectiveness of a neural cache in conjunction with our proposed model, we achieve an even lower state-of-the-art perplexity of 52.8 on Penn Treebank and 52.0 on WikiText-2.
Adaptive Lock-Free Data Structures in Haskell: A General Method for Concurrent Implementation Swapping
Venue: arXiv cs.PL 2017
Year: 2017

A key part of implementing high-level languages is providing built-in and default data structures. Yet selecting good defaults is hard. A mutable data structure's workload is not known in advance, and it may shift over its lifetime - e.g., between read-heavy and write-heavy, or from heavy contention by multiple threads to single-threaded or low-frequency use. One idea is to switch implementations adaptively, but it is nontrivial to switch the implementation of a concurrent data structure at runtime. Performing the transition requires a concurrent snapshot of data structure contents, which normally demands special engineering in the data structure's design. However, in this paper we identify and formalize an relevant property of lock-free algorithms. Namely, lock-freedom is sufficient to guarantee that freezing memory locations in an arbitrary order will result in a valid snapshot. Several functional languages have data structures that freeze and thaw, transitioning between mutable and immutable, such as Haskell vectors and Clojure transients, but these enable only single-threaded writers. We generalize this approach to augment an arbitrary lock-free data structure with the ability to gradually freeze and optionally transition to a new representation. This augmentation doesn't require changing the algorithm or code for the data structure, only replacing its datatype for mutable references with a freezable variant. In this paper, we present an algorithm for lifting plain to adaptive data and prove that the resulting hybrid data structure is itself lock-free, linearizable, and simulates the original. We also perform an empirical case study in the context of heating up and cooling down concurrent maps.
On the Learnability of Programming Language Semantics
Venue: arXiv cs.PL 2017
Year: 2017

Game semantics is a powerful method of semantic analysis for programming languages. It gives mathematically accurate models ("fully abstract") for a wide variety of programming languages. Game semantic models are combinatorial characterisations of all possible interactions between a term and its syntactic context. Because such interactions can be concretely represented as sets of sequences, it is possible to ask whether they can be learned from examples. Concretely, we are using long short-term memory neural nets (LSTM), a technique which proved effective in learning natural languages for automatic translation and text synthesis, to learn game-semantic models of sequential and concurrent versions of Idealised Algol (IA), which are algorithmically complex yet can be concisely described. We will measure how accurate the learned models are as a function of the degree of the term and the number of free variables involved. Finally, we will show how to use the learned model to perform latent semantic analysis between concurrent and sequential Idealised Algol.
Self-triggering in Vehicular Networked Systems with State-dependent Bursty Fading Channels
Venue: arXiv cs.SY 2017
Year: 2017

Vehicular Networked Systems (VNS) are mobile ad hoc networks where vehicles exchange information over wireless communication networks to ensure safe and efficient operation. It is, however, challenging to ensure system safety and efficiency as the wireless channels in VNS are often subject to state-dependent deep fades where the data rate suffers a severe drop and changes as a function of vehicle states. Such couplings between vehicle states and channel states in VNS thereby invalidate the use of separation principle to design event-based control strategies. By adopting a state-dependent fading channel model that was proposed to capture the interaction between vehicle and channel states, this paper presents a novel self-triggered scheme under which the VNS ensures efficient use of communication bandwidth while preserving stochastic stability. The novelty of the proposed scheme lies in its use of the state-dependent fading channel model in the event design that enables an adaptive and effective adjustment on transmission frequency in response to dynamic variations on channel and vehicle states. Under the proposed self-triggered scheme, this paper presents a novel source coding scheme that tracks vehicle's states with performance guarantee in the presence of state-dependent fading channels. The efficacy and advantages of the proposed scheme over other event-based strategies are verified through both simulation and experimental results of a leader-follower example.
2D SLAM Quality Evaluation Methods
Venue: arXiv cs.RO 2017
Year: 2017

SLAM (Simultaneous Localization and mapping) is one of the most challenging problems for mobile platforms and there is a huge amount of modern SLAM algorithms. The choice of the algorithm that might be used in every particular problem requires prior knowledge about advantages and disadvantages of each algorithm. This paper presents the approach for comparison of SLAM algorithms that allows to find the most accurate one. The accent of research is made on 2D SLAM algorithms and the focus of analysis is 2D map that is built after algorithm performance. Three metrics for evaluation of maps are presented in this paper
Learning a Repression Network for Precise Vehicle Search
Venue: arXiv cs.CV 2017
Year: 2017

The growing explosion in the use of surveillance cameras in public security highlights the importance of vehicle search from large-scale image databases. Precise vehicle search, aiming at finding out all instances for a given query vehicle image, is a challenging task as different vehicles will look very similar to each other if they share same visual attributes. To address this problem, we propose the Repression Network (RepNet), a novel multi-task learning framework, to learn discriminative features for each vehicle image from both coarse-grained and detailed level simultaneously. Besides, benefited from the satisfactory accuracy of attribute classification, a bucket search method is proposed to reduce the retrieval time while still maintaining competitive performance. We conduct extensive experiments on the revised VehcileID dataset. Experimental results show that our RepNet achieves the state-of-the-art performance and the bucket search method can reduce the retrieval time by about 24 times.