Markov models have been a keystone in Artificial Intelligence for many decades. However, they remain unsatisfactory when the environment modeled is partially observable. There are pathological examples where no history of fixed length is sufficient for accurate deci- sion making. On the other hand, working with a hidden state (such as in POMDPs) has a high computational cost. In order to circumvent this problem, I suggest the use of a context- based model. My approach replaces strict transition probabilities by a linear approximation of probability distributions. The method proposed provides a trade-off between a fully and partially observable model. I also discuss improving the approximation by constructing history-based features. Simple examples are given in order to show that the linear approx- imation can behave like certain Markov models. Empirical results on feature construction are also given to illustrate the power of the approach. / Depuis plusieurs déecennies, les modèeles de Markov forment l'une des bases de l'Intelligence Artificielle. Lorsque l'environnement modélisé n'est que partiellement observable, cepen- dant, ceux-ci demeurent insatisfaisants. Il est connu que la prise de décision optimale dans certains problèmes exige un historique infini. D'un autre côté, faire appel au con- cept d'état caché (tel qu'à travers l'utilisation de POMDPs) implique un coût computa- tionnel plus élevé. Afin de pallier à ce problème, je propose un modèle se servant une représentation concise de l'historique. Plutôt que de stocker un modèle parfait des prob- abilitités de transition, mon approche emploie d'une approximation linéaire des distribu- tions de probabilités. La méthode proposée est un compromis entre les modèles partielle- ment et complètement observables. Je traite aussi de la construction d'éléments en lien avec l'historique afin d'améliorer l'approximation linéaire. Des exemples restreints sont présentés afin de montrer qu'une approximation linéaire de certains modèles de Markov peut être atteinte. Des résultats empiriques au niveau de la construction d'éléments sont aussi présentés afin d'illustrer les bénéfices de mon approche.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.18471 |
| Date | January 2007 |
| Creators | Gendron-Bellemare, Marc |
| Contributors | Doina Precup (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (School of Computer Science) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0027 seconds