OpenRaiser/Intern-Atlas huggingface dataset:
A Probabilistic Simulator of Spatial Demand for Product Allocation
Venue: arXiv cs.AI 2020
Year: 2020

Connecting consumers with relevant products is a very important problem in both online and offline commerce. In physical retail, product placement is an effective way to connect consumers with products. However, selecting product locations within a store can be a tedious process. Moreover, learning important spatial patterns in offline retail is challenging due to the scarcity of data and the high cost of exploration and experimentation in the physical world. To address these challenges, we propose a stochastic model of spatial demand in physical retail. We show that the proposed model is more predictive of demand than existing baselines. We also perform a preliminary study into different automation techniques and show that an optimal product allocation policy can be learned through Deep Q-Learning.
Simulating Lexical Semantic Change from Sense-Annotated Data
Venue: arXiv cs.CL 2020
Year: 2020

We present a novel procedure to simulate lexical semantic change from synchronic sense-annotated data, and demonstrate its usefulness for assessing lexical semantic change detection models. The induced dataset represents a stronger correspondence to empirically observed lexical semantic change than previous synthetic datasets, because it exploits the intimate relationship between synchronic polysemy and diachronic change. We publish the data and provide the first large-scale evaluation gold standard for LSC detection models.
Searching a Database of Source Codes Using Contextualized Code Search
Venue: arXiv cs.SE 2020
Year: 2020

Consider the case where a programmer has written some part of a program, but has left part of the program (such as a method or a function body) incomplete. The goal is to use the context surrounding the missing code to automatically 'figure out' which of the codes in the database would be useful to the programmer in order to help complete the missing code. The search is 'contextualized' in the sense that the search engine should use clues in the partially-completed code to figure out which database code is most useful. The user should not be required to formulate an explicit query. We cast contextualized code search as a learning problem, where the goal is to learn a distribution function computing the likelihood that each database code completes the program, and propose a neural model for predicting which database code is likely to be most useful. Because it will be prohibitively expensive to apply a neural model to each code in a database of millions or billions of codes at search time, one of our key technical concerns is ensuring a speedy search. We address this by learning a 'reverse encoder' that can be used to reduce the problem of evaluating each database code to computing a convolution of two normal distributions.
Simultaneous Signal-and-Interference Alignment for Two-Cell Over-the-Air Computation
Venue: arXiv cs.IT 2020
Year: 2020

The next-generation wireless networks are envisioned to support large-scale sensing and distributed machine learning, thereby enabling new intelligent mobile applications. One common network operation will be the aggregation of distributed data (such as sensor observations or AI-model updates) for functional computation (e.g., averaging) so as to support large-scale sensing and distributed machine learning. An efficient solution for data aggregation, called "over-the-air computation" (AirComp), embeds functional computation into simultaneous access by many edge devices. Such schemes exploit the waveform superposition of a multi-access channel to allow an access point to receive a desired function of simultaneous signals. In this work, we aim at realizing AirComp in a two-cell multi-antenna system. To this end, a novel scheme of simultaneous signal-and-interference alignment (SIA) is proposed that builds on classic IA to manage interference for multi-cell AirComp. The principle of SIA is to divide the spatial channel space into two subspaces with equal dimensions: one for signal alignment required by AirComp and the other for inter-cell IA. As a result, the number of interference-free spatially multiplexed functional streams received by each AP is maximized (equal to half of the available spatial degrees-of-freedom). Furthermore, the number is independent of the population of devices in each cell. In addition, the extension to SIA for more than two cells is discussed.
Fault Tolerance for Service Function Chains
Venue: arXiv cs.NI 2020
Year: 2020

Enterprise network traffic typically traverses a sequence of middleboxes forming a service function chain, or simply a chain. Tolerating failures when they occur along chains is imperative to the availability and reliability of enterprise applications. Making a chain fault-tolerant is challenging since, in the event of failures, the state of faulty middleboxes must be correctly and quickly recovered while providing high throughput and low latency. In this paper, we introduce FTC, novel system design and protocol for fault-tolerant service function chaining. FTC provides strong consistency with up to f middlebox failures for chains of length f+1 or longer without requiring dedicated replica nodes. In FTC, state updates caused by packet processing at a middlebox are collected, piggybacked into the packet, and sent along the chain to be replicated. The evaluation of our FTC implementation shows that compared with the state of art [46], FTC improves throughput by 2-3.5x for a chain of two to five middleboxes.
Visual Question Answering on 360° Images
Venue: arXiv cs.CV 2020
Year: 2020

In this work, we introduce VQA 360, a novel task of visual question answering on 360 images. Unlike a normal field-of-view image, a 360 image captures the entire visual content around the optical center of a camera, demanding more sophisticated spatial understanding and reasoning. To address this problem, we collect the first VQA 360 dataset, containing around 17,000 real-world image-question-answer triplets for a variety of question types. We then study two different VQA models on VQA 360, including one conventional model that takes an equirectangular image (with intrinsic distortion) as input and one dedicated model that first projects a 360 image onto cubemaps and subsequently aggregates the information from multiple spatial resolutions. We demonstrate that the cubemap-based model with multi-level fusion and attention diffusion performs favorably against other variants and the equirectangular-based models. Nevertheless, the gap between the humans' and machines' performance reveals the need for more advanced VQA 360 algorithms. We, therefore, expect our dataset and studies to serve as the benchmark for future development in this challenging task. Dataset, code, and pre-trained models are available online.
Measuring Similarity between Brands using Followers' Post in Social Media
Venue: arXiv cs.SI 2020
Year: 2020

In this paper, we propose a new measure to estimate the similarity between brands via posts of brands' followers on social network services (SNS). Our method was developed with the intention of exploring the brands that customers are likely to jointly purchase. Nowadays, brands use social media for targeted advertising because influencing users' preferences can greatly affect the trends in sales. We assume that data on SNS allows us to make quantitative comparisons between brands. Our proposed algorithm analyzes the daily photos and hashtags posted by each brand's followers. By clustering them and converting them to histograms, we can calculate the similarity between brands. We evaluated our proposed algorithm with purchase logs, credit card information, and answers to the questionnaires. The experimental results show that the purchase data maintained by a mall or a credit card company can predict the co-purchase very well, but not the customer's willingness to buy products of new brands. On the other hand, our method can predict the users' interest on brands with a correlation value over 0.53, which is pretty high considering that such interest to brands are high subjective and individual dependent.
RMWPaxos: Fault-Tolerant In-Place Consensus Sequences
Venue: arXiv cs.DC 2020
Year: 2020

Building consensus sequences based on distributed, fault-tolerant consensus, as used for replicated state machines, typically requires a separate distributed state for every new consensus instance. Allocating and maintaining this state causes significant overhead. In particular, freeing the distributed, outdated states in a fault-tolerant way is not trivial and adds further complexity and cost to the system. In this paper, we propose an extension to the single-decree Paxos protocol that can learn a sequence of consensus decisions 'in-place', i.e. with a single set of distributed states. Our protocol does not require dynamic log structures and hence has no need for distributed log pruning, snapshotting, compaction, or dynamic resource allocation. The protocol builds a fault-tolerant atomic register that supports arbitrary read-modify-write operations. We use the concept of consistent quorums to detect whether the previous consensus still needs to be consolidated or is already finished so that the next consensus value can be safely proposed. Reading a consolidated consensus is done without state modifications and is thereby free of concurrency control and demand for serialisation. A proposer that is not interrupted reaches agreement on consecutive consensus decisions within a single message round-trip per decision by preparing the acceptors eagerly with the previous request.
Trace Clustering on Very Large Event Data in Healthcare Using Frequent Sequence Patterns
Venue: arXiv cs.DB 2020
Year: 2020

Trace clustering has increasingly been applied to find homogenous process executions. However, current techniques have difficulties in finding a meaningful and insightful clustering of patients on the basis of healthcare data. The resulting clusters are often not in line with those of medical experts, nor do the clusters guarantee to help return meaningful process maps of patients' clinical pathways. After all, a single hospital may conduct thousands of distinct activities and generate millions of events per year. In this paper, we propose a novel trace clustering approach by using sample sets of patients provided by medical experts. More specifically, we learn frequent sequence patterns on a sample set, rank each patient based on the patterns, and use an automated approach to determine the corresponding cluster. We find each cluster separately, while the frequent sequence patterns are used to discover a process map. The approach is implemented in ProM and evaluated using a large data set obtained from a university medical center. The evaluation shows F1-scores of 0.7 for grouping kidney injury, 0.9 for diabetes, and 0.64 for head/neck tumor, while the process maps show meaningful behavioral patterns of the clinical pathways of these groups, according to the domain experts.
An Efficient Universal Construction for Large Objects
Venue: arXiv cs.DC 2020
Year: 2020

This paper presents L-UC, a universal construction that efficiently implements dynamic objects of large state in a wait-free manner. The step complexity of L-UC is O(n+kw), where n is the number of processes, k is the interval contention (i.e., the maximum number of active processes during the execution interval of an operation), and w is the worst-case time complexity to perform an operation on the sequential implementation of the simulated object. L-UC efficiently implements objects whose size can change dynamically. It improves upon previous universal constructions either by efficiently handling objects whose state is large and can change dynamically, or by achieving better step complexity.
Deformable Groupwise Image Registration using Low-Rank and Sparse Decomposition
Venue: arXiv cs.CV 2020
Year: 2020

Low-rank and sparse decompositions and robust PCA (RPCA) are highly successful techniques in image processing and have recently found use in groupwise image registration. In this paper, we investigate the drawbacks of the most common RPCA-dissimi\-larity metric in image registration and derive an improved version. In particular, this new metric models low-rank requirements through explicit constraints instead of penalties and thus avoids the pitfalls of the established metric. Equipped with total variation regularization, we present a theoretically justified multilevel scheme based on first-order primal-dual optimization to solve the resulting non-parametric registration problem. As confirmed by numerical experiments, our metric especially lends itself to data involving recurring changes in object appearance and potential sparse perturbations. We numerically compare its peformance to a number of related approaches.
Towards Minimal Supervision BERT-based Grammar Error Correction
Venue: arXiv cs.CL 2020
Year: 2020

Current grammatical error correction (GEC) models typically consider the task as sequence generation, which requires large amounts of annotated data and limit the applications in data-limited settings. We try to incorporate contextual information from pre-trained language model to leverage annotation and benefit multilingual scenarios. Results show strong potential of Bidirectional Encoder Representations from Transformers (BERT) in grammatical error correction task.
Variable-Length Coding for Zero-Error Channel Capacity
Venue: arXiv cs.IT 2020
Year: 2020

The zero-error channel capacity is the maximum asymptotic rate that can be reached with error probability exactly zero, instead of a vanishing error probability. The nature of this problem, essentially combinatorial rather than probabilistic, has led to various researches both in Information Theory and Combinatorics. However, the zero-error capacity is still an open problem, for example the capacity of the noisy-typewriter channel with 7 letters is unknown. In this article, we propose a new approach to construct optimal zero-error codes, based on the concatenation of words of variable-length, taken from a generator set. Three zero-error variable-length coding schemes, referred to as "variable-length coding", "intermingled coding" and "automata-based coding", are under study. We characterize their asymptotic performances via linear difference equations, in terms of simple properties of the generator set, e.g. the roots of the characteristic polynomial, the spectral radius of an adjacency matrix, the inverse of the convergence radius of a generator series. For a specific example, we construct an "intermingled" coding scheme that achieves asymptotically the zero-error capacity.
Exploratory Study on User's Dynamic Visual Acuity and Quality Perception of Impaired Images
Venue: arXiv cs.MM 2020
Year: 2020

In this paper we assess the impact of head movement on user's visual acuity and their quality perception of impaired images. There are physical limitations on the amount of visual information a person can perceive and physical limitations regarding the speed at which our body, and as a consequence our head, can explore a scene. In these limitations lie fundamental solutions for the communication of multimedia systems. As such, subjects were asked to evaluate the perceptual quality of static images presented on a TV screen while their head was in a dynamic (moving) state. The idea is potentially applicable to virtual reality applications and therefore, we also measured the image quality perception of each subject on a head mounted display. Experiments show the significant decrease in visual acuity and quality perception when the user's head is not static, and give an indication on how much the quality can be reduced without the user noticing any impairments.
Pruning Convolutional Neural Networks with Self-Supervision
Venue: arXiv cs.CV 2020
Year: 2020

Convolutional neural networks trained without supervision come close to matching performance with supervised pre-training, but sometimes at the cost of an even higher number of parameters. Extracting subnetworks from these large unsupervised convnets with preserved performance is of particular interest to make them less computationally intensive. Typical pruning methods operate during training on a task while trying to maintain the performance of the pruned network on the same task. However, in self-supervised feature learning, the training objective is agnostic on the representation transferability to downstream tasks. Thus, preserving performance for this objective does not ensure that the pruned subnetwork remains effective for solving downstream tasks. In this work, we investigate the use of standard pruning methods, developed primarily for supervised learning, for networks trained without labels (i.e. on self-supervised tasks). We show that pruned masks obtained with or without labels reach comparable performance when re-trained on labels, suggesting that pruning operates similarly for self-supervised and supervised learning. Interestingly, we also find that pruning preserves the transfer performance of self-supervised subnetwork representations.
Should Artificial Intelligence Governance be Centralised? Design Lessons from History
Venue: arXiv cs.CY 2020
Year: 2020

Can effective international governance for artificial intelligence remain fragmented, or is there a need for a centralised international organisation for AI? We draw on the history of other international regimes to identify advantages and disadvantages in centralising AI governance. Some considerations, such as efficiency and political power, speak in favour of centralisation. Conversely, the risk of creating a slow and brittle institution speaks against it, as does the difficulty in securing participation while creating stringent rules. Other considerations depend on the specific design of a centralised institution. A well-designed body may be able to deter forum shopping and ensure policy coordination. However, forum shopping can be beneficial and a fragmented landscape of institutions can be self-organising. Centralisation entails trade-offs and the details matter. We conclude with two core recommendations. First, the outcome will depend on the exact design of a central institution. A well-designed centralised regime covering a set of coherent issues could be beneficial. But locking-in an inadequate structure may pose a fate worse than fragmentation. Second, for now fragmentation will likely persist. This should be closely monitored to see if it is self-organising or simply inadequate.
Can Giraffes Become Birds? An Evaluation of Image-to-image Translation for Data Generation
Venue: arXiv cs.CV 2020
Year: 2020

There is an increasing interest in image-to-image translation with applications ranging from generating maps from satellite images to creating entire clothes' images from only contours. In the present work, we investigate image-to-image translation using Generative Adversarial Networks (GANs) for generating new data, taking as a case study the morphing of giraffes images into bird images. Morphing a giraffe into a bird is a challenging task, as they have different scales, textures, and morphology. An unsupervised cross-domain translator entitled InstaGAN was trained on giraffes and birds, along with their respective masks, to learn translation between both domains. A dataset of synthetic bird images was generated using translation from originally giraffe images while preserving the original spatial arrangement and background. It is important to stress that the generated birds do not exist, being only the result of a latent representation learned by InstaGAN. Two subsets of common literature datasets were used for training the GAN and generating the translated images: COCO and Caltech-UCSD Birds 200-2011. To evaluate the realness and quality of the generated images and masks, qualitative and quantitative analyses were made. For the quantitative analysis, a pre-trained Mask R-CNN was used for the detection and segmentation of birds on Pascal VOC, Caltech-UCSD Birds 200-2011, and our new dataset entitled FakeSet. The generated dataset achieved detection and segmentation results close to the real datasets, suggesting that the generated images are realistic enough to be detected and segmented by a state-of-the-art deep neural network.
Towards GAN Benchmarks Which Require Generalization
Venue: arXiv cs.LG 2020
Year: 2020

For many evaluation metrics commonly used as benchmarks for unconditional image generation, trivially memorizing the training set attains a better score than models which are considered state-of-the-art; we consider this problematic. We clarify a necessary condition for an evaluation metric not to behave this way: estimating the function must require a large sample from the model. In search of such a metric, we turn to neural network divergences (NNDs), which are defined in terms of a neural network trained to distinguish between distributions. The resulting benchmarks cannot be "won" by training set memorization, while still being perceptually correlated and computable only from samples. We survey past work on using NNDs for evaluation and implement an example black-box metric based on these ideas. Through experimental validation we show that it can effectively measure diversity, sample quality, and generalization.
ReluDiff: Differential Verification of Deep Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

As deep neural networks are increasingly being deployed in practice, their efficiency has become an important issue. While there are compression techniques for reducing the network's size, energy consumption and computational requirement, they only demonstrate empirically that there is no loss of accuracy, but lack formal guarantees of the compressed network, e.g., in the presence of adversarial examples. Existing verification techniques such as Reluplex, ReluVal, and DeepPoly provide formal guarantees, but they are designed for analyzing a single network instead of the relationship between two networks. To fill the gap, we develop a new method for differential verification of two closely related networks. Our method consists of a fast but approximate forward interval analysis pass followed by a backward pass that iteratively refines the approximation until the desired property is verified. We have two main innovations. During the forward pass, we exploit structural and behavioral similarities of the two networks to more accurately bound the difference between the output neurons of the two networks. Then in the backward pass, we leverage the gradient differences to more accurately compute the most beneficial refinement. Our experiments show that, compared to state-of-the-art verification tools, our method can achieve orders-of-magnitude speedup and prove many more properties than existing tools.
PatentTransformer-2: Controlling Patent Text Generation by Structural Metadata
Venue: arXiv cs.CL 2020
Year: 2020

PatentTransformer is our codename for patent text generation based on Transformer-based models. Our goal is "Augmented Inventing." In this second version, we leverage more of the structural metadata in patents. The structural metadata includes patent title, abstract, and dependent claim, in addition to independent claim previously. Metadata controls what kind of patent text for the model to generate. Also, we leverage the relation between metadata to build a text-to-text generation flow, for example, from a few words to a title, the title to an abstract, the abstract to an independent claim, and the independent claim to multiple dependent claims. The text flow can go backward because the relation is trained bidirectionally. We release our GPT-2 models trained from scratch and our code for inference so that readers can verify and generate patent text on their own. As for generation quality, we measure it by both ROUGE and Google Universal Sentence Encoder.