OpenRaiser/Intern-Atlas huggingface dataset:
An EPTAS for Budgeted Matching and Budgeted Matroid Intersection
Venue: arXiv cs.DS 2023
Year: 2023

We study the budgeted versions of the well known matching and matroid intersection problems. While both problems admit a polynomial-time approximation scheme (PTAS) [Berger et al. (Math. Programming, 2011), Chekuri, Vondrak and Zenklusen (SODA 2011)], it has been an intriguing open question whether these problems admit a fully PTAS (FPTAS), or even an efficient PTAS (EPTAS). In this paper we answer the second part of this question affirmatively, by presenting an EPTAS for budgeted matching and budgeted matroid intersection. A main component of our scheme is a novel construction of representative sets for desired solutions, whose cardinality depends only on $\varepsilon$, the accuracy parameter. Thus, enumerating over solutions within a representative set leads to an EPTAS. This crucially distinguishes our algorithms from previous approaches, which rely on exhaustive enumeration over the solution set. Our ideas for constructing representative sets may find use in tackling other budgeted optimization problems, and are thus of independent interest.
Maintaining Discrete Probability Distributions in Practice
Venue: arXiv cs.DS 2023
Year: 2023

A classical problem in random number generation is the sampling of elements from a given discrete distribution. Formally, given a set of indices $S = \{1, \dots, n\}$ and sequence of weights $w_1, \dots, w_n \in \mathbb{R}^+$, the task is to provide samples from $S$ with distribution $p(i) = w_i / W$ where $W = \sum_j w_j$. A commonly accepted solution is Walker's Alias Table, which allows for each sample to be drawn in constant time. However, some applications correspond to a dynamic setting, where elements are inserted or removed, or weights change over time. Here, the Alias Table is not efficient, as it needs to be re-built whenever the underlying distribution changes. In this paper, we engineer a simple data structure for maintaining discrete probability distributions in the dynamic setting. Construction of the data structure is possible in time $O(n)$, sampling is possible in expected time $O(1)$, and an update of size $Δ$ can be processed in time $O(Δn / W)$. As a special case, we maintain an urn containing $W$ marbles of $n$ colors where with each update $O(W / n)$ marbles can be added or removed in $O(1)$ time per update. To evaluate the efficiency of the data structure in practice we conduct an empirical study. The results suggest that the dynamic sampling performance is competitive with the static Alias Table. Compared to existing more complex dynamic solutions we obtain a sampling speed-up of up to half an order of magnitude.
Attention does not guarantee best performance in speech enhancement
Venue: arXiv cs.SD 2023
Year: 2023

Attention mechanism has been widely utilized in speech enhancement (SE) because theoretically it can effectively model the long-term inherent connection of signal both in time domain and spectrum domain. However, the generally used global attention mechanism might not be the best choice since the adjacent information naturally imposes more influence than the far-apart information in speech enhancement. In this paper, we validate this conjecture by replacing attention with RNN in two typical state-of-the-art (SOTA) models, multi-scale temporal frequency convolutional network (MTFAA) with axial attention and conformer-based metric-GAN network (CMGAN).
Gintropic Scaling of Scientometric Indexes
Venue: arXiv cs.DL 2023
Year: 2023

The most frequently used indicators for the productivity and impact of scientists are the total number of publication ($N_{pub}$), total number of citations ($N_{cit}$) and the Hirsch (h) index. Since the seminal paper of Hirsch, in 2005, it is largely debated whether the h index can be considered as an indicator independent of $N_{pub}$ and $N_{cit}$. Exploiting the Paretian form for the distribution of citations for the papers authored by a researcher, here we discuss scaling relations between h, $N_{pub}$ and $N_{cit}$. The analysis incorporates the Gini index as an inequality measure of citation distributions and a recently proposed inequality kernel, gintropy (resembling to the entropy kernel). We find a new upper bound for the h value as a function of the total number of citations, confimed on massive data collected from Google Scholar. Our analyses reveals also that the individualized Gini index calculated for the citations received by the publications of an author peaks around 0.8, a value much higher than the one characteristic for the usual socio-economic inequalities.
A Brief Report on LawGPT 1.0: A Virtual Legal Assistant Based on GPT-3
Venue: arXiv cs.CL 2023
Year: 2023

LawGPT 1.0 is a virtual legal assistant built on the state-of-the-art language model GPT-3, fine-tuned for the legal domain. The system is designed to provide legal assistance to users in a conversational manner, helping them with tasks such as answering legal questions, generating legal documents, and providing legal advice. In this paper, we provide a brief overview of LawGPT 1.0, its architecture, and its performance on a set of legal benchmark tasks. Please note that the detailed information about the model is protected by a non-disclosure agreement (NDA) and cannot be disclosed in this report.
Porting numerical integration codes from CUDA to oneAPI: a case study
Venue: arXiv cs.DC 2023
Year: 2023

We present our experience in porting optimized CUDA implementations to oneAPI. We focus on the use case of numerical integration, particularly the CUDA implementations of PAGANI and $m$-Cubes. We faced several challenges that caused performance degradation in the oneAPI ports. These include differences in utilized registers per thread, compiler optimizations, and mappings of CUDA library calls to oneAPI equivalents. After addressing those challenges, we tested both the PAGANI and m-Cubes integrators on numerous integrands of various characteristics. To evaluate the quality of the ports, we collected performance metrics of the CUDA and oneAPI implementations on the Nvidia V100 GPU. We found that the oneAPI ports often achieve comparable performance to the CUDA versions, and that they are at most 10% slower.
Coherence by Normalization for Linear Multicategorical Structures
Venue: arXiv cs.LO 2023
Year: 2023

We establish a formal correspondence between resource calculi an appropriate linear multicategories. We consider the cases of (symmetric) representable, symmetric closed and autonomous multicategories. For all these structures, we prove that morphisms of the corresponding free constructions can be presented by means of typed resource terms, up to a reduction relation and a structural equivalence. Thanks to the linearity of the calculi, we can prove strong normalization of the reduction by combinatorial methods, defining appropriate decreasing measures. From this, we achieve a general coherence result: morphisms that live in the free multicategorical structures are the same whenever the normal forms of the associated terms are equal. As further application, we obtain syntactic proofs of Mac Lane's coherence theorems for (symmetric) monoidal categories.
Assessment HTN (A-HTN) for Automated Task Performance Assessment in 3D Serious Games
Venue: arXiv cs.HC 2023
Year: 2023

In the recent years, various 3D mixed reality serious games have been developed for different applications such as physical training, rehabilitation, and education. Task performance in a serious game is a measurement of how efficiently and accurately users accomplish the game's objectives. Prior research includes a graph-based representation of tasks, e.g. Hierarchical Task Network (HTN), which only models a game's tasks but does not perform assessment. In this paper, we propose Assessment HTN (A-HTN), which both models the task efficiently and incorporates assessment logic for game objectives. Based on how the task performance is evaluated, A-HTN automatically performs: (a) Task-level Assessment by comparing object manipulations and (b) Action-level Assessment by comparing motion trajectories. The system can also categorize the task performance assessment into single user or multi-user based on who is being assessed. We showcase the effectiveness of the A-HTN using two 3D VR serious games: a hydrometer experiment and a multi-user chemistry experiment. The A-HTN experiments show a high correlation between instructor scores and the system generated scores indicating that the proposed A-HTN generalizes automatic assessment at par with Subject Matter Experts.
60 GHz Wi-Fi As A Tractor-Trailer Wireless Harness
Venue: arXiv cs.NI 2023
Year: 2023

Reverse driving a truck is a challenging task for human drivers and self-driving software due to the lack for sensors on the trailer. Self-driving and conventional trucks have an increasing need to replace the legacy communication channels between the truck and the trailer to accommodate bandwidth and latency requirements when more sensors and features are added to the trailer to support driver assist features or self-driving functions, in addition to the need of automating the tractor-trailer hitching and unhitching, which is a complex process when using wires and connectors for communication between the truck and the trailer. In this paper, we address using a wireless harness between the tractor and the trailer based on Wi-Fi, in addition to discussing using Named Data networking protocol for communication between the truck and the trailer including handling interest and data packets. A Testbed is used to evaluate communicating different data types from one device to three devices over 802.11ac and it indicated a stable communication performance when Named Data Networking and Data Distribution Service were used. Using a wireless harness will ease the automation of trailer hitching and unhitching process and will eliminate the need for communication wires or connectors between the tractor and the trailers, therefore, reducing the complexity of the process.
On Comparing Fair Classifiers under Data Bias
Venue: arXiv cs.LG 2023
Year: 2023

In this paper, we consider a theoretical model for injecting data bias, namely, under-representation and label bias (Blum & Stangl, 2019). We empirically study the effect of varying data biases on the accuracy and fairness of fair classifiers. Through extensive experiments on both synthetic and real-world datasets (e.g., Adult, German Credit, Bank Marketing, COMPAS), we empirically audit pre-, in-, and post-processing fair classifiers from standard fairness toolkits for their fairness and accuracy by injecting varying amounts of under-representation and label bias in their training data (but not the test data). Our main observations are: 1. The fairness and accuracy of many standard fair classifiers degrade severely as the bias injected in their training data increases, 2. A simple logistic regression model trained on the right data can often outperform, in both accuracy and fairness, most fair classifiers trained on biased training data, and 3. A few, simple fairness techniques (e.g., reweighing, exponentiated gradients) seem to offer stable accuracy and fairness guarantees even when their training data is injected with under-representation and label bias. Our experiments also show how to integrate a measure of data bias risk in the existing fairness dashboards for real-world deployments.
An Extended Sequence Tagging Vocabulary for Grammatical Error Correction
Venue: arXiv cs.CL 2023
Year: 2023

We extend a current sequence-tagging approach to Grammatical Error Correction (GEC) by introducing specialised tags for spelling correction and morphological inflection using the SymSpell and LemmInflect algorithms. Our approach improves generalisation: the proposed new tagset allows a smaller number of tags to correct a larger range of errors. Our results show a performance improvement both overall and in the targeted error categories. We further show that ensembles trained with our new tagset outperform those trained with the baseline tagset on the public BEA benchmark.
Generalized Few-Shot Continual Learning with Contrastive Mixture of Adapters
Venue: arXiv cs.CV 2023
Year: 2023

The goal of Few-Shot Continual Learning (FSCL) is to incrementally learn novel tasks with limited labeled samples and preserve previous capabilities simultaneously, while current FSCL methods are all for the class-incremental purpose. Moreover, the evaluation of FSCL solutions is only the cumulative performance of all encountered tasks, but there is no work on exploring the domain generalization ability. Domain generalization is a challenging yet practical task that aims to generalize beyond training domains. In this paper, we set up a Generalized FSCL (GFSCL) protocol involving both class- and domain-incremental situations together with the domain generalization assessment. Firstly, two benchmark datasets and protocols are newly arranged, and detailed baselines are provided for this unexplored configuration. We find that common continual learning methods have poor generalization ability on unseen domains and cannot better cope with the catastrophic forgetting issue in cross-incremental tasks. In this way, we further propose a rehearsal-free framework based on Vision Transformer (ViT) named Contrastive Mixture of Adapters (CMoA). Due to different optimization targets of class increment and domain increment, the CMoA contains two parts: (1) For the class-incremental issue, the Mixture of Adapters (MoA) module is incorporated into ViT, then cosine similarity regularization and the dynamic weighting are designed to make each adapter learn specific knowledge and concentrate on particular classes. (2) For the domain-related issues and domain-invariant representation learning, we alleviate the inner-class variation by prototype-calibrated contrastive learning. The codes and protocols are available at https://github.com/yawencui/CMoA.
SpReME: Sparse Regression for Multi-Environment Dynamic Systems
Venue: arXiv cs.LG 2023
Year: 2023

Learning dynamical systems is a promising avenue for scientific discoveries. However, capturing the governing dynamics in multiple environments still remains a challenge: model-based approaches rely on the fidelity of assumptions made for a single environment, whereas data-driven approaches based on neural networks are often fragile on extrapolating into the future. In this work, we develop a method of sparse regression dubbed SpReME to discover the major dynamics that underlie multiple environments. Specifically, SpReME shares a sparse structure of ordinary differential equation (ODE) across different environments in common while allowing each environment to keep the coefficients of ODE terms independently. We demonstrate that the proposed model captures the correct dynamics from multiple environments over four different dynamic systems with improved prediction performance.
Infinite Lewis Weights in Spectral Graph Theory
Venue: arXiv cs.DS 2023
Year: 2023

We study the spectral implications of re-weighting a graph by the $\ell_\infty$-Lewis weights of its edges. Our main motivation is the ER-Minimization problem (Saberi et al., SIAM'08): Given an undirected graph $G$, the goal is to find positive normalized edge-weights $w\in \mathbb{R}_+^m$ which minimize the sum of pairwise \emph{effective-resistances} of $G_w$ (Kirchhoff's index). By contrast, $\ell_\infty$-Lewis weights minimize the \emph{maximum} effective-resistance of \emph{edges}, but are much cheaper to approximate, especially for Laplacians. With this algorithmic motivation, we study the ER-approximation ratio obtained by Lewis weights. Our first main result is that $\ell_\infty$-Lewis weights provide a constant ($\approx 3.12$) approximation for ER-minimization on \emph{trees}. The proof introduces a new technique, a local polarization process for effective-resistances ($\ell_2$-congestion) on trees, which is of independent interest in electrical network analysis. For general graphs, we prove an upper bound $α(G)$ on the approximation ratio obtained by Lewis weights, which is always $\leq \min\{ \text{diam}(G), κ(L_{w_\infty})\}$, where $κ$ is the condition number of the weighted Laplacian. All our approximation algorithms run in \emph{input-sparsity} time $\tilde{O}(m)$, a major improvement over Saberi et al.'s $O(m^{3.5})$ SDP for exact ER-minimization. Finally, we demonstrate the favorable effects of $\ell_\infty$-LW reweighting on the \emph{spectral-gap} of graphs and on their \emph{spectral-thinness} (Anari and Gharan, 2015). En-route to our results, we prove a weighted analogue of Mohar's classical bound on $λ_2(G)$, and provide a new characterization of leverage-scores of a matrix, as the gradient (w.r.t weights) of the volume of the enclosing ellipsoid.
ASR Bundestag: A Large-Scale political debate dataset in German
Venue: arXiv cs.CL 2023
Year: 2023

We present ASR Bundestag, a dataset for automatic speech recognition in German, consisting of 610 hours of aligned audio-transcript pairs for supervised training as well as 1,038 hours of unlabeled audio snippets for self-supervised learning, based on raw audio data and transcriptions from plenary sessions and committee meetings of the German parliament. In addition, we discuss utilized approaches for the automated creation of speech datasets and assess the quality of the resulting dataset based on evaluations and finetuning of a pre-trained state of the art model. We make the dataset publicly available, including all subsets.
Emotion Detection in Unfix-length-Context Conversation
Venue: arXiv cs.CL 2023
Year: 2023

We leverage different context windows when predicting the emotion of different utterances. New modules are included to realize variable-length context: 1) two speaker-aware units, which explicitly model inner- and inter-speaker dependencies to form distilled conversational context, and 2) a top-k normalization layer, which determines the most proper context windows from the conversational context to predict emotion. Experiments and ablation studies show that our approach outperforms several strong baselines on three public datasets.
Time-to-event modeling of subreddits transitions to r/SuicideWatch
Venue: arXiv cs.SI 2023
Year: 2023

Recent data mining research has focused on the analysis of social media text, content and networks to identify suicide ideation online. However, there has been limited research on the temporal dynamics of users and suicide ideation. In this work, we use time-to-event modeling to identify which subreddits have a higher association with users transitioning to posting on r/suicidewatch. For this purpose we use a Cox proportional hazards model that takes as input text and subreddit network features and outputs a probability distribution for the time until a Reddit user posts on r/suicidewatch. In our analysis we find a number of statistically significant features that predict earlier transitions to r/suicidewatch. While some patterns match existing intuition, for example r/depression is positively associated with posting sooner on r/suicidewatch, others were more surprising (for example, the average time between a high risk post on r/Wishlist and a post on r/suicidewatch is 10.2 days). We then discuss these results as well as directions for future research.
Generalizable End-to-End Deep Learning Frameworks for Real-Time Attitude Estimation Using 6DoF Inertial Measurement Units
Venue: arXiv cs.RO 2023
Year: 2023

This paper presents a novel end-to-end deep learning framework for real-time inertial attitude estimation using 6DoF IMU measurements. Inertial Measurement Units are widely used in various applications, including engineering and medical sciences. However, traditional filters used for attitude estimation suffer from poor generalization over different motion patterns and environmental disturbances. To address this problem, we propose two deep learning models that incorporate accelerometer and gyroscope readings as inputs. These models are designed to be generalized to different motion patterns, sampling rates, and environmental disturbances. Our models consist of convolutional neural network layers combined with Bi-Directional Long-Short Term Memory followed by a Fully Forward Neural Network to estimate the quaternion. We evaluate the proposed method on seven publicly available datasets, totaling more than 120 hours and 200 kilometers of IMU measurements. Our results show that the proposed method outperforms state-of-the-art methods in terms of accuracy and robustness. Additionally, our framework demonstrates superior generalization over various motion characteristics and sensor sampling rates. Overall, this paper provides a comprehensive and reliable solution for real-time inertial attitude estimation using 6DoF IMUs, which has significant implications for a wide range of applications.
Unsupervised Deep One-Class Classification with Adaptive Threshold based on Training Dynamics
Venue: arXiv cs.LG 2023
Year: 2023

One-class classification has been a prevailing method in building deep anomaly detection models under the assumption that a dataset consisting of normal samples is available. In practice, however, abnormal samples are often mixed in a training dataset, and they detrimentally affect the training of deep models, which limits their applicability. For robust normality learning of deep practical models, we propose an unsupervised deep one-class classification that learns normality from pseudo-labeled normal samples, i.e., outlier detection in single cluster scenarios. To this end, we propose a pseudo-labeling method by an adaptive threshold selected by ranking-based training dynamics. The experiments on 10 anomaly detection benchmarks show that our method effectively improves performance on anomaly detection by sizable margins.
Universal Online Optimization in Dynamic Environments via Uniclass Prediction
Venue: arXiv cs.LG 2023
Year: 2023

Recently, several universal methods have been proposed for online convex optimization which can handle convex, strongly convex and exponentially concave cost functions simultaneously. However, most of these algorithms have been designed with static regret minimization in mind, but this notion of regret may not be suitable for changing environments. To address this shortcoming, we propose a novel and intuitive framework for universal online optimization in dynamic environments. Unlike existing universal algorithms, our strategy does not rely on the construction of a set of experts and an accompanying meta-algorithm. Instead, we show that the problem of dynamic online optimization can be reduced to a uniclass prediction problem. By leaving the choice of uniclass loss function in the user's hands, they are able to control and optimize dynamic regret bounds, which in turn carry over into the original problem. To the best of our knowledge, this is the first paper proposing a universal approach with state-of-the-art dynamic regret guarantees even for general convex cost functions.
Lower Bounds for Possibly Divergent Probabilistic Programs
Venue: arXiv cs.LO 2023
Year: 2023

We present a new proof rule for verifying lower bounds on quantities of probabilistic programs. Our proof rule is not confined to almost-surely terminating programs -- as is the case for existing rules -- and can be used to establish non-trivial lower bounds on, e.g., termination probabilities and expected values, for possibly divergent probabilistic loops, e.g., the well-known three-dimensional random walk on a lattice.
Dynamic Simulation of Splashing Fluids
Venue: arXiv cs.GR 2023
Year: 2023

In this paper we describe a method for modeling the dynamic behavior of splashing fluids. The model simulates the behavior of a fluid when objects impact or float on its surface. The forces generated by the objects create waves and splashes on the surface of the fluid. To demonstrate the realism and limitations of the model, images from a computer-generated animation are presented and compared with video frames of actual splashes occurring under similar initial conditions.