Ranking queries are widely used in data exploration, data analysis and decision making scenarios. While most of the currently proposed ranking techniques focus on deterministic data, several emerging applications involve data that are imprecise or uncertain. Ranking uncertain data raises new challenges in query semantics and processing, making conventional methods inapplicable. Furthermore, the interplay between ranking and uncertainty models introduces new dimensions for ordering query results that do not exist in the traditional settings. This dissertation introduces new formulations and processing techniques for ranking queries on uncertain data. The formulations are based on marriage of traditional ranking semantics with possible worlds semantics under widely-adopted uncertainty models. In particular, we focus on studying the impact of tuple-level and attribute-level uncertainty on the semantics and processing techniques of ranking queries. Under the tuple-level uncertainty model, we introduce a processing framework leveraging the capabilities of relational database systems to recognize and handle data uncertainty in score-based ranking. The framework encapsulates a state space model, and efficient search algorithms that compute query answers by lazily materializing the necessary parts of the space. Under the attribute-level uncertainty model, we give a new probabilistic ranking model, based on partial orders, to encapsulate the space of possible rankings originating from uncertainty in attribute values. We present a set of efficient query evaluation algorithms, including sampling-based techniques based on the theory of Markov chains and Monte-Carlo method, to compute query answers. We build on our techniques for ranking under attribute-level uncertainty to support rank join queries on uncertain data. We show how to extend current rank join methods to handle uncertainty in scoring attributes. We provide a pipelined query operator implementation of uncertainty-aware rank join algorithm integrated with sampling techniques to compute query answers.

<p>Sequence modelling is used for analysing newly sequenced proteins, giving indication of the 3-D structure and functionality. Current approaches to the modelling of protein families are either based on discrete or probabilistic methods. Here we present an approach for combining these two approaches in a hybrid model, where discrete patterns are used to model conserved regions and probabilistic models are used for variable regions. When hidden Markov models are used to model the variable regions, the hybrid method gives increased classification accuracy, compared to pure discrete or probabilistic models.</p>

Scene perception is a fundamental aspect of vision. Humans are capable of analyzing behaviorally-relevant scene properties such as spatial layouts or scene categories very quickly, even from low resolution versions of scenes. Although humans perform these tasks effortlessly, they are very challenging for machines. Developing methods that well capture the properties of the representation used by the visual system will be useful for building computational models that are more consistent with perception. While it is common to use hand-engineered features that extract information from predefined dimensions, they require careful tuning of parameters and do not generalize well to other tasks or larger datasets. This thesis is driven by the hypothesis that the perceptual representations are adapted to the statistical properties of natural visual scenes. For developing statistical features for global-scale structures (low spatial frequency information that encompasses entire scenes), I propose to train hierarchical probabilistic models on whole scene images. I first investigate statistical clusters of scene images by training a mixture model under the assumption that each image can be decoded by sparse and independent coefficients. Each cluster discovered by the unsupervised classifier is consistent with the high-level semantic categories (such as indoor, outdoor-natural and outdoor-manmade) as well as perceptual layout properties (mean depth, openness and perspective). To address the limitation of mixture models in their assumptions of a discrete number of underlying clusters, I further investigate a continuous representation for the distributions of whole scenes. The model parameters optimized for natural visual scenes reveal a compact representation that encodes their global-scale structures. I develop a probabilistic similarity measure based on the model and demonstrate its consistency with the perceptual similarities. Lastly, to learn the representations that better encode the manifold structures in general high-dimensional image space, I develop the image normalization process to find a set of canonical images that anchors the probabilistic distributions around the real data manifolds. The canonical images are employed as the centers of the conditional multivariate Gaussian distributions. This approach allows to learn more detailed structures of the local manifolds resulting in improved representation of the high level properties of scene images.

A probabilistic framework is developed to assess the structural reliability of offshore wind turbines. Probabilistic models are developed to predict the deformation, shear force and bending moment demands on the support structure of wind turbines. The proposed probabilistic models are developed starting from a commonly accepted deterministic model and by adding correction terms and model errors to capture respectively, the inherent bias and the uncertainty in developed models. A Bayesian approach is then used to assess the model parameters incorporating the information from virtual experiment data. The database of virtual experiments is generated using detailed three-dimensional finite element analyses of a suite of typical offshore wind turbines. The finite element analyses properly account for the nonlinear soil-structure interaction. Separate probabilistic demand models are developed for three operational/load conditions including: (1) operating under day-to-day wind and wave loading; (2) operating throughout earthquake in presence of day-to-day loads; and (3) parked under extreme wind speeds and earthquake ground motions. The proposed approach gives special attention to the treatment of both aleatory and epistemic uncertainties in predicting the demands on the support structure of wind turbines. The developed demand models are then used to assess the reliability of the support structure of wind turbines based on the proposed damage states for typical wind turbines and their corresponding performance levels. A multi-hazard fragility surface of a given wind turbine support structure as well as the seismic and wind hazards at a specific site location are incorporated into a probabilistic framework to estimate the annual probability of failure of the support structure. Finally, a framework is proposed to investigate the performance of offshore wind turbines operating under day-to-day loads based on their availability for power production. To this end, probabilistic models are proposed to predict the mean and standard deviation of drift response of the tower. The results are used in a random vibration based framework to assess the fragility as the probability of exceeding certain drift thresholds given specific levels of wind speed.

This thesis introduces normal factor graphs under a new semantics, namely, the exterior function semantics. Initially, this work was motivated by two distinct lines of research. One line is ``holographic algorithms,'' a powerful approach introduced by Valiant for solving various counting problems in computer science; the other is ``normal graphs,'' an elegant framework proposed by Forney for representing codes defined on graphs. The nonrestrictive normality constraint enables the notion of holographic transformations for normal factor graphs. We establish a theorem, called the generalized Holant theorem, which relates a normal factor graph to its holographic transformation. We show that the generalized Holant theorem on one hand underlies the principle of holographic algorithms, and on the other reduces to a general duality theorem for normal factor graphs, a special case of which was first proved by Forney. As an application beyond Forney's duality, we show that the normal factor graphs duality facilitates the approximation of the partition function for the two-dimensional nearest-neighbor Potts model. In the course of our development, we formalize a new semantics for normal factor graphs, which highlights various linear algebraic properties that enables the use of normal factor graphs as a linear algebraic tool. Indeed, we demonstrate the ability of normal factor graphs to encode several concepts from linear algebra and present normal factor graphs as a generalization of ``trace diagrams.'' We illustrate, with examples, the workings of this framework and how several identities from linear algebra may be obtained using a simple graphical manipulation procedure called ``vertex merging/splitting.'' We also discuss translation association schemes with the aid of normal factor graphs, which we believe provides a simple approach to understanding the subject. Further, under the new semantics, normal factor graphs provide a probabilistic model that unifies several graphical models such as factor graphs, convolutional factor graphs, and cumulative distribution networks.

There are two main types of logistical models used for long-term performance prediction of autonomous power systems: time series and probabilistic. Time series models are more common and are more accurate for sizing storage systems because they are able to track the state of charge. However, the computational time is usually greater than for probabilistic models. It is common for time series models to perform 1-year simulations with a 1-hour time step. This is likely because of the limited availability of high resolution data and the increase in computation time with a shorter time step. Computation time is particularly important because these types of models are often used for component size optimization which requires many model runs. This thesis includes a sensitivity analysis examining the effect of the time step on these simulations. The results show that it can be significant, though it depends on the system configuration and site characteristics. Two probabilistic models are developed to estimate the temporal resolution error of a 1-hour simulation: a time series/probabilistic model and a fully probabilistic model. To demonstrate the application of and evaluate the performance of these models, two case studies are analyzed. One is for a typical residential system and one is for a system designed to provide on-site power at an aquaculture site. The results show that the time series/probabilistic model would be a useful tool if accurate distributions of the sub-hour data can be determined. Additionally, the method of cumulant arithmetic is demonstrated to be a useful technique for incorporating multiple non-Gaussian random variables into a probabilistic model, a feature other models such as Hybrid2 currently do not have. The results from the fully probabilistic model showed that some form of autocorrelation is required to account for seasonal and diurnal trends. / Graduate

Ranking queries are widely used in data exploration, data analysis and decision making scenarios. While most of the currently proposed ranking techniques focus on deterministic data, several emerging applications involve data that are imprecise or uncertain. Ranking uncertain data raises new challenges in query semantics and processing, making conventional methods inapplicable. Furthermore, the interplay between ranking and uncertainty models introduces new dimensions for ordering query results that do not exist in the traditional settings. This dissertation introduces new formulations and processing techniques for ranking queries on uncertain data. The formulations are based on marriage of traditional ranking semantics with possible worlds semantics under widely-adopted uncertainty models. In particular, we focus on studying the impact of tuple-level and attribute-level uncertainty on the semantics and processing techniques of ranking queries. Under the tuple-level uncertainty model, we introduce a processing framework leveraging the capabilities of relational database systems to recognize and handle data uncertainty in score-based ranking. The framework encapsulates a state space model, and efficient search algorithms that compute query answers by lazily materializing the necessary parts of the space. Under the attribute-level uncertainty model, we give a new probabilistic ranking model, based on partial orders, to encapsulate the space of possible rankings originating from uncertainty in attribute values. We present a set of efficient query evaluation algorithms, including sampling-based techniques based on the theory of Markov chains and Monte-Carlo method, to compute query answers. We build on our techniques for ranking under attribute-level uncertainty to support rank join queries on uncertain data. We show how to extend current rank join methods to handle uncertainty in scoring attributes. We provide a pipelined query operator implementation of uncertainty-aware rank join algorithm integrated with sampling techniques to compute query answers.

<p>The analysis of time series and sequences has been challenging in both statistics and machine learning community, because of their properties including high dimensionality, pattern dynamics, and irregular observations. In this thesis, novel methods are proposed to handle the difficulties mentioned above, thus enabling representation learning (dimension reduction and pattern extraction), and prediction making (classification and forecasting). This thesis consists of three main parts. </p><p>The first part analyzes multivariate time series, which is often non-stationary due to high levels of ambient noise and various interferences. We propose a nonlinear dimensionality reduction framework using diffusion maps on a learned statistical manifold, which gives rise to the construction of a low-dimensional representation of the high-dimensional non-stationary time series. We show that diffusion maps, with affinity kernels based on the Kullback-Leibler divergence between the local statistics of samples, allow for efficient approximation of pairwise geodesic distances. To construct the statistical manifold, we estimate time-evolving parametric distributions by designing a family of Bayesian generative models. The proposed framework can be applied to problems in which the time-evolving distributions (of temporally localized data), rather than the samples themselves, are driven by a low-dimensional underlying process. We provide efficient parameter estimation and dimensionality reduction methodology and apply it to two applications: music analysis and epileptic-seizure prediction.</p><p> </p><p>The second part focuses on a time series classification task, where we want to leverage the temporal dynamic information in the classifier design. In many time series classification problems including fraud detection, a low false alarm rate is required; meanwhile, we enhance the positive detection rate. Therefore, we directly optimize the partial area under the curve (PAUC), which maximizes the accuracy in low false alarm rate regions. Latent variables are introduced to incorporate the temporal information, while maintaining a max-margin based method solvable. An optimization routine is proposed with its properties analyzed; the algorithm is designed as scalable to web-scale data. Simulation results demonstrate the effectiveness of optimizing the performance in the low false alarm rate regions. </p><p> </p><p>The third part focuses on pattern extraction from correlated point process data, which consist of multiple correlated sequences observed at irregular times. The analysis of correlated point process data has wide applications, ranging from biomedical research to network analysis. We model such data as generated by a latent collection of continuous-time binary semi-Markov processes, corresponding to external events appearing and disappearing. A continuous-time modeling framework is more appropriate for multichannel point process data than a binning approach requiring time discretization, and we show connections between our model and recent ideas from the discrete-time literature. We describe an efficient MCMC algorithm for posterior inference, and apply our ideas to both synthetic data and a real-world biometrics application.</p> / Dissertation

[pt] Esta dissertação inicia com uma discussão sobre a importância da gestão de estoque para as empresas e dá um enfoque especial à gestão de estoque de sobressalentes para manutenção. Mostra-se que a gestão eficiente deste tipo de estoques pode ser a diferença entre ter ou não grandes prejuízos, uma vez que os seus custos são altos, mas sua falta pode gerar grandes perdas. Além da perspectiva econômica, os estoques de sobressalentes podem ter funções estratégicas importantes. Em seguida são apresentados desenvolvimentos recentes sobre a gestão de estoque de sobressalentes para então propor um modelo baseado no sistema de controle (r, q) no qual o nível ótimo de estoque é atingido dada uma restrição no nível de serviço. Por fim, o modelo é utilizado para estimar o nível ótimo de estoque de itens da Refinaria Landulpho Alves- Mataripe, RLAM. / [en] This dissertation begins with a discussion about the importance of inventory control to companies with a special approach for inventory control of spare parts. It shows that an efficient control of this kind of inventories can avoid large financial losses, due the high stock carrying and stock-out costs. Besides the economic perspective, the inventory of spare parts can have important strategic functions. Next, the text presents the recent development of spare parts´ inventory control. Then it is proposed a model based on the (r, q) control system, in which the optimal stock level is achieved by a service level restriction. Finally, the model is used to estimate optimal stock levels of some Landulpho Alves-Mataripe Refinery´s spare parts.

Dans cette thèse, nous abordons le problème de l’estimation de pose de visage dans le contexte des interactions homme-robot. Nous abordons la résolution de cette tâche à l’aide d’une approche en deux étapes. Tout d’abord en nous inspirant de [Deleforge 15], nous proposons une nouvelle façon d’estimer la pose d’un visage, en apprenant un lien entre deux espaces, l’espace des paramètres de pose et un espace de grande dimension représentant les observations perçues par une caméra. L’apprentissage de ce lien se fait à l’aide d’une approche probabiliste, utilisant un mélange de regressions affines. Par rapport aux méthodes d’estimation de pose de visage déjà existantes, nous incorporons de nouvelles informations à l’espace des paramètres de pose, ces additions sont nécessaires afin de pouvoir prendre en compte la diversité des observations, comme les differents visages et expressions mais aussi lesdécalages entre les positions des visages détectés et leurs positions réelles, cela permet d’avoir une méthode robuste aux conditions réelles. Les évaluations ont montrées que cette méthode permettait d’avoir de meilleurs résultats que les méthodes de regression standard et des résultats similaires aux méthodes de l’état de l’art qui pour certaines utilisent plus d’informations, comme la profondeur, pour estimer la pose. Dans un second temps, nous développons un modèle temporel qui utilise les capacités des traqueurs pour combiner l’information du présent avec celle du passé. Le but à travers cela est de produire une estimation de la pose plus lisse dans le temps, mais aussi de corriger les oscillations entre deux estimations consécutives indépendantes. Le modèle proposé intègre le précédent modèle de régression dans une structure de filtrage de Kalman. Cette extension fait partie de la famille des modèles dynamiques commutatifs et garde tous les avantages du mélange de regressionsaffines précédent. Globalement, le modèle temporel proposé permet d’obtenir des estimations de pose plus précises et plus lisses sur une vidéo. Le modèle dynamique commutatif donne de meilleurs résultats qu’un modèle de suivi utilsant un filtre de Kalman standard. Bien qu’appliqué à l’estimation de pose de visage le modèle presenté dans cette thèse est très général et peut être utilisé pour résoudre d’autres problèmes de régressions et de suivis. / In this thesis, we address the well-known problem of head-pose estimationin the context of human-robot interaction (HRI). We accomplish this taskin a two step approach. First, we focus on the estimation of the head pose from visual features. We design features that could represent the face under different orientations and various resolutions in the image. The resulting is a high-dimensional representation of a face from an RGB image. Inspired from [Deleforge 15] we propose to solve the head-pose estimation problem by building a link between the head-pose parameters and the high-dimensional features perceived by a camera. This link is learned using a high-to-low probabilistic regression built using probabilistic mixture of affine transformations. With respect to classic head-pose estimation methods we extend the head-pose parameters by adding some variables to take into account variety in the observations (e.g. misaligned face bounding-box), to obtain a robust method under realistic conditions. Evaluation of the methods shows that our approach achieve better results than classic regression methods and similar results thanstate of the art methods in head pose that use additional cues to estimate the head pose (e.g depth information). Secondly, we propose a temporal model by using tracker ability to combine information from both the present and the past. Our aim through this is to give a smoother estimation output, and to correct oscillations between two consecutives independent observations. The proposed approach embeds the previous regression into a temporal filtering framework. This extention is part of the family of switching dynamic models and keeps all the advantages of the mixture of affine regressions used. Overall the proposed tracker gives a more accurate and smoother estimation of the head pose on a video sequence. In addition, the proposed switching dynamic model gives better results than standard tracking models such as Kalman filter. While being applied to the head-pose estimation problem the methodology presented in this thesis is really general and can be used to solve various regression and tracking problems, e.g. we applied it to the tracking of a sound source in an image.