OpenRaiser/Intern-Atlas huggingface dataset:
Isomorphism Testing Parameterized by Genus and Beyond
Venue: arXiv cs.DS 2023
Year: 2023

We give an isomorphism test for graphs of Euler genus $g$ running in time $2^{O(g^4 \log g)}n^{O(1)}$. Our algorithm provides the first explicit upper bound on the dependence on $g$ for an fpt isomorphism test parameterized by the Euler genus of the input graphs. The only previous fpt algorithm runs in time $f(g)n$ for some function $f$ (Kawarabayashi 2015). Actually, our algorithm even works when the input graphs only exclude $K_{3,h}$ as a minor. For such graphs, no fpt isomorphism test was known before. The algorithm builds on an elegant combination of simple group-theoretic, combinatorial, and graph-theoretic approaches. In particular, we introduce $(t,k)$-WL-bounded graphs which provide a powerful tool to combine group-theoretic techniques with the standard Weisfeiler-Leman algorithm. This concept may be of independent interest.
Exploring the Latent Space of Autoencoders with Interventional Assays
Venue: arXiv cs.LG 2023
Year: 2023

Autoencoders exhibit impressive abilities to embed the data manifold into a low-dimensional latent space, making them a staple of representation learning methods. However, without explicit supervision, which is often unavailable, the representation is usually uninterpretable, making analysis and principled progress challenging. We propose a framework, called latent responses, which exploits the locally contractive behavior exhibited by variational autoencoders to explore the learned manifold. More specifically, we develop tools to probe the representation using interventions in the latent space to quantify the relationships between latent variables. We extend the notion of disentanglement to take the learned generative process into account and consequently avoid the limitations of existing metrics that may rely on spurious correlations. Our analyses underscore the importance of studying the causal structure of the representation to improve performance on downstream tasks such as generation, interpolation, and inference of the factors of variation.
Egocentric Image Captioning for Privacy-Preserved Passive Dietary Intake Monitoring
Venue: arXiv cs.CV 2023
Year: 2023

Camera-based passive dietary intake monitoring is able to continuously capture the eating episodes of a subject, recording rich visual information, such as the type and volume of food being consumed, as well as the eating behaviours of the subject. However, there currently is no method that is able to incorporate these visual clues and provide a comprehensive context of dietary intake from passive recording (e.g., is the subject sharing food with others, what food the subject is eating, and how much food is left in the bowl). On the other hand, privacy is a major concern while egocentric wearable cameras are used for capturing. In this paper, we propose a privacy-preserved secure solution (i.e., egocentric image captioning) for dietary assessment with passive monitoring, which unifies food recognition, volume estimation, and scene understanding. By converting images into rich text descriptions, nutritionists can assess individual dietary intake based on the captions instead of the original images, reducing the risk of privacy leakage from images. To this end, an egocentric dietary image captioning dataset has been built, which consists of in-the-wild images captured by head-worn and chest-worn cameras in field studies in Ghana. A novel transformer-based architecture is designed to caption egocentric dietary images. Comprehensive experiments have been conducted to evaluate the effectiveness and to justify the design of the proposed architecture for egocentric dietary image captioning. To the best of our knowledge, this is the first work that applies image captioning for dietary intake assessment in real life settings.
Out-of-distribution Generalization in the Presence of Nuisance-Induced Spurious Correlations
Venue: arXiv cs.LG 2023
Year: 2023

In many prediction problems, spurious correlations are induced by a changing relationship between the label and a nuisance variable that is also correlated with the covariates. For example, in classifying animals in natural images, the background, which is a nuisance, can predict the type of animal. This nuisance-label relationship does not always hold, and the performance of a model trained under one such relationship may be poor on data with a different nuisance-label relationship. To build predictive models that perform well regardless of the nuisance-label relationship, we develop Nuisance-Randomized Distillation (NURD). We introduce the nuisance-randomized distribution, a distribution where the nuisance and the label are independent. Under this distribution, we define the set of representations such that conditioning on any member, the nuisance and the label remain independent. We prove that the representations in this set always perform better than chance, while representations outside of this set may not. NURD finds a representation from this set that is most informative of the label under the nuisance-randomized distribution, and we prove that this representation achieves the highest performance regardless of the nuisance-label relationship. We evaluate NURD on several tasks including chest X-ray classification where, using non-lung patches as the nuisance, NURD produces models that predict pneumonia under strong spurious correlations.
Mava: a research library for distributed multi-agent reinforcement learning in JAX
Venue: arXiv cs.LG 2023
Year: 2023

Multi-agent reinforcement learning (MARL) research is inherently computationally expensive and it is often difficult to obtain a sufficient number of experiment samples to test hypotheses and make robust statistical claims. Furthermore, MARL algorithms are typically complex in their design and can be tricky to implement correctly. These aspects of MARL present a difficult challenge when it comes to creating useful software for advanced research. Our criteria for such software is that it should be simple enough to use to implement new ideas quickly, while at the same time be scalable and fast enough to test those ideas in a reasonable amount of time. In this preliminary technical report, we introduce Mava, a research library for MARL written purely in JAX, that aims to fulfill these criteria. We discuss the design and core features of Mava, and demonstrate its use and performance across a variety of environments. In particular, we show Mava's substantial speed advantage, with improvements of 10-100x compared to other popular MARL frameworks, while maintaining strong performance. This allows for researchers to test ideas in a few minutes instead of several hours. Finally, Mava forms part of an ecosystem of libraries that seamlessly integrate with each other to help facilitate advanced research in MARL. We hope Mava will benefit the community and help drive scientifically sound and statistically robust research in the field. The open-source repository for Mava is available at https://github.com/instadeepai/Mava.
Improve Agents without Retraining: Parallel Tree Search with Off-Policy Correction
Venue: arXiv cs.AI 2023
Year: 2023

Tree Search (TS) is crucial to some of the most influential successes in reinforcement learning. Here, we tackle two major challenges with TS that limit its usability: \textit{distribution shift} and \textit{scalability}. We first discover and analyze a counter-intuitive phenomenon: action selection through TS and a pre-trained value function often leads to lower performance compared to the original pre-trained agent, even when having access to the exact state and reward in future steps. We show this is due to a distribution shift to areas where value estimates are highly inaccurate and analyze this effect using Extreme Value theory. To overcome this problem, we introduce a novel off-policy correction term that accounts for the mismatch between the pre-trained value and its corresponding TS policy by penalizing under-sampled trajectories. We prove that our correction eliminates the above mismatch and bound the probability of sub-optimal action selection. Our correction significantly improves pre-trained Rainbow agents without any further training, often more than doubling their scores on Atari games. Next, we address the scalability issue given by the computational complexity of exhaustive TS that scales exponentially with the tree depth. We introduce Batch-BFS: a GPU breadth-first search that advances all nodes in each depth of the tree simultaneously. Batch-BFS reduces runtime by two orders of magnitude and, beyond inference, enables also training with TS of depths that were not feasible before. We train DQN agents from scratch using TS and show improvement in several Atari games compared to both the original DQN and the more advanced Rainbow. The code for BCTS can be found in \url{https://github.com/NVlabs/bcts}.
Improving a neural network model by explanation-guided training for glioma classification based on MRI data
Venue: arXiv cs.CV 2023
Year: 2023

In recent years, artificial intelligence (AI) systems have come to the forefront. These systems, mostly based on Deep learning (DL), achieve excellent results in areas such as image processing, natural language processing, or speech recognition. Despite the statistically high accuracy of deep learning models, their output is often a decision of "black box". Thus, Interpretability methods have become a popular way to gain insight into the decision-making process of deep learning models. Explanation of a deep learning model is desirable in the medical domain since the experts have to justify their judgments to the patient. In this work, we proposed a method for explanation-guided training that uses a Layer-wise relevance propagation (LRP) technique to force the model to focus only on the relevant part of the image. We experimentally verified our method on a convolutional neural network (CNN) model for low-grade and high-grade glioma classification problems. Our experiments show promising results in a way to use interpretation techniques in the model training process.
A comparison of LSTM and GRU networks for learning symbolic sequences
Venue: arXiv cs.LG 2023
Year: 2023

We explore the architecture of recurrent neural networks (RNNs) by studying the complexity of string sequences it is able to memorize. Symbolic sequences of different complexity are generated to simulate RNN training and study parameter configurations with a view to the network's capability of learning and inference. We compare Long Short-Term Memory (LSTM) networks and gated recurrent units (GRUs). We find that an increase in RNN depth does not necessarily result in better memorization capability when the training time is constrained. Our results also indicate that the learning rate and the number of units per layer are among the most important hyper-parameters to be tuned. Generally, GRUs outperform LSTM networks on low-complexity sequences while on high-complexity sequences LSTMs perform better.
Universal approximation and model compression for radial neural networks
Venue: arXiv cs.LG 2023
Year: 2023

We introduce a class of fully-connected neural networks whose activation functions, rather than being pointwise, rescale feature vectors by a function depending only on their norm. We call such networks radial neural networks, extending previous work on rotation equivariant networks that considers rescaling activations in less generality. We prove universal approximation theorems for radial neural networks, including in the more difficult cases of bounded widths and unbounded domains. Our proof techniques are novel, distinct from those in the pointwise case. Additionally, radial neural networks exhibit a rich group of orthogonal change-of-basis symmetries on the vector space of trainable parameters. Factoring out these symmetries leads to a practical lossless model compression algorithm. Optimization of the compressed model by gradient descent is equivalent to projected gradient descent for the full model.
Wireless Network Scheduling with Discrete Propagation Delays: Theorems and Algorithms
Venue: arXiv cs.IT 2023
Year: 2023

This paper focuses on the link scheduling problem in networks where signal delays between nodes are multiples of a time interval. To model such networks, a directed hypergraph is employed, along with an integer matrix that specifies the delays. The link scheduling problem is closely connected to the independent sets of the periodic hypergraph induced by the network model. However, due to the infinite number of vertices, it is impractical to enumerate the independent sets of the periodic hypergraph using generic graph algorithms. To tackle this challenge, a graphical approach is proposed in this paper. The link scheduling rate region is characterized using a finite directed graph called a scheduling graph, which is derived from the network model. A collision-free schedule of the network corresponds to a path in the scheduling graph, and the rate region is determined by the convex hull of the rate vectors associated with the cycles in the scheduling graph. Although existing cycle enumeration algorithms can be employed to calculate the rate region, their computational complexity becomes prohibitively high as the size of the scheduling graph grows exponentially with the number of network links. To address this issue, the dominance property of a special scheduling graph called the step-T scheduling graph is investigated. This property allows the utilization of specific subgraphs of the step-T scheduling graph to characterize the scheduling rate region, achieving a reduction in both the number of cycles and their lengths. For common problems such as calculating the rate region and maximizing a weighted sum of the scheduling rates, algorithms leveraging the dominance property are developed. These algorithms can be more efficient than using generic graph algorithms directly on the scheduling graphs.
Topological synthesis of fluidic pressure-actuated robust compliant mechanisms
Venue: arXiv cs.CE 2023
Year: 2023

This paper presents a robust density-based topology optimization approach for synthesizing pressure-actuated compliant mechanisms. To ensure functionality under manufacturing inaccuracies, the robust or three-field formulation is employed, involving dilated, intermediate and eroded realizations of the design. Darcy's law in conjunction with a conceptualized drainage term is used to model the pressure load as a function of the design vector. The consistent nodal loads are evaluated from the obtained pressure field using the standard finite element method. The objective and load sensitivities are obtained using the adjoint-variable approach. A multi-criteria objective involving both the stiffness and flexibility of the mechanism is employed in the robust formulation, and min-max optimization problems are solved to obtain pressure-actuated inverter, gripper, and contractor compliant mechanisms with different minimum feature sizes. Limitations of the linear elasticity assumptions while designing mechanisms are identified with high pressure loads. Challenges involved in designing finite deformable pressure-actuated compliant mechanisms are presented.
Full-Body Torque-Level Non-linear Model Predictive Control for Aerial Manipulation
Venue: arXiv cs.RO 2023
Year: 2023

Non-linear model predictive control (nMPC) is a powerful approach to control complex robots (such as humanoids, quadrupeds, or unmanned aerial manipulators (UAMs)) as it brings important advantages over other existing techniques. The full-body dynamics, along with the prediction capability of the optimal control problem (OCP) solved at the core of the controller, allows to actuate the robot in line with its dynamics. This fact enhances the robot capabilities and allows, e.g., to perform intricate maneuvers at high dynamics while optimizing the amount of energy used. Despite the many similarities between humanoids or quadrupeds and UAMs, full-body torque-level nMPC has rarely been applied to UAMs. This paper provides a thorough description of how to use such techniques in the field of aerial manipulation. We give a detailed explanation of the different parts involved in the OCP, from the UAM dynamical model to the residuals in the cost function. We develop and compare three different nMPC controllers: Weighted MPC, Rail MPC, and Carrot MPC, which differ on the structure of their OCPs and on how these are updated at every time step. To validate the proposed framework, we present a wide variety of simulated case studies. First, we evaluate the trajectory generation problem, i.e., optimal control problems solved offline, involving different kinds of motions (e.g., aggressive maneuvers or contact locomotion) for different types of UAMs. Then, we assess the performance of the three nMPC controllers, i.e., closed-loop controllers solved online, through a variety of realistic simulations. For the benefit of the community, we have made available the source code related to this work.
Homogenizing Entropy Across Different Environmental Conditions: A Universally Applicable Method for Transforming Continuous Variables
Venue: arXiv cs.IT 2023
Year: 2023

In classical information theory, a causal relationship between two variables is typically modelled by assuming that, for every possible state of one of the variables, there exists a particular distribution of states of the second variable. Let us call these two variables the causal and caused variables, respectively. We shall assume that both variables are continuous and one-dimensional. In this work we consider a procedure to transform each variable, using transformations that are differentiable and strictly increasing. We call these increasing transformations. Any causal relationship (as defined here) is associated with a channel capacity, which is the maximum rate that information could be sent if the causal relationship was used as a signalling system. Channel capacity is unaffected when the two variables are changed by use of increasing transformations. For any causal relationship we show that there is always a way to transform the caused variable such that the entropy associated with the caused variable is independent of the value of the causal variable. Furthermore, the resulting universal entropy has an absolute value that is equal to the channel capacity associated with the causal relationship. This observation may be useful in statistical applications. Also, for any causal relationship, it implies that there is a 'natural' way to transform a continuous caused variable. We also show that, with additional constraints on the causal relationship, a natural increasing transformation of both variables leads to a transformed causal relationship that has properties that might be expected from a well-engineered measuring device.
Medical Profile Model: Scientific and Practical Applications in Healthcare
Venue: arXiv cs.CY 2023
Year: 2023

The paper researches the problem of representation learning for electronic health records. We present the patient histories as temporal sequences of diseases for which embeddings are learned in an unsupervised setup with a transformer-based neural network model. Additionally the embedding space includes demographic parameters which allow the creation of generalized patient profiles and successful transfer of medical knowledge to other domains. The training of such a medical profile model has been performed on a dataset of more than one million patients. Detailed model analysis and its comparison with the state-of-the-art method show its clear advantage in the diagnosis prediction task. Further, we show two applications based on the developed profile model. First, a novel Harbinger Disease Discovery method allowing to reveal disease associated hypotheses and potentially are beneficial in the design of epidemiological studies. Second, the patient embeddings extracted from the profile model applied to the insurance scoring task allow significant improvement in the performance metrics.
Being Together in Place as a Catalyst for Scientific Advance
Venue: arXiv cs.DL 2023
Year: 2023

The COVID-19 pandemic necessitated social distancing at every level of society, including universities and research institutes, raising essential questions concerning the continuing importance of physical proximity for scientific and scholarly advance. Using customized author surveys about the intellectual influence of referenced work on scientists' own papers, combined with precise measures of geographical and semantic distance between focal and referenced works, we find that being at the same institution is strongly associated with intellectual influence on scientists' and scholars' published work. However, this influence increases with intellectual distance: the more different the referenced work done by colleagues at one's institution, the more influential it is on one's own. Universities worldwide constitute places where people doing very different work engage in sustained interactions through departments, committees, seminars, and communities. These interactions come to uniquely influence their published research, suggesting the need to replace rather than displace diverse engagements for sustainable advance.
The Unintended Consequences of Minimizing the Price of Anarchy in Congestion Games
Venue: arXiv cs.GT 2023
Year: 2023

This work focuses on the design of taxes in atomic congestion games, a commonly studied model for competitive resource sharing. While most related studies focus on optimizing either the worst- or best-case performance (i.e., Price of Anarchy (PoA) or Price of Stability (PoS)), we investigate whether optimizing for the PoA has consequences on the PoS. Perhaps surprisingly, our results reveal a fundamental trade-off between the two performance metrics. Our main result demonstrates that the taxation rule that optimizes the PoA inherits a matching PoS, implying that the best outcome is no better than the worst outcome under such a design choice. We then study this trade-off in terms of the Pareto frontier between the PoA and PoS. Our results also establish that any taxes with PoS equal to 1 incur a much higher PoA, and that, in several well-studied cases, the untaxed setting lies strictly above the Pareto frontier.