OpenRaiser/Intern-Atlas huggingface dataset:
Arms Race in Adversarial Malware Detection: A Survey
Venue: arXiv cs.CR 2021
Year: 2021

Malicious software (malware) is a major cyber threat that has to be tackled with Machine Learning (ML) techniques because millions of new malware examples are injected into cyberspace on a daily basis. However, ML is vulnerable to attacks known as adversarial examples. In this paper, we survey and systematize the field of Adversarial Malware Detection (AMD) through the lens of a unified conceptual framework of assumptions, attacks, defenses, and security properties. This not only leads us to map attacks and defenses to partial order structures, but also allows us to clearly describe the attack-defense arms race in the AMD context. We draw a number of insights, including: knowing the defender's feature set is critical to the success of transfer attacks; the effectiveness of practical evasion attacks largely depends on the attacker's freedom in conducting manipulations in the problem space; knowing the attacker's manipulation set is critical to the defender's success; the effectiveness of adversarial training depends on the defender's capability in identifying the most powerful attack. We also discuss a number of future research directions.
Walrasian Equilibria in Markets with Small Demands
Venue: arXiv cs.GT 2021
Year: 2021

We study the complexity of finding a Walrasian equilibrium in markets where the agents have $k$-demand valuations. These valuations are an extension of unit-demand valuations where a bundle's value is the maximum of its $k$-subsets' values. For unit-demand agents, where the existence of a Walrasian equilibrium is guaranteed, we show that the problem is in quasi-NC. For $k=2$, we show that it is NP-hard to decide if a Walrasian equilibrium exists even if the valuations are fractionally subadditive (XOS), while for $k=3$ the hardness carries over to budget-additive valuations. In addition, we give a polynomial-time algorithm for markets with 2-demand single-minded valuations, or unit-demand valuations.
On Optimal Partitioning For Sparse Matrices In Variable Block Row Format
Venue: arXiv cs.DS 2021
Year: 2021

The Variable Block Row (VBR) format is an influential blocked sparse matrix format designed for matrices with shared sparsity structure between adjacent rows and columns. VBR groups adjacent rows and columns, storing the resulting blocks that contain nonzeros in a dense format. This reduces the memory footprint and enables optimizations such as register blocking and instruction-level parallelism. Existing approaches use heuristics to determine which rows and columns should be grouped together. We show that finding the optimal grouping of rows and columns for VBR is NP-hard under several reasonable cost models. In light of this finding, we propose a 1-dimensional variant of VBR, called 1D-VBR, which achieves better performance than VBR by only grouping rows. We describe detailed cost models for runtime and memory consumption. Then, we describe a linear time dynamic programming solution for optimally grouping the rows for 1D-VBR format. We extend our algorithm to produce a heuristic VBR partitioner which alternates between optimally partitioning rows and columns, assuming the columns or rows to be fixed, respectively. Our alternating heuristic produces VBR matrices with the smallest memory footprint of any partitioner we tested.
Is deeper better? It depends on locality of relevant features
Venue: arXiv cs.LG 2021
Year: 2021

It has been recognized that a heavily overparameterized artificial neural network exhibits surprisingly good generalization performance in various machine-learning tasks. Recent theoretical studies have made attempts to unveil the mystery of the overparameterization. In most of those previous works, the overparameterization is achieved by increasing the width of the network, while the effect of increasing the depth has remained less well understood. In this work, we investigate the effect of increasing the depth within an overparameterized regime. To gain an insight into the advantage of depth, we introduce local and global labels as abstract but simple classification rules. It turns out that the locality of the relevant feature for a given classification rule plays a key role; our experimental results suggest that deeper is better for local labels, whereas shallower is better for global labels. We also compare the results of finite networks with those of the neural tangent kernel (NTK), which is equivalent to an infinitely wide network with a proper initialization and an infinitesimal learning rate. It is shown that the NTK does not correctly capture the depth dependence of the generalization performance, which indicates the importance of the feature learning rather than the lazy learning.
CRUDE: Calibrating Regression Uncertainty Distributions Empirically
Venue: arXiv cs.LG 2021
Year: 2021

Calibrated uncertainty estimates in machine learning are crucial to many fields such as autonomous vehicles, medicine, and weather and climate forecasting. While there is extensive literature on uncertainty calibration for classification, the classification findings do not always translate to regression. As a result, modern models for predicting uncertainty in regression settings typically produce uncalibrated and overconfident estimates. To address these gaps, we present a calibration method for regression settings that does not assume a particular uncertainty distribution over the error: Calibrating Regression Uncertainty Distributions Empirically (CRUDE). CRUDE makes the weaker assumption that error distributions have a constant arbitrary shape across the output space, shifted by predicted mean and scaled by predicted standard deviation. We detail a theoretical connection between CRUDE and conformal inference. Across an extensive set of regression tasks, CRUDE demonstrates consistently sharper, better calibrated, and more accurate uncertainty estimates than state-of-the-art techniques.
Contrastive Learning for Debiased Candidate Generation in Large-Scale Recommender Systems
Venue: arXiv cs.IR 2021
Year: 2021

Deep candidate generation (DCG) that narrows down the collection of relevant items from billions to hundreds via representation learning has become prevalent in industrial recommender systems. Standard approaches approximate maximum likelihood estimation (MLE) through sampling for better scalability and address the problem of DCG in a way similar to language modeling. However, live recommender systems face severe exposure bias and have a vocabulary several orders of magnitude larger than that of natural language, implying that MLE will preserve and even exacerbate the exposure bias in the long run in order to faithfully fit the observed samples. In this paper, we theoretically prove that a popular choice of contrastive loss is equivalent to reducing the exposure bias via inverse propensity weighting, which provides a new perspective for understanding the effectiveness of contrastive learning. Based on the theoretical discovery, we design CLRec, a contrastive learning method to improve DCG in terms of fairness, effectiveness and efficiency in recommender systems with extremely large candidate size. We further improve upon CLRec and propose Multi-CLRec, for accurate multi-intention aware bias reduction. Our methods have been successfully deployed in Taobao, where at least four-month online A/B tests and offline analyses demonstrate its substantial improvements, including a dramatic reduction in the Matthew effect.
Comparing BERT against traditional machine learning text classification
Venue: arXiv cs.CL 2021
Year: 2021

The BERT model has arisen as a popular state-of-the-art machine learning model in the recent years that is able to cope with multiple NLP tasks such as supervised text classification without human supervision. Its flexibility to cope with any type of corpus delivering great results has make this approach very popular not only in academia but also in the industry. Although, there are lots of different approaches that have been used throughout the years with success. In this work, we first present BERT and include a little review on classical NLP approaches. Then, we empirically test with a suite of experiments dealing different scenarios the behaviour of BERT against the traditional TF-IDF vocabulary fed to machine learning algorithms. Our purpose of this work is to add empirical evidence to support or refuse the use of BERT as a default on NLP tasks. Experiments show the superiority of BERT and its independence of features of the NLP problem such as the language of the text adding empirical evidence to use BERT as a default technique to be used in NLP problems.
Predict-then-Decide: A Predictive Approach for Wait or Answer Task in Dialogue Systems
Venue: arXiv cs.CL 2021
Year: 2021

Different people have different habits of describing their intents in conversations. Some people tend to deliberate their intents in several successive utterances, i.e., they use several consistent messages for readability instead of a long sentence to express their question. This creates a predicament faced by the application of dialogue systems, especially in real-world industry scenarios, in which the dialogue system is unsure whether it should answer the query of user immediately or wait for further supplementary input. Motivated by such an interesting predicament, we define a novel Wait-or-Answer task for dialogue systems. We shed light on a new research topic about how the dialogue system can be more intelligent to behave in this Wait-or-Answer quandary. Further, we propose a predictive approach named Predict-then-Decide (PTD) to tackle this Wait-or-Answer task. More specifically, we take advantage of a decision model to help the dialogue system decide whether to wait or answer. The decision of decision model is made with the assistance of two ancillary prediction models: a user prediction and an agent prediction. The user prediction model tries to predict what the user would supplement and uses its prediction to persuade the decision model that the user has some information to add, so the dialogue system should wait. The agent prediction model tries to predict the answer of the dialogue system and convince the decision model that it is a superior choice to answer the query of user immediately since the input of user has come to an end. We conduct our experiments on two real-life scenarios and three public datasets. Experimental results on five datasets show our proposed PTD approach significantly outperforms the existing models in solving this Wait-or-Answer problem.
How does Working from Home Affect Developer Productivity? -- A Case Study of Baidu During COVID-19 Pandemic
Venue: arXiv cs.SE 2021
Year: 2021

Nowadays, working from home (WFH) has become a popular work arrangement due to its many potential benefits for both companies and employees (e.g., increasing job satisfaction and retention of employees). Many previous studies have investigated the impact of working from home on the productivity of employees. However, most of these studies usually use a qualitative analysis method such as survey and interview, and the studied participants do not work from home for a long continuing time. Due to the outbreak of coronavirus disease 2019 (COVID-19), a large number of companies asked their employees to work from home, which provides us an opportunity to investigate whether working from home affects their productivity. In this study, to investigate the difference of developer productivity between working from home and working onsite, we conduct a quantitative analysis based on a dataset of developers' daily activities from Baidu Inc, one of the largest IT companies in China. In total, we collected approximately four thousand records of 139 developers' activities of 138 working days. Out of these records, 1,103 records are submitted when developers work from home due to COVID-19 pandemic. We find that WFH has both positive and negative impacts on developer productivity in terms of different metrics, e.g., the number of builds/commits/code reviews. We also notice that working from home has different impacts on projects with different characteristics including programming language, project type/age/size. For example, working from home has a negative impact on developer productivity for large projects. Additionally, we find that productivity varies for different developers. Based on these findings, we get some feedbacks from developers of Baidu and understand some reasons why WFH has different impacts on developer productivity.
Tensor decomposition to Compress Convolutional Layers in Deep Learning
Venue: arXiv cs.LG 2021
Year: 2021

Feature extraction for tensor data serves as an important step in many tasks such as anomaly detection, process monitoring, image classification, and quality control. Although many methods have been proposed for tensor feature extraction, there are still two challenges that need to be addressed: 1) how to reduce the computation cost for high dimensional and large volume tensor data; 2) how to interpret the output features and evaluate their significance. {The most recent methods in deep learning, such as Convolutional Neural Network (CNN), have shown outstanding performance in analyzing tensor data, but their wide adoption is still hindered by model complexity and lack of interpretability. To fill this research gap, we propose to use CP-decomposition to approximately compress the convolutional layer (CPAC-Conv layer) in deep learning. The contributions of our work could be summarized into three aspects: (1) we adapt CP-decomposition to compress convolutional kernels and derive the expressions of both forward and backward propagations for our proposed CPAC-Conv layer; (2) compared with the original convolutional layer, the proposed CPAC-Conv layer can reduce the number of parameters without decaying prediction performance. It can combine with other layers to build novel deep Neural Networks; (3) the value of decomposed kernels indicates the significance of the corresponding feature map, which provides us with insights to guide feature selection.
Age of Information in an Overtake-Free Network of Quasi-Reversible Queues
Venue: arXiv cs.PF 2021
Year: 2021

We show how to calculate the Age of Information in an overtake-free network of quasi-reversible queues, with exponential exogenous interarrivals of multiple classes of update packets and exponential service times at all nodes. Results are provided for any number of M/M/1 First-Come-First-Served (FCFS) queues in tandem, and for a network with two classes of update packets, entering through different queues in the network and exiting through the same queue. The main takeaway is that in a network with different classes of update packets, individual classes roughly preserve the ages they would achieve if they were alone in the network, except when shared queues become saturated, in which case the ages increase considerably.
Fundamental Limits of Stochastic Shared Caches Networks
Venue: arXiv cs.IT 2021
Year: 2021

The work establishes the exact performance limits of stochastic coded caching when users share a bounded number of cache states, and when the association between users and caches, is random. Under the premise that more balanced user-to-cache associations perform better than unbalanced ones, our work provides a statistical analysis of the average performance of such networks, identifying in closed form, the exact optimal average delivery time. To insightfully capture this delay, we derive easy to compute closed-form analytical bounds that prove tight in the limit of a large number $Λ$ of cache states. In the scenario where delivery involves $K$ users, we conclude that the multiplicative performance deterioration due to randomness -- as compared to the well-known deterministic uniform case -- can be unbounded and can scale as $Θ\left( \frac{\log Λ}{\log \log Λ} \right)$ at $K=Θ\left(Λ\right)$, and that this scaling vanishes when $K=Ω\left(Λ\log Λ\right)$. To alleviate this adverse effect of cache-load imbalance, we consider various load balancing methods, and show that employing proximity-bounded load balancing with an ability to choose from $h$ neighboring caches, the aforementioned scaling reduces to $Θ\left(\frac{\log(Λ/ h)}{ \log \log(Λ/ h)} \right)$, while when the proximity constraint is removed, the scaling is of a much slower order $Θ\left( \log \log Λ\right)$. The above analysis is extensively validated numerically.
CoDiNet: Path Distribution Modeling with Consistency and Diversity for Dynamic Routing
Venue: arXiv cs.CV 2021
Year: 2021

Dynamic routing networks, aimed at finding the best routing paths in the networks, have achieved significant improvements to neural networks in terms of accuracy and efficiency. In this paper, we see dynamic routing networks in a fresh light, formulating a routing method as a mapping from a sample space to a routing space. From the perspective of space mapping, prevalent methods of dynamic routing didn't consider how inference paths would be distributed in the routing space. Thus, we propose a novel method, termed CoDiNet, to model the relationship between a sample space and a routing space by regularizing the distribution of routing paths with the properties of consistency and diversity. Specifically, samples with similar semantics should be mapped into the same area in routing space, while those with dissimilar semantics should be mapped into different areas. Moreover, we design a customizable dynamic routing module, which can strike a balance between accuracy and efficiency. When deployed upon ResNet models, our method achieves higher performance and effectively reduces average computational cost on four widely used datasets.
Machine learning methods to detect money laundering in the Bitcoin blockchain in the presence of label scarcity
Venue: arXiv cs.LG 2021
Year: 2021

Every year, criminals launder billions of dollars acquired from serious felonies (e.g., terrorism, drug smuggling, or human trafficking) harming countless people and economies. Cryptocurrencies, in particular, have developed as a haven for money laundering activity. Machine Learning can be used to detect these illicit patterns. However, labels are so scarce that traditional supervised algorithms are inapplicable. Here, we address money laundering detection assuming minimal access to labels. First, we show that existing state-of-the-art solutions using unsupervised anomaly detection methods are inadequate to detect the illicit patterns in a real Bitcoin transaction dataset. Then, we show that our proposed active learning solution is capable of matching the performance of a fully supervised baseline by using just 5\% of the labels. This solution mimics a typical real-life situation in which a limited number of labels can be acquired through manual annotation by experts.
Discrete Signaling and Treating Interference as Noise for the Gaussian Interference Channel
Venue: arXiv cs.IT 2021
Year: 2021

The two-user Gaussian interference channel (G-IC) is revisited, with a particular focus on practically amenable discrete input signalling and treating interference as noise (TIN) receivers. The corresponding deterministic interference channel (D-IC) is first investigated and coding schemes that can achieve the entire capacity region of D-IC under TIN are proposed. These schemes are then systematically translate into multi-layer superposition coding schemes based on purely discrete inputs for the real-valued G-IC. Our analysis shows that the proposed scheme is able to achieve the entire capacity region to within a constant gap for all channel parameters. To the best of our knowledge, this is the first constant-gap result under purely discrete signalling and TIN for the entire capacity region and all the interference regimes. Furthermore, the approach is extended to obtain coding scheme based on discrete inputs for the complex-valued G-IC. For such a scenario, the minimum distance and the achievable rate of the proposed scheme under TIN are analyzed, which takes into account the effects of random phase rotations introduced by the channels. Simulation results show that our scheme is capable of approaching the capacity region of the complex-valued G-IC and significantly outperforms Gaussian signalling with TIN in various interference regimes.
Spatial Distribution of the Mean Peak Age of Information in Wireless Networks
Venue: arXiv cs.IT 2021
Year: 2021

This paper considers a large-scale wireless network consisting of source-destination (SD) pairs, where the sources send time-sensitive information, termed status updates, to their corresponding destinations in a time-slotted fashion. We employ Age of information (AoI) for quantifying the freshness of the status updates measured at the destination nodes for two different queuing disciplines, namely Type I and II queues. Type I queue is assumed to transmit the status updates in a first-come-first-served (FCFS) fashion with no storage facility. However, Type I queue may not necessarily minimize AoI because a new update will not be allowed to enter a server until the current update has been successfully transmitted. To overcome this shortcoming, we consider Type II queue in which the most recent status update available at a given transmission slot is transmitted in order to minimize the AoI. As the update delivery rate for a given link is a function of the interference field seen from the receiver, the temporal mean AoI can be treated as a random variable over space. Our goal in this paper is to characterize the spatial distribution of the mean AoI observed by the SD pairs by modeling them as a Poisson bipolar process. Towards this objective, we first derive accurate bounds on the moments of success probability while efficiently capturing the interference-induced coupling in the activities of the SD pairs. Using this result, we then derive tight bounds on the moments as well as the spatial distribution of peak AoI. Our numerical results verify our analytical findings and demonstrate the impact of various system design parameters on the mean peak AoI.
Centralized and Decentralized Non-Cooperative Load-Balancing Games among Federated Cloudlets
Venue: arXiv cs.NI 2021
Year: 2021

Edge computing servers like cloudlets from different service providers compensate scarce computational, memory, and energy resources of mobile devices, are distributed across access networks. However, depending on the mobility pattern and dynamically varying computational requirements of associated mobile devices, cloudlets at different parts of the network become either overloaded or under-loaded. Hence, load balancing among neighboring cloudlets appears to be an essential research problem. Nonetheless, the existing load balancing frameworks are unsuitable for low-latency applications. Thus, in this paper, we propose an economic and non-cooperative load balancing game for low-latency applications among federated neighboring cloudlets from the same as well as different service providers and heterogeneous classes of job requests. Firstly, we propose a centralized incentive mechanism to compute the pure strategy Nash equilibrium load balancing strategies of the cloudlets under the supervision of a neutral mediator. With this mechanism, we ensure that the truthful revelation of private information to the mediator is a weakly-dominant strategy for all the federated cloudlets. Secondly, we propose a continuous-action reinforcement learning automata-based algorithm, which allows each cloudlet to independently compute the Nash equilibrium in a completely distributed network setting. We critically study the convergence properties of the designed learning algorithm, scaffolding our understanding of the underlying load balancing game for faster convergence. Furthermore, through extensive simulations, we study the impacts of exploration and exploitation on learning accuracy. This is the first study to show the effectiveness of reinforcement learning algorithms for load balancing games among neighboring cloudlets.