Probabilistic graphical models have been successfully applied to a wide variety of fields such as computer vision, natural language processing, robotics, and many more. However, for large scale problems represented using unrestricted probabilistic graphical models, exact inference is often intractable, which means that the model cannot compute the correct value of a joint probability query in a reasonable time. In general, approximate inference has been used to address this intractability, in which the exact joint probability is approximated. An increasingly popular alternative is tractable models. These models are constrained such that exact inference is efficient. To offer efficient exact inference, tractable models either benefit from graph-theoretic properties, such as bounded treewidth, or structural properties such as local structures, determinism, or symmetry. An appealing group of probabilistic models that capture local structures and determinism includes arithmetic circuits (ACs) and sum-product networks (SPNs), in which marginal and conditional queries can be answered efficiently. In this dissertation, we describe ID-SPN, a state-of-the-art SPN learner as well as novel methods for learning tractable graphical models in a discriminative setting, in particular through introducing Generalized ACs, which combines ACs and neural networks. Using extensive experiments, we show that the proposed methods often achieves better performance comparing to selected baselines. This dissertation includes previously published and unpublished co-authored material. / 10000-01-01

The sum-product network (SPN) is a recently-proposed generative, probabilistic model that is guaranteed to compute any joint or any marginal probability in time linear in the size of the model. An SPN is represented as a directed, acyclic graph (DAG) of sum and product nodes, with univariate probability distributions at the leaves. It is important to learn the structure of this DAG since the set of distributions representable by an SPN is constrained by it. We present the first batch structure learning algorithm for SPNs and show its advantage over learning the parameters of an SPN with fixed architecture. We propose a search algorithm for learning the structure of an SPN and show that its ability to learn a DAG-structured SPN makes it better for some tasks than algorithms that only learn tree-structured SPNs. We adapt the structure search algorithm to learn the structure of an SPN in the online setting and show that two other methods for online SPN structure learning are slower or learn models with lower likelihood. We also propose to combine SPNs with an autoencoder to model image data; this application of SPN structure learning shows that both models benefit from being combined.We are also the first to propose a distinction between nonmonotone and monotone SPNs, or SPNs with negative edge-weights and those without, respectively. We prove several important properties of nonmonotone SPNs, propose algorithms for learning a special class of nonmonotone SPN called the twin SPNs, and show that allowing negative edge-weights can help twin SPNs model some distributions more compactly than monotone SPNs.

Multi-label classification consists of learning a function that is capable of mapping an object to a set of relevant labels. It has applications such as the association of genes with biological functions, semantic classification of scenes and text categorization. Traditional classification (i.e., single-label) is therefore a particular case of multi-label classification in which each object is associated with exactly one label. A successful approach to constructing classifiers is to obtain a probabilistic model of the relation between object attributes and labels. This model can then be used to classify objects, finding the most likely prediction by computing the marginal probability or the most probable explanation (MPE) of the labels given the attributes. Depending on the probabilistic models family chosen, such inferences may be intractable when the number of labels is large. Sum-Product Networks (SPN) are deep probabilistic models, that allow tractable marginal inference. Nevertheless, as with many other probabilistic models, performing MPE inference is NP- hard. Although, SPNs have already been used successfully for traditional classification tasks (i.e. single-label), there is no in-depth investigation on the use of SPNs for Multi-Label classification. In this work we investigate the use of SPNs for Multi-Label classification. We compare several algorithms for learning SPNs combined with different proposed approaches for classification. We show that SPN-based multi-label classifiers are competitive against state-of-the-art classifiers, such as Random k-Labelsets with Support Vector Machine and MPE inference on CutNets, in a collection of benchmark datasets. / A classificação Multi-Rótulo consiste em aprender uma função que seja capaz de mapear um objeto para um conjunto de rótulos relevantes. Ela possui aplicações como associação de genes com funções biológicas, classificação semântica de cenas e categorização de texto. A classificação tradicional, de rótulo único é, portanto, um caso particular da Classificação Multi-Rótulo, onde cada objeto está associado com exatamente um rótulo. Uma abordagem bem sucedida para classificação é obter um modelo probabilístico da relação entre atributos do objeto e rótulos. Esse modelo pode então ser usado para classificar objetos, encon- trando a predição mais provável por meio da probabilidade marginal ou a explicação mais provavél dos rótulos dados os atributos. Dependendo da família de modelos probabilísticos escolhidos, tais inferências podem ser intratáveis quando o número de rótulos é grande. As redes Soma-Produto (SPN, do inglês Sum Product Network) são modelos probabilísticos profundos, que permitem inferência marginal tratável. No entanto, como em muitos outros modelos probabilísticos, a inferência da explicação mais provavél é NP-difícil. Embora SPNs já tenham sido usadas com sucesso para tarefas de classificação tradicionais, não existe investigação aprofundada no uso de SPNs para classificação Multi-Rótulo. Neste trabalho, investigamos o uso de SPNs para classificação Multi-Rótulo. Comparamos vários algoritmos de aprendizado de SPNs combinados com diferentes abordagens propostos para classi- ficação. Mostramos que os classificadores Multi-Rótulos baseados em SPN são competitivos contra classificadores estado-da-arte, como Random k-Labelsets usando Máquinas de Suporte Vetorial e inferência exata da explicação mais provavél em CutNets, em uma coleção de conjuntos de dados de referência.

Multi-label classification consists of learning a function that is capable of mapping an object to a set of relevant labels. It has applications such as the association of genes with biological functions, semantic classification of scenes and text categorization. Traditional classification (i.e., single-label) is therefore a particular case of multi-label classification in which each object is associated with exactly one label. A successful approach to constructing classifiers is to obtain a probabilistic model of the relation between object attributes and labels. This model can then be used to classify objects, finding the most likely prediction by computing the marginal probability or the most probable explanation (MPE) of the labels given the attributes. Depending on the probabilistic models family chosen, such inferences may be intractable when the number of labels is large. Sum-Product Networks (SPN) are deep probabilistic models, that allow tractable marginal inference. Nevertheless, as with many other probabilistic models, performing MPE inference is NP- hard. Although, SPNs have already been used successfully for traditional classification tasks (i.e. single-label), there is no in-depth investigation on the use of SPNs for Multi-Label classification. In this work we investigate the use of SPNs for Multi-Label classification. We compare several algorithms for learning SPNs combined with different proposed approaches for classification. We show that SPN-based multi-label classifiers are competitive against state-of-the-art classifiers, such as Random k-Labelsets with Support Vector Machine and MPE inference on CutNets, in a collection of benchmark datasets. / A classificação Multi-Rótulo consiste em aprender uma função que seja capaz de mapear um objeto para um conjunto de rótulos relevantes. Ela possui aplicações como associação de genes com funções biológicas, classificação semântica de cenas e categorização de texto. A classificação tradicional, de rótulo único é, portanto, um caso particular da Classificação Multi-Rótulo, onde cada objeto está associado com exatamente um rótulo. Uma abordagem bem sucedida para classificação é obter um modelo probabilístico da relação entre atributos do objeto e rótulos. Esse modelo pode então ser usado para classificar objetos, encon- trando a predição mais provável por meio da probabilidade marginal ou a explicação mais provavél dos rótulos dados os atributos. Dependendo da família de modelos probabilísticos escolhidos, tais inferências podem ser intratáveis quando o número de rótulos é grande. As redes Soma-Produto (SPN, do inglês Sum Product Network) são modelos probabilísticos profundos, que permitem inferência marginal tratável. No entanto, como em muitos outros modelos probabilísticos, a inferência da explicação mais provavél é NP-difícil. Embora SPNs já tenham sido usadas com sucesso para tarefas de classificação tradicionais, não existe investigação aprofundada no uso de SPNs para classificação Multi-Rótulo. Neste trabalho, investigamos o uso de SPNs para classificação Multi-Rótulo. Comparamos vários algoritmos de aprendizado de SPNs combinados com diferentes abordagens propostos para classi- ficação. Mostramos que os classificadores Multi-Rótulos baseados em SPN são competitivos contra classificadores estado-da-arte, como Random k-Labelsets usando Máquinas de Suporte Vetorial e inferência exata da explicação mais provavél em CutNets, em uma coleção de conjuntos de dados de referência.