AZENCOTT Robert

< Back to ILB Patrimony
Topics of productions
Affiliations
  • 2014 - 2015
    University of Houston
  • 2014 - 2015
    Ecole normale supérieure Paris
  • 2015
  • 2014
  • 2005
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1990
  • Accuracy of Maximum Likelihood Parameter Estimators for Heston Stochastic Volatility SDE.

    Robert AZENCOTT, Yutheeka GADHYAN
    Journal of Statistical Physics | 2015
    We study approximate maximum likelihood estimators (MLEs) for the parameters of the widely used Heston stock and volatility stochastic differential equations (SDEs). We compute explicit closed form estimators maximizing the discretized log-likelihood of $N$ observations recorded at times $T,2T, \ldots, NT$. We study the asymptotic bias of these parameter estimators first for $T$ fixed and $N \to \infty$, as well as when the global observation time $S= NT \to \infty$ and $T = S/N \to 0$. We identify two explicit key functions of the parameters which control the type of asymptotic distribution of these estimators, and we analyze the dichotomy between asymptotic normality and attraction by stable like distributions with heavy tails. \\ We present two examples of model fitting for Heston SDEs, one for daily data and one for intraday data, with moderate values of $N$.
  • Biomarker Signature Discovery from Mass Spectrometry Data.

    Ao KONG, Chinmaya GUPTA, Mauro FERRARI, Marco AGOSTINI, Chiara BEDIN, Ali BOUAMRANI, Ennio TASCIOTTI, Robert AZENCOTT
    IEEE/ACM Transactions on Computational Biology and Bioinformatics | 2014
    Mass spectrometry based high throughput proteomics are used for protein analysis and clinical diagnosis. Many machine learning methods have been used to construct classifiers based on mass spectrometry data, for discrimination between cancer stages. However, the classifiers generated by machine learning such as SVM techniques typically lack biological interpretability. We present an innovative technique for automated discovery of signatures optimized to characterize various cancer stages. We validate our signature discovery algorithm on one new colorectal cancer MALDI-TOF data set, and two well-known ovarian cancer SELDI-TOF data sets. In all of these cases, our signature based classifiers performed either better or at least as well as four benchmark machine learning algorithms including SVM and KNN. Moreover, our optimized signatures automatically select smaller sets of key biomarkers than the black-boxes generated by machine learning, and are much easier to interpret.
  • Nonlinear control and formal neural networks: Piecewise Affine Perceptrons.

    Charles albert LEHALLE, Robert AZENCOTT
    2005
    No summary available.
  • Multisignal neural classification and temporal distortions: application to the detection of driver vigilance.

    Bruno DURAND, Robert AZENCOTT
    2000
    The automatic detection of driver's vigilance decreases is considered from the signals describing the vehicle driving. As most of the phenomena that reflect a human intervention, temporal distortions distort these signals and mask the information sought. A first approach consists in temporally shifting the signals. A shift energy quantifies the effort required to realign two curves. The minimization of this energy is achieved by dynamic programming. A second approach consists in using a coding of the signals adapted to their nature. Based on a wavelet transform, this representation quantifies the size distribution of the oscillations at each scale. This coding is robust to temporal distortions and achieves a significant compression of the data. A family of primary vigilance classifiers is built: each classifier bases its decisions on the coding of a given signal at a given scale. The classification is established by an artificial neural network. The weights of the network are selected after scanning several architectures. A multi-sensor and multi-scale hypovigilance detection is finally built by optimal combination of the primary classifiers.
  • Neural network modeling: application to fuel management in a reactor.

    Fabrice GAUDIER, Robert AZENCOTT
    1999
    Every year, a quarter of the nuclear fuel in a reactor core is replaced by new fuel. Because of their history. The other fuels have very different physical properties. This raises the problem of how to distribute the fuel within the core while ensuring that the proposed loading plan meets safety constraints: this is the problem of fuel repositioning. If an exhaustive search is illusory, it requires the calculation of neutron characteristics, especially the power peak, for thousands of loading plans. In an automatic optimization code such as Formosa, the calculation of these characteristics represents 90% of the ten hours necessary for the optimization. In order to reduce this computation time, we propose an original neural architecture adapted to the physical phenomenon to model. A data analysis has allowed us to characterize the nuclear fuel more precisely. The introduction of an a priori knowledge of the neutron phenomena allowed to reduce the number of free parameters of the model. We then implemented this neural model in Formosa, and we showed a considerable time saving on real EDF problems. Finally, we also propose a hybrid method combining the best of the local linear approximator GPT (generalized perturbation theory) and neural networks.
  • Non-destructive testing by supervised analysis of 3D ultrasound images.

    Etienne GOUBET, Robert AZENCOTT
    1999
    The purpose of this thesis is to develop a processing chain to extract useful information from 3d ultrasonic data and to characterize any defects present in the inspected part. This characterization was approached for cracks controlled by the same transmitter/receiver. In a first part, we recall the principles of ultrasonic non-destructive testing as well as the classical representations of ultrasonic data. The second part is devoted to the study of a model of extraction of the echo information present on the data by means of an adapted wavelet base. The use of a single wavelet translated in time is made possible by working on a complex representation of the original real data. A first step allows to detect and position the echoes of significant amplitude. In a second step, a spatially consistent regularization of the detection times is performed using a Markovian model. This eliminates echoes whose detection times are not part of regular time surfaces. The following sections deal with the localization and sizing of cracks. Features extracted from the ultrasonic beam are used to determine the path of the ultrasonic wave from the sensor to the diffracting object when the echo response is maximum. The time of detection obtained for this echo is matched with the time of travel along the defined path to position an edge point in the part. We thus obtain a set of discretization points for each edge. In the framework of 3d data obtained on an isotropic material, the extreme edge points are eliminated by using a comparison criterion on the echodynamic curves associated with the detection points on real data and on equivalent simulated data. Localization is discussed for cracks located in an isotropic material or anisotropic coated steel.
  • Stochastic modeling and handwritten letter recognition.

    Eric L HOMER, Robert AZENCOTT
    1998
    Among the numerous handwritten letter recognition methods proposed in the last few years, a very limited number of them use or propose a modelization able to simulate the handwriting. This rarity is due to the difficulty to estimate, from a letter image, the trace of the strokes that compose it, because of many crossings and overlaps, trace from which an efficient modeling is possible. In this work, an algorithm for estimating the trajectories of features is described, based on a statistical study and a modeling of the crossings of features. Each letter is then characterized by a graph of curves. A stochastic modeling of this graph, using a mixture of Gaussian laws, is estimated by an em-type algorithm, on a large standard database. A recognition algorithm, based on this modeling, is described. For each letter image and for each letter class, an estimator of the curve graph is computed. A pre-estimation of this graph, using a regression on global characteristics of the letters, whose parameters have been estimated from simulation of letters, allows to obtain this estimator quickly. The identification of the class of the letter is obtained by a test on the likelihood of the graphs of curves. The results obtained allow to consider an extension of the model to handwritten words.
  • Modeling test results: evaluation of adaptive methodologies.

    Anne sophie TAILLANDIER MICHEL, Robert AZENCOTT
    1998
    This thesis is composed of three parts: discriminant analysis, regression by revealing directions (also known as projection pursuit regression) and neural networks. In discriminant analysis, we are interested in the assignment of a new individual, assuming that the different classes of the response are known. Gaussian assumptions are adopted in the problem, the assignment criterion is based on the maximum likelihood. It is optimal if the means and the covariance matrices are known. The covariance matrices are unknown, the assignment indicator is computed by taking their estimates on the samples of the different populations. Our approach is to help a user to choose between linear (equal covariance matrices) and quadratic (distinct covariance matrices) methodologies from the starting data at his disposal. Expressions for the error majorants of the assignment are given in the thesis. In regression by revealing directions, we first evaluated existing methods such as that of j. Friedman and w. Stuetzle and P. Hall for practical situations likely to be encountered in an industrial domain. We propose a new version of the regression by revealing directions, whose procedure is automated. Finally, we are interested in neural methods for the approximation of unknown functions. The neural networks used are very simple, as is the learning algorithm. The approach adopted was to separate the domain of variation of the input variables but also of the output variable. This separation is much more natural for a non-statistician user of statistics, it allows to improve very clearly the results. This is illustrated in a practical case treated in this part.
  • Tomographic reconstruction from a small number of views.

    Jean michel LAGRANGE, Robert AZENCOTT
    1998
    This thesis is devoted to the tomographic reconstruction of a 3d object from a small number of views, under symmetry assumptions. As classical inversions are very unstable, I approached this problem by modeling the object: the reconstruction consists in determining the parameters of the model by comparing the projections of the latter to the data. The illumination being parallel, I first studied the reconstruction of a plane section. The 1d model is then described by zones and has n parameters. The search for these parameters is expressed as the minimization of a quadratic criterion under constraints. As the latter is not differentiable, I have proposed three techniques to regularize it. I then studied the sensitivity of the parameterized vector to the noise present on the data after having determined the covariance matrix of this vector. I finally proposed a reconstruction of all the slices of the object by iteration of this 1d approach by adding a smoothing term between the slices. I then turned to the construction of a 3d model of the objects, characterized by six quantities: three separating surfaces (generated by the rotation of three plane curves) and the density fields on these interfaces. The first difficulty was to fill a 3d field from the density fields on the interfaces. I then proposed an adaptive elliptic operator to perform this operation. With fixed interfaces, I implemented the search for densities on each of them. I then formalized the deformation of these surfaces, i.e. of the plane generators. It is characterized by the search for an optimal base of deformations obtained by PCA on a set of examples. This set is constructed in a random way: the realizations are obtained by integration of the solution of a linear stochastic differential equation.
  • Elements for formalizing active recognition: application to three-dimensional vision.

    Stephane HERBIN, Robert AZENCOTT
    1997
    The usual recognition model proposed in the literature is the matching model. It consists in a matching of a sensory form data and an object model stored in memory. It implicitly distinguishes a perceptual level, source of representations able to universally substitute for the original signal, from a cognitive level, likely to use them to produce inferences. However, immediate perception rarely reveals all the information useful for object recognition. The conditions of observation are often ambiguous and the perceptual systems themselves are limited in their sensitivity. To be able to apprehend complex situations, object recognition requires an exploratory phase of search for useful information. The central work presented in this thesis consisted in proposing a general model that takes into account an authentic recognition activity. This model has been applied to a three-dimensional object recognition problem. The typical framework is that of an agent equipped with a camera, able to dynamically produce new sensory acquisitions by modifying its point of view or the parameters of its own perceptual system. The silhouette of the object, and the associated structure of its salient points, is considered as a priori discriminating data. The theory of aspect graphs, inspired by the theory of singularities of differentiable applications, then ensures that the sequence of data will be characteristic of the observed object. By providing it with a probabilistic Markovian structure, the aspect graph gains a quantifiable predictive capacity that can be exploited mathematically. The asymptotic theory of hypothesis testing, in its relation to large deviations techniques, then provides tools for a global quantitative characterization of the complexity of the problem.
  • Elastic comparison of curves using distances built on stichastic and deterministic models.

    Michel BENARD, Robert AZENCOTT
    1997
    This thesis deals with curve comparison in image processing. In the first part, we build a distance from a stochastic deformation model of a curve closed by random similarities. We study the displacement between the initial curve and the deformed curve. Starting from a discrete curve model, we establish the continuous limit model, which is identified with a stochastic diffusion, solution of a stochastic differential equation. In the demonstration we highlight the relevant types of similarity variances. We give a method for simulating the random displacement, and then argue for a modification of the displacement to have displacements with zero barycenter. These modified displacements are no longer diffusions. We then use a large deviation inequality to deduce from this type of displacement a distance between curves. We then show that by choosing a particular variance function, we find a distance between curves already used in image processing, although found according to other premises, thus bridging the gap between purely deterministic methods and a stochastic method. In the second part, we start from an already established distance and show the need for a multiscale algorithm for the computation of optimal parameters. We describe methods to speed up the minimization process, and provide a criterion for deciding whether or not to use a multi-resolution analysis. Application examples are given.
  • Multiscale recognition of objects in scenes.

    Jose PAUMARD, Robert AZENCOTT
    1996
    In this thesis, we study the possibility of recognizing objects in compressed images, without reconstructing them. The most suitable compression algorithm seems to be the one based on the extraction of multi-scale staggered contours from images. The recognition problem leads us to introduce a new tool for binary image comparison: the censored Hausdorff distance. This tool has proven to be robust and fast to compute. These two points are carefully studied. This distance is finally used to recognize and localize specific objects in large scenes. We propose three multiscale approaches to solve this problem, which take into account the fact that the desired object may be partially hidden, or that it may be seen from a different angle than its model. The algorithm we have developed is fast on a classical workstation. Its robustness has been carefully studied. Its parallelization allows us to reach real time in a reasonable operational framework.
  • Stochastic optimization. Choice of perturbation laws. Application to the itineris network.

    Francois DREYFUSS, Robert AZENCOTT
    1995
    Both the stochastic gradient algorithm and the simulated annealing are perturbations of local descent algorithms. Our theoretical analysis of the unconstrained stochastic gradient with Gaussian and Cauchy perturbations shows that in both cases a correct decay of the parameters ensures an efficient exploration, with different application domains: the second variant is less precise but faster, and thus adapted to problems of moderate complexity. The second part of this paper illustrates this discussion with an application to the optimization of the itineris cellular telephone network: an implementation based on simulated annealing is compared with a variant where the exponentially decaying metropolis transition law is replaced by a slower decaying transition law.
  • Large deviations for slow learning processes with discontinuous statistics on a surface.

    Isabelle NAGOT, Robert AZENCOTT
    1995
    We establish the principle of large deviations for markov chains whose transition probabilities are different depending on whether the process is on one side or the other of a surface. The large deviations are then observed over a fixed time interval for the properly normalized process. On each probability field, we make the continuity assumptions that usually allow us to obtain the large deviations principle. This continuity is lost on the boundary. Such dynamics are used in many stochastic algorithms, in particular in some learning algorithms for neural networks. Depending on the configuration of the supports of the measurements in the vicinity of the boundary, two types of behavior are possible for the process. In one, the number of border crossings is not bounded. A new cost function appears, combining the Cramer transforms of each field. It corresponds to the mixture of the two fields. The action functional is computed only on the paths for which there is a finite number of intervals where they remain either in one of the two half-spaces or on the border. In the other type of behavior, the process locally crosses the boundary at most once. The cost functional is obtained by integrating successively each cramer transform. In the last chapter, we give the equations verified by a minimum cost trajectory between two points. Their solution can be used for accelerated simulations of rare events.
  • Multiscale Markovian fields: applications to textured image segmentation and multi-film fusion.

    Jiaping WANG, Robert AZENCOTT
    1994
    This thesis is composed of two independent parts. The first part deals with texture representation and segmentation of textured images. We use Gaussian modeling and Gabor filters to characterize the textures. By our analysis, we see that, from a stochastic point of view, the characterization by gabor filters and the one by gaussian modelizations are comparable in the sense of random fields, although their motivations are very different. We present a method for the segmentation of multiscale unsupervised textured images, using partitions by related regions. We use Markov field methods to segment images, which by relaxation, tend to group points with similar texture characteristics. Our method progressively limits the domain of exploration of segmentations in the natural progression of the multiscale algorithm. The second part of this thesis deals with the fusion of a series of images (x-rays) obtained from distinct films in order to restore the 2d image of an object. This requires the estimation of the transfer function allowing to pass from one film to another. This task is made difficult by the presence of spatial inhomogeneity. We propose a method to estimate the transfer function between two films of different sensitivities and non-homogeneity. We consider that the image of the object is a realization of a Markov field whose a priori energy is built on the fact that the image verifies some regularization constraints. The restoration is then done by likelihood maximization.
  • Markovian fields and variational methods applied to low-level vision tasks.

    Francois COLDEFY, Robert AZENCOTT
    1993
    In many situations, image processing comes down to the translation of a given problem in the form of an energy minimization. The main difficulty then lies in the quality of this translation, i.e. in the construction of an energy whose minimum represents the information that we wish to extract or reconstruct. This thesis presents two different approaches to this problem, depending on whether we place ourselves in the probabilistic framework of Markov fields or in the deterministic framework of variational calculus. The first part deals with the detection of valley lines on a pair of noisy images degraded by a strong luminosity gradient. The valley background lines are represented by their discrete version and modeled by a Markov field. The bayes-markov approach leads to minimize an energy composed of two terms. The first one represents the a priori model on the discrete curves and integrates the regularity (low curvature) and length constraints. The second one is deduced from the noise model and is controlled by a parameter defining the minimal signal-to-noise ratio from which a detection is performed on the pair of recalibrated images. This energy is minimized by a stochastic algorithm of type mpm. The second part concerns the automatic reconstruction of the silhouette of an object placed on a noisy homogeneous background. The framework used is that of snakes, a method derived from variational computing. The contour is obtained by minimizing an energy by means of a deterministic gradient algorithm using several levels of resolution. Finally, this work also presents a study on the Lambertian illumination model. We propose a semi-local approach to estimate the reflectance and local orientation of objects when the direction of the incident light is unknown.
  • Examples of the use of Markovian fields in explanatory modeling.

    Anne RICORDEAU, Robert AZENCOTT
    1993
    Markov fields have undergone significant development in applied research, mainly because they are suitable for the study of spatial phenomena such as image analysis. But outside this framework, Markovian models have been little exploited. This work deals with their use in explanatory modeling, in an economic context for example. The different tools related to model fitting are detailed in the first chapter. The possibilities of Markovian fields in explanatory modeling are then explored through two studies for which real data are available. The first study deals with the modeling of a field, not structured a priori, of binary variables influenced by explanatory variables. A search and adjustment module adapted to the model is developed, then applied to data provided by the Renault company, data representative of the quality control of an assembly line. The second study concerns the modeling of multivariate series with integer values by self-poissonian fields. This modelization is an alternative to the arma modelization for data with non-Gaussian characteristics. Prediction methods adapted to this Poissonian model are proposed, and their performances are compared on simulations. An application, realized for the Ministry of Transport and dealing with the modeling of a bivariate set of road safety indicators, is then presented in detail.
  • Massive parallelization of simulated annealing.

    Alain TROUVE, Robert AZENCOTT
    1993
    We will start with the generalization to potential-free annealing of some results of large deviations of olivier catoni and we will establish the expression of the optimal exponent for triangular sequences of temperature patterns depending on the horizon. We give an algorithm for computing the critical constants through an effective decomposition according to the wentzell and freidlin cycles. We then consider massively parallel forms of simulated annealing for spaces of configurations defined by a family of labels indexed by a finite set of sites. After giving a general framework of massively parallel annealing, we develop fixed rate parallelization where at each iteration a site can be frozen with a fixed probability. We will focus on the role of the parallelization rate and the neighborhood structure in the low temperature behavior of the algorithm and in the efficiency of the parallelization. We will also show the singularity of the totally parallel algorithm. Finally, we will study a form of parallelization of simulated annealing where we dynamically control the simultaneous renewals of neighboring sites. We will show for this last algorithm the convergence to global minima and we will conduct a numerical comparison with the parallel annealing by classical coding.
  • Segmentation algorithms, Markovian fields and parallelism.

    Christophe LABOURDETTE, Robert AZENCOTT
    1992
    This thesis deals with the parallelization of image segmentation algorithms, based on Markovian models. After a brief review of Markovian field techniques, we present transputer networks and more particularly the t-node, as well as its distributed operating system helios. With the help of some experiments, we show that we can predict the execution time of some algorithms on t-node machines. We then present two algorithms: the first one is a segmentation of textured images, the second one is an augmentation of multispectral images, each followed by its parallel version implemented on the t-node. The last part discusses in detail a color image segmentation algorithm, intrinsically parallel. The parallelisation possibilities of such an algorithm are discussed, but not implemented for material reasons, the t-node not being a suitable machine. This algorithm builds locally, on overlapping images, segmentations that are made to cooperate in order to obtain a global segmentation. The global coherence is done by processing a graph of labels.
  • Machines de boltzmann. Theorie et applications.

    Jerome LACAILLE, Robert AZENCOTT
    1992
    This paper presents the boltzmann machines in three main parts. First, the formalism and the algorithmic of these machines are detailed from a theoretical point of view. Emphasis will be put on parallel and asymmetric architectures. An application of this type of network is presented in a second time. It is an edge detector on gray level photographs. The last part describes a software implementation of asymmetric synchronous boltzmann machines. We propose a simulator and an interpreter with a user manual. This last part is designed in a didactic way since each step is illustrated by computer examples.
  • Connectionist models applied to image compression and self-organization of the mammalian visual system.

    Mathilde MOUGEOT, Robert AZENCOTT
    1992
    The gradient backpropagation algorithm has been used to compress images on multi-layer autoassociation networks. The solution obtained by the network after learning is realized in a very different way than the classical methods. A theoretical study on the convexity of the solution space allowed to improve the convergence speed of the network by imposing constraints on the synaptic weights. In order to improve the visual results of image compression, we introduced, in the backpropagation algorithm, the minimization of the holder norms. This algorithm has proven to be a very efficient tool and brings new solutions to the image compression problem. Our second task was to study and generalize a self-organization model to explain the formation and organization of cells characteristic of the mammalian visual system during the prenatal and postnatal periods. We propose a statistical model to study postnatal evolution. We propose a statistical model to study the postnatal evolution of the orientation columns of layer iv of the visual cortex by simulating the first visual experiences of the animal on the retina after birth (darkness, biased environments, normal visual environments). Our model takes into account recent neurobiological observations on the development of intra-cortical connections. Our simulations recover the neurobiological results showing the existence of excitatory intracortical connections between selective cells at the same orientations, and belonging to different hypercolumns.
  • Markov fields and contour matching in imaging.

    Isabelle TROUVE GAUDRON, Robert AZENCOTT
    1992
    This thesis has for central theme the pattern recognition in image analysis. It is composed of three independent parts. A contour detection algorithm developed with olivier catoni is presented in the first part. We build by smoothing and thresholding binary images whose edges contain the contour points. We regularize them with a gibbs sampler, which gives us smooth contours. The algorithm operates at different scales, which we combine to obtain a multi-scale detector. The problem that we deal with in the second part is to recognize and position on a digital image given manufactured objects. The objects present on the image are the transforms of objects modeled by any similarity. It is thus a question of associating each object present on the image with the good model and of estimating this similarity. Each object is represented by a value graph. Any geometrical correspondence between two objects is translated into a correspondence between graphs that must satisfy some local constraints. We place ourselves in a Markovian context to determine a graph matching that best satisfies these constraints. The third part presents a study carried out with alain trouve on the parallelization of simulated annealing for spin glass energies. Each spin is linked to a processor. At each step, each processor is active with a probability p and all active processors renew their spin values simultaneously. We show that if all the processors are active, there is no convergence towards the global minima of the energy. As soon as p is strictly less than 1, there seems to be convergence towards energy configurations close to the minimum energy. Finally, we compute an effective time saving of the partially parallel annealing compared to the sequential annealing.
  • Some mathematical aspects of neural self-organization and multilayer perceptrons.

    Claire DEVOUGE, Robert AZENCOTT
    1992
    This thesis is devoted to the mathematical study of two types of neural networks and is composed of two distinct parts. The first part focuses on the multilayer perceptron, and more particularly on the problems of convexity of the error function. We show that weak conditions are sufficient to ensure convexity for all perceptrons without hidden layers, while convexity becomes impossible for perceptrons with one or more hidden layers, even taking into account the group of geometric transformations that leave the error invariant. We then propose a new learning algorithm using the information obtained and which we have tested on the classical problem of print recognition. The second part is based on the work of r. Linsker on vision. This researcher has proposed, since 1986, a rather simple model (based on a hebbian learning rule) which allows to explain the emergence of orientation selective cells in prenatal vision. We propose a mathematical study of this model. The operator that defines the time evolution of cortical connections depends on two real parameters and is diagonalizable in an orthonormal basis of eigenfunctions. We show that, depending on the value of these parameters, these eigenfunctions are, after renormalization, either hermits functions in two variables or sums of these hermits functions. In order to determine the asymptotic behavior of the synaptic weight function, we then study the relative position of the eigenvalues according to the parameters. This allows us, finally, to derive explicit conditions to force such or such mode (symmetric or not) to become preponderant in time.
  • Galton-Watson process depending on the population size*.

    Daniel PIERRE LOTI VIAUD, Robert AZENCOTT
    1990
    To study the generalization of Galton-Watson processes to the case where the reproduction laws depend on the population size we consider different families of such processes indexed by the initial population size. When the initial population size increases towards infinity we show results of the law of large numbers, central limit theorem and principle of large deviations. We discuss the generalization of our results for spatial Galton-Watson processes.
  • Asymptotic study of simulated annealing algorithms.

    Olivier CATONI, Robert AZENCOTT
    1990
    Simulated annealing algorithms are an approach to optimization where the state space is explored by an inhomogeneous markov chain. We study the dynamics of metropolis on a finite space by large deviation methods. A decomposition of the space into cycles, following wentzell and freidlin, leads to estimate the law of time and of the entry point in a set for the trajectories remaining in another given set. The proof, by recurrence, establishes that the estimates are conserved by composition of the laws by tensor inner product. Applications follow: a complement to hajek's theorem on the necessary and sufficient conditions for convergence, an upper bound for the speed of convergence, estimates of the law of the system for different temperature sequences. We show that the optimal temperature sequence in the far finite horizon decreases as the inverse of the logarithm in its first part, but in general not in its part near the horizon. On the other hand, we obtain an asymptotically optimal convergence rate in the sense of logarithmic equivalents with geometric temperature sequences whose rate is suitably adapted to the horizon.
Affiliations are detected from the signatures of publications identified in scanR. An author can therefore appear to be affiliated with several structures or supervisors according to these signatures. The dates displayed correspond only to the dates of the publications found. For more information, see https://scanr.enseignementsup-recherche.gouv.fr