OpenRaiser/Intern-Atlas huggingface dataset:
Age of Information in G/G/1/1 Systems
Venue: arXiv cs.IT 2018
Year: 2018

We consider a single server communication setting where the interarrival times of data updates at the source node and the service times to the destination node are arbitrarily distributed. We consider two service discipline models. If a new update arrives when the service is busy, it is dropped in the first model; and it preempts the current update in the second model. For both models, we derive exact expressions for the age of information metric with no restriction on the distributions of interarrival and service times. In addition, we derive upper bounds that are easier to calculate than the exact expressions. In the case with dropping, we also derive a second upper bound by utilizing stochastic ordering if the interarrival times have decreasing mean residual life (DMRL) and service times have new better than use in expectation (NBUE) property.
Efficient Algorithms and Lower Bounds for Robust Linear Regression
Venue: arXiv cs.LG 2018
Year: 2018

We study the problem of high-dimensional linear regression in a robust model where an $ε$-fraction of the samples can be adversarially corrupted. We focus on the fundamental setting where the covariates of the uncorrupted samples are drawn from a Gaussian distribution $\mathcal{N}(0, Σ)$ on $\mathbb{R}^d$. We give nearly tight upper bounds and computational lower bounds for this problem. Specifically, our main contributions are as follows: For the case that the covariance matrix is known to be the identity, we give a sample near-optimal and computationally efficient algorithm that outputs a candidate hypothesis vector $\widehatβ$ which approximates the unknown regression vector $β$ within $\ell_2$-norm $O(ε\log(1/ε) σ)$, where $σ$ is the standard deviation of the random observation noise. An error of $Ω(εσ)$ is information-theoretically necessary, even with infinite sample size. Prior work gave an algorithm for this problem with sample complexity $\tildeΩ(d^2/ε^2)$ whose error guarantee scales with the $\ell_2$-norm of $β$. For the case of unknown covariance, we show that we can efficiently achieve the same error guarantee as in the known covariance case using an additional $\tilde{O}(d^2/ε^2)$ unlabeled examples. On the other hand, an error of $O(εσ)$ can be information-theoretically attained with $O(d/ε^2)$ samples. We prove a Statistical Query (SQ) lower bound providing evidence that this quadratic tradeoff in the sample size is inherent. More specifically, we show that any polynomial time SQ learning algorithm for robust linear regression (in Huber's contamination model) with estimation complexity $O(d^{2-c})$, where $c>0$ is an arbitrarily small constant, must incur an error of $Ω(\sqrtε σ)$.
Resisting Adversarial Attacks using Gaussian Mixture Variational Autoencoders
Venue: arXiv cs.LG 2018
Year: 2018

Susceptibility of deep neural networks to adversarial attacks poses a major theoretical and practical challenge. All efforts to harden classifiers against such attacks have seen limited success. Two distinct categories of samples to which deep networks are vulnerable, "adversarial samples" and "fooling samples", have been tackled separately so far due to the difficulty posed when considered together. In this work, we show how one can address them both under one unified framework. We tie a discriminative model with a generative model, rendering the adversarial objective to entail a conflict. Our model has the form of a variational autoencoder, with a Gaussian mixture prior on the latent vector. Each mixture component of the prior distribution corresponds to one of the classes in the data. This enables us to perform selective classification, leading to the rejection of adversarial samples instead of misclassification. Our method inherently provides a way of learning a selective classifier in a semi-supervised scenario as well, which can resist adversarial attacks. We also show how one can reclassify the rejected adversarial samples.
Complete characterization of a class of privacy-preserving tracking problems
Venue: arXiv cs.RO 2018
Year: 2018

We examine the problem of target tracking whilst simultaneously preserving the target's privacy as epitomized by the robotic panda tracking scenario, which O'Kane introduced at the 2008 Workshop on the Algorithmic Foundations of Robotics in order to elegantly illustrate the utility of ignorance. The present paper reconsiders his formulation and the tracking strategy he proposed, along with its completeness. We explore how the capabilities of the robot and panda affect the feasibility of tracking with a privacy stipulation, uncovering intrinsic limits, no matter the strategy employed. This paper begins with a one-dimensional setting and, putting the trivially infeasible problems aside, analyzes the strategy space as a function of problem parameters. We show that it is not possible to actively track the target as well as protect its privacy for every nontrivial pair of tracking and privacy stipulations. Secondly, feasibility can be sensitive, in several cases, to the information available to the robot initially. Quite naturally in the one-dimensional model, one may quantify sensing power by the number of perceptual (or output) classes available to the robot. The robot's power to achieve privacy-preserving tracking is bounded, converging asymptotically with increasing sensing power. We analyze the entire space of possible tracking problems, characterizing every instance as either achievable, constructively by giving a policy where one exists (some of which depend on the initial information), or proving the instance impossible. Finally, to relate some of the impossibility results in one dimension to their higher-dimensional counterparts, including the planar panda tracking problem studied by O'Kane, we establish a connection between tracking dimensionality and the sensing power of a one-dimensional robot.
Multi-vehicle Flocking Control with Deep Deterministic Policy Gradient Method
Venue: arXiv cs.RO 2018
Year: 2018

Flocking control has been studied extensively along with the wide application of multi-vehicle systems. In this paper the Multi-vehicles System (MVS) flocking control with collision avoidance and communication preserving is considered based on the deep reinforcement learning framework. Specifically the deep deterministic policy gradient (DDPG) with centralized training and distributed execution process is implemented to obtain the flocking control policy. First, to avoid the dynamically changed observation of state, a three layers tensor based representation of the observation is used so that the state remains constant although the observation dimension is changing. A reward function is designed to guide the way-points tracking, collision avoidance and communication preserving. The reward function is augmented by introducing the local reward function of neighbors. Finally, a centralized training process which trains the shared policy based on common training set among all agents. The proposed method is tested under simulated scenarios with different setup.
Being curious about the answers to questions: novelty search with learned attention
Venue: arXiv cs.AI 2018
Year: 2018

We investigate the use of attentional neural network layers in order to learn a `behavior characterization' which can be used to drive novelty search and curiosity-based policies. The space is structured towards answering a particular distribution of questions, which are used in a supervised way to train the attentional neural network. We find that in a 2d exploration task, the structure of the space successfully encodes local sensory-motor contingencies such that even a greedy local `do the most novel action' policy with no reinforcement learning or evolution can explore the space quickly. We also apply this to a high/low number guessing game task, and find that guessing according to the learned attention profile performs active inference and can discover the correct number more quickly than an exact but passive approach.
Creativity in Science and the Link to Cited References: Is the Creative Potential of Papers Reflected in their Cited References?
Venue: arXiv cs.DL 2018
Year: 2018

Several authors have proposed that a large number of unusual combinations of cited references in a paper point to its high creative potential (or novelty). However, it is still not clear whether the number of unusual combinations can really measure the creative potential of papers. The current study addresses this question on the basis of several case studies from the field of scientometrics. We identified some landmark papers in this field. Study subjects were the corresponding authors of these papers. We asked them where the ideas for the papers came from and which role the cited publications played. The results revealed that the creative ideas might not necessarily have been inspired by past publications. The literature seems to be important for the contextualization of the idea in the field of scientometrics. Instead, we found that creative ideas are the result of finding solutions to practical problems, result from discussions with colleagues, and profit from interdisciplinary exchange. The roots of the studied landmark papers are discussed in detail.
SaGe: Preemptive Query Execution for High Data Availability on the Web
Venue: arXiv cs.DB 2018
Year: 2018

Semantic Web applications require querying available RDF Data with high performance and reliability. However, ensuring both data availability and performant SPARQL query execution in the context of public SPARQL servers are challenging problems. Queries could have arbitrary execution time and unknown arrival rates. In this paper, we propose SaGe, a preemptive server-side SPARQL query engine. SaGe relies on a preemptable physical query execution plan and preemptable physical operators. SaGe stops query execution after a given slice of time, saves the state of the plan and sends the saved plan back to the client with retrieved results. Later, the client can continue the query execution by resubmitting the saved plan to the server. By ensuring a fair query execution, SaGe maintains server availability and provides high query throughput. Experimental results demonstrate that SaGe outperforms the state of the art SPARQL query engines in terms of query throughput, query timeout and answer completeness.
Proportional Fairness in ALOHA Networks with RF Energy Harvesting
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we study wireless powered communication networks that employ the slotted ALOHA protocol, which is the preferred protocol for simple and uncoordinated networks. In the energy harvesting (EH) phase, the base station broadcasts radio frequency energy to the EH users (EHUs). The EHUs harvest the broadcasted energy and use it to transmit information back to the base station by contending for access to the uplink channel in the random access (RA) phase. In order to ensure fairness among the users, we propose a proportionally fair resource allocation scheme that exploits the RA nature of slotted ALOHA. Specifically, assuming statistical channel state information, we determine the optimal transmit power at the base station, the optimal durations of the EH and RA phases, the channel access probability, and the rate of each EHU.
The Complexity of Bisimulation and Simulation on Finite Systems
Venue: arXiv cs.LO 2018
Year: 2018

In this paper the computational complexity of the (bi)simulation problem over restricted graph classes is studied. For trees given as pointer structures or terms the (bi)simulation problem is complete for logarithmic space or NC$^1$, respectively. This solves an open problem from Balcázar, Gabarró, and Sántha. Furthermore, if only one of the input graphs is required to be a tree, the bisimulation (simulation) problem is contained in AC$^1$ (LogCFL). In contrast, it is also shown that the simulation problem is P-complete already for graphs of bounded path-width.
A Revision Control System for Image Editing in Collaborative Multimedia Design
Venue: arXiv cs.MM 2018
Year: 2018

Revision control is a vital component in the collaborative development of artifacts such as software code and multimedia. While revision control has been widely deployed for text files, very few attempts to control the versioning of binary files can be found in the literature. This can be inconvenient for graphics applications that use a significant amount of binary data, such as images, videos, meshes, and animations. Existing strategies such as storing whole files for individual revisions or simple binary deltas, respectively consume significant storage and obscure semantic information. To overcome these limitations, in this paper we present a revision control system for digital images that stores revisions in form of graphs. Besides, being integrated with Git, our revision control system also facilitates artistic creation processes in common image editing and digital painting workflows. A preliminary user study demonstrates the usability of the proposed system.
Well defined quantum key distribution using calibration, synchronization, and a programmable quantum channel
Venue: arXiv cs.CR 2018
Year: 2018

Well defined quantum key distribution between two users requires both calibration to ensure quantum effects and synchronization to stabilize the bit parity of the results. Here we present two quantum effects regarding two entangled photons in a single fiber that can be used for both calibration and synchronization. In particular, we show how the synchronization problem can be transformed from a maximization of the bit parity between two photons sent to two users to finding an average 50/50 bit parity for two photons sent to a single user; the end result being first order feedback rather than second order feedback. Once we show how to calibrate and synchronize a quantum channel for two users, we then show how to introduce multiple users through a programmable quantum channel that can change its configuration depending on who needs to exchange quantum information. The programmable quantum channel is created by using a programmable classical channel to control the quantum devices as well as introducing new metadata on the classical channel specific to quantum applications.
A Reinforcement Learning Approach to Age of Information in Multi-User Networks
Venue: arXiv cs.LG 2018
Year: 2018

Scheduling the transmission of time-sensitive data to multiple users over error-prone communication channels is studied with the goal of minimizing the long-term average age of information (AoI) at the users under a constraint on the average number of transmissions at the source node. After each transmission, the source receives an instantaneous ACK/NACK feedback from the intended receiver and decides on what time and to which user to transmit the next update. The optimal scheduling policy is first studied under different feedback mechanisms when the channel statistics are known; in particular, the standard automatic repeat request (ARQ) and hybrid ARQ (HARQ) protocols are considered. Then a reinforcement learning (RL) approach is introduced, which does not assume any a priori information on the random processes governing the channel states. Different RL methods are verified and compared through numerical simulations.
Domain Adaptation for MRI Organ Segmentation using Reverse Classification Accuracy
Venue: arXiv cs.CV 2018
Year: 2018

The variations in multi-center data in medical imaging studies have brought the necessity of domain adaptation. Despite the advancement of machine learning in automatic segmentation, performance often degrades when algorithms are applied on new data acquired from different scanners or sequences than the training data. Manual annotation is costly and time consuming if it has to be carried out for every new target domain. In this work, we investigate automatic selection of suitable subjects to be annotated for supervised domain adaptation using the concept of reverse classification accuracy (RCA). RCA predicts the performance of a trained model on data from the new domain and different strategies of selecting subjects to be included in the adaptation via transfer learning are evaluated. We perform experiments on a two-center MR database for the task of organ segmentation. We show that subject selection via RCA can reduce the burden of annotation of new data for the target domain.
Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients
Venue: arXiv cs.LG 2018
Year: 2018

We show that Newton's method converges globally at a linear rate for objective functions whose Hessians are stable. This class of problems includes many functions which are not strongly convex, such as logistic regression. Our linear convergence result is (i) affine-invariant, and holds even if an (ii) approximate Hessian is used, and if the subproblems are (iii) only solved approximately. Thus we theoretically demonstrate the superiority of Newton's method over first-order methods, which would only achieve a sublinear $O(1/t^2)$ rate under similar conditions.
Do CIFAR-10 Classifiers Generalize to CIFAR-10?
Venue: arXiv cs.LG 2018
Year: 2018

Machine learning is currently dominated by largely experimental work focused on improvements in a few key tasks. However, the impressive accuracy numbers of the best performing models are questionable because the same test sets have been used to select these models for multiple years now. To understand the danger of overfitting, we measure the accuracy of CIFAR-10 classifiers by creating a new test set of truly unseen images. Although we ensure that the new test set is as close to the original data distribution as possible, we find a large drop in accuracy (4% to 10%) for a broad range of deep learning models. Yet more recent models with higher original accuracy show a smaller drop and better overall performance, indicating that this drop is likely not due to overfitting based on adaptivity. Instead, we view our results as evidence that current accuracy numbers are brittle and susceptible to even minute natural variations in the data distribution.
Backpropagation for Implicit Spectral Densities
Venue: arXiv cs.LG 2018
Year: 2018

Most successful machine intelligence systems rely on gradient-based learning, which is made possible by backpropagation. Some systems are designed to aid us in interpreting data when explicit goals cannot be provided. These unsupervised systems are commonly trained by backpropagating through a likelihood function. We introduce a tool that allows us to do this even when the likelihood is not explicitly set, by instead using the implicit likelihood of the model. Explicitly defining the likelihood often entails making heavy-handed assumptions that impede our ability to solve challenging tasks. On the other hand, the implicit likelihood of the model is accessible without the need for such assumptions. Our tool, which we call spectral backpropagation, allows us to optimize it in much greater generality than what has been attempted before. GANs can also be viewed as a technique for optimizing implicit likelihoods. We study them using spectral backpropagation in order to demonstrate robustness for high-dimensional problems, and identify two novel properties of the generator G: (1) there exist aberrant, nonsensical outputs to which G assigns very high likelihood, and (2) the eigenvectors of the metric induced by G over latent space correspond to quasi-disentangled explanatory factors.
The Externalities of Exploration and How Data Diversity Helps Exploitation
Venue: arXiv cs.LG 2018
Year: 2018

Online learning algorithms, widely used to power search and content optimization on the web, must balance exploration and exploitation, potentially sacrificing the experience of current users for information that will lead to better decisions in the future. Recently, concerns have been raised about whether the process of exploration could be viewed as unfair, placing too much burden on certain individuals or groups. Motivated by these concerns, we initiate the study of the externalities of exploration - the undesirable side effects that the presence of one party may impose on another - under the linear contextual bandits model. We introduce the notion of a group externality, measuring the extent to which the presence of one population of users impacts the rewards of another. We show that this impact can in some cases be negative, and that, in a certain sense, no algorithm can avoid it. We then study externalities at the individual level, interpreting the act of exploration as an externality imposed on the current user of a system by future users. This drives us to ask under what conditions inherent diversity in the data makes explicit exploration unnecessary. We build on a recent line of work on the smoothed analysis of the greedy algorithm that always chooses the action that currently looks optimal, improving on prior results to show that a greedy approach almost matches the best possible Bayesian regret rate of any other algorithm on the same problem instance whenever the diversity conditions hold, and that this regret is at most $\tilde{O}(T^{1/3})$. Returning to group-level effects, we show that under the same conditions, negative group externalities essentially vanish under the greedy algorithm. Together, our results uncover a sharp contrast between the high externalities that exist in the worst case, and the ability to remove all externalities if the data is sufficiently diverse.
Does the brain represent words? An evaluation of brain decoding studies of language understanding
Venue: arXiv cs.CL 2018
Year: 2018

Language decoding studies have identified word representations which can be used to predict brain activity in response to novel words and sentences (Anderson et al., 2016; Pereira et al., 2018). The unspoken assumption of these studies is that, during processing, linguistic information is transformed into some shared semantic space, and those semantic representations are then used for a variety of linguistic and non-linguistic tasks. We claim that current studies vastly underdetermine the content of these representations, the algorithms which the brain deploys to produce and consume them, and the computational tasks which they are designed to solve. We illustrate this indeterminacy with an extension of the sentence-decoding experiment of Pereira et al. (2018), showing how standard evaluations fail to distinguish between language processing models which deploy different mechanisms and which are optimized to solve very different tasks. We conclude by suggesting changes to the brain decoding paradigm which can support stronger claims of neural representation.
GamePad: A Learning Environment for Theorem Proving
Venue: arXiv cs.LG 2018
Year: 2018

In this paper, we introduce a system called GamePad that can be used to explore the application of machine learning methods to theorem proving in the Coq proof assistant. Interactive theorem provers such as Coq enable users to construct machine-checkable proofs in a step-by-step manner. Hence, they provide an opportunity to explore theorem proving with human supervision. We use GamePad to synthesize proofs for a simple algebraic rewrite problem and train baseline models for a formalization of the Feit-Thompson theorem. We address position evaluation (i.e., predict the number of proof steps left) and tactic prediction (i.e., predict the next proof step) tasks, which arise naturally in tactic-based theorem proving.