OpenRaiser/Intern-Atlas huggingface dataset:
When does the Physarum Solver Distinguish the Shortest Path from other Paths: the Transition Point and its Applications
Venue: arXiv cs.NE 2021
Year: 2021

Physarum solver, also called the physarum polycephalum inspired algorithm (PPA), is a newly developed bio-inspired algorithm that has an inherent ability to find the shortest path in a given graph. Recent research has proposed methods to develop this algorithm further by accelerating the original PPA (OPPA)'s path-finding process. However, when does the PPA ascertain that the shortest path has been found? Is there a point after which the PPA could distinguish the shortest path from other paths? By innovatively proposing the concept of the dominant path (D-Path), the exact moment, named the transition point (T-Point), when the PPA finds the shortest path can be identified. Based on the D-Path and T-Point, a newly accelerated PPA named OPPA-D using the proposed termination criterion is developed which is superior to all other baseline algorithms according to the experiments conducted in this paper. The validity and the superiority of the proposed termination criterion is also demonstrated. Furthermore, an evaluation method is proposed to provide new insights for the comparison of different accelerated OPPAs. The breakthrough of this paper lies in using D-path and T-point to terminate the OPPA. The novel termination criterion reveals the actual performance of this OPPA. This OPPA is the fastest algorithm, outperforming some so-called accelerated OPPAs. Furthermore, we explain why some existing works inappropriately claim to be accelerated algorithms is in fact a product of inappropriate termination criterion, thus giving rise to the illusion that the method is accelerated.
Observations on the Bias of Nonnegative Mechanisms for Differential Privacy
Venue: arXiv cs.CR 2021
Year: 2021

We study two methods for differentially private analysis of bounded data and extend these to nonnegative queries. We first recall that for the Laplace mechanism, boundary inflated truncation (BIT) applied to nonnegative queries and truncation both lead to strictly positive bias. We then consider a generalization of BIT using translated ramp functions. We explicitly characterise the optimal function in this class for worst case bias. We show that applying any square-integrable post-processing function to a Laplace mechanism leads to a strictly positive maximal absolute bias. A corresponding result is also shown for a generalisation of truncation, which we refer to as restriction. We also briefly consider an alternative approach based on multiplicative mechanisms for positive data and show that, without additional restrictions, these mechanisms can lead to infinite bias.
One-Class Classification: A Survey
Venue: arXiv cs.CV 2021
Year: 2021

One-Class Classification (OCC) is a special case of multi-class classification, where data observed during training is from a single positive class. The goal of OCC is to learn a representation and/or a classifier that enables recognition of positively labeled queries during inference. This topic has received considerable amount of interest in the computer vision, machine learning and biometrics communities in recent years. In this article, we provide a survey of classical statistical and recent deep learning-based OCC methods for visual recognition. We discuss the merits and drawbacks of existing OCC approaches and identify promising avenues for research in this field. In addition, we present a discussion of commonly used datasets and evaluation metrics for OCC.
The role of scientific output in public debates in times of crisis: A case study of the reopening of schools during the COVID-19 pandemic
Venue: arXiv cs.DL 2021
Year: 2021

Situations in which no scientific consensus has been reached due to either insufficient, inconclusive or contradicting findings place strain on governments and public organizations which are forced to take action under circumstances of uncertainty. In this chapter, we focus on the case of COVID-19, its effects on children and the public debate around the reopening of schools. The aim is to better understand the relationship between policy interventions in the face of an uncertain and rapidly changing knowledge landscape and the subsequent use of scientific information in public debates related to the policy interventions. Our approach is to combine scientific information from journal articles and preprints with their appearance in the popular media, including social media. First, we provide a picture of the different scientific areas and approaches, by which the effects of COVID-19 on children are being studied. Second, we identify news media and social media attention around the COVID-19 scientific output related to children and schools. We focus on policies and media responses in three countries: Spain, South Africa and the Netherlands. These countries have followed very different policy actions with regard to the reopening of schools and represent very different policy approaches to the same problem. We analyse the activity in (social) media around the debate between COVID-19, children and school closures by focusing on the use of references to scientific information in the debate. Finally, we analyse the dominant topics that emerge in the news outlets and the online debates. We draw attention to illustrative cases of miscommunication related to scientific output and conclude the chapter by discussing how information from scientific publication, the media and policy actions shape the public discussion in the context of a global health pandemic.
Twitch Gamers: a Dataset for Evaluating Proximity Preserving and Structural Role-based Node Embeddings
Venue: arXiv cs.SI 2021
Year: 2021

Proximity preserving and structural role-based node embeddings have become a prime workhorse of applied graph mining. Novel node embedding techniques are often tested on a restricted set of benchmark datasets. In this paper, we propose a new diverse social network dataset called Twitch Gamers with multiple potential target attributes. Our analysis of the social network and node classification experiments illustrate that Twitch Gamers is suitable for assessing the predictive performance of novel proximity preserving and structural role-based node embedding algorithms.
A Rewriting Logic Approach to Specification, Proof-search, and Meta-proofs in Sequent Systems
Venue: arXiv cs.LO 2021
Year: 2021

This paper develops an algorithmic-based approach for proving inductive properties of propositional sequent systems such as admissibility, invertibility, cut-elimination, and identity expansion. Although undecidable in general, these structural properties are crucial in proof theory because they can reduce the proof-search effort and further be used as scaffolding for obtaining other meta-results such as consistency. The algorithms -- which take advantage of the rewriting logic meta-logical framework, and use rewrite- and narrowing-based reasoning -- are explained in detail and illustrated with examples throughout the paper. They have been fully mechanized in the L-Framework, thus offering both a formal specification language and off-the-shelf mechanization of the proof-search algorithms coming together with semi-decision procedures for proving theorems and meta-theorems of the object system. As illustrated with case studies in the paper, the L-Framework, achieves a great degree of automation when used on several propositional sequent systems, including single conclusion and multi-conclusion intuitionistic logic, classical logic, classical linear logic and its dyadic system, intuitionistic linear logic, and normal modal logics.
Bit Error Rate Analysis for Reconfigurable Intelligent Surfaces with Phase Errors
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we analyze the error probability of reconfigurable intelligent surfaces (RIS)-enabled communication systems with quantized channel phase compensation over Rayleigh fading channels. The probability density and characteristic functions of the received signal amplitude are derive dand used to compute exact expressions for the bit error rate(BER). The resulting expressions are general, as they hold for an arbitrary number of reflecting elements N, and quantization levels, L. We introduce an exact asymptotic analysis in the high signal-to-noise ratio (SNR) regime, from which we demonstrate, in particular, that the diversity order is N/2 when L=2 and N when L >2. The theoretical frameworks and findings are validated with the aid of Monte Carlo simulation.
SDRBench: Scientific Data Reduction Benchmark for Lossy Compressors
Venue: arXiv cs.DC 2021
Year: 2021

Efficient error-controlled lossy compressors are becoming critical to the success of today's large-scale scientific applications because of the ever-increasing volume of data produced by the applications. In the past decade, many lossless and lossy compressors have been developed with distinct design principles for different scientific datasets in largely diverse scientific domains. In order to support researchers and users assessing and comparing compressors in a fair and convenient way, we establish a standard compression assessment benchmark -- Scientific Data Reduction Benchmark (SDRBench). SDRBench contains a vast variety of real-world scientific datasets across different domains, summarizes several critical compression quality evaluation metrics, and integrates many state-of-the-art lossy and lossless compressors. We demonstrate evaluation results using SDRBench and summarize six valuable takeaways that are helpful to the in-depth understanding of lossy compressors.
Breaking Writer's Block: Low-cost Fine-tuning of Natural Language Generation Models
Venue: arXiv cs.CL 2021
Year: 2021

It is standard procedure these days to solve Information Extraction task by fine-tuning large pre-trained language models. This is not the case for generation task, which relies on a variety of techniques for controlled language generation. In this paper, we describe a system that fine-tunes a natural language generation model for the problem of solving Writer's Block. The fine-tuning changes the conditioning to also include the right context in addition to the left context, as well as an optional list of entities, the size, the genre and a summary of the paragraph that the human author wishes to generate. Our proposed fine-tuning obtains excellent results, even with a small number of epochs and a total cost of USD 150. The system can be accessed as a web-service, and all the code is released. A video showcasing the interface and the model is also available.
Spending Your Winning Lottery Better After Drawing It
Venue: arXiv cs.LG 2021
Year: 2021

Lottery Ticket Hypothesis (LTH) suggests that a dense neural network contains a sparse sub-network that can match the performance of the original dense network when trained in isolation from scratch. Most works retrain the sparse sub-network with the same training protocols as its dense network, such as initialization, architecture blocks, and training recipes. However, till now it is unclear that whether these training protocols are optimal for sparse networks. In this paper, we demonstrate that it is unnecessary for spare retraining to strictly inherit those properties from the dense network. Instead, by plugging in purposeful "tweaks" of the sparse subnetwork architecture or its training recipe, its retraining can be significantly improved than the default, especially at high sparsity levels. Combining all our proposed "tweaks" can yield the new state-of-the-art performance of LTH, and these modifications can be easily adapted to other sparse training algorithms in general. Specifically, we have achieved a significant and consistent performance gain of1.05% - 4.93% for ResNet18 on CIFAR-100 over vanilla-LTH. Moreover, our methods are shown to generalize across datasets (CIFAR10, CIFAR100, TinyImageNet) and architectures (Vgg16, ResNet-18/ResNet-34, MobileNet). All codes will be publicly available.
Identifying Human Edited Images using a CNN
Venue: arXiv cs.CV 2021
Year: 2021

Most non-professional photo manipulations are not made using propriety software like Adobe Photoshop, which is expensive and complicated to use for the average consumer selfie-taker or meme-maker. Instead, these individuals opt for user friendly mobile applications like FaceTune and Pixlr to make human face edits and alterations. Unfortunately, there is no existing dataset to train a model to classify these type of manipulations. In this paper, we present a generative model that approximates the distribution of human face edits and a method for detecting Facetune and Pixlr manipulations to human faces.
Trankit: A Light-Weight Transformer-based Toolkit for Multilingual Natural Language Processing
Venue: arXiv cs.CL 2021
Year: 2021

We introduce Trankit, a light-weight Transformer-based Toolkit for multilingual Natural Language Processing (NLP). It provides a trainable pipeline for fundamental NLP tasks over 100 languages, and 90 pretrained pipelines for 56 languages. Built on a state-of-the-art pretrained language model, Trankit significantly outperforms prior multilingual NLP pipelines over sentence segmentation, part-of-speech tagging, morphological feature tagging, and dependency parsing while maintaining competitive performance for tokenization, multi-word token expansion, and lemmatization over 90 Universal Dependencies treebanks. Despite the use of a large pretrained transformer, our toolkit is still efficient in memory usage and speed. This is achieved by our novel plug-and-play mechanism with Adapters where a multilingual pretrained transformer is shared across pipelines for different languages. Our toolkit along with pretrained models and code are publicly available at: https://github.com/nlp-uoregon/trankit. A demo website for our toolkit is also available at: http://nlp.uoregon.edu/trankit. Finally, we create a demo video for Trankit at: https://youtu.be/q0KGP3zGjGc.
FakeBuster: A DeepFakes Detection Tool for Video Conferencing Scenarios
Venue: arXiv cs.CV 2021
Year: 2021

This paper proposes a new DeepFake detector FakeBuster for detecting impostors during video conferencing and manipulated faces on social media. FakeBuster is a standalone deep learning based solution, which enables a user to detect if another person's video is manipulated or spoofed during a video conferencing based meeting. This tool is independent of video conferencing solutions and has been tested with Zoom and Skype applications. It uses a 3D convolutional neural network for predicting video segment-wise fakeness scores. The network is trained on a combination of datasets such as Deeperforensics, DFDC, VoxCeleb, and deepfake videos created using locally captured (for video conferencing scenarios) images. This leads to different environments and perturbations in the dataset, which improves the generalization of the deepfake network.
Task Adaptive Pretraining of Transformers for Hostility Detection
Venue: arXiv cs.CL 2021
Year: 2021

Identifying adverse and hostile content on the web and more particularly, on social media, has become a problem of paramount interest in recent years. With their ever increasing popularity, fine-tuning of pretrained Transformer-based encoder models with a classifier head are gradually becoming the new baseline for natural language classification tasks. In our work, we explore the gains attributed to Task Adaptive Pretraining (TAPT) prior to fine-tuning of Transformer-based architectures. We specifically study two problems, namely, (a) Coarse binary classification of Hindi Tweets into Hostile or Not, and (b) Fine-grained multi-label classification of Tweets into four categories: hate, fake, offensive, and defamation. Building up on an architecture which takes emojis and segmented hashtags into consideration for classification, we are able to experimentally showcase the performance upgrades due to TAPT. Our system (with team name 'iREL IIIT') ranked first in the 'Hostile Post Detection in Hindi' shared task with an F1 score of 97.16% for coarse-grained detection and a weighted F1 score of 62.96% for fine-grained multi-label classification on the provided blind test corpora.
Context-Aware Target Apps Selection and Recommendation for Enhancing Personal Mobile Assistants
Venue: arXiv cs.IR 2021
Year: 2021

Users install many apps on their smartphones, raising issues related to information overload for users and resource management for devices. Moreover, the recent increase in the use of personal assistants has made mobile devices even more pervasive in users' lives. This paper addresses two research problems that are vital for developing effective personal mobile assistants: target apps selection and recommendation. The former is the key component of a unified mobile search system: a system that addresses the users' information needs for all the apps installed on their devices with a unified mode of access. The latter, instead, predicts the next apps that the users would want to launch. Here we focus on context-aware models to leverage the rich contextual information available to mobile devices. We design an in situ study to collect thousands of mobile queries enriched with mobile sensor data (now publicly available for research purposes). With the aid of this dataset, we study the user behavior in the context of these tasks and propose a family of context-aware neural models that take into account the sequential, temporal, and personal behavior of users. We study several state-of-the-art models and show that the proposed models significantly outperform the baselines.
Are We There Yet? Learning to Localize in Embodied Instruction Following
Venue: arXiv cs.AI 2021
Year: 2021

Embodied instruction following is a challenging problem requiring an agent to infer a sequence of primitive actions to achieve a goal environment state from complex language and visual inputs. Action Learning From Realistic Environments and Directives (ALFRED) is a recently proposed benchmark for this problem consisting of step-by-step natural language instructions to achieve subgoals which compose to an ultimate high-level goal. Key challenges for this task include localizing target locations and navigating to them through visual inputs, and grounding language instructions to visual appearance of objects. To address these challenges, in this study, we augment the agent's field of view during navigation subgoals with multiple viewing angles, and train the agent to predict its relative spatial relation to the target location at each timestep. We also improve language grounding by introducing a pre-trained object detection module to the model pipeline. Empirical studies show that our approach exceeds the baseline model performance.
Shortest non-separating st-path on chordal graphs
Venue: arXiv cs.DS 2021
Year: 2021

Many NP-Hard problems on general graphs, such as maximum independence set, maximal cliques and graph coloring can be solved efficiently on chordal graphs. In this paper, we explore the problem of non-separating st-paths defined on edges: for a connected undirected graph and two vertices, a non-separating path is a path between the two vertices such that if we remove all the edges on the path, the graph remains connected. We show that on general graphs, checking the existence of non-separating st-paths is NP-Hard, but the same problem can be solved in linear time on chordal graphs. In the case that such path exists, we introduce an algorithm that finds the shortest non-separating st-path on a connected chordal graph of $n$ vertices and $m$ edges with positive edge lengths that runs in $O(n\log{n} + m)$ time.
Learning from Satisfying Assignments Using Risk Minimization
Venue: arXiv cs.LG 2021
Year: 2021

In this paper we consider the problem of Learning from Satisfying Assignments introduced by \cite{1} of finding a distribution that is a close approximation to the uniform distribution over the satisfying assignments of a low complexity Boolean function $f$. In a later work \cite{2} consider the same problem but with the knowledge of some continuous distribution $D$ and the objective being to estimate $D_f$, which is $D$ restricted to the satisfying assignments of an unknown Boolean function $f$. We consider these problems from the point of view of parameter estimation techniques in statistical machine learning and prove similar results that are based on standard optimization algorithms for Risk Minimization.
Bandwidth Allocation for Multiple Federated Learning Services in Wireless Edge Networks
Venue: arXiv cs.NI 2021
Year: 2021

This paper studies a federated learning (FL) system, where \textit{multiple} FL services co-exist in a wireless network and share common wireless resources. It fills the void of wireless resource allocation for multiple simultaneous FL services in the existing literature. Our method designs a two-level resource allocation framework comprising \emph{intra-service} resource allocation and \emph{inter-service} resource allocation. The intra-service resource allocation problem aims to minimize the length of FL rounds by optimizing the bandwidth allocation among the clients of each FL service. Based on this, an inter-service resource allocation problem is further considered, which distributes bandwidth resources among multiple simultaneous FL services. We consider both cooperative and selfish providers of the FL services. For cooperative FL service providers, we design a distributed bandwidth allocation algorithm to optimize the overall performance of multiple FL services, meanwhile cater to the fairness among FL services and the privacy of clients. For selfish FL service providers, a new auction scheme is designed with the FL service owners as the bidders and the network provider as the auctioneer. The designed auction scheme strikes a balance between the overall FL performance and fairness. Our simulation results show that the proposed algorithms outperform other benchmarks under various network conditions.
The Degraded Discrete-Time Poisson Wiretap Channel
Venue: arXiv cs.IT 2021
Year: 2021

This paper addresses the degraded discrete-time Poisson wiretap channel (DT--PWC) in an optical wireless communication system based on intensity modulation and direct detection. Subject to nonnegativity, peak- and average-intensity as well as bandwidth constraints, we study the secrecy-capacity-achieving input distribution of this wiretap channel and prove it to be unique and discrete with a finite number of mass points; one of them located at the origin. Furthermore, we establish that every point on the boundary of the rate-equivocation region of this wiretap channel is also obtained by a unique and discrete input distribution with finitely many mass points. In general, the number of mass points of the optimal distributions is greater than two. This is in contrast with the degraded continuous-time PWC when the signaling bandwidth is not restricted and where the secrecy capacity and the entire boundary of the rate-equivocation region are achieved by binary distributions. Furthermore, we extend our analysis to the case where only an average-intensity constraint is active. For this case, we find that the secrecy capacity and the entire boundary of the rate-equivocation region are attained by discrete distributions with countably \textit{infinite} number of mass points, but with finitely many mass points in any bounded interval.