OpenRaiser/Intern-Atlas huggingface dataset:
Maximum Coverage in the Data Stream Model: Parameterized and Generalized
Venue: arXiv cs.DS 2021
Year: 2021

We present algorithms for the Max-Cover and Max-Unique-Cover problems in the data stream model. The input to both problems are $m$ subsets of a universe of size $n$ and a value $k\in [m]$. In Max-Cover, the problem is to find a collection of at most $k$ sets such that the number of elements covered by at least one set is maximized. In Max-Unique-Cover, the problem is to find a collection of at most $k$ sets such that the number of elements covered by exactly one set is maximized. Our goal is to design single-pass algorithms that use space that is sublinear in the input size. Our main algorithmic results are: If the sets have size at most $d$, there exist single-pass algorithms using $\tilde{O}(d^{d+1} k^d)$ space that solve both problems exactly. This is optimal up to polylogarithmic factors for constant $d$. If each element appears in at most $r$ sets, we present single pass algorithms using $\tilde{O}(k^2 r/ε^3)$ space that return a $1+ε$ approximation in the case of Max-Cover. We also present a single-pass algorithm using slightly more memory, i.e., $\tilde{O}(k^3 r/ε^{4})$ space, that $1+ε$ approximates Max-Unique-Cover. In contrast to the above results, when $d$ and $r$ are arbitrary, any constant pass $1+ε$ approximation algorithm for either problem requires $Ω(ε^{-2}m)$ space but a single pass $O(ε^{-2}mk)$ space algorithm exists. In fact any constant-pass algorithm with an approximation better than $e/(e-1)$ and $e^{1-1/k}$ for Max-Cover and Max-Unique-Cover respectively requires $Ω(m/k^2)$ space when $d$ and $r$ are unrestricted. En route, we also obtain an algorithm for a parameterized version of the streaming Set-Cover problem.
Addressing the Need for Remote Patient Monitoring Applications in Appalachian Areas
Venue: arXiv cs.HC 2021
Year: 2021

There is a need to address the urban-rural disparities in healthcare regarding equal access and quality of care. Due to higher rates of chronic disease, reduced access to providers, and a continuous decline in rural hospitals, it is imperative that Appalachian cancer patients adopt the use of health information technology (HIT). The NCCN Distress Thermometer and Problem List (DT) is under-utilized, not patient-centered, does not consider provider needs, and is outdated in the current digital landscape. Digitizing patient distress screening poses advantages, such as allowing for more frequent screenings, removing geographical barriers, and rural patient autonomy. In this paper, we discuss how knowledge gained from patient-centered design led to the underpinnings of developing a rural remote patient monitoring app that provides delightful and insightful experiences to users.
Active Face Frontalization using Commodity Unmanned Aerial Vehicles
Venue: arXiv cs.CV 2021
Year: 2021

This paper describes a system by which Unmanned Aerial Vehicles (UAVs) can gather high-quality face images that can be used in biometric identification tasks. Success in face-based identification depends in large part on the image quality, and a major factor is how frontal the view is. Face recognition software pipelines can improve identification rates by synthesizing frontal views from non-frontal views by a process call {\em frontalization}. Here we exploit the high mobility of UAVs to actively gather frontal images using components of a synthetic frontalization pipeline. We define a frontalization error and show that it can be used to guide an UAVs to capture frontal views. Further, we show that the resulting image stream improves matching quality of a typical face recognition similarity metric. The system is implemented using an off-the-shelf hardware and software components and can be easily transfered to any ROS enabled UAVs.
Challenges of Applying E-Learning in the Libyan Higher Education System
Venue: arXiv cs.CY 2021
Year: 2021

The adoption of ICT in classrooms is very important in order to improve education quality, promote effective management of knowledge, and improve delivery of knowledge in higher education. Some of the Libyan universities have already started using E-learning in classrooms, but many challenges are still hindering that adoption. This paper endeavors to find the obstacles that may face the adoption of E-learning in Libya and sketches out the possible solutions. Further, it highlights the potentials for the adoption of E-learning in the higher education system in Libya using both qualitative and quantitative approaches. Both questioner and interview have been used on a focused group to collect the data. Teachers and students at Al Asmarya Islamic University have been selected as a sample for this study. This paper reveals that the challenges hindering teachers and students from using ICT and E-learning are: the lack of knowledge about ICT and E-learning, the lack of ICT infrastructure, and the lack of financial support. However, the participants show a high level of interest in applying the ICT and E-learning in the university despite the unsuitability of the environment.
Contextual Skipgram: Training Word Representation Using Context Information
Venue: arXiv cs.CL 2021
Year: 2021

The skip-gram (SG) model learns word representation by predicting the words surrounding a center word from unstructured text data. However, not all words in the context window contribute to the meaning of the center word. For example, less relevant words could be in the context window, hindering the SG model from learning a better quality representation. In this paper, we propose an enhanced version of the SG that leverages context information to produce word representation. The proposed model, Contextual Skip-gram, is designed to predict contextual words with both the center words and the context information. This simple idea helps to reduce the impact of irrelevant words on the training process, thus enhancing the final performance
Constructing a Distance Sensitivity Oracle in $O(n^{2.5794}M)$ Time
Venue: arXiv cs.DS 2021
Year: 2021

We continue the study of distance sensitivity oracles (DSOs). Given a directed graph $G$ with $n$ vertices and edge weights in $\{1, 2, \dots, M\}$, we want to build a data structure such that given any source vertex $u$, any target vertex $v$, and any failure $f$ (which is either a vertex or an edge), it outputs the length of the shortest path from $u$ to $v$ not going through $f$. Our main result is a DSO with preprocessing time $O(n^{2.5794}M)$ and constant query time. Previously, the best preprocessing time of DSOs for directed graphs is $O(n^{2.7233}M)$, and even in the easier case of undirected graphs, the best preprocessing time is $O(n^{2.6865}M)$ [Ren, ESA 2020]. One drawback of our DSOs, though, is that it only supports distance queries but not path queries. Our main technical ingredient is an algorithm that computes the inverse of a degree-$d$ polynomial matrix (i.e. a matrix whose entries are degree-$d$ univariate polynomials) modulo $x^r$. The algorithm is adapted from [Zhou, Labahn, and Storjohann, Journal of Complexity, 2015], and we replace some of its intermediate steps with faster rectangular matrix multiplication algorithms. We also show how to compute unique shortest paths in a directed graph with edge weights in $\{1, 2, \dots, M\}$, in $O(n^{2.5286}M)$ time. This algorithm is crucial in the preprocessing algorithm of our DSO. Our solution improves the $O(n^{2.6865}M)$ time bound in [Ren, ESA 2020], and matches the current best time bound for computing all-pairs shortest paths.
Localization using Mobile Wireless Sensor Networks
Venue: arXiv cs.NI 2021
Year: 2021

Wireless Sensor Networks (WSNs) are groups of spatially distributed and dedicated autonomous sensors for monitoring (and recording) the physical conditions of the environment (and organizing the collected data at a central location). They have been a topic of interest due to their versatility and diverse capabilities despite having simple sensors measuring local quantities such as temperature, pH, or pressure. We delve into understanding how such networks can be utilized for localization, and propose a technique for improving conditions of living for animals and humans on the IIT Bombay campus.
Open-Retrieval Conversational Machine Reading
Venue: arXiv cs.CL 2021
Year: 2021

In conversational machine reading, systems need to interpret natural language rules, answer high-level questions such as "May I qualify for VA health care benefits?", and ask follow-up clarification questions whose answer is necessary to answer the original question. However, existing works assume the rule text is provided for each user question, which neglects the essential retrieval step in real scenarios. In this work, we propose and investigate an open-retrieval setting of conversational machine reading. In the open-retrieval setting, the relevant rule texts are unknown so that a system needs to retrieve question-relevant evidence from a collection of rule texts, and answer users' high-level questions according to multiple retrieved rule texts in a conversational manner. We propose MUDERN, a Multi-passage Discourse-aware Entailment Reasoning Network which extracts conditions in the rule texts through discourse segmentation, conducts multi-passage entailment reasoning to answer user questions directly, or asks clarification follow-up questions to inquiry more information. On our created OR-ShARC dataset, MUDERN achieves the state-of-the-art performance, outperforming existing single-passage conversational machine reading models as well as a new multi-passage conversational machine reading baseline by a large margin. In addition, we conduct in-depth analyses to provide new insights into this new setting and our model.
ACTA: A Mobile-Health Solution for Integrated Nudge-Neurofeedback Training for Senior Citizens
Venue: arXiv cs.CY 2021
Year: 2021

As the worldwide population gets increasingly aged, in-home telemedicine and mobile-health solutions represent promising services to promote active and independent aging and to contribute to a paradigm shift towards patient-centric healthcare. In this work, we present ACTA (Advanced Cognitive Training for Aging), a prototype mobile-health solution to provide advanced cognitive training for senior citizens with mild cognitive impairments. We disclose here the conceptualization of ACTA as the integration of two promising rehabilitation strategies: the "Nudge theory", from the cognitive domain, and the neurofeedback, from the neuroscience domain. Moreover, in ACTA we exploit the most advanced machine learning techniques to deliver customized and fully adaptive support to the elderly, while training in an ecological environment. ACTA represents the next-step beyond SENIOR, an earlier mobile-health project for cognitive training based on Nudge theory, currently ongoing in Lombardy Region. Beyond SENIOR, ACTA represents a highly-usable, accessible, low-cost, new-generation mobile-health solution to promote independent aging and effective motor-cognitive training support, while empowering the elderly in their own aging.
Local Mending
Venue: arXiv cs.DC 2021
Year: 2021

In this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far one needs to modify a partial solution in order to "patch a hole." We explore how mendability is connected to the existence of efficient algorithms, especially in distributed, parallel, and fault-tolerant settings. It is easy to see that $O(1)$-mendable problems are also solvable in $O(\log^* n)$ rounds in the LOCAL model of distributed computing. One of the surprises is that in paths and cycles, a converse also holds in the following sense: if a problem $Π$ can be solved in $O(\log^* n)$, there is always a restriction $Π' \subseteq Π$ that is still efficiently solvable but that is also $O(1)$-mendable. We also explore the structure of the landscape of mendability. For example, we show that in trees, the mending radius of any locally checkable problem is $O(1)$, $Θ(\log n)$, or $Θ(n)$, while in general graphs the structure is much more diverse.
Learning Visual Models using a Knowledge Graph as a Trainer
Venue: arXiv cs.CV 2021
Year: 2021

Traditional computer vision approaches, based on neural networks (NN), are typically trained on a large amount of image data. By minimizing the cross-entropy loss between a prediction and a given class label, the NN and its visual embedding space are learned to fulfill a given task. However, due to the sole dependence on the image data distribution of the training domain, these models tend to fail when applied to a target domain that differs from their source domain. To learn a more robust NN to domain shifts, we propose the knowledge graph neural network (KG-NN), a neuro-symbolic approach that supervises the training using image-data-invariant auxiliary knowledge. The auxiliary knowledge is first encoded in a knowledge graph with respective concepts and their relationships, which is then transformed into a dense vector representation via an embedding method. Using a contrastive loss function, KG-NN learns to adapt its visual embedding space and thus its weights according to the image-data invariant knowledge graph embedding space. We evaluate KG-NN on visual transfer learning tasks for classification using the mini-ImageNet dataset and its derivatives, as well as road sign recognition datasets from Germany and China. The results show that a visual model trained with a knowledge graph as a trainer outperforms a model trained with cross-entropy in all experiments, in particular when the domain gap increases. Besides better performance and stronger robustness to domain shifts, these KG-NN adapts to multiple datasets and classes without suffering heavily from catastrophic forgetting.
Vote Delegation and Misbehavior
Venue: arXiv cs.GT 2021
Year: 2021

We study vote delegation with "well-behaving" and "misbehaving" agents and compare it with conventional voting. Typical examples for vote delegation are validation or governance tasks on blockchains. There is a majority of well-behaving agents, but they may abstain or delegate their vote to other agents since voting is costly. Misbehaving agents always vote. We compare conventional voting allowing for abstention with vote delegation. Preferences of voters are private information and a positive outcome is achieved if well-behaving agents win. We illustrate that vote delegation leads to quite different outcomes than conventional voting with abstention. In particular, we obtain three insights: First, if the number of misbehaving voters, denoted by f , is high, both voting methods fail to deliver a positive outcome. Second, if f takes an intermediate value, conventional voting delivers a positive outcome, while vote delegation fails with probability one. Third, if f is low, delegation delivers a positive outcome with higher probability than conventional voting. Finally, our results characterize worst-case outcomes that can happen in a liquid democracy.
DESED-FL and URBAN-FL: Federated Learning Datasets for Sound Event Detection
Venue: arXiv cs.SD 2021
Year: 2021

Research on sound event detection (SED) in environmental settings has seen increased attention in recent years. The large amounts of (private) domestic or urban audio data needed raise significant logistical and privacy concerns. The inherently distributed nature of these tasks, make federated learning (FL) a promising approach to take advantage of largescale data while mitigating privacy issues. While FL has also seen increased attention recently, to the best of our knowledge there is no research towards FL for SED. To address this gap and foster further research in this field, we create and publish novel FL datasets for SED in domestic and urban environments. Furthermore, we provide baseline results on the datasets in a FL context for three deep neural network architectures. The results indicate that FL is a promising approach for SED, but faces challenges with divergent data distributions inherent to distributed client edge devices.
Automated Curriculum Learning for Embodied Agents: A Neuroevolutionary Approach
Venue: arXiv cs.NE 2021
Year: 2021

We demonstrate how an evolutionary algorithm can be extended with a curriculum learning process that selects automatically the environmental conditions in which the evolving agents are evaluated. The environmental conditions are selected so to adjust the level of difficulty to the ability level of the current evolving agents and so to challenge the weaknesses of the evolving agents. The method does not require domain knowledge and does not introduce additional hyperparameters. The results collected on two benchmark problems, that require to solve a task in significantly varying environmental conditions, demonstrate that the method proposed outperforms conventional algorithms and generates solutions that are robust to variations
Mining API Usage Scenarios from Stack Overflow
Venue: arXiv cs.SE 2021
Year: 2021

We propose a framework to mine API usage scenarios from Stack Overflow. Each task consists of a code example, the task description, and the reactions of developers towards the code example. First, we present an algorithm to automatically link a code example in a forum post to an API mentioned in the textual contents of the forum post. Second, we generate a natural language description of the task by summarizing the discussions around the code example. Third, we automatically associate developers reactions (i.e., positive and negative opinions) towards the code example to offer information about code quality. We evaluate the algorithms using three benchmarks.
Blockchain-based Security Services for Fog Computing
Venue: arXiv cs.CR 2021
Year: 2021

Fog computing is a paradigm for distributed computing that enables sharing of resources such as computing, storage and network services. Unlike cloud computing, fog computing platforms primarily support {\em non-functional properties} such as location awareness, mobility and reduced latency. This emerging paradigm has many potential applications in domains such as smart grids, smart cities, and transport management. Most of these domains collect and monitor personal information through edge devices to offer personalized services. A {\em centralized} server either at the level of cloud or fog, has been found ineffective to provide a high degree of security and privacy-preserving services. Blockchain technology supports the development of {\em decentralized} applications designed around the principles of immutability, cryptography, consistency preserving consensus protocols and smart contracts. Hence blockchain technology has emerged as a preferred technology in recent times to build trustworthy distributed applications. The chapter describes the potential of blockchain technology to realize security services such as authentication, secured communication, availability, privacy and trust management to support the development of dependable fog services.
SimFaaS: A Performance Simulator for Serverless Computing Platforms
Venue: arXiv cs.DC 2021
Year: 2021

Developing accurate and extendable performance models for serverless platforms, aka Function-as-a-Service (FaaS) platforms, is a very challenging task. Also, implementation and experimentation on real serverless platforms is both costly and time-consuming. However, at the moment, there is no comprehensive simulation tool or framework to be used instead of the real platform. As a result, in this paper, we fill this gap by proposing a simulation platform, called SimFaaS, which assists serverless application developers to develop optimized Function-as-a-Service applications in terms of cost and performance. On the other hand, SimFaaS can be leveraged by FaaS providers to tailor their platforms to be workload-aware so that they can increase profit and quality of service at the same time. Also, serverless platform providers can evaluate new designs, implementations, and deployments on SimFaaS in a timely and cost-efficient manner. SimFaaS is open-source, well-documented, and publicly available, making it easily usable and extendable to incorporate more use case scenarios in the future. Besides, it provides performance engineers with a set of tools that can calculate several characteristics of serverless platform internal states, which is otherwise hard (mostly impossible) to extract from real platforms. We show how SimFaaS facilitates the prediction of essential performance metrics such as average response time, probability of cold start, and the average number of instances reflecting the infrastructure cost incurred by the serverless computing provider. We evaluate the accuracy and applicability of SimFaaS by comparing the prediction results with real-world traces from Amazon AWS Lambda.
Stackelberg-Pareto Synthesis (Full Version)
Venue: arXiv cs.GT 2021
Year: 2021

In this paper, we study the framework of two-player Stackelberg games played on graphs in which Player 0 announces a strategy and Player 1 responds rationally with a strategy that is an optimal response. While it is usually assumed that Player 1 has a single objective, we consider here the new setting where he has several. In this context, after responding with his strategy, Player 1 gets a payoff in the form of a vector of Booleans corresponding to his satisfied objectives. Rationality of Player 1 is encoded by the fact that his response must produce a Pareto-optimal payoff given the strategy of Player 0. We study the Stackelberg-Pareto Synthesis problem which asks whether Player 0 can announce a strategy which satisfies his objective, whatever the rational response of Player 1. For games in which objectives are either all parity or all reachability objectives, we show that this problem is fixed-parameter tractable and NEXPTIME-complete. This problem is already NP-complete in the simple case of reachability objectives and graphs that are trees.
Deep Learning Anomaly Detection for Cellular IoT with Applications in Smart Logistics
Venue: arXiv cs.NI 2021
Year: 2021

The number of connected Internet of Things (IoT) devices within cyber-physical infrastructure systems grows at an increasing rate. This poses significant device management and security challenges to current IoT networks. Among several approaches to cope with these challenges, data-based methods rooted in deep learning (DL) are receiving an increased interest. In this paper, motivated by the upcoming surge of 5G IoT connectivity in industrial environments, we propose to integrate a DL-based anomaly detection (AD) as a service into the 3GPP mobile cellular IoT architecture. The proposed architecture embeds autoencoder based anomaly detection modules both at the IoT devices (ADM-EDGE) and in the mobile core network (ADM-FOG), thereby balancing between the system responsiveness and accuracy. We design, integrate, demonstrate and evaluate a testbed that implements the above service in a real-world deployment integrated within the 3GPP Narrow-Band IoT (NB-IoT) mobile operator network.