Algorithme minimax

L'algorithme minimax (aussi appelé algorithme MinMax) est un algorithme qui s'applique à la théorie des jeux pour les jeux à deux joueurs à somme nulle (et à information complète) consistant à minimiser la perte maximum (c'est-à-dire dans le pire des cas). Pour une vaste famille de jeux, le théorème du minimax de von Neumann assure l'existence d'un tel algorithme, même si dans la pratique il n'est souvent guère aisé de le trouver. Le jeu de hex est un exemple où l'existence d'un tel algorithme est établie et montre que le premier joueur peut toujours gagner, sans pour autant que cette stratégie soit connue. Il amène l'ordinateur à passer en revue toutes les possibilités pour un nombre limité de coups et à leur assigner une valeur qui prend en compte les bénéfices pour le joueur et pour son adversaire. Le meilleur choix est alors celui qui minimise les pertes du joueur tout en supposant que l'adversaire cherche au contraire à les maximiser (le jeu est à somme nulle). Il existe différ

Stratégies de compromis pour l'estimation des paramètres de régression et pour la classification floue

Nicolas Fournier

Model specification is an integral part of any statistical inference problem. Several model selection techniques have been developed in order to determine which model is the best one among a list of possible candidates. Another way to deal with this question is the so-called model averaging, and in particular the frequentist approach. An estimation of the parameters of interest is obtained by constructing a weighted average of the estimates of these quantities under each candidate model. We develop compromise frequentist strategies for the estimation of regression parameters, as well as for the probabilistic clustering problem. In the regression context, we construct compromise strategies based on the Pitman estimators associated with various underlying errors distributions. The weight given to each model is equal to its profile likelihood, which gives a measure of the goodness-of-fit. Asymptotic properties of both Pitman estimators and profile likelihood allow us to define a minimax strategy for choosing the distributions of the compromise, involving a notion of distance between distributions. Performances of such estimators are then compared to other usual and robust procedures. In the second part of the thesis, we develop compromise strategies in the probabilistic clustering context. Although this clustering method is based on mixtures of distributions, our compromise strategies are not applied directly to the estimates of the parameters, but on the posterior probabilities of membership. Two types of compromise are presented, and the performances of resulting classification rules are investigated.

EPFL2011

Truthful, Transparent and Fair Data Collection Mechanisms

Naman Goel

An important prerequisite for developing trustworthy artificial intelligence is high quality data. Crowdsourcing has emerged as a popular method of data collection in the past few years. However, there is always a concern about the quality of the data thus collected. This thesis addresses two major challenges in collecting high quality data from a crowd: 1) how to incentivize crowd workers to report accurate data; 2) how to ensure that the data collection mechanism is transparent and fair. We first propose two novel peer-consistency mechanisms for crowdsourcing: the Deep Bayesian Trust (DBT) mechanism and the Personalized Peer Truth Serum (PPTS). The DBT mechanism incentivizes workers to report accurate answers for objective questions with discrete ground truth answers. It is useful, for example, in collecting labels for supervised machine learning tasks. The mechanism ensures dominant uniform strategy incentive compatibility and fair rewards to the workers. The PPTS incentivizes workers to truthfully report their personal data (for example, body measurements). Since data is personal in nature, the tasks can not be shared between two workers. We show that when individuals report combinations of multiple personal data attributes, the correlation between them can be exploited to find peers and provide guarantees on the incentive compatibility of the mechanism. We next address the transparency issue of data collection. Smart contracts often rely on a trusted third party (oracle) to get correct information about real-world events. We show how peer-consistency mechanisms can be used to build decentralized, trustless and transparent data oracles on blockchain. We derive conditions under which a peer-consistency incentive mechanism can be used to acquire truthful information from an untrusted and self-interested crowd, even when the crowd has outside incentives to provide wrong information. We also show how to implement the peer-consistency mechanisms in Ethereum. We discuss various non-trivial issues that arise in implementing peer-consistency mechanisms in Ethereum, suggest several optimizations to reduce gas cost and provide empirical analysis. Finally, we address the problem of fair data collection from a crowd. Sharing economy platforms such as Airbnb and Uber face a major challenge in the form of peer-to-peer discrimination based on sensitive personal attributes such as race and gender. We show that how a peer-consistency incentive mechanism can be used to encourage users to go against common bias and provide a truthful rating about others, obtained through a more careful and deeper evaluation. In situations where an incentive mechanism canât be implemented, we show that a simple post-processing approach can also be used to correct bias in the reputation scores, while minimizing loss in the useful information provided by the scores. We also address the problem of fair and diverse data collection from a crowd under budget constraints. We propose a novel algorithm which maximizes the expected accuracy of the collected data, while ensuring that the errors satisfy desired notions of fairness w.r.t sensitive attributes.

EPFL2020

Truthful, Transparent and Fair Data Collection Mechanisms

Naman Goel

EPFL2020

Stratégies de compromis pour l'estimation des paramètres de régression et pour la classification floue

Truthful, Transparent and Fair Data Collection Mechanisms

A Minimax Approach for Multi-Objective Controller Design Using Multiple Models

Truthful, Transparent and Fair Data Collection Mechanisms

Stratégies de compromis pour l'estimation des paramètres de régression et pour la classification floue

A Minimax Approach for Multi-Objective Controller Design Using Multiple Models