OpenRaiser/Intern-Atlas huggingface dataset:
Near-optimality for infinite-horizon restless bandits with many arms
Venue: arXiv cs.LG 2022
Year: 2022

Restless bandits are an important class of problems with applications in recommender systems, active learning, revenue management and other areas. We consider infinite-horizon discounted restless bandits with many arms where a fixed proportion of arms may be pulled in each period and where arms share a finite state space. Although an average-case-optimal policy can be computed via stochastic dynamic programming, the computation required grows exponentially with the number of arms $N$. Thus, it is important to find scalable policies that can be computed efficiently for large $N$ and that are near optimal in this regime, in the sense that the optimality gap (i.e. the loss of expected performance against an optimal policy) per arm vanishes for large $N$. However, the most popular approach, the Whittle index, requires a hard-to-verify indexability condition to be well-defined and another hard-to-verify condition to guarantee a $o(N)$ optimality gap. We present a method resolving these difficulties. By replacing a global Lagrange multiplier used by the Whittle index with a sequence of Lagrangian multipliers, one per time period up to a finite truncation point, we derive a class of policies, called fluid-balance policies, that have a $O(\sqrt{N})$ optimality gap. Unlike the Whittle index, fluid-balance policies do not require indexability to be well-defined and their $O(\sqrt{N})$ optimality gap bound holds universally without sufficient conditions. We also demonstrate empirically that fluid-balance policies provide state-of-the-art performance on specific problems.
Restless Temporal Path Parameterized Above Lower Bounds
Venue: arXiv cs.DS 2022
Year: 2022

Reachability questions are one of the most fundamental algorithmic primitives in temporal graphs -- graphs whose edge set changes over discrete time steps. A core problem here is the NP-hard Short Restless Temporal Path: given a temporal graph $\mathcal G$, two distinct vertices $s$ and $z$, and two numbers $δ$ and $k$, is there a $δ$-restless temporal $s$-$z$ path of length at most $k$? A temporal path is a path whose edges appear in chronological order and a temporal path is $δ$-restless if two consecutive path edges appear at most $δ$ time steps apart from each other. Among others, this problem has applications in neuroscience and epidemiology. While Short Restless Temporal Path is known to be computationally hard, e.g., it is NP-hard for only three time steps and W[1]-hard when parameterized by the feedback vertex number of the underlying graph, it is fixed-parameter tractable when parameterized by the path length $k$. We improve on this by showing that Short Restless Temporal Path can be solved in (randomized) $4^{k-d}|\mathcal G|^{O(1)}$ time, where $d$ is the minimum length of a temporal $s$-$z$ path.
The root extraction problem in braid group-based cryptography
Venue: arXiv cs.CR 2022
Year: 2022

The root extraction problem in braid groups is the following: given a braid $β\in \mathcal{B}_n$ and a number $k\in \mathbb{N}$, find $α\in \mathcal{B}_n$ such that $α^k=β$. In the last decades, many cryptosystems such as authentication schemes and digital signatures based on the root extraction problem have been proposed. In this paper, we first describe these cryptosystems built around braid groups. Then we prove that, in general, these authentication schemes and digital signature are not secure by presenting for each of them a possible attack.
Leveraging Evolutionary Algorithms for Feasible Hexapod Locomotion Across Uneven Terrain
Venue: arXiv cs.RO 2022
Year: 2022

Optimizing gait stability for legged robots is a difficult problem. Even on level surfaces, effectively traversing across different textures (e.g., carpet) rests on dynamically tuning parameters in multidimensional space. Inspired by biology, evolutionary algorithms (EA) remain an attractive solution for feasibly implementing robotic locomotion with both energetic economy and rapid parameter convergence. Here, we leveraged this class of algorithms to evolve a stable hexapod gait controller capable of traversing uneven terrain and obstacles. Gait parameters were evolved in a rigid body dynamics simulation on an 8 x 3 meter obstacle course comprised of random step field, linear obstacles and inclined surfaces. Using a fitness function that jointly optimized locomotion velocity and stability, we found that multiple successful gait parameter evolutions yielded specialized functionality for each leg. Specific gait parameters were identified as critical to developing a rough terrain gait.
Entity-driven Fact-aware Abstractive Summarization of Biomedical Literature
Venue: arXiv cs.CL 2022
Year: 2022

As part of the large number of scientific articles being published every year, the publication rate of biomedical literature has been increasing. Consequently, there has been considerable effort to harness and summarize the massive amount of biomedical research articles. While transformer-based encoder-decoder models in a vanilla source document-to-summary setting have been extensively studied for abstractive summarization in different domains, their major limitations continue to be entity hallucination (a phenomenon where generated summaries constitute entities not related to or present in source article(s)) and factual inconsistency. This problem is exacerbated in a biomedical setting where named entities and their semantics (which can be captured through a knowledge base) constitute the essence of an article. The use of named entities and facts mined from background knowledge bases pertaining to the named entities to guide abstractive summarization has not been studied in biomedical article summarization literature. In this paper, we propose an entity-driven fact-aware framework for training end-to-end transformer-based encoder-decoder models for abstractive summarization of biomedical articles. We call the proposed approach, whose building block is a transformer-based model, EFAS, Entity-driven Fact-aware Abstractive Summarization. We conduct experiments using five state-of-the-art transformer-based models (two of which are specifically designed for long document summarization) and demonstrate that injecting knowledge into the training/inference phase of these models enables the models to achieve significantly better performance than the standard source document-to-summary setting in terms of entity-level factual accuracy, N-gram novelty, and semantic equivalence while performing comparably on ROUGE metrics. The proposed approach is evaluated on ICD-11-Summ-1000, and PubMed-50k.
Higher-Order Generalization Bounds: Learning Deep Probabilistic Programs via PAC-Bayes Objectives
Venue: arXiv cs.LG 2022
Year: 2022

Deep Probabilistic Programming (DPP) allows powerful models based on recursive computation to be learned using efficient deep-learning optimization techniques. Additionally, DPP offers a unified perspective, where inference and learning algorithms are treated on a par with models as stochastic programs. Here, we offer a framework for representing and learning flexible PAC-Bayes bounds as stochastic programs using DPP-based methods. In particular, we show that DPP techniques may be leveraged to derive generalization bounds that draw on the compositionality of DPP representations. In turn, the bounds we introduce offer principled training objectives for higher-order probabilistic programs. We offer a definition of a higher-order generalization bound, which naturally encompasses single- and multi-task generalization perspectives (including transfer- and meta-learning) and a novel class of bound based on a learned measure of model complexity. Further, we show how modified forms of all higher-order bounds can be efficiently optimized as objectives for DPP training, using variational techniques. We test our framework using single- and multi-task generalization settings on synthetic and biological data, showing improved performance and generalization prediction using flexible DPP model representations and learned complexity measures.
Does Configuration Encoding Matter in Learning Software Performance? An Empirical Study on Encoding Schemes
Venue: arXiv cs.SE 2022
Year: 2022

Learning and predicting the performance of a configurable software system helps to provide better quality assurance. One important engineering decision therein is how to encode the configuration into the model built. Despite the presence of different encoding schemes, there is still little understanding of which is better and under what circumstances, as the community often relies on some general beliefs that inform the decision in an ad-hoc manner. To bridge this gap, in this paper, we empirically compared the widely used encoding schemes for software performance learning, namely label, scaled label, and one-hot encoding. The study covers five systems, seven models, and three encoding schemes, leading to 105 cases of investigation. Our key findings reveal that: (1) conducting trial-and-error to find the best encoding scheme in a case by case manner can be rather expensive, requiring up to 400+ hours on some models and systems; (2) the one-hot encoding often leads to the most accurate results while the scaled label encoding is generally weak on accuracy over different models; (3) conversely, the scaled label encoding tends to result in the fastest training time across the models/systems while the one-hot encoding is the slowest; (4) for all models studied, label and scaled label encoding often lead to relatively less biased outcomes between accuracy and training time, but the paired model varies according to the system. We discuss the actionable suggestions derived from our findings, hoping to provide a better understanding of this topic for the community. To promote open science, the data and code of this work can be publicly accessed at https://github.com/ideas-labo/MSR2022-encoding-study.
Theory of Acceleration of Decision Making by Correlated Time Sequences
Venue: arXiv cs.LG 2022
Year: 2022

Photonic accelerators have been intensively studied to provide enhanced information processing capability to benefit from the unique attributes of physical processes. Recently, it has been reported that chaotically oscillating ultrafast time series from a laser, called laser chaos, provide the ability to solve multi-armed bandit (MAB) problems or decision-making problems at GHz order. Furthermore, it has been confirmed that the negatively correlated time-domain structure of laser chaos contributes to the acceleration of decision-making. However, the underlying mechanism of why decision-making is accelerated by correlated time series is unknown. In this study, we demonstrate a theoretical model to account for accelerating decision-making by correlated time sequence. We first confirm the effectiveness of the negative autocorrelation inherent in time series for solving two-armed bandit problems using Fourier transform surrogate methods. We propose a theoretical model that concerns the correlated time series subjected to the decision-making system and the internal status of the system therein in a unified manner, inspired by correlated random walks. We demonstrate that the performance derived analytically by the theory agrees well with the numerical simulations, which confirms the validity of the proposed model and leads to optimal system design. The present study paves the way for improving the effectiveness of correlated time series for decision-making, impacting artificial intelligence and other applications.
Deep Joint Source-Channel Coding for CSI Feedback: An End-to-End Approach
Venue: arXiv cs.IT 2022
Year: 2022

The increased throughput brought by MIMO technology relies on the knowledge of channel state information (CSI) acquired in the base station (BS). To make the CSI feedback overhead affordable for the evolution of MIMO technology (e.g., massive MIMO and ultra-massive MIMO), deep learning (DL) is introduced to deal with the CSI compression task. Based on the separation principle in existing communication systems, DL based CSI compression is used as source coding. However, this separate source-channel coding (SSCC) scheme is inferior to the joint source-channel coding (JSCC) scheme in the finite blocklength regime. In this paper, we propose a deep joint source-channel coding (DJSCC) based framework for the CSI feedback task. In particular, the proposed method can simultaneously learn from the CSI source and the wireless channel. Instead of truncating CSI via Fourier transform in the delay domain in existing methods, we apply non-linear transform networks to compress the CSI. Furthermore, we adopt an SNR adaption mechanism to deal with the wireless channel variations. The extensive experiments demonstrate the validity, adaptability, and generality of the proposed framework.
Clozer: Adaptable Data Augmentation for Cloze-style Reading Comprehension
Venue: arXiv cs.CL 2022
Year: 2022

Task-adaptive pre-training (TAPT) alleviates the lack of labelled data and provides performance lift by adapting unlabelled data to downstream task. Unfortunately, existing adaptations mainly involve deterministic rules that cannot generalize well. Here, we propose Clozer, a sequence-tagging based cloze answer extraction method used in TAPT that is extendable for adaptation on any cloze-style machine reading comprehension (MRC) downstream tasks. We experiment on multiple-choice cloze-style MRC tasks, and show that Clozer performs significantly better compared to the oracle and state-of-the-art in escalating TAPT effectiveness in lifting model performance, and prove that Clozer is able to recognize the gold answers independently of any heuristics.
Matrix Multiplication with Less Arithmetic Complexity and IO Complexity
Venue: arXiv cs.SC 2022
Year: 2022

After Strassen presented the first sub-cubic matrix multiplication algorithm, many Strassen-like algorithms are presented. Most of them with low asymptotic cost have large hidden leading coefficient which are thus impractical. To reduce the leading coefficient, Cenk and Hasan give a general approach reducing the leading coefficient of $<2,2,2;7>$-algorithm to $5$ but increasing IO complexity. In 2017, Karstadt and Schwartz also reduce the leading coefficient of $<2,2,2;7>$-algorithm to $5$ by the Alternative Basis Matrix Multiplication method. Meanwhile, their method reduces the IO complexity and low-order monomials in arithmetic complexity. In 2019, Beniamini and Schwartz generalize Alternative Basis Matrix Multiplication method reducing leading coefficient in arithmetic complexity but increasing IO complexity. In this paper, we propose a new matrix multiplication algorithm which reduces leading coefficient both in arithmetic complexity and IO complexity. We apply our method to Strassen-like algorithms improving arithmetic complexity and IO complexity (the comparison with previous results are shown in Tables 1 and 2). Surprisingly, our IO complexity of $<3,3,3;23>$-algorithm is $14n^{\log_323}M^{-\frac{1}{2}} + o(n^{\log_323})$ which breaks Ballard's IO complexity low bound ($Ω(n^{\log_323}M^{1-\frac{\log_323}{2}})$) for recursive Strassen-like algorithms.
Coarse-to-Fine Recursive Speech Separation for Unknown Number of Speakers
Venue: arXiv cs.SD 2022
Year: 2022

The vast majority of speech separation methods assume that the number of speakers is known in advance, hence they are specific to the number of speakers. By contrast, a more realistic and challenging task is to separate a mixture in which the number of speakers is unknown. This paper formulates the speech separation with the unknown number of speakers as a multi-pass source extraction problem and proposes a coarse-to-fine recursive speech separation method. This method comprises two stages, namely, recursive cue extraction and target speaker extraction. The recursive cue extraction stage determines how many computational iterations need to be performed and outputs a coarse cue speech by monitoring statistics in the mixture. As the number of recursive iterations increases, the accumulation of distortion eventually comes into the extracted speech and reminder. Therefore, in the second stage, we use a target speaker extraction network to extract a fine speech based on the coarse target cue and the original distortionless mixture. Experiments show that the proposed method archived state-of-the-art performance on the WSJ0 dataset with a different number of speakers. Furthermore, it generalizes well to an unseen large number of speakers.
Decision-Focused Learning without Differentiable Optimization: Learning Locally Optimized Decision Losses
Venue: arXiv cs.LG 2022
Year: 2022

Decision-Focused Learning (DFL) is a paradigm for tailoring a predictive model to a downstream optimization task that uses its predictions in order to perform better on that specific task. The main technical challenge associated with DFL is that it requires being able to differentiate through the optimization problem, which is difficult due to discontinuous solutions and other challenges. Past work has largely gotten around this issue by handcrafting task-specific surrogates to the original optimization problem that provide informative gradients when differentiated through. However, the need to handcraft surrogates for each new task limits the usability of DFL. In addition, there are often no guarantees about the convexity of the resulting surrogates and, as a result, training a predictive model using them can lead to inferior local optima. In this paper, we do away with surrogates altogether and instead learn loss functions that capture task-specific information. To the best of our knowledge, ours is the first approach that entirely replaces the optimization component of decision-focused learning with a loss that is automatically learned. Our approach (a) only requires access to a black-box oracle that can solve the optimization problem and is thus generalizable, and (b) can be convex by construction and so can be easily optimized over. We evaluate our approach on three resource allocation problems from the literature and find that our approach outperforms learning without taking into account task structure in all three domains, and even hand-crafted surrogates from the literature.
Contribution of the Temperature of the Objects to the Problem of Thermal Imaging Focusing
Venue: arXiv cs.CV 2022
Year: 2022

When focusing an image, depth of field, aperture and distance from the camera to the object, must be taking into account, both, in visible and in infrared spectrum. Our experiments reveal that in addition, the focusing problem in thermal spectrum is also hardly dependent of the temperature of the object itself (and/or the scene).
Applying Model Checking to Highly-Configurable Safety Critical Software: The SPS-PPS PLC Program
Venue: arXiv cs.SE 2022
Year: 2022

An important aspect of many particle accelerators is the constant evolution and frequent configuration changes that are needed to perform the experiments they are designed for. This often leads to the design of configurable software that can absorb these changes and perform the required control and protection actions. This design strategy minimizes the engineering and maintenance costs, but it makes the software verification activities more challenging since safety properties must be guaranteed for any of the possible configurations. Software model checking is a popular automated verification technique in many industries. This verification method explores all possible combinations of the system model to guarantee its compliance with certain properties or specification. This is a very appropriate technique for highly configurable software, since there is usually an enormous amount of combinations to be checked. This paper presents how PLCverif, a CERN model checking platform, has been applied to a highly configurable Programmable Logic Controller (PLC) program, the SPS Personnel Protection System (PPS). The benefits and challenges of this verification approach are also discussed.
Anticipatory Counterplanning
Venue: arXiv cs.AI 2022
Year: 2022

In competitive environments, commonly agents try to prevent opponents from achieving their goals. Most previous preventing approaches assume the opponent's goal is known a priori. Others only start executing actions once the opponent's goal has been inferred. In this work we introduce a novel domain-independent algorithm called Anticipatory Counterplanning. It combines inference of opponent's goals with computation of planning centroids to yield proactive counter strategies in problems where the opponent's goal is unknown. Experimental results show how this novel technique outperforms reactive counterplanning, increasing the chances of stopping the opponent from achieving its goals.
When Gamification Spoils Your Learning: A Qualitative Case Study of Gamification Misuse in a Language-Learning App
Venue: arXiv cs.HC 2022
Year: 2022

More and more learning apps like Duolingo are using some form of gamification (e.g., badges, points, and leaderboards) to enhance user learning. However, they are not always successful. Gamification misuse is a phenomenon that occurs when users become too fixated on gamification and get distracted from learning. This undesirable phenomenon wastes users' precious time and negatively impacts their learning performance. However, there has been little research in the literature to understand gamification misuse and inform future gamification designs. Therefore, this paper aims to fill this knowledge gap by conducting the first extensive qualitative research on gamification misuse in a popular learning app called Duolingo. Duolingo is currently the world's most downloaded learning app used to learn languages. This study consists of two phases: (I) a content analysis of data from Duolingo forums (from the past nine years) and (II) semi-structured interviews with 15 international Duolingo users. Our research contributes to the Human-Computer Interaction (HCI) and Learning at Scale (L@S) research communities in three ways: (1) elaborating the ramifications of gamification misuse on user learning, well-being, and ethics, (2) identifying the most common reasons for gamification misuse (e.g., competitiveness, overindulgence in playfulness, and herding), and (3) providing designers with practical suggestions to prevent (or mitigate) the occurrence of gamification misuse in their future designs of gamified learning apps.
Enabling Trade-offs in Machine Learning-based Matching for Refugee Resettlement
Venue: arXiv cs.GT 2022
Year: 2022

The Swiss State Secretariat for Migration recently announced a pilot project for a machine learning-based assignment process for refugee resettlement. This approach has the potential to substantially increase the overall employment rate of refugees in Switzerland. However, the currently proposed method ignores families' preferences. In this paper, we build on this prior work and propose two matching mechanisms that additionally take families' preferences over locations into account. The first mechanism is strategyproof while the second is not but achieves higher family welfare. Importantly, we parameterize both mechanisms, giving placement officers precise control how to trade off family welfare against overall employment success. Preliminary simulations on synthetic data show that both mechanisms can significantly increase family welfare even with only a small loss on the overall employment rate of refugees.