OpenRaiser/Intern-Atlas huggingface dataset:
Fast and Scalable Channels in Kotlin Coroutines
Venue: arXiv cs.DS 2022
Year: 2022

Asynchronous programming has gained significant popularity over the last decade: support for this programming pattern is available in many popular languages via libraries and native language implementations, typically in the form of coroutines or the async/await construct. Instead of programming via shared memory, this concept assumes implicit synchronization through message passing. The key data structure enabling such communication is the rendezvous channel. Roughly, a rendezvous channel is a blocking queue of size zero, so both send(e) and receive() operations wait for each other, performing a rendezvous when they meet. To optimize the message passing pattern, channels are usually equipped with a fixed-size buffer, so send(e)-s do not suspend and put elements into the buffer until its capacity is exceeded. This primitive is known as a buffered channel. This paper presents a fast and scalable algorithm for both rendezvous and buffered channels. Similarly to modern queues, our solution is based on an infinite array with two positional counters for send(e) and receive() operations, leveraging the unconditional Fetch-And-Add instruction to update them. Yet, the algorithm requires non-trivial modifications of this classic pattern, in order to support the full channel semantics, such as buffering and cancellation of waiting requests. We compare the performance of our solution to that of the Kotlin implementation, as well as against other academic proposals, showing up to 9.8x speedup. To showcase its expressiveness and performance, we also integrated the proposed algorithm into the standard Kotlin Coroutines library, replacing the previous channel implementations.
Creative Writing with an AI-Powered Writing Assistant: Perspectives from Professional Writers
Venue: arXiv cs.HC 2022
Year: 2022

Recent developments in natural language generation (NLG) using neural language models have brought us closer than ever to the goal of building AI-powered creative writing tools. However, most prior work on human-AI collaboration in the creative writing domain has evaluated new systems with amateur writers, typically in contrived user studies of limited scope. In this work, we commissioned 13 professional, published writers from a diverse set of creative writing backgrounds to craft stories using Wordcraft, a text editor with built-in AI-powered writing assistance tools. Using interviews and participant journals, we discuss the potential of NLG to have significant impact in the creative writing domain--especially with respect to brainstorming, generation of story details, world-building, and research assistance. Experienced writers, more so than amateurs, typically have well-developed systems and methodologies for writing, as well as distinctive voices and target audiences. Our work highlights the challenges in building for these writers; NLG technologies struggle to preserve style and authorial voice, and they lack deep understanding of story contents. In order for AI-powered writing assistants to realize their full potential, it is essential that they take into account the diverse goals and expertise of human writers.
Message passing methods on complex networks
Venue: arXiv cs.SI 2022
Year: 2022

Networks and network computations have become a primary mathematical tool for analyzing the structure of many kinds of complex systems, ranging from the Internet and transportation networks to biochemical interactions and social networks. A common task in network analysis is the calculation of quantities that reside on the nodes of a network, such as centrality measures, probabilities, or model states. In this review article we discuss message passing methods, a family of techniques for performing such calculations, based on the propagation of information between the nodes of a network. We introduce the message passing approach with a series of examples, give some illustrative applications and results, and discuss the deep connections between message passing and phase transitions in networks. We also point out some limitations of the message passing approach and describe some recently-introduced methods that address these limitations.
Basis for a vector space generated by Hamiltonian time paths in a complete time graph
Venue: arXiv cs.CC 2022
Year: 2022

In this paper we introduce the notion of a complete time graph of order n. We define time paths and Hamiltonian time paths in a complete time graph. Each Hamiltonian time path (htp) is associated with some permutation p of the integers 1 to n. The characteristic function of this path forms a vector in the vector space of rational-valued functions on the set of edges of the compete time graph. We will consider the vector space generated by these functions. The main result in this paper is to determine the dimension of this vector space for n greater than or equal to 5. We also give an algorithm with its complexity for the construction of a basis in this vector space.
Mapping Out the HPC Dependency Chaos
Venue: arXiv cs.SE 2022
Year: 2022

High Performance Computing~(HPC) software stacks have become complex, with the dependencies of some applications numbering in the hundreds. Packaging, distributing, and administering software stacks of that scale is a complex undertaking anywhere. HPC systems deal with esoteric compilers, hardware, and a panoply of uncommon combinations. In this paper, we explore the mechanisms available for packaging software to find its own dependencies in the context of a taxonomy of software distribution, and discuss their benefits and pitfalls. We discuss workarounds for some common problems caused by using these composed stacks and introduce Shrinkwrap: A solution to producing binaries that directly load their dependencies from precise locations and in a precise order. Beyond simplifying the use of the binaries, this approach also speeds up loading as much as 7x for a large dynamically-linked MPI application in our evaluation.
Deep Learning based Computer Vision Methods for Complex Traffic Environments Perception: A Review
Venue: arXiv cs.CV 2022
Year: 2022

Computer vision applications in intelligent transportation systems (ITS) and autonomous driving (AD) have gravitated towards deep neural network architectures in recent years. While performance seems to be improving on benchmark datasets, many real-world challenges are yet to be adequately considered in research. This paper conducted an extensive literature review on the applications of computer vision in ITS and AD, and discusses challenges related to data, models, and complex urban environments. The data challenges are associated with the collection and labeling of training data and its relevance to real world conditions, bias inherent in datasets, the high volume of data needed to be processed, and privacy concerns. Deep learning (DL) models are commonly too complex for real-time processing on embedded hardware, lack explainability and generalizability, and are hard to test in real-world settings. Complex urban traffic environments have irregular lighting and occlusions, and surveillance cameras can be mounted at a variety of angles, gather dirt, shake in the wind, while the traffic conditions are highly heterogeneous, with violation of rules and complex interactions in crowded scenarios. Some representative applications that suffer from these problems are traffic flow estimation, congestion detection, autonomous driving perception, vehicle interaction, and edge computing for practical deployment. The possible ways of dealing with the challenges are also explored while prioritizing practical deployment.
Up to 58 Tets/Hex to untangle Hex meshes
Venue: arXiv cs.GR 2022
Year: 2022

The request for high-quality solutions continually grows in a world where more and more tasks are executed through computers. This also counts for fields such as engineering, computer graphics, etc., which use meshes to solve their problems. A mesh is a combination of some elementary elements, for which hexahedral elements are a good choice thanks to their superior numerical features. The solutions reached using these meshes depend on the quality of the elements making up the mesh. The problem is that these individual elements can take on a shape which prevents accurate computations. Such elements are considered to be invalid. To allow users to get accurate results, the shape of these elements must therefore be changed to be considered valid. In this work, we combine the results of two papers to scan a mesh, identify possible invalid elements and then change the shape of these elements to make them valid. With this combination, we end up with a working algorithm. But there is room for improvement, which is why we introduce multiple improvements to speed up the algorithm as well as make it more robust. We then test our algorithm and compare it to another approach. This work, therefore, introduces a new efficient and robust approach to untangle invalid meshes.
Are All Edges Necessary? A Unified Framework for Graph Purification
Venue: arXiv cs.SI 2022
Year: 2022

Graph Neural Networks (GNNs) as deep learning models working on graph-structure data have achieved advanced performance in many works. However, it has been proved repeatedly that, not all edges in a graph are necessary for the training of machine learning models. In other words, some of the connections between nodes may bring redundant or even misleading information to downstream tasks. In this paper, we try to provide a method to drop edges in order to purify the graph data from a new perspective. Specifically, it is a framework to purify graphs with the least loss of information, under which the core problems are how to better evaluate the edges and how to delete the relatively redundant edges with the least loss of information. To address the above two problems, we propose several measurements for the evaluation and different judges and filters for the edge deletion. We also introduce a residual-iteration strategy and a surrogate model for measurements requiring unknown information. The experimental results show that our proposed measurements for KL divergence with constraints to maintain the connectivity of the graph and delete edges in an iterative way can find out the most edges while keeping the performance of GNNs. What's more, further experiments show that this method also achieves the best defense performance against adversarial attacks.
Training a Vision Transformer from scratch in less than 24 hours with 1 GPU
Venue: arXiv cs.CV 2022
Year: 2022

Transformers have become central to recent advances in computer vision. However, training a vision Transformer (ViT) model from scratch can be resource intensive and time consuming. In this paper, we aim to explore approaches to reduce the training costs of ViT models. We introduce some algorithmic improvements to enable training a ViT model from scratch with limited hardware (1 GPU) and time (24 hours) resources. First, we propose an efficient approach to add locality to the ViT architecture. Second, we develop a new image size curriculum learning strategy, which allows to reduce the number of patches extracted from each image at the beginning of the training. Finally, we propose a new variant of the popular ImageNet1k benchmark by adding hardware and time constraints. We evaluate our contributions on this benchmark, and show they can significantly improve performances given the proposed training budget. We will share the code in https://github.com/BorealisAI/efficient-vit-training.
Content-Diverse Comparisons improve IQA
Venue: arXiv cs.CV 2022
Year: 2022

Image quality assessment (IQA) forms a natural and often straightforward undertaking for humans, yet effective automation of the task remains highly challenging. Recent metrics from the deep learning community commonly compare image pairs during training to improve upon traditional metrics such as PSNR or SSIM. However, current comparisons ignore the fact that image content affects quality assessment as comparisons only occur between images of similar content. This restricts the diversity and number of image pairs that the model is exposed to during training. In this paper, we strive to enrich these comparisons with content diversity. Firstly, we relax comparison constraints, and compare pairs of images with differing content. This increases the variety of available comparisons. Secondly, we introduce listwise comparisons to provide a holistic view to the model. By including differentiable regularizers, derived from correlation coefficients, models can better adjust predicted scores relative to one another. Evaluation on multiple benchmarks, covering a wide range of distortions and image content, shows the effectiveness of our learning scheme for training image quality assessment models.
Automatic Creativity Measurement in Scratch Programs Across Modalities
Venue: arXiv cs.HC 2022
Year: 2022

Promoting creativity is considered an important goal of education, but creativity is notoriously hard to measure.In this paper, we make the journey fromdefining a formal measure of creativity that is efficientlycomputable to applying the measure in a practical domain. The measure is general and relies on coretheoretical concepts in creativity theory, namely fluency, flexibility, and originality, integratingwith prior cognitive science literature. We adapted the general measure for projects in the popular visual programming language Scratch.We designed a machine learning model for predicting the creativity of Scratch projects, trained and evaluated on human expert creativity assessments in an extensive user study. Our results show that opinions about creativity in Scratch varied widely across experts. The automatic creativity assessment aligned with the assessment of the human experts more than the experts agreed with each other. This is a first step in providing computational models for measuring creativity that can be applied to educational technologies, and to scale up the benefit of creativity education in schools.
BERT-Based Combination of Convolutional and Recurrent Neural Network for Indonesian Sentiment Analysis
Venue: arXiv cs.CL 2022
Year: 2022

Sentiment analysis is the computational study of opinions and emotions ex-pressed in text. Deep learning is a model that is currently producing state-of-the-art in various application domains, including sentiment analysis. Many researchers are using a hybrid approach that combines different deep learning models and has been shown to improve model performance. In sentiment analysis, input in text data is first converted into a numerical representation. The standard method used to obtain a text representation is the fine-tuned embedding method. However, this method does not pay attention to each word's context in the sentence. Therefore, the Bidirectional Encoder Representation from Transformer (BERT) model is used to obtain text representations based on the context and position of words in sentences. This research extends the previous hybrid deep learning using BERT representation for Indonesian sentiment analysis. Our simulation shows that the BERT representation improves the accuracies of all hybrid architectures. The BERT-based LSTM-CNN also reaches slightly better accuracies than other BERT-based hybrid architectures.
Combating Health Misinformation in Social Media: Characterization, Detection, Intervention, and Open Issues
Venue: arXiv cs.SI 2022
Year: 2022

Social media has been one of the main information consumption sources for the public, allowing people to seek and spread information more quickly and easily. However, the rise of various social media platforms also enables the proliferation of online misinformation. In particular, misinformation in the health domain has significant impacts on our society such as the COVID-19 infodemic. Therefore, health misinformation in social media has become an emerging research direction that attracts increasing attention from researchers of different disciplines. Compared to misinformation in other domains, the key differences of health misinformation include the potential of causing actual harm to humans' bodies and even lives, the hardness to identify for normal people, and the deep connection with medical science. In addition, health misinformation on social media has distinct characteristics from conventional channels such as television on multiple dimensions including the generation, dissemination, and consumption paradigms. Because of the uniqueness and importance of combating health misinformation in social media, we conduct this survey to further facilitate interdisciplinary research on this problem. In this survey, we present a comprehensive review of existing research about online health misinformation in different disciplines. Furthermore, we also systematically organize the related literature from three perspectives: characterization, detection, and intervention. Lastly, we conduct a deep discussion on the pressing open issues of combating health misinformation in social media and provide future directions for multidisciplinary researchers.
Prior-enhanced Temporal Action Localization using Subject-aware Spatial Attention
Venue: arXiv cs.CV 2022
Year: 2022

Temporal action localization (TAL) aims to detect the boundary and identify the class of each action instance in a long untrimmed video. Current approaches treat video frames homogeneously, and tend to give background and key objects excessive attention. This limits their sensitivity to localize action boundaries. To this end, we propose a prior-enhanced temporal action localization method (PETAL), which only takes in RGB input and incorporates action subjects as priors. This proposal leverages action subjects' information with a plug-and-play subject-aware spatial attention module (SA-SAM) to generate an aggregated and subject-prioritized representation. Experimental results on THUMOS-14 and ActivityNet-1.3 datasets demonstrate that the proposed PETAL achieves competitive performance using only RGB features, e.g., boosting mAP by 2.41% or 0.25% over the state-of-the-art approach that uses RGB features or with additional optical flow features on the THUMOS-14 dataset.
Set based velocity shaping for robotic manipulators
Venue: arXiv cs.RO 2022
Year: 2022

We develop a new framework for trajectory planning on predefined paths, for general N-link manipulators. Different from previous approaches generating open-loop minimum time controllers or pre-tuned motion profiles by time-scaling, we establish analytic algorithms that recover all initial conditions that can be driven to the desirable target set while adhering to environment constraints. More technologically relevant, we characterise families of corresponding safe state-feedback controllers with several desirable properties. A key enabler in our framework is the introduction of a state feedback template, that induces ordering properties between trajectories of the resulting closed-loop system. The proposed structure allows working on the nonlinear system directly in both the analysis and synthesis problems. Both offline computations and online implementation are scalable with respect to the number of links of the manipulator. The results can potentially be used in a series of challenging problems: Numerical experiments on a commercial robotic manipulator demonstrate that efficient online implementation is possible.
Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs
Venue: arXiv cs.CG 2022
Year: 2022

We consider problems related to finding short cycles, small cliques, small independent sets, and small subgraphs in geometric intersection graphs. We obtain a plethora of new results. For example: * For the intersection graph of $n$ line segments in the plane, we give algorithms to find a 3-cycle in $O(n^{1.408})$ time, a size-3 independent set in $O(n^{1.652})$ time, a 4-clique in near-$O(n^{24/13})$ time, and a $k$-clique (or any $k$-vertex induced subgraph) in $O(n^{0.565k+O(1)})$ time for any constant $k$; we can also compute the girth in near-$O(n^{3/2})$ time. * For the intersection graph of $n$ axis-aligned boxes in a constant dimension $d$, we give algorithms to find a 3-cycle in $O(n^{1.408})$ time for any $d$, a 4-clique (or any 4-vertex induced subgraph) in $O(n^{1.715})$ time for any $d$, a size-4 independent set in near-$O(n^{3/2})$ time for any $d$, a size-5 independent set in near-$O(n^{4/3})$ time for $d=2$, and a $k$-clique (or any $k$-vertex induced subgraph) in $O(n^{0.429k+O(1)})$ time for any $d$ and any constant $k$. * For the intersection graph of $n$ fat objects in any constant dimension $d$, we give an algorithm to find any $k$-vertex (non-induced) subgraph in $O(n\log n)$ time for any constant $k$, generalizing a result by Kaplan, Klost, Mulzer, Roddity, Seiferth, and Sharir (1999) for 3-cycles in 2D disk graphs. A variety of techniques is used, including geometric range searching, biclique covers, "high-low" tricks, graph degeneracy and separators, and shifted quadtrees. We also prove a near-$Ω(n^{4/3})$ conditional lower bound for finding a size-4 independent set for boxes.
Decomposing the Fundamentals of Creepy Stories
Venue: arXiv cs.CY 2022
Year: 2022

Fear is a universal concept; people crave it in urban legends, scary movies, and modern stories. Open questions remain, however, about why these stories are scary and more generally what scares people. In this study, we explore these questions by analyzing tens of thousands of scary stories on forums (known as subreddits) in a social media website, Reddit. We first explore how writing styles have evolved to keep these stories fresh before we analyze the stable core techniques writers use to make stories scary. We find that writers have changed the themes of their stories over years from haunted houses to school-related themes, body horror, and diseases. Yet some features remain stable; words associated with pseudo-human nouns, such as clown or devil are more common in scary stories than baselines. In addition, we collect a range of datasets that annotate sentences containing fear. We use these data to develop a high-accuracy fear detection neural network model, which is used to quantify where people express fear in scary stories. We find that sentences describing fear, and words most often seen in scary stories, spike at particular points in a story, possibly as a way to keep the readers on the edge of their seats until the story's conclusion. These results provide a new understanding of how authors cater to their readers, and how fear may manifest in stories.
On the Privacy Risks of Algorithmic Recourse
Venue: arXiv cs.LG 2022
Year: 2022

As predictive models are increasingly being employed to make consequential decisions, there is a growing emphasis on developing techniques that can provide algorithmic recourse to affected individuals. While such recourses can be immensely beneficial to affected individuals, potential adversaries could also exploit these recourses to compromise privacy. In this work, we make the first attempt at investigating if and how an adversary can leverage recourses to infer private information about the underlying model's training data. To this end, we propose a series of novel membership inference attacks which leverage algorithmic recourse. More specifically, we extend the prior literature on membership inference attacks to the recourse setting by leveraging the distances between data instances and their corresponding counterfactuals output by state-of-the-art recourse methods. Extensive experimentation with real world and synthetic datasets demonstrates significant privacy leakage through recourses. Our work establishes unintended privacy leakage as an important risk in the widespread adoption of recourse methods.