OpenRaiser/Intern-Atlas huggingface dataset:
Straggler Mitigation through Unequal Error Protection for Distributed Approximate Matrix Multiplication
Venue: arXiv cs.DC 2021
Year: 2021

Large-scale machine learning and data mining methods routinely distribute computations across multiple agents to parallelize processing. The time required for the computations at the agents is affected by the availability of local resources and/or poor channel conditions giving rise to the "straggler problem". As a remedy to this problem, we employ Unequal Error Protection (UEP) codes to obtain an approximation of the matrix product in the distributed computation setting to provide higher protection for the blocks with higher effect on the final result. We characterize the performance of the proposed approach from a theoretical perspective by bounding the expected reconstruction error for matrices with uncorrelated entries. We also apply the proposed coding strategy to the computation of the back-propagation step in the training of a Deep Neural Network (DNN) for an image classification task in the evaluation of the gradients. Our numerical experiments show that it is indeed possible to obtain significant improvements in the overall time required to achieve the DNN training convergence by producing approximation of matrix products using UEP codes in the presence of stragglers.
Restoring Execution Environments of Jupyter Notebooks
Venue: arXiv cs.SE 2021
Year: 2021

More than ninety percent of published Jupyter notebooks do not state dependencies on external packages. This makes them non-executable and thus hinders reproducibility of scientific results. We present SnifferDog, an approach that 1) collects the APIs of Python packages and versions, creating a database of APIs; 2) analyzes notebooks to determine candidates for required packages and versions; and 3) checks which packages are required to make the notebook executable (and ideally, reproduce its stored results). In its evaluation, we show that SnifferDog precisely restores execution environments for the largest majority of notebooks, making them immediately executable for end users.
Wireless Coded Caching Can Overcome the Worst-User Bottleneck by Exploiting Finite File Sizes
Venue: arXiv cs.IT 2021
Year: 2021

We address the worst-user bottleneck of wireless coded caching, which is known to severely diminish cache-aided multicasting gains due to the fundamental worst-channel limitation of multicasting transmission. We consider the quasi-static Rayleigh fading Broadcast Channel, for which we first show that the effective coded caching gain of the XOR-based standard coded-caching scheme completely vanishes in the low-SNR regime. Then, we reveal that this collapse is not intrinsic to coded caching. We do so by presenting a novel scheme that can fully recover the coded caching gains by capitalizing on one aspect that has to date remained unexploited: the shared side information brought about by the effectively unavoidable file-size constraint. As a consequence, the worst-user effect is dramatically ameliorated, as it is substituted by a much more subtle worst-group-of-users effect, where the suggested grouping is fixed, and it is decided before the channel or the demands are known. In some cases, the theoretical gains are completely recovered, and this is done without any user selection technique. We analyze the achievable rate performance of the proposed scheme and derive insightful performance approximations which prove to be very precise.
Computing Subset Feedback Vertex Set via Leafage
Venue: arXiv cs.DS 2021
Year: 2021

A typical example that behaves computationally different in subclasses of chordal graphs is the \textsc{Subset Feedback Vertex Set} (SFVS) problem: given a vertex-weighted graph $G=(V,E)$ and a set $S\subseteq V$, the \textsc{Subset Feedback Vertex Set} (SFVS) problem asks for a vertex set of minimum weight that intersects all cycles containing a vertex of $S$. SFVS is known to be polynomial-time solvable on interval graphs, whereas SFVS remains \NP-complete on split graphs and, consequently, on chordal graphs. Towards a better understanding of the complexity of SFVS on subclasses of chordal graphs, we exploit structural properties of a tree model in order to cope with the hardness of SFVS. Here we consider variants of the \emph{leafage} that measures the minimum number of leaves in a tree model. We show that SFVS can be solved in polynomial time for every chordal graph with bounded leafage. In particular, given a chordal graph on $n$ vertices with leafage $\ell$, we provide an algorithm for SFVS with running time $n^{O(\ell)}$. We complement our result by showing that SFVS is \W[1]-hard parameterized by $\ell$. Pushing further our positive result, it is natural to consider a slight generalization of leafage, the \emph{vertex leafage}, which measures the smallest number among the maximum number of leaves of all subtrees in a tree model. However, we show that it is unlikely to obtain a similar result, as we prove that SFVS remains \NP-complete on undirected path graphs, i.e., graphs having vertex leafage at most two. Moreover, we strengthen previously-known polynomial-time algorithm for SFVS on rooted path graphs that form a proper subclass of undirected path graphs and graphs of mim-width one.
An Internet of Things Service Roadmap
Venue: arXiv cs.NI 2021
Year: 2021

We propose a roadmap for leveraging the tremendous opportunities the Internet of Things (IoT) has to offer. We argue that the combination of the recent advances in service computing and IoT technology provide a unique framework for innovations not yet envisaged, as well as the emergence of yet-to-be-developed IoT applications. This roadmap covers: emerging novel IoT services, articulation of major research directions, and suggestion of a roadmap to guide the IoT and service computing community to address key IoT service challenges.
Toward Automated Generation of Affective Gestures from Text:A Theory-Driven Approach
Venue: arXiv cs.RO 2021
Year: 2021

Communication in both human-human and human-robot interac-tion (HRI) contexts consists of verbal (speech-based) and non-verbal(facial expressions, eye gaze, gesture, body pose, etc.) components.The verbal component contains semantic and affective information;accordingly, HRI work on the gesture component so far has focusedon rule-based (mapping words to gestures) and data-driven (deep-learning) approaches to generating speech-paired gestures basedon either semantics or the affective state. Consequently, most ges-ture systems are confined to producing either semantically-linkedor affect-based gesticures. This paper introduces an approach forenabling human-robot communication based on a theory-drivenapproach to generate speech-paired robot gestures using both se-mantic and affective information. Our model takes as input textand sentiment analysis, and generates robot gestures in terms oftheir shape, intensity, and speed.
It's A Match! Gesture Generation Using Expressive Parameter Matching
Venue: arXiv cs.HC 2021
Year: 2021

Automatic gesture generation from speech generally relies on implicit modelling of the nondeterministic speech-gesture relationship and can result in averaged motion lacking defined form. Here, we propose a database-driven approach of selecting gestures based on specific motion characteristics that have been shown to be associated with the speech audio. We extend previous work that identified expressive parameters of gesture motion that can both be predicted from speech and are perceptually important for a good speech-gesture match, such as gesture velocity and finger extension. A perceptual study was performed to evaluate the appropriateness of the gestures selected with our method. We compare our method with two baseline selection methods. The first respects timing, the desired onset and duration of a gesture, but does not match gesture form in other ways. The second baseline additionally disregards the original gesture timing for selecting gestures. The gesture sequences from our method were rated as a significantly better match to the speech than gestures selected by either baseline method.
Catala: A Programming Language for the Law
Venue: arXiv cs.PL 2021
Year: 2021

Law at large underpins modern society, codifying and governing many aspects of citizens' daily lives. Oftentimes, law is subject to interpretation, debate and challenges throughout various courts and jurisdictions. But in some other areas, law leaves little room for interpretation, and essentially aims to rigorously describe a computation, a decision procedure or, simply said, an algorithm. Unfortunately, prose remains a woefully inadequate tool for the job. The lack of formalism leaves room for ambiguities; the structure of legal statutes, with many paragraphs and sub-sections spread across multiple pages, makes it hard to compute the intended outcome of the algorithm underlying a given text; and, as with any other piece of poorly-specified critical software, the use of informal language leaves corner cases unaddressed. We introduce Catala, a new programming language that we specifically designed to allow a straightforward and systematic translation of statutory law into an executable implementation. Catala aims to bring together lawyers and programmers through a shared medium, which together they can understand, edit and evolve, bridging a gap that often results in dramatically incorrect implementations of the law. We have implemented a compiler for Catala, and have proven the correctness of its core compilation steps using the F* proof assistant. We evaluate Catala on several legal texts that are algorithms in disguise, notably section 121 of the US federal income tax and the byzantine French family benefits; in doing so, we uncover a bug in the official implementation. We observe as a consequence of the formalization process that using Catala enables rich interactions between lawyers and programmers, leading to a greater understanding of the original legislative intent, while producing a correct-by-construction executable specification reusable by the greater software ecosystem.
Time granularity impact on propagation of disruptions in a system-of-systems simulation of infrastructure and business networks
Venue: arXiv cs.SI 2021
Year: 2021

System-of-systems (SoS) approach is often used for simulating disruptions to business and infrastructure system networks allowing for integration of several models into one simulation. However, the integration is frequently challenging as each system is designed individually with different characteristics, such as time granularity. Understanding the impact of time granularity on propagation of disruptions between businesses and infrastructure systems and finding the appropriate granularity for the SoS simulation remain as major challenges. To tackle these, we explore how time granularity, recovery time, and disruption size affect the propagation of disruptions between constituent systems of an SoS simulation. To address this issue, we developed a High Level Architecture (HLA) simulation of 3 networks and performed a series of simulation experiments. Our results revealed that time granularity and especially recovery time have huge impact on propagation of disruptions. Consequently, we developed a model for selecting an appropriate time granularity for an SoS simulation based on expected recovery time. Our simulation experiments show that time granularity should be less than 1.13 of expected recovery time. We identified some areas for future research centered around extending the experimental factors space.
Epistemic Signaling Games for Cyber Deception with Asymmetric Recognition
Venue: arXiv cs.CR 2021
Year: 2021

This study provides a model of cyber deception with asymmetric recognition represented by private beliefs. Signaling games, which are often used in existing works, are built on the implicit premise that the receiver's belief is public information. However, this assumption, which leads to symmetric recognition, is unrealistic in adversarial decision making. For a precise evaluation of risks arising from cognitive gaps, this paper proposes epistemic signaling games based on the Mertens-Zamir model, which explicitly quantifies players' asymmetric recognition. Equilibria of the games are analytically characterized with an interpretation.
Technical Leverage in a Software Ecosystem: Development Opportunities and Security Risks
Venue: arXiv cs.SE 2021
Year: 2021

In finance, leverage is the ratio between assets borrowed from others and one's own assets. A matching situation is present in software: by using free open-source software (FOSS) libraries a developer leverages on other people's code to multiply the offered functionalities with a much smaller own codebase. In finance as in software, leverage magnifies profits when returns from borrowing exceed costs of integration, but it may also magnify losses, in particular in the presence of security vulnerabilities. We aim to understand the level of technical leverage in the FOSS ecosystem and whether it can be a potential source of security vulnerabilities. Also, we introduce two metrics change distance and change direction to capture the amount and the evolution of the dependency on third-party libraries. The application of the proposed metrics on 8494 distinct library versions from the FOSS Maven-based Java libraries shows that small and medium libraries (less than 100KLoC) have disproportionately more leverage on FOSS dependencies in comparison to large libraries. We show that leverage pays off as leveraged libraries only add a 4% delay in the time interval between library releases while providing four times more code than their own. However, libraries with such leverage (i.e., 75% of libraries in our sample) also have 1.6 higher odds of being vulnerable in comparison to the libraries with lower leverage. We provide an online demo for computing the proposed metrics for real-world software libraries available under the following URL: https://techleverage.eu/.
Neural model robustness for skill routing in large-scale conversational AI systems: A design choice exploration
Venue: arXiv cs.CL 2021
Year: 2021

Current state-of-the-art large-scale conversational AI or intelligent digital assistant systems in industry comprises a set of components such as Automatic Speech Recognition (ASR) and Natural Language Understanding (NLU). For some of these systems that leverage a shared NLU ontology (e.g., a centralized intent/slot schema), there exists a separate skill routing component to correctly route a request to an appropriate skill, which is either a first-party or third-party application that actually executes on a user request. The skill routing component is needed as there are thousands of skills that can either subscribe to the same intent and/or subscribe to an intent under specific contextual conditions (e.g., device has a screen). Ensuring model robustness or resilience in the skill routing component is an important problem since skills may dynamically change their subscription in the ontology after the skill routing model has been deployed to production. We show how different modeling design choices impact the model robustness in the context of skill routing on a state-of-the-art commercial conversational AI system, specifically on the choices around data augmentation, model architecture, and optimization method. We show that applying data augmentation can be a very effective and practical way to drastically improve model robustness.
New Directions in Science Emerge from Disconnection and Discord
Venue: arXiv cs.DL 2021
Year: 2021

Science is built on the scholarly consensus that shifts with time. This raises the question of how new and revolutionary ideas are evaluated and become accepted into the canon of science. Using two recently proposed metrics, we identify papers with high atypicality, which models how research draws upon novel combinations of prior research, and evaluate disruption, which captures the degree to which a study creates a new direction by eclipsing its intellectual forebears. Atypical papers are nearly two times more likely to disrupt science than conventional papers, but this is a slow process taking ten years or longer for disruption scores to converge. We provide the first computational model reformulating atypicality as the distance across latent knowledge spaces learned by neural networks. The evolution of this knowledge space characterizes how yesterday's novelty forms today's scientific conventions, which condition the novelty--and surprise--of tomorrow's breakthroughs.
A General Method to Find Highly Coordinating Communities in Social Media through Inferred Interaction Links
Venue: arXiv cs.SI 2021
Year: 2021

Political misinformation, astroturfing and organised trolling are online malicious behaviours with significant real-world effects. Many previous approaches examining these phenomena have focused on broad campaigns rather than the small groups responsible for instigating or sustaining them. To reveal latent (i.e., hidden) networks of cooperating accounts, we propose a novel temporal window approach that relies on account interactions and metadata alone. It detects groups of accounts engaging in various behaviours that, in concert, come to execute different goal-based strategies, a number of which we describe. The approach relies upon a pipeline that extracts relevant elements from social media posts, infers connections between accounts based on criteria matching the coordination strategies to build an undirected weighted network of accounts, which is then mined for communities exhibiting high levels of evidence of coordination using a novel community extraction method. We address the temporal aspect of the data by using a windowing mechanism, which may be suitable for near real-time application. We further highlight consistent coordination with a sliding frame across multiple windows and application of a decay factor. Our approach is compared with other recent similar processing approaches and community detection methods and is validated against two relevant datasets with ground truth data, using content, temporal, and network analyses, as well as with the design, training and application of three one-class classifiers built using the ground truth; its utility is furthermore demonstrated in two case studies of contentious online discussions.
Efficient Encrypted Inference on Ensembles of Decision Trees
Venue: arXiv cs.CR 2021
Year: 2021

Data privacy concerns often prevent the use of cloud-based machine learning services for sensitive personal data. While homomorphic encryption (HE) offers a potential solution by enabling computations on encrypted data, the challenge is to obtain accurate machine learning models that work within the multiplicative depth constraints of a leveled HE scheme. Existing approaches for encrypted inference either make ad-hoc simplifications to a pre-trained model (e.g., replace hard comparisons in a decision tree with soft comparators) at the cost of accuracy or directly train a new depth-constrained model using the original training set. In this work, we propose a framework to transfer knowledge extracted by complex decision tree ensembles to shallow neural networks (referred to as DTNets) that are highly conducive to encrypted inference. Our approach minimizes the accuracy loss by searching for the best DTNet architecture that operates within the given depth constraints and training this DTNet using only synthetic data sampled from the training data distribution. Extensive experiments on real-world datasets demonstrate that these characteristics are critical in ensuring that DTNet accuracy approaches that of the original tree ensemble. Our system is highly scalable and can perform efficient inference on batched encrypted (134 bits of security) data with amortized time in milliseconds. This is approximately three orders of magnitude faster than the standard approach of applying soft comparison at the internal nodes of the ensemble trees.
Exploring the effect of streamed social media data variations on social network analysis
Venue: arXiv cs.SI 2021
Year: 2021

To study the effects of Online Social Network (OSN) activity on real-world offline events, researchers need access to OSN data, the reliability of which has particular implications for social network analysis. This relates not only to the completeness of any collected dataset, but also to constructing meaningful social and information networks from them. In this multidisciplinary study, we consider the question of constructing traditional social networks from OSN data and then present several measurement case studies showing how variations in collected OSN data affects social network analyses. To this end we developed a systematic com parison methodology, which we applied to five pairs of parallel datasets collected from Twitter in four case studies. We found considerable differences in several of the datasets collected with different tools and that these variations significantly alter the results of subsequent analyses. Our results lead to a set of guidelines for researchers planning to collect online data streams to infer social networks.
MD-MTL: An Ensemble Med-Multi-Task Learning Package for DiseaseScores Prediction and Multi-Level Risk Factor Analysis
Venue: arXiv cs.LG 2021
Year: 2021

While many machine learning methods have been used for medical prediction and risk factor analysis on healthcare data, most prior research has involved single-task learning (STL) methods. However, healthcare research often involves multiple related tasks. For instance, implementation of disease scores prediction and risk factor analysis in multiple subgroups of patients simultaneously and risk factor analysis at multi-levels synchronously. In this paper, we developed a new ensemble machine learning Python package based on multi-task learning (MTL), referred to as the Med-Multi-Task Learning (MD-MTL) package and applied it in predicting disease scores of patients, and in carrying out risk factor analysis on multiple subgroups of patients simultaneously. Our experimental results on two datasets demonstrate the utility of the MD-MTL package, and show the advantage of MTL (vs. STL), when analyzing data that is organized into different categories (tasks, which can be various age groups, different levels of disease severity, etc.).
Towards Evaluating the Robustness of Deep Diagnostic Models by Adversarial Attack
Venue: arXiv cs.CV 2021
Year: 2021

Deep learning models (with neural networks) have been widely used in challenging tasks such as computer-aided disease diagnosis based on medical images. Recent studies have shown deep diagnostic models may not be robust in the inference process and may pose severe security concerns in clinical practice. Among all the factors that make the model not robust, the most serious one is adversarial examples. The so-called "adversarial example" is a well-designed perturbation that is not easily perceived by humans but results in a false output of deep diagnostic models with high confidence. In this paper, we evaluate the robustness of deep diagnostic models by adversarial attack. Specifically, we have performed two types of adversarial attacks to three deep diagnostic models in both single-label and multi-label classification tasks, and found that these models are not reliable when attacked by adversarial example. We have further explored how adversarial examples attack the models, by analyzing their quantitative classification results, intermediate features, discriminability of features and correlation of estimated labels for both original/clean images and those adversarial ones. We have also designed two new defense methods to handle adversarial examples in deep diagnostic models, i.e., Multi-Perturbations Adversarial Training (MPAdvT) and Misclassification-Aware Adversarial Training (MAAdvT). The experimental results have shown that the use of defense methods can significantly improve the robustness of deep diagnostic models against adversarial attacks.