**Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?**

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Concept# Variable-order Markov model

Résumé

In the mathematical theory of stochastic processes, variable-order Markov (VOM) models are an important class of models that extend the well known Markov chain models. In contrast to the Markov chain models, where each random variable in a sequence with a Markov property depends on a fixed number of random variables, in VOM models this number of conditioning random variables may vary based on the specific observed realization.
This realization sequence is often called the context; therefore the VOM models are also called context trees. VOM models are nicely rendered by colorized probabilistic suffix trees (PST). The flexibility in the number of conditioning random variables turns out to be of real advantage for many applications, such as statistical analysis, classification and prediction.
Example
Consider for example a sequence of random variables, each of which takes a value from the ternary alphabet . Specifically, consider the string constructed from infinite concatena

Source officielle

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés

Chargement

Cours associés

Chargement

Séances de cours associées

Chargement

Publications associées (9)

Personnes associées (3)

Chargement

Chargement

Chargement

Cours associés (1)

The study of random walks finds many applications in computer science and communications. The goal of the course is to get familiar with the theory of random walks, and to get an overview of some applications of this theory to problems of interest in communications, computer and network science.

Unités associées (2)

Concepts associés (2)

Séances de cours associées (1)

Chaîne de Markov

vignette|Exemple élémentaire de chaîne de Markov, à deux états A et E. Les flèches indiquent les probabilités de transition d'un état à un autre.
En mathématiques, une chaîne de Markov est un process

Propriété de Markov

vignette|Exemple de processus stochastique vérifiant la propriété de Markov: un mouvement Brownien (ici représenté en 3D) d'une particule dont la position à un instant t+1 ne dépend que de la position

Boi Faltings, Stéphane Bernard Martin, Vincent Schickel

Recommender systems typically determine the items they should recommend by learning models of user-preferences. Most often, those preferences are modeled as static and independent of context. In real life however, users consider items in sequence: TV series are watched episode by episode and accessories are chosen after the main appliance. Unfortunately, since sequences are more complex to model, they are often not taken into account. We developed an efficient sequence-modeling approach based on Bayesian Variable-order Markov Models and combined it with an existing content-based system, the Ontology Filtering. We tested this approach through live evaluations on two e-commerce sites. It dramatically increased performance, more than doubling the CTR and strongly increasing recommendation-mediated sales. These tests also confirm that the technique works efficiently and reliably in a production setting.

Boi Faltings, Stéphane Bernard Martin, Vincent Schickel

We describe the selection, implementation and online evaluation of two e-commerce recommender systems developed with our partner company, Prediggo. The first one is based on the novel method of Bayesian Variable-order Markov Modeling (BVMM). The second, SSAGD, is a novel variant of the Matrix-Factorization technique (MF), which is considered state-of-the-art in the recommender literature. We discuss the offline tests we carried out to select the best MF variant, and present the results of two A/B tests performed on live ecommerce websites after the deployment of the new algorithms. Comparing the new recommenders and Prediggo’s proprietary algorithm of Ontology Filtering, we show that the BVMM significantly outperforms the two others in terms of CTR and prediction speed, and leads to a strong increase in recommendation-mediated sales. Although MF exhibits reasonably good accuracy, the BVMM is still significantly more accurate and avoids the high memory requirements of MF. This scalability is essential for its application in online businesses.

, ,

Recommender systems typically determine the items they should recommend by learning models of user-preferences. Most often, those preferences are modeled as static and independent of context. In real life however, users consider items in sequence: TV series are watched episode by episode and accessories are chosen after the main appliance. Unfortunately, since sequences are more complex to model, they are often not taken into account. We developed an efficient sequence-modeling approach based on Bayesian Variable-order Markov Models and combined it with an existing content-based system, the Ontology Filtering. We tested this approach through live evaluations on two e-commerce sites. It dramatically increased performance, more than doubling the CTR and strongly increasing recommendation-mediated sales. These tests also confirm that the technique works efficiently and reliably in a production setting.