Comunicazione Corso di Laurea Magistrale in Informatica Continuous Time Bayesian Network Classifiers Relatore: Prof. Fabio Stella Correlatore: Dott. Daniele Codecasa Leonardo Di Donato Matr. n. 744739 24 settembre 2013 Anno accademico 2012-2013
di un pacchetto R per il framework delle CTBN ◦ apprendimento parametri CTBN e apprendimento CTBNC ◦ apprendimento strutturale CTBN ◦ classificazione supervisionata CTBNC • progettazione e implementazione di una RTE1 di TSIS2 ◦ software per il monitoraggio e tracciamento del passaggio di veicoli sui sensori delle reti stradali ◦ creazione modelli di traffico ◦ generazione di dataset per le CTBN • applicazione dei CTBNC al problema della classificazione di profili di traffico 1Estensione a tempo d’esecuzione. 2Ambiente di sviluppo integrato per la creazione e simulazione di modelli di traffico, supportato dalla Federal Highway Administration (FHWA). Introduzione 2 / 14
Cosa sono? Estensione temporale delle Bayesian Network. Modellano la dinamica di un sistema suddividendo il tempo in intervalli di egual durata. Come? Rappresentano le distribuzioni delle transizioni di stato effettuate dalle variabili casuali in un intervallo di tempo tramite una BN. svantaggi • granularità temporale fissata a priori • difficoltà nella rappresentazione di sistemi i cui processi evolvono con differenti granularità temporali Introduzione 3 / 14
Cosa sono? Estensione temporale delle Bayesian Network. Modellano la dinamica di un sistema suddividendo il tempo in intervalli di egual durata. Come? Rappresentano le distribuzioni delle transizioni di stato effettuate dalle variabili casuali in un intervallo di tempo tramite una BN. svantaggi • granularità temporale fissata a priori • difficoltà nella rappresentazione di sistemi i cui processi evolvono con differenti granularità temporali Introduzione 3 / 14
Cosa sono? Estensione temporale delle Bayesian Network. Modellano la dinamica di un sistema suddividendo il tempo in intervalli di egual durata. Come? Rappresentano le distribuzioni delle transizioni di stato effettuate dalle variabili casuali in un intervallo di tempo tramite una BN. svantaggi • granularità temporale fissata a priori • difficoltà nella rappresentazione di sistemi i cui processi evolvono con differenti granularità temporali Introduzione 3 / 14
network classifiers Definizione (Stella 2012) Un CTBNC è composto da una coppia C = (N , P(Y)) dove: • N è una CTBN con nodi attributo X1 , X2 , . . . , XN • Y è il nodo classe con valori val(Y) = { y1 , . . . , yK } e probabilità marginale P(Y). Continuous Time Bayesian Network Classifiers 5 / 14
network classifiers Definizione (Stella 2012) Il grafo su N rispetta le seguenti condizioni: • G è un grafo connesso • Pa(Y) = ∅ – la variabile casuale Y è associata al nodo classe • il nodo Y è indipendente dal tempo ed è specificato solo dalla sua probabilità marginale P(Y). Continuous Time Bayesian Network Classifiers 5 / 14
network classifiers Definizione (Stella 2012) Il grafo su N rispetta le seguenti condizioni: • G è un grafo connesso • Pa(Y) = ∅ – la variabile casuale Y è associata al nodo classe • il nodo Y è indipendente dal tempo ed è specificato solo dalla sua probabilità marginale P(Y). Y X1 X2 X3 X4 X5 Continuous Time Bayesian Network Classifiers 5 / 14
network classifiers Definizione (Stella 2012) Il grafo su N rispetta le seguenti condizioni: • G è un grafo connesso • Pa(Y) = ∅ – la variabile casuale Y è associata al nodo classe • il nodo Y è indipendente dal tempo ed è specificato solo dalla sua probabilità marginale P(Y). Y X1 X2 X3 X4 X5 Continuous Time Bayesian Network Classifiers 5 / 14
bayes classifier Definizione (Stella 2012) Un classificatore Continuous Time Naive Bayes (CTNBC) è un CTBNC C = (N , P(Y)) in cui ogni nodo attributo ha un solo genitore, il nodo classe Y. Quindi: Pa(Xn ) = {Y} ∀ Xn ∈ G. Continuous Time Bayesian Network Classifiers 6 / 14
bayes classifier Definizione (Stella 2012) Un classificatore Continuous Time Naive Bayes (CTNBC) è un CTBNC C = (N , P(Y)) in cui ogni nodo attributo ha un solo genitore, il nodo classe Y. Quindi: Pa(Xn ) = {Y} ∀ Xn ∈ G. X1 X2 X3 X4 X5 Y Continuous Time Bayesian Network Classifiers 6 / 14
CTBNC cattura più informazione rispetto al CTNBC. Ad esempio: • la dinamica del sensore S1 dipende da C1 • la dinamica del sensore S2 dipende da S1. Continuous Time Bayesian Network Classifiers 7 / 14
Approccio basato su punteggio: • punteggio di una struttura G rispetto a un training set D scoreB (G : D) = ln P(D | G) + ln P(G) • ricerca euristica (e.g., hill climbing) del punteggio massimo. scoreB (G : D) = Xi famscoreB (Xi , PaG (Xi ) : D) (Nodelman 2002) Osservazione No vincolo aciclicità: ottimizzazione dell’insieme di genitori di ogni nodo eseguibile indipendentemente dagli altri nodi. Apprendimento strutturale 8 / 14
Approccio basato su punteggio: • punteggio di una struttura G rispetto a un training set D scoreB (G : D) = ln P(D | G) + ln P(G) • ricerca euristica (e.g., hill climbing) del punteggio massimo. scoreB (G : D) = Xi famscoreB (Xi , PaG (Xi ) : D) (Nodelman 2002) Osservazione No vincolo aciclicità: ottimizzazione dell’insieme di genitori di ogni nodo eseguibile indipendentemente dagli altri nodi. Apprendimento strutturale 8 / 14
Approccio basato su punteggio: • punteggio di una struttura G rispetto a un training set D scoreB (G : D) = ln P(D | G) + ln P(G) • ricerca euristica (e.g., hill climbing) del punteggio massimo. scoreB (G : D) = Xi famscoreB (Xi , PaG (Xi ) : D) (Nodelman 2002) Osservazione No vincolo aciclicità: ottimizzazione dell’insieme di genitori di ogni nodo eseguibile indipendentemente dagli altri nodi. Apprendimento strutturale 8 / 14
che implementa il framework CTBN e i CTBNC. Requisito 3 – Apprendimento strutturale per CTBN • funzione di punteggio • ricerca euristica. Requisito 4 – Classificazione supervisionata tramite CTBNC • apprendimento CTBNC • inferenza tramite CTBNC. Strumenti software 9 / 14
di TSIS finalizzata al monitoraggio e tracciamento del passaggio dei veicoli sui sensori delle reti stradali. Motivazione 1. CORSIM3 non può restituire dati temporali non aggregati 2. massima granularità temporale di CORSIM: 1 secondo. Obiettivo Superamento delle limitazioni di CORSIM al fine di: 1. rilevare il passaggio dei veicoli sui sensori di una rete stradale TSIS nell’istante in cui esso avviene 2. generare e memorizzare le onde quadre dei sensori. 3Simulatore di modelli di traffico incluso in TSIS. Strumenti software 10 / 14
problema del traffico affligge tutte le grandi città. La congestione delle reti urbane incide negativamente su vari aspetti della qualità della vita. Approccio (Angulo 2011) Ottimizzazione dei piani semaforici in base alle condizioni di traffico: 1. classificazione dei profili di traffico 2. selezione del piano semaforico ad esso associato. Classificazione di profili di traffico 11 / 14
traffico 1. modello fittizio 2. riproduzione della rete stradale circostante Viale C. Battisti, Monza - Italia Classificazione di profili di traffico 12 / 14
traffico 1. modello fittizio 2. riproduzione della rete stradale circostante Viale C. Battisti, Monza - Italia Classificazione di profili di traffico 12 / 14
traffico 1. modello fittizio 2. riproduzione della rete stradale circostante Viale C. Battisti, Monza - Italia Classificazione di profili di traffico 12 / 14
• 40 sensori • 86400 secondi totali di simulazione • 6 classi – mattina , giorno, pomeriggio, sera, notte, alba Generate 2 varianti: traiettorie da 100 o 300 secondi. Dataset 2 • 6 sensori reali • 32 sensori totali • 86400 secondi totali di simulazione • 6 classi – mattina , giorno, pomeriggio, sera, notte, alba Generate 4 varianti: traiettorie da 100 o 300 secondi, solo sensori reali o tutti i sensori. Classificazione di profili di traffico 12 / 14
classificazione di profili di traffico tramite classificatori CTBN • comparazione di 4 istanze di classificatori: CTNBC, CTBNC23, CTBNC3, CTBNC4. Metodologia Per ogni dataset, per ogni classificatore: 1. esecuzione k-fold cross-validazione con k = 10 2. computazione metriche di valutazione per ogni fold 3. aggregazione risultati tramite approccio macro-average e micro-average. 3Classificatore CTBN appreso fissando il numero massimo di genitori a 2. Similmente per le altre istanze. Classificazione di profili di traffico 12 / 14
classificazione di profili di traffico tramite classificatori CTBN • comparazione di 4 istanze di classificatori: CTNBC, CTBNC23, CTBNC3, CTBNC4. Metodologia Per ogni dataset, per ogni classificatore: 1. esecuzione k-fold cross-validazione con k = 10 2. computazione metriche di valutazione per ogni fold 3. aggregazione risultati tramite approccio macro-average e micro-average. 3Classificatore CTBN appreso fissando il numero massimo di genitori a 2. Similmente per le altre istanze. Classificazione di profili di traffico 12 / 14