OpenRaiser/Intern-Atlas huggingface dataset:
How to Better Distinguish Security Bug Reports (using Dual Hyperparameter Optimization
Venue: arXiv cs.SE 2021
Year: 2021

Background: In order that the general public is not vulnerable to hackers, security bug reports need to be handled by small groups of engineers before being widely discussed. But learning how to distinguish the security bug reports from other bug reports is challenging since they may occur rarely. Data mining methods that can find such scarce targets require extensive optimization effort. Goal: The goal of this research is to aid practitioners as they struggle to optimize methods that try to distinguish between rare security bug reports and other bug reports. Method: Our proposed method, called Swift, is a dual optimizer that optimizes both learner and pre-processor options. Since this is a large space of options, Swift uses a technique called epsilon-dominance that learns how to avoid operations that do not significantly improve performance. Result: When compared to recent state-of-the-art results (from FARSEC which is published in TSE'18), we find that the Swift's dual optimization of both pre-processor and learner is more useful than optimizing each of them individually. For example, in a study of security bug reports from the Chromium dataset, the median recalls of FARSEC and Swift were 15.7% and 77.4%, respectively. For another example, in experiments with data from the Ambari project, the median recalls improved from 21.5% to 85.7% (FARSEC to SWIFT). Conclusion: Overall, our approach can quickly optimize models that achieve better recalls than the prior state-of-the-art. These increases in recall are associated with moderate increases in false positive rates (from 8% to 24%, median). For future work, these results suggest that dual optimization is both practical and useful.
Graph Domain Adaptation with Localized Graph Signal Representations
Venue: arXiv cs.LG 2021
Year: 2021

In this paper we propose a domain adaptation algorithm designed for graph domains. Given a source graph with many labeled nodes and a target graph with few or no labeled nodes, we aim to estimate the target labels by making use of the similarity between the characteristics of the variation of the label functions on the two graphs. Our assumption about the source and the target domains is that the local behaviour of the label function, such as its spread and speed of variation on the graph, bears resemblance between the two graphs. We estimate the unknown target labels by solving an optimization problem where the label information is transferred from the source graph to the target graph based on the prior that the projections of the label functions onto localized graph bases be similar between the source and the target graphs. In order to efficiently capture the local variation of the label functions on the graphs, spectral graph wavelets are used as the graph bases. Experimentation on various data sets shows that the proposed method yields quite satisfactory classification accuracy compared to reference domain adaptation methods.
Penalty Method for Inversion-Free Deep Bilevel Optimization
Venue: arXiv cs.LG 2021
Year: 2021

Solving a bilevel optimization problem is at the core of several machine learning problems such as hyperparameter tuning, data denoising, meta- and few-shot learning, and training-data poisoning. Different from simultaneous or multi-objective optimization, the steepest descent direction for minimizing the upper-level cost in a bilevel problem requires the inverse of the Hessian of the lower-level cost. In this work, we propose a novel algorithm for solving bilevel optimization problems based on the classical penalty function approach. Our method avoids computing the Hessian inverse and can handle constrained bilevel problems easily. We prove the convergence of the method under mild conditions and show that the exact hypergradient is obtained asymptotically. Our method's simplicity and small space and time complexities enable us to effectively solve large-scale bilevel problems involving deep neural networks. We present results on data denoising, few-shot learning, and training-data poisoning problems in a large-scale setting. Our results show that our approach outperforms or is comparable to previously proposed methods based on automatic differentiation and approximate inversion in terms of accuracy, run-time, and convergence speed.
Adaptive Fusion Techniques for Multimodal Data
Venue: arXiv cs.CL 2021
Year: 2021

Effective fusion of data from multiple modalities, such as video, speech, and text, is challenging due to the heterogeneous nature of multimodal data. In this paper, we propose adaptive fusion techniques that aim to model context from different modalities effectively. Instead of defining a deterministic fusion operation, such as concatenation, for the network, we let the network decide "how" to combine a given set of multimodal features more effectively. We propose two networks: 1) Auto-Fusion, which learns to compress information from different modalities while preserving the context, and 2) GAN-Fusion, which regularizes the learned latent space given context from complementing modalities. A quantitative evaluation on the tasks of multimodal machine translation and emotion recognition suggests that our lightweight, adaptive networks can better model context from other modalities than existing methods, many of which employ massive transformer-based networks.
Socially-Aware Navigation: A Non-linear Multi-Objective Optimization Approach
Venue: arXiv cs.RO 2021
Year: 2021

Mobile robots are increasingly populating homes, hospitals, shopping malls, factory floors, and other human environments. Human society has social norms that people mutually accept; obeying these norms is an essential signal that someone is participating socially with respect to the rest of the population. For robots to be socially compatible with humans, it is crucial for robots to obey these social norms. In prior work, we demonstrated a Socially-Aware Navigation (SAN) planner, based on Pareto Concavity Elimination Transformation (PaCcET), in a hallway scenario, optimizing two objectives so that the robot does not invade the personal space of people. This paper extends our PaCcET based SAN planner to multiple scenarios with more than two objectives. We modified the Robot Operating System's (ROS) navigation stack to include PaCcET in the local planning task. We show that our approach can accommodate multiple Human-Robot Interaction (HRI) scenarios. Using the proposed approach, we achieved successful HRI in multiple scenarios like hallway interactions, an art gallery, waiting in a queue, and interacting with a group. We implemented our method on a simulated PR2 robot in a 2D simulator (Stage) and a pioneer-3DX mobile robot in the real-world to validate all the scenarios. A comprehensive set of experiments shows that our approach can handle multiple interaction scenarios on both holonomic and non-holonomic robots; hence, it can be a viable option for a Unified Socially-Aware Navigation (USAN).
Text classification with pixel embedding
Venue: arXiv cs.CL 2021
Year: 2021

We propose a novel framework to understand the text by converting sentences or articles into video-like 3-dimensional tensors. Each frame, corresponding to a slice of the tensor, is a word image that is rendered by the word's shape. The length of the tensor equals to the number of words in the sentence or article. The proposed transformation from the text to a 3-dimensional tensor makes it very convenient to implement an $n$-gram model with convolutional neural networks for text analysis. Concretely, we impose a 3-dimensional convolutional kernel on the 3-dimensional text tensor. The first two dimensions of the convolutional kernel size equal the size of the word image and the last dimension of the kernel size is $n$. That is, every time when we slide the 3-dimensional kernel over a word sequence, the convolution covers $n$ word images and outputs a scalar. By iterating this process continuously for each $n$-gram along with the sentence or article with multiple kernels, we obtain a 2-dimensional feature map. A subsequent 1-dimensional max-over-time pooling is applied to this feature map, and three fully-connected layers are used for conducting text classification finally. Experiments of several text classification datasets demonstrate surprisingly superior performances using the proposed model in comparison with existing methods.
FLAML: A Fast and Lightweight AutoML Library
Venue: arXiv cs.LG 2021
Year: 2021

We study the problem of using low computational cost to automate the choices of learners and hyperparameters for an ad-hoc training dataset and error metric, by conducting trials of different configurations on the given training data. We investigate the joint impact of multiple factors on both trial cost and model error, and propose several design guidelines. Following them, we build a fast and lightweight library FLAML which optimizes for low computational resource in finding accurate models. FLAML integrates several simple but effective search strategies into an adaptive system. It significantly outperforms top-ranked AutoML libraries on a large open source AutoML benchmark under equal, or sometimes orders of magnitude smaller budget constraints.
CHEETAH: An Ultra-Fast, Approximation-Free, and Privacy-Preserved Neural Network Framework based on Joint Obscure Linear and Nonlinear Computations
Venue: arXiv cs.LG 2021
Year: 2021

Machine Learning as a Service (MLaaS) is enabling a wide range of smart applications on end devices. However, such convenience comes with a cost of privacy because users have to upload their private data to the cloud. This research aims to provide effective and efficient MLaaS such that the cloud server learns nothing about user data and the users cannot infer the proprietary model parameters owned by the server. This work makes the following contributions. First, it unveils the fundamental performance bottleneck of existing schemes due to the heavy permutations in computing linear transformation and the use of communication intensive Garbled Circuits for nonlinear transformation. Second, it introduces an ultra-fast secure MLaaS framework, CHEETAH, which features a carefully crafted secret sharing scheme that runs significantly faster than existing schemes without accuracy loss. Third, CHEETAH is evaluated on the benchmark of well-known, practical deep networks such as AlexNet and VGG-16 on the MNIST and ImageNet datasets. The results demonstrate more than 100x speedup over the fastest GAZELLE (Usenix Security'18), 2000x speedup over MiniONN (ACM CCS'17) and five orders of magnitude speedup over CryptoNets (ICML'16). This significant speedup enables a wide range of practical applications based on privacy-preserved deep neural networks.
Double cycle-consistent generative adversarial network for unsupervised conditional generation
Venue: arXiv cs.LG 2021
Year: 2021

Conditional generative models have achieved considerable success in the past few years, but usually require a lot of labeled data. Recently, ClusterGAN combines GAN with an encoder to achieve remarkable clustering performance via unsupervised conditional generation. However, it ignores the real conditional distribution of data, which leads to generating less diverse samples for each class and makes the encoder only achieve sub-optimal clustering performance. Here, we propose a new unsupervised conditional generation framework, Double Cycle-Consistent Conditional GAN (DC3-GAN), which can generate diverse class-conditioned samples. We enforce the encoder and the generator of GAN to form an encoder-generator pair in addition to the generator-encoder pair, which enables us to avoid the low-diversity generation and the triviality of latent features. We train the encoder-generator pair using real data, which can indirectly estimate the real conditional distribution. Meanwhile, this framework enforces the outputs of the encoder to match the inputs of GAN and the prior noise distribution, which disentangles latent space into two parts: one-hot discrete and continuous latent variables. The former can be directly expressed as clusters and the latter represents remaining unspecified factors. This work demonstrates that enhancing the diversity of unsupervised conditional generated samples can improve the clustering performance. Experiments on different benchmark datasets show that the proposed method outperforms existing generative model-based clustering methods, and also achieves the optimal disentanglement performance.
Securely Computing the $n$-Variable Equality Function with $2n$ Cards
Venue: arXiv cs.CR 2021
Year: 2021

Research in the area of secure multi-party computation using a deck of playing cards, often called card-based cryptography, started from the introduction of the five-card trick protocol to compute the logical AND function by den Boer in 1989. Since then, many card-based protocols to compute various functions have been developed. In this paper, we propose two new protocols that securely compute the $n$-variable equality function (determining whether all inputs are equal) $E: \{0,1\}^n \rightarrow \{0,1\}$ using $2n$ cards. The first protocol can be generalized to compute any doubly symmetric function $f: \{0,1\}^n \rightarrow \mathbb{Z}$ using $2n$ cards, and any symmetric function $f: \{0,1\}^n \rightarrow \mathbb{Z}$ using $2n+2$ cards. The second protocol can be generalized to compute the $k$-candidate $n$-variable equality function $E: (\mathbb{Z}/k\mathbb{Z})^n \rightarrow \{0,1\}$ using $2 \lceil \lg k \rceil n$ cards.
Instance-based Transfer Learning for Multilingual Deep Retrieval
Venue: arXiv cs.CL 2021
Year: 2021

We focus on the problem of search in the multilingual setting. Examining the problems of next-sentence prediction and inverse cloze, we show that at large scale, instance-based transfer learning is surprisingly effective in the multilingual setting, leading to positive transfer on all of the 35 target languages and two tasks tested. We analyze this improvement and argue that the most natural explanation, namely direct vocabulary overlap between languages, only partially explains the performance gains: in fact, we demonstrate target-language improvement can occur after adding data from an auxiliary language even with no vocabulary in common with the target. This surprising result is due to the effect of transitive vocabulary overlaps between pairs of auxiliary and target languages.
Improve CAM with Auto-adapted Segmentation and Co-supervised Augmentation
Venue: arXiv cs.CV 2021
Year: 2021

Weakly Supervised Object Localization (WSOL) methods generate both classification and localization results by learning from only image category labels. Previous methods usually utilize class activation map (CAM) to obtain target object regions. However, most of them only focus on improving foreground object parts in CAM, but ignore the important effect of its background contents. In this paper, we propose a confidence segmentation (ConfSeg) module that builds confidence score for each pixel in CAM without introducing additional hyper-parameters. The generated sample-specific confidence mask is able to indicate the extent of determination for each pixel in CAM, and further supervises additional CAM extended from internal feature maps. Besides, we introduce Co-supervised Augmentation (CoAug) module to capture feature-level representation for foreground and background parts in CAM separately. Then a metric loss is applied at batch sample level to augment distinguish ability of our model, which helps a lot to localize more related object parts. Our final model, CSoA, combines the two modules and achieves superior performance, e.g. $37.69\%$ and $48.81\%$ Top-1 localization error on CUB-200 and ILSVRC datasets, respectively, which outperforms all previous methods and becomes the new state-of-the-art.
Influence-aware Memory Architectures for Deep Reinforcement Learning
Venue: arXiv cs.LG 2021
Year: 2021

Due to its perceptual limitations, an agent may have too little information about the state of the environment to act optimally. In such cases, it is important to keep track of the observation history to uncover hidden state. Recent deep reinforcement learning methods use recurrent neural networks (RNN) to memorize past observations. However, these models are expensive to train and have convergence difficulties, especially when dealing with high dimensional input spaces. In this paper, we propose influence-aware memory (IAM), a theoretically inspired memory architecture that tries to alleviate the training difficulties by restricting the input of the recurrent layers to those variables that influence the hidden state information. Moreover, as opposed to standard RNNs, in which every piece of information used for estimating Q values is inevitably fed back into the network for the next prediction, our model allows information to flow without being necessarily stored in the RNN's internal memory. Results indicate that, by letting the recurrent layers focus on a small fraction of the observation variables while processing the rest of the information with a feedforward neural network, we can outperform standard recurrent architectures both in training speed and policy performance. This approach also reduces runtime and obtains better scores than methods that stack multiple observations to remove partial observability.
When Smoothness is Not Enough: Toward Exact Quantification and Optimization of the Price of Anarchy
Venue: arXiv cs.GT 2021
Year: 2021

The price of anarchy (PoA) is a popular metric for analyzing the inefficiency of self-interested decision making. Although its study is widespread, characterizing the PoA can be challenging. A commonly employed approach is based on the smoothness framework, which provides tight PoA values under the assumption that the system objective consists in the sum of the agents' individual welfares. Unfortunately, several important classes of problems do not satisfy this requirement (e.g., taxation in congestion games), and our first result demonstrates that the smoothness framework does *not* tightly characterize the PoA for such settings. Motivated by this observation, this work develops a framework that achieves two chief objectives: i) to tightly characterize the PoA for such scenarios, and ii) to do so through a tractable approach. As a direct consequence, the proposed framework recovers and generalizes many existing PoA results, and enables efficient computation of incentives that optimize the PoA. We conclude by highlighting the applicability of our contributions to incentive design in congestion games and utility design in distributed welfare games.
Frequent Elements with Witnesses in Data Streams
Venue: arXiv cs.DS 2021
Year: 2021

Detecting frequent elements is among the oldest and most-studied problems in the area of data streams. Given a stream of $m$ data items in $\{1, 2, \dots, n\}$, the objective is to output items that appear at least $d$ times, for some threshold parameter $d$, and provably optimal algorithms are known today. However, in many applications, knowing only the frequent elements themselves is not enough: For example, an Internet router may not only need to know the most frequent destination IP addresses of forwarded packages, but also the timestamps of when these packages appeared or any other meta-data that "arrived" with the packages, e.g., their source IP addresses. In this paper, we introduce the witness version of the frequent elements problem: Given a desired approximation guarantee $α\ge 1$ and a desired frequency $d \le Δ$, where $Δ$ is the frequency of the most frequent item, the objective is to report an item together with at least $d / α$ timestamps of when the item appeared in the stream (or any other meta-data that arrived with the items). We give provably optimal algorithms for both the insertion-only and insertion-deletion stream settings: In insertion-only streams, we show that space $\tilde{O}(n + d \cdot n^{\frac{1}α})$ is necessary and sufficient for every integral $1 \le α\le \log n$. In insertion-deletion streams, we show that space $\tilde{O}(\frac{n \cdot d}{α^2})$ is necessary and sufficient, for every $α\le \sqrt{n}$.
Problems with SZZ and Features: An empirical study of the state of practice of defect prediction data collection
Venue: arXiv cs.SE 2021
Year: 2021

Context: The SZZ algorithm is the de facto standard for labeling bug fixing commits and finding inducing changes for defect prediction data. Recent research uncovered potential problems in different parts of the SZZ algorithm. Most defect prediction data sets provide only static code metrics as features, while research indicates that other features are also important. Objective: We provide an empirical analysis of the defect labels created with the SZZ algorithm and the impact of commonly used features on results. Method: We used a combination of manual validation and adopted or improved heuristics for the collection of defect data. We conducted an empirical study on 398 releases of 38 Apache projects. Results: We found that only half of the bug fixing commits determined by SZZ are actually bug fixing. If a six-month time frame is used in combination with SZZ to determine which bugs affect a release, one file is incorrectly labeled as defective for every file that is correctly labeled as defective. In addition, two defective files are missed. We also explored the impact of the relatively small set of features that are available in most defect prediction data sets, as there are multiple publications that indicate that, e.g., churn related features are important for defect prediction. We found that the difference of using more features is not significant. Conclusion: Problems with inaccurate defect labels are a severe threat to the validity of the state of the art of defect prediction. Small feature sets seem to be a less severe threat.
New Algorithms for Mixed Dominating Set
Venue: arXiv cs.DS 2021
Year: 2021

A mixed dominating set is a collection of vertices and edges that dominates all vertices and edges of a graph. We study the complexity of exact and parameterized algorithms for \textsc{Mixed Dominating Set}, resolving some open questions. In particular, we settle the problem's complexity parameterized by treewidth and pathwidth by giving an algorithm running in time $O^*(5^{tw})$ (improving the current best $O^*(6^{tw})$), as well as a lower bound showing that our algorithm cannot be improved under the Strong Exponential Time Hypothesis (SETH), even if parameterized by pathwidth (improving a lower bound of $O^*((2 - \varepsilon)^{pw})$). Furthermore, by using a simple but so far overlooked observation on the structure of minimal solutions, we obtain branching algorithms which improve both the best known FPT algorithm for this problem, from $O^*(4.172^k)$ to $O^*(3.510^k)$, and the best known exponential-time exact algorithm, from $O^*(2^n)$ and exponential space, to $O^*(1.912^n)$ and polynomial space.
Rule Extraction in Unsupervised Anomaly Detection for Model Explainability: Application to OneClass SVM
Venue: arXiv cs.LG 2021
Year: 2021

OneClass SVM is a popular method for unsupervised anomaly detection. As many other methods, it suffers from the black box problem: it is difficult to justify, in an intuitive and simple manner, why the decision frontier is identifying data points as anomalous or non anomalous. Such type of problem is being widely addressed for supervised models. However, it is still an uncharted area for unsupervised learning. In this paper, we evaluate several rule extraction techniques over OneClass SVM models, as well as present alternative designs for some of those algorithms. Together with that, we propose algorithms to compute metrics related with eXplainable Artificial Intelligence (XAI) regarding the "comprehensibility", "representativeness", "stability" and "diversity" of the extracted rules. We evaluate our proposals with different datasets, including real-world data coming from industry. With this, our proposal contributes to extend XAI techniques to unsupervised machine learning models.