The thesis underpinning this study is as follows; it is possible to build machine models that are indistinguishable from the mental models used by humans to generate language to describe their environment. This is to say that the machine model should perform in such a way that a human listener could not discern whether a description of a scene was generated by a human or by the machine model. Many linguistic processes are used to generate even simple scene descriptions and developing machine models of all of them is beyond the scope of this study. The goal of this study is, therefore, to model a sufficient part of the scene description process, operating in a sufficiently realistic environment, so that the likelihood of being able to build machine models of the remaining processes, operating in the real world, can be established. The relatively under-researched process of reference object selection is chosen as the focus of this study. A reference object is, for instance, the `table' in the phrase ``The flowers are on the table''. This study demonstrates that the reference selection process is of similar complexity to others involved in generating scene descriptions which include: assigning prepositions, selecting reference frames and disambiguating objects (usually termed `generating referring expressions'). The secondary thesis of this study is therefore; it is possible to build a machine model that is indistinguishable from the mental models used by humans in selecting reference objects. Most of the practical work in the study is aimed at establishing this. An environment sufficiently near to the real-world for the machine models to operate on is developed as part of this study. It consists of a series of 3-dimensional scenes containing multiple objects that are recognisable to humans and `readable' by the machine models. The rationale for this approach is discussed. The performance of human subjects in describing this environment is evaluated, and measures by which the human performance can be compared to the performance of the machine models are discussed. The machine models used in the study are variants on Bayesian networks. A new approach to learning the structure of a subset of Bayesian networks is presented. Simple existing Bayesian classifiers such as naive or tree augmented naive networks did not perform sufficiently well. A significant result of this study is that useful machine models for reference object choice are of such complexity that a machine learning approach is required. Earlier proposals based on sum-of weighted-factors or similar constructions will not produce satisfactory models. Two differently derived sets of variables are used and compared in this study. Firstly variables derived from the basic geometry of the scene and the properties of objects are used. Models built from these variables match the choice of reference of a group of humans some 73\% of the time, as compared with 90\% for the median human subject. Secondly variables derived from `ray casting' the scene are used. Ray cast variables performed much worse than anticipated, suggesting that humans use object knowledge as well as immediate perception in the reference choice task. Models combining geometric and ray-cast variables match the choice of reference of the group of humans some 76\% of the time. Although niether of these machine models are likely to be indistinguishable from a human, the reference choices are rarely, if ever, entirely ridiculous. A secondary goal of the study is to contribute to the understanding of the process by which humans select reference objects. Several statistically significant results concerning the necessary complexity of the human models and the nature of the variables within them are established. Problems that remain with both the representation of the near-real-world environment and the Bayesian models and variables used within them are detailed. While these problems cast some doubt on the results it is argued that solving these problems is possible and would, on balance, lead to improved performance of the machine models. This further supports the assertion that machine models producing reference choices indistinguishable from those of humans are possible.

The main theme of this dissertation is the study of polytopes arising from binary multi-way contingency tables and characteristic imsets for Bayesian networks. Firstly, we study on three-way tables whose entries are independent Bernoulli ran- dom variables with canonical parameters under no three-way interaction generalized linear models. Here, we use the sequential importance sampling (SIS) method with the conditional Poisson (CP) distribution to sample binary three-way tables with the sufficient statistics, i.e., all two-way marginal sums, fixed. Compared with Monte Carlo Markov Chain (MCMC) approach with a Markov basis (MB), SIS procedure has the advantage that it does not require expensive or prohibitive pre-computations. Note that this problem can also be considered as estimating the number of lattice points inside the polytope defined by the zero-one and two-way marginal constraints. The theorems in Chapter 2 give the parameters for the CP distribution on each column when it is sampled. In this chapter, we also present the algorithms, the simulation results, and the results for Samson’s monks data. Bayesian networks, a part of the family of probabilistic graphical models, are widely applied in many areas and much work has been done in model selections for Bayesian networks. The second part of this dissertation investigates the problem of finding the optimal graph by using characteristic imsets, where characteristic imsets are defined as 0-1 vector representations of Bayesian networks which are unique up to Markov equivalence. Characteristic imset polytopes are defined as the convex hull of all characteristic imsets we consider. It was proven that the problem of finding optimal Bayesian network for a specific dataset can be converted to a linear programming problem over the characteristic imset polytope [51]. In Chapter 3, we first consider characteristic imset polytopes for all diagnosis models and show that these polytopes are direct product of simplices. Then we give the combinatorial description of all edges and all facets of these polytopes. At the end of this chapter, we generalize these results to the characteristic imset polytopes for all Bayesian networks with a fixed underlying ordering of nodes. Chapter 4 includes discussion and future work on these two topics.

Este trabalho fornece uma avaliação empírica do desempenho de Redes Bayesianas quando se impõe restrições à largura de árvore de sua estrutura. O desempenho da rede é visto especificamente pela sua capacidade de generalização e também pela precisão da inferência em problemas de tomada de decisão. Resultados preliminares sugerem que adicionar essa restrição na largura de árvore diminui a capacidade de generalização do modelo além de tornar a tarefa de aprendizado mais difícil. / This work provides an empirical evaluation of the performance of Bayesian Networks when treewidth is bounded. The performance of the network is viewed as its generalizability and also as the accuracy of inference in decision making problems. Preliminary results suggest that adding constraints to treewidth decreases the model performance on unseen data and makes the corresponding optimization problem more difficult.

Este trabalho fornece uma avaliação empírica do desempenho de Redes Bayesianas quando se impõe restrições à largura de árvore de sua estrutura. O desempenho da rede é visto especificamente pela sua capacidade de generalização e também pela precisão da inferência em problemas de tomada de decisão. Resultados preliminares sugerem que adicionar essa restrição na largura de árvore diminui a capacidade de generalização do modelo além de tornar a tarefa de aprendizado mais difícil. / This work provides an empirical evaluation of the performance of Bayesian Networks when treewidth is bounded. The performance of the network is viewed as its generalizability and also as the accuracy of inference in decision making problems. Preliminary results suggest that adding constraints to treewidth decreases the model performance on unseen data and makes the corresponding optimization problem more difficult.