In this dissertation, we exhibit two instances of polyhedra in combinatorial convex geometry. The first instance arises in the context of Ehrhart theory, and the polyhedra are the central objects of study. The second instance arises in algebraic statistics, and the polyhedra act as a conduit through which we study a nonpolyhedral problem. In the first case, we examine combinatorial and algebraic properties of the Ehrhart h*-polynomial of the r-stable (n,k)-hypersimplices. These are a family of polytopes which form a nested chain of subpolytopes within the (n,k)-hypersimplex. We show that a well-studied unimodular triangulation of the (n,k)-hypersimplex restricts to a triangulation of each r-stable (n,k)-hypersimplex within. We then use this triangulation to compute the facet-defining inequalities of these polytopes. In the k=2 case, we use shelling techniques to devise a combinatorial interpretation of the coefficients of the h*-polynomials in terms of independent sets of certain graphs. From this, we then extract some results on unimodality. We also characterize the Gorenstein r-stable (n,k)-hypersimplices, and we conclude that these also have unimodal h*-polynomials. In the second case, for a graph G on p vertices we consider the closure of the cone of concentration matrices of G. The extreme rays of this cone, and their associated ranks, have applications in maximum likelihood estimation for the undirected Gaussian graphical model associated to G. Consequently, the extreme ranks of this cone have been well-studied. Yet, there are few graph classes for which all the possible extreme ranks are known. We show that the facet-normals of the cut polytope of G can serve to identify extreme rays of this nonpolyhedral cone. We see that for graphs without K5 minors each facet-normal of the cut polytope identifies an extreme ray in the cone, and we determine the rank of this extreme ray. When the graph is also series-parallel, we find that all possible extreme ranks arise in this fashion, thereby extending the collection of graph classes for which all the possible extreme ranks are known.

Στην παρούσα διπλωματική εργασία πραγματευόμαστε το θέμα της χρήσης των Bayesian Δικτύων -και γενικότερα των Πιθανοτικών Γραφικών Μοντέλων - στη Μηχανική Μάθηση. Στα πρώτα κεφάλαια της εργασίας αυτής παρουσιάζουμε συνοπτικά τη θεωρητική θεμελίωση αυτών των δομημένων πιθανοτικών μοντέλων, η οποία απαρτίζεται από τις βασικές φάσεις της αναπαράστασης, επαγωγής συμπερασμάτων, λήψης αποφάσεων και εκμάθησης από τα διαθέσιμα δεδομένα. Στα επόμενα κεφάλαια, εξετάζουμε ένα ευρύ φάσμα εφαρμογών των πιθανοτικών γραφικών μοντέλων και παρουσιάζουμε τα αποτελέσματα των εξομοιώσεων που υλοποιήσαμε. Συγκεκριμένα, αρχικά με χρήση γράφων ορίζονται τα Bayesian δίκτυα, Markov δίκτυα και Factor Graphs. Έπειτα, παρουσιάζονται οι αλγόριθμοι επαγωγής συμπερασμάτων που επιτρέπουν τον απευθείας υπολογισμό πιθανοτικών κατανομών από τους γράφους. Διευκολύνεται η λήψη αποφάσεων υπό αβεβαιότητα με τα δέντρα αποφάσεων και τα Influence διαγράμματα. Ακολούθως, μελετάται η εκμάθηση της δομής και των παραμέτρων των πιθανοτικών γραφικών μοντέλων σε παρουσία πλήρους ή μερικού συνόλου δεδομένων. Τέλος, παρουσιάζονται εκτενώς σενάρια τα οποία καταδεικνύουν την εκφραστική δύναμη, την ευελιξία και τη χρηστικότητα των Πιθανοτικών Γραφικών Μοντέλων σε εφαρμογές του πραγματικού κόσμου. / The main subject of this diploma thesis is how probabilistic graphical models can be used in a wide range of real-world scenarios. In the first chapters, we have presented in a concise way the theoretical foundations of graphical models, which consists of the deeply related phases of representation, inference, decision theory and learning from data. In the next chapters, we have worked on many applications, from Optical Character Recognition to Recoginizing Actions and we have presented the results from the simulations.

Thesis (MScEng (Electrical and Electronic Engineering))--University of Stellenbosch, 2010. / ENGLISH ABSTRACT: In this thesis we present GrMPy, a library of classes and functions implemented in Python, designed for implementing graphical models. GrMPy supports both undirected and directed models, exact and approximate probabilistic inference, and parameter estimation from complete and incomplete data. In this thesis we outline the necessary theory required to understand the tools implemented within GrMPy as well as provide pseudo-code algorithms that illustrate how GrMPy is implemented. / AFRIKAANSE OPSOMMING: In hierdie verhandeling bied ons GrMPy aan,'n biblioteek van klasse en funksies wat Python geim- plimenteer word en ontwerp is vir die implimentering van grafiese modelle. GrMPy ondersteun beide gerigte en ongerigte modelle, presies eenbenaderde moontlike gevolgtrekkings en parameterskat- tings van volledige en onvolledige inligting. In hierdie verhandeling beskryf ons die nodige teorie wat benodig word om die hulpmiddels wat binne GrMPy geimplimenteer word te verstaan sowel as die pseudo-kodealgoritmes wat illustreer hoe GrMPy geimplimenteer is.

This thesis investigates the use of static, adaptive, adaptable and mixed-initiative approaches to the personalisation of content and graphical user interfaces (GUIs). This empirical study consisted of three experimental phases. The first examined the use of static, adaptive, adaptable and mixed-initiative approaches to web content. More specifically, it measured the usability (efficiency, frequency of error occurrence, effectiveness and satisfaction) of an e-commerce website. The experiment was conducted with 60 subjects and was tested empirically by four independent groups (15 subjects each). The second experiment examined the use of adaptive, adaptable and mixed-initiative approaches to GUIs. More specifically, it measured the usability (efficiency, frequency of error occurrence, effectiveness and satisfaction) in GUI control structures (menus). In addition, it investigated empirically the effects of content size on five different personalised menu types. In order to carry out this comparative investigation, two independent experiments were conducted, on small menus (17 items) and large ones (29 items) respectively. The experiment was conducted with 60 subjects and was tested empirically by four independent groups (15 subjects each). The third experiment was conducted with 40 subjects and was tested empirically by four dependent groups (5 subjects each). The aim of the third experiment was to mitigate the drawbacks of the adaptive, adaptable and mixedinitiative approaches, to improve their performance and to increase their usability by using multimodal auditory solutions (speech, earcons and auditory icons). The results indicate that the size of content affects the usability of personalised approaches. In other words, as the size of content increases, so does the need of the adaptive and mixed-initiative approaches, whereas that of the adaptable approach decreases. A set of empirically derived guidelines were also produced to assist designers with the use of adaptive, adaptable and mixed-initiative approaches to web content and GUI control structure.

Recent advances in sensor technologies and the growing interest in context- aware applications, such as targeted advertising and location-based services, have led to a demand for understanding human behavior patterns from sensor data. People engage in routine behaviors. Automatic routine discovery goes beyond low-level activity recognition such as sitting or standing and analyzes human behaviors at a higher level (e.g., commuting to work). The goal of the research presented in this thesis is to automatically discover high-level semantic human routines from low-level sensor streams. One recent line of research is to mine human routines from sensor data using parametric topic models. The main shortcoming of parametric models is that they assume a fixed, pre-specified parameter regardless of the data. Choosing an appropriate parameter usually requires an inefficient trial-and-error model selection process. Furthermore, it is even more difficult to find optimal parameter values in advance for personalized applications. The research presented in this thesis offers a novel nonparametric framework for human routine discovery that can infer high-level routines without knowing the number of latent low-level activities beforehand. More specifically, the frame-work automatically finds the size of the low-level feature vocabulary from sensor feature vectors at the vocabulary extraction phase. At the routine discovery phase, the framework further automatically selects the appropriate number of latent low-level activities and discovers latent routines. Moreover, we propose a new generative graphical model to incorporate multimodal sensor streams for the human activity discovery task. The hypothesis and approaches presented in this thesis are evaluated on public datasets in two routine domains: two daily-activity datasets and a transportation mode dataset. Experimental results show that our nonparametric framework can automatically learn the appropriate model parameters from multimodal sensor data without any form of manual model selection procedure and can outperform traditional parametric approaches for human routine discovery tasks.

Accurate and efficient localization of facial features is a crucial first step in many face-related computer vision tasks. Some of these tasks include, but not limited to: identity recognition, expression recognition, and head-pose estimation. Most effort in the field has been exerted towards developing better ways of modeling prior appearance knowledge and image observations. Modeling prior shape knowledge, on the other hand, has not been explored as much. In this dissertation I primarily focus on the limitations of the existing methods in terms of modeling the prior shape knowledge. I first introduce a new pose-constrained shape model. I describe my shape model as being "highly flexible yet sufficiently strict". Existing pose-constrained shape models are either too strict, and have questionable generalization power, or they are too loose, and have questionable localization accuracies. My model tries to find a good middle-ground by learning which shape constraints are more "informative" and should be kept, and which ones are not-so-important and may be omitted. I build my pose-constrained facial feature localization approach on this new shape model using a probabilistic graphical model framework. Within this framework, observed and unobserved variables are defined as the local image observations, and the feature locations, respectively. Feature localization, or "probabilistic inference", is then achieved by nonparametric belief propagation. I show that this approach outperforms other popular pose-constrained methods through qualitative and quantitative experiments. Next, I expand my pose-constrained localization approach to unconstrained setting using a multi-model strategy. While doing so, once again I identify and address the two key limitations of existing multi-model methods: 1) semantically and manually defining the models or "guiding" their generation, and 2) not having efficient and effective model selection strategies. First, I introduce an approach based on unsupervised clustering where the models are automatically learned from training data. Then, I complement this approach with an efficient and effective model selection strategy, which is based on a multi-class naive Bayesian classifier. This way, my method can have many more models, each with a higher level of expressive power, and consequently, provides a more effective partitioning of the face image space. This approach is validated through extensive experiments and comparisons with state-of-the-art methods on state-of-the-art datasets. In the last part of this dissertation I discuss a particular application of the previously introduced techniques; facial feature localization in unconstrained videos. I improve the frame-by-frame localization results, by estimating the actual head-movement from a sequence of noisy head-pose estimates, and then using this information for detecting and fixing the localization failures. / text

This dissertation describes research in the application and evaluation of a Kohonen Self-Organizing Map (SOM) to the problem of classification of Electronic Brainstorming output. Electronic Brainstorming is one of the most productive tools in the Electronic Meeting System called GroupSystems. A major step in group problem solving involves the classification of Electronic Brainstorming output into a manageable list of concepts, topics, or issues that can be further evaluated by the group. This step is problematic due to the information overload and cognitive load of the large quantity of data. This research builds upon previous work in automating the classification process using a Hopfield Neural Network. Evaluation of the Kohonen output in comparison with the Hopfield and human expert output over the same set of data found that the Kohonen SOM performed as well as a human expert in the recollection of associated term pairs and outperformed the Hopfield Neural Network algorithm. Using information retrieval measures, recall of concepts using the Kohonen algorithm was equivalent to the human expert. However, precision was poor. The graphical representation of textual data produced by the Kohonen SOM suggests many opportunities for improving information management of textual electronic information. Increasing uses of electronic mail, computer-based bulletin board systems, and world-wide web textual data suggest an overwhelming amount of textual information to manage. This research suggests that the Kohonen SOM may be used to automatically create "a picture that can represent a thousand (or more) words."

Tikslas: ištirti žiniatinklių vartotojo sąsajos naudojimosi patogumą. Tyrimo objektas: žiniatinklių grafinės vartotojo sąsajos. Problema: šiandien internetinės svetainės yra labai populiarios, jas kuria visi. Dažniausiai kūrėjai neatsižvelgia į grafinės vartotojo sąsajos kūrimo reikalavimus, ir pateiktos internetinės svetainės būna perkrautos, netvarkingos. Todėl šiuo tyrimu siekiama atskleisti žiniatinklių vartotojo sąsajos problemas ir pateikti rekomendacijų internetinių svetainių kūrėjams. Tyrimo metodologija: žiniatinklių tyrimui buvo išskirti trys pagrindiniai kriterijai: atliktų žingsnių skaičius, atvertų puslapių skaičius, sugaištas laikas. O klaidų palyginimui buvo stebima judėjimo trajektorija. Naudotos priemonės: Selenium-ide-1.0.6 – fiksuoja visus atliekamus veiksmus, taip pat atkuria tą pačią veiksmų seką. Mozilla Firefox 3.0.15 – žiniatinklio naršyklė. Microsoft Office Excel 2003 – tyrime gautų duomenų suvedimui, lentelių ir grafikų sudarymui. Microsoft Office Word 2003 – ataskaitos paruošimui. Tyrimo apimtis: žiniatinklių vartotojo sąsajų tyrimui buvo parinktos 5 žiniatinklių grupės (kurios buvo panašios savo turiniu). Viso buvo tiriama 18 internetinių svetainių. Sugalvotos 5 užduotys. Tyrimo rezultatų apdorojimo ir pateikimo metodai: gauti tyrimo duomenys buvo susisteminti ir pateikiami stulpelinėse diagramose su detaliais aprašymais. Diagramos: užduotyje atliktų žingsnių skaičius, užduotyje atvertų puslapių skaičius, užduoties įvykdymo laikas, užduoties... [toliau žr. visą tekstą] / The goal of the final bachelor work – to research the convenience of the Web interface usage. The topicality of the subject, problems, goals and objectives are preceded. The interface usage, design technologies and requirements are analysed in the final work. The conception, classification and the system analysis are approved. The graphic usage interface, design, requirements, characteristic and technologies are enlarged. The research of web interface usage, environment, respondents, technologies, criterions, the results are approved in the work. Three main criterions were distinguished to fulfil the research: the number of performed steps, the number of opened pages, the delayed time. The criterions are necessary to compare webs . The trajectory of move is observed in order to accent the errors. Research results were systematised and presented in bar charts with detailed descriptions (comparison, error accent). The result of the research: not every Internet site is oriented towards the user. Oftentimes they are busy, non-qualitative, it is hard to find necessary information for users.

This thesis tackles a series of problems related to the evolution of completesoftware systems both in terms of the underlying Genetic Programmingsystem and the application of that system. A new representation is presented that addresses some of the issues withother Genetic Program representations while keeping their advantages. Thiscombines the easy reproduction of the linear representation with the inheritablecharacteristics of the tree representation by using fixed-length blocks ofgenes representing single program statements. This means that each block ofgenes will always map to the same statement in the parent and child unless itis mutated, irrespective of changes to the surrounding blocks. This methodis compared to the variable length gene blocks used by other representationswith a clear improvement in the similarity between parent and child. Traditionally, fitness functions have either been created as a selection ofsample inputs with known outputs or as hand-crafted evaluation functions. Anew method of creating fitness evaluation functions is introduced that takesthe formal specification of the desired function as its basis. This approachensures that the fitness function is complete and concise. The fitness functionscreated from formal specifications are compared to simple input/outputpairs and the results show that the functions created from formal specificationsperform significantly better. A set of list evaluation and manipulation functions was evolved as anapplication of the new Genetic Program components. These functions havethe common feature that they all need to be 100% correct to be useful. Traditional Genetic Programming problems have mainly been optimizationor approximation problems. The list results are good but do highlight theproblem of scalability in that more complex functions lead to a dramaticincrease in the required evolution time. Finally, the evolution of graphical user interfaces is addressed. The representationfor the user interfaces is based on the new representation forprograms. In this case each gene block represents a component of the userinterface. The fitness of the interface is determined by comparing it to a seriesof constraints, which specify the layout, style and functionality requirements. A selection of web-based and desktop-based user interfaces were evolved. With these new approaches to Genetic Programming, the evolution ofcomplete software systems is now a realistic goal.

The harmonisation of the European Trade Mark laws and the introduction of unconventional marks under this regime have encouraged interested parties to seek registration of chemical senses (scent and taste) as trade marks. This thesis studies the current state of affairs of these types of marks. It discusses in general, the panorama that these types of marks have when registrability is at issue. The purpose of this research is therefore to scrutinise the trade mark legal system, including a discussion of the origins and rationale underlying it, to try to understand the burdens presented when registering chemical sense marks. The starting point of this thesis is that the European Regulation and the Directive of the Trade Mark law open the door to the protection of chemical senses under the Trade Mark law regime. Yet, despite some early successful registration, their fate is still burdened with uncertainty and therefore the rationale for this study is to try to find whether chemical sense marks are truly marks and therefore protectable under the trade mark system. The approach chosen addresses the examination of all requirements for a sign to be protected under the trade mark system. The reason is that protection of chemical senses might be granted if such marks are recognised as signs, are graphically represented and are capable of distinguishing products of one undertaking from those of another undertaking. By examining the aforementioned requirements, the study reveals that while chemical senses marks might be seen as marks, they find that registration is not quite feasible. The thesis emphasises that graphic representation is only one of the many issues that chemical sense marks are confronted with. Issues such as distinctiveness, the need to keep free and functionality remain problematic. Moreover, the scope of protection afforded to chemical sense marks are yet untested. Case law will ascertain that the intent behind the trade mark regime to grant registration to chemical senses is unresolved. Still, the significant interest in chemical senses as trade marks appears to be not softening by this notion.