OpenRaiser/Intern-Atlas huggingface dataset:
Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

Recent works using deep learning to solve the Traveling Salesman Problem (TSP) have focused on learning construction heuristics. Such approaches find TSP solutions of good quality but require additional procedures such as beam search and sampling to improve solutions and achieve state-of-the-art performance. However, few studies have focused on improvement heuristics, where a given solution is improved until reaching a near-optimal one. In this work, we propose to learn a local search heuristic based on 2-opt operators via deep reinforcement learning. We propose a policy gradient algorithm to learn a stochastic policy that selects 2-opt operations given a current solution. Moreover, we introduce a policy neural network that leverages a pointing attention mechanism, which unlike previous works, can be easily extended to more general k-opt moves. Our results show that the learned policies can improve even over random initial solutions and approach near-optimal solutions at a faster rate than previous state-of-the-art deep learning methods.
A Quadratic Form Approach to Construction A of Lattices over Cyclic Algebras
Venue: arXiv cs.IT 2020
Year: 2020

We propose a construction of lattices from (skew-) polynomial codes, by endowing quotients of some ideals in both number fields and cyclic algebras with a suitable trace form. We give criteria for unimodularity. This yields integral and unimodular lattices with a multiplicative structure. Examples are provided.
Error Detection and Correction in Communication Networks
Venue: arXiv cs.IT 2020
Year: 2020

Let $G$ be a connected graph on $n$ vertices and $C$ be an $(n,k,d)$ code with $d\ge 2$, defined on the alphabet set $\{0,1\}^m$. Suppose that for $1\le i\le n$, the $i$-th vertex of $G$ holds an input symbol $x_i\in\{0,1\}^m$ and let $\vec{x}=(x_1,\ldots,x_n)\in\{0,1\}^{mn}$ be the input vector formed by those symbols. Assume that each vertex of $G$ can communicate with its neighbors by transmitting messages along the edges, and these vertices must decide deterministically, according to a predetermined communication protocol, that whether $\vec{x}\in C$. Then what is the minimum communication cost to solve this problem? Moreover, if $\vec{x}\not\in C$, say, there is less than $\lfloor(d-1)/2\rfloor$ input errors among the $x_i$'s, then what is the minimum communication cost for error correction? In this paper we initiate the study of the two problems mentioned above. For the error detection problem, we obtain two lower bounds on the communication cost as functions of $n,k,d,m$, and our bounds are tight for several graphs and codes. For the error correction problem, we design a protocol which can efficiently correct a single input error when $G$ is a cycle and $C$ is a repetition code. We also present several interesting problems for further research.
Ticking clocks as dependent right adjoints: Denotational semantics for clocked type theory
Venue: arXiv cs.LO 2020
Year: 2020

Clocked Type Theory (CloTT) is a type theory for guarded recursion useful for programming with coinductive types, allowing productivity to be encoded in types, and for reasoning about advanced programming language features using an abstract form of step-indexing. CloTT has previously been shown to enjoy a number of syntactic properties including strong normalisation, canonicity and decidability of the equational theory. In this paper we present a denotational semantics for CloTT useful, e.g., for studying future extensions of CloTT with constructions such as path types. The main challenge for constructing this model is to model the notion of ticks on a clock used in CloTT for coinductive reasoning about coinductive types. We build on a category previously used to model guarded recursion with multiple clocks. In this category there is an object of clocks but no object of ticks, and so tick-assumptions in a context can not be modelled using standard tools. Instead we model ticks using dependent right adjoint functors, a generalisation of the category theoretic notion of adjunction to the setting of categories with families. Dependent right adjoints are known to model Fitch-style modal types, but in the case of CloTT, the modal operators constitute a family indexed internally in the type theory by clocks. We model this family using a dependent right adjoint on the slice category over the object of clocks. Finally we show how to model the tick constant of CloTT using a semantic substitution. This work improves on a previous model by the first two named authors which not only had a flaw but was also considerably more complicated.
Unsupervised Domain Adaptation with Progressive Domain Augmentation
Venue: arXiv cs.LG 2020
Year: 2020

Domain adaptation aims to exploit a label-rich source domain for learning classifiers in a different label-scarce target domain. It is particularly challenging when there are significant divergences between the two domains. In the paper, we propose a novel unsupervised domain adaptation method based on progressive domain augmentation. The proposed method generates virtual intermediate domains via domain interpolation, progressively augments the source domain and bridges the source-target domain divergence by conducting multiple subspace alignment on the Grassmann manifold. We conduct experiments on multiple domain adaptation tasks and the results shows the proposed method achieves the state-of-the-art performance.
Generative Forensics: Procedural Generation and Information Games
Venue: arXiv cs.AI 2020
Year: 2020

Procedural generation is used across game design to achieve a wide variety of ends, and has led to the creation of several game subgenres by injecting variance, surprise or unpredictability into otherwise static designs. Information games are a type of mystery game in which the player is tasked with gathering knowledge and developing an understanding of an event or system. Their reliance on player knowledge leaves them vulnerable to spoilers and hard to replay. In this paper we introduce the notion of generative forensics games, a subgenre of information games that challenge the player to understand the output of a generative system. We introduce information games, show how generative forensics develops the idea, report on two prototype games we created, and evaluate our work on generative forensics so far from a player and a designer perspective.
Software Engineering For Automated Game Design
Venue: arXiv cs.SE 2020
Year: 2020

As we develop more assistive and automated game design systems, the question of how these systems should be integrated into game development workflows, and how much adaptation may be required, becomes increasingly important. In this paper we explore the impact of software engineering decisions on the ability of an automated game design system to understand a game's codebase, generate new game code, and evaluate its work. We argue that a new approach to software engineering may be required in order for game developers to fully benefit from automated game designers.
On the Efficient Design of LSM Stores
Venue: arXiv cs.DB 2020
Year: 2020

In the last decade, key-value data storage systems have gained significantly more interest from academia and industry. These systems face numerous challenges concerning storage space- and read optimization. There exists a large potential for improving current solutions by introducing new management techniques and algorithms. In this paper we give an overview of the basic concept of key-value data storage systems and provide an explanation for bottlenecks. Further we introduce two new memory management algorithms and a improved index structure. Finally, these solutions are compared to each other and discussed.
Abstracting Fairness: Oracles, Metrics, and Interpretability
Venue: arXiv cs.LG 2020
Year: 2020

It is well understood that classification algorithms, for example, for deciding on loan applications, cannot be evaluated for fairness without taking context into account. We examine what can be learned from a fairness oracle equipped with an underlying understanding of ``true'' fairness. The oracle takes as input a (context, classifier) pair satisfying an arbitrary fairness definition, and accepts or rejects the pair according to whether the classifier satisfies the underlying fairness truth. Our principal conceptual result is an extraction procedure that learns the underlying truth; moreover, the procedure can learn an approximation to this truth given access to a weak form of the oracle. Since every ``truly fair'' classifier induces a coarse metric, in which those receiving the same decision are at distance zero from one another and those receiving different decisions are at distance one, this extraction process provides the basis for ensuring a rough form of metric fairness, also known as individual fairness. Our principal technical result is a higher fidelity extractor under a mild technical constraint on the weak oracle's conception of fairness. Our framework permits the scenario in which many classifiers, with differing outcomes, may all be considered fair. Our results have implications for interpretablity -- a highly desired but poorly defined property of classification systems that endeavors to permit a human arbiter to reject classifiers deemed to be ``unfair'' or illegitimately derived.
Theoretical Insights into the Use of Structural Similarity Index In Generative Models and Inferential Autoencoders
Venue: arXiv cs.LG 2020
Year: 2020

Generative models and inferential autoencoders mostly make use of $\ell_2$ norm in their optimization objectives. In order to generate perceptually better images, this short paper theoretically discusses how to use Structural Similarity Index (SSIM) in generative models and inferential autoencoders. We first review SSIM, SSIM distance metrics, and SSIM kernel. We show that the SSIM kernel is a universal kernel and thus can be used in unconditional and conditional generated moment matching networks. Then, we explain how to use SSIM distance in variational and adversarial autoencoders and unconditional and conditional Generative Adversarial Networks (GANs). Finally, we propose to use SSIM distance rather than $\ell_2$ norm in least squares GAN.
News-Driven Stock Prediction With Attention-Based Noisy Recurrent State Transition
Venue: arXiv cs.CL 2020
Year: 2020

We consider direct modeling of underlying stock value movement sequences over time in the news-driven stock movement prediction. A recurrent state transition model is constructed, which better captures a gradual process of stock movement continuously by modeling the correlation between past and future price movements. By separating the effects of news and noise, a noisy random factor is also explicitly fitted based on the recurrent states. Results show that the proposed model outperforms strong baselines. Thanks to the use of attention over news events, our model is also more explainable. To our knowledge, we are the first to explicitly model both events and noise over a fundamental stock value state for news-driven stock movement prediction.
Scalar Product Lattice Computation for Efficient Privacy-preserving Systems
Venue: arXiv cs.CR 2020
Year: 2020

Privacy-preserving applications allow users to perform on-line daily actions without leaking sensitive information. Privacy-preserving scalar product is one of the critical algorithms in many private applications. The state-of-the-art privacy-preserving scalar product schemes use either computationally intensive homomorphic (public-key) encryption techniques such as Paillier encryption to achieve strong security (i.e., 128-bit) or random masking technique to achieve high efficiency for low security. In this paper, lattice structures have been exploited to develop an efficient privacy-preserving system. The proposed scheme is not only efficient in computation as compared to the state-of-the-art but also provides high degree of security against quantum attacks. Rigorous security and privacy analyses of the proposed scheme have been provided along with a concrete set of parameters to achieve 128-bit and 256-bit security. Performance analysis shows that the scheme is at least five orders faster than the Paillier schemes and at least twice as faster than the existing randomisation technique at 128-bit security.
Efficiently Finding Higher-Order Mutants
Venue: arXiv cs.SE 2020
Year: 2020

Higher-order mutation has the potential for improving major drawbacks of traditional first-order mutation, such as by simulating more realistic faults or improving test optimization techniques. Despite interest in studying promising higher-order mutants, such mutants are difficult to find due to the exponential search space of mutation combinations. State-of-the-art approaches rely on genetic search, which is often incomplete and expensive due to its stochastic nature. First, we propose a novel way of finding a complete set of higher-order mutants by using variational execution, a technique that can, in many cases, explore large search spaces completely and often efficiently. Second, we use the identified complete set of higher-order mutants to study their characteristics. Finally, we use the identified characteristics to design and evaluate a new search strategy, independent of variational execution, that is highly effective at finding higher-order mutants even in large code bases.
Graph Sequential Network for Reasoning over Sequences
Venue: arXiv cs.CL 2020
Year: 2020

Recently Graph Neural Network (GNN) has been applied successfully to various NLP tasks that require reasoning, such as multi-hop machine reading comprehension. In this paper, we consider a novel case where reasoning is needed over graphs built from sequences, i.e. graph nodes with sequence data. Existing GNN models fulfill this goal by first summarizing the node sequences into fixed-dimensional vectors, then applying GNN on these vectors. To avoid information loss inherent in the early summarization and make sequential labeling tasks on GNN output feasible, we propose a new type of GNN called Graph Sequential Network (GSN), which features a new message passing algorithm based on co-attention between a node and each of its neighbors. We validate the proposed GSN on two NLP tasks: interpretable multi-hop reading comprehension on HotpotQA and graph based fact verification on FEVER. Both tasks require reasoning over multiple documents or sentences. Our experimental results show that the proposed GSN attains better performance than the standard GNN based methods.
Scalable In Situ Lagrangian Flow Map Extraction: Demonstrating the Viability of a Communication-Free Model
Venue: arXiv cs.CE 2020
Year: 2020

We introduce and evaluate a new algorithm for the in situ extraction of Lagrangian flow maps, which we call Boundary Termination Optimization (BTO). Our approach is a communication-free model, requiring no message passing or synchronization between processes, improving scalability, thereby reducing overall execution time and alleviating the encumbrance placed on simulation codes from in situ processing. We terminate particle integration at node boundaries and store only a subset of the flow map that would have been extracted by communicating particles across nodes, thus introducing an accuracy-performance tradeoff. We run experiments with as many as 2048 GPUs and with multiple simulation data sets. For the experiment configurations we consider, our findings demonstrate that our communication-free technique saves as much as 2x to 4x in execution time in situ, while staying nearly as accurate quantitatively and qualitatively as previous work. Most significantly, this study establishes the viability of approaching in situ Lagrangian flow map extraction using communication-free models in the future.
Measuring Social Biases of Crowd Workers using Counterfactual Queries
Venue: arXiv cs.HC 2020
Year: 2020

Social biases based on gender, race, etc. have been shown to pollute machine learning (ML) pipeline predominantly via biased training datasets. Crowdsourcing, a popular cost-effective measure to gather labeled training datasets, is not immune to the inherent social biases of crowd workers. To ensure such social biases aren't passed onto the curated datasets, it's important to know how biased each crowd worker is. In this work, we propose a new method based on counterfactual fairness to quantify the degree of inherent social bias in each crowd worker. This extra information can be leveraged together with individual worker responses to curate a less biased dataset.
ObjectNet Dataset: Reanalysis and Correction
Venue: arXiv cs.CV 2020
Year: 2020

Recently, Barbu et al introduced a dataset called ObjectNet which includes objects in daily life situations. They showed a dramatic performance drop of the state of the art object recognition models on this dataset. Due to the importance and implications of their results regarding generalization ability of deep models, we take a second look at their findings. We highlight a major problem with their work which is applying object recognizers to the scenes containing multiple objects rather than isolated objects. The latter results in around 20-30% performance gain using our code. Compared with the results reported in the ObjectNet paper, we observe that around 10-15 % of the performance loss can be recovered, without any test time data augmentation. In accordance with Barbu et al.'s conclusions, however, we also conclude that deep models suffer drastically on this dataset. Thus, we believe that ObjectNet remains a challenging dataset for testing the generalization power of models beyond datasets on which they have been trained.
Macroscopic network circulation for planar graphs
Venue: arXiv cs.DM 2020
Year: 2020

The analysis of networks, aimed at suitably defined functionality, often focuses on partitions into subnetworks that capture desired features. Chief among the relevant concepts is a 2-partition, that underlies the classical Cheeger inequality, and highlights a constriction (bottleneck) that limits accessibility between the respective parts of the network. In a similar spirit, the purpose of the present work is to introduce a new concept of maximal global circulation and to explore 3-partitions that expose this type of macroscopic feature of networks. Herein, graph circulation is motivated by transportation networks and probabilistic flows (Markov chains) on graphs. Our goal is to quantify the large-scale imbalance of network flows and delineate key parts that mediate such global features. While we introduce and propose these notions in a general setting, in this paper, we only work out the case of planar graphs. We explain that a scalar potential can be identified to encapsulate the concept of circulation, quite similarly as in the case of the curl of planar vector fields. Beyond planar graphs, in the general case, the problem to determine global circulation remains at present a combinatorial problem.
S4oC: A Self-optimizing, Self-adapting Secure System-on-Chip Design Framework to Tackle Unknown Threats -- A Network Theoretic, Learning Approach
Venue: arXiv cs.DC 2020
Year: 2020

We propose a framework for the design and optimization of a secure self-optimizing, self-adapting system-on-chip (S4oC) architecture. The goal is to minimize the impact of attacks such as hardware Trojan and side-channel, by making real-time adjustments. S4oC learns to reconfigure itself, subject to various security measures and attacks, some of which possibly unknown at design time. Furthermore, the data types and patterns of the target applications, environmental conditions, and sources of variations are incorporated. S4oC is a manycore system, modeled as a four-layer graph, representing the model of computation (MoCp), model of connection (MoCn), model of memory (MoM) and model of storage (MoS), with a large number of elements including heterogeneous reconfigurable processing elements in MoCp, and memory elements in the MoM layer. Security driven community detection, and neural networks are utilized for application task clustering, and distributed reinforcement learning (RL) for task mapping.
An Eigenspace Divide-and-Conquer Approach for Large-Scale Optimization
Venue: arXiv cs.NE 2020
Year: 2020

Divide-and-conquer-based (DC-based) evolutionary algorithms (EAs) have achieved notable success in dealing with large-scale optimization problems (LSOPs). However, the appealing performance of this type of algorithms generally requires a high-precision decomposition of the optimization problem, which is still a challenging task for existing decomposition methods. This study attempts to address the above issue from a different perspective and proposes an eigenspace divide-and-conquer (EDC) approach. Different from existing DC-based algorithms that perform decomposition and optimization in the original decision space, EDC first establishes an eigenspace by conducting singular value decomposition on a set of high-quality solutions selected from recent generations. Then it transforms the optimization problem into the eigenspace, and thus significantly weakens the dependencies among the corresponding eigenvariables. Accordingly, these eigenvariables can be efficiently grouped by a simple random strategy and each of the resulting subproblems can be addressed more easily by a traditional EA. To verify the efficiency of EDC, comprehensive experimental studies were conducted on two sets of benchmark functions. Experimental results indicate that EDC is robust to its parameters and has good scalability to the problem dimension. The comparison with several state-of-the-art algorithms further confirms that EDC is pretty competitive and performs better on complicated LSOPs.
Reference Language based Unsupervised Neural Machine Translation
Venue: arXiv cs.CL 2020
Year: 2020

Exploiting a common language as an auxiliary for better translation has a long tradition in machine translation and lets supervised learning-based machine translation enjoy the enhancement delivered by the well-used pivot language in the absence of a source language to target language parallel corpus. The rise of unsupervised neural machine translation (UNMT) almost completely relieves the parallel corpus curse, though UNMT is still subject to unsatisfactory performance due to the vagueness of the clues available for its core back-translation training. Further enriching the idea of pivot translation by extending the use of parallel corpora beyond the source-target paradigm, we propose a new reference language-based framework for UNMT, RUNMT, in which the reference language only shares a parallel corpus with the source, but this corpus still indicates a signal clear enough to help the reconstruction training of UNMT through a proposed reference agreement mechanism. Experimental results show that our methods improve the quality of UNMT over that of a strong baseline that uses only one auxiliary language, demonstrating the usefulness of the proposed reference language-based UNMT and establishing a good start for the community.