"Curiouser and curiouser!" Cried Alice.

• Peter Henderson*, Ben Chugg*, Brandon Anderson, Daniel E. Ho. Beyond Ads: Sequential Decision-Making Algorithms in Public Policy. Advances in Neural Information Processing Systems, Causal Inference Challenges in Sequential Decision Making: Bridging Theory and Practice Workshop. 2021.
We explore the promises and challenges of employing sequential decision-making algorithms — such as bandits, reinforcement learning, and active learning — in the public sector. While such algorithms have been heavily studied in settings that are suitable for the private sector (e.g., online advertising), the public sec- tor could greatly benefit from these approaches, but poses unique methodological challenges for machine learning. We highlight several applications of sequential decision-making algorithms in regulation and governance, and discuss areas for further research which would enable them to be more widely applicable, fair, and effective. In particular, ensuring that these systems learn rational, causal decision- making policies can be difficult and requires great care. We also note the potential risks of such deployments and urge caution when conducting work in this area. We hope our work inspires more investigation of public-sector sequential decision-making applications, which provide unique challenges for machine learning researchers and can be socially beneficial.
• Ben Chugg, Daniel E. Ho. Reconciling Risk Allocation and Prevalence Estimation in Public Health Using Batched Bandits. Neural Information Processing Systems, Machine Learning in Public Health Workshop. 2021.
| arXiv
In many public health settings, there is a perceived tension between allocating resources to known vulnerable areas and learning about the overall prevalence of the problem. Inspired by a door-to-door Covid-19 testing program we helped design, we combine multi-armed bandit strategies and insights from sampling theory to demonstrate how to recover accurate prevalence estimates while continuing to allocate resources to at-risk areas. We use the outbreak of an infectious disease as our running example. The public health setting has several characteristics distinguishing it from typical bandit settings, such as distribution shift (the true disease prevalence is changing with time) and batched sampling (multiple decisions must be made simultaneously). Nevertheless, we demonstrate that several bandit algorithms are capable out-performing greedy resource allocation strategies, which often perform worse than random allocation as they fail to notice outbreaks in new areas.
• Ben Chugg*, Brandon Anderson*, Seiji Eicher, Sandy Lee, Daniel E. Ho. Enhancing Environmental Enforcement with Near Real-Time Monitoring: Likelihood-Based Detection of Structural Expansion of Intensive Livestock Farms. Journal of Applied Earth Observation and Geoinformation. 2021.
| journal version | arXiv | Code
Environmental enforcement has historically relied on physical, resource-intensive, and infrequent inspections. Advances in remote sensing and computer vision have the potential to augment compliance monitoring, by providing early warning signals of permit violations. We demonstrate a process for rapid identification of significant structural expansion using satellite imagery and focusing on Concentrated Animal Feeding Operations (CAFOs) as a test case. Unpermitted expansion has been a particular challenge with CAFOs, which pose significant health and environmental risks. Using a new hand-labeled dataset of 175,736 images of 1,513 CAFOs, we combine state-of-the-art building segmentation with a likelihood-based change-point detection model to provide a robust signal of building expansion (AUC = 0.80). A major advantage of this approach is that it is able to work with high-cadence (daily to weekly), but lower resolution (3m/pixel), satellite imagery. It is also highly generalizable and thus provides a near real-time monitoring tool to prioritize enforcement resources to other settings where unpermitted construction poses environmental risk, e.g. zoning, habitat modification, or wetland protection.
• Ben Chugg*, Lisa Lu*, Derek Ouyang*, Ben Anderson, Raymond Ha et al. Evaluation of Allocation Schemes of COVID-19 Testing Resources in a Community-Based Door-to-Door Testing Program. Journals of the American Medical Assocation (JAMA), Health Forum. 2021.
journal version
• Hooman Hashemi, Ben Chugg, Anne Condon. Composable Computation in Leaderless, Discrete Chemical Reaction Networks. International Conference on DNA Computing and Molecular Programming. 2020.
| conference version
We classify the functions $$f:\mathbb{N}^d \rightarrow \mathbb{N}$$ that are stably computable by leaderless, output-oblivious discrete (stochastic) Chemical Reaction Networks (CRNs). CRNs that compute such functions are systems of reactions over species that include $$d$$ designated input species, whose initial counts represent an input $$x \in \mathbb{N}^d$$, and one output species whose eventual count represents $$f(x)$$. Chen et al. showed that the class of functions computable by CRNs is precisely the semilinear functions. In output-oblivious CRNs, the output species is never a reactant. Output-oblivious CRNs are easily composable since a downstream CRN can consume the output of an upstream CRN without affecting its correctness. Severson et al. showed that output-oblivious CRNs compute exactly the subclass of semilinear functions that are eventually the minimum of quilt-affine functions, i.e., affine functions with different intercepts in each of finitely many congruence classes. They call such functions the output-oblivious functions. A leaderless CRN can compute only superadditive functions, and so a leaderless output-oblivious CRN can compute only superadditive, output-oblivious functions. In this work we show that a function $$f:\mathbb{N}^d \rightarrow \mathbb{N}$$ is stably computable by a leaderless, output-oblivious CRN if and only if it is superadditive and output-oblivious.
• Ben Chugg, Will Evans, Kelvin Wong. Simultaneous Visibility Representations of Undirected Graphs. Canadian Conference on Computational Geometry. 2020. Journal of Computational Geometry. 2021.
| journal version | arXiv
We consider the problem of determining if a pair of undirected graphs $$\langle G_V,G_H\rangle$$, which share the same vertex set, has a representation using opaque geometric shapes for vertices, and vertical/horizontal visibility between shapes to determine the edges of $$G_V/G_H$$. While such a simultaneous visibility representation of two graphs can be determined efficiently if the direction of the required visibility for each edge is provided (and the vertex shapes are sufficiently simple), it was unclear if edge direction is critical for efficiency. We show that the problem is NP-complete without that information, even for graphs that are only slightly more complex than paths. In addition, we characterize which pairs of paths have simultaneous visibility representations using fixed orientation L-shapes. This narrows the range of possible graph families for which determining simultaneous visibility representation is non-trivial yet not NP-hard.
• Ben Chugg. The Graph-Simplex Correspondence and its Algorithmic Foundations. M.Sc. Thesis, The University of Oxford. 2019.
| pdf
We present and study the graph-simplex correspondence—a tool providing a series of relationships between weighted, undirected graphs on $$n$$ vertices and simplices in $$(n-1)$$-dimensional Euclidean space. The core of the correspondence is a bijection between graphs and hyperacute simplices, first uncovered by Miroslav Fiedler. We consolidate Fiedler's work on the subject and expand on it in several ways.
The first relates purely to the mathematical properties of the correspondence. Among other things, we extend the correspondence to the normalized Laplacian matrix $$\widehat{L}_G$$ (whereas previously only the combinatorial Laplacian, $$L_G$$, had been used), develop new equations and inequalities relating aspects of the simplex to those of the graph, and give an isometry between a graph's "inverse combinatorial simplex" and an $$n$$-dimensional polytope arising from the Laplacian's pseudoinverse.
Secondly, we examine the algorithmic underpinnings and consequences of the correspondence. We begin by demonstrating that it can be used to draw conclusions about the computational complexity of various geometric problems. We then provide lower bounds on the complexity of transitioning between graphs and simplices, and end by studying low dimensional representations of the simplices. This provides theoretical justification for recent empirical work on Laplacian eigenmaps.
Of possible independent interest, we provide a formula for the non-zero eigenvalues of $$\widehat{L}_G$$ in terms of the total weight of spanning trees in the graph $$G$$, relate the volume of an arbitrary simplex to the eigenvalues of the Gram matrix of its dual simplex (an object we introduce), and give an equation for the adjugate of $$\widehat{L}_G$$ in terms of the weights of the vertices in $$G$$.
• Ben Chugg, Takanori Maehara. Submodular Stochastic Probing with Prices. International Conference on Control, Decision, and Information Technologies. 2019.
| arXiv
We introduce Stochastic Probing with Prices (SPP), a variant of the Stochastic Probing (SP) model in which we must pay a price to probe an element. A SPP problem involves two set systems $$(\mathcal{N} , \mathcal{I}_{in})$$ and $$(\mathcal{N} , \mathcal{I}_{out})$$ where each $$e\in\mathcal{N}$$ is active with probability $$p_e$$. To discover whether an element $$e$$ is active, it must be probed by paying the price $$\Delta_e$$. If an element is probed and is active, then it is irrevocably added to the solution. Moreover, at all times, the set of probed elements must lie in $$\mathcal{I}_{out}$$, and the solution (the set of probed and active elements) must lie in $$\mathcal{I}_{in}$$. The goal is to maximize a submodular set function $$f$$ minus the cost of the probes. We give a bi-criteria approximation algorithm to the online version of this problem, in which the elements are shown to the algorithm in a possibly adversarial order. Our results translate to state-of-the-art approximations for the traditional (online) stochastic probing problem.
• Ben Chugg, Anne Condon, Hooman Hashemi. Output-Oblivious Stochastic Chemical Reaction Networks. International Conference on Principles of Distributed Systems. 2018.
| conference version | arXiv
We classify the functions $$f: \mathbb{N}^2\to \mathbb{N}$$ which are stably computable by output-oblivious Stochastic Chemical Reaction Networks (CRNs), i.e., systems of reactions in which output species are never reactants. While it is known that precisely the semilinear functions are stably computable by CRNs, such CRNs sometimes rely on initially producing too many output species, and then consuming the excess in order to reach a correct stable state. These CRNs may be difficult to integrate into larger systems: if the output of a CRN $$C$$ becomes the input to a downstream CRN $$C'$$, then $$C'$$ could inadvertently consume too many outputs before $$C$$ stabilizes. If, on the other hand, $$C$$ is output-oblivious then $$C'$$ may consume $$C$$'s output as soon as it is available. In this work we prove that a semilinear function $$f : \mathbb{N}^2\to\mathbb{N}$$ is stably computable by an output-oblivious CRN with a leader if and only if it is both increasing and either grid-affine (intuitively, its domains are congruence classes), or the minimum of a finite set of fissure functions (intuitively, functions behaving like the min function).
• Ben Chugg. A Model for Computing in Dynamic, Resource-Limited Environments. B.Sc Thesis, The University of British Columbia. 2018.