This research is an effort to improve the performance of successive approximation algorithm with a prime aim of solving finite states and actions, infinite horizon, stationary, discrete and discounted Markov Decision Processes (MDPs). Successive approximation is a simple and commonly used method to solve MDPs. Successive approximation often appears to be intractable for solving large scale MDPs due to its computational complexity. Action elimination, one of the techniques used to accelerate solving MDPs, reduces the problem size through identifying and eliminating sub-optimal actions. In some cases successive approximation is terminated when all actions but one per state are eliminated. The bounds on value functions are the key element in action elimination. New terms (action gain, action relative gain and action cumulative relative gain) were introduced to construct tighter bounds on the value functions and to propose an improved action elimination algorithm. When span semi-norm is used, we show numerically that the actual convergence of successive approximation is faster than the known theoretical rate. The absence of easy-to-compute bounds on the actual convergence rate motivated the current research to try a heuristic action elimination algorithm. The heuristic utilizes an estimated convergence rate in the span semi-norm to speed up action elimination. The algorithm demonstrated exceptional performance in terms of solution optimality and savings in computational time. Certain types of structured Markov processes are known to have monotone optimal policy. Two special action elimination algorithms are proposed in this research to accelerate successive approximation for these types of MDPs. The first algorithm uses the state space partitioning and prioritize iterate values updating in a way that maximizes temporary elimination of sub-optimal actions based on the policy monotonicity. The second algorithm is an improved version that includes permanent action elimination to improve the performance of the algorithm. The performance of the proposed algorithms are assessed and compared to that of other algorithms. The proposed algorithms demonstrated outstanding performance in terms of number of iterations and omputational time to converge.

In this thesis, we use martingales to show that the dilation of a sequence of monotone convolutions $D_\frac{1}{b_n} (\mu_1 \triangleright \mu_2 \triangleright \cdots \triangleright \mu_n)$ is stable, where $\mu_j$ are probability distributions with the condition $\sum \limits_{n=1}^\infty \frac{1}{b_n} \text{var}(\mu_n) < \infty$. This proves a law of large numbers for monotonically independent random variables.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Dans la première partie de cette thèse, on donne, sous certaines hypothèses, une minoration du nombre de points d’intersections d’une sous-variété Lagrangienne monotone L avec son image par une isotopie Hamiltonienne. Dans le cas où L est un espace K(pi, 1), et en particulier à courbure sectionnelle strictement négative, le minorant est 1 + beta1(L), où beta1 est le premier nombre de Betti à coefficients dans Z2. Une autre conséquence est la non-déplaçabilité d’un plongement Lagrangien monotone de RPn × K (où K est une sous-variété à courbure sectionnelle strictement négative telle que H1(K, Z) ≠ 0) dans certaines variétés symplectiques. Dans la seconde partie, on considère une sous-variété Lagrangienne monotone L non déplaçable. En utilisant l’homologie de Floer définie pour les Lagrangiennes qui sont C-1-proches de L, on obtient des informations sur son nombre de Maslov. De plus, si L peut être approchée par une suite de Lagrangiennes déplaçables, alors, sous certaines hypothèses topologiques sur L, l’énergie de déplacement des éléments de cette suite tend vers l’infini. / N the first part of the thesis, we give, under some hypotheses, a lower bound on the intersection number of a closed monotone Lagrangian submanifold L with its image by a generic Hamiltonianisotopy. For monotone Lagrangian submanifolds L which are K(pi, 1) and, in particular with negative sectional curvature, this bound is 1 + beta_1(L), where beta_1 is the first Betti number with coefficients in Z_2. Another consequence, is the non-displaceability of a monotone Lagrangian embedding of RPn x K (where K is a submanifold with negative sectional curvature such that H^1(K, Z) ≠ 0) in some symplectic manifolds. In the second part, given a closed monotone Lagrangian submanifold L, which is not displaceable, we use Floer homology defined on Lagrangians which are C^1 - close to L, to get information about it Maslov number. Besides, if L can be approached by a sequence of displaceable Lagrangians, then, under some topological assumptions on L, the displacement energy of the elements of this sequence converge to infinity.

Monotone function, such as growth function and cumulative distribution function, is often a study of interest in statistical literature. In this dissertation, we propose a nonparametric least-squares method for estimating monotone functions induced from stochastic processes in which the starting time of the process is subject to interval censoring. We apply this method to estimate the mean function of tumor growth with the data from either animal experiments or tumor screening programs to investigate tumor progression. In this type of application, the tumor onset time is observed within an interval. The proposed method can also be used to estimate the cumulative distribution function of the elapsed time between two related events in human immunodeficiency virus (HIV)/acquired immunodeficiency syndrome (AIDS) studies, such as HIV transmission time between two partners and AIDS incubation time from HIV infection to AIDS onset. In these applications, both the initial event and the subsequent event are only known to occur within some intervals. Such data are called doubly interval-censored data. The common property of these stochastic processes is that the starting time of the process is subject to interval censoring. A unified two-step nonparametric estimation procedure is proposed for these problems. In the first step of this method, the nonparametric maximum likelihood estimate (NPMLE) of the cumulative distribution function for the starting time of the stochastic process is estimated with the framework of interval-censored data. In the second step, a specially designed least-squares objective function is constructed with the above NPMLE plugged in and the nonparametric least-squares estimate (NPLSE) of the mean function of tumor growth or the cumulative distribution function of the elapsed time is obtained by minimizing the aforementioned objective function. The theory of modern empirical process is applied to prove the consistency of the proposed NPLSE. Simulation studies are extensively carried out to provide numerical evidence for the validity of the NPLSE. The proposed estimation method is applied to two real scientific applications. For the first application, California Partners' Study, we estimate the distribution function of HIV transmission time between two partners. In the second application, the NPLSEs of the mean functions of tumor growth are estimated for tumors with different stages at diagnosis based on the data from a cancer surveillance program, the SEER program. An ad-hoc nonparametric statistic is designed to test the difference between two monotone functions under this context. In this dissertation, we also propose a numerical algorithm, the projected Newton-Raphson algorithm, to compute the non– and semi-parametric estimate for the M-estimation problems subject to linear equality or inequality constraints. By combining the Newton-Raphson algorithm and the dual method for strictly convex quadratic programming, the projected Newton-Raphson algorithm shows the desired convergence rate. Compared to the well-known iterative convex minorant algorithm, the projected Newton-Raphson algorithm achieves much quicker convergence when computing the non- and semi-parametric maximum likelihood estimate of panel count data.

Le raisonnement hypothétique consiste à compléter la connaissance<br />disponible afin de poursuivre un raisonnement. L'aide aux utilisateurs de systèmes de raisonnement hypothétique nécessite la conception d'algorithmes spécifiques, pour pouvoir gérer efficacement les hypothèses et leurs conséquences et pour permettre de poser automatiquement des hypothèses. Cette dernière exigence conduit à implémenter un raisonnement non monotone. Les systèmes de maintenance de la vérité enregistrent les inférences produites par un système de raisonnement sous forme d'un graphe de dépendances et se chargent de garantir la cohérence des formules présentes dans une base de connaissance. Deux types de systèmes de maintenance de la vérité ont été proposés:<br /><br />- Les systèmes à propagation acceptent des inférences non monotones et propagent la validité absolue au sein du graphe de dépendances. L'étiquetage obtenu représente une interprétation du graphe.<br /> <br />- Les systèmes à contextes n'acceptent que des inférences monotones mais propagent des étiquettes dénotant les contextes dans lesquels les formules doivent être présentes. Ils<br />permettent donc de raisonner sous plusieurs contextes<br />simultanément.<br />Le but de ce travail est de concevoir un système qui combine leurs<br />avantages. Il permet de raisonner simultanément sous plusieurs<br />contextes à l'aide d'inférences non monotones. Pour cela, des<br />environnements capables de tenir compte de l'absence d'hypothèses sont définis. Une interprétation est associée à ces environnements et est étendue aux noeuds du graphe de dépendances, en accord avec l'interprétation des systèmes à propagation. Cela permet d'établir la signification des étiquettes associées aux noeuds du graphe, et de proposer de multiples possibilités de soumettre des requêtes au systême. Un systême correspondant à cette caractérisation, le CP-TMS,<br />est implémenté comme une extension des systèmes de maintenance de la vérité à propagation. Cette implementation est décrite ici, puis critiquée.

Nous considérons l'estimation non-paramétrique d'une densité k-monotone définie sur (0,∞), pour un entier k > 0 donné, via les méthodes de maximum de vraisemblance et des moindres carrés qu'on note respectivement par MLE et LSE.<br /><br />Dans l'introduction, nous présentons tout d'abord la motivation principale derrière ce problème et nous faisons l'effort d'inclure dans le cadre général de notre travail les résultats asymptotiques qui étaient déjà établis pour les cas spéciaux k=1 et k=2.<br /> <br />Ensuite, nous nous penchons sur l'étude des propriétés des MLE et LSE d'une densité k-monotone g_0 dans le cas où on dispose de n observations indépendantes générées de g_0. Notre étude asymptotique est locale, c'est-à-dire que nous nous intéressons uniquement aux propriétés asymptotiques des estimateurs et de leur dérivées à un point fixe, x_0. Sous certaines hypothèses que nous précisons, nous établissons d'abord les bornes inférieures minimax pour l'estimation des dérivées g^{(j)}_0(x_0), j=0,...,k-1. Les bornes obtenues indiquent que n^{-(k-j)/(2k+1)} est la vitesse de convergence optimale de n'importe quel estimateur non-paramétrique de g^{(j)}_0(x_0). Sous les mêmes hypothèses et si une certaine conjecture est vraie, nous démontrons que cette vitesse optimale est atteinte dans le cas des MLE et LSE.<br /><br />Pour compléter la théorie asymptotique des estimateurs et de leur dérivées au point x_0, nous passons à la dérivation de leurs distributions limites lorsque la taille de l'échantillon n tend vers l'infini. Il s'avère que ces distributions dépendent d'un processus stochastique bien particulier défini sur l'ensemble des réels R. On note ce processus par H_k Le 3ème chapitre est consacré essentiellement à l'existence et à l'unicité de H_k, ainsi qu'à sa caractérisation. Nous démontrons que si Y_k est la primitive (k-1)-ème d'un mouvement Brownien + k!/(2k)! t^{2k}, alors H_k reste au-dessus (au-dessous) de Y_k lorsque k est pair (impair). Un simple changement de variable suffit pour reconnaître que nos résultats comprennent les cas spéciaux k=1 et k=2 où le problème se réduit à l'estimation d'une densité décroissante et d'une densité décroissante et convexe respectivement. Pour ces cas-là, la théorie asymptotique des MLE et LES a été déjà établie.<br /><br />L'aspect algorithmique fait l'objet du 4ème chapitre. Les algorithmes de Splines itératifs (Iterative Spline algorithms) sont développés et implémentés afin de calculer les estimateurs et aussi pour obtenir une approximation du processus limite sur n'importe quel compact dans R. Ces algorithmes exploitent essentiellement la structure 'splineuse' des MLE, LSE et H_k, et se basent ainsi sur la suppression et l'addition itératives des noeuds de certains Splines aléatoires.

L'idée d'établir des relations entre des objets et de les représenter dans la base de connaissances d'un système informatique est le propre de toute approche en Intelligence Artificielle. Cependant, la plupart des formalismes de représentation de connaissances n'exploitent pas toute la richesse de la sémantique de ces relations, ni le comportement qui leur est associé. En recherche d'informations, les traitements de ces relations ne sont guère mieux élaborés et l'impact de leur prise en compte lors de la phase de correspondance n'a jamais été établi, même s'il reste vrai que de nombreuses approches tiennent compte de leur présence dans le document et tentent ainsi de les représenter lors du processus d'indexation. Pourtant la recherche de documents structurés ou complexes exige plus que jamais, outre un langage d'indexation robuste et expressif, la prise en charge de la sémantique des relations ainsi que leurs propriétés. À travers une étude des nouvelles exigences auxquelles la recherche d'informations d'aujourd'hui doit répondre, nous proposons un modèle d'indexation relationnel pour les documents. L'approche consiste à considérer qu'un terme d'indexation est fondé sur des concepts complexes où les connecteurs sémantiques sont vus comme des opérateurs, ou des relations permettant de construire des expressions nouvelles représentant des concepts nouveaux ou des situations nouvelles. Le modèle proposé ne se contente pas de représenter les relations, mais permet aussi d'offrir un cadre général précisant les principes généraux de manipulation de ces relations et la prise en compte de leurs propriétés dans un processus de recherche fondé sur une approche logique. Le modèle proposé comporte deux composantes: le langage de représentation des informations, permettant une approche d'indexation relationnelle, et les règles de dérivation qui, reprenant ce langage, permettent de diriger le processus de correspondance. Nous utilisons la théorie des situations comme langage de représentation et un système de dérivation de pertinence, reposant sur une axiomatisation de la notion de correspondance entre les documents et la requête pour la prise en compte des relations. Une caractéristique intéressante de ce modèle est qu'il conduit à étendre certains formalismes de représentation de connaissances par des notions utiles en recherche d'informations. Les limitations de la famille des logiques terminologiques, utilisée par ailleurs comme base formelle de l'approche d'indexation relationnelle proposée, peuvent ainsi être surmontées. Cependant, la complexité des traitements associés à cette famille de logiques empêche de les utiliser comme un modèle opérationnel. Nous proposons alors le formalisme des graphes conceptuels comme un bon compromis entre la complexité des démonstrateurs de théorèmes et la simplicité des approches algébriques. Ce formalisme est alors vu, à travers une interprétation logique adéquate, comme une implantation d'une logique terminologique étendue et du modèle d'indexation. Notre approche a été implantée sur une plate-forme de gestion de graphes conceptuels, réalisée sur le système de gestion de base de données à objets O2. Le prototype RELIEF résultant de notre expérimentation a été testé sur une collection d'images et a démontré l'applicabilité et le bien-fondé de notre approche.

Lorsqu'une base de connaissance est construite de manière incrémentale, le dernier ajout peut être contradictoire avec le contenu de la base. Or, l'objectif d'une base de connaissance est de modéliser un domaine et elle doit donc être consistante, c'est-à-dire admettre au moins un modèle. Pour ajouter une connaissance inconsistante avec la base, il faut donc modifier celle-ci afin de préserver sa consistance. Cette problématique se rapproche de celle de la révision dans les langages logiques, dont le principal inconvénient est la complexité qui ne permet pas l'implémentation. L'objectif est de définir une révision, dans le cadre des représentations de connaissance par objets, qui puisse être implémentée, notamment en tenant compte des particularités des langages de représentation par objets. Dans un premier temps, nous définissons formellement un langage d'objets : sa sémantique et un système déductif syntaxique correct et complet par rapport à la sémantique. De plus, nous définissons syntaxiquement l'inconsistance, ce qui permet de la détecter en se basant sur les propriétés de localité du langage. Contrairement aux langages logiques classiques, une inconsistance ne permet pas de tout déduire et reste donc localisée. Dans un second temps, nous définissons les bases révisées qui satisfont les postulats classiques de la révision, en particulier la minimalité, principe selon lequel il faut perdre le moins possible de connaissance. La minimalité peut s'interpréter intuitivement selon la relation d'ordre entre les classes. Cependant, elle est basée sur l'inclusion ensembliste et n'est pas un critère suffisant pour obtenir une unique base. Un algorithme, qui a été implémenté, propose donc toutes les bases révisées minimales suite à un ajout inconsistant ; il est interactif afin de maîtriser la complexité inhérente à la révision.

We formalize and analyze the notions of monotonicity and complete monotonicity for Markov Chains in continuous-time, taking values in a finite partially ordered set. Similarly to what happens in discrete-time, the two notions are not equivalent. However, we show that there are partially ordered sets for which monotonicity and complete monotonicity coincide in continuoustime but not in discrete-time.