Apprentissage de représentation pour la prédiction et la classification de séries temporelles

Données de transport et données séquentielles

Les dernières années ont été marquées par l’explosion de la quantité de données temporelles dans différents domaines tels que la météorologie, la biologie, le trafic automobile et la finance entre autres. Les données sont produites sous la forme de séries temporelles qui sont le plus souvent multi-variées et qui exhibent des dépendances spatio-temporelles. Celà est spécialement vrai dans le domaine du transport où le développement des ITS (Intelligent Transportation System) qui nécessite la collecte d’informations sur le trafic et l’infrastructure routière en temps réel est en pleine expansion. Depuis plusieurs années, dans le but d’améliorer les conditions et la fluidité du trafic routier, les méthodes de collecte de données ont considérablement évolué et l’accès aux informations de trafic en temps réel est devenu courant. Les capteurs statiques (caméras, boucles magnétiques) et mobiles (GPS embarqués dans les véhicules ou les smartphones) capturent en temps réel l’évolution de l’activité urbaine.

L’usage des capteurs traditionnellement installés directement dans la chaussée (e.g. boucles magnétiques, pneumatiques) pour collecter des données est toujours nécessaire mais pas suffisant étant données les limitations inhérentes à ces méthodes : couverture partielle d’un réseau routier, forts coûts d’installation et de maintenance. Récemment, on a pu observer l’émergence de sources de données alternatives. C’est par exemple le cas pour des méthodes basées sur la position du véhicule; les FCD (Floatting Car Data; véhicules équipés de GPS) en particulier sont considérés comme la solution la plus à même de pallier les limitations des capteurs fixes et à un moindre coût. La croissance importante de cette famille de collecte de données est liée non seulement au fait qu’une demande importante des utilisateurs aujourd’hui est d’avoir des services leur permettant d’avoir des informations pertinentes sur l’état des réseaux de transport, mais aussi aux perspectives atteignables grâce aux informations précises et en temps réel : la prédiction de l’évolution du trafic et des congestions, la détection automatique d’évènements routiers en temps réel, l’évaluation de la durée des futures congestions, la prédiction d’évènements routiers… Ces questions requièrent que les données soient au maximum précises, fiables et complètes. Celà soulève plusieurs difficultés : les capteurs peuvent couvrir une zone spatiale importante ce qui mène à une grande quantité de séries observées à prédire, et cela durant une période de temps qui peut être longue. Une autre caractéristique de ces données réside dans leur incomplétude: les capteurs mobiles en particulier fournissent de l’information sur une partie du réseau étudié qui varie dans le temps et les données produites sont par nature partielle. Une autre difficulté inhérente aux données spatio-temporelles est la prise en compte de leur particularité structurelle : les séries temporelles étudiées sont corrélées les unes aux autres selon des relations spatiales qui peuvent être complexes.

Les données collectées peuvent être utilisées pour prédire l’évolution future des phénomènes mesurés : la prédiction de trafic est un problème qui a focalisé l’attention de la communauté scientifique depuis longtemps. Depuis les premiers travaux de recherche sur le sujet [3], un grand nombre de techniques ont été proposées, essentiellement basées sur de la prédiction de séries temporelles univariées, puis plus récemment sur de la prédiction multi-variée [108] [63]. Cependant, les méthodes développées ont très peu pris en compte l’aspect géographique des données et les dépendances spatiales que les séries temporelles pouvaient exhiber. Celà est spécialement vrai dans le cas de la prédiction de trafic, mais également pour les données spatio-temporelles collectées plus généralement dans des domaines comme la météorologie ou la médecine. Tandis qu’historiquement ces données étaient le plus souvent étudiées à travers des modèles issus de la physique statistique [34] et basés sur des lois a priori, les développements récents en machine learning permettent de proposer des méthodes pour extraire des modèles prédictifs prenant en compte les caractéristiques spatiales directement depuis les données. Ces méthodes ont par exemple récemment été appliquées au problème de la prédiction de trafic [5].

Séries temporelles 

Les séries temporelles constituent une part importante des données produites et disponibles sur Internet dans de très différents domaines. Par exemple, dans le seul domaine médical, l’information enregistrée par les électroencéphalogrammes ou par des électrocardiogrammes, les données qui représentent l’expression de gènes [2], les données sur la croissance d’un individu etc., sont des séries temporelles fréquemment traitées. Les séries temporelles se retrouvent de la même manière dans d’autres domaines tels que la finance, la météorologie, le son… Si depuis plus d’un siècle la communauté scientifique s’est penchée sur le traitement des séries temporelles [101], la disponibilité de grandes quantités de données est relativement récente et de nouveaux challenges s’offrent à elle. Les principaux axes d’études autour des séries temporelles qui ont été proposés dans la littérature sont les suivants :
— La prédiction : étant donnée une série temporelle X = x1, x2, …, xT contenant T points, il s’agit de prédire la ou les valeurs suivantes, c’est-à-dire les valeurs xt+1, xt+2, xt+3… [128, 23, 70, 112].
— La classification : étant donnée une série temporelles X, il s’agit de l’assigner à une des (deux ou plus) classes prédéfinies [61, 55, 129].
— La complétion : étant donnée une série temporelle X = x1, x2, …, xT contenant T points et un masque mi tel que mi = 1 si la valeur de xi est connue et mi = 0 sinon, il s’agit d’inférer la ou les valeurs manquantes, c’est-à-dire les valeurs pour lesquelles mi = 0 [118].
— L’indexation : étant donnée une série temporelle X ainsi qu’une mesure de similarité (ou dissimilarité) notée D(X, X’ ) telle que D(X, X’ ) est grand si les séries X et X’ sont similaires et petit sinon, il s’agit de trouver la ou les séries temporelles les plus similaires dans une base de données donnée [65, 47].
— La segmentation : étant donnée une série temporelle X = x1, x2, …, xT avec ∀i, xi ∈ R, il s’agit de trouver une approximation Xˆ = k1, k2, …, kK avec∀i, ki ∈ R et K << T et où Xˆ est une bonne approximation de X [52, 66].
— Le partitionnement : il s’agit de regrouper des séries temporelles d’une base de données donnée en plusieurs partitions différentes selon une mesure de similarité (ou dissimilarité) notée D(A, B)) telle que D(X, X’ ) est grand si les séries X et X’ sont similaires et petit sinon [78, 125, 86]
— La détection d’anomalies : étant donnée une série temporelle X que l’on considère comme étant « normale », déterminer quelles séries au sein d’une base de données contiennent une « anomalie » [48, 119].

Nous nous intéressons dans la première partie de ce manuscrit aux tâches de prédiction et de complétion de séries temporelles dans le cas où les séries sont multivariées et relationnelles. Nous proposons ensuite une méthode de classification de séries temporelles.

Prédiction

Le sujet de la modélisation et de la prédiction de séries temporelles a donné lieu à une riche littérature depuis de nombreuses années en statistique et en apprentissage automatique. En statistiques, les approches linéaires classiques basées sur les modèles à moyenne mobile et autorégressifs ont été les plus utilisées. Ces modèles supposent que les séries temporelles sont stationnaires et qu’elles présentent des dépendances linéaires dans le temps [38]. En apprentissage automatique, des extensions non linéaires de ces modèles, basées essentiellement sur des réseaux de neuronnes, ont été proposées dès le début des années 1990, ouvrant la voie à de nombreuses extensions non linéaires comme les méthodes à noyaux [85].

Les modèles dynamiques à état comme les réseaux de neurones récurrents ont également été utilisés pour la prédiction séquentielle dans différents contextes [32]. Récemment, ces méthodes ont été à la base d’importants succès dans différents domaines en modélisation de séquence avec notamment de forts progrès en modélisation du langage [46], génération de langage naturel [111], traduction [28] et beaucoup d’autres [24]. Un modèle proche de ceux que l’on propose dans cette thèse est dénommé « dynamic factor graph » [83] conçu pour la modélisation de séries temporelles multivariées. Comme les nôtres, c’est un modèle génératif à vecteurs latents qui capture les dynamiques temporelles dans un espace de représentation et qui prédit le futur des séries à l’aide d’une fonction de décodage de l’espace latent. A la différence des modèles prédictifs que nous proposons, aucune dépendance spatiale n’est considérée dans cette approche.

Les statistiques spatio-temporelles ont également un long historique [34, 121]. Les méthodes traditionnelles se basent sur des approches descriptives qui utilisent les moments du premier et du second ordre pour modéliser les dépendances spatiotemporelles. Plus récemment, des modèles dynamiques à états où l’état courant est conditionné par les états précédents ont été explorés [120]. Pour ces modèles, le temps et l’espace peuvent être continus ou discrets, cependant la méthodologie usuelle est de considérer un temps discret ce qui mène à modéliser des processus spatiaux comme des séries temporelles. Quand l’espace est continu à l’inverse, les modèles sont généralement exprimés par des équations intégro différentielles linéaires. Quand l’espace est discret, les formulations sont le plus souvent autorégressives. Ces modèles font face à des difficultés de passage à l’échelle dans le cas où un grand nombre de sources produisent des séries incomplètes : pour nombre de processus complexes, les observations ne fournissent qu’une description incomplète des dynamiques des phénomènes observés. Différentes stratégies ont été adoptées pour traiter ces particularités comme représenter le processus par des espaces à petites dimensions, menant à des familles de modèles assez proches de celles utilisées en machine learning pour modéliser des phénomènes dynamiques. Une propriété intéressante de ces approches est la possibilité d’incorporer de la connaissance a priori comme pour les processus spatio-temporels inspirés des phénomènes physiques. Cette stratégie consiste à s’inspirer de principes concrets comme par exemple les équations à dérivées partielles développées pour modéliser des phénomènes de diffusion en physique. En climatologie, des modèles prenant en compte des composantes géographiques et temporelles ont aussi été développés comme les « Gaussian Markov Random Fields » [96]. En apprentissage automatique, la modélisaton spatio temporelle a été assez peu considérée. Par exemple, [9] introduit un modèle de tenseur pour la prédiction et le kriging. Les auteurs de [69] utilisent des champs aléatoires conditionnels pour detecter de l’activité dans des vidéos; le temps est discrétisé (image par image) et un des buts visés est la prédiction d’activité future. Le BCI (Brain Computer Interface) est un autre domaine pour l’analyse de données spatio-temporelles avec notamment des travaux s’intéressant à l’apprentissage de filtres spatio-temporels [39, 90]. En deeplearning, des approches ont également été proposées sans prendre en compte explicitement les liens entre les dimensions spatiales et temporelles [72].

Modèles de prédiction de séries temporelles univariées

Modèles linéaires 

La plupart des applications réelles de modélisation de séries temporelles univariées utilisent des modèles linaires. Les modèles linéaires les plus populaires sont les modèles autorégressifs (AR). Un des avantages de ces modèles est qu’ils donnent une bonne approximation du premier ordre des dynamiques des processus sous-jacents aux données. Ces modèles peuvent théoriquement modéliser parfaitement des données qui sont décrites exhaustivement par le premier et le deuxième moment dans un monde de distributions gaussiennes. Ces méthodes sont aussi attractives de par leur simplicité et leur relative efficacité : même pour des problèmes connus comme présentant des dynamiques non linéaires, la non linéarité est soit pas assez significative soit pas assez constante dans le temps pour que les modèles autorégressifs présentent des performances acceptables.

Modèles non linéaires

Au début des années 90, les modèles non linéaires de prédiction de séries temporelles ont commencé à être popularisés [113]. Ces modèles nécessitant en général une quantité de données en apprentissage plus importante pour obtenir des gains de performances de prédictions, les applications visées ont été essentiellement la finance et le transport [50]. Là encore, un grand nombre de méthodes a été proposée, en statistique tout d’abord, avec le modèle ARCH [71] puis son extension GARCH, mais aussi en machine learning avec les modèles SVR [85] (Support Vector Regression) et surtout les réseaux de neurones qui sont devenus les modèles parmi les plus populaires en modélisation et prédiction de séquences. Ces derniers sont utilisés classiquement comme fonction autorégressive prenant la forme usuelle :

xt = f (xt−1, xt−2, …, xt−p) .

Table des matières

1 Introduction
1.1 Contexte : UPMC/VEDECOM
1.2 Données de transport et données séquentielles
2 État de l’art
2.1 Séries temporelles
2.2 Prédiction
2.2.1 Modèles de prédiction de séries temporelles univariées
2.2.1.1 Modèles linéaires
2.2.1.2 Modèles non linéaires
2.2.2 Modèles de prédiction de séries temporelles multivariées
2.2.3 Réseaux de neurones récurrents
2.2.4 Autres modèles
2.3 Données manquantes
2.3.1 Heuristiques
2.3.2 Méthodes autorégressives
2.3.3 Maximum de vraisemblance et E.M
2.3.4 Factorisation matricielle
2.4 Classification
2.4.1 Extraction de caractéristiques descriptives
2.4.2 Mesures de similarités
2.4.3 Apprentissage de métrique
2.4.3.1 Distance de Mahalanobis
2.4.3.2 Réseaux de neurones siamois
2.5 Apprentissage de représentation dans les graphes
3 RAINSTORM
3.1 Introduction
3.2 Modèle
3.2.1 Notations et tâches
3.2.2 Idée principale
3.3 RepresentAtIoN-baSed TempORal relational Model
3.3.1 Apprentissage
3.3.2 Inférence
3.3.2.1 Complétion de valeurs manquantes
3.3.2.2 Prédiction des futures valeurs
3.4 Prédiction de trafic et expériences
3.4.1 Trafic routier
3.4.2 Données réelles
3.4.3 Protocole expérimental
3.4.4 Méthodes de l’état de l’art
3.4.4.1 Complétion
3.4.4.2 Prédiction
3.4.5 Expériences et résultats
3.5 Information hétérogène
3.6 Conclusion
4 Autres Contributions
4.1 Prédiction de Parkings et de Trafic
4.1.1 Contexte et Tâches
4.1.1.1 Notations
4.1.2 Modèle
4.1.2.1 Apprentissage
4.1.3 Expériences
4.1.3.1 Données
4.1.4 Méthodes Concurrentes
4.1.5 Résultats
4.1.6 Conclusion
4.2 Utilisation de Représentations Gaussiennes
4.2.1 Principes
4.2.2 Notations et Tâches
4.2.3 Définition du modèle
4.2.3.1 Apprentissage
4.2.3.2 Modélisation du Décodeur
4.2.3.3 Modélisation de la Dynamique
4.2.3.4 Terme de Régularisation Structurelle
5 Conclusion

Télécharger le rapport complet