OpenRaiser/Intern-Atlas huggingface dataset:
Simulating Data Access Profiles of Computational Jobs in Data Grids
Venue: arXiv cs.DC 2019
Year: 2019

The data access patterns of applications running in computing grids are changing due to the recent proliferation of high speed local and wide area networks. The data-intensive jobs are no longer strictly required to run at the computing sites, where the respective input data are located. Instead, jobs may access the data employing arbitrary combinations of data-placement, stage-in and remote data access. These data access profiles exhibit partially non-overlapping throughput bottlenecks. This fact can be exploited in order to minimize the time jobs spend waiting for input data. In this work we present a novel grid computing simulator, which puts a heavy emphasis on the various data access profiles. The fundamental assumptions underlying our simulator are justified by empirical experiments performed in the Worldwide LHC Computing Grid (WLCG) at CERN. We demonstrate how to calibrate the simulator parameters in accordance with the true system using posterior inference with likelihood-free Markov Chain Monte Carlo. Thereafter, we validate the simulator's output with respect to an authentic production workload from WLCG, demonstrating its remarkable accuracy.
SceneFlowFields++: Multi-frame Matching, Visibility Prediction, and Robust Interpolation for Scene Flow Estimation
Venue: arXiv cs.CV 2019
Year: 2019

State-of-the-art scene flow algorithms pursue the conflicting targets of accuracy, run time, and robustness. With the successful concept of pixel-wise matching and sparse-to-dense interpolation, we push the limits of scene flow estimation. Avoiding strong assumptions on the domain or the problem yields a more robust algorithm. This algorithm is fast because we avoid explicit regularization during matching, which allows an efficient computation. Using image information from multiple time steps and explicit visibility prediction based on previous results, we achieve competitive performances on different data sets. Our contributions and results are evaluated in comparative experiments. Overall, we present an accurate scene flow algorithm that is faster and more generic than any individual benchmark leader.
Multi-Task Learning with Contextualized Word Representations for Extented Named Entity Recognition
Venue: arXiv cs.CL 2019
Year: 2019

Fine-Grained Named Entity Recognition (FG-NER) is critical for many NLP applications. While classical named entity recognition (NER) has attracted a substantial amount of research, FG-NER is still an open research domain. The current state-of-the-art (SOTA) model for FG-NER relies heavily on manual efforts for building a dictionary and designing hand-crafted features. The end-to-end framework which achieved the SOTA result for NER did not get the competitive result compared to SOTA model for FG-NER. In this paper, we investigate how effective multi-task learning approaches are in an end-to-end framework for FG-NER in different aspects. Our experiments show that using multi-task learning approaches with contextualized word representation can help an end-to-end neural network model achieve SOTA results without using any additional manual effort for creating data and designing features.
BUT-FIT at SemEval-2019 Task 7: Determining the Rumour Stance with Pre-Trained Deep Bidirectional Transformers
Venue: arXiv cs.CL 2019
Year: 2019

This paper describes our system submitted to SemEval 2019 Task 7: RumourEval 2019: Determining Rumour Veracity and Support for Rumours, Subtask A (Gorrell et al., 2019). The challenge focused on classifying whether posts from Twitter and Reddit support, deny, query, or comment a hidden rumour, truthfulness of which is the topic of an underlying discussion thread. We formulate the problem as a stance classification, determining the rumour stance of a post with respect to the previous thread post and the source thread post. The recent BERT architecture was employed to build an end-to-end system which has reached the F1 score of 61.67% on the provided test data. It finished at the 2nd place in the competition, without any hand-crafted features, only 0.2% behind the winner.
Coloring Big Graphs with AlphaGoZero
Venue: arXiv cs.AI 2019
Year: 2019

We show that recent innovations in deep reinforcement learning can effectively color very large graphs -- a well-known NP-hard problem with clear commercial applications. Because the Monte Carlo Tree Search with Upper Confidence Bound algorithm used in AlphaGoZero can improve the performance of a given heuristic, our approach allows deep neural networks trained using high performance computing (HPC) technologies to transform computation into improved heuristics with zero prior knowledge. Key to our approach is the introduction of a novel deep neural network architecture (FastColorNet) that has access to the full graph context and requires $O(V)$ time and space to color a graph with $V$ vertices, which enables scaling to very large graphs that arise in real applications like parallel computing, compilers, numerical solvers, and design automation, among others. As a result, we are able to learn new state of the art heuristics for graph coloring.
Unmasking Clever Hans Predictors and Assessing What Machines Really Learn
Venue: arXiv cs.AI 2019
Year: 2019

Current learning machines have successfully solved hard application problems, reaching high accuracy and displaying seemingly "intelligent" behavior. Here we apply recent techniques for explaining decisions of state-of-the-art learning machines and analyze various tasks from computer vision and arcade games. This showcases a spectrum of problem-solving behaviors ranging from naive and short-sighted, to well-informed and strategic. We observe that standard performance evaluation metrics can be oblivious to distinguishing these diverse problem solving behaviors. Furthermore, we propose our semi-automated Spectral Relevance Analysis that provides a practically effective way of characterizing and validating the behavior of nonlinear learning machines. This helps to assess whether a learned model indeed delivers reliably for the problem that it was conceived for. Furthermore, our work intends to add a voice of caution to the ongoing excitement about machine intelligence and pledges to evaluate and judge some of these recent successes in a more nuanced manner.
Deep MR Fingerprinting with total-variation and low-rank subspace priors
Venue: arXiv cs.CV 2019
Year: 2019

Deep learning (DL) has recently emerged to address the heavy storage and computation requirements of the baseline dictionary-matching (DM) for Magnetic Resonance Fingerprinting (MRF) reconstruction. Fed with non-iterated back-projected images, the network is unable to fully resolve spatially-correlated corruptions caused from the undersampling artefacts. We propose an accelerated iterative reconstruction to minimize these artefacts before feeding into the network. This is done through a convex regularization that jointly promotes spatio-temporal regularities of the MRF time-series. Except for training, the rest of the parameter estimation pipeline is dictionary-free. We validate the proposed approach on synthetic and in-vivo datasets.
Efficient Probabilistic Collision Detection for Non-Gaussian Noise Distributions
Venue: arXiv cs.RO 2019
Year: 2019

We present an efficient algorithm to compute tight upper bounds of collision probability between two objects with positional uncertainties, whose error distributions are represented with non-Gaussian forms. Our approach can handle noisy datasets from depth sensors, whose distributions may correspond to Truncated Gaussian, Weighted Samples, or Truncated Gaussian Mixture Model. We derive tight probability bounds for convex shapes and extend them to non-convex shapes using hierarchical representations. We highlight the benefits of our approach over prior probabilistic collision detection algorithms in terms of tighter bounds ($10$x) and improved running time ($3$x). Moreover, we use our tight bounds to design an efficient and accurate motion planning algorithm for a 7-DOF robot arm operating in tight scenarios with sensor and motion uncertainties.
Exploiting Population Activity Dynamics to Predict Urban Epidemiological Incidence
Venue: arXiv cs.CY 2019
Year: 2019

Ambulance services worldwide are of vital importance to population health. Timely responding to incidents by dispatching an ambulance vehicle to the location a call came from can offer significant benefits to patient care across a number of medical conditions. Moreover, identifying the reasons that drive ambulance activity at an area not only can improve the operational capacity of emergency services, but can lead to better policy design in healthcare. In this work, we analyse the temporal dynamics of 5.6 million ambulance calls across a region of 7 million residents in the UK. We identify characteristic temporal patterns featuring diurnal and weekly cycles in ambulance call activity. These patterns are stable over time and across geographies. Using a dataset sourced from location intelligence platform Foursquare, we establish a link between the spatio-temporal dynamics of mobile users engaging with urban activities locally and emergency incidents. We use this information to build a novel metric that assesses the health risk of a geographic area in terms of its propensity to yield ambulance calls. Formulating then an online classification task where the goal becomes to identify which regions will need an ambulance at a given time, we demonstrate how semantic information about real world places crowdsourced through online platforms, can become a useful source of information in understanding and predicting regional epidemiological trends.
On the extension complexity of scheduling
Venue: arXiv cs.DS 2019
Year: 2019

Linear programming is a powerful method in combinatorial optimization with many applications in theory and practice. For solving a linear program quickly it is desirable to have a formulation of small size for the given problem. A useful approach for this is the construction of an extended formulation, which is a linear program in a higher dimensional space whose projection yields the original linear program. For many problems it is known that a small extended formulation cannot exist. However, most of these problems are either $\mathsf{NP}$-hard (like TSP), or only quite complicated polynomial time algorithms are known for them (like for the matching problem). In this work we study the minimum makespan problem on identical machines in which we want to assign a set of $n$ given jobs to $m$ machines in order to minimize the maximum load over the machines. We prove that the canonical formulation for this problem has extension complexity $2^{Ω(n/\log n)}$, even if each job has size 1 or 2 and the optimal makespan is 2. This is a case that a trivial greedy algorithm can solve optimally! For the more powerful configuration integer program, we even prove a lower bound of $2^{Ω(n)}$. On the other hand, we show that there is an abstraction of the configuration integer program admitting an extended formulation of size $f(\text{opt})\cdot \text{poly}(n,m)$. In addition, we give an $O(\log n)$-approximate integral formulation of polynomial size, even for arbitrary processing times and for the far more general setting of unrelated machines.
Ordinal Distance Metric Learning with MDS for Image Ranking
Venue: arXiv cs.LG 2019
Year: 2019

Image ranking is to rank images based on some known ranked images. In this paper, we propose an improved linear ordinal distance metric learning approach based on the linear distance metric learning model. By decomposing the distance metric $A$ as $L^TL$, the problem can be cast as looking for a linear map between two sets of points in different spaces, meanwhile maintaining some data structures. The ordinal relation of the labels can be maintained via classical multidimensional scaling, a popular tool for dimension reduction in statistics. A least squares fitting term is then introduced to the cost function, which can also maintain the local data structure. The resulting model is an unconstrained problem, and can better fit the data structure. Extensive numerical results demonstrate the improvement of the new approach over the linear distance metric learning model both in speed and ranking performance.
A Framework for Decoding Event-Related Potentials from Text
Venue: arXiv cs.CL 2019
Year: 2019

We propose a novel framework for modeling event-related potentials (ERPs) collected during reading that couples pre-trained convolutional decoders with a language model. Using this framework, we compare the abilities of a variety of existing and novel sentence processing models to reconstruct ERPs. We find that modern contextual word embeddings underperform surprisal-based models but that, combined, the two outperform either on its own.
Deep Adversarial Network Alignment
Venue: arXiv cs.SI 2019
Year: 2019

Network alignment, in general, seeks to discover the hidden underlying correspondence between nodes across two (or more) networks when given their network structure. However, most existing network alignment methods have added assumptions of additional constraints to guide the alignment, such as having a set of seed node-node correspondences across the networks or the existence of side-information. Instead, we seek to develop a general network alignment algorithm that makes no additional assumptions. Recently, network embedding has proven effective in many network analysis tasks, but embeddings of different networks are not aligned. Thus, we present our Deep Adversarial Network Alignment (DANA) framework that first uses deep adversarial learning to discover complex mappings for aligning the embedding distributions of the two networks. Then, using our learned mapping functions, DANA performs an efficient nearest neighbor node alignment. We perform experiments on real world datasets to show the effectiveness of our framework for first aligning the graph embedding distributions and then discovering node alignments that outperform existing methods.
Multiple Constrained Routing Algorithms in Large-Scaled Software Defined Networks
Venue: arXiv cs.NI 2019
Year: 2019

In this paper, we consider the bandwidth-delay-hop constrained routing problem in large-scaled software defined networks. A number of demands, each of which specifies a source vertex and a sink vertex, are required to route in a given network. We are asked to select a subset of demands, and assign a routing path for each selected demand without violating the hop and delay constraints, while assuring that the bandwidth occupied in each edge is not beyond its capacity. The goal is to maximize the throughput (the total bandwidth) of the selected demands. We develop an efficient heuristic algorithm for the problem, which consists of three main steps, namely, computing feasible paths for each demand, sorting the demands with some priority rules, selecting a path for each demand. The algorithm is tested with networks of actual sizes and topologies, generated by Huawei Technologies Company. The experiments show that the proposed approach outperforms existing algorithms both in throughput and in running time. In the experiments, our algorithm achieves more than 90\% of the total bandwidth of the given demands within 10 seconds. Moreover, a large part of our algorithm can run in parallel which largely speeds up the process when using multi-core processors.
CN-Probase: A Data-driven Approach for Large-scale Chinese Taxonomy Construction
Venue: arXiv cs.CL 2019
Year: 2019

Taxonomies play an important role in machine intelligence. However, most well-known taxonomies are in English, and non-English taxonomies, especially Chinese ones, are still very rare. In this paper, we focus on automatic Chinese taxonomy construction and propose an effective generation and verification framework to build a large-scale and high-quality Chinese taxonomy. In the generation module, we extract isA relations from multiple sources of Chinese encyclopedia, which ensures the coverage. To further improve the precision of taxonomy, we apply three heuristic approaches in verification module. As a result, we construct the largest Chinese taxonomy with high precision about 95% called CN-Probase. Our taxonomy has been deployed on Aliyun, with over 82 million API calls in six months.
Backscatter Data Collection with Unmanned Ground Vehicle: Mobility Management and Power Allocation
Venue: arXiv cs.IT 2019
Year: 2019

Collecting data from massive Internet of Things (IoT) devices is a challenging task, since communication circuits are power-demanding while energy supply at IoT devices is limited. To overcome this challenge, backscatter communication emerges as a promising solution as it eliminates radio frequency components in IoT devices. Unfortunately, the transmission range of backscatter communication is short. To facilitate backscatter communication, this work proposes to integrate unmanned ground vehicle (UGV) with backscatter data collection. With such a scheme, the UGV could improve the communication quality by approaching various IoT devices. However, moving also costs energy consumption and a fundamental question is: what is the right balance between spending energy on moving versus on communication? To answer this question, this paper studies energy minimization under a joint graph mobility and backscatter communication model. With the joint model, the mobility management and power allocation problem unfortunately involves nonlinear coupling between discrete variables brought by mobility and continuous variables brought by communication. Despite the optimization challenges, an algorithm that theoretically achieves the minimum energy consumption is derived, and it leads to automatic trade-off between spending energy on moving versus on communication in the UGV backscatter system. Simulation results show that if the noise power is small (e.g., -100 dBm), the UGV should collect the data with small movements. However, if the noise power is increased to a larger value (e.g., -60 dBm), the UGV should spend more motion energy to get closer to IoT users.
Distributed Byzantine Tolerant Stochastic Gradient Descent in the Era of Big Data
Venue: arXiv cs.LG 2019
Year: 2019

The recent advances in sensor technologies and smart devices enable the collaborative collection of a sheer volume of data from multiple information sources. As a promising tool to efficiently extract useful information from such big data, machine learning has been pushed to the forefront and seen great success in a wide range of relevant areas such as computer vision, health care, and financial market analysis. To accommodate the large volume of data, there is a surge of interest in the design of distributed machine learning, among which stochastic gradient descent (SGD) is one of the mostly adopted methods. Nonetheless, distributed machine learning methods may be vulnerable to Byzantine attack, in which the adversary can deliberately share falsified information to disrupt the intended machine learning procedures. Therefore, two asynchronous Byzantine tolerant SGD algorithms are proposed in this work, in which the honest collaborative workers are assumed to store the model parameters derived from their own local data and use them as the ground truth. The proposed algorithms can deal with an arbitrary number of Byzantine attackers and are provably convergent. Simulation results based on a real-world dataset are presented to verify the theoretical results and demonstrate the effectiveness of the proposed algorithms.
Counting to Ten with Two Fingers: Compressed Counting with Spiking Neurons
Venue: arXiv cs.NE 2019
Year: 2019

We consider the task of measuring time with probabilistic threshold gates implemented by bio-inspired spiking neurons. In the model of spiking neural networks, network evolves in discrete rounds, where in each round, neurons fire in pulses in response to a sufficiently high membrane potential. This potential is induced by spikes from neighboring neurons that fired in the previous round, which can have either an excitatory or inhibitory effect. We first consider a deterministic implementation of a neural timer and show that $Θ(\log t)$ (deterministic) threshold gates are both sufficient and necessary. This raised the question of whether randomness can be leveraged to reduce the number of neurons. We answer this question in the affirmative by considering neural timers with spiking neurons where the neuron $y$ is required to fire for $t$ consecutive rounds with probability at least $1-δ$, and should stop firing after at most $2t$ rounds with probability $1-δ$ for some input parameter $δ\in (0,1)$. Our key result is a construction of a neural timer with $O(\log\log 1/δ)$ spiking neurons. Interestingly, this construction uses only one spiking neuron, while the remaining neurons can be deterministic threshold gates. We complement this construction with a matching lower bound of $Ω(\min\{\log\log 1/δ, \log t\})$ neurons. This provides the first separation between deterministic and randomized constructions in the setting of spiking neural networks. Finally, we demonstrate the usefulness of compressed counting networks for synchronizing neural networks.
Interference Management in NOMA-based Fog-Radio Access Networks via Joint Scheduling and Power Adaptation
Venue: arXiv cs.NI 2019
Year: 2019

Non-Orthogonal Multiple Access (NOMA) and Fog Radio Access Networks (FRAN) are promising candidates within the 5G and beyond systems. This work examines the benefit of adopting NOMA in an FRAN architecture with constrained capacity fronthaul. The paper proposes methods for optimizing joint scheduling and power adaptation in the downlink of a NOMA-based FRAN with multiple resource blocks (RB). We consider a mixed-integer optimization problem which maximizes a network-wide rate-based utility function subject to fronthaul-capacity constraints, so as to determine i) the user-to-RB assignment, ii) the allocated power to each RB, and iii) the power split levels of the NOMA users in each RB. The paper proposes a feasible decoupled solution for such non-convex optimization problem using a three-step hybrid centralized/distributed approach. The proposed solution complies with FRAN operation that aims to partially shift the network control to the FAPs, so as to overcome delays due to fronthaul rate constraints. The paper proposes and compares two distinct methods for solving the assignment problem, namely the Hungarian method, and the Multiple Choice Knapsack method. The power allocation and the NOMA power split optimization, on the other hand, are solved using the alternating direction method of multipliers (ADMM). Simulations results illustrate the advantages of the proposed methods compared to different baseline schemes including the conventional Orthogonal Multiple Access (OMA), for different utility functions and different network environments.