OpenRaiser/Intern-Atlas huggingface dataset:
Where are the Masks: Instance Segmentation with Image-level Supervision
Venue: arXiv cs.CV 2019
Year: 2019

A major obstacle in instance segmentation is that existing methods often need many per-pixel labels in order to be effective. These labels require large human effort and for certain applications, such labels are not readily available. To address this limitation, we propose a novel framework that can effectively train with image-level labels, which are significantly cheaper to acquire. For instance, one can do an internet search for the term "car" and obtain many images where a car is present with minimal effort. Our framework consists of two stages: (1) train a classifier to generate pseudo masks for the objects of interest; (2) train a fully supervised Mask R-CNN on these pseudo masks. Our two main contribution are proposing a pipeline that is simple to implement and is amenable to different segmentation methods; and achieves new state-of-the-art results for this problem setup. Our results are based on evaluating our method on PASCAL VOC 2012, a standard dataset for weakly supervised methods, where we demonstrate major performance gains compared to existing methods with respect to mean average precision.
A Note On The Popularity of Stochastic Optimization Algorithms in Different Fields: A Quantitative Analysis from 2007 to 2017
Venue: arXiv cs.NE 2019
Year: 2019

Stochastic optimization algorithms are often used to solve complex large-scale optimization problems in various fields. To date, there have been a number of stochastic optimization algorithms such as Genetic Algorithm, Cuckoo Search, Tabu Search, Simulated Annealing, Particle Swarm Optimization, Ant Colony Optimization, etc. Each algorithm has some advantages and disadvantages. Currently, there is no study that can help researchers to choose the most popular optimization algorithm to deal with the problems in different research fields. In this note, a quantitative analysis of the popularity of 14 stochastic optimization algorithms in 18 different research fields in the last ten years from 2007 to 2017 is provided. This quantitative analysis can help researchers/practitioners select the best optimization algorithm to solve complex large-scale optimization problems in the fields of Engineering, Computer science, Operations research, Mathematics, Physics, Chemistry, Automation control systems, Materials science, Energy fuels, Mechanics, Telecommunications, Thermodynamics, Optics, Environmental sciences ecology, Water resources, Transportation, Construction building technology, and Robotics.
Semantic Driven Fielded Entity Retrieval
Venue: arXiv cs.IR 2019
Year: 2019

A common approach for knowledge-base entity search is to consider an entity as a document with multiple fields. Models that focus on matching query terms in different fields are popular choices for searching such entity representations. An instance of such a model is FSDM (Fielded Sequential Dependence Model). We propose to integrate field-level semantic features into FSDM. We use FSDM to retrieve a pool of documents, and then to use semantic field-level features to re-rank those documents. We propose to represent queries as bags of terms as well as bags of entities, and eventually, use their dense vector representation to compute semantic features based on query document similarity. Our proposed re-ranking approach achieves significant improvement in entity retrieval on the DBpedia-Entity (v2) dataset over existing FSDM model. Specifically, for all queries we achieve 2.5% and 1.2% significant improvement in NDCG@10 and NDCG@100, respectively.
Augmenting Self-attention with Persistent Memory
Venue: arXiv cs.LG 2019
Year: 2019

Transformer networks have lead to important progress in language modeling and machine translation. These models include two consecutive modules, a feed-forward layer and a self-attention layer. The latter allows the network to capture long term dependencies and are often regarded as the key ingredient in the success of Transformers. Building upon this intuition, we propose a new model that solely consists of attention layers. More precisely, we augment the self-attention layers with persistent memory vectors that play a similar role as the feed-forward layer. Thanks to these vectors, we can remove the feed-forward layer without degrading the performance of a transformer. Our evaluation shows the benefits brought by our model on standard character and word level language modeling benchmarks.
Obj-GloVe: Scene-Based Contextual Object Embedding
Venue: arXiv cs.CV 2019
Year: 2019

Recently, with the prevalence of large-scale image dataset, the co-occurrence information among classes becomes rich, calling for a new way to exploit it to facilitate inference. In this paper, we propose Obj-GloVe, a generic scene-based contextual embedding for common visual objects, where we adopt the word embedding method GloVe to exploit the co-occurrence between entities. We train the embedding on pre-processed Open Images V4 dataset and provide extensive visualization and analysis by dimensionality reduction and projecting the vectors along a specific semantic axis, and showcasing the nearest neighbors of the most common objects. Furthermore, we reveal the potential applications of Obj-GloVe on object detection and text-to-image synthesis, then verify its effectiveness on these two applications respectively.
Themis: Fair and Efficient GPU Cluster Scheduling
Venue: arXiv cs.DC 2019
Year: 2019

Modern distributed machine learning (ML) training workloads benefit significantly from leveraging GPUs. However, significant contention ensues when multiple such workloads are run atop a shared cluster of GPUs. A key question is how to fairly apportion GPUs across workloads. We find that established cluster scheduling disciplines are a poor fit because of ML workloads' unique attributes: ML jobs have long-running tasks that need to be gang-scheduled, and their performance is sensitive to tasks' relative placement. We propose Themis, a new scheduling framework for ML training workloads. It's GPU allocation policy enforces that ML workloads complete in a finish-time fair manner, a new notion we introduce. To capture placement sensitivity and ensure efficiency, Themis uses a two-level scheduling architecture where ML workloads bid on available resources that are offered in an auction run by a central arbiter. Our auction design allocates GPUs to winning bids by trading off efficiency for fairness in the short term but ensuring finish-time fairness in the long term. Our evaluation on a production trace shows that Themis can improve fairness by more than 2.25X and is ~5% to 250% more cluster efficient in comparison to state-of-the-art schedulers.
Continuous Integration Theater
Venue: arXiv cs.SE 2019
Year: 2019

Background: Continuous Integration (CI) systems are now the bedrock of several software development practices. Several tools such as TravisCI, CircleCI, and Hudson, that implement CI practices, are commonly adopted by software engineers. However, the way that software engineers use these tools could lead to what we call "Continuous Integration Theater", a situation in which software engineers do not employ these tools effectively, leading to unhealthy CI practices. Aims: The goal of this paper is to make sense of how commonplace are these unhealthy continuous integration practices being employed in practice. Method: By inspecting 1,270 open-source projects that use TravisCI, the most used CI service, we quantitatively studied how common is to use CI (1) with infrequent commits, (2) in a software project with poor test coverage, (3) with builds that stay broken for long periods, and (4) with builds that take too long to run. Results: We observed that 748 ($sim$60%) projects face infrequent commits, which essentially makes the merging process harder. Moreover, we were able to find code coverage information for 51 projects. The average code coverage was 78%, although Ruby projects have a higher code coverage than Java projects (86% and 63%, respectively). However, some projects with very small coverage ($sim$4%) were found. Still, we observed that 85% of the studied projects have at least one broken build that take more than four days to be fixed. Interestingly, very small projects (up to 1,000 lines of code) are the ones that take the longest to fix broken builds. Finally, we noted that, for the majority of the studied projects, the build is executed under the 10 minutes rule of thumb. Conclusions: Our results are important to an increasing community of software engineers that employ CI practices on daily basis but may not be aware of bad practices that are eventually employed.
A Short Proof of the Toughness of Delaunay Triangulations
Venue: arXiv cs.CG 2019
Year: 2019

We present a self-contained short proof of the seminal result of Dillencourt (SoCG 1987 and DCG 1990) that Delaunay triangulations, of planar point sets in general position, are 1-tough. An important implication of this result is that Delaunay triangulations have perfect matchings. Another implication of our result is a proof of the conjecture of Aichholzer et al. (2010) that at least $n$ points are required to block any $n$-vertex Delaunay triangulation
Rule Applicability on RDF Triplestore Schemas
Venue: arXiv cs.DB 2019
Year: 2019

Rule-based systems play a critical role in health and safety, where policies created by experts are usually formalised as rules. When dealing with increasingly large and dynamic sources of data, as in the case of Internet of Things (IoT) applications, it becomes important not only to efficiently apply rules, but also to reason about their applicability on datasets confined by a certain schema. In this paper we define the notion of a triplestore schema which models a set of RDF graphs. Given a set of rules and such a schema as input we propose a method to determine rule applicability and produce output schemas. Output schemas model the graphs that would be obtained by running the rules on the graph models of the input schema. We present two approaches: one based on computing a canonical (critical) instance of the schema, and a novel approach based on query rewriting. We provide theoretical, complexity and evaluation results that show the superior efficiency of our rewriting approach.
Adaptive Deep Learning of Cross-Domain Loss in Collaborative Filtering
Venue: arXiv cs.IR 2019
Year: 2019

Nowadays, users open multiple accounts on social media platforms and e-commerce sites, expressing their personal preferences on different domains. However, users' behaviors change across domains, depending on the content that users interact with, such as movies, music, clothing and retail products. In this paper, we propose an adaptive deep learning strategy for cross-domain recommendation, referred to as ADC. We design a neural architecture and formulate a cross-domain loss function, to compute the non-linearity in user preferences across domains and transfer the knowledge of users' multiple behaviors, accordingly. In addition, we introduce an efficient algorithm for cross-domain loss balancing which directly tunes gradient magnitudes and adapts the learning rates based on the domains' complexities/scales when training the model via backpropagation. In doing so, ADC controls and adjusts the contribution of each domain when optimizing the model parameters. Our experiments on six publicly available cross-domain recommendation tasks demonstrate the effectiveness of the proposed ADC model over other state-of-the-art methods. Furthermore, we study the effect of the proposed adaptive deep learning strategy and show that ADC can well balance the impact of the domains with different complexities.
MimosaNet: An Unrobust Neural Network Preventing Model Stealing
Venue: arXiv cs.LG 2019
Year: 2019

Deep Neural Networks are robust to minor perturbations of the learned network parameters and their minor modifications do not change the overall network response significantly. This allows space for model stealing, where a malevolent attacker can steal an already trained network, modify the weights and claim the new network his own intellectual property. In certain cases this can prevent the free distribution and application of networks in the embedded domain. In this paper, we propose a method for creating an equivalent version of an already trained fully connected deep neural network that can prevent network stealing: namely, it produces the same responses and classification accuracy, but it is extremely sensitive to weight changes.
Graph Neural Network for Interpreting Task-fMRI Biomarkers
Venue: arXiv cs.LG 2019
Year: 2019

Finding the biomarkers associated with ASD is helpful for understanding the underlying roots of the disorder and can lead to earlier diagnosis and more targeted treatment. A promising approach to identify biomarkers is using Graph Neural Networks (GNNs), which can be used to analyze graph structured data, i.e. brain networks constructed by fMRI. One way to interpret important features is through looking at how the classification probability changes if the features are occluded or replaced. The major limitation of this approach is that replacing values may change the distribution of the data and lead to serious errors. Therefore, we develop a 2-stage pipeline to eliminate the need to replace features for reliable biomarker interpretation. Specifically, we propose an inductive GNN to embed the graphs containing different properties of task-fMRI for identifying ASD and then discover the brain regions/sub-graphs used as evidence for the GNN classifier. We first show GNN can achieve high accuracy in identifying ASD. Next, we calculate the feature importance scores using GNN and compare the interpretation ability with Random Forest. Finally, we run with different atlases and parameters, proving the robustness of the proposed method. The detected biomarkers reveal their association with social behaviors. We also show the potential of discovering new informative biomarkers. Our pipeline can be generalized to other graph feature importance interpretation problems.
MultiWOZ 2.1: A Consolidated Multi-Domain Dialogue Dataset with State Corrections and State Tracking Baselines
Venue: arXiv cs.CL 2019
Year: 2019

MultiWOZ 2.0 (Budzianowski et al., 2018) is a recently released multi-domain dialogue dataset spanning 7 distinct domains and containing over 10,000 dialogues. Though immensely useful and one of the largest resources of its kind to-date, MultiWOZ 2.0 has a few shortcomings. Firstly, there is substantial noise in the dialogue state annotations and dialogue utterances which negatively impact the performance of state-tracking models. Secondly, follow-up work (Lee et al., 2019) has augmented the original dataset with user dialogue acts. This leads to multiple co-existent versions of the same dataset with minor modifications. In this work we tackle the aforementioned issues by introducing MultiWOZ 2.1. To fix the noisy state annotations, we use crowdsourced workers to re-annotate state and utterances based on the original utterances in the dataset. This correction process results in changes to over 32% of state annotations across 40% of the dialogue turns. In addition, we fix 146 dialogue utterances by canonicalizing slot values in the utterances to the values in the dataset ontology. To address the second problem, we combined the contributions of the follow-up works into MultiWOZ 2.1. Hence, our dataset also includes user dialogue acts as well as multiple slot descriptions per dialogue state slot. We then benchmark a number of state-of-the-art dialogue state tracking models on the MultiWOZ 2.1 dataset and show the joint state tracking performance on the corrected state annotations. We are publicly releasing MultiWOZ 2.1 to the community, hoping that this dataset resource will allow for more effective models across various dialogue subproblems to be built in the future.
HyperNOMAD: Hyperparameter optimization of deep neural networks using mesh adaptive direct search
Venue: arXiv cs.LG 2019
Year: 2019

The performance of deep neural networks is highly sensitive to the choice of the hyperparameters that define the structure of the network and the learning process. When facing a new application, tuning a deep neural network is a tedious and time consuming process that is often described as a "dark art". This explains the necessity of automating the calibration of these hyperparameters. Derivative-free optimization is a field that develops methods designed to optimize time consuming functions without relying on derivatives. This work introduces the HyperNOMAD package, an extension of the NOMAD software that applies the MADS algorithm [7] to simultaneously tune the hyperparameters responsible for both the architecture and the learning process of a deep neural network (DNN), and that allows for an important flexibility in the exploration of the search space by taking advantage of categorical variables. This new approach is tested on the MNIST and CIFAR-10 data sets and achieves results comparable to the current state of the art.
On Adaptivity Gaps of Influence Maximization under the Independent Cascade Model with Full Adoption Feedback
Venue: arXiv cs.SI 2019
Year: 2019

In this paper, we study the adaptivity gap of the influence maximization problem under independent cascade model when full-adoption feedback is available. Our main results are to derive upper bounds on several families of well-studied influence graphs, including in-arborescences, out-arborescences and bipartite graphs. Especially, we prove that the adaptivity gap for the in-arborescence is between $[\frac{e}{e-1}, \frac{2e}{e - 1}]$ and for the out-arborescence, the gap is between $[\frac{e}{e-1}, 2]$. These are the first constant upper bounds in the full-adoption feedback model. We provide several novel ideas to tackle with correlated feedback appearing in the adaptive stochastic optimization, which we believe to be of independent interests.
Mask Embedding in conditional GAN for Guided Synthesis of High Resolution Images
Venue: arXiv cs.CV 2019
Year: 2019

Recent advancements in conditional Generative Adversarial Networks (cGANs) have shown promises in label guided image synthesis. Semantic masks, such as sketches and label maps, are another intuitive and effective form of guidance in image synthesis. Directly incorporating the semantic masks as constraints dramatically reduces the variability and quality of the synthesized results. We observe this is caused by the incompatibility of features from different inputs (such as mask image and latent vector) of the generator. To use semantic masks as guidance whilst providing realistic synthesized results with fine details, we propose to use mask embedding mechanism to allow for a more efficient initial feature projection in the generator. We validate the effectiveness of our approach by training a mask guided face generator using CELEBA-HQ dataset. We can generate realistic and high resolution facial images up to the resolution of 512*512 with a mask guidance. Our code is publicly available.
Quickly Finding the Best Linear Model in High Dimensions
Venue: arXiv cs.LG 2019
Year: 2019

We study the problem of finding the best linear model that can minimize least-squares loss given a data-set. While this problem is trivial in the low dimensional regime, it becomes more interesting in high dimensions where the population minimizer is assumed to lie on a manifold such as sparse vectors. We propose projected gradient descent (PGD) algorithm to estimate the population minimizer in the finite sample regime. We establish linear convergence rate and data dependent estimation error bounds for PGD. Our contributions include: 1) The results are established for heavier tailed sub-exponential distributions besides sub-gaussian. 2) We directly analyze the empirical risk minimization and do not require a realizable model that connects input data and labels. 3) Our PGD algorithm is augmented to learn the bias terms which boosts the performance. The numerical experiments validate our theoretical results.
Generalized Assignment via Submodular Optimization with Reserved Capacity
Venue: arXiv cs.DS 2019
Year: 2019

We study a variant of the \emph{generalized assignment problem} ({\sf GAP}) with group constraints. An instance of {\sf Group GAP} is a set $I$ of items, partitioned into $L$ groups, and a set of $m$ uniform (unit-sized) bins. Each item $i \in I$ has a size $s_i >0$, and a profit $p_{i,j} \geq 0$ if packed in bin $j$. A group of items is \emph{satisfied} if all of its items are packed. The goal is to find a feasible packing of a subset of the items in the bins such that the total profit from satisfied groups is maximized. We point to central applications of {\sf Group GAP} in Video-on-Demand services, mobile Device-to-Device network caching and base station cooperation in 5G networks. Our main result is a $\frac{1}{6}$-approximation algorithm for {\sf Group GAP} instances where the total size of each group is at most $\frac{m}{2}$. At the heart of our algorithm lies an interesting derivation of a submodular function from the classic LP formulation of {\sf GAP}, which facilitates the construction of a high profit solution utilizing at most half the total bin capacity, while the other half is \emph{reserved} for later use. In particular, we give an algorithm for submodular maximization subject to a knapsack constraint, which finds a solution of profit at least $\frac{1}{3}$ of the optimum, using at most half the knapsack capacity, under mild restrictions on element sizes. Our novel approach of submodular optimization subject to a knapsack \emph{with reserved capacity} constraint may find applications in solving other group assignment problems.
GeoPrune: Efficiently Finding Shareable Vehicles Based on Geometric Properties
Venue: arXiv cs.DB 2019
Year: 2019

On-demand ride-sharing is rapidly growing.Matching trip requests to vehicles efficiently is critical for the service quality of ride-sharing. To match trip requests with vehicles, a prune-and-select scheme is commonly used. The pruning stage identifies feasible vehicles that can satisfy the trip constraints (e.g., trip time). The selection stage selects the optimal one(s) from the feasible vehicles. The pruning stage is crucial to reduce the complexity of the selection stage and to achieve efficient matching. We propose an effective and efficient pruning algorithm called GeoPrune. GeoPrune represents the time constraints of trip requests using circles and ellipses, which can be computed and updated efficiently. Experiments on real-world datasets show that GeoPrune reduces the number of vehicle candidates in nearly all cases by an order of magnitude and the update cost by two to three orders of magnitude compared to the state-of-the-art.
A general representation of dynamical systems for reservoir computing
Venue: arXiv cs.NE 2019
Year: 2019

Dynamical systems are capable of performing computation in a reservoir computing paradigm. This paper presents a general representation of these systems as an artificial neural network (ANN). Initially, we implement the simplest dynamical system, a cellular automaton. The mathematical fundamentals behind an ANN are maintained, but the weights of the connections and the activation function are adjusted to work as an update rule in the context of cellular automata. The advantages of such implementation are its usage on specialized and optimized deep learning libraries, the capabilities to generalize it to other types of networks and the possibility to evolve cellular automata and other dynamical systems in terms of connectivity, update and learning rules. Our implementation of cellular automata constitutes an initial step towards a general framework for dynamical systems. It aims to evolve such systems to optimize their usage in reservoir computing and to model physical computing substrates.