OpenRaiser/Intern-Atlas huggingface dataset:
Detecting and Simulating Artifacts in GAN Fake Images
Venue: arXiv cs.CV 2019
Year: 2019

To detect GAN generated images, conventional supervised machine learning algorithms require collection of a number of real and fake images from the targeted GAN model. However, the specific model used by the attacker is often unavailable. To address this, we propose a GAN simulator, AutoGAN, which can simulate the artifacts produced by the common pipeline shared by several popular GAN models. Additionally, we identify a unique artifact caused by the up-sampling component included in the common GAN pipeline. We show theoretically such artifacts are manifested as replications of spectra in the frequency domain and thus propose a classifier model based on the spectrum input, rather than the pixel input. By using the simulated images to train a spectrum based classifier, even without seeing the fake images produced by the targeted GAN model during training, our approach achieves state-of-the-art performances on detecting fake images generated by popular GAN models such as CycleGAN.
Summary: Multi-modal Biometric-based Implicit Authentication of Wearable Device Users
Venue: arXiv cs.CR 2019
Year: 2019

The Internet of Things (IoT) is increasingly empowering people with an interconnected world of physical objects ranging from smart buildings to portable smart devices such as wearables. With recent advances in mobile sensing, wearables have become a rich collection of portable sensors and are able to provide various types of services including tracking of health and fitness, making financial transactions, and unlocking smart locks and vehicles. Most of these services are delivered based on users' confidential and personal data, which are stored on these wearables. Existing explicit authentication approaches (i.e., PINs or pattern locks) for wearables suffer from several limitations, including small or no displays, risk of shoulder surfing, and users' recall burden. Oftentimes, users completely disable security features out of convenience. Therefore, there is a need for a burden-free (implicit) authentication mechanism for wearable device users based on easily obtainable biometric data. In this paper, we present an implicit wearable device user authentication mechanism using combinations of three types of coarse-grain minute-level biometrics: behavioral (step counts), physiological (heart rate), and hybrid (calorie burn and metabolic equivalent of task). From our analysis of over 400 Fitbit users from a 17-month long health study, we are able to authenticate subjects with average accuracy values of around .93 (sedentary) and .90 (non-sedentary) with equal error rates of .05 using binary SVM classifiers. Our findings also show that the hybrid biometrics perform better than other biometrics and behavioral biometrics do not have a significant impact, even during non-sedentary periods.
Adversarial Video Generation on Complex Datasets
Venue: arXiv cs.CV 2019
Year: 2019

Generative models of natural images have progressed towards high fidelity samples by the strong leveraging of scale. We attempt to carry this success to the field of video modeling by showing that large Generative Adversarial Networks trained on the complex Kinetics-600 dataset are able to produce video samples of substantially higher complexity and fidelity than previous work. Our proposed model, Dual Video Discriminator GAN (DVD-GAN), scales to longer and higher resolution videos by leveraging a computationally efficient decomposition of its discriminator. We evaluate on the related tasks of video synthesis and video prediction, and achieve new state-of-the-art Fréchet Inception Distance for prediction for Kinetics-600, as well as state-of-the-art Inception Score for synthesis on the UCF-101 dataset, alongside establishing a strong baseline for synthesis on Kinetics-600.
On circles enclosing many points
Venue: arXiv cs.CG 2019
Year: 2019

We prove that every set of $n$ red and $n$ blue points in the plane contains a red and a blue point such that every circle through them encloses at least $n(1-\frac{1}{\sqrt{2}}) -o(n)$ points of the set. This is a two-colored version of a problem posed by Neumann-Lara and Urrutia. We also show that every set $S$ of $n$ points contains two points such that every circle passing through them encloses at most $\lfloor{\frac{2n-3}{3}}\rfloor$ points of $S$. The proofs make use of properties of higher order Voronoi diagrams, in the spirit of the work of Edelsbrunner, Hasan, Seidel and Shen on this topic. Closely related, we also study the number of collinear edges in higher order Voronoi diagrams and present several constructions.
Hotelling Games with Multiple Line Faults
Venue: arXiv cs.GT 2019
Year: 2019

The Hotelling game consists of n servers each choosing a point on the line segment, so as to maximize the amount of clients it attracts. Clients are uniformly distributed along the line, and each client buys from the closest server. In this paper, we study a fault-prone version of the Hotelling game, where the line fails at multiple random locations. Each failure disconnects the line, blocking the passage of clients. We show that the game admits a Nash equilibrium if and only if the rate of faults exceeds a certain threshold, and calculate that threshold approximately. Moreover, when a Nash equilibrium exists we show it is unique and construct it explicitly. Hence, somewhat surprisingly, the potential occurrence of failures has a stabilizing effect on the game (provided there are enough of them). Additionally, we study the social cost of the game (measured in terms of the total transportation cost of the clients), which also seems to benefit in a certain sense from the potential presence of failures.
Agglomerative Attention
Venue: arXiv cs.LG 2019
Year: 2019

Neural networks using transformer-based architectures have recently demonstrated great power and flexibility in modeling sequences of many types. One of the core components of transformer networks is the attention layer, which allows contextual information to be exchanged among sequence elements. While many of the prevalent network structures thus far have utilized full attention -- which operates on all pairs of sequence elements -- the quadratic scaling of this attention mechanism significantly constrains the size of models that can be trained. In this work, we present an attention model that has only linear requirements in memory and computation time. We show that, despite the simpler attention model, networks using this attention mechanism can attain comparable performance to full attention networks on language modeling tasks.
Partitioning Graphs for the Cloud using Reinforcement Learning
Venue: arXiv cs.DC 2019
Year: 2019

In this paper, we propose Revolver, a parallel graph partitioning algorithm capable of partitioning large-scale graphs on a single shared-memory machine. Revolver employs an asynchronous processing framework, which leverages reinforcement learning and label propagation to adaptively partition a graph. In addition, it adopts a vertex-centric view of the graph where each vertex is assigned an autonomous agent responsible for selecting a suitable partition for it, distributing thereby the computation across all vertices. The intuition behind using a vertex-centric view is that it naturally fits the graph partitioning problem, which entails that a graph can be partitioned using local information provided by each vertex's neighborhood. We fully implemented and comprehensively tested Revolver using nine real-world graphs. Our results show that Revolver is scalable and can outperform three popular and state-of-the-art graph partitioners via producing comparable localized partitions, yet without sacrificing the load balance across partitions.
Instant Motion Tracking and Its Applications to Augmented Reality
Venue: arXiv cs.CV 2019
Year: 2019

Augmented Reality (AR) brings immersive experiences to users. With recent advances in computer vision and mobile computing, AR has scaled across platforms, and has increased adoption in major products. One of the key challenges in enabling AR features is proper anchoring of the virtual content to the real world, a process referred to as tracking. In this paper, we present a system for motion tracking, which is capable of robustly tracking planar targets and performing relative-scale 6DoF tracking without calibration. Our system runs in real-time on mobile phones and has been deployed in multiple major products on hundreds of millions of devices.
Quality-aware skill translation models for expert finding on StackOverflow
Venue: arXiv cs.IR 2019
Year: 2019

StackOverflow has become an emerging resource for talent recognition in recent years. While users exploit technical language on StackOverflow, recruiters try to find the relevant candidates for jobs using their own terminology. This procedure implies a gap which exists between recruiters and candidates terms. Due to this gap, the state-of-the-art expert finding models cannot effectively address the expert finding problem on StackOverflow. We propose two translation models to bridge this gap. The first approach is a statistical method and the second is based on word embedding approach. Utilizing several translations for a given query during the scoring step, the result of each intermediate query is blended together to obtain the final ranking. Here, we propose a new approach which takes the quality of documents into account in scoring step. We have made several observations to visualize the effectiveness of the translation approaches and also the quality-aware scoring approach. Our experiments indicate the following: First, while statistical and word embedding translation approaches provide different translations for each query, both can considerably improve the recall. Besides, the quality-aware scoring approach can improve the precision remarkably. Finally, our best proposed method can improve the MAP measure up to 46% on average, in comparison with the state-of-the-art expert finding approach.
Modeling User Selection in Quality Diversity
Venue: arXiv cs.NE 2019
Year: 2019

The initial phase in real world engineering optimization and design is a process of discovery in which not all requirements can be made in advance, or are hard to formalize. Quality diversity algorithms, which produce a variety of high performing solutions, provide a unique chance to support engineers and designers in the search for what is possible and high performing. In this work we begin to answer the question how a user can interact with quality diversity and turn it into an interactive innovation aid. By modeling a user's selection it can be determined whether the optimization is drifting away from the user's preferences. The optimization is then constrained by adding a penalty to the objective function. We present an interactive quality diversity algorithm that can take into account the user's selection. The approach is evaluated in a new multimodal optimization benchmark that allows various optimization tasks to be performed. The user selection drift of the approach is compared to a state of the art alternative on both a planning and a neuroevolution control task, thereby showing its limits and possibilities.
On Convergence and Optimality of Best-Response Learning with Policy Types in Multiagent Systems
Venue: arXiv cs.AI 2019
Year: 2019

While many multiagent algorithms are designed for homogeneous systems (i.e. all agents are identical), there are important applications which require an agent to coordinate its actions without knowing a priori how the other agents behave. One method to make this problem feasible is to assume that the other agents draw their latent policy (or type) from a specific set, and that a domain expert could provide a specification of this set, albeit only a partially correct one. Algorithms have been proposed by several researchers to compute posterior beliefs over such policy libraries, which can then be used to determine optimal actions. In this paper, we provide theoretical guidance on two central design parameters of this method: Firstly, it is important that the user choose a posterior which can learn the true distribution of latent types, as otherwise suboptimal actions may be chosen. We analyse convergence properties of two existing posterior formulations and propose a new posterior which can learn correlated distributions. Secondly, since the types are provided by an expert, they may be inaccurate in the sense that they do not predict the agents' observed actions. We provide a novel characterisation of optimality which allows experts to use efficient model checking algorithms to verify optimality of types.
Latent Adversarial Defence with Boundary-guided Generation
Venue: arXiv cs.LG 2019
Year: 2019

Deep Neural Networks (DNNs) have recently achieved great success in many tasks, which encourages DNNs to be widely used as a machine learning service in model sharing scenarios. However, attackers can easily generate adversarial examples with a small perturbation to fool the DNN models to predict wrong labels. To improve the robustness of shared DNN models against adversarial attacks, we propose a novel method called Latent Adversarial Defence (LAD). The proposed LAD method improves the robustness of a DNN model through adversarial training on generated adversarial examples. Different from popular attack methods which are carried in the input space and only generate adversarial examples of repeating patterns, LAD generates myriad of adversarial examples through adding perturbations to latent features along the normal of the decision boundary which is constructed by an SVM with an attention mechanism. Once adversarial examples are generated, we adversarially train the model through augmenting the training data with generated adversarial examples. Extensive experiments on the MNIST, SVHN, and CelebA dataset demonstrate the effectiveness of our model in defending against different types of adversarial attacks.
Threshold Logical Clocks for Asynchronous Distributed Coordination and Consensus
Venue: arXiv cs.DC 2019
Year: 2019

Consensus protocols for asynchronous networks are usually complex and inefficient, leading practical systems to rely on synchronous protocols. This paper attempts to simplify asynchronous consensus by building atop a novel threshold logical clock abstraction, which enables upper layers to operate as if on a synchronous network. This approach yields an asynchronous consensus protocol for fail-stop nodes that may be simpler and more robust than Paxos and its leader-based variants, requiring no common coins and achieving consensus in a constant expected number of rounds. The same approach can be strengthened against Byzantine failures by building on well-established techniques such as tamper-evident logging and gossip, accountable state machines, threshold signatures and witness cosigning, and verifiable secret sharing. This combination of existing abstractions and threshold logical clocks yields a modular, cleanly-layered approach to building practical and efficient Byzantine consensus, distributed key generation, time, timestamping, and randomness beacons, and other critical services.
On The Termination of a Flooding Process
Venue: arXiv cs.DS 2019
Year: 2019

Flooding is among the simplest and most fundamental of all distributed network algorithms. A node begins the process by sending a message to all its neighbours and the neighbours, in the next round forward the message to all the neighbours they did not receive the message from and so on. We assume that the nodes do not keep a record of the flooding event. We call this amnesiac flooding (AF). Since the node forgets, if the message is received again in subsequent rounds, it will be forwarded again raising the possibility that the message may be circulated infinitely even on a finite graph. As far as we know, the question of termination for such a flooding process has not been settled - rather, non-termination is implicitly assumed. In this paper, we show that synchronous AF always terminates on any arbitrary finite graph and derive exact termination times which differ sharply in bipartite and non-bipartite graphs. Let $G$ be a finite connected graph. We show that synchronous AF from a single source node terminates on $G$ in $e$ rounds, where $e$ is the eccentricity of the source node, if and only if $G$ is bipartite. For non-bipartite $G$, synchronous AF from a single source terminates in $j$ rounds where $e < j \leq e+d+1$ and $d$ is the diameter of $G$. This limits termination time to at most $d$ and at most $2d + 1$ for bipartite and non-bipartite graphs respectively. If communication/broadcast to all nodes is the motivation, our results show that AF is asymptotically time optimal and obviates the need for construction and maintenance of spanning structures like spanning trees. The clear separation in the termination times of bipartite and non-bipartite graphs also suggests mechanisms for distributed discovery of the topology/distances in arbitrary graphs. For comparison, we show that, in asynchronous networks, an adaptive adversary can force AF to be non-terminating.
An efficient method to construct self-dual cyclic codes of length $p^s$ over $\mathbb{F}_{p^m}+u\mathbb{F}_{p^m}$
Venue: arXiv cs.IT 2019
Year: 2019

Let $p$ be an odd prime number, $\mathbb{F}_{p^m}$ be a finite field of cardinality $p^m$ and $s$ a positive integer. Using some combinatorial identities, we obtain certain properties for Kronecker product of matrices over $\mathbb{F}_p$ with a specific type. On that basis, we give an explicit representation and enumeration for all distinct self-dual cyclic codes of length $p^s$ over the finite chain ring $\mathbb{F}_{p^m}+u\mathbb{F}_{p^m}$ $(u^2=0)$. Moreover, We provide an efficient method to construct every self-dual cyclic code of length $p^s$ over $\mathbb{F}_{p^m}+u\mathbb{F}_{p^m}$ precisely.
Predicting Next-Season Designs on High Fashion Runway
Venue: arXiv cs.CV 2019
Year: 2019

Fashion is a large and fast-changing industry. Foreseeing the upcoming fashion trends is beneficial for fashion designers, consumers, and retailers. However, fashion trends are often perceived as unpredictable due to the enormous amount of factors involved into designers' subjectivity. In this paper, we propose a fashion trend prediction framework and design neural network models to leverage structured fashion runway show data, learn the fashion collection embedding, and further train RNN/LSTM models to capture the designers' style evolution. Our proposed framework consists of (1) a runway embedding learning model that uses fashion runway images to learn every season's collection embedding, and (2) a next-season fashion design prediction model that leverage the concept of designer style and trend to predict next-season design given designers. Through experiments on a collected dataset across 32 years of fashion shows, our framework can achieve the best performance of 78.42% AUC on average and 95% for an individual designer when predicting the next season's design.
Crisis: Probabilistically Self Organizing Total Order in Unstructured P2P Networks
Venue: arXiv cs.DC 2019
Year: 2019

A framework for asynchronous, signature free, fully local and probabilistically converging total order algorithms is developed, that may survive in high entropy, unstructured Peer-to-Peer networks with near optimal communication efficiency. Regarding the natural boundaries of the CAP-theorem, Crisis chooses different compromises for consistency and availability, depending on the severity of the attack. The family is parameterized by a few constants and external functions called voting-weight, incentivation \& punishement, difficulty oracle and quorum-selector. These functions are necessary to fine tune the dynamics and very different long term behavior might appear, depending on any actual choice.
Effcient logging and querying for Blockchain-based cross-site genomic dataset access audit
Venue: arXiv cs.DB 2019
Year: 2019

Background: Genomic data have been collected by different institutions and companies and need to be shared for broader use. In a cross-site genomic data sharing system, a secure and transparent access control audit module plays an essential role in ensuring the accountability. The 2018 iDASH competition first track provides us with an opportunity to design efficient logging and querying system for cross-site genomic dataset access audit. We designed a blockchain-based log system which can provide a light-weight and widely compatible module for existing blockchain platforms. The submitted solution won the third place of the competition. In this paper, we report the technical details in our system. Methods: We present two methods: baseline method and enhanced method. We started with the baseline method and then adjusted our implementation based on the competition evaluation criteria and characteristics of the log system. To overcome obstacles of indexing on the immutable Blockchain system, we designed a hierarchical timestamp structure which supports efficient range queries on the timestamp field. Results: We implemented our methods in Python3, tested the scalability, and compared the performance using the test data supplied by competition organizer. We successfully boosted the log retrieval speed for complex AND queries that contain multiple predicates. For the range query, we boosted the speed for at least one order of magnitude. The storage usage is reduced by 25%. Conclusion: We demonstrate that Blockchain can be used to build a time and space efficient log and query genomic dataset audit trail. Therefore, it provides a promising solution for sharing genomic data with accountability requirement across multiple sites.
On the challenges of data provenance in the Internet of Things
Venue: arXiv cs.CR 2019
Year: 2019

The IoT is described as a smart interactive environment where devices communicate together ubiquitously sometimes in the background, performing functions on behalf of the users and offering many advanced services to them. Examples range from simple smart home applications such as ambient intelligence and remote controlling functionalities to more advanced smart cities setups. A smart IoT city for instance will encompass a network of many interconnected networks where various sensors and actuators distributed across many areas of the city share information, create knowledge and trigger actuation events. In such a dynamic and rich environment, it is vital for security to trace the source of data and verify its origin. This where data provenance in the IoT come to play. This work attempts to explore requirements and applications of data provenance in the IoT and the challenges pertaining to its realisation.
Feature Selection via Mutual Information: New Theoretical Insights
Venue: arXiv cs.LG 2019
Year: 2019

Mutual information has been successfully adopted in filter feature-selection methods to assess both the relevancy of a subset of features in predicting the target variable and the redundancy with respect to other variables. However, existing algorithms are mostly heuristic and do not offer any guarantee on the proposed solution. In this paper, we provide novel theoretical results showing that conditional mutual information naturally arises when bounding the ideal regression/classification errors achieved by different subsets of features. Leveraging on these insights, we propose a novel stopping condition for backward and forward greedy methods which ensures that the ideal prediction error using the selected feature subset remains bounded by a user-specified threshold. We provide numerical simulations to support our theoretical claims and compare to common heuristic methods.