OpenRaiser/Intern-Atlas huggingface dataset:
Collaborative Top Distribution Identifications with Limited Interaction
Venue: arXiv cs.DS 2020
Year: 2020

We consider the following problem in this paper: given a set of $n$ distributions, find the top-$m$ ones with the largest means. This problem is also called {\em top-$m$ arm identifications} in the literature of reinforcement learning, and has numerous applications. We study the problem in the collaborative learning model where we have multiple agents who can draw samples from the $n$ distributions in parallel. Our goal is to characterize the tradeoffs between the running time of learning process and the number of rounds of interaction between agents, which is very expensive in various scenarios. We give optimal time-round tradeoffs, as well as demonstrate complexity separations between top-$1$ arm identification and top-$m$ arm identifications for general $m$ and between fixed-time and fixed-confidence variants. As a byproduct, we also give an algorithm for selecting the distribution with the $m$-th largest mean in the collaborative learning model.
Causality-aware counterfactual confounding adjustment for feature representations learned by deep models
Venue: arXiv cs.LG 2020
Year: 2020

Causal modeling has been recognized as a potential solution to many challenging problems in machine learning (ML). Here, we describe how a recently proposed counterfactual approach developed to deconfound linear structural causal models can still be used to deconfound the feature representations learned by deep neural network (DNN) models. The key insight is that by training an accurate DNN using softmax activation at the classification layer, and then adopting the representation learned by the last layer prior to the output layer as our features, we have that, by construction, the learned features will fit well a (multi-class) logistic regression model, and will be linearly associated with the labels. As a consequence, deconfounding approaches based on simple linear models can be used to deconfound the feature representations learned by DNNs. We validate the proposed methodology using colored versions of the MNIST dataset. Our results illustrate how the approach can effectively combat confounding and improve model stability in the context of dataset shifts generated by selection biases.
Attention Routing: track-assignment detailed routing using attention-based reinforcement learning
Venue: arXiv cs.LG 2020
Year: 2020

In the physical design of integrated circuits, global and detailed routing are critical stages involving the determination of the interconnected paths of each net on a circuit while satisfying the design constraints. Existing actual routers as well as routability predictors either have to resort to expensive approaches that lead to high computational times, or use heuristics that do not generalize well. Even though new, learning-based routing methods have been proposed to address this need, requirements on labelled data and difficulties in addressing complex design rule constraints have limited their adoption in advanced technology node physical design problems. In this work, we propose a new router: attention router, which is the first attempt to solve the track-assignment detailed routing problem using reinforcement learning. Complex design rule constraints are encoded into the routing algorithm and an attention-model-based REINFORCE algorithm is applied to solve the most critical step in routing: sequencing device pairs to be routed. The attention router and its baseline genetic router are applied to solve different commercial advanced technologies analog circuits problem sets. The attention router demonstrates generalization ability to unseen problems and is also able to achieve more than 100 times acceleration over the genetic router without significantly compromising the routing solution quality. We also discover a similarity between the attention router and the baseline genetic router in terms of positive correlations in cost and routing patterns, which demonstrate the attention router's ability to be utilized not only as a detailed router but also as a predictor for routability and congestion.
Connecting Robust Shuffle Privacy and Pan-Privacy
Venue: arXiv cs.CR 2020
Year: 2020

In the \emph{shuffle model} of differential privacy, data-holding users send randomized messages to a secure shuffler, the shuffler permutes the messages, and the resulting collection of messages must be differentially private with regard to user data. In the \emph{pan-private} model, an algorithm processes a stream of data while maintaining an internal state that is differentially private with regard to the stream data. We give evidence connecting these two apparently different models. Our results focus on \emph{robustly} shuffle private protocols, whose privacy guarantees are not greatly affected by malicious users. First, we give robustly shuffle private protocols and upper bounds for counting distinct elements and uniformity testing. Second, we use pan-private lower bounds to prove robustly shuffle private lower bounds for both problems. Focusing on the dependence on the domain size $k$, we find that robust approximate shuffle privacy and approximate pan-privacy have additive error $Θ(\sqrt{k})$ for counting distinct elements. For uniformity testing, we give a robust approximate shuffle private protocol with sample complexity $\tilde O(k^{2/3})$ and show that an $Ω(k^{2/3})$ dependence is necessary for any robust pure shuffle private tester. Finally, we show that this connection is useful in both directions: we give a pan-private adaptation of recent work on shuffle private histograms and use it to recover further separations between pan-privacy and interactive local privacy.
Experimental Evaluation of Asynchronous Binary Byzantine Consensus Algorithms with $t < n/3$ and $O(n^2)$ Messages and $O(1)$ Round Expected Termination
Venue: arXiv cs.DC 2020
Year: 2020

This work performs an experimental evaluation of four asynchronous binary Byzantine consensus algorithms [11,16,18] in various configurations. In addition to being asynchronous these algorithms run in rounds, tolerate up to one third of faulty nodes, use $O(n^2)$ messages, and use randomized common coins to terminate in an expected constant number of rounds. Each of the four algorithms have different requirements for the random coin, for the number of messages needed per round, whether or not cryptographic signatures are needed, among other details. Two different non-interactive threshold common coin implementations are tested, one using threshold signatures, and one based on the Diffe-Hellman problem using validity proofs [11]. Experiments are run in single data center and geo-distributed configurations with between $4$ and $48$ nodes. Various simple faulty behaviors are tested. As no algorithm performs best in all experimental conditions, two new algorithms introduced that simply combine properties of the existing algorithms with the goal of having good performance in the majority of experimental settings.
Why do People Share Misinformation during the COVID-19 Pandemic?
Venue: arXiv cs.CY 2020
Year: 2020

The World Health Organization have emphasised that misinformation - spreading rapidly through social media - poses a serious threat to the COVID-19 response. Drawing from theories of health perception and cognitive load, we develop and test a research model hypothesizing why people share unverified COVID-19 information through social media. Our findings suggest a person's trust in online information and perceived information overload are strong predictors of unverified information sharing. Furthermore, these factors, along with a person's perceived COVID-19 severity and vulnerability influence cyberchondria. Females were significantly more likely to suffer from cyberchondria, however, males were more likely to share news without fact checking their source. Our findings suggest that to mitigate the spread of COVID-19 misinformation and cyberchondria, measures should be taken to enhance a healthy skepticism of health news while simultaneously guarding against information overload.
Flattening the Curve: Insights From Queueing Theory
Venue: arXiv cs.PF 2020
Year: 2020

The worldwide outbreak of the coronavirus was first identified in 2019 in Wuhan, China. Since then, the disease has spread worldwide. As it currently spreading in the United States, policy makers, public health officials and citizens are racing to understand the impact of this virus on the United States healthcare system. They fear that the rapid influx of patients will overwhelm the healthcare system leading to unnecessary fatalities. Most countries and states in America have introduced mitigation strategies, such as social distancing, to decrease the rate of newly infected people, i.e. flattening the curve.In this paper, we analyze the time evolution of the number of people hospitalized due to the coronavirus using the methods of queueing theory. Given that the rate of new infections varies over time as the pandemic evolves, we model the number of coronavirus patients as a dynamical system based on the theory of infinite server queues with non-stationary Poisson arrival rates. With this model we are able to quantify how flattening the curve affects the peak demand for hospital resources. This allows us to characterize how aggressively society must flatten the curve in order to avoid overwhelming the capacity of healthcare system. We also demonstrate how flattening the curve impacts the elapsed time between the peak rate of hospitalizations and the time of the peak demand for the hospital resources. Finally, we present empirical evidence from China, South Korea, Italy and the United States that supports the insights from the model.
Local Clustering with Mean Teacher for Semi-supervised Learning
Venue: arXiv cs.LG 2020
Year: 2020

The Mean Teacher (MT) model of Tarvainen and Valpola has shown favorable performance on several semi-supervised benchmark datasets. MT maintains a teacher model's weights as the exponential moving average of a student model's weights and minimizes the divergence between their probability predictions under diverse perturbations of the inputs. However, MT is known to suffer from confirmation bias, that is, reinforcing incorrect teacher model predictions. In this work, we propose a simple yet effective method called Local Clustering (LC) to mitigate the effect of confirmation bias. In MT, each data point is considered independent of other points during training; however, data points are likely to be close to each other in feature space if they share similar features. Motivated by this, we cluster data points locally by minimizing the pairwise distance between neighboring data points in feature space. Combined with a standard classification cross-entropy objective on labeled data points, the misclassified unlabeled data points are pulled towards high-density regions of their correct class with the help of their neighbors, thus improving model performance. We demonstrate on semi-supervised benchmark datasets SVHN and CIFAR-10 that adding our LC loss to MT yields significant improvements compared to MT and performance comparable to the state of the art in semi-supervised learning.
Towards Automated Augmentation and Instrumentation of Legacy Cryptographic Executables: Extended Version
Venue: arXiv cs.CR 2020
Year: 2020

Implementation flaws in cryptographic libraries, design flaws in underlying cryptographic primitives, and weaknesses in protocols using both, can all lead to exploitable vulnerabilities in software. Manually fixing such issues is challenging and resource consuming, especially when maintaining legacy software that contains broken or outdated cryptography, and for which source code may not be available. While there is existing work on identifying cryptographic primitives (often in the context of malware analysis), none of this prior work has focused on replacing such primitives with stronger (or more secure ones) after they have been identified. This paper explores feasibility of designing and implementing a toolchain for Augmentation and Legacy-software Instrumentation of Cryptographic Executables (ALICE). The key features of ALICE are: (i) automatically detecting and extracting implementations of weak or broken cryptographic primitives from binaries without requiring source code or debugging symbols, (ii) identifying the context and scope in which such primitives are used, and performing program analysis to determine the effects of replacing such implementations with more secure ones, and (iii) replacing implementations of weak primitives with those of stronger or more secure ones. We demonstrate practical feasibility of our approach on cryptographic hash functions with several popular cryptographic libraries and real-world programs of various levels of complexity. Our experimental results show that ALICE can locate and replace insecure hash functions, even in large binaries (we tested ones of size up to 1.5MB), while preserving existing functionality of the original binaries, and while incurring minimal execution-time overhead in the rewritten binaries. We also open source ALICE's code at https://github.com/SRI-CSL/ALICE.
On the Performance of Hybrid Search Strategies for Systematic Literature Reviews in Software Engineering
Venue: arXiv cs.DL 2020
Year: 2020

Context: When conducting a Systematic Literature Review (SLR), researchers usually face the challenge of designing a search strategy that appropriately balances result quality and review effort. Using digital library (or database) searches or snowballing alone may not be enough to achieve high-quality results. On the other hand, using both digital library searches and snowballing together may increase the overall review effort. Objective: The goal of this research is to propose and evaluate hybrid search strategies that selectively combine database searches with snowballing. Method: We propose four hybrid search strategies combining database searches in digital libraries with iterative, parallel, or sequential backward and forward snowballing. We simulated the strategies over three existing SLRs in SE that adopted both database searches and snowballing. We compared the outcome of digital library searches, snowballing, and hybrid strategies using precision, recall, and F-measure to investigate the performance of each strategy. Results: Our results show that, for the analyzed SLRs, combining database searches from the Scopus digital library with parallel or sequential snowballing achieved the most appropriate balance of precision and recall. Conclusion: We put forward that, depending on the goals of the SLR and the available resources, using a hybrid search strategy involving a representative digital library and parallel or sequential snowballing tends to represent an appropriate alternative to be used when searching for evidence in SLRs.
Take a NAP: Non-Autoregressive Prediction for Pedestrian Trajectories
Venue: arXiv cs.CV 2020
Year: 2020

Pedestrian trajectory prediction is a challenging task as there are three properties of human movement behaviors which need to be addressed, namely, the social influence from other pedestrians, the scene constraints, and the multimodal (multiroute) nature of predictions. Although existing methods have explored these key properties, the prediction process of these methods is autoregressive. This means they can only predict future locations sequentially. In this paper, we present NAP, a non-autoregressive method for trajectory prediction. Our method comprises specifically designed feature encoders and a latent variable generator to handle the three properties above. It also has a time-agnostic context generator and a time-specific context generator for non-autoregressive prediction. Through extensive experiments that compare NAP against several recent methods, we show that NAP has state-of-the-art trajectory prediction performance.
Channel Estimation and Power Scaling Law of Large Reflecting Surface with Non-Ideal Hardware
Venue: arXiv cs.IT 2020
Year: 2020

Large reflecting surface (LRS) has emerged as a new solution to improve the energy and spectrum efficiency of wireless communication system. Most existing studies were conducted with an assumption of ideal hardware, and the impact of hardware impairments receives little attention. However, the non-negligible hardware impairments should be taken into consideration when we evaluate the system performance. In this paper, we consider an LRS assisted communication system with hardware impairments, and focus on the channel estimation study and the power scaling law analysis. First, with linear minimum mean square error estimation, we theoretically characterize the relationship between channel estimation performance and impairment level, number of reflecting elements, and pilot power. After that, we analyze the power scaling law and reveal that if the base station (BS) has perfect channel state information, the transmit power of user can be made inversely proportional to the number of BS antennas and the square of the number of reflecting elements with no reduction in performance; If the BS has imperfectly estimated channel state information, to achieve the same performance, the transmit power of user can be made inversely proportional to the square-root of the number of BS antennas and the square of the number of reflecting elements.
Decoupling Video and Human Motion: Towards Practical Event Detection in Athlete Recordings
Venue: arXiv cs.CV 2020
Year: 2020

In this paper we address the problem of motion event detection in athlete recordings from individual sports. In contrast to recent end-to-end approaches, we propose to use 2D human pose sequences as an intermediate representation that decouples human motion from the raw video information. Combined with domain-adapted athlete tracking, we describe two approaches to event detection on pose sequences and evaluate them in complementary domains: swimming and athletics. For swimming, we show how robust decision rules on pose statistics can detect different motion events during swim starts, with a F1 score of over 91% despite limited data. For athletics, we use a convolutional sequence model to infer stride-related events in long and triple jump recordings, leading to highly accurate detections with 96% in F1 score at only +/- 5ms temporal deviation. Our approach is not limited to these domains and shows the flexibility of pose-based motion event detection.
PhishOut: Effective Phishing Detection Using Selected Features
Venue: arXiv cs.CR 2020
Year: 2020

Phishing emails are the first step for many of today's attacks. They come with a simple hyperlink, request for action or a full replica of an existing service or website. The goal is generally to trick the user to voluntarily give away his sensitive information such as login credentials. Many approaches and applications have been proposed and developed to catch and filter phishing emails. However, the problem still lacks a complete and comprehensive solution. In this paper, we apply knowledge discovery principles from data cleansing, integration, selection, aggregation, data mining to knowledge extraction. We study the feature effectiveness based on Information Gain and contribute two new features to the literature. We compare six machine-learning approaches to detect phishing based on a small number of carefully chosen features. We calculate false positives, false negatives, mean absolute error, recall, precision and F-measure and achieve very low false positive and negative rates. Na{\"ı}ve Bayes has the least true positives rate and overall Neural Networks holds the most promise for accurate phishing detection with accuracy of 99.4\%.
A CNN Framenwork Based on Line Annotations for Detecting Nematodes in Microscopic Images
Venue: arXiv cs.CV 2020
Year: 2020

Plant parasitic nematodes cause damage to crop plants on a global scale. Robust detection on image data is a prerequisite for monitoring such nematodes, as well as for many biological studies involving the nematode C. elegans, a common model organism. Here, we propose a framework for detecting worm-shaped objects in microscopic images that is based on convolutional neural networks (CNNs). We annotate nematodes with curved lines along the body, which is more suitable for worm-shaped objects than bounding boxes. The trained model predicts worm skeletons and body endpoints. The endpoints serve to untangle the skeletons from which segmentation masks are reconstructed by estimating the body width at each location along the skeleton. With light-weight backbone networks, we achieve 75.85 % precision, 73.02 % recall on a potato cyst nematode data set and 84.20 % precision, 85.63 % recall on a public C. elegans data set.
A Decomposition-based Large-scale Multi-modal Multi-objective Optimization Algorithm
Venue: arXiv cs.NE 2020
Year: 2020

A multi-modal multi-objective optimization problem is a special kind of multi-objective optimization problem with multiple Pareto subsets. In this paper, we propose an efficient multi-modal multi-objective optimization algorithm based on the widely used MOEA/D algorithm. In our proposed algorithm, each weight vector has its own sub-population. With a clearing mechanism and a greedy removal strategy, our proposed algorithm can effectively preserve equivalent Pareto optimal solutions (i.e., different Pareto optimal solutions with same objective values). Experimental results show that our proposed algorithm can effectively preserve the diversity of solutions in the decision space when handling large-scale multi-modal multi-objective optimization problems.
SIBRE: Self Improvement Based REwards for Adaptive Feedback in Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

We propose a generic reward shaping approach for improving the rate of convergence in reinforcement learning (RL), called Self Improvement Based REwards, or SIBRE. The approach is designed for use in conjunction with any existing RL algorithm, and consists of rewarding improvement over the agent's own past performance. We prove that SIBRE converges in expectation under the same conditions as the original RL algorithm. The reshaped rewards help discriminate between policies when the original rewards are weakly discriminated or sparse. Experiments on several well-known benchmark environments with different RL algorithms show that SIBRE converges to the optimal policy faster and more stably. We also perform sensitivity analysis with respect to hyper-parameters, in comparison with baseline RL algorithms.
Large Population Sizes and Crossover Help in Dynamic Environments
Venue: arXiv cs.NE 2020
Year: 2020

Dynamic linear functions on the hypercube are functions which assign to each bit a positive weight, but the weights change over time. Throughout optimization, these functions maintain the same global optimum, and never have defecting local optima. Nevertheless, it was recently shown [Lengler, Schaller, FOCI 2019] that the $(1+1)$-Evolutionary Algorithm needs exponential time to find or approximate the optimum for some algorithm configurations. In this paper, we study the effect of larger population sizes for Dynamic BinVal, the extremal form of dynamic linear functions. We find that moderately increased population sizes extend the range of efficient algorithm configurations, and that crossover boosts this positive effect substantially. Remarkably, similar to the static setting of monotone functions in [Lengler, Zou, FOGA 2019], the hardest region of optimization for $(μ+1)$-EA is not close the optimum, but far away from it. In contrast, for the $(μ+1)$-GA, the region around the optimum is the hardest region in all studied cases.