OpenRaiser/Intern-Atlas huggingface dataset:
An Evaluation of Visualization Methods for Population Statistics Based on Choropleth Maps
Venue: arXiv cs.HC 2020
Year: 2020

We evaluate several augmentations to the choropleth map to convey additional information, including glyphs, 3D, cartograms, juxtaposed maps, and shading methods. While choropleth maps are a common method used to represent societal data, with multivariate data they can impede as much as improve understanding. In particular large, low population density regions often dominate the map and can mislead the viewer as to the message conveyed. Our results highlight the potential of 3D choropleth maps as well as the low accuracy of choropleth map tasks with multivariate data. We also introduce and evaluate popcharts, four techniques designed to show the density of population at a very fine scale on top of choropleth maps. All the data, results, and scripts are available from https://osf.io/8rxwg/.
Formal assessment of some properties of Context-Aware Systems
Venue: arXiv cs.FL 2020
Year: 2020

Context-Aware systems are becoming useful components in autonomic and monitoring applications and the assessment of their properties is an important step towards reliable implementation, especially in safety-critical applications. In this paper, using an avalanche/landslide alert system as a running example, we propose a technique, based on Boolean Control Networks, to verify that the system dynamics has stable equilibrium states, corresponding to constant inputs, and hence it does not exhibit oscillatory behaviors, and to establish other useful properties in order to implement a precise and timely alarm system.
Bionic Tracking: Using Eye Tracking to Track Biological Cells in Virtual Reality
Venue: arXiv cs.HC 2020
Year: 2020

We present Bionic Tracking, a novel method for solving biological cell tracking problems with eye tracking in virtual reality using commodity hardware. Using gaze data, and especially smooth pursuit eye movements, we are able to track cells in time series of 3D volumetric datasets. The problem of tracking cells is ubiquitous in developmental biology, where large volumetric microscopy datasets are acquired on a daily basis, often comprising hundreds or thousands of time points that span hours or days. The image data, however, is only a means to an end, and scientists are often interested in the reconstruction of cell trajectories and cell lineage trees. Reliably tracking cells in crowded three-dimensional space over many timepoints remains an open problem, and many current approaches rely on tedious manual annotation and curation. In our Bionic Tracking approach, we substitute the usual 2D point-and-click annotation to track cells with eye tracking in a virtual reality headset, where users simply have to follow a cell with their eyes in 3D space in order to track it. We detail the interaction design of our approach and explain the graph-based algorithm used to connect different time points, also taking occlusion and user distraction into account. We demonstrate our cell tracking method using the example of two different biological datasets. Finally, we report on a user study with seven cell tracking experts, demonstrating the benefits of our approach over manual point-and-click tracking.
Can a powerful neural network be a teacher for a weaker neural network?
Venue: arXiv cs.LG 2020
Year: 2020

The transfer learning technique is widely used to learning in one context and applying it to another, i.e. the capacity to apply acquired knowledge and skills to new situations. But is it possible to transfer the learning from a deep neural network to a weaker neural network? Is it possible to improve the performance of a weak neural network using the knowledge acquired by a more powerful neural network? In this work, during the training process of a weak network, we add a loss function that minimizes the distance between the features previously learned from a strong neural network with the features that the weak network must try to learn. To demonstrate the effectiveness and robustness of our approach, we conducted a large number of experiments using three known datasets and demonstrated that a weak neural network can increase its performance if its learning process is driven by a more powerful neural network.
Improved Bound for Matching in Random-Order Streams
Venue: arXiv cs.DS 2020
Year: 2020

We study the problem of computing an approximate maximum cardinality matching in the semi-streaming model when edges arrive in a \emph{random} order. In the semi-streaming model, the edges of the input graph G = (V,E) are given as a stream e_1, ..., e_m, and the algorithm is allowed to make a single pass over this stream while using $O(n \textrm{polylog}(n))$ space ($m = |E|$ and $n = |V|$). If the order of edges is adversarial, a simple single-pass greedy algorithm yields a $1/2$-approximation in $O(n)$ space; achieving a better approximation in adversarial streams remains an elusive open question. A line of recent work shows that one can improve upon the $1/2$-approximation if the edges of the stream arrive in a random order. The state of the art for this model is two-fold: Assadi et al. [SODA 2019] show how to compute a $2/3(\sim.66)$-approximate matching, but the space requirement is $O(n^{1.5} \textrm{polylog}(n))$. Very recently, Farhadi et al. [SODA 2020] presented an algorithm with the desired space usage of $O(n \textrm{polylog}(n))$, but a worse approximation ratio of $6/11(\sim.545)$, or $3/5(=.6)$ in bipartite graphs. In this paper, we present an algorithm that computes a $2/3(\sim.66)$-approximate matching using only $O(n \log(n))$ space, improving upon both results above. We also note that for adversarial streams, a lower bound of Kapralov [SODA 2013] shows that any algorithm that achieves a $1-1/e(\sim.63)$-approximation requires $(n^{1+Ω(1/\log\log(n))})$ space. Our result for random-order streams is the first to go beyond the adversarial-order lower bound, thus establishing that computing a maximum matching is provably easier in random-order streams.
Quantum arithmetic operations based on quantum Fourier transform on signed integers
Venue: arXiv cs.IT 2020
Year: 2020

The quantum Fourier transform (QFT) brings efficiency in many respects, especially usage of resource, for most operations on quantum computers. In this study, the existing QFT-based and non-QFT-based quantum arithmetic operations are examined. The capabilities of QFT-based addition and multiplication are improved with some modifications. The proposed operations are compared with the nearest quantum arithmetic operations. Furthermore, novel QFT-based subtraction, division and exponentiation operations are presented. The proposed arithmetic operations can perform nonmodular operations on all signed numbers without any limitation by using less resources. In addition, novel quantum circuits of two's complement, absolute value and comparison operations are also presented by using the proposed QFT-based addition and subtraction operations.
Optimal Scheduling of Age-centric Caching: Tractability and Computation
Venue: arXiv cs.DC 2020
Year: 2020

The notion of age of information (AoI) has become an important performance metric in network and control systems. Information freshness, represented by AoI, naturally arises in the context of caching. We address optimal scheduling of cache updates for a time-slotted system where the contents vary in size. There is limited capacity for the cache and for making content updates. Each content is associated with a utility function that is monotonically decreasing in the AoI. For this combinatorial optimization problem, we present the following contributions. First, we provide theoretical results settling the boundary of problem tractability. In particular, by a reformulation using network flows, we prove the boundary is essentially determined by whether or not the contents are of equal size. Second, we derive an integer linear formulation for the problem, of which the optimal solution can be obtained for small-scale scenarios. Next, via a mathematical reformulation, we derive a scalable optimization algorithm using repeated column generation. In addition, the algorithm computes a bound of global optimum, that can be used to assess the performance of any scheduling solution. Performance evaluation of large-scale scenarios demonstrates the strengths of the algorithm in comparison to a greedy schedule. Finally, we extend the applicability of our work to cyclic scheduling.
Defense of Word-level Adversarial Attacks via Random Substitution Encoding
Venue: arXiv cs.CL 2020
Year: 2020

The adversarial attacks against deep neural networks on computer vision tasks have spawned many new technologies that help protect models from avoiding false predictions. Recently, word-level adversarial attacks on deep models of Natural Language Processing (NLP) tasks have also demonstrated strong power, e.g., fooling a sentiment classification neural network to make wrong decisions. Unfortunately, few previous literatures have discussed the defense of such word-level synonym substitution based attacks since they are hard to be perceived and detected. In this paper, we shed light on this problem and propose a novel defense framework called Random Substitution Encoding (RSE), which introduces a random substitution encoder into the training process of original neural networks. Extensive experiments on text classification tasks demonstrate the effectiveness of our framework on defense of word-level adversarial attacks, under various base and attack models.
Eliciting User Preferences for Personalized Explanations for Video Summaries
Venue: arXiv cs.HC 2020
Year: 2020

Video summaries or highlights are a compelling alternative for exploring and contextualizing unprecedented amounts of video material. However, the summarization process is commonly automatic, non-transparent and potentially biased towards particular aspects depicted in the original video. Therefore, our aim is to help users like archivists or collection managers to quickly understand which summaries are the most representative for an original video. In this paper, we present empirical results on the utility of different types of visual explanations to achieve transparency for end users on how representative video summaries are, with respect to the original video. We consider four types of video summary explanations, which use in different ways the concepts extracted from the original video subtitles and the video stream, and their prominence. The explanations are generated to meet target user preferences and express different dimensions of transparency: concept prominence, semantic coverage, distance and quantity of coverage. In two user studies we evaluate the utility of the visual explanations for achieving transparency for end users. Our results show that explanations representing all of the dimensions have the highest utility for transparency, and consequently, for understanding the representativeness of video summaries.
A Parallel Optimal Task Allocation Mechanism for Large-Scale Mobile Edge Computing
Venue: arXiv cs.NI 2020
Year: 2020

We consider the problem of intelligent and efficient task allocation mechanism in large-scale mobile edge computing (MEC), which can reduce delay and energy consumption in a parallel and distributed optimization. In this paper, we study the joint optimization model to consider cooperative task management mechanism among mobile terminals (MT), macro cell base station (MBS), and multiple small cell base station (SBS) for large-scale MEC applications. We propose a parallel multi-block Alternating Direction Method of Multipliers (ADMM) based method to model both requirements of low delay and low energy consumption in the MEC system which formulates the task allocation under those requirements as a nonlinear 0-1 integer programming problem. To solve the optimization problem, we develop an efficient combination of conjugate gradient, Newton and linear search techniques based algorithm with Logarithmic Smoothing (for global variables updating) and the Cyclic Block coordinate Gradient Projection (CBGP, for local variables updating) methods, which can guarantee convergence and reduce computational complexity with a good scalability. Numerical results demonstrate the effectiveness of the proposed mechanism and it can effectively reduce delay and energy consumption for a large-scale MEC system.
When Ensembling Smaller Models is More Efficient than Single Large Models
Venue: arXiv cs.LG 2020
Year: 2020

Ensembling is a simple and popular technique for boosting evaluation performance by training multiple models (e.g., with different initializations) and aggregating their predictions. This approach is commonly reserved for the largest models, as it is commonly held that increasing the model size provides a more substantial reduction in error than ensembling smaller models. However, we show results from experiments on CIFAR-10 and ImageNet that ensembles can outperform single models with both higher accuracy and requiring fewer total FLOPs to compute, even when those individual models' weights and hyperparameters are highly optimized. Furthermore, this gap in improvement widens as models become large. This presents an interesting observation that output diversity in ensembling can often be more efficient than training larger models, especially when the models approach the size of what their dataset can foster. Instead of using the common practice of tuning a single large model, one can use ensembles as a more flexible trade-off between a model's inference speed and accuracy. This also potentially eases hardware design, e.g., an easier way to parallelize the model across multiple workers for real-time or distributed inference.
Global Table Extractor (GTE): A Framework for Joint Table Identification and Cell Structure Recognition Using Visual Context
Venue: arXiv cs.CV 2020
Year: 2020

Documents are often used for knowledge sharing and preservation in business and science, within which are tables that capture most of the critical data. Unfortunately, most documents are stored and distributed as PDF or scanned images, which fail to preserve logical table structure. Recent vision-based deep learning approaches have been proposed to address this gap, but most still cannot achieve state-of-the-art results. We present Global Table Extractor (GTE), a vision-guided systematic framework for joint table detection and cell structured recognition, which could be built on top of any object detection model. With GTE-Table, we invent a new penalty based on the natural cell containment constraint of tables to train our table network aided by cell location predictions. GTE-Cell is a new hierarchical cell detection network that leverages table styles. Further, we design a method to automatically label table and cell structure in existing documents to cheaply create a large corpus of training and test data. We use this to enhance PubTabNet with cell labels and create FinTabNet, real-world and complex scientific and financial datasets with detailed table structure annotations to help train and test structure recognition. Our framework surpasses previous state-of-the-art results on the ICDAR 2013 and ICDAR 2019 table competition in both table detection and cell structure recognition with a significant 5.8% improvement in the full table extraction system. Further experiments demonstrate a greater than 45% improvement in cell structure recognition when compared to a vanilla RetinaNet object detection model in our new out-of-domain FinTabNet.
Strong subalgebras and the Constraint Satisfaction Problem
Venue: arXiv cs.CC 2020
Year: 2020

In 2007 it was conjectured that the Constraint Satisfaction Problem (CSP) over a constraint language $Γ$ is tractable if and only if $Γ$ is preserved by a weak near-unanimity (WNU) operation. After many efforts and partial results, this conjecture was independently proved by Andrei Bulatov and the author in 2017. In this paper we consider one of two main ingredients of my proof, that is, strong subalgebras that allow us to reduce domains of the variables iteratively. To explain how this idea works we show the algebraic properties of strong subalgebras and provide self-contained proof of two important facts about the complexity of the CSP. First, we prove that if a constraint language is not preserved by a WNU operation then the corresponding CSP is NP-hard. Second, we characterize all constraint languages that can be solved by local consistency checking. Additionally, we characterize all idempotent algebras not having a WNU term of a concrete arity $n$, not having a WNU term, having WNU terms of all arities greater than 2. Most of the results presented in the paper are not new, but I believe this paper can help to understand my approach to CSP and the new self-contained proof of known facts will be also useful.
Intermediate-Task Transfer Learning with Pretrained Models for Natural Language Understanding: When and Why Does It Work?
Venue: arXiv cs.CL 2020
Year: 2020

While pretrained models such as BERT have shown large gains across natural language understanding tasks, their performance can be improved by further training the model on a data-rich intermediate task, before fine-tuning it on a target task. However, it is still poorly understood when and why intermediate-task training is beneficial for a given target task. To investigate this, we perform a large-scale study on the pretrained RoBERTa model with 110 intermediate-target task combinations. We further evaluate all trained models with 25 probing tasks meant to reveal the specific skills that drive transfer. We observe that intermediate tasks requiring high-level inference and reasoning abilities tend to work best. We also observe that target task performance is strongly correlated with higher-level abilities such as coreference resolution. However, we fail to observe more granular correlations between probing and target task performance, highlighting the need for further work on broad-coverage probing benchmarks. We also observe evidence that the forgetting of knowledge learned during pretraining may limit our analysis, highlighting the need for further work on transfer learning methods in these settings.
KLEJ: Comprehensive Benchmark for Polish Language Understanding
Venue: arXiv cs.CL 2020
Year: 2020

In recent years, a series of Transformer-based models unlocked major improvements in general natural language understanding (NLU) tasks. Such a fast pace of research would not be possible without general NLU benchmarks, which allow for a fair comparison of the proposed methods. However, such benchmarks are available only for a handful of languages. To alleviate this issue, we introduce a comprehensive multi-task benchmark for the Polish language understanding, accompanied by an online leaderboard. It consists of a diverse set of tasks, adopted from existing datasets for named entity recognition, question-answering, textual entailment, and others. We also introduce a new sentiment analysis task for the e-commerce domain, named Allegro Reviews (AR). To ensure a common evaluation scheme and promote models that generalize to different NLU tasks, the benchmark includes datasets from varying domains and applications. Additionally, we release HerBERT, a Transformer-based model trained specifically for the Polish language, which has the best average performance and obtains the best results for three out of nine tasks. Finally, we provide an extensive evaluation, including several standard baselines and recently proposed, multilingual Transformer-based models.
Stochastic Neighbor Embedding of Multimodal Relational Data for Image-Text Simultaneous Visualization
Venue: arXiv cs.LG 2020
Year: 2020

Multimodal relational data analysis has become of increasing importance in recent years, for exploring across different domains of data, such as images and their text tags obtained from social networking services (e.g., Flickr). A variety of data analysis methods have been developed for visualization; to give an example, t-Stochastic Neighbor Embedding (t-SNE) computes low-dimensional feature vectors so that their similarities keep those of the observed data vectors. However, t-SNE is designed only for a single domain of data but not for multimodal data; this paper aims at visualizing multimodal relational data consisting of data vectors in multiple domains with relations across these vectors. By extending t-SNE, we herein propose Multimodal Relational Stochastic Neighbor Embedding (MR-SNE), that (1) first computes augmented relations, where we observe the relations across domains and compute those within each of domains via the observed data vectors, and (2) jointly embeds the augmented relations to a low-dimensional space. Through visualization of Flickr and Animal with Attributes 2 datasets, proposed MR-SNE is compared with other graph embedding-based approaches; MR-SNE demonstrates the promising performance.
Are Emojis Emotional? A Study to Understand the Association between Emojis and Emotions
Venue: arXiv cs.CL 2020
Year: 2020

Given the growing ubiquity of emojis in language, there is a need for methods and resources that shed light on their meaning and communicative role. One conspicuous aspect of emojis is their use to convey affect in ways that may otherwise be non-trivial to achieve. In this paper, we seek to explore the connection between emojis and emotions by means of a new dataset consisting of human-solicited association ratings. We additionally conduct experiments to assess to what extent such associations can be inferred from existing data, such that similar associations can be predicted for a larger set of emojis. Our experiments show that this succeeds when high-quality word-level information is available.
Deep ConvLSTM with self-attention for human activity decoding using wearables
Venue: arXiv cs.HC 2020
Year: 2020

Decoding human activity accurately from wearable sensors can aid in applications related to healthcare and context awareness. The present approaches in this domain use recurrent and/or convolutional models to capture the spatio-temporal features from time-series data from multiple sensors. We propose a deep neural network architecture that not only captures the spatio-temporal features of multiple sensor time-series data but also selects, learns important time points by utilizing a self-attention mechanism. We show the validity of the proposed approach across different data sampling strategies on six public datasets and demonstrate that the self-attention mechanism gave a significant improvement in performance over deep networks using a combination of recurrent and convolution networks. We also show that the proposed approach gave a statistically significant performance enhancement over previous state-of-the-art methods for the tested datasets. The proposed methods open avenues for better decoding of human activity from multiple body sensors over extended periods of time. The code implementation for the proposed model is available at https://github.com/isukrit/encodingHumanActivity.
A Benchmark for Structured Procedural Knowledge Extraction from Cooking Videos
Venue: arXiv cs.CL 2020
Year: 2020

Watching instructional videos are often used to learn about procedures. Video captioning is one way of automatically collecting such knowledge. However, it provides only an indirect, overall evaluation of multimodal models with no finer-grained quantitative measure of what they have learned. We propose instead, a benchmark of structured procedural knowledge extracted from cooking videos. This work is complementary to existing tasks, but requires models to produce interpretable structured knowledge in the form of verb-argument tuples. Our manually annotated open-vocabulary resource includes 356 instructional cooking videos and 15,523 video clip/sentence-level annotations. Our analysis shows that the proposed task is challenging and standard modeling approaches like unsupervised segmentation, semantic role labeling, and visual action detection perform poorly when forced to predict every action of a procedure in a structured form.