OpenRaiser/Intern-Atlas huggingface dataset:
Largest similar copies of convex polygons amidst polygonal obstacles
Venue: arXiv cs.CG 2020
Year: 2020

Given a convex polygon $P$ with $k$ vertices and a polygonal domain $Q$ consisting of polygonal obstacles with total size $n$ in the plane, we study the optimization problem of finding a largest similar copy of $P$ that can be placed in $Q$ without intersecting the obstacles. We improve the time complexity for solving the problem to $O(k^2n^2λ_4(k)\log{n})$. This is progress of improving the previously best known results by Chew and Kedem [SoCG89, CGTA93] and Sharir and Toledo [SoCG91, CGTA94] on the problem in more than 25 years.
GeoNet++: Iterative Geometric Neural Network with Edge-Aware Refinement for Joint Depth and Surface Normal Estimation
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we propose a geometric neural network with edge-aware refinement (GeoNet++) to jointly predict both depth and surface normal maps from a single image. Building on top of two-stream CNNs, GeoNet++ captures the geometric relationships between depth and surface normals with the proposed depth-to-normal and normal-to-depth modules. In particular, the "depth-to-normal" module exploits the least square solution of estimating surface normals from depth to improve their quality, while the "normal-to-depth" module refines the depth map based on the constraints on surface normals through kernel regression. Boundary information is exploited via an edge-aware refinement module. GeoNet++ effectively predicts depth and surface normals with strong 3D consistency and sharp boundaries resulting in better reconstructed 3D scenes. Note that GeoNet++ is generic and can be used in other depth/normal prediction frameworks to improve the quality of 3D reconstruction and pixel-wise accuracy of depth and surface normals. Furthermore, we propose a new 3D geometric metric (3DGM) for evaluating depth prediction in 3D. In contrast to current metrics that focus on evaluating pixel-wise error/accuracy, 3DGM measures whether the predicted depth can reconstruct high-quality 3D surface normals. This is a more natural metric for many 3D application domains. Our experiments on NYUD-V2 and KITTI datasets verify that GeoNet++ produces fine boundary details, and the predicted depth can be used to reconstruct high-quality 3D surfaces. Code has been made publicly available.
Effective multi-view registration of point sets based on student's t mixture model
Venue: arXiv cs.CV 2020
Year: 2020

Recently, Expectation-maximization (EM) algorithm has been introduced as an effective means to solve multi-view registration problem. Most of the previous methods assume that each data point is drawn from the Gaussian Mixture Model (GMM), which is difficult to deal with the noise with heavy-tail or outliers. Accordingly, this paper proposed an effective registration method based on Student's t Mixture Model (StMM). More specially, we assume that each data point is drawn from one unique StMM, where its nearest neighbors (NNs) in other point sets are regarded as the t-distribution centroids with equal covariances, membership probabilities, and fixed degrees of freedom. Based on this assumption, the multi-view registration problem is formulated into the maximization of the likelihood function including all rigid transformations. Subsequently, the EM algorithm is utilized to optimize rigid transformations as well as the only t-distribution covariance for multi-view registration. Since only a few model parameters require to be optimized, the proposed method is more likely to obtain the desired registration results. Besides, all t-distribution centroids can be obtained by the NN search method, it is very efficient to achieve multi-view registration. What's more, the t-distribution takes the noise with heavy-tail into consideration, which makes the proposed method be inherently robust to noises and outliers. Experimental results tested on benchmark data sets illustrate its superior performance on robustness and accuracy over state-of-the-art methods.
C2C-GenDA: Cluster-to-Cluster Generation for Data Augmentation of Slot Filling
Venue: arXiv cs.CL 2020
Year: 2020

Slot filling, a fundamental module of spoken language understanding, often suffers from insufficient quantity and diversity of training data. To remedy this, we propose a novel Cluster-to-Cluster generation framework for Data Augmentation (DA), named C2C-GenDA. It enlarges the training set by reconstructing existing utterances into alternative expressions while keeping semantic. Different from previous DA works that reconstruct utterances one by one independently, C2C-GenDA jointly encodes multiple existing utterances of the same semantics and simultaneously decodes multiple unseen expressions. Jointly generating multiple new utterances allows to consider the relations between generated instances and encourages diversity. Besides, encoding multiple existing utterances endows C2C with a wider view of existing expressions, helping to reduce generation that duplicates existing data. Experiments on ATIS and Snips datasets show that instances augmented by C2C-GenDA improve slot filling by 7.99 (11.9%) and 5.76 (13.6%) F-scores respectively, when there are only hundreds of training utterances.
InferCode: Self-Supervised Learning of Code Representations by Predicting Subtrees
Venue: arXiv cs.SE 2020
Year: 2020

Building deep learning models on source code has found many successful software engineering applications, such as code search, code comment generation, bug detection, code migration, and so on. Current learning techniques, however, have a major drawback that these models are mostly trained on datasets labeled for particular downstream tasks, and code representations may not be suitable for other tasks. While some techniques produce representations from unlabeled code, they are far from satisfactory when applied to downstream tasks. Although certain techniques generate representations from unlabeled code when applied to downstream tasks they are far from satisfactory. This paper proposes InferCode to overcome the limitation by adapting the self-supervised learning mechanism to build source code model. The key novelty lies in training code representations by predicting automatically identified subtrees from the context of the ASTs. Subtrees in ASTs are treated with InferCode as the labels for training code representations without any human labeling effort or the overhead of expensive graph construction, and the trained representations are no longer tied to any specific downstream tasks or code units. We trained an InferCode model instance using the Tree-based CNN as the encoder of a large set of Java code and applied it to downstream unsupervised tasks such as code clustering, code clone detection, cross-language code search or reused under a transfer learning scheme to continue training the model weights for supervised tasks such as code classification and method name prediction. Compared to previous code learning techniques applied to the same downstream tasks, such as Code2Vec, Code2Seq, ASTNN, higher performance results are achieved using our pre-trained InferCode model with a significant margin for most tasks including those involving different programming languages.
Efficient Human Pose Estimation by Learning Deeply Aggregated Representations
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we propose an efficient human pose estimation network (DANet) by learning deeply aggregated representations. Most existing models explore multi-scale information mainly from features with different spatial sizes. Powerful multi-scale representations usually rely on the cascaded pyramid framework. This framework largely boosts the performance but in the meanwhile makes networks very deep and complex. Instead, we focus on exploiting multi-scale information from layers with different receptive-field sizes and then making full of use this information by improving the fusion method. Specifically, we propose an orthogonal attention block (OAB) and a second-order fusion unit (SFU). The OAB learns multi-scale information from different layers and enhances them by encouraging them to be diverse. The SFU adaptively selects and fuses diverse multi-scale information and suppress the redundant ones. This could maximize the effective information in final fused representations. With the help of OAB and SFU, our single pyramid network may be able to generate deeply aggregated representations that contain even richer multi-scale information and have a larger representing capacity than that of cascaded networks. Thus, our networks could achieve comparable or even better accuracy with much smaller model complexity. Specifically, our \mbox{DANet-72} achieves $70.5$ in AP score on COCO test-dev set with only $1.0G$ FLOPs. Its speed on a CPU platform achieves $58$ Persons-Per-Second~(PPS).
Fault Injectors for TensorFlow: Evaluation of the Impact of Random Hardware Faults on Deep CNNs
Venue: arXiv cs.LG 2020
Year: 2020

Today, Deep Learning (DL) enhances almost every industrial sector, including safety-critical areas. The next generation of safety standards will define appropriate verification techniques for DL-based applications and propose adequate fault tolerance mechanisms. DL-based applications, like any other software, are susceptible to common random hardware faults such as bit flips, which occur in RAM and CPU registers. Such faults can lead to silent data corruption. Therefore, it is crucial to develop methods and tools that help to evaluate how DL components operate under the presence of such faults. In this paper, we introduce two new Fault Injection (FI) frameworks InjectTF and InjectTF2 for TensorFlow 1 and TensorFlow 2, respectively. Both frameworks are available on GitHub and allow the configurable injection of random faults into Neural Networks (NN). In order to demonstrate the feasibility of the frameworks, we also present the results of FI experiments conducted on four VGG-based Convolutional NNs using two image sets. The results demonstrate how random bit flips in the output of particular mathematical operations and layers of NNs affect the classification accuracy. These results help to identify the most critical operations and layers, compare the reliability characteristics of functionally similar NNs, and introduce selective fault tolerance mechanisms.
Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous Feedback
Venue: arXiv cs.LG 2020
Year: 2020

We study the multi-armed bandit (MAB) problem with composite and anonymous feedback. In this model, the reward of pulling an arm spreads over a period of time (we call this period as reward interval) and the player receives partial rewards of the action, convoluted with rewards from pulling other arms, successively. Existing results on this model require prior knowledge about the reward interval size as an input to their algorithms. In this paper, we propose adaptive algorithms for both the stochastic and the adversarial cases, without requiring any prior information about the reward interval. For the stochastic case, we prove that our algorithm guarantees a regret that matches the lower bounds (in order). For the adversarial case, we propose the first algorithm to jointly handle non-oblivious adversary and unknown reward interval size. We also conduct simulations based on real-world dataset. The results show that our algorithms outperform existing benchmarks.
A Reliability-Aware, Delay Guaranteed, and Resource Efficient Placement of Service Function Chains in Softwarized 5G Networks
Venue: arXiv cs.NI 2020
Year: 2020

Network Functions Virtualization (NFV) allows flexibility, scalability, agility, and easy manageability of networks by leveraging the features of virtualization and cloud computing technologies. However, softwarization of network functions imposes many challenges. Reliability and latency are major challenges in NFV-enabled 5G networks that can lead to customer dissatisfaction and revenue loss. In general, redundancy is used to improve the reliability of communication services. However, redundancy requires the same amount of additional resources and thus increases cost. In this work, we address the reliability-aware, delay guaranteed, and resource efficient Service Function Chain (SFC) placement problem in softwarized 5G networks. First, we propose a novel SFC subchaining method to enhance the reliability of an SFC without backups. If reliability requirement is not met after subchaining method, we add backups to VNFs to meet the reliability requirement. Then, we formulate the reliable SFC placement problem as an Integer Linear Programming (ILP) problem in order to solve it optimally. Owing to high computational complexity of the ILP problem for solving large input instances, we propose a modified stable matching algorithm to provide near-optimal solution in polynomial time. By extensive simulations we show that our proposed solutions consume lesser physical resources compared to state-of-the-art solutions for provisioning reliable communication services.
Adaptive and Oblivious Randomized Subspace Methods for High-Dimensional Optimization: Sharp Analysis and Lower Bounds
Venue: arXiv cs.IT 2020
Year: 2020

We propose novel randomized optimization methods for high-dimensional convex problems based on restrictions of variables to random subspaces. We consider oblivious and data-adaptive subspaces and study their approximation properties via convex duality and Fenchel conjugates. A suitable adaptive subspace can be generated by sampling a correlated random matrix whose second order statistics mirror the input data. We illustrate that the adaptive strategy can significantly outperform the standard oblivious sampling method, which is widely used in the recent literature. We show that the relative error of the randomized approximations can be tightly characterized in terms of the spectrum of the data matrix and Gaussian width of the dual tangent cone at optimum. We develop lower bounds for both optimization and statistical error measures based on concentration of measure and Fano's inequality. We then present the consequences of our theory with data matrices of varying spectral decay profiles. Experimental results show that the proposed approach enables significant speed ups in a wide variety of machine learning and optimization problems including logistic regression, kernel classification with random convolution layers and shallow neural networks with rectified linear units.
Computing Nash equilibria for integer programming games
Venue: arXiv cs.GT 2020
Year: 2020

The recently defined class of integer programming games (IPG) models situations where multiple self-interested decision makers interact, with their strategy sets represented by a finite set of linear constraints together with integer requirements. Many real-world problems can suitably be fit in this class, and hence anticipating IPG outcomes is of crucial value for policy makers and regulators. Nash equilibria have been widely accepted as the solution concept of a game. Consequently, their computation provides a reasonable prediction of the games outcome. In this paper, we start by showing the computational complexity of deciding the existence of a Nash equilibrium for an IPG. Then, using sufficient conditions for their existence, we develop two general algorithmic approaches that are guaranteed to approximate an equilibrium under mild conditions. We also showcase how our methodology can be changed to determine other equilibria definitions. The performance of our methods is analyzed through computational experiments in a knapsack game, a competitive lot-sizing game, and a kidney exchange game. To the best of our knowledge, this is the first time that equilibria computation methods for general integer programming games have been designed and computationally tested.
Learning Heatmap-Style Jigsaw Puzzles Provides Good Pretraining for 2D Human Pose Estimation
Venue: arXiv cs.CV 2020
Year: 2020

The target of 2D human pose estimation is to locate the keypoints of body parts from input 2D images. State-of-the-art methods for pose estimation usually construct pixel-wise heatmaps from keypoints as labels for learning convolution neural networks, which are usually initialized randomly or using classification models on ImageNet as their backbones. We note that 2D pose estimation task is highly dependent on the contextual relationship between image patches, thus we introduce a self-supervised method for pretraining 2D pose estimation networks. Specifically, we propose Heatmap-Style Jigsaw Puzzles (HSJP) problem as our pretext-task, whose target is to learn the location of each patch from an image composed of shuffled patches. During our pretraining process, we only use images of person instances in MS-COCO, rather than introducing extra and much larger ImageNet dataset. A heatmap-style label for patch location is designed and our learning process is in a non-contrastive way. The weights learned by HSJP pretext task are utilised as backbones of 2D human pose estimator, which are then finetuned on MS-COCO human keypoints dataset. With two popular and strong 2D human pose estimators, HRNet and SimpleBaseline, we evaluate mAP score on both MS-COCO validation and test-dev datasets. Our experiments show that downstream pose estimators with our self-supervised pretraining obtain much better performance than those trained from scratch, and are comparable to those using ImageNet classification models as their initial backbones.
Knowledge Graph Management on the Edge
Venue: arXiv cs.DB 2020
Year: 2020

Edge computing emerges as an innovative platform for services requiring low latency decision making. Its success partly depends on the existence of efficient data management systems. We consider that knowledge graph management systems have a key role to play in this context due to their data integration and reasoning features. In this paper, we present SuccinctEdge, a compact, decompression-free, self-index, in-memory RDF store that can answer SPARQL queries, including those requiring reasoning services associated to some ontology. We provide details on its design and implementation before demonstrating its efficiency on real-world and synthetic datasets.
Leaking Sensitive Financial Accounting Data in Plain Sight using Deep Autoencoder Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Nowadays, organizations collect vast quantities of sensitive information in `Enterprise Resource Planning' (ERP) systems, such as accounting relevant transactions, customer master data, or strategic sales price information. The leakage of such information poses a severe threat for companies as the number of incidents and the reputational damage to those experiencing them continue to increase. At the same time, discoveries in deep learning research revealed that machine learning models could be maliciously misused to create new attack vectors. Understanding the nature of such attacks becomes increasingly important for the (internal) audit and fraud examination practice. The creation of such an awareness holds in particular for the fraudulent data leakage using deep learning-based steganographic techniques that might remain undetected by state-of-the-art `Computer Assisted Audit Techniques' (CAATs). In this work, we introduce a real-world `threat model' designed to leak sensitive accounting data. In addition, we show that a deep steganographic process, constituted by three neural networks, can be trained to hide such data in unobtrusive `day-to-day' images. Finally, we provide qualitative and quantitative evaluations on two publicly available real-world payment datasets.
How Trans-Inclusive are Hackathons?
Venue: arXiv cs.SE 2020
Year: 2020

Hackathons are fun! People go there to learn, meet new colleagues, intensively work on a collaborative project, and mix pizza with energy drinks. However, for transgender community and other minorities, hackathons can have an uncomfortable atmosphere. Some transgender and non-conforming people that, although enjoying hackathons, decided not to participate anymore, afraid of LGBQTPhobia and other discomforts. In this paper we surveyed 44 trans and cis hackathons participants and interviewed seven transgender ones. By understanding their needs and challenges, we introduce five recommendations to make hackathons more inclusive.
On Non-Markovian Performance Models
Venue: arXiv cs.PF 2020
Year: 2020

We present an approach that can be useful when the network or system performance is described by a model that is not Markovian. Although most performance models are based on Markov chains or Markov processes, in some cases the Markov property does not hold. This can occur, for example, when the system exhibits long range dependencies. For such situations, and other non-Markovian cases, our method may provide useful help.
Intelligent Reflecting Surface Aided Full-Duplex Communication: Passive Beamforming and Deployment Design
Venue: arXiv cs.IT 2020
Year: 2020

This paper investigates the passive beamforming and deployment design for an intelligent reflecting surface (IRS) aided full-duplex (FD) wireless system, where an FD access point (AP) communicates with an uplink (UL) user and a downlink (DL) user simultaneously over the same time-frequency dimension with the help of IRS. Under this setup, we consider three deployment cases: 1) two distributed IRSs placed near the UL user and DL user, respectively; 2) one centralized IRS placed near the DL user; 3) one centralized IRS placed near the UL user. In each case, we aim to minimize the weighted sum transmit power consumption of the AP and UL user by jointly optimizing their transmit power and the passive reflection coefficients at the IRS (or IRSs), subject to the UL and DL users' rate constraints and the uni-modulus constraints on the IRS reflection coefficients. First, we analyze the minimum transmit power required in the IRS-aided FD system under each deployment scheme, and compare it with that of the corresponding half-duplex (HD) system. We show that the FD system outperforms its HD counterpart for all IRS deployment schemes, while the distributed deployment further outperforms the other two centralized deployment schemes. Next, we transform the challenging power minimization problem into an equivalent but more tractable form and propose an efficient algorithm to solve it based on the block coordinate descent (BCD) method. Finally, numerical results are presented to validate our analysis as well as the efficacy of the proposed passive beamforming design.
Breaking the Expressive Bottlenecks of Graph Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Recently, the Weisfeiler-Lehman (WL) graph isomorphism test was used to measure the expressiveness of graph neural networks (GNNs), showing that the neighborhood aggregation GNNs were at most as powerful as 1-WL test in distinguishing graph structures. There were also improvements proposed in analogy to $k$-WL test ($k>1$). However, the aggregators in these GNNs are far from injective as required by the WL test, and suffer from weak distinguishing strength, making it become expressive bottlenecks. In this paper, we improve the expressiveness by exploring powerful aggregators. We reformulate aggregation with the corresponding aggregation coefficient matrix, and then systematically analyze the requirements of the aggregation coefficient matrix for building more powerful aggregators and even injective aggregators. It can also be viewed as the strategy for preserving the rank of hidden features, and implies that basic aggregators correspond to a special case of low-rank transformations. We also show the necessity of applying nonlinear units ahead of aggregation, which is different from most aggregation-based GNNs. Based on our theoretical analysis, we develop two GNN layers, ExpandingConv and CombConv. Experimental results show that our models significantly boost performance, especially for large and densely connected graphs.