OpenRaiser/Intern-Atlas huggingface dataset:
A Note on Approximating Weighted Independence on Intersection Graphs of Paths on a Grid
Venue: arXiv cs.CG 2018
Year: 2018

A graph $G$ is called $B_k$-VPG, for some constant $k\geq 0$, if it has a string representation on an axis-parallel grid such that each vertex is a path with at most $k$ bends and two vertices are adjacent in $G$ if and only if the corresponding paths intersect each other. The part of a path that is between two consecutive bends is called a segment of the path. In this paper, we study the Maximum-Weighted Independent Set problem on $B_k$-VPG graphs. The problem is known to be NP-complete on $B_1$-VPG graphs, even when the two segments of every path have unit length [12], and $O(\log n)$-approximation algorithms are known on $B_k$-VPG graphs, for $k\leq 2$ [3, 14]. In this paper, we give a $(ck+c+1)$-approximation algorithm for the problem on $B_k$-VPG graphs for any $k\geq 0$, where $c>0$ is the length of the longest segment among all segments of paths in the graph. Notice that $c$ is not required to be a constant; for instance, when $c\in O(\log \log n)$, we get an $O(\log \log n)$-approximation or we get an $O(1)$-approximation when $c$ is a constant. To our knowledge, this is the first $o(\log n)$-approximation algorithm for a non-trivial subclass of $B_k$-VPG graphs.
Resilient Autonomous Control of Distributed Multi-agent Systems in Contested Environments
Venue: arXiv cs.MA 2018
Year: 2018

An autonomous and resilient controller is proposed for leader-follower multi-agent systems under uncertainties and cyber-physical attacks. The leader is assumed non-autonomous with a nonzero control input, which allows changing the team behavior or mission in response to environmental changes. A resilient learning-based control protocol is presented to find optimal solutions to the synchronization problem in the presence of attacks and system dynamic uncertainties. An observer-based distributed H_infinity controller is first designed to prevent propagating the effects of attacks on sensors and actuators throughout the network, as well as to attenuate the effect of these attacks on the compromised agent itself. Non-homogeneous game algebraic Riccati equations are derived to solve the H_infinity optimal synchronization problem and off-policy reinforcement learning is utilized to learn their solution without requiring any knowledge of the agent's dynamics. A trust-confidence based distributed control protocol is then proposed to mitigate attacks that hijack the entire node and attacks on communication links. A confidence value is defined for each agent based solely on its local evidence. The proposed resilient reinforcement learning algorithm employs the confidence value of each agent to indicate the trustworthiness of its own information and broadcast it to its neighbors to put weights on the data they receive from it during and after learning. If the confidence value of an agent is low, it employs a trust mechanism to identify compromised agents and remove the data it receives from them from the learning process. Simulation results are provided to show the effectiveness of the proposed approach.
Walking Through Waypoints
Venue: arXiv cs.DS 2018
Year: 2018

We initiate the study of a fundamental combinatorial problem: Given a capacitated graph $G=(V,E)$, find a shortest walk ("route") from a source $s\in V$ to a destination $t\in V$ that includes all vertices specified by a set $\mathscr{W}\subseteq V$: the \emph{waypoints}. This waypoint routing problem finds immediate applications in the context of modern networked distributed systems. Our main contribution is an exact polynomial-time algorithm for graphs of bounded treewidth. We also show that if the number of waypoints is logarithmically bounded, exact polynomial-time algorithms exist even for general graphs. Our two algorithms provide an almost complete characterization of what can be solved exactly in polynomial-time: we show that more general problems (e.g., on grid graphs of maximum degree 3, with slightly more waypoints) are computationally intractable.
Model based learning for accelerated, limited-view 3D photoacoustic tomography
Venue: arXiv cs.CV 2018
Year: 2018

Recent advances in deep learning for tomographic reconstructions have shown great potential to create accurate and high quality images with a considerable speed-up. In this work we present a deep neural network that is specifically designed to provide high resolution 3D images from restricted photoacoustic measurements. The network is designed to represent an iterative scheme and incorporates gradient information of the data fit to compensate for limited view artefacts. Due to the high complexity of the photoacoustic forward operator, we separate training and computation of the gradient information. A suitable prior for the desired image structures is learned as part of the training. The resulting network is trained and tested on a set of segmented vessels from lung CT scans and then applied to in-vivo photoacoustic measurement data.
Convex skeletons of complex networks
Venue: arXiv cs.SI 2018
Year: 2018

A convex network can be defined as a network such that every connected induced subgraph includes all the shortest paths between its nodes. Fully convex network would therefore be a collection of cliques stitched together in a tree. In this paper, we study the largest high-convexity part of empirical networks obtained by removing the least number of edges, which we call a convex skeleton. A convex skeleton is a generalisation of a network spanning tree in which each edge can be replaced by a clique of arbitrary size. We present different approaches for extracting convex skeletons and apply them to social collaboration and protein interactions networks, autonomous systems graphs and food webs. We show that the extracted convex skeletons retain the degree distribution, clustering, connectivity, distances, node position and also community structure, while making the shortest paths between the nodes largely unique. Moreover, in the Slovenian computer scientists coauthorship network, a convex skeleton retains the strongest ties between the authors, differently from a spanning tree or high-betweenness backbone and high-salience skeleton. A convex skeleton thus represents a simple definition of a network backbone with applications in coauthorship and other social collaboration networks.
Algorithmically probable mutations reproduce aspects of evolution such as convergence rate, genetic memory, and modularity
Venue: arXiv cs.NE 2018
Year: 2018

Natural selection explains how life has evolved over millions of years from more primitive forms. The speed at which this happens, however, has sometimes defied formal explanations when based on random (uniformly distributed) mutations. Here we investigate the application of a simplicity bias based on a natural but algorithmic distribution of mutations (no recombination) in various examples, particularly binary matrices in order to compare evolutionary convergence rates. Results both on synthetic and on small biological examples indicate an accelerated rate when mutations are not statistical uniform but \textit{algorithmic uniform}. We show that algorithmic distributions can evolve modularity and genetic memory by preservation of structures when they first occur sometimes leading to an accelerated production of diversity but also population extinctions, possibly explaining naturally occurring phenomena such as diversity explosions (e.g. the Cambrian) and massive extinctions (e.g. the End Triassic) whose causes are currently a cause for debate. The natural approach introduced here appears to be a better approximation to biological evolution than models based exclusively upon random uniform mutations, and it also approaches a formal version of open-ended evolution based on previous formal results. These results validate some suggestions in the direction that computation may be an equally important driver of evolution. We also show that inducing the method on problems of optimization, such as genetic algorithms, has the potential to accelerate convergence of artificial evolutionary algorithms.
Space-efficient classical and quantum algorithms for the shortest vector problem
Venue: arXiv cs.DS 2018
Year: 2018

A lattice is the integer span of some linearly independent vectors. Lattice problems have many significant applications in coding theory and cryptographic systems for their conjectured hardness. The Shortest Vector Problem (SVP), which is to find the shortest non-zero vector in a lattice, is one of the well-known problems that are believed to be hard to solve, even with a quantum computer. In this paper we propose space-efficient classical and quantum algorithms for solving SVP. Currently the best time-efficient algorithm for solving SVP takes $2^{n+o(n)}$ time and $2^{n+o(n)}$ space. Our classical algorithm takes $2^{2.05n+o(n)}$ time to solve SVP with only $2^{0.5n+o(n)}$ space. We then modify our classical algorithm to a quantum version, which can solve SVP in time $2^{1.2553n+o(n)}$ with $2^{0.5n+o(n)}$ classical space and only poly(n) qubits.
Visual art inspired by the collective feeding behavior of sand-bubbler crabs
Venue: arXiv cs.NE 2018
Year: 2018

Sand--bubblers are crabs of the genera Dotilla and Scopimera which are known to produce remarkable patterns and structures at tropical beaches. From these pattern-making abilities, we may draw inspiration for digital visual art. A simple mathematical model is proposed and an algorithm is designed that may create such sand-bubbler patterns artificially. In addition, design parameters to modify the patterns are identified and analyzed by computational aesthetic measures. Finally, an extension of the algorithm is discussed that may enable controlling and guiding generative evolution of the art-making process.
A Generative Model For Zero Shot Learning Using Conditional Variational Autoencoders
Venue: arXiv cs.CV 2018
Year: 2018

Zero shot learning in Image Classification refers to the setting where images from some novel classes are absent in the training data but other information such as natural language descriptions or attribute vectors of the classes are available. This setting is important in the real world since one may not be able to obtain images of all the possible classes at training. While previous approaches have tried to model the relationship between the class attribute space and the image space via some kind of a transfer function in order to model the image space correspondingly to an unseen class, we take a different approach and try to generate the samples from the given attributes, using a conditional variational autoencoder, and use the generated samples for classification of the unseen classes. By extensive testing on four benchmark datasets, we show that our model outperforms the state of the art, particularly in the more realistic generalized setting, where the training classes can also appear at the test time along with the novel classes.
Compressed Sensing MRI Reconstruction using a Generative Adversarial Network with a Cyclic Loss
Venue: arXiv cs.CV 2018
Year: 2018

Compressed Sensing MRI (CS-MRI) has provided theoretical foundations upon which the time-consuming MRI acquisition process can be accelerated. However, it primarily relies on iterative numerical solvers which still hinders their adaptation in time-critical applications. In addition, recent advances in deep neural networks have shown their potential in computer vision and image processing, but their adaptation to MRI reconstruction is still in an early stage. In this paper, we propose a novel deep learning-based generative adversarial model, RefineGAN, for fast and accurate CS-MRI reconstruction. The proposed model is a variant of fully-residual convolutional autoencoder and generative adversarial networks (GANs), specifically designed for CS-MRI formulation; it employs deeper generator and discriminator networks with cyclic data consistency loss for faithful interpolation in the given under-sampled k-space data. In addition, our solution leverages a chained network to further enhance the reconstruction quality. RefineGAN is fast and accurate -- the reconstruction process is extremely rapid, as low as tens of milliseconds for reconstruction of a 256x256 image, because it is one-way deployment on a feed-forward network, and the image quality is superior even for extremely low sampling rate (as low as 10%) due to the data-driven nature of the method. We demonstrate that RefineGAN outperforms the state-of-the-art CS-MRI methods by a large margin in terms of both running time and image quality via evaluation using several open-source MRI databases.
A Unified Query-based Generative Model for Question Generation and Question Answering
Venue: arXiv cs.CL 2018
Year: 2018

We propose a query-based generative model for solving both tasks of question generation (QG) and question an- swering (QA). The model follows the classic encoder- decoder framework. The encoder takes a passage and a query as input then performs query understanding by matching the query with the passage from multiple per- spectives. The decoder is an attention-based Long Short Term Memory (LSTM) model with copy and coverage mechanisms. In the QG task, a question is generated from the system given the passage and the target answer, whereas in the QA task, the answer is generated given the question and the passage. During the training stage, we leverage a policy-gradient reinforcement learning algorithm to overcome exposure bias, a major prob- lem resulted from sequence learning with cross-entropy loss. For the QG task, our experiments show higher per- formances than the state-of-the-art results. When used as additional training data, the automatically generated questions even improve the performance of a strong ex- tractive QA system. In addition, our model shows bet- ter performance than the state-of-the-art baselines of the generative QA task.
SafeKeeper: Protecting Web Passwords using Trusted Execution Environments
Venue: arXiv cs.CR 2018
Year: 2018

Passwords are undoubtedly the most dominant user authentication mechanism on the web today. Although they are inexpensive and easy-to-use, security concerns of password-based authentication are serious. Phishing and theft of password databases are two critical concerns. The tendency of users to re-use passwords across different services exacerbates the impact of these two concerns. Current solutions addressing these concerns are not fully satisfactory: they typically address only one of the two concerns; they do not protect passwords from rogue servers; they do not provide any verifiable evidence of their (server-side) adoption to users; and they face deployability challenges in terms of the cost for service providers and/or ease-of-use for end users. We present SafeKeeper, a comprehensive approach to protect the confidentiality of passwords in web authentication systems. Unlike previous approaches, SafeKeeper protects user passwords against very strong adversaries, including rogue servers and sophisticated external phishers. It is relatively inexpensive to deploy as it (i) uses widely available hardware security mechanisms like Intel SGX, (ii) is integrated into popular web platforms like WordPress, and (iii) has small performance overhead. We describe a variety of challenges in designing and implementing such a system, and how we overcome them. Through an 86-participant user study, and systematic analysis and experiments, we demonstrate the usability, security and deployability of SafeKeeper, which is available as open-source.
CONE: Community Oriented Network Embedding
Venue: arXiv cs.SI 2018
Year: 2018

Detecting communities has long been popular in the research on networks. It is usually modeled as an unsupervised clustering problem on graphs, based on heuristic assumptions about community characteristics, such as edge density and node homogeneity. In this work, we doubt the universality of these widely adopted assumptions and compare human labeled communities with machine predicted ones obtained via various mainstream algorithms. Based on supportive results, we argue that communities are defined by various social patterns and unsupervised learning based on heuristics is incapable of capturing all of them. Therefore, we propose to inject supervision into community detection through Community Oriented Network Embedding (CONE), which leverages limited ground-truth communities as examples to learn an embedding model aware of the social patterns underlying them. Specifically, a deep architecture is developed by combining recurrent neural networks with random-walks on graphs towards capturing social patterns directed by ground-truth communities. Generic clustering algorithms on the embeddings of other nodes produced by the learned model then effectively reveals more communities that share similar social patterns with the ground-truth ones.
Robust Semi-Cooperative Multi-Agent Coordination in the Presence of Stochastic Disturbances
Venue: arXiv cs.SY 2018
Year: 2018

This paper presents a robust distributed coordination protocol that achieves generation of collision-free trajectories for multiple unicycle agents in the presence of stochastic uncertainties. We build upon our earlier work on semi-cooperative coordination and we redesign the coordination controllers so that the agents counteract a class of state (wind) disturbances and measurement noise. Safety and convergence is proved analytically, while simulation results demonstrate the efficacy of the proposed solution.
Trace-Based Run-time Analysis of Message-Passing Go Programs
Venue: arXiv cs.PL 2018
Year: 2018

We consider the task of analyzing message-passing programs by observing their run-time behavior. We introduce a purely library-based instrumentation method to trace communication events during execution. A model of the dependencies among events can be constructed to identify potential bugs. Compared to the vector clock method, our approach is much simpler and has in general a significant lower run-time overhead. A further advantage is that we also trace events that could not commit. Thus, we can infer alternative communications. This provides the user with additional information to identify potential bugs. We have fully implemented our approach in the Go programming language and provide a number of examples to substantiate our claims.
Spoken English Intelligibility Remediation with PocketSphinx Alignment and Feature Extraction Improves Substantially over the State of the Art
Venue: arXiv cs.CL 2018
Year: 2018

We use automatic speech recognition to assess spoken English learner pronunciation based on the authentic intelligibility of the learners' spoken responses determined from support vector machine (SVM) classifier or deep learning neural network model predictions of transcription correctness. Using numeric features produced by PocketSphinx alignment mode and many recognition passes searching for the substitution and deletion of each expected phoneme and insertion of unexpected phonemes in sequence, the SVM models achieve 82 percent agreement with the accuracy of Amazon Mechanical Turk crowdworker transcriptions, up from 75 percent reported by multiple independent researchers. Using such features with SVM classifier probability prediction models can help computer-aided pronunciation teaching (CAPT) systems provide intelligibility remediation.
Synthetic Medical Images from Dual Generative Adversarial Networks
Venue: arXiv cs.CV 2018
Year: 2018

Currently there is strong interest in data-driven approaches to medical image classification. However, medical imaging data is scarce, expensive, and fraught with legal concerns regarding patient privacy. Typical consent forms only allow for patient data to be used in medical journals or education, meaning the majority of medical data is inaccessible for general public research. We propose a novel, two-stage pipeline for generating synthetic medical images from a pair of generative adversarial networks, tested in practice on retinal fundi images. We develop a hierarchical generation process to divide the complex image generation task into two parts: geometry and photorealism. We hope researchers will use our pipeline to bring private medical data into the public domain, sparking growth in imaging tasks that have previously relied on the hand-tuning of models. We have begun this initiative through the development of SynthMed, an online repository for synthetic medical images.
Basic Filters for Convolutional Neural Networks Applied to Music: Training or Design?
Venue: arXiv cs.LG 2018
Year: 2018

When convolutional neural networks are used to tackle learning problems based on music or, more generally, time series data, raw one-dimensional data are commonly pre-processed to obtain spectrogram or mel-spectrogram coefficients, which are then used as input to the actual neural network. In this contribution, we investigate, both theoretically and experimentally, the influence of this pre-processing step on the network's performance and pose the question, whether replacing it by applying adaptive or learned filters directly to the raw data, can improve learning success. The theoretical results show that approximately reproducing mel-spectrogram coefficients by applying adaptive filters and subsequent time-averaging is in principle possible. We also conducted extensive experimental work on the task of singing voice detection in music. The results of these experiments show that for classification based on Convolutional Neural Networks the features obtained from adaptive filter banks followed by time-averaging perform better than the canonical Fourier-transform-based mel-spectrogram coefficients. Alternative adaptive approaches with center frequencies or time-averaging lengths learned from training data perform equally well.
Fixed-Gain Augmented-State Tracking-Filters
Venue: arXiv cs.SY 2018
Year: 2018

A procedure for the design of fixed-gain tracking filters, using an augmented-state observer with signal and interference subspaces, is proposed. The signal subspace incorporates an integrating Newtonian model and a second-order maneuver model that is matched to a sustained constant-g turn; the deterministic interference model creates a Nyquist null for smoother track estimates. The selected models provide a simple means of shaping and analyzing the (transient and steady-state) response of tracking-filters of elevated order.
Algorithmically generated subject categories based on citation relations: An empirical micro study using papers on overall water splitting
Venue: arXiv cs.DL 2018
Year: 2018

One important reason for the use of field categorization in bibliometrics is the necessity to make citation impact of papers published in different scientific fields comparable with each other. Raw citations are normalized by using field-normalization schemes to achieve comparable citation scores. There are different approaches to field categorization available. They can be broadly classified as intellectual and algorithmic approaches. A paper-based algorithmically constructed classification system (ACCS) was proposed which is based on citation relations. Using a few ACCS field-specific clusters, we investigate the discriminatory power of the ACCS. The micro study focusses on the topic "overall water splitting" and related topics. The first part of the study investigates intellectually whether the ACCS is able to identify papers on overall water splitting reliably and validly. Next, we compare the ACCS with (1) a paper-based intellectual (INSPEC) classification and (2) a journal-based intellectual classification (Web of Science, WoS, subject categories). In the last part of our case study, we compare the average number of citations in selected ACCS clusters (on overall water splitting and related topics) with the average citation count of publications in WoS subject categories related to these clusters. The results of this micro study question the discriminatory power of the ACCS. We recommend larger follow-up studies on broad datasets.