OpenRaiser/Intern-Atlas huggingface dataset:
Weighted Reservoir Sampling from Distributed Streams
Venue: arXiv cs.DS 2019
Year: 2019

We consider message-efficient continuous random sampling from a distributed stream, where the probability of inclusion of an item in the sample is proportional to a weight associated with the item. The unweighted version, where all weights are equal, is well studied, and admits tight upper and lower bounds on message complexity. For weighted sampling with replacement, there is a simple reduction to unweighted sampling with replacement. However, in many applications the stream has only a few heavy items which may dominate a random sample when chosen with replacement. Weighted sampling \textit{without replacement} (weighted SWOR) eludes this issue, since such heavy items can be sampled at most once. In this work, we present the first message-optimal algorithm for weighted SWOR from a distributed stream. Our algorithm also has optimal space and time complexity. As an application of our algorithm for weighted SWOR, we derive the first distributed streaming algorithms for tracking \textit{heavy hitters with residual error}. Here the goal is to identify stream items that contribute significantly to the residual stream, once the heaviest items are removed. Residual heavy hitters generalize the notion of $\ell_1$ heavy hitters and are important in streams that have a skewed distribution of weights. In addition to the upper bound, we also provide a lower bound on the message complexity that is nearly tight up to a $\log(1/ε)$ factor. Finally, we use our weighted sampling algorithm to improve the message complexity of distributed $L_1$ tracking, also known as count tracking, which is a widely studied problem in distributed streaming. We also derive a tight message lower bound, which closes the message complexity of this fundamental problem.
A note on Cunningham's algorithm for matroid intersection
Venue: arXiv cs.DS 2019
Year: 2019

In the matroid intersection problem, we are given two matroids of rank $r$ on a common ground set $E$ of $n$ elements and the goal is to find the maximum set that is independent in both matroids. In this note, we show that Cunningham's algorithm for matroid intersection can be implemented to use $O(nr\log^2(r))$ independent oracle calls.
Accelerated Neural Networks on OpenCL Devices Using SYCL-DNN
Venue: arXiv cs.LG 2019
Year: 2019

Over the past few years machine learning has seen a renewed explosion of interest, following a number of studies showing the effectiveness of neural networks in a range of tasks which had previously been considered incredibly hard. Neural networks' effectiveness in the fields of image recognition and natural language processing stems primarily from the vast amounts of data available to companies and researchers, coupled with the huge amounts of compute power available in modern accelerators such as GPUs, FPGAs and ASICs. There are a number of approaches available to developers for utilizing GPGPU technologies such as SYCL, OpenCL and CUDA, however many applications require the same low level mathematical routines. Libraries dedicated to accelerating these common routines allow developers to easily make full use of the available hardware without requiring low level knowledge of the hardware themselves, however such libraries are often provided by hardware manufacturers for specific hardware such as cuDNN for Nvidia hardware or MIOpen for AMD hardware. SYCL-DNN is a new open-source library dedicated to providing accelerated routines for neural network operations which are hardware and vendor agnostic. Built on top of the SYCL open standard and written entirely in standard C++, SYCL-DNN allows a user to easily accelerate neural network code for a wide range of hardware using a modern C++ interface. The library is tested on AMD's OpenCL for GPU, Intel's OpenCL for CPU and GPU, ARM's OpenCL for Mali GPUs as well as ComputeAorta's OpenCL for R-Car CV engine and host CPU. In this talk we will present performance figures for SYCL-DNN on this range of hardware, and discuss how high performance was achieved on such a varied set of accelerators with such different hardware features.
Relational Action Forecasting
Venue: arXiv cs.CV 2019
Year: 2019

This paper focuses on multi-person action forecasting in videos. More precisely, given a history of H previous frames, the goal is to detect actors and to predict their future actions for the next T frames. Our approach jointly models temporal and spatial interactions among different actors by constructing a recurrent graph, using actor proposals obtained with Faster R-CNN as nodes. Our method learns to select a subset of discriminative relations without requiring explicit supervision, thus enabling us to tackle challenging visual data. We refer to our model as Discriminative Relational Recurrent Network (DRRN). Evaluation of action prediction on AVA demonstrates the effectiveness of our proposed method compared to simpler baselines. Furthermore, we significantly improve performance on the task of early action classification on J-HMDB, from the previous SOTA of 48% to 60%.
The Fault-Tolerant Metric Dimension of Cographs
Venue: arXiv cs.DS 2019
Year: 2019

A vertex set $U \subseteq V$ of an undirected graph $G=(V,E)$ is a \textit{resolving set} for $G$ if for every two distinct vertices $u,v \in V$ there is a vertex $w \in U$ such that the distance between $u$ and $w$ and the distance between $v$ and $w$ are different. A resolving set $U$ is {\em fault-tolerant} if for every vertex $u\in U$ set $U\setminus \{u\}$ is still a resolving set. {The \em (fault-tolerant) Metric Dimension} of $G$ is the size of a smallest (fault-tolerant) resolving set for $G$. The {\em weighted (fault-tolerant) Metric Dimension} for a given cost function $c: V \longrightarrow \mathbb{R}_+$ is the minimum weight of all (fault-tolerant) resolving sets. Deciding whether a given graph $G$ has (fault-tolerant) Metric Dimension at most $k$ for some integer $k$ is known to be NP-complete. The weighted fault-tolerant Metric Dimension problem has not been studied extensively so far. In this paper we show that the weighted fault-tolerant metric dimension problem can be solved in linear time on cographs.
A High-Performance Energy Management System based on Evolving Graph
Venue: arXiv cs.DC 2019
Year: 2019

As the fast growth and large integration of distributed generation, renewable energy resource, energy storage system and load response, the modern power system operation becomes much more complicated with increasing uncertainties and frequent changes. Increased operation risks are introduced to the existing commercial Energy Management System (EMS), due to its limited computational capability. In this paper, a high-performance EMS analysis framework based on the evolving graph is developed. A power grid is first modeled as an evolving graph and then the power system dynamic analysis applications, like network topology processing (NTP), state estimation (SE), power flow (PF), and contingency analysis (CA), are efficiently implemented on the system evolving graph to build a high-performance EMS analysis framework. Its computation performance is field tested using a 2749-bus power system in Sichuan, China. The results illustrate that the proposed EMS remarkably speeds up the computation performance and reaches the goal of real-time power system analysis.
More barriers for rank methods, via a "numeric to symbolic" transfer
Venue: arXiv cs.CC 2019
Year: 2019

We prove new barrier results in arithmetic complexity theory, showing severe limitations of natural lifting (aka escalation) techniques. For example, we prove that even optimal rank lower bounds on $k$-tensors cannot yield non-trivial lower bounds on the rank of $d$-tensors, for any constant $d>k$. This significantly extends recent barrier results on the limits of (matrix) rank methods by Efremenko, Garg, Oliveira and Wigderson, which handles the (very important) case $k=2$. Our generalization requires the development of new technical tools and results in algebraic geometry, which are interesting in their own right and possibly applicable elsewhere. The basic issue they probe is the relation between numeric and symbolic rank of tensors, essential in the proofs of previous and current barriers. Our main technical result implies that for every symbolic $k$-tensor (namely one whose entries are polynomials in some set of variables), if the tensor rank is small for every evaluation of the variables, then it is small symbolically. This statement is obvious for $k=2$. To prove an analogous statement for $k>2$ we develop a "numeric to symbolic" transfer of algebraic relations to algebraic functions, somewhat in the spirit of the implicit function theorem. It applies in the general setting of inclusion of images of polynomial maps, in the form appearing in Raz's elusive functions approach to proving VP $\neq$ VNP. We give a toy application showing how our transfer theorem may be useful in pursuing this approach to prove arithmetic complexity lower bounds.
A Time-Segmented Consortium Blockchain for Robotic Event Registration
Venue: arXiv cs.RO 2019
Year: 2019

A blockchain, during its lifetime, records large amounts of data, that in a common usage its kept on its entirety. In a robotics environment, the old information is useful for human evaluation, or oracles interfacing with the blockchain but it is not useful for the robots that require only current information in order to continue their work. This causes a storage problem in blockchain nodes that have limited storage capacity, such as in the case of nodes attached to robots that are usually built around embedded solutions. This paper presents a time-segmentation solution for devices with limited storage capacity, integrated in a particular robot-directed blockchain called RobotChain. Results are presented regarding the proposed solution that show that the goal of restricting each node's capacity is reached without compromising all the benefits that arise from the use of blockchains in these contexts, and on the contrary, it allows for cheap nodes to use this blockchain, reduces storage costs and allows faster deployment of new nodes.
Data adaptation in HANDY economy-ideology model
Venue: arXiv cs.LG 2019
Year: 2019

The concept of mathematical modeling is widespread across almost all of the fields of contemporary science and engineering. Because of the existing necessity of predictions the behavior of natural phenomena, the researchers develop more and more complex models. However, despite their ability to better forecasting, the problem of an appropriate fitting ground truth data to those, high-dimensional and nonlinear models seems to be inevitable. In order to deal with this demanding problem the entire discipline of data assimilation has been developed. Basing on the Human and Nature Dynamics (HANDY) model, we have presented a detailed and comprehensive comparison of Approximate Bayesian Computation (classic data assimilation method) and a novelty approach of Supermodeling. Furthermore, with the usage of Sensitivity Analysis, we have proposed the methodology to reduce the number of coupling coefficients between submodels and as a consequence to increase the speed of the Supermodel converging. In addition, we have demonstrated that usage of Approximate Bayesian Computation method with the knowledge about parameters' sensitivities could result with satisfactory estimation of the initial parameters. However, we have also presented the mentioned methodology as unable to achieve similar predictions to Approximate Bayesian Computation. Finally, we have proved that Supermodeling with synchronization via the most sensitive variable could effect with the better forecasting for chaotic as well as more stable systems than the Approximate Bayesian Computation. What is more, we have proposed the adequate methodologies.
MFV: Application software for the visualization and characterization of the DC magnetic field distribution in circular coil systems
Venue: arXiv cs.CE 2019
Year: 2019

The characterization of the magnetic field distribution is essential in experiments and devices that use magnetic field coil systems. We present an open-source application software, MFV (Magnetic Field Visualizer), for the visualization of the distribution of the magnetic field produced by circular coil systems. MFV models, simulates, and plots the magnetic field of coil systems composed by any number of circular coils of any size placed symmetrically along the same axis. Therefore, any new design or well known coil system, such as the Helmholtz or the Maxwell coil, can be easily modeled and simulated using MFV. A graph of the homogeneity of the magnetic field can be also produced, showing the work region where the magnetic field is homogeneous according to a percentage of homogeneity given by the user. An standardized input and output file format is employed to facilitate the exchange and archiving of data. We include some results obtained using MFV, showing its applicability to characterize the magnetic field in different coil systems. Furthermore, the magnetic field results provided by MFV were validated by comparing them with results obtained experimentally in a Helmholtz coil system.
Automated Monitoring Cropland Using Remote Sensing Data: Challenges and Opportunities for Machine Learning
Venue: arXiv cs.CV 2019
Year: 2019

This paper provides an overview of how recent advances in machine learning and the availability of data from earth observing satellites can dramatically improve our ability to automatically map croplands over long period and over large regions. It discusses three applications in the domain of crop monitoring where ML approaches are beginning to show great promise. For each application, it highlights machine learning challenges, proposed approaches, and recent results. The paper concludes with discussion of major challenges that need to be addressed before ML approaches will reach their full potential for this problem of great societal relevance.
Polynomial Invariant Theory and Shape Enumerator of Self-Dual Codes in the NRT-Metric
Venue: arXiv cs.IT 2019
Year: 2019

In this paper we consider self-dual NRT-codes, that is, self-dual codes in the metric space endowed with the Niederreiter-Rosenbloom-Tsfasman (NRT-metric). We use polynomial invariant theory to describe the shape enumerator of a binary self-dual, doubly even self-dual, and doubly-doubly even self dual NRT-code $C\subseteq M_{n,2}(\mathbb{F}_{2})$. Motivated by these results we describe the number of invariant polinomials that we must find to describe the shape enumerator of a self-dual NRT-code of $M_{n,s}(\mathbb{F}_{2})$. We define the ordered flip of a matrix $A\in M_{k,ns}(\mathbb{F}_{q})$ and present some constructions of self-dual NRT-codes over $\mathbb{F}_{q}$. We further give an application of ordered flip to the classification of bidimensional self-dual NRT-codes.
L2AE-D: Learning to Aggregate Embeddings for Few-shot Learning with Meta-level Dropout
Venue: arXiv cs.LG 2019
Year: 2019

Few-shot learning focuses on learning a new visual concept with very limited labelled examples. A successful approach to tackle this problem is to compare the similarity between examples in a learned metric space based on convolutional neural networks. However, existing methods typically suffer from meta-level overfitting due to the limited amount of training tasks and do not normally consider the importance of the convolutional features of different examples within the same channel. To address these limitations, we make the following two contributions: (a) We propose a novel meta-learning approach for aggregating useful convolutional features and suppressing noisy ones based on a channel-wise attention mechanism to improve class representations. The proposed model does not require fine-tuning and can be trained in an end-to-end manner. The main novelty lies in incorporating a shared weight generation module that learns to assign different weights to the feature maps of different examples within the same channel. (b) We also introduce a simple meta-level dropout technique that reduces meta-level overfitting in several few-shot learning approaches. In our experiments, we find that this simple technique significantly improves the performance of the proposed method as well as various state-of-the-art meta-learning algorithms. Applying our method to few-shot image recognition using Omniglot and miniImageNet datasets shows that it is capable of delivering a state-of-the-art classification performance.
Collision-aware Task Assignment for Multi-Robot Systems
Venue: arXiv cs.RO 2019
Year: 2019

We propose a novel formulation of the collision-aware task assignment (CATA) problem and a decentralized auction-based algorithm to solve the problem with optimality bound. Using a collision cone, we predict potential collisions and introduce a binary decision variable into the local reward function for task bidding. We further improve CATA by implementing a receding collision horizon to address the stopping robot scenario, i.e. when robots are confined to their task location and become static obstacles to other moving robots. The auction-based algorithm encourages the robots to bid for tasks with collision mitigation considerations. We validate the improved task assignment solution with both simulation and experimental results, which show significant reduction of overlapping paths as well as deadlocks.
Reasoning about Block-based Cloud Storage Systems
Venue: arXiv cs.LO 2019
Year: 2019

Owing to the massive growth in the storage demands of big data, Cloud Storage Systems (CSSs) have been put forward to improve the storage capacity. Compared with traditional storage systems, CSSs have lots of advantages, such as higher capacity, lower cost, and easier scalability. But they are also with higher complexity. In order to ensure CSSs to be reliable, it is necessary to prove the correctness of CSSs management programs. In fact, we are going to verify Block-based Cloud Storage Systems (BCSSs), since BCSSs are the most popular CSSs. In this paper, the correctness of management programs in BCSSs have been proven, and a verification framework based on separation logic is proposed to finish the proven process. The main contributions are as follows. (1) A novel framework with two-tier heap structure is constructed to reflect the characteristics of BCSSs, and a modeling language is defined based on it. (2) Assertions based on separation logic is constructed to describe the properties of BCSSs. (3) The Hoare-style specifications are proposed to reason about the BCSSs. The results demonstrate that the correctness and reliability of BCSSs can be verified by the above proposed methods. Furthermore, the proposed specifications is sound in the application of reasoning about BCSSs.
Semi-Supervised Segmentation of Salt Bodies in Seismic Images using an Ensemble of Convolutional Neural Networks
Venue: arXiv cs.CV 2019
Year: 2019

Seismic image analysis plays a crucial role in a wide range of industrial applications and has been receiving significant attention. One of the essential challenges of seismic imaging is detecting subsurface salt structure which is indispensable for identification of hydrocarbon reservoirs and drill path planning. Unfortunately, exact identification of large salt deposits is notoriously difficult and professional seismic imaging often requires expert human interpretation of salt bodies. Convolutional neural networks (CNNs) have been successfully applied in many fields, and several attempts have been made in the field of seismic imaging. But the high cost of manual annotations by geophysics experts and scarce publicly available labeled datasets hinder the performance of the existing CNN-based methods. In this work, we propose a semi-supervised method for segmentation (delineation) of salt bodies in seismic images which utilizes unlabeled data for multi-round self-training. To reduce error amplification during self-training we propose a scheme which uses an ensemble of CNNs. We show that our approach outperforms state-of-the-art on the TGS Salt Identification Challenge dataset and is ranked the first among the 3234 competing methods.
Explaining Wrong Queries Using Small Examples
Venue: arXiv cs.DB 2019
Year: 2019

For testing the correctness of SQL queries, e.g., evaluating student submissions in a database course, a standard practice is to execute the query in question on some test database instance and compare its result with that of the correct query. Given two queries $Q_1$ and $Q_2$, we say that a database instance $D$ is a counterexample (for $Q_1$ and $Q_2$) if $Q_1(D)$ differs from $Q_2(D)$; such a counterexample can serve as an explanation of why $Q_1$ and $Q_2$ are not equivalent. While the test database instance may serve as a counterexample, it may be too large or complex to read and understand where the inequivalence comes from. Therefore, in this paper, given a known counterexample $D$ for $Q_1$ and $Q_2$, we aim to find the smallest counterexample $D' \subseteq D$ where $Q_1(D') \neq Q_2(D')$. The problem in general is NP-hard. We give a suite of algorithms for finding the smallest counterexample for different classes of queries, some more tractable than others. We also present an efficient provenance-based algorithm for SPJUD queries that uses a constraint solver, and extend it to more complex queries with aggregation, group-by, and nested queries. We perform extensive experiments indicating the effectiveness and scalability of our solution on student queries from an undergraduate database course and on queries from the TPC-H benchmark. We also report a user study from the course where we deployed our tool to help students with an assignment on relational algebra.
Private Pliable Index Coding
Venue: arXiv cs.IT 2019
Year: 2019

The Pliable Index CODing (PICOD) problem is a variant of the Index Coding (IC) problem, where the desired messages by the users, who are equipped with message side information, is part of the optimization. This paper studies the PICOD problem where users are subject to a privacy constraint. In particular, the following spacial class of private PICODs is investigated: 1) the side information structure is circular, and 2) each user can decode one and only one message. The first condition is a special case of the "circular-arc network topology hypergraph" class of PICOD studied in [Liu and D. Tuninetti, "Tight information theoretic converse results for some pliable index coding problems," ITW, 2018], for which an optimal solution was given without the privacy constraint. The second condition was first studied in [S. Sasi and B. S. Rajan, "On pliable index coding," arXiv:1901.05809] and was motivated by the need to keep content privacy is some distribution networks. This paper proposes both converse and achievable bounds. The proposed achievable scheme not only strictly outperforms the one in [S. Sasi and B. S. Rajan, "On pliable index coding," arXiv:1901.05809] for some values of the system parameters, but it is also information theoretically optimal in some settings. For the remaining cases, the proposed linear code is shown to require at most one more transmission than the converse bound derived by restricting the sender to only use linear codes.