OpenRaiser/Intern-Atlas huggingface dataset:
StyTr$^2$: Image Style Transfer with Transformers
Venue: arXiv cs.CV 2022
Year: 2022

The goal of image style transfer is to render an image with artistic features guided by a style reference while maintaining the original content. Owing to the locality in convolutional neural networks (CNNs), extracting and maintaining the global information of input images is difficult. Therefore, traditional neural style transfer methods face biased content representation. To address this critical issue, we take long-range dependencies of input images into account for image style transfer by proposing a transformer-based approach called StyTr$^2$. In contrast with visual transformers for other vision tasks, StyTr$^2$ contains two different transformer encoders to generate domain-specific sequences for content and style, respectively. Following the encoders, a multi-layer transformer decoder is adopted to stylize the content sequence according to the style sequence. We also analyze the deficiency of existing positional encoding methods and propose the content-aware positional encoding (CAPE), which is scale-invariant and more suitable for image style transfer tasks. Qualitative and quantitative experiments demonstrate the effectiveness of the proposed StyTr$^2$ compared with state-of-the-art CNN-based and flow-based approaches. Code and models are available at https://github.com/diyiiyiii/StyTR-2.
NoiLIn: Improving Adversarial Training and Correcting Stereotype of Noisy Labels
Venue: arXiv cs.LG 2022
Year: 2022

Adversarial training (AT) formulated as the minimax optimization problem can effectively enhance the model's robustness against adversarial attacks. The existing AT methods mainly focused on manipulating the inner maximization for generating quality adversarial variants or manipulating the outer minimization for designing effective learning objectives. However, empirical results of AT always exhibit the robustness at odds with accuracy and the existence of the cross-over mixture problem, which motivates us to study some label randomness for benefiting the AT. First, we thoroughly investigate noisy labels (NLs) injection into AT's inner maximization and outer minimization, respectively and obtain the observations on when NL injection benefits AT. Second, based on the observations, we propose a simple but effective method -- NoiLIn that randomly injects NLs into training data at each training epoch and dynamically increases the NL injection rate once robust overfitting occurs. Empirically, NoiLIn can significantly mitigate the AT's undesirable issue of robust overfitting and even further improve the generalization of the state-of-the-art AT methods. Philosophically, NoiLIn sheds light on a new perspective of learning with NLs: NLs should not always be deemed detrimental, and even in the absence of NLs in the training set, we may consider injecting them deliberately. Codes are available in https://github.com/zjfheart/NoiLIn.
Bangla Natural Language Processing: A Comprehensive Analysis of Classical, Machine Learning, and Deep Learning Based Methods
Venue: arXiv cs.CL 2022
Year: 2022

The Bangla language is the seventh most spoken language, with 265 million native and non-native speakers worldwide. However, English is the predominant language for online resources and technical knowledge, journals, and documentation. Consequently, many Bangla-speaking people, who have limited command of English, face hurdles to utilize English resources. To bridge the gap between limited support and increasing demand, researchers conducted many experiments and developed valuable tools and techniques to create and process Bangla language materials. Many efforts are also ongoing to make it easy to use the Bangla language in the online and technical domains. There are some review papers to understand the past, previous, and future Bangla Natural Language Processing (BNLP) trends. The studies are mainly concentrated on the specific domains of BNLP, such as sentiment analysis, speech recognition, optical character recognition, and text summarization. There is an apparent scarcity of resources that contain a comprehensive review of the recent BNLP tools and methods. Therefore, in this paper, we present a thorough analysis of 75 BNLP research papers and categorize them into 11 categories, namely Information Extraction, Machine Translation, Named Entity Recognition, Parsing, Parts of Speech Tagging, Question Answering System, Sentiment Analysis, Spam and Fake Detection, Text Summarization, Word Sense Disambiguation, and Speech Processing and Recognition. We study articles published between 1999 to 2021, and 50% of the papers were published after 2015. Furthermore, we discuss Classical, Machine Learning and Deep Learning approaches with different datasets while addressing the limitations and current and future trends of the BNLP.
Design of Placement Delivery Arrays for Coded Caching with Small Subpacketizations and Flexible Memory Sizes
Venue: arXiv cs.IT 2022
Year: 2022

Coded caching is an emerging technique to reduce the data transmission load during the peak-traffic times. In such a scheme, each file in the data center or library is usually divided into a number of packets to pursue a low broadcasting rate based on the designed placements at each user's cache. However, the implementation complexity of this scheme increases as the number of packets increases. It is crucial to design a scheme with a small subpacketization level, while maintaining a relatively low transmission rate. It is known that the design of caches in users (i.e., the placement phase) and broadcasting (i.e., the delivery phase) can be unified in one matrix, namely the placement delivery array (PDA). This paper proposes a novel PDA construction by selecting proper orthogonal arrays (POAs), which generalizes some known constructions but with a more flexible memory size. Based on the proposed PDA construction, an effective transformation is further proposed to enable a coded caching scheme to have a smaller subpacketization level. Moreover, two new coded caching schemes with the coded placement are considered. It is shown that the proposed schemes yield a lower subpacketization level and transmission rate over some existing schemes.
Invariant Policy Learning: A Causal Perspective
Venue: arXiv cs.LG 2022
Year: 2022

Contextual bandit and reinforcement learning algorithms have been successfully used in various interactive learning systems such as online advertising, recommender systems, and dynamic pricing. However, they have yet to be widely adopted in high-stakes application domains, such as healthcare. One reason may be that existing approaches assume that the underlying mechanisms are static in the sense that they do not change over different environments. In many real-world systems, however, the mechanisms are subject to shifts across environments which may invalidate the static environment assumption. In this paper, we take a step toward tackling the problem of environmental shifts considering the framework of offline contextual bandits. We view the environmental shift problem through the lens of causality and propose multi-environment contextual bandits that allow for changes in the underlying mechanisms. We adopt the concept of invariance from the causality literature and introduce the notion of policy invariance. We argue that policy invariance is only relevant if unobserved variables are present and show that, in that case, an optimal invariant policy is guaranteed to generalize across environments under suitable assumptions. Our results establish concrete connections among causality, invariance, and contextual bandits.
Unsupervised Out-of-Domain Detection via Pre-trained Transformers
Venue: arXiv cs.CL 2022
Year: 2022

Deployed real-world machine learning applications are often subject to uncontrolled and even potentially malicious inputs. Those out-of-domain inputs can lead to unpredictable outputs and sometimes catastrophic safety issues. Prior studies on out-of-domain detection require in-domain task labels and are limited to supervised classification scenarios. Our work tackles the problem of detecting out-of-domain samples with only unsupervised in-domain data. We utilize the latent representations of pre-trained transformers and propose a simple yet effective method to transform features across all layers to construct out-of-domain detectors efficiently. Two domain-specific fine-tuning approaches are further proposed to boost detection accuracy. Our empirical evaluations of related methods on two datasets validate that our method greatly improves out-of-domain detection ability in a more general scenario.
On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correction
Venue: arXiv cs.LG 2022
Year: 2022

In this paper, we study the convergence properties of off-policy policy improvement algorithms with state-action density ratio correction under function approximation setting, where the objective function is formulated as a max-max-min optimization problem. We characterize the bias of the learning objective and present two strategies with finite-time convergence guarantees. In our first strategy, we present algorithm P-SREDA with convergence rate $O(ε^{-3})$, whose dependency on $ε$ is optimal. In our second strategy, we propose a new off-policy actor-critic style algorithm named O-SPIM. We prove that O-SPIM converges to a stationary point with total complexity $O(ε^{-4})$, which matches the convergence rate of some recent actor-critic algorithms in the on-policy setting.
SocAoG: Incremental Graph Parsing for Social Relation Inference in Dialogues
Venue: arXiv cs.CL 2022
Year: 2022

Inferring social relations from dialogues is vital for building emotionally intelligent robots to interpret human language better and act accordingly. We model the social network as an And-or Graph, named SocAoG, for the consistency of relations among a group and leveraging attributes as inference cues. Moreover, we formulate a sequential structure prediction task, and propose an $α$-$β$-$γ$ strategy to incrementally parse SocAoG for the dynamic inference upon any incoming utterance: (i) an $α$ process predicting attributes and relations conditioned on the semantics of dialogues, (ii) a $β$ process updating the social relations based on related attributes, and (iii) a $γ$ process updating individual's attributes based on interpersonal social relations. Empirical results on DialogRE and MovieGraph show that our model infers social relations more accurately than the state-of-the-art methods. Moreover, the ablation study shows the three processes complement each other, and the case study demonstrates the dynamic relational inference.
Expected Scalarised Returns Dominance: A New Solution Concept for Multi-Objective Decision Making
Venue: arXiv cs.LG 2022
Year: 2022

In many real-world scenarios, the utility of a user is derived from the single execution of a policy. In this case, to apply multi-objective reinforcement learning, the expected utility of the returns must be optimised. Various scenarios exist where a user's preferences over objectives (also known as the utility function) are unknown or difficult to specify. In such scenarios, a set of optimal policies must be learned. However, settings where the expected utility must be maximised have been largely overlooked by the multi-objective reinforcement learning community and, as a consequence, a set of optimal solutions has yet to be defined. In this paper we address this challenge by proposing first-order stochastic dominance as a criterion to build solution sets to maximise expected utility. We also propose a new dominance criterion, known as expected scalarised returns (ESR) dominance, that extends first-order stochastic dominance to allow a set of optimal policies to be learned in practice. We then define a new solution concept called the ESR set, which is a set of policies that are ESR dominant. Finally, we define a new multi-objective distributional tabular reinforcement learning (MOT-DRL) algorithm to learn the ESR set in a multi-objective multi-armed bandit setting.
Automating Speedrun Routing: Overview and Vision
Venue: arXiv cs.NE 2022
Year: 2022

Speedrunning in general means to play a video game fast, i.e. using all means at one's disposal to achieve a given goal in the least amount of time possible. To do so, a speedrun must be planned in advance, or routed, as referred to by the community. This paper focuses on discovering challenges and defining models needed when trying to approach the problem of routing algorithmically. To do so, this paper is split in two parts. The first part provides an overview of relevant speedrunning literature, extracting vital information and formulating criticism. Important categorizations are pointed out and a nomenclature is built to support professional discussion. The second part of this paper then refers to the actual speedrun routing optimization problem. Different concepts of graph representations are presented and their potential is discussed. Visions both for problem modeling as well as solving are presented and assessed regarding suitability and expected challenges. Finally, a first assessment of the applicability of existing optimization methods to the defined problem is made, including metaheuristics/EA and Deep Learning methods.
Sound-to-Imagination: An Exploratory Study on Unsupervised Crossmodal Translation Using Diverse Audiovisual Data
Venue: arXiv cs.SD 2022
Year: 2022

The motivation of our research is to explore the possibilities of automatic sound-to-image (S2I) translation for enabling a human receiver to visually infer the occurrence of sound related events. We expect the computer to 'imagine' the scene from the captured sound, generating original images that picture the sound emitting source. Previous studies on similar topics opted for simplified approaches using data with low content diversity and/or sound class supervision. Differently, we propose to perform unsupervised S2I translation using thousands of distinct and unknown scenes, with slightly pre-cleaned data, just enough to guarantee aural-visual semantic coherence. To that end, we employ conditional generative adversarial networks (GANs) with a deep densely connected generator. Additionally, we present a solution using informativity classifiers to perform quantitative evaluation of the generated images. This enabled us to analyze the influence of network bottleneck variation over the translation, observing a potential trade-off between informativity and pixel space convergence. Despite the complexity of the specified S2I translation task, we were able to generalize the model enough to obtain more than 14%, in average, of interpretable and semantically coherent images translated from unknown sounds.
Ver: View Discovery in the Wild
Venue: arXiv cs.DB 2022
Year: 2022

We present Ver, a data discovery system that identifies project-join views over large repositories of tables that do not contain join path information, and even when input queries are inaccurate. Ver implements a reference architecture to solve both the technical (scale and search) and human (semantic ambiguity, navigating a large number of results) problems of view discovery. We demonstrate users find the view they want when using Ver with a user study and we demonstrate its performance with large-scale end-to-end experiments on real-world datasets containing tens of millions of join paths.
Semi-Empirical Objective Functions for MCMC Proposal Optimization
Venue: arXiv cs.LG 2022
Year: 2022

Current objective functions used for training neural MCMC proposal distributions implicitly rely on architectural restrictions to yield sensible optimization results, which hampers the development of highly expressive neural MCMC proposal architectures. In this work, we introduce and demonstrate a semi-empirical procedure for determining approximate objective functions suitable for optimizing arbitrarily parameterized proposal distributions in MCMC methods. Our proposed Ab Initio objective functions consist of the weighted combination of functions following constraints on their global optima and transformation invariances that we argue should be upheld by general measures of MCMC efficiency for use in proposal optimization. Our experimental results demonstrate that Ab Initio objective functions maintain favorable performance and preferable optimization behavior compared to existing objective functions for neural MCMC optimization. We find that Ab Initio objective functions are sufficiently robust to enable the confident optimization of neural proposal distributions parameterized by deep generative networks extending beyond the regimes of traditional MCMC schemes
Approximation Algorithms for Min-Distance Problems in DAGs
Venue: arXiv cs.DS 2022
Year: 2022

The min-distance between two nodes $u, v$ is defined as the minimum of the distance from $v$ to $u$ or from $u$ to $v$, and is a natural distance metric in DAGs. As with the standard distance problems, the Strong Exponential Time Hypothesis [Impagliazzo-Paturi-Zane 2001, Calabro-Impagliazzo-Paturi 2009] leaves little hope for computing min-distance problems faster than computing All Pairs Shortest Paths, which can be solved in $\tilde{O}(mn)$ time. So it is natural to resort to approximation algorithms in $\tilde{O}(mn^{1-ε})$ time for some positive $ε$. Abboud, Vassilevska W., and Wang [SODA 2016] first studied min-distance problems achieving constant factor approximation algorithms on DAGs, obtaining a $3$-approximation algorithm for min-radius on DAGs which works in $\tilde{O}(m\sqrt{n})$ time, and showing that any $(2-δ)$-approximation requires $n^{2-o(1)}$ time for any $δ>0$, under the Hitting Set Conjecture. We close the gap, obtaining a $2$-approximation algorithm which runs in $\tilde{O}(m\sqrt{n})$ time. As the lower bound of Abboud et al only works for sparse DAGs, we further show that our algorithm is conditionally tight for dense DAGs using a reduction from Boolean matrix multiplication. Moreover, Abboud et al obtained a linear time $2$-approximation algorithm for min-diameter along with a lower bound stating that any $(3/2-δ)$-approximation algorithm for sparse DAGs requires $n^{2-o(1)}$ time under SETH. We close this gap for dense DAGs by obtaining a near-$3/2$-approximation algorithm which works in $O(n^{2.350})$ time and showing that the approximation factor is unlikely to be improved within $O(n^{ω- o(1)})$ time under the high dimensional Orthogonal Vectors Conjecture, where $ω$ is the matrix multiplication exponent.
Envy-free division of multi-layered cakes
Venue: arXiv cs.GT 2022
Year: 2022

We study the problem of dividing a multi-layered cake under non-overlapping constraints. This problem, recently proposed by Hosseini et al. (IJCAI, 2020), captures several natural scenarios such as the allocation of multiple facilities over time where each agent can utilize at most one facility simultaneously, and the allocation of tasks over time where each agent can perform at most one task simultaneously. We establish the existence of an envy-free multi-division that is both non-overlapping and contiguous within each layer when the number of agents is a prime power and the number of layers is at most the number of agents, providing a positive partial answer to an open question by Hosseini et al. To achieve this, we employ a new approach based on a general fixed point theorem, originally proven by Volovikov (1996), and recently applied by Jojić, Panina, and Živaljević (2020) to the envy-free division problem of a cake. We further design a fully polynomial-time approximation scheme (FPTAS) to find an approximate envy-free solution that is both non-overlapping and contiguous for a two-layered cake division among three agents with monotone preferences. More generally, we establish all the results for divisions among groups of almost the same size. When there are three groups and one layer, our FPTAS is actually able to deal with groups of any predetermined sizes, still under the monotone preference assumptions. For three groups, this provides thus an algorithmic version of a recent theorem by Segal-Halevi and Suksompong (2021). A classical lemma from topology ensures that every self-map of a simplex mapping each facet to itself is surjective. This lemma has often been used in economics theory and our algorithm can be interpreted as an FPTAS counterpart of its two-dimensional version.
Strategyproof Learning: Building Trustworthy User-Generated Datasets
Venue: arXiv cs.LG 2022
Year: 2022

We prove in this paper that, perhaps surprisingly, incentivizing data misreporting is not a fatality. By leveraging a careful design of the loss function, we propose Licchavi, a global and personalized learning framework with provable strategyproofness guarantees. Essentially, we prove that no user can gain much by replying to Licchavi's queries with answers that deviate from their true preferences. Interestingly, Licchavi also promotes the desirable "one person, one unit-force vote" fairness principle. Furthermore, our empirical evaluation of its performance showcases Licchavi's real-world applicability. We believe that our results are critical for the safety of any learning scheme that leverages user-generated data.
Network and Physical Layer Attacks and countermeasures to AI-Enabled 6G O-RAN
Venue: arXiv cs.CR 2022
Year: 2022

Artificial intelligence (AI) will play an increasing role in cellular network deployment, configuration and management. This paper examines the security implications of AI-driven 6G radio access networks (RANs). While the expected timeline for 6G standardization is still several years out, pre-standardization efforts related to 6G security are already ongoing and will benefit from fundamental and experimental research. The Open RAN (O-RAN) describes an industry-driven open architecture and interfaces for building next generation RANs with AI control. Considering this architecture, we identify the critical threats to data driven network and physical layer elements, the corresponding countermeasures, and the research directions.
Hidden Markov Modeling for Maximum Likelihood Neuron Reconstruction
Venue: arXiv cs.CV 2022
Year: 2022

Recent advances in brain clearing and imaging have made it possible to image entire mammalian brains at sub-micron resolution. These images offer the potential to assemble brain-wide atlases of neuron morphology, but manual neuron reconstruction remains a bottleneck. Several automatic reconstruction algorithms exist, but most focus on single neuron images. In this paper, we present a probabilistic reconstruction method, ViterBrain, which combines a hidden Markov state process that encodes neuron geometry with a random field appearance model of neuron fluorescence. Our method utilizes dynamic programming to compute the global maximizers of what we call the "most probable" neuron path. Our most probable estimation method models the task of reconstructing neuronal processes in the presence of other neurons, and thus is applicable in images with several neurons. Our method operates on image segmentations in order to leverage cutting edge computer vision technology. We applied our algorithm to imperfect image segmentations where false negatives severed neuronal processes, and showed that it can follow axons in the presence of noise or nearby neurons. Additionally, it creates a framework where users can intervene to, for example, fit start and endpoints. The code used in this work is available in our open-source Python package brainlit.