OpenRaiser/Intern-Atlas huggingface dataset:
The Quasi-probability Method and Applications for Trace Reconstruction
Venue: arXiv cs.DS 2024
Year: 2024

In the trace reconstruction problem, one attempts to reconstruct a fixed but unknown string $x$ of length $n$ from a given number of traces $\tilde{x}$ drawn iid from the application of a noisy process (such as the deletion channel) to $x$. The best known algorithm for the trace reconstruction from the deletion channel is due to Chase, and recovers the input string whp given $\exp(\tilde{O}(n^{1/5}))$ traces [Cha21b]. The main component in Chase's algorithm is a procedure for k-mer estimation, which, for any marker $w$ in $\{0, 1\}^k$ of length $k$, computes a "smoothed" distribution of its appearances in the input string $x$ [CGL+23, MS24]. Current k-mer estimation algorithms fail when the deletion probability is above $1/2$, requiring a more complex analysis for Chase's algorithm. Moreover, the only known extension of these approaches beyond the deletion channels is based on numerically estimating high-order differentials of a multivariate polynomial, making it highly impractical [Rub23]. In this paper, we construct a simple Monte Carlo method for k-mer estimation which can be easily applied to a much wider variety of channels. In particular, we solve k-mer estimation for any combination of insertion, deletion, and bit-flip channels, even in the high deletion probability regime, allowing us to directly apply Chase's algorithm for this wider class of channels. To accomplish this, we utilize an approach from the field of quantum error mitigation (the process of using many measurements from noisy quantum computers to simulate a clean quantum computer), called the quasi-probability method (also known as probabilistic error cancellation) [TBG17, PSW22]. We derive a completely classical version of this technique, and use it to construct a k-mer estimation algorithm. No background in quantum computing is needed to understand this paper.
Impacts of Continued Legal Pre-Training and IFT on LLMs' Latent Representations of Human-Defined Legal Concepts
Venue: arXiv cs.CL 2024
Year: 2024

This paper aims to offer AI & Law researchers and practitioners a more detailed understanding of whether and how continued pre-training and instruction fine-tuning (IFT) of large language models (LLMs) on legal corpora increases their utilization of human-defined legal concepts when developing global contextual representations of input sequences. We compared three models: Mistral 7B, SaulLM-7B-Base (Mistral 7B with continued pre-training on legal corpora), and SaulLM-7B-Instruct (with further IFT). This preliminary assessment examined 7 distinct text sequences from recent AI & Law literature, each containing a human-defined legal concept. We first compared the proportions of total attention the models allocated to subsets of tokens representing the legal concepts. We then visualized patterns of raw attention score alterations, evaluating whether legal training introduced novel attention patterns corresponding to structures of human legal knowledge. This inquiry revealed that (1) the impact of legal training was unevenly distributed across the various human-defined legal concepts, and (2) the contextual representations of legal knowledge learned during legal training did not coincide with structures of human-defined legal concepts. We conclude with suggestions for further investigation into the dynamics of legal LLM training.
MoE-Pruner: Pruning Mixture-of-Experts Large Language Model using the Hints from Its Router
Venue: arXiv cs.CL 2024
Year: 2024

Mixture-of-Experts (MoE) architectures face challenges such as high memory consumption and redundancy in experts. Pruning MoE can reduce network weights while maintaining model performance. Motivated by the recent observation of emergent large magnitude features in Large Language Models (LLM) and MoE routing policy, we propose MoE-Pruner, a method that prunes weights with the smallest magnitudes multiplied by the corresponding input activations and router weights, on each output neuron. Our pruning method is one-shot, requiring no retraining or weight updates. We evaluate our method on Mixtral-8x7B and Mixtral-8x22B across multiple language benchmarks. Experimental results show that our pruning method significantly outperforms state-of-the-art LLM pruning methods. Furthermore, our pruned MoE models can benefit from a pretrained teacher model through expert-wise knowledge distillation, improving performance post-pruning. Experimental results demonstrate that the Mixtral-8x7B model with 50% sparsity maintains 99% of the performance of the original model after the expert-wise knowledge distillation.
LocoMotion: Learning Motion-Focused Video-Language Representations
Venue: arXiv cs.CV 2024
Year: 2024

This paper strives for motion-focused video-language representations. Existing methods to learn video-language representations use spatial-focused data, where identifying the objects and scene is often enough to distinguish the relevant caption. We instead propose LocoMotion to learn from motion-focused captions that describe the movement and temporal progression of local object motions. We achieve this by adding synthetic motions to videos and using the parameters of these motions to generate corresponding captions. Furthermore, we propose verb-variation paraphrasing to increase the caption variety and learn the link between primitive motions and high-level verbs. With this, we are able to learn a motion-focused video-language representation. Experiments demonstrate our approach is effective for a variety of downstream tasks, particularly when limited data is available for fine-tuning. Code is available: https://hazeldoughty.github.io/Papers/LocoMotion/
Concept-Reversed Winograd Schema Challenge: Evaluating and Improving Robust Reasoning in Large Language Models via Abstraction
Venue: arXiv cs.CL 2024
Year: 2024

While Large Language Models (LLMs) have showcased remarkable proficiency in reasoning, there is still a concern about hallucinations and unreliable reasoning issues due to semantic associations and superficial logical chains. To evaluate the extent to which LLMs perform robust reasoning instead of relying on superficial logical chains, we propose a new evaluation dataset, the Concept-Reversed Winograd Schema Challenge (CR-WSC), based on the famous Winograd Schema Challenge (WSC) dataset. By simply reversing the concepts to those that are more associated with the wrong answer, we find that the performance of LLMs drops significantly despite the rationale of reasoning remaining the same. Furthermore, we propose Abstraction-of-Thought (AoT), a novel prompt method for recovering adversarial cases to normal cases using conceptual abstraction to improve LLMs' robustness and consistency in reasoning, as demonstrated by experiments on CR-WSC.
A State-of-the-Art Morphosyntactic Parser and Lemmatizer for Ancient Greek
Venue: arXiv cs.CL 2024
Year: 2024

This paper presents an experiment consisting in the comparison of six models to identify a state-of-the-art morphosyntactic parser and lemmatizer for Ancient Greek capable of annotating according to the Ancient Greek Dependency Treebank annotation scheme. A normalized version of the major collections of annotated texts was used to (i) train the baseline model Dithrax with randomly initialized character embeddings and (ii) fine-tune Trankit and four recent models pretrained on Ancient Greek texts, i.e., GreBERTa and PhilBERTa for morphosyntactic annotation and GreTA and PhilTa for lemmatization. A Bayesian analysis shows that Dithrax and Trankit annotate morphology practically equivalently, while syntax is best annotated by Trankit and lemmata by GreTa. The results of the experiment suggest that token embeddings are not sufficient to achieve high UAS and LAS scores unless they are coupled with a modeling strategy specifically designed to capture syntactic relationships. The dataset and best-performing models are made available online for reuse.
LegalLens Shared Task 2024: Legal Violation Identification in Unstructured Text
Venue: arXiv cs.CL 2024
Year: 2024

This paper presents the results of the LegalLens Shared Task, focusing on detecting legal violations within text in the wild across two sub-tasks: LegalLens-NER for identifying legal violation entities and LegalLens-NLI for associating these violations with relevant legal contexts and affected individuals. Using an enhanced LegalLens dataset covering labor, privacy, and consumer protection domains, 38 teams participated in the task. Our analysis reveals that while a mix of approaches was used, the top-performing teams in both tasks consistently relied on fine-tuning pre-trained language models, outperforming legal-specific models and few-shot methods. The top-performing team achieved a 7.11% improvement in NER over the baseline, while NLI saw a more marginal improvement of 5.7%. Despite these gains, the complexity of legal texts leaves room for further advancements.
Learning to rumble: Automated elephant call classification, detection and endpointing using deep architectures
Venue: arXiv cs.SD 2024
Year: 2024

We consider the problem of detecting, isolating and classifying elephant calls in continuously recorded audio. Such automatic call characterisation can assist conservation efforts and inform environmental management strategies. In contrast to previous work in which call detection was performed at a segment level, we perform call detection at a frame level which implicitly also allows call endpointing, the isolation of a call in a longer recording. For experimentation, we employ two annotated datasets, one containing Asian and the other African elephant vocalisations. We evaluate several shallow and deep classifier models, and show that the current best performance can be improved by using an audio spectrogram transformer (AST), a neural architecture which has not been used for this purpose before, and which we have configured in a novel sequence-to-sequence manner. We also show that using transfer learning by pre-training leads to further improvements both in terms of computational complexity and performance. Finally, we consider sub-call classification using an accepted taxonomy of call types, a task which has not previously been considered. We show that also in this case the transformer architectures provide the best performance. Our best classifiers achieve an average precision (AP) of 0.962 for framewise binary call classification, and an area under the receiver operating characteristic (AUC) of 0.957 and 0.979 for call classification with 5 classes and sub-call classification with 7 classes respectively. All of these represent either new benchmarks (sub-call classifications) or improvements on previously best systems. We conclude that a fully-automated elephant call detection and subcall classification system is within reach. Such a system would provide valuable information on the behaviour and state of elephant herds for the purposes of conservation and management.
A Novel Twisted-Winching String Actuator for Robotic Applications: Design and Validation
Venue: arXiv cs.RO 2024
Year: 2024

This paper presents a novel actuator system combining a twisted string actuator (TSA) with a winch mechanism. Relative to traditional hydraulic and pneumatic systems in robotics, TSAs are compact and lightweight but face limitations in stroke length and force-transmission ratios. Our integrated TSA-winch system overcomes these constraints by providing variable transmission ratios through dynamic adjustment. It increases actuator stroke by winching instead of overtwisting, and it improves force output by twisting. The design features a rotating turret that houses a winch, which is mounted on a bevel gear assembly driven by a through-hole drive shaft. Mathematical models are developed for the combined displacement and velocity control of this system. Experimental validation demonstrates the actuator's ability to achieve a wide range of transmission ratios and precise movement control. We present performance data on movement precision and generated forces, discussing the results in the context of existing literature. This research contributes to the development of more versatile and efficient actuation systems for advanced robotic applications and improved automation solutions.
Enhancing IoT Communication and Localization via Smarter Antenna
Venue: arXiv cs.NI 2024
Year: 2024

The convergence of sensing and communication functionalities is poised to become a pivotal feature of the sixth-generation (6G) wireless networks. This vision represents a paradigm shift in wireless network design, moving beyond mere communication to a holistic integration of sensing and communication capabilities, thereby further narrowing the gap between the physical and digital worlds. While Internet of Things (IoT) devices are integral to future wireless networks, their current capabilities in sensing and communication are constrained by their power and resource limitations. On one hand, their restricted power budget limits their transmission power, leading to reduced communication range and data rates. On the other hand, their limited hardware and processing abilities hinder the adoption of sophisticated sensing technologies, such as direction finding and localization. In this work, we introduce Wi-Pro, a system which seamlessly integrates today's WiFi protocol with smart antenna design to enhance the communication and sensing capabilities of existing IoT devices. This plug-and-play system can be easily installed by replacing the IoT device's antenna. Wi-Pro seamlessly integrates smart antenna hardware with current WiFi protocols, utilizing their inherent features to not only enhance communication but also to enable precise localization on low-cost IoT devices. Our evaluation results demonstrate that Wi-Pro achieves up to 150\% data rate improvement, up to five times range improvement, accurate direction finding, and localization on single-chain IoT devices.
A Web App for Teaching Finite State Automata
Venue: arXiv cs.CY 2024
Year: 2024

We present the open-source tool finsm.io, a tool for creating, simulating and exporting deterministic and non-deterministic finite state automata (DFA/NFA). We first describe the conceptual background on which the tool is based, followed by a description of features and preliminary evaluation of the tool based on use spanning multiple years and hundreds of student users. Preliminary evaluation found that instructors and students overwhelmingly recommend the tool to others and agree that it has improved their learning and teaching. The authors invite interested educators to use the tool in their finite automata courses.
Consider an Applications-First Approach for PDC
Venue: arXiv cs.DC 2024
Year: 2024

I propose an applications-first approach for adjusting how parallel and distributed computing concepts are incorporated into curricula. By focusing on practical applications that leverage parallelism and distributed systems, this approach aims to make these complex topics more accessible and engaging for both CS and non-CS majors. An applications-first approach demonstrates the advantages of parallel and distributed computing in solving real-world problems while building practical experience and skills before delving into theoretical concepts. This could potentially broaden the appeal and retention of these concepts. I highlight some example application-centric efforts, and conclude with questions that could be investigated in the service of exploring applications-first approaches.
Ranking with Multiple Objectives
Venue: arXiv cs.DS 2024
Year: 2024

In search and advertisement ranking, it is often required to simultaneously maximize multiple objectives. For example, the objectives can correspond to multiple intents of a search query, or in the context of advertising, they can be relevance and revenue. It is important to efficiently find rankings which strike a good balance between such objectives. Motivated by such applications, we formulate a general class of problems where - each result gets a different score corresponding to each objective, - the results of a ranking are aggregated by taking, for each objective, a weighted sum of the scores in the order of the ranking, and - an arbitrary concave function of the aggregates is maximized. Combining the aggregates using a concave function will naturally lead to more balanced outcomes. We give an approximation algorithm in a bicriteria/resource augmentation setting: the algorithm with a slight advantage does as well as the optimum. In particular, if the aggregation step is just the sum of the top k results, then the algorithm outputs k + 1 results which do as well the as the optimal top k results. We show how this approach helps with balancing different objectives via simulations on synthetic data as well as on real data from LinkedIn.
Layer-of-Thoughts Prompting (LoT): Leveraging LLM-Based Retrieval with Constraint Hierarchies
Venue: arXiv cs.CL 2024
Year: 2024

This paper presents a novel approach termed Layer-of-Thoughts Prompting (LoT), which utilizes constraint hierarchies to filter and refine candidate responses to a given query. By integrating these constraints, our method enables a structured retrieval process that enhances explainability and automation. Existing methods have explored various prompting techniques but often present overly generalized frameworks without delving into the nuances of prompts in multi-turn interactions. Our work addresses this gap by focusing on the hierarchical relationships among prompts. We demonstrate that the efficacy of thought hierarchy plays a critical role in developing efficient and interpretable retrieval algorithms. Leveraging Large Language Models (LLMs), LoT significantly improves the accuracy and comprehensibility of information retrieval tasks.
Table-LLM-Specialist: Language Model Specialists for Tables using Iterative Generator-Validator Fine-tuning
Venue: arXiv cs.CL 2024
Year: 2024

In this work, we propose Table-LLM-Specialist, or Table-Specialist for short, as a new self-trained fine-tuning paradigm specifically designed for table tasks. Our insight is that for each table task, there often exist two dual versions of the same task, one generative and one classification in nature. Leveraging their duality, we propose a Generator-Validator paradigm, to iteratively generate-then-validate training data from language-models, to fine-tune stronger \sys models that can specialize in a given task, without requiring manually-labeled data. Our extensive evaluations suggest that our Table-Specialist has (1) \textit{strong performance} on diverse table tasks over vanilla language-models -- for example, Table-Specialist fine-tuned on GPT-3.5 not only outperforms vanilla GPT-3.5, but can often match or surpass GPT-4 level quality, (2) \textit{lower cost} to deploy, because when Table-Specialist fine-tuned on GPT-3.5 achieve GPT-4 level quality, it becomes possible to deploy smaller models with lower latency and inference cost, with comparable quality, and (3) \textit{better generalizability} when evaluated across multiple benchmarks, since \sys is fine-tuned on a broad range of training data systematically generated from diverse real tables. Our code and data will be available at https://github.com/microsoft/Table-LLM-Specialist.
Dual-Model Distillation for Efficient Action Classification with Hybrid Edge-Cloud Solution
Venue: arXiv cs.CV 2024
Year: 2024

As Artificial Intelligence models, such as Large Video-Language models (VLMs), grow in size, their deployment in real-world applications becomes increasingly challenging due to hardware limitations and computational costs. To address this, we design a hybrid edge-cloud solution that leverages the efficiency of smaller models for local processing while deferring to larger, more accurate cloud-based models when necessary. Specifically, we propose a novel unsupervised data generation method, Dual-Model Distillation (DMD), to train a lightweight switcher model that can predict when the edge model's output is uncertain and selectively offload inference to the large model in the cloud. Experimental results on the action classification task show that our framework not only requires less computational overhead, but also improves accuracy compared to using a large model alone. Our framework provides a scalable and adaptable solution for action classification in resource-constrained environments, with potential applications beyond healthcare. Noteworthy, while DMD-generated data is used for optimizing performance and resource usage in our pipeline, we expect the concept of DMD to further support future research on knowledge alignment across multiple models.
Elementary Constructions of Best Known Quantum Codes
Venue: arXiv cs.IT 2024
Year: 2024

Recently, many good quantum codes over various finite fields $F_q$ have been constructed from codes over extension rings or mixed alphabet rings via some version of a Gray map. We show that most of these codes can be obtained more directly from cyclic codes or their generalizations over $F_q$. Unless explicit benefits are demonstrated for the indirect approach, we believe that direct and more elementary methods should be preferred.
A Lattice-based Method for Optimization in Continuous Spaces with Genetic Algorithms
Venue: arXiv cs.NE 2024
Year: 2024

This work presents a novel lattice-based methodology for incorporating multidimensional constraints into continuous decision variables within a genetic algorithm (GA) framework. The proposed approach consolidates established transcription techniques for crossover of continuous decision variables, aiming to leverage domain knowledge and guide the search process towards feasible regions of the design space. This work offers a robust and general purpose lattice-based GA that is applicable to a broad range of optimization problems. Monte Carlo analysis demonstrates that lattice-based methods find solutions two orders of magnitude closer to optima in fewer generations. The effectiveness of the lattice-based approach is showcased through two illustrative multi-objective design problems: (1) optimal telescope placement for astrophotography and (2) optimal design of a satellite constellation for maximizing ground station access. The optimal telescope placement example shows that lattice-based methods converge to the Pareto front in 15% fewer generations than traditional methods. The orbit design example shows that lattice-based methods discover an order of magnitude more Pareto-optimal solutions than traditional methods in a highly constrained design space. Overall, the results show that the lattice-based method exhibits enhanced exploration capabilities, traversing the solution space more comprehensively and achieving faster convergence compared to conventional GAs.