OpenRaiser/Intern-Atlas huggingface dataset:
A Logic of "Black Box" Classifier Systems
Venue: arXiv cs.LO 2024
Year: 2024

Binary classifiers are traditionally studied by propositional logic (PL). PL can only represent them as white boxes, under the assumption that the underlying Boolean function is fully known. Binary classifiers used in practical applications and trained by machine learning are however opaque. They are usually described as black boxes. In this paper, we provide a product modal logic called PLC (Product modal Logic for binary input Classifier) in which the notion of "black box" is interpreted as the uncertainty over a set of classifiers. We give results about axiomatics and complexity of satisfiability checking for our logic. Moreover, we present a dynamic extension in which the process of acquiring new information about the actual classifier can be represented.
Mutual Information Regularized Offline Reinforcement Learning
Venue: arXiv cs.LG 2024
Year: 2024

The major challenge of offline RL is the distribution shift that appears when out-of-distribution actions are queried, which makes the policy improvement direction biased by extrapolation errors. Most existing methods address this problem by penalizing the policy or value for deviating from the behavior policy during policy improvement or evaluation. In this work, we propose a novel MISA framework to approach offline RL from the perspective of Mutual Information between States and Actions in the dataset by directly constraining the policy improvement direction. MISA constructs lower bounds of mutual information parameterized by the policy and Q-values. We show that optimizing this lower bound is equivalent to maximizing the likelihood of a one-step improved policy on the offline dataset. Hence, we constrain the policy improvement direction to lie in the data manifold. The resulting algorithm simultaneously augments the policy evaluation and improvement by adding mutual information regularizations. MISA is a general framework that unifies conservative Q-learning (CQL) and behavior regularization methods (e.g., TD3+BC) as special cases. We introduce 3 different variants of MISA, and empirically demonstrate that tighter mutual information lower bound gives better offline RL performance. In addition, our extensive experiments show MISA significantly outperforms a wide range of baselines on various tasks of the D4RL benchmark,e.g., achieving 742.9 total points on gym-locomotion tasks. Our code is available at https://github.com/sail-sg/MISA.
Liquid Welfare Guarantees for No-Regret Learning in Sequential Budgeted Auctions
Venue: arXiv cs.GT 2024
Year: 2024

We study the liquid welfare in sequential first-price auctions with budget-limited buyers. We focus on first-price auctions, which are increasingly commonly used in many settings, and consider liquid welfare, a natural and well-studied generalization of social welfare for buyers with budgets. We use a behavioral model for the buyers, assuming a learning style guarantee: the resulting utility of each buyer is within a $γ$ factor (where $γ\ge 1$) of the utility achievable by shading her value with the same factor at each round. Under this assumption, we show a $γ+1/2+O(1/γ)$ price of anarchy for liquid welfare assuming buyers have additive valuations. This positive result is in contrast to sequential second-price auctions, where even with $γ=1$, the resulting liquid welfare can be arbitrarily smaller than the maximum liquid welfare. We prove a lower bound of $γ$ on the liquid welfare loss under the above assumption in first-price auctions, making our bound asymptotically tight. For the case when $γ= 1$ our theorem implies a price of anarchy upper bound that is about $2.41$; we show a lower bound of $2$ for that case. We also give a learning algorithm that the players can use to achieve the guarantee needed for our liquid welfare result. Our algorithm achieves utility within a $γ=O(1)$ factor of the optimal utility even when a buyer's values and the bids of the other buyers are chosen adversarially, assuming the buyer's budget grows linearly with time. The competitiveness guarantee of the learning algorithm deteriorates somewhat as the budget grows slower than linearly with time. Finally, we extend our liquid welfare results for the case where buyers have submodular valuations over the set of items they win across iterations with a slightly worse price of anarchy bound of $γ+1+O(1/γ)$ compared to the guarantee for the additive case.
Superpixel perception graph neural network for intelligent defect detection of aero-engine blade
Venue: arXiv cs.CV 2024
Year: 2024

Aero-engine is the core component of aircraft and other spacecraft. The high-speed rotating blades provide power by sucking in air and fully combusting, and various defects will inevitably occur, threatening the operation safety of aero-engine. Therefore, regular inspections are essential for such a complex system. However, existing traditional technology which is borescope inspection is labor-intensive, time-consuming, and experience-dependent. To endow this technology with intelligence, a novel superpixel perception graph neural network (SPGNN) is proposed by utilizing a multi-stage graph convolutional network (MSGCN) for feature extraction and superpixel perception region proposal network (SPRPN) for region proposal. First, to capture complex and irregular textures, the images are transformed into a series of patches, to obtain their graph representations. Then, MSGCN composed of several GCN blocks extracts graph structure features and performs graph information processing at graph level. Last but not least, the SPRPN is proposed to generate perceptual bounding boxes by fusing graph representation features and superpixel perception features. Therefore, the proposed SPGNN always implements feature extraction and information transmission at the graph level in the whole SPGNN pipeline, to alleviate the reduction of receptive field and information loss. To verify the effectiveness of SPGNN, we construct a simulated blade dataset with 3000 images. A public aluminum dataset is also used to validate the performances of different methods. The experimental results demonstrate that the proposed SPGNN has superior performance compared with the state-of-the-art methods.
Faster Space-Efficient STR-IC-LCS Computation
Venue: arXiv cs.DS 2024
Year: 2024

One of the most fundamental method for comparing two given strings $A$ and $B$ is the longest common subsequence (LCS), where the task is to find (the length) of an LCS of $A$ and $B$. In this paper, we deal with the STR-IC-LCS problem which is one of the constrained LCS problems proposed by Chen and Chao [J. Comb. Optim, 2011]. A string $Z$ is said to be an STR-IC-LCS of three given strings $A$, $B$, and $P$, if $Z$ is a longest string satisfying that (1) $Z$ includes $P$ as a substring and (2) $Z$ is a common subsequence of $A$ and $B$. We present three efficient algorithms for this problem: First, we begin with a space-efficient solution which computes the length of an STR-IC-LCS in $O(n^2)$ time and $O((\ell+1)(n-\ell+1))$ space, where $\ell$ is the length of an LCS of $A$ and $B$ of length $n$. When $\ell = O(1)$ or $n-\ell = O(1)$, then this algorithm uses only linear $O(n)$ space. Second, we present a faster algorithm that works in $O(nr/\log{r}+n(n-\ell+1))$ time, where $r$ is the length of $P$, while retaining the $O((\ell+1)(n-\ell+1))$ space efficiency. Third, we give an alternative algorithm that runs in $O(nr/\log{r}+n(n-\ell'+1))$ time with $O((\ell'+1)(n-\ell'+1))$ space, where $\ell'$ denotes the STR-IC-LCS length for input strings $A$, $B$, and $P$.
An Improved Multi-State Constraint Kalman Filter for Visual-Inertial Odometry
Venue: arXiv cs.RO 2024
Year: 2024

Fast pose estimation (PE) is of vital importance for successful mission performance of agile autonomous robots. Global Positioning Systems such as GPS and GNSS have been typically used in fusion with Inertial Navigation Systems (INS) for PE. However, the low update rate and lack of proper signals make their utility impractical for indoor and urban applications. On the other hand, Visual-Inertial Odometry (VIO) is gaining popularity as a practical alternative for GNSS/INS systems in GPS-denied environments. Among the many VIO-based methods, the Multi-State Constraint Kalman Filter (MSCKF) has received a greater attention due to its robustness, speed and accuracy. To this end, the high computational cost associated with image processing for real-time implementation of MSCKF on resource-constrained vehicles is still a challenging ongoing research. In this paper, an enhanced version of the MSCKF is proposed. To this aim, different feature marginalization and state pruning strategies are suggested that result in a much faster algorithm. The proposed algorithm is tested both on an open-source dataset and in real-world experiments for validation. It is demonstrated that the proposed Fast-MSCKF (FMSCKF) is about six times faster and at least 20% more accurate in final position estimation than the standard MSCKF algorithm.
OST: Efficient One-stream Network for 3D Single Object Tracking in Point Clouds
Venue: arXiv cs.CV 2024
Year: 2024

Although recent Siamese network-based trackers have achieved impressive perceptual accuracy for single object tracking in LiDAR point clouds, they usually utilized heavy correlation operations to capture category-level characteristics only, and overlook the inherent merit of arbitrariness in contrast to multiple object tracking. In this work, we propose a radically novel one-stream network with the strength of the instance-level encoding, which avoids the correlation operations occurring in previous Siamese network, thus considerably reducing the computational effort. In particular, the proposed method mainly consists of a Template-aware Transformer Module (TTM) and a Multi-scale Feature Aggregation (MFA) module capable of fusing spatial and semantic information. The TTM stitches the specified template and the search region together and leverages an attention mechanism to establish the information flow, breaking the previous pattern of independent \textit{extraction-and-correlation}. As a result, this module makes it possible to directly generate template-aware features that are suitable for the arbitrary and continuously changing nature of the target, enabling the model to deal with unseen categories. In addition, the MFA is proposed to make spatial and semantic information complementary to each other, which is characterized by reverse directional feature propagation that aggregates information from shallow to deep layers. Extensive experiments on KITTI and nuScenes demonstrate that our method has achieved considerable performance not only for class-specific tracking but also for class-agnostic tracking with less computation and higher efficiency.
Accelerating Transfer Learning with Near-Data Computation on Cloud Object Stores
Venue: arXiv cs.LG 2024
Year: 2024

Storage disaggregation underlies today's cloud and is naturally complemented by pushing down some computation to storage, thus mitigating the potential network bottleneck between the storage and compute tiers. We show how ML training benefits from storage pushdowns by focusing on transfer learning (TL), the widespread technique that democratizes ML by reusing existing knowledge on related tasks. We propose HAPI, a new TL processing system centered around two complementary techniques that address challenges introduced by disaggregation. First, applications must carefully balance execution across tiers for performance. HAPI judiciously splits the TL computation during the feature extraction phase yielding pushdowns that not only improve network time but also improve total TL training time by overlapping the execution of consecutive training iterations across tiers. Second, operators want resource efficiency from the storage-side computational resources. HAPI employs storage-side batch size adaptation allowing increased storage-side pushdown concurrency without affecting training accuracy. HAPI yields up to 2.5x training speed-up while choosing in 86.8% of cases the best performing split point or one that is at most 5% off from the best.
Evaluation of Pedestrian Safety in a High-Fidelity Simulation Environment Framework
Venue: arXiv cs.AI 2024
Year: 2024

Pedestrians' safety is a crucial factor in assessing autonomous driving scenarios. However, pedestrian safety evaluation is rarely considered by existing autonomous driving simulation platforms. This paper proposes a pedestrian safety evaluation method for autonomous driving, in which not only the collision events but also the conflict events together with the characteristics of pedestrians are fully considered. Moreover, to apply the pedestrian safety evaluation system, we construct a high-fidelity simulation framework embedded with pedestrian safety-critical characteristics. We demonstrate our simulation framework and pedestrian safety evaluation with a comparative experiment with two kinds of autonomous driving perception algorithms -- single-vehicle perception and vehicle-to-infrastructure (V2I) cooperative perception. The results show that our framework can evaluate different autonomous driving algorithms with detailed and quantitative pedestrian safety indexes. To this end, the proposed simulation method and framework can be used to access different autonomous driving algorithms and evaluate pedestrians' safety performance in future autonomous driving simulations, which can inspire more pedestrian-friendly autonomous driving algorithms.
DPIS: An Enhanced Mechanism for Differentially Private SGD with Importance Sampling
Venue: arXiv cs.CR 2024
Year: 2024

Nowadays, differential privacy (DP) has become a well-accepted standard for privacy protection, and deep neural networks (DNN) have been immensely successful in machine learning. The combination of these two techniques, i.e., deep learning with differential privacy, promises the privacy-preserving release of high-utility models trained with sensitive data such as medical records. A classic mechanism for this purpose is DP-SGD, which is a differentially private version of the stochastic gradient descent (SGD) optimizer commonly used for DNN training. Subsequent approaches have improved various aspects of the model training process, including noise decay schedule, model architecture, feature engineering, and hyperparameter tuning. However, the core mechanism for enforcing DP in the SGD optimizer remains unchanged ever since the original DP-SGD algorithm, which has increasingly become a fundamental barrier limiting the performance of DP-compliant machine learning solutions. Motivated by this, we propose DPIS, a novel mechanism for differentially private SGD training that can be used as a drop-in replacement of the core optimizer of DP-SGD, with consistent and significant accuracy gains over the latter. The main idea is to employ importance sampling (IS) in each SGD iteration for mini-batch selection, which reduces both sampling variance and the amount of random noise injected to the gradients that is required to satisfy DP. Integrating IS into the complex mathematical machinery of DP-SGD is highly non-trivial. DPIS addresses the challenge through novel mechanism designs, fine-grained privacy analysis, efficiency enhancements, and an adaptive gradient clipping optimization. Extensive experiments on four benchmark datasets, namely MNIST, FMNIST, CIFAR-10 and IMDb, demonstrate the superior effectiveness of DPIS over existing solutions for deep learning with differential privacy.
Finite-time analysis of single-timescale actor-critic
Venue: arXiv cs.LG 2024
Year: 2024

Actor-critic methods have achieved significant success in many challenging applications. However, its finite-time convergence is still poorly understood in the most practical single-timescale form. Existing works on analyzing single-timescale actor-critic have been limited to i.i.d. sampling or tabular setting for simplicity. We investigate the more practical online single-timescale actor-critic algorithm on continuous state space, where the critic assumes linear function approximation and updates with a single Markovian sample per actor step. Previous analysis has been unable to establish the convergence for such a challenging scenario. We demonstrate that the online single-timescale actor-critic method provably finds an $ε$-approximate stationary point with $\widetilde{\mathcal{O}}(ε^{-2})$ sample complexity under standard assumptions, which can be further improved to $\mathcal{O}(ε^{-2})$ under the i.i.d. sampling. Our novel framework systematically evaluates and controls the error propagation between the actor and critic. It offers a promising approach for analyzing other single-timescale reinforcement learning algorithms as well.
Log-linear Guardedness and its Implications
Venue: arXiv cs.LG 2024
Year: 2024

Methods for erasing human-interpretable concepts from neural representations that assume linearity have been found to be tractable and useful. However, the impact of this removal on the behavior of downstream classifiers trained on the modified representations is not fully understood. In this work, we formally define the notion of log-linear guardedness as the inability of an adversary to predict the concept directly from the representation, and study its implications. We show that, in the binary case, under certain assumptions, a downstream log-linear model cannot recover the erased concept. However, we demonstrate that a multiclass log-linear model \emph{can} be constructed that indirectly recovers the concept in some cases, pointing to the inherent limitations of log-linear guardedness as a downstream bias mitigation technique. These findings shed light on the theoretical limitations of linear erasure methods and highlight the need for further research on the connections between intrinsic and extrinsic bias in neural models.
Black Box Model Explanations and the Human Interpretability Expectations -- An Analysis in the Context of Homicide Prediction
Venue: arXiv cs.LG 2024
Year: 2024

Strategies based on Explainable Artificial Intelligence (XAI) have promoted better human interpretability of the results of black box models. This opens up the possibility of questioning whether explanations created by XAI methods meet human expectations. The XAI methods being currently used (Ciu, Dalex, Eli5, Lofo, Shap, and Skater) provide various forms of explanations, including global rankings of relevance of features, which allow for an overview of how the model is explained as a result of its inputs and outputs. These methods provide for an increase in the explainability of the model and a greater interpretability grounded on the context of the problem. Intending to shed light on the explanations generated by XAI methods and their interpretations, this research addresses a real-world classification problem related to homicide prediction, already peer-validated, replicated its proposed black box model and used 6 different XAI methods to generate explanations and 6 different human experts. The results were generated through calculations of correlations, comparative analysis and identification of relationships between all ranks of features produced. It was found that even though it is a model that is difficult to explain, 75\% of the expectations of human experts were met, with approximately 48\% agreement between results from XAI methods and human experts. The results allow for answering questions such as: "Are the Expectation of Interpretation generated among different human experts similar?", "Do the different XAI methods generate similar explanations for the proposed problem?", "Can explanations generated by XAI methods meet human expectation of Interpretations?", and "Can Explanations and Expectations of Interpretation work together?".
A Polynomial-time Algorithm to Solve the Airplane Refueling Problem: the Sequential Search Algorithm
Venue: arXiv cs.DS 2024
Year: 2024

Airplane refueling problem is a nonlinear unconstrained optimization problem with $n!$ feasible solutions. Given a fleet of $n$ airplanes with mid-air refueling technique, the question is to find the best refueling policy to make the last remaining airplane travel the farthest. In order to solve airplane refueling problem, we proposed the definition of sequential feasible solution by employing the refueling properties of data structure. We proved that if an airplane refueling instance has feasible solutions, it must have sequential feasible solutions; and the optimal feasible solution must be the optimal sequential feasible solution. So we need to numerate all the sequential feasible solutions to get an exact algorithm. We proposed the sequential search algorithm which consists of two steps, the first step of which aims to seek out all of the sequential feasible solutions, and the second step aims to search for the maximal sequential feasible solution by bubble sorting all of the sequential feasible solutions. We observed that the number of the sequential feasible solutions will change to grow at a polynomial rate when the input size of $n$ is greater than an inflection point $N$. Then we proved that the sequential search algorithm is a polynomial-time algorithm to solve the airplane refueling problem. Moreover, we built an efficient computability scheme, according to which we could forecast within a polynomial time the computational complexity of the sequential search algorithm that runs on any given airplane refueling instance. Thus we could provide a computational strategy for decision makers or algorithm users by considering with their available computing resources.
Not All Asians are the Same: A Disaggregated Approach to Identifying Anti-Asian Racism in Social Media
Venue: arXiv cs.SI 2024
Year: 2024

Recent policy initiatives have acknowledged the importance of disaggregating data pertaining to diverse Asian ethnic communities to gain a more comprehensive understanding of their current status and to improve their overall well-being. However, research on anti-Asian racism has thus far fallen short of properly incorporating data disaggregation practices. Our study addresses this gap by collecting 12-month-long data from X (formerly known as Twitter) that contain diverse sub-ethnic group representations within Asian communities. In this dataset, we break down anti-Asian toxic messages based on both temporal and ethnic factors and conduct a series of comparative analyses of toxic messages, targeting different ethnic groups. Using temporal persistence analysis, $n$-gram-based correspondence analysis, and topic modeling, this study provides compelling evidence that anti-Asian messages comprise various distinctive narratives. Certain messages targeting sub-ethnic Asian groups entail different topics that distinguish them from those targeting Asians in a generic manner or those aimed at major ethnic groups, such as Chinese and Indian. By introducing several techniques that facilitate comparisons of online anti-Asian hate towards diverse ethnic communities, this study highlights the importance of taking a nuanced and disaggregated approach for understanding racial hatred to formulate effective mitigation strategies.