OpenRaiser/Intern-Atlas huggingface dataset:
A Data-Centric Methodology and Task Typology for Time-Stamped Event Sequences
Venue: arXiv cs.GR 2022
Year: 2022

Task abstractions and taxonomic structures for tasks are useful for designers of interactive data analysis approaches, serving as design targets and evaluation criteria alike. For individual data types, dataset-specific taxonomic structures capture unique data characteristics, while being generalizable across application domains. The creation of dataset-centric but domain-agnostic taxonomic structures is difficult, especially if best practices for a focused data type are still missing, observing experts is not feasible, and means for reflection and generalization are scarce. We discovered this need for methodological support when working with time-stamped event sequences, a datatype that has not yet been fully systematically studied in visualization research. To address this shortcoming, we present a methodology that enables researchers to abstract tasks and build dataset-centric taxonomic structures in five phases (data collection, coding, task categorization, task synthesis, and action-target(criterion) crosscut). We validate the methodology by applying it to time-stamped event sequences and present a task typology that uses triples as a novel language of description for tasks: (1) action, (2) data target, and (3) data criterion. We further evaluate the descriptive power of the typology with a real-world case on cybersecurity.
Is More Data Better? Re-thinking the Importance of Efficiency in Abusive Language Detection with Transformers-Based Active Learning
Venue: arXiv cs.CL 2022
Year: 2022

Annotating abusive language is expensive, logistically complex and creates a risk of psychological harm. However, most machine learning research has prioritized maximizing effectiveness (i.e., F1 or accuracy score) rather than data efficiency (i.e., minimizing the amount of data that is annotated). In this paper, we use simulated experiments over two datasets at varying percentages of abuse to demonstrate that transformers-based active learning is a promising approach to substantially raise efficiency whilst still maintaining high effectiveness, especially when abusive content is a smaller percentage of the dataset. This approach requires a fraction of labeled data to reach performance equivalent to training over the full dataset.
PTSG: a test generation tool based on extended finite state machine
Venue: arXiv cs.SE 2022
Year: 2022

The Extended Finite State Machine (EFSM) is one of the most popular modeling approaches for model-based testing. However, EFSM-based test case generation is susceptible to the infeasible (inexecutable) path problem, which stems from the conflict of predicates (guards) between transitions in the path. Therefore, in order to derive feasible test cases, a test generation algorithm needs to dynamically acquire information about the model and verify the feasibility of the generated test path through the simulation execution of the model. The traditional method of constructing executable models using hard-coding for different EFSM models under test has limitations such as inflexibility, time-consuming and error-prone. To address this issue, this paper develops an open source test generation tool for testing EFSM-specified systems, PTSG, to support the automatic generation of executable test cases. It decouples the EFSM model description, parsing and simulation execution functions from the test generation algorithm, which can effectively improve the efficiency and quality of test generation. In particular, PTSG first uses a well-designed JSON syntax to describe the specific EFSM under test. Then, based on the model description file, it uses lexical and syntactic parsers to dynamically extract model information to construct various model objects in memory such as state configurations, transitions, etc. Finally, the tool provide a series of service interfaces to support model information acquisition, transition feasibility evaluation, and model simulation execution. A case study of test sequence generation for the SCP protocol model demonstrates the capability and promise of the PTSG to serve executable test cases.
Improved Approximation for Two-Edge-Connectivity
Venue: arXiv cs.DS 2022
Year: 2022

The basic goal of survivable network design is to construct low-cost networks which preserve a sufficient level of connectivity despite the failure or removal of a few nodes or edges. One of the most basic problems in this area is the $2$-Edge-Connected Spanning Subgraph problem (2-ECSS): given an undirected graph $G$, find a $2$-edge-connected spanning subgraph $H$ of $G$ with the minimum number of edges (in particular, $H$ remains connected after the removal of one arbitrary edge). 2-ECSS is NP-hard and the best-known (polynomial-time) approximation factor for this problem is $4/3$. Interestingly, this factor was achieved with drastically different techniques by [Hunkenschr{ö}der, Vempala and Vetta '00,'19] and [Seb{ö} and Vygen, '14]. In this paper we present an improved $\frac{118}{89}+ε<1.326$ approximation for 2-ECSS. The key ingredient in our approach (which might also be helpful in future work) is a reduction to a special type of structured graphs: our reduction preserves approximation factors up to $6/5$. While reducing to 2-vertex-connected graphs is trivial (and heavily used in prior work), our structured graphs are "almost" 3-vertex-connected: more precisely, given any 2-vertex-cut $\{u,v\}$ of a structured graph $G=(V,E)$, $G[V\setminus \{u,v\}]$ has exactly 2 connected components, one of which contains exactly one node of degree $2$ in $G$.
An Automatically Verified Prototype of the Android Permissions System
Venue: arXiv cs.SE 2022
Year: 2022

In a previous work De Luca and Luna presented formal specifications of idealized formulations of the permission model of Android in the Coq proof assistant. This formal development is about 23 KLOC of Coq code, including proofs. This work aims at showing that {log} (`setlog') -- a satisfiability solver and a constraint logic programming language -- can be used as an effective automated prover for the class of proofs that must be discharged in the formal verification of systems such as the one carried out by De Luca and Luna. We show how the Coq model is encoded in {log} and how automated proofs are performed. The resulting {log} model is an automatically verified executable prototype of the Android permissions system. Detailed data on the empirical evaluation resulting after executing all the proofs in {log} is provided. The integration of Coq and {log} as to provide a framework featuring automated proof and prototype generation is discussed.
Influence Maximization in Real-World Closed Social Networks
Venue: arXiv cs.SI 2022
Year: 2022

In the last few years, many closed social networks such as WhatsAPP and WeChat have emerged to cater for people's growing demand of privacy and independence. In a closed social network, the posted content is not available to all users or senders can set limits on who can see the posted content. Under such a constraint, we study the problem of influence maximization in a closed social network. It aims to recommend users (not just the seed users) a limited number of existing friends who will help propagate the information, such that the seed users' influence spread can be maximized. We first prove that this problem is NP-hard. Then, we propose a highly effective yet efficient method to augment the diffusion network, which initially consists of seed users only. The augmentation is done by iteratively and intelligently selecting and inserting a limited number of edges from the original network. Through extensive experiments on real-world social networks including deployment into a real-world application, we demonstrate the effectiveness and efficiency of our proposed method.
Tree Methods for Hierarchical Classification in Parallel
Venue: arXiv cs.LG 2022
Year: 2022

We propose methods that enable efficient hierarchical classification in parallel. Our methods transform a batch of classification scores and labels, corresponding to given nodes in a semantic tree, to scores and labels corresponding to all nodes in the ancestral paths going down the tree to every given node, relying only on tensor operations that execute efficiently on hardware accelerators. We implement our methods and test them on current hardware accelerators with a tree incorporating all English-language synsets in WordNet 3.0, spanning 117,659 classes in 20 levels of depth. We transform batches of scores and labels to their respective ancestral paths, incurring negligible computation and consuming only a fixed 0.04GB of memory over the footprint of data.
Seeking Diverse Reasoning Logic: Controlled Equation Expression Generation for Solving Math Word Problems
Venue: arXiv cs.CL 2022
Year: 2022

To solve Math Word Problems, human students leverage diverse reasoning logic that reaches different possible equation solutions. However, the mainstream sequence-to-sequence approach of automatic solvers aims to decode a fixed solution equation supervised by human annotation. In this paper, we propose a controlled equation generation solver by leveraging a set of control codes to guide the model to consider certain reasoning logic and decode the corresponding equations expressions transformed from the human reference. The empirical results suggest that our method universally improves the performance on single-unknown (Math23K) and multiple-unknown (DRAW1K, HMWP) benchmarks, with substantial improvements up to 13.2% accuracy on the challenging multiple-unknown datasets.
Schema-Based Automata Determinization
Venue: arXiv cs.FL 2022
Year: 2022

We propose an algorithm for schema-based determinization of finite automata on words and of step-wise hedge automata on nested words. The idea is to integrate schema-based cleaning directly into automata determinization. We prove the correctness of our new algorithm and show that it is alway smore efficient than standard determinization followed by schema-based cleaning. Our implementation permits to obtain a small deterministic automaton for an example of an XPath query, where standard determinization yields a huge stepwise hedge automaton for which schema-based cleaning runs out of memory.
Fast Traffic Engineering by Gradient Descent with Learned Differentiable Routing
Venue: arXiv cs.NI 2022
Year: 2022

Emerging applications such as the metaverse, telesurgery or cloud computing require increasingly complex operational demands on networks (e.g., ultra-reliable low latency). Likewise, the ever-faster traffic dynamics will demand network control mechanisms that can operate at short timescales (e.g., sub-minute). In this context, Traffic Engineering (TE) is a key component to efficiently control network traffic according to some performance goals (e.g., minimize network congestion). This paper presents Routing By Backprop (RBB), a novel TE method based on Graph Neural Networks (GNN) and differentiable programming. Thanks to its internal GNN model, RBB builds an end-to-end differentiable function of the target TE problem (MinMaxLoad). This enables fast TE optimization via gradient descent. In our evaluation, we show the potential of RBB to optimize OSPF-based routing ($\approx$25\% of improvement with respect to default OSPF configurations). Moreover, we test the potential of RBB as an initializer of computationally-intensive TE solvers. The experimental results show promising prospects for accelerating this type of solvers and achieving efficient online TE optimization.
IoU-Enhanced Attention for End-to-End Task Specific Object Detection
Venue: arXiv cs.CV 2022
Year: 2022

Without densely tiled anchor boxes or grid points in the image, sparse R-CNN achieves promising results through a set of object queries and proposal boxes updated in the cascaded training manner. However, due to the sparse nature and the one-to-one relation between the query and its attending region, it heavily depends on the self attention, which is usually inaccurate in the early training stage. Moreover, in a scene of dense objects, the object query interacts with many irrelevant ones, reducing its uniqueness and harming the performance. This paper proposes to use IoU between different boxes as a prior for the value routing in self attention. The original attention matrix multiplies the same size matrix computed from the IoU of proposal boxes, and they determine the routing scheme so that the irrelevant features can be suppressed. Furthermore, to accurately extract features for both classification and regression, we add two lightweight projection heads to provide the dynamic channel masks based on object query, and they multiply with the output from dynamic convs, making the results suitable for the two different tasks. We validate the proposed scheme on different datasets, including MS-COCO and CrowdHuman, showing that it significantly improves the performance and increases the model convergence speed.
Quantifying attention via dwell time and engagement in a social media browsing environment
Venue: arXiv cs.HC 2022
Year: 2022

Modern computational systems have an unprecedented ability to detect, leverage and influence human attention. Prior work identified user engagement and dwell time as two key metrics of attention in digital environments, but these metrics have yet to be integrated into a unified model that can advance the theory andpractice of digital attention. We draw on work from cognitive science, digital advertising, and AI to propose a two-stage model of attention for social media environments that disentangles engagement and dwell. In an online experiment, we show that attention operates differently in these two stages and find clear evidence of dissociation: when dwelling on posts (Stage 1), users attend more to sensational than credible content, but when deciding whether to engage with content (Stage 2), users attend more to credible than sensational content. These findings have implications for the design and development of computational systems that measure and model human attention, such as newsfeed algorithms on social media.
Recurrent Super-Resolution Method for Enhancing Low Quality Thermal Facial Data
Venue: arXiv cs.CV 2022
Year: 2022

The process of obtaining high-resolution images from single or multiple low-resolution images of the same scene is of great interest for real-world image and signal processing applications. This study is about exploring the potential usage of deep learning based image super-resolution algorithms on thermal data for producing high quality thermal imaging results for in-cabin vehicular driver monitoring systems. In this work we have proposed and developed a novel multi-image super-resolution recurrent neural network to enhance the resolution and improve the quality of low-resolution thermal imaging data captured from uncooled thermal cameras. The end-to-end fully convolutional neural network is trained from scratch on newly acquired thermal data of 30 different subjects in indoor environmental conditions. The effectiveness of the thermally tuned super-resolution network is validated quantitatively as well as qualitatively on test data of 6 distinct subjects. The network was able to achieve a mean peak signal to noise ratio of 39.24 on the validation dataset for 4x super-resolution, outperforming bicubic interpolation both quantitatively and qualitatively.
Seen to Unseen: When Fuzzy Inference System Predicts IoT Device Positioning Labels That Had Not Appeared in Training Phase
Venue: arXiv cs.LG 2022
Year: 2022

Situating at the core of Artificial Intelligence (AI), Machine Learning (ML), and more specifically, Deep Learning (DL) have embraced great success in the past two decades. However, unseen class label prediction is far less explored due to missing classes being invisible in training ML or DL models. In this work, we propose a fuzzy inference system to cope with such a challenge by adopting TSK+ fuzzy inference engine in conjunction with the Curvature-based Feature Selection (CFS) method. The practical feasibility of our system has been evaluated by predicting the positioning labels of networking devices within the realm of the Internet of Things (IoT). Competitive prediction performance confirms the efficiency and efficacy of our system, especially when a large number of continuous class labels are unseen during the model training stage.
The Interaction Gap: A Step Toward Understanding Trust in Autonomous Vehicles Between Encounters
Venue: arXiv cs.HC 2022
Year: 2022

Shared autonomous vehicles (SAVs) will be introduced in greater numbers over the coming decade. Due to rapid advances in shared mobility and the slower development of fully autonomous vehicles (AVs), SAVs will likely be deployed before privately-owned AVs. Moreover, existing shared mobility services are transitioning their vehicle fleets toward those with increasingly higher levels of driving automation. Consequently, people who use shared vehicles on an "as needed" basis will have infrequent interactions with automated driving, thereby experiencing interaction gaps. Using human trust data of 25 participants, we show that interaction gaps can affect human trust in automated driving. Participants engaged in a simulator study consisting of two interactions separated by a one-week interaction gap. A moderate, inverse correlation was found between the change in trust during the initial interaction and the interaction gap, suggesting people "forget" some of their gained trust or distrust in automation during an interaction gap.
Explaining Anomalies using Denoising Autoencoders for Financial Tabular Data
Venue: arXiv cs.LG 2022
Year: 2022

Recent advances in Explainable AI (XAI) increased the demand for deployment of safe and interpretable AI models in various industry sectors. Despite the latest success of deep neural networks in a variety of domains, understanding the decision-making process of such complex models still remains a challenging task for domain experts. Especially in the financial domain, merely pointing to an anomaly composed of often hundreds of mixed type columns, has limited value for experts. Hence, in this paper, we propose a framework for explaining anomalies using denoising autoencoders designed for mixed type tabular data. We specifically focus our technique on anomalies that are erroneous observations. This is achieved by localizing individual sample columns (cells) with potential errors and assigning corresponding confidence scores. In addition, the model provides the expected cell value estimates to fix the errors. We evaluate our approach based on three standard public tabular datasets (Credit Default, Adult, IEEE Fraud) and one proprietary dataset (Holdings). We find that denoising autoencoders applied to this task already outperform other approaches in the cell error detection rates as well as in the expected value rates. Additionally, we analyze how a specialized loss designed for cell error detection can further improve these metrics. Our framework is designed for a domain expert to understand abnormal characteristics of an anomaly, as well as to improve in-house data quality management processes.
Contrastive Learning for Time Series on Dynamic Graphs
Venue: arXiv cs.LG 2022
Year: 2022

There have been several recent efforts towards developing representations for multivariate time-series in an unsupervised learning framework. Such representations can prove beneficial in tasks such as activity recognition, health monitoring, and anomaly detection. In this paper, we consider a setting where we observe time-series at each node in a dynamic graph. We propose a framework called GraphTNC for unsupervised learning of joint representations of the graph and the time-series. Our approach employs a contrastive learning strategy. Based on an assumption that the time-series and graph evolution dynamics are piecewise smooth, we identify local windows of time where the signals exhibit approximate stationarity. We then train an encoding that allows the distribution of signals within a neighborhood to be distinguished from the distribution of non-neighboring signals. We first demonstrate the performance of our proposed framework using synthetic data, and subsequently we show that it can prove beneficial for the classification task with real-world datasets.
Changing the Scene: applying four models of social evolution to the scenescape
Venue: arXiv cs.SI 2022
Year: 2022

This paper elaborates a multi-model approach to studying how local scenes change. We refer to this as the "4 D's" of scene change: development, differentiation, defense, and diffusion. Each posits somewhat distinct change processes, and has its own tradition of theory and empirical research, which we briefly review. After summarizing some major trends in scenes and amenities in the US context, for each change model, we present some initial findings, discussing data and methods throughout. Our overall goal is to point toward new research arcs on change models of scenes, and to give some clear examples and directions for how to think about and collect data to understand what makes some scenes change, others not, why, and in what directions.
Nesting Forward Automatic Differentiation for Memory-Efficient Deep Neural Network Training
Venue: arXiv cs.LG 2022
Year: 2022

An activation function is an element-wise mathematical function and plays a crucial role in deep neural networks (DNN). Many novel and sophisticated activation functions have been proposed to improve the DNN accuracy but also consume massive memory in the training process with back-propagation. In this study, we propose the nested forward automatic differentiation (Forward-AD), specifically for the element-wise activation function for memory-efficient DNN training. We deploy nested Forward-AD in two widely-used deep learning frameworks, TensorFlow and PyTorch, which support the static and dynamic computation graph, respectively. Our evaluation shows that nested Forward-AD reduces the memory footprint by up to 1.97x than the baseline model and outperforms the recomputation by 20% under the same memory reduction ratio.
Learning Model Predictive Controllers with Real-Time Attention for Real-World Navigation
Venue: arXiv cs.RO 2022
Year: 2022

Despite decades of research, existing navigation systems still face real-world challenges when deployed in the wild, e.g., in cluttered home environments or in human-occupied public spaces. To address this, we present a new class of implicit control policies combining the benefits of imitation learning with the robust handling of system constraints from Model Predictive Control (MPC). Our approach, called Performer-MPC, uses a learned cost function parameterized by vision context embeddings provided by Performers -- a low-rank implicit-attention Transformer. We jointly train the cost function and construct the controller relying on it, effectively solving end-to-end the corresponding bi-level optimization problem. We show that the resulting policy improves standard MPC performance by leveraging a few expert demonstrations of the desired navigation behavior in different challenging real-world scenarios. Compared with a standard MPC policy, Performer-MPC achieves >40% better goal reached in cluttered environments and >65% better on social metrics when navigating around humans.