OpenRaiser/Intern-Atlas huggingface dataset:
Counting Reward Automata: Sample Efficient Reinforcement Learning Through the Exploitation of Reward Function Structure
Venue: arXiv cs.AI 2024
Year: 2024

We present counting reward automata-a finite state machine variant capable of modelling any reward function expressible as a formal language. Unlike previous approaches, which are limited to the expression of tasks as regular languages, our framework allows for tasks described by unrestricted grammars. We prove that an agent equipped with such an abstract machine is able to solve a larger set of tasks than those utilising current approaches. We show that this increase in expressive power does not come at the cost of increased automaton complexity. A selection of learning algorithms are presented which exploit automaton structure to improve sample efficiency. We show that the state machines required in our formulation can be specified from natural language task descriptions using large language models. Empirical results demonstrate that our method outperforms competing approaches in terms of sample efficiency, automaton complexity, and task completion.
An Algebraic Approach to the Longest Path Problem
Venue: arXiv cs.DS 2024
Year: 2024

The Longest Path Problem is a question of finding the maximum length between pairs of vertices of a graph. In the general case, the problem is NP-complete. However, there is a small collection of graph classes for which there exists an efficient solution. Current approaches involve either approximation or computational enumeration. For Tree-like classes of graphs, there are approximation and enumeration algorithms which solves the problem efficiently. Despite this, we propose a new method of approaching the longest path problem with exact algebraic solutions that give rise to polynomial-time algorithms. Our method provides algorithms that are proven correct by their underlying algebraic operations unlike existing purely algorithmic solutions to this problem. We introduce a `booleanize' mapping on the adjacency matrix of a graph which we prove identifies the solution for trees, uniform block graphs, block graphs, and directed acyclic graphs with exact conditions and associated polynomial-time algorithms. In addition, we display additional algorithms that can generate every possible longest path of acyclic graphs in efficient time, as well as for block graphs.
Preference and Concurrence Aware Bayesian Graph Neural Networks for Recommender Systems
Venue: arXiv cs.IR 2024
Year: 2024

Graph-based collaborative filtering methods have prevailing performance for recommender systems since they can capture high-order information between users and items, in which the graphs are constructed from the observed user-item interactions that might miss links or contain spurious positive interactions in industrial scenarios. The Bayesian Graph Neural Network framework approaches this issue with generative models for the interaction graphs. The critical problem is to devise a proper family of graph generative models tailored to recommender systems. We propose an efficient generative model that jointly considers the preferences of users, the concurrence of items and some important graph structure information. Experiments on four popular benchmark datasets demonstrate the effectiveness of our proposed graph generative methods for recommender systems.
Labrador: Exploring the Limits of Masked Language Modeling for Laboratory Data
Venue: arXiv cs.CL 2024
Year: 2024

In this work we introduce Labrador, a pre-trained Transformer model for laboratory data. Labrador and BERT were pre-trained on a corpus of 100 million lab test results from electronic health records (EHRs) and evaluated on various downstream outcome prediction tasks. Both models demonstrate mastery of the pre-training task but neither consistently outperform XGBoost on downstream supervised tasks. Our ablation studies reveal that transfer learning shows limited effectiveness for BERT and achieves marginal success with Labrador. We explore the reasons for the failure of transfer learning and suggest that the data generating process underlying each patient cannot be characterized sufficiently using labs alone, among other factors. We encourage future work to focus on joint modeling of multiple EHR data categories and to include tree-based baselines in their evaluations.
ComplexityNet: Increasing LLM Inference Efficiency by Learning Task Complexity
Venue: arXiv cs.CL 2024
Year: 2024

We present ComplexityNet, a streamlined language model designed for assessing task complexity. This model predicts the likelihood of accurate output by various language models, each with different capabilities. Our initial application of ComplexityNet involves the Mostly Basic Python Problems (MBPP) dataset. We pioneered the creation of the first set of labels to define task complexity. ComplexityNet achieved a notable 79% accuracy in determining task complexity, a significant improvement over the 34% accuracy of the original, non fine-tuned model. Furthermore, ComplexityNet effectively reduces computational resource usage by 90% compared to using the highest complexity model, while maintaining a high code generation accuracy of 86.7%. This study demonstrates that fine-tuning smaller models to categorize tasks based on their complexity can lead to a more balanced trade-off between accuracy and efficiency in the use of Large Language Models. Our findings suggest a promising direction for optimizing LLM applications, especially in resource-constrained environments.
Emotion Based Prediction in the Context of Optimized Trajectory Planning for Immersive Learning
Venue: arXiv cs.HC 2024
Year: 2024

In the virtual elements of immersive learning, the use of Google Expedition and touch-screen-based emotion are examined. The objective is to investigate possible ways to combine these technologies to enhance virtual learning environments and learners emotional engagement. Pedagogical application, affordances, and cognitive load are the corresponding measures that are involved. Students will gain insight into the reason behind their significantly higher post-assessment Prediction Systems scores compared to preassessment scores through this work that leverages technology. This suggests that it is effective to include emotional elements in immersive learning scenarios. The results of this study may help develop new strategies by leveraging the features of immersive learning technology in educational technologies to improve virtual reality and augmented reality experiences. Furthermore, the effectiveness of immersive learning environments can be raised by utilizing magnetic, optical, or hybrid trackers that considerably improve object tracking.
Evaluating Language-Model Agents on Realistic Autonomous Tasks
Venue: arXiv cs.CL 2024
Year: 2024

In this report, we explore the ability of language model agents to acquire resources, create copies of themselves, and adapt to novel challenges they encounter in the wild. We refer to this cluster of capabilities as "autonomous replication and adaptation" or ARA. We believe that systems capable of ARA could have wide-reaching and hard-to-anticipate consequences, and that measuring and forecasting ARA may be useful for informing measures around security, monitoring, and alignment. Additionally, once a system is capable of ARA, placing bounds on a system's capabilities may become significantly more difficult. We construct four simple example agents that combine language models with tools that allow them to take actions in the world. We then evaluate these agents on 12 tasks relevant to ARA. We find that these language model agents can only complete the easiest tasks from this list, although they make some progress on the more challenging tasks. Unfortunately, these evaluations are not adequate to rule out the possibility that near-future agents will be capable of ARA. In particular, we do not think that these evaluations provide good assurance that the ``next generation'' of language models (e.g. 100x effective compute scaleup on existing models) will not yield agents capable of ARA, unless intermediate evaluations are performed during pretraining. Relatedly, we expect that fine-tuning of the existing models could produce substantially more competent agents, even if the fine-tuning is not directly targeted at ARA.
Assessing Logical Reasoning Capabilities of Encoder-Only Transformer Models
Venue: arXiv cs.CL 2024
Year: 2024

Logical reasoning is central to complex human activities, such as thinking, debating, and planning; it is also a central component of many AI systems as well. In this paper, we investigate the extent to which encoder-only transformer language models (LMs) can reason according to logical rules. We ask whether those LMs can deduce theorems in propositional calculus and first-order logic; if their relative success in these problems reflects general logical capabilities; and which layers contribute the most to the task. First, we show for several encoder-only LMs that they can be trained, to a reasonable degree, to determine logical validity on various datasets. Next, by cross-probing fine-tuned models on these datasets, we show that LMs have difficulty in transferring their putative logical reasoning ability, which suggests that they may have learned dataset-specific features, instead of a general capability. Finally, we conduct a layerwise probing experiment, which shows that the hypothesis classification task is mostly solved through higher layers.
Can IKEA effect promote empathy for agents?
Venue: arXiv cs.HC 2024
Year: 2024

Cooperative relationships between humans and agents are becoming more important for the social coexistence of anthropomorphic agents, including virtual agents and robots. One way to improve the relationship between humans and agents is for humans to empathize with the agents. Empathy can help humans become more accepting of agents. In this study, we focus on the IKEA effect in creating agents and investigate human empathy toward agents through relationships with others in the same space. For this reason, this study used a robot assembly task in which two participants cooperatively build the same robot or individually their own robot. We conducted experiments to examine the relationship between participants, the IKEA effect in creating an agent, and the influence of the empathy object on human empathy. The results showed that the IKEA effect promoted empathy toward the agent regardless of the relationship between participants. On the other hand, there was no significant difference in empathy from one participant to another before and after the task. These results indicate that regardless of the relationship between participants in the same space, the creation of an agent can promote empathy toward the agent.
Multi-agent reinforcement learning using echo-state network and its application to pedestrian dynamics
Venue: arXiv cs.MA 2024
Year: 2024

In recent years, simulations of pedestrians using the multi-agent reinforcement learning (MARL) have been studied. This study considered the roads on a grid-world environment, and implemented pedestrians as MARL agents using an echo-state network and the least squares policy iteration method. Under this environment, the ability of these agents to learn to move forward by avoiding other agents was investigated. Specifically, we considered two types of tasks: the choice between a narrow direct route and a broad detour, and the bidirectional pedestrian flow in a corridor. The simulations results indicated that the learning was successful when the density of the agents was not that high.
Adaptive Tracking and Perching for Quadrotor in Dynamic Scenarios
Venue: arXiv cs.RO 2024
Year: 2024

Perching on the moving platforms is a promising solution to enhance the endurance and operational range of quadrotors, which could benefit the efficiency of a variety of air-ground cooperative tasks. To ensure robust perching, tracking with a steady relative state and reliable perception is a prerequisite. This paper presents an adaptive dynamic tracking and perching scheme for autonomous quadrotors to achieve tight integration with moving platforms. For reliable perception of dynamic targets, we introduce elastic visibility-aware planning to actively avoid occlusion and target loss. Additionally, we propose a flexible terminal adjustment method that adapts the changes in flight duration and the coupled terminal states, ensuring full-state synchronization with the time-varying perching surface at various angles. A relaxation strategy is developed by optimizing the tangential relative speed to address the dynamics and safety violations brought by hard boundary conditions. Moreover, we take SE(3) motion planning into account to ensure no collision between the quadrotor and the platform until the contact moment. Furthermore, we propose an efficient spatiotemporal trajectory optimization framework considering full state dynamics for tracking and perching. The proposed method is extensively tested through benchmark comparisons and ablation studies. To facilitate the application of academic research to industry and to validate the efficiency of our scheme under strictly limited computational resources, we deploy our system on a commercial drone (DJI-MAVIC3) with a full-size sport-utility vehicle (SUV). We conduct extensive real-world experiments, where the drone successfully tracks and perches at 30~km/h (8.3~m/s) on the top of the SUV, and at 3.5~m/s with 60° inclined into the trunk of the SUV.
Active Preference Inference using Language Models and Probabilistic Reasoning
Venue: arXiv cs.CL 2024
Year: 2024

Actively inferring user preferences, for example by asking good questions, is important for any human-facing decision-making system. Active inference allows such systems to adapt and personalize themselves to nuanced individual preferences. To enable this ability for instruction-tuned large language models (LLMs), one may prompt them to ask users questions to infer their preferences, transforming the language models into more robust, interactive systems. However, out of the box, these models are not efficient at extracting preferences: the questions they generate are not informative, requiring a high number of user interactions and impeding the usability of the downstream system. In this work, we introduce an inference-time algorithm that helps LLMs quickly infer preferences by using more informative questions. Our algorithm uses a probabilistic model whose conditional distributions are defined by prompting an LLM, and returns questions that optimize expected entropy and expected model change. Results in a simplified interactive web shopping setting with real product items show that an LLM equipped with our entropy reduction algorithm outperforms baselines with the same underlying LLM on task performance while using fewer user interactions.
Pose2Gaze: Eye-body Coordination during Daily Activities for Gaze Prediction from Full-body Poses
Venue: arXiv cs.CV 2024
Year: 2024

Human eye gaze plays a significant role in many virtual and augmented reality (VR/AR) applications, such as gaze-contingent rendering, gaze-based interaction, or eye-based activity recognition. However, prior works on gaze analysis and prediction have only explored eye-head coordination and were limited to human-object interactions. We first report a comprehensive analysis of eye-body coordination in various human-object and human-human interaction activities based on four public datasets collected in real-world (MoGaze), VR (ADT), as well as AR (GIMO and EgoBody) environments. We show that in human-object interactions, e.g. pick and place, eye gaze exhibits strong correlations with full-body motion while in human-human interactions, e.g. chat and teach, a person's gaze direction is correlated with the body orientation towards the interaction partner. Informed by these analyses we then present Pose2Gaze, a novel eye-body coordination model that uses a convolutional neural network and a spatio-temporal graph convolutional neural network to extract features from head direction and full-body poses, respectively, and then uses a convolutional neural network to predict eye gaze. We compare our method with state-of-the-art methods that predict eye gaze only from head movements and show that Pose2Gaze outperforms these baselines with an average improvement of 24.0% on MoGaze, 10.1% on ADT, 21.3% on GIMO, and 28.6% on EgoBody in mean angular error, respectively. We also show that our method significantly outperforms prior methods in the sample downstream task of eye-based activity recognition. These results underline the significant information content available in eye-body coordination during daily activities and open up a new direction for gaze prediction.
General-Purpose User Modeling with Behavioral Logs: A Snapchat Case Study
Venue: arXiv cs.HC 2024
Year: 2024

Learning general-purpose user representations based on user behavioral logs is an increasingly popular user modeling approach. It benefits from easily available, privacy-friendly yet expressive data, and does not require extensive re-tuning of the upstream user model for different downstream tasks. While this approach has shown promise in search engines and e-commerce applications, its fit for instant messaging platforms, a cornerstone of modern digital communication, remains largely uncharted. We explore this research gap using Snapchat data as a case study. Specifically, we implement a Transformer-based user model with customized training objectives and show that the model can produce high-quality user representations across a broad range of evaluation tasks, among which we introduce three new downstream tasks that concern pivotal topics in user research: user safety, engagement and churn. We also tackle the challenge of efficient extrapolation of long sequences at inference time, by applying a novel positional encoding method.
Best Arm Identification with Fixed Budget: A Large Deviation Perspective
Venue: arXiv cs.LG 2024
Year: 2024

We consider the problem of identifying the best arm in stochastic Multi-Armed Bandits (MABs) using a fixed sampling budget. Characterizing the minimal instance-specific error probability for this problem constitutes one of the important remaining open problems in MABs. When arms are selected using a static sampling strategy, the error probability decays exponentially with the number of samples at a rate that can be explicitly derived via Large Deviation techniques. Analyzing the performance of algorithms with adaptive sampling strategies is however much more challenging. In this paper, we establish a connection between the Large Deviation Principle (LDP) satisfied by the empirical proportions of arm draws and that satisfied by the empirical arm rewards. This connection holds for any adaptive algorithm, and is leveraged (i) to improve error probability upper bounds of some existing algorithms, such as the celebrated \sr (Successive Rejects) algorithm \citep{audibert2010best}, and (ii) to devise and analyze new algorithms. In particular, we present \sred (Continuous Rejects), a truly adaptive algorithm that can reject arms in {\it any} round based on the observed empirical gaps between the rewards of various arms. Applying our Large Deviation results, we prove that \sred enjoys better performance guarantees than existing algorithms, including \sr. Extensive numerical experiments confirm this observation.
Value Explicit Pretraining for Learning Transferable Representations
Venue: arXiv cs.LG 2024
Year: 2024

We propose Value Explicit Pretraining (VEP), a method that learns generalizable representations for transfer reinforcement learning. VEP enables learning of new tasks that share similar objectives as previously learned tasks, by learning an encoder for objective-conditioned representations, irrespective of appearance changes and environment dynamics. To pre-train the encoder from a sequence of observations, we use a self-supervised contrastive loss that results in learning temporally smooth representations. VEP learns to relate states across different tasks based on the Bellman return estimate that is reflective of task progress. Experiments using a realistic navigation simulator and Atari benchmark show that the pretrained encoder produced by our method outperforms current SoTA pretraining methods on the ability to generalize to unseen tasks. VEP achieves up to a 2 times improvement in rewards on Atari and visual navigation, and up to a 3 times improvement in sample efficiency. For videos of policy performance visit our https://sites.google.com/view/value-explicit-pretraining/
An integrated EOS, pore-crush, strength and damage model framework for near-field ground-shock
Venue: arXiv cs.CE 2024
Year: 2024

An integrated Equation of State (EOS) and strength/pore-crush/damage model framework is provided for modeling near to source (near-field) ground-shock response, where large deformations and pressures necessitate coupling EOS with pressure-dependent plastic yield and damage. Nonlinear pressure-dependence of strength up to high-pressures is combined with a Modified Cam-Clay-like cap-plasticity model in a way to allow degradation of strength from pore-crush damage, what we call the "Yp-Cap" model. Nonlinear hardening under compaction allows modeling the crush-out of pores in combination with a fully saturated EOS, i.e., for modeling partially saturated ground-shock response, where air-filled voids crush. Attention is given to algorithmic clarity and efficiency of the provided model, and the model is employed in example numerical simulations, including finite element simulations of underground explosions to exemplify its robustness and utility.
"It Can Relate to Real Lives": Attitudes and Expectations in Justice-Centered Data Structures & Algorithms for Non-Majors
Venue: arXiv cs.CY 2024
Year: 2024

Prior work has argued for a more justice-centered approach to postsecondary computing education by emphasizing ethics, identity, and political vision. In this experience report, we examine how postsecondary students of diverse gender and racial identities experience a justice-centered Data Structures and Algorithms designed for undergraduate non-computer science majors. Through a quantitative and qualitative analysis of two quarters of student survey data collected at the start and end of each quarter, we report on student attitudes and expectations. Across the class, we found a significant increase in the following attitudes: computing confidence and sense of belonging. While women, non-binary, and other students not identifying as men (WNB+) also increased in these areas, they still reported significantly lower confidence and sense of belonging than men at the end of the quarter. Black, Latinx, Middle Eastern and North African, Native American, and Pacific Islander (BLMNPI) students had no significant differences compared to white and Asian students. We also analyzed end-of-quarter student self-reflections on their fulfillment of expectations prior to taking the course. While the majority of students reported a positive overall sentiment about the course and many students specifically appreciated the justice-centered approach, some desired more practice with program implementation and interview preparation. We discuss implications for practice and articulate a political vision for holding both appreciation for computing ethics and a desire for professional preparation together through iterative design.