OpenRaiser/Intern-Atlas huggingface dataset:
Computational Complexity Characterization of Protecting Elections from Bribery
Venue: arXiv cs.CC 2020
Year: 2020

The bribery problem in election has received considerable attention in the literature, upon which various algorithmic and complexity results have been obtained. It is thus natural to ask whether we can protect an election from potential bribery. We assume that the protector can protect a voter with some cost (e.g., by isolating the voter from potential bribers). A protected voter cannot be bribed. Under this setting, we consider the following bi-level decision problem: Is it possible for the protector to protect a proper subset of voters such that no briber with a fixed budget on bribery can alter the election result? The goal of this paper is to give a full picture on the complexity of protection problems. We give an extensive study on the protection problem and provide algorithmic and complexity results. Comparing our results with that on the bribery problems, we observe that the protection problem is in general significantly harder. Indeed, it becomes $\sum_{p}^2$-complete even for very restricted special cases, while most bribery problems lie in NP. However, it is not necessarily the case that the protection problem is always harder. Some of the protection problems can still be solved in polynomial time, while some of them remain as hard as the bribery problem under the same setting.
Tensor Convolutional Sparse Coding with Low-Rank activations, an application to EEG analysis
Venue: arXiv cs.LG 2020
Year: 2020

Recently, there has been growing interest in the analysis of spectrograms of ElectroEncephaloGram (EEG), particularly to study the neural correlates of (un)-consciousness during General Anesthesia (GA). Indeed, it has been shown that order three tensors (channels x frequencies x times) are a natural and useful representation of these signals. However this encoding entails significant difficulties, especially for convolutional sparse coding (CSC) as existing methods do not take advantage of the particularities of tensor representation, such as rank structures, and are vulnerable to the high level of noise and perturbations that are inherent to EEG during medical acts. To address this issue, in this paper we introduce a new CSC model, named Kruskal CSC (K-CSC), that uses the Kruskal decomposition of the activation tensors to leverage the intrinsic low rank nature of these representations in order to extract relevant and interpretable encodings. Our main contribution, TC-FISTA, uses multiple tools to efficiently solve the resulting optimization problem despite the increasing complexity induced by the tensor representation. We then evaluate TC-FISTA on both synthetic dataset and real EEG recorded during GA. The results show that TC-FISTA is robust to noise and perturbations, resulting in accurate, sparse and interpretable encoding of the signals.
Reducing Misinformation in Query Autocompletions
Venue: arXiv cs.IR 2020
Year: 2020

Query autocompletions help users of search engines to speed up their searches by recommending completions of partially typed queries in a drop down box. These recommended query autocompletions are usually based on large logs of queries that were previously entered by the search engine's users. Therefore, misinformation entered -- either accidentally or purposely to manipulate the search engine -- might end up in the search engine's recommendations, potentially harming organizations, individuals, and groups of people. This paper proposes an alternative approach for generating query autocompletions by extracting anchor texts from a large web crawl, without the need to use query logs. Our evaluation shows that even though query log autocompletions perform better for shorter queries, anchor text autocompletions outperform query log autocompletions for queries of 2 words or more.
GCN for HIN via Implicit Utilization of Attention and Meta-paths
Venue: arXiv cs.SI 2020
Year: 2020

Heterogeneous information network (HIN) embedding, aiming to map the structure and semantic information in a HIN to distributed representations, has drawn considerable research attention. Graph neural networks for HIN embeddings typically adopt a hierarchical attention (including node-level and meta-path-level attentions) to capture the information from meta-path-based neighbors. However, this complicated attention structure often cannot achieve the function of selecting meta-paths due to severe overfitting. Moreover, when propagating information, these methods do not distinguish direct (one-hop) meta-paths from indirect (multi-hop) ones. But from the perspective of network science, direct relationships are often believed to be more essential, which can only be used to model direct information propagation. To address these limitations, we propose a novel neural network method via implicitly utilizing attention and meta-paths, which can relieve the severe overfitting brought by the current over-parameterized attention mechanisms on HIN. We first use the multi-layer graph convolutional network (GCN) framework, which performs a discriminative aggregation at each layer, along with stacking the information propagation of direct linked meta-paths layer-by-layer, realizing the function of attentions for selecting meta-paths in an indirect way. We then give an effective relaxation and improvement via introducing a new propagation operation which can be separated from aggregation. That is, we first model the whole propagation process with well-defined probabilistic diffusion dynamics, and then introduce a random graph-based constraint which allows it to reduce noise with the increase of layers. Extensive experiments demonstrate the superiority of the new approach over state-of-the-art methods.
Separating Positive and Negative Data Examples by Concepts and Formulas: The Case of Restricted Signatures
Venue: arXiv cs.AI 2020
Year: 2020

We study the separation of positive and negative data examples in terms of description logic (DL) concepts and formulas of decidable FO fragments, in the presence of an ontology. In contrast to previous work, we add a signature that specifies a subset of the symbols from the data and ontology that can be used for separation. We consider weak and strong versions of the resulting problem that differ in how the negative examples are treated. Our main results are that (a projective form of) the weak version is decidable in $\mathcal{ALCI}$ while it is undecidable in the guarded fragment GF, the guarded negation fragment GNF, and the DL $\mathcal{ALCFIO}$, and that strong separability is decidable in $\mathcal{ALCI}$, GF, and GNF. We also provide (mostly tight) complexity bounds.
On the Influence of Ageing on Face Morph Attacks: Vulnerability and Detection
Venue: arXiv cs.CV 2020
Year: 2020

Face morphing attacks have raised critical concerns as they demonstrate a new vulnerability of Face Recognition Systems (FRS), which are widely deployed in border control applications. The face morphing process uses the images from multiple data subjects and performs an image blending operation to generate a morphed image of high quality. The generated morphed image exhibits similar visual characteristics corresponding to the biometric characteristics of the data subjects that contributed to the composite image and thus making it difficult for both humans and FRS, to detect such attacks. In this paper, we report a systematic investigation on the vulnerability of the Commercial-Off-The-Shelf (COTS) FRS when morphed images under the influence of ageing are presented. To this extent, we have introduced a new morphed face dataset with ageing derived from the publicly available MORPH II face dataset, which we refer to as MorphAge dataset. The dataset has two bins based on age intervals, the first bin - MorphAge-I dataset has 1002 unique data subjects with the age variation of 1 year to 2 years while the MorphAge-II dataset consists of 516 data subjects whose age intervals are from 2 years to 5 years. To effectively evaluate the vulnerability for morphing attacks, we also introduce a new evaluation metric, namely the Fully Mated Morphed Presentation Match Rate (FMMPMR), to quantify the vulnerability effectively in a realistic scenario. Extensive experiments are carried out by using two different COTS FRS (COTS I - Cognitec and COTS II - Neurotechnology) to quantify the vulnerability with ageing. Further, we also evaluate five different Morph Attack Detection (MAD) techniques to benchmark their detection performance with ageing.
Finally a Case for Collaborative VR?: The Need to Design for Remote Multi-Party Conversations
Venue: arXiv cs.HC 2020
Year: 2020

Amid current social distancing measures requiring people to work from home, there has been renewed interest on how to effectively converse and collaborate remotely utilizing currently available technologies. On the surface, VR provides a perfect platform for effective remote communication. It can transfer contextual and environmental cues and facilitate a shared perspective while also allowing people to be virtually co-located. Yet we argue that currently VR is not adequately designed for such a communicative purpose. In this paper, we outline three key barriers to using VR for conversational activity : (1) variability of social immersion, (2) unclear user roles, and (3) the need for effective shared visual reference. Based on this outline, key design topics are discussed through a user experience design perspective for considerations in a future collaborative design framework.
The FORA Fog Computing Platform for Industrial IoT
Venue: arXiv cs.DC 2020
Year: 2020

Industry 4.0 will only become a reality through the convergence of Operational and Information Technologies (OT & IT), which use different computation and communication technologies. Cloud Computing cannot be used for OT involving industrial applications, since it cannot guar-antee stringent non-functional requirements, e.g., dependability, trustworthiness and timeliness. Instead, a new computing paradigm, called Fog Computing, is envisioned as an architectural means to realize the IT/OT convergence. In this paper we propose a Fog Computing Platform (FCP) reference architecture targeting Industrial IoT applications. The FCP is based on: deter-ministic virtualization that reduces the effort required for safety and security assurance; middle-ware for supporting both critical control and dynamic Fog applications; deterministic networking and interoperability, using open standards such as IEEE 802.1 Time-Sensitive Networking (TSN) and OPC Unified Architecture (OPC UA); mechanisms for resource management and or-chestration; and services for security, fault tolerance and distributed machine learning. We pro-pose a methodology for the definition and the evaluation of the reference architecture. We use the Architecture Analysis Design Language (AADL) to model the FCP reference architecture, and a set of industrial use cases to evaluate its suitability for the Industrial IoT area.
On Designing a Machine Learning Based Wireless Link Quality Classifier
Venue: arXiv cs.NI 2020
Year: 2020

Ensuring a reliable communication in wireless networks strictly depends on the effective estimation of the link quality, which is particularly challenging when propagation environment for radio signals significantly varies. In such environments, intelligent algorithms that can provide robust, resilient and adaptive links are being investigated to complement traditional algorithms in maintaining a reliable communication. In this respect, the data-driven link quality estimation (LQE) using machine learning (ML) algorithms is one of the most promising approaches. In this paper, we provide a quantitative evaluation of design decisions taken at each step involved in developing a ML based wireless LQE on a selected, publicly available dataset. Our study shows that, re-sampling to achieve training class balance and feature engineering have a larger impact on the final performance of the LQE than the selection of the ML method on the selected data.
Black-box Adversarial Example Generation with Normalizing Flows
Venue: arXiv cs.LG 2020
Year: 2020

Deep neural network classifiers suffer from adversarial vulnerability: well-crafted, unnoticeable changes to the input data can affect the classifier decision. In this regard, the study of powerful adversarial attacks can help shed light on sources of this malicious behavior. In this paper, we propose a novel black-box adversarial attack using normalizing flows. We show how an adversary can be found by searching over a pre-trained flow-based model base distribution. This way, we can generate adversaries that resemble the original data closely as the perturbations are in the shape of the data. We then demonstrate the competitive performance of the proposed approach against well-known black-box adversarial attack methods.
Towards Game-Playing AI Benchmarks via Performance Reporting Standards
Venue: arXiv cs.AI 2020
Year: 2020

While games have been used extensively as milestones to evaluate game-playing AI, there exists no standardised framework for reporting the obtained observations. As a result, it remains difficult to draw general conclusions about the strengths and weaknesses of different game-playing AI algorithms. In this paper, we propose reporting guidelines for AI game-playing performance that, if followed, provide information suitable for unbiased comparisons between different AI approaches. The vision we describe is to build benchmarks and competitions based on such guidelines in order to be able to draw more general conclusions about the behaviour of different AI algorithms, as well as the types of challenges different games pose.
Learning the Prediction Distribution for Semi-Supervised Learning with Normalising Flows
Venue: arXiv cs.LG 2020
Year: 2020

As data volumes continue to grow, the labelling process increasingly becomes a bottleneck, creating demand for methods that leverage information from unlabelled data. Impressive results have been achieved in semi-supervised learning (SSL) for image classification, nearing fully supervised performance, with only a fraction of the data labelled. In this work, we propose a probabilistically principled general approach to SSL that considers the distribution over label predictions, for labels of different complexity, from "one-hot" vectors to binary vectors and images. Our method regularises an underlying supervised model, using a normalising flow that learns the posterior distribution over predictions for labelled data, to serve as a prior over the predictions on unlabelled data. We demonstrate the general applicability of this approach on a range of computer vision tasks with varying output complexity: classification, attribute prediction and image-to-image translation.
Sentiment Polarity Detection on Bengali Book Reviews Using Multinomial Naive Bayes
Venue: arXiv cs.CL 2020
Year: 2020

Recently, sentiment polarity detection has increased attention to NLP researchers due to the massive availability of customer's opinions or reviews in the online platform. Due to the continued expansion of e-commerce sites, the rate of purchase of various products, including books, are growing enormously among the people. Reader's opinions/reviews affect the buying decision of a customer in most cases. This work introduces a machine learning-based technique to determine sentiment polarities (either positive or negative category) from Bengali book reviews. To assess the effectiveness of the proposed technique, a corpus with 2000 reviews on Bengali books is developed. A comparative analysis with various approaches (such as logistic regression, naive Bayes, SVM, and SGD) also performed by taking into consideration of the unigram, bigram, and trigram features, respectively. Experimental result reveals that the multinomial Naive Bayes with unigram feature outperforms the other techniques with 84% accuracy on the test set.
Intelligent Reflecting Surface Aided Wireless Communications: A Tutorial
Venue: arXiv cs.IT 2020
Year: 2020

Intelligent reflecting surface (IRS) is an enabling technology to engineer the radio signal prorogation in wireless networks. By smartly tuning the signal reflection via a large number of low-cost passive reflecting elements, IRS is capable of dynamically altering wireless channels to enhance the communication performance. It is thus expected that the new IRS-aided hybrid wireless network comprising both active and passive components will be highly promising to achieve a sustainable capacity growth cost-effectively in the future. Despite its great potential, IRS faces new challenges to be efficiently integrated into wireless networks, such as reflection optimization, channel estimation, and deployment from communication design perspectives. In this paper, we provide a tutorial overview of IRS-aided wireless communication to address the above issues, and elaborate its reflection and channel models, hardware architecture and practical constraints, as well as various appealing applications in wireless networks. Moreover, we highlight important directions worthy of further investigation in future work.
Model-based Exploration of the Frontier of Behaviours for Deep Learning System Testing
Venue: arXiv cs.SE 2020
Year: 2020

With the increasing adoption of Deep Learning (DL) for critical tasks, such as autonomous driving, the evaluation of the quality of systems that rely on DL has become crucial. Once trained, DL systems produce an output for any arbitrary numeric vector provided as input, regardless of whether it is within or outside the validity domain of the system under test. Hence, the quality of such systems is determined by the intersection between their validity domain and the regions where their outputs exhibit a misbehaviour. In this paper, we introduce the notion of frontier of behaviours, i.e., the inputs at which the DL system starts to misbehave. If the frontier of misbehaviours is outside the validity domain of the system, the quality check is passed. Otherwise, the inputs at the intersection represent quality deficiencies of the system. We developed DeepJanus, a search-based tool that generates frontier inputs for DL systems. The experimental results obtained for the lane keeping component of a self-driving car show that the frontier of a well trained system contains almost exclusively unrealistic roads that violate the best practices of civil engineering, while the frontier of a poorly trained one includes many valid inputs that point to serious deficiencies of the system.
Disaggregating Non-Volatile Memory for Throughput-Oriented Genomics Workloads
Venue: arXiv cs.DC 2020
Year: 2020

Massive exploitation of next-generation sequencing technologies requires dealing with both: huge amounts of data and complex bioinformatics pipelines. Computing architectures have evolved to deal with these problems, enabling approaches that were unfeasible years ago: accelerators and Non-Volatile Memories (NVM) are becoming widely used to enhance the most demanding workloads. However, bioinformatics workloads are usually part of bigger pipelines with different and dynamic needs in terms of resources. The introduction of Software Defined Infrastructures (SDI) for data centers provides roots to dramatically increase the efficiency in the management of infrastructures. SDI enables new ways to structure hardware resources through disaggregation, and provides new hardware composability and sharing mechanisms to deploy workloads in more flexible ways. In this paper we study a state-of-the-art genomics application, SMUFIN, aiming to address the challenges of future HPC facilities.
Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis
Venue: arXiv cs.LG 2020
Year: 2020

Algorithm selection (AS) deals with the automatic selection of an algorithm from a fixed set of candidate algorithms most suitable for a specific instance of an algorithmic problem class, where "suitability" often refers to an algorithm's runtime. Due to possibly extremely long runtimes of candidate algorithms, training data for algorithm selection models is usually generated under time constraints in the sense that not all algorithms are run to completion on all instances. Thus, training data usually comprises censored information, as the true runtime of algorithms timed out remains unknown. However, many standard AS approaches are not able to handle such information in a proper way. On the other side, survival analysis (SA) naturally supports censored data and offers appropriate ways to use such data for learning distributional models of algorithm runtime, as we demonstrate in this work. We leverage such models as a basis of a sophisticated decision-theoretic approach to algorithm selection, which we dub Run2Survive. Moreover, taking advantage of a framework of this kind, we advocate a risk-averse approach to algorithm selection, in which the avoidance of a timeout is given high priority. In an extensive experimental study with the standard benchmark ASlib, our approach is shown to be highly competitive and in many cases even superior to state-of-the-art AS approaches.
Dynamic Awareness
Venue: arXiv cs.AI 2020
Year: 2020

We investigate how to model the beliefs of an agent who becomes more aware. We use the framework of Halpern and Rego (2013) by adding probability, and define a notion of a model transition that describes constraints on how, if an agent becomes aware of a new formula $ϕ$ in state $s$ of a model $M$, she transitions to state $s^*$ in a model $M^*$. We then discuss how such a model can be applied to information disclosure.
Eliminating Catastrophic Interference with Biased Competition
Venue: arXiv cs.CV 2020
Year: 2020

We present here a model to take advantage of the multi-task nature of complex datasets by learning to separate tasks and subtasks in and end to end manner by biasing competitive interactions in the network. This method does not require additional labelling or reformatting of data in a dataset. We propose an alternate view to the monolithic one-task-fits-all learning of multi-task problems, and describe a model based on a theory of neuronal attention from neuroscience, proposed by Desimone. We create and exhibit a new toy dataset, based on the MNIST dataset, which we call MNIST-QA, for testing Visual Question Answering architectures in a low-dimensional environment while preserving the more difficult components of the Visual Question Answering task, and demonstrate the proposed network architecture on this new dataset, as well as on COCO-QA and DAQUAR-FULL. We then demonstrate that this model eliminates catastrophic interference between tasks on a newly created toy dataset and provides competitive results in the Visual Question Answering space. We provide further evidence that Visual Question Answering can be approached as a multi-task problem, and demonstrate that this new architecture based on the Biased Competition model is capable of learning to separate and learn the tasks in an end-to-end fashion without the need for task labels.
Contextualized Spoken Word Representations from Convolutional Autoencoders
Venue: arXiv cs.CL 2020
Year: 2020

A lot of work has been done to build text-based language models for performing different NLP tasks, but not much research has been done in the case of audio-based language models. This paper proposes a Convolutional Autoencoder based neural architecture to model syntactically and semantically adequate contextualized representations of varying length spoken words. The use of such representations can not only lead to great advances in the audio-based NLP tasks but can also curtail the loss of information like tone, expression, accent, etc while converting speech to text to perform these tasks. The performance of the proposed model is validated by (1) examining the generated vector space, and (2) evaluating its performance on three benchmark datasets for measuring word similarities, against existing widely used text-based language models that are trained on the transcriptions. The proposed model was able to demonstrate its robustness when compared to the other two language-based models.