OpenRaiser/Intern-Atlas huggingface dataset:
Protecting Sensory Data against Sensitive Inferences
Venue: arXiv cs.LG 2018
Year: 2018

There is growing concern about how personal data are used when users grant applications direct access to the sensors of their mobile devices. In fact, high resolution temporal data generated by motion sensors reflect directly the activities of a user and indirectly physical and demographic attributes. In this paper, we propose a feature learning architecture for mobile devices that provides flexible and negotiable privacy-preserving sensor data transmission by appropriately transforming raw sensor data. The objective is to move from the current binary setting of granting or not permission to an application, toward a model that allows users to grant each application permission over a limited range of inferences according to the provided services. The internal structure of each component of the proposed architecture can be flexibly changed and the trade-off between privacy and utility can be negotiated between the constraints of the user and the underlying application. We validated the proposed architecture in an activity recognition application using two real-world datasets, with the objective of recognizing an activity without disclosing gender as an example of private information. Results show that the proposed framework maintains the usefulness of the transformed data for activity recognition, with an average loss of only around three percentage points, while reducing the possibility of gender classification to around 50\%, the target random guess, from more than 90\% when using raw sensor data. We also present and distribute MotionSense, a new dataset for activity and attribute recognition collected from motion sensors.
Efficient Enumeration of Dominating Sets for Sparse Graphs
Venue: arXiv cs.DS 2018
Year: 2018

A dominating set $D$ of a graph $G$ is a set of vertices such that any vertex in $G$ is in $D$ or its neighbor is in $D$. Enumeration of minimal dominating sets in a graph is one of central problems in enumeration study since enumeration of minimal dominating sets corresponds to enumeration of minimal hypergraph transversal. However, enumeration of dominating sets including non-minimal ones has not been received much attention. In this paper, we address enumeration problems for dominating sets from sparse graphs which are degenerate graphs and graphs with large girth, and we propose two algorithms for solving the problems. The first algorithm enumerates all the dominating sets for a $k$-degenerate graph in $O(k)$ time per solution using $O(n + m)$ space, where $n$ and $m$ are respectively the number of vertices and edges in an input graph. That is, the algorithm is optimal for graphs with constant degeneracy such as trees, planar graphs, $H$-minor free graphs with some fixed $H$. The second algorithm enumerates all the dominating sets in constant time per solution for input graphs with girth at least nine.
Graph-Based Blind Image Deblurring From a Single Photograph
Venue: arXiv cs.CV 2018
Year: 2018

Blind image deblurring, i.e., deblurring without knowledge of the blur kernel, is a highly ill-posed problem. The problem can be solved in two parts: i) estimate a blur kernel from the blurry image, and ii) given estimated blur kernel, de-convolve blurry input to restore the target image. In this paper, we propose a graph-based blind image deblurring algorithm by interpreting an image patch as a signal on a weighted graph. Specifically, we first argue that a skeleton image---a proxy that retains the strong gradients of the target but smooths out the details---can be used to accurately estimate the blur kernel and has a unique bi-modal edge weight distribution. Then, we design a reweighted graph total variation (RGTV) prior that can efficiently promote a bi-modal edge weight distribution given a blurry patch. Further, to analyze RGTV in the graph frequency domain, we introduce a new weight function to represent RGTV as a graph $l_1$-Laplacian regularizer. This leads to a graph spectral filtering interpretation of the prior with desirable properties, including robustness to noise and blur, strong piecewise smooth (PWS) filtering and sharpness promotion. Minimizing a blind image deblurring objective with RGTV results in a non-convex non-differentiable optimization problem. We leverage the new graph spectral interpretation for RGTV to design an efficient algorithm that solves for the skeleton image and the blur kernel alternately. Specifically for Gaussian blur, we propose a further speedup strategy for blind Gaussian deblurring using accelerated graph spectral filtering. Finally, with the computed blur kernel, recent non-blind image deblurring algorithms can be applied to restore the target image. Experimental results demonstrate that our algorithm successfully restores latent sharp images and outperforms state-of-the-art methods quantitatively and qualitatively.
Faster integer multiplication using short lattice vectors
Venue: arXiv cs.SC 2018
Year: 2018

We prove that $n$-bit integers may be multiplied in $O(n \log n \, 4^{\log^* n})$ bit operations. This complexity bound had been achieved previously by several authors, assuming various unproved number-theoretic hypotheses. Our proof is unconditional, and depends in an essential way on Minkowski's theorem concerning lattice vectors in symmetric convex sets.
On detection of Gaussian stochastic sequences
Venue: arXiv cs.IT 2018
Year: 2018

The problem of minimax detection of Gaussian random signal vector in White Gaussian additive noise is considered. It is supposed that an unknown vector $\boldsymbolσ$ of the signal vector intensities belong to the given set ${\mathcal E}$. It is investigated when it is possible to replace the set ${\mathcal E}$ by a smaller set ${\mathcal E}_{0}$ without loss of quality (and, in particular, to replace it by a single point $\boldsymbolσ_{0}$).
Learning to Route with Sparse Trajectory Sets---Extended Version
Venue: arXiv cs.LG 2018
Year: 2018

Motivated by the increasing availability of vehicle trajectory data, we propose learn-to-route, a comprehensive trajectory-based routing solution. Specifically, we first construct a graph-like structure from trajectories as the routing infrastructure. Second, we enable trajectory-based routing given an arbitrary (source, destination) pair. In the first step, given a road network and a collection of trajectories, we propose a trajectory-based clustering method that identifies regions in a road network. If a pair of regions are connected by trajectories, we maintain the paths used by these trajectories and learn a routing preference for travel between the regions. As trajectories are skewed and sparse, many region pairs are not connected by trajectories. We thus transfer routing preferences from region pairs with sufficient trajectories to such region pairs and then use the transferred preferences to identify paths between the regions. In the second step, we exploit the above graph-like structure to achieve a comprehensive trajectory-based routing solution. Empirical studies with two substantial trajectory data sets offer insight into the proposed solution, indicating that it is practical. A comparison with a leading routing service offers evidence that the paper's proposal is able to enhance routing quality. This is an extended version of "Learning to Route with Sparse Trajectory Sets" [1], to appear in IEEE ICDE 2018.
Tapir: Automation Support of Exploratory Testing Using Model Reconstruction of the System Under Test
Venue: arXiv cs.SE 2018
Year: 2018

For a considerable number of software projects, the creation of effective test cases is hindered by design documentation that is either lacking, incomplete or obsolete. The exploratory testing approach can serve as a sound method in such situations. However, the efficiency of this testing approach strongly depends on the method, the documentation of explored parts of a system, the organization and distribution of work among individual testers on a team, and the minimization of potential (very probable) duplicities in performed tests. In this paper, we present a framework for replacing and automating a portion of these tasks. A screen-flow-based model of the tested system is incrementally reconstructed during the exploratory testing process by tracking testers' activities. With additional metadata, the model serves for an automated navigation process for a tester. Compared with the exploratory testing approach, which is manually performed in two case studies, the proposed framework allows the testers to explore a greater extent of the tested system and enables greater detection of the defects present in the system. The results show that the time efficiency of the testing process improved with framework support. This efficiency can be increased by team-based navigational strategies that are implemented within the proposed framework, which is documented by another case study presented in this paper.
Sounderfeit: Cloning a Physical Model with Conditional Adversarial Autoencoders
Venue: arXiv cs.SD 2018
Year: 2018

An adversarial autoencoder conditioned on known parameters of a physical modeling bowed string synthesizer is evaluated for use in parameter estimation and resynthesis tasks. Latent dimensions are provided to capture variance not explained by the conditional parameters. Results are compared with and without the adversarial training, and a system capable of "copying" a given parameter-signal bidirectional relationship is examined. A real-time synthesis system built on a generative, conditioned and regularized neural network is presented, allowing to construct engaging sound synthesizers based purely on recorded data.
Iterate averaging as regularization for stochastic gradient descent
Venue: arXiv cs.LG 2018
Year: 2018

We propose and analyze a variant of the classic Polyak-Ruppert averaging scheme, broadly used in stochastic gradient methods. Rather than a uniform average of the iterates, we consider a weighted average, with weights decaying in a geometric fashion. In the context of linear least squares regression, we show that this averaging scheme has a the same regularizing effect, and indeed is asymptotically equivalent, to ridge regression. In particular, we derive finite-sample bounds for the proposed approach that match the best known results for regularized stochastic gradient methods.
Are Two (Samples) Really Better Than One? On the Non-Asymptotic Performance of Empirical Revenue Maximization
Venue: arXiv cs.GT 2018
Year: 2018

The literature on "mechanism design from samples," which has flourished in recent years at the interface of economics and computer science, offers a bridge between the classic computer-science approach of worst-case analysis (corresponding to "no samples") and the classic economic approach of average-case analysis for a given Bayesian prior (conceptually corresponding to the number of samples tending to infinity). Nonetheless, the two directions studied so far are two extreme and almost diametrically opposed directions: that of asymptotic results where the number of samples grows large, and that where only a single sample is available. In this paper, we take a first step toward understanding the middle ground that bridges these two approaches: that of a fixed number of samples greater than one. In a variety of contexts, we ask what is possibly the most fundamental question in this direction: "are two samples really better than one sample?". We present a few surprising negative results, and complement them with our main result: showing that the worst-case, over all regular distributions, expected-revenue guarantee of the Empirical Revenue Maximization algorithm given two samples is greater than that of this algorithm given one sample. The proof is technically challenging, and provides the first result that shows that some deterministic mechanism constructed using two samples can guarantee more than one half of the optimal revenue.
Deep Online Video Stabilization
Venue: arXiv cs.GR 2018
Year: 2018

Video stabilization technique is essential for most hand-held captured videos due to high-frequency shakes. Several 2D-, 2.5D- and 3D-based stabilization techniques are well studied, but to our knowledge, no solutions based on deep neural networks had been proposed. The reason for this is mostly the shortage of training data, as well as the challenge of modeling the problem using neural networks. In this paper, we solve the video stabilization problem using a convolutional neural network (ConvNet). Instead of dealing with offline holistic camera path smoothing based on feature matching, we focus on low-latency real-time camera path smoothing without explicitly representing the camera path. Our network, called StabNet, learns a transformation for each input unsteady frame progressively along the time-line, while creating a more stable latent camera path. To train the network, we create a dataset of synchronized steady/unsteady video pairs via a well designed hand-held hardware. Experimental results shows that the proposed online method (without using future frames) performs comparatively to traditional offline video stabilization methods, while running about 30 times faster. Further, the proposed StabNet is able to handle night-time and blurry videos, where existing methods fail in robust feature matching.
A novel incentive-based demand response model for Cournot competition in electricity markets
Venue: arXiv cs.GT 2018
Year: 2018

This paper presents an analysis of competition between generators when incentive-based demand response is employed in an electricity market. Thermal and hydropower generation are considered in the model. A smooth inverse demand function is designed using a sigmoid and two linear functions for modeling the consumer preferences under incentive-based demand response program. Generators compete to sell energy bilaterally to consumers and system operator provides transmission and arbitrage services. The profit of each agent is posed as an optimization problem, then the competition result is found by solving simultaneously Karush-Kuhn-Tucker conditions for all generators. A Nash-Cournot equilibrium is found when the system operates normally and at peak demand times when DR is required. Under this model, results show that DR diminishes the energy consumption at peak periods, shifts the power requirement to off-peak times and improves the net consumer surplus due to incentives received for participating in DR program. However, the generators decrease their profit due to the reduction of traded energy and market prices.
Analyzing Real-Time Multimedia Content From Network Cameras Using CPUs and GPUs in the Cloud
Venue: arXiv cs.DC 2018
Year: 2018

Millions of network cameras are streaming real-time multimedia content (images or videos) for various environments (e.g., highways and malls) and can be used for a variety of applications. Analyzing the content from many network cameras requires significant amounts of computing resources. Cloud vendors offer resources in the form of cloud instances with different capabilities and hourly costs. Some instances include GPUs that can accelerate analysis programs. Doing so incurs additional monetary cost because instances with GPUs are more expensive. It is a challenging problem to reduce the overall monetary cost of using the cloud to analyze the real-time multimedia content from network cameras while meeting the desired analysis frame rates. This paper describes a cloud resource manager that solves this problem by estimating the resource requirements of executing analysis programs using CPU or GPU, formulating the resource allocation problem as a multiple-choice vector bin packing problem, and solving it using an existing algorithm. The experiments show that the manager can reduce up to 61\% of the cost compared with other allocation strategies.
The iisignature library: efficient calculation of iterated-integral signatures and log signatures
Venue: arXiv cs.DS 2018
Year: 2018

Iterated-integral signatures and log signatures are vectors calculated from a path that characterise its shape. They come from the theory of differential equations driven by rough paths, and also have applications in statistics and machine learning. We present algorithms for efficiently calculating these signatures, and benchmark their performance. We release the methods as a Python package.
Unicorn: Continual Learning with a Universal, Off-policy Agent
Venue: arXiv cs.LG 2018
Year: 2018

Some real-world domains are best characterized as a single task, but for others this perspective is limiting. Instead, some tasks continually grow in complexity, in tandem with the agent's competence. In continual learning, also referred to as lifelong learning, there are no explicit task boundaries or curricula. As learning agents have become more powerful, continual learning remains one of the frontiers that has resisted quick progress. To test continual learning capabilities we consider a challenging 3D domain with an implicit sequence of tasks and sparse rewards. We propose a novel agent architecture called Unicorn, which demonstrates strong continual learning and outperforms several baseline agents on the proposed domain. The agent achieves this by jointly representing and learning multiple policies efficiently, using a parallel off-policy learning setup.
Feedback Control of an Exoskeleton for Paraplegics: Toward Robustly Stable Hands-free Dynamic Walking
Venue: arXiv cs.RO 2018
Year: 2018

This manuscript presents control of a high-DOF fully actuated lower-limb exoskeleton for paraplegic individuals. The key novelty is the ability for the user to walk without the use of crutches or other external means of stabilization. We harness the power of modern optimization techniques and supervised machine learning to develop a smooth feedback control policy that provides robust velocity regulation and perturbation rejection. Preliminary evaluation of the stability and robustness of the proposed approach is demonstrated through the Gazebo simulation environment. In addition, preliminary experimental results with (complete) paraplegic individuals are included for the previous version of the controller.
From Hazard Analysis to Hazard Mitigation Planning: The Automated Driving Case
Venue: arXiv cs.SE 2018
Year: 2018

Vehicle safety depends on (a) the range of identified hazards and (b) the operational situations for which mitigations of these hazards are acceptably decreasing risk. Moreover, with an increasing degree of autonomy, risk ownership is likely to increase for vendors towards regulatory certification. Hence, highly automated vehicles have to be equipped with verified controllers capable of reliably identifying and mitigating hazards in all possible operational situations. To this end, available methods for the design and verification of automated vehicle controllers have to be supported by models for hazard analysis and mitigation. In this paper, we describe (1) a framework for the analysis and design of planners (i.e., high-level controllers) capable of run-time hazard identification and mitigation, (2) an incremental algorithm for constructing planning models from hazard analysis, and (3) an exemplary application to the design of a fail-operational controller based on a given control system architecture. Our approach equips the safety engineer with concepts and steps to (2a) elaborate scenarios of endangerment and (2b) design operational strategies for mitigating such scenarios.
Real-Time End-to-End Action Detection with Two-Stream Networks
Venue: arXiv cs.CV 2018
Year: 2018

Two-stream networks have been very successful for solving the problem of action detection. However, prior work using two-stream networks train both streams separately, which prevents the network from exploiting regularities between the two streams. Moreover, unlike the visual stream, the dominant forms of optical flow computation typically do not maximally exploit GPU parallelism. We present a real-time end-to-end trainable two-stream network for action detection. First, we integrate the optical flow computation in our framework by using Flownet2. Second, we apply early fusion for the two streams and train the whole pipeline jointly end-to-end. Finally, for better network initialization, we transfer from the task of action recognition to action detection by pre-training our framework using the recently released large-scale Kinetics dataset. Our experimental results show that training the pipeline jointly end-to-end with fine-tuning the optical flow for the objective of action detection improves detection performance significantly. Additionally, we observe an improvement when initializing with parameters pre-trained using Kinetics. Last, we show that by integrating the optical flow computation, our framework is more efficient, running at real-time speeds (up to 31 fps).
Building a coverage hole-free communication tree
Venue: arXiv cs.NI 2018
Year: 2018

Wireless networks are present everywhere but their management can be tricky since their coverage may contain holes even if the network is fully connected. In this paper we propose an algorithm that can build a communication tree between nodes of a wireless network with guarantee that there is no coverage hole in the tree. We use simplicial homology to compute mathematically the coverage, and Prim's algorithm principle to build the communication tree. Some simulation results are given to study the performance of the algorithm and compare different metrics. In the end, we show that our algorithm can be used to create coverage hole-free communication groups with a limited number of hops.
A Matrix Approach for Weighted Argumentation Frameworks: a Preliminary Report
Venue: arXiv cs.AI 2018
Year: 2018

The assignment of weights to attacks in a classical Argumentation Framework allows to compute semantics by taking into account the different importance of each argument. We represent a Weighted Argumentation Framework by a non-binary matrix, and we characterize the basic extensions (such as w-admissible, w- stable, w-complete) by analysing sub-blocks of this matrix. Also, we show how to reduce the matrix into another one of smaller size, that is equivalent to the original one for the determination of extensions. Furthermore, we provide two algorithms that allow to build incrementally w-grounded and w-preferred extensions starting from a w-admissible extension.
IPA: Invariant-preserving Applications for Weakly-consistent Replicated Databases
Venue: arXiv cs.DC 2018
Year: 2018

Storage systems based on Weak Consistency provide better availability and lower latency than systems that use Strong Consistency, especially in geo-replicated settings. However, under Weak Consistency, it is harder to ensure the correctness of applications, as the execution of uncoordinated operations may lead to invalid states. In this paper we show how to modify an application to make it run correctly under Weak Consistency. We developed an analysis that detects which operations need to be corrected, and proposes possible modifications to operations to prevent inconsistencies. This analysis allows the programmer to choose the preferred semantics for each problematic execution, while preserving the original semantics of operations when no conflicts occur. The modified application runs with small overhead when compared with its Weak Consistency counterpart, which cannot preserve application correctness.