OpenRaiser/Intern-Atlas huggingface dataset:
Mapping Patent Classifications: Portfolio and Statistical Analysis, and the Comparison of Strengths and Weaknesses
Venue: arXiv cs.DL 2017
Year: 2017

The Cooperative Patent Classifications (CPC) jointly developed by the European and US Patent Offices provide a new basis for mapping and portfolio analysis. This update provides an occasion for rethinking the parameter choices. The new maps are significantly different from previous ones, although this may not always be obvious on visual inspection. Since these maps are statistical constructs based on index terms, their quality--as different from utility--can only be controlled discursively. We provide nested maps online and a routine for portfolio overlays and further statistical analysis. We add a new tool for "difference maps" which is illustrated by comparing the portfolios of patents granted to Novartis and MSD in 2016.
Featured Weighted Automata
Venue: arXiv cs.FL 2017
Year: 2017

A featured transition system is a transition system in which the transitions are annotated with feature expressions: Boolean expressions on a finite number of given features. Depending on its feature expression, each individual transition can be enabled when some features are present, and disabled for other sets of features. The behavior of a featured transition system hence depends on a given set of features. There are algorithms for featured transition systems which can check their properties for all sets of features at once, for example for LTL or CTL properties. Here we introduce a model of featured weighted automata which combines featured transition systems and (semiring-) weighted automata. We show that methods and techniques from weighted automata extend to featured weighted automata and devise algorithms to compute quantitative properties of featured weighted automata for all sets of features at once. We show applications to minimum reachability and to energy properties.
A generalization of crossing families
Venue: arXiv cs.CG 2017
Year: 2017

For a set of points in the plane, a \emph{crossing family} is a set of line segments, each joining two of the points, such that any two line segments cross. We investigate the following generalization of crossing families: a \emph{spoke set} is a set of lines drawn through a point set such that each unbounded region of the induced line arrangement contains at least one point of the point set. We show that every point set has a spoke set of size $\sqrt{\frac{n}{8}}$. We also characterize the matchings obtained by selecting exactly one point in each unbounded region and connecting every such point to the point in the antipodal unbounded region.
Simple, Fast and Lightweight Parallel Wavelet Tree Construction
Venue: arXiv cs.DS 2017
Year: 2017

The wavelet tree (Grossi et al. [SODA, 2003]) and wavelet matrix (Claude et al. [Inf. Syst., 47:15--32, 2015]) are compact indices for texts over an alphabet $[0,σ)$ that support rank, select and access queries in $O(\lg σ)$ time. We first present new practical sequential and parallel algorithms for wavelet tree construction. Their unifying characteristics is that they construct the wavelet tree bottomup}, i.e., they compute the last level first. We also show that this bottom-up construction can easily be adapted to wavelet matrices. In practice, our best sequential algorithm is up to twice as fast as the currently fastest sequential wavelet tree construction algorithm (Shun [DCC, 2015]), simultaneously saving a factor of 2 in space. This scales up to 32 cores, where we are about equally fast as the currently fastest parallel wavelet tree construction algorithm (Labeit et al. [DCC, 2016]), but still use only about 75 % of the space. An additional theoretical result shows how to adapt any wavelet tree construction algorithm to the wavelet matrix in the same (asymptotic) time, using only little extra space.
Compact Self-Stabilizing Leader Election for Arbitrary Networks
Venue: arXiv cs.DC 2017
Year: 2017

We present a self-stabilizing leader election algorithm for arbitrary networks, with space-complexity $O(\max\{\log Δ, \log \log n\})$ bits per node in $n$-node networks with maximum degree~$Δ$. This space complexity is sub-logarithmic in $n$ as long as $Δ= n^{o(1)}$. The best space-complexity known so far for arbitrary networks was $O(\log n)$ bits per node, and algorithms with sub-logarithmic space-complexities were known for the ring only. To our knowledge, our algorithm is the first algorithm for self-stabilizing leader election to break the $Ω(\log n)$ bound for silent algorithms in arbitrary networks. Breaking this bound was obtained via the design of a (non-silent) self-stabilizing algorithm using sophisticated tools such as solving the distance-2 coloring problem in a silent self-stabilizing manner, with space-complexity $O(\max\{\log Δ, \log \log n\})$ bits per node. Solving this latter coloring problem allows us to implement a sub-logarithmic encoding of spanning trees --- storing the IDs of the neighbors requires $Ω(\log n)$ bits per node, while we encode spanning trees using $O(\max\{\log Δ, \log \log n\})$ bits per node. Moreover, we show how to construct such compactly encoded spanning trees without relying on variables encoding distances or number of nodes, as these two types of variables would also require $Ω(\log n)$ bits per node.
How ConvNets model Non-linear Transformations
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we theoretically address three fundamental problems involving deep convolutional networks regarding invariance, depth and hierarchy. We introduce the paradigm of Transformation Networks (TN) which are a direct generalization of Convolutional Networks (ConvNets). Theoretically, we show that TNs (and thereby ConvNets) are can be invariant to non-linear transformations of the input despite pooling over mere local translations. Our analysis provides clear insights into the increase in invariance with depth in these networks. Deeper networks are able to model much richer classes of transformations. We also find that a hierarchical architecture allows the network to generate invariance much more efficiently than a non-hierarchical network. Our results provide useful insight into these three fundamental problems in deep learning using ConvNets.
Practical Magick with C, PDL, and PDL::PP -- a guide to compiled add-ons for PDL
Venue: arXiv cs.PL 2017
Year: 2017

This guide is intended to knit together, and extend, the existing PP and C documentation on PDL internals. It draws heavily from prior work by the authors of the code. Special thanks go to Christian Soeller, and Tuomas Lukka, who together with Glazebrook conceived and implemented PDL and PP; and to Chris Marshall, who has led the PDL development team through several groundbreaking releases and to new levels of usability.
Near-Data Scheduling for Data Centers with Multiple Levels of Data Locality
Venue: arXiv cs.DC 2017
Year: 2017

Data locality is a fundamental issue for data-parallel applications. Considering MapReduce in Hadoop, the map task scheduling part requires an efficient algorithm which takes data locality into consideration; otherwise, the system may become unstable under loads inside the system's capacity region and jobs may experience longer completion times which are not of interest. The data chunk needed for any map task can be in memory, on a local disk, in a local rack, in the same cluster or even in another data center. Hence, unless there has been much work on improving the speed of data center networks, different levels of service rates still exist for a task depending on where its data chunk is saved and from which server it receives service. Most of the theoretical work on load balancing is for systems with two levels of data locality including the Pandas algorithm by Xie et al. and the JSQ-MW algorithm by Wang et al., where the former is both throughput and heavy-traffic optimal, while the latter is only throughput optimal, but heavy-traffic optimal in only a special traffic load. We show that an extension of the JSQ-MW algorithm for a system with thee levels of data locality is throughput optimal, but not heavy-traffic optimal for all loads, only for a special traffic scenario. Furthermore, we show that the Pandas algorithm is not even throughput optimal for a system with three levels of data locality. We then propose a novel algorithm, Balanced-Pandas, which is both throughput and heavy-traffic optimal. To the best of our knowledge, this is the first theoretical work on load balancing for a system with more than two levels of data locality. This is more challenging than two levels of data locality as a dilemma between performance and throughput emerges.
Critical Survey of the Freely Available Arabic Corpora
Venue: arXiv cs.CL 2017
Year: 2017

The availability of corpora is a major factor in building natural language processing applications. However, the costs of acquiring corpora can prevent some researchers from going further in their endeavours. The ease of access to freely available corpora is urgent needed in the NLP research community especially for language such as Arabic. Currently, there is not easy was to access to a comprehensive and updated list of freely available Arabic corpora. We present in this paper, the results of a recent survey conducted to identify the list of the freely available Arabic corpora and language resources. Our preliminary results showed an initial list of 66 sources. We presents our findings in the various categories studied and we provided the direct links to get the data when possible.
Automated Verification and Synthesis of Embedded Systems using Machine Learning
Venue: arXiv cs.LO 2017
Year: 2017

The dependency on the correct functioning of embedded systems is rapidly growing, mainly due to their wide range of applications, such as micro-grids, automotive device control, health care, surveillance, mobile devices, and consumer electronics. Their structures are becoming more and more complex and now require multi-core processors with scalable shared memory, in order to meet increasing computational power demands. As a consequence, reliability of embedded (distributed) software becomes a key issue during system development, which must be carefully addressed and assured. The present research discusses challenges, problems, and recent advances to ensure correctness and timeliness regarding embedded systems. Reliability issues, in the development of micro-grids and cyber-physical systems, are then considered, as a prominent verification and synthesis application. In particular, machine learning techniques emerge as one of the main approaches to learn reliable implementations of embedded software for achieving a correct-by-construction design.
On the Performance of Wireless Powered Communication With Non-linear Energy Harvesting
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we analyze the performance of a time-slotted multi-antenna wireless powered communication (WPC) system, where a wireless device first harvests radio frequency (RF) energy from a power station (PS) in the downlink to facilitate information transfer to an information receiving station (IRS) in the uplink. The main goal of this paper is to provide insights and guidelines for the design of practical WPC systems. To this end, we adopt a recently proposed parametric non-linear RF energy harvesting (EH) model, which has been shown to accurately model the end-to-end non-linearity of practical RF EH circuits. In order to enhance the RF power transfer efficiency, maximum ratio transmission is adopted at the PS to focus the energy signals on the wireless device. Furthermore, at the IRS, maximum ratio combining is used. We analyze the outage probability and the average throughput of information transfer, assuming Nakagami-$m$ fading uplink and downlink channels. Moreover, we study the system performance as a function of the number of PS transmit antennas, the number of IRS receive antennas, the transmit power of the PS, the fading severity, the transmission rate of the wireless device, and the EH time duration. In addition, we obtain a fixed point equation for the optimal transmission rate and the optimal EH time duration that maximize the asymptotic throughput for high PS transmit powers. All analytical results are corroborated by simulations.
Building up user confidence for the spaceborne derived global and continental land cover products for the Mediterranean region: the case of Thessaly
Venue: arXiv cs.OH 2017
Year: 2017

Across globe and space agencies nations recognize the importance of homogenized land cover information, prone to regular updates, both in the context of thematic and spatial resolutions. Recent sensor advances and the free distribution policy promote the utilization of spaceborne products in an unprecedented pace into an increasingly wider range of applications. Ensuring credibility to the users is a major enabler in this process. To this end this study contributes with a systematic accuracy performance measurement and continental/global land cover layers' inter-comparison moving towards confidence built up. Confidence levels during validation and a weighted overall accuracy assessment were applied. Google Earth imagery was employed to assess the accuracy of three land cover products, i.e., Globeland30, HRLs and CLC 2012, for the years 2010 and 2012. Reported rates indicate a minimum weighted overall accuracy of 84%. Specific classes' performance deviations from the general trend were noted and discussed on the basis of an unbiased sampling approach. By integrating confidence levels during the ground truth annotation, stratified sampling on the several Corine Level 3 subclasses and the weighted overall accuracy assessment, the different aspects of the considered land cover products can be highlighted more objectively.
Coarse Grained Exponential Variational Autoencoders
Venue: arXiv cs.LG 2017
Year: 2017

Variational autoencoders (VAE) often use Gaussian or category distribution to model the inference process. This puts a limit on variational learning because this simplified assumption does not match the true posterior distribution, which is usually much more sophisticated. To break this limitation and apply arbitrary parametric distribution during inference, this paper derives a \emph{semi-continuous} latent representation, which approximates a continuous density up to a prescribed precision, and is much easier to analyze than its continuous counterpart because it is fundamentally discrete. We showcase the proposition by applying polynomial exponential family distributions as the posterior, which are universal probability density function generators. Our experimental results show consistent improvements over commonly used VAE models.
A decentralized algorithm for control of autonomous agents coupled by feasibility constraints
Venue: arXiv cs.MA 2017
Year: 2017

In this paper a decentralized control algorithm for systems composed of $N$ dynamically decoupled agents, coupled by feasibility constraints, is presented. The control problem is divided into $N$ optimal control sub-problems and a communication scheme is proposed to decouple computations. The derivative of the solution of each sub-problem is used to approximate the evolution of the system allowing the algorithm to decentralize and parallelize computations. The effectiveness of the proposed algorithm is shown through simulations in a cooperative driving scenario.
McFSM: Globally Taming Complex Systems
Venue: arXiv cs.SE 2017
Year: 2017

Industrial computing devices, in particular cyber-physical, real-time and safety-critical systems, focus on reacting to external events and the need to cooperate with other devices to create a functional system. They are often implemented with languages that focus on a simple, local description of how a component reacts to external input data and stimuli. Despite the trend in modern software architectures to structure systems into largely independent components, the remaining interdependencies still create rich behavioural dynamics even for small systems. Standard and industrial programming approaches do usually not model or extensively describe the global properties of an entire system. Although a large number of approaches to solve this dilemma have been suggested, it remains a hard and error-prone task to implement systems with complex interdependencies correctly. We introduce multiple coupled finite state machines (McFSMs), a novel mechanism that allows us to model and manage such interdependencies. It is based on a consistent, well-structured and simple global description. A sound theoretical foundation is provided, and associated tools allow us to generate efficient low-level code in various programming languages using model-driven techniques. We also present a domain specific language to express McFSMs and their connections to other systems, to model their dynamic behaviour, and to investigate their efficiency and correctness at compile-time.
Generative Adversarial Active Learning
Venue: arXiv cs.LG 2017
Year: 2017

We propose a new active learning by query synthesis approach using Generative Adversarial Networks (GAN). Different from regular active learning, the resulting algorithm adaptively synthesizes training instances for querying to increase learning speed. We generate queries according to the uncertainty principle, but our idea can work with other active learning principles. We report results from various numerical experiments to demonstrate the effectiveness the proposed approach. In some settings, the proposed algorithm outperforms traditional pool-based approaches. To the best our knowledge, this is the first active learning work using GAN.
Multi-scale Spectrum Sensing in Small-Cell mm-Wave Cognitive Wireless Networks
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, a multi-scale approach to spectrum sensing in cognitive cellular networks is proposed. In order to overcome the huge cost incurred in the acquisition of full network state information, a hierarchical scheme is proposed, based on which local state estimates are aggregated up the hierarchy to obtain aggregate state information at multiple scales, which are then sent back to each cell for local decision making. Thus, each cell obtains fine-grained estimates of the channel occupancies of nearby cells, but coarse-grained estimates of those of distant cells. The performance of the aggregation scheme is studied in terms of the trade-off between the throughput achievable by secondary users and the interference generated by the activity of these secondary users to primary users. In order to account for the irregular structure of interference patterns arising from path loss, shadowing, and blockages, which are especially relevant in millimeter wave networks, a greedy algorithm is proposed to find a multi-scale aggregation tree to optimize the performance. It is shown numerically that this tailored hierarchy outperforms a regular tree construction by 60%.
Exact Random Coding Exponents and Universal Decoders for the Asymmetric Broadcast Channel
Venue: arXiv cs.IT 2017
Year: 2017

This work contains two main contributions concerning the asymmetric broadcast channel. The first is an analysis of the exact random coding error exponents for both users, and the second is the derivation of universal decoders for both users. These universal decoders are certain variants of the maximum mutual information (MMI) universal decoder, which achieve the corresponding random coding exponents of optimal decoding. In addition, we introduce some lower bounds, which involve optimization over very few parameters, unlike the original, exact exponents, which involve minimizations over auxiliary probability distributions. Numerical results for the binary symmetric broadcast channel show improvements over previously derived error exponents for the same model.
A Software Repository and Toolset for Empirical Research
Venue: arXiv cs.SE 2017
Year: 2017

This paper proposes a software repository model together with associated tooling and consists of several complex, open-source GUI driven applications ready to be used in empirical software research. We start by providing the rationale for our repository and criteria that guided us in searching for suitable applications. We detail the model of the repository together with associated artifacts and supportive tooling. We detail current applications in the repository together with ways in which it can be further extended. Finally we provide examples of how our repository facilitates research in software visualization and testing.
Bayesian Nonparametric Unmixing of Hyperspectral Images
Venue: arXiv cs.CV 2017
Year: 2017

Hyperspectral imaging is an important tool in remote sensing, allowing for accurate analysis of vast areas. Due to a low spatial resolution, a pixel of a hyperspectral image rarely represents a single material, but rather a mixture of different spectra. HSU aims at estimating the pure spectra present in the scene of interest, referred to as endmembers, and their fractions in each pixel, referred to as abundances. Today, many HSU algorithms have been proposed, based either on a geometrical or statistical model. While most methods assume that the number of endmembers present in the scene is known, there is only little work about estimating this number from the observed data. In this work, we propose a Bayesian nonparametric framework that jointly estimates the number of endmembers, the endmembers itself, and their abundances, by making use of the Indian Buffet Process as a prior for the endmembers. Simulation results and experiments on real data demonstrate the effectiveness of the proposed algorithm, yielding results comparable with state-of-the-art methods while being able to reliably infer the number of endmembers. In scenarios with strong noise, where other algorithms provide only poor results, the proposed approach tends to overestimate the number of endmembers slightly. The additional endmembers, however, often simply represent noisy replicas of present endmembers and could easily be merged in a post-processing step.
Friends and Enemies of Clinton and Trump: Using Context for Detecting Stance in Political Tweets
Venue: arXiv cs.CL 2017
Year: 2017

Stance detection, the task of identifying the speaker's opinion towards a particular target, has attracted the attention of researchers. This paper describes a novel approach for detecting stance in Twitter. We define a set of features in order to consider the context surrounding a target of interest with the final aim of training a model for predicting the stance towards the mentioned targets. In particular, we are interested in investigating political debates in social media. For this reason we evaluated our approach focusing on two targets of the SemEval-2016 Task6 on Detecting stance in tweets, which are related to the political campaign for the 2016 U.S. presidential elections: Hillary Clinton vs. Donald Trump. For the sake of comparison with the state of the art, we evaluated our model against the dataset released in the SemEval-2016 Task 6 shared task competition. Our results outperform the best ones obtained by participating teams, and show that information about enemies and friends of politicians help in detecting stance towards them.