Grant: Discovery Grants Program - Individual

Deep learning is currently in the media spotlight due to several impressive feats, including Google's self-driving cars, voice recognition in intelligent personal assistants (Apple's Siri, Google's Now, Microsoft's Cortana, and Amazon's Alexa), and beating a world champion in the game GO. Other notable achievements involve setting new records in image recognition, analyzing particle accelerator data, and predicting the effects of mutations in non-coding DNA on gene expression and disease. Although there is no consensus on the definition of deep learning, deep learning involves modelling a problem domain by learning a multiply-layered network from a large amount of data using specialized computer hardware (graphical processing units rather than central processing units). *One required step in deep learning is inference. Inference means updating the knowledge base according to real-world observations. Sum-Product Networks (SPNs) are a deep learning model that can perform inference in linear time. This is important, since it means that the inference step can be done efficiently. This proposal primarily focuses on further optimizing SPN inference. One objective is to perform SPN inference in sub-linear time. The probabilistic reasoning literature has shown that moving from linear time to sub-linear time can yield significant time savings in practice. Another objective is to incorporate semantics into SPNs. Currently, SPNs lack semantics. Incorporating semantics will bring meaning to the structure of the SPN. This, in turn, can be exploited in at least two ways. First, irrelevant parts of a SPN can be ignored during inference. Second, the SPN itself can be compressed. Both cases can result in faster SPN inference, which then implies faster learning.*We will achieve the above objectives using our extensive history working on semantics in probabilistic inference and by exploiting Darwinian Networks (DNs), which are like looking at Bayesian networks (BNs) through a microscope. DNs have led to the development of Simple Propagation (SP), which is a method for BN inference and empirical results demonstrate that it tends to be faster than Lazy Propagation (LP), a standard approach to BN inference. Moreover, DNs have lead to rp-separation, which is a method for testing independence in BNs. Experimental results show that this approach is 53% faster than algorithms (Reachable and Bayes-Ball) for the same purpose. Given these exciting results, we are eager to develop methods for sub-linear SPN inference.