Publications

Conditions for indexability of restless bandits and an
$\mathcal{O}\!\left(K^3\right)$
algorithm to compute Whittle index
Nima Akbarzadeh
Aditya Mahajan
Abstract Restless bandits are a class of sequential resource allocation problems concerned with allocating one or more resources among sever… (voir plus)al alternative processes where the evolution of the processes depends on the resources allocated to them. Such models capture the fundamental trade-offs between exploration and exploitation. In 1988, Whittle developed an index heuristic for restless bandit problems which has emerged as a popular solution approach because of its simplicity and strong empirical performance. The Whittle index heuristic is applicable if the model satisfies a technical condition known as indexability. In this paper, we present two general sufficient conditions for indexability and identify simpler-to-verify refinements of these conditions. We then revisit a previously proposed algorithm called the adaptive greedy algorithm which is known to compute the Whittle index for a sub-class of restless bandits. We show that a generalization of the adaptive greedy algorithm computes the Whittle index for all indexable restless bandits. We present an efficient implementation of this algorithm which can compute the Whittle index of a restless bandit with K states in
2022-06-13
Advances in Applied Probability (publié)
doi.org
arxiv.org
Unsupervised Model-based Pre-training for Data-efficient Reinforcement Learning from Pixels
Sai Rajeswar
Pietro Mazzaglia
Tim Verbelen
Alexandre Piché
Bart Dhoedt
Aaron Courville
Alexandre Lacoste
Reinforcement learning (RL) aims at autonomously performing complex tasks. To this end, a reward signal is used to steer the learning proces… (voir plus)s. While successful in many circumstances, the approach is typically data hungry, requiring large amounts of task-specific interaction between agent and environment to learn efficient behaviors. To alleviate this, unsupervised RL proposes to collect data through self-supervised interaction to accelerate task-specific adaptation. However, whether current unsupervised strategies lead to improved generalization capabilities is still unclear, more so when the input observations are high-dimensional. In this work, we advance the field by closing the performance gap in the Unsupervised RL Benchmark, a collection of tasks to be solved in a data-efficient manner, after interacting with the environment in a self-supervised way. Our approach uses unsupervised exploration for collecting experience to pre-train a world model. Then, when fine-tuning for downstream tasks, the agent leverages the learned model and a hybrid planner to efficiently adapt for the given tasks, achieving comparable results to task-specific base-lines, while using 20x less data. We extensively evaluate our work, comparing several exploration methods and improving the fine-tuning process by studying the interactions between the learned components. Furthermore, we investigate the limitations of the pre-trained agent, gaining insights into how these influence the decision process and shedding light on new research directions.
2022-06-13
ICML.cc/2022/Workshop/DARL (inconnu)
openreview.net
openreview.net
Clustering units in neural networks: upstream vs downstream information
Richard D Lange
David Rolnick
Konrad Paul Kording
It has been hypothesized that some form of"modular"structure in artificial neural networks should be useful for learning, compositionality, … (voir plus)and generalization. However, defining and quantifying modularity remains an open problem. We cast the problem of detecting functional modules into the problem of detecting clusters of similar-functioning units. This begs the question of what makes two units functionally similar. For this, we consider two broad families of methods: those that define similarity based on how units respond to structured variations in inputs ("upstream"), and those based on how variations in hidden unit activations affect outputs ("downstream"). We conduct an empirical study quantifying modularity of hidden layer representations of simple feedforward, fully connected networks, across a range of hyperparameters. For each model, we quantify pairwise associations between hidden units in each layer using a variety of both upstream and downstream measures, then cluster them by maximizing their"modularity score"using established tools from network science. We find two surprising results: first, dropout dramatically increased modularity, while other forms of weight regularization had more modest effects. Second, although we observe that there is usually good agreement about clusters within both upstream methods and downstream methods, there is little agreement about the cluster assignments across these two families of methods. This has important implications for representation-learning, as it suggests that finding modular representations that reflect structure in inputs (e.g. disentanglement) may be a distinct goal from learning modular representations that reflect structure in outputs (e.g. compositionality).
2022-06-12
TMLR (accepté)
doi.org
openreview.net
Studying the Practices of Deploying Machine Learning Projects on Docker
Moses Openja
forough majidi
Foutse Khomh
Bhagya Chembakottu
Heng Li
Docker is a containerization service that allows for convenient deployment of websites, databases, applications' APIs, and machine learning … (voir plus)(ML) models with a few lines of code. Studies have recently explored the use of Docker for deploying general software projects with no specific focus on how Docker is used to deploy ML-based projects. In this study, we conducted an exploratory study to understand how Docker is being used to deploy ML-based projects. As the initial step, we examined the categories of ML-based projects that use Docker. We then examined why and how these projects use Docker, and the characteristics of the resulting Docker images. Our results indicate that six categories of ML-based projects use Docker for deployment, including ML Applications, MLOps/ AIOps, Toolkits, DL Frameworks, Models, and Documentation. We derived the taxonomy of 21 major categories representing the purposes of using Docker, including those specific to models such as model management tasks (e.g., testing, training). We then showed that ML engineers use Docker images mostly to help with the platform portability, such as transferring the software across the operating systems, runtimes such as GPU, and language constraints. However, we also found that more resources may be required to run the Docker images for building ML-based software projects due to the large number of files contained in the image layers with deeply nested directories. We hope to shed light on the emerging practices of deploying ML software projects using containers and highlight aspects that should be improved.
2022-06-12
The International Conference on Evaluation and Assessment in Software Engineering 2022 (publié)
doi.org
arxiv.org
Leveraging Integer Linear Programming to Learn Optimal Fair Rule Lists
Ulrich Matchi Aïvodji
Julien Ferry
Sébastien Gambs
Marie-José Huguet
Mohamed
Siala
2022-06-09
Integration of Constraint Programming, Artificial Intelligence, and Operations Research (publié)
doi.org
Ageism and Artificial Intelligence: Protocol for a Scoping Review
Charlene H Chu
Kathleen Leslie
Jiamin Shi
Rune Nyrup
Andria Bianchi
Shehroz S Khan
S. A. Rahimi
Alexandra Lyn
Amanda Grenier
Background Artificial intelligence (AI) has emerged as a major driver of technological development in the 21st century, yet little attention… (voir plus) has been paid to algorithmic biases toward older adults. Objective This paper documents the search strategy and process for a scoping review exploring how age-related bias is encoded or amplified in AI systems as well as the corresponding legal and ethical implications. Methods The scoping review follows a 6-stage methodology framework developed by Arksey and O’Malley. The search strategy has been established in 6 databases. We will investigate the legal implications of ageism in AI by searching grey literature databases, targeted websites, and popular search engines and using an iterative search strategy. Studies meet the inclusion criteria if they are in English, peer-reviewed, available electronically in full text, and meet one of the following two additional criteria: (1) include “bias” related to AI in any application (eg, facial recognition) and (2) discuss bias related to the concept of old age or ageism. At least two reviewers will independently conduct the title, abstract, and full-text screening. Search results will be reported using the PRISMA-ScR (Preferred Reporting Items for Systematic Reviews and Meta-Analyses Extension for Scoping Reviews) reporting guideline. We will chart data on a structured form and conduct a thematic analysis to highlight the societal, legal, and ethical implications reported in the literature. Results The database searches resulted in 7595 records when the searches were piloted in November 2021. The scoping review will be completed by December 2022. Conclusions The findings will provide interdisciplinary insights into the extent of age-related bias in AI systems. The results will contribute foundational knowledge that can encourage multisectoral cooperation to ensure that AI is developed and deployed in a manner consistent with ethical values and human rights legislation as it relates to an older and aging population. We will publish the review findings in peer-reviewed journals and disseminate the key results with stakeholders via workshops and webinars. Trial Registration OSF Registries AMG5P; https://osf.io/amg5p International Registered Report Identifier (IRRID) DERR1-10.2196/33211
2022-06-08
JMIR Research Protocols (publié)
doi.org
On Neural Architecture Inductive Biases for Relational Tasks
Giancarlo Kerg
Sarthak Mittal
David Rolnick
Yoshua Bengio
Blake Richards
Guillaume Lajoie
Current deep learning approaches have shown good in-distribution generalization performance, but struggle with out-of-distribution generaliz… (voir plus)ation. This is especially true in the case of tasks involving abstract relations like recognizing rules in sequences, as we find in many intelligence tests. Recent work has explored how forcing relational representations to remain distinct from sensory representations, as it seems to be the case in the brain, can help artificial systems. Building on this work, we further explore and formalize the advantages afforded by 'partitioned' representations of relations and sensory details, and how this inductive bias can help recompose learned relational structure in newly encountered settings. We introduce a simple architecture based on similarity scores which we name Compositional Relational Network (CoRelNet). Using this model, we investigate a series of inductive biases that ensure abstract relations are learned and represented distinctly from sensory data, and explore their effects on out-of-distribution generalization for a series of relational psychophysics tasks. We find that simple architectural choices can outperform existing models in out-of-distribution generalization. Together, these results show that partitioning relational representations from other information streams may be a simple way to augment existing network architectures' robustness when performing out-of-distribution relational computations.
2022-06-08
ArXiv (prépublication)
doi.org
arxiv.org
Few-shot Question Generation for Personalized Feedback in Intelligent Tutoring Systems
Devang Kulshreshtha
Muhammad Shayan
Robert Belfer
Siva Reddy
Iulian V. Serban
Ekaterina Kochmar
2022-06-07
ArXiv (prépublication)
doi.org
arxiv.org
Looking at the BiG picture: incorporating bipartite graphs in drug response prediction
David Earl Hostallero
Yihui Li
Amin Emad
Online-only supplementary data is available at the journal’s website.
2022-06-07
Bioinformatics (inconnu)
doi.org
Sequential Density Estimation via NCWFAs Sequential Density Estimation via Nonlinear Continuous Weighted Finite Automata
Tianyu Li
Bogdan Mazoure
Guillaume Rabusseau
Weighted finite automata (WFAs) have been widely applied in many fields. One of the classic problems for WFAs is probability distribution es… (voir plus)timation over sequences of discrete symbols. Although WFAs have been extended to deal with continuous input data, namely continuous WFAs (CWFAs), it is still unclear how to approximate density functions over sequences of continuous random variables using WFA-based models, due to the limitation on the expressiveness of the model as well as the tractability of approximating density functions via CWFAs. In this paper, we propose a nonlinear extension to the CWFA model to first improve its expressiveness, we refer to it as the nonlinear continuous WFAs (NCWFAs). Then we leverage the so-called RNADE method, which is a well-known density estimator based on neural networks, and propose the RNADE-NCWFA model. The RNADE-NCWFA model computes a density function by design. We show that this model is strictly more expressive than the Gaussian HMM model, which CWFA cannot approximate. Empirically, we conduct a synthetic experiment using Gaussian HMM generated data. We focus on evaluating the model's ability to estimate densities for sequences of varying lengths (longer length than the training data). We observe that our model performs the best among the compared baseline methods.
2022-06-07
arXiv (prépublication)
doi.org
arxiv.org
The epidemiological impact of the Canadian COVID Alert app
Shuo Sun
Mairead Shaw
Erica E.M. Moodie
Derek Ruths
We analyzed the effectiveness of the Canadian COVID Alert app on reducing COVID-19 infections and deaths due to the COVID-19 virus. … (voir plus) Two separate but complementary approaches were taken. First, we undertook a comparative study to assess how the adoption and usage of the COVID Alert app compared to those of similar apps deployed in other regions. Next, we used data from the COVID Alert server and a range of plausible parameter values to estimate the numbers of infections and deaths averted in Canada using a model that combines information on number of notifications, secondary attack rate, expected fraction of transmissions that could be prevented, quarantine effectiveness, and expected size of the full transmission chain in the absence of exposure notification. The comparative analysis revealed that the COVID Alert app had among the lowest adoption levels among apps that reported usage. Our model indicates that use of the COVID Alert app averted between 6284 and 10,894 infections across the six Canadian provinces where app usage was highest during the March–July 2021 period. This range is equivalent to 1.6–2.9% of the total recorded infections across Canada in that time. Using province-specific case fatality rates, 57–101 deaths were averted during the same period. The number of cases and deaths averted was greatest in Ontario, whereas the proportion of cases and deaths averted was greatest in Newfoundland and Labrador. App impact measures were reported so rarely and so inconsistently by other regions that the relative assessment of impact is inconclusive. While the nationwide rates are low, provinces with widespread adoption of the app showed high ratios of averted cases and deaths (upper bound was greater than 60% of averted cases). This finding suggests that the COVID Alert app, when adopted at sufficient levels, can be an effective public health tool for combatting a pandemic such as COVID-19.
2022-06-06
Canadian Journal of Public Health = Revue Canadienne de Santé Publique (publié)
doi.org
Interacting brains revisited: A cross‐brain network neuroscience perspective
Christian Gerloff
Kerstin Konrad
Danilo Bzdok
Christina Büsing
Vanessa Reindl
Elucidating the neural basis of social behavior is a long‐standing challenge in neuroscience. Such endeavors are driven by attempts to ext… (voir plus)end the isolated perspective on the human brain by considering interacting persons' brain activities, but a theoretical and computational framework for this purpose is still in its infancy. Here, we posit a comprehensive framework based on bipartite graphs for interbrain networks and address whether they provide meaningful insights into the neural underpinnings of social interactions. First, we show that the nodal density of such graphs exhibits nonrandom properties. While the current hyperscanning analyses mostly rely on global metrics, we encode the regions' roles via matrix decomposition to obtain an interpretable network representation yielding both global and local insights. With Bayesian modeling, we reveal how synchrony patterns seeded in specific brain regions contribute to global effects. Beyond inferential inquiries, we demonstrate that graph representations can be used to predict individual social characteristics, outperforming functional connectivity estimators for this purpose. In the future, this may provide a means of characterizing individual variations in social behavior or identifying biomarkers for social interaction and disorders.
2022-06-05
Human Brain Mapping (inconnu)
doi.org