OpenRaiser/Intern-Atlas huggingface dataset:
The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness
Venue: arXiv cs.DS 2020
Year: 2020

We consider the classical problem of maximizing a monotone submodular function subject to a cardinality constraint, which, due to its numerous applications, has recently been studied in various computational models. We consider a clean multi-player model that lies between the offline and streaming model, and study it under the aspect of one-way communication complexity. Our model captures the streaming setting (by considering a large number of players), and, in addition, two player approximation results for it translate into the robust setting. We present tight one-way communication complexity results for our model, which, due to the above-mentioned connections, have multiple implications in the data stream and robust setting. Even for just two players, a prior information-theoretic hardness result implies that no approximation factor above $1/2$ can be achieved in our model, if only queries to feasible sets are allowed. We show that the possibility of querying infeasible sets can actually be exploited to beat this bound, by presenting a tight $2/3$-approximation taking exponential time, and an efficient $0.514$-approximation. To the best of our knowledge, this is the first example where querying a submodular function on infeasible sets leads to provably better results. Through the above-mentioned link to the robust setting, both of these algorithms improve on the current state-of-the-art for robust submodular maximization, showing that approximation factors beyond $1/2$ are possible. Moreover, exploiting the link of our model to streaming, we settle the approximability for streaming algorithms by presenting a tight $1/2+\varepsilon$ hardness result, based on the construction of a new family of coverage functions. This improves on a prior $1-1/e+\varepsilon$ hardness and matches, up to an arbitrarily small margin, the best known approximation algorithm.
Extending a Tag-based Collaborative Recommender with Co-occurring Information Interests
Venue: arXiv cs.IR 2020
Year: 2020

Collaborative Filtering is largely applied to personalize item recommendation but its performance is affected by the sparsity of rating data. In order to address this issue, recent systems have been developed to improve recommendation by extracting latent factors from the rating matrices, or by exploiting trust relations established among users in social networks. In this work, we are interested in evaluating whether other sources of preference information than ratings and social ties can be used to improve recommendation performance. Specifically, we aim at testing whether the integration of frequently co-occurring interests in information search logs can improve recommendation performance in User-to-User Collaborative Filtering (U2UCF). For this purpose, we propose the Extended Category-based Collaborative Filtering (ECCF) recommender, which enriches category-based user profiles derived from the analysis of rating behavior with data categories that are frequently searched together by people in search sessions. We test our model using a big rating dataset and a log of a largely used search engine to extract the co-occurrence of interests. The experiments show that ECCF outperforms U2UCF and category-based collaborative recommendation in accuracy, MRR, diversity of recommendations and user coverage. Moreover, it outperforms the SVD++ Matrix Factorization algorithm in accuracy and diversity of recommendation lists.
Modeling Network Security: Case Study of Email System
Venue: arXiv cs.SE 2020
Year: 2020

We study operational security in computer network security, including infrastructure, internal processes, resources, information, and physical environment. Current works on developing a security framework focus on a security ontology that contributes to applying common vocabulary, but such an approach does not assist in constructing a foundation for a holistic security methodology. We focus on defining the bounds and creating a representation of a security system by developing a diagrammatic representation (i.e. a model) as a means to describe computer network processes. The model, referred to a thinging machine, is a first step toward developing a security strategy and plan. The general aim is to demonstrate that the representation of the security system plays a key role in making thinking visible through conceptual description of the operational environment, a region in which active security operations are undertaken. We apply the proposed model for email security by conceptually describing a real email system.
QRMine: A python package for triangulation in Grounded Theory
Venue: arXiv cs.CL 2020
Year: 2020

Grounded theory (GT) is a qualitative research method for building theory grounded in data. GT uses textual and numeric data and follows various stages of coding or tagging data for sense-making, such as open coding and selective coding. Machine Learning (ML) techniques, including natural language processing (NLP), can assist the researchers in the coding process. Triangulation is the process of combining various types of data. ML can facilitate deriving insights from numerical data for corroborating findings from the textual interview transcripts. We present an open-source python package (QRMine) that encapsulates various ML and NLP libraries to support coding and triangulation in GT. QRMine enables researchers to use these methods on their data with minimal effort. Researchers can install QRMine from the python package index (PyPI) and can contribute to its development. We believe that the concept of computational triangulation will make GT relevant in the realm of big data.
SiTGRU: Single-Tunnelled Gated Recurrent Unit for Abnormality Detection
Venue: arXiv cs.CV 2020
Year: 2020

Abnormality detection is a challenging task due to the dependence on a specific context and the unconstrained variability of practical scenarios. In recent years, it has benefited from the powerful features learnt by deep neural networks, and handcrafted features specialized for abnormality detectors. However, these approaches with large complexity still have limitations in handling long term sequential data (e.g., videos), and their learnt features do not thoroughly capture useful information. Recurrent Neural Networks (RNNs) have been shown to be capable of robustly dealing with temporal data in long term sequences. In this paper, we propose a novel version of Gated Recurrent Unit (GRU), called Single Tunnelled GRU for abnormality detection. Particularly, the Single Tunnelled GRU discards the heavy weighted reset gate from GRU cells that overlooks the importance of past content by only favouring current input to obtain an optimized single gated cell model. Moreover, we substitute the hyperbolic tangent activation in standard GRUs with sigmoid activation, as the former suffers from performance loss in deeper networks. Empirical results show that our proposed optimized GRU model outperforms standard GRU and Long Short Term Memory (LSTM) networks on most metrics for detection and generalization tasks on CUHK Avenue and UCSD datasets. The model is also computationally efficient with reduced training and testing time over standard RNNs.
A Privacy-Preserving Distributed Architecture for Deep-Learning-as-a-Service
Venue: arXiv cs.LG 2020
Year: 2020

Deep-learning-as-a-service is a novel and promising computing paradigm aiming at providing machine/deep learning solutions and mechanisms through Cloud-based computing infrastructures. Thanks to its ability to remotely execute and train deep learning models (that typically require high computational loads and memory occupation), such an approach guarantees high performance, scalability, and availability. Unfortunately, such an approach requires to send information to be processed (e.g., signals, images, positions, sounds, videos) to the Cloud, hence having potentially catastrophic-impacts on the privacy of users. This paper introduces a novel distributed architecture for deep-learning-as-a-service that is able to preserve the user sensitive data while providing Cloud-based machine and deep learning services. The proposed architecture, which relies on Homomorphic Encryption that is able to perform operations on encrypted data, has been tailored for Convolutional Neural Networks (CNNs) in the domain of image analysis and implemented through a client-server REST-based approach. Experimental results show the effectiveness of the proposed architecture.
A faster algorithm for the FSSP in one-dimensional CA with multiple speeds
Venue: arXiv cs.CC 2020
Year: 2020

In cellular automata with multiple speeds for each cell $i$ there is a positive integer $p_i$ such that this cell updates its state still periodically but only at times which are a multiple of $p_i$. Additionally there is a finite upper bound on all $p_i$. Manzoni and Umeo have described an algorithm for these (one-dimensional) cellular automata which solves the Firing Squad Synchronization Problem. This algorithm needs linear time (in the number of cells to be synchronized) but for many problem instances it is slower than the optimum time by some positive constant factor. In the present paper we derive lower bounds on possible synchronization times and describe an algorithm which is never slower and in some cases faster than the one by Manzoni and Umeo and which is close to a lower bound (up to a constant summand) in more cases.
On Biased Random Walks, Corrupted Intervals, and Learning Under Adversarial Design
Venue: arXiv cs.LG 2020
Year: 2020

We tackle some fundamental problems in probability theory on corrupted random processes on the integer line. We analyze when a biased random walk is expected to reach its bottommost point and when intervals of integer points can be detected under a natural model of noise. We apply these results to problems in learning thresholds and intervals under a new model for learning under adversarial design.
Difference Attention Based Error Correction LSTM Model for Time Series Prediction
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we propose a novel model for time series prediction in which difference-attention LSTM model and error-correction LSTM model are respectively employed and combined in a cascade way. While difference-attention LSTM model introduces a difference feature to perform attention in traditional LSTM to focus on the obvious changes in time series. Error-correction LSTM model refines the prediction error of difference-attention LSTM model to further improve the prediction accuracy. Finally, we design a training strategy to jointly train the both models simultaneously. With additional difference features and new principle learning framework, our model can improve the prediction accuracy in time series. Experiments on various time series are conducted to demonstrate the effectiveness of our method.
Laplacian Denoising Autoencoder
Venue: arXiv cs.CV 2020
Year: 2020

While deep neural networks have been shown to perform remarkably well in many machine learning tasks, labeling a large amount of ground truth data for supervised training is usually very costly to scale. Therefore, learning robust representations with unlabeled data is critical in relieving human effort and vital for many downstream tasks. Recent advances in unsupervised and self-supervised learning approaches for visual data have benefited greatly from domain knowledge. Here we are interested in a more generic unsupervised learning framework that can be easily generalized to other domains. In this paper, we propose to learn data representations with a novel type of denoising autoencoder, where the noisy input data is generated by corrupting latent clean data in the gradient domain. This can be naturally generalized to span multiple scales with a Laplacian pyramid representation of the input data. In this way, the agent learns more robust representations that exploit the underlying data structures across multiple scales. Experiments on several visual benchmarks demonstrate that better representations can be learned with the proposed approach, compared to its counterpart with single-scale corruption and other approaches. Furthermore, we also demonstrate that the learned representations perform well when transferring to other downstream vision tasks.
Coronavirus Optimization Algorithm: A bioinspired metaheuristic based on the COVID-19 propagation model
Venue: arXiv cs.AI 2020
Year: 2020

A novel bioinspired metaheuristic is proposed in this work, simulating how the coronavirus spreads and infects healthy people. From an initial individual (the patient zero), the coronavirus infects new patients at known rates, creating new populations of infected people. Every individual can either die or infect and, afterwards, be sent to the recovered population. Relevant terms such as re-infection probability, super-spreading rate or traveling rate are introduced in the model in order to simulate as accurately as possible the coronavirus activity. The Coronavirus Optimization Algorithm has two major advantages compared to other similar strategies. First, the input parameters are already set according to the disease statistics, preventing researchers from initializing them with arbitrary values. Second, the approach has the ability of ending after several iterations, without setting this value either. Infected population initially grows at an exponential rate but after some iterations, when considering social isolation measures and the high number recovered and dead people, the number of infected people starts decreasing in subsequent iterations. Furthermore, a parallel multi-virus version is proposed in which several coronavirus strains evolve over time and explore wider search space areas in less iterations. Finally, the metaheuristic has been combined with deep learning models, in order to find optimal hyperparameters during the training phase. As application case, the problem of electricity load time series forecasting has been addressed, showing quite remarkable performance.
Deep reinforcement learning for large-scale epidemic control
Venue: arXiv cs.LG 2020
Year: 2020

Epidemics of infectious diseases are an important threat to public health and global economies. Yet, the development of prevention strategies remains a challenging process, as epidemics are non-linear and complex processes. For this reason, we investigate a deep reinforcement learning approach to automatically learn prevention strategies in the context of pandemic influenza. Firstly, we construct a new epidemiological meta-population model, with 379 patches (one for each administrative district in Great Britain), that adequately captures the infection process of pandemic influenza. Our model balances complexity and computational efficiency such that the use of reinforcement learning techniques becomes attainable. Secondly, we set up a ground truth such that we can evaluate the performance of the 'Proximal Policy Optimization' algorithm to learn in a single district of this epidemiological model. Finally, we consider a large-scale problem, by conducting an experiment where we aim to learn a joint policy to control the districts in a community of 11 tightly coupled districts, for which no ground truth can be established. This experiment shows that deep reinforcement learning can be used to learn mitigation policies in complex epidemiological models with a large state space. Moreover, through this experiment, we demonstrate that there can be an advantage to consider collaboration between districts when designing prevention strategies.
An Interface-enriched Generalized Finite Element Method for Levelset-based Topology Optimization
Venue: arXiv cs.CE 2020
Year: 2020

During design optimization, a smooth description of the geometry is important, especially for problems that are sensitive to the way interfaces are resolved, e.g., wave propagation or fluid-structure interaction. A levelset description of the boundary, when combined with an enriched finite element formulation, offers a smoother description of the design than traditional density-based methods. However, existing enriched methods have drawbacks, including ill-conditioning and difficulties in prescribing essential boundary conditions. In this work we introduce a new enriched topology optimization methodology that overcomes the aforementioned drawbacks; boundaries are resolved accurately by means of the Interface-enriched Generalized Finite Element Method (IGFEM), coupled to a levelset function constructed by radial basis functions. The enriched method used in this new approach to topology optimization has the same level of accuracy in the analysis as standard the finite element method with matching meshes, but without the need for remeshing. We derive the analytical sensitivities and we discuss the behavior of the optimization process in detail. We establish that IGFEM-based levelset topology optimization generates correct topologies for well-known compliance minimization problems.
Quasi-experimental Designs for Assessing Response on Social Media to Policy Changes
Venue: arXiv cs.SI 2020
Year: 2020

Regulation of tobacco products is rapidly evolving. Understanding public sentiment in response to changes is very important as authorities assess how to effectively protect population health. Social media systems are widely recognized to be useful for collecting data about human preferences and perceptions. However, how social media data may be used, in rapid policy change settings, given challenges of narrow time periods and specific locations and non-representative the population using social media is an open question. In this paper we apply quasi-experimental designs, which have been used previously in observational data such as social media, to control for time and location confounders on social media, and then use content analysis of Twitter and Reddit posts to illustrate the content of reactions to tobacco flavor bans and the effect of taxation on e-cigarettes. Conclusions distill the potential role of social media in settings of rapidly changing regulation, in complement to what is learned by traditional denominator-based representative surveys.
Span-based discontinuous constituency parsing: a family of exact chart-based algorithms with time complexities from O(n^6) down to O(n^3)
Venue: arXiv cs.CL 2020
Year: 2020

We introduce a novel chart-based algorithm for span-based parsing of discontinuous constituency trees of block degree two, including ill-nested structures. In particular, we show that we can build variants of our parser with smaller search spaces and time complexities ranging from $\mathcal O(n^6)$ down to $\mathcal O(n^3)$. The cubic time variant covers 98\% of constituents observed in linguistic treebanks while having the same complexity as continuous constituency parsers. We evaluate our approach on German and English treebanks (Negra, Tiger and Discontinuous PTB) and report state-of-the-art results in the fully supervised setting. We also experiment with pre-trained word embeddings and \bert{}-based neural networks.
Anytime and Efficient Coalition Formation with Spatial and Temporal Constraints
Venue: arXiv cs.MA 2020
Year: 2020

The Coalition Formation with Spatial and Temporal constraints Problem (CFSTP) is a multi-agent task scheduling problem where the tasks are spatially distributed, with deadlines and workloads, and the number of agents is typically much smaller than the number of tasks, thus the agents have to form coalitions in order to maximise the number of completed tasks. The current state-of-the-art CFSTP solver, the Coalition Formation with Look-Ahead (CFLA) algorithm, has two main limitations. First, its time complexity is exponential with the number of agents. Second, as we show, its look-ahead technique is not effective in real-world scenarios, such as open multi-agent systems, where new tasks can appear at any time. In this work, we study its design and define an extension, called Coalition Formation with Improved Look-Ahead (CFLA2), which achieves better performance. Since we cannot eliminate the limitations of CFLA in CFLA2, we also develop a novel algorithm to solve the CFSTP, the first to be anytime, efficient and with provable guarantees, called Cluster-based Coalition Formation (CCF). We empirically show that, in settings where the look-ahead technique is highly effective, CCF completes up to 30% (resp. 10%) more tasks than CFLA (resp. CFLA2) while being up to four orders of magnitude faster. Our results affirm CCF as the new state-of-the-art algorithm to solve the CFSTP.
ActGAN: Flexible and Efficient One-shot Face Reenactment
Venue: arXiv cs.CV 2020
Year: 2020

This paper introduces ActGAN - a novel end-to-end generative adversarial network (GAN) for one-shot face reenactment. Given two images, the goal is to transfer the facial expression of the source actor onto a target person in a photo-realistic fashion. While existing methods require target identity to be predefined, we address this problem by introducing a "many-to-many" approach, which allows arbitrary persons both for source and target without additional retraining. To this end, we employ the Feature Pyramid Network (FPN) as a core generator building block - the first application of FPN in face reenactment, producing finer results. We also introduce a solution to preserve a person's identity between synthesized and target person by adopting the state-of-the-art approach in deep face recognition domain. The architecture readily supports reenactment in different scenarios: "many-to-many", "one-to-one", "one-to-another" in terms of expression accuracy, identity preservation, and overall image quality. We demonstrate that ActGAN achieves competitive performance against recent works concerning visual quality.
DeepGS: Deep Representation Learning of Graphs and Sequences for Drug-Target Binding Affinity Prediction
Venue: arXiv cs.LG 2020
Year: 2020

Accurately predicting drug-target binding affinity (DTA) in silico is a key task in drug discovery. Most of the conventional DTA prediction methods are simulation-based, which rely heavily on domain knowledge or the assumption of having the 3D structure of the targets, which are often difficult to obtain. Meanwhile, traditional machine learning-based methods apply various features and descriptors, and simply depend on the similarities between drug-target pairs. Recently, with the increasing amount of affinity data available and the success of deep representation learning models on various domains, deep learning techniques have been applied to DTA prediction. However, these methods consider either label/one-hot encodings or the topological structure of molecules, without considering the local chemical context of amino acids and SMILES sequences. Motivated by this, we propose a novel end-to-end learning framework, called DeepGS, which uses deep neural networks to extract the local chemical context from amino acids and SMILES sequences, as well as the molecular structure from the drugs. To assist the operations on the symbolic data, we propose to use advanced embedding techniques (i.e., Smi2Vec and Prot2Vec) to encode the amino acids and SMILES sequences to a distributed representation. Meanwhile, we suggest a new molecular structure modeling approach that works well under our framework. We have conducted extensive experiments to compare our proposed method with state-of-the-art models including KronRLS, SimBoost, DeepDTA and DeepCPI. Extensive experimental results demonstrate the superiorities and competitiveness of DeepGS.