OpenRaiser/Intern-Atlas huggingface dataset:
An Under-Approximate Relational Logic: Heralding Logics of Insecurity, Incorrect Implementation & More
Venue: arXiv cs.LO 2020
Year: 2020

Recently, authors have proposed under-approximate logics for reasoning about programs. So far, all such logics have been confined to reasoning about individual program behaviours. Yet there exist many over-approximate relational logics for reasoning about pairs of programs and relating their behaviours. We present the first under-approximate relational logic, for the simple imperative language IMP. We prove our logic is both sound and complete. Additionally, we show how reasoning in this logic can be decomposed into non-relational reasoning in an under-approximate Hoare logic, mirroring Beringer's result for over-approximate relational logics. We illustrate the application of our logic on some small examples in which we provably demonstrate the presence of insecurity.
Multi-SimLex: A Large-Scale Evaluation of Multilingual and Cross-Lingual Lexical Semantic Similarity
Venue: arXiv cs.CL 2020
Year: 2020

We introduce Multi-SimLex, a large-scale lexical resource and evaluation benchmark covering datasets for 12 typologically diverse languages, including major languages (e.g., Mandarin Chinese, Spanish, Russian) as well as less-resourced ones (e.g., Welsh, Kiswahili). Each language dataset is annotated for the lexical relation of semantic similarity and contains 1,888 semantically aligned concept pairs, providing a representative coverage of word classes (nouns, verbs, adjectives, adverbs), frequency ranks, similarity intervals, lexical fields, and concreteness levels. Additionally, owing to the alignment of concepts across languages, we provide a suite of 66 cross-lingual semantic similarity datasets. Due to its extensive size and language coverage, Multi-SimLex provides entirely novel opportunities for experimental evaluation and analysis. On its monolingual and cross-lingual benchmarks, we evaluate and analyze a wide array of recent state-of-the-art monolingual and cross-lingual representation models, including static and contextualized word embeddings (such as fastText, M-BERT and XLM), externally informed lexical representations, as well as fully unsupervised and (weakly) supervised cross-lingual word embeddings. We also present a step-by-step dataset creation protocol for creating consistent, Multi-Simlex-style resources for additional languages. We make these contributions -- the public release of Multi-SimLex datasets, their creation protocol, strong baseline results, and in-depth analyses which can be be helpful in guiding future developments in multilingual lexical semantics and representation learning -- available via a website which will encourage community effort in further expansion of Multi-Simlex to many more languages. Such a large-scale semantic resource could inspire significant further advances in NLP across languages.
Unsupervised and Interpretable Domain Adaptation to Rapidly Filter Tweets for Emergency Services
Venue: arXiv cs.CL 2020
Year: 2020

During the onset of a disaster event, filtering relevant information from the social web data is challenging due to its sparse availability and practical limitations in labeling datasets of an ongoing crisis. In this paper, we hypothesize that unsupervised domain adaptation through multi-task learning can be a useful framework to leverage data from past crisis events for training efficient information filtering models during the sudden onset of a new crisis. We present a novel method to classify relevant tweets during an ongoing crisis without seeing any new examples, using the publicly available dataset of TREC incident streams. Specifically, we construct a customized multi-task architecture with a multi-domain discriminator for crisis analytics: multi-task domain adversarial attention network. This model consists of dedicated attention layers for each task to provide model interpretability; critical for real-word applications. As deep networks struggle with sparse datasets, we show that this can be improved by sharing a base layer for multi-task learning and domain adversarial training. Evaluation of domain adaptation for crisis events is performed by choosing a target event as the test set and training on the rest. Our results show that the multi-task model outperformed its single task counterpart. For the qualitative evaluation of interpretability, we show that the attention layer can be used as a guide to explain the model predictions and empower emergency services for exploring accountability of the model, by showcasing the words in a tweet that are deemed important in the classification process. Finally, we show a practical implication of our work by providing a use-case for the COVID-19 pandemic.
Learning to mirror speaking styles incrementally
Venue: arXiv cs.CL 2020
Year: 2020

Mirroring is the behavior in which one person subconsciously imitates the gesture, speech pattern, or attitude of another. In conversations, mirroring often signals the speakers enjoyment and engagement in their communication. In chatbots, methods have been proposed to add personas to the chatbots and to train them to speak or to shift their dialogue style to that of the personas. However, they often require a large dataset consisting of dialogues of the target personalities to train. In this work, we explore a method that can learn to mirror the speaking styles of a person incrementally. Our method extracts ngrams that capture a persons speaking styles and uses the ngrams to create patterns for transforming sentences to the persons speaking styles. Our experiments show that our method is able to capture patterns of speaking style that can be used to transform regular sentences into sentences with the target style.
A Hierarchical Semantic Overlay for P2P Search
Venue: arXiv cs.DC 2020
Year: 2020

In this paper, we propose a hierarchical semantic overlay network for searching heterogeneous data over wide-area networks. In this system, data are represented as RDF triples based on ontologies. Peers that have the same semantics are organized into a semantic cluster, and the semantic clusters are self-organized into a one-dimensional ring space to form the toplevel semantic overlay network. Each semantic cluster has its low-level overlay network which can be built using an unstructured overlay or a DHT-based overlay. A search is first forwarded to the appropriate semantic cluster, and then routed to the specific peers that hold the relevant data using a parallel flooding algorithm or a DHT-based routing algorithm. By combining the advantages of both unstructured and structured overlay networks, we are able to achieve a better tradeoff in terms of search efficiency, search cost and overlay maintenance cost.
TyDi QA: A Benchmark for Information-Seeking Question Answering in Typologically Diverse Languages
Venue: arXiv cs.CL 2020
Year: 2020

Confidently making progress on multilingual modeling requires challenging, trustworthy evaluations. We present TyDi QA---a question answering dataset covering 11 typologically diverse languages with 204K question-answer pairs. The languages of TyDi QA are diverse with regard to their typology---the set of linguistic features each language expresses---such that we expect models performing well on this set to generalize across a large number of the world's languages. We present a quantitative analysis of the data quality and example-level qualitative linguistic analyses of observed language phenomena that would not be found in English-only corpora. To provide a realistic information-seeking task and avoid priming effects, questions are written by people who want to know the answer, but don't know the answer yet, and the data is collected directly in each language without the use of translation.
Retrospective Analysis of the 2019 MineRL Competition on Sample Efficient Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

To facilitate research in the direction of sample efficient reinforcement learning, we held the MineRL Competition on Sample Efficient Reinforcement Learning Using Human Priors at the Thirty-third Conference on Neural Information Processing Systems (NeurIPS 2019). The primary goal of this competition was to promote the development of algorithms that use human demonstrations alongside reinforcement learning to reduce the number of samples needed to solve complex, hierarchical, and sparse environments. We describe the competition, outlining the primary challenge, the competition design, and the resources that we provided to the participants. We provide an overview of the top solutions, each of which use deep reinforcement learning and/or imitation learning. We also discuss the impact of our organizational decisions on the competition and future directions for improvement.
Text classification with word embedding regularization and soft similarity measure
Venue: arXiv cs.IR 2020
Year: 2020

Since the seminal work of Mikolov et al., word embeddings have become the preferred word representations for many natural language processing tasks. Document similarity measures extracted from word embeddings, such as the soft cosine measure (SCM) and the Word Mover's Distance (WMD), were reported to achieve state-of-the-art performance on semantic text similarity and text classification. Despite the strong performance of the WMD on text classification and semantic text similarity, its super-cubic average time complexity is impractical. The SCM has quadratic worst-case time complexity, but its performance on text classification has never been compared with the WMD. Recently, two word embedding regularization techniques were shown to reduce storage and memory costs, and to improve training speed, document processing speed, and task performance on word analogy, word similarity, and semantic text similarity. However, the effect of these techniques on text classification has not yet been studied. In our work, we investigate the individual and joint effect of the two word embedding regularization techniques on the document processing speed and the task performance of the SCM and the WMD on text classification. For evaluation, we use the $k$NN classifier and six standard datasets: BBCSPORT, TWITTER, OHSUMED, REUTERS-21578, AMAZON, and 20NEWS. We show 39% average $k$NN test error reduction with regularized word embeddings compared to non-regularized word embeddings. We describe a practical procedure for deriving such regularized embeddings through Cholesky factorization. We also show that the SCM with regularized word embeddings significantly outperforms the WMD on text classification and is over 10,000 times faster.
Beam Designs for Millimeter-Wave Backhaul with Dual-Polarized Uniform Planar Arrays
Venue: arXiv cs.IT 2020
Year: 2020

This paper proposes hybrid beamforming designs for millimeter-wave (mmWave) multiple-input multiple-output (MIMO) backhaul systems equipped with uniform planar arrays (UPAs) of dual-polarization antennas at both the transmit and receive base stations. The proposed beamforming designs are to near-optimally solve optimization problems taking the dual-polarization UPA structure into account. Based on the solutions of optimization problems, this paper shows it is possible to generate the optimal dual-polarization beamformer from the optimal single-polarization beamformer sharing the same optimality. As specific examples, squared error and magnitude of inner product are considered respectively for optimization criteria. To optimize proposed beamformers, partial channel information is needed, and the use of low overhead pilot sequences is also proposed to figure out the required information. Simulation results verify that the resulting beamformers have the most uniform gain (with the squared error criterion) or the highest average gain (with the magnitude of inner product criterion) in the covering region with the UPA of dual-polarization antennas.
Trusted Confidence Bounds for Learning Enabled Cyber-Physical Systems
Venue: arXiv cs.LG 2020
Year: 2020

Cyber-physical systems (CPS) can benefit by the use of learning enabled components (LECs) such as deep neural networks (DNNs) for perception and decision making tasks. However, DNNs are typically non-transparent making reasoning about their predictions very difficult, and hence their application to safety-critical systems is very challenging. LECs could be integrated easier into CPS if their predictions could be complemented with a confidence measure that quantifies how much we trust their output. The paper presents an approach for computing confidence bounds based on Inductive Conformal Prediction (ICP). We train a Triplet Network architecture to learn representations of the input data that can be used to estimate the similarity between test examples and examples in the training data set. Then, these representations are used to estimate the confidence of set predictions from a classifier that is based on the neural network architecture used in the triplet. The approach is evaluated using a robotic navigation benchmark and the results show that we can computed trusted confidence bounds efficiently in real-time.
CASIA-SURF CeFA: A Benchmark for Multi-modal Cross-ethnicity Face Anti-spoofing
Venue: arXiv cs.CV 2020
Year: 2020

Ethnic bias has proven to negatively affect the performance of face recognition systems, and it remains an open research problem in face anti-spoofing. In order to study the ethnic bias for face anti-spoofing, we introduce the largest up to date CASIA-SURF Cross-ethnicity Face Anti-spoofing (CeFA) dataset (briefly named CeFA), covering $3$ ethnicities, $3$ modalities, $1,607$ subjects, and 2D plus 3D attack types. Four protocols are introduced to measure the affect under varied evaluation conditions, such as cross-ethnicity, unknown spoofs or both of them. To the best of our knowledge, CeFA is the first dataset including explicit ethnic labels in current published/released datasets for face anti-spoofing. Then, we propose a novel multi-modal fusion method as a strong baseline to alleviate these bias, namely, the static-dynamic fusion mechanism applied in each modality (i.e., RGB, Depth and infrared image). Later, a partially shared fusion strategy is proposed to learn complementary information from multiple modalities. Extensive experiments demonstrate that the proposed method achieves state-of-the-art results on the CASIA-SURF, OULU-NPU, SiW and the CeFA dataset.
Regularized Adaptation for Stable and Efficient Continuous-Level Learning on Image Processing Networks
Venue: arXiv cs.CV 2020
Year: 2020

In Convolutional Neural Network (CNN) based image processing, most of the studies propose networks that are optimized for a single-level (or a single-objective); thus, they underperform on other levels and must be retrained for delivery of optimal performance. Using multiple models to cover multiple levels involves very high computational costs. To solve these problems, recent approaches train the networks on two different levels and propose their own interpolation methods to enable the arbitrary intermediate levels. However, many of them fail to adapt hard tasks or interpolate smoothly, or the others still require large memory and computational cost. In this paper, we propose a novel continuous-level learning framework using a Filter Transition Network (FTN) which is a non-linear module that easily adapt to new levels, and is regularized to prevent undesirable side-effects. Additionally, for stable learning of FTN, we newly propose a method to initialize non-linear CNNs with identity mappings. Furthermore, FTN is extremely lightweight module since it is a data-independent module, which means it is not affected by the spatial resolution of the inputs. Extensive results for various image processing tasks indicate that the performance of FTN is stable in terms of adaptation and interpolation, and comparable to that of the other heavy frameworks.
Multi-Rate Fluid Scheduling of Mixed-Criticality Systems on Multiprocessors
Venue: arXiv cs.OS 2020
Year: 2020

In this paper we consider the problem of mixed-criticality (MC) scheduling of implicit-deadline sporadic task systems on a homogenous multiprocessor platform. Focusing on dual-criticality systems, algorithms based on the fluid scheduling model have been proposed in the past. These algorithms use a dual-rate execution model for each high-criticality task depending on the system mode. Once the system switches to the high-criticality mode, the execution rates of such tasks are increased to meet their increased demand. Although these algorithms are speed-up optimal, they are unable to schedule several feasible dual-criticality task systems. This is because a single fixed execution rate for each high-criticality task after the mode switch is not efficient to handle the high variability in demand during the transition period immediately following the mode switch. This demand variability exists as long as the carry-over jobs of high-criticality tasks, that is jobs released before the mode switch, have not completed. Addressing this shortcoming, we propose a multi-rate fluid execution model for dual-criticality task systems in this paper. Under this model, high-criticality tasks are allocated varying execution rates in the transition period after the mode switch to efficiently handle the demand variability. We derive a sufficient schedulability test for the proposed model and show its dominance over the dual-rate fluid execution model. Further, we also present a speed-up optimal rate assignment strategy for the multi-rate model, and experimentally show that the proposed model outperforms all the existing MC scheduling algorithms with known speed-up bounds.
Online Graph Matching Problems with a Worst-Case Reassignment Budget
Venue: arXiv cs.DS 2020
Year: 2020

In the online bipartite matching with reassignments problem, an algorithm is initially given only one side of the vertex set of a bipartite graph; the vertices on the other side are revealed to the algorithm one by one, along with its incident edges. The algorithm is required to maintain a matching in the current graph, where the algorithm revises the matching after each vertex arrival by reassigning vertices. Bernstein, Holm, and Rotenberg showed that an online algorithm can maintain a matching of maximum cardinality by performing amortized $O(\log^2 n)$ reassignments per arrival. In this paper, we propose to consider the general question of how requiring a non-amortized hard budget $k$ on the number of reassignments affects the algorithms' performances, under various models from the literature. We show that a simple, widely-used algorithm is a best-possible deterministic algorithm for all these models. For the unweighted maximum-cardinality problem, the algorithm is a $(1-\frac{2}{k+2})$-competitive algorithm, which is the best possible for a deterministic algorithm both under vertex arrivals and edge arrivals. Applied to the load balancing problem, this yields a bifactor online algorithm. For the weighted problem, which is traditionally studied assuming the triangle inequality, we show that the power of reassignment allows us to lift this assumption and the algorithm becomes a $\frac{1}{2}$-competitive algorithm for $k=4$, improving upon the $\frac{1}{3}$ of the previous algorithm without reassignments. We show that this also is a best-possible deterministic algorithm.
Uncovering the Data-Related Limits of Human Reasoning Research: An Analysis based on Recommender Systems
Venue: arXiv cs.AI 2020
Year: 2020

Understanding the fundamentals of human reasoning is central to the development of any system built to closely interact with humans. Cognitive science pursues the goal of modeling human-like intelligence from a theory-driven perspective with a strong focus on explainability. Syllogistic reasoning as one of the core domains of human reasoning research has seen a surge of computational models being developed over the last years. However, recent analyses of models' predictive performances revealed a stagnation in improvement. We believe that most of the problems encountered in cognitive science are not due to the specific models that have been developed but can be traced back to the peculiarities of behavioral data instead. Therefore, we investigate potential data-related reasons for the problems in human reasoning research by comparing model performances on human and artificially generated datasets. In particular, we apply collaborative filtering recommenders to investigate the adversarial effects of inconsistencies and noise in data and illustrate the potential for data-driven methods in a field of research predominantly concerned with gaining high-level theoretical insight into a domain. Our work (i) provides insight into the levels of noise to be expected from human responses in reasoning data, (ii) uncovers evidence for an upper-bound of performance that is close to being reached urging for an extension of the modeling task, and (iii) introduces the tools and presents initial results to pioneer a new paradigm for investigating and modeling reasoning focusing on predicting responses for individual human reasoners.
Self-supervised Point Set Local Descriptors for Point Cloud Registration
Venue: arXiv cs.RO 2020
Year: 2020

In this work, we propose to learn local descriptors for point clouds in a self-supervised manner. In each iteration of the training, the input of the network is merely one unlabeled point cloud. On top of our previous work, that directly solves the transformation between two point sets in one step without correspondences, the proposed method is able to train from one point cloud, by supervising its self-rotation, that we randomly generate. The whole training requires no manual annotation. In several experiments we evaluate the performance of our method on various datasets and compare to other state of the art algorithms. The results show, that our self-supervised learned descriptor achieves equivalent or even better performance than the supervised learned model, while being easier to train and not requiring labeled data.
In Situ Network and Application Performance Measurement on Android Devices and the Imperfections
Venue: arXiv cs.NI 2020
Year: 2020

Understanding network and application performance are essential for debugging, improving user experience, and performance comparison. Meanwhile, modern mobile systems are optimized for energy-efficient computation and communications that may limit the performance of network and applications. In recent years, several tools have emerged that analyze network performance of mobile applications in~situ with the help of the VPN service. There is a limited understanding of how these measurement tools and system optimizations affect the network and application performance. In this study, we first demonstrate that mobile systems employ energy-aware system hardware tuning, which affects application performance and network throughput. We next show that the VPN-based application performance measurement tools, such as Lumen, PrivacyGuard, and Video Optimizer, aid in ambiguous network performance measurements and degrade the application performance. Our findings suggest that sound application and network performance measurement on Android devices requires a good understanding of the device, networks, measurement tools, and applications.