OpenRaiser/Intern-Atlas huggingface dataset:
The Complexity of Matching Games: A Survey
Venue: arXiv cs.GT 2023
Year: 2023

Matching games naturally generalize assignment games, a well-known class of cooperative games. Interest in matching games has grown recently due to some breakthrough results and new applications. This state-of-the-art survey provides an overview of matching games and extensions, such as $b$-matching games and partitioned matching games; the latter originating from the emerging area of international kidney exchange. In this survey we focus on computational complexity aspects of various game-theoretical solution concepts, such as the core, nucleolus and Shapley value, when the input is restricted to a matching game or one if its variants.
Towards Best Practice of Interpreting Deep Learning Models for EEG-based Brain Computer Interfaces
Venue: arXiv cs.NE 2023
Year: 2023

As deep learning has achieved state-of-the-art performance for many tasks of EEG-based BCI, many efforts have been made in recent years trying to understand what have been learned by the models. This is commonly done by generating a heatmap indicating to which extent each pixel of the input contributes to the final classification for a trained model. Despite the wide use, it is not yet understood to which extent the obtained interpretation results can be trusted and how accurate they can reflect the model decisions. In order to fill this research gap, we conduct a study to evaluate different deep interpretation techniques quantitatively on EEG datasets. The results reveal the importance of selecting a proper interpretation technique as the initial step. In addition, we also find that the quality of the interpretation results is inconsistent for individual samples despite when a method with an overall good performance is used. Many factors, including model structure and dataset types, could potentially affect the quality of the interpretation results. Based on the observations, we propose a set of procedures that allow the interpretation results to be presented in an understandable and trusted way. We illustrate the usefulness of our method for EEG-based BCI with instances selected from different scenarios.
A Survey on Dynamic Neural Networks for Natural Language Processing
Venue: arXiv cs.CL 2023
Year: 2023

Effectively scaling large Transformer models is a main driver of recent advances in natural language processing. Dynamic neural networks, as an emerging research direction, are capable of scaling up neural networks with sub-linear increases in computation and time by dynamically adjusting their computational path based on the input. Dynamic neural networks could be a promising solution to the growing parameter numbers of pretrained language models, allowing both model pretraining with trillions of parameters and faster inference on mobile devices. In this survey, we summarize progress of three types of dynamic neural networks in NLP: skimming, mixture of experts, and early exit. We also highlight current challenges in dynamic neural networks and directions for future research.
Enhancing Cross-lingual Prompting with Dual Prompt Augmentation
Venue: arXiv cs.CL 2023
Year: 2023

Prompting shows promising results in few-shot scenarios. However, its strength for multilingual/cross-lingual problems has not been fully exploited. Zhao and Schütze (2021) made initial explorations in this direction by presenting that cross-lingual prompting outperforms cross-lingual finetuning. In this paper, we conduct an empirical exploration on the effect of each component in cross-lingual prompting and derive language-agnostic Universal Prompting, which helps alleviate the discrepancies between source-language training and target-language inference. Based on this, we propose DPA, a dual prompt augmentation framework, aiming at relieving the data scarcity issue in few-shot cross-lingual prompting. Notably, for XNLI, our method achieves 46.54% with only 16 English training examples per class, significantly better than 34.99% of finetuning. Our code is available at https://github.com/DAMO-NLP-SG/DPA.
Mathematical Cookbook for Snapshot Compressive Imaging
Venue: arXiv cs.CV 2023
Year: 2023

The author intends to provide you with a beautiful, elegant, user-friendly cookbook for mathematics in Snapshot Compressive Imaging (SCI). Currently, the cookbook is composed of introduction, conventional optimization, and deep equilibrium models. The latest releases are strongly recommended! For any other questions, suggestions, or comments, feel free to email the author.
Inclusive Study Group Formation At Scale
Venue: arXiv cs.CY 2023
Year: 2023

Underrepresented students face many significant challenges in their education. In particular, they often have a harder time than their peers from majority groups in building long-term high-quality study groups. This challenge is exacerbated in remote-learning scenarios, where students are unable to meet face-to-face and must rely on pre-existing networks for social support. We present a scalable system that removes structural obstacles faced by underrepresented students and supports all students in building inclusive and flexible study groups. One of our main goals is to make the traditionally informal and unstructured process of finding study groups for homework more equitable by providing a uniform but lightweight structure. We aim to provide students from underrepresented groups an experience that is similar in quality to that of students from majority groups. Our process is unique in that it allows students the opportunity to request group reassignments during the semester if they wish. Unlike other collaboration tools our system is not mandatory and does not use peer-evaluation. We trialed our approach in a 1000+ student introductory Engineering and Computer Science course that was conducted entirely online during the COVID-19 pandemic. We find that students from underrepresented backgrounds were more likely to ask for group-matching support compared to students from majority groups. At the same time, underrepresented students that we matched into study groups had group experiences that were comparable to students we matched from majority groups. B-range students in high-comfort and high-quality groups had improved learning outcomes.
Delving Deeper into Cross-lingual Visual Question Answering
Venue: arXiv cs.CL 2023
Year: 2023

Visual question answering (VQA) is one of the crucial vision-and-language tasks. Yet, existing VQA research has mostly focused on the English language, due to a lack of suitable evaluation resources. Previous work on cross-lingual VQA has reported poor zero-shot transfer performance of current multilingual multimodal Transformers with large gaps to monolingual performance, without any deeper analysis. In this work, we delve deeper into the different aspects of cross-lingual VQA, aiming to understand the impact of 1) modeling methods and choices, including architecture, inductive bias, fine-tuning; 2) learning biases: including question types and modality biases in cross-lingual setups. The key results of our analysis are: 1) We show that simple modifications to the standard training setup can substantially reduce the transfer gap to monolingual English performance, yielding +10 accuracy points over existing methods. 2) We analyze cross-lingual VQA across different question types of varying complexity for different multilingual multimodal Transformers, and identify question types that are the most difficult to improve on. 3) We provide an analysis of modality biases present in training data and models, revealing why zero-shot performance gaps remain for certain question types and languages.
Causal Process Mining from Relational Databases with Domain Knowledge
Venue: arXiv cs.DB 2023
Year: 2023

The plethora of algorithms in the research field of process mining builds on directly-follows relations. Even though various improvements have been made in the last decade, there are serious weaknesses of these relationships. Once events associated with different objects that relate with a cardinality of 1:N and N:M to each other, techniques based on directly-follows relations produce spurious relations, self-loops, and back-jumps. This is due to the fact that event sequence as described in classical event logs differs from event causation. In this paper, we address the research problem of representing the causal structure of process-related event data. To this end, we develop a new approach called Causal Process Mining. This approach renounces the use of flat event logs and considers relational databases of event data as an input. More specifically, we transform the relational data structures based on the Causal Process Template into what we call Causal Event Graph. We evaluate our approach and compare its outputs with techniques based on directly-follows relations in a case study with an European food production company. Our results demonstrate the benefits for enriching process mining with additional knowledge from the domain.
CADRE: A Cascade Deep Reinforcement Learning Framework for Vision-based Autonomous Urban Driving
Venue: arXiv cs.CV 2023
Year: 2023

Vision-based autonomous urban driving in dense traffic is quite challenging due to the complicated urban environment and the dynamics of the driving behaviors. Widely-applied methods either heavily rely on hand-crafted rules or learn from limited human experience, which makes them hard to generalize to rare but critical scenarios. In this paper, we present a novel CAscade Deep REinforcement learning framework, CADRE, to achieve model-free vision-based autonomous urban driving. In CADRE, to derive representative latent features from raw observations, we first offline train a Co-attention Perception Module (CoPM) that leverages the co-attention mechanism to learn the inter-relationships between the visual and control information from a pre-collected driving dataset. Cascaded by the frozen CoPM, we then present an efficient distributed proximal policy optimization framework to online learn the driving policy under the guidance of particularly designed reward functions. We perform a comprehensive empirical study with the CARLA NoCrash benchmark as well as specific obstacle avoidance scenarios in autonomous urban driving tasks. The experimental results well justify the effectiveness of CADRE and its superiority over the state-of-the-art by a wide margin.
Adaptive Experimentation in the Presence of Exogenous Nonstationary Variation
Venue: arXiv cs.LG 2023
Year: 2023

We investigate experiments that are designed to select a treatment arm for population deployment. Multi-armed bandit algorithms can enhance efficiency by dynamically allocating measurement effort towards higher performing arms based on observed feedback. However, such dynamics can result in brittle behavior in the face of nonstationary exogenous factors influencing arms' performance during the experiment. To counter this, we propose deconfounded Thompson sampling (DTS), a more robust variant of the prominent Thompson sampling algorithm. As observations accumulate, DTS projects the population-level performance of an arm while controlling for the context within which observed treatment decisions were made. Contexts here might capture a comprehensible source of variation, such as the country of a treated individual, or simply record the time of treatment. We provide bounds on both within-experiment and post-experiment regret of DTS, illustrating its resilience to exogenous variation and the delicate balance it strikes between exploration and exploitation. Our proofs leverage inverse propensity weights to analyze the evolution of the posterior distribution, a departure from established methods in the literature. Hinting that new understanding is indeed necessary, we show that a deconfounded variant of the popular upper confidence bound algorithm can fail completely.
Learning Physics-Informed Neural Networks without Stacked Back-propagation
Venue: arXiv cs.LG 2023
Year: 2023

Physics-Informed Neural Network (PINN) has become a commonly used machine learning approach to solve partial differential equations (PDE). But, facing high-dimensional secondorder PDE problems, PINN will suffer from severe scalability issues since its loss includes second-order derivatives, the computational cost of which will grow along with the dimension during stacked back-propagation. In this work, we develop a novel approach that can significantly accelerate the training of Physics-Informed Neural Networks. In particular, we parameterize the PDE solution by the Gaussian smoothed model and show that, derived from Stein's Identity, the second-order derivatives can be efficiently calculated without back-propagation. We further discuss the model capacity and provide variance reduction methods to address key limitations in the derivative estimation. Experimental results show that our proposed method can achieve competitive error compared to standard PINN training but is significantly faster. Our code is released at https://github.com/LithiumDA/PINN-without-Stacked-BP.
Deep Learning for Hate Speech Detection: A Comparative Study
Venue: arXiv cs.CL 2023
Year: 2023

Automated hate speech detection is an important tool in combating the spread of hate speech, particularly in social media. Numerous methods have been developed for the task, including a recent proliferation of deep-learning based approaches. A variety of datasets have also been developed, exemplifying various manifestations of the hate-speech detection problem. We present here a large-scale empirical comparison of deep and shallow hate-speech detection methods, mediated through the three most commonly used datasets. Our goal is to illuminate progress in the area, and identify strengths and weaknesses in the current state-of-the-art. We particularly focus our analysis on measures of practical performance, including detection accuracy, computational efficiency, capability in using pre-trained models, and domain generalization. In doing so we aim to provide guidance as to the use of hate-speech detection in practice, quantify the state-of-the-art, and identify future research directions. Code and dataset are available at https://github.com/jmjmalik22/Hate-Speech-Detection.
On the best lattice quantizers
Venue: arXiv cs.IT 2023
Year: 2023

A lattice quantizer approximates an arbitrary real-valued source vector with a vector taken from a specific discrete lattice. The quantization error is the difference between the source vector and the lattice vector. In a classic 1996 paper, Zamir and Feder show that the globally optimal lattice quantizer (which minimizes the mean square error) has white quantization error: for a uniformly distributed source, the covariance of the error is the identity matrix, multiplied by a positive real factor. We generalize the theorem, showing that the same property holds (i) for any lattice whose mean square error cannot be decreased by a small perturbation of the generator matrix, and (ii) for an optimal product of lattices that are themselves locally optimal in the sense of (i). We derive an upper bound on the normalized second moment (NSM) of the optimal lattice in any dimension, by proving that any lower- or upper-triangular modification to the generator matrix of a product lattice reduces the NSM. Using these tools and employing the best currently known lattice quantizers to build product lattices, we construct improved lattice quantizers in dimensions 13 to 15, 17 to 23, and 25 to 48. In some dimensions, these are the first reported lattices with normalized second moments below the best known upper bound.
Evaluation of Neuromorphic Spike Encoding of Sound Using Information Theory
Venue: arXiv cs.SD 2023
Year: 2023

The problem of spike encoding of sound consists in transforming a sound waveform into spikes. It is of interest in many domains, including the development of audio-based spiking neural networks, where it is the first and most crucial stage of processing. Many algorithms have been proposed to perform spike encoding of sound. However, a systematic approach to quantitatively evaluate their performance is currently lacking. We propose the use of an information-theoretic framework to solve this problem. Specifically, we evaluate the coding efficiency of four spike encoding algorithms on two coding tasks that consist of coding the fundamental characteristics of sound: frequency and amplitude. The algorithms investigated are: Independent Spike Coding, Send-on-Delta coding, Ben's Spiker Algorithm, and Leaky Integrate-and-Fire coding. Using the tools of information theory, we estimate the information that the spikes carry on relevant aspects of an input stimulus. We find disparities in the coding efficiencies of the algorithms, where Leaky Integrate-and-Fire coding performs best. The information-theoretic analysis of their performance on these coding tasks provides insight on the encoding of richer and more complex sound stimuli.
Accountable Javascript Code Delivery
Venue: arXiv cs.CR 2023
Year: 2023

The internet is a major distribution platform for web applications, but there are no effective transparency and audit mechanisms in place for the web. Due to the ephemeral nature of web applications, a client visiting a website has no guarantee that the code it receives today is the same as yesterday, or the same as other visitors receive. Despite advances in web security, it is thus challenging to audit web applications before they are rendered in the browser. We propose Accountable JS, a browser extension and opt in protocol for accountable delivery of active content on a web page. We prototype our protocol, formally model its security properties with the Tamarin Prover, and evaluate its compatibility and performance impact with case studies including WhatsApp Web, AdSense and Nimiq. Accountability is beginning to be deployed at scale, with Meta's recent announcement of Code Verify available to all 2 billion WhatsApp users, but there has been little formal analysis of such protocols. We formally model Code Verify using the Tamarin Prover and compare its properties to our Accountable JS protocol. We also compare Code Verify's and Accountable JS extension's performance impacts on WhatsApp Web.
$\mathcal{Y}$-Tuning: An Efficient Tuning Paradigm for Large-Scale Pre-Trained Models via Label Representation Learning
Venue: arXiv cs.CL 2023
Year: 2023

With the success of large-scale pre-trained models (PTMs), how efficiently adapting PTMs to downstream tasks has attracted tremendous attention, especially for PTMs with billions of parameters. Although some parameter-efficient tuning paradigms have been proposed to address this problem, they still require large resources to compute the gradients in the training phase. In this paper, we propose $\mathcal{Y}$-Tuning, an efficient yet effective paradigm to adapt frozen large-scale PTMs to specific downstream tasks. $\mathcal{Y}$-tuning learns dense representations for labels $\mathcal{Y}$ defined in a given task and aligns them to fixed feature representation. Without tuning the features of input text and model parameters, $\mathcal{Y}$-tuning is both parameter-efficient and training-efficient. For $\text{DeBERTa}_\text{XXL}$ with 1.6 billion parameters, $\mathcal{Y}$-tuning achieves performance more than $96\%$ of full fine-tuning on GLUE Benchmark with only $2\%$ tunable parameters and much fewer training costs.
Redundancy Resolution at Position Level
Venue: arXiv cs.RO 2023
Year: 2023

Increasing the degrees of freedom of robotic systems makes them more versatile and flexible. This usually renders the system kinematically redundant: the main manipulation or interaction task does not fully determine its joint maneuvers. Additional constraints or objectives are required to solve the under-determined control and planning problems. The state-of-the-art approaches arrange tasks in a hierarchy and decouple lower from higher priority tasks on velocity or torque level using projectors. We develop an approach to redundancy resolution and decoupling on position level by determining subspaces of the configurations space independent of the primary task. We call them \emph{orthogonal foliations} because they are, in a certain sense, orthogonal to the task self-motion manifolds. The approach provides a better insight into the topological properties of robot kinematics and control problems, allowing a global view. A condition for the existence of orthogonal foliations is derived. If the condition is not satisfied, we will still find approximate solutions by numerical optimization. Coordinates can be defined on these orthogonal foliations and can be used as additional task variables for control. We show in simulations that we can control the system without the need for projectors using these coordinates, and we validate the approach experimentally on a 7-DoF robot.
Berman Codes: A Generalization of Reed-Muller Codes that Achieve BEC Capacity
Venue: arXiv cs.IT 2023
Year: 2023

We identify a family of binary codes whose structure is similar to Reed-Muller (RM) codes and which include RM codes as a strict subclass. The codes in this family are denoted as $C_n(r,m)$, and their duals are denoted as $B_n(r,m)$. The length of these codes is $n^m$, where $n \geq 2$, and $r$ is their `order'. When $n=2$, $C_n(r,m)$ is the RM code of order $r$ and length $2^m$. The special case of these codes corresponding to $n$ being an odd prime was studied by Berman (1967) and Blackmore and Norton (2001). Following the terminology introduced by Blackmore and Norton, we refer to $B_n(r,m)$ as the Berman code and $C_n(r,m)$ as the dual Berman code. We identify these codes using a recursive Plotkin-like construction, and we show that these codes have a rich automorphism group, they are generated by the minimum weight codewords, and that they can be decoded up to half the minimum distance efficiently. Using a result of Kumar et al. (2016), we show that these codes achieve the capacity of the binary erasure channel (BEC) under bit-MAP decoding. Furthermore, except double transitivity, they satisfy all the code properties used by Reeves and Pfister to show that RM codes achieve the capacity of binary-input memoryless symmetric channels. Finally, when $n$ is odd, we identify a large class of abelian codes that includes $B_n(r,m)$ and $C_n(r,m)$ and which achieves BEC capacity.
VRL3: A Data-Driven Framework for Visual Deep Reinforcement Learning
Venue: arXiv cs.CV 2023
Year: 2023

We propose VRL3, a powerful data-driven framework with a simple design for solving challenging visual deep reinforcement learning (DRL) tasks. We analyze a number of major obstacles in taking a data-driven approach, and present a suite of design principles, novel findings, and critical insights about data-driven visual DRL. Our framework has three stages: in stage 1, we leverage non-RL datasets (e.g. ImageNet) to learn task-agnostic visual representations; in stage 2, we use offline RL data (e.g. a limited number of expert demonstrations) to convert the task-agnostic representations into more powerful task-specific representations; in stage 3, we fine-tune the agent with online RL. On a set of challenging hand manipulation tasks with sparse reward and realistic visual inputs, compared to the previous SOTA, VRL3 achieves an average of 780% better sample efficiency. And on the hardest task, VRL3 is 1220% more sample efficient (2440% when using a wider encoder) and solves the task with only 10% of the computation. These significant results clearly demonstrate the great potential of data-driven deep reinforcement learning.