Une donnée peut avoir diverses formes et peut provenir d'un large panel d'applications. Habituellement, une donnée possède beaucoup de bruit et peut être soumise aux effets du hasard. Les récents progrès en apprentissage automatique ont relancé les recherches théoriques sur les limites des différentes méthodes probabilistes de traitement du signal. Dans cette thèse, nous nous intéressons aux questions suivantes : quelle est la meilleure performance possible atteignable ? Et comment peut-elle être atteinte, i.e., quelle est la stratégie algorithmique optimale ?La réponse dépend de la forme des données. Les sujets traités dans cette thèse peuvent tous être représentés par des modèles graphiques. Les propriétés des données déterminent la structure intrinsèque du modèle graphique correspondant. Les structures considérées ici sont soit éparses, soit denses. Les questions précédentes peuvent être étudiées dans un cadre probabiliste, qui permet d'apporter des réponses typiques. Un tel cadre est naturel en physique statistique et crée une analogie formelle avec la physique des systèmes désordonnés. En retour, cela permet l'utilisation d'outils spécifiques à ce domaine et de résoudre des problèmes de satisfaction de contraintes et d'inférence statistique. La problématique de performance optimale est directement reliée à la structure des extrema de la fonction d'énergie libre macroscopique, tandis que les aspects algorithmiques proviennent eux de la minimisation de la fonction d'énergie libre microscopique (c'est-à-dire, dans la forme de Bethe).Cette thèse est divisée en quatre parties. Premièrement, nous aborderons par une approche de physique statistique le problème de la coloration de graphes aléatoires et mettrons en évidence un certain nombre de caractéristiques. Dans un second temps, nous calculerons une nouvelle limite supérieure de la taille de l'ensemble contagieux. Troisièmement, nous calculerons le diagramme de phase du modèle de Dawid et Skene dans la région dense en modélisant le problème par une factorisation matricielle de petit rang. Enfin, nous calculerons l'erreur optimale de Bayes pour une classe restreinte de l'estimation matricielle de rang élevé. / Datasets come in a variety of forms and from a broad range of different applications. Typically, the observed data is noisy or in some other way subject to randomness. The recent developments in machine learning have revived the need for exact theoretical limits of probabilistic methods that recover information from noisy data. In this thesis we are concerned with the following two questions: what is the asymptotically best achievable performance? And how can this performance be achieved, i.e., what is the optimal algorithmic strategy? The answer depends on the properties of the data. The problems in this thesis can all be represented as probabilistic graphical models. The generative process of the data determines the structure of the underlying graphical model. The structures considered here are either sparse random graphs or dense (fully connected) models. The above questions can be studied in a probabilistic framework, which leads to an average (or typical) case answer. Such a probabilistic formulation is natural to statistical physics and leads to a formal analogy with problems in disordered systems. In turn, this permits to harvest the methods developed in the study of disordered systems, to attack constraint satisfaction and statistical inference problems. The formal analogy can be exploited as follows. The optimal performance analysis is directly related to the structure of the extrema of the macroscopic free energy. The algorithmic aspects follow from the minimization of the microscopic free energy (that is, the Bethe free energy in this work) which is closely related to message passing algorithms. This thesis is divided into four contributions. First, a statistical physics investigation of the circular coloring problem is carried out that reveals several distinct features. Second, new rigorous upper bounds on the size of minimal contagious sets in random graphs, with bounded maximum degree, are obtained. Third, the phase diagram of the dense Dawid-Skene model is derived by mapping the problem onto low-rank matrix factorization. The associated approximate message passing algorithm is evaluated on real-world data. Finally, the Bayes optimal denoising mean square error is derived for a restricted class of extensive rank matrix estimation problems.

Neste trabalho consideramos um processo de Markov a tempo contínuo com espaço de estados finito em um meio aleatório, a saber, a dinâmica de Metropolis para o Modelo de Energia Aleatória Generalizado (GREM) com um número de níveis finito e discutimos o comportamento do seu tempo de chegada ao equilíbrio, o qual é dado pelo inverso da lacuna espectral de sua matriz de probabilidades de transição. No principal resultado desta tese provamos que o quociente entre o volume do sistema e o logaritmo do inverso da lacuna é quase sempre limitado, por cima, por uma função da temperatura, que também é a que descreve a energia livre do GREM sob o regime de temperaturas baixas. Como um estudo adicional, também é discutido um correspondente limitante inferior em um caso particular do GREM com 2 níveis. / In this work we consider a finite state continuous-time Markov process in a random environment, namely, the Metropolis dynamics for the Generalized Random Energy Model (GREM) with a finite number of levels, and we discuss the behavior of its reaching time to equilibrium which is given by inverse of the spectral gap of its transition probability matrix. On the main result of this thesis, we prove the division between the system volume and the logarithm of the inverse of the gap is almost surely upper bounded by a function of the temperature that it is also the function that describe the free energy of the GREM at low temperature. As an additional study, it is also discuss the corresponding limiting lower in a particular case of the 2-level GREM.

The results reported in this thesis contribute to the understanding of disordered systems, to mesoscopic physics on the one hand, and to the physics of spin glasses on the other hand. The first part of this thesis studies numerically coherent electronic transport in a non magnetic metal accurately doped with frozen magnetic impurities (a low temperature spin glass). Thanks to a recursive code that calculates the two terminal conductance of the system, we study in detail the metallic regime of conduction (large conductance) as well as the insulating regime (small conductance). In both regimes, we highlight a universal behavior of the system. Moreover, a study of correlations between the conductance of different spin configurations of impurities allows us to link these correlations with correlations between spin configurations. This study opens the route for the first experimental determination of the overlap via transport measurements. A second part of this thesis deals with the study of the mean field Sherrington-Kirkpatrick model, which describes the low temperature phase of an Ising spin glass. We are interested here in the generalization of this model to quantum spins (i.e including the possibility to flip by quantum tunneling) of this classical model that was well studied during the past thirty years. We deduce analytically motion equations at the semi-classical level, for which the influence of quantum tunneling is weak, and we compare them with the classical case. We finally solve numerically these equations using a pseudo-spectral method.

Dans la présente thèse de doctorat je présente des résultats concernant des modèles désordonnés et frustrés venant de la physique statistique et de l'optimisation combinatoire. Comme application de la théorie des verres de spins, j'étudie le modèle de Blume, Emery et Griffiths désordonné et frustré. Ce modèle est traité dans l'approximation de champ moyen dans le cadre de la méthode des répliques A l'aide de l'Ansatz symétrique dans les répliques je présente une solution numérique complète puis je discute des effets de brisure de cette symétrie La stabilité de la solution symétrique a été Rudik et les régions instables identifiées Le diagramme de phase exhibe des transitions de premier et de second ordre. Le point tricritique persiste dans le modèle frustré, Ce qui est en accord avec des travaux antérieurs une version du modèle BEG avec un potentiel chimique désordonné a également été étudiée. les calculs confirment que le point tricritique apparaît à plus basse température quand il y a du désordre. Ensuite je considère le problème de la bipartition d'un graphe. Ce problème correspond du point de vue de la physique statistique h un verre de spins soumis h une contrainte d'aimantation totale nulle. je considère les propriétés statistiques des solutions de faible énergie engendrées par des algorithmes heuristiques. de tels algorithme sont en général conçus pour résoudre des problèmes d'optimisation combinatoire qui sont NP- difficiles. Plusieurs heuristiques ont 60 implémentées pour le problème de la bipartition de graphe. des lois d'échelle ont été obtenues : en particulier la moyenne et la variance du coût obéissent A une loi linéaire en N. Par conséquent le coût obtenu par des heuristiques est une quantité auto-moyennante. je suggère que cette propriété est générale valable aussi pour les solutions aléatoires pour les solutions quasi-optimales et pour les solutions optimales. En outre je propose une procédure pour comparer des algorithmes heuristiques. Cette procédure tient compte de la qualité de la solution aussi bien que du temps de calcul utilisé. Dans la troisième partie de ma thèse j'ai étudié en détail les propriétés h température nulle des verres de spins sur des graphes aléatoires lacunaires avec une coordination fixe. les verres de spins sur de tels graphes peuvent être considérés comme une approximation aux vrais verres de spins qui est plus réaliste que le modèle de Sherrington et Kirkpatrick. J'ai conçu un nouvel algorithme pour trouver les états fondamentaux. Aussi je teste numériquement une conjecture de Banavar, Sherrington et Sourlas qui donne la densité d'énergie du fondamental dans la limite de grande taille en fonction de la coordination. La distribution du paramètre d'ordre se révèle être non triviale et les données présentent une forte indication de la présence d'ultramétricité pour toutes les valeur de la coordination. Ces résultats confirment que les propriétés particulières des verres de spin, déduites an niveau de l'approximation de champ moyen dans le cadre du modèle de Sherrington et Kirkpatrick, sont aussi présentes pour des modèles plus réalistes comme les verres de spins sur des graphes aléatoires lacunaires avec une coordination fixe.

Recent experimental techniques in biology made possible the acquisition of overwhelming amounts of data concerning complex biological networks, such as neural networks, gene regulation networks and protein-protein interaction networks. These techniques are able to record states of individual components of such networks (neurons, genes, proteins) for a large number of configurations. However, the most biologically relevantinformation lies in their connectivity and in the way their components interact, information that these techniques aren't able to record directly. The aim of this thesis is to study statistical methods for inferring information about the connectivity of complex networks starting from experimental data. The subject is approached from a statistical physics point of view drawing from the arsenal of methods developed in the study of spin glasses. Spin-glasses are prototypes of networks of discrete variables interacting in a complex way and are widely used to model biological networks. After an introduction of the models used and a discussion on the biological motivation of the thesis, all known methods of network inference are introduced and analysed from the point of view of their performance. Then, in the third part of the thesis, a new method is proposed which relies in the remark that the interactions in biology are not necessarily symmetric (i.e. the interaction from node A to node B is not the same as the one from B to A). It is shown that this assumption leads to methods that are both exact and efficient. This means that the interactions can be computed exactly, given a sufficient amount of data, and in a reasonable amount of time. This is an important original contribution since no other method is known to be both exact and efficient.

No description available.

Orientador: Mario Antonio Bica de Moraes / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Fisica Gleb Wataghin / Made available in DSpace on 2018-08-11T18:58:49Z (GMT). No. of bitstreams: 1 Rouxinol_FranciscoPauloMarques_D.pdf: 6433084 bytes, checksum: 84d703ca8da3620b077c3b1335c59965 (MD5) Previous issue date: 2008 / Resumo: Técnicas de condensação de vapor são úteis na preparação de ligas magnéticas cujos componentes têm pouca, o mesmo nenhuma, solubilidade em condições de equilíbrio Neste trabalho, uma dessas técnicas ¿ sputtering ¿ foi empregada para fabricar ligas metaestáveis de GdXCr1-X, cujas propriedades magnéticas foram investigadas em função da concentração de Gd, x. Difratometria de raios-X de baixo ângulo (GAXRD) e espectroscopia de retroespalhamento Rutherford foram utilizados para determinar a estrutura do filme e sua composição elementar, respectivamente. As análises de GAXRD mostraram que a estrutura da fase de Gd, é hcp quando x ³ 0,88; e amorfa quando 0,16 £ 0,76. Uma estrutura bcc , para a fase de Cr, foi observada nos difratogramas quando x < 0,16, e amorfa quando x ³ 0,16 Para investigar as propriedades magnéticas utilizamos um magnetometro SQUID e m PPMS. O primeiro foi utilizado para as medidas de momento magnético em função do campo estático e temperatura. O PPMS foi tilizado nas investigações de susceptibilidade-AC em função da freqüência de oscilação do campo, temperatura e campo estático. A complexa natureza magnética dos filmes de Gd-Cr foi observada através das isotermas MxH, que não apresentaram saturação em baixas temperaturas, nem comportamento linear em altas temperaturas. Pela análise dos dados magnéticos, observamos que as amostras admitem um comportamento ferromagnético para x ³ 0,5 e paramagnético para as outras concentrações de Gd. A temperatura de Curie (TC) apresenta um aumento monotônico de 170 para 290 K quando x aumenta de 0,5 para 1,0. A temperatura de Curie-Weiss (q C) mostra um aumento monotônico com x. A partir das isotermas MxH a 2 K, o momento de saturação foi calculado, sendo independente de x e aproximadamente constante com um valor médio de 7,3 µB. Medidas de susceptibilidade em campos estáticos e dinâmicos revelaram a existência de comportamentos de vidros magnéticos em todas as amostras abaixo da temperat ra de freezing (Tf). Observamos, nas ligas com altas concentrações de Gd, a presença de comportamentos ferromagnéticos e cluster-glass em baixas temperaturas. Concluímos que a interação de troca entre os átomos de Gd dentro dos clusters de Gd não é do tipo RKKY, e sim do tipo supertroca. O efeito magnetocalórico (MCE) foi investigado através da variação de entropia magnética ( D SM) em função da temperatura, para a remoção de um campo de 50 kOe Curva de D SMxT para as amostras com x < 0,2 apresentaram um formato típico de superferromagneto, consistente com a existência de clusters Gd nos filmes. Nas outras amostras em que o EMC foi analisado, a presença de clusters é observada pelo comportamento dessas curvas a baixa temperatura; a altas temperaturas o comportamento de D SM com T indica fortemente a presença de mais fases magnéticas no filme. O diagrama de fase baseado em TC e Tf, e sua dependência com x é apresentado / Abstract: Vapor condensation techniques are very useful for preparation of alloys whose components have no mutual solubility under equilibrium conditions In this work, one of these techniques ¿ sputtering ¿ has been used to fabricate metastable GdXCr1-X alloys whose magnetic properties were investigated as a function of the Gd concentration, x. Grazing incidence angle X-ray diffraction (GAXRD) and Rutherford backscattering spectroscopy were employed to characterize the film structure and elemental composition, respectively. The GAXRD measurements revealed, for the Gd fraction, a hcp structure for x ³ 0,88; for 0,16 £ x £ 0,76 the Gd fraction was amorphous. The existence of a bcc structure for x < 0,16 was observed in the diffractograms for the Cr phase, which was amorphous for x ³ 0,16. To investigate the magnetic properties, a SQUID magnetometer and a PPMS were used. The former was employed for magnetic moment measurements as a function of applied static field and temperature. The PPMS was used for ac-susceptibility determinations as a function of the frequency of the ac driving field, temperature, and applied static field. The complex magnetic nature of the Gd-Cr films was revealed from the MxH isotherms which did not show saturation even at the lowest temperatures, and did not exhibit a linear behavior at higher temperatures. Processing of the magnetic data has shown that the films exhibit a ferromagnetic behavior for x ³ 0,5 and paramagnetic one for all other Gd concentrations. The Curie temperature (TC) increased monotonically from 170 to 290 K as x increased from 0,5 to 1,0. A monotonical increase in the Curie-Weiss temperature ( q C ) with x was also observed for all films. From the extrapolated MxH isotherm at 2 K (saturation magnetization), the saturation moments were calculated and found to be nearly constant at about 7.3 µB. Both static and dynamic susceptibility measurements revealed the existence of a magnetic glassy behavior in all alloys, occurring below a freezing temperature Tf . For the higher concentration alloys, the ferromagnetic and the cluster glass state were observed at low temperatures. It was thus concluded that the exchange interactions within Gd atoms in the clusters were not of the RKKY but of the superexchange type. The magnetocaloric effect (MCE) was investigated from the magnetic entropy change ( DSM) as a function of temperature, for the removal of a 50 kOe field. Samples with x < 0,2 exhibited DSMxT curves whose shapes are typical of a superferromagnet, consistently with the existence of Gd clusters in the films. For all the other alloys whose MCE was investigated, the presence of clusters is manifested from the behavior of these curves at low temperatures; at higher temperatures, the evolution of DSM with T strongly indicated the presence of more than one magnetic phase in the alloys A magnetic phase diagram based on the Tf and Tc transition temperatures and their dependence on x is presented in this thesis / Doutorado / Física da Matéria Condensada / Doutor em Ciências

Des techniques expérimentales récentes ont donné la possibilité d'acquérir un très grand nombre de données concernant des réseaux biologiques complexes, comme des réseaux de neurones, des réseaux de gènes et des réseaux d'interactions de protéines. Ces techniques sont capables d'enregistrer les états des composantes individuelles de ces réseaux (neurones, gènes, protéines) pour un grand nombre de configurations. Cependant, l'information la plus pertinente biologiquement se trouve dans la connectivité de ces systèmes et dans la façon précise avec laquelle ces composantes interagissent, information que les techniques expérimentales ne sont pas au point d'observer directement. Le bût de cette thèse est d'étudier les méthodes statistiques nécessaires pour inférer de l'information sur la connectivité des réseaux complexes en partant des données expérimentales. Ce sujet est traité par le point de vue de la physique statistique, en puisant de l'arsenal de méthodes théoriques qui ont été développées pour l'étude des verres de spins. Les verres de spins sont des exemples de réseaux à variables discrètes qui interagissent de façon complexe et sont souvent utilisés pour modéliser des réseaux biologiques. Après une introduction sur les modèles utilisés ainsi qu'une discussion sur la motivation biologique de cette thèse, toutes les méthodes d'inférence de réseaux connues sont présentées et analysées du point de vue de leur performance. Par la suite, dans la troisième partie de la thèse, un nouvelle méthode est proposée qui s'appuie sur la remarque que les interactions en biologie ne sont pas nécessairement symétriques (c'est-à-dire l'interaction entre les noeuds A et B n'est pas la même dans les deux directions). Il est démontré que cette assomption conduit à des méthodes qui sont capables de prédire les interactions de façon exacte, étant donné un nombre suffisant de données, tout en utilisant un temps de calcul polynomial. Ceci est un résultat original important car toutes les autres méthodes connues sont soit exactes et non-polynomiales soit inexactes et polynomiales. / Recent experimental techniques in biology made possible the acquisition of overwhelming amounts of data concerning complex biological networks, such as neural networks, gene regulation networks and protein-protein interaction networks. These techniques are able to record states of individual components of such networks (neurons, genes, proteins) for a large number of configurations. However, the most biologically relevantinformation lies in their connectivity and in the way their components interact, information that these techniques aren't able to record directly. The aim of this thesis is to study statistical methods for inferring information about the connectivity of complex networks starting from experimental data. The subject is approached from a statistical physics point of view drawing from the arsenal of methods developed in the study of spin glasses. Spin-glasses are prototypes of networks of discrete variables interacting in a complex way and are widely used to model biological networks. After an introduction of the models used and a discussion on the biological motivation of the thesis, all known methods of network inference are introduced and analysed from the point of view of their performance. Then, in the third part of the thesis, a new method is proposed which relies in the remark that the interactions in biology are not necessarily symmetric (i.e. the interaction from node A to node B is not the same as the one from B to A). It is shown that this assumption leads to methods that are both exact and efficient. This means that the interactions can be computed exactly, given a sufficient amount of data, and in a reasonable amount of time. This is an important original contribution since no other method is known to be both exact and efficient.