OpenRaiser/Intern-Atlas huggingface dataset:
Character Networks and Book Genre Classification
Venue: arXiv cs.SI 2018
Year: 2018

We compare the social character networks of biographical, legendary and fictional texts, in search for marks of genre differentiation. We examine the degree distribution of character appearance and find a power law that does not depend on the literary genre or historical content. We also analyze local and global complex networks measures, in particular, correlation plots between the recently introduced Lobby (or Hirsh $H(1)$) index and Degree, Betweenness and Closeness centralities. Assortativity plots, which previous literature claims to separate fictional from real social networks, were also studied. We've found no relevant differences in the books for these network measures and we give a plausible explanation why the previous assortativity result is not correct.
DNA Steganalysis Using Deep Recurrent Neural Networks
Venue: arXiv cs.LG 2018
Year: 2018

Recent advances in next-generation sequencing technologies have facilitated the use of deoxyribonucleic acid (DNA) as a novel covert channels in steganography. There are various methods that exist in other domains to detect hidden messages in conventional covert channels. However, they have not been applied to DNA steganography. The current most common detection approaches, namely frequency analysis-based methods, often overlook important signals when directly applied to DNA steganography because those methods depend on the distribution of the number of sequence characters. To address this limitation, we propose a general sequence learning-based DNA steganalysis framework. The proposed approach learns the intrinsic distribution of coding and non-coding sequences and detects hidden messages by exploiting distribution variations after hiding these messages. Using deep recurrent neural networks (RNNs), our framework identifies the distribution variations by using the classification score to predict whether a sequence is to be a coding or non-coding sequence. We compare our proposed method to various existing methods and biological sequence analysis methods implemented on top of our framework. According to our experimental results, our approach delivers a robust detection performance compared to other tools.
Weighted network estimation by the use of topological graph metrics
Venue: arXiv cs.DS 2018
Year: 2018

Topological metrics of graphs provide a natural way to describe the prominent features of various types of networks. Graph metrics describe the structure and interplay of graph edges and have found applications in many scientific fields. In this work, graph metrics are used in network estimation by developing optimisation methods that incorporate prior knowledge of a network's topology. The derivatives of graph metrics are used in gradient descent schemes for weighted undirected network denoising, network completion, and network decomposition. The successful performance of our methodology is shown in a number of toy examples and real-world datasets. Most notably, our work establishes a new link between graph theory, network science and optimisation.
On the effectiveness of feature set augmentation using clusters of word embeddings
Venue: arXiv cs.CL 2018
Year: 2018

Word clusters have been empirically shown to offer important performance improvements on various tasks. Despite their importance, their incorporation in the standard pipeline of feature engineering relies more on a trial-and-error procedure where one evaluates several hyper-parameters, like the number of clusters to be used. In order to better understand the role of such features we systematically evaluate their effect on four tasks, those of named entity segmentation and classification as well as, those of five-point sentiment classification and quantification. Our results strongly suggest that cluster membership features improve the performance.
A General Safety Framework for Learning-Based Control in Uncertain Robotic Systems
Venue: arXiv cs.RO 2018
Year: 2018

The proven efficacy of learning-based control schemes strongly motivates their application to robotic systems operating in the physical world. However, guaranteeing correct operation during the learning process is currently an unresolved issue, which is of vital importance in safety-critical systems. We propose a general safety framework based on Hamilton-Jacobi reachability methods that can work in conjunction with an arbitrary learning algorithm. The method exploits approximate knowledge of the system dynamics to guarantee constraint satisfaction while minimally interfering with the learning process. We further introduce a Bayesian mechanism that refines the safety analysis as the system acquires new evidence, reducing initial conservativeness when appropriate while strengthening guarantees through real-time validation. The result is a least-restrictive, safety-preserving control law that intervenes only when (a) the computed safety guarantees require it, or (b) confidence in the computed guarantees decays in light of new observations. We prove theoretical safety guarantees combining probabilistic and worst-case analysis and demonstrate the proposed framework experimentally on a quadrotor vehicle. Even though safety analysis is based on a simple point-mass model, the quadrotor successfully arrives at a suitable controller by policy-gradient reinforcement learning without ever crashing, and safely retracts away from a strong external disturbance introduced during flight.
A Note on Hardness of Diameter Approximation
Venue: arXiv cs.DS 2018
Year: 2018

We revisit the hardness of approximating the diameter of a network. In the CONGEST model of distributed computing, $ \tilde Ω(n) $ rounds are necessary to compute the diameter [Frischknecht et al. SODA'12], where $ \tilde Ω(\cdot) $ hides polylogarithmic factors. Abboud et al. [DISC 2016] extended this result to sparse graphs and, at a more fine-grained level, showed that, for any integer $ 1 \leq \ell \leq \operatorname{polylog} (n) $, distinguishing between networks of diameter $ 4 \ell + 2 $ and $ 6 \ell + 1 $ requires $ \tilde Ω(n) $ rounds. We slightly tighten this result by showing that even distinguishing between diameter $ 2 \ell + 1 $ and $ 3 \ell + 1 $ requires $ \tilde Ω(n) $ rounds. The reduction of Abboud et al. is inspired by recent conditional lower bounds in the RAM model, where the orthogonal vectors problem plays a pivotal role. In our new lower bound, we make the connection to orthogonal vectors explicit, leading to a conceptually more streamlined exposition.
Analysis and Design of Convolutional Networks via Hierarchical Tensor Decompositions
Venue: arXiv cs.LG 2018
Year: 2018

The driving force behind convolutional networks - the most successful deep learning architecture to date, is their expressive power. Despite its wide acceptance and vast empirical evidence, formal analyses supporting this belief are scarce. The primary notions for formally reasoning about expressiveness are efficiency and inductive bias. Expressive efficiency refers to the ability of a network architecture to realize functions that require an alternative architecture to be much larger. Inductive bias refers to the prioritization of some functions over others given prior knowledge regarding a task at hand. In this paper we overview a series of works written by the authors, that through an equivalence to hierarchical tensor decompositions, analyze the expressive efficiency and inductive bias of various convolutional network architectural features (depth, width, strides and more). The results presented shed light on the demonstrated effectiveness of convolutional networks, and in addition, provide new tools for network design.
An $O(n\log n)$-Time Algorithm for the k-Center Problem in Trees
Venue: arXiv cs.DS 2018
Year: 2018

We consider a classical k-center problem in trees. Let T be a tree of n vertices and every vertex has a nonnegative weight. The problem is to find k centers on the edges of T such that the maximum weighted distance from all vertices to their closest centers is minimized. Megiddo and Tamir (SIAM J. Comput., 1983) gave an algorithm that can solve the problem in $O(n\log^2 n)$ time by using Cole's parametric search. Since then it has been open for over three decades whether the problem can be solved in $O(n\log n)$ time. In this paper, we present an $O(n\log n)$ time algorithm for the problem and thus settle the open problem affirmatively.
Faster tuple lattice sieving using spherical locality-sensitive filters
Venue: arXiv cs.DS 2018
Year: 2018

To overcome the large memory requirement of classical lattice sieving algorithms for solving hard lattice problems, Bai-Laarhoven-Stehlé [ANTS 2016] studied tuple lattice sieving, where tuples instead of pairs of lattice vectors are combined to form shorter vectors. Herold-Kirshanova [PKC 2017] recently improved upon their results for arbitrary tuple sizes, for example showing that a triple sieve can solve the shortest vector problem (SVP) in dimension $d$ in time $2^{0.3717d + o(d)}$, using a technique similar to locality-sensitive hashing for finding nearest neighbors. In this work, we generalize the spherical locality-sensitive filters of Becker-Ducas-Gama-Laarhoven [SODA 2016] to obtain space-time tradeoffs for near neighbor searching on dense data sets, and we apply these techniques to tuple lattice sieving to obtain even better time complexities. For instance, our triple sieve heuristically solves SVP in time $2^{0.3588d + o(d)}$. For practical sieves based on Micciancio-Voulgaris' GaussSieve [SODA 2010], this shows that a triple sieve uses less space and less time than the current best near-linear space double sieve.
Automated Synthesis of Secure Platform Mappings
Venue: arXiv cs.SE 2018
Year: 2018

System development often involves decisions about how a high-level design is to be implemented using primitives from a low-level platform. Certain decisions, however, may introduce undesirable behavior into the resulting implementation, possibly leading to a violation of a desired property that has already been established at the design level. In this paper, we introduce the problem of synthesizing a property-preserving platform mapping: A set of implementation decisions ensuring that a desired property is preserved from a high-level design into a low-level platform implementation. We provide a formalization of the synthesis problem and propose a technique for synthesizing a mapping based on symbolic constraint search. We describe our prototype implementation, and a real-world case study demonstrating the application of our technique to synthesizing secure mappings for the popular web authorization protocols OAuth 1.0 and 2.0.
Graph-Based Shape Analysis Beyond Context-Freeness
Venue: arXiv cs.PL 2018
Year: 2018

We develop a shape analysis for reasoning about relational properties of data structures. Both the concrete and the abstract domain are represented by hypergraphs. The analysis is parameterized by user-supplied indexed graph grammars to guide concretization and abstraction. This novel extension of context-free graph grammars is powerful enough to model complex data structures such as balanced binary trees with parent pointers, while preserving most desirable properties of context-free graph grammars. One strength of our analysis is that no artifacts apart from grammars are required from the user; it thus offers a high degree of automation. We implemented our analysis and successfully applied it to various programs manipulating AVL trees, (doubly-linked) lists, and combinations of both.
Defining and Surveying Wireless Link Virtualization and Wireless Network Virtualization
Venue: arXiv cs.NI 2018
Year: 2018

Virtualization is a topic of great interest in the area of mobile and wireless communication systems. However the term virtualization is used in an inexact manner which makes it difficult to compare and contrast work that has been carried out to date. The purpose of this paper is twofold. In the first place, the paper develops a formal theory for defining virtualization. In the second instance, this theory is used as a way of surveying a body of work in the field of wireless link virtualization, a subspace of wireless network virtualization. The formal theory provides a means for distinguishing work that should be classed as resource allocation as distinct from virtualization. It also facilitates a further classification of the representation level at which the virtualization occurs, which makes comparison of work more meaningful. The paper provides a comprehensive survey and highlights gaps in the research that make for fruitful future work.
Quasi-Steady Model of a Pumping Kite Power System
Venue: arXiv cs.SY 2018
Year: 2018

The traction force of a kite can be used to drive a cyclic motion for extracting wind energy from the atmosphere. This paper presents a novel quasi-steady modelling framework for predicting the power generated over a full pumping cycle. The cycle is divided into traction, retraction and transition phases, each described by an individual set of analytic equations. The effect of gravity on the airborne system components is included in the framework. A trade-off is made between modelling accuracy and computation speed such that the model is specifically useful for system optimisation and scaling in economic feasibility studies. Simulation results are compared to experimental measurements of a 20 kW kite power system operated up to a tether length of 720 m. Simulation and experiment agree reasonably well, both for moderate and for strong wind conditions, indicating that the effect of gravity has to be taken into account for a predictive performance simulation.
Incremental Learning Through Deep Adaptation
Venue: arXiv cs.CV 2018
Year: 2018

Given an existing trained neural network, it is often desirable to learn new capabilities without hindering performance of those already learned. Existing approaches either learn sub-optimal solutions, require joint training, or incur a substantial increment in the number of parameters for each added domain, typically as many as the original network. We propose a method called \emph{Deep Adaptation Networks} (DAN) that constrains newly learned filters to be linear combinations of existing ones. DANs precisely preserve performance on the original domain, require a fraction (typically 13\%, dependent on network architecture) of the number of parameters compared to standard fine-tuning procedures and converge in less cycles of training to a comparable or better level of performance. When coupled with standard network quantization techniques, we further reduce the parameter cost to around 3\% of the original with negligible or no loss in accuracy. The learned architecture can be controlled to switch between various learned representations, enabling a single network to solve a task from multiple different domains. We conduct extensive experiments showing the effectiveness of our method on a range of image classification tasks and explore different aspects of its behavior.
Long-term Blood Pressure Prediction with Deep Recurrent Neural Networks
Venue: arXiv cs.LG 2018
Year: 2018

Existing methods for arterial blood pressure (BP) estimation directly map the input physiological signals to output BP values without explicitly modeling the underlying temporal dependencies in BP dynamics. As a result, these models suffer from accuracy decay over a long time and thus require frequent calibration. In this work, we address this issue by formulating BP estimation as a sequence prediction problem in which both the input and target are temporal sequences. We propose a novel deep recurrent neural network (RNN) consisting of multilayered Long Short-Term Memory (LSTM) networks, which are incorporated with (1) a bidirectional structure to access larger-scale context information of input sequence, and (2) residual connections to allow gradients in deep RNN to propagate more effectively. The proposed deep RNN model was tested on a static BP dataset, and it achieved root mean square error (RMSE) of 3.90 and 2.66 mmHg for systolic BP (SBP) and diastolic BP (DBP) prediction respectively, surpassing the accuracy of traditional BP prediction models. On a multi-day BP dataset, the deep RNN achieved RMSE of 3.84, 5.25, 5.80 and 5.81 mmHg for the 1st day, 2nd day, 4th day and 6th month after the 1st day SBP prediction, and 1.80, 4.78, 5.0, 5.21 mmHg for corresponding DBP prediction, respectively, which outperforms all previous models with notable improvement. The experimental results suggest that modeling the temporal dependencies in BP dynamics significantly improves the long-term BP prediction accuracy.
Combination of Hidden Markov Random Field and Conjugate Gradient for Brain Image Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

Image segmentation is the process of partitioning the image into significant regions easier to analyze. Nowadays, segmentation has become a necessity in many practical medical imaging methods as locating tumors and diseases. Hidden Markov Random Field model is one of several techniques used in image segmentation. It provides an elegant way to model the segmentation process. This modeling leads to the minimization of an objective function. Conjugate Gradient algorithm (CG) is one of the best known optimization techniques. This paper proposes the use of the Conjugate Gradient algorithm (CG) for image segmentation, based on the Hidden Markov Random Field. Since derivatives are not available for this expression, finite differences are used in the CG algorithm to approximate the first derivative. The approach is evaluated using a number of publicly available images, where ground truth is known. The Dice Coefficient is used as an objective criterion to measure the quality of segmentation. The results show that the proposed CG approach compares favorably with other variants of Hidden Markov Random Field segmentation algorithms.
Inter-Area Oscillation Damping With Non-Synchronized Wide-Area Power System Stabilizer
Venue: arXiv cs.SY 2018
Year: 2018

One of the major issues in an interconnected power system is the low damping of inter-area oscillations which significantly reduces the power transfer capability. Advances in Wide-Area Measurement System (WAMS) makes it possible to use the information from geographical distant location to improve power system dynamics and performances. A speed deviation based Wide-Area Power System Stabilizer (WAPSS) is known to be effective in damping inter-area modes. However, the involvement of wide-area signals gives rise to the problem of time-delay, which may degrade the system performance. In general, time-stamped synchronized signals from Phasor Data Concentrator (PDC) are used for WAPSS, in which delays are introduced in both local and remote signals. One can opt for a feedback of remote signal only from PDC and uses the local signal as it is available, without time synchronization. This paper utilizes configurations of time-matched synchronized and nonsychronized feedback and provides the guidelines to design the controller. The controllers are synthesized using $H_\infty$ control with regional pole placement for ensuring adequate dynamic performance. To show the effectiveness of the proposed approach, two power system models have been used for the simulations. It is shown that the controllers designed based on the nonsynchronized signals are more robust to time time delay variations than the controllers using synchronized signal.
Relaxation heuristics for the set multicover problem with generalized upper bound constraints
Venue: arXiv cs.DS 2018
Year: 2018

We consider an extension of the set covering problem (SCP) introducing (i)~multicover and (ii)~generalized upper bound (GUB)~constraints. For the conventional SCP, the pricing method has been introduced to reduce the size of instances, and several efficient heuristic algorithms based on such reduction techniques have been developed to solve large-scale instances. However, GUB constraints often make the pricing method less effective, because they often prevent solutions from containing highly evaluated variables together. To overcome this problem, we develop heuristic algorithms to reduce the size of instances, in which new evaluation schemes of variables are introduced taking account of GUB constraints. We also develop an efficient implementation of a 2-flip neighborhood local search algorithm that reduces the number of candidates in the neighborhood without sacrificing the solution quality. In order to guide the search to visit a wide variety of good solutions, we also introduce a path relinking method that generates new solutions by combining two or more solutions obtained so far. According to computational comparison on benchmark instances, the proposed method succeeds in selecting a small number of promising variables properly and performs quite effectively even for large-scale instances having hard GUB constraints.
On-Grid DOA Estimation Method Using Orthogonal Matching Pursuit
Venue: arXiv cs.IT 2018
Year: 2018

Direction of Arrival (DOA) estimation of multiple narrow-band coherent or partially coherent sources is a major challenge in array signal processing. Though many subspace- based algorithms are available in literature, none of them tackle the problem of resolving coherent sources directly, e.g. without modifying the sample data covariance matrix. Compressive Sensing (CS) based sparse recovery algorithms are being applied as a novel technique to this area. In this paper, we introduce Orthogonal Matching Pursuit (OMP) to the DOA estimation problem. We demonstrate how a DOA estimation problem can be modelled for sparse recovery problem and then exploited using OMP to obtain the set of DOAs. Moreover, this algorithm uses only one snapshot to obtain the results. The simulation results demonstrate the validity and advantages of using OMP algorithm over the existing subspace- based algorithms.
Robotic Wireless Sensor Networks
Venue: arXiv cs.RO 2018
Year: 2018

In this chapter, we present a literature survey of an emerging, cutting-edge, and multi-disciplinary field of research at the intersection of Robotics and Wireless Sensor Networks (WSN) which we refer to as Robotic Wireless Sensor Networks (RWSN). We define a RWSN as an autonomous networked multi-robot system that aims to achieve certain sensing goals while meeting and maintaining certain communication performance requirements, through cooperative control, learning and adaptation. While both of the component areas, i.e., Robotics and WSN, are very well-known and well-explored, there exist a whole set of new opportunities and research directions at the intersection of these two fields which are relatively or even completely unexplored. One such example would be the use of a set of robotic routers to set up a temporary communication path between a sender and a receiver that uses the controlled mobility to the advantage of packet routing. We find that there exist only a limited number of articles to be directly categorized as RWSN related works whereas there exist a range of articles in the robotics and the WSN literature that are also relevant to this new field of research. To connect the dots, we first identify the core problems and research trends related to RWSN such as connectivity, localization, routing, and robust flow of information. Next, we classify the existing research on RWSN as well as the relevant state-of-the-arts from robotics and WSN community according to the problems and trends identified in the first step. Lastly, we analyze what is missing in the existing literature, and identify topics that require more research attention in the future.