Significant strides have been made toward designing better generative models in recent years. Despite this progress, however, state-of-the-art approaches are still largely unable to capture complex global structure in data. For example, images of buildings typically contain spatial patterns such as windows repeating at regular intervals; state-of-the-art generative methods can’t easily reproduce these structures. We propose to address this problem by incorporating programs representing global structure into the generative model—e.g., a 2D for-loop may represent a configuration of windows. Furthermore, we propose a framework for learning these models by leveraging program synthesis to generate training data. On both synthetic and real-world data, we demonstrate that our approach is substantially better than the state-of-the-art at both generating and completing images that contain global structure.
 There has been much interest recently in generative models, following the introduction of both variational autoencoders (VAEs) BID13 and generative adversarial networks (GANs) BID6 . These models have successfully been applied to a range of tasks, including image generation BID16 , image completion BID10 , texture synthesis BID12 ; BID22 , sketch generation BID7 , and music generation BID3 .Despite their successes, generative models still have difficulty capturing global structure. For example , consider the image completion task in Figure 1 . The original image (left) is of a building, for which the global structure is a 2D repeating pattern of windows. Given a partial image (middle left), the goal is to predict the completion of the image. As can be seen, a state-of-the-art image completion algorithm has trouble reconstructing the original image (right) BID10 .1 Real-world data often contains such global structure, including repetitions, reflectional or rotational symmetry, or even more complex patterns.In the past few years, program synthesis Solar- BID17 has emerged as a promising approach to capturing patterns in data BID4 ; BID19 . The idea is that simple programs can capture global structure that evades state-of-the-art deep neural networks. A key benefit of using program synthesis is that we can design the space of programs to capture different kinds of structure-e.g., repeating patterns BID5 , symmetries, or spatial structure BID2 -depending on the application domain. The challenge is that for the most part, existing approaches have synthesized programs that operate directly over raw data. Since programs have difficulty operating over perceptual data, existing approaches have largely been limited to very simple data-e.g., detecting 2D repeating patterns of simple shapes BID5 .We propose to address these shortcomings by synthesizing programs that represent the underlying structure of high-dimensional data. In particular, we decompose programs into two parts: (i) a sketch s ∈ S that represents the skeletal structure of the program BID17 , with holes that are left unimplemented, and (ii) components c ∈ C that can be used to fill these holes. We consider perceptual components-i.e ., holes in the sketch are filled with raw perceptual data. For example, the original image x * partial image x part completionx (ours) completionx (baseline) Figure 1 : The task is to complete the partial image x part (middle left) into an image that is close to the original image x * (left). By incorporating programmatic structure into generative models, the completion (middle right) is able to substantially outperform a state-of-the-art baseline BID10 (right) . Note that not all non-zero pixels in the sketch rendering retain the same value in the completed picture due to the nature of the following completion process program represents the structure in the original image x * in Figure 1 (left). The black text is the sketch, and the component is a sub-image taken from the given partial image. Then, the draw function renders the given sub-image at the given position. We call a sketch whose holes are filled with perceptual components a neurosymbolic program.Building on these ideas, we propose an approach called program-synthesis (guided) generative models (PS-GM) that combines neurosymbolic programs representing global structure with state-of-the-art deep generative models. By incorporating programmatic structure, PS-GM substantially improves the quality of these state-of-the-art models. As can be seen, the completion produced using PS-GM (middle right of Figure 1 ) substantially outperforms the baseline.We show that PS-GM can be used for both generation from scratch and for image completion. The generation pipeline is shown in FIG0 . At a high level, PS-GM for generation operates in two phases:• First, it generates a program that represents the global structure in the image to be generated.In particular, it generates a program P = (s, c) representing the latent global structure in the image (left in FIG0 , where s is a sketch (in the domain considered here, a list of 12 for-loop structures) and c is a perceptual component (in the domain considered here, a list of 12 sub-images).• Second, our algorithm executes P to obtain a structure rendering x struct representing the program as an image (middle of FIG0 ). Then, our algorithm uses a deep generative model to complete x struct into a full image (right of FIG0 ). The structure in x struct helps guide the deep generative model towards images that preserve the global structure.The image-completion pipeline (see Figure 3 ) is similar.Training these models end-to-end is challenging, since a priori, ground truth global structure is unavailable. Furthermore, representative global structure is very sparse, so approaches such as reinforcement learning do not scale. Instead, we leverage domain-specific program synthesis algorithms to produce examples of programs that represent global structure of the training data. In particular, we propose a synthesis algorithm tailored to the image domain , which extracts programs with nested for-loops that can represent multiple 2D repeating patterns in images. Then, we use these example programs as supervised training data.Our programs can capture rich spatial structure in the training data. For example, in FIG0 , the program structure encodes a repeating structure of 0's and 2's on the whole image, and a separate repeating structure of 3's on the right-hand side of the image. Furthermore, in Figure 1 , the generated image captures the idea that the repeating pattern of windows does not extend to the bottom portion of the image.for loop from sampled program P structure rendering x struct completed image x (ii) Our model executes P to obtain a rendering of the program structure x struct ( middle). (iii) Our model samples a completion x ∼ p θ (x | s, c) of x struct into a full image (right).Contributions. We propose an architecture of generative models that incorporates programmatic structure, as well as an algorithm for training these models (Section 2). Our learning algorithm depends on a domain-specific program synthesis algorithm for extracting global structure from the training data; we propose such an algorithm for the image domain (Section 3). Finally, we evaluate our approach on synthetic data and on a real-world dataset of building facades Tyleček &Šára (2013), both on the task of generation from scratch and on generation from a partial image. We show that our approach substantially outperforms several state-of-the-art deep generative models (Section 4).Related work. There has been growing interest in applying program synthesis to machine learning, for purposes of interpretability BID21 ; BID20 , safety BID1 , and lifelong learning BID19 . Most relevantly, there has been interest in using programs to capture structure that deep learning models have difficulty representing Lake et al. (2015) ; BID4 ; . For instance, BID4 proposes an unsupervised learning algorithm for capturing repeating patterns in simple line drawings; however, not only are their domains simple, but they can only handle a very small amount of noise. Similarly, BID5 captures 2D repeating patterns of simple circles and polygons; however, rather than synthesizing programs with perceptual components, they learn a simple mapping from images to symbols as a preprocessing step. The closest work we are aware of is BID19 , which synthesizes programs with neural components (i.e., components implemented as neural networks); however, their application is to lifelong learning, not generation, and to learning with supervision (labels) rather than to unsupervised learning of structure.Additionally, there has been work extending neural module networks BID0 to generative models BID2 . These algorithms essentially learn a collection of neural components that can be composed together based on hierarchical structure . However, they require that the structure be available (albeit in natural language form) both for training the model and for generating new images.Finally, there has been work incorporating spatial structure into generative models for generating textures BID12 ; however, their work only handles a single infinite repeating 2D pattern. In contrast, we can capture a rich variety of spatial patterns parameterized by a space of programs. For example, the image in Figure 1 generated by our technique contains different repeating patterns in different parts of the image. We have proposed a new approach to generation that incorporates programmatic structure into state-ofthe-art deep learning models. In our experiments, we have demonstrated the promise of our approach to improve generation of high-dimensional data with global structure that current state-of-the-art deep generative models have difficulty capturing. We leave a number of directions for future work. Most importantly, we have relied on a custom synthesis algorithm to eliminate the need for learning latent program structure. Learning to synthesize latent structure during training is an important direction for future work. In addition, future work will explore more expressive programmatic structures, including if-then-else statements.A EXPERIMENTAL DETAILS
Applying program synthesis to the tasks of image completion and generation within a deep learning framework
{"src": "scitldr-AIC_train", "paper_id": "S1gUCFx4dN"}