OpenRaiser/Intern-Atlas huggingface dataset:
Existential Second-Order Logic Over Graphs: Parameterized Complexity
Venue: arXiv cs.LO 2023
Year: 2023

By Fagin's Theorem, NP contains precisely those problems that can be described by formulas starting with an existential second-order quantifier, followed by only first-order quantifiers (ESO formulas). Subsequent research refined this result, culminating in powerful theorems that characterize for each possible sequence of first-order quantifiers how difficult the described problem can be. We transfer this line of inquiry to the parameterized setting, where the size of the set quantified by the second-order quantifier is the parameter. Many natural parameterized problems can be described in this way using simple sequences of first-order quantifiers: For the clique or vertex cover problems, two universal first-order quantifiers suffice ("for all pairs of vertices ... must hold"); for the dominating set problem, a universal followed by an existential quantifier suffice ("for all vertices, there is a vertex such that ..."); and so on. We present a complete characterization that states for each possible sequence of first-order quantifiers how high the parameterized complexity of the described problems can be. The uncovered dividing line between quantifier sequences that lead to tractable versus intractable problems is distinct from that known from the classical setting, and it depends on whether the parameter is a lower bound on, an upper bound on, or equal to the size of the quantified set.
NewsRecLib: A PyTorch-Lightning Library for Neural News Recommendation
Venue: arXiv cs.IR 2023
Year: 2023

NewsRecLib is an open-source library based on Pytorch-Lightning and Hydra developed for training and evaluating neural news recommendation models. The foremost goals of NewsRecLib are to promote reproducible research and rigorous experimental evaluation by (i) providing a unified and highly configurable framework for exhaustive experimental studies and (ii) enabling a thorough analysis of the performance contribution of different model architecture components and training regimes. NewsRecLib is highly modular, allows specifying experiments in a single configuration file, and includes extensive logging facilities. Moreover, NewsRecLib provides out-of-the-box implementations of several prominent neural models, training methods, standard evaluation benchmarks, and evaluation metrics for news recommendation.
RRR-Net: Reusing, Reducing, and Recycling a Deep Backbone Network
Venue: arXiv cs.LG 2023
Year: 2023

It has become mainstream in computer vision and other machine learning domains to reuse backbone networks pre-trained on large datasets as preprocessors. Typically, the last layer is replaced by a shallow learning machine of sorts; the newly-added classification head and (optionally) deeper layers are fine-tuned on a new task. Due to its strong performance and simplicity, a common pre-trained backbone network is ResNet152.However, ResNet152 is relatively large and induces inference latency. In many cases, a compact and efficient backbone with similar performance would be preferable over a larger, slower one. This paper investigates techniques to reuse a pre-trained backbone with the objective of creating a smaller and faster model. Starting from a large ResNet152 backbone pre-trained on ImageNet, we first reduce it from 51 blocks to 5 blocks, reducing its number of parameters and FLOPs by more than 6 times, without significant performance degradation. Then, we split the model after 3 blocks into several branches, while preserving the same number of parameters and FLOPs, to create an ensemble of sub-networks to improve performance. Our experiments on a large benchmark of $40$ image classification datasets from various domains suggest that our techniques match the performance (if not better) of ``classical backbone fine-tuning'' while achieving a smaller model size and faster inference speed.
DINE: Dimensional Interpretability of Node Embeddings
Venue: arXiv cs.LG 2023
Year: 2023

Graphs are ubiquitous due to their flexibility in representing social and technological systems as networks of interacting elements. Graph representation learning methods, such as node embeddings, are powerful approaches to map nodes into a latent vector space, allowing their use for various graph tasks. Despite their success, only few studies have focused on explaining node embeddings locally. Moreover, global explanations of node embeddings remain unexplored, limiting interpretability and debugging potentials. We address this gap by developing human-understandable explanations for dimensions in node embeddings. Towards that, we first develop new metrics that measure the global interpretability of embedding vectors based on the marginal contribution of the embedding dimensions to predicting graph structure. We say that an embedding dimension is more interpretable if it can faithfully map to an understandable sub-structure in the input graph - like community structure. Having observed that standard node embeddings have low interpretability, we then introduce DINE (Dimension-based Interpretable Node Embedding), a novel approach that can retrofit existing node embeddings by making them more interpretable without sacrificing their task performance. We conduct extensive experiments on synthetic and real-world graphs and show that we can simultaneously learn highly interpretable node embeddings with effective performance in link prediction.
Segment Any Building
Venue: arXiv cs.CV 2023
Year: 2023

The task of identifying and segmenting buildings within remote sensing imagery has perennially stood at the forefront of scholarly investigations. This manuscript accentuates the potency of harnessing diversified datasets in tandem with cutting-edge representation learning paradigms for building segmentation in such images. Through the strategic amalgamation of disparate datasets, we have not only expanded the informational horizon accessible for model training but also manifested unparalleled performance metrics across multiple datasets. Our avant-garde joint training regimen underscores the merit of our approach, bearing significant implications in pivotal domains such as urban infrastructural development, disaster mitigation strategies, and ecological surveillance. Our methodology, predicated upon the fusion of datasets and gleaning insights from pre-trained models, carves a new benchmark in the annals of building segmentation endeavors. The outcomes of this research both fortify the foundations for ensuing scholarly pursuits and presage a horizon replete with innovative applications in the discipline of building segmentation.
Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via Planning and Learning
Venue: arXiv cs.AI 2023
Year: 2023

Multi-agent Pathfinding (MAPF) problem generally asks to find a set of conflict-free paths for a set of agents confined to a graph and is typically solved in a centralized fashion. Conversely, in this work, we investigate the decentralized MAPF setting, when the central controller that posses all the information on the agents' locations and goals is absent and the agents have to sequientially decide the actions on their own without having access to a full state of the environment. We focus on the practically important lifelong variant of MAPF, which involves continuously assigning new goals to the agents upon arrival to the previous ones. To address this complex problem, we propose a method that integrates two complementary approaches: planning with heuristic search and reinforcement learning through policy optimization. Planning is utilized to construct and re-plan individual paths. We enhance our planning algorithm with a dedicated technique tailored to avoid congestion and increase the throughput of the system. We employ reinforcement learning to discover the collision avoidance policies that effectively guide the agents along the paths. The policy is implemented as a neural network and is effectively trained without any reward-shaping or external guidance. We evaluate our method on a wide range of setups comparing it to the state-of-the-art solvers. The results show that our method consistently outperforms the learnable competitors, showing higher throughput and better ability to generalize to the maps that were unseen at the training stage. Moreover our solver outperforms a rule-based one in terms of throughput and is an order of magnitude faster than a state-of-the-art search-based solver.
Enabling predictable parallelism in single-GPU systems with persistent CUDA threads
Venue: arXiv cs.DC 2023
Year: 2023

Graphics Processing Unit, or GPUs, have been successfully adopted both for graphic computation in 3D applications, and for general purpose application (GP-GPUs), thank to their tremendous performance-per-watt. Recently, there is a big interest in adopting them also within automotive and avionic industrial settings, imposing for the first time real-time constraints on the design of such devices. Unfortunately, it is extremely hard to extract timing guarantees from modern GPU designs, and current approaches rely on a model where the GPU is treated as a unique monolithic execution device. Unlike state-of-the-art of research, we try to open the box of modern GPU architectures, providing a clean way to exploit intra-GPU predictable execution.
Cell-Free Bistatic Backscatter Communication: Channel Estimation, Optimization, and Performance Analysis
Venue: arXiv cs.IT 2023
Year: 2023

This study introduces and investigates the integration of a cell-free architecture with bistatic backscatter communication (BiBC), referred to as cell-free BiBC or distributed access point (AP)-assisted BiBC, which can enable potential applications in future (EH)-based Internet-of-Things (IoT) networks. To that purpose, we first present a pilot-based channel estimation scheme for estimating the direct, cascaded, forward channels of the proposed system setup. We next utilize the channel estimates for designing the optimal beamforming weights at the APs, reflection coefficients at the tags, and reception filters at the reader to maximize the tag sum rate while meeting the tags' minimum energy requirements. Because the proposed maximization problem is non-convex, we propose a solution based on alternative optimization, fractional programming, and Rayleigh quotient techniques. We also quantify the computational complexity of the developed algorithms. Finally, we present extensive numerical results to validate the proposed channel estimation scheme and optimization framework, as well as the performance of the integration of these two technologies. Compared to the random beamforming/combining benchmark, our algorithm yields impressive gains. For example, it achieves $\sim$ 64.8\% and $\sim$ 253.5\% gains in harvested power and tag sum rate, respectively, for 10 dBm with 36 APs and 3 tags.
Short Time Angular Impulse Response of Rayleigh Beams
Venue: arXiv cs.CE 2023
Year: 2023

In the dynamics of linear structures, the impulse response function is of fundamental interest. In some cases one examines the short term response wherein the disturbance is still local and the boundaries have not yet come into play, and for such short-time analysis the geometrical extent of the structure may be taken as unbounded. Here we examine the response of slender beams to angular impulses. The Euler-Bernoulli model, which does not include rotary inertia of cross sections, predicts an unphysical and unbounded initial rotation at the point of application. A finite length Euler-Bernoulli beam, when modelled using finite elements, predicts a mesh-dependent response that shows fast large-amplitude oscillations setting in very quickly. The simplest introduction of rotary inertia yields the Rayleigh beam model, which has more reasonable behaviour including a finite wave speed at all frequencies. If a Rayleigh beam is given an impulsive moment at a location away from its boundaries, then the predicted behaviour has an instantaneous finite jump in local slope or rotation, followed by smooth evolution of the slope for a finite time interval until reflections arrive from the boundary, causing subsequent slope discontinuities in time. We present a detailed study of the angular impulse response of a simply supported Rayleigh beam, starting with dimensional analysis, followed by modal expansion including all natural frequencies, culminating with an asymptotic formula for the short-time response. The asymptotic formula is obtained by breaking the series solution into two parts to be treated independently term by term, and leads to a polynomial in time. The polynomial matches the response from refined finite element (FE) simulations.
Elephant Neural Networks: Born to Be a Continual Learner
Venue: arXiv cs.LG 2023
Year: 2023

Catastrophic forgetting remains a significant challenge to continual learning for decades. While recent works have proposed effective methods to mitigate this problem, they mainly focus on the algorithmic side. Meanwhile, we do not fully understand what architectural properties of neural networks lead to catastrophic forgetting. This study aims to fill this gap by studying the role of activation functions in the training dynamics of neural networks and their impact on catastrophic forgetting. Our study reveals that, besides sparse representations, the gradient sparsity of activation functions also plays an important role in reducing forgetting. Based on this insight, we propose a new class of activation functions, elephant activation functions, that can generate both sparse representations and sparse gradients. We show that by simply replacing classical activation functions with elephant activation functions, we can significantly improve the resilience of neural networks to catastrophic forgetting. Our method has broad applicability and benefits for continual learning in regression, class incremental learning, and reinforcement learning tasks. Specifically, we achieves excellent performance on Split MNIST dataset in just one single pass, without using replay buffer, task boundary information, or pre-training.
Type-Based Verification of Delegated Control in Hybrid~Systems (Full Version)
Venue: arXiv cs.PL 2023
Year: 2023

We present a post-region-based verification system for distributed hybrid systems modeled with Hybrid Active Objects. The post-region of a class method is the region of the state space where a physical process must be proven safe to ensure some object invariant. Prior systems computed the post-region locally to a single object and could only verify systems where each object ensures its own safety, or relied on specific, non-modular communication patterns. The system presented here uses a type-and-effect system to structure the interactions between objects and computes post-regions globally, but verifies them locally. Furthermore, we are able to handle systems with delegated control: the object and method that shape the post-region change over time. We exemplify our approach with a model of a cloud-based hybrid system.
It's MBR All the Way Down: Modern Generation Techniques Through the Lens of Minimum Bayes Risk
Venue: arXiv cs.CL 2023
Year: 2023

Minimum Bayes Risk (MBR) decoding is a method for choosing the outputs of a machine learning system based not on the output with the highest probability, but the output with the lowest risk (expected error) among multiple candidates. It is a simple but powerful method: for an additional cost at inference time, MBR provides reliable several-point improvements across metrics for a wide variety of tasks without any additional data or training. Despite this, MBR is not frequently applied in NLP works, and knowledge of the method itself is limited. We first provide an introduction to the method and the recent literature. We show that several recent methods that do not reference MBR can be written as special cases of MBR; this reformulation provides additional theoretical justification for the performance of these methods, explaining some results that were previously only empirical. We provide theoretical and empirical results about the effectiveness of various MBR variants and make concrete recommendations for the application of MBR in NLP models, including future directions in this area.
The Impact of COVID-19 on Chronic Pain: Multidimensional Clustering Reveals Deep Insights into Spinal Cord Stimulation Patients
Venue: arXiv cs.CE 2023
Year: 2023

The emergence of COVID-19 offered a unique opportunity to study chronic pain patients as they responded to sudden changes in social environments, increased community stress, and reduced access to care. We report findings from n=70 Spinal Cord Stimulation (SCS) patients before and during initial pandemic stages resulting from advances in home monitoring and artificial intelligence that produced novel insights despite pandemic-related disruptions. From a multi-dimensional array of frequently monitored signals-including mobility, sleep, voice, and psychological assessments-we found that while the overall patient cohort appeared unaffected by the pandemic onset, patients had significantly different individual experiences. Three distinct patient responses (sub-cohorts) were revealed, those with: worsened pain, reduced activities, or improved quality of life. Remarkably, none of the specific measures by themselves were significantly affected; instead, it was their synergy that exposed the effects elicited by the pandemic onset. Partial correlations illustrating linked dimensions by sub-cohort during the pandemic and those associations were different for each sub-cohort before COVID-19, suggesting that daily at-home tele-monitoring of chronic conditions may reveal novel patient types. This work highlights the opportunities afforded by applying modern analytic techniques to more holistic and longitudinal patient outcomes, which might aid clinicians in making more informed treatment decisions in the future.
Cordyceps@LT-EDI: Depression Detection with Reddit and Self-training
Venue: arXiv cs.CL 2023
Year: 2023

Depression is debilitating, and not uncommon. Indeed, studies of excessive social media users show correlations with depression, ADHD, and other mental health concerns. Given that there is a large number of people with excessive social media usage, then there is a significant population of potentially undiagnosed users and posts that they create. In this paper, we propose a depression severity detection system using a semi-supervised learning technique to predict if a post is from a user who is experiencing severe, moderate, or low (non-diagnostic) levels of depression. Namely, we use a trained model to classify a large number of unlabelled social media posts from Reddit, then use these generated labels to train a more powerful classifier. We demonstrate our framework on Detecting Signs of Depression from Social Media Text - LT-EDI@RANLP 2023 shared task, where our framework ranks 3rd overall.
Service Pet Robot Design: Queer, Feminine and Sexuality Aspects
Venue: arXiv cs.RO 2023
Year: 2023

The integration of robots and AI in society raises concerns about discrimination and biases mostly affecting underrepresented groups, including queer and feminine figures. Socially assistive robots (SAR) are being used in a variety of service and companion roles, following social norms during their interaction with humans and seem to be beneficial in many roles, such as the pet therapy robots. To promote inclusion and representation, robot design should incorporate queer and feminine characteristics. As a response to these concerns, a pet robot called BB was designed using a multidisciplinary and inclusive approach. BB was presented in a queer architecture and aesthetics environment, emphasizing aspects of techno-touch, vulnerability, and sexuality in human-robot interactions. The audience's perception of both the robot and the female researcher was evaluated through questionnaires and focus groups. This study aims to explore how technology and design can better accommodate diverse perspectives and needs in the field of SAR.
Sarcasm in Sight and Sound: Benchmarking and Expansion to Improve Multimodal Sarcasm Detection
Venue: arXiv cs.CL 2023
Year: 2023

The introduction of the MUStARD dataset, and its emotion recognition extension MUStARD++, have identified sarcasm to be a multi-modal phenomenon -- expressed not only in natural language text, but also through manners of speech (like tonality and intonation) and visual cues (facial expression). With this work, we aim to perform a rigorous benchmarking of the MUStARD++ dataset by considering state-of-the-art language, speech, and visual encoders, for fully utilizing the totality of the multi-modal richness that it has to offer, achieving a 2\% improvement in macro-F1 over the existing benchmark. Additionally, to cure the imbalance in the `sarcasm type' category in MUStARD++, we propose an extension, which we call \emph{MUStARD++ Balanced}, benchmarking the same with instances from the extension split across both train and test sets, achieving a further 2.4\% macro-F1 boost. The new clips were taken from a novel source -- the TV show, House MD, which adds to the diversity of the dataset, and were manually annotated by multiple annotators with substantial inter-annotator agreement in terms of Cohen's kappa and Krippendorf's alpha. Our code, extended data, and SOTA benchmark models are made public.
UPAR: A Kantian-Inspired Prompting Framework for Enhancing Large Language Model Capabilities
Venue: arXiv cs.CL 2023
Year: 2023

Large Language Models (LLMs) have demonstrated impressive inferential capabilities, with numerous research endeavors devoted to enhancing this capacity through prompting. Despite these efforts, a unified epistemological foundation is still conspicuously absent. Drawing inspiration from Kant's a priori philosophy, we propose the UPAR prompting framework, designed to emulate the structure of human cognition within LLMs. The UPAR framework is delineated into four phases: "Understand", "Plan", "Act", and "Reflect", enabling the extraction of structured information from complex contexts, prior planning of solutions, execution according to plan, and self-reflection. This structure significantly augments the explainability and accuracy of LLM inference, producing a human-understandable and inspectable inferential trajectory. Furthermore, our work offers an epistemological foundation for existing prompting techniques, allowing for a possible systematic integration of these methods. With GPT-4, our approach elevates the accuracy from COT baseline of 22.92% to 58.33% in a challenging subset of GSM8K, and from 67.91% to 75.40% in the causal judgment task. Without using few-shot examples or external tools, UPAR significantly outperforms existing prompting methods on SCIBENCH, a challenging dataset containing collegiate-level mathematics, chemistry, and physics scientific problems.
Meta Semantic Template for Evaluation of Large Language Models
Venue: arXiv cs.CL 2023
Year: 2023

Do large language models (LLMs) genuinely understand the semantics of the language, or just memorize the training data? The recent concern on potential data contamination of LLMs has raised awareness of the community to conduct research on LLMs evaluation. In this paper, we propose MSTemp, an approach that creates meta semantic templates to evaluate the semantic understanding ability of LLMs. The core of MSTemp is not to perform evaluation directly on existing benchmark datasets, but to generate new out-of-distribution (OOD) evaluation sets using existing datasets as seeds. Specifically, for a given sentence, MSTemp leverages another language model to generate new samples while preserving its semantics. The new samples are called semantic templates to the original sentence. Then, MSTemp generates evaluation samples via sentence parsing and random word replacement on the semantic templates. MSTemp is highly flexible, dynamic, and cost-effective. Our initial experiments show that MSTemp-generated samples can significantly reduce the performance of LLMs using existing datasets as seeds. We hope this initial work can shed light on future research of LLMs evaluation.