We prove a new bound on a version of the sum-product problem studied by Chang. By introducing several combinatorial tools, this expands upon a method of Croot and Hart which used the Tarry-Escott problem to build distinct sums from polynomials with specific vanishing properties. We also study other aspects of the sum-product problem such as a method to prove a dual to a result of Elekes and Ruzsa and a conjecture of J. Solymosi on combinatorial geometry. Lastly, we study two combinatorial problems on sumsets over the reals. The first involves finding Freiman isomorphisms of real-valued sets that also preserve the order of the original set. The second applies results from the former in proving a new Balog-Szemeredi type theorem for real-valued sets.

We demonstrate new results in additive combinatorics, including a proof of a conjecture by J. Solymosi: for every epsilon > 0, there exists delta > 0 such that, given n² points in a grid formation in R², if L is a set of lines in general position such that each line intersects at least n^{1-delta} points of the grid, then |L| < n^epsilon. This result implies a conjecture of Gy. Elekes regarding a uniform statistical version of Freiman's theorem for linear functions with small image sets.

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.

A Factor Graph (FG -- http://en.wikipedia.org/wiki/Factor_graph) is a structure used to find solutions to problems that can be represented as a Probabilistic Graphical Model (PGM). They consist of interconnected variable nodes and factor nodes, which iteratively compute and pass messages to each other. FGs can be applied to solve decoding of forward error correcting codes, Markov chains and Markov Random Fields, Kalman Filtering, Fourier Transforms, and even some games such as Sudoku. In this paper, a framework is presented for rapid prototyping of hardware implementations of FG-based applications. The FG developer specifies aspects of the application, such as graphical structure, factor computation, and message passing algorithm, and the framework returns a design. A system of Python scripts and Verilog Hardware Description Language templates together are used to generate the HDL source code for the application. The generated designs are vendor/platform agnostic, but currently target the Xilinx Virtex-6-based ML605. The framework has so far been primarily applied to construct Low Density Parity Check (LDPC) decoders. The characteristics of a large basket of generated LDPC decoders, including contemporary 802.11n decoders, have been examined as a verification of the system and as a demonstration of its capabilities. As a further demonstration, the framework has been applied to construct a Sudoku solver. / Master of Science

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.

<p>Low-density parity-check codes have recently received much attention because of their excellent performance and the availability of a simple iterative decoder. The decoder, however, requires large amounts of memory, which causes problems with memory consumption. </p><p>We investigate a new decoding scheme for low density parity check codes to address this problem. The basic idea is to define a reliability measure and a threshold, and stop updating the messages for a bit whenever its reliability is higher than the threshold. We also consider some modifications to this scheme, including a dynamic threshold more suitable for codes with cycles, and a scheme with soft thresholds which allow the possibility of removing a decision which have proved wrong. </p><p>By exploiting the bits different rates of convergence we are able to achieve an efficiency of up to 50% at a bit error rate of less than 10^-5. The efficiency should roughly correspond to the power consumption of a hardware implementation of the algorithm.</p>

Low-density parity-check codes have recently received much attention because of their excellent performance and the availability of a simple iterative decoder. The decoder, however, requires large amounts of memory, which causes problems with memory consumption. We investigate a new decoding scheme for low density parity check codes to address this problem. The basic idea is to define a reliability measure and a threshold, and stop updating the messages for a bit whenever its reliability is higher than the threshold. We also consider some modifications to this scheme, including a dynamic threshold more suitable for codes with cycles, and a scheme with soft thresholds which allow the possibility of removing a decision which have proved wrong. By exploiting the bits different rates of convergence we are able to achieve an efficiency of up to 50% at a bit error rate of less than 10^-5. The efficiency should roughly correspond to the power consumption of a hardware implementation of the algorithm.

We will survey some of the major directions of research in arithmetic combinatorics and their connections to other fields. We will then discuss three new results. The first result will generalize a structural theorem from Balog and Szemerédi. The second result will establish a new tool in incidence geometry, which should prove useful in attacking combinatorial estimates. The third result evolved from the famous sum-product problem, by providing a partial categorization of bivariate polynomial set functions which induce exponential expansion on all finite sets of real numbers.

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.