OpenRaiser/Intern-Atlas huggingface dataset:
Stochastic High Fidelity Autonomous Fixed Wing Aircraft Flight Simulator
Venue: arXiv cs.RO 2023
Year: 2023

This document describes the architecture and algorithms of a high fidelity fixed wing flight simulator intended to test and validate novel guidance, navigation, and control (GNC) algorithms for autonomous aircraft. It aims to replicate the influence of as many factors as possible on the aircraft performances, the Earth model, the physics of flight and the associated equations of motion, and in particular the behavior of the onboard sensors, limiting the assumptions to the bare minimum, and including multiple relatively minor effects not usually considered in simulation that may play a role in the GNC algorithms not performing as intended. The author releases the flight simulator C ++ implementation as open-source software. The simulator modular design enables the replacement of the standard GNC algorithms with the objective of evaluating their performances when subject to specific missions and meteorological conditions (atmospheric properties, wind field, air turbulence). The testing and evaluation is performed by means of Monte Carlo simulations, as most simulation modules (such as the aircraft mission, the meteorological conditions, the errors introduced by the sensors, and the initial conditions) are defined stochastically and hence vary in a pseudo-random way from one execution to the next according to certain user-defined input parameters, ensuring that the results are valid for a wide range of conditions. In addition to modeling the outputs of all sensors usually present onboard a fixed wing platform, such as accelerometers, gyroscopes, magnetometers, Pitot tube, air vanes, and a Global Navigation Satellite System (GNCC) receiver, the simulator is also capable of generating realistic images of the Earth surface that resemble what an onboard camera would record if following the resulting trajectory, enabling the use and evaluation of visual and visual inertial navigation systems.
Gym-preCICE: Reinforcement Learning Environments for Active Flow Control
Venue: arXiv cs.LG 2023
Year: 2023

Active flow control (AFC) involves manipulating fluid flow over time to achieve a desired performance or efficiency. AFC, as a sequential optimisation task, can benefit from utilising Reinforcement Learning (RL) for dynamic optimisation. In this work, we introduce Gym-preCICE, a Python adapter fully compliant with Gymnasium (formerly known as OpenAI Gym) API to facilitate designing and developing RL environments for single- and multi-physics AFC applications. In an actor-environment setting, Gym-preCICE takes advantage of preCICE, an open-source coupling library for partitioned multi-physics simulations, to handle information exchange between a controller (actor) and an AFC simulation environment. The developed framework results in a seamless non-invasive integration of realistic physics-based simulation toolboxes with RL algorithms. Gym-preCICE provides a framework for designing RL environments to model AFC tasks, as well as a playground for applying RL algorithms in various AFC-related engineering applications.
Algorithmic Theory of Qubit Routing
Venue: arXiv cs.DS 2023
Year: 2023

The qubit routing problem, also known as the swap minimization problem, is a (classical) combinatorial optimization problem that arises in the design of compilers of quantum programs. We study the qubit routing problem from the viewpoint of theoretical computer science, while most of the existing studies investigated the practical aspects. We concentrate on the linear nearest neighbor (LNN) architectures of quantum computers, in which the graph topology is a path. Our results are three-fold. (1) We prove that the qubit routing problem is NP-hard. (2) We give a fixed-parameter algorithm when the number of two-qubit gates is a parameter. (3) We give a polynomial-time algorithm when each qubit is involved in at most one two-qubit gate.
HD Map Generation from Noisy Multi-Route Vehicle Fleet Data on Highways with Expectation Maximization
Venue: arXiv cs.RO 2023
Year: 2023

High Definition (HD) maps are necessary for many applications of automated driving (AD), but their manual creation and maintenance is very costly. Vehicle fleet data from series production vehicles can be used to automatically generate HD maps, but the data is often incomplete and noisy. We propose a system for the generation of HD maps from vehicle fleet data, which is tolerant to missing or misclassified detections and can handle drives with multiple routes, generating a single complete map, model-free and without prior reference lines. Using randomly selected drives as pivot drives, a step-wise lateral sampling of detections is performed. These sampled points are then clustered and aligned using Expectation Maximization (EM), estimating a lateral offset for each drive to compensate localization errors. The clustered points are replaced with the maxima of their probability density function (PDF) and connected to form polylines using a modified rectangular linear assignment algorithm. The data from vehicles on varying routes is then fused into a hierarchical singular map graph. The proposed approach achieves an average accuracy below 0.5 meters compared to a hand annotated ground truth map, as well as correctly resolving lane splits and merges, proving the feasibility of the use of vehicle fleet data for the generation of highway HD maps.
Single Image Deraining via Feature-based Deep Convolutional Neural Network
Venue: arXiv cs.CV 2023
Year: 2023

It is challenging to remove rain-steaks from a single rainy image because the rain steaks are spatially varying in the rainy image. Although the CNN based methods have reported promising performance recently, there are still some defects, such as data dependency and insufficient interpretation. A single image deraining algorithm based on the combination of data-driven and model-based approaches is proposed. Firstly, an improved weighted guided image filter (iWGIF) is used to extract high-frequency information and learn the rain steaks to avoid interference from other information through the input image. Then, transfering the input image and rain steaks from the image domain to the feature domain adaptively to learn useful features for high-quality image deraining. Finally, networks with attention mechanisms is used to restore high-quality images from the latent features. Experiments show that the proposed algorithm significantly outperforms state-of-the-art methods in terms of both qualitative and quantitative measures.
Heterogeneous GNN-RL Based Task Offloading for UAV-aided Smart Agriculture
Venue: arXiv cs.NI 2023
Year: 2023

Having unmanned aerial vehicles (UAVs) with edge computing capability hover over smart farmlands supports Internet of Things (IoT) devices with low processing capacity and power to accomplish their deadline-sensitive tasks efficiently and economically. In this work, we propose a graph neural network-based reinforcement learning solution to optimize the task offloading from these IoT devices to the UAVs. We conduct evaluations to show that our approach reduces task deadline violations while also increasing the mission time of the UAVs by optimizing their battery usage. Moreover, the proposed solution has increased robustness to network topology changes and is able to adapt to extreme cases, such as the failure of a UAV.
Why Oatmeal is Cheap: Kolmogorov Complexity and Procedural Generation
Venue: arXiv cs.AI 2023
Year: 2023

Although procedural generation is popular among game developers, academic research on the topic has primarily focused on new applications, with some research into empirical analysis. In this paper we relate theoretical work in information theory to the generation of content for games. We prove that there is a relationship between the Kolomogorov complexity of the most complex artifact a generator can produce, and the size of that generator's possibility space. In doing so, we identify the limiting relationship between the knowledge encoded in a generator, the density of its output space, and the intricacy of the artifacts it produces. We relate our result to the experience of expert procedural generator designers, and illustrate it with some examples.
Hierarchical and Upstream-Downstream Composition of Stock and Flow Models
Venue: arXiv cs.LO 2023
Year: 2023

The growing complexity of decision-making in public health and health care has motivated an increasing use of mathematical modeling. An important line of health modeling is based on stock & flow diagrams. Such modeling elevates transparency across the interdisciplinary teams responsible for most impactful models, but existing tools suffer from a number of shortcomings when used at scale. Recent research has sought to address such limitations by establishing a categorical foundation for stock & flow modeling, including the capacity to compose a pair of models through identification of common stocks and sum variables. This work supplements such efforts by contributing two new forms of composition for stock & flow diagrams. We first describe a hierarchical means of diagram composition, in which a single existing stock is replaced by a diagram featuring compatible flow structure. Our composition method offers extra flexibility by allowing a single flow in the stock being replaced to split into several flows totalling to the same overall flow rate. Secondly, to address the common need of docking a stock & flow diagram with another "upstream" diagram depicting antecedent factors, we contribute a composition approach that allows a flow out of an upstream stock in one diagram to be connected to a downstream stock in another diagram. Both of these approaches are enabled by performing colimit decomposition of stock & flow diagrams into single-stock corollas and unit flows.
Stackelberg Attacks on Auctions and Blockchain Transaction Fee Mechanisms
Venue: arXiv cs.GT 2023
Year: 2023

We study an auction with $m$ identical items in a context where $n$ agents can arbitrarily commit to strategies. In general, such commitments non-trivially change the equilibria by inducing a metagame of choosing which strategies to commit to. In this model, we demonstrate a strategy that an attacker may commit to that ensures they receive one such item for free, while forcing the remaining agents to enter into a lottery for the remaining items (albeit for free). The attack is thus detrimental to the auctioneer who loses most of their revenue. For various types of auctions that are not too congested, we show that the strategy works as long as the agents have valuations that are somewhat concentrated. In this case, all agents will voluntarily cooperate with the attacker to enter into the lottery, because doing so gives them a chance of receiving a free item that would have otherwise cost an amount commensurate with their valuation. The attack is robust to a large constant fraction of the agents being either oblivious to the attack or having exceptionally high valuations (thus reluctant to enter into the lottery). For these agents, the attacker may coerce them into cooperating by promising them a free item rather than entering in to the lottery. We show that the conditions for the attack to work hold with high probability when (1) the auction is not too congested, and (2) the valuations are sampled i.i.d. from either a uniform distribution or a Pareto distribution. The attack works for first-price auctions, second-price auctions and the transaction fee mechanism EIP-1559 used by the Ethereum blockchain.
Uncovering ChatGPT's Capabilities in Recommender Systems
Venue: arXiv cs.IR 2023
Year: 2023

The debut of ChatGPT has recently attracted the attention of the natural language processing (NLP) community and beyond. Existing studies have demonstrated that ChatGPT shows significant improvement in a range of downstream NLP tasks, but the capabilities and limitations of ChatGPT in terms of recommendations remain unclear. In this study, we aim to conduct an empirical analysis of ChatGPT's recommendation ability from an Information Retrieval (IR) perspective, including point-wise, pair-wise, and list-wise ranking. To achieve this goal, we re-formulate the above three recommendation policies into a domain-specific prompt format. Through extensive experiments on four datasets from different domains, we demonstrate that ChatGPT outperforms other large language models across all three ranking policies. Based on the analysis of unit cost improvements, we identify that ChatGPT with list-wise ranking achieves the best trade-off between cost and performance compared to point-wise and pair-wise ranking. Moreover, ChatGPT shows the potential for mitigating the cold start problem and explainable recommendation. To facilitate further explorations in this area, the full code and detailed original results are open-sourced at https://github.com/rainym00d/LLM4RS.
Experiences with Remote Examination Formats in Light of GPT-4
Venue: arXiv cs.CY 2023
Year: 2023

Sudden access to the rapidly improving large language model GPT by open-ai forces educational institutions worldwide to revisit their exam procedures. In the pre-GPT era, we successfully applied oral and open-book home exams for two courses in the third year of our predominantly remote Software Engineering BSc program. We ask in this paper whether our current open-book exams are still viable or whether a move back to a legally compliant but less scalable oral exam is the only workable alternative. We further compare work-effort estimates between oral and open-book exams and report on differences in throughput and grade distribution over eight years to better understand the impact of examination format on the outcome. Examining GPT v4 on the most recent open-book exams showed that our current Artificial Intelligence and Reactive Programming exams are not GPT v4 proof. Three potential weaknesses of GPT are outlined. We also found that grade distributions have largely been unaffected by the examination format, opening up for a move to oral examinations only if needed. Throughput was higher for open-book exam course instances (73% vs 64%), while fail rates were too (12% vs 7%), with teacher workload increasing even for smaller classes. We also report on our experience regarding effort. Oral examinations are efficient for smaller groups but come with caveats regarding intensity and stress.
Some Observations on Fact-Checking Work with Implications for Computational Support
Venue: arXiv cs.HC 2023
Year: 2023

Social media and user-generated content (UGC) have become increasingly important features of journalistic work in a number of different ways. However, the growth of misinformation means that news organisations have had devote more and more resources to determining its veracity and to publishing corrections if it is found to be misleading. In this work, we present the results of interviews with eight members of fact-checking teams from two organisations. Team members described their fact-checking processes and the challenges they currently face in completing a fact-check in a robust and timely way. The former reveals, inter alia, significant differences in fact-checking practices and the role played by collaboration between team members. We conclude with a discussion of the implications for the development and application of computational tools, including where computational tool support is currently lacking and the importance of being able to accommodate different fact-checking practices.
Connecting the Dots in Trustworthy Artificial Intelligence: From AI Principles, Ethics, and Key Requirements to Responsible AI Systems and Regulation
Venue: arXiv cs.CY 2023
Year: 2023

Trustworthy Artificial Intelligence (AI) is based on seven technical requirements sustained over three main pillars that should be met throughout the system's entire life cycle: it should be (1) lawful, (2) ethical, and (3) robust, both from a technical and a social perspective. However, attaining truly trustworthy AI concerns a wider vision that comprises the trustworthiness of all processes and actors that are part of the system's life cycle, and considers previous aspects from different lenses. A more holistic vision contemplates four essential axes: the global principles for ethical use and development of AI-based systems, a philosophical take on AI ethics, a risk-based approach to AI regulation, and the mentioned pillars and requirements. The seven requirements (human agency and oversight; robustness and safety; privacy and data governance; transparency; diversity, non-discrimination and fairness; societal and environmental wellbeing; and accountability) are analyzed from a triple perspective: What each requirement for trustworthy AI is, Why it is needed, and How each requirement can be implemented in practice. On the other hand, a practical approach to implement trustworthy AI systems allows defining the concept of responsibility of AI-based systems facing the law, through a given auditing process. Therefore, a responsible AI system is the resulting notion we introduce in this work, and a concept of utmost necessity that can be realized through auditing processes, subject to the challenges posed by the use of regulatory sandboxes. Our multidisciplinary vision of trustworthy AI culminates in a debate on the diverging views published lately about the future of AI. Our reflections in this matter conclude that regulation is a key for reaching a consensus among these views, and that trustworthy and responsible AI systems will be crucial for the present and future of our society.
$L$ is unequal $NL$ under the Strong Exponential Time Hypothesis
Venue: arXiv cs.CC 2023
Year: 2023

Due to Savitch's theorem we know $NL\subseteq DSPACE(\log^2(n))$. To show this upper bound, Savitch constructed an algorithm with $O(\log^2(n))$ space on the working tape. We will show that Savitch's algorithm also described a lower bound under the Strong Exponential Time Hypothesis. Every algorithm for the Connectivity Problem needs $O(\log^2(n))$ space in this case.
The offline digital currency puzzle solved by a local blockchain
Venue: arXiv cs.CR 2023
Year: 2023

A major drawback in deploying central bank digital currencies (CDBC) is the offline puzzle, which requires that a CBDC must keep the provision given by cash, and, simultaneously, avoid double-spending, counterfeiting, and other issues. The puzzle is solved by minting the coins in serials, which are stored on a local blockchain (e.g. smartphone). The local blockchain is secured by keys embedded in the hardware and can be continuously mined by the wallet to enhance security. The coins can be either minted as hot coins, which can be retrieved in case of loss, or minted as cold coins, like physical cash.
Entity-Based Evaluation of Political Bias in Automatic Summarization
Venue: arXiv cs.CL 2023
Year: 2023

Growing literature has shown that NLP systems may encode social biases; however, the political bias of summarization models remains relatively unknown. In this work, we use an entity replacement method to investigate the portrayal of politicians in automatically generated summaries of news articles. We develop an entity-based computational framework to assess the sensitivities of several extractive and abstractive summarizers to the politicians Donald Trump and Joe Biden. We find consistent differences in these summaries upon entity replacement, such as reduced emphasis of Trump's presence in the context of the same article and a more individualistic representation of Trump with respect to the collective US government (i.e., administration). These summary dissimilarities are most prominent when the entity is heavily featured in the source article. Our characterization provides a foundation for future studies of bias in summarization and for normative discussions on the ideal qualities of automatic summaries.
Proof in the time of machines
Venue: arXiv cs.LO 2023
Year: 2023

We compare the values associated with (traditional) community based proof verification to those associated with computer proof verification. We propose ways that computer proofs might incorporate successful strategies from human experiences.
Approximating CKY with Transformers
Venue: arXiv cs.CL 2023
Year: 2023

We investigate the ability of transformer models to approximate the CKY algorithm, using them to directly predict a sentence's parse and thus avoid the CKY algorithm's cubic dependence on sentence length. We find that on standard constituency parsing benchmarks this approach achieves competitive or better performance than comparable parsers that make use of CKY, while being faster. We also evaluate the viability of this approach for parsing under \textit{random} PCFGs. Here we find that performance declines as the grammar becomes more ambiguous, suggesting that the transformer is not fully capturing the CKY computation. However, we also find that incorporating additional inductive bias is helpful, and we propose a novel approach that makes use of gradients with respect to chart representations in predicting the parse, in analogy with the CKY algorithm being a subgradient of a partition function variant with respect to the chart.
Defending against Insertion-based Textual Backdoor Attacks via Attribution
Venue: arXiv cs.CL 2023
Year: 2023

Textual backdoor attack, as a novel attack model, has been shown to be effective in adding a backdoor to the model during training. Defending against such backdoor attacks has become urgent and important. In this paper, we propose AttDef, an efficient attribution-based pipeline to defend against two insertion-based poisoning attacks, BadNL and InSent. Specifically, we regard the tokens with larger attribution scores as potential triggers since larger attribution words contribute more to the false prediction results and therefore are more likely to be poison triggers. Additionally, we further utilize an external pre-trained language model to distinguish whether input is poisoned or not. We show that our proposed method can generalize sufficiently well in two common attack scenarios (poisoning training data and testing data), which consistently improves previous methods. For instance, AttDef can successfully mitigate both attacks with an average accuracy of 79.97% (56.59% up) and 48.34% (3.99% up) under pre-training and post-training attack defense respectively, achieving the new state-of-the-art performance on prediction recovery over four benchmark datasets.
Backdoor Learning on Sequence to Sequence Models
Venue: arXiv cs.CL 2023
Year: 2023

Backdoor learning has become an emerging research area towards building a trustworthy machine learning system. While a lot of works have studied the hidden danger of backdoor attacks in image or text classification, there is a limited understanding of the model's robustness on backdoor attacks when the output space is infinite and discrete. In this paper, we study a much more challenging problem of testing whether sequence-to-sequence (seq2seq) models are vulnerable to backdoor attacks. Specifically, we find by only injecting 0.2\% samples of the dataset, we can cause the seq2seq model to generate the designated keyword and even the whole sentence. Furthermore, we utilize Byte Pair Encoding (BPE) to create multiple new triggers, which brings new challenges to backdoor detection since these backdoors are not static. Extensive experiments on machine translation and text summarization have been conducted to show our proposed methods could achieve over 90\% attack success rate on multiple datasets and models.