OpenRaiser/Intern-Atlas huggingface dataset:
Exposing DeepFake Videos By Detecting Face Warping Artifacts
Venue: arXiv cs.CV 2019
Year: 2019

In this work, we describe a new deep learning based method that can effectively distinguish AI-generated fake videos (referred to as {\em DeepFake} videos hereafter) from real videos. Our method is based on the observations that current DeepFake algorithm can only generate images of limited resolutions, which need to be further warped to match the original faces in the source video. Such transforms leave distinctive artifacts in the resulting DeepFake videos, and we show that they can be effectively captured by convolutional neural networks (CNNs). Compared to previous methods which use a large amount of real and DeepFake generated images to train CNN classifier, our method does not need DeepFake generated images as negative training examples since we target the artifacts in affine face warping as the distinctive feature to distinguish real and fake images. The advantages of our method are two-fold: (1) Such artifacts can be simulated directly using simple image processing operations on a image to make it as negative example. Since training a DeepFake model to generate negative examples is time-consuming and resource-demanding, our method saves a plenty of time and resources in training data collection; (2) Since such artifacts are general existed in DeepFake videos from different sources, our method is more robust compared to others. Our method is evaluated on two sets of DeepFake video datasets for its effectiveness in practice.
Passive Whole-body Control for Quadruped Robots: Experimental Validation over Challenging Terrain
Venue: arXiv cs.RO 2019
Year: 2019

We present experimental results using a passive whole-body control approach for quadruped robots that achieves dynamic locomotion while compliantly balancing the robot's trunk. We formulate the motion tracking as a Quadratic Program (QP) that takes into account the full robot rigid body dynamics, the actuation limits, the joint limits and the contact interaction. We analyze the controller's robustness against inaccurate friction coefficient estimates and unstable footholds, as well as its capability to redistribute the load as a consequence of enforcing actuation limits. Additionally, we present practical implementation details gained from the experience with the real platform. Extensive experimental trials on the 90 kg Hydraulically actuated Quadruped (HyQ) robot validate the capabilities of this controller under various terrain conditions and gaits. The proposed approach is superior for accurate execution of highly dynamic motions with respect to the current state of the art.
Sentence Encoders on STILTs: Supplementary Training on Intermediate Labeled-data Tasks
Venue: arXiv cs.CL 2019
Year: 2019

Pretraining sentence encoders with language modeling and related unsupervised tasks has recently been shown to be very effective for language understanding tasks. By supplementing language model-style pretraining with further training on data-rich supervised tasks, such as natural language inference, we obtain additional performance improvements on the GLUE benchmark. Applying supplementary training on BERT (Devlin et al., 2018), we attain a GLUE score of 81.8---the state of the art (as of 02/24/2019) and a 1.4 point improvement over BERT. We also observe reduced variance across random restarts in this setting. Our approach yields similar improvements when applied to ELMo (Peters et al., 2018a) and Radford et al. (2018)'s model. In addition, the benefits of supplementary training are particularly pronounced in data-constrained regimes, as we show in experiments with artificially limited training data.
Space-Time Sampling for Network Observability
Venue: arXiv cs.SY 2019
Year: 2019

Designing sparse sampling strategies is one of the important components in having resilient estimation and control in networked systems as they make network design problems more cost-effective due to their reduced sampling requirements and less fragile to where and when samples are collected. It is shown that under what conditions taking coarse samples from a network will contain the same amount of information as a more finer set of samples. Our goal is to estimate initial condition of linear time-invariant networks using a set of noisy measurements. The observability condition is reformulated as the frame condition, where one can easily trace location and time stamps of each sample. We compare estimation quality of various sampling strategies using estimation measures, which depend on spectrum of the corresponding frame operators. Using properties of the minimal polynomial of the state matrix, deterministic and randomized methods are suggested to construct observability frames. Intrinsic tradeoffs assert that collecting samples from fewer subsystems dictates taking more samples (in average) per subsystem. Three scalable algorithms are developed to generate sparse space-time sampling strategies with explicit error bounds.
Bi-Real Net: Binarizing Deep Network Towards Real-Network Performance
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we study 1-bit convolutional neural networks (CNNs), of which both the weights and activations are binary. While efficient, the lacking of representational capability and the training difficulty impede 1-bit CNNs from performing as well as real-valued networks. We propose Bi-Real net with a novel training algorithm to tackle these two challenges. To enhance the representational capability, we propagate the real-valued activations generated by each 1-bit convolution via a parameter-free shortcut. To address the training difficulty, we propose a training algorithm using a tighter approximation to the derivative of the sign function, a magnitude-aware gradient for weight updating, a better initialization method, and a two-step scheme for training a deep network. Experiments on ImageNet show that an 18-layer Bi-Real net with the proposed training algorithm achieves 56.4% top-1 classification accuracy, which is 10% higher than the state-of-the-arts (e.g., XNOR-Net) with greater memory saving and lower computational cost. Bi-Real net is also the first to scale up 1-bit CNNs to an ultra-deep network with 152 layers, and achieves 64.5% top-1 accuracy on ImageNet. A 50-layer Bi-Real net shows comparable performance to a real-valued network on the depth estimation task with only a 0.3% accuracy gap.
Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs
Venue: arXiv cs.CC 2019
Year: 2019

We show that if a system of degree-$k$ polynomial constraints on~$n$ Boolean variables has a Sums-of-Squares (SOS) proof of unsatisfiability with at most~$s$ many monomials, then it also has one whose degree is of the order of the square root of~$n \log s$ plus~$k$. A similar statement holds for the more general Positivstellensatz (PS) proofs. This establishes size-degree trade-offs for SOS and PS that match their analogues for weaker proof systems such as Resolution, Polynomial Calculus, and the proof systems for the LP and SDP hierarchies of Lovász and Schrijver. As a corollary to this, and to the known degree lower bounds, we get optimal integrality gaps for exponential size SOS proofs for sparse random instances of the standard NP-hard constraint optimization problems. We also get exponential size SOS lower bounds for Tseitin and Knapsack formulas. The proof of our main result relies on a zero-gap duality theorem for pre-ordered vector spaces that admit an order unit, whose specialization to PS and SOS may be of independent interest.
Texture Synthesis Guided Deep Hashing for Texture Image Retrieval
Venue: arXiv cs.CV 2019
Year: 2019

With the large-scale explosion of images and videos over the internet, efficient hashing methods have been developed to facilitate memory and time efficient retrieval of similar images. However, none of the existing works uses hashing to address texture image retrieval mostly because of the lack of sufficiently large texture image databases. Our work addresses this problem by developing a novel deep learning architecture that generates binary hash codes for input texture images. For this, we first pre-train a Texture Synthesis Network (TSN) which takes a texture patch as input and outputs an enlarged view of the texture by injecting newer texture content. Thus it signifies that the TSN encodes the learnt texture specific information in its intermediate layers. In the next stage, a second network gathers the multi-scale feature representations from the TSN's intermediate layers using channel-wise attention, combines them in a progressive manner to a dense continuous representation which is finally converted into a binary hash code with the help of individual and pairwise label information. The new enlarged texture patches also help in data augmentation to alleviate the problem of insufficient texture data and are used to train the second stage of the network. Experiments on three public texture image retrieval datasets indicate the superiority of our texture synthesis guided hashing approach over current state-of-the-art methods.
Theoretical and Experimental Analysis on the Generalizability of Distribution Regression Network
Venue: arXiv cs.LG 2019
Year: 2019

There is emerging interest in performing regression between distributions. In contrast to prediction on single instances, these machine learning methods can be useful for population-based studies or on problems that are inherently statistical in nature. The recently proposed distribution regression network (DRN) has shown superior performance for the distribution-to-distribution regression task compared to conventional neural networks. However, in Kou et al. (2018) and some other works on distribution regression, there is a lack of comprehensive comparative study on both theoretical basis and generalization abilities of the methods. We derive some mathematical properties of DRN and qualitatively compare it to conventional neural networks. We also perform comprehensive experiments to study the generalizability of distribution regression models, by studying their robustness to limited training data, data sampling noise and task difficulty. DRN consistently outperforms conventional neural networks, requiring fewer training data and maintaining robust performance with noise. Furthermore, the theoretical properties of DRN can be used to provide some explanation on the ability of DRN to achieve better generalization performance than conventional neural networks.
Confidence Propagation through CNNs for Guided Sparse Depth Regression
Venue: arXiv cs.CV 2019
Year: 2019

Generally, convolutional neural networks (CNNs) process data on a regular grid, e.g. data generated by ordinary cameras. Designing CNNs for sparse and irregularly spaced input data is still an open research problem with numerous applications in autonomous driving, robotics, and surveillance. In this paper, we propose an algebraically-constrained normalized convolution layer for CNNs with highly sparse input that has a smaller number of network parameters compared to related work. We propose novel strategies for determining the confidence from the convolution operation and propagating it to consecutive layers. We also propose an objective function that simultaneously minimizes the data error while maximizing the output confidence. To integrate structural information, we also investigate fusion strategies to combine depth and RGB information in our normalized convolution network framework. In addition, we introduce the use of output confidence as an auxiliary information to improve the results. The capabilities of our normalized convolution network framework are demonstrated for the problem of scene depth completion. Comprehensive experiments are performed on the KITTI-Depth and the NYU-Depth-v2 datasets. The results clearly demonstrate that the proposed approach achieves superior performance while requiring only about 1-5% of the number of parameters compared to the state-of-the-art methods.
Blockchain-based Charging Coordination Mechanism for Smart Grid Energy Storage Units
Venue: arXiv cs.CR 2019
Year: 2019

Energy storage units (ESUs) enable several attractive features of modern smart grids such as enhanced grid resilience, effective demand response, and reduced bills. However, uncoordinated charging of ESUs stresses the power system and can lead to a blackout. On the other hand, existing charging coordination mechanisms suffer from several limitations. First, the need for a central charging coordinator (CC) presents a single point of failure that jeopardizes the effectiveness of the charging coordination. Second, a transparent charging coordination mechanism does not exist where users are not aware whether the CC is honest or not in coordination charging requests among them in a fair way. Third, existing mechanisms overlook the privacy concerns of the involved customers. To address these limitations, in this paper, we leverage the blockchain and smart contracts to build a decentralized charging coordination mechanism without the need for a centralized charging coordinator. First ESUs should use tokens for anonymously authenticate themselves to the blockchain. Then each ESU sends a charging request that contains its State-of-Charge (SoC), Time-to-complete-charge (TCC) and amount of required charging to the smart contract address on the blockchain. The smart contract will then run the charging coordination mechanism in a self-executed manner such that ESUs with the highest priorities are charged in the present time slot while charging requests of lower priority ESUs are deferred to future time slots. In this way, each ESU can make sure that charging schedules are computed correctly. Finally, we have implemented the proposed mechanism on the Ethereum test-bed blockchain, and our analysis shows that execution cost can be acceptable in terms of gas consumption while enabling decentralized charging coordination with increased transparency, reliability, and privacy preserving.
FPT-algorithms for computing Gromov-Hausdorff and interleaving distances between trees
Venue: arXiv cs.CG 2019
Year: 2019

Gromov-Hausdorff (GH) distance is a natural way to measure the distortion between two metric spaces. However, there has been only limited algorithmic development to compute or approximate this distance. We focus on computing the Gromov-Hausdorff distance between two metric trees. Roughly speaking, a metric tree is a metric space that can be realized by the shortest path metric on a tree. Previously, Agarwal et al. showed that even for trees with unit edge length, it is NP hard to approximate the GH distance between them within a factor of 3. In this paper, we present a fixed-parameter tractable (FPT) algorithm that can approximate the GH distance between two general metric trees within a factor of 14. Interestingly, the development of our algorithm is made possible by a connection between the GH distance for metric trees and the interleaving distance for the so-called merge trees. The merge trees arise in practice naturally as a simple yet meaningful topological summary, and are of independent interest. It turns out that an exact or approximation algorithm for the interleaving distance leads to an approximation algorithm for the Gromov-Hausdorff distance. One of the key contributions of our work is that we re-define the interleaving distance in a way that makes it easier to develop dynamic programming approaches to compute it. We then present a FPT algorithm to compute the interleaving distance between two merge trees exactly, which ultimately leads to an FPT-algorithm to approximate the GH distance between two metric trees. This exact FPT-algorithm to compute the interleaving distance between merge trees is of interest itself, as it is known that it is NP-hard to approximate it within a factor of 3, and previously the best known algorithm has an approximation factor of $O(\sqrt{n})$ even for trees with unit edge length.
OverSketch: Approximate Matrix Multiplication for the Cloud
Venue: arXiv cs.DC 2019
Year: 2019

We propose OverSketch, an approximate algorithm for distributed matrix multiplication in serverless computing. OverSketch leverages ideas from matrix sketching and high-performance computing to enable cost-efficient multiplication that is resilient to faults and straggling nodes pervasive in low-cost serverless architectures. We establish statistical guarantees on the accuracy of OverSketch and empirically validate our results by solving a large-scale linear program using interior-point methods and demonstrate a 34% reduction in compute time on AWS Lambda.
Machine Learning Algorithms for Classification of Microcirculation Images from Septic and Non-Septic Patients
Venue: arXiv cs.CV 2019
Year: 2019

Sepsis is a life-threatening disease and one of the major causes of death in hospitals. Imaging of microcirculatory dysfunction is a promising approach for automated diagnosis of sepsis. We report a machine learning classifier capable of distinguishing non-septic and septic images from dark field microcirculation videos of patients. The classifier achieves an accuracy of 89.45%. The area under the receiver operating characteristics of the classifier was 0.92, the precision was 0.92 and the recall was 0.84. Codes representing the learned feature space of trained classifier were visualized using t-SNE embedding and were separable and distinguished between images from critically ill and non-septic patients. Using an unsupervised convolutional autoencoder, independent of the clinical diagnosis, we also report clustering of learned features from a compressed representation associated with healthy images and those with microcirculatory dysfunction. The feature space used by our trained classifier to distinguish between images from septic and non-septic patients has potential diagnostic application.
SocialGCN: An Efficient Graph Convolutional Network based Model for Social Recommendation
Venue: arXiv cs.IR 2019
Year: 2019

Collaborative Filtering (CF) is one of the most successful approaches for recommender systems. With the emergence of online social networks, social recommendation has become a popular research direction. Most of these social recommendation models utilized each user's local neighbors' preferences to alleviate the data sparsity issue in CF. However, they only considered the local neighbors of each user and neglected the process that users' preferences are influenced as information diffuses in the social network. Recently, Graph Convolutional Networks~(GCN) have shown promising results by modeling the information diffusion process in graphs that leverage both graph structure and node feature information. To this end, in this paper, we propose an effective graph convolutional neural network based model for social recommendation. Based on a classical CF model, the key idea of our proposed model is that we borrow the strengths of GCNs to capture how users' preferences are influenced by the social diffusion process in social networks. The diffusion of users' preferences is built on a layer-wise diffusion manner, with the initial user embedding as a function of the current user's features and a free base user latent vector that is not contained in the user feature. Similarly, each item's latent vector is also a combination of the item's free latent vector, as well as its feature representation. Furthermore, we show that our proposed model is flexible when user and item features are not available. Finally, extensive experimental results on two real-world datasets clearly show the effectiveness of our proposed model.
Secrecy Outage Analysis for Cooperative NOMA Systems with Relay Selection Scheme
Venue: arXiv cs.IT 2019
Year: 2019

This paper considers the secrecy outage performance of a multiple-relay assisted non-orthogonal multiple access (NOMA) network over Nakagami-$m$ fading channels. Two slots are utilized to transmit signals from the base station to destination. At the first slot, the base station broadcasts the superposition signal of the two users to all decode-and-forward relays by message mapping strategy. Then the selected relay transmits superposition signal to the two users via power-domain NOMA technology. Three relay selection (RS) schemes, i.e., optimal single relay selection (OSRS) scheme, two-step single relay selection (TSRS) scheme, and optimal dual relay selection (ODRS) scheme, are proposed and the secrecy outage performance are analyzed. As a benchmark, we also examine the secrecy outage performance of the NOMA systems with traditional multiple relays combining (TMRC) scheme in which all the relay that successfully decode signals from the source forward signals to the NOMA users with equal power. Considering the correlation between the secrecy capacity of two users and different secrecy requirement for two NOMA users, the closed-form expressions for the security outage probability (SOP) of the proposed OSRS, TSRS, and ODRS schemes along with the TMRC scheme are derived and validated via simulations. To get more insights, we also derive the closed-form expressions for the asymptotic SOP for all the schemes with fixed and dynamic power allocations. Furthermore, the secrecy diversity order (SDO) of cooperative NOMA systems is obtained. The results demonstrate that our proposed schemes can significantly enhance the secrecy performance compared to the TMRC scheme and that all the RS schemes with fixed power allocation obtain zero SDO and the OSRS scheme with dynamic power allocation obtains the same SDO as TMRC.
Uncovering the Social Interaction in Swarm Intelligence with Network Science
Venue: arXiv cs.NE 2019
Year: 2019

Swarm intelligence is the collective behavior emerging in systems with locally interacting components. Because of their self-organization capabilities, swarm-based systems show essential properties for handling real-world problems such as robustness, scalability, and flexibility. Yet, we do not know why swarm-based algorithms work well and neither we can compare the different approaches in the literature. The lack of a common framework capable of characterizing these several swarm-based algorithms, transcending their particularities, has led to a stream of publications inspired by different aspects of nature without a systematic comparison over existing approaches. Here, we address this gap by introducing a network-based framework---the interaction network---to examine computational swarm-based systems via the optics of the social dynamics of such interaction network; a clear example of network science being applied to bring further clarity to a complicated field within artificial intelligence. We discuss the social interactions of four well-known swarm-based algorithms and provide an in-depth case study of the Particle Swarm Optimization. The interaction network enables researchers to study swarm algorithms as systems, removing the algorithm particularities from the analyses while focusing on the structure of the social interactions.
Scale-variant topological information for characterizing the structure of complex networks
Venue: arXiv cs.SI 2019
Year: 2019

The structure of real-world networks is usually difficult to characterize owing to the variation of topological scales, the nondyadic complex interactions, and the fluctuations in the network. We aim to address these problems by introducing a general framework using a method based on topological data analysis. By considering the diffusion process at a single specified timescale in a network, we map the network nodes to a finite set of points that contains the topological information of the network at a single scale. Subsequently, we study the shape of these point sets over variable timescales that provide scale-variant topological information, to understand the varying topological scales and the complex interactions in the network. We conduct experiments on synthetic and real-world data to demonstrate the effectiveness of the proposed framework in identifying network models, classifying real-world networks, and detecting transition points in time-evolving networks. Overall, our study presents a unified analysis that can be applied to more complex network structures, as in the case of multilayer and multiplex networks.