New Results for the MAP Problem in Bayesian Networks

This paper presents new results for the (partial) maximum a posteriori (MAP) problem in Bayesian networks, which is the problem of querying the most probable state configuration of some of the network variables given evidence. First, it is demonstrated that the problem remains hard even in networks with very simple topology, such as binary polytrees and simple trees (including the Naive Bayes structure). Such proofs extend previous complexity results for the problem. Inapproximability results are also derived in the case of trees if the number of states per variable is not bounded. Although the problem is shown to be hard and inapproximable even in very simple scenarios, a new exact algorithm is described that is empirically fast in networks of bounded treewidth and bounded number of states per variable. The same algorithm is used as basis of a Fully Polynomial Time Approximation Scheme for MAP under such assumptions. Approximation schemes were generally thought to be impossible for this problem, but we show otherwise for classes of networks that are important in practice. The algorithms are extensively tested using some well-known networks as well as random generated cases to show their effectiveness.

Fast Rule Mining over Multi-dimensional Windows

Association rule mining is an indispensable tool for discovering
insights from large databases and data warehouses.
The data in a warehouse being multi-dimensional, it is often
useful to mine rules over subsets of data defined by selections
over the dimensions. Such interactive rule mining
over multi-dimensional query windows is difficult since rule
mining is computationally expensive. Current methods using
pre-computation of frequent itemsets require counting
of some itemsets by revisiting the transaction database at
query time, which is very expensive. We develop a method
(RMW) that identifies the minimal set of itemsets to compute
and store for each cell, so that rule mining over any
query window may be performed without going back to the
transaction database. We give formal proofs that the set of
itemsets chosen by RMW is sufficient to answer any query
and also prove that it is the optimal set to be computed
for 1 dimensional queries. We demonstrate through an extensive
empirical evaluation that RMW achieves extremely
fast query response time compared to existing methods, with
only moderate overhead in pre-computation and storage

Triangular Objects and Systematic K-Theory

We investigate modules over “systematic” rings. Such rings are “almost graded” and have appeared under various names in the literature; they are special cases of the G-systems of Grzeszczuk. We analyse their K-theory in the presence of conditions on the support, and explain how this generalises and unifies calculations of graded and filtered K-theory scattered in the literature. Our treatment makes systematic use of the formalism of idempotent completion and a theory of triangular objects in additive categories, leading to elementary and transparent proofs throughout.

Prediction and Privacy in Healthcare Analytics

Thesis (Master's)--University of Washington, 2016-03

Providing User Security Guarantees in Public Infrastructure Clouds

The infrastructure cloud (IaaS) service model offers improved resource flexibility and availability, where tenants - insulated from the minutiae of hardware maintenance - rent computing resources to deploy and operate complex systems. Large-scale services running on IaaS platforms demonstrate the viability of this model; nevertheless, many organizations operating on sensitive data avoid migrating operations to IaaS platforms due to security concerns. In this paper, we describe a framework for data and operation security in IaaS, consisting of protocols for a trusted launch of virtual machines and domain-based storage protection. We continue with an extensive theoretical analysis with proofs about protocol resistance against attacks in the defined threat model. The protocols allow trust to be established by remotely attesting host platform configuration prior to launching guest virtual machines and ensure confidentiality of data in remote storage, with encryption keys maintained outside of the IaaS domain. Presented experimental results demonstrate the validity and efficiency of the proposed protocols. The framework prototype was implemented on a test bed operating a public electronic health record system, showing that the proposed protocols can be integrated into existing cloud environments.

ViDi Stat

A tese desenvolvida tem como foco fornecer os meios necessários para extrair conhecimento contidos no histórico académico da instituição transformando a informação em algo simples e de fácil leitura para qualquer utilizador. Com o progresso da sociedade, as escolas recebem milhares de alunos todos os anos que terão de ser orientados e monitorizados pelos dirigentes das instituições académicas de forma a garantir programas eficientes e adequados para o progresso educacional de todos os alunos. Atribuir a um docente a responsabilidade de actuar segundo o historial académico dos seus alunos não é plausível uma vez que um aluno consegue produzir milhares de registos para análise. O paradigma de mineração de dados na educação surge com a necessidade de otimizar os recursos disponíveis expondo conclusões que não se encontram visiveis sem uma análise acentuada e cuidada. Este paradigma expõe de forma clara e sucinta os dados estatísticos analisados por computador oferecendo a possibilidade de melhorar as lacunas na qualidade de ensino das instituições. Esta dissertação detalha o desenvolvimento de uma ferramente de inteligência de negócio capaz de, através de mineração de dados, analisar e apresentar conclusões pertinentes de forma legível ao utilizador.

A internet e o sistema de justiça

The subject of study of this Thesis aims to highlight and recognize as an object of reflection the undoubted relationship between the Internet and the Justice System, based on the issue of digital evidence. The simultaneously crossing of the juridical-legal implications and the more technical computer issues is the actual trigger for the discussion of the issues established. The Convention on Cybercrime of the Council of Europe of 23rd November 2001 and the Council Framework Decision n.° 2005/222/JHA of 24th February 2005 were avant-garde in terms of the international work about the crimes in the digital environment. In addition they enabled the harmonization of national legislations on the matter and, consequently, a greater flexibility in international judicial cooperation. Portugal, in compliance with these international studies, ratified, implemented and approved Law n. º 109/2009 of 15th September concerning the Cybercrime Act, establishing a more specific investigation and collection of evidence in electronic support when it comes to combating this type of crime, as it reinforced the Substantive Criminal Law and Procedural Nature. Nevertheless, the constant debates about the New Technologies of Information and Communication have not neglected the positive role of these tools for the user. However, they express a particular concern for their counterproductive effects; a special caution prevails on the part of the judge in assessing the digital evidence, especially circumstantial evidence, due to the its fragility. Indisputably, the practice of crimes through the computer universe, given its inexorable technical complexity, entails many difficulties for the forensic investigation, since the proofs hold temporary, changeable, volatile, and dispersed features. In this pillar, after the consummation of iter criminis, the Fundamental Rights of the suspects may be debated in the course of the investigation and the construction of iter probatorium. The intent of this Thesis is to contribute in a reflective way on the issues presented in order to achieve a bigger technical and legal awareness regarding the collection of digital proof, looking for a much lighter approach to its suitability in terms of evidentiary value.

Nietzsche's eternal recurrence of the same : the effect of logic abridgement, contradictions and inconsistencies

I will argue that the doctrine of eternal recurrence of the same no better interprets cosmology than pink elephants interpret zoology. I will also argue that the eternal-reiurn-of-the-same doctrine as what Magnus calls "existential imperative" is without possibility of application and thus futile. To facilitate those arguments, the validity of the doctrine of the eternal recurrence of the same will be tested under distinct rubrics. Although each rubric will stand alone, one per chapter, as an evaluation of some specific aspect of eternal recurrence, the rubric sequence has been selected to accommodate the identification of what I shall be calling logic abridgments. The conclusions to be extracted from each rubric are grouped under the heading CONCLUSION and appear immediately following rubric ten. Then, or if, at the end of a rubric a reader is inclined to wonder which rubric or topic is next, and why, the answer can be found at the top of the following page. The question is usually answered in the very first sentence, but always answered in the first paragraph. The first rubric has been placed in order by chronological entitlement in that it deals with the evolution of the idea of eternal recurrence from the time of the ancient Greeks to Nietzsche's August, 1881 inspiration. This much-recommended technique is also known as starting at the beginning. Rubric 1 also deals with 20th. Century philosophers' assessments of the relationship between Nietzsche and ancient Greek thought. The only experience of E-R, Zarathustra's mountain vision, is second only because it sets the scene alluded to in following rubrics. The third rubric explores .ii?.ih T jc,i -I'w Nietzsche's evaluation of rationality so that his thought processes will be understood appropriately. The actual mechanism of E-R is tested in rubric four...The scientific proof Nietzsche assembled in support of E-R is assessed by contemporary philosophers in rubric five. E-R's function as an ethical imperative is debated in rubrics six and seven.. .The extent to which E-R fulfills its purpose in overcoming nihilism is measured against the comfort assured by major world religions in rubric eight. Whether E-R also serves as a redemption for revenge is questioned in rubric nine. Rubric ten assures that E-R refers to return of the identically same and not merely the similar. In addition to assemblage and evaluation of all ten rubrics, at the end of each rubric a brief recapitulation of its principal points concludes the chapter. In this essay I will assess the theoretical conditions under which the doctrine cannot be applicable and will show what contradictions and inconsistencies follow if the doctrine is taken to be operable. Harold Alderman in his book Nietzsche's Gift wrote, the "doctrine of eternal recurrence gives us a problem not in Platonic cosmology, but in Socratic selfreflection." ^ I will illustrate that the recurrence doctrine's cosmogony is unworkable and that if it were workable, it would negate self-reflection on the grounds that selfreflection cannot find its cause in eternal recurrence of the same. Thus, when the cosmology is shown to be impossible, any expected ensuing results or benefits will be rendered also impossible. The so-called "heaviest burden" will be exposed as complex, engrossing "what if speculations deserving no linkings to reality. To identify ^Alderman p. 84 abridgments of logic, contradictions and inconsistencies in Nietzsche's doctrine of eternal recurrence of the same, I. will examine the subject under the following schedule. In Chapter 1 the ancient origins of recurrence theories will be introduced. ..This chapter is intended to establish the boundaries within which the subsequent chapters, except Chapter 10, will be confined. Chapter 2, Zarathustra's vision of E-R, assesses the sections of Thus Spoke Zarathustra in which the phenomenon of recurrence of the same is reported. ..Nihilism as a psychological difficulty is introduced in this rubric, but that subject will be studied in detail in Chapter 8. In Chapter 2 the symbols of eternal recurrence of the same will be considered. Whether the recurrence image should be of a closed ring or as a coil will be of significance in many sections of my essay. I will argue that neither symbolic configuration can accommodate Nietzsche's supposed intention. Chapter 3 defends the description of E-R given by Zarathustra. Chapter 4, the cosmological mechanics of E-R, speculates on the seriousness with which Nietzsche might have intended the doctrine of eternal recurrence to be taken. My essay reports, and then assesses, the argument of those who suppose the doctrine to have been merely exploratory musings by Nietzsche on cosmological hypotheses...The cosmogony of E-R is examined. In Chapter 5, cosmological proofs tested, the proofs for Nietzsche's doctrine of return of the same are evaluated. This chapter features the position taken by Martin ' Heidegger. My essay suggests that while Heidegger's argument that recurrence of the same is a genuine cosmic agenda is admirable, it is not at all persuasive. Chapter 6, E-R is an ethical imperative, is in essence the reporting of a debate between two scholars regarding the possibility of an imperative in the doctrine of recurrence. Their debate polarizes the arguments I intend to develop. Chapter 7, does E-R of the same preclude alteration of attitudes, is a continuation of the debate presented in Chapter 6 with the focus shifted to the psychological from the cosmological aspects of eternal recurrence of the same. Chapter 8, Can E-R Overcome Nihilism?, is divided into two parts. In the first, nihilism as it applies to Nietzsche's theory is discussed. ..In part 2, the broader consequences, sources and definitions of nihilism are outlined. My essay argues that Nietzsche's doctrine is more nihilistic than are the world's major religions. Chapter 9, Is E-R a redemption for revenge?, examines the suggestion extracted from Thus Spoke Zarathustra that the doctrine of eternal recurrence is intended, among other purposes, as a redemption for mankind from the destructiveness of revenge. Chapter 10, E-R of the similar refuted, analyses a position that an element of chance can influence the doctrine of recurrence. This view appears to allow, not for recurrence of the same, but recurrence of the similar. A summary will recount briefly the various significant logic abridgments, contradictions, and inconsistencies associated with Nietzsche's doctrine of eternal recurrence of the same. In the 'conclusion' section of my essay my own opinions and observations will be assembled from the body of the essay.

Candidate Stability and Nonbinary Social Choice

A desirable property of a voting procedure is that it be immune to the strategic withdrawal of a candidate for election. Dutta, Jackson, and Le Breton (Econometrica, 2001) have established a number of theorems that demonstrate that this condition is incompatible with some other desirable properties of voting procedures. This article shows that Grether and Plott's nonbinary generalization of Arrow's Theorem can be used to provide simple proofs of two of these impossibility theorems.

La relation complexe du juge et de l'expert-psychiatre

L'expertise psychiatrique est requise au tribunal dans plusieurs situations juridiques tant en matière criminelle que civile et elle est soumise aux mêmes règles de preuve que n'importe quelle expertise. Pourtant, la psychiatrie et son objet sont tout à fait particuliers. La relation que peuvent entretenir le juge et l'expert-psychiatre est teintée par plusieurs éléments de nature sociale et professionnelle, mais aussi simplement juridique et procédural. Alors que les juristes parlent de cette relation comme d'une usurpation du rôle du juge par l'expert-psychiatre, les psychiatres, au contraire, croient que leur expertise est totalement pervertie dans le processus judiciaire. Mais la réalité n'est pourtant pas univoque: si l'expertise psychiatrique est de façon générale une preuve parmi les autres, elle peut également occuper une place centrale dans le mécanisme décisionnel.

Variétés de drapeaux et opérateurs différentiels

Soit G un groupe algébrique semi-simple sur un corps de caractéristique 0. Ce mémoire discute d'un théorème d'annulation de la cohomologie supérieure du faisceau D des opérateurs différentiels sur une variété de drapeaux de G. On démontre que si P est un sous-groupe parabolique de G, alors H^i(G/P,D)=0 pour tout i>0. On donne en fait trois preuves indépendantes de ce théorème. La première preuve est de Hesselink et n'est valide que dans le cas où le sous-groupe parabolique est un sous-groupe de Borel. Elle utilise un argument de suites spectrales et le théorème de Borel-Weil-Bott. La seconde preuve est de Kempf et n'est valide que dans le cas où le radical unipotent de P agit trivialement sur son algèbre de Lie. Elle n'utilise que le théorème de Borel-Weil-Bott. Enfin, la troisième preuve est attribuée à Elkik. Elle est valide pour tout sous-groupe parabolique mais utilise le théorème de Grauert-Riemenschneider. On présente aussi une construction détaillée du faisceau des opérateurs différentiels sur une variété.

Preuves interactives quantiques

Cette thèse est consacrée à la complexité basée sur le paradigme des preuves interactives. Les classes ainsi définies ont toutes en commun qu’un ou plusieurs prouveurs, infiniment puissants, tentent de convaincre un vérificateur, de puissance bornée, de l’appartenance d’un mot à un langage. Nous abordons ici le modèle classique, où les participants sont des machines de Turing, et le modèle quantique, où ceux-ci sont des circuits quantiques. La revue de littérature que comprend cette thèse s’adresse à un lecteur déjà familier avec la complexité et l’informatique quantique. Cette thèse présente comme résultat la caractérisation de la classe NP par une classe de preuves interactives quantiques de taille logarithmique. Les différentes classes sont présentées dans un ordre permettant d’aborder aussi facilement que possible les classes interactives. Le premier chapitre est consacré aux classes de base de la complexité ; celles-ci seront utiles pour situer les classes subséquemment présentées. Les chapitres deux et trois présentent respectivement les classes à un et à plusieurs prouveurs. La présentation du résultat ci-haut mentionné est l’objet du chapitre quatre.

Sur l'inégalité de Visser

Soit p un polynôme d'une variable complexe z. On peut trouver plusieurs inégalités reliant le module maximum de p et une combinaison de ses coefficients. Dans ce mémoire, nous étudierons principalement les preuves connues de l'inégalité de Visser. Nous montrerons aussi quelques généralisations de cette inégalité. Finalement, nous obtiendrons quelques applications de l'inégalité de Visser à l'inégalité de Chebyshev.

Multi-Prover and parallel repetition in non-classical interactive games

Depuis l’introduction de la mécanique quantique, plusieurs mystères de la nature ont trouvé leurs explications. De plus en plus, les concepts de la mécanique quantique se sont entremêlés avec d’autres de la théorie de la complexité du calcul. De nouvelles idées et solutions ont été découvertes et élaborées dans le but de résoudre ces problèmes informatiques. En particulier, la mécanique quantique a secoué plusieurs preuves de sécurité de protocoles classiques. Dans ce m´emoire, nous faisons un étalage de résultats récents de l’implication de la mécanique quantique sur la complexité du calcul, et cela plus précisément dans le cas de classes avec interaction. Nous présentons ces travaux de recherches avec la nomenclature des jeux à information imparfaite avec coopération. Nous exposons les différences entre les théories classiques, quantiques et non-signalantes et les démontrons par l’exemple du jeu à cycle impair. Nous centralisons notre attention autour de deux grands thèmes : l’effet sur un jeu de l’ajout de joueurs et de la répétition parallèle. Nous observons que l’effet de ces modifications a des conséquences très différentes en fonction de la théorie physique considérée.

Distribution asymptotique du nombre de diviseurs premiers distincts inférieurs ou égaux à m

Le sujet principal de ce mémoire est l'étude de la distribution asymptotique de la fonction f_m qui compte le nombre de diviseurs premiers distincts parmi les nombres premiers $p_1,...,p_m$. Au premier chapitre, nous présentons les sept résultats qui seront démontrés au chapitre 4. Parmi ceux-ci figurent l'analogue du théorème d'Erdos-Kac et un résultat sur les grandes déviations. Au second chapitre, nous définissons les espaces de probabilités qui serviront à calculer les probabilités asymptotiques des événements considérés, et éventuellement à calculer les densités qui leur correspondent. Le troisième chapitre est la partie centrale du mémoire. On y définit la promenade aléatoire qui, une fois normalisée, convergera vers le mouvement brownien. De là, découleront les résultats qui formeront la base des démonstrations de ceux chapitre 1.