OpenRaiser/Intern-Atlas huggingface dataset:
Supervised Auto-Encoding Twin-Bottleneck Hashing
Venue: arXiv cs.LG 2023
Year: 2023

Deep hashing has shown to be a complexity-efficient solution for the Approximate Nearest Neighbor search problem in high dimensional space. Many methods usually build the loss function from pairwise or triplet data points to capture the local similarity structure. Other existing methods construct the similarity graph and consider all points simultaneously. Auto-encoding Twin-bottleneck Hashing is one such method that dynamically builds the graph. Specifically, each input data is encoded into a binary code and a continuous variable, or the so-called twin bottlenecks. The similarity graph is then computed from these binary codes, which get updated consistently during the training. In this work, we generalize the original model into a supervised deep hashing network by incorporating the label information. In addition, we examine the differences of codes structure between these two networks and consider the class imbalance problem especially in multi-labeled datasets. Experiments on three datasets yield statistically significant improvement against the original model. Results are also comparable and competitive to other supervised methods.
Insufficiently Justified Disparate Impact: A New Criterion for Subgroup Fairness
Venue: arXiv cs.LG 2023
Year: 2023

In this paper, we develop a new criterion, "insufficiently justified disparate impact" (IJDI), for assessing whether recommendations (binarized predictions) made by an algorithmic decision support tool are fair. Our novel, utility-based IJDI criterion evaluates false positive and false negative error rate imbalances, identifying statistically significant disparities between groups which are present even when adjusting for group-level differences in base rates. We describe a novel IJDI-Scan approach which can efficiently identify the intersectional subpopulations, defined across multiple observed attributes of the data, with the most significant IJDI. To evaluate IJDI-Scan's performance, we conduct experiments on both simulated and real-world data, including recidivism risk assessment and credit scoring. Further, we implement and evaluate approaches to mitigating IJDI for the detected subpopulations in these domains.
Quasipolynomiality of the Smallest Missing Induced Subgraph
Venue: arXiv cs.DS 2023
Year: 2023

We study the problem of finding the smallest graph that does not occur as an induced subgraph of a given graph. This missing induced subgraph has at most logarithmic size and can be found by a brute-force search, in an $n$-vertex graph, in time $n^{O(\log n)}$. We show that under the Exponential Time Hypothesis this quasipolynomial time bound is optimal. We also consider variations of the problem in which either the missing subgraph or the given graph comes from a restricted graph family; for instance, we prove that the smallest missing planar induced subgraph of a given planar graph can be found in polynomial time.
A Novel Counterfactual Data Augmentation Method for Aspect-Based Sentiment Analysis
Venue: arXiv cs.CL 2023
Year: 2023

Aspect-based-sentiment-analysis (ABSA) is a fine-grained sentiment evaluation task, which analyzes the emotional polarity of the evaluation aspects. Generally, the emotional polarity of an aspect exists in the corresponding opinion expression, whose diversity has great impact on model's performance. To mitigate this problem, we propose a novel and simple counterfactual data augmentation method to generate opinion expressions with reversed sentiment polarity. In particular, the integrated gradients are calculated to locate and mask the opinion expression. Then, a prompt combined with the reverse expression polarity is added to the original text, and a Pre-trained language model (PLM), T5, is finally was employed to predict the masks. The experimental results shows the proposed counterfactual data augmentation method performs better than current augmentation methods on three ABSA datasets, i.e. Laptop, Restaurant, and MAMS.
Decentralized Quantum Federated Learning for Metaverse: Analysis, Design and Implementation
Venue: arXiv cs.LG 2023
Year: 2023

With the emerging developments of the Metaverse, a virtual world where people can interact, socialize, play, and conduct their business, it has become critical to ensure that the underlying systems are transparent, secure, and trustworthy. To this end, we develop a decentralized and trustworthy quantum federated learning (QFL) framework. The proposed QFL leverages the power of blockchain to create a secure and transparent system that is robust against cyberattacks and fraud. In addition, the decentralized QFL system addresses the risks associated with a centralized server-based approach. With extensive experiments and analysis, we evaluate classical federated learning (CFL) and QFL in a distributed setting and demonstrate the practicality and benefits of the proposed design. Our theoretical analysis and discussions develop a genuinely decentralized financial system essential for the Metaverse. Furthermore, we present the application of blockchain-based QFL in a hybrid metaverse powered by a metaverse observer and world model. Our implementation details and code are publicly available 1.
Low Latency Edge Classification GNN for Particle Trajectory Tracking on FPGAs
Venue: arXiv cs.AR 2023
Year: 2023

In-time particle trajectory reconstruction in the Large Hadron Collider is challenging due to the high collision rate and numerous particle hits. Using GNN (Graph Neural Network) on FPGA has enabled superior accuracy with flexible trajectory classification. However, existing GNN architectures have inefficient resource usage and insufficient parallelism for edge classification. This paper introduces a resource-efficient GNN architecture on FPGAs for low latency particle tracking. The modular architecture facilitates design scalability to support large graphs. Leveraging the geometric properties of hit detectors further reduces graph complexity and resource usage. Our results on Xilinx UltraScale+ VU9P demonstrate 1625x and 1574x performance improvement over CPU and GPU respectively.
Evaluation of motion comfort using advanced active human body models and efficient simplified models
Venue: arXiv cs.HC 2023
Year: 2023

Active muscles are crucial for maintaining postural stability when seated in a moving vehicle. Advanced active 3D non-linear full body models have been developed for impact and comfort simulation, including large numbers of individual muscle elements, and detailed non-linear models of the joint structures. While such models have an apparent potential to provide insight into postural stabilization, they are computationally demanding, making them less practical in particular for driving comfort where long time periods are to be studied. In vibrational comfort and in general biomechanical research, linearized models are effectively used. This paper evaluates the effectiveness of simplified 3D full-body human models to capture comfort provoked by whole-body vibrations. An efficient seated human body model is developed and validated using experimental data. We evaluate the required complexity in terms of joints and degrees of freedom for the spine, and explore how well linear spring-damper models can approximate reflexive postural stabilization. Results indicate that linear stiffness and damping models can well capture the human response. The results are improved by adding proportional integral derivative (PID) and head-in-space (HIS) controllers to maintain the defined initial body posture. The integrator is shown to be essential to prevent drift from the defined posture. The joint angular relative displacement is used as the input reference to each PID controller. With this model, a faster than real-time solution is obtained when used with a simple seat model. The paper also discusses the advantages and disadvantages of various models and provides insight into which models are more appropriate for motion comfort analysis.
Size Matters: Large Graph Generation with HiGGs
Venue: arXiv cs.LG 2023
Year: 2023

Large graphs are present in a variety of domains, including social networks, civil infrastructure, and the physical sciences to name a few. Graph generation is similarly widespread, with applications in drug discovery, network analysis and synthetic datasets among others. While GNN (Graph Neural Network) models have been applied in these domains their high in-memory costs restrict them to small graphs. Conversely less costly rule-based methods struggle to reproduce complex structures. We propose HIGGS (Hierarchical Generation of Graphs) as a model-agnostic framework of producing large graphs with realistic local structures. HIGGS uses GNN models with conditional generation capabilities to sample graphs in hierarchies of resolution. As a result HIGGS has the capacity to extend the scale of generated graphs from a given GNN model by quadratic order. As a demonstration we implement HIGGS using DiGress, a recent graph-diffusion model, including a novel edge-predictive-diffusion variant edge-DiGress. We use this implementation to generate categorically attributed graphs with tens of thousands of nodes. These HIGGS generated graphs are far larger than any previously produced using GNNs. Despite this jump in scale we demonstrate that the graphs produced by HIGGS are, on the local scale, more realistic than those from the rule-based model BTER.
CATS: A Pragmatic Chinese Answer-to-Sequence Dataset with Large Scale and High Quality
Venue: arXiv cs.CL 2023
Year: 2023

There are three problems existing in the popular data-to-text datasets. First, the large-scale datasets either contain noise or lack real application scenarios. Second, the datasets close to real applications are relatively small in size. Last, current datasets bias in the English language while leaving other languages underexplored. To alleviate these limitations, in this paper, we present CATS, a pragmatic Chinese answer-to-sequence dataset with large scale and high quality. The dataset aims to generate textual descriptions for the answer in the practical TableQA system. Further, to bridge the structural gap between the input SQL and table and establish better semantic alignments, we propose a Unified Graph Transformation approach to establish a joint encoding space for the two hybrid knowledge resources and convert this task to a graph-to-text problem. The experiment results demonstrate the effectiveness of our proposed method. Further analysis on CATS attests to both the high quality and challenges of the dataset.
Int-HRL: Towards Intention-based Hierarchical Reinforcement Learning
Venue: arXiv cs.LG 2023
Year: 2023

While deep reinforcement learning (RL) agents outperform humans on an increasing number of tasks, training them requires data equivalent to decades of human gameplay. Recent hierarchical RL methods have increased sample efficiency by incorporating information inherent to the structure of the decision problem but at the cost of having to discover or use human-annotated sub-goals that guide the learning process. We show that intentions of human players, i.e. the precursor of goal-oriented decisions, can be robustly predicted from eye gaze even for the long-horizon sparse rewards task of Montezuma's Revenge - one of the most challenging RL tasks in the Atari2600 game suite. We propose Int-HRL: Hierarchical RL with intention-based sub-goals that are inferred from human eye gaze. Our novel sub-goal extraction pipeline is fully automatic and replaces the need for manual sub-goal annotation by human experts. Our evaluations show that replacing hand-crafted sub-goals with automatically extracted intentions leads to a HRL agent that is significantly more sample efficient than previous methods.
Software Engineers' Questions and Answers on Stack Exchange
Venue: arXiv cs.SE 2023
Year: 2023

There exists a large number of research works analyzing questions and answers on the popular Stack Overflow website. However, other sub-sites of the Stack Exchange platform are studied rarely. In this paper, we analyze the questions and answers on the Software Engineering Stack Exchange site that encompasses a broader set of areas, such as testing or software processes. Topics and quantities of the questions, historical trends, and the authors' sentiment were analyzed using downloaded datasets. We found that the asked questions are most frequently related to database systems, quality assurance, and agile software development. The most attractive topics were career and teamwork problems, and the least attractive ones were network programming and software modeling. Historically, the topic of domain-driven design recorded the highest rise, and jobs and career the most significant fall. The number of new questions dropped, while the portion of unanswered ones increased.
FAIR: A Causal Framework for Accurately Inferring Judgments Reversals
Venue: arXiv cs.CL 2023
Year: 2023

Artificial intelligence researchers have made significant advances in legal intelligence in recent years. However, the existing studies have not focused on the important value embedded in judgments reversals, which limits the improvement of the efficiency of legal intelligence. In this paper, we propose a causal Framework for Accurately Inferring case Reversals (FAIR), which models the problem of judgments reversals based on real Chinese judgments. We mine the causes of judgments reversals by causal inference methods and inject the obtained causal relationships into the neural network as a priori knowledge. And then, our framework is validated on a challenging dataset as a legal judgment prediction task. The experimental results show that our framework can tap the most critical factors in judgments reversal, and the obtained causal relationships can effectively improve the neural network's performance. In addition, we discuss the generalization ability of large language models for legal intelligence tasks using ChatGPT as an example. Our experiment has found that the generalization ability of large language models still has defects, and mining causal relationships can effectively improve the accuracy and explain ability of model predictions.
Composition of nested embeddings with an application to outlier removal
Venue: arXiv cs.DS 2023
Year: 2023

We study the design of embeddings into Euclidean space with outliers. Given a metric space $(X,d)$ and an integer $k$, the goal is to embed all but $k$ points in $X$ (called the ``outliers") into $\ell_2$ with the smallest possible distortion $c$. Finding the optimal distortion $c$ for a given outlier set size $k$, or alternately the smallest $k$ for a given target distortion $c$ are both NP-hard problems. In fact, it is UGC-hard to approximate $k$ to within a factor smaller than $2$ even when the metric sans outliers is isometrically embeddable into $\ell_2$. We consider bi-criteria approximations. Our main result is a polynomial time algorithm that approximates the outlier set size to within an $O(\log^2 k)$ factor and the distortion to within a constant factor. The main technical component in our result is an approach for constructing Lipschitz extensions of embeddings into Banach spaces (such as $\ell_p$ spaces). We consider a stronger version of Lipschitz extension that we call a \textit{nested composition of embeddings}: given a low distortion embedding of a subset $S$ of the metric space $X$, our goal is to extend this embedding to all of $X$ such that the distortion over $S$ is preserved, whereas the distortion over the remaining pairs of points in $X$ is bounded by a function of the size of $X\setminus S$. Prior work on Lipschitz extension considers settings where the size of $X$ is potentially much larger than that of $S$ and the expansion bounds depend on $|S|$. In our setting, the set $S$ is nearly all of $X$ and the remaining set $X\setminus S$, a.k.a. the outliers, is small. We achieve an expansion bound that is logarithmic in $|X\setminus S|$.
Collision Avoidance Detour for Multi-Agent Trajectory Forecasting
Venue: arXiv cs.CV 2023
Year: 2023

We present our approach, Collision Avoidance Detour (CAD), which won the 3rd place award in the 2023 Waymo Open Dataset Challenge - Sim Agents, held at the 2023 CVPR Workshop on Autonomous Driving. To satisfy the motion prediction factorization requirement, we partition all the valid objects into three mutually exclusive sets: Autonomous Driving Vehicle (ADV), World-tracks-to-predict, and World-others. We use different motion models to forecast their future trajectories independently. Furthermore, we also apply collision avoidance detour resampling, additive Gaussian noise, and velocity-based heading estimation to improve the realism of our simulation result.
SALSA VERDE: a machine learning attack on Learning With Errors with sparse small secrets
Venue: arXiv cs.CR 2023
Year: 2023

Learning with Errors (LWE) is a hard math problem used in post-quantum cryptography. Homomorphic Encryption (HE) schemes rely on the hardness of the LWE problem for their security, and two LWE-based cryptosystems were recently standardized by NIST for digital signatures and key exchange (KEM). Thus, it is critical to continue assessing the security of LWE and specific parameter choices. For example, HE uses secrets with small entries, and the HE community has considered standardizing small sparse secrets to improve efficiency and functionality. However, prior work, SALSA and PICANTE, showed that ML attacks can recover sparse binary secrets. Building on these, we propose VERDE, an improved ML attack that can recover sparse binary, ternary, and narrow Gaussian secrets. Using improved preprocessing and secret recovery techniques, VERDE can attack LWE with larger dimensions ($n=512$) and smaller moduli ($\log_2 q=12$ for $n=256$), using less time and power. We propose novel architectures for scaling. Finally, we develop a theory that explains the success of ML LWE attacks.
Safe and Scalable Real-Time Trajectory Planning Framework for Urban Air Mobility
Venue: arXiv cs.RO 2023
Year: 2023

This paper presents a real-time trajectory planning framework for Urban Air Mobility (UAM) that is both safe and scalable. The proposed framework employs a decentralized, free-flight concept of operation in which each aircraft independently performs separation assurance and conflict resolution, generating safe trajectories by accounting for the future states of nearby aircraft. The framework consists of two main components: a data-driven reachability analysis tool and an efficient Markov Decision Process (MDP) based decision maker. The reachability analysis over-approximates the reachable set of each aircraft through a discrepancy function learned online from simulated trajectories. The decision maker, on the other hand, uses a 6-degrees-of-freedom guidance model of fixed-wing aircraft to ensure collision-free trajectory planning. Additionally, the proposed framework incorporates reward shaping and action shielding techniques to enhance safety performance. The proposed framework is evaluated through simulation experiments involving up to 32 aircraft in a UAM setting, with performance measured by the number of Near Mid Air Collisions (NMAC) and computational time. The results demonstrate the safety and scalability of the proposed framework.
The Implicit Bias of Batch Normalization in Linear Models and Two-layer Linear Convolutional Neural Networks
Venue: arXiv cs.LG 2023
Year: 2023

We study the implicit bias of batch normalization trained by gradient descent. We show that when learning a linear model with batch normalization for binary classification, gradient descent converges to a uniform margin classifier on the training data with an $\exp(-Ω(\log^2 t))$ convergence rate. This distinguishes linear models with batch normalization from those without batch normalization in terms of both the type of implicit bias and the convergence rate. We further extend our result to a class of two-layer, single-filter linear convolutional neural networks, and show that batch normalization has an implicit bias towards a patch-wise uniform margin. Based on two examples, we demonstrate that patch-wise uniform margin classifiers can outperform the maximum margin classifiers in certain learning problems. Our results contribute to a better theoretical understanding of batch normalization.
MoleCLUEs: Molecular Conformers Maximally In-Distribution for Predictive Models
Venue: arXiv cs.LG 2023
Year: 2023

Structure-based molecular ML (SBML) models can be highly sensitive to input geometries and give predictions with large variance. We present an approach to mitigate the challenge of selecting conformations for such models by generating conformers that explicitly minimize predictive uncertainty. To achieve this, we compute estimates of aleatoric and epistemic uncertainties that are differentiable w.r.t. latent posteriors. We then iteratively sample new latents in the direction of lower uncertainty by gradient descent. As we train our predictive models jointly with a conformer decoder, the new latent embeddings can be mapped to their corresponding inputs, which we call \textit{MoleCLUEs}, or (molecular) counterfactual latent uncertainty explanations \citep{antoran2020getting}. We assess our algorithm for the task of predicting drug properties from 3D structure with maximum confidence. We additionally analyze the structure trajectories obtained from conformer optimizations, which provide insight into the sources of uncertainty in SBML.
Lingua Manga: A Generic Large Language Model Centric System for Data Curation
Venue: arXiv cs.DB 2023
Year: 2023

Data curation is a wide-ranging area which contains many critical but time-consuming data processing tasks. However, the diversity of such tasks makes it challenging to develop a general-purpose data curation system. To address this issue, we present Lingua Manga, a user-friendly and versatile system that utilizes pre-trained large language models. Lingua Manga offers automatic optimization for achieving high performance and label efficiency while facilitating flexible and rapid development. Through three example applications with distinct objectives and users of varying levels of technical proficiency, we demonstrate that Lingua Manga can effectively assist both skilled programmers and low-code or even no-code users in addressing data curation challenges.
Automated Grading and Feedback Tools for Programming Education: A Systematic Review
Venue: arXiv cs.SE 2023
Year: 2023

We conducted a systematic literature review on automated grading and feedback tools for programming education. We analysed 121 research papers from 2017 to 2021 inclusive and categorised them based on skills assessed, approach, language paradigm, degree of automation and evaluation techniques. Most papers assess the correctness of assignments in object-oriented languages. Typically, these tools use a dynamic technique, primarily unit testing, to provide grades and feedback to the students or static analysis techniques to compare a submission with a reference solution or with a set of correct student submissions. However, these techniques' feedback is often limited to whether the unit tests have passed or failed, the expected and actual output, or how they differ from the reference solution. Furthermore, few tools assess the maintainability, readability or documentation of the source code, with most using static analysis techniques, such as code quality metrics, in conjunction with grading correctness. Additionally, we found that most tools offered fully automated assessment to allow for near-instantaneous feedback and multiple resubmissions, which can increase student satisfaction and provide them with more opportunities to succeed. In terms of techniques used to evaluate the tools' performance, most papers primarily use student surveys or compare the automatic assessment tools to grades or feedback provided by human graders. However, because the evaluation dataset is frequently unavailable, it is more difficult to reproduce results and compare tools to a collection of common assignments.