OpenRaiser/Intern-Atlas huggingface dataset:
3/2-Approximation for the Forest Augmentation Problem
Venue: arXiv cs.DS 2024
Year: 2024

We describe a $\frac{3}{2}$-approximation algorithm for the Forest Augmentation Problem (\textsf{FAP}), which is a special case of the Weighted 2-Edge-Connected Spanning Subgraph Problem (\textsf{Weighted 2-ECSS}). This significantly improves upon the previous best ratio $1.9973$, and proceeds toward the goal of a $\frac{3}{2}$-approximation algorithm for \textsf{Weighted 2-ECSS}.
UFQA: Utility guided Fingerphoto Quality Assessment
Venue: arXiv cs.CV 2024
Year: 2024

Quality assessment of fingerprints captured using digital cameras and smartphones, also called fingerphotos, is a challenging problem in biometric recognition systems. As contactless biometric modalities are gaining more attention, their reliability should also be improved. Many factors, such as illumination, image contrast, camera angle, etc., in fingerphoto acquisition introduce various types of distortion that may render the samples useless. Current quality estimation methods developed for fingerprints collected using contact-based sensors are inadequate for fingerphotos. We propose Utility guided Fingerphoto Quality Assessment (UFQA), a self-supervised dual encoder framework to learn meaningful feature representations to assess fingerphoto quality. A quality prediction model is trained to assess fingerphoto quality with additional supervision of quality maps. The quality metric is a predictor of the utility of fingerphotos in matching scenarios. Therefore, we use a holistic approach by including fingerphoto utility and local quality when labeling the training data. Experimental results verify that our approach performs better than the widely used fingerprint quality metric NFIQ2.2 and state-of-the-art image quality assessment algorithms on multiple publicly available fingerphoto datasets.
YouTube-SL-25: A Large-Scale, Open-Domain Multilingual Sign Language Parallel Corpus
Venue: arXiv cs.CL 2024
Year: 2024

Even for better-studied sign languages like American Sign Language (ASL), data is the bottleneck for machine learning research. The situation is worse yet for the many other sign languages used by Deaf/Hard of Hearing communities around the world. In this paper, we present YouTube-SL-25, a large-scale, open-domain multilingual corpus of sign language videos with seemingly well-aligned captions drawn from YouTube. With >3000 hours of videos across >25 sign languages, YouTube-SL-25 is a) >3x the size of YouTube-ASL, b) the largest parallel sign language dataset to date, and c) the first or largest parallel dataset for many of its component languages. We provide baselines for sign-to-text tasks using a unified multilingual multitask model based on T5 and report scores on benchmarks across 4 sign languages. The results demonstrate that multilingual transfer benefits both higher- and lower-resource sign languages within YouTube-SL-25.
Transformer-based Drum-level Prediction in a Boiler Plant with Delayed Relations among Multivariates
Venue: arXiv cs.LG 2024
Year: 2024

The steam drum water level is a critical parameter that directly impacts the safety and efficiency of power plant operations. However, predicting the drum water level in boilers is challenging due to complex non-linear process dynamics originating from long-time delays and interrelations, as well as measurement noise. This paper investigates the application of Transformer-based models for predicting drum water levels in a steam boiler plant. Leveraging the capabilities of Transformer architectures, this study aims to develop an accurate and robust predictive framework to anticipate water level fluctuations and facilitate proactive control strategies. To this end, a prudent pipeline is proposed, including 1) data preprocess, 2) causal relation analysis, 3) delay inference, 4) variable augmentation, and 5) prediction. Through extensive experimentation and analysis, the effectiveness of Transformer-based approaches in steam drum water level prediction is evaluated, highlighting their potential to enhance operational stability and optimize plant performance.
Algorithms for College Admissions Decision Support: Impacts of Policy Change and Inherent Variability
Venue: arXiv cs.CY 2024
Year: 2024

Each year, selective American colleges sort through tens of thousands of applications to identify a first-year class that displays both academic merit and diversity. In the 2023-2024 admissions cycle, these colleges faced unprecedented challenges. First, the number of applications has been steadily growing. Second, test-optional policies that have remained in place since the COVID-19 pandemic limit access to key information historically predictive of academic success. Most recently, longstanding debates over affirmative action culminated in the Supreme Court banning race-conscious admissions. Colleges have explored machine learning (ML) models to address the issues of scale and missing test scores, often via ranking algorithms intended to focus on 'top' applicants. However, the Court's ruling will force changes to these models, which were able to consider race as a factor in ranking. There is currently a poor understanding of how these mandated changes will shape applicant ranking algorithms, and, by extension, admitted classes. We seek to address this by quantifying the impact of different admission policies on the applications prioritized for review. We show that removing race data from a developed applicant ranking algorithm reduces the diversity of the top-ranked pool without meaningfully increasing the academic merit of that pool. We contextualize this impact by showing that excluding data on applicant race has a greater impact than excluding other potentially informative variables like intended majors. Finally, we measure the impact of policy change on individuals by comparing the arbitrariness in applicant rank attributable to policy change to the arbitrariness attributable to randomness. We find that any given policy has a high degree of arbitrariness and that removing race data from the ranking algorithm increases arbitrariness in outcomes for most applicants.
Actuation without production bias
Venue: arXiv cs.CL 2024
Year: 2024

Phonetic production bias is the external force most commonly invoked in computational models of sound change, despite the fact that it is not responsible for all, or even most, sound changes. Furthermore, the existence of production bias alone cannot account for how changes do or do not propagate throughout a speech community. While many other factors have been invoked by (socio)phoneticians, including but not limited to contact (between subpopulations) and differences in social evaluation (of variants, groups, or individuals), these are not typically modeled in computational simulations of sound change. In this paper, we consider whether production biases have a unique dynamics in terms of how they impact the population-level spread of change in a setting where agents learn from multiple teachers. We show that, while the dynamics conditioned by production bias are not unique, it is not the case that all perturbing forces have the same dynamics: in particular, if social weight is a function of individual teachers and the correlation between a teacher's social weight and the extent to which they realize a production bias is weak, change is unlikely to propagate. Nevertheless, it remains the case that changes initiated from different sources may display a similar dynamics. A more nuanced understanding of how population structure interacts with individual biases can thus provide a (partial) solution to the `non-phonologization problem'.
Impact on clinical guideline adherence of Orient-COVID, a CDSS based on dynamic medical decision trees for COVID19 management: a randomized simulation trial
Venue: arXiv cs.HC 2024
Year: 2024

Background: The adherence of clinicians to clinical practice guidelines is known to be low, including for the management of COVID-19, due to their difficult use at the point of care and their complexity. Clinical decision support systems have been proposed to implement guidelines and improve adherence. One approach is to permit the navigation inside the recommendations, presented as a decision tree, but the size of the tree often limits this approach and may cause erroneous navigation, especially when it does not fit in a single screen. Methods: We proposed an innovative visual interface to allow clinicians easily navigating inside decision trees for the management of COVID-19 patients. It associates a multi-path tree model with the use of the fisheye visual technique, allowing the visualization of large decision trees in a single screen. To evaluate the impact of this tool on guideline adherence, we conducted a randomized controlled trial in a near-real simulation setting, comparing the decisions taken by medical students using Orient-COVID with those taken with paper guidelines or without guidance, when performing on six realistic clinical cases. Results: The results show that paper guidelines had no impact (p=0.97), while Orient-COVID significantly improved the guideline adherence compared to both other groups (p<0.0003). A significant impact of Orient-COVID was identified on several key points during the management of COVID-19: ordering troponin lab tests, prescribing anticoagulant and oxygen therapy. A multifactor analysis showed no difference between male and female participants. Conclusions: The use of an interactive decision tree for the management of COVID-19 significantly improved the clinician adherence to guidelines. Future works will focus on the integration of the system to electronic health records and on the adaptation of the system to other clinical conditions.
Unraveling the Truth: Do VLMs really Understand Charts? A Deep Dive into Consistency and Robustness
Venue: arXiv cs.CL 2024
Year: 2024

Chart question answering (CQA) is a crucial area of Visual Language Understanding. However, the robustness and consistency of current Visual Language Models (VLMs) in this field remain under-explored. This paper evaluates state-of-the-art VLMs on comprehensive datasets, developed specifically for this study, encompassing diverse question categories and chart formats. We investigate two key aspects: 1) the models' ability to handle varying levels of chart and question complexity, and 2) their robustness across different visual representations of the same underlying data. Our analysis reveals significant performance variations based on question and chart types, highlighting both strengths and weaknesses of current models. Additionally, we identify areas for improvement and propose future research directions to build more robust and reliable CQA systems. This study sheds light on the limitations of current models and paves the way for future advancements in the field.
Making New Connections: LLMs as Puzzle Generators for The New York Times' Connections Word Game
Venue: arXiv cs.AI 2024
Year: 2024

The Connections puzzle is a word association game published daily by The New York Times (NYT). In this game, players are asked to find groups of four words that are connected by a common theme. While solving a given Connections puzzle requires both semantic knowledge and abstract reasoning, generating novel puzzles additionally requires a form of metacognition: generators must be able to accurately model the downstream reasoning of potential solvers. In this paper, we investigate the ability of the GPT family of Large Language Models (LLMs) to generate challenging and creative word games for human players. We start with an analysis of the word game Connections and the unique challenges it poses as a Procedural Content Generation (PCG) domain. We then propose a method for generating Connections puzzles using LLMs by adapting a Tree of Thoughts (ToT) prompting approach. We evaluate this method by conducting a user study, asking human players to compare AI-generated puzzles against published Connections puzzles. Our findings show that LLMs are capable puzzle creators, and can generate diverse sets of enjoyable, challenging, and creative Connections puzzles as judged by human users.
(Deep) Generative Geodesics
Venue: arXiv cs.LG 2024
Year: 2024

In this work, we propose to study the global geometrical properties of generative models. We introduce a new Riemannian metric to assess the similarity between any two data points. Importantly, our metric is agnostic to the parametrization of the generative model and requires only the evaluation of its data likelihood. Moreover, the metric leads to the conceptual definition of generative distances and generative geodesics, whose computation can be done efficiently in the data space. Their approximations are proven to converge to their true values under mild conditions. We showcase three proof-of-concept applications of this global metric, including clustering, data visualization, and data interpolation, thus providing new tools to support the geometrical understanding of generative models.
Conditions for Altruistic Perversity in Two-Strategy Population Games
Venue: arXiv cs.GT 2024
Year: 2024

Self-interested behavior from individuals can collectively lead to poor societal outcomes. These outcomes can seemingly be improved through the actions of altruistic agents, which benefit other agents in the system. However, it is known in specific contexts that altruistic agents can actually induce worse outcomes compared to a fully selfish population -- a phenomenon we term altruistic perversity. This paper provides a holistic investigation into the necessary conditions that give rise to altruistic perversity. In particular, we study the class of two-strategy population games where one sub-population is altruistic and the other is selfish. We find that a population game can admit altruistic perversity only if the associated social welfare function is convex and the altruistic population is sufficiently large. Our results are a first step in establishing a connection between properties of nominal agent interactions and the potential impacts from altruistic behaviors.
SoK: Software Debloating Landscape and Future Directions
Venue: arXiv cs.SE 2024
Year: 2024

Software debloating seeks to mitigate security risks and improve performance by eliminating unnecessary code. In recent years, a plethora of debloating tools have been developed, creating a dense and varied landscape. Several studies have delved into the literature, focusing on comparative analysis of these tools. To build upon these efforts, this paper presents a comprehensive systematization of knowledge (SoK) of the software debloating landscape. We conceptualize the software debloating workflow, which serves as the basis for developing a multilevel taxonomy. This framework classifies debloating tools according to their input/output artifacts, debloating strategies, and evaluation criteria. Lastly, we apply the taxonomy to pinpoint open problems in the field, which, together with the SoK, provide a foundational reference for researchers aiming to improve software security and efficiency through debloating.
Static Detection of Filesystem Vulnerabilities in Android Systems
Venue: arXiv cs.CR 2024
Year: 2024

Filesystem vulnerabilities persist as a significant threat to Android systems, despite various proposed defenses and testing techniques. The complexity of program behaviors and access control mechanisms in Android systems makes it challenging to effectively identify these vulnerabilities. In this paper, we present PathSentinel, which overcomes the limitations of previous techniques by combining static program analysis and access control policy analysis to detect three types of filesystem vulnerabilities: path traversals, hijacking vulnerabilities, and luring vulnerabilities. By unifying program and access control policy analysis, PathSentinel identifies attack surfaces accurately and prunes many impractical attacks to generate input payloads for vulnerability testing. To streamline vulnerability validation, PathSentinel leverages large language models (LLMs) to generate targeted exploit code based on the identified vulnerabilities and generated input payloads. The LLMs serve as a tool to reduce the engineering effort required for writing test applications, demonstrating the potential of combining static analysis with LLMs to enhance the efficiency of exploit generation and vulnerability validation. Evaluation on Android 12 and 14 systems from Samsung and OnePlus demonstrates PathSentinel's effectiveness, uncovering 51 previously unknown vulnerabilities among 217 apps with only 2 false positives. These results underscore the importance of combining program and access control policy analysis for accurate vulnerability detection and highlight the promising direction of integrating LLMs for automated exploit generation, providing a comprehensive approach to enhancing the security of Android systems against filesystem vulnerabilities.
Novel Approach for Predicting the Air Quality Index of Megacities through Attention-Enhanced Deep Multitask Spatiotemporal Learning
Venue: arXiv cs.LG 2024
Year: 2024

Air pollution remains one of the most formidable environmental threats to human health globally, particularly in urban areas, contributing to nearly 7 million premature deaths annually. Megacities, defined as cities with populations exceeding 10 million, are frequent hotspots of severe pollution, experiencing numerous weeks of dangerously poor air quality due to the concentration of harmful pollutants. In addition, the complex interplay of factors makes accurate air quality predictions incredibly challenging, and prediction models often struggle to capture these intricate dynamics. To address these challenges, this paper proposes an attention-enhanced deep multitask spatiotemporal machine learning model based on long-short-term memory networks for long-term air quality monitoring and prediction. The model demonstrates robust performance in predicting the levels of major pollutants such as sulfur dioxide and carbon monoxide, effectively capturing complex trends and fluctuations. The proposed model provides actionable information for policymakers, enabling informed decision making to improve urban air quality.
PADRe: A Unifying Polynomial Attention Drop-in Replacement for Efficient Vision Transformer
Venue: arXiv cs.CV 2024
Year: 2024

We present Polynomial Attention Drop-in Replacement (PADRe), a novel and unifying framework designed to replace the conventional self-attention mechanism in transformer models. Notably, several recent alternative attention mechanisms, including Hyena, Mamba, SimA, Conv2Former, and Castling-ViT, can be viewed as specific instances of our PADRe framework. PADRe leverages polynomial functions and draws upon established results from approximation theory, enhancing computational efficiency without compromising accuracy. PADRe's key components include multiplicative nonlinearities, which we implement using straightforward, hardware-friendly operations such as Hadamard products, incurring only linear computational and memory costs. PADRe further avoids the need for using complex functions such as Softmax, yet it maintains comparable or superior accuracy compared to traditional self-attention. We assess the effectiveness of PADRe as a drop-in replacement for self-attention across diverse computer vision tasks. These tasks include image classification, image-based 2D object detection, and 3D point cloud object detection. Empirical results demonstrate that PADRe runs significantly faster than the conventional self-attention (11x ~ 43x faster on server GPU and mobile NPU) while maintaining similar accuracy when substituting self-attention in the transformer models.
Detection of Global Anomalies on Distributed IoT Edges with Device-to-Device Communication
Venue: arXiv cs.LG 2024
Year: 2024

Anomaly detection is an important function in IoT applications for finding outliers caused by abnormal events. Anomaly detection sometimes comes with high-frequency data sampling which should be carried out at Edge devices rather than Cloud. In this paper, we consider the case that multiple IoT devices are installed in a single remote site and that they collaboratively detect anomalies from the observations with device-to-device communications. For this, we propose a fully distributed collaborative scheme for training distributed anomaly detectors with Wireless Ad Hoc Federated Learning, namely "WAFL-Autoencoder". We introduce the concept of Global Anomaly which sample is not only rare to the local device but rare to all the devices in the target domain. We also propose a distributed threshold-finding algorithm for Global Anomaly detection. With our standard benchmark-based evaluation, we have confirmed that our scheme trained anomaly detectors perfectly across the devices. We have also confirmed that the devices collaboratively found thresholds for Global Anomaly detection with low false positive rates while achieving high true positive rates with few exceptions.
A2E: Attribute-based Anonymity-Enhanced Authentication for Accessing Driverless Taxi Service
Venue: arXiv cs.CR 2024
Year: 2024

Driverless vehicle as a taxi is gaining more attention due to its potential to enhance urban transportation efficiency. However, both unforeseen incidents led by unsupervised physical users' driverless taxi (DT) rides and personalized needs of users when riding in a DT necessitate the authentication of user identity and attributes. Moreover, safeguarding user identity privacy and quickly tracing malicious users if necessary to enhance the adoption of DTs remains a challenge. This paper proposes a novel Attribute-based Anonymity Enhanced (A2E) authentication scheme for users to access DT service. From the security aspect, A2E has attribute verifiability, which is achieved by designing a user attribute credential based on redactable signature. Meanwhile, this attribute credential also satisfies unlinkability and unforgeability. In addition, A2E has enhanced anonymity, which is achieved by designing a decentralized credential issuance mechanism utilizing ring signature and secret sharing, safeguarding user attributes from association with anonymous identities. Moreover, this mechanism provides traceability and non-frameability to users. From the performance aspect, A2E causes low overhead when tracing malicious users and updating credentials. Besides, both scalability and lightweight are satisfied, which contributes to A2E's practicability. We conduct security analysis and performance evaluation to the security and performance capabilities of A2E.