OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Codes Detecting Deletions in Concatenated Binary Strings Applied to Trace Reconstruction
Venue: arXiv cs.IT 2023
Year: 2023

Consider two or more strings $\mathbf{x}^1,\mathbf{x}^2,\ldots,$ that are concatenated to form $\mathbf{x}=\langle \mathbf{x}^1,\mathbf{x}^2,\ldots \rangle$. Suppose that up to $δ$ deletions occur in each of the concatenated strings. Since deletions alter the lengths of the strings, a fundamental question to ask is: how much redundancy do we need to introduce in $\mathbf{x}$ in order to recover the boundaries of $\mathbf{x}^1,\mathbf{x}^2,\ldots$? This boundary problem is equivalent to the problem of designing codes that can detect the exact number of deletions in each concatenated string. In this work, we answer the question above by first deriving converse results that give lower bounds on the redundancy of deletion-detecting codes. Then, we present a marker-based code construction whose redundancy is asymptotically optimal in $δ$ among all families of deletion-detecting codes, and exactly optimal among all block-by-block decodable codes. To exemplify the usefulness of such deletion-detecting codes, we apply our code to trace reconstruction and design an efficient coded reconstruction scheme that requires a constant number of traces.
Coloring Fast with Broadcasts
Venue: arXiv cs.DC 2023
Year: 2023

We present an $O(\log^3\log n)$-round distributed algorithm for the $(Δ+1)$-coloring problem, where each node broadcasts only one $O(\log n)$-bit message per round to its neighbors. Previously, the best such broadcast-based algorithm required $O(\log n)$ rounds. If $Δ\in Ω(\log^{3} n)$, our algorithm runs in $O(\log^* n)$ rounds. Our algorithm's round complexity matches state-of-the-art in the much more powerful CONGEST model [Halldórsson et al., STOC'21 & PODC'22], where each node sends one different message to each of its neighbors, thus sending up to $Θ(n\log n)$ bits per round. This is the best complexity known, even if message sizes are unbounded. Our algorithm is simple enough to be implemented in even weaker models: we can achieve the same $O(\log^3\log n)$ round complexity if each node reads its received messages in a streaming fashion, using only $O(\log^3 n)$-bit memory. Therefore, we hope that our algorithm opens the road for adopting the recent exciting progress on sublogarithmic-time distributed $(Δ+1)$-coloring algorithms in a wider range of (theoretical or practical) settings.
GeoGraphViz: Geographically Constrained 3D Force-Directed Graph for Knowledge Graph Visualization
Venue: arXiv cs.HC 2023
Year: 2023

Knowledge graphs are a key technique for linking and integrating cross-domain data, concepts, tools, and knowledge to enable data-driven analytics. As much of the worlds data have become massive in size, visualizing graph entities and their interrelationships intuitively and interactively has become a crucial task for ingesting and better utilizing graph content to support semantic reasoning, discovering hidden knowledge discovering, and better scientific understanding of geophysical and social phenomena. Despite the fact that many such phenomena (e.g., disasters) have clear spatial footprints and geographical properties, their location information is considered only as a textual label in existing graph visualization tools, limiting their capability to reveal the geospatial distribution patterns of the graph nodes. In addition, most graph visualization techniques rely on 2D graph visualization, which constraints the dimensions of information that can be presented and lacks support for graph structure examination from multiple angles. To tackle the above challenges, we developed a novel 3D map-based graph visualization algorithm to enable interactive exploration of graph content and patterns in a spatially explicit manner. The algorithm extends a 3D force directed graph by integrating a web map, an additional geolocational force, and a force balancing variable that allows for the dynamic adjustment of the 3D graph structure and layout. This mechanism helps create a balanced graph view between the semantic forces among the graph nodes and the attractive force from a geolocation to a graph node. Our solution offers a new perspective in visualizing and understanding spatial entities and events in a knowledge graph.
Accelerate Support Vector Clustering via Spectrum-Preserving Data Compression
Venue: arXiv cs.LG 2023
Year: 2023

This paper proposes a novel framework for accelerating support vector clustering. The proposed method first computes much smaller compressed data sets while preserving the key cluster properties of the original data sets based on a novel spectral data compression approach. Then, the resultant spectrally-compressed data sets are leveraged for the development of fast and high quality algorithm for support vector clustering. We conducted extensive experiments using real-world data sets and obtained very promising results. The proposed method allows us to achieve 100X and 115X speedups over the state of the art SVC method on the Pendigits and USPS data sets, respectively, while achieving even better clustering quality. To the best of our knowledge, this represents the first practical method for high-quality and fast SVC on large-scale real-world data sets
A Latent Space Theory for Emergent Abilities in Large Language Models
Venue: arXiv cs.CL 2023
Year: 2023

Languages are not created randomly but rather to communicate information. There is a strong association between languages and their underlying meanings, resulting in a sparse joint distribution that is heavily peaked according to their correlations. Moreover, these peak values happen to match with the marginal distribution of languages due to the sparsity. With the advent of LLMs trained on big data and large models, we can now precisely assess the marginal distribution of languages, providing a convenient means of exploring the sparse structures in the joint distribution for effective inferences. In this paper, we categorize languages as either unambiguous or ε-ambiguous and present quantitative results to demonstrate that the emergent abilities of LLMs, such as language understanding, in-context learning, chain-of-thought prompting, and effective instruction fine-tuning, can all be attributed to Bayesian inference on the sparse joint distribution of languages.
Vulnerability of Finitely-long Blockchains in Securing Data
Venue: arXiv cs.CR 2023
Year: 2023

Recently, blockchain has been applied in various fields to secure data exchanges and storage in decentralized systems. In a blockchain application where the task of the application which makes use of the data stored in a blockchain has to be accomplished by a time instant, the employed blockchain is essentially finitely-long. In this paper, we consider a general finitely-long blockchain model which is generalized from most existing works on finitely-long blockchain applications, and take the first step towards characterizing the vulnerability of finitely-long blockchains in securing data against double-spending attacks. For the first time, we develop a general closed-form expression for the probability of success in launching a double-spending attack on a finitely-long blockchain. This probability essentially characterizes the vulnerability of finitely-long blockchains. Then, we prove that the probability of success in launching a double-spending attack on a finitely-long blockchain is no greater than that on an infinitely-long blockchain, which implies that finitely-long blockchains are less vulnerable to double-spending attacks than infinitely-long blockchains. Moreover, we show that unlike infinitely-long blockchains which can be surely paralyzed by a 51% attack, finitely-long blockchains are more resistant to 51% attacks.
Availability Model of a 5G-MEC System
Venue: arXiv cs.NI 2023
Year: 2023

Multi-access Edge Computing (MEC) is one of the enabling technologies of the fifth generation (5G) of mobile networks. MEC enables services with strict latency requirements by bringing computing capabilities close to the users. As with any new technology, the dependability of MEC is one of the aspects that need to be carefully studied. In this paper, we propose a two-level model to compute the availability of a 5G-MEC system. We then use the model to evaluate the availability of a 5G-MEC system under various configurations. The results show that having a single redundancy of the 5G-MEC elements leads an acceptable availability. To reach a high availability, the software failure intensity of the management elements of 5G and MEC should be reduced.
Performance of A Reconfigurable Intelligent Surface Controlled by An Illegitimate User
Venue: arXiv cs.IT 2023
Year: 2023

In this paper, we investigate how an illegitimate user can use a reconfigurable intelligent surface (RIS) to maximally degrade the secrecy performance of the legitimate system. We first consider the case when the illegitimate user performs eavesdropping only. A problem is formulated to minimize the system secrecy rate by optimizing the phase shifts of the RIS elements. We also consider the case when the illegitimate user works with full-duplex technology and can perform eavesdropping and jamming simultaneously through the RIS. A problem is formulated to minimize the system secrecy rate by optimizing the jamming power and the phase shifts of the RIS elements. Although the two formulated problems are nonconvex, they are optimally solved in this paper. Our results show that good eavesdropping performance can be achieved by placing the RIS at an appropriate position. Further, jamming plus eavesdropping can largely reduce the secrecy rate of the legitimate system.
Power Law Trends in Speedrunning and Machine Learning
Venue: arXiv cs.LG 2023
Year: 2023

We find that improvements in speedrunning world records follow a power law pattern. Using this observation, we answer an outstanding question from previous work: How do we improve on the baseline of predicting no improvement when forecasting speedrunning world records out to some time horizon, such as one month? Using a random effects model, we improve on this baseline for relative mean square error made on predicting out-of-sample world record improvements as the comparison metric at a $p < 10^{-5}$ significance level. The same set-up improves \textit{even} on the ex-post best exponential moving average forecasts at a $p = 0.15$ significance level while having access to substantially fewer data points. We demonstrate the effectiveness of this approach by applying it to Machine Learning benchmarks and achieving forecasts that exceed a baseline. Finally, we interpret the resulting model to suggest that 1) ML benchmarks are far from saturation and 2) sudden large improvements in Machine Learning are unlikely but cannot be ruled out.
Finding Bug-Inducing Program Environments
Venue: arXiv cs.SE 2023
Year: 2023

Some bugs cannot be exposed by program inputs, but only by certain program environments. During execution, most programs access various resources, like databases, files, or devices, that are external to the program and thus part of the program's environment. In this paper, we present a coverage-guided, mutation-based environment synthesis approach of bug-inducing program environments. Specifically, we observe that programs interact with their environment via dedicated system calls and propose to intercept these system calls (i) to capture the resources accessed during the first execution of an input as initial program environment, and (ii) mutate copies of these resources during subsequent executions of that input to generate slightly changed program environments. Any generated environment that is observed to increase coverage is added to the corpus of environment seeds and becomes subject to further fuzzing. Bug-inducing program environments are reported to the user. Experiments demonstrate the effectiveness of our approach. We implemented a prototype called AFLChaos which found bugs in the resource-handling code of five (5) of the seven (7) open source projects in our benchmark set (incl. OpenSSL). Automatically, AFLChaos generated environments consisting of bug-inducing databases used for storing information, bug-inducing multimedia files used for streaming, bug-inducing cryptographic keys used for encryption, and bug-inducing configuration files used to configure the program. To support open science, we publish the experimental infrastructure, our tool, and all data.
Fruit Picker Activity Recognition with Wearable Sensors and Machine Learning
Venue: arXiv cs.LG 2023
Year: 2023

In this paper we present a novel application of detecting fruit picker activities based on time series data generated from wearable sensors. During harvesting, fruit pickers pick fruit into wearable bags and empty these bags into harvesting bins located in the orchard. Once full, these bins are quickly transported to a cooled pack house to improve the shelf life of picked fruits. For farmers and managers, the knowledge of when a picker bag is emptied is important for managing harvesting bins more effectively to minimise the time the picked fruit is left out in the heat (resulting in reduced shelf life). We propose a means to detect these bag-emptying events using human activity recognition with wearable sensors and machine learning methods. We develop a semi-supervised approach to labelling the data. A feature-based machine learning ensemble model and a deep recurrent convolutional neural network are developed and tested on a real-world dataset. When compared, the neural network achieves 86% detection accuracy.
Heteromated Decision-Making: Integrating Socially Assistive Robots in Care Relationships
Venue: arXiv cs.HC 2023
Year: 2023

Technological development continues to advance, with consequences for the use of robots in health care. For this reason, this workshop contribution aims at consideration of how socially assistive robots can be integrated into care and what tasks they can take on. This also touches on the degree of autonomy of these robots and the balance of decision support and decision making in different situations. We want to show that decision making by robots is mediated by the balance between autonomy and safety. Our results are based on Design Fiction and Zine-Making workshops we conducted with scientific experts. Ultimately, we show that robots' actions take place in social groups. A robot does not typically decide alone, but its decision-making is embedded in group processes. The concept of heteromation, which describes the interconnection of human and machine actions, offers fruitful possibilities for exploring how robots can be integrated into caring relationships.
On the Independence of Association Bias and Empirical Fairness in Language Models
Venue: arXiv cs.CL 2023
Year: 2023

The societal impact of pre-trained language models has prompted researchers to probe them for strong associations between protected attributes and value-loaded terms, from slur to prestigious job titles. Such work is said to probe models for bias or fairness-or such probes 'into representational biases' are said to be 'motivated by fairness'-suggesting an intimate connection between bias and fairness. We provide conceptual clarity by distinguishing between association biases (Caliskan et al., 2022) and empirical fairness (Shen et al., 2022) and show the two can be independent. Our main contribution, however, is showing why this should not come as a surprise. To this end, we first provide a thought experiment, showing how association bias and empirical fairness can be completely orthogonal. Next, we provide empirical evidence that there is no correlation between bias metrics and fairness metrics across the most widely used language models. Finally, we survey the sociological and psychological literature and show how this literature provides ample support for expecting these metrics to be uncorrelated.
Motion Artifacts Detection in Short-scan Dental CBCT Reconstructions
Venue: arXiv cs.CV 2023
Year: 2023

Cone Beam Computed Tomography (CBCT) is widely used in dentistry for diagnostics and treatment planning. CBCT Imaging has a long acquisition time and consequently, the patient is likely to move. This motion causes significant artifacts in the reconstructed data which may lead to misdiagnosis. Existing motion correction algorithms only address this issue partially, struggling with inconsistencies due to truncation, accuracy, and execution speed. On the other hand, a short-scan reconstruction using a subset of motion-free projections with appropriate weighting methods can have a sufficient clinical image quality for most diagnostic purposes. Therefore, a framework is used in this study to extract the motion-free part of the scanned projections with which a clean short-scan volume can be reconstructed without using correction algorithms. Motion artifacts are detected using deep learning with a slice-based prediction scheme followed by volume averaging to get the final result. A realistic motion simulation strategy and data augmentation has been implemented to address data scarcity. The framework has been validated by testing it with real motion-affected data while the model was trained only with simulated motion data. This shows the feasibility to apply the proposed framework to a broad variety of motion cases for further research.
Efficient Uncertainty Estimation in Spiking Neural Networks via MC-dropout
Venue: arXiv cs.NE 2023
Year: 2023

Spiking neural networks (SNNs) have gained attention as models of sparse and event-driven communication of biological neurons, and as such have shown increasing promise for energy-efficient applications in neuromorphic hardware. As with classical artificial neural networks (ANNs), predictive uncertainties are important for decision making in high-stakes applications, such as autonomous vehicles, medical diagnosis, and high frequency trading. Yet, discussion of uncertainty estimation in SNNs is limited, and approaches for uncertainty estimation in artificial neural networks (ANNs) are not directly applicable to SNNs. Here, we propose an efficient Monte Carlo(MC)-dropout based approach for uncertainty estimation in SNNs. Our approach exploits the time-step mechanism of SNNs to enable MC-dropout in a computationally efficient manner, without introducing significant overheads during training and inference while demonstrating high accuracy and uncertainty quality.
CoT-MoTE: Exploring ConTextual Masked Auto-Encoder Pre-training with Mixture-of-Textual-Experts for Passage Retrieval
Venue: arXiv cs.CL 2023
Year: 2023

Passage retrieval aims to retrieve relevant passages from large collections of the open-domain corpus. Contextual Masked Auto-Encoding has been proven effective in representation bottleneck pre-training of a monolithic dual-encoder for passage retrieval. Siamese or fully separated dual-encoders are often adopted as basic retrieval architecture in the pre-training and fine-tuning stages for encoding queries and passages into their latent embedding spaces. However, simply sharing or separating the parameters of the dual-encoder results in an imbalanced discrimination of the embedding spaces. In this work, we propose to pre-train Contextual Masked Auto-Encoder with Mixture-of-Textual-Experts (CoT-MoTE). Specifically, we incorporate textual-specific experts for individually encoding the distinct properties of queries and passages. Meanwhile, a shared self-attention layer is still kept for unified attention modeling. Results on large-scale passage retrieval benchmarks show steady improvement in retrieval performances. The quantitive analysis also shows a more balanced discrimination of the latent embedding spaces.
Multi-view Vision-Prompt Fusion Network: Can 2D Pre-trained Model Boost 3D Point Cloud Data-scarce Learning?
Venue: arXiv cs.CV 2023
Year: 2023

Point cloud based 3D deep model has wide applications in many applications such as autonomous driving, house robot, and so on. Inspired by the recent prompt learning in natural language processing, this work proposes a novel Multi-view Vision-Prompt Fusion Network (MvNet) for few-shot 3D point cloud classification. MvNet investigates the possibility of leveraging the off-the-shelf 2D pre-trained models to achieve the few-shot classification, which can alleviate the over-dependence issue of the existing baseline models towards the large-scale annotated 3D point cloud data. Specifically, MvNet first encodes a 3D point cloud into multi-view image features for a number of different views. Then, a novel multi-view prompt fusion module is developed to effectively fuse information from different views to bridge the gap between 3D point cloud data and 2D pre-trained models. A set of 2D image prompts can then be derived to better describe the suitable prior knowledge for a large-scale pre-trained image model for few-shot 3D point cloud classification. Extensive experiments on ModelNet, ScanObjectNN, and ShapeNet datasets demonstrate that MvNet achieves new state-of-the-art performance for 3D few-shot point cloud image classification. The source code of this work will be available soon.
Image-text Retrieval via Preserving Main Semantics of Vision
Venue: arXiv cs.CV 2023
Year: 2023

Image-text retrieval is one of the major tasks of cross-modal retrieval. Several approaches for this task map images and texts into a common space to create correspondences between the two modalities. However, due to the content (semantics) richness of an image, redundant secondary information in an image may cause false matches. To address this issue, this paper presents a semantic optimization approach, implemented as a Visual Semantic Loss (VSL), to assist the model in focusing on an image's main content. This approach is inspired by how people typically annotate the content of an image by describing its main content. Thus, we leverage the annotated texts corresponding to an image to assist the model in capturing the main content of the image, reducing the negative impact of secondary content. Extensive experiments on two benchmark datasets (MSCOCO and Flickr30K) demonstrate the superior performance of our method. The code is available at: https://github.com/ZhangXu0963/VSL.
OOD-CV-v2: An extended Benchmark for Robustness to Out-of-Distribution Shifts of Individual Nuisances in Natural Images
Venue: arXiv cs.CV 2023
Year: 2023

Enhancing the robustness of vision algorithms in real-world scenarios is challenging. One reason is that existing robustness benchmarks are limited, as they either rely on synthetic data or ignore the effects of individual nuisance factors. We introduce OOD-CV-v2, a benchmark dataset that includes out-of-distribution examples of 10 object categories in terms of pose, shape, texture, context and the weather conditions, and enables benchmarking of models for image classification, object detection, and 3D pose estimation. In addition to this novel dataset, we contribute extensive experiments using popular baseline methods, which reveal that: 1) Some nuisance factors have a much stronger negative effect on the performance compared to others, also depending on the vision task. 2) Current approaches to enhance robustness have only marginal effects, and can even reduce robustness. 3) We do not observe significant differences between convolutional and transformer architectures. We believe our dataset provides a rich test bed to study robustness and will help push forward research in this area. Our dataset can be accessed from https://bzhao.me/OOD-CV/