OpenRaiser/Intern-Atlas huggingface dataset:
Learning Orthogonal Projections in Linear Bandits
Venue: arXiv cs.LG 2019
Year: 2019

In a linear stochastic bandit model, each arm is a vector in an Euclidean space and the observed return at each time step is an unknown linear function of the chosen arm at that time step. In this paper, we investigate the problem of learning the best arm in a linear stochastic bandit model, where each arm's expected reward is an unknown linear function of the projection of the arm onto a subspace. We call this the projection reward. Unlike the classical linear bandit problem in which the observed return corresponds to the reward, the projection reward at each time step is unobservable. Such a model is useful in recommendation applications where the observed return includes corruption by each individual's biases, which we wish to exclude in the learned model. In the case where there are finitely many arms, we develop a strategy to achieve $O(|\bbD|\log n)$ regret, where $n$ is the number of time steps and $|\bbD|$ is the number of arms. In the case where each arm is chosen from an infinite compact set, our strategy achieves $O(n^{2/3}(\log{n})^{1/2})$ regret. Experiments verify the efficiency of our strategy.
Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
Venue: arXiv cs.DS 2019
Year: 2019

The area of parameterized approximation seeks to combine approximation and parameterized algorithms to obtain, e.g., (1+eps)-approximations in f(k,eps)n^{O(1)} time where k is some parameter of the input. We obtain the following results on parameterized approximability: 1) In the maximum independent set of rectangles problem (MISR) we are given a collection of n axis parallel rectangles in the plane. Our goal is to select a maximum-cardinality subset of pairwise non-overlapping rectangles. This problem is NP-hard and also W[1]-hard [Marx, ESA'05]. The best-known polynomial-time approximation factor is O(loglog n) [Chalermsook and Chuzhoy, SODA'09] and it admits a QPTAS [Adamaszek and Wiese, FOCS'13; Chuzhoy and Ene, FOCS'16]. Here we present a parameterized approximation scheme (PAS) for MISR, i.e. an algorithm that, for any given constant eps>0 and integer k>0, in time f(k,eps)n^{g(eps)}, either outputs a solution of size at least k/(1+eps), or declares that the optimum solution has size less than k. 2) In the (2-dimensional) geometric knapsack problem (TDK) we are given an axis-aligned square knapsack and a collection of axis-aligned rectangles in the plane (items). Our goal is to translate a maximum cardinality subset of items into the knapsack so that the selected items do not overlap. In the version of TDK with rotations (TDKR), we are allowed to rotate items by 90 degrees. Both variants are NP-hard, and the best-known polynomial-time approximation factors are 558/325+eps and 4/3+eps, resp. [Galvez et al., FOCS'17]. These problems admit a QPTAS for polynomially bounded item sizes [Adamaszek and Wiese, SODA'15]. We show that both variants are W[1]-hard. Furthermore, we present a PAS for TDKR. For all considered problems, getting time f(k,eps)n^{O(1)}, rather than f(k,eps)n^{g(eps)}, would give FPT time f'(k)n^{O(1)} exact algorithms using eps=1/(k+1), contradicting W[1]-hardness.
Comparing Popularity of Testing Careers among Canadian, Chinese, Indian Students
Venue: arXiv cs.SE 2019
Year: 2019

Despite its importance, software testing is, arguably, the least understood part of the software life cycle and still the toughest to perform correctly. Many researchers and practitioners have been working to address the situation. However, most of the studies focus on the process and technology dimensions and only a few on the human dimension of testing, in spite of the reported relevance of human aspects of software testing. Testers need to understand various stakeholders explicit and implicit requirements, be aware of how developers work individually and in teams, and develop skills to report test results wisely to stakeholders. These multifaceted qualifications lend vitality to the human dimension in software testing. Exploring this human dimension carefully may help understand testing in a better way.
Further advantages of data augmentation on convolutional neural networks
Venue: arXiv cs.CV 2019
Year: 2019

Data augmentation is a popular technique largely used to enhance the training of convolutional neural networks. Although many of its benefits are well known by deep learning researchers and practitioners, its implicit regularization effects, as compared to popular explicit regularization techniques, such as weight decay and dropout, remain largely unstudied. As a matter of fact, convolutional neural networks for image object classification are typically trained with both data augmentation and explicit regularization, assuming the benefits of all techniques are complementary. In this paper, we systematically analyze these techniques through ablation studies of different network architectures trained with different amounts of training data. Our results unveil a largely ignored advantage of data augmentation: networks trained with just data augmentation more easily adapt to different architectures and amount of training data, as opposed to weight decay and dropout, which require specific fine-tuning of their hyperparameters.
EdgeLens: Deep Learning based Object Detection in Integrated IoT, Fog and Cloud Computing Environments
Venue: arXiv cs.DC 2019
Year: 2019

Data-intensive applications are growing at an increasing rate and there is a growing need to solve scalability and high-performance issues in them. By the advent of Cloud computing paradigm, it became possible to harness remote resources to build and deploy these applications. In recent years, new set of applications and services based on Internet of Things (IoT) paradigm, require to process large amount of data in very less time. Among them surveillance and object detection have gained prime importance, but cloud is unable to bring down the network latencies to meet the response time requirements. This problem is solved by Fog computing which harnesses resources in the edge of the network along with remote cloud resources as required. However, there is still a lack of frameworks that are successfully able to integrate sophisticated software and applications, especially deep learning, with fog and cloud computing environments. In this work, we propose a framework to deploy deep learning-based applications in fog-cloud environments to harness edge and cloud resources to provide better service quality for such applications. Our proposed framework, called EdgeLens, adapts to the application or user requirements to provide high accuracy or low latency modes of services. We also tested the performance of the software in terms of accuracy, response time, jitter, network bandwidth and power consumption and show how EdgeLens adapts to different service requirements.
Expected Sarsa($λ$) with Control Variate for Variance Reduction
Venue: arXiv cs.LG 2019
Year: 2019

Off-policy learning is powerful for reinforcement learning. However, the high variance of off-policy evaluation is a critical challenge, which causes off-policy learning falls into an uncontrolled instability. In this paper, for reducing the variance, we introduce control variate technique to $\mathtt{Expected}$ $\mathtt{Sarsa}$($λ$) and propose a tabular $\mathtt{ES}$($λ$)-$\mathtt{CV}$ algorithm. We prove that if a proper estimator of value function reaches, the proposed $\mathtt{ES}$($λ$)-$\mathtt{CV}$ enjoys a lower variance than $\mathtt{Expected}$ $\mathtt{Sarsa}$($λ$). Furthermore, to extend $\mathtt{ES}$($λ$)-$\mathtt{CV}$ to be a convergent algorithm with linear function approximation, we propose the $\mathtt{GES}$($λ$) algorithm under the convex-concave saddle-point formulation. We prove that the convergence rate of $\mathtt{GES}$($λ$) achieves $\mathcal{O}(1/T)$, which matches or outperforms lots of state-of-art gradient-based algorithms, but we use a more relaxed condition. Numerical experiments show that the proposed algorithm performs better with lower variance than several state-of-art gradient-based TD learning algorithms: $\mathtt{GQ}$($λ$), $\mathtt{GTB}$($λ$) and $\mathtt{ABQ}$($ζ$).
Non-malleable Coding for Arbitrary Varying Channels
Venue: arXiv cs.IT 2019
Year: 2019

Non-malleable codes protect against an adversary who can tamper with the coded message by using a tampering function in a specified function family, guaranteeing that the tampering result will only depend on the chosen function and not the coded message. The codes have been motivated for providing protection against tampering with hardware that stores the secret cryptographic keys, and have found significant attention in cryptography. Traditional Shannon model of communication systems assumes the communication channel is perfectly known to the transmitter and the receiver. Arbitrary Varying Channels (AVCs) remove this assumption and have been used to model adversarially controlled channels. Transmission over these channels has been originally studied with the goal of recovering the sent message, and more recently with the goal of detecting tampering with the sent messages. In this paper we introduce non-malleability as the protection goal of message transmission over these channels, and study binary (discrete memoryless) AVCs where possible tampering is modelled by the set of channel states. Our main result is that non-malleability for these channels is achievable at a rate asymptotically approaching 1. We also consider the setting of an AVC with a special state s*, and the additional requirement that the message must be recoverable if s* is applied to all the transmitted bits. We give the outline of a message encoding scheme that in addition to non-malleability, can provide recovery for all s* channel.
AGAN: Towards Automated Design of Generative Adversarial Networks
Venue: arXiv cs.LG 2019
Year: 2019

Recent progress in Generative Adversarial Networks (GANs) has shown promising signs of improving GAN training via architectural change. Despite some early success, at present the design of GAN architectures requires human expertise, laborious trial-and-error testings, and often draws inspiration from its image classification counterpart. In the current paper, we present the first neural architecture search algorithm, automated neural architecture search for deep generative models, or AGAN for abbreviation, that is specifically suited for GAN training. For unsupervised image generation tasks on CIFAR-10, our algorithm finds architecture that outperforms state-of-the-art models under same regularization techniques. For supervised tasks, the automatically searched architectures also achieve highly competitive performance, outperforming best human-invented architectures at resolution $32\times32$. Moreover, we empirically demonstrate that the modules learned by AGAN are transferable to other image generation tasks such as STL-10.
Mapped Convolutions
Venue: arXiv cs.CV 2019
Year: 2019

We present a versatile formulation of the convolution operation that we term a "mapped convolution." The standard convolution operation implicitly samples the pixel grid and computes a weighted sum. Our mapped convolution decouples these two components, freeing the operation from the confines of the image grid and allowing the kernel to process any type of structured data. As a test case, we demonstrate its use by applying it to dense inference on spherical data. We perform an in-depth study of existing spherical image convolution methods and propose an improved sampling method for equirectangular images. Then, we discuss the impact of data discretization when deriving a sampling function, highlighting drawbacks of the cube map representation for spherical data. Finally, we illustrate how mapped convolutions enable us to convolve directly on a mesh by projecting the spherical image onto a geodesic grid and training on the textured mesh. This method exceeds the state of the art for spherical depth estimation by nearly 17%. Our findings suggest that mapped convolutions can be instrumental in expanding the application scope of convolutional neural networks.
Leader Election Requires Logarithmic Time in Population Protocols
Venue: arXiv cs.DC 2019
Year: 2019

This paper shows that every leader election protocol requires logarithmic stabilization time both in expectation and with high probability in the population protocol model. This lower bound holds even if each agent has knowledge of the exact size of a population and is allowed to use an arbitrarily large number of agent states. This lower bound concludes that the protocol given in [Sudo et al., SSS 2019] is time-optimal in expectation.
Chaining Meets Chain Rule: Multilevel Entropic Regularization and Training of Neural Nets
Venue: arXiv cs.LG 2019
Year: 2019

We derive generalization and excess risk bounds for neural nets using a family of complexity measures based on a multilevel relative entropy. The bounds are obtained by introducing the notion of generated hierarchical coverings of neural nets and by using the technique of chaining mutual information introduced in Asadi et al. NeurIPS'18. The resulting bounds are algorithm-dependent and exploit the multilevel structure of neural nets. This, in turn, leads to an empirical risk minimization problem with a multilevel entropic regularization. The minimization problem is resolved by introducing a multi-scale generalization of the celebrated Gibbs posterior distribution, proving that the derived distribution achieves the unique minimum. This leads to a new training procedure for neural nets with performance guarantees, which exploits the chain rule of relative entropy rather than the chain rule of derivatives (as in backpropagation). To obtain an efficient implementation of the latter, we further develop a multilevel Metropolis algorithm simulating the multi-scale Gibbs distribution, with an experiment for a two-layer neural net on the MNIST data set.
Modeling Embedding Dimension Correlations via Convolutional Neural Collaborative Filtering
Venue: arXiv cs.IR 2019
Year: 2019

As the core of recommender system, collaborative filtering (CF) models the affinity between a user and an item from historical user-item interactions, such as clicks, purchases, and so on. Benefited from the strong representation power, neural networks have recently revolutionized the recommendation research, setting up a new standard for CF. However, existing neural recommender models do not explicitly consider the correlations among embedding dimensions, making them less effective in modeling the interaction function between users and items. In this work, we emphasize on modeling the correlations among embedding dimensions in neural networks to pursue higher effectiveness for CF. We propose a novel and general neural collaborative filtering framework, namely ConvNCF, which is featured with two designs: 1) applying outer product on user embedding and item embedding to explicitly model the pairwise correlations between embedding dimensions, and 2) employing convolutional neural network above the outer product to learn the high-order correlations among embedding dimensions. To justify our proposal, we present three instantiations of ConvNCF by using different inputs to represent a user and conduct experiments on two real-world datasets. Extensive results verify the utility of modeling embedding dimension correlations with ConvNCF, which outperforms several competitive CF methods.
A formalisation of the SPARC TSO memory model for multi-core machine code
Venue: arXiv cs.LO 2019
Year: 2019

SPARC processors have many applications in mission-critical industries such as aviation and space engineering. Hence, it is important to provide formal frameworks that facilitate the verification of hardware and software that run on or interface with these processors. This paper presents the first mechanised SPARC Total Store Ordering (TSO) memory model which operates on top of an abstract model of the SPARC Instruction Set Architecture (ISA) for multi-core processors. Both models are specified in the theorem prover Isabelle/HOL. We formalise two TSO memory models: one is an adaptation of the axiomatic SPARC TSO model, the other is a novel operational TSO model which is suitable for verifying execution results. We prove that the operational model is sound and complete with respect to the axiomatic model. Finally, we give verification examples with two case studies drawn from the SPARCv9 manual.
Beyond DAGs: Modeling Causal Feedback with Fuzzy Cognitive Maps
Venue: arXiv cs.AI 2019
Year: 2019

Fuzzy cognitive maps (FCMs) model feedback causal relations in interwoven webs of causality and policy variables. FCMs are fuzzy signed directed graphs that allow degrees of causal influence and event occurrence. Such causal models can simulate a wide range of policy scenarios and decision processes. Their directed loops or cycles directly model causal feedback. Their nonlinear dynamics permit forward-chaining inference from input causes and policy options to output effects. Users can add detailed dynamics and feedback links directly to the causal model or infer them with statistical learning laws. Users can fuse or combine FCMs from multiple experts by weighting and adding the underlying fuzzy edge matrices and do so recursively if needed. The combined FCM tends to better represent domain knowledge as the expert sample size increases if the expert sample approximates a random sample. Many causal models use more restrictive directed acyclic graphs (DAGs) and Bayesian probabilities. DAGs do not model causal feedback because they do not contain closed loops. Combining DAGs also tends to produce cycles and thus tends not to produce a new DAG. Combining DAGs tends to produce a FCM. FCM causal influence is also transitive whereas probabilistic causal influence is not transitive in general. Overall: FCMs trade the numerical precision of probabilistic DAGs for pattern prediction, faster and scalable computation, ease of combination, and richer feedback representation. We show how FCMs can apply to problems of public support for insurgency and terrorism and to US-China conflict relations in Graham Allison's Thucydides-trap framework. The appendix gives the textual justification of the Thucydides-trap FCM. It also extends our earlier theorem [Osoba-Kosko2017] to a more general result that shows the transitive and total causal influence that upstream concept nodes exert on downstream nodes.
Secure Client and Server Geolocation Over the Internet
Venue: arXiv cs.CR 2019
Year: 2019

In this article, we provide a summary of recent efforts towards achieving Internet geolocation securely, \ie without allowing the entity being geolocated to cheat about its own geographic location. Cheating motivations arise from many factors, including impersonation (in the case locations are used to reinforce authentication), and gaining location-dependent benefits. In particular, we provide a technical overview of Client Presence Verification (CPV) and Server Location Verification (SLV)---two recently proposed techniques designed to verify the geographic locations of clients and servers in realtime over the Internet. Each technique addresses a wide range of adversarial tactics to manipulate geolocation, including the use of IP-hiding technologies like VPNs and anonymizers, as we now explain.
Personalized Student Stress Prediction with Deep Multitask Network
Venue: arXiv cs.LG 2019
Year: 2019

With the growing popularity of wearable devices, the ability to utilize physiological data collected from these devices to predict the wearer's mental state such as mood and stress suggests great clinical applications, yet such a task is extremely challenging. In this paper, we present a general platform for personalized predictive modeling of behavioural states like students' level of stress. Through the use of Auto-encoders and Multitask learning we extend the prediction of stress to both sequences of passive sensor data and high-level covariates. Our model outperforms the state-of-the-art in the prediction of stress level from mobile sensor data, obtaining a 45.6 % improvement in F1 score on the StudentLife dataset.
Vector Programming Using Generative Recursion
Venue: arXiv cs.DS 2019
Year: 2019

Vector programming is an important topic in many Introduction to Computer Science courses. Despite the importance of vectors, learning vector programming is a source of frustration for many students. Much of the frustration is rooted in discovering the source of bugs that are manifested as out-of-bounds indexing. The problem is that such bugs are, sometimes, rooted in incorrectly computing an index. Other times, however, these errors are rooted in mistaken reasoning about how to correctly process a vector. Unfortunately, either way, all too often beginners are left adrift to resolve indexing errors on their own. This article extends the work done on vector programming using vector intervals and structural recursion to using generative recursion. As for problems solved using structural recursion, vector intervals provide beginners with a useful framework for designing code that properly indexes vectors. This article presents the methodology and concrete examples that others may use to build their own CS1 modules involving vector programming using any programming language.
Traffic Management Strategies for Multi-Robotic Rigid Payload Transport Systems
Venue: arXiv cs.MA 2019
Year: 2019

In this work, we address traffic management of multiple payload transport systems comprising of non-holonomic robots. We consider loosely coupled rigid robot formations carrying a payload from one place to another. Each payload transport system (PTS) moves in various kinds of environments with obstacles. We ensure each PTS completes its given task by avoiding collisions with other payload systems and obstacles as well. Each PTS has one leader and multiple followers and the followers maintain a desired distance and angle with respect to the leader using a decentralized leader-follower control architecture while moving in the traffic. We showcase, through simulations the time taken by each PTS to traverse its respective trajectory with and without other PTS and obstacles. We show that our strategies help manage the traffic for a large number of PTS moving from one place to another.
Flexible Anonymous Network
Venue: arXiv cs.CR 2019
Year: 2019

Internet technologies have been designed from guidelines like the robustness principle also known as Postel's law. Jon Postel's law is described as: "Be conservative in what you do, be liberal in what you accept from others." Fundamentally, it advises protocol designs to be tolerant with what they accept from the other peers. We propose to take a step back and wonder how the robustness principle could be revisited to support security requirements as well as unifying flexibility from specifications, protocol design and software implementations. Our goal would be to define a software architecture that offers the benefits of the robustness principle (i.e., efficient network services despite the presence of various software versions), while also guaranteeing that this robustness cannot be exploited by making sure that it is only used to support authentic evolution of the protocol specification.