OpenRaiser/Intern-Atlas huggingface dataset:
Relational Graph Neural Network Design via Progressive Neural Architecture Search
Venue: arXiv cs.LG 2022
Year: 2022

We propose a novel solution to addressing a long-standing dilemma in the representation learning of graph neural networks (GNNs): how to effectively capture and represent useful information embedded in long-distance nodes to improve the performance of nodes with low homophily without leading to performance degradation in nodes with high homophily. This dilemma limits the generalization capability of existing GNNs. Intuitively, interactions with distant nodes introduce more noise for a node than those with close neighbors. However, in most existing works, messages being passed among nodes are mingled together, which is inefficient from a communication perspective. Our solution is based on a novel, simple, yet effective aggregation scheme, resulting in a ladder-style GNN architecture, namely LADDER-GNN. Specifically, we separate messages from different hops, assign different dimensions for them, and then concatenate them to obtain node representations. Such disentangled representations facilitate improving the information-to-noise ratio of messages passed from different hops. To explore an effective hop-dimension relationship, we develop a conditionally progressive neural architecture search strategy. Based on the searching results, we further propose an efficient approximate hop-dimension relation function to facilitate the rapid configuration of the proposed LADDER-GNN. We verify the proposed LADDER-GNN on seven diverse semi-supervised node classification datasets. Experimental results show that our solution achieves better performance than most existing GNNs. We further analyze our aggregation scheme with two commonly used GNN architectures, and the results corroborate that our scheme outperforms existing schemes in classifying low homophily nodes by a large margin.
Some hypersurfaces over finite fields, minimal codes and secret sharing schemes
Venue: arXiv cs.IT 2022
Year: 2022

Linear error-correcting codes can be used for constructing secret sharing schemes; however finding in general the access structures of these secret sharing schemes and, in particular, determining efficient access structures is difficult. Here we investigate the properties of certain algebraic hypersurfaces over finite fields, whose intersection numbers with any hyperplane only takes a few values; these varieties give rise to $q$-divisible linear codes with at most $5$ weights. Furthermore, for $q$ odd these codes turn out to be minimal and we characterize the access structures of the secret sharing schemes based on their dual codes. Indeed, the secret sharing schemes thus obtained are democratic, that is each participant belongs to the same number of minimal access sets and can easily be described.
Fast Nearest Neighbor Machine Translation
Venue: arXiv cs.CL 2022
Year: 2022

Though nearest neighbor Machine Translation ($k$NN-MT) \citep{khandelwal2020nearest} has proved to introduce significant performance boosts over standard neural MT systems, it is prohibitively slow since it uses the entire reference corpus as the datastore for the nearest neighbor search. This means each step for each beam in the beam search has to search over the entire reference corpus. $k$NN-MT is thus two-orders slower than vanilla MT models, making it hard to be applied to real-world applications, especially online services. In this work, we propose Fast $k$NN-MT to address this issue. Fast $k$NN-MT constructs a significantly smaller datastore for the nearest neighbor search: for each word in a source sentence, Fast $k$NN-MT first selects its nearest token-level neighbors, which is limited to tokens that are the same as the query token. Then at each decoding step, in contrast to using the entire corpus as the datastore, the search space is limited to target tokens corresponding to the previously selected reference source tokens. This strategy avoids search through the whole datastore for nearest neighbors and drastically improves decoding efficiency. Without loss of performance, Fast $k$NN-MT is two-orders faster than $k$NN-MT, and is only two times slower than the standard NMT model. Fast $k$NN-MT enables the practical use of $k$NN-MT systems in real-world MT applications. The code is available at \url{https://github.com/ShannonAI/fast-knn-nmt}
DeepChange: A Large Long-Term Person Re-Identification Benchmark with Clothes Change
Venue: arXiv cs.CV 2022
Year: 2022

Existing person re-identification (re-id) works mostly consider short-term application scenarios without clothes change. In real-world, however, we often dress differently across space and time. To solve this contrast, a few recent attempts have been made on long-term re-id with clothes change. Currently, one of the most significant limitations in this field is the lack of a large realistic benchmark. In this work, we contribute a large, realistic long-term person re-identification benchmark, named as DeepChange. It has several unique characteristics: (1) Realistic and rich personal appearance (e.g., clothes and hair style) and variations: Highly diverse clothes change and styles, with varying reappearing gaps in time from minutes to seasons, different weather conditions (e.g., sunny, cloudy, windy, rainy, snowy, extremely cold) and events (e.g., working, leisure, daily activities). (2) Rich camera setups: Raw videos were recorded by 17 outdoor varying resolution cameras operating in a real-world surveillance system. (3) The currently largest number of (17) cameras, (1, 121) identities, and (178, 407) bounding boxes, over the longest time span (12 months). Further, we investigate multimodal fusion strategies for tackling the clothes change challenge. Extensive experiments show that our fusion models outperform a wide variety of state-of-the-art models on DeepChange. Our dataset and documents are available at https://github.com/PengBoXiangShang/deepchange.
Blockchain Assisted Federated Learning over Wireless Channels: Dynamic Resource Allocation and Client Scheduling
Venue: arXiv cs.DC 2022
Year: 2022

The blockchain technology has been extensively studied to enable distributed and tamper-proof data processing in federated learning (FL). Most existing blockchain assisted FL (BFL) frameworks have employed a third-party blockchain network to decentralize the model aggregation process. However, decentralized model aggregation is vulnerable to pooling and collusion attacks from the third-party blockchain network. Driven by this issue, we propose a novel BFL framework that features the integration of training and mining at the client side. To optimize the learning performance of FL, we propose to maximize the long-term time average (LTA) training data size under a constraint of LTA energy consumption. To this end, we formulate a joint optimization problem of training client selection and resource allocation (i.e., the transmit power and computation frequency at the client side), and solve the long-term mixed integer non-linear programming based on a Lyapunov technique. In particular, the proposed dynamic resource allocation and client scheduling (DRACS) algorithm can achieve a trade-off of [$\mathcal{O}(1/V)$, $\mathcal{O}(\sqrt{V})$] to balance the maximization of the LTA training data size and the minimization of the LTA energy consumption with a control parameter $V$. Our experimental results show that the proposed DRACS algorithm achieves better learning accuracy than benchmark client scheduling strategies with limited time or energy consumption.
Emotional Voice Conversion: Theory, Databases and ESD
Venue: arXiv cs.CL 2022
Year: 2022

In this paper, we first provide a review of the state-of-the-art emotional voice conversion research, and the existing emotional speech databases. We then motivate the development of a novel emotional speech database (ESD) that addresses the increasing research need. With this paper, the ESD database is now made available to the research community. The ESD database consists of 350 parallel utterances spoken by 10 native English and 10 native Chinese speakers and covers 5 emotion categories (neutral, happy, angry, sad and surprise). More than 29 hours of speech data were recorded in a controlled acoustic environment. The database is suitable for multi-speaker and cross-lingual emotional voice conversion studies. As case studies, we implement several state-of-the-art emotional voice conversion systems on the ESD database. This paper provides a reference study on ESD in conjunction with its release.
Q-attention: Enabling Efficient Learning for Vision-based Robotic Manipulation
Venue: arXiv cs.RO 2022
Year: 2022

Despite the success of reinforcement learning methods, they have yet to have their breakthrough moment when applied to a broad range of robotic manipulation tasks. This is partly due to the fact that reinforcement learning algorithms are notoriously difficult and time consuming to train, which is exacerbated when training from images rather than full-state inputs. As humans perform manipulation tasks, our eyes closely monitor every step of the process with our gaze focusing sequentially on the objects being manipulated. With this in mind, we present our Attention-driven Robotic Manipulation (ARM) algorithm, which is a general manipulation algorithm that can be applied to a range of sparse-rewarded tasks, given only a small number of demonstrations. ARM splits the complex task of manipulation into a 3 stage pipeline: (1) a Q-attention agent extracts relevant pixel locations from RGB and point cloud inputs, (2) a next-best pose agent that accepts crops from the Q-attention agent and outputs poses, and (3) a control agent that takes the goal pose and outputs joint actions. We show that current learning algorithms fail on a range of RLBench tasks, whilst ARM is successful.
Greedy-layer Pruning: Speeding up Transformer Models for Natural Language Processing
Venue: arXiv cs.CL 2022
Year: 2022

Fine-tuning transformer models after unsupervised pre-training reaches a very high performance on many different natural language processing tasks. Unfortunately, transformers suffer from long inference times which greatly increases costs in production. One possible solution is to use knowledge distillation, which solves this problem by transferring information from large teacher models to smaller student models. Knowledge distillation maintains high performance and reaches high compression rates, nevertheless, the size of the student model is fixed after pre-training and can not be changed individually for a given downstream task and use-case to reach a desired performance/speedup ratio. Another solution to reduce the size of models in a much more fine-grained and computationally cheaper fashion is to prune layers after the pre-training. The price to pay is that the performance of layer-wise pruning algorithms is not on par with state-of-the-art knowledge distillation methods. In this paper, Greedy-layer pruning is introduced to (1) outperform current state-of-the-art for layer-wise pruning, (2) close the performance gap when compared to knowledge distillation, while (3) providing a method to adapt the model size dynamically to reach a desired performance/speedup tradeoff without the need of additional pre-training phases. Our source code is available on https://github.com/deepopinion/greedy-layer-pruning.
Consistency Regularization for Variational Auto-Encoders
Venue: arXiv cs.LG 2022
Year: 2022

Variational auto-encoders (VAEs) are a powerful approach to unsupervised learning. They enable scalable approximate posterior inference in latent-variable models using variational inference (VI). A VAE posits a variational family parameterized by a deep neural network called an encoder that takes data as input. This encoder is shared across all the observations, which amortizes the cost of inference. However the encoder of a VAE has the undesirable property that it maps a given observation and a semantics-preserving transformation of it to different latent representations. This "inconsistency" of the encoder lowers the quality of the learned representations, especially for downstream tasks, and also negatively affects generalization. In this paper, we propose a regularization method to enforce consistency in VAEs. The idea is to minimize the Kullback-Leibler (KL) divergence between the variational distribution when conditioning on the observation and the variational distribution when conditioning on a random semantic-preserving transformation of this observation. This regularization is applicable to any VAE. In our experiments we apply it to four different VAE variants on several benchmark datasets and found it always improves the quality of the learned representations but also leads to better generalization. In particular, when applied to the Nouveau Variational Auto-Encoder (NVAE), our regularization method yields state-of-the-art performance on MNIST and CIFAR-10. We also applied our method to 3D data and found it learns representations of superior quality as measured by accuracy on a downstream classification task.
The effectiveness of feature attribution methods and its correlation with automatic evaluation scores
Venue: arXiv cs.CV 2022
Year: 2022

Explaining the decisions of an Artificial Intelligence (AI) model is increasingly critical in many real-world, high-stake applications. Hundreds of papers have either proposed new feature attribution methods, discussed or harnessed these tools in their work. However, despite humans being the target end-users, most attribution methods were only evaluated on proxy automatic-evaluation metrics (Zhang et al. 2018; Zhou et al. 2016; Petsiuk et al. 2018). In this paper, we conduct the first user study to measure attribution map effectiveness in assisting humans in ImageNet classification and Stanford Dogs fine-grained classification, and when an image is natural or adversarial (i.e., contains adversarial perturbations). Overall, feature attribution is surprisingly not more effective than showing humans nearest training-set examples. On a harder task of fine-grained dog categorization, presenting attribution maps to humans does not help, but instead hurts the performance of human-AI teams compared to AI alone. Importantly, we found automatic attribution-map evaluation measures to correlate poorly with the actual human-AI team performance. Our findings encourage the community to rigorously test their methods on the downstream human-in-the-loop applications and to rethink the existing evaluation metrics.
Pho(SC)-CTC -- A Hybrid Approach Towards Zero-shot Word Image Recognition
Venue: arXiv cs.CV 2022
Year: 2022

Annotating words in a historical document image archive for word image recognition purpose demands time and skilled human resource (like historians, paleographers). In a real-life scenario, obtaining sample images for all possible words is also not feasible. However, Zero-shot learning methods could aptly be used to recognize unseen/out-of-lexicon words in such historical document images. Based on previous state-of-the-art method for zero-shot word recognition Pho(SC)Net, we propose a hybrid model based on the CTC framework (Pho(SC)-CTC) that takes advantage of the rich features learned by Pho(SC)Net followed by a connectionist temporal classification (CTC) framework to perform the final classification. Encouraging results were obtained on two publicly available historical document datasets and one synthetic handwritten dataset, which justifies the efficacy of Pho(SC)-CTC and Pho(SC)Net.
PIGLeT: Language Grounding Through Neuro-Symbolic Interaction in a 3D World
Venue: arXiv cs.CL 2022
Year: 2022

We propose PIGLeT: a model that learns physical commonsense knowledge through interaction, and then uses this knowledge to ground language. We factorize PIGLeT into a physical dynamics model, and a separate language model. Our dynamics model learns not just what objects are but also what they do: glass cups break when thrown, plastic ones don't. We then use it as the interface to our language model, giving us a unified model of linguistic form and grounded meaning. PIGLeT can read a sentence, simulate neurally what might happen next, and then communicate that result through a literal symbolic representation, or natural language. Experimental results show that our model effectively learns world dynamics, along with how to communicate them. It is able to correctly forecast "what happens next" given an English sentence over 80% of the time, outperforming a 100x larger, text-to-text approach by over 10%. Likewise, its natural language summaries of physical interactions are also judged by humans as more accurate than LM alternatives. We present comprehensive analysis showing room for future work.
$L_0$ Isotonic Regression With Secondary Objectives
Venue: arXiv cs.DS 2022
Year: 2022

We provide algorithms for isotonic regression minimizing $L_0$ error (Hamming distance). This is also known as monotonic relabeling, and is applicable when labels have a linear ordering but not necessarily a metric. There may be exponentially many optimal relabelings, so we look at secondary criteria to determine which are best. For arbitrary ordinal labels the criterion is maximizing the number of labels which are only changed to an adjacent label (and recursively apply this). For real-valued labels we minimize the $L_p$ error. For linearly ordered sets we also give algorithms which minimize the sum of the $L_p$ and weighted $L_0$ errors, a form of penalized (regularized) regression. We also examine $L_0$ isotonic regression on multidimensional coordinate-wise orderings. Previous algorithms took $Θ(n^3)$ time, but we reduce this to $o(n^{3/2})$.
Shapley Counterfactual Credits for Multi-Agent Reinforcement Learning
Venue: arXiv cs.AI 2022
Year: 2022

Centralized Training with Decentralized Execution (CTDE) has been a popular paradigm in cooperative Multi-Agent Reinforcement Learning (MARL) settings and is widely used in many real applications. One of the major challenges in the training process is credit assignment, which aims to deduce the contributions of each agent according to the global rewards. Existing credit assignment methods focus on either decomposing the joint value function into individual value functions or measuring the impact of local observations and actions on the global value function. These approaches lack a thorough consideration of the complicated interactions among multiple agents, leading to an unsuitable assignment of credit and subsequently mediocre results on MARL. We propose Shapley Counterfactual Credit Assignment, a novel method for explicit credit assignment which accounts for the coalition of agents. Specifically, Shapley Value and its desired properties are leveraged in deep MARL to credit any combinations of agents, which grants us the capability to estimate the individual credit for each agent. Despite this capability, the main technical difficulty lies in the computational complexity of Shapley Value who grows factorially as the number of agents. We instead utilize an approximation method via Monte Carlo sampling, which reduces the sample complexity while maintaining its effectiveness. We evaluate our method on StarCraft II benchmarks across different scenarios. Our method outperforms existing cooperative MARL algorithms significantly and achieves the state-of-the-art, with especially large margins on tasks with more severe difficulties.
Fast Splitting Algorithms for Sparsity-Constrained and Noisy Group Testing
Venue: arXiv cs.IT 2022
Year: 2022

In group testing, the goal is to identify a subset of defective items within a larger set of items based on tests whose outcomes indicate whether at least one defective item is present. This problem is relevant in areas such as medical testing, DNA sequencing, communication protocols, and many more. In this paper, we study (i) a sparsity-constrained version of the problem, in which the testing procedure is subjected to one of the following two constraints: items are finitely divisible and thus may participate in at most $γ$ tests; or tests are size-constrained to pool no more than $ρ$ items per test; and (ii) a noisy version of the problem, where each test outcome is independently flipped with some constant probability. Under each of these settings, considering the for-each recovery guarantee with asymptotically vanishing error probability, we introduce a fast splitting algorithm and establish its near-optimality not only in terms of the number of tests, but also in terms of the decoding time. While the most basic formulations of our algorithms require $Ω(n)$ storage for each algorithm, we also provide low-storage variants based on hashing, with similar recovery guarantees.
A note on the network coloring game: A randomized distributed $(Δ+1)$-coloring algorithm
Venue: arXiv cs.DM 2022
Year: 2022

The network coloring game has been proposed in the literature of social sciences as a model for conflict-resolution circumstances. The players of the game are the vertices of a graph with $n$ vertices and maximum degree $Δ$. The game is played over rounds, and in each round all players simultaneously choose a color from a set of available colors. Players have local information of the graph: they only observe the colors chosen by their neighbors and do not communicate or cooperate with one another. A player is happy when she has chosen a color that is different from the colors chosen by her neighbors, otherwise she is unhappy, and a configuration of colors for which all players are happy is a proper coloring of the graph. It has been shown in the literature that, when the players adopt a particular greedy randomized strategy, the game reaches a proper coloring of the graph within $O(\log(n))$ rounds, with high probability, provided the number of colors available to each player is at least $Δ+2$. In this note we show that a modification of the aforementioned greedy strategy yields likewise a proper coloring of the graph, provided the number of colors available to each player is at least $Δ+1$, and results in a simple randomized distributed algorithm for the $(Δ+1)$-coloring problem..
Asymptotics of representation learning in finite Bayesian neural networks
Venue: arXiv cs.LG 2022
Year: 2022

Recent works have suggested that finite Bayesian neural networks may sometimes outperform their infinite cousins because finite networks can flexibly adapt their internal representations. However, our theoretical understanding of how the learned hidden layer representations of finite networks differ from the fixed representations of infinite networks remains incomplete. Perturbative finite-width corrections to the network prior and posterior have been studied, but the asymptotics of learned features have not been fully characterized. Here, we argue that the leading finite-width corrections to the average feature kernels for any Bayesian network with linear readout and Gaussian likelihood have a largely universal form. We illustrate this explicitly for three tractable network architectures: deep linear fully-connected and convolutional networks, and networks with a single nonlinear hidden layer. Our results begin to elucidate how task-relevant learning signals shape the hidden layer representations of wide Bayesian neural networks.