OpenRaiser/Intern-Atlas huggingface dataset:
The Partial Entropy Decomposition: Decomposing multivariate entropy and mutual information via pointwise common surprisal
Venue: arXiv cs.IT 2017
Year: 2017

Obtaining meaningful quantitative descriptions of the statistical dependence within multivariate systems is a difficult open problem. Recently, the Partial Information Decomposition (PID) was proposed to decompose mutual information (MI) about a target variable into components which are redundant, unique and synergistic within different subsets of predictor variables. Here, we propose to apply the elegant formalism of the PID to multivariate entropy, resulting in a Partial Entropy Decomposition (PED). We implement the PED with an entropy redundancy measure based on pointwise common surprisal; a natural definition which is closely related to the definition of MI. We show how this approach can reveal the dyadic vs triadic generative structure of multivariate systems that are indistinguishable with classical Shannon measures. The entropy perspective also shows that misinformation is synergistic entropy and hence that MI itself includes both redundant and synergistic effects. We show the relationships between the PED and MI in two predictors, and derive two alternative information decompositions which we illustrate on several example systems. This reveals that in entropy terms, univariate predictor MI is not a proper subset of the joint MI, and we suggest this previously unrecognised fact explains in part why obtaining a consistent PID has proven difficult. The PED also allows separate quantification of mechanistic redundancy (related to the function of the system) versus source redundancy (arising from dependencies between inputs); an important distinction which no existing methods can address. The new perspective provided by the PED helps to clarify some of the difficulties encountered with the PID approach and the resulting decompositions provide useful tools for practical data analysis across a wide range of application areas.
Fast multiplication for skew polynomials
Venue: arXiv cs.SC 2017
Year: 2017

We describe an algorithm for fast multiplication of skew polynomials. It is based on fast modular multiplication of such skew polynomials, for which we give an algorithm relying on evaluation and interpolation on normal bases. Our algorithms improve the best known complexity for these problems, and reach the optimal asymptotic complexity bound for large degree. We also give an adaptation of our algorithm for polynomials of small degree. Finally, we use our methods to improve on the best known complexities for various arithmetics problems.
Distributed Evolutionary k-way Node Separators
Venue: arXiv cs.NE 2017
Year: 2017

Computing high quality node separators in large graphs is necessary for a variety of applications, ranging from divide-and-conquer algorithms to VLSI design. In this work, we present a novel distributed evolutionary algorithm tackling the k-way node separator problem. A key component of our contribution includes new k-way local search algorithms based on maximum flows. We combine our local search with a multilevel approach to compute an initial population for our evolutionary algorithm, and further show how to modify the coarsening stage of our multilevel algorithm to create effective combine and mutation operations. Lastly, we combine these techniques with a scalable communication protocol, producing a system that is able to compute high quality solutions in a short amount of time. Our experiments against competing algorithms show that our advanced evolutionary algorithm computes the best result on 94% of the chosen benchmark instances.
Multi-task memory networks for category-specific aspect and opinion terms co-extraction
Venue: arXiv cs.CL 2017
Year: 2017

In aspect-based sentiment analysis, most existing methods either focus on aspect/opinion terms extraction or aspect terms categorization. However, each task by itself only provides partial information to end users. To generate more detailed and structured opinion analysis, we propose a finer-grained problem, which we call category-specific aspect and opinion terms extraction. This problem involves the identification of aspect and opinion terms within each sentence, as well as the categorization of the identified terms. To this end, we propose an end-to-end multi-task attention model, where each task corresponds to aspect/opinion terms extraction for a specific category. Our model benefits from exploring the commonalities and relationships among different tasks to address the data sparsity issue. We demonstrate its state-of-the-art performance on three benchmark datasets.
Toward the automated analysis of complex diseases in genome-wide association studies using genetic programming
Venue: arXiv cs.NE 2017
Year: 2017

Machine learning has been gaining traction in recent years to meet the demand for tools that can efficiently analyze and make sense of the ever-growing databases of biomedical data in health care systems around the world. However, effectively using machine learning methods requires considerable domain expertise, which can be a barrier of entry for bioinformaticians new to computational data science methods. Therefore, off-the-shelf tools that make machine learning more accessible can prove invaluable for bioinformaticians. To this end, we have developed an open source pipeline optimization tool (TPOT-MDR) that uses genetic programming to automatically design machine learning pipelines for bioinformatics studies. In TPOT-MDR, we implement Multifactor Dimensionality Reduction (MDR) as a feature construction method for modeling higher-order feature interactions, and combine it with a new expert knowledge-guided feature selector for large biomedical data sets. We demonstrate TPOT-MDR's capabilities using a combination of simulated and real world data sets from human genetics and find that TPOT-MDR significantly outperforms modern machine learning methods such as logistic regression and eXtreme Gradient Boosting (XGBoost). We further analyze the best pipeline discovered by TPOT-MDR for a real world problem and highlight TPOT-MDR's ability to produce a high-accuracy solution that is also easily interpretable.
Robustness Analysis of Systems' Safety through a New Notion of Input-to-State Safety
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, we propose a new robustness notion that is applicable for certifying systems' safety with respect to external disturbance signals. The proposed input-to-state safety (ISSf) notion allows us to certify systems' safety in the presence of the disturbances which is analogous to the notion of input-to-state stability (ISS) for analyzing systems' stability.
Petri Automata
Venue: arXiv cs.LO 2017
Year: 2017

Kleene algebra axioms are complete with respect to both language models and binary relation models. In particular, two regular expressions recognise the same language if and only if they are universally equivalent in the model of binary relations. We consider Kleene allegories, i.e., Kleene algebras with two additional operations and a constant which are natural in binary relation models: intersection, converse, and the full relation. While regular languages are closed under those operations, the above characterisation breaks. Putting together a few results from the literature, we give a characterisation in terms of languages of directed and labelled graphs. By taking inspiration from Petri nets, we design a finite automata model, Petri automata, allowing to recognise such graphs. We prove a Kleene theorem for this automata model: the sets of graphs recognisable by Petri automata are precisely the sets of graphs definable through the extended regular expressions we consider. Petri automata allow us to obtain decidability of identity-free relational Kleene lattices, i.e., the equational theory generated by binary relations on the signature of regular expressions with intersection, but where one forbids unit. This restriction is used to ensure that the corresponding graphs are acyclic. We actually show that this decision problem is EXPSPACE-complete.
Seamless Handover in IP over ICN Networks: a Coding Approach
Venue: arXiv cs.NI 2017
Year: 2017

Seamless connectivity plays a key role in realising QoS-based delivery in mobile networks. However, current handover mechanisms hinder the ability to meet this target, due to the high ratio of handover failures, packet loss and service interruption. These challenges are further magnified in Heterogeneous Cellular Networks (HCN) such as Advanced Long Term Evolution (LTE-Advanced) and LTE in unlicensed spectrum (LTE-LAA), due to the variation in handover requirements. Although mechanisms, such as Fast Handover for Proxy Mobile IPv6 (PFMIPv6), attempt to tackle these issues; they come at a high cost with sub-optimal outcomes. This primarily stems from various limitations of existing IP core networks. In this paper we propose a novel handover solution for mobile networks, exploiting the advantages of a revolutionary IP over Information-Centric Networking (IP-over-ICN) architecture in supporting flexible service provisioning through anycast and multicast, combined with the advantages of random linear coding techniques in eliminating the need for retransmissions. Our solution allows coded traffic to be disseminated in a multicast fashion during handover phase from source directly to the destination(s), without the need for an intermediate anchor as in exiting solutions; thereby, overcoming packet loss and handover failures, while reducing overall delivery cost. We evaluate our approach with an analytical and simulation model showing significant cost reduction compared to PFMIPv6.
Achieving Dilution without Knowledge of Coordinates in the SINR Model
Venue: arXiv cs.DC 2017
Year: 2017

Considerable literature has been developed for various fundamental distributed problems in the SINR (Signal-to-Interference-plus-Noise-Ratio) model for radio transmission. A setting typically studied is when all nodes transmit a signal of the same strength, and each device only has access to knowledge about the total number of nodes in the network $n$, the range from which each node's label is taken $[1,\dots,N]$, and the label of the device itself. In addition, an assumption is made that each node also knows its coordinates in the Euclidean plane. In this paper, we create a technique which allows algorithm designers to remove that last assumption. The assumption about the unavailability of the knowledge of the physical coordinates of the nodes truly captures the `ad-hoc' nature of wireless networks. Previous work in this area uses a flavor of a technique called dilution, in which nodes transmit in a (predetermined) round-robin fashion, and are able to reach all their neighbors. However, without knowing the physical coordinates, it's not possible to know the coordinates of their containing (pivotal) grid box and seemingly not possible to use dilution (to coordinate their transmissions). We propose a new technique to achieve dilution without using the knowledge of physical coordinates. This technique exploits the understanding that the transmitting nodes lie in 2-D space, segmented by an appropriate pivotal grid, without explicitly referring to the actual physical coordinates of these nodes. Using this technique, it is possible for every weak device to successfully transmit its message to all of its neighbors in $Θ(\lg N)$ rounds, as long as the density of transmitting nodes in any physical grid box is bounded by a known constant. This technique, we feel, is an important generic tool for devising practical protocols when physical coordinates of the nodes are not known.
Tracking using Numerous Anchor points
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, an online adaptive model-free tracker is proposed to track single objects in video sequences to deal with real-world tracking challenges like low-resolution, object deformation, occlusion and motion blur. The novelty lies in the construction of a strong appearance model that captures features from the initialized bounding box and then are assembled into anchor-point features. These features memorize the global pattern of the object and have an internal star graph-like structure. These features are unique and flexible and helps tracking generic and deformable objects with no limitation on specific objects. In addition, the relevance of each feature is evaluated online using short-term consistency and long-term consistency. These parameters are adapted to retain consistent features that vote for the object location and that deal with outliers for long-term tracking scenarios. Additionally, voting in a Gaussian manner helps in tackling inherent noise of the tracking system and in accurate object localization. Furthermore, the proposed tracker uses pairwise distance measure to cope with scale variations and combines pixel-level binary features and global weighted color features for model update. Finally, experimental results on a visual tracking benchmark dataset are presented to demonstrate the effectiveness and competitiveness of the proposed tracker.
Optimal Tracking Performance of Control Systems with Two-Channel Constraints
Venue: arXiv cs.SY 2017
Year: 2017

This paper focuses on the tracking performance limitation for a class of networked control systems(NCSs) with two-channel constraints. In communication channels, we consider bandwidth, energy constraints and additive colored Gaussian noise(ACGN) simultaneously. In plant, non-minimal zeros and unstable poles are considered; multi-repeated zeros and poles are also applicable. To obtain the optimal performance, the two-parameter controller is adopted. The theoretical results show that the optimal tracking performance is influenced by the non-minimum phase zeros, unstable poles, gain at all frequencies of the given plant, and the reference input signal for NCSs. Moreover, the performance limitation is also affected by the limited bandwidth, additive colored Gaussian noise, and the corresponding multiples for the non-minimum phase zeros and unstable poles. Additionally, the channel minimal input power constraints are given under the condition ensuring the stability of the system and acquiring system performance limitation. Finally, simulation examples are given to illustrate the theoretical results.
Optimal Tracking Performance Limitation of Networked Control Systems with Limited Bandwidth and Additive Colored White Gaussian Noise
Venue: arXiv cs.SY 2017
Year: 2017

This paper studies optimal tracking performance issues for multi-input-multi-output linear time-invariant systems under networked control with limited bandwidth and additive colored white Gaussian noise channel. The tracking performance is measured by control input energy and the energy of the error signal between the output of the system and the reference signal with respect to a Brownian motion random process. This paper focuses on two kinds of network parameters, the basic network parameter-bandwidth and the additive colored white Gaussian noise, and studies the tracking performance limitation problem. The best attainable tracking performance is obtained, and the impact of limited bandwidth and additive colored white Gaussian noise of the communication channel on the attainable tracking performance is revealed. It is shown that the optimal tracking performance depends on nonminimum phase zeros, gain at all frequencies and their directions unitary vector of the given plant, as well as the limited bandwidth and additive colored white Gaussian noise of the communication channel. The simulation results are finally given to illustrate the theoretical results.
Rayleigh Quotient Iteration with a Multigrid in Energy Preconditioner for Massively Parallel Neutron Transport
Venue: arXiv cs.CE 2017
Year: 2017

Three complementary methods have been implemented in the code Denovo that accelerate neutral particle transport calculations with methods that use leadership-class computers fully and effectively: a multigroup block (MG) Krylov solver, a Rayleigh quotient iteration (RQI) eigenvalue solver, and a multigrid in energy preconditioner. The multigroup Krylov solver converges more quickly than Gauss Seidel and enables energy decomposition such that Denovo can scale to hundreds of thousands of cores. The new multigrid in energy preconditioner reduces iteration count for many problem types and takes advantage of the new energy decomposition such that it can scale efficiently. These two tools are useful on their own, but together they enable the RQI eigenvalue solver to work. Each individual method has been described before, but this is the first time they have been demonstrated to work together effectively. RQI should converge in fewer iterations than power iteration (PI) for large and challenging problems. RQI creates shifted systems that would not be tractable without the MG Krylov solver. It also creates ill-conditioned matrices that cannot converge without the multigrid in energy preconditioner. Using these methods together, RQI converged in fewer iterations and in less time than all PI calculations for a full pressurized water reactor core. It also scaled reasonably well out to 275,968 cores.
Massive MIMO Beam-forming for High Speed Train Communication: Directivity vs Beamwidth
Venue: arXiv cs.IT 2017
Year: 2017

High-mobility adaption and massive Multiple-input Multiple-output (MIMO) application are two primary evolving objectives for the next generation high speed train communication system. In this paper, we consider how to design a location-aware beam-forming for the massive MIMO system.We first analyze the tradeoff between beam directivity and beamwidth, based on which we present the sensitivity analysis of positioning accuracy. Then, we derive the maximum beam directivity and corresponding beamwidth under the restriction of diverse positioning accuracies to guarantee a high efficient transmission. Finally, we present a low-complexity beam-forming design with positioning robustness utilizing location information, which requires neither eigen-decomposing (ED) the uplink channel covariance matrix (CCM) nor ED the downlink CCM (DCCM). Numerical simulation indicates that a massive MIMO system with less than a certain positioning error can guarantee a required performance with satisfying transmission efficiency in the high-mobility scenario.
Estimation of classrooms occupancy using a multi-layer perceptron
Venue: arXiv cs.NE 2017
Year: 2017

This paper presents a multi-layer perceptron model for the estimation of classrooms number of occupants from sensed indoor environmental data-relative humidity, air temperature, and carbon dioxide concentration. The modelling datasets were collected from two classrooms in the Secondary School of Pombal, Portugal. The number of occupants and occupation periods were obtained from class attendance reports. However, post-class occupancy was unknown and the developed model is used to reconstruct the classrooms occupancy by filling the unreported periods. Different model structure and environment variables combination were tested. The model with best accuracy had as input vector 10 variables of five averaged time intervals of relative humidity and carbon dioxide concentration. The model presented a mean square error of 1.99, coefficient of determination of 0.96 with a significance of p-value < 0.001, and a mean absolute error of 1 occupant. These results show promising estimation capabilities in uncertain indoor environment conditions.
Opportunistic Content Delivery in Fading Broadcast Channels
Venue: arXiv cs.IT 2017
Year: 2017

We consider content delivery over fading broadcast channels. A server wants to transmit K files to K users, each equipped with a cache of finite size. Using the coded caching scheme of Maddah-Ali and Niesen, we design an opportunistic delivery scheme where the long-term sum content delivery rate scales with K the number of users in the system. The proposed delivery scheme combines superposition coding together with appropriate power allocation across sub-files intended to different subsets of users. We analyze the long-term average sum content delivery rate achieved by two special cases of our scheme: a) a selection scheme that chooses the subset of users with the largest weighted rate, and b) a baseline scheme that transmits to K users using the scheme of Maddah-Ali and Niesen. We prove that coded caching with appropriate user selection is scalable since it yields a linear increase of the average sum content delivery rate.
Multitask Evolution with Cartesian Genetic Programming
Venue: arXiv cs.NE 2017
Year: 2017

We introduce a genetic programming method for solving multiple Boolean circuit synthesis tasks simultaneously. This allows us to solve a set of elementary logic functions twice as easily as with a direct, single-task approach.
Retractions in Intersection Types
Venue: arXiv cs.LO 2017
Year: 2017

This paper deals with retraction - intended as isomorphic embedding - in intersection types building left and right inverses as terms of a lambda calculus with a bottom constant. The main result is a necessary and sufficient condition two strict intersection types must satisfy in order to assure the existence of two terms showing the first type to be a retract of the second one. Moreover, the characterisation of retraction in the standard intersection types is discussed.
A Historical Review of Forty Years of Research on CMAC
Venue: arXiv cs.NE 2017
Year: 2017

The Cerebellar Model Articulation Controller (CMAC) is an influential brain-inspired computing model in many relevant fields. Since its inception in the 1970s, the model has been intensively studied and many variants of the prototype, such as Kernel-CMAC, Self-Organizing Map CMAC, and Linguistic CMAC, have been proposed. This review article focus on how the CMAC model is gradually developed and refined to meet the demand of fast, adaptive, and robust control. Two perspective, CMAC as a neural network and CMAC as a table look-up technique are presented. Three aspects of the model: the architecture, learning algorithms and applications are discussed. In the end, some potential future research directions on this model are suggested.
Intersection Types and Counting
Venue: arXiv cs.LO 2017
Year: 2017

We present a new approach to the following meta-problem: given a quantitative property of trees, design a type system such that the desired property for the tree generated by an infinitary ground lambda-term corresponds to some property of a derivation of a type for this lambda-term, in this type system. Our approach is presented in the particular case of the language finiteness problem for nondeterministic higher-order recursion schemes (HORSes): given a nondeterministic HORS, decide whether the set of all finite trees generated by this HORS is finite. We give a type system such that the HORS can generate a tree of an arbitrarily large finite size if and only if in the type system we can obtain derivations that are arbitrarily large, in an appropriate sense; the latter condition can be easily decided.
Dependent Types for Multi-Rate Flows in Synchronous Programming
Venue: arXiv cs.PL 2017
Year: 2017

Synchronous programming languages emerged in the 1980s as tools for implementing reactive systems, which interact with events from physical environments and often must do so under strict timing constraints. In this report, we encode inside ATS various real-time primitives in an experimental synchronous language called Prelude, where ATS is a statically typed language with an ML-like functional core that supports both dependent types (of DML-style) and linear types. We show that the verification requirements imposed on these primitives can be formally expressed in terms of dependent types in ATS. Moreover, we modify the Prelude compiler to automatically generate ATS code from Prelude source. This modified compiler allows us to solely rely on typechecking in ATS to discharge proof obligations originating from the need to typecheck Prelude code. Whereas ATS is typically used as a general purpose programming language, we hereby demonstrate that it can also be conveniently used to support some forms of advanced static checking in languages equipped with less expressive types.