Nesta tese, exploramos tomada de decisão com preferências parcialmente ordenadas: dadas duas ações, o indivíduo pode preferir uma ação a outra, julgá-las equivalentes, ou julgá-las incomparáveis. Tais preferências são originárias da incerteza sobre determinados estados do modelo de decisão e são reveladas pela imprecisão nos valores de probabilidade. Investigamos seis critérios de escolha de estratégias em problemas de decisão seqüenciais, representados por árvores de decisão e diagramas de influência, com probabilidades imprecisas: T-maximin, T-maximax, T-maximix, Dominação por Intervalos, Maximalidade e E-admissibilidade. Apresentamos novos algoritmos que geram estratégias para todos estes critérios. As principais contribuições deste trabalho estão na implementação dos algoritmos e na análise, sob o ponto de vista computacional, dos diversos critérios considerados como racionais em situações de incerteza representada por conjuntos de probabilidades. / In this thesis we explore situations where preferences are partially ordered: given two acts, the agent may prefer one to another, or nd them to be equivalent, or nd them to be incomparable. Such preferences stem from the uncertainty associated to some states of the decisions model and are revealed by imprecision in probability values. We investigate six criteria for strategy selection in decision trees and inuence diagrams with imprecise probabilities: -maximin, -maximax, -maximix, Interval Dominance, Maximality and E-admissibility. We present new algorithms that generate strategies for all these criteria. The main contributions of this work are twofold: the implementation of these algorithms and the analysis, under the computational point of view, of the criteria considered ratio- nal in uncertain situations represented by set of probabilities.

Orientador: Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-22T15:27:35Z (GMT). No. of bitstreams: 1 Curi_RafaelLima_M.pdf: 1469554 bytes, checksum: 8367cf52c9256338ee2963b9a9cdf41d (MD5) Previous issue date: 2013 / Resumo: Neste trabalho estudamos Jogos de Roteamento. Esta subclasse de jogos e uma das mais estudadas na literatura e permite modelar de forma relativamente simples vários cenários realistas. Por exemplo, tráfego de veículos em rodovias, transporte de mercadorias, redes de telefonia, redes de computadores como a Internet, etc. Analisamos as principais variantes de jogos de roteamento, destacando suas diferenças. Comparamos jogos atômicos versus jogos não-atômicos, jogos com fluxo divisível versus jogos com fluxo indivisível, jogos com demanda uniforme versus jogos com demanda genérica e jogos com redes específicas versus jogos com redes genéricas. Focamos nosso estudo na existência, unicidade e quantificação da ineficiência de equilíbrios que emergem do comportamento independente e egoísta dos jogadores. Estudamos o equilíbrio de Wardrop para jogos não-atômicos e o equilíbrio de Nash para jogos atômicos. Na literatura, notamos que a existência e unicidade de um equilíbrio dependem basicamente de três fatores: pressupostos nas funções que definem os custos dos segmentos de uma rota, tipo dos jogadores (atômicos ou não-atômicos, com demandas iguais ou diferentes) e topologia da rede. Apresentamos também os principais resultados de ineficiência obtidos para as métricas Preço da Anarquia (PoA) e Limite de Bicritério. Nos resultados que vimos, observamos que jogos não-atômicos possuem um PoA menor que o de jogos atômicos, jogos com fluxo divisível possuem um PoA menor que o de jogos com fluxo indivisível e jogos com demanda uniforme um PoA menor que o de jogos com demanda genérica / Abstract: In this work, we study Routing Games. This subclass of games is one of the most studied in the literature and allows us to model several realistic scenarios, in a relatively simple way. For instance, road traffic, freight transportation, telephone networks, computer networks like the Internet, etc. We analyze the main variants of routing games, emphasizing their differences. We compare atomic games versus nonatomic games, unsplittable flow games versus splittable flow games, unweighted games versus weighted games and specific network games versus generic network games. We focus our study on the existence, uniqueness and quantification of the inefficiency of equilibria that emerge from the independent and selfish behavior of the players. We study the Wardrop equilibrium for nonatomic games and the Nash equilibrium for atomic games. In the literature, we note that the existence and uniqueness of an equilibrium depends basically on three factors: assumptions on the functions that define the costs of the segments of a route, type of the players (atomic or nonatomic, with equal or different demands), and network topology. We present the main results of inefficiency obtained for the metrics Price of Anarchy (PoA) and Bicriteria Limit. In the results we have considered, we noticed that nonatomic games have lower PoA than the atomic ones, splittable flow games have lower PoA than the unsplittable flow ones, and unweighted games have lower PoA than the weighted ones / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientadores: Christophe Frédéric Gallesco, Serguei Popov / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-22T17:31:03Z (GMT). No. of bitstreams: 1 VasquezMercedes_ClaudiaEdith_M.pdf: 743991 bytes, checksum: 587d04d1b7b45c75dd5eeea766258b02 (MD5) Previous issue date: 2013 / Resumo: O resumo poderá ser visualizado no texto completo da tese digital / Abstract: The abstract is available with the full electronic document / Mestrado / Estatistica / Mestra em Estatística

Nous étudions dans cette thèse l'influence d'un système d'authentification utilisant des codes graphiques 2D modifiés lors de l'impression par un procédé physique non-clônable. Un tel procédé part du principe qu'à très haute résolution le système d'impression acquisition peut être modélisé comme un processus stochastique, de part le caractère aléatoire de la disposition des fibres de papiers, de mélange des particules d'encre, de l'adressabilité de l'imprimante ou encore du bruit d'acquisition. Nous considérons un scénario où l'adversaire pourra estimer le code original et essaiera de le reproduire en utilisant son propre système d'impression. La première solution que nous proposons pour arriver à l'authentification est d'utiliser un test d'hypothèse à partir des modèles à priori connus et sans mémoire des canaux d'impression-acquisition de l'imprimeur légitime et du contrefacteur. Dans ce contexte nous proposons une approximation fiable des probabilités d'erreur via l'utilisation de bornes exponentiels et du principe des grandes déviations. Dans un second temps, nous analysons un scénario plus réaliste qui prends en compte une estimation a priori du canal du contrefacteur et nous mesurons l'impact de cette étape sur les performances du système d'authentification. Nous montrons qu'il est possible de calculer la distribution des probabilité de non-détection et d'en extraire par exemple ses performances moyennes. La dernière partie de cette thèse propose d'optimiser, au travers d'un jeu minimax, le canal de l'imprimeur. / We study in this thesis the impact of an authentication system based on 2D graphical codes that are corrupted by a physically unclonable noise such as the one emitted by a printing process. The core of such a system is that a printing process at very high resolution can be seen as a stochastic process and hence produces noise, this is due to the nature of different elements such as the randomness of paper fibers, the physical properties of the ink drop, the dot addressability of the printer, etc. We consider a scenario where the opponent may estimate the original graphical code and tries to reproduce the forged one using his printing process in order to fool the receiver. Our first solution to perform authentication is to use hypothesis testing on the observed memoryless sequences of a printed graphical code considering the assumption that we are able to perfectly model the printing process. The proposed approach arises from error exponent using exponential bounds as a direct application of the large deviation principle. Moreover, when looking for a more practical scenario, we take into account the estimation of the printing process used to generate the graphical code of the opponent, and we see how it impacts the performance of the authentication system. We show that it is both possible to compute the distribution of the probability of non-detection and to compute the average performance of the authentication system when the opponent channel has to be estimated. The last part of this thesis addresses the optimization problem of the printing channel.

Em problemas de tomada de decisão sequencial modelados como Processos de Decisão Markovianos (MDP) pode não ser possível obter uma medida exata para as probabilidades de transição de estados. Visando resolver esta situação os Processos de Decisão Markovianos com Probabilidades Imprecisas (Markov Decision Processes with Imprecise Transition Probabilities, MDP-IPs) foram introduzidos. Porém, enquanto estes MDP-IPs se mostram como um arcabouço robusto para aplicações de planejamento no mundo real, suas soluções consomem muito tempo na prática. Em trabalhos anteriores, buscando melhorar estas soluções foram propostos algoritmos de programação dinâmica síncrona eficientes para resolver MDP-IPs com uma representação fatorada para as funções de transição probabilística e recompensa, chamados de MDP-IP fatorados. Entretanto quando o estado inicial de um problema do Caminho mais Curto Estocástico (Stochastic Shortest Path MDP, SSP MDP) é dado, estas soluções não utilizam esta informação. Neste trabalho será introduzido o problema do Caminho mais Curto Estocástico com Probabilidades Imprecisas (Stochastic Shortest Path MDP-IP, SSP MDP-IP) tanto em sua forma enumerativa, quanto na fatorada. Um algoritmo de programação dinâmica assíncrona para SSP MDP-IP enumerativos com probabilidades dadas por intervalos foi proposto por Buffet e Aberdeen (2005). Entretanto, em geral um problema é dado de forma fatorada, i.e., em termos de variáveis de estado e nesse caso, mesmo se for assumida a imprecisão dada por intervalos sobre as variáveis, ele não poderá ser mais aplicado, pois as probabilidades de transição conjuntas serão multilineares. Assim, será mostrado que os SSP MDP-IPs fatorados são mais expressivos que os enumerativos e que a mudança do SSP MDP-IP enumerativo para o caso geral de um SSP MDP-IPs fatorado leva a uma mudança de resolução da função objetivo do Bellman backup de uma função linear para uma não-linear. Também serão propostos algoritmos enumerativos, chamados de RTDP-IP (Real-time Dynamic Programming with Imprecise Transition Probabilities), LRTDP-IP (Labeled Real-time Dynamic Programming with Imprecise Transition Probabilities), SSiPP-IP (Short-Sighted Probabilistic Planner with Imprecise Transition Probabilities) e LSSiPP-IP (Labeled Short-Sighted Probabilistic Planner with Imprecise Transition Probabilities) e fatorados chamados factRTDP-IP (factored RTDP-IP) e factLRTDP-IP (factored LRTDP-IP). Eles serão avaliados em relação aos algoritmos de programação dinâmica síncrona em termos de tempo de convergência da solução e de escalabilidade. / In sequential decision making problems modelled as Markov Decision Processes (MDP) we may not have the state transition probabilities. To solve this issue, the framework based in Markov Decision Processes with Imprecise Transition Probabilities (MDP-IPs) is introduced. Therefore, while MDP-IPs is a robust framework to use in real world planning problems, its solutions are time-consuming in practice. In previous works, efficient algorithms based in synchronous dynamic programming to solve MDP-IPs with factored representations of the probabilistic transition function and reward function, called factored MDP-IPs. However, given a initial state of a system, modeled as a Stochastic Shortest Path MDP (SSP MDP), solutions does not use this information. In this work we introduce the Stochastic Shortest Path MDP-IPs (SSP MDP-IPs) in enumerative form and in factored form. An efficient asynchronous dynamic programming solution for SSP MDP-IPs with enumerated states has been proposed by Buffet e Aberdeen (2005) before which is restricted to interval-based imprecision. Nevertheless, in general the problem is given in a factored form, i.e., in terms of state variables and in this case even if we assume interval-based imprecision over the variables, the previous solution is no longer applicable since we have multilinear parameterized joint transition probabilities. In this work we show that the innocuous change from the enumerated SSP MDP-IP cases to the general case of factored SSP MDP-IPs leads to a switch from a linear to nonlinear objectives in the Bellman backup. Also we propose assynchronous dynamic programming enumerative algorithms, called RTDP-IP (Real-time Dynamic Programming with Imprecise Transition Probabilities), LRTDP-IP (Labeled Real-time Dynamic Programming with Imprecise Transition Probabilities), SSiPP-IP (Short-Sighted Probabilistic Planner with Imprecise Transition Probabilities) and LSSiPP-IP (Labeled Short-Sighted Probabilistic Planner with Imprecise Transition Probabilities), and factored algorithms called factRTDP-IP (factored RTDP-IP) and factLRTDP-IP (factored LRTDP-IP). There algorithms will be evaluated with the synchronous dynamic programming algorithms previously proposed in terms of convergence time and scalability.

This project describes Automine, a program intended to aid in the solving of the Minesweeper computer game. Automine is based on the Linux xwindow C program with xwindow graphic library. The program uses heuristics and probability statistics to help in determining safe squares and squares concealing mines with the goal of allowing a player to achieve minimal time performance. The source code for Automine and for a game simulation is provided in the appendices.

La modélisation cardiaque personnalisée consiste à créer des simulations 3D virtuelles de cas cliniques réels pour aider les cliniciens à prédire le comportement du cœur ou à mieux comprendre certaines pathologies. Dans cette thèse nous illustrons d'abord la nécessité d'une approche robuste d'estimation des paramètres, dans un cas ou l'incertitude dans l'orientation des fibres myocardiques entraîne une incertitude dans les paramètres estimés qui est très large par rapport à leur variabilité physiologique. Nous présentons ensuite une approche originale multi-échelle 0D/3D pour réduire le temps de calcul, basée sur un couplage multi-échelle entre les simulations du modèle 3D et d'une version "0D" réduite de ce modèle. Ensuite, nous dérivons un algorithme rapide de personnalisation multi-échelle pour le modèle 3D. Dans un deuxième temps, nous construisons plus de 140 simulations 3D personnalisées, dans le cadre de deux études impliquant l'analyse longitudinale de la fonction cardiaque : d'une part, l'analyse de l'évolution de cardiomyopathies à long terme, d'autre part la modélisation des changements cardiovasculaires pendant la digestion. Enfin, nous présentons un algorithme pour sélectionner automatiquement des directions observables dans l'espace des paramètres à partir d'un ensemble de mesures, et calculer des probabilités "a priori" cohérentes dans ces directions à partir des valeurs de paramètres dans la population. Cela permet en particulier de contraindre l'estimation de paramètres dans les cas où des mesures sont manquantes. Au final nous présentons des estimations cohérentes de paramètres dans une base de données de 811 cas avec le modèle 0D et 137 cas du modèle 3D. / Personalised cardiac modeling consists in creating virtual 3D simulations of real clinical cases to help clinicians predict the behaviour of the heart, or better understand some pathologies from the estimated values of biophysical parameters. In this work we first motivate the need for a consistent parameter estimation framework, from a case study were uncertainty in myocardial fibre orientation leads to an uncertainty in estimated parameters which is extremely large compared to their physiological variability. To build a consistent approach to parameter estimation, we then tackle the computational complexity of 3D models. We introduce an original multiscale 0D/3D approach for cardiac models, based on a multiscale coupling to approximate outputs of a 3D model with a reduced "0D" version of the same model. Then we derive from this coupling an efficient multifidelity optimisation algorithm for the 3D model. In a second step, we build more than 140 personalised 3D simulations, in the context of two studies involving the longitudinal analysis of the cardiac function: on one hand the analysis of long-term evolution of cardiomyopathies under therapy, on the other hand the modeling of short-term cardiovascular changes during digestion. Finally we present an algorithm to automatically detect and select observable directions in the parameter space from a set of measurements, and compute consistent population-based priors probabilities in these directions, which can be used to constrain parameter estimation for cases where measurements are missing. This enables consistent parameter estimations in a large databases of 811 cases with the 0D model, and 137 cases of the 3D model.

L'objectif de cette thèse est de développer des méthodes statistiques basées sur la théorie des valeurs extrêmes pour estimer des probabilités d'évènements rares et des quantiles extrêmes conditionnelles. Nous considérons une suite de variables aléatoires indépendantes X_{t_1}$, $X_{t_2}$,...$,$X_{t_n}$ associées aux temps $0≤t_{1}< … <t_{n}≤T_{\max}$ où $X_{t_i}$ a la fonction de répartition $F_{t_i}$ et $F_t$ est la loi conditionnelle de $X$ sachant $T=t \in [0,T_{\max}]$. Pour chaque $t \in [0,T_{\max}]$, nous proposons un estimateur non paramétrique de quantiles extrêmes de $F_t$. L'idée de notre approche consiste à ajuster pour chaque $t \in [0,T_{\max}]$ la queue de la distribution $F_{t}$, par une distribution de Pareto de paramètre $\theta_{t,\tau}$ à partir d'un seuil $\tau.$ Le paramètre $\theta_{t,\tau}$ est estimé en utilisant un estimateur non paramétrique à noyau de taille de fenêtre $h$ basé sur les observations plus grandes que $\tau$. Sous certaines hypothèses de régularité, nous montrons que l'estimateur adaptatif proposé de $\theta_{t,\tau} $ est consistant et nous donnons sa vitesse de convergence. Nous proposons une procédure de tests séquentiels pour déterminer le seuil $\tau$ et nous obtenons le paramètre $h$ suivant deux méthodes : la validation croisée et une approche adaptative. Nous proposons également une méthode pour choisir simultanément le seuil $\tau$ et la taille de la fenêtre $h$. Finalement, les procédures proposées sont étudiées sur des données simulées et sur des données réelles dans le but d'aider à la surveillance de systèmes aquatiques. / The objective of this PhD thesis is to develop statistical methods based on the theory of extreme values to estimate the probabilities of rare events and conditional extreme quantiles. We consider independent random variables $X_{t_1},…,X_{t_n}$ associated to a sequence of times $0 ≤t_1 <… < t_n ≤ T_{\max}$ where $X_{t_i}$ has distribution function $F_{t_i}$ and $F_t$ is the conditional distribution of $X$ given $T = t \in [0,T_{\max}]$. For each $ t \in [0, T {\max}]$, we propose a nonparametric adaptive estimator for extreme quantiles of $F_t$. The idea of our approach is to adjust the tail of the distribution function $F_t$ with a Pareto distribution of parameter $\theta {t,\tau}$ starting from a threshold $\tau$. The parameter $\theta {t,\tau}$ is estimated using a nonparametric kernel estimator of bandwidth $h$ based on the observations larger than $\tau$. We propose a sequence testing based procedure for the choice of the threshold $\tau$ and we determine the bandwidth $h$ by two methods: cross validation and an adaptive procedure. Under some regularity assumptions, we prove that the adaptive estimator of $\theta {t, \tau}$ is consistent and we determine its rate of convergence. We also propose a method to choose simultaneously the threshold $\tau$ and the bandwidth $h$. Finally, we study the proposed procedures by simulation and on real data set to contribute to the survey of aquatic systems.

In this thesis, annuity-due and annuity-immediate discrete time risk models are introduced and ruin probabilities in these two models under dependent forces of interest are discussed. Recursive and integral equations for these ruin probabilities are given. Inequalities for the ruin probability estimation are derived by an inductive approach. Finally, an example is given to illustrate the application of these results.

Stacking, also known as stacked generalization, is a method of ensemble learning where multiple base models are trained on the same dataset, and their predictions are used as input for one or more metamodels in an extra layer. This technique can lead to improved performance compared to single layer ensembles, but often requires a time-consuming trial-and-error process. Therefore, the previously developed Visual Analytics system, StackGenVis, was designed to help users select the set of the most effective and diverse models and measure their predictive performance. However, StackGenVis was developed with only one metamodel: Logistic Regression. The focus of this Bachelor's thesis is to examine how alternative metamodels affect the performance of stacked ensembles through the use of a visualization tool called MetaStackVis. Our interactive tool facilitates visual examination of individual metamodels and metamodels' pairs based on their predictive probabilities (or confidence), various supported validation metrics, and their accuracy in predicting specific problematic data instances. The efficiency and effectiveness of MetaStackVis are demonstrated with an example based on a real healthcare dataset. The tool has also been evaluated through semi-structured interview sessions with Machine Learning and Visual Analytics experts. In addition to this thesis, we have written a short research paper explaining the design and implementation of MetaStackVis. However, this thesis  provides further insights into the topic explored in the paper by offering additional findings and in-depth analysis. Thus, it can be considered a supplementary source of information for readers who are interested in diving deeper into the subject.