OpenRaiser/Intern-Atlas huggingface dataset:
A Distributed Algorithm for Training Augmented Complex Adaptive IIR Filters
Venue: arXiv cs.DC 2016
Year: 2016

In this paper we consider the problem of decentralized (distributed) adaptive learning, where the aim of the network is to train the coefficients of a widely linear autoregressive moving average (ARMA) model by measurements collected by the nodes. Such a problem arises in many sensor network-based applications such as target tracking, fast rerouting, data reduction and data aggregation. We assume that each node of the network uses the augmented complex adaptive infinite impulse response (ACAIIR) filter as the learning rule, and nodes interact with each other under an incremental mode of cooperation. Since the proposed algorithm (incremental augmented complex IIR (IACA-IIR) algorithm) relies on the augmented complex statistics, it can be used to model both types of complex-valued signals (proper and improper signals). To evaluate the performance of the proposed algorithm, we use both synthetic and real-world complex signals in our simulations. The results exhibit superior performance of the proposed algorithm over the non-cooperative ACAIIR algorithm.
Hitting times of local and global optima in genetic algorithms with very high selection pressure
Venue: arXiv cs.NE 2016
Year: 2016

The paper is devoted to upper bounds on the expected first hitting times of the sets of local or global optima for non-elitist genetic algorithms with very high selection pressure. The results of this paper extend the range of situations where the upper bounds on the expected runtime are known for genetic algorithms and apply, in particular, to the Canonical Genetic Algorithm. The obtained bounds do not require the probability of fitness-decreasing mutation to be bounded by a constant less than one.
Degrees of Freedom of Spatial Self-Interference Suppression for In-Band Full-Duplex with Inter-node Interference
Venue: arXiv cs.IT 2016
Year: 2016

We study a three-node network with a full-duplex base-station communicating with one uplink and one downlink half-duplex node. In this network, both self-interference and inter-node interference are present. We use an antenna-theory-based channel model to study the spatial degrees of freedom of such network, and study if and how much does spatial isolation outperforms time-division (i.e. half-duplex) counterpart. Using degrees of freedom analysis, we show that spatial isolation outperforms time division, unless the angular spread of the objects that scatters to the intended users is overlapped by the spread of objects that back scatters to the receivers.
Can Machine Generate Traditional Chinese Poetry? A Feigenbaum Test
Venue: arXiv cs.CL 2016
Year: 2016

Recent progress in neural learning demonstrated that machines can do well in regularized tasks, e.g., the game of Go. However, artistic activities such as poem generation are still widely regarded as human's special capability. In this paper, we demonstrate that a simple neural model can imitate human in some tasks of art generation. We particularly focus on traditional Chinese poetry, and show that machines can do as well as many contemporary poets and weakly pass the Feigenbaum Test, a variant of Turing test in professional domains. Our method is based on an attention-based recurrent neural network, which accepts a set of keywords as the theme and generates poems by looking at each keyword during the generation. A number of techniques are proposed to improve the model, including character vector initialization, attention to input and hybrid-style training. Compared to existing poetry generation methods, our model can generate much more theme-consistent and semantic-rich poems.
A Consumer Focused Open Data Platform
Venue: arXiv cs.CY 2016
Year: 2016

Open data has been around for many years but with the advancement of technology and its steady adoption by businesses and governments it promises to create new opportunities for the advancement of society as a whole. Many popular open data platforms have focused on solving the problems faced by the data producer and offers limited support for the data consumers in the way of tools and supported processes for easy access, modeling and mining of data within the various platforms. In this paper we present the specifications for a data consumer oriented platform for open data, the Data-TAP. We demonstrate how this platform is able to (a) meet the goal of leveraging the data resources of existing Open Data platforms, (b) provide a means to standardize and structure data to allow for the merging of related data resources and (c) use a rule-based method for parsing resources. This paper will show how Data-TAP provides an easy to use and understand interface for making open data friendlier for consumers.
Acyclic Games and Iterative Voting
Venue: arXiv cs.MA 2016
Year: 2016

We consider iterative voting models and position them within the general framework of acyclic games and game forms. More specifically, we classify convergence results based on the underlying assumptions on the agent scheduler (the order of players) and the action scheduler (which better-reply is played). Our main technical result is providing a complete picture of conditions for acyclicity in several variations of Plurality voting. In particular, we show that (a) under the traditional lexicographic tie-breaking, the game converges for any order of players under a weak restriction on voters' actions; and (b) Plurality with randomized tie-breaking is not guaranteed to converge under arbitrary agent schedulers, but from any initial state there is \emph{some} path of better-replies to a Nash equilibrium. We thus show a first separation between restricted-acyclicity and weak-acyclicity of game forms, thereby settling an open question from [Kukushkin, IJGT 2011]. In addition, we refute another conjecture regarding strongly-acyclic voting rules.
Can Scientific Impact Be Predicted?
Venue: arXiv cs.DL 2016
Year: 2016

A widely used measure of scientific impact is citations. However, due to their heavy-tailed distribution, citations are fundamentally difficult to predict. Instead, to characterize scientific impact, we address two analogous questions asked by many scientific researchers: "How will my h-index evolve over time, and which of my previously or newly published papers will contribute to it?" To answer these questions, we perform two related tasks. First, we develop a model to predict authors' future h-indices based on their current scientific impact. Second, we examine the factors that drive papers---either previously or newly published---to increase their authors' predicted future h-indices. By leveraging relevant factors, we can predict an author's h-index in five years with an R2 value of 0.92 and whether a previously (newly) published paper will contribute to this future h-index with an F1 score of 0.99 (0.77). We find that topical authority and publication venue are crucial to these effective predictions, while topic popularity is surprisingly inconsequential. Further, we develop an online tool that allows users to generate informed h-index predictions. Our work demonstrates the predictability of scientific impact, and can help scholars to effectively leverage their position of "standing on the shoulders of giants."
How to verify computation with a rational network
Venue: arXiv cs.GT 2016
Year: 2016

The present paper introduces a practical protocol for provably secure, outsourced computation. Our protocol minimizes overhead for verification by requiring solutions to withstand an interactive game between a prover and challenger. For optimization problems, the best or nearly best of all submitted solutions is expected to be accepted by this approach. Financial incentives and deposits are used in order to overcome the problem of fake participants.
Probabilistic estimation of software project duration
Venue: arXiv cs.SE 2016
Year: 2016

This paper presents a framework for the representation of uncertainty in the estimates for software design projects for use throughout the entire project lifecycle. The framework is flexible in order to accommodate uncertainty in the project and utilises Monte Carlo simulation to compute the propagation of uncertainty in effort estimates towards the total project uncertainty and therefore gives a project manager the means to make informed decisions throughout the project life. The framework also provides a mechanism for accumulating project knowledge through the use of a historical database, allowing effort estimates to be informed by, or indeed based upon, the outcome of previous projects. Initial results using simulated data are presented and avenues for further work are discussed.
Adapting ELM to Time Series Classification: A Novel Diversified Top-k Shapelets Extraction Method
Venue: arXiv cs.LG 2016
Year: 2016

ELM (Extreme Learning Machine) is a single hidden layer feed-forward network, where the weights between input and hidden layer are initialized randomly. ELM is efficient due to its utilization of the analytical approach to compute weights between hidden and output layer. However, ELM still fails to output the semantic classification outcome. To address such limitation, in this paper, we propose a diversified top-k shapelets transform framework, where the shapelets are the subsequences i.e., the best representative and interpretative features of each class. As we identified, the most challenge problems are how to extract the best k shapelets in original candidate sets and how to automatically determine the k value. Specifically, we first define the similar shapelets and diversified top-k shapelets to construct diversity shapelets graph. Then, a novel diversity graph based top-k shapelets extraction algorithm named as \textbf{DivTopkshapelets}\ is proposed to search top-k diversified shapelets. Finally, we propose a shapelets transformed ELM algorithm named as \textbf{DivShapELM} to automatically determine the k value, which is further utilized for time series classification. The experimental results over public data sets demonstrate that the proposed approach significantly outperforms traditional ELM algorithm in terms of effectiveness and efficiency.
Formalization of Phase Ordering
Venue: arXiv cs.DC 2016
Year: 2016

Phasers pose an interesting synchronization mechanism that generalizes many collective synchronization patterns seen in parallel programming languages, including barriers, clocks, and point-to-point synchronization using latches or semaphores. This work characterizes scheduling constraints on phaser operations, by relating the execution state of two tasks that operate on the same phaser. We propose a formalization of Habanero phasers, May-Happen-In-Parallel, and Happens-Before relations for phaser operations, and show that these relations conform with the semantics. Our formalization and proofs are fully mechanized using the Coq proof assistant, and are available online.
Event-driven Adaptation in COP
Venue: arXiv cs.PL 2016
Year: 2016

Context-Oriented Programming languages provide us with primitive constructs to adapt program behaviour depending on the evolution of their operational environment, namely the context. In previous work we proposed ML_CoDa, a context-oriented language with two-components: a declarative constituent for programming the context and a functional one for computing. This paper describes an extension of ML_CoDa to deal with adaptation to unpredictable context changes notified by asynchronous events.
Goal Translation for a Hammer for Coq (Extended Abstract)
Venue: arXiv cs.LO 2016
Year: 2016

Hammers are tools that provide general purpose automation for formal proof assistants. Despite the gaining popularity of the more advanced versions of type theory, there are no hammers for such systems. We present an extension of the various hammer components to type theory: (i) a translation of a significant part of the Coq logic into the format of automated proof systems; (ii) a proof reconstruction mechanism based on a Ben-Yelles-type algorithm combined with limited rewriting, congruence closure and a first-order generalization of the left rules of Dyckhoff's system LJT.
Consensus with Output Saturations
Venue: arXiv cs.SY 2016
Year: 2016

This paper consider a standard consensus algorithm under output saturations. In the presence of output saturations, global consensus can not be realized due to the existence of stable, unachievable equilibrium points for the consensus. Therefore, this paper investigates necessary and sufficient initial conditions for the achievement of consensus, that is an exact domain of attraction. Specifically, this paper considers singe-integrator agents with both fixed and time-varying undirected graphs, as well as double-integrator agents with fixed undirected graph. Then, we derive that the consensus will be achieved if and only if the average of the initial states (only velocities for double-integrator agents with homogeneous saturation levels for the outputs) is within the minimum saturation level. An extension to the case of fixed directed graph is also provided in which an weighted average is required to be within the minimum saturation limit.
Modeling and Self-Configuring SaaS Application
Venue: arXiv cs.SE 2016
Year: 2016

The main objectives of SaaS application are to make the management and control of software easier and take the management strain away from consumers. However, it also leads to software services available globally and this has been realized in our paper by designing a new model for SaaS application. The three levels we have classified in our model easy adapted to workflow and services. From the application layers meat-model description we discovered a new algorithm for the self-configuration of SaaS application. We used a feature model to define the variation of our model's management levels. The Xml file obtained from the feature model gave interactive communication between three levels and our new self-configuration algorithm. That increased the performance by selecting from the web a suitable configuration for every level. We have explained all the processes by an online booking example. Finally we present a conclusion and future work.
The Role of CNL and AMR in Scalable Abstractive Summarization for Multilingual Media Monitoring
Venue: arXiv cs.CL 2016
Year: 2016

In the era of Big Data and Deep Learning, there is a common view that machine learning approaches are the only way to cope with the robust and scalable information extraction and summarization. It has been recently proposed that the CNL approach could be scaled up, building on the concept of embedded CNL and, thus, allowing for CNL-based information extraction from e.g. normative or medical texts that are rather controlled by nature but still infringe the boundaries of CNL. Although it is arguable if CNL can be exploited to approach the robust wide-coverage semantic parsing for use cases like media monitoring, its potential becomes much more obvious in the opposite direction: generation of story highlights from the summarized AMR graphs, which is in the focus of this position paper.
Contravening Esotery: Cryptanalysis of Knapsack Cipher using Genetic Algorithms
Venue: arXiv cs.CR 2016
Year: 2016

Cryptanalysis of knapsack cipher is a fascinating problem which has eluded the computing fraternity for decades. However, in most of the cases either the time complexity of the proposed algorithm is colossal or an insufficient number of samples have been taken for verification. The present work proposes a Genetic Algorithm based technique for cryptanalysis of knapsack cipher. The experiments conducted prove the validity of the technique. The results prove that the technique is better than the existing techniques. An extensive review has been carried out in order to find the gaps in the existing techniques. The work paves the way of the application of computational intelligence techniques to the discipline of cryptanalysis.
A Study of Energy and Locality Effects using Space-filling Curves
Venue: arXiv cs.DC 2016
Year: 2016

The cost of energy is becoming an increasingly important driver for the operating cost of HPC systems, adding yet another facet to the challenge of producing efficient code. In this paper, we investigate the energy implications of trading computation for locality using Hilbert and Morton space-filling curves with dense matrix-matrix multiplication. The advantage of these curves is that they exhibit an inherent tiling effect without requiring specific architecture tuning. By accessing the matrices in the order determined by the space-filling curves, we can trade computation for locality. The index computation overhead of the Morton curve is found to be balanced against its locality and energy efficiency, while the overhead of the Hilbert curve outweighs its improvements on our test system.
The Minimum Cost Connected Subgraph Problem in Medical Image Analysis
Venue: arXiv cs.CV 2016
Year: 2016

Several important tasks in medical image analysis can be stated in the form of an optimization problem whose feasible solutions are connected subgraphs. Examples include the reconstruction of neural or vascular structures under connectedness constraints. We discuss the minimum cost connected subgraph (MCCS) problem and its approximations from the perspective of medical applications. We propose a) objective-dependent constraints and b) novel constraint generation schemes to solve this optimization problem exactly by means of a branch-and-cut algorithm. These are shown to improve scalability and allow us to solve instances of two medical benchmark datasets to optimality for the first time. This enables us to perform a quantitative comparison between exact and approximative algorithms, where we identify the geodesic tree algorithm as an excellent alternative to exact inference on the examined datasets.
MOSI: Multimodal Corpus of Sentiment Intensity and Subjectivity Analysis in Online Opinion Videos
Venue: arXiv cs.CL 2016
Year: 2016

People are sharing their opinions, stories and reviews through online video sharing websites every day. Studying sentiment and subjectivity in these opinion videos is experiencing a growing attention from academia and industry. While sentiment analysis has been successful for text, it is an understudied research question for videos and multimedia content. The biggest setbacks for studies in this direction are lack of a proper dataset, methodology, baselines and statistical analysis of how information from different modality sources relate to each other. This paper introduces to the scientific community the first opinion-level annotated corpus of sentiment and subjectivity analysis in online videos called Multimodal Opinion-level Sentiment Intensity dataset (MOSI). The dataset is rigorously annotated with labels for subjectivity, sentiment intensity, per-frame and per-opinion annotated visual features, and per-milliseconds annotated audio features. Furthermore, we present baselines for future studies in this direction as well as a new multimodal fusion approach that jointly models spoken words and visual gestures.
A Data-Driven Approach for Semantic Role Labeling from Induced Grammar Structures in Language
Venue: arXiv cs.CL 2016
Year: 2016

Semantic roles play an important role in extracting knowledge from text. Current unsupervised approaches utilize features from grammar structures, to induce semantic roles. The dependence on these grammars, however, makes it difficult to adapt to noisy and new languages. In this paper we develop a data-driven approach to identifying semantic roles, the approach is entirely unsupervised up to the point where rules need to be learned to identify the position the semantic role occurs. Specifically we develop a modified-ADIOS algorithm based on ADIOS Solan et al. (2005) to learn grammar structures, and use these grammar structures to learn the rules for identifying the semantic roles based on the context in which the grammar structures appeared. The results obtained are comparable with the current state-of-art models that are inherently dependent on human annotated data.
Contextual Weisfeiler-Lehman Graph Kernel For Malware Detection
Venue: arXiv cs.CR 2016
Year: 2016

In this paper, we propose a novel graph kernel specifically to address a challenging problem in the field of cyber-security, namely, malware detection. Previous research has revealed the following: (1) Graph representations of programs are ideally suited for malware detection as they are robust against several attacks, (2) Besides capturing topological neighbourhoods (i.e., structural information) from these graphs it is important to capture the context under which the neighbourhoods are reachable to accurately detect malicious neighbourhoods. We observe that state-of-the-art graph kernels, such as Weisfeiler-Lehman kernel (WLK) capture the structural information well but fail to capture contextual information. To address this, we develop the Contextual Weisfeiler-Lehman kernel (CWLK) which is capable of capturing both these types of information. We show that for the malware detection problem, CWLK is more expressive and hence more accurate than WLK while maintaining comparable efficiency. Through our large-scale experiments with more than 50,000 real-world Android apps, we demonstrate that CWLK outperforms two state-of-the-art graph kernels (including WLK) and three malware detection techniques by more than 5.27% and 4.87% F-measure, respectively, while maintaining high efficiency. This high accuracy and efficiency make CWLK suitable for large-scale real-world malware detection.
A verified abstract machine for functional coroutines
Venue: arXiv cs.LO 2016
Year: 2016

Functional coroutines are a restricted form of control mechanism, where each coroutine is represented with both a continuation and an environment. This restriction was originally obtained by considering a constructive version of Parigot's classical natural deduction which is sound and complete for the Constant Domain logic. In this article, we present a refinement of de Groote's abstract machine for functional coroutines and we prove its correctness. Therefore, this abstract machine also provides a direct computational interpretation of the Constant Domain logic.
A Modular Structural Operational Semantics for Delimited Continuations
Venue: arXiv cs.PL 2016
Year: 2016

It has been an open question as to whether the Modular Structural Operational Semantics framework can express the dynamic semantics of call/cc. This paper shows that it can, and furthermore, demonstrates that it can express the more general delimited control operators control and shift.
The computational content of Nonstandard Analysis
Venue: arXiv cs.LO 2016
Year: 2016

Kohlenbach's proof mining program deals with the extraction of effective information from typically ineffective proofs. Proof mining has its roots in Kreisel's pioneering work on the so-called unwinding of proofs. The proof mining of classical mathematics is rather restricted in scope due to the existence of sentences without computational content which are provable from the law of excluded middle and which involve only two quantifier alternations. By contrast, we show that the proof mining of classical Nonstandard Analysis has a very large scope. In particular, we will observe that this scope includes any theorem of pure Nonstandard Analysis, where `pure' means that only nonstandard definitions (and not the epsilon-delta kind) are used. In this note, we survey results in analysis, computability theory, and Reverse Mathematics.
A Linear Potential Function for Pairing Heaps
Venue: arXiv cs.DS 2016
Year: 2016

We present the first potential function for pairing heaps with linear range. This implies that the runtime of a short sequence of operations is faster than previously known. It is also simpler than the only other potential function known to give amortized constant amortized time for insertion.