OpenRaiser/Intern-Atlas huggingface dataset:
A Stopping Game on Zero-Sum Sequences
Venue: arXiv cs.DM 2024
Year: 2024

We introduce and analyze a natural game formulated as follows. In this one-person game, the player is given a random permutation $A=(a_1,\dots, a_n)$ of a multiset $M$ of $n$ reals that sum up to $0$, where each of the $n!$ permutation sequences is equally likely. The player only knows the value of $n$ beforehand. The elements of the sequence are revealed one by one and the player can stop the game at any time. Once the process stops, say, after the $i$th element is revealed, the player collects the amount $\sum_{j=i+1}^{n} a_j$ as his/her payoff and the game is over (the payoff corresponds to the unrevealed part of the sequence). Three online algorithms are given for maximizing the expected payoff in the binary case when $M$ contains only $1$'s and $-1$'s. $\texttt{Algorithm 1}$ is slightly suboptimal, but is easier to analyze. Moreover, it can also be used when $n$ is only known with some approximation. $\texttt{Algorithm 2}$ is exactly optimal but not so easy to analyze on its own. $\texttt{Algorithm 3}$ is the simplest of all three. It turns out that the expected payoffs of the player are $Θ(\sqrt{n})$ for all three algorithms. In the end, we address the general problem and deal with an arbitrary zero-sum multiset, for which we show that our $\texttt{Algorithm 3}$ returns a payoff proportional to $\sqrt{n}$, which is worst case-optimal.
Building music with Lego bricks and Raspberry Pi
Venue: arXiv cs.HC 2024
Year: 2024

In this paper, a system to build music in an intuitive and accessible way, with Lego bricks, is presented. The system makes use of the new powerful and cheap possibilities that technology offers for making old things in a new way. The Raspberry Pi is used to control the system and run the necessary algorithms, customized Lego bricks are used for building melodies, custom electronic designs, software pieces and 3D printed parts complete the items employed. The system designed is modular, it allows creating melodies with chords and percussion or just melodies or perform as a beatbox or a melody box. The main interaction with the system is made using Lego-type building blocks. Tests have demonstrated its versatility and ease of use, as well as its usefulness in music learning for both children and adults.
Probabilistic Trust-Based Enhancement for simultaneous transmission in AOMDV Routing Protocol
Venue: arXiv cs.NI 2024
Year: 2024

This work addresses a trust-based enhancement to the Multipath Ad hoc On-Demand Distance Vector (AOMDV) routing protocol. While AODV and its multipath variant AOMDV have been fundamental in mobile ad hoc networks, they lack mechanisms to account for node reliability. A probabilistic link-trust model is proposed that incorporates factors such as past behavior, battery levels, and node coupling to distribute data optimally to reduce delay while simultaneously transmitting through multiple paths.
[Experiments \& Analysis] Hash-Based vs. Sort-Based Group-By-Aggregate: A Focused Empirical Study [Extended Version]
Venue: arXiv cs.DB 2024
Year: 2024

Group-by-aggregate (GBA) queries are integral to data analysis, allowing users to group data by specific attributes and apply aggregate functions such as sum, average, and count. Database Management Systems (DBMSs) typically execute GBA queries using either sort- or hash-based methods, each with unique advantages and trade-offs. Sort-based approaches are efficient for large datasets but become computationally expensive due to record comparisons, especially in cases with a small number of groups. In contrast, hash-based approaches offer faster performance in general but require significant memory and can suffer from hash collisions when handling large numbers of groups or uneven data distributions. This paper presents a focused empirical study comparing these two approaches, analyzing their strengths and weaknesses across varying data sizes, datasets, and group counts using Apache AsterixDB. Our findings indicate that sort-based methods excel in scenarios with large datasets or when subsequent operations benefit from sorted data, whereas hash-based methods are advantageous for smaller datasets or scenarios with fewer groupings. Our results provide insights into the scenarios where each method excels, offering practical guidance for optimizing GBA query performance.
Interface for Sparse Linear Algebra Operations
Venue: arXiv cs.MS 2024
Year: 2024

The standardization of an interface for dense linear algebra operations in the BLAS standard has enabled interoperability between different linear algebra libraries, thereby boosting the success of scientific computing, in particular in scientific HPC. Despite numerous efforts in the past, the community has not yet agreed on a standardization for sparse linear algebra operations due to numerous reasons. One is the fact that sparse linear algebra objects allow for many different storage formats, and different hardware may favor different storage formats. This makes the definition of a FORTRAN-style all-circumventing interface extremely challenging. Another reason is that opposed to dense linear algebra functionality, in sparse linear algebra, the size of the sparse data structure for the operation result is not always known prior to the information. Furthermore, as opposed to the standardization effort for dense linear algebra, we are late in the technology readiness cycle, and many production-ready software libraries using sparse linear algebra routines have implemented and committed to their own sparse BLAS interface. At the same time, there exists a demand for standardization that would improve interoperability, and sustainability, and allow for easier integration of building blocks. In an inclusive, cross-institutional effort involving numerous academic institutions, US National Labs, and industry, we spent two years designing a hardware-portable interface for basic sparse linear algebra functionality that serves the user needs and is compatible with the different interfaces currently used by different vendors. In this paper, we present a C++ API for sparse linear algebra functionality, discuss the design choices, and detail how software developers preserve a lot of freedom in terms of how to implement functionality behind this API.
Introducing Schema Inference as a Scalable SQL Function [Extended Version]
Venue: arXiv cs.DB 2024
Year: 2024

This paper introduces a novel approach to schema inference as an on-demand function integrated directly within a DBMS, targeting NoSQL databases where schema flexibility can create challenges. Unlike previous methods relying on external frameworks like Apache Spark, our solution enables schema inference as a SQL function, allowing users to infer schemas natively within the DBMS. Implemented in Apache AsterixDB, it performs schema discovery in two phases, local inference and global schema merging, leveraging internal resources for improved performance. Experiments with real world datasets show up to a two orders of magnitude performance boost over external methods, enhancing usability and scalability.
Fine-tuning Myoelectric Control through Reinforcement Learning in a Game Environment
Venue: arXiv cs.HC 2024
Year: 2024

Objective: Enhancing the reliability of myoelectric controllers that decode motor intent is a pressing challenge in the field of bionic prosthetics. State-of-the-art research has mostly focused on Supervised Learning (SL) techniques to tackle this problem. However, obtaining high-quality labeled data that accurately represents muscle activity during daily usage remains difficult. We investigate the potential of Reinforcement Learning (RL) to further improve the decoding of human motion intent by incorporating usage-based data. Methods: The starting point of our method is a SL control policy, pretrained on a static recording of electromyographic (EMG) ground truth data. We then apply RL to fine-tune the pretrained classifier with dynamic EMG data obtained during interaction with a game environment developed for this work. We conducted real-time experiments to evaluate our approach and achieved significant improvements in human-in-the-loop performance. Results: The method effectively predicts simultaneous finger movements, leading to a two-fold increase in decoding accuracy during gameplay and a 39\% improvement in a separate motion test. Conclusion: By employing RL and incorporating usage-based EMG data during fine-tuning, our method achieves significant improvements in accuracy and robustness. Significance: These results showcase the potential of RL for enhancing the reliability of myoelectric controllers, of particular importance for advanced bionic limbs. See our project page for visual demonstrations: https://sites.google.com/view/bionic-limb-rl
REVISE: Robust Probabilistic Motion Planning in a Gaussian Random Field
Venue: arXiv cs.RO 2024
Year: 2024

This paper presents Robust samplE-based coVarIance StEering (REVISE), a multi-query algorithm that generates robust belief roadmaps for dynamic systems navigating through spatially dependent disturbances modeled as a Gaussian random field. Our proposed method develops a novel robust sample-based covariance steering edge controller to safely steer a robot between state distributions, satisfying state constraints along the trajectory. Our proposed approach also incorporates an edge rewiring step into the belief roadmap construction process, which provably improves the coverage of the belief roadmap. When compared to state-of-the-art methods, REVISE improves median plan accuracy (as measured by Wasserstein distance between the actual and planned final state distribution) by 10x in multi-query planning and reduces median plan cost (as measured by the largest eigenvalue of the planned state covariance at the goal) by 2.5x in single-query planning for a 6DoF system. We will release our code at https://acl.mit.edu/REVISE/.
A Survey On Enhancing Reinforcement Learning in Complex Environments: Insights from Human and LLM Feedback
Venue: arXiv cs.LG 2024
Year: 2024

Reinforcement learning (RL) is one of the active fields in machine learning, demonstrating remarkable potential in tackling real-world challenges. Despite its promising prospects, this methodology has encountered with issues and challenges, hindering it from achieving the best performance. In particular, these approaches lack decent performance when navigating environments and solving tasks with large observation space, often resulting in sample-inefficiency and prolonged learning times. This issue, commonly referred to as the curse of dimensionality, complicates decision-making for RL agents, necessitating a careful balance between attention and decision-making. RL agents, when augmented with human or large language models' (LLMs) feedback, may exhibit resilience and adaptability, leading to enhanced performance and accelerated learning. Such feedback, conveyed through various modalities or granularities including natural language, serves as a guide for RL agents, aiding them in discerning relevant environmental cues and optimizing decision-making processes. In this survey paper, we mainly focus on problems of two-folds: firstly, we focus on humans or an LLMs assistance, investigating the ways in which these entities may collaborate with the RL agent in order to foster optimal behavior and expedite learning; secondly, we delve into the research papers dedicated to addressing the intricacies of environments characterized by large observation space.
From Prompt Engineering to Prompt Craft
Venue: arXiv cs.HC 2024
Year: 2024

This pictorial presents an ongoing research programme comprising three practice-based Design Research projects conducted through 2024, exploring the affordances of diffusion-based AI image generation systems, specifically Stable Diffusion. The research employs tangible and embodied interactions to investigate emerging qualitative aspects of generative AI, including uncertainty and materiality. Our approach leverages the flexibility and adaptability of Design Research to navigate the rapidly evolving field of generative AI. The pictorial proposes the notion of prompt craft as a productive reframing of prompt engineering. This is comprised of two contributions: (1) reflections on the notion of materiality for diffusion-based generative AI and a proposed method for a craft-like navigation of the latent space within generative AI models and (2) discussing interaction design strategies for designing user interfaces informed by these affordances. The outcomes are presented as strong concepts or intermediate knowledge, applicable to various situations and domains.
A Case Study of API Design for Interoperability and Security of the Internet of Things
Venue: arXiv cs.DC 2024
Year: 2024

Heterogeneous distributed systems, including the Internet of Things (IoT) or distributed cyber-physical systems (CPS), often suffer a lack of interoperability and security, which hinders the wider deployment of such systems. Specifically, the different levels of security requirements and the heterogeneity in terms of communication models, for instance, point-to-point vs. publish-subscribe, are the example challenges of IoT and distributed CPS consisting of heterogeneous devices and applications. In this paper, we propose a working application programming interface (API) and runtime to enhance interoperability and security while addressing the challenges that stem from the heterogeneity in the IoT and distributed CPS. In our case study, we design and implement our application programming interface (API) design approach using open-source software, and with our working implementation, we evaluate the effectiveness of our proposed approach. Our experimental results suggest that our approach can achieve both interoperability and security in the IoT and distributed CPS with a reasonably small overhead and better-managed software.
PatentEdits: Framing Patent Novelty as Textual Entailment
Venue: arXiv cs.CL 2024
Year: 2024

A patent must be deemed novel and non-obvious in order to be granted by the US Patent Office (USPTO). If it is not, a US patent examiner will cite the prior work, or prior art, that invalidates the novelty and issue a non-final rejection. Predicting what claims of the invention should change given the prior art is an essential and crucial step in securing invention rights, yet has not been studied before as a learnable task. In this work we introduce the PatentEdits dataset, which contains 105K examples of successful revisions that overcome objections to novelty. We design algorithms to label edits sentence by sentence, then establish how well these edits can be predicted with large language models (LLMs). We demonstrate that evaluating textual entailment between cited references and draft sentences is especially effective in predicting which inventive claims remained unchanged or are novel in relation to prior art.
Dynamically Feasible Path Planning in Cluttered Environments via Reachable Bezier Polytopes
Venue: arXiv cs.RO 2024
Year: 2024

The deployment of robotic systems in real world environments requires the ability to quickly produce paths through cluttered, non-convex spaces. These planned trajectories must be both kinematically feasible (i.e., collision free) and dynamically feasible (i.e., satisfy the underlying system dynamics), necessitating a consideration of both the free space and the dynamics of the robot in the path planning phase. In this work, we explore the application of reachable Bezier polytopes as an efficient tool for generating trajectories satisfying both kinematic and dynamic requirements. Furthermore, we demonstrate that by offloading specific computation tasks to the GPU, such an algorithm can meet tight real time requirements. We propose a layered control architecture that efficiently produces collision free and dynamically feasible paths for nonlinear control systems, and demonstrate the framework on the tasks of 3D hopping in a cluttered environment.
Generating 3D-Consistent Videos from Unposed Internet Photos
Venue: arXiv cs.CV 2024
Year: 2024

We address the problem of generating videos from unposed internet photos. A handful of input images serve as keyframes, and our model interpolates between them to simulate a path moving between the cameras. Given random images, a model's ability to capture underlying geometry, recognize scene identity, and relate frames in terms of camera position and orientation reflects a fundamental understanding of 3D structure and scene layout. However, existing video models such as Luma Dream Machine fail at this task. We design a self-supervised method that takes advantage of the consistency of videos and variability of multiview internet photos to train a scalable, 3D-aware video model without any 3D annotations such as camera parameters. We validate that our method outperforms all baselines in terms of geometric and appearance consistency. We also show our model benefits applications that enable camera control, such as 3D Gaussian Splatting. Our results suggest that we can scale up scene-level 3D learning using only 2D data such as videos and multiview internet photos.
Enhancing Bidirectional Sign Language Communication: Integrating YOLOv8 and NLP for Real-Time Gesture Recognition & Translation
Venue: arXiv cs.CV 2024
Year: 2024

The primary concern of this research is to take American Sign Language (ASL) data through real time camera footage and be able to convert the data and information into text. Adding to that, we are also putting focus on creating a framework that can also convert text into sign language in real time which can help us break the language barrier for the people who are in need. In this work, for recognising American Sign Language (ASL), we have used the You Only Look Once(YOLO) model and Convolutional Neural Network (CNN) model. YOLO model is run in real time and automatically extracts discriminative spatial-temporal characteristics from the raw video stream without the need for any prior knowledge, eliminating design flaws. The CNN model here is also run in real time for sign language detection. We have introduced a novel method for converting text based input to sign language by making a framework that will take a sentence as input, identify keywords from that sentence and then show a video where sign language is performed with respect to the sentence given as input in real time. To the best of our knowledge, this is a rare study to demonstrate bidirectional sign language communication in real time in the American Sign Language (ASL).
DSTC: Direct Preference Learning with Only Self-Generated Tests and Code to Improve Code LMs
Venue: arXiv cs.SE 2024
Year: 2024

Direct preference learning offers a promising and computation-efficient beyond supervised fine-tuning (SFT) for improving code generation in coding large language models (LMs). However, the scarcity of reliable preference data is a bottleneck for the performance of direct preference learning to improve the coding accuracy of code LMs. In this paper, we introduce \underline{\textbf{D}}irect Preference Learning with Only \underline{\textbf{S}}elf-Generated \underline{\textbf{T}}ests and \underline{\textbf{C}}ode (DSTC), a framework that leverages only self-generated code snippets and tests to construct reliable preference pairs such that direct preference learning can improve LM coding accuracy without external annotations. DSTC combines a minimax selection process and test-code concatenation to improve preference pair quality, reducing the influence of incorrect self-generated tests and enhancing model performance without the need for costly reward models. When applied with direct preference learning methods such as Direct Preference Optimization (DPO) and Kahneman-Tversky Optimization (KTO), DSTC yields stable improvements in coding accuracy (pass@1 score) across diverse coding benchmarks, including HumanEval, MBPP, and BigCodeBench, demonstrating both its effectiveness and scalability for models of various sizes. This approach autonomously enhances code generation accuracy across LLMs of varying sizes, reducing reliance on expensive annotated coding datasets.
CryptoFormalEval: Integrating LLMs and Formal Verification for Automated Cryptographic Protocol Vulnerability Detection
Venue: arXiv cs.CR 2024
Year: 2024

Cryptographic protocols play a fundamental role in securing modern digital infrastructure, but they are often deployed without prior formal verification. This could lead to the adoption of distributed systems vulnerable to attack vectors. Formal verification methods, on the other hand, require complex and time-consuming techniques that lack automatization. In this paper, we introduce a benchmark to assess the ability of Large Language Models (LLMs) to autonomously identify vulnerabilities in new cryptographic protocols through interaction with Tamarin: a theorem prover for protocol verification. We created a manually validated dataset of novel, flawed, communication protocols and designed a method to automatically verify the vulnerabilities found by the AI agents. Our results about the performances of the current frontier models on the benchmark provides insights about the possibility of cybersecurity applications by integrating LLMs with symbolic reasoning systems.
Sounds Good? Fast and Secure Contact Exchange in Groups
Venue: arXiv cs.HC 2024
Year: 2024

Trustworthy digital communication requires the secure exchange of contact information, but current approaches lack usability and scalability for larger groups of users. We evaluate the usability of two secure contact exchange systems: the current state of the art, SafeSlinger, and our newly designed protocol, PairSonic, which extends trust from physical encounters to spontaneous online communication. Our lab study (N=45) demonstrates PairSonic's superior usability, automating the tedious verification tasks from previous approaches via an acoustic out-of-band channel. Although participants significantly preferred our system, minimizing user effort surprisingly decreased the perceived security for some users, who associated security with complexity. We discuss user perceptions of the different protocol components and identify remaining usability barriers for CSCW application scenarios.
A Framework for Evaluating LLMs Under Task Indeterminacy
Venue: arXiv cs.LG 2024
Year: 2024

Large language model (LLM) evaluations often assume there is a single correct response -- a gold label -- for each item in the evaluation corpus. However, some tasks can be ambiguous -- i.e., they provide insufficient information to identify a unique interpretation -- or vague -- i.e., they do not clearly indicate where to draw the line when making a determination. Both ambiguity and vagueness can cause task indeterminacy -- the condition where some items in the evaluation corpus have more than one correct response. In this paper, we develop a framework for evaluating LLMs under task indeterminacy. Our framework disentangles the relationships between task specification, human ratings, and LLM responses in the LLM evaluation pipeline. Using our framework, we conduct a synthetic experiment showing that evaluations that use the "gold label" assumption underestimate the true performance. We also provide a method for estimating an error-adjusted performance interval given partial knowledge about indeterminate items in the evaluation corpus. We conclude by outlining implications of our work for the research community.