Algorithme de Metropolis-Hastings

En statistique, l'algorithme de Metropolis-Hastings est une méthode MCMC dont le but est d'obtenir un échantillonnage aléatoire d'une distribution de probabilité quand l'échantillonnage direct en est difficile. Plus formellement, étant donné une distribution de probabilité \pi sur un univers \Omega, cet algorithme définit une chaîne de Markov dont la distribution stationnaire est \pi. Il permet ainsi de tirer aléatoirement un élément de \Omega selon la loi \pi. Un point essentiel de l'algorithme de Metropolis-Hastings est qu'il ne nécessite que la connaissance de \pi à une constante multiplicative près. En particulier, il n'est pas nécessaire de calculer la fonction de partition de \pi, tâche souvent difficile. Pour cette raison, cette méthode est très utilisée en physique statistique. On peut noter que l'algorithme de Metropolis–Hastings (comme d'autres méthodes MCMC) est généralement ut

Understanding the Web

Eda Baykan

The World Wide Web is one of the most widely used information resources. Understanding the web better will enable us to benefit more of it. In this thesis we develop techniques to learn the properties of the web pages like language and topic using only the URLs of web pages. Furthermore we make a comparison and evaluation of web page sampling algorithms to learn about the web properties like content length, top level domain and outdegree distribution. In the first part of this thesis, we develop high performance classifiers for web page language classification using only the URL of web pages. We make a comprehensive study of features and algorithms and test the performance of our classifiers on various real data sets. For language classification the quality of our URL-based classifiers rival the quality of classifiers based on content. Language classification from URL is useful when the content of the web page is not available and when the classification speed is important. Language classifiers based on URLs can be used by crawlers of general and language specific search engines to avoid bandwidth waste. In the second part of this thesis, we investigate whether web page topic classification can be done only with URL. We explore this problem in various dimensions like experimenting with different algorithms, features, data sets and topics. URL-based topic classification is useful when the content of the web page is not available or the content is hidden in images. Topic classifiers based on URLs can be used to filter information and in applications like topic focused crawlers. Although content based topic classifiers give better performances, our URL-based topic classifiers work reasonably well and can be used as a signal to improve the performance of content based classifiers. In the third part of this thesis, we compare the state of art web page sampling algorithms and analyze the samples returned by these algorithms using the web properties like content length, top level domain and outdegree distribution. We discuss the strengths and weaknesses of each algorithm and propose improvements based on experimental results. The sampling algorithms we run on the web are influenced by the structure of the web. We investigate the relationship between the properties of the web and the structure of it. A uniform random sample of the web would be quite useful to learn about the composition and development of the web as it is not possible to download all the web pages to determine the properties of the web.

EPFL2009

Stable computation of probability densities for metastable dynamical systems

Lionel Walter

Whenever the invariant stationary density of metastable dynamical systems decomposes into almost invariant partial densities, its computation as eigenvector of some transition probability matrix is an ill-conditioned problem. In order to avoid this computational difficulty, we suggest applying an aggregation/disaggregation method which addresses only well-conditioned subproblems aud thus results in a stable algorithm. In contrast to existing methods, the aggregation step is done via a sampling algorithm which covers only small patches of the sampling space. Finally, the theoretical analysis is illustrated by two biomolecular examples.

Society for Industrial and Applied Mathematics2007

Understanding the Web

Eda Baykan

EPFL2009