In recent years, the crucial importance of metrics in machine learningalgorithms has led to an increasing interest in optimizing distanceand similarity functions using knowledge from training data to make them suitable for the problem at hand.This area of research is known as metric learning. Existing methods typically aim at optimizing the parameters of a given metric with respect to some local constraints over the training sample. The learned metrics are generally used in nearest-neighbor and clustering algorithms.When data consist of feature vectors, a large body of work has focused on learning a Mahalanobis distance, which is parameterized by a positive semi-definite matrix. Recent methods offer good scalability to large datasets.Less work has been devoted to metric learning from structured objects (such as strings or trees), because it often involves complex procedures. Most of the work has focused on optimizing a notion of edit distance, which measures (in terms of number of operations) the cost of turning an object into another.We identify two important limitations of current supervised metric learning approaches. First, they allow to improve the performance of local algorithms such as k-nearest neighbors, but metric learning for global algorithms (such as linear classifiers) has not really been studied so far. Second, and perhaps more importantly, the question of the generalization ability of metric learning methods has been largely ignored.In this thesis, we propose theoretical and algorithmic contributions that address these limitations. Our first contribution is the derivation of a new kernel function built from learned edit probabilities. Unlike other string kernels, it is guaranteed to be valid and parameter-free. Our second contribution is a novel framework for learning string and tree edit similarities inspired by the recent theory of (epsilon,gamma,tau)-good similarity functions and formulated as a convex optimization problem. Using uniform stability arguments, we establish theoretical guarantees for the learned similarity that give a bound on the generalization error of a linear classifier built from that similarity. In our third contribution, we extend the same ideas to metric learning from feature vectors by proposing a bilinear similarity learning method that efficiently optimizes the (epsilon,gamma,tau)-goodness. The similarity is learned based on global constraints that are more appropriate to linear classification. Generalization guarantees are derived for our approach, highlighting that our method minimizes a tighter bound on the generalization error of the classifier. Our last contribution is a framework for establishing generalization bounds for a large class of existing metric learning algorithms. It is based on a simple adaptation of the notion of algorithmic robustness and allows the derivation of bounds for various loss functions and regularizers.

Cet article étudie la sensibilité des estimations de certaines variables explicatives de la croissance économique dans des régressions en coupe transversale sur un ensemble de pays. Il applique un modèle modifié de l’analyse de sensibilité de Leamer (1983, 1985). Mes résultats confirment la conclusion de Levine and Renelt (1992), toutefois, je montre que plus de variables sont solidement corrélées à la croissance économique. Entre 1990-2010, je trouve que huit sur vingt cinq variables ont des coefficients significatifs et sont solidement corrélées à la croissance de long terme, notamment, les parts de l’investissement et des dépenses étatiques dans le PIB, la primauté du droit et une variable dichotomique pour les pays subsahariens. Je trouve aussi une preuve empirique solide de l'hypothèse de la convergence conditionnelle, ce qui est cohérent avec le modèle de croissance néoclassique. / This paper examines the robustness of explanatory variables in cross-country growth regressions. It employs a variant of Leamer’s (1983, 1985) extreme-bounds analysis. My results confirm Levine and Renelt’s (1992) conclusion, but identify more variables to be robustly correlated with economic growth. Of 25 explanatory variables tested, I find 8 to be significantly and robustly correlated with long-term growth over the 1990-2010 period. The strongest evidence is for the investment ratio, government consumption share in GDP, the rule of law, and the Sub-Saharan dummy. I also find strong empirical evidence for conditional convergence, which is consistent with the neoclassical growth model.

Diss. Stockholm : Handelshögskolan, 2009

Le but principal de ce manuscrit est celui de présenter une nouvelle méthode d'interpolation entre des probabilités inspirée du problème de Schrödinger, problème de minimisation entropique ayant des liens très forts avec le transport optimal. À l'aide de solutions au problème de Schrödinger, nous obtenons un schéma d'approximation robuste jusqu'au deuxième ordre et différent de Brenier-McCann qui permet d'établir la formule de dérivation du deuxième ordre le long des géodésiques Wasserstein dans le cadre de espaces RCD* de dimension finie. Cette formule était inconnue même dans le cadre des espaces d'Alexandrov et nous en donnerons quelques applications. La démonstration utilise un ensemble remarquable de nouvelles propriétés pour les solutions au problème de Schrödinger dynamique :- une borne uniforme des densités le long des interpolations entropiques ;- la lipschitzianité uniforme des potentiels de Schrödinger ;- un contrôle L2 uniforme des accélérations. Ces outils sont indispensables pour explorer les informations géométriques encodées par les interpolations entropiques. Les techniques utilisées peuvent aussi être employées pour montrer que la solution visqueuse de l'équation d'Hamilton-Jacobi peut être récupérée à travers une méthode de « vanishing viscosity », comme dans le cas lisse.Dans tout le manuscrit, plusieurs remarques sur l'interprétation physique du problème de Schrödinger seront mises en lumière. Cela pourra aider le lecteur à mieux comprendre les motivations probabilistes et physiques du problème, ainsi qu'à les connecter avec la nature analytique et géométrique de la dissertation. / Main aim of this manuscript is to present a new interpolation technique for probability measures, which is strongly inspired by the Schrödinger problem, an entropy minimization problem deeply related to optimal transport. By means of the solutions to the Schrödinger problem, we build an efficient approximation scheme, robust up to the second order and different from Brenier-McCann's classical one. Such scheme allows us to prove the second order differentiation formula along geodesics in finite-dimensional RCD* spaces. This formula is new even in the context of Alexandrov spaces and we provide some applications.The proof relies on new, even in the smooth setting, estimates concerning entropic interpolations which we believe are interesting on their own. In particular we obtain:- equiboundedness of the densities along the entropic interpolations,- equi-Lipschitz continuity of the Schrödinger potentials,- a uniform weighted L2 control of the Hessian of such potentials. These tools are very useful in the investigation of the geometric information encoded in entropic interpolations. The techniques used in this work can be also used to show that the viscous solution of the Hamilton-Jacobi equation can be obtained via a vanishing viscosity method, in accordance with the smooth case. Throughout the whole manuscript, several remarks on the physical interpretation of the Schrödinger problem are pointed out. Hopefully, this will allow the reader to better understand the physical and probabilistic motivations of the problem as well as to connect them with the analytical and geometric nature of the dissertation.

Le cadre général de cette thèse est l'étude des polynômes comme objets de modèles de calcul. Cette approche permet de définir de manière précise la complexité d'évaluation d'un polynôme, puis de classifier des familles de polynômes en fonction de leur difficulté dans ce modèle. Dans cette thèse, nous nous intéressons en particulier au modèle AffPow des sommes de puissance de forme linéaire, i.e. les polynômes qui s'écrivent $f = \sum_{i = 1}^s \alpha_i \ell_i^{e_i}$, avec $\deg \ell_i = 1$. Ce modèle semble assez naturel car il étend à la fois le modèle de Waring $f = \sum \alpha_i \ell_i^d$ et le modèle du décalage creux $f = \sum \alpha_i \ell^{e_i}$, mais peu de résultats sont connus pour cette généralisation.Nous avons pu prouver des résultats structurels pour la version univarié de ce modèle, qui nous ont ensuite permis d'obtenir des bornes inférieures et des algorithmes de reconstruction, qui répondent au problème suivant : étant donné $f = \sum \alpha_i (x-a_i)^{e_i}$ par la liste de ses coefficients, retrouver les $\alpha_i, a_i, e_i$ qui apparaissent dans la décomposition optimale de $f$.Nous avons aussi étudié plus en détails la version multivarié du modèle, qui avait été laissé ouverte par nos précédents algorithmes de reconstruction, et avons obtenu plusieurs résultats lorsque le nombre de termes dans une expression optimale est relativement petit devant le nombre de variables ou devant le degré du polynôme. / The general framework of this thesis is the study of polynomials as objects of models of computation. This approach allows to define precisely the evaluation complexity of a polynomial, and then to classify families of polynomials depending on their complexity. In this thesis, we focus on the study of the model of sums of affine powers, that is polynomials that can be written as $f = \sum_{i = 1}^s \alpha_i \ell_i^{e_i}$, with $\deg \ell_i = 1$.This model is quite natural, as it extends both the Waring model $f = \sum \alpha_i \ell_i^d$ , and the sparsest shift model $f = \sum \alpha_i \ell^{e_i}$, but it is still not well known.In this work, we obtained structural results for the univariate variant of this model, which allow us to obtain lower bounds and reconstruction algorithms, that solve the following problem : given $f = \sum \alpha_i (x-a_i)^{e_i}$ as a list of its coefficient, find the values of the $\alpha_i$’s, $e_i$’s and $a_i$’s in the optimal decomposition of $f$.We also studied the multivariate case and obtained several reconstruction algorithms that work whenever the number of terms in the optimal expression is small in terms of the number of variable or the degree of the polynomial.

A Constituição Federal de 1988 inseriu no ordenamento jurídico uma série de direitos e garantias fundamentais. Dentre eles, pode-se citar a divisão de poderes, a qual distribuiu no texto constitucional o papel de cada ente estatal, sobretudo, para o presente estudo, a função relativa ao Judiciário. Nesse esteio, pode-se afirmar que tanto as normas promulgadas no período pós 1988, como as que foram recebidas pelo novo ordenamento, passaram a ser analisadas sob o espectro do prisma principiológico. As normas procedimentais e processuais coordenam os trilhos da aplicação do Direito ao caso concreto e a formação do Direito para o caso abstrato. No entanto, há que se mitigar toda aplicabilidade ordinária pelo tempero dos princípios. Essa pesquisa terá como guia a colisão entre os princípios processuais da efetividade e da instrumentalidade em face do devido processo legal. Tem-se por premissa que o percurso do devido processo deve servir como ferramenta para a busca pela decisão final de mérito e consequente pacificação social. Caso contrário, em nada serviria todo o aparato do judiciário disponibilizado para a população. Desse modo, o presente estudo propõe uma análise sobre a atuação do Estado-Juiz no que tange ao ativismo processual. Diante do objetivo maior, qual seja a necessidade de efetivação dos direitos fundamentais e sociais, o fenômeno do ativismo judicial às vezes esquecido, às vezes exacerbado, se mostra como ferramenta necessária no contexto destacado. / The Federal Constitutional of 1988 introduces at the legal system a series of fundamental rights and guarantees. Among them, its significant the division of powers, which distributed in the Constitution the role of each state entity, above all, for this study, the judiciary function. Thus, it can be said that both the rules promulgated in the period after 1988 as those received by the new system, have been analyzed through the principles spectrum prism. The procedural rules coordinate the application of law to the cases and the creation of law for abstract case. However, it is necessary to mitigate any regular applicability with the principles orientation. This research tries are the collision between the procedural principles of effectiveness and instrumentality in the face of due process of law. As premised the route of due process should serve as a tool to the final decision and consequent social peace. Otherwise, it would be unnecessary the entire legal apparatus available to the public. Lastly, this study proposes an analysis about the performance of the Judge-State regarding the judicial activism. Looking to a larger goal, the need for enforcement of fundamental and social rights, the judicial activism phenomenon sometimes forgotten, sometimes exacerbated, shown itself as a necessary tool in the context highlighted.

Made available in DSpace on 2014-07-29T16:02:20Z (GMT). No. of bitstreams: 1 Rosane Gomes Pereira.pdf: 525845 bytes, checksum: 76abe0b472d0e4b44a4d3197912958d3 (MD5) Previous issue date: 2012-03-09 / In this work, we study eigenvalues of polyharmonic operators on compact Riemannian manifolds with boundary (possibly empty). Here, we bring in a universal inequality for the eigenvalues of the polyharmonic operator on compact domains in an Euclidean space Rn. This inequality controls the kth eigenvalue by the lower eigenvalues, independently of the particular geometry of the domain. Besides, a inequality we present covers the important Yang inequality on eigenvalues of the Dirichlet Laplacian. Finally, we introduce universal inequalities for eigenvalues of polyharmonic operator on compact domains in a unit n-sphere Sn. NOTE: Programs do not copy or copy errors with certain symbols, formulas, formatting, etc ..., n of Rn and Sn are overwritten. View all content by clicking pdf - dissertation at the bottom of the screen. / Neste trabalho, estudamos autovalores do operador poli-harmônico em variedades Riemannianas compactas com fronteira ( possivelmente vazia ). Aqui, apresentamos uma desigualdade universal para os autovalores do operador poliharmônico em domínios compactos no Espaço Euclidiano Rn. Esta desigualdade controla o k-ésimo autovalor pelos autovalores menores, independentemente da geometria particular do domínio. Além disso, a desigualdade que apresentamos cobre a importante desigualdade de Yang em autovalores do Laplaciano de Dirichlet. Finalmente, apresentamos desigualdades universais para autovalores do operador poli-harmônico em domínios compactos na esfera unitária n- dimensional Sn. OBS: Programas não copiam ou copiam com erros certos símbolos, fórmulas, formatações etc..., o n de Rn e Sn está sobrescrito. Visualize todo conteúdo clicando pdf - dissertação na parte de baixo da tela.

Développer un programme capable de jouer à n’importe quel jeu de stratégie, souvent désigné par le General Game Playing (GGP) constitue un des Graal de l’intelligence artificielle. Les compétitions GGP, où chaque jeu est représenté par un ensemble de règles logiques au travers du Game Description Language (GDL), ont conduit la recherche à confronter de nombreuses approches incluant les méthodes de type Monte Carlo, la construction automatique de fonctions d’évaluation, ou la programmation logique et ASP. De par cette thèse, nous proposons une nouvelle approche dirigée par les contraintes stochastiques.Dans un premier temps, nous nous concentrons sur l’élaboration d’une traduction de GDL en réseauxde contraintes stochastiques (SCSP) dans le but de fournir une représentation dense des jeux de stratégies et permettre la modélisation de stratégies.Par la suite, nous exploitons un fragment de SCSP au travers d’un algorithme dénommé MAC-UCBcombinant l’algorithme MAC (Maintaining Arc Consistency) utilisé pour résoudre chaque niveau duSCSP tour après tour, et à l’aide de UCB (Upper Confidence Bound) afin d’estimer l’utilité de chaquestratégie obtenue par le dernier niveau de chaque séquence. L’efficacité de cette nouvelle technique sur les autres approches GGP est confirmée par WoodStock, implémentant MAC-UCB, le leader actuel du tournoi continu de GGP.Finalement, dans une dernière partie, nous proposons une approche alternative à la détection de symétries dans les jeux stochastiques, inspirée de la programmation par contraintes. Nous montrons expérimentalement que cette approche couplée à MAC-UCB, surpasse les meilleures approches du domaine et a permis à WoodStock de devenir champion GGP 2016. / The ability for a computer program to effectively play any strategic game, often referred to General Game Playing (GGP), is a key challenge in AI. The GGP competitions, where any game is represented according to a set of logical rules in the Game Description Language (GDL), have led researches to compare various approaches, including Monte Carlo methods, automatic constructions of evaluation functions, logic programming, and answer set programming through some general game players. In this thesis, we offer a new approach driven by stochastic constraints. We first focus on a translation process from GDL to stochastic constraint networks (SCSP) in order to provide compact representations of strategic games and to model strategies. In a second part, we exploit a fragment of SCSP through an algorithm called MAC-UCB by coupling the MAC (Maintaining Arc Consistency) algorithm, used to solve each stage of the SCSP in turn, together with the UCB (Upper Confidence Bound) policy for approximating the values of those strategies obtained by the last stage in the sequence. The efficiency of this technical on the others GGP approaches is confirmed by WoodStock, implementing MAC-UCB, the actual leader on the GGP Continuous Tournament. Finally, in the last part, we propose an alternative approach to symmetry detection in stochastic games, inspired from constraint programming techniques. We demonstrate experimentally that MAC-UCB, coupled with our constranit-based symmetry detection approach, significantly outperforms the best approaches and made WoodStock the GGP champion 2016.

No description available.

No description available.