Discrete location analysis is one of the most widely studied branches of operations research, whose applications arise in a wide variety of settings. This thesis describes a powerful new approach to facility location problems - that of message passing inference in probabilistic graphical models. Using this framework, we develop new heuristic algorithms, as well as a new approximation algorithm for a particular problem type. In machine learning applications, facility location can be seen a discrete formulation of clustering and mixture modeling problems. We apply the developed algorithms to such problems in computer vision. We tackle the problem of motion segmentation in video sequences by formulating it as a facility location instance and demonstrate the advantages of message passing algorithms over current segmentation methods.

Discrete location analysis is one of the most widely studied branches of operations research, whose applications arise in a wide variety of settings. This thesis describes a powerful new approach to facility location problems - that of message passing inference in probabilistic graphical models. Using this framework, we develop new heuristic algorithms, as well as a new approximation algorithm for a particular problem type. In machine learning applications, facility location can be seen a discrete formulation of clustering and mixture modeling problems. We apply the developed algorithms to such problems in computer vision. We tackle the problem of motion segmentation in video sequences by formulating it as a facility location instance and demonstrate the advantages of message passing algorithms over current segmentation methods.

Many tasks in Natural Language Processing (NLP) require us to predict a relational structure over entities. For example, in Semantic Role Labelling we try to predict the ’semantic role’ relation between a predicate verb and its argument constituents. Often NLP tasks not only involve related entities but also relations that are stochastically correlated. For instance, in Semantic Role Labelling the roles of different constituents are correlated: we cannot assign the agent role to one constituent if we have already assigned this role to another. Statistical Relational Learning (also known as First Order Probabilistic Logic) allows us to capture the aforementioned nature of NLP tasks because it is based on the notions of entities, relations and stochastic correlations between relationships. It is therefore often straightforward to formulate an NLP task using a First Order probabilistic language such as Markov Logic. However, the generality of this approach comes at a price: the process of finding the relational structure with highest probability, also known as maximum a posteriori (MAP) inference, is often inefficient, if not intractable. In this work we seek to improve the efficiency of MAP inference for Statistical Relational Learning. We propose a meta-algorithm, namely Cutting Plane Inference (CPI), that iteratively solves small subproblems of the original problem using any existing MAP technique and inspects parts of the problem that are not yet included in the current subproblem but could potentially lead to an improved solution. Our hypothesis is that this algorithm can dramatically improve the efficiency of existing methods while remaining at least as accurate. We frame the algorithm in Markov Logic, a language that combines First Order Logic and Markov Networks. Our hypothesis is evaluated using two tasks: Semantic Role Labelling and Entity Resolution. It is shown that the proposed algorithm improves the efficiency of two existing methods by two orders of magnitude and leads an approximate method to more probable solutions. We also give show that CPI, at convergence, is guaranteed to be at least as accurate as the method used within its inner loop. Another core contribution of this work is a theoretic and empirical analysis of the boundary conditions of Cutting Plane Inference. We describe cases when Cutting Plane Inference will definitely be difficult (because it instantiates large networks or needs many iterations) and when it will be easy (because it instantiates small networks and needs only few iterations).

Submitted by ÉRICO FERNANDO DE OLIVEIRA MARTINS null (profericomartins@gmail.com) on 2017-10-20T20:50:58Z No. of bitstreams: 1 TESE_PPGCC_EFOM_FINAL.pdf: 19920753 bytes, checksum: 0914bc57a7e2e403ee03d576a74e8e57 (MD5) / Approved for entry into archive by Luiz Galeffi (luizgaleffi@gmail.com) on 2017-10-23T19:41:39Z (GMT) No. of bitstreams: 1 martins_efo_dr_prud.pdf: 19920753 bytes, checksum: 0914bc57a7e2e403ee03d576a74e8e57 (MD5) / Made available in DSpace on 2017-10-23T19:41:39Z (GMT). No. of bitstreams: 1 martins_efo_dr_prud.pdf: 19920753 bytes, checksum: 0914bc57a7e2e403ee03d576a74e8e57 (MD5) Previous issue date: 2017-08-25 / Fundação de Amparo à Pesquisa do Estado de Mato Grosso (FAPEMAT) / Os processos convencionais de extração de rodovias em imagens digitais não costumam fazer uso de informações a priori e normalmente não há uma preocupação a respeito da padronização necessária para que os resultados das extrações sejam utilizados em Infraestruturas de Dados Espaciais (IDE). Por consequência, os resultados dessas extrações acabam sendo geometricamente robustos, porém fragmentados em relação ao contexto e a seu padrão de estrutura, ou seja, necessitarão de um grande esforço do operador humano para que possam se tornar elegíveis à IDE, contrariando uma das principais motivações para o desenvolvimento de métodos (semi-) automáticos de extração, que é desonerar o operador humano de tarefas repetitivas e enfadonhas. Neste contexto a hipótese motivadora desta pesquisa levanta a questão: “adaptando processos clássicos de extração de rodovias para a integração de dados geoespaciais preexistentes, será possível apresentar um método para atualização sistemática de malha rodoviária em área rural, que seja capaz de preservar informações e estruturas preexistentes? ”. Como resposta é apresentado aqui um método para a atualização da malha rodoviária em formato vetorial, advinda de bases de dados cartográficas elaboradas segundo uma IDE, por meio da integração de diferentes tipos de dados, preservando sua integridade. No decorrer das três etapas em que está organizado o método o arquivo vetorial sofrerá uma série de modificações geométricas, configuradas em distintos processos, começando com uma conflação vetor-para-vetor com o mapa de rodovias inferido a partir de trajetórias de deslocamento com objetivo de identificar ramos ausentes na malha e agregá-los (Expansão da Malha); seguida de uma conflação vetor-para-vetor com os segmentos de eixo de rodovias extraídos de uma imagem sintética obtida a partir das imagens RapidEye (Ajuste da Malha Expandida); finalizando com a etapa de refino pela aplicação das snakes de redes sobre a malha ajustada e a imagem sintética (Refino da Malha Ajustada) e por fim uma atribuição da componente altimétrica por meio de um Modelo Digital de Superfície, resultando em um arquivo vetorial geometricamente atualizado e expandido para o espaço tridimensional, com estrutura e atributos preservados. Os experimentos realizados demonstraram a robustez do método, com a média do RMSE da malha inicial em 50,86 m, alcançando 18,72 m na primeira etapa do método (expansão da malha), reduzindo para 7,25 m na etapa seguinte (ajuste da malha), e para 3,74 m na etapa final (refino da malha). Assim, o processo finaliza com um RMSE médio de 3,74 m e um desvio-padrão de 2,86 m, que permite o enquadramento da malha resultante no PEC-PCD 1:50.000 classe A, devidamente adequado aos padrões da IDE. / Conventional road extraction processes in digital imagery do not usually make use of a priori information and there is usually no concern about the standardization required for extraction results to be used in Spatial Data Infrastructures (SDI). As a result, these extractions turn out to be geometrically robust but fragmented in relation to the context and their structure pattern, that is, they will require a great effort from the human operator so that they can become eligible for SDI, contrary to one of the main motivations for the development of (semi) automatic extraction methods, which is to deprive the human operator of repetitive and tedious tasks. In this context the motivating hypothesis of this research raises the question: "adapting classic processes of road extraction for the integration of preexisting geospatial data, it will be possible to present a method for systematic updating of road network in rural area, which is able to preserve preexisting information and structures? ". A method for updating the road network in vector format from cartographic databases elaborated according to an SDI is presented here, through the integration of different types of data, preserving its integrity. During the three stages in which the method is organized the vector file will undergo a series of geometric modifications, configured in different processes, starting with a vector-to-vector conflation with the road map inferred from displacement paths with the objective of identify missing branches in the mesh and aggregate them (Mesh Expansion); followed by vector-to-vector conflation with the segments of road axes extracted from a synthetic image obtained from the RapidEye (Expanded Mesh Adjustment) images; finishing with the refining step by applying the network snakes on the adjusted mesh and the synthetic image (Refining the Adjusted Mesh) and finally an assignment of the altimetric component through a Digital Surface Model, resulting in a vector file geometrically updated and expanded for the three-dimensional space with preserved structure and attributes. The experiments showed the robustness of the method, with the average RMSE of the initial mesh in 50.86 m, reaching 18.72 m in the first step of the method (mesh expansion), reducing to 7.25 m in the next step (mesh adjustment), and to 3.74 m in the final step (mesh refining). Thus, the process ends with an average RMSE of 3.74 m and a standard deviation of 2.86 m, which allows framing of the resulting mesh in the 1: 50,000 Class A PEC-PCD, duly adapted to SDI standards. / FAPEMAT: 231463/2013

Cette thèse contribue au développement de formalismes efficaces pour représenter l’information incertaine. Les formalismes existants tels que la théorie des probabilités ou la théorie des possibilités sont parmi les cadres les plus connus et utilisés pour représenter ce type d’information. Différentes extensions (e.g. théorie des probabilités imprécises, théorie des possibilités à intervalles) ont été proposées pour traiter des informations incomplètes ou des connaissances mal-connues, ainsi que pour raisonner avec les connaissances d’un groupe d’experts. Les contributions de cette thèse sont divisées en deux parties. Dans la première partie, nous développons le conditionnement dans le cadre des possibilités à intervalles et dans le cadre des possibilités ensemblistes. Conditionner dans le cadre standard diffère que l’on considère l’échelle possibiliste qualitative ou quantitative. Notre travail traite les deux définitions du conditionnement possibiliste. Ce qui nous amène à étudier une nouvelle extension de la logique possibiliste, définie comme logique possibiliste ensembliste, et son opérateur de conditionnement dans le cadre possibiliste qualitatif. Ces résultats, plus spécialement en termes de complexité, nous amène à étudier les transformations, plus précisément des transformations du cadre probabiliste vers le cadre possibiliste. En effet, nous analysons des propriétés les tâches de raisonnement comme la marginalisation et le conditionnement. Nous nous attaquons aussi aux transformations des probabilités imprécises vers les possibilités avec un intérêt particulier pour l’inférence MAP. / This thesis contributes to the development of efficient formalisms to handle uncertain information. Existing formalisms such as probability theory or possibility theory are among the most known and used settings to represent such information. Extensions and generalizations (e.g. imprecise probability theory, interval-based possibilistic theory) have been provided to handle uncertainty such as incomplete and ill-known knowledge and reasoning with the knowledge of a group of experts. We are particularly interested in reasoning tasks within these theories such as conditioning. The contributions of this thesis are divided in two parts. In the first part, we tackle conditioning in interval-based possibilistic framework and set-valued possibilistic framework. The purpose is to develop a conditioning machinery for interval-based possibilistic logic. Conditioning in a standard possibilistic setting differs whether we consider a qualitative or quantitative scale. Our works deal with both definitions of possibilistic conditioning. This leads us to investigate a new extension of possibilisticlogic, defined as set-valued possibilistic logic, and its conditioning machinery in the qualitative possibilistic setting. These results, especially in terms of complexity, lead us to study transformations, more precisely from probability to possibility theories. The second part of our contributions deals with probability-possibility transformation procedures. Indeed, we analyze properties of reasoning tasks such as conditioning and marginalization. We also tackle transformations from imprecise probability theory to possibility theory with a particular interest in MAP inference.

Les relaxations en problème d’optimisation linéaire jouent un rôle central en inférence du maximum a posteriori (map) dans les champs aléatoires de Markov discrets. Nous étudions ici les avantages offerts par les méthodes de Newton pour résoudre efficacement le problème dual (au sens de Lagrange) d’une reformulation lisse du problème. Nous comparons ces dernières aux méthodes de premier ordre, à la fois en terme de vitesse de convergence et de robustesse au mauvais conditionnement du problème. Nous exposons donc un cadre général pour l’apprentissage non-supervisé basé sur le transport optimal et les régularisations parcimonieuses. Nous exhibons notamment une approche prometteuse pour résoudre le problème de la préimage dans l’acp à noyau. Du point de vue de l’optimisation, nous décrivons le calcul du gradient d’une version lisse de la norme p de Schatten et comment cette dernière peut être utilisée dans un schéma de majoration-minimisation. / Numerical optimization and machine learning have had a fruitful relationship, from the perspective of both theory and application. In this thesis, we present an application oriented take on some inference and learning problems. Linear programming relaxations are central to maximum a posteriori (MAP) inference in discrete Markov Random Fields (MRFs). Especially, inference in higher-order MRFs presents challenges in terms of efficiency, scalability and solution quality. In this thesis, we study the benefit of using Newton methods to efficiently optimize the Lagrangian dual of a smooth version of the problem. We investigate their ability to achieve superior convergence behavior and to better handle the ill-conditioned nature of the formulation, as compared to first order methods. We show that it is indeed possible to obtain an efficient trust region Newton method, which uses the true Hessian, for a broad range of MAP inference problems. Given the specific opportunities and challenges in the MAP inference formulation, we present details concerning (i) efficient computation of the Hessian and Hessian-vector products, (ii) a strategy to damp the Newton step that aids efficient and correct optimization, (iii) steps to improve the efficiency of the conjugate gradient method through a truncation rule and a pre-conditioner. We also demonstrate through numerical experiments how a quasi-Newton method could be a good choice for MAP inference in large graphs. MAP inference based on a smooth formulation, could greatly benefit from efficient sum-product computation, which is required for computing the gradient and the Hessian. We show a way to perform sum-product computation for trees with sparse clique potentials. This result could be readily used by other algorithms, also. We show results demonstrating the usefulness of our approach using higher-order MRFs. Then, we discuss potential research topics regarding tightening the LP relaxation and parallel algorithms for MAP inference.Unsupervised learning is an important topic in machine learning and it could potentially help high dimensional problems like inference in graphical models. We show a general framework for unsupervised learning based on optimal transport and sparse regularization. Optimal transport presents interesting challenges from an optimization point of view with its simplex constraints on the rows and columns of the transport plan. We show one way to formulate efficient optimization problems inspired by optimal transport. This could be done by imposing only one set of the simplex constraints and by imposing structure on the transport plan through sparse regularization. We show how unsupervised learning algorithms like exemplar clustering, center based clustering and kernel PCA could fit into this framework based on different forms of regularization. We especially demonstrate a promising approach to address the pre-image problem in kernel PCA. Several methods have been proposed over the years, which generally assume certain types of kernels or have too many hyper-parameters or make restrictive approximations of the underlying geometry. We present a more general method, with only one hyper-parameter to tune and with some interesting geometric properties. From an optimization point of view, we show how to compute the gradient of a smooth version of the Schatten p-norm and how it can be used within a majorization-minimization scheme. Finally, we present results from our various experiments.