OpenRaiser/Intern-Atlas huggingface dataset:
ChartStory: Automated Partitioning, Layout, and Captioning of Charts into Comic-Style Narratives
Venue: arXiv cs.HC 2021
Year: 2021

Visual data storytelling is gaining importance as a means of presenting data-driven information or analysis results, especially to the general public. This has resulted in design principles being proposed for data-driven storytelling, and new authoring tools being created to aid such storytelling. However, data analysts typically lack sufficient background in design and storytelling to make effective use of these principles and authoring tools. To assist this process, we present ChartStory for crafting data stories from a collection of user-created charts, using a style akin to comic panels to imply the underlying sequence and logic of data-driven narratives. Our approach is to operationalize established design principles into an advanced pipeline which characterizes charts by their properties and similarity, and recommends ways to partition, layout, and caption story pieces to serve a narrative. ChartStory also augments this pipeline with intuitive user interactions for visual refinement of generated data comics. We extensively and holistically evaluate ChartStory via a trio of studies. We first assess how the tool supports data comic creation in comparison to a manual baseline tool. Data comics from this study are subsequently compared and evaluated to ChartStory's automated recommendations by a team of narrative visualization practitioners. This is followed by a pair of interview studies with data scientists using their own datasets and charts who provide an additional assessment of the system. We find that ChartStory provides cogent recommendations for narrative generation, resulting in data comics that compare favorably to manually-created ones.
Off-Belief Learning
Venue: arXiv cs.AI 2021
Year: 2021

The standard problem setting in Dec-POMDPs is self-play, where the goal is to find a set of policies that play optimally together. Policies learned through self-play may adopt arbitrary conventions and implicitly rely on multi-step reasoning based on fragile assumptions about other agents' actions and thus fail when paired with humans or independently trained agents at test time. To address this, we present off-belief learning (OBL). At each timestep OBL agents follow a policy $π_1$ that is optimized assuming past actions were taken by a given, fixed policy ($π_0$), but assuming that future actions will be taken by $π_1$. When $π_0$ is uniform random, OBL converges to an optimal policy that does not rely on inferences based on other agents' behavior (an optimal grounded policy). OBL can be iterated in a hierarchy, where the optimal policy from one level becomes the input to the next, thereby introducing multi-level cognitive reasoning in a controlled manner. Unlike existing approaches, which may converge to any equilibrium policy, OBL converges to a unique policy, making it suitable for zero-shot coordination (ZSC). OBL can be scaled to high-dimensional settings with a fictitious transition mechanism and shows strong performance in both a toy-setting and the benchmark human-AI & ZSC problem Hanabi.
Dynamic Resource Management for Providing QoS in Drone Delivery Systems
Venue: arXiv cs.RO 2021
Year: 2021

Drones have been considered as an alternative means of package delivery to reduce the delivery cost and time. Due to the battery limitations, the drones are best suited for last-mile delivery, i.e., the delivery from the package distribution centers (PDCs) to the customers. Since a typical delivery system consists of multiple PDCs, each having random and time-varying demands, the dynamic drone-to-PDC allocation would be of great importance in meeting the demand in an efficient manner. In this paper, we study the dynamic UAV assignment problem for a drone delivery system with the goal of providing measurable Quality of Service (QoS) guarantees. We adopt a queueing theoretic approach to model the customer-service nature of the problem. Furthermore, we take a deep reinforcement learning approach to obtain a dynamic policy for the re-allocation of the UAVs. This policy guarantees a probabilistic upper-bound on the queue length of the packages waiting in each PDC, which is beneficial from both the service provider's and the customers' viewpoints. We evaluate the performance of our proposed algorithm by considering three broad arrival classes, including Bernoulli, Time-Varying Bernoulli, and Markov-Modulated Bernoulli arrivals. Our results show that the proposed method outperforms the baselines, particularly in scenarios with Time-Varying and Markov-Modulated Bernoulli arrivals, which are more representative of real-world demand patterns. Moreover, our algorithm satisfies the QoS constraints in all the studied scenarios while minimizing the average number of UAVs in use.
Combining IOTA and Attribute-Based Encryption for Access Control in the Internet of Things
Venue: arXiv cs.CR 2021
Year: 2021

Unauthorized resource access represents a typical security threat in the Internet of things (IoT), while distributed ledger technologies (e.g., blockchain and IOTA) hold great promise to address this threat. Although blockchain-based IoT access control schemes have been the most popular ones, they suffer from several significant limitations, such as high monetary cost and low throughput of processing access requests. To overcome these limitations, this paper proposes a novel IoT access control scheme by combining the fee-less IOTA technology and the Ciphertext-Policy Attribute-Based Encryption (CP-ABE) technology. To control the access to a resource, a token, which records access permissions to this resource, is encrypted by the CP-ABE technology and uploaded to the IOTA Tangle (i.e., the underlying database of IOTA). Any user can fetch the encrypted token from the Tangle, while only those who can decrypt this token are authorized to access the resource. In this way, the proposed scheme enables not only distributed, fee-less and scalable access control thanks to the IOTA but also fine-grained attribute-based access control thanks to the CP-ABE. We show the feasibility of our scheme by implementing a proof-of-concept prototype system and evaluate its performance in terms of access request processing throughput.
Hidden Backdoor Attack against Semantic Segmentation Models
Venue: arXiv cs.CR 2021
Year: 2021

Deep neural networks (DNNs) are vulnerable to the \emph{backdoor attack}, which intends to embed hidden backdoors in DNNs by poisoning training data. The attacked model behaves normally on benign samples, whereas its prediction will be changed to a particular target label if hidden backdoors are activated. So far, backdoor research has mostly been conducted towards classification tasks. In this paper, we reveal that this threat could also happen in semantic segmentation, which may further endanger many mission-critical applications ($e.g.$, autonomous driving). Except for extending the existing attack paradigm to maliciously manipulate the segmentation models from the image-level, we propose a novel attack paradigm, the \emph{fine-grained attack}, where we treat the target label ($i.e.$, annotation) from the object-level instead of the image-level to achieve more sophisticated manipulation. In the annotation of poisoned samples generated by the fine-grained attack, only pixels of specific objects will be labeled with the attacker-specified target class while others are still with their ground-truth ones. Experiments show that the proposed methods can successfully attack semantic segmentation models by poisoning only a small proportion of training data. Our method not only provides a new perspective for designing novel attacks but also serves as a strong baseline for improving the robustness of semantic segmentation methods.
New Separations Results for External Information
Venue: arXiv cs.CC 2021
Year: 2021

We obtain new separation results for the two-party external information complexity of boolean functions. The external information complexity of a function $f(x,y)$ is the minimum amount of information a two-party protocol computing $f$ must reveal to an outside observer about the input. We obtain the following results: 1. We prove an exponential separation between external and internal information complexity, which is the best possible; previously no separation was known. 2. We prove a near-quadratic separation between amortized zero-error communication complexity and external information complexity for total functions, disproving a conjecture of \cite{Bravermansurvey}. 3. We prove a matching upper showing that our separation result is tight.
Low-Rank Isomap Algorithm
Venue: arXiv cs.LG 2021
Year: 2021

The Isomap is a well-known nonlinear dimensionality reduction method that highly suffers from computational complexity. Its computational complexity mainly arises from two stages; a) embedding a full graph on the data in the ambient space, and b) a complete eigenvalue decomposition. Although the reduction of the computational complexity of the graphing stage has been investigated, yet the eigenvalue decomposition stage remains a bottleneck in the problem. In this paper, we propose the Low-Rank Isomap algorithm by introducing a projection operator on the embedded graph from the ambient space to a low-rank latent space to facilitate applying the partial eigenvalue decomposition. This approach leads to reducing the complexity of Isomap to a linear order while preserving the structural information during the dimensionality reduction process. The superiority of the Low-Rank Isomap algorithm compared to some state-of-art algorithms is experimentally verified on facial image clustering in terms of speed and accuracy.
On the determinization of event-clock input-driven pushdown automata
Venue: arXiv cs.FL 2021
Year: 2021

Input-driven pushdown automata (also known as visibly pushdown automata and as nested word automata) are a subclass of deterministic pushdown automata and a superclass of the parenthesis languages. Nguyen and Ogawa ("Event-clock visibly pushdown automata", SOFSEM 2009) defined a timed extension of these automata under the event-clock model, and showed that this model can be determinized using the method of region construction. This paper defines a further extension of this model with the event clock on the call-return operations, and proposes a new, direct determinization procedure for these automata: an $n$-state nondeterministic automaton with $k$ different clock constraints is transformed to a deterministic automaton with $2^{n^2}$ states, $2^{n^2+k}$ stack symbols and the same clock constraints as in the original automaton. The construction is shown to be asymptotically optimal with respect to both the number of states and the number of stack symbols.
Zero-Sum Semi-Markov Games with State-Action-Dependent Discount Factors
Venue: arXiv cs.GT 2021
Year: 2021

Semi-Markov model is one of the most general models for stochastic dynamic systems. This paper deals with a two-person zero-sum game for semi-Markov processes. We focus on the expected discounted payoff criterion with state-action-dependent discount factors. The state and action spaces are both Polish spaces, and the payoff function is $ω$-bounded. We first construct a fairly general model of semi-Markov games under a given semi-Markov kernel and a pair of strategies. Next, based on the standard regularity condition and the continuity-compactness condition for semi-Markov games, we derive a "drift condition" on the semi-Markov kernel and suppose that the discount factors have a positive lower bound, under which the existence of the value function and a pair of optimal stationary strategies of our semi-Markov game are proved by using the Shapley equation. Moreover, when the state and action spaces are both finite, a value iteration-type algorithm for computing the value function and $\varepsilon$-Nash equilibrium of the game is developed. The convergence of the algorithm is also proved. Finally, we conduct numerical examples to demonstrate our main results.
On the experiences of adopting automated data validation in an industrial machine learning project
Venue: arXiv cs.SE 2021
Year: 2021

Background: Data errors are a common challenge in machine learning (ML) projects and generally cause significant performance degradation in ML-enabled software systems. To ensure early detection of erroneous data and avoid training ML models using bad data, research and industrial practice suggest incorporating a data validation process and tool in ML system development process. Aim: The study investigates the adoption of a data validation process and tool in industrial ML projects. The data validation process demands significant engineering resources for tool development and maintenance. Thus, it is important to identify the best practices for their adoption especially by development teams that are in the early phases of deploying ML-enabled software systems. Method: Action research was conducted at a large-software intensive organization in telecommunications, specifically within the analytics R\&D organization for an ML use case of classifying faults from returned hardware telecommunication devices. Results: Based on the evaluation results and learning from our action research, we identified three best practices, three benefits, and two barriers to adopting the data validation process and tool in ML projects. We also propose a data validation framework (DVF) for systematizing the adoption of a data validation process. Conclusions: The results show that adopting a data validation process and tool in ML projects is an effective approach of testing ML-enabled software systems. It requires having an overview of the level of data (feature, dataset, cross-dataset, data stream) at which certain data quality tests can be applied.
Towards Fully Autonomous Drone-Based Last-Mile Delivery
Venue: arXiv cs.CY 2021
Year: 2021

The drone-based last-mile delivery is an emerging technology to deliver parcels using drones loaded on a truck. As more and more autonomous vehicles (AVs) will be available for delivery services, an opportunity is arising to fully automate drone-based last-mile delivery. In this paper, we integrate AVs with drone-based last-mile delivery aiming to fully automate the last-mile delivery process. We define a new problem called the autonomous vehicle routing problem with drones (A-VRPD). A-VRPD is to select AVs from a pool of available AVs and to schedule them to serve customers with an objective of minimizing the total operational cost. We formulate A-VRPD as an Integer Linear Programming (ILP) and propose a greedy algorithm to solve the problem based on real-world operational costs for different types of AVs, traveling distances calculated considering the current traffic conditions, and varying load capacities of AVs. Extensive simulations performed under various random delivery scenarios demonstrate that the proposed algorithm effectively increases profits for both the delivery company and AV owners compared with traditional VRP-D (and TSP-D) algorithm-based approaches.
Panoptic Lintention Network: Towards Efficient Navigational Perception for the Visually Impaired
Venue: arXiv cs.CV 2021
Year: 2021

Classic computer vision algorithms, instance segmentation, and semantic segmentation can not provide a holistic understanding of the surroundings for the visually impaired. In this paper, we utilize panoptic segmentation to assist the navigation of visually impaired people by offering both things and stuff awareness in the proximity of the visually impaired efficiently. To this end, we propose an efficient Attention module -- Lintention which can model long-range interactions in linear time using linear space. Based on Lintention, we then devise a novel panoptic segmentation model which we term Panoptic Lintention Net. Experiments on the COCO dataset indicate that the Panoptic Lintention Net raises the Panoptic Quality (PQ) from 39.39 to 41.42 with 4.6\% performance gain while only requiring 10\% fewer GFLOPs and 25\% fewer parameters in the semantic branch. Furthermore, a real-world test via our designed compact wearable panoptic segmentation system, indicates that our system based on the Panoptic Lintention Net accomplishes a relatively stable and exceptionally remarkable panoptic segmentation in real-world scenes.
Selective Encryption of the Versatile Video Coding Standard
Venue: arXiv cs.CR 2021
Year: 2021

Versatile video coding (VVC) is the next generation video coding standard developed by the joint video experts team (JVET) and released in July 2020. VVC introduces several new coding tools providing a significant coding gain over the high efficiency video coding (HEVC) standard. It is well known that increasing the coding efficiency adds more dependencies in the video bitstream making format-compliant encryption with the standard more challenging. In this paper we tackle the problem of selective encryption of the VVC standard in format-compliant and constant bitrate. These two constraints ensure that the encrypted bitstream can be decoded by any VVC decoder while the bitrate remains unchanged by the encryption. The selective encryption of all possible VVC syntax elements is investigated. A new algorithm is proposed to encrypt in format-compliant and constant bitrate the transform coefficients (TCs) together with other syntax elements at the level of the entropy encoder. The proposed solution was integrated and assessed under the VVC reference software model version 6.0. Experimental results showed that the encryption drastically decreases the video quality while the encryption is robust against several types of attacks. The encryption space is estimated in the range of 15% to 26% of the bitstream size resulting in a lightweight encryption process. The web page of this work is available at https://gugautie.github.io/sevvc/.
Translating the Unseen? Yoruba-English MT in Low-Resource, Morphologically-Unmarked Settings
Venue: arXiv cs.CL 2021
Year: 2021

Translating between languages where certain features are marked morphologically in one but absent or marked contextually in the other is an important test case for machine translation. When translating into English which marks (in)definiteness morphologically, from Yorùbá which uses bare nouns but marks these features contextually, ambiguities arise. In this work, we perform fine-grained analysis on how an SMT system compares with two NMT systems (BiLSTM and Transformer) when translating bare nouns in Yorùbá into English. We investigate how the systems what extent they identify BNs, correctly translate them, and compare with human translation patterns. We also analyze the type of errors each model makes and provide a linguistic description of these errors. We glean insights for evaluating model performance in low-resource settings. In translating bare nouns, our results show the transformer model outperforms the SMT and BiLSTM models for 4 categories, the BiLSTM outperforms the SMT model for 3 categories while the SMT outperforms the NMT models for 1 category.
Adaptive Coding for Matrix Multiplication at Edge Networks
Venue: arXiv cs.IT 2021
Year: 2021

Edge computing is emerging as a new paradigm to allow processing data at the edge of the network, where data is typically generated and collected, by exploiting multiple devices at the edge collectively. However, exploiting the potential of edge computing is challenging mainly due to the heterogeneous and time-varying nature of edge devices. Coded computation, which advocates mixing data in sub-tasks by employing erasure codes and offloading these sub-tasks to other devices for computation, is recently gaining interest, thanks to its higher reliability, smaller delay, and lower communication cost. In this paper, our focus is on characterizing the cost-benefit trade-offs of coded computation for practical edge computing systems, and develop an adaptive coded computation framework. In particular, we focus on matrix multiplication as a computationally intensive task, and develop an adaptive coding for matrix multiplication (ACM^2) algorithm by taking into account the heterogeneous and time varying nature of edge devices. ACM^2 dynamically selects the best coding policy by taking into account the computing time, storage requirements as well as successful decoding probability. We show that ACM^2 improves the task completion delay significantly as compared to existing coded matrix multiplication algorithms.
Uncovering the Benefits and Challenges of Continuous Integration Practices
Venue: arXiv cs.SE 2021
Year: 2021

In 2006, Fowler and Foemmel defined ten core Continuous Integration (CI) practices that could increase the speed of software development feedback cycles and improve software quality. Since then, these practices have been widely adopted by industry and subsequent research has shown they improve software quality. However, there is poor understanding of how organizations implement these practices, of the benefits developers perceive they bring, and of the challenges developers and organizations experience in implementing them. In this paper, we discuss a multiple-case study of three small- to medium-sized companies using the recommended suite of ten CI practices. Using interviews and activity log mining, we learned that these practices are broadly implemented but how they are implemented varies depending on their perceived benefits, the context of the project, and the CI tools used by the organization. We also discovered that CI practices can create new constraints on the software process that hurt feedback cycle time. For researchers, we show that how CI is implemented varies, and thus studying CI (for example, using data mining) requires understanding these differences as important context for research studies. For practitioners, our findings reveal in-depth insights on the possible benefits and challenges from using the ten practices, and how project context matters.
Developing a Data-Driven Categorical Taxonomy of Emotional Expressions in Real World Human Robot Interactions
Venue: arXiv cs.RO 2021
Year: 2021

Emotions are reactions that can be expressed through a variety of social signals. For example, anger can be expressed through a scowl, narrowed eyes, a long stare, or many other expressions. This complexity is problematic when attempting to recognize a human's expression in a human-robot interaction: categorical emotion models used in HRI typically use only a few prototypical classes, and do not cover the wide array of expressions in the wild. We propose a data-driven method towards increasing the number of known emotion classes present in human-robot interactions, to 28 classes or more. The method includes the use of automatic segmentation of video streams into short (<10s) videos, and annotation using the large set of widely-understood emojis as categories. In this work, we showcase our initial results using a large in-the-wild HRI dataset (UE-HRI), with 61 clips randomly sampled from the dataset, labeled with 28 different emojis. In particular, our results showed that the "skeptical" emoji was a common expression in our dataset, which is not often considered in typical emotion taxonomies. This is the first step in developing a rich taxonomy of emotional expressions that can be used in the future as labels for training machine learning models, towards more accurate perception of humans by robots.
MTLHealth: A Deep Learning System for Detecting Disturbing Content in Student Essays
Venue: arXiv cs.CL 2021
Year: 2021

Essay submissions to standardized tests like the ACT occasionally include references to bullying, self-harm, violence, and other forms of disturbing content. Graders must take great care to identify cases like these and decide whether to alert authorities on behalf of students who may be in danger. There is a growing need for robust computer systems to support human decision-makers by automatically flagging potential instances of disturbing content. This paper describes MTLHealth, a disturbing content detection pipeline built around recent advances from computational linguistics, particularly pre-trained language model Transformer networks.