OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Multi-objective Optimization of the Travelling Thief Problem
Venue: arXiv cs.NE 2020
Year: 2020

Investigation of detailed and complex optimisation problem formulations that reflect realistic scenarios is a burgeoning field of research. A growing body of work exists for the Travelling Thief Problem, including multi-objective formulations and comparisons of exact and approximate methods to solve it. However, as many realistic scenarios are non-static in time, dynamic formulations have yet to be considered for the TTP. Definition of dynamics within three areas of the TTP problem are addressed; in the city locations, availability map and item values. Based on the elucidation of solution conservation between initial sets and obtained non-dominated sets, we define a range of initialisation mechanisms using solutions generated via solvers, greedily and randomly. These are then deployed to seed the population after a change and the performance in terms of hypervolume and spread is presented for comparison. Across a range of problems with varying TSP-component and KP-component sizes, we observe interesting trends in line with existing conclusions; there is little benefit to using randomisation as a strategy for initialisation of solution populations when the optimal TSP and KP component solutions can be exploited. Whilst these separate optima don't guarantee good TTP solutions, when combined, provide better initial performance and therefore in some examined instances, provides the best response to dynamic changes. A combined approach that mixes solution generation methods to provide a composite population in response to dynamic changes provides improved performance in some instances for the different dynamic TTP formulations. Potential for further development of a more cooperative combined method are realised to more cohesively exploit known information about the problems.
Deterministic Leader Election in Anonymous Radio Networks
Venue: arXiv cs.DC 2020
Year: 2020

We consider leader election in anonymous radio networks modeled as simple undirected connected graphs. Nodes communicate in synchronous rounds. Nodes are anonymous and execute the same deterministic algorithm, so symmetry can be broken only in one way: by different wake-up times of the nodes. In which situations is it possible to break symmetry and elect a leader using time as symmetry breaker? To answer this question, we consider configurations. A configuration is the underlying graph with nodes tagged by non-negative integers with the following meaning. A node can either wake up spontaneously in the round shown on its tag, according to some global clock, or can be woken up hearing a message sent by one of its already awoken neighbours. The local clock of a node starts at its wakeup and nodes do not have access to the global clock determining their tags. A configuration is feasible if there exists a distributed algorithm that elects a leader for this configuration. Our main result is a complete algorithmic characterization of feasible configurations: we design a centralized decision algorithm, working in polynomial time, whose input is a configuration and which decides if the configuration is feasible. We also provide a dedicated deterministic distributed leader election algorithm for each feasible configuration that elects a leader for this configuration in time $O(n^2σ)$, where $n$ is the number of nodes and $σ$ is the difference between the largest and smallest tag of the configuration. We then prove that there cannot exist a universal deterministic distributed algorithm electing a leader for all feasible configurations. In fact, we show that such a universal algorithm cannot exist even for the class of 4-node feasible configurations. We also prove that a distributed version of our decision algorithm cannot exist.
Short sighted deep learning
Venue: arXiv cs.LG 2020
Year: 2020

A theory explaining how deep learning works is yet to be developed. Previous work suggests that deep learning performs a coarse graining, similar in spirit to the renormalization group (RG). This idea has been explored in the setting of a local (nearest neighbor interactions) Ising spin lattice. We extend the discussion to the setting of a long range spin lattice. Markov Chain Monte Carlo (MCMC) simulations determine both the critical temperature and scaling dimensions of the system. The model is used to train both a single RBM (restricted Boltzmann machine) network, as well as a stacked RBM network. Following earlier Ising model studies, the trained weights of a single layer RBM network define a flow of lattice models. In contrast to results for nearest neighbor Ising, the RBM flow for the long ranged model does not converge to the correct values for the spin and energy scaling dimension. Further, correlation functions between visible and hidden nodes exhibit key differences between the stacked RBM and RG flows. The stacked RBM flow appears to move towards low temperatures whereas the RG flow moves towards high temperature. This again differs from results obtained for nearest neighbor Ising.
How do Quantifiers Affect the Quality of Requirements?
Venue: arXiv cs.SE 2020
Year: 2020

Context: Requirements quality can have a substantial impact on the effectiveness and efficiency of using requirements artifacts in a development process. Quantifiers such as "at least", "all", or "exactly" are common language constructs used to express requirements. Quantifiers can be formulated by affirmative phrases ("At least") or negative phrases ("Not less than"). Problem: It is long assumed that negation in quantification negatively affects the readability of requirements, however, empirical research on these topics remains sparse. Principal Idea: In a web-based experiment with 51 participants, we compare the impact of negations and quantifiers on readability in terms of reading effort, reading error rate and perceived reading difficulty of requirements. Results: For 5 out of 9 quantifiers, our participants performed better on the affirmative phrase compared to the negative phrase. Only for one quantifier, the negative phrase was more effective. Contribution: This research focuses on creating an empirical understanding of the effect of language in Requirements Engineering. It furthermore provides concrete advice on how to phrase requirements.
Protograph-Based Decoding of LDPC Codes with Hamming Weight Amplifiers
Venue: arXiv cs.CR 2020
Year: 2020

A new protograph-based framework for message passing (MP) decoding of low density parity-check (LDPC) codes with Hamming weight amplifiers (HWAs), which are used e.g. in the NIST post-quantum crypto candidate LEDAcrypt, is proposed. The scheme exploits the correlations in the error patterns introduced by the HWA using a turbo-like decoding approach where messages between the decoders for the outer code given by the HWA and the inner LDPC code are exchanged. Decoding thresholds for the proposed scheme are computed using density evolution (DE) analysis for belief propagation (BP) and ternary message passing (TMP) decoding and compared to existing decoding approaches. The proposed scheme improves upon the basic approach of decoding LDPC code from the amplified error and has a similar performance as decoding the corresponding moderate-density parity-check (MDPC) code but with a significantly lower computational complexity.
Iterative Label Improvement: Robust Training by Confidence Based Filtering and Dataset Partitioning
Venue: arXiv cs.LG 2020
Year: 2020

State-of-the-art, high capacity deep neural networks not only require large amounts of labelled training data, they are also highly susceptible to label errors in this data, typically resulting in large efforts and costs and therefore limiting the applicability of deep learning. To alleviate this issue, we propose a novel meta training and labelling scheme that is able to use inexpensive unlabelled data by taking advantage of the generalization power of deep neural networks. We show experimentally that by solely relying on one network architecture and our proposed scheme of iterative training and prediction steps, both label quality and resulting model accuracy can be improved significantly. Our method achieves state-of-the-art results, while being architecture agnostic and therefore broadly applicable. Compared to other methods dealing with erroneous labels, our approach does neither require another network to be trained, nor does it necessarily need an additional, highly accurate reference label set. Instead of removing samples from a labelled set, our technique uses additional sensor data without the need for manual labelling. Furthermore, our approach can be used for semi-supervised learning.
Unsupervised non-parametric change point detection in quasi-periodic signals
Venue: arXiv cs.LG 2020
Year: 2020

We propose a new unsupervised and non-parametric method to detect change points in intricate quasi-periodic signals. The detection relies on optimal transport theory combined with topological analysis and the bootstrap procedure. The algorithm is designed to detect changes in virtually any harmonic or a partially harmonic signal and is verified on three different sources of physiological data streams. We successfully find abnormal or irregular cardiac cycles in the waveforms for the six of the most frequent types of clinical arrhythmias using a single algorithm. The validation and the efficiency of the method are shown both on synthetic and on real time series. Our unsupervised approach reaches the level of performance of the supervised state-of-the-art techniques. We provide conceptual justification for the efficiency of the method and prove the convergence of the bootstrap procedure theoretically.
A note on the rationing of divisible and indivisible goods in a general network
Venue: arXiv cs.GT 2020
Year: 2020

The study of matching theory has gained importance recently with applications in Kidney Exchange, House Allocation, School Choice etc. The general theme of these problems is to allocate goods in a fair manner amongst participating agents. The agents generally have a unit supply/demand of a good that they want to exchange with other agents. On the other hand, Bochet et al. study a more general version of the problem where they allow for agents to have arbitrary number of divisible goods to be rationed to other agents in the network. In this current work, our main focus is on non-bipartite networks where agents have arbitrary units of a homogeneous indivisible good that they want to exchange with their neighbors. Our aim is to develop mechanisms that would identify a fair and strategyproof allocation for the agents in the network. Thus, we generalize the kidney exchange problem to that of a network with arbitrary capacity of available goods. Our main idea is that this problem and a couple of other related versions of non-bipartite fair allocation problem can be suitably transformed to one of fair allocations on bipartite networks for which we know of well studied fair allocation mechanisms.
Deep HyperNetwork-Based MIMO Detection
Venue: arXiv cs.IT 2020
Year: 2020

Optimal symbol detection for multiple-input multiple-output (MIMO) systems is known to be an NP-hard problem. Conventional heuristic algorithms are either too complex to be practical or suffer from poor performance. Recently, several approaches tried to address those challenges by implementing the detector as a deep neural network. However, they either still achieve unsatisfying performance on practical spatially correlated channels, or are computationally demanding since they require retraining for each channel realization. In this work, we address both issues by training an additional neural network (NN), referred to as the hypernetwork, which takes as input the channel matrix and generates the weights of the neural NN-based detector. Results show that the proposed approach achieves near state-of-the-art performance without the need for re-training.
On-Device Information Extraction from SMS using Hybrid Hierarchical Classification
Venue: arXiv cs.CL 2020
Year: 2020

Cluttering of SMS inbox is one of the serious problems that users today face in the digital world where every online login, transaction, along with promotions generate multiple SMS. This problem not only prevents users from searching and navigating messages efficiently but often results in users missing out the relevant information associated with the corresponding SMS like offer codes, payment reminders etc. In this paper, we propose a unique architecture to organize and extract the appropriate information from SMS and further display it in an intuitive template. In the proposed architecture, we use a Hybrid Hierarchical Long Short Term Memory (LSTM)-Convolutional Neural Network (CNN) to categorize SMS into multiple classes followed by a set of entity parsers used to extract the relevant information from the classified message. The architecture using its preprocessing techniques not only takes into account the enormous variations observed in SMS data but also makes it efficient for its on-device (mobile phone) functionalities in terms of inference timing and size.
Switchable Precision Neural Networks
Venue: arXiv cs.CV 2020
Year: 2020

Instantaneous and on demand accuracy-efficiency trade-off has been recently explored in the context of neural networks slimming. In this paper, we propose a flexible quantization strategy, termed Switchable Precision neural Networks (SP-Nets), to train a shared network capable of operating at multiple quantization levels. At runtime, the network can adjust its precision on the fly according to instant memory, latency, power consumption and accuracy demands. For example, by constraining the network weights to 1-bit with switchable precision activations, our shared network spans from BinaryConnect to Binarized Neural Network, allowing to perform dot-products using only summations or bit operations. In addition, a self-distillation scheme is proposed to increase the performance of the quantized switches. We tested our approach with three different quantizers and demonstrate the performance of SP-Nets against independently trained quantized models in classification accuracy for Tiny ImageNet and ImageNet datasets using ResNet-18 and MobileNet architectures.
Causally Correct Partial Models for Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

In reinforcement learning, we can learn a model of future observations and rewards, and use it to plan the agent's next actions. However, jointly modeling future observations can be computationally expensive or even intractable if the observations are high-dimensional (e.g. images). For this reason, previous works have considered partial models, which model only part of the observation. In this paper, we show that partial models can be causally incorrect: they are confounded by the observations they don't model, and can therefore lead to incorrect planning. To address this, we introduce a general family of partial models that are provably causally correct, yet remain fast because they do not need to fully model future observations.
Input Dropout for Spatially Aligned Modalities
Venue: arXiv cs.CV 2020
Year: 2020

Computer vision datasets containing multiple modalities such as color, depth, and thermal properties are now commonly accessible and useful for solving a wide array of challenging tasks. However, deploying multi-sensor heads is not possible in many scenarios. As such many practical solutions tend to be based on simpler sensors, mostly for cost, simplicity and robustness considerations. In this work, we propose a training methodology to take advantage of these additional modalities available in datasets, even if they are not available at test time. By assuming that the modalities have a strong spatial correlation, we propose Input Dropout, a simple technique that consists in stochastic hiding of one or many input modalities at training time, while using only the canonical (e.g. RGB) modalities at test time. We demonstrate that Input Dropout trivially combines with existing deep convolutional architectures, and improves their performance on a wide range of computer vision tasks such as dehazing, 6-DOF object tracking, pedestrian detection and object classification.
Security Certification in Payment Card Industry: Testbeds, Measurements, and Recommendations
Venue: arXiv cs.CR 2020
Year: 2020

The massive payment card industry (PCI) involves various entities such as merchants, issuer banks, acquirer banks, and card brands. Ensuring security for all entities that process payment card information is a challenging task. The PCI Security Standards Council requires all entities to be compliant with the PCI Data Security Standard (DSS), which specifies a series of security requirements. However, little is known regarding how well PCI DSS is enforced in practice. In this paper, we take a measurement approach to systematically evaluate the PCI DSS certification process for e-commerce websites. We develop an e-commerce web application testbed, BuggyCart, which can flexibly add or remove 35 PCI DSS related vulnerabilities. Then we use the testbed to examine the capability and limitations of PCI scanners and the rigor of the certification process. We find that there is an alarming gap between the security standard and its real-world enforcement. None of the 6 PCI scanners we tested are fully compliant with the PCI scanning guidelines, issuing certificates to merchants that still have major vulnerabilities. To further examine the compliance status of real-world e-commerce websites, we build a new lightweight scanning tool named PciCheckerLite and scan 1,203 e-commerce websites across various business sectors. The results confirm that 86% of the websites have at least one PCI DSS violation that should have disqualified them as non-compliant. Our in-depth accuracy analysis also shows that PciCheckerLite's output is more precise than w3af. We reached out to the PCI Security Council to share our research results to improve the enforcement in practice.
Differentiable Forward and Backward Fixed-Point Iteration Layers
Venue: arXiv cs.LG 2020
Year: 2020

Recently, several studies proposed methods to utilize some classes of optimization problems in designing deep neural networks to encode constraints that conventional layers cannot capture. However, these methods are still in their infancy and require special treatments, such as analyzing the KKT condition, for deriving the backpropagation formula. In this paper, we propose a new layer formulation called the fixed-point iteration (FPI) layer that facilitates the use of more complicated operations in deep networks. The backward FPI layer is also proposed for backpropagation, which is motivated by the recurrent back-propagation (RBP) algorithm. But in contrast to RBP, the backward FPI layer yields the gradient by a small network module without an explicit calculation of the Jacobian. In actual applications, both the forward and backward FPI layers can be treated as nodes in the computational graphs. All components in the proposed method are implemented at a high level of abstraction, which allows efficient higher-order differentiations on the nodes. In addition, we present two practical methods of the FPI layer, FPI_NN and FPI_GD, where the update operations of FPI are a small neural network module and a single gradient descent step based on a learnable cost function, respectively. FPI\_NN is intuitive, simple, and fast to train, while FPI_GD can be used for efficient training of energy networks that have been recently studied. While RBP and its related studies have not been applied to practical examples, our experiments show the FPI layer can be successfully applied to real-world problems such as image denoising, optical flow, and multi-label classification.
Multilayer Routing and Resource Assignment in Spatial Channel Networks (SCNs): Oriented Toward the Massive SDM Era
Venue: arXiv cs.NI 2020
Year: 2020

In the past few decades, optical transport networks (OTNs) have undergone significant evolution, from the earliest wavelength-division multiplexing (WDM) OTNs to elastic optical networks (EONs) and later to space-division multiplexing (SDM) OTNs, to address the continuous growth of Internet traffic. By 2024, Pbps-level OTNs are expected, far exceeding the capacity limit of single-mode fibers. The massive SDM era is on the horizon. In this context, newly designed OTNs called spatial channel networks (SCNs), which achieve high cost efficiency by means of practical hierarchical optical cross-connects, have recently been proposed. However, the evolution of OTNs will simultaneously present challenges related to resource allocation in networking. For instance, with the evolution from WDM-OTNs to EONs, the resource allocation problem was transformed from the routing and wavelength assignment (RWA) problem to the routing and spectrum assignment (RSA) problem due to the additionally introduced constraint of spectrum contiguity. Similarly, specially designed algorithms are also expected to be essential for addressing the resource allocation problem in SCNs. In this paper, we define this new problem as the routing, spatial channel, and spectrum assignment (RSCSA) problem. We propose an integer linear programming (ILP) model and a heuristic algorithm to solve the RSCSA problem. We examine the performance of the proposed approaches via simulation experiments. The results show that both proposed approaches are effective in finding the optimal solutions or solutions close to the lower bounds. To the best of our knowledge, this is the first work to focus on the problem of resource allocation in SCNs.
Meta-learning framework with applications to zero-shot time-series forecasting
Venue: arXiv cs.LG 2020
Year: 2020

Can meta-learning discover generic ways of processing time series (TS) from a diverse dataset so as to greatly improve generalization on new TS coming from different datasets? This work provides positive evidence to this using a broad meta-learning framework which we show subsumes many existing meta-learning algorithms. Our theoretical analysis suggests that residual connections act as a meta-learning adaptation mechanism, generating a subset of task-specific parameters based on a given TS input, thus gradually expanding the expressive power of the architecture on-the-fly. The same mechanism is shown via linearization analysis to have the interpretation of a sequential update of the final linear layer. Our empirical results on a wide range of data emphasize the importance of the identified meta-learning mechanisms for successful zero-shot univariate forecasting, suggesting that it is viable to train a neural network on a source TS dataset and deploy it on a different target TS dataset without retraining, resulting in performance that is at least as good as that of state-of-practice univariate forecasting models.
Session-Based Recommender Systems for Action Selection in GUI Test Generation
Venue: arXiv cs.SE 2020
Year: 2020

Test generation at the graphical user interface (GUI) level has proven to be an effective method to reveal faults. When doing so, a test generator has to repeatably decide what action to execute given the current state of the system under test (SUT). This problem of action selection usually involves random choice, which is often referred to as monkey testing. Some approaches leverage other techniques to improve the overall effectiveness, but only a few try to create human-like actions---or even entire action sequences. We have built a novel session-based recommender system that can guide test generation. This allows us to mimic past user behavior, reaching states that require complex interactions. We present preliminary results from an empirical study, where we use GitHub as the SUT. These results show that recommender systems appear to be well-suited for action selection, and that the approach can significantly contribute to the improvement of GUI-based test generation.