OpenRaiser/Intern-Atlas huggingface dataset:
Fast and Practical DAG Decomposition with Reachability Applications
Venue: arXiv cs.DS 2022
Year: 2022

We present practical linear and almost linear-time algorithms to compute a chain decomposition of a directed acyclic graph (DAG), $G=(V,E)$. The number of vertex-disjoint chains computed is very close to the minimum. The time complexity of our algorithm is $O(|E|+c*l)$, where $c$ is the number of path concatenations and $l$ is the length of a longest path of the graph. We give a comprehensive explanation on factors $c$ and $l$ in the following sections. Our techniques have important applications in many areas, including the design of faster practical transitive closure algorithms. We observe that $|E_{red}|\leq width*|V|$ ($E_{red}$: non-transitive edges) and show how to find a substantially large subset of $E_{tr}$ (transitive edges) using a chain decomposition in linear time, without calculating the transitive closure. Our extensive experimental results show the interplay between the width, $E_{red}$, $E_{tr}$ in various models of graphs. We show how to compute a reachability indexing scheme in $O(k_c*|E_{red}|)$ time, where $k_c$ is the number of chains and $|E_{red}|$ is the number of non-transitive edges. This scheme can answer reachabilitiy queries in constant time. The space complexity of the scheme is $O(k_c*|V|)$. The experimental results reveal that our methods are even better in practice than the theoretical bounds imply, indicating how fast chain decomposition algorithms can be applied to the transitive closure problem.
Too Slow to Be Useful? On Incorporating Humans in the Loop of Smart Speakers
Venue: arXiv cs.HC 2022
Year: 2022

Real-time crowd-powered systems, such as Chorus/Evorus, VizWiz, and Apparition, have shown how incorporating humans into automated systems could supplement where the automatic solutions fall short. However, one unspoken bottleneck of applying such architectures to more scenarios is the longer latency of including humans in the loop of automated systems. For the applications that have hard constraints in turnaround times, human-operated components' longer latency and large speed variation seem to be apparent deal breakers. This paper explicates and quantifies these limitations by using a human-powered text-based backend to hold conversations with users through a voice-only smart speaker. Smart speakers must respond to users' requests within seconds, so the workers behind the scenes only have a few seconds to compose answers. We measured the end-to-end system latency and the conversation quality with eight pairs of participants, showing the challenges and superiority of such systems.
State Grammars with Stores
Venue: arXiv cs.FL 2022
Year: 2022

State grammars are context-free grammars where the productions have states associated with them, and a production can only be applied to a nonterminal if the current state matches the state in the production. Once states are added to grammars, it is natural to add various stores, similar to machine models. With such extensions, productions can only be applied if both the state and the value read from each store matches between the current sentential form and the production. Here, generative capacity results are presented for different derivation modes, with and without additional stores. In particular, with the standard derivation relation, it is shown that adding reversal-bounded counters does not increase the capacity, and states are enough. Also, state grammars with reversal-bounded counters that operate using leftmost derivations are shown to coincide with languages accepted by one-way machines with a pushdown and reversal-bounded counters, and these are surprisingly shown to be strictly weaker than state grammars with the standard derivation relation (and no counters). The complexity of the emptiness problem involving state grammars with reversal-bounded counters is also studied.
A study of the design and documentation skills of industry-ready CS students
Venue: arXiv cs.SE 2022
Year: 2022

An engineer in a product company is expected to design a good solution to a computing problem (Design skill) and articulate the solution well (Expression skill). We expect an industry-ready student (final year student or a fresh campus hire) as well to demonstrate both these skills when working on simple problems assigned to them. This paper reports on the results when we tested a cohort of participants (N=16) for these two skills. We created two participant groups from two different tiers of college, one from a Tier 1 college (who were taking an advanced elective course), and another from Tier 2 colleges (who had been hired for internship in a SaaS product company). We gave them a simple design problem and evaluated the quality of their design and expression. Design quality was evaluated along three design principles of Abstraction, Decomposition, and Precision (adapted from the Software Engineering Book of Knowledge). Expression quality was evaluated using criteria we developed for our study that is based on the diversity and density of the expressions used in the articulation. We found the students lacking in design and expression skills. Specifically, a) they struggled with abstraction as a design principle, b) they did not use enough modes of expressions to articulate their design, and c) they did not use enough formal notations (UML, equations, relations, etc.). We also found significant difference in the performance between the two participant groups.
A Comprehensive Survey on Multi-hop Machine Reading Comprehension Datasets and Metrics
Venue: arXiv cs.CL 2022
Year: 2022

Multi-hop Machine reading comprehension is a challenging task with aim of answering a question based on disjoint pieces of information across the different passages. The evaluation metrics and datasets are a vital part of multi-hop MRC because it is not possible to train and evaluate models without them, also, the proposed challenges by datasets often are an important motivation for improving the existing models. Due to increasing attention to this field, it is necessary and worth reviewing them in detail. This study aims to present a comprehensive survey on recent advances in multi-hop MRC evaluation metrics and datasets. In this regard, first, the multi-hop MRC problem definition will be presented, then the evaluation metrics based on their multi-hop aspect will be investigated. Also, 15 multi-hop datasets have been reviewed in detail from 2017 to 2022, and a comprehensive analysis has been prepared at the end. Finally, open issues in this field have been discussed.
Age of Information with On-Off Service
Venue: arXiv cs.IT 2022
Year: 2022

This paper considers a communication system where a source sends time-sensitive information to its destination. We assume that both arrival and service processes of the messages are memoryless and the source has a single server with no buffer. Besides, we consider that the service is interrupted by an independent random process, which we model using the On-Off process. For this setup, we study the age of information for two queueing disciplines: 1) non-preemptive, where the messages arriving while the server is occupied are discarded, and 2) preemptive, where the in-service messages are replaced with newly arriving messages in the Off states. For these disciplines, we derive closed-form expressions for the mean peak age and mean age.
Optimization-Based Predictive Congestion Control for the Tor Network: Opportunities and Challenges
Venue: arXiv cs.NI 2022
Year: 2022

Based on the principle of onion routing, the Tor network achieves anonymity for its users by relaying user data over a series of intermediate relays. This approach makes congestion control in the network a challenging task. As of today, this results in higher latencies due to considerable backlog as well as unfair data rate allocation. In this paper, we present a concept study of PredicTor, a novel approach to congestion control that tackles clogged overlay networks. Unlike traditional approaches, it is built upon the idea of distributed model predictive control, a recent advancement from the area of control theory. PredicTor is tailored to minimizing latency in the network and achieving max-min fairness. We contribute a thorough evaluation of its behavior in both toy scenarios to assess the optimizer and complex networks to assess its potential. For this, we conduct large-scale simulation studies and compare PredicTor to existing congestion control mechanisms in Tor. We show that PredicTor is highly effective in reducing latency and realizing fair rate allocations. In addition, we strive to bring the ideas of modern control theory to the networking community, enabling the development of improved, future congestion control. We therefore demonstrate benefits and issues alike with this novel research direction.
ChromaCorrect: Prescription Correction in Virtual Reality Headsets through Perceptual Guidance
Venue: arXiv cs.HC 2022
Year: 2022

A large portion of today's world population suffer from vision impairments and wear prescription eyeglasses. However, eyeglasses causes additional bulk and discomfort when used with augmented and virtual reality headsets, thereby negatively impacting the viewer's visual experience. In this work, we remedy the usage of prescription eyeglasses in Virtual Reality (VR) headsets by shifting the optical complexity completely into software and propose a prescription-aware rendering approach for providing sharper and immersive VR imagery. To this end, we develop a differentiable display and visual perception model encapsulating display-specific parameters, color and visual acuity of human visual system and the user-specific refractive errors. Using this differentiable visual perception model, we optimize the rendered imagery in the display using stochastic gradient-descent solvers. This way, we provide prescription glasses-free sharper images for a person with vision impairments. We evaluate our approach on various displays, including desktops and VR headsets, and show significant quality and contrast improvements for users with vision impairments.
Approximations in Deep Learning
Venue: arXiv cs.AR 2022
Year: 2022

The design and implementation of Deep Learning (DL) models is currently receiving a lot of attention from both industrials and academics. However, the computational workload associated with DL is often out of reach for low-power embedded devices and is still costly when run on datacenters. By relaxing the need for fully precise operations, Approximate Computing (AxC) substantially improves performance and energy efficiency. DL is extremely relevant in this context, since playing with the accuracy needed to do adequate computations will significantly enhance performance, while keeping the quality of results in a user-constrained range. This chapter will explore how AxC can improve the performance and energy efficiency of hardware accelerators in DL applications during inference and training.
Bio-Inspired, Task-Free Continual Learning through Activity Regularization
Venue: arXiv cs.NE 2022
Year: 2022

The ability to sequentially learn multiple tasks without forgetting is a key skill of biological brains, whereas it represents a major challenge to the field of deep learning. To avoid catastrophic forgetting, various continual learning (CL) approaches have been devised. However, these usually require discrete task boundaries. This requirement seems biologically implausible and often limits the application of CL methods in the real world where tasks are not always well defined. Here, we take inspiration from neuroscience, where sparse, non-overlapping neuronal representations have been suggested to prevent catastrophic forgetting. As in the brain, we argue that these sparse representations should be chosen on the basis of feed forward (stimulus-specific) as well as top-down (context-specific) information. To implement such selective sparsity, we use a bio-plausible form of hierarchical credit assignment known as Deep Feedback Control (DFC) and combine it with a winner-take-all sparsity mechanism. In addition to sparsity, we introduce lateral recurrent connections within each layer to further protect previously learned representations. We evaluate the new sparse-recurrent version of DFC on the split-MNIST computer vision benchmark and show that only the combination of sparsity and intra-layer recurrent connections improves CL performance with respect to standard backpropagation. Our method achieves similar performance to well-known CL methods, such as Elastic Weight Consolidation and Synaptic Intelligence, without requiring information about task boundaries. Overall, we showcase the idea of adopting computational principles from the brain to derive new, task-free learning algorithms for CL.
Maintainability and evolvability of control software in machine and plant manufacturing -- An industrial survey
Venue: arXiv cs.SE 2022
Year: 2022

Automated Production Systems (aPS) have lifetimes of up to 30-50 years, throughout which the desired products change ever more frequently. This requires flexible, reusable control software that can be easily maintained and evolved. To evaluate selected criteria that are especially relevant for maturity in software maintainability and evolvability of aPS, the approach SWMAT4aPS+ builds on a questionnaire with 52 questions. The three main research questions cover updates of software modules and success factors for both cross-disciplinary development as well as reusable models. This paper presents the evaluation results of 68 companies from machine and plant manufacturing (MPM). Companies providing automation devices and/or engineering tools will be able to identify challenges their customers in MPM face. Validity is ensured through feedback of the participating companies and an analysis of the statistical unambiguousness of the results. From a software or systems engineering point of view, almost all criteria are fulfilled below expectations.
Improved Deep Neural Network Generalization Using m-Sharpness-Aware Minimization
Venue: arXiv cs.LG 2022
Year: 2022

Modern deep learning models are over-parameterized, where the optimization setup strongly affects the generalization performance. A key element of reliable optimization for these systems is the modification of the loss function. Sharpness-Aware Minimization (SAM) modifies the underlying loss function to guide descent methods towards flatter minima, which arguably have better generalization abilities. In this paper, we focus on a variant of SAM known as mSAM, which, during training, averages the updates generated by adversarial perturbations across several disjoint shards of a mini-batch. Recent work suggests that mSAM can outperform SAM in terms of test accuracy. However, a comprehensive empirical study of mSAM is missing from the literature -- previous results have mostly been limited to specific architectures and datasets. To that end, this paper presents a thorough empirical evaluation of mSAM on various tasks and datasets. We provide a flexible implementation of mSAM and compare the generalization performance of mSAM to the performance of SAM and vanilla training on different image classification and natural language processing tasks. We also conduct careful experiments to understand the computational cost of training with mSAM, its sensitivity to hyperparameters and its correlation with the flatness of the loss landscape. Our analysis reveals that mSAM yields superior generalization performance and flatter minima, compared to SAM, across a wide range of tasks without significantly increasing computational costs.
A Fine-grained Chinese Software Privacy Policy Dataset for Sequence Labeling and Regulation Compliant Identification
Venue: arXiv cs.CR 2022
Year: 2022

Privacy protection raises great attention on both legal levels and user awareness. To protect user privacy, countries enact laws and regulations requiring software privacy policies to regulate their behavior. However, privacy policies are written in natural languages with many legal terms and software jargon that prevent users from understanding and even reading them. It is desirable to use NLP techniques to analyze privacy policies for helping users understand them. Furthermore, existing datasets ignore law requirements and are limited to English. In this paper, we construct the first Chinese privacy policy dataset, namely CA4P-483, to facilitate the sequence labeling tasks and regulation compliance identification between privacy policies and software. Our dataset includes 483 Chinese Android application privacy policies, over 11K sentences, and 52K fine-grained annotations. We evaluate families of robust and representative baseline models on our dataset. Based on baseline performance, we provide findings and potential research directions on our dataset. Finally, we investigate the potential applications of CA4P-483 combing regulation requirements and program analysis.
A Rubric for Human-like Agents and NeuroAI
Venue: arXiv cs.AI 2022
Year: 2022

Researchers across cognitive, neuro-, and computer sciences increasingly reference human-like artificial intelligence and neuroAI. However, the scope and use of the terms are often inconsistent. Contributed research ranges widely from mimicking behaviour, to testing machine learning methods as neurally plausible hypotheses at the cellular or functional levels, or solving engineering problems. However, it cannot be assumed nor expected that progress on one of these three goals will automatically translate to progress in others. Here a simple rubric is proposed to clarify the scope of individual contributions, grounded in their commitments to human-like behaviour, neural plausibility, or benchmark/engineering goals. This is clarified using examples of weak and strong neuroAI and human-like agents, and discussing the generative, corroborate, and corrective ways in which the three dimensions interact with one another. The author maintains that future progress in artificial intelligence will need strong interactions across the disciplines, with iterative feedback loops and meticulous validity tests, leading to both known and yet-unknown advances that may span decades to come.
Objective Surgical Skills Assessment and Tool Localization: Results from the MICCAI 2021 SimSurgSkill Challenge
Venue: arXiv cs.CV 2022
Year: 2022

Timely and effective feedback within surgical training plays a critical role in developing the skills required to perform safe and efficient surgery. Feedback from expert surgeons, while especially valuable in this regard, is challenging to acquire due to their typically busy schedules, and may be subject to biases. Formal assessment procedures like OSATS and GEARS attempt to provide objective measures of skill, but remain time-consuming. With advances in machine learning there is an opportunity for fast and objective automated feedback on technical skills. The SimSurgSkill 2021 challenge (hosted as a sub-challenge of EndoVis at MICCAI 2021) aimed to promote and foster work in this endeavor. Using virtual reality (VR) surgical tasks, competitors were tasked with localizing instruments and predicting surgical skill. Here we summarize the winning approaches and how they performed. Using this publicly available dataset and results as a springboard, future work may enable more efficient training of surgeons with advances in surgical data science. The dataset can be accessed from https://console.cloud.google.com/storage/browser/isi-simsurgskill-2021.
Diffusion Guided Domain Adaptation of Image Generators
Venue: arXiv cs.CV 2022
Year: 2022

Can a text-to-image diffusion model be used as a training objective for adapting a GAN generator to another domain? In this paper, we show that the classifier-free guidance can be leveraged as a critic and enable generators to distill knowledge from large-scale text-to-image diffusion models. Generators can be efficiently shifted into new domains indicated by text prompts without access to groundtruth samples from target domains. We demonstrate the effectiveness and controllability of our method through extensive experiments. Although not trained to minimize CLIP loss, our model achieves equally high CLIP scores and significantly lower FID than prior work on short prompts, and outperforms the baseline qualitatively and quantitatively on long and complicated prompts. To our best knowledge, the proposed method is the first attempt at incorporating large-scale pre-trained diffusion models and distillation sampling for text-driven image generator domain adaptation and gives a quality previously beyond possible. Moreover, we extend our work to 3D-aware style-based generators and DreamBooth guidance.
babble: Learning Better Abstractions with E-Graphs and Anti-Unification
Venue: arXiv cs.PL 2022
Year: 2022

Library learning compresses a given corpus of programs by extracting common structure from the corpus into reusable library functions. Prior work on library learning suffers from two limitations that prevent it from scaling to larger, more complex inputs. First, it explores too many candidate library functions that are not useful for compression. Second, it is not robust to syntactic variation in the input. We propose library learning modulo theory (LLMT), a new library learning algorithm that additionally takes as input an equational theory for a given problem domain. LLMT uses e-graphs and equality saturation to compactly represent the space of programs equivalent modulo the theory, and uses a novel e-graph anti-unification technique to find common patterns in the corpus more directly and efficiently. We implemented LLMT in a tool named BABBLE. Our evaluation shows that BABBLE achieves better compression orders of magnitude faster than the state of the art. We also provide a qualitative evaluation showing that BABBLE learns reusable functions on inputs previously out of reach for library learning.
CBE Clima Tool: a free and open-source web application for climate analysis tailored to sustainable building design
Venue: arXiv cs.HC 2022
Year: 2022

Buildings that are designed specifically to respond to the local climate can be more comfortable, energy-efficient, and with a lower environmental impact. However, there are many social, cultural, and economic obstacles that might prevent the wide adoption of designing climate-adapted buildings. One of the said obstacles can be removed by enabling practitioners to easily access and analyse local climate data. The CBE Clima Tool (Clima) is a free and open-source web application that offers easy access to publicly available weather files (in EPW format) specifically created for building energy simulation and design. It provides a series of interactive visualization of the variables therein contained and several derived ones. It is aimed at students, educators, and practitioners in the architecture and engineering fields. Since its launch has been consistently recording over 3000 monthly unique users from over 70 countries worldwide, both in professional and educational settings.