projects

Table of Contents

1. Efficient Matroid-constraint-based Submodular Maximization
2. Post-hoc Out of Distribution Detection
3. Estimation of Epidemic State using Graph Neural Networks

Efficient Matroid-constraint-based Submodular Maximization

Report: [Click here]
Code: [Click here]
Summary: Maximization of monotone submodular functions subject to cardinality constraints has been a topic of interest with various greedy algorithms, with many of these algorithms achieving a \(\left(1 - \frac{1}{e}\right)\) approximation on the optimal solution (OPT) at high computational speeds. However, these variants of classical greedy do not work well on matroid constraints, and only provide a \(\frac{1}{2}\) approximation of OPT. To overcome this, CONTINUOUS-GREEDY was introduced which gives a \(\left(1-\frac{1}{e} -\epsilon\right)\) approximation of OPT but it has a \(O(n^8)\) running time. In spite of that, the algorithm is useful and generalizable. An improvement to the algorithm is ACCELERATED-CONTINUOUS-GREEDY introduced which has \(\widetilde{O}(n^2)\) running time and is much more efficient than the previous version. The project creates support for matroid-based optimization implementation of these two optimization algorithms along with four matroid-constraint-based submodular functions in SUBMODLIB an efficient and scalable Python library for submodular optimization in Python with a C++ optimization engine. We improve the ACCELERATED-CONTINUOUS-GREEDY procedure further, and demonstrate performance on the SAP, GAP and SWP problems.

Post-hoc Out of Distribution Detection

Report: [Click here]
Slides: [Click here]
Code: [Click here]
Summary: We focus on OOD detection, in a classification setting, after a classifier has already been trained (i.e., a post-hoc/post-training setting). Many popular baselines propose score functions to detect OOD data. These score functions should assign low scores to OOD data and high scores to ID data. We introduce a Dirichlet-based scoring function which outperforms other scoring functions, is computationally cheap, can generalize across different OOD settings and has a theoretical backing. In cases when the performance is not good enough, we provide ways to further improve the separability between the ID and OOD data without using a large and diverse auxiliary OOD dataset (like 80 Million Tiny Images and ImageNet-22K) for fine-tuning, unlike many other popular approaches. We further demonstrate that tuned margins don’t always improve the result over different non-parametric energy-based loss functions.

Estimation of Epidemic State using Graph Neural Networks

Report: [Click here]
Code: [Click here]
Summary: Epidemic forecasting provides an opportunity to predict geographic disease spread as well as case counts to better inform public health interventions when outbreaks occur. In this project, we firstly explore the work already done in the domain of epidemics, using both classical machine learning and deep learning. Further, we demonstrate the spread of epidemics using the famous SIR model on random graphs generated by the Erd˝os–Rényi-Gilbert, Watts-Strogatz and Barabási–Albert models. Finally, we construct a graph neural network followed by a fully connected network to predict the category (safe/infected/recovered) a person might be in during an epidemic, while monitoring only a fraction of the nodes – which aligns with the practicality of epidemic monitoring.