The human ability to think about thinking (“theory of mind”) is a fundamental object of study in many disciplines. In recent decades, researchers across these disciplines have converged on a rich computational paradigm for modeling theory of mind, grounded in recursive probabilistic reasoning. However, practitioners often find programming in this paradigm challenging: first, because thinking-about-thinking is confusing for programmers, and second, because models are slow to run. This paper presents memo , a new domain-specific probabilistic programming language that overcomes these challenges: first, by providing specialized syntax and semantics for theory of mind, and second, by taking a unique approach to inference that scales well on modern hardware via array programming. memo enables practitioners to write dramatically faster models with much less code, and has already been adopted by several research groups.

Impossible objects, geometric constructions that humans can perceive but that cannot exist in real life, have been a topic of intrigue in visual arts, perception, and graphics, yet no satisfying computer representation of such objects exists. Previous work embeds impossible objects in 3D, cutting them or twisting/bending them in the depth axis. Cutting an impossible object changes its local geometry at the cut, which can hamper downstream graphics applications, such as smoothing, while bending makes it difficult to relight the object. Both of these can invalidate geometry operations, such as distance computation. As an alternative, we introduce Meschers, meshes capable of representing impossible constructions akin to those found in M.C. Escher's woodcuts. Our representation has a theoretical foundation in discrete exterior calculus and supports the use-cases above, as we demonstrate in a number of example applications. Moreover, because we can do discrete geometry processing on our representation, we can inverse-render impossible objects. We also compare our representation to cut and bend representations of impossible objects.

SA Conference Papers ’24, December 03–06, 2024, Tokyo, Japan

A single panel of a comic book can say a lot: it can depict not only where the characters currently are, but also their motions, their motivations, their emotions, and what they might do next. More generally, humans routinely infer complex sequences of past and future events from a *static snapshot* of a *dynamic scene*, even in situations they have never seen before. In this paper, we model how humans make such rapid and flexible inferences. Building on a long line of work in cognitive science, we offer a Monte Carlo algorithm whose inferences correlate well with human intuitions in a wide variety of domains, while only using a small, cognitively-plausible number of samples. Our key technical insight is a surprising connection between our inference problem and Monte Carlo path tracing, which allows us to apply decades of ideas from the computer graphics community to this seemingly-unrelated theory of mind task.

Working with any gradient-based machine learning algorithm involves the tedious task of tuning the optimizer's hyperparameters, such as its step size. Recent work has shown how the step size can itself be optimized alongside the model parameters by manually deriving expressions for "hypergradients" ahead of time.We show how to automatically compute hypergradients with a simple and elegant modification to backpropagation. This allows us to easily apply the method to other optimizers and hyperparameters (e.g. momentum coefficients). We can even recursively apply the method to its own hyper-hyperparameters, and so on ad infinitum. As these towers of optimizers grow taller, they become less sensitive to the initial choice of hyperparameters. We present experiments validating this for MLPs, CNNs, and RNNs. Finally, we provide a simple PyTorch implementation of this algorithm (see http://people.csail.mit.edu/kach/gradient-descent-the-ultimate-optimizer).

We consider the task of mapping pseudocode to executable code, assuming a one-to-one correspondence between lines of pseudocode and lines of code. Given test cases as a mechanism to validate programs, we search over the space of possible translations of the pseudocode to find a program that compiles and passes the test cases. While performing a best-first search, compilation errors constitute 88.7% of program failures. To better guide this search, we learn to predict the line of the program responsible for the failure and focus search over alternative translations of the pseudocode for that line. For evaluation, we collected the SPoC dataset (Search-based Pseudocode to Code) containing 18,356 C++ programs with human-authored pseudocode and test cases. Under a budget of 100 program compilations, performing search improves the synthesis success rate over using the top-one translation of the pseudocode from 25.6% to 44.7%.

When designing a type system, we may want to mechanically check the design to guide its further development. We describe algorithms that perform symbolic reasoning about executable models of type systems. The algorithms support three queries. First, they check type soundness and synthesize a counterexample program if such a soundness bug is found. Second, they compare two versions of a type system, synthesizing a program accepted by one but rejected by the other. Third, they minimize the size of synthesized counterexample programs. These algorithms symbolically evaluate typecheckers and interpreters, producing formulas that characterize the set of programs that fail or succeed in the typechecker and the interpreter. However, symbolically evaluating interpreters poses efficiency challenges, which are caused by having to merge execution paths of the various possible input programs. Our main contribution is the bonsai tree , a novel symbolic representation of programs and program states that addresses these challenges. Bonsai trees encode complex syntactic information in terms of logical constraints, enabling more efficient merging. We implement these algorithms in the Bonsai tool, an assistant for type system designers. We perform case studies on how Bonsai helps test and explore a variety of type systems. Bonsai efficiently synthesizes counterexamples for soundness bugs previously inaccessible to automatic tools and is the first automated tool to find a counterexample for the recently discovered Scala soundness bug SI-9633.

Spectral reflectance is an inherent material property which can be used for material identification tasks. We present a nonlinear algorithm for estimating surface spectral reflectance of the ground material using images acquired by an airborne sensor. The nonlinear algorithm separates the atmospheric and illumination effects from the measured spectral radiance corresponding to a single pixel in the image to recover the surface spectral reflectance. A low-dimensional subspace model for the reflectance spectra is used for the algorithm. The algorithm also considers the interdependence of the path radiance and illumination spectra by using a coupled subspace model. We have analyzed the accuracy of the algorithm over simulated and real 0.4-1.74-mum sensor radiance spectra.

We present algorithms to estimate the surface spectral reflectance and the orientation of a ground material corresponding to a pixel in a hyperspectral image acquired by an airborne sensor under unknown atmospheric conditions. A physics-based image formation model is used in which the spectral reflectance of the ground material, the orientation of the material surface, and the atmospheric and illumination conditions determine the sensor radiance of a pixel. The algorithm uses low-dimensional subspace models for the surface reflectance, solar radiance, sky radiance, and path-scattered radiance. The common inter-dependence of the illumination spectra and path- scattered radiance on the environmental condition and viewing geometry is considered by using a coupled subspace model. We use nonlinear optimization methods to estimate the subspace parameters and orientation parameters used in the physics-based image formation model. The subspace and orientation parameters are used for surface reflectance and orientation recovery. We have tested the utility of the algorithms using a large set of 0.42-1.74 micron sensor radiance spectra simulated for varying surface orientations of different materials.

The spectral radiance measured by an airborne sensor is dependent on the spectral reflectance of the ground material, the orientation of the material surface, and the atmospheric and illumination conditions. We present a nonlinear algorithm for estimating surface spectral reflectance of a surface on the ground from the spectral radiance measured by an airborne sensor. The nonlinear separation algorithm uses a low-dimensional subspace model for the reflectance spectra. The algorithm also considers the inter-dependence of the path radiance and illumination spectra by using a coupled subspace model. We have applied the algorithm to a large set of 0.4-1.74 micron sensor radiance spectra. We have examined the use of the recovered reflectance vectors for material identification over a database of materials from the US geological Survey (USGS) library. We also extend the nonlinear algorithm to estimate the reflectance spectra of materials having varying orientations. We have applied the algorithm to 0.42-1.74 micron sensor radiance spectra in digital imaging and remote sensing image generation (DIRSIG) model scenes that contain 3D objects.