OpenRaiser/Intern-Atlas huggingface dataset:
Distributed adaptive algorithm based on the asymmetric cost of error functions
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, a family of novel diffusion adaptive estimation algorithm is proposed from the asymmetric cost function perspective by combining diffusion strategy and the linear-linear cost (LLC), quadratic-quadratic cost (QQC), and linear-exponential cost (LEC), at all distributed network nodes, and named diffusion LLCLMS (DLLCLMS), diffusion QQCLMS (DQQCLMS), and diffusion LECLMS (DLECLMS), respectively. Then the stability of mean estimation error and computational complexity of those three diffusion algorithms are analyzed theoretically. Finally, several experiment simulation results are designed to verify the superiority of those three proposed diffusion algorithms. Experimental simulation results show that DLLCLMS, DQQCLMS, and DLECLMS algorithms are more robust to the input signal and impulsive noise than the DSELMS, DRVSSLMS, and DLLAD algorithms. In brief, theoretical analysis and experiment results show that those proposed DLLCLMS, DQQCLMS, and DLECLMS algorithms have superior performance when estimating the unknown linear system under the changeable impulsive noise environments and different types of input signals.
RISAN: Robust Instance Specific Abstention Network
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we propose deep architectures for learning instance specific abstain (reject option) binary classifiers. The proposed approach uses double sigmoid loss function as described by Kulin Shah and Naresh Manwani in ("Online Active Learning of Reject Option Classifiers", AAAI, 2020), as a performance measure. We show that the double sigmoid loss is classification calibrated. We also show that the excess risk of 0-d-1 loss is upper bounded by the excess risk of double sigmoid loss. We derive the generalization error bounds for the proposed architecture for reject option classifiers. To show the effectiveness of the proposed approach, we experiment with several real world datasets. We observe that the proposed approach not only performs comparable to the state-of-the-art approaches, it is also robust against label noise. We also provide visualizations to observe the important features learned by the network corresponding to the abstaining decision.
A Heuristic for Direct Product Graph Decomposition
Venue: arXiv cs.DS 2021
Year: 2021

In this paper we describe a heuristic for decomposing a directed graph into factors according to the direct product (also known as Kronecker, cardinal or tensor product). Given a directed, unweighted graph~$G$ with adjacency matrix Adj($G$), our heuristic searches for a pair of graphs~$G_1$ and~$G_2$ such that $G = G_1 \otimes G_2$, where $G_1 \otimes G_2$ is the direct product of~$G_1$ and~$G_2$. For undirected, connected graphs it has been shown that graph decomposition is "at least as difficult" as graph isomorphism; therefore, polynomial-time algorithms for decomposing a general directed graph into factors are unlikely to exist. Although graph factorization is a problem that has been extensively investigated, the heuristic proposed in this paper represents -- to the best of our knowledge -- the first computational approach for general directed, unweighted graphs. We have implemented our algorithm using the MATLAB environment; we report on a set of experiments that show that the proposed heuristic solves reasonably-sized instances in a few seconds on general-purpose hardware.
FBC-GAN: Diverse and Flexible Image Synthesis via Foreground-Background Composition
Venue: arXiv cs.CV 2021
Year: 2021

Generative Adversarial Networks (GANs) have become the de-facto standard in image synthesis. However, without considering the foreground-background decomposition, existing GANs tend to capture excessive content correlation between foreground and background, thus constraining the diversity in image generation. This paper presents a novel Foreground-Background Composition GAN (FBC-GAN) that performs image generation by generating foreground objects and background scenes concurrently and independently, followed by composing them with style and geometrical consistency. With this explicit design, FBC-GAN can generate images with foregrounds and backgrounds that are mutually independent in contents, thus lifting the undesirably learned content correlation constraint and achieving superior diversity. It also provides excellent flexibility by allowing the same foreground object with different background scenes, the same background scene with varying foreground objects, or the same foreground object and background scene with different object positions, sizes and poses. It can compose foreground objects and background scenes sampled from different datasets as well. Extensive experiments over multiple datasets show that FBC-GAN achieves competitive visual realism and superior diversity as compared with state-of-the-art methods.
Trans4Trans: Efficient Transformer for Transparent Object Segmentation to Help Visually Impaired People Navigate in the Real World
Venue: arXiv cs.CV 2021
Year: 2021

Common fully glazed facades and transparent objects present architectural barriers and impede the mobility of people with low vision or blindness, for instance, a path detected behind a glass door is inaccessible unless it is correctly perceived and reacted. However, segmenting these safety-critical objects is rarely covered by conventional assistive technologies. To tackle this issue, we construct a wearable system with a novel dual-head Transformer for Transparency (Trans4Trans) model, which is capable of segmenting general and transparent objects and performing real-time wayfinding to assist people walking alone more safely. Especially, both decoders created by our proposed Transformer Parsing Module (TPM) enable effective joint learning from different datasets. Besides, the efficient Trans4Trans model composed of symmetric transformer-based encoder and decoder, requires little computational expenses and is readily deployed on portable GPUs. Our Trans4Trans model outperforms state-of-the-art methods on the test sets of Stanford2D3D and Trans10K-v2 datasets and obtains mIoU of 45.13% and 75.14%, respectively. Through various pre-tests and a user study conducted in indoor and outdoor scenarios, the usability and reliability of our assistive system have been extensively verified.
Time-Aware Ancient Chinese Text Translation and Inference
Venue: arXiv cs.CL 2021
Year: 2021

In this paper, we aim to address the challenges surrounding the translation of ancient Chinese text: (1) The linguistic gap due to the difference in eras results in translations that are poor in quality, and (2) most translations are missing the contextual information that is often very crucial to understanding the text. To this end, we improve upon past translation techniques by proposing the following: We reframe the task as a multi-label prediction task where the model predicts both the translation and its particular era. We observe that this helps to bridge the linguistic gap as chronological context is also used as auxiliary information. % As a natural step of generalization, we pivot on the modern Chinese translations to generate multilingual outputs. %We show experimentally the efficacy of our framework in producing quality translation outputs and also validate our framework on a collected task-specific parallel corpus. We validate our framework on a parallel corpus annotated with chronology information and show experimentally its efficacy in producing quality translation outputs. We release both the code and the data https://github.com/orina1123/time-aware-ancient-text-translation for future research.
The Geography of Open Source Software: Evidence from GitHub
Venue: arXiv cs.SI 2021
Year: 2021

Open Source Software (OSS) plays an important role in the digital economy. Yet although software production is amenable to remote collaboration and its outputs are easily shared across distances, software development seems to cluster geographically in places such as Silicon Valley, London, or Berlin. And while recent work indicates that OSS activity creates positive externalities which accrue locally through knowledge spillovers and information effects, up-to-date data on the geographic distribution of active open source developers is limited. This presents a significant blindspot for policymakers, who tend to promote OSS at the national level as a cost-saving tool for public sector institutions. We address this gap by geolocating more than half a million active contributors to GitHub in early 2021 at various spatial scales. Compared to results from 2010, we find a significant increase in the share of developers based in Asia, Latin America and Eastern Europe, suggesting a more even spread of OSS developers globally. Within countries, however, we find significant concentration in regions, exceeding the concentration of workers in high-tech fields. Social and economic development indicators predict at most half of regional variation in OSS activity in the EU, suggesting that clusters of OSS have idiosyncratic roots. We argue that policymakers seeking to foster OSS should focus locally rather than nationally, using the tools of cluster policy to support networks of OSS developers.
Nominal Büchi Automata with Name Allocation
Venue: arXiv cs.FL 2021
Year: 2021

Infinite words over infinite alphabets serve as models of the temporal development of the allocation and (re-)use of resources over linear time. We approach omega-languages over infinite alphabets in the setting of nominal sets, and study languages of infinite bar strings, i.e. infinite sequences of names that feature binding of fresh names; binding corresponds roughly to reading letters from input words in automata models with registers. We introduce regular nominal nondeterministic Büchi automata (Büchi RNNAs), an automata model for languages of infinite bar strings, repurposing the previously introduced RNNAs over finite bar strings. Our machines feature explicit binding (i.e. resource-allocating) transitions and process their input via a Büchi-type acceptance condition. They emerge from the abstract perspective on name binding given by the theory of nominal sets. As our main result we prove that, in contrast to most other nondeterministic automata models over infinite alphabets, language inclusion of Büchi RNNAs is decidable and in fact elementary. This makes Büchi RNNAs a suitable tool for applications in model checking.
Syntactic Minimization of Nondeterministic Finite Automata
Venue: arXiv cs.FL 2021
Year: 2021

Nondeterministic automata may be viewed as succinct programs implementing deterministic automata, i.e. complete specifications. Converting a given deterministic automaton into a small nondeterministic one is known to be computationally very hard; in fact, the ensuing decision problem is PSPACE-complete. This paper stands in stark contrast to the status quo. We restrict attention to subatomic nondeterministic automata, whose individual states accept unions of syntactic congruence classes. They are general enough to cover almost all structural results concerning nondeterministic state-minimality. We prove that converting a monoid recognizing a regular language into a small subatomic acceptor corresponds to an NP-complete problem. The NP certificates are solutions of simple equations involving relations over the syntactic monoid. We also consider the subclass of atomic nondeterministic automata introduced by Brzozowski and Tamm. Given a deterministic automaton and another one for the reversed language, computing small atomic acceptors is shown to be NP-complete with analogous certificates. Our complexity results emerge from an algebraic characterization of (sub)atomic acceptors in terms of deterministic automata with semilattice structure, combined with an equivalence of categories leading to succinct representations.
How Big Are Peoples' Computer Files? File Size Distributions Among User-managed Collections
Venue: arXiv cs.HC 2021
Year: 2021

Improving file management interfaces and optimising system performance requires current data about users' digital collections and particularly about the file size distributions of such collections. However, prior works have examined only the sizes of system files and users' work files in varied contexts, and there has been no such study since 2013; it therefore remains unclear how today's file sizes are distributed, particularly personal files, and further if distributions differ among the major operating systems or common occupations. Here we examine such differences among 49 million files in 348 user collections. We find that the average file size has grown more than ten-fold since the mid-2000s, though most files are still under 8 MB, and that there are demographic and technological influences in the size distributions. We discuss the implications for user interfaces, system optimisation, and PIM research.
Strategy Complexity of Mean Payoff, Total Payoff and Point Payoff Objectives in Countable MDPs
Venue: arXiv cs.AI 2021
Year: 2021

We study countably infinite Markov decision processes (MDPs) with real-valued transition rewards. Every infinite run induces the following sequences of payoffs: 1. Point payoff (the sequence of directly seen transition rewards), 2. Total payoff (the sequence of the sums of all rewards so far), and 3. Mean payoff. For each payoff type, the objective is to maximize the probability that the $\liminf$ is non-negative. We establish the complete picture of the strategy complexity of these objectives, i.e., how much memory is necessary and sufficient for $\varepsilon$-optimal (resp. optimal) strategies. Some cases can be won with memoryless deterministic strategies, while others require a step counter, a reward counter, or both.
SoundStream: An End-to-End Neural Audio Codec
Venue: arXiv cs.SD 2021
Year: 2021

We present SoundStream, a novel neural audio codec that can efficiently compress speech, music and general audio at bitrates normally targeted by speech-tailored codecs. SoundStream relies on a model architecture composed by a fully convolutional encoder/decoder network and a residual vector quantizer, which are trained jointly end-to-end. Training leverages recent advances in text-to-speech and speech enhancement, which combine adversarial and reconstruction losses to allow the generation of high-quality audio content from quantized embeddings. By training with structured dropout applied to quantizer layers, a single model can operate across variable bitrates from 3kbps to 18kbps, with a negligible quality loss when compared with models trained at fixed bitrates. In addition, the model is amenable to a low latency implementation, which supports streamable inference and runs in real time on a smartphone CPU. In subjective evaluations using audio at 24kHz sampling rate, SoundStream at 3kbps outperforms Opus at 12kbps and approaches EVS at 9.6kbps. Moreover, we are able to perform joint compression and enhancement either at the encoder or at the decoder side with no additional latency, which we demonstrate through background noise suppression for speech.
A Graph-based Approach for Mitigating Multi-sided Exposure Bias in Recommender Systems
Venue: arXiv cs.IR 2021
Year: 2021

Fairness is a critical system-level objective in recommender systems that has been the subject of extensive recent research. A specific form of fairness is supplier exposure fairness where the objective is to ensure equitable coverage of items across all suppliers in recommendations provided to users. This is especially important in multistakeholder recommendation scenarios where it may be important to optimize utilities not just for the end-user, but also for other stakeholders such as item sellers or producers who desire a fair representation of their items. This type of supplier fairness is sometimes accomplished by attempting to increasing aggregate diversity in order to mitigate popularity bias and to improve the coverage of long-tail items in recommendations. In this paper, we introduce FairMatch, a general graph-based algorithm that works as a post processing approach after recommendation generation to improve exposure fairness for items and suppliers. The algorithm iteratively adds high quality items that have low visibility or items from suppliers with low exposure to the users' final recommendation lists. A comprehensive set of experiments on two datasets and comparison with state-of-the-art baselines show that FairMatch, while significantly improves exposure fairness and aggregate diversity, maintains an acceptable level of relevance of the recommendations.
Reconfigurable Intelligent Surface-Assisted Massive MIMO: Favorable Propagation, Channel Hardening, and Rank Deficiency
Venue: arXiv cs.IT 2021
Year: 2021

Massive multiple-input multiple-output (MIMO) and reconfigurable intelligent surface (RIS) are two promising technologies for 5G-and-beyond wireless networks, capable of providing large array gain and multiuser spatial multiplexing. Without requiring additional frequency bands, those technologies offer significant improvements in both spectral and energy efficiency by simultaneously serving many users. The performance analysis of an RIS-assisted Massive MIMO system as a function of the channel statistics relies heavily on fundamental properties including favorable propagation, channel hardening, and rank deficiency. The coexistence of both direct and indirect links results in aggregated channels, whose properties are the main concerns of this lecture note. For practical systems with a finite number of antennas and scattering elements of the RIS, we evaluate the corresponding deterministic metrics with Rayleigh fading channels as a typical example.
Tensor Methods in Computer Vision and Deep Learning
Venue: arXiv cs.CV 2021
Year: 2021

Tensors, or multidimensional arrays, are data structures that can naturally represent visual data of multiple dimensions. Inherently able to efficiently capture structured, latent semantic spaces and high-order interactions, tensors have a long history of applications in a wide span of computer vision problems. With the advent of the deep learning paradigm shift in computer vision, tensors have become even more fundamental. Indeed, essential ingredients in modern deep learning architectures, such as convolutions and attention mechanisms, can readily be considered as tensor mappings. In effect, tensor methods are increasingly finding significant applications in deep learning, including the design of memory and compute efficient network architectures, improving robustness to random noise and adversarial attacks, and aiding the theoretical understanding of deep networks. This article provides an in-depth and practical review of tensors and tensor methods in the context of representation learning and deep learning, with a particular focus on visual data analysis and computer vision applications. Concretely, besides fundamental work in tensor-based visual data analysis methods, we focus on recent developments that have brought on a gradual increase of tensor methods, especially in deep learning architectures, and their implications in computer vision applications. To further enable the newcomer to grasp such concepts quickly, we provide companion Python notebooks, covering key aspects of the paper and implementing them, step-by-step with TensorLy.
Geometric averages of partitioned datasets
Venue: arXiv cs.CG 2021
Year: 2021

We introduce a method for jointly registering ensembles of partitioned datasets in a way which is both geometrically coherent and partition-aware. Once such a registration has been defined, one can group partition blocks across datasets in order to extract summary statistics, generalizing the commonly used order statistics for scalar-valued data. By modeling a partitioned dataset as an unordered $k$-tuple of points in a Wasserstein space, we are able to draw from techniques in optimal transport. More generally, our method is developed using the formalism of local Fréchet means in symmetric products of metric spaces. We establish basic theory in this general setting, including Alexandrov curvature bounds and a verifiable characterization of local means. Our method is demonstrated on ensembles of political redistricting plans to extract and visualize basic properties of the space of plans for a particular state, using North Carolina as our main example.
Space-Efficient Fault-Tolerant Diameter Oracles
Venue: arXiv cs.DS 2021
Year: 2021

We design $f$-edge fault-tolerant diameter oracles ($f$-FDOs). We preprocess a given graph $G$ on $n$ vertices and $m$ edges, and a positive integer $f$, to construct a data structure that, when queried with a set $F$ of $|F| \leq f$ edges, returns the diameter of $G-F$. For a single failure ($f=1$) in an unweighted directed graph of diameter $D$, there exists an approximate FDO by Henzinger et al. [ITCS 2017] with stretch $(1+\varepsilon)$, constant query time, space $O(m)$, and a combinatorial preprocessing time of $\widetilde{O}(mn + n^{1.5} \sqrt{Dm/\varepsilon})$.We present an FDO for directed graphs with the same stretch, query time, and space. It has a preprocessing time of $\widetilde{O}(mn + n^2/\varepsilon)$. The preprocessing time nearly matches a conditional lower bound for combinatorial algorithms, also by Henzinger et al. With fast matrix multiplication, we achieve a preprocessing time of $\widetilde{O}(n^{2.5794} + n^2/\varepsilon)$. We further prove an information-theoretic lower bound showing that any FDO with stretch better than $3/2$ requires $Ω(m)$ bits of space. For multiple failures ($f>1$) in undirected graphs with non-negative edge weights, we give an $f$-FDO with stretch $(f+2)$, query time $O(f^2\log^2{n})$, $\widetilde{O}(fn)$ space, and preprocessing time $\widetilde{O}(fm)$. We complement this with a lower bound excluding any finite stretch in $o(fn)$ space. We show that for unweighted graphs with polylogarithmic diameter and up to $f = o(\log n/ \log\log n)$ failures, one can swap approximation for query time and space. We present an exact combinatorial $f$-FDO with preprocessing time $mn^{1+o(1)}$, query time $n^{o(1)}$, and space $n^{2+o(1)}$. When using fast matrix multiplication instead, the preprocessing time can be improved to $n^{ω+o(1)}$, where $ω< 2.373$ is the matrix multiplication exponent.
Tuning Channel Access to Enable Real-Time Applications in Wi-Fi 7
Venue: arXiv cs.NI 2021
Year: 2021

Real-Time Applications (RTA) are among the most important use cases for future Wi-Fi 7, defined by the IEEE 802.11be standard. This paper studies two backward-compatible channel access approaches to satisfy the strict quality of service (QoS) requirements of RTA on the transmission latency and packet loss rate that have been considered in the 802.11be Task Group. The first approach is based on limiting the transmission duration of non-RTA frames in the network. The second approach is based on preliminary channel access to ensure the timely delivery of RTA frames. With the developed mathematical model of these approaches, it is shown that both of them can satisfy the RTA QoS requirements. At the same time, the preliminary channel access provides up to 60% higher efficiency of the channel usage by the non-RTA traffic in scenarios with very strict RTA QoS requirements or with low intensity of the RTA traffic.
Adaptive Stress Testing for Adversarial Learning in a Financial Environment
Venue: arXiv cs.AI 2021
Year: 2021

We demonstrate the use of Adaptive Stress Testing to detect and address potential vulnerabilities in a financial environment. We develop a simplified model for credit card fraud detection that utilizes a linear regression classifier based on historical payment transaction data coupled with business rules. We then apply the reinforcement learning model known as Adaptive Stress Testing to train an agent, that can be thought of as a potential fraudster, to find the most likely path to system failure -- successfully defrauding the system. We show the connection between this most likely failure path and the limits of the classifier and discuss how the fraud detection system's business rules can be further augmented to mitigate these failure modes.