OpenRaiser/Intern-Atlas huggingface dataset:
WindTunnel -- A Framework for Community Aware Sampling of Large Corpora
Venue: arXiv cs.IR 2024
Year: 2024

Conducting comprehensive information retrieval experiments, such as in search or retrieval augmented generation, often comes with high computational costs. This is because evaluating a retrieval algorithm requires indexing the entire corpus, which is significantly larger than the set of (query, result) pairs under evaluation. This issue is especially pronounced in big data and neural retrieval, where indexing becomes increasingly time-consuming and complex. In this paper, we present WindTunnel, a novel framework developed at Yext to generate representative samples of large corpora, enabling efficient end-to-end information retrieval experiments. By preserving the community structure of the dataset, WindTunnel overcomes limitations in current sampling methods, providing more accurate evaluations.
A New Non-Binary Response Generation Scheme from Physical Unclonable Functions
Venue: arXiv cs.CR 2024
Year: 2024

Physical Unclonable Functions (PUFs) are widely used in key generation, with each PUF cell typically producing one bit of data. To enable the extraction of longer keys, a new non-binary response generation scheme based on the one-probability of PUF bits is proposed. Instead of using PUF bits directly as keys, non-binary responses are first derived by comparing the one-frequency of PUF bits with thresholds that evenly divide the area under the probability density function of the one-probability distribution and then converted to binary keys. To simplify the calculation of these thresholds, a re-scaling process is proposed and the beta distribution is used to model the one-probability distribution. Our FPGA implementation results demonstrate a significant increase in effective key length as opposed to previous works. Finally, we estimate the error rates and biases of the generated keys, and confirm the feasibility of the proposed key generation scheme.
Get Large Language Models Ready to Speak: A Late-fusion Approach for Speech Generation
Venue: arXiv cs.CL 2024
Year: 2024

Large language models (LLMs) have revolutionized natural language processing (NLP) with impressive performance across various text-based tasks. However, the extension of text-dominant LLMs to with speech generation tasks remains under-explored. In this work, we introduce a text-to-speech (TTS) system powered by a fine-tuned Llama model, named TTS-Llama, that achieves state-of-the-art speech synthesis performance. Building on TTS-Llama, we further propose MoLE-Llama, a text-and-speech multimodal LLM developed through purely late-fusion parameter-efficient fine-tuning (PEFT) and a mixture-of-expert architecture. Extensive empirical results demonstrate MoLE-Llama's competitive performance on both text-only question-answering (QA) and TTS tasks, mitigating catastrophic forgetting issue in either modality. Finally, we further explore MoLE-Llama in text-in-speech-out QA tasks, demonstrating its great potential as a multimodal dialog system capable of speech generation.
On the I/O Complexity of the CYK Algorithm and of a Family of Related DP Algorithms
Venue: arXiv cs.DS 2024
Year: 2024

Asymptotically tight lower bounds are derived for the Input/Output (I/O) complexity of a class of dynamic programming algorithms including matrix chain multiplication, optimal polygon triangulation, and the construction of optimal binary search trees. Assuming no recomputation of intermediate values, we establish an $Ω\left(\frac{n^3}{\sqrt{M}B}\right)$ I/O lower bound, where $n$ denotes the size of the input and $M$ denotes the size of the available fast memory (cache). When recomputation is allowed, we show the same bound holds for $M < cn$, where $c$ is a positive constant. In the case where $M \ge 2n$, we show an $Ω\left(n/B\right)$ I/O lower bound. We also discuss algorithms for which the number of executed I/O operations matches asymptotically each of the presented lower bounds, which are thus asymptotically tight. Additionally, we refine our general method to obtain a lower bound for the I/O complexity of the Cocke-Younger-Kasami algorithm, where the size of the grammar impacts the I/O complexity. An upper bound with asymptotically matching performance in many cases is also provided.
Leveraging Auxiliary Task Relevance for Enhanced Bearing Fault Diagnosis through Curriculum Meta-learning
Venue: arXiv cs.LG 2024
Year: 2024

The accurate diagnosis of machine breakdowns is crucial for maintaining operational safety in smart manufacturing. Despite the promise shown by deep learning in automating fault identification, the scarcity of labeled training data, particularly for equipment failure instances, poses a significant challenge. This limitation hampers the development of robust classification models. Existing methods like model-agnostic meta-learning (MAML) do not adequately address variable working conditions, affecting knowledge transfer. To address these challenges, a Related Task Aware Curriculum Meta-learning (RT-ACM) enhanced fault diagnosis framework is proposed in this paper, inspired by human cognitive learning processes. RT-ACM improves training by considering the relevance of auxiliary sensor working conditions, adhering to the principle of ``paying more attention to more relevant knowledge", and focusing on ``easier first, harder later" curriculum sampling. This approach aids the meta-learner in achieving a superior convergence state. Extensive experiments on two real-world datasets demonstrate the superiority of RT-ACM framework.
Distributed Complexity of $P_k$-freeness: Decision and Certification
Venue: arXiv cs.DC 2024
Year: 2024

The class of graphs that do not contain a path on $k$ nodes as an induced subgraph ($P_k$-free graphs) has rich applications in the theory of graph algorithms. This paper explores the problem of deciding $P_k$-freeness from the viewpoint of distributed computing. For specific small values of $k$, we present the \textit{first} $\mathsf{CONGEST}$ algorithms specified for $P_k$-freeness, utilizing structural properties of $P_k$-free graphs in a novel way. Specifically, we show that $P_k$-freeness can be decided in $\tilde{O}(1)$ rounds for $k=4$ in the $\mathsf{broadcast\;CONGEST}$ model, and in $\tilde{O}(n)$ rounds for $k=5$ in the $\mathsf{CONGEST}$ model, where $n$ is the number of nodes in the network and $\tilde{O}(\cdot)$ hides a $\mathrm{polylog}(n)$ factor. These results significantly improve the previous $O(n^{2-2/(3k+2)})$ upper bounds by Eden et al. (Dist.~Comp.~2022). We also construct a local certification of $P_5$-freeness with certificates of size $\tilde{O}(n)$. This is nearly optimal, given our $Ω(n^{1-o(1)})$ lower bound on certificate size, and marks a significant advancement as no nontrivial bounds for proof-labeling schemes of $P_5$-freeness were previously known. For general $k$, we establish the first $\mathsf{CONGEST}$ lower bound, which is of the form $n^{2-1/Θ(k)}$. The $n^{1/Θ(k)}$ factor is unavoidable, in view of the $O(n^{2-2/(3k+2)})$ upper bound mentioned above. Additionally, our approach yields the \textit{first} superlinear lower bound on certificate size for local certification. This partially answers the conjecture on the optimal certificate size of $P_k$-freeness, asked by Bousquet et al. (arXiv:2402.12148). Finally, we propose a novel variant of the problem called ordered $P_k$ detection, and show a linear lower bound and its nontrivial connection to distributed subgraph detection.
RopeTP: Global Human Motion Recovery via Integrating Robust Pose Estimation with Diffusion Trajectory Prior
Venue: arXiv cs.CV 2024
Year: 2024

We present RopeTP, a novel framework that combines Robust pose estimation with a diffusion Trajectory Prior to reconstruct global human motion from videos. At the heart of RopeTP is a hierarchical attention mechanism that significantly improves context awareness, which is essential for accurately inferring the posture of occluded body parts. This is achieved by exploiting the relationships with visible anatomical structures, enhancing the accuracy of local pose estimations. The improved robustness of these local estimations allows for the reconstruction of precise and stable global trajectories. Additionally, RopeTP incorporates a diffusion trajectory model that predicts realistic human motion from local pose sequences. This model ensures that the generated trajectories are not only consistent with observed local actions but also unfold naturally over time, thereby improving the realism and stability of 3D human motion reconstruction. Extensive experimental validation shows that RopeTP surpasses current methods on two benchmark datasets, particularly excelling in scenarios with occlusions. It also outperforms methods that rely on SLAM for initial camera estimates and extensive optimization, delivering more accurate and realistic trajectories.
Conditional GAN for Enhancing Diffusion Models in Efficient and Authentic Global Gesture Generation from Audios
Venue: arXiv cs.SD 2024
Year: 2024

Audio-driven simultaneous gesture generation is vital for human-computer communication, AI games, and film production. While previous research has shown promise, there are still limitations. Methods based on VAEs are accompanied by issues of local jitter and global instability, whereas methods based on diffusion models are hampered by low generation efficiency. This is because the denoising process of DDPM in the latter relies on the assumption that the noise added at each step is sampled from a unimodal distribution, and the noise values are small. DDIM borrows the idea from the Euler method for solving differential equations, disrupts the Markov chain process, and increases the noise step size to reduce the number of denoising steps, thereby accelerating generation. However, simply increasing the step size during the step-by-step denoising process causes the results to gradually deviate from the original data distribution, leading to a significant drop in the quality of the generated actions and the emergence of unnatural artifacts. In this paper, we break the assumptions of DDPM and achieves breakthrough progress in denoising speed and fidelity. Specifically, we introduce a conditional GAN to capture audio control signals and implicitly match the multimodal denoising distribution between the diffusion and denoising steps within the same sampling step, aiming to sample larger noise values and apply fewer denoising steps for high-speed generation.
YourSkatingCoach: A Figure Skating Video Benchmark for Fine-Grained Element Analysis
Venue: arXiv cs.CV 2024
Year: 2024

Combining sports and machine learning involves leveraging ML algorithms and techniques to extract insight from sports-related data such as player statistics, game footage, and other relevant information. However, datasets related to figure skating in the literature focus primarily on element classification and are currently unavailable or exhibit only limited access, which greatly raise the entry barrier to developing visual sports technology for it. Moreover, when using such data to help athletes improve their skills, we find they are very coarse-grained: they work for learning what an element is, but they are poorly suited to learning whether the element is good or bad. Here we propose air time detection, a novel motion analysis task, the goal of which is to accurately detect the duration of the air time of a jump. We present YourSkatingCoach, a large, novel figure skating dataset which contains 454 videos of jump elements, the detected skater skeletons in each video, along with the gold labels of the start and ending frames of each jump, together as a video benchmark for figure skating. In addition, although this type of task is often viewed as classification, we cast it as a sequential labeling problem and propose a Transformer-based model to calculate the duration. Experimental results show that the proposed model yields a favorable results for a strong baseline. To further verify the generalizability of the fine-grained labels, we apply the same process to other sports as cross-sports tasks but for coarse-grained task action classification. Here we fine-tune the classification to demonstrate that figure skating, as it contains the essential body movements, constitutes a strong foundation for adaptation to other sports.
Architectural Solutions for High-Speed Data Processing Demands of CERN LHC Detectors with FPGA and High-Level Synthesis
Venue: arXiv cs.AR 2024
Year: 2024

The planned high-luminosity upgrade of the Large Hadron Collider (LHC) at CERN will bring much higher data rates that are far above the capabilities of currently installed software-based data processing systems. Therefore, new methods must be used to facilitate on-the-fly extraction of scientifically significant information from the immense flow of data produced by LHC particle detectors. This paper focuses on implementation of a tau lepton triggering algorithm in FPGA. Due to the algorithm's complexity and strict technical requirements, its implementation in FPGA fabric becomes a particularly challenging task. The paper presents a study of algorithm development with the help of High-Level Synthesis (HLS) technique that can generate hardware description from C++ code. Various architectural solutions and optimizations that were tried out during the design architecture exploration process are also discussed in the paper.
Unlocking Comics: The AI4VA Dataset for Visual Understanding
Venue: arXiv cs.CV 2024
Year: 2024

In the evolving landscape of deep learning, there is a pressing need for more comprehensive datasets capable of training models across multiple modalities. Concurrently, in digital humanities, there is a growing demand to leverage technology for diverse media adaptation and creation, yet limited by sparse datasets due to copyright and stylistic constraints. Addressing this gap, our paper presents a novel dataset comprising Franco-Belgian comics from the 1950s annotated for tasks including depth estimation, semantic segmentation, saliency detection, and character identification. It consists of two distinct and consistent styles and incorporates object concepts and labels taken from natural images. By including such diverse information across styles, this dataset not only holds promise for computational creativity but also offers avenues for the digitization of art and storytelling innovation. This dataset is a crucial component of the AI4VA Workshop Challenges~\url{https://sites.google.com/view/ai4vaeccv2024}, where we specifically explore depth and saliency. Dataset details at \url{https://github.com/IVRL/AI4VA}.
Understanding Communication Preferences of Information Workers in Engagement with Text-Based Conversational Agents
Venue: arXiv cs.HC 2024
Year: 2024

Communication traits in text-based human-AI conversations play pivotal roles in shaping user experiences and perceptions of systems. With the advancement of large language models (LLMs), it is now feasible to analyze these traits at a more granular level. In this study, we explore the preferences of information workers regarding chatbot communication traits across seven applications. Participants were invited to participate in an interactive survey, which featured adjustable sliders, allowing them to adjust and express their preferences for five key communication traits: formality, personification, empathy, sociability, and humor. Our findings reveal distinct communication preferences across different applications; for instance, there was a preference for relatively high empathy in wellbeing contexts and relatively low personification in coding. Similarities in preferences were also noted between applications such as chatbots for customer service and scheduling. These insights offer crucial design guidelines for future chatbots, emphasizing the need for nuanced trait adjustments for each application.
Improved Online Reachability Preservers
Venue: arXiv cs.DS 2024
Year: 2024

A reachability preserver is a basic kind of graph sparsifier, which preserves the reachability relation of an $n$-node directed input graph $G$ among a set of given demand pairs $P$ of size $|P|=p$. We give constructions of sparse reachability preservers in the online setting, where $G$ is given on input, the demand pairs $(s, t) \in P$ arrive one at a time, and we must irrevocably add edges to a preserver $H$ to ensure reachability for the pair $(s, t)$ before we can see the next demand pair. Our main results are: -- There is a construction that guarantees a maximum preserver size of $$|E(H)| \le O\left( n^{0.72}p^{0.56} + n^{0.6}p^{0.7} + n\right).$$ This improves polynomially on the previous online upper bound of $O( \min\{np^{0.5}, n^{0.5}p\}) + n$, implicit in the work of Coppersmith and Elkin [SODA '05]. -- Given a promise that the demand pairs will satisfy $P \subseteq S \times V$ for some vertex set $S$ of size $|S|=:σ$, there is a construction that guarantees a maximum preserver size of $$|E(H)| \le O\left( (npσ)^{1/2} + n\right).$$ A slightly different construction gives the same result for the setting $P \subseteq V \times S$. This improves polynomially on the previous online upper bound of $O( σn)$ (folklore). All of these constructions are polynomial time, deterministic, and they do not require knowledge of the values of $p, σ$, or $S$. Our techniques also give a small polynomial improvement in the current upper bounds for offline reachability preservers, and they extend to a stronger model in which we must commit to a path for all possible reachable pairs in $G$ before any demand pairs have been received. As an application, we improve the competitive ratio for Online Unweighted Directed Steiner Forest to $O(n^{3/5 + \varepsilon})$.
MidiTok Visualizer: a tool for visualization and analysis of tokenized MIDI symbolic music
Venue: arXiv cs.SD 2024
Year: 2024

Symbolic music research plays a crucial role in music-related machine learning, but MIDI data can be complex for those without musical expertise. To address this issue, we present MidiTok Visualizer, a web application designed to facilitate the exploration and visualization of various MIDI tokenization methods from the MidiTok Python package. MidiTok Visualizer offers numerous customizable parameters, enabling users to upload MIDI files to visualize tokenized data alongside an interactive piano roll.
Llama Scope: Extracting Millions of Features from Llama-3.1-8B with Sparse Autoencoders
Venue: arXiv cs.LG 2024
Year: 2024

Sparse Autoencoders (SAEs) have emerged as a powerful unsupervised method for extracting sparse representations from language models, yet scalable training remains a significant challenge. We introduce a suite of 256 SAEs, trained on each layer and sublayer of the Llama-3.1-8B-Base model, with 32K and 128K features. Modifications to a state-of-the-art SAE variant, Top-K SAEs, are evaluated across multiple dimensions. In particular, we assess the generalizability of SAEs trained on base models to longer contexts and fine-tuned models. Additionally, we analyze the geometry of learned SAE latents, confirming that \emph{feature splitting} enables the discovery of new features. The Llama Scope SAE checkpoints are publicly available at~\url{https://huggingface.co/fnlp/Llama-Scope}, alongside our scalable training, interpretation, and visualization tools at \url{https://github.com/OpenMOSS/Language-Model-SAEs}. These contributions aim to advance the open-source Sparse Autoencoder ecosystem and support mechanistic interpretability research by reducing the need for redundant SAE training.
Malinowski in the Age of AI: Can large language models create a text game based on an anthropological classic?
Venue: arXiv cs.HC 2024
Year: 2024

Recent advancements in Large Language Models (LLMs) like ChatGPT and GPT-4 have shown remarkable abilities in a wide range of tasks such as summarizing texts and assisting in coding. Scientific research has demonstrated that these models can also play text-adventure games. This study aims to explore whether LLMs can autonomously create text-based games based on anthropological classics, evaluating also their effectiveness in communicating knowledge. To achieve this, the study engaged anthropologists in discussions to gather their expectations and design inputs for an anthropologically themed game. Through iterative processes following the established HCI principle of 'design thinking', the prompts and the conceptual framework for crafting these games were refined. Leveraging GPT3.5, the study created three prototypes of games centered around the seminal anthropological work of the social anthropologist's Bronislaw Malinowski's "Argonauts of the Western Pacific" (1922). Subsequently, evaluations were conducted by inviting senior anthropologists to playtest these games, and based on their inputs, the game designs were refined. The tests revealed promising outcomes but also highlighted key challenges: the models encountered difficulties in providing in-depth thematic understandings, showed suspectibility to misinformation, tended towards monotonic responses after an extended period of play, and struggled to offer detailed biographical information. Despite these limitations, the study's findings open up new research avenues at the crossroads of artificial intelligence, machine learning, LLMs, ethnography, anthropology and human-computer interaction.
Improving the Leading Constant of Matrix Multiplication
Venue: arXiv cs.CC 2024
Year: 2024

Algebraic matrix multiplication algorithms are designed by bounding the rank of matrix multiplication tensors, and then using a recursive method. However, designing algorithms in this way quickly leads to large constant factors: if one proves that the tensor for multiplying $n \times n$ matrices has rank $\leq t$, then the resulting recurrence shows that $M \times M$ matrices can be multiplied using $O(n^2 \cdot M^{\log_n t})$ operations, where the leading constant scales proportionally to $n^2$. Even modest increases in $n$ can blow up the leading constant too much to be worth the slight decrease in the exponent of $M$. Meanwhile, the asymptotically best algorithms use very large $n$, such that $n^2$ is larger than the number of atoms in the visible universe! In this paper, we give new ways to use tensor rank bounds to design matrix multiplication algorithms, which lead to smaller leading constants than the standard recursive method. Our main result shows that, if the tensor for multiplying $n \times n$ matrices has rank $\leq t$, then $M \times M$ matrices can be multiplied using only $n^{O(1/(\log n)^{0.33})} \cdot M^{\log_n t}$ operations. In other words, we improve the leading constant in general from $O(n^2)$ to $n^{O(1/(\log n)^{0.33})} < n^{o(1)}$. We then apply this and further improve the leading constant in a number of situations of interest. We show that, in the popularly-conjectured case where $ω=2$, a new, different recursive approach can lead to an improvement. We also show that the leading constant of the current asymptotically fastest matrix multiplication algorithm, and any algorithm designed using the group-theoretic method, can be further improved by taking advantage of additional structure of the underlying tensor identities.