OpenRaiser/Intern-Atlas huggingface dataset:
Extraction of Sleep Information from Clinical Notes of Patients with Alzheimer's Disease Using Natural Language Processing
Venue: arXiv cs.CL 2024
Year: 2024

Alzheimer's Disease (AD) is the most common form of dementia in the United States. Sleep is one of the lifestyle-related factors that has been shown critical for optimal cognitive function in old age. However, there is a lack of research studying the association between sleep and AD incidence. A major bottleneck for conducting such research is that the traditional way to acquire sleep information is time-consuming, inefficient, non-scalable, and limited to patients' subjective experience. A gold standard dataset is created from manual annotation of 570 randomly sampled clinical note documents from the adSLEEP, a corpus of 192,000 de-identified clinical notes of 7,266 AD patients retrieved from the University of Pittsburgh Medical Center (UPMC). We developed a rule-based Natural Language Processing (NLP) algorithm, machine learning models, and Large Language Model(LLM)-based NLP algorithms to automate the extraction of sleep-related concepts, including snoring, napping, sleep problem, bad sleep quality, daytime sleepiness, night wakings, and sleep duration, from the gold standard dataset. Rule-based NLP algorithm achieved the best performance of F1 across all sleep-related concepts. In terms of Positive Predictive Value (PPV), rule-based NLP algorithm achieved 1.00 for daytime sleepiness and sleep duration, machine learning models: 0.95 and for napping, 0.86 for bad sleep quality and 0.90 for snoring; and LLAMA2 with finetuning achieved PPV of 0.93 for Night Wakings, 0.89 for sleep problem, and 1.00 for sleep duration. The results show that the rule-based NLP algorithm consistently achieved the best performance for all sleep concepts. This study focused on the clinical notes of patients with AD, but could be extended to general sleep information extraction for other diseases.
Facility Location Games Beyond Single-Peakedness: the Entrance Fee Model
Venue: arXiv cs.GT 2024
Year: 2024

The facility location game has been studied extensively in mechanism design. In the classical model, each agent's cost is solely determined by her distance to the nearest facility. In this paper, we introduce a novel model where each facility charges an entrance fee. Thus, the cost of each agent is determined by both the distance to the facility and the entrance fee of the facility. In our model, the entrance fee function is allowed to be an arbitrary function, causing agents' preferences may no longer be single-peaked anymore: This departure from the classical model introduces additional challenges. We systematically delve into the intricacies of the model, designing strategyproof mechanisms with favorable approximation ratios. Additionally, we complement these ratios with nearly-tight impossibility results. Specifically, for one-facility and two-facility games, we provide upper and lower bounds for the approximation ratios given by deterministic and randomized mechanisms with respect to utilitarian and egalitarian objectives.
Is Universal Broadband Service Impossible?
Venue: arXiv cs.NI 2024
Year: 2024

Broadband Internet service is widely expected to be the fundamental universal service for the 21st century. But more than a decade of national and international struggles to close the digital divide between broadband haves and have nots suggest that reaching global universality will be a very difficult task. This paper argues that the strong guarantees made by the current broadband paradigm - low latency and constant availability - are unnecessary obstacles to its adoption as an affordable and universal digital service. We show that there is nonetheless a plausible strategy for deploying a Basic Broadband service that does not require such guarantees and is able to offer, at reasonable cost, almost all the critical and valuable services and applications currently delivered over low latency broadband, synchronous telepresence excepted.
Attentive Fine-Grained Structured Sparsity for Image Restoration
Venue: arXiv cs.CV 2024
Year: 2024

Image restoration tasks have witnessed great performance improvement in recent years by developing large deep models. Despite the outstanding performance, the heavy computation demanded by the deep models has restricted the application of image restoration. To lift the restriction, it is required to reduce the size of the networks while maintaining accuracy. Recently, N:M structured pruning has appeared as one of the effective and practical pruning approaches for making the model efficient with the accuracy constraint. However, it fails to account for different computational complexities and performance requirements for different layers of an image restoration network. To further optimize the trade-off between the efficiency and the restoration accuracy, we propose a novel pruning method that determines the pruning ratio for N:M structured sparsity at each layer. Extensive experimental results on super-resolution and deblurring tasks demonstrate the efficacy of our method which outperforms previous pruning methods significantly. PyTorch implementation for the proposed methods is available at https://github.com/JungHunOh/SLS_CVPR2022.
Hierarchical Control for Cooperative Teams in Competitive Autonomous Racing
Venue: arXiv cs.MA 2024
Year: 2024

We investigate the problem of autonomous racing among teams of cooperative agents that are subject to realistic racing rules. Our work extends previous research on hierarchical control in head-to-head autonomous racing by considering a generalized version of the problem while maintaining the two-level hierarchical control structure. A high-level tactical planner constructs a discrete game that encodes the complex rules using simplified dynamics to produce a sequence of target waypoints. The low-level path planner uses these waypoints as a reference trajectory and computes high-resolution control inputs by solving a simplified formulation of a racing game with a simplified representation of the realistic racing rules. We explore two approaches for the low-level path planner: training a multi-agent reinforcement learning (MARL) policy and solving a linear-quadratic Nash game (LQNG) approximation. We evaluate our controllers on simple and complex tracks against three baselines: an end-to-end MARL controller, a MARL controller tracking a fixed racing line, and an LQNG controller tracking a fixed racing line. Quantitative results show our hierarchical methods outperform the baselines in terms of race wins, overall team performance, and compliance with the rules. Qualitatively, we observe the hierarchical controllers mimic actions performed by expert human drivers such as coordinated overtaking, defending against multiple opponents, and long-term planning for delayed advantages.
Fairness and promptness in Muller formulas
Venue: arXiv cs.LO 2024
Year: 2024

In this paper we consider two different views of the model checking problems for the Linear Temporal Logic (LTL). On the one hand, we consider the universal model checking problem for LTL, where one asks that for a given system and a given formula all the runs of the system satisfy the formula. On the other hand, the fair model checking problem for LTL asks that for a given system and a given formula almost all the runs of the system satisfy the formula. It was shown that these two problems have the same theoretical complexity i.e. PSPACE-complete. The question arises whether one can find a fragment of LTL for which the complexity of these two problems differs. One such fragment was identified in a previous work, namely the Muller fragment. We address a similar comparison for the prompt fragment of LTL (pLTL). pLTL extends LTL with an additional operator, i.e. the prompt-eventually. This operator ensures the existence of a bound such that liveness properties are satisfied within this bound. We show that the corresponding Muller fragment for pLTL does not enjoy the same algorithmic properties with respect to the comparison considered. We also identify a new expressive fragment for which the fair model checking is faster than the universal one.
A Modular Approach to Construct Signature-Free BRB Algorithms under a Message Adversary
Venue: arXiv cs.DC 2024
Year: 2024

This paper explores how reliable broadcast can be implemented without signatures when facing a dual adversary that can both corrupt processes and remove messages. More precisely, we consider an asynchronous $n$-process message-passing system in which up to $t_b$ processes are Byzantine and where, at the network level, for each message broadcast by a correct process, an adversary can prevent up to $t_m$ processes from receiving it (the integer $t_m$ defines the power of the message adversary). So, unlike previous works, this work considers that not only can computing entities be faulty (Byzantine processes), but, in addition, that the network can also lose messages. To this end, the paper adopts a modular strategy and first introduces a new basic communication abstraction denoted $k2\ell$-cast, which simplifies quorum engineering, and studies its properties in this new adversarial context. Then, the paper deconstructs existing signature-free Byzantine-tolerant asynchronous broadcast algorithms and, with the help of the $k2\ell$-cast communication abstraction, reconstructs versions of them that tolerate both Byzantine processes and message adversaries. Interestingly, these reconstructed algorithms are also more efficient than the Byzantine-tolerant-only algorithms from which they originate.
Deterministic pushdown automata can compress some normal sequences
Venue: arXiv cs.FL 2024
Year: 2024

In this paper, we give a deterministic pushdown transducer and a normal sequence of digits compressed by it. This solves positively a question left open in a previous paper by V. Becher, P. A. Heiber and the first author.
Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements
Venue: arXiv cs.GT 2024
Year: 2024

Fisher markets are one of the most fundamental models for resource allocation. However, the problem of computing equilibrium prices in Fisher markets typically relies on complete knowledge of users' budgets and utility functions and requires transactions to happen in a static market where all users are present simultaneously. Motivated by these practical considerations, we study an online variant of Fisher markets, wherein users with privately known utility and budget parameters, drawn i.i.d. from a distribution, arrive sequentially. In this setting, we first study the limitations of static pricing algorithms, which set uniform prices for all users, along two performance metrics: (i) regret, i.e., the optimality gap in the objective of the Eisenberg-Gale program between an online algorithm and an oracle with complete information, and (ii) capacity violations, i.e., the over-consumption of goods relative to their capacities. Given the limitations of static pricing, we design adaptive posted-pricing algorithms, one with knowledge of the distribution of users' budget and utility parameters and another that adjusts prices solely based on past observations of user consumption, i.e., revealed preference feedback, with improved performance guarantees. Finally, we present numerical experiments to compare our revealed preference algorithm's performance to several benchmarks.
Separations in Proof Complexity and TFNP
Venue: arXiv cs.CC 2024
Year: 2024

It is well-known that Resolution proofs can be efficiently simulated by Sherali-Adams (SA) proofs. We show, however, that any such simulation needs to exploit huge coefficients: Resolution cannot be efficiently simulated by SA when the coefficients are written in unary. We also show that Reversible Resolution (a variant of MaxSAT Resolution) cannot be efficiently simulated by Nullstellensatz (NS). These results have consequences for total NP search problems. First, we characterise the classes PPADS, PPAD, SOPL by unary-SA, unary-NS, and Reversible Resolution, respectively. Second, we show that, relative to an oracle, PLS $\not\subseteq$ PPP, SOPL $\not\subseteq$ PPA, and EOPL $\not\subseteq$ UEOPL. In particular, together with prior work, this gives a complete picture of the black-box relationships between all classical TFNP classes introduced in the 1990s.
Generative Evolutionary Strategy For Black-Box Optimizations
Venue: arXiv cs.NE 2024
Year: 2024

Many scientific and technological problems are related to optimization. Among them, black-box optimization in high-dimensional space is particularly challenging. Recent neural network-based black-box optimization studies have shown noteworthy achievements. However, their capability in high-dimensional search space is still limited. This study proposes a black-box optimization method based on the evolution strategy (ES) and the generative neural network (GNN) model. We designed the algorithm so that the ES and the GNN model work cooperatively. This hybrid model enables reliable training of surrogate networks; it optimizes multi-objective, high-dimensional, and stochastic black-box functions. Our method outperforms baseline optimization methods in this experiment, including ES, and Bayesian optimization.
Training from Zero: Radio Frequency Machine Learning Data Quantity Forecasting
Venue: arXiv cs.LG 2024
Year: 2024

The data used during training in any given application space is directly tied to the performance of the system once deployed. While there are many other factors that go into producing high performance models within machine learning, there is no doubt that the data used to train a system provides the foundation from which to build. One of the underlying rule of thumb heuristics used within the machine learning space is that more data leads to better models, but there is no easy answer for the question, "How much data is needed?" This work examines a modulation classification problem in the Radio Frequency domain space, attempting to answer the question of how much training data is required to achieve a desired level of performance, but the procedure readily applies to classification problems across modalities. The ultimate goal is determining an approach that requires the least amount of data collection to better inform a more thorough collection effort to achieve the desired performance metric. While this approach will require an initial dataset that is germane to the problem space to act as a \textit{target} dataset on which metrics are extracted, the goal is to allow for the initial data to be orders of magnitude smaller than what is required for delivering a system that achieves the desired performance. An additional benefit of the techniques presented here is that the quality of different datasets can be numerically evaluated and tied together with the quantity of data, and ultimately, the performance of the architecture in the problem domain.
Probabilistic Approach for Detection of High-Frequency Periodic Signals using an Event Camera
Venue: arXiv cs.CV 2024
Year: 2024

Being inspired by the biological eye, event camera is a novel asynchronous technology that pose a paradigm shift in acquisition of visual information. This paradigm enables event cameras to capture pixel-size fast motions much more naturally compared to classical cameras. In this paper we present a new asynchronous event-driven algorithm for detection of high-frequency pixel-size periodic signals using an event camera. Development of such new algorithms, to efficiently process the asynchronous information of event cameras, is essential and being a main challenge in the research community, in order to utilize its special properties and potential. It turns out that this algorithm, that was developed in order to satisfy the new paradigm, is related to an untreated theoretical problem in probability: let $0\leqτ_{1}\leqτ_{2}\leq\cdots\leqτ_{m}\leq1$, originated from an unknown distribution. Let also $ε,δ\in\mathbb{R}$, and $d\in\mathbb{N}$. What can be said about the probability $Φ(m,d)$ of having more than $d$ adjacent $τ_{i}$-s pairs that the distance between them is $δ$, up to an error $ε$ ? This problem, that reminds the area of order statistic, shows how the new visualization paradigm is also an opportunity to develop new areas and problems in mathematics.
RotorTM: A Flexible Simulator for Aerial Transportation and Manipulation
Venue: arXiv cs.RO 2024
Year: 2024

Low-cost autonomous Micro Aerial Vehicles (MAVs) have the potential to help humans by simplifying and speeding up complex tasks that require their interaction with the environment, such as construction, package delivery, and search and rescue. These systems, composed of single or multiple vehicles, can be endowed with passive connection mechanisms such as rigid links or cables to perform transportation and manipulation tasks. However, they are inherently complex since they are often underactuated and evolve in nonlinear manifold configuration spaces. In addition, the complexity of systems with cable-suspended load is further increased by the hybrid dynamics depending on the cables' varying tension conditions. This paper presents the first aerial transportation and manipulation simulator incorporating different payloads and passive connection mechanisms with full system dynamics, planning, and control algorithms. Furthermore, it includes a novel general model accounting for the transient hybrid dynamics for aerial systems with cable-suspended load to closely mimic real-world systems. The availability of a flexible and intuitive interface further contributes to its usability and versatility. Comparisons between simulations and real-world experiments with different vehicles' configurations show the fidelity of the simulator results with respect to real-world settings. The experiments also show the simulator's benefit for the rapid prototyping and transitioning of aerial transportation and manipulation systems to real-world deployment.
Self-Supervised Anomaly Detection in Computer Vision and Beyond: A Survey and Outlook
Venue: arXiv cs.LG 2024
Year: 2024

Anomaly detection (AD) plays a crucial role in various domains, including cybersecurity, finance, and healthcare, by identifying patterns or events that deviate from normal behaviour. In recent years, significant progress has been made in this field due to the remarkable growth of deep learning models. Notably, the advent of self-supervised learning has sparked the development of novel AD algorithms that outperform the existing state-of-the-art approaches by a considerable margin. This paper aims to provide a comprehensive review of the current methodologies in self-supervised anomaly detection. We present technical details of the standard methods and discuss their strengths and drawbacks. We also compare the performance of these models against each other and other state-of-the-art anomaly detection models. Finally, the paper concludes with a discussion of future directions for self-supervised anomaly detection, including the development of more effective and efficient algorithms and the integration of these techniques with other related fields, such as multi-modal learning.
Optimal grading contests
Venue: arXiv cs.GT 2024
Year: 2024

We study the design of effort-maximizing grading schemes between agents with private abilities. Assuming agents derive value from the information their grade reveals about their ability, we find that more informative grading schemes induce more competitive contests. In the contest framework, we investigate the effect of manipulating individual prizes and increasing competition on expected effort, identifying conditions on ability distributions and cost functions under which these transformations may encourage or discourage effort. Our results suggest that more informative grading schemes encourage effort when agents of moderate ability are highly likely, and discourage effort when such agents are unlikely.
Outage Analysis of Aerial Semi-Grant-Free NOMA Systems
Venue: arXiv cs.IT 2024
Year: 2024

In this paper, we analyze the outage performance of unmanned aerial vehicles (UAVs)-enabled downlink non-orthogonal multiple access (NOMA) communication systems with the semi-grant-free (SGF) transmission scheme. A UAV provides coverage services for a grant-based (GB) user and one user is allowed to utilize the same channel resource opportunistically. The hybrid successive interference cancellation scheme is implemented in the downlink NOMA scenarios for the first time. The analytical expressions for the exact and asymptotic outage probability (OP) of the grant-free (GF) user are derived. The results demonstrate that no-zero diversity order can be achieved only under stringent conditions on users' quality of service requirements. Subsequently, we propose an efficient dynamic power allocation (DPA) scheme to relax such data rate constraints to address this issue. The analytical expressions for the exact and asymptotic OP of the GF user with the DPA scheme are derived. Finally, Monte Carlo simulation results are presented to validate the correctness of the derived analytical expressions and demonstrate the effects of the UAV's location and altitude on the OP of the GF user.
Fully Abstract Encodings of $λ$-Calculus in HOcore through Abstract Machines
Venue: arXiv cs.LO 2024
Year: 2024

We present fully abstract encodings of the call-by-name and call-by-value $λ$-calculus into HOcore, a minimal higher-order process calculus with no name restriction. We consider several equivalences on the $λ$-calculus side -- normal-form bisimilarity, applicative bisimilarity, and contextual equivalence -- that we internalize into abstract machines in order to prove full abstraction of the encodings. We also demonstrate that this technique scales to the $λμ$-calculus, i.e., a standard extension of the $λ$-calculus with control operators.
Tight Differential Privacy Guarantees for the Shuffle Model with $k$-Randomized Response
Venue: arXiv cs.CR 2024
Year: 2024

Most differentially private (DP) algorithms assume a central model in which a reliable third party inserts noise to queries made on datasets, or a local model where the users locally perturb their data. However, the central model is vulnerable via a single point of failure, and in the local model, the utility of the data deteriorates significantly. The recently proposed shuffle model is an intermediate framework between the central and the local paradigms where the users send their locally privatized data to a server where messages are shuffled, effacing the link between a privatized message and the corresponding user, giving a better trade-off between privacy and utility than the local model, as its privacy gets amplified without adding more noise. In this paper, we theoretically derive the strictest known bound for DP guarantee for the shuffle models with $k$-Randomized Response local randomizers. There on, we focus on the utility of the shuffle model for histogram queries. Leveraging on the matrix inversion method, which is used to approximate the original distribution from the empirical one produced by the $k$-RR mechanism, we de-noise the histogram produced by the shuffle model to evaluate the total variation distance of the resulting histogram from the true one, which we regard as the measure of utility of the privacy mechanism. We perform experiments on both synthetic and real data to compare the privacy-utility trade-off of the shuffle model with that of the central one privatized by adding the state-of-the-art Gaussian noise to each bin. Although the experimental results stay consistent with the literature that favour the central model, we see that, the difference in statistical utilities between the central and the shuffle models is very small, showing that they are almost comparable under the same level of DP.