OpenRaiser/Intern-Atlas huggingface dataset:
Learning Structured Declarative Rule Sets -- A Challenge for Deep Discrete Learning
Venue: arXiv cs.LG 2020
Year: 2020

Arguably the key reason for the success of deep neural networks is their ability to autonomously form non-linear combinations of the input features, which can be used in subsequent layers of the network. The analogon to this capability in inductive rule learning is to learn a structured rule base, where the inputs are combined to learn new auxiliary concepts, which can then be used as inputs by subsequent rules. Yet, research on rule learning algorithms that have such capabilities is still in their infancy, which is - we would argue - one of the key impediments to substantial progress in this field. In this position paper, we want to draw attention to this unsolved problem, with a particular focus on previous work in predicate invention and multi-label rule learning
Algorithms for finding $k$ in $k$-means
Venue: arXiv cs.DS 2020
Year: 2020

$k-$means Clustering requires as input the exact value of $k$, the number of clusters. Two challenges are open: (i) Is there a data-determined definition of $k$ which is provably correct and (ii) Is there a polynomial time algorithm to find $k$ from data ? This paper provides the first affirmative answers to both these questions. As common in the literature, we assume that the data admits an unknown Ground Truth (GT) clustering with cluster centers separated. This assumption alone is not sufficient to answer Yes to (i). We assume a novel, but natural second constraint called no tight sub-cluster (NTSC) which stipulates that no substantially large subset of a GT cluster can be "tighter" (in a sense we define) than the cluster. Our yes answer to (i) and (ii) are under these two deterministic assumptions. We also give polynomial time algorithm to identify $k$. Our algorithm relies on NTSC to peel off one cluster at a time by identifying points which are tightly packed. We are also able to show that our algorithm(s) apply to data generated by mixtures of Gaussians and more generally to mixtures of sub-Gaussian pdf's and hence are able to find the number of components of the mixture from data. To our knowledge, previous results for these specialized settings as well, assume generally that $k$ is given besides the data.
Computing The Packedness of Curves
Venue: arXiv cs.CG 2020
Year: 2020

A polygonal curve $P$ with $n$ vertices is $c$-packed, if the sum of the lengths of the parts of the edges of the curve that are inside any disk of radius $r$ is at most $cr$, for any $r>0$. Similarly, the concept of $c$-packedness can be defined for any scaling of a given shape. Assuming $L$ is the diameter of $P$ and $δ$ is the minimum distance between points on disjoint edges of $P$, we show the approximation factor of the existing $O(\frac{\log (L/δ)}εn^3)$ time algorithm is $1+ε$-approximation algorithm. The massively parallel versions of these algorithms run in $O(\log (L/δ))$ rounds. We improve the existing $O((\frac{n}{ε^3})^{\frac 4 3}\polylog \frac n ε)$ time $(6+ε)$-approximation algorithm by providing a $(4+ε)$-approximation $O(n(\log^2 n)(\log^2 \frac{1}ε)+\frac{n}ε)$ time algorithm, and the existing $O(n^2)$ time $2$-approximation algorithm improving the existing $O(n^2\log n)$ time $2$-approximation algorithm. Our exact $c$-packedness algorithm takes $O(n^5)$ time, which is the first exact algorithm for disks. We show using $α$-fat shapes instead of disks adds a factor $α^2$ to the approximation. We also give a data-structure for computing the curve-length inside query disks. It has $O(n^6\log n)$ construction time, uses $O(n^6)$ space, and has query time $O(\log n+k)$, where $k$ is the number of intersected segments with the query shape. We also give a massively parallel algorithm for relative $c$-packedness with $O(1)$ rounds.
NavRep: Unsupervised Representations for Reinforcement Learning of Robot Navigation in Dynamic Human Environments
Venue: arXiv cs.RO 2020
Year: 2020

Robot navigation is a task where reinforcement learning approaches are still unable to compete with traditional path planning. State-of-the-art methods differ in small ways, and do not all provide reproducible, openly available implementations. This makes comparing methods a challenge. Recent research has shown that unsupervised learning methods can scale impressively, and be leveraged to solve difficult problems. In this work, we design ways in which unsupervised learning can be used to assist reinforcement learning for robot navigation. We train two end-to-end, and 18 unsupervised-learning-based architectures, and compare them, along with existing approaches, in unseen test cases. We demonstrate our approach working on a real life robot. Our results show that unsupervised learning methods are competitive with end-to-end methods. We also highlight the importance of various components such as input representation, predictive unsupervised learning, and latent features. We make all our models publicly available, as well as training and testing environments, and tools. This release also includes OpenAI-gym-compatible environments designed to emulate the training conditions described by other papers, with as much fidelity as possible. Our hope is that this helps in bringing together the field of RL for robot navigation, and allows meaningful comparisons across state-of-the-art methods.
Maximum Coverage with Cluster Constraints: An LP-Based Approximation Technique
Venue: arXiv cs.DS 2020
Year: 2020

Packing problems constitute an important class of optimization problems, both because of their high practical relevance and theoretical appeal. However, despite the large number of variants that have been studied in the literature, most packing problems encompass a single tier of capacity restrictions only. For example, in the Multiple Knapsack Problem, we assign items to multiple knapsacks such that their capacities are not exceeded. But what if these knapsacks are partitioned into clusters, each imposing an additional capacity restriction on the knapsacks contained in that cluster? In this paper, we study the Maximum Coverage Problem with Cluster Constraints (MCPC), which generalizes the Maximum Coverage Problem with Knapsack Constraints (MCPK) by incorporating cluster constraints. Our main contribution is a general LP-based technique to derive approximation algorithms for cluster capacitated problems. Our technique allows us to reduce the cluster capacitated problem to the respective original packing problem. By using an LP-based approximation algorithm for the original problem, we can then obtain an effective rounding scheme for the problem, which only loses a small fraction in the approximation guarantee. We apply our technique to derive approximation algorithms for MCPC. To this aim, we develop an LP-based $\frac12(1-\frac1e)$-approximation algorithm for MCPK by adapting the pipage rounding technique. Combined with our reduction technique, we obtain a $\frac13(1-\frac1e)$-approximation algorithm for MCPC. We also derive improved results for a special case of MCPC, the Multiple Knapsack Problem with Cluster Constraints (MKPC). Based on a simple greedy algorithm, our approach yields a $\frac13$-approximation algorithm. By combining our technique with a more sophisticated iterative rounding approach, we obtain a $\frac12$-approximation algorithm for certain special cases of MKPC.
Multiple Hypothesis Semantic Mapping for Robust Data Association
Venue: arXiv cs.RO 2020
Year: 2020

In this paper, we present a semantic mapping approach with multiple hypothesis tracking for data association. As semantic information has the potential to overcome ambiguity in measurements and place recognition, it forms an eminent modality for autonomous systems. This is particularly evident in urban scenarios with several similar looking surroundings. Nevertheless, it requires the handling of a non-Gaussian and discrete random variable coming from object detectors. Previous methods facilitate semantic information for global localization and data association to reduce the instance ambiguity between the landmarks. However, many of these approaches do not deal with the creation of complete globally consistent representations of the environment and typically do not scale well. We utilize multiple hypothesis trees to derive a probabilistic data association for semantic measurements by means of position, instance and class to create a semantic representation. We propose an optimized mapping method and make use of a pose graph to derive a novel semantic SLAM solution. Furthermore, we show that semantic covisibility graphs allow for a precise place recognition in urban environments. We verify our approach using real-world outdoor dataset and demonstrate an average drift reduction of 33 % w.r.t. the raw odometry source. Moreover, our approach produces 55 % less hypotheses on average than a regular multiple hypotheses approach.
Extractive Opinion Summarization in Quantized Transformer Spaces
Venue: arXiv cs.CL 2020
Year: 2020

We present the Quantized Transformer (QT), an unsupervised system for extractive opinion summarization. QT is inspired by Vector-Quantized Variational Autoencoders, which we repurpose for popularity-driven summarization. It uses a clustering interpretation of the quantized space and a novel extraction algorithm to discover popular opinions among hundreds of reviews, a significant step towards opinion summarization of practical scope. In addition, QT enables controllable summarization without further training, by utilizing properties of the quantized space to extract aspect-specific summaries. We also make publicly available SPACE, a large-scale evaluation benchmark for opinion summarizers, comprising general and aspect-specific summaries for 50 hotels. Experiments demonstrate the promise of our approach, which is validated by human studies where judges showed clear preference for our method over competitive baselines.
Split: Inferring Unobserved Event Probabilities for Disentangling Brand-Customer Interactions
Venue: arXiv cs.LG 2020
Year: 2020

Often, data contains only composite events composed of multiple events, some observed and some unobserved. For example, search ad click is observed by a brand, whereas which customers were shown a search ad - an actionable variable - is often not observed. In such cases, inference is not possible on unobserved event. This occurs when a marketing action is taken over earned and paid digital channels. Similar setting arises in numerous datasets where multiple actors interact. One approach is to use the composite event as a proxy for the unobserved event of interest. However, this leads to invalid inference. This paper takes a direct approach whereby an event of interest is identified based on information on the composite event and aggregate data on composite events (e.g. total number of search ads shown). This work contributes to the literature by proving identification of the unobserved events' probabilities up to a scalar factor under mild condition. We propose an approach to identify the scalar factor by using aggregate data that is usually available from earned and paid channels. The factor is identified by adding a loss term to the usual cross-entropy loss. We validate the approach on three synthetic datasets. In addition, the approach is validated on a real marketing problem where some observed events are hidden from the algorithm for validation. The proposed modification to the cross-entropy loss function improves the average performance by 46%.
Accomplice Manipulation of the Deferred Acceptance Algorithm
Venue: arXiv cs.GT 2020
Year: 2020

The deferred acceptance algorithm is an elegant solution to the stable matching problem that guarantees optimality and truthfulness for one side of the market. Despite these desirable guarantees, it is susceptible to strategic misreporting of preferences by the agents on the other side. We study a novel model of strategic behavior under the deferred acceptance algorithm: manipulation through an accomplice. Here, an agent on the proposed-to side (say, a woman) partners with an agent on the proposing side -- an accomplice -- to manipulate on her behalf (possibly at the expense of worsening his match). We show that the optimal manipulation strategy for an accomplice comprises of promoting exactly one woman in his true list (i.e., an inconspicuous manipulation). This structural result immediately gives a polynomial-time algorithm for computing an optimal accomplice manipulation. We also study the conditions under which the manipulated matching is stable with respect to the true preferences. Our experimental results show that accomplice manipulation outperforms self manipulation both in terms of the frequency of occurrence as well as the quality of matched partners.
Big Green at WNUT 2020 Shared Task-1: Relation Extraction as Contextualized Sequence Classification
Venue: arXiv cs.CL 2020
Year: 2020

Relation and event extraction is an important task in natural language processing. We introduce a system which uses contextualized knowledge graph completion to classify relations and events between known entities in a noisy text environment. We report results which show that our system is able to effectively extract relations and events from a dataset of wet lab protocols.
CoShaRP: A Convex Program for Single-shot Tomographic Shape Sensing
Venue: arXiv cs.CV 2020
Year: 2020

We introduce single-shot X-ray tomography that aims to estimate the target image from a single cone-beam projection measurement. This linear inverse problem is extremely under-determined since the measurements are far fewer than the number of unknowns. Moreover, it is more challenging than conventional tomography where a sufficiently large number of projection angles forms the measurements, allowing for a simple inversion process. However, single-shot tomography becomes less severe if the target image is only composed of known shapes. Hence, the shape prior transforms a linear ill-posed image estimation problem to a non-linear problem of estimating the roto-translations of the shapes. In this paper, we circumvent the non-linearity by using a dictionary of possible roto-translations of the shapes. We propose a convex program CoShaRP to recover the dictionary-coefficients successfully. CoShaRP relies on simplex-type constraint and can be solved quickly using a primal-dual algorithm. The numerical experiments show that CoShaRP recovers shapes stably from moderately noisy measurements.
Pattern Morphing for Efficient Graph Mining
Venue: arXiv cs.DC 2020
Year: 2020

Graph mining applications analyze the structural properties of large graphs, and they do so by finding subgraph isomorphisms, which makes them computationally intensive. Existing graph mining techniques including both custom graph mining applications and general-purpose graph mining systems, develop efficient execution plans to speed up the exploration of the given query patterns that represent subgraph structures of interest. In this paper, we step beyond the traditional philosophy of optimizing the execution plans for a given set of patterns, and exploit the sub-structural similarities across different query patterns. We propose Pattern Morphing, a technique that enables structure-aware algebra over patterns to accurately infer the results for a given set of patterns using the results of a completely different set of patterns that are less expensive to compute. Pattern morphing "morphs" (or converts) a given set of query patterns into alternative patterns, while retaining full equivalency. It is a general technique that supports various operations over matches of a pattern beyond just counting (e.g., support calculation, enumeration, etc.), making it widely applicable to various graph mining applications like Motif Counting and Frequent Subgraph Mining. Since pattern morphing mainly transforms query patterns before their exploration starts, it can be easily incorporated in existing general-purpose graph mining systems. We evaluate the effectiveness of pattern morphing by incorporating it in Peregrine, a recent state-of-the-art graph mining system, and show that pattern morphing significantly improves the performance of different graph mining applications.
TADO: Time-varying Attention with Dual-Optimizer Model
Venue: arXiv cs.IR 2020
Year: 2020

The review-based recommender systems are commonly utilized to measure users preferences towards different items. In this paper, we focus on addressing three main problems existing in the review-based methods. Firstly, these methods suffer from the class-imbalanced problem where rating levels with lower proportions will be ignored to some extent. Thus, their performance on relatively rare rating levels is unsatisfactory. As the first attempt in this field to address this problem, we propose a flexible dual-optimizer model to gain robustness from both regression loss and classification loss. Secondly, to address the problem caused by the insufficient contextual information extraction ability of word embedding, we first introduce BERT into the review-based method to improve the performance of the semantic analysis. Thirdly, the existing methods ignore the feature information of the time-varying user preferences. Therefore, we propose a time-varying feature extraction module with bidirectional long short-term memory and multi-scale convolutional neural network. Afterward, an interaction component is proposed to further summarize the contextual information of the user-item pairs. To verify the effectiveness of the proposed TADO, we conduct extensive experiments on 23 benchmark datasets selected from Amazon Product Reviews. Compared with several recently proposed state-of-the-art methods, our model obtains significant gain over ALFM, MPCN, and ANR averagely with 20.98\%, 9.84\%, and 15.46\%, respectively. Further analysis proves the necessity of jointly using the proposed components in TADO.
Synthetic Data: Opening the data floodgates to enable faster, more directed development of machine learning methods
Venue: arXiv cs.LG 2020
Year: 2020

Many ground-breaking advancements in machine learning can be attributed to the availability of a large volume of rich data. Unfortunately, many large-scale datasets are highly sensitive, such as healthcare data, and are not widely available to the machine learning community. Generating synthetic data with privacy guarantees provides one such solution, allowing meaningful research to be carried out "at scale" - by allowing the entirety of the machine learning community to potentially accelerate progress within a given field. In this article, we provide a high-level view of synthetic data: what it means, how we might evaluate it and how we might use it.
Class Clown: Data Redaction in Machine Unlearning at Enterprise Scale
Venue: arXiv cs.CR 2020
Year: 2020

Individuals are gaining more control of their personal data through recent data privacy laws such the General Data Protection Regulation and the California Consumer Privacy Act. One aspect of these laws is the ability to request a business to delete private information, the so called "right to be forgotten" or "right to erasure". These laws have serious financial implications for companies and organizations that train large, highly accurate deep neural networks (DNNs) using these valuable consumer data sets. However, a received redaction request poses complex technical challenges on how to comply with the law while fulfilling core business operations. We introduce a DNN model lifecycle maintenance process that establishes how to handle specific data redaction requests and minimize the need to completely retrain the model. Our process is based upon the membership inference attack as a compliance tool for every point in the training set. These attack models quantify the privacy risk of all training data points and form the basis of follow-on data redaction from an accurate deployed model; excision is implemented through incorrect label assignment within incremental model updates.
A SAT-based Resolution of Lam's Problem
Venue: arXiv cs.DM 2020
Year: 2020

In 1989, computer searches by Lam, Thiel, and Swiercz experimentally resolved Lam's problem from projective geometry$\unicode{x2014}$the long-standing problem of determining if a projective plane of order ten exists. Both the original search and an independent verification in 2011 discovered no such projective plane. However, these searches were each performed using highly specialized custom-written code and did not produce nonexistence certificates. In this paper, we resolve Lam's problem by translating the problem into Boolean logic and use satisfiability (SAT) solvers to produce nonexistence certificates that can be verified by a third party. Our work uncovered consistency issues in both previous searches$\unicode{x2014}$highlighting the difficulty of relying on special-purpose search code for nonexistence results.
RAMPVIS: Towards a New Methodology for Developing Visualisation Capabilities for Large-scale Emergency Responses
Venue: arXiv cs.HC 2020
Year: 2020

The effort for combating the COVID-19 pandemic around the world has resulted in a huge amount of data, e.g., from testing, contact tracing, modelling, treatment, vaccine trials, and more. In addition to numerous challenges in epidemiology, healthcare, biosciences, and social sciences, there has been an urgent need to develop and provide visualisation and visual analytics (VIS) capacities to support emergency responses under difficult operational conditions. In this paper, we report the experience of a group of VIS volunteers who have been working in a large research and development consortium and providing VIS support to various observational, analytical, model-developmental and disseminative tasks. In particular, we describe our approaches to the challenges that we have encountered in requirements analysis, data acquisition, visual design, software design, system development, team organisation, and resource planning. By reflecting on our experience, we propose a set of recommendations as the first step towards a methodology for developing and providing rapid VIS capacities to support emergency responses.
Concept Drift and Covariate Shift Detection Ensemble with Lagged Labels
Venue: arXiv cs.AI 2020
Year: 2020

In model serving, having one fixed model during the entire often life-long inference process is usually detrimental to model performance, as data distribution evolves over time, resulting in lack of reliability of the model trained on historical data. It is important to detect changes and retrain the model in time. The existing methods generally have three weaknesses: 1) using only classification error rate as signal, 2) assuming ground truth labels are immediately available after features from samples are received and 3) unable to decide what data to use to retrain the model when change occurs. We address the first problem by utilizing six different signals to capture a wide range of characteristics of data, and we address the second problem by allowing lag of labels, where labels of corresponding features are received after a lag in time. For the third problem, our proposed method automatically decides what data to use to retrain based on the signals. Extensive experiments on structured and unstructured data for different type of data changes establish that our method consistently outperforms the state-of-the-art methods by a large margin.