OpenRaiser/Intern-Atlas huggingface dataset:
Spectral identification of networks with inputs
Venue: arXiv cs.SY 2017
Year: 2017

We consider a network of interconnected dynamical systems. Spectral network identification consists in recovering the eigenvalues of the network Laplacian from the measurements of a very limited number (possibly one) of signals. These eigenvalues allow to deduce some global properties of the network, such as bounds on the node degree. Having recently introduced this approach for autonomous networks of nonlinear systems, we extend it here to treat networked systems with external inputs on the nodes, in the case of linear dynamics. This is more natural in several applications, and removes the need to sometimes use several independent trajectories. We illustrate our framework with several examples, where we estimate the mean, minimum, and maximum node degree in the network. Inferring some information on the leading Laplacian eigenvectors, we also use our framework in the context of network clustering.
One-Bit Sphere Decoding for Uplink Massive MIMO Systems with One-Bit ADCs
Venue: arXiv cs.IT 2017
Year: 2017

This paper presents a low-complexity near-maximum-likelihood-detection (near-MLD) algorithm called one-bit-sphere-decoding for an uplink massive multiple-input multiple-output (MIMO) system with one-bit analog-to-digital converters (ADCs). The idea of the proposed algorithm is to estimate the transmitted symbol vector sent by uplink users (a codeword vector) by searching over a sphere, which contains a collection of codeword vectors close to the received signal vector at the base station in terms of a weighted Hamming distance. To reduce the computational complexity for the construction of the sphere, the proposed algorithm divides the received signal vector into multiple sub-vectors each with reduced dimension. Then, it generates multiple spheres in parallel, where each sphere is centered at the sub-vector and contains a list of sub-codeword vectors. The detection performance of the proposed algorithm is also analyzed by characterizing the probability that the proposed algorithm performs worse than the MLD. The analysis shows how the dimension of each sphere and the size of the sub-codeword list are related to the performance-complexity tradeoff achieved by the proposed algorithm. Simulation results demonstrate that the proposed algorithm achieves near-MLD performance, while reducing the computational complexity compared to the existing MLD method.
A Comparison of Public Causal Search Packages on Linear, Gaussian Data with No Latent Variables
Venue: arXiv cs.AI 2017
Year: 2017

We compare Tetrad (Java) algorithms to the other public software packages BNT (Bayes Net Toolbox, Matlab), pcalg (R), bnlearn (R) on the \vanilla" task of recovering DAG structure to the extent possible from data generated recursively from linear, Gaussian structure equation models (SEMs) with no latent variables, for random graphs, with no additional knowledge of variable order or adjacency structure, and without additional specification of intervention information. Each one of the above packages offers at least one implementation suitable to this purpose. We compare them on adjacency and orientation accuracy as well as time performance, for fixed datasets. We vary the number of variables, the number of samples, and the density of graph, for a total of 27 combinations, averaging all statistics over 10 runs, for a total of 270 datasets. All runs are carried out on the same machine and on their native platforms. An interactive visualization tool is provided for the reader who wishes to know more than can be documented explicitly in this report.
Dialogue Act Sequence Labeling using Hierarchical encoder with CRF
Venue: arXiv cs.CL 2017
Year: 2017

Dialogue Act recognition associate dialogue acts (i.e., semantic labels) to utterances in a conversation. The problem of associating semantic labels to utterances can be treated as a sequence labeling problem. In this work, we build a hierarchical recurrent neural network using bidirectional LSTM as a base unit and the conditional random field (CRF) as the top layer to classify each utterance into its corresponding dialogue act. The hierarchical network learns representations at multiple levels, i.e., word level, utterance level, and conversation level. The conversation level representations are input to the CRF layer, which takes into account not only all previous utterances but also their dialogue acts, thus modeling the dependency among both, labels and utterances, an important consideration of natural dialogue. We validate our approach on two different benchmark data sets, Switchboard and Meeting Recorder Dialogue Act, and show performance improvement over the state-of-the-art methods by $2.2\%$ and $4.1\%$ absolute points, respectively. It is worth noting that the inter-annotator agreement on Switchboard data set is $84\%$, and our method is able to achieve the accuracy of about $79\%$ despite being trained on the noisy data.
On the Generation of Initial Contexts for Effective Deadlock Detection
Venue: arXiv cs.PL 2017
Year: 2017

It has been recently proposed that testing based on symbolic execution can be used in conjunction with static deadlock analysis to define a deadlock detection framework that: (i) can show deadlock presence, in that case a concrete test-case and trace are obtained, and (ii) can also prove deadlock freedom. Such symbolic execution starts from an initial distributed context, i.e., a set of locations and their initial tasks. Considering all possibilities results in a combinatorial explosion on the different distributed contexts that must be considered. This paper proposes a technique to effectively generate initial contexts that can lead to deadlock, using the possible conflicting task interactions identified by static analysis, discarding other distributed contexts that cannot lead to deadlock. The proposed technique has been integrated in the above-mentioned deadlock detection framework hence enabling it to analyze systems without the need of any user supplied initial context.
Flora robotica -- An Architectural System Combining Living Natural Plants and Distributed Robots
Venue: arXiv cs.ET 2017
Year: 2017

Key to our project flora robotica is the idea of creating a bio-hybrid system of tightly coupled natural plants and distributed robots to grow architectural artifacts and spaces. Our motivation with this ground research project is to lay a principled foundation towards the design and implementation of living architectural systems that provide functionalities beyond those of orthodox building practice, such as self-repair, material accumulation and self-organization. Plants and robots work together to create a living organism that is inhabited by human beings. User-defined design objectives help to steer the directional growth of the plants, but also the system's interactions with its inhabitants determine locations where growth is prohibited or desired (e.g., partitions, windows, occupiable space). We report our plant species selection process and aspects of living architecture. A leitmotif of our project is the rich concept of braiding: braids are produced by robots from continuous material and serve as both scaffolds and initial architectural artifacts before plants take over and grow the desired architecture. We use light and hormones as attraction stimuli and far-red light as repelling stimulus to influence the plants. Applied sensors range from simple proximity sensing to detect the presence of plants to sophisticated sensing technology, such as electrophysiology and measurements of sap flow. We conclude by discussing our anticipated final demonstrator that integrates key features of flora robotica, such as the continuous growth process of architectural artifacts and self-repair of living architecture.
Densely tracking sequences of 3D face scans
Venue: arXiv cs.CV 2017
Year: 2017

3D face dense tracking aims to find dense inter-frame correspondences in a sequence of 3D face scans and constitutes a powerful tool for many face analysis tasks, e.g., 3D dynamic facial expression analysis. The majority of the existing methods just fit a 3D face surface or model to a 3D target surface without considering temporal information between frames. In this paper, we propose a novel method for densely tracking sequences of 3D face scans, which ex- tends the non-rigid ICP algorithm by adding a novel specific criterion for temporal information. A novel fitting framework is presented for automatically tracking a full sequence of 3D face scans. The results of experiments carried out on the BU4D-FE database are promising, showing that the proposed algorithm outperforms state-of-the-art algorithms for 3D face dense tracking.
Pattern Recognition using Artificial Immune System
Venue: arXiv cs.NE 2017
Year: 2017

In this thesis, the uses of Artificial Immune Systems (AIS) in Machine learning is studded. the thesis focus on some of immune inspired algorithms such as clonal selection algorithm and artificial immune network. The effect of changing the algorithm parameter on its performance is studded. Then a new immune inspired algorithm for unsupervised classification is proposed. The new algorithm is based on clonal selection principle and named Unsupervised Clonal Selection Classification (UCSC). The new proposed algorithm is almost parameter free. The algorithm parameters are data driven and it adjusts itself to make the classification as fast as possible. The performance of UCSC is evaluated. The experiments show that the proposed UCSC algorithm has a good performance and more reliable.
Distributed Scheduling in Time Dependent Environments: Algorithms and Analysis
Venue: arXiv cs.IT 2017
Year: 2017

Consider the problem of a multiple access channel in a time dependent environment with a large number of users. In such a system, mostly due to practical constraints (e.g., decoding complexity), not all users can be scheduled together, and usually only one user may transmit at any given time. Assuming a distributed, opportunistic scheduling algorithm, we analyse the system's properties, such as delay, QoS and capacity scaling laws. Specifically, we start with analyzing the performance while \emph{assuming the users are not necessarily fully backlogged}, focusing on the queueing problem and, especially, on the \emph{strong dependence between the queues}. We first extend a known queueing model by Ephremides and Zhu, to give new results on the convergence of the probability of collision to its average value (as the number of users grows), and hence for the ensuing system performance metrics, such as throughput and delay. This model, however, is limited in the number of users one can analyze. We thus suggest a new model, which is much simpler yet can accurately describes the system behaviour when the number of users is large. We then proceed to the analysis of this system under the assumption of time dependent channels. Specifically, we assume each user experiences a different channel state sequence, expressing different channel fluctuations (specifically, the Gilbert-Elliott model). The system performance under this setting is analysed, along with the channel capacity scaling laws.
Exploiting skeletal structure in computer vision annotation with Benders decomposition
Venue: arXiv cs.CV 2017
Year: 2017

Many annotation problems in computer vision can be phrased as integer linear programs (ILPs). The use of standard industrial solvers does not to exploit the underlying structure of such problems eg, the skeleton in pose estimation. The leveraging of the underlying structure in conjunction with industrial solvers promises increases in both speed and accuracy. Such structure can be exploited using Bender's decomposition, a technique from operations research, that solves complex ILPs or mixed integer linear programs by decomposing them into sub-problems that communicate via a master problem. The intuition is that conditioned on a small subset of the variables the solution to the remaining variables can be computed easily by taking advantage of properties of the ILP constraint matrix such as block structure. In this paper we apply Benders decomposition to a typical problem in computer vision where we have many sub-ILPs (eg, partitioning of detections, body-parts) coupled to a master ILP (eg, constructing skeletons). Dividing inference problems into a master problem and sub-problems motivates the development of a plethora of novel models, and inference approaches for the field of computer vision.
Visualization of Big Spatial Data using Coresets for Kernel Density Estimates
Venue: arXiv cs.HC 2017
Year: 2017

The size of large, geo-located datasets has reached scales where visualization of all data points is inefficient. Random sampling is a method to reduce the size of a dataset, yet it can introduce unwanted errors. We describe a method for subsampling of spatial data suitable for creating kernel density estimates from very large data and demonstrate that it results in less error than random sampling. We also introduce a method to ensure that thresholding of low values based on sampled data does not omit any regions above the desired threshold when working with sampled data. We demonstrate the effectiveness of our approach using both, artificial and real-world large geospatial datasets.
Gene tree reconciliation including transfers with replacement is hard and FPT
Venue: arXiv cs.DS 2017
Year: 2017

Phylogenetic trees illustrate the evolutionary history of genes and species. In most cases, although genes evolve along with the species they belong to, a species tree and gene tree are not identical, because of evolutionary events at the gene level like duplication or transfer. These differences are handled by phylogenetic reconciliation, which formally is a mapping between gene tree nodes and species tree nodes and branches. We investigate models of reconciliation with a gene transfer that replaces existing gene, which is a biological important event but never included in reconciliation models. Also the problem is close to a dated version of the classical subtree prune and regraft (SPR) distance problem, where a pruned subtree has to be regrafted only on a branch closer to the root. We prove that the reconciliation problem including transfer and replacement is NP-hard, and that if speciations and transfers with replacement are the only allowed evolutionary events, then it is fixed-parameter tractable (FPT) with respect to the reconciliation's weight. We prove that the results extend to the dated SPR problem.
Using NLU in Context for Question Answering: Improving on Facebook's bAbI Tasks
Venue: arXiv cs.CL 2017
Year: 2017

For the next step in human to machine interaction, Artificial Intelligence (AI) should interact predominantly using natural language because, if it worked, it would be the fastest way to communicate. Facebook's toy tasks (bAbI) provide a useful benchmark to compare implementations for conversational AI. While the published experiments so far have been based on exploiting the distributional hypothesis with machine learning, our model exploits natural language understanding (NLU) with the decomposition of language based on Role and Reference Grammar (RRG) and the brain-based Patom theory. Our combinatorial system for conversational AI based on linguistics has many advantages: passing bAbI task tests without parsing or statistics while increasing scalability. Our model validates both the training and test data to find 'garbage' input and output (GIGO). It is not rules-based, nor does it use parts of speech, but instead relies on meaning. While Deep Learning is difficult to debug and fix, every step in our model can be understood and changed like any non-statistical computer program. Deep Learning's lack of explicable reasoning has raised opposition to AI, partly due to fear of the unknown. To support the goals of AI, we propose extended tasks to use human-level statements with tense, aspect and voice, and embedded clauses with junctures: and answers to be natural language generation (NLG) instead of keywords. While machine learning permits invalid training data to produce incorrect test responses, our system cannot because the context tracking would need to be intentionally broken. We believe no existing learning systems can currently solve these extended natural language tests. There appears to be a knowledge gap between NLP researchers and linguists, but ongoing competitive results such as these promise to narrow that gap.
REMOTEGATE: Incentive-Compatible Remote Configuration of Security Gateways
Venue: arXiv cs.CR 2017
Year: 2017

Imagine that a malicious hacker is trying to attack a server over the Internet and the server wants to block the attack packets as close to their point of origin as possible. However, the security gateway ahead of the source of attack is untrusted. How can the server block the attack packets through this gateway? In this paper, we introduce REMOTEGATE, a trustworthy mechanism for allowing any party (server) on the Internet to configure a security gateway owned by a second party, at a certain agreed upon reward that the former pays to the latter for its service. We take an interactive incentive-compatible approach, for the case when both the server and the gateway are rational, to devise a protocol that will allow the server to help the security gateway generate and deploy a policy rule that filters the attack packets before they reach the server. The server will reward the gateway only when the latter can successfully verify that it has generated and deployed the correct rule for the issue. This mechanism will enable an Internet-scale approach to improving security and privacy, backed by digital payment incentives.
Autonomous Extracting a Hierarchical Structure of Tasks in Reinforcement Learning and Multi-task Reinforcement Learning
Venue: arXiv cs.AI 2017
Year: 2017

Reinforcement learning (RL), while often powerful, can suffer from slow learning speeds, particularly in high dimensional spaces. The autonomous decomposition of tasks and use of hierarchical methods hold the potential to significantly speed up learning in such domains. This paper proposes a novel practical method that can autonomously decompose tasks, by leveraging association rule mining, which discovers hidden relationship among entities in data mining. We introduce a novel method called ARM-HSTRL (Association Rule Mining to extract Hierarchical Structure of Tasks in Reinforcement Learning). It extracts temporal and structural relationships of sub-goals in RL, and multi-task RL. In particular,it finds sub-goals and relationship among them. It is shown the significant efficiency and performance of the proposed method in two main topics of RL.
Pisano period codes
Venue: arXiv cs.IT 2017
Year: 2017

The cyclic codes with parity check polynomial the reciprocal of the characteristic polynomial of the Fibonacci recurrence over a prime finite field are shown to have either one weight or two weights. When these codes are irreducible cyclic we obtain many counterexamples to the conjectural classification of two-weight irreducible cyclic codes of Schmidt and White (2002). When they are reducible and projective their duals are uniformly packed.
Scalability Evaluation of NSLP Algorithm for Solving Non-Stationary Linear Programming Problems on Cluster Computing Systems
Venue: arXiv cs.DC 2017
Year: 2017

The paper is devoted to a scalability study of the NSLP algorithm for solving non-stationary high-dimension linear programming problem on the cluster computing systems. The analysis is based on the BSF model of parallel computations. The BSF model is a new parallel computation model designed on the basis of BSP and SPMD models. The brief descriptions of the NSLP algorithm and the BSF model are given. The NSLP algorithm implementation in the form of a BSF program is considered. On the basis of the BSF cost metric, the upper bound of the NSLP algorithm scalability is derived and its parallel efficiency is estimated. NSLP algorithm implementation using BSF skeleton is described. A comparison of scalability estimations obtained analytically and experimentally is provided.
Network Slicing in Fog Radio Access Networks: Issues and Challenges
Venue: arXiv cs.IT 2017
Year: 2017

Network slicing has been advocated by both academia and industry as a cost-efficient way to enable operators to provide networks on an as-a-service basis and meet the wide range of use cases that the fifth generation wireless network will serve. The existing works on network slicing are mainly targeted at the partition of the core network, and the prospect of network slicing in radio access networks should be jointly exploited. To solve this challenge, an enhanced network slicing in fog radio access networks (F-RANs), termed as access slicing, is proposed. This article comprehensively presents a novel architecture and related key techniques for access slicing in F-RANs. The proposed hierarchical architecture of access slicing consists of centralized orchestration layer and slice instance layer, which makes the access slicing adaptively implement in an convenient way. Meanwhile, key techniques and their corresponding solutions, including the radio and cache resource management, as well as the social-aware slicing, are presented. Open issues in terms of standardization developments and field trials are identified.
Resource Allocation in Cloud Radio Access Networks with Device-to-Device Communications
Venue: arXiv cs.IT 2017
Year: 2017

To alleviate the burdens on the fronthaul and reduce the transmit latency, the device-to-device (D2D) communication is presented in cloud radio access networks (C-RANs). Considering dynamic traffic arrivals and time-varying channel conditions, the resource allocation in C-RANs with D2D is formulated into a stochastic optimization problem, which is aimed at maximizing the overall throughput subject to network stability, interference, and fronthaul capacity constraints. Leveraging on the Lyapunov optimization technique, the stochastic optimization problem is transformed into a delay-aware optimization problem, which is a mixed-integer nonlinear programming problem and can be decomposed into three subproblems: mode selection, uplink beamforming design, and power control. An optimization solution that consists of a modified branch and bound method as well as a weighted minimum mean square error approach has been developed to obtain the close-to-optimal solution. Simulation results validate that the D2D can improve throughput, decrease latency, and alleviate the burdens of the constrained fronthaul in C-RANs. Furthermore, an average throughput-delay tradeoff can be achieved by the proposed solution.
One-to-One Matching of RTT and Path Changes
Venue: arXiv cs.NI 2017
Year: 2017

Route selection based on performance measurements is an essential task in inter-domain Traffic Engineering. It can benefit from the detection of significant changes in RTT measurements and the understanding on potential causes of change. Among the extensive works on change detection methods and their applications in various domains, few focus on RTT measurements. It is thus unclear which approach works the best on such data. In this paper, we present an evaluation framework for change detection on RTT times series, consisting of: 1) a carefully labelled 34,008-hour RTT dataset as ground truth; 2) a scoring method specifically tailored for RTT measurements. Furthermore, we proposed a data transformation that improves the detection performance of existing methods. Path changes are as well attended to. We fix shortcomings of previous works by distinguishing path changes due to routing protocols (IGP and BGP) from those caused by load balancing. Finally, we apply our change detection methods to a large set of measurements from RIPE Atlas. The characteristics of both RTT and path changes are analyzed; the correlation between the two are also illustrated. We identify extremely frequent AS path changes yet with few consequences on RTT, which has not been reported before.