OpenRaiser/Intern-Atlas huggingface dataset:
AugTriever: Unsupervised Dense Retrieval and Domain Adaptation by Scalable Data Augmentation
Venue: arXiv cs.CL 2024
Year: 2024

Dense retrievers have made significant strides in text retrieval and open-domain question answering. However, most of these achievements have relied heavily on extensive human-annotated supervision. In this study, we aim to develop unsupervised methods for improving dense retrieval models. We propose two approaches that enable annotation-free and scalable training by creating pseudo querydocument pairs: query extraction and transferred query generation. The query extraction method involves selecting salient spans from the original document to generate pseudo queries. On the other hand, the transferred query generation method utilizes generation models trained for other NLP tasks, such as summarization, to produce pseudo queries. Through extensive experimentation, we demonstrate that models trained using these augmentation methods can achieve comparable, if not better, performance than multiple strong dense baselines. Moreover, combining these strategies leads to further improvements, resulting in superior performance of unsupervised dense retrieval, unsupervised domain adaptation and supervised finetuning, benchmarked on both BEIR and ODQA datasets. Code and datasets are publicly available at https://github.com/salesforce/AugTriever.
UAVCAN Dataset Description
Venue: arXiv cs.CR 2024
Year: 2024

We collected attack data from unmanned vehicles using the UAVCAN protocol, and public and described technical documents. A testbed was built with a drone using PX4, and a total of three attacks, Flooding, Fuzzy, and Replay, were performed. The attack was carried out in a total of 10 scenarios. We expect that the attack data will help develop technologies such as anomaly detection to solve the security threat problem of drones.
Medical Knowledge Graph QA for Drug-Drug Interaction Prediction based on Multi-hop Machine Reading Comprehension
Venue: arXiv cs.CL 2024
Year: 2024

Drug-drug interaction prediction is a crucial issue in molecular biology. Traditional methods of observing drug-drug interactions through medical experiments require significant resources and labor. This paper presents a medical knowledge graph question answering model, dubbed MedKGQA, that predicts drug-drug interaction by employing machine reading comprehension from closed-domain literature and constructing a knowledge graph of drug-protein triplets from open-domain documents. The model vectorizes the drug-protein target attributes in the graph using entity embeddings and establishes directed connections between drug and protein entities based on the metabolic interaction pathways of protein targets in the human body. This aligns multiple external knowledge and applies it to learn the graph neural network. Without bells and whistles, the proposed model achieved a 4.5% improvement in terms of drug-drug interaction prediction accuracy compared to previous state-of-the-art models on the Qangaroo MedHop dataset. Experimental results demonstrate the efficiency and effectiveness of the model and verify the feasibility of integrating external knowledge in machine reading comprehension tasks.
Improving Faithfulness of Abstractive Summarization by Controlling Confounding Effect of Irrelevant Sentences
Venue: arXiv cs.CL 2024
Year: 2024

Lack of factual correctness is an issue that still plagues state-of-the-art summarization systems despite their impressive progress on generating seemingly fluent summaries. In this paper, we show that factual inconsistency can be caused by irrelevant parts of the input text, which act as confounders. To that end, we leverage information-theoretic measures of causal effects to quantify the amount of confounding and precisely quantify how they affect the summarization performance. Based on insights derived from our theoretical results, we design a simple multi-task model to control such confounding by leveraging human-annotated relevant sentences when available. Crucially, we give a principled characterization of data distributions where such confounding can be large thereby necessitating the use of human annotated relevant sentences to generate factual summaries. Our approach improves faithfulness scores by 20\% over strong baselines on AnswerSumm \citep{fabbri2021answersumm}, a conversation summarization dataset where lack of faithfulness is a significant issue due to the subjective nature of the task. Our best method achieves the highest faithfulness score while also achieving state-of-the-art results on standard metrics like ROUGE and METEOR. We corroborate these improvements through human evaluation.
Distributional Robustness Bounds Generalization Errors
Venue: arXiv cs.LG 2024
Year: 2024

Bayesian methods, distributionally robust optimization methods, and regularization methods are three pillars of trustworthy machine learning combating distributional uncertainty, e.g., the uncertainty of an empirical distribution compared to the true underlying distribution. This paper investigates the connections among the three frameworks and, in particular, explores why these frameworks tend to have smaller generalization errors. Specifically, first, we suggest a quantitative definition for "distributional robustness", propose the concept of "robustness measure", and formalize several philosophical concepts in distributionally robust optimization. Second, we show that Bayesian methods are distributionally robust in the probably approximately correct (PAC) sense; in addition, by constructing a Dirichlet-process-like prior in Bayesian nonparametrics, it can be proven that any regularized empirical risk minimization method is equivalent to a Bayesian method. Third, we show that generalization errors of machine learning models can be characterized using the distributional uncertainty of the nominal distribution and the robustness measures of these machine learning models, which is a new perspective to bound generalization errors, and therefore, explain the reason why distributionally robust machine learning models, Bayesian models, and regularization models tend to have smaller generalization errors in a unified manner.
BMX: Boosting Natural Language Generation Metrics with Explainability
Venue: arXiv cs.CL 2024
Year: 2024

State-of-the-art natural language generation evaluation metrics are based on black-box language models. Hence, recent works consider their explainability with the goals of better understandability for humans and better metric analysis, including failure cases. In contrast, our proposed method BMX: Boosting Natural Language Generation Metrics with explainability explicitly leverages explanations to boost the metrics' performance. In particular, we perceive feature importance explanations as word-level scores, which we convert, via power means, into a segment-level score. We then combine this segment-level score with the original metric to obtain a better metric. Our tests show improvements for multiple metrics across MT and summarization datasets. While improvements in machine translation are small, they are strong for summarization. Notably, BMX with the LIME explainer and preselected parameters achieves an average improvement of 0.087 points in Spearman correlation on the system-level evaluation of SummEval.
Re-evaluating the Need for Multimodal Signals in Unsupervised Grammar Induction
Venue: arXiv cs.CL 2024
Year: 2024

Are multimodal inputs necessary for grammar induction? Recent work has shown that multimodal training inputs can improve grammar induction. However, these improvements are based on comparisons to weak text-only baselines that were trained on relatively little textual data. To determine whether multimodal inputs are needed in regimes with large amounts of textual training data, we design a stronger text-only baseline, which we refer to as LC-PCFG. LC-PCFG is a C-PFCG that incorporates em-beddings from text-only large language models (LLMs). We use a fixed grammar family to directly compare LC-PCFG to various multi-modal grammar induction methods. We compare performance on four benchmark datasets. LC-PCFG provides an up to 17% relative improvement in Corpus-F1 compared to state-of-the-art multimodal grammar induction methods. LC-PCFG is also more computationally efficient, providing an up to 85% reduction in parameter count and 8.8x reduction in training time compared to multimodal approaches. These results suggest that multimodal inputs may not be necessary for grammar induction, and emphasize the importance of strong vision-free baselines for evaluating the benefit of multimodal approaches.
Discovering Process Models With Long-Term Dependencies While Providing Guarantees and Filtering Infrequent Behavior Patterns
Venue: arXiv cs.DB 2024
Year: 2024

In process discovery, the goal is to find, for a given event log, the model describing the underlying process. While process models can be represented in a variety of ways, Petri nets form a theoretically well-explored description language and are therefore often used. In this paper, we extend the eST-Miner process discovery algorithm. The eST-Miner computes a set of Petri net places which are considered to be fitting with respect to a certain fraction of the behavior described by the given event log as indicated by a given noise threshold. It evaluates all possible candidate places using token-based replay. The set of replayable traces is determined for each place in isolation, i.e., these sets do not need to be consistent. This allows the algorithm to abstract from infrequent behavioral patterns occurring only in some traces. However, when combining places into a Petri net by connecting them to the corresponding uniquely labeled transitions, the resulting net can replay exactly those traces from the event log that are allowed by the combination of all inserted places. Thus, inserting places one-by-one without considering their combined effect may result in deadlocks and low fitness of the Petri net. In this paper, we explore adaptions of the eST-Miner, that aim to select a subset of places such that the resulting Petri net guarantees a definable minimal fitness while maintaining high precision with respect to the input event log. Furthermore, current place evaluation techniques tend to block the execution of infrequent activity labels. Thus, a refined place fitness metric is introduced and thoroughly investigated. In our experiments we use real and artificial event logs to evaluate and compare the impact of the various place selection strategies and place fitness evaluation metrics on the returned Petri net.
Improved Field Size Bounds for Higher Order MDS Codes
Venue: arXiv cs.IT 2024
Year: 2024

Higher order MDS codes are an interesting generalization of MDS codes recently introduced by Brakensiek, Gopi and Makam (IEEE Trans. Inf. Theory 2022). In later works, they were shown to be intimately connected to optimally list-decodable codes and maximally recoverable tensor codes. Therefore (explicit) constructions of higher order MDS codes over small fields is an important open problem. Higher order MDS codes are denoted by $\operatorname{MDS}(\ell)$ where $\ell$ denotes the order of generality, $\operatorname{MDS}(2)$ codes are equivalent to the usual MDS codes. The best prior lower bound on the field size of an $(n,k)$-$\operatorname{MDS}(\ell)$ codes is $Ω_\ell(n^{\ell-1})$, whereas the best known (non-explicit) upper bound is $O_\ell(n^{k(\ell-1)})$ which is exponential in the dimension. In this work, we nearly close this exponential gap between upper and lower bounds. We show that an $(n,k)$-$\operatorname{MDS}(3)$ codes requires a field of size $Ω_k(n^{k-1})$, which is close to the known upper bound. Using the connection between higher order MDS codes and optimally list-decodable codes, we show that even for a list size of 2, a code which meets the optimal list-decoding Singleton bound requires exponential field size; this resolves an open question from Shangguan and Tamo (STOC 2020 / SIAM J. on Computing 2023). We also give explicit constructions of $(n,k)$-$\operatorname{MDS}(\ell)$ code over fields of size $n^{(\ell k)^{O(\ell k)}}$. The smallest non-trivial case where we still do not have optimal constructions is $(n,3)$-$\operatorname{MDS}(3)$. In this case, the known lower bound on the field size is $Ω(n^2)$ and the best known upper bounds are $O(n^5)$ for a non-explicit construction and $O(n^{32})$ for an explicit construction. In this paper, we give an explicit construction over fields of size $O(n^3)$ which comes very close to being optimal.
Language models are better than humans at next-token prediction
Venue: arXiv cs.CL 2024
Year: 2024

Current language models are considered to have sub-human capabilities at natural language tasks like question-answering or writing code. However, language models are not trained to perform well at these tasks, they are trained to accurately predict the next token given previous tokes in tokenized text. It is not clear whether language models are better or worse than humans at next token prediction. To try to answer this question, we performed two distinct experiments to directly compare humans and language models on this front: one measuring top-1 accuracy and the other measuring perplexity. In both experiments, we find humans to be consistently \emph{worse} than even relatively small language models like GPT3-Ada at next-token prediction.
Bent functions and strongly regular graphs
Venue: arXiv cs.IT 2024
Year: 2024

The family of bent functions is a known class of Boolean functions, which have a great importance in cryptography. The Cayley graph defined on $\mathbb{Z}_{2}^{n}$ by the support of a bent function is a strongly regular graph $srg(v,kλ,μ)$, with $λ=μ$. In this note we list the parameters of such Cayley graphs. Moreover, it is given a condition on $(n,m)$-bent functions $F=(f_1,\ldots,f_m)$, involving the support of their components $f_i$, and their $n$-ary symmetric differences.
Mask Focal Loss: A unifying framework for dense crowd counting with canonical object detection networks
Venue: arXiv cs.CV 2024
Year: 2024

As a fundamental computer vision task, crowd counting plays an important role in public safety. Currently, deep learning based head detection is a promising method for crowd counting. However, the highly concerned object detection networks cannot be well applied to this problem for three reasons: (1) Existing loss functions fail to address sample imbalance in highly dense and complex scenes; (2) Canonical object detectors lack spatial coherence in loss calculation, disregarding the relationship between object location and background region; (3) Most of the head detection datasets are only annotated with the center points, i.e. without bounding boxes. To overcome these issues, we propose a novel Mask Focal Loss (MFL) based on heatmap via the Gaussian kernel. MFL provides a unifying framework for the loss functions based on both heatmap and binary feature map ground truths. Additionally, we introduce GTA_Head, a synthetic dataset with comprehensive annotations, for evaluation and comparison. Extensive experimental results demonstrate the superior performance of our MFL across various detectors and datasets, and it can reduce MAE and RMSE by up to 47.03% and 61.99%, respectively. Therefore, our work presents a strong foundation for advancing crowd counting methods based on density estimation.
Graph-Based Specification and Automated Construction of ILP Problems
Venue: arXiv cs.SE 2024
Year: 2024

In the Model-Driven Software Engineering (MDSE) community, the combination of techniques operating on graph-based models (e.g., Pattern Matching (PM) and Graph Transformation (GT)) and Integer Linear Programming (ILP) is a common occurrence, since ILP solvers offer a powerful approach to solve linear optimization problems and help to enforce global constraints while delivering optimal solutions. However, designing and specifying complex optimization problems from more abstract problem descriptions can be a challenging task. A designer must be an expert in the specific problem domain as well as the ILP optimization domain to translate the given problem into a valid ILP problem. Typically, domain-specific ILP problem generators are hand-crafted by experts, to avoid specifying a new ILP problem by hand for each new instance of a problem domain. Unfortunately, the task of writing ILP problem generators is an exercise, which has to be repeated for each new scenario, tool, and approach. For this purpose, we introduce the GIPS (Graph-Based ILP Problem Specification Tool) framework that simplifies the development of ILP problem generators for graph-based optimization problems and a new Domain-Specific Language (DSL) called GIPSL (Graph-Based ILP Problem Specification Language) that integrates GT and ILP problems on an abstract level. Our approach uses GIPSL specifications as a starting point to derive ILP problem generators for a specific application domain automatically. First experiments show that the derived ILP problem generators can compete with hand-crafted programs developed by ILP experts.
Dataset of Pathloss and ToA Radio Maps With Localization Application
Venue: arXiv cs.NI 2024
Year: 2024

In this article, we present a collection of radio map datasets in dense urban setting, which we generated and made publicly available. The datasets include simulated pathloss/received signal strength (RSS) and time of arrival (ToA) radio maps over a large collection of realistic dense urban setting in real city maps. The two main applications of the presented dataset are 1) learning methods that predict the pathloss from input city maps (namely, deep learning-based simulations), and, 2) wireless localization. The fact that the RSS and ToA maps are computed by the same simulations over the same city maps allows for a fair comparison of the RSS and ToA-based localization methods.
Storage codes on coset graphs with asymptotically unit rate
Venue: arXiv cs.IT 2024
Year: 2024

A storage code on a graph $G$ is a set of assignments of symbols to the vertices such that every vertex can recover its value by looking at its neighbors. We consider the question of constructing large-size storage codes on triangle-free graphs constructed as coset graphs of binary linear codes. Previously it was shown that there are infinite families of binary storage codes on coset graphs with rate converging to 3/4. Here we show that codes on such graphs can attain rate asymptotically approaching 1. Equivalently, this question can be phrased as a version of hat-guessing games on graphs (e.g., P.J. Cameron e.a., \emph{Electronic J. Comb.} 2016). In this language, we construct triangle-free graphs with success probability of the players approaching one as the number of vertices tends to infinity. Furthermore, finding linear index codes of rate approaching zero is also an equivalent problem. Another family of storage codes on triangle-free graphs of rate approaching 1 was constructed earlier by A. Golovnev and I. Haviv (36th Computational Complexity Conf., 2021) relying on a different family of graphs.
Agent-based Modeling and Simulation of Human Muscle For Development of Human Gait Analyzer Application
Venue: arXiv cs.AI 2024
Year: 2024

Despite the fact that only a small portion of muscles are affected in motion disease and disorders, medical therapies do not distinguish between healthy and unhealthy muscles. In this paper, a method is devised in order to calculate the neural stimuli of the lower body during gait cycle and check if any group of muscles are not acting properly. For this reason, an agent-based model of human muscle is proposed. The agent is able to convert neural stimuli to force generated by the muscle and vice versa. It can be used in many researches including medical education and research and prosthesis development. Then, Boots algorithm is designed based on a biomechanical model of human lower body to do a reverse dynamics of human motion by computing the forces generated by each muscle group. Using the agent-driven model of human muscle and boots algorithm, a user-friendly application is developed which can calculate the number of neural stimuli received by each muscle during gait cycle. The application can be used by clinical experts to distinguish between healthy and unhealthy muscles.
MicroRes: Versatile Resilience Profiling in Microservices via Degradation Dissemination Indexing
Venue: arXiv cs.SE 2024
Year: 2024

Microservice resilience, the ability of microservices to recover from failures and continue providing reliable and responsive services, is crucial for cloud vendors. However, the current practice relies on manually configured rules specific to a certain microservice system, resulting in labor-intensity and flexibility issues, given the large scale and high dynamics of microservices. A more labor-efficient and versatile solution is desired. Our insight is that resilient deployment can effectively prevent the dissemination of degradation from system performance metrics to user-aware metrics, and the latter directly affects service quality. In other words, failures in a non-resilient deployment can impact both types of metrics, leading to user dissatisfaction. With this in mind, we propose MicroRes, the first versatile resilience profiling framework for microservices via degradation dissemination indexing. MicroRes first injects failures into microservices and collects available monitoring metrics. Then, it ranks the metrics according to their contributions to the overall service degradation. It produces a resilience index by how much the degradation is disseminated from system performance metrics to user-aware metrics. Higher degradation dissemination indicates lower resilience. We evaluate MicroRes on two open-source and one industrial microservice system. The experiments show MicroRes' efficient and effective resilience profiling of microservices. We also showcase MicroRes' practical usage in production.
Improved Kernel Alignment Regret Bound for Online Kernel Learning
Venue: arXiv cs.LG 2024
Year: 2024

In this paper, we improve the kernel alignment regret bound for online kernel learning in the regime of the Hinge loss function. Previous algorithm achieves a regret of $O((\mathcal{A}_TT\ln{T})^{\frac{1}{4}})$ at a computational complexity (space and per-round time) of $O(\sqrt{\mathcal{A}_TT\ln{T}})$, where $\mathcal{A}_T$ is called \textit{kernel alignment}. We propose an algorithm whose regret bound and computational complexity are better than previous results. Our results depend on the decay rate of eigenvalues of the kernel matrix. If the eigenvalues of the kernel matrix decay exponentially, then our algorithm enjoys a regret of $O(\sqrt{\mathcal{A}_T})$ at a computational complexity of $O(\ln^2{T})$. Otherwise, our algorithm enjoys a regret of $O((\mathcal{A}_TT)^{\frac{1}{4}})$ at a computational complexity of $O(\sqrt{\mathcal{A}_TT})$. We extend our algorithm to batch learning and obtain a $O(\frac{1}{T}\sqrt{\mathbb{E}[\mathcal{A}_T]})$ excess risk bound which improves the previous $O(1/\sqrt{T})$ bound.