OpenRaiser/Intern-Atlas huggingface dataset:
Practical calibration of the temperature parameter in Gibbs posteriors
Venue: arXiv cs.LG 2020
Year: 2020

PAC-Bayesian algorithms and Gibbs posteriors are gaining popularity due to their robustness against model misspecification even when Bayesian inference is inconsistent. The PAC-Bayesian alpha-posterior is a generalization of the standard Bayes posterior which can be tempered with a parameter alpha to handle inconsistency. Data driven methods for tuning alpha have been proposed but are still few, and are often computationally heavy. Additionally, the adequacy of these methods in cases where we use variational approximations instead of exact alpha-posteriors is not clear. This narrows their usage to simple models and prevents their application to large-scale problems. We hence need fast methods to tune alpha that work with both exact and variational alpha-posteriors. First, we propose two data driven methods for tuning alpha, based on sample-splitting and bootstrapping respectively. Second, we formulate the (exact or variational) posteriors of three popular statistical models, and modify them into alpha-posteriors. For each model, we test our strategies and compare them with standard Bayes and Grunwald's SafeBayes. While bootstrapping achieves mixed results, sample-splitting and SafeBayes perform well on the exact and variational alpha-posteriors we describe, and achieve better results than standard Bayes in misspecified or complex models. Additionally, sample-splitting outperforms SafeBayes in terms of speed. Sample-splitting offers a fast and easy solution to inconsistency and typically performs similarly or better than Bayesian inference. Our results provide hints on the calibration of alpha in PAC-Bayesian and Gibbs posteriors, and may facilitate using these methods in large and complex models.
Multi-Domain Learning and Identity Mining for Vehicle Re-Identification
Venue: arXiv cs.CV 2020
Year: 2020

This paper introduces our solution for the Track2 in AI City Challenge 2020 (AICITY20). The Track2 is a vehicle re-identification (ReID) task with both the real-world data and synthetic data. Our solution is based on a strong baseline with bag of tricks (BoT-BS) proposed in person ReID. At first, we propose a multi-domain learning method to joint the real-world and synthetic data to train the model. Then, we propose the Identity Mining method to automatically generate pseudo labels for a part of the testing data, which is better than the k-means clustering. The tracklet-level re-ranking strategy with weighted features is also used to post-process the results. Finally, with multiple-model ensemble, our method achieves 0.7322 in the mAP score which yields third place in the competition. The codes are available at https://github.com/heshuting555/AICITY2020_DMT_VehicleReID.
Provably robust deep generative models
Venue: arXiv cs.LG 2020
Year: 2020

Recent work in adversarial attacks has developed provably robust methods for training deep neural network classifiers. However, although they are often mentioned in the context of robustness, deep generative models themselves have received relatively little attention in terms of formally analyzing their robustness properties. In this paper, we propose a method for training provably robust generative models, specifically a provably robust version of the variational auto-encoder (VAE). To do so, we first formally define a (certifiably) robust lower bound on the variational lower bound of the likelihood, and then show how this bound can be optimized during training to produce a robust VAE. We evaluate the method on simple examples, and show that it is able to produce generative models that are substantially more robust to adversarial attacks (i.e., an adversary trying to perturb inputs so as to drastically lower their likelihood under the model).
MangaGAN: Unpaired Photo-to-Manga Translation Based on The Methodology of Manga Drawing
Venue: arXiv cs.CV 2020
Year: 2020

Manga is a world popular comic form originated in Japan, which typically employs black-and-white stroke lines and geometric exaggeration to describe humans' appearances, poses, and actions. In this paper, we propose MangaGAN, the first method based on Generative Adversarial Network (GAN) for unpaired photo-to-manga translation. Inspired by how experienced manga artists draw manga, MangaGAN generates the geometric features of manga face by a designed GAN model and delicately translates each facial region into the manga domain by a tailored multi-GANs architecture. For training MangaGAN, we construct a new dataset collected from a popular manga work, containing manga facial features, landmarks, bodies, and so on. Moreover, to produce high-quality manga faces, we further propose a structural smoothing loss to smooth stroke-lines and avoid noisy pixels, and a similarity preserving module to improve the similarity between domains of photo and manga. Extensive experiments show that MangaGAN can produce high-quality manga faces which preserve both the facial similarity and a popular manga style, and outperforms other related state-of-the-art methods.
Typilus: Neural Type Hints
Venue: arXiv cs.PL 2020
Year: 2020

Type inference over partial contexts in dynamically typed languages is challenging. In this work, we present a graph neural network model that predicts types by probabilistically reasoning over a program's structure, names, and patterns. The network uses deep similarity learning to learn a TypeSpace -- a continuous relaxation of the discrete space of types -- and how to embed the type properties of a symbol (i.e. identifier) into it. Importantly, our model can employ one-shot learning to predict an open vocabulary of types, including rare and user-defined ones. We realise our approach in Typilus for Python that combines the TypeSpace with an optional type checker. We show that Typilus accurately predicts types. Typilus confidently predicts types for 70% of all annotatable symbols; when it predicts a type, that type optionally type checks 95% of the time. Typilus can also find incorrect type annotations; two important and popular open source libraries, fairseq and allennlp, accepted our pull requests that fixed the annotation errors Typilus discovered.
Frechet-Like Distances between Two Merge Trees
Venue: arXiv cs.CC 2020
Year: 2020

The purpose of this paper is to extend the definition of Frechet distance which measures the distance between two curves to a distance (Frechet-Like distance) which measures the similarity between two rooted trees. The definition of Frechet-Like distance is as follows: Tow men start from the roots of two trees. When they reach to a node with the degree of more than $2$, they construct $k-1$ men which $k$ is the outgoing degree of the node and each man monitor a man in another tree (there is a rope between them). The distance is the minimum length of the ropes between the men and the men whom are monitored and they all go forward (the geodesic distance between them to the root of the tree increases) and reach to the leaves of the trees. Here, I prove that the Frechet-Like distance between two trees is SNP-hard to compute. I modify the definition of Frechet-Like distance to measure the distance between tow merge trees, and I prove the relation between the interleaving distance and the modified Frechet-Like distance.
Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay
Venue: arXiv cs.DS 2020
Year: 2020

We consider the problem of scheduling $n$ precedence-constrained jobs on $m$ uniformly-related machines in the presence of an arbitrary, fixed communication delay $ρ$. We consider a model that allows job duplication, i.e. processing of the same job on multiple machines, which, as we show, can reduce the length of a schedule (i.e., its makespan) by a logarithmic factor. Our main result is an $O(\log m \log ρ/ \log \log ρ)$-approximation algorithm for minimizing makespan, assuming the minimum makespan is at least $ρ$. Our algorithm is based on rounding a linear programming relaxation for the problem, which includes carefully designed constraints capturing the interaction among communication delay, precedence requirements, varying speeds, and job duplication. Our result builds on two previous lines of work, one with communication delay but identical machines (Lepere, Rapine 2002) and the other with uniformly-related machines but no communication delay (Chudak, Shmoys 1999). We next show that the integrality gap of our mathematical program is $Ω(\sqrt{\log ρ})$. Our gap construction employs expander graphs and exploits a property of robust expansion and its generalization to paths of longer length. Finally, we quantify the advantage of duplication in scheduling with communication delay. We show that the best schedule without duplication can have makespan $Ω(ρ/\log ρ)$ or $Ω(\log m/\log\log m)$ or $Ω(\log n/\log \log n)$ times that of an optimal schedule allowing duplication. Nevertheless, we present a polynomial time algorithm to transform any schedule to a schedule without duplication at the cost of a $O(\log^2 n \log m)$ factor increase in makespan. Together with our makespan approximation algorithm for schedules allowing duplication, this also yields a polylogarithmic-approximation algorithm for the setting where duplication is not allowed.
Learning to Classify Intents and Slot Labels Given a Handful of Examples
Venue: arXiv cs.CL 2020
Year: 2020

Intent classification (IC) and slot filling (SF) are core components in most goal-oriented dialogue systems. Current IC/SF models perform poorly when the number of training examples per class is small. We propose a new few-shot learning task, few-shot IC/SF, to study and improve the performance of IC and SF models on classes not seen at training time in ultra low resource scenarios. We establish a few-shot IC/SF benchmark by defining few-shot splits for three public IC/SF datasets, ATIS, TOP, and Snips. We show that two popular few-shot learning algorithms, model agnostic meta learning (MAML) and prototypical networks, outperform a fine-tuning baseline on this benchmark. Prototypical networks achieves significant gains in IC performance on the ATIS and TOP datasets, while both prototypical networks and MAML outperform the baseline with respect to SF on all three datasets. In addition, we demonstrate that joint training as well as the use of pre-trained language models, ELMo and BERT in our case, are complementary to these few-shot learning methods and yield further gains.
Tension Space Analysis for Emergent Narrative
Venue: arXiv cs.AI 2020
Year: 2020

Emergent narratives provide a unique and compelling approach to interactive storytelling through simulation, and have applications in games, narrative generation, and virtual agents. However the inherent complexity of simulation makes understanding the expressive potential of emergent narratives difficult, particularly at the design phase of development. In this paper, we present a novel approach to emergent narrative using the narratological theory of possible worlds and demonstrate how the design of works in such a system can be understood through a formal means of analysis inspired by expressive range analysis. Lastly, we propose a novel way through which content may be authored for the emergent narrative system using a sketch-based interface.
MobiGyges: A mobile hidden volume for preventing data loss, improving storage utilization, and avoiding device reboot
Venue: arXiv cs.CR 2020
Year: 2020

Sensitive data protection is essential for mobile users. Plausibly Deniable Encryption (PDE) systems provide an effective manner to protect sensitive data by hiding them on the device. However, existing PDE systems can lose data due to overriding the hidden volume, waste physical storage because of the reserved area used for avoiding data loss, and require device reboot when using the hidden volume. This paper presents MobiGyges, a hidden volume-based mobile PDE system, to fill the gap. MobiGyges addresses the problem of data loss by restricting each storage block used only by one volume, and it improves storage utilization by eliminating the reserved area. MobiGyges can also avoid device reboot by mounting the hidden volume dynamically on-demand with the Dynamic Mounting service. Moreover, we identify two novel PDE oriented attacks, the capacity comparison attack and the fill-to-full attack. MobiGyges can defend them by jointly leveraging the Shrunk U-disk method and multi-level deniability. We implement the MobiGyges proof-of-concept system on a real mobile phone Google Nexus 6P with LineageOS 13. Experimental results show that MobiGyges prevents data loss, avoids device reboot, improves storage utilization by over 30% with acceptable performance overhead compared with current works.
TensorOpt: Exploring the Tradeoffs in Distributed DNN Training with Auto-Parallelism
Venue: arXiv cs.DC 2020
Year: 2020

A good parallelization strategy can significantly improve the efficiency or reduce the cost for the distributed training of deep neural networks (DNNs). Recently, several methods have been proposed to find efficient parallelization strategies but they all optimize a single objective (e.g., execution time, memory consumption) and produce only one strategy. We propose FT, an efficient algorithm that searches for an optimal set of parallelization strategies to allow the trade-off among different objectives. FT can adapt to different scenarios by minimizing the memory consumption when the number of devices is limited and fully utilize additional resources to reduce the execution time. For popular DNN models (e.g., vision, language), an in-depth analysis is conducted to understand the trade-offs among different objectives and their influence on the parallelization strategies. We also develop a user-friendly system, called TensorOpt, which allows users to run their distributed DNN training jobs without caring the details of parallelization strategies. Experimental results show that FT runs efficiently and provides accurate estimation of runtime costs, and TensorOpt is more flexible in adapting to resource availability compared with existing frameworks.
Visible Insights of the Invisible Pandemic: A Scientometric, Altmetric and Topic Trend Analysis
Venue: arXiv cs.DL 2020
Year: 2020

The recent SARS-COV-2 virus outbreak has created an unprecedented global health crisis! The disease is showing alarming trends with the number of people getting infected with this disease, new cases and death rate are all highlighting the need to control this disease at the earliest. The strategy now for the governments around the globe is how to limit the spread of the virus until the research community develops treatment/drug or vaccination against the virus. The outbreak of this disease has unsurprisingly led to huge volume of research within a short period of time surrounding this disease. It has also led to aggressive social media activity on twitter, Facebook, dedicated blogs, news reports and other online sites actively involved in discussing about the various aspects of and related to this disease. It becomes a useful and challenging exercise to draw from this huge volume of research, the key papers that form the research front, its influence in the research community, and other important research insights. Similarly, it becomes important to discern the key issues that influence the society concerning this disease. The paper is motivated by this. It attempts to distinguish which are the most influential papers, the key knowledge base and major topics surrounding the research covered by COVID-19. Further it attempts to capture the society's perception by discerning key topics that are trending online. The study concludes by highlighting the implications of this study.
Flexibility of Planar Graphs -- Sharpening the Tools to Get Lists of Size Four
Venue: arXiv cs.DM 2020
Year: 2020

A graph where each vertex $v$ has a list $L(v)$ of available colors is $L$-colorable if there is a proper coloring such that the color of $v$ is in $L(v)$ for each $v$. A graph is $k$-choosable if every assignment $L$ of at least $k$ colors to each vertex guarantees an $L$-coloring. Given a list assignment $L$, an $L$-request for a vertex $v$ is a color $c\in L(v)$. In this paper, we look at a variant of the widely studied class of precoloring extension problems from [Z. Dvořák, S. Norin, and L. Postle: List coloring with requests. J. Graph Theory 2019], wherein one must satisfy "enough", as opposed to all, of the requested set of precolors. A graph $G$ is $\varepsilon$-flexible for list size $k$ if for any $k$-list assignment $L$, and any set $S$ of $L$-requests, there is an $L$-coloring of $G$ satisfying an $\varepsilon$-fraction of the requests in $S$. It is conjectured that planar graphs are $\varepsilon$-flexible for list size $5$, yet it is proved only for list size $6$ and for certain subclasses of planar graphs. We give a stronger version of the main tool used in the proofs of the aforementioned results. By doing so, we improve upon a result by Masařík and show that planar graphs without $K_4^-$ are $\varepsilon$-flexible for list size $5$. We also prove that planar graphs without $4$-cycles and $3$-cycle distance at least 2 are $\varepsilon$-flexible for list size $4$. Finally, we introduce a new (slightly weaker) form of $\varepsilon$-flexibility where each vertex has exactly one request. In that setting, we provide a stronger tool and we demonstrate its usefulness to further extend the class of graphs that are $\varepsilon$-flexible for list size $5$.
YOLOv4: Optimal Speed and Accuracy of Object Detection
Venue: arXiv cs.CV 2020
Year: 2020

There are a huge number of features which are said to improve Convolutional Neural Network (CNN) accuracy. Practical testing of combinations of such features on large datasets, and theoretical justification of the result, is required. Some features operate on certain models exclusively and for certain problems exclusively, or only for small-scale datasets; while some features, such as batch-normalization and residual-connections, are applicable to the majority of models, tasks, and datasets. We assume that such universal features include Weighted-Residual-Connections (WRC), Cross-Stage-Partial-connections (CSP), Cross mini-Batch Normalization (CmBN), Self-adversarial-training (SAT) and Mish-activation. We use new features: WRC, CSP, CmBN, SAT, Mish activation, Mosaic data augmentation, CmBN, DropBlock regularization, and CIoU loss, and combine some of them to achieve state-of-the-art results: 43.5% AP (65.7% AP50) for the MS COCO dataset at a realtime speed of ~65 FPS on Tesla V100. Source code is at https://github.com/AlexeyAB/darknet
Semi-Supervised Models via Data Augmentationfor Classifying Interactive Affective Responses
Venue: arXiv cs.CL 2020
Year: 2020

We present semi-supervised models with data augmentation (SMDA), a semi-supervised text classification system to classify interactive affective responses. SMDA utilizes recent transformer-based models to encode each sentence and employs back translation techniques to paraphrase given sentences as augmented data. For labeled sentences, we performed data augmentations to uniform the label distributions and computed supervised loss during training process. For unlabeled sentences, we explored self-training by regarding low-entropy predictions over unlabeled sentences as pseudo labels, assuming high-confidence predictions as labeled data for training. We further introduced consistency regularization as unsupervised loss after data augmentations on unlabeled data, based on the assumption that the model should predict similar class distributions with original unlabeled sentences as input and augmented sentences as input. Via a set of experiments, we demonstrated that our system outperformed baseline models in terms of F1-score and accuracy.
Encoding Power Traces as Images for Efficient Side-Channel Analysis
Venue: arXiv cs.CR 2020
Year: 2020

Side-Channel Attacks (SCAs) are a powerful method to attack implementations of cryptographic algorithms. State-of-the-art techniques such as template attacks and stochastic models usually require a lot of manual preprocessing and feature extraction by the attacker. Deep Learning (DL) methods have been introduced to simplify SCAs and simultaneously lowering the amount of required side-channel traces for a successful attack. However, the general success of DL is largely driven by their capability to classify images, a field in which they easily outperform humans. In this paper, we present a novel technique to interpret 1D traces as 2D images. We show and compare several techniques to transform power traces into images, and apply these on different implementations of the Advanced Encryption Standard (AES). By allowing the neural network to interpret the trace as an image, we are able to significantly reduce the number of required attack traces for a correct key guess.We also demonstrate that the attack efficiency can be improved by using multiple 2D images in the depth channel as an input. Furthermore, by applying image-based data augmentation, we show how the number of profiling traces is reduced by a factor of 50 while simultaneously enhancing the attack performance. This is a crucial improvement, as the amount of traces that can be recorded by an attacker is often very limited in real-life applications.
Long-Short Term Spatiotemporal Tensor Prediction for Passenger Flow Profile
Venue: arXiv cs.LG 2020
Year: 2020

Spatiotemporal data is very common in many applications, such as manufacturing systems and transportation systems. It is typically difficult to be accurately predicted given intrinsic complex spatial and temporal correlations. Most of the existing methods based on various statistical models and regularization terms, fail to preserve innate features in data alongside their complex correlations. In this paper, we focus on a tensor-based prediction and propose several practical techniques to improve prediction. For long-term prediction specifically, we propose the "Tensor Decomposition + 2-Dimensional Auto-Regressive Moving Average (2D-ARMA)" model, and an effective way to update prediction real-time; For short-term prediction, we propose to conduct tensor completion based on tensor clustering to avoid oversimplifying and ensure accuracy. A case study based on the metro passenger flow data is conducted to demonstrate the improved performance.
SEVurity: No Security Without Integrity -- Breaking Integrity-Free Memory Encryption with Minimal Assumptions
Venue: arXiv cs.CR 2020
Year: 2020

One reason for not adopting cloud services is the required trust in the cloud provider: As they control the hypervisor, any data processed in the system is accessible to them. Full memory encryption for Virtual Machines (VM) protects against curious cloud providers as well as otherwise compromised hypervisors. AMD Secure Encrypted Virtualization (SEV) is the most prevalent hardware-based full memory encryption for VMs. Its newest extension, SEV-ES, also protects the entire VM state during context switches, aiming to ensure that the host neither learns anything about the data that is processed inside the VM, nor is able to modify its execution state. Several previous works have analyzed the security of SEV and have shown that, by controlling I/O, it is possible to exfiltrate data or even gain control over the VM's execution. In this work, we introduce two new methods that allow us to inject arbitrary code into SEV-ES secured virtual machines. Due to the lack of proper integrity protection, it is sufficient to reuse existing ciphertext to build a high-speed encryption oracle. As a result, our attack no longer depends on control over the I/O, which is needed by prior attacks. As I/O manipulation is highly detectable, our attacks are stealthier. In addition, we reverse-engineer the previously unknown, improved Xor-Encrypt-Xor (XEX) based encryption mode, that AMD is using on updated processors, and show, for the first time, how it can be overcome by our new attacks.