OpenRaiser/Intern-Atlas huggingface dataset:
Approximating Weighted Completion Time for Order Scheduling with Setup Times
Venue: arXiv cs.DS 2019
Year: 2019

Consider a scheduling problem in which jobs need to be processed on a single machine. Each job has a weight and is composed of several operations belonging to different families. The machine needs to perform a setup between the processing of operations of different families. A job is completed when its latest operation completes and the goal is to minimize the total weighted completion time of all jobs. We study this problem from the perspective of approximability and provide constant factor approximations as well as an inapproximability result. Prior to this work, only the NP-hardness of the unweighted case and the polynomial solvability of a certain special case were known.
Illumination-Based Data Augmentation for Robust Background Subtraction
Venue: arXiv cs.CV 2019
Year: 2019

A core challenge in background subtraction (BGS) is handling videos with sudden illumination changes in consecutive frames. In this paper, we tackle the problem from a data point-of-view using data augmentation. Our method performs data augmentation that not only creates endless data on the fly, but also features semantic transformations of illumination which enhance the generalisation of the model. It successfully simulates flashes and shadows by applying the Euclidean distance transform over a binary mask that is randomly generated. Such data allows us to effectively train an illumination-invariant deep learning model for BGS. Experimental results demonstrate the contribution of the synthetics in the ability of the models to perform BGS even when significant illumination changes take place. The source code of the project is made publicly available at https://github.com/dksakkos/illumination_augmentation.
Texture Bias Of CNNs Limits Few-Shot Classification Performance
Venue: arXiv cs.LG 2019
Year: 2019

Accurate image classification given small amounts of labelled data (few-shot classification) remains an open problem in computer vision. In this work we examine how the known texture bias of Convolutional Neural Networks (CNNs) affects few-shot classification performance. Although texture bias can help in standard image classification, in this work we show it significantly harms few-shot classification performance. After correcting this bias we demonstrate state-of-the-art performance on the competitive miniImageNet task using a method far simpler than the current best performing few-shot learning approaches.
Towards Interpretable Graph Modeling with Vertex Replacement Grammars
Venue: arXiv cs.SI 2019
Year: 2019

An enormous amount of real-world data exists in the form of graphs. Oftentimes, interesting patterns that describe the complex dynamics of these graphs are captured in the form of frequently reoccurring substructures. Recent work at the intersection of formal language theory and graph theory has explored the use of graph grammars for graph modeling and pattern mining. However, existing formulations do not extract meaningful and easily interpretable patterns from the data. The present work addresses this limitation by extracting a special type of vertex replacement grammar, which we call a KT grammar, according to the Minimum Description Length (MDL) heuristic. In experiments on synthetic and real-world datasets, we show that KT-grammars can be efficiently extracted from a graph and that these grammars encode meaningful patterns that represent the dynamics of the real-world system.
Comparing Greedy Constructive Heuristic Subtour Elimination Methods for the Traveling Salesman Problem
Venue: arXiv cs.AI 2019
Year: 2019

This paper further defines the class of fragment constructive heuristics used to compute feasible solutions for the Traveling Salesman Problem into arc-greedy and node-greedy subclasses. Since these subclasses of heuristics can create subtours, two known methodologies for subtour elimination on symmetric instances are reviewed and are expanded to cover asymmetric problem instances. This paper introduces a third novel methodology, the Greedy Tracker, and compares it to both known methodologies. Computational results are generated across multiple symmetric and asymmetric instances. The results demonstrate the Greedy Tracker is the fastest method for preventing subtours for instances below 400 nodes. A distinction between fragment constructive heuristics and the subtour elimination methodology used to ensure the feasibility of resulting solutions enables the introduction of a new node-greedy fragment heuristic called Ordered Greedy.
NASIB: Neural Architecture Search withIn Budget
Venue: arXiv cs.LG 2019
Year: 2019

Neural Architecture Search (NAS) represents a class of methods to generate the optimal neural network architecture and typically iterate over candidate architectures till convergence over some particular metric like validation loss. They are constrained by the available computation resources, especially in enterprise environments. In this paper, we propose a new approach for NAS, called NASIB, which adapts and attunes to the computation resources (budget) available by varying the exploration vs. exploitation trade-off. We reduce the expert bias by searching over an augmented search space induced by Superkernels. The proposed method can provide the architecture search useful for different computation resources and different domains beyond image classification of natural images where we lack bespoke architecture motifs and domain expertise. We show, on CIFAR10, that itis possible to search over a space that comprises of 12x more candidate operations than the traditional prior art in just 1.5 GPU days, while reaching close to state of the art accuracy. While our method searches over an exponentially larger search space, it could lead to novel architectures that require lesser domain expertise, compared to the majority of the existing methods.
Introduction to Coresets: Accurate Coresets
Venue: arXiv cs.LG 2019
Year: 2019

A coreset (or core-set) of an input set is its small summation, such that solving a problem on the coreset as its input, provably yields the same result as solving the same problem on the original (full) set, for a given family of problems (models, classifiers, loss functions). Over the past decade, coreset construction algorithms have been suggested for many fundamental problems in e.g. machine/deep learning, computer vision, graphics, databases, and theoretical computer science. This introductory paper was written following requests from (usually non-expert, but also colleagues) regarding the many inconsistent coreset definitions, lack of available source code, the required deep theoretical background from different fields, and the dense papers that make it hard for beginners to apply coresets and develop new ones. The paper provides folklore, classic and simple results including step-by-step proofs and figures, for the simplest (accurate) coresets of very basic problems, such as: sum of vectors, minimum enclosing ball, SVD/ PCA and linear regression. Nevertheless, we did not find most of their constructions in the literature. Moreover, we expect that putting them together in a retrospective context would help the reader to grasp modern results that usually extend and generalize these fundamental observations. Experts might appreciate the unified notation and comparison table that links between existing results. Open source code with example scripts are provided for all the presented algorithms, to demonstrate their practical usage, and to support the readers who are more familiar with programming than math.
A Type of Virtual Force based Energy-hole Mitigation Strategy for Sensor Networks
Venue: arXiv cs.NI 2019
Year: 2019

In the era of Big Data and Mobile Internet, how to ensure the terminal devices (e.g., sensor nodes) work steadily for a long time is one of the key issues to improve the efficiency of the whole network. However, a lot of facts have shown that the unattended equipments are prone to failure due to energy exhaustion, physical damage and other reasons. This may result in the emergence of energy-hole, seriously affecting network performance and shortening its lifetime. To reduce data redundancy and avoid the generation of sensing blind areas, a type of Virtual Force based Energy-hole Mitigation strategy (VFEM) is proposed in this paper. Firstly, the virtual force (gravitation and repulsion) between nodes is introduced that makes nodes distribute as uniformly as possible. Secondly, in order to alleviate the "energy-hole problem", the network is divided into several annuluses with the same width. Then, another type of virtual force, named "virtual gravity generated by annulus", is proposed to further optimize the positions of nodes in each annulus. Finally, with the help of the "data forwarding area", the optimal paths for data uploading can be selected out, which effectively balances energy consumption of nodes. Experiment results show that, VFEM has a relatively good performance on postponing the generation time of energy-holes as well as prolonging the network lifetime compared with other typical energy-hole mitigation methods.
On Adaptivity in Information-constrained Online Learning
Venue: arXiv cs.LG 2019
Year: 2019

We study how to adapt to smoothly-varying ('easy') environments in well-known online learning problems where acquiring information is expensive. For the problem of label efficient prediction, which is a budgeted version of prediction with expert advice, we present an online algorithm whose regret depends optimally on the number of labels allowed and $Q^*$ (the quadratic variation of the losses of the best action in hindsight), along with a parameter-free counterpart whose regret depends optimally on $Q$ (the quadratic variation of the losses of all the actions). These quantities can be significantly smaller than $T$ (the total time horizon), yielding an improvement over existing, variation-independent results for the problem. We then extend our analysis to handle label efficient prediction with bandit feedback, i.e., label efficient bandits. Our work builds upon the framework of optimistic online mirror descent, and leverages second order corrections along with a carefully designed hybrid regularizer that encodes the constrained information structure of the problem. We then consider revealing action-partial monitoring games -- a version of label efficient prediction with additive information costs, which in general are known to lie in the \textit{hard} class of games having minimax regret of order $T^{\frac{2}{3}}$. We provide a strategy with an $\mathcal{O}((Q^*T)^{\frac{1}{3}})$ bound for revealing action games, along with one with a $\mathcal{O}((QT)^{\frac{1}{3}})$ bound for the full class of hard partial monitoring games, both being strict improvements over current bounds.
On Using Chatbots to Promote Smoking Cessation Among Adolescents of Low Socioeconomic Status
Venue: arXiv cs.HC 2019
Year: 2019

Reducing youth tobacco use is critical for improving child health since tobacco use is associated with respiratory problems, and nicotine may interfere with healthy brain development. While tobacco regulation has contributed to declines in cigarette use among youth, these declines have occurred more quickly for youth of high socioeconomic status (SES) compared to youth of low SES. A major barrier to smoking cessation for adolescents of low SES is coordination of access and transportation to in-person treatment sessions. Low-SES youth may have family obligations that limit their ability to access in-person treatment. At the same time, mobile use among adolescents is high: 85% have smartphones. Additionally, adolescents engage in texting at high rates, suggesting that they are well-suited for mobile instant messaging interventions. Mobile interventions have shown promise for youth, but their use remains low. Thus, more research is needed to develop effective and engaging mobile interventions to increase quit rates. In this paper, we provide a brief review of approaches to adolescent smoking cessation and describe the promise of chatbots for smoking cessation.
The Deepfake Detection Challenge (DFDC) Preview Dataset
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we introduce a preview of the Deepfakes Detection Challenge (DFDC) dataset consisting of 5K videos featuring two facial modification algorithms. A data collection campaign has been carried out where participating actors have entered into an agreement to the use and manipulation of their likenesses in our creation of the dataset. Diversity in several axes (gender, skin-tone, age, etc.) has been considered and actors recorded videos with arbitrary backgrounds thus bringing visual variability. Finally, a set of specific metrics to evaluate the performance have been defined and two existing models for detecting deepfakes have been tested to provide a reference performance baseline. The DFDC dataset preview can be downloaded at: deepfakedetectionchallenge.ai
Integrating DFT and DRBD Formalizations in HOL4
Venue: arXiv cs.LO 2019
Year: 2019

Dynamic Fault Trees (DFT) and Dynamic Reliability Block Diagrams (DRBD) are two modeling approaches that capture the dynamic failure behavior of engineering systems for their reliability analysis. Recently, two independent higher-order logic (HOL) formalizations of DFT and DRBD algebras have been developed in the HOL4 theorem prover. In this work, we propose to integrate these two modeling approaches for the efficient formal reliability analysis of complex systems by leveraging upon the advantages of each method. The soundness of this integration is provided through a formal proof of equivalence between the DFT and DRBD algebras. We show the efficiency of the proposed integrated formal reliability analysis on a drive-by-wire system as a case study.
Planted Models for $k$-way Edge and Vertex Expansion
Venue: arXiv cs.DS 2019
Year: 2019

Graph partitioning problems are a central topic of study in algorithms and complexity theory. Edge expansion and vertex expansion, two popular graph partitioning objectives, seek a $2$-partition of the vertex set of the graph that minimizes the considered objective. However, for many natural applications, one might require a graph to be partitioned into $k$ parts, for some $k \geq 2$. For a $k$-partition $S_1, \ldots, S_k$ of the vertex set of a graph $G = (V,E)$, the $k$-way edge expansion (resp. vertex expansion) of $\{S_1, \ldots, S_k\}$ is defined as $\max_{i \in [k]} Φ(S_i)$, and the balanced $k$-way edge expansion (resp. vertex expansion) of $G$ is defined as \[ \min_{ \{S_1, \ldots, S_k\} \in \mathcal{P}_k} \max_{i \in [k]} Φ(S_i) \, , \] where $\mathcal{P}_k$ is the set of all balanced $k$-partitions of $V$ (i.e each part of a $k$-partition in $\mathcal{P}_k$ should have cardinality $|V|/k$), and $Φ(S)$ denotes the edge expansion (resp. vertex expansion) of $S \subset V$. We study a natural planted model for graphs where the vertex set of a graph has a $k$-partition $S_1, \ldots, S_k$ such that the graph induced on each $S_i$ has large expansion, but each $S_i$ has small edge expansion (resp. vertex expansion) in the graph. We give bi-criteria approximation algorithms for computing the balanced $k$-way edge expansion (resp. vertex expansion) of instances in this planted model.
Matrix-Product Codes over Commutative Rings and Constructions Arising from $(σ,δ)$-Codes
Venue: arXiv cs.IT 2019
Year: 2019

A well-known lower bound (over finite fields and some special finite commutative rings) on the Hamming distance of a matrix-product code (MPC) is shown to remain valid over any commutative ring $R$. A sufficient condition is given, as well, for such a bound to be sharp. It is also shown that an MPC is free when its input codes are all free, in which case a generating matrix is given. If $R$ is finite, a sufficient condition is provided for the dual of an MPC to be an MPC, a generating matrix for such a dual is given, and characterizations of LCD, self-dual, and self-orthogonal MPCs are presented. Finally, results of this paper are used along with previous results of the authors to construct novel MPCs arising from $(σ, δ)$-codes. Some properties of such constructions are also studied.
Benchmark Dataset for Timetable Optimization of Bus Routes in the City of New Delhi
Venue: arXiv cs.OH 2019
Year: 2019

Public transport is one of the major forms of transportation in the world. This makes it vital to ensure that public transport is efficient. This research presents a novel real-time GPS bus transit data for over 500 routes of buses operating in New Delhi. The data can be used for modeling various timetable optimization tasks as well as in other domains such as traffic management, travel time estimation, etc. The paper also presents an approach to reduce the waiting time of Delhi buses by analyzing the traffic behavior and proposing a timetable. This algorithm serves as a benchmark for the dataset. The algorithm uses a constrained clustering algorithm for classification of trips. It further analyses the data statistically to provide a timetable which is efficient in learning the inter- and intra-month variations.
Sparse-Dense Subspace Clustering
Venue: arXiv cs.LG 2019
Year: 2019

Subspace clustering refers to the problem of clustering high-dimensional data into a union of low-dimensional subspaces. Current subspace clustering approaches are usually based on a two-stage framework. In the first stage, an affinity matrix is generated from data. In the second one, spectral clustering is applied on the affinity matrix. However, the affinity matrix produced by two-stage methods cannot fully reveal the similarity between data points from the same subspace (intra-subspace similarity), resulting in inaccurate clustering. Besides, most approaches fail to solve large-scale clustering problems due to poor efficiency. In this paper, we first propose a new scalable sparse method called Iterative Maximum Correlation (IMC) to learn the affinity matrix from data. Then we develop Piecewise Correlation Estimation (PCE) to densify the intra-subspace similarity produced by IMC. Finally we extend our work into a Sparse-Dense Subspace Clustering (SDSC) framework with a dense stage to optimize the affinity matrix for two-stage methods. We show that IMC is efficient when clustering large-scale data, and PCE ensures better performance for IMC. We show the universality of our SDSC framework as well. Experiments on several data sets demonstrate the effectiveness of our approaches. Moreover, we are the first one to apply densification on affinity matrix before spectral clustering, and SDSC constitutes the first attempt to build a universal three-stage subspace clustering framework.
Improved solution to data gathering with mobile mule
Venue: arXiv cs.NI 2019
Year: 2019

In this work we study the problem of collecting protected data in ad-hoc sensor network using a mobile entity called MULE. The objective is to increase information survivability in the network. Sensors from all over the network, route their sensing data through a data gathering tree, towards a particular node, called the $sink$. In case of a failed sensor, all the aggregated data from the sensor and from its children is lost. In order to retrieve the lost data, the MULE is required to travel among all the children of the failed sensor and to re-collect the data. There is a cost to travel between two points in the plane. We aim to minimize the MULE traveling cost, given that any sensor can fail. In order to reduce the traveling cost, it is necessary to find the optimal data gathering tree and the MULE location. We are considering the problem for the unit disk graphs (UDG) and Euclidean distance cost function. We propose a primal-dual algorithm that produces a $\left(20+\varepsilon\right)$-approximate solution for the problem, where $\varepsilon\rightarrow0$ as the sensor network spreads over a larger area. The algorithm requires $O\left(n^{3}\cdot\varDelta\left(G\right)\right)$ time to construct a gathering tree and to place the MULE, where $\varDelta\left(G\right)$ is the maximum degree in the graph and $n$ is the number of nodes.
Learning from both experts and data
Venue: arXiv cs.LG 2019
Year: 2019

In this work we study the problem of inferring a discrete probability distribution using both expert knowledge and empirical data. This is an important issue for many applications where the scarcity of data prevents a purely empirical approach. In this context, it is common to rely first on an initial domain knowledge a priori before proceeding to an online data acquisition. We are particularly interested in the intermediate regime where we do not have enough data to do without the initial expert a priori of the experts, but enough to correct it if necessary. We present here a novel way to tackle this issue with a method providing an objective way to choose the weight to be given to experts compared to data. We show, both empirically and theoretically, that our proposed estimator is always more efficient than the best of the two models (expert or data) within a constant.
Boosting Mapping Functionality of Neural Networks via Latent Feature Generation based on Reversible Learning
Venue: arXiv cs.LG 2019
Year: 2019

This paper addresses a boosting method for mapping functionality of neural networks in visual recognition such as image classification and face recognition. We present reversible learning for generating and learning latent features using the network itself. By generating latent features corresponding to hard samples and applying the generated features in a training stage, reversible learning can improve a mapping functionality without additional data augmentation or handling the bias of dataset. We demonstrate an efficiency of the proposed method on the MNIST,Cifar-10/100, and Extremely Biased and poorly categorized dataset (EBPC dataset). The experimental results show that the proposed method can outperform existing state-of-the-art methods in visual recognition. Extensive analysis shows that our method can efficiently improve the mapping capability of a network.
Unsupervised Out-of-Distribution Detection with Batch Normalization
Venue: arXiv cs.LG 2019
Year: 2019

Likelihood from a generative model is a natural statistic for detecting out-of-distribution (OoD) samples. However, generative models have been shown to assign higher likelihood to OoD samples compared to ones from the training distribution, preventing simple threshold-based detection rules. We demonstrate that OoD detection fails even when using more sophisticated statistics based on the likelihoods of individual samples. To address these issues, we propose a new method that leverages batch normalization. We argue that batch normalization for generative models challenges the traditional i.i.d. data assumption and changes the corresponding maximum likelihood objective. Based on this insight, we propose to exploit in-batch dependencies for OoD detection. Empirical results suggest that this leads to more robust detection for high-dimensional images.