%\subsection{Metodo di soluzione proposto}



L'operazione di \emph{split} proposta nel paragrafo precedente non è, per cos dire, ""autosufficiente'': l'aggiornamento che viene fatto sulla matrice delle probabilità di transizione è, infatti, solo una stima grossolana dei valori, cioè non è detto sia la descrizione più giusta della nuova configurazione degli stati. 
La soluzione a questo problema è data dall'algoritmo di Baum, il quale, come spiegato in precedenza, fa una ri-stima dei parametri del modello in funzione delle osservazioni. L'idea è quella di applicarlo ripetutamente dopo ciascuno \emph{split} in modo da far convergere i parametri entro una certa tolleranza. 
In particolare, si impone che il ciclo continui finchè nessun aggiustamento dei valori tra la $A$ in ingresso e quella in uscita supera un $\nu$ fissato (inizialmente posto pari a $10^{-4}$ ma poi portato a $10^{-3}$ nella parte sperimentale per ridurre l'onerosità computazionale).\\
Tutto questo viene ripetuto finchè ci sono condizioni che suggeriscono di fare uno \emph{split}, che come si è detto, si ha quando un qualche $\sigma$ assume il valore 0.\\
Il procedimento seguito dal programma principale implementato è ben descritto nel diagramma di flusso di Figura \ref{fig:diagrammadiflusso}.
\begin{figure}[h]
	\begin{center}
	\includegraphics[width=\textwidth]{pictures/Flusso_totale}
	\end{center}
	\mycaption{Diagramma di flusso rappresentante il procedimento seguito dal programma principale implementato.}
	\label{fig:diagrammadiflusso}
\end{figure}


\paragraph{Indice di prestazione}
\ \\

Come accennato negli obiettivi, si considera l'indice di prestazione 
\begin{equation}
\eta = \frac{\displaystyle \sum_{t=0}^{T-2} \mathcal{P}[\hat{y}_{t+1} = y_{t+1} | y_{0:T-1}]}{T-1} \,.
\end{equation}
Può essere interpretato come una sorta di rendimento: infatti vale al più 1, essendo una somma di probabilità divisa per il numero di elementi della sommatoria stessa. Questi sono $T-1$ perchè l'uscita all'istante $t=0$ non è stimata ma supposta nota.\\
Per calcolarlo, si supponga di generare le stime delle osservazioni $\hat{y}_{t+1}$ da uno stato $x_t$ secondo la distribuzione data dalle probabilità degli archi uscenti da esso (in realtà la stima sarebbe $\hat{x}_{t+1}$ ma ricordando che ad ogni stato è associata sempre una sola osservazione, è come avere direttamente $\hat{y}_{t+1}$).
Riferendosi all'esempio di Figura \ref{fig:schema indice prestazione} (in cui le osservazioni sono indicate con A, B e C) per un generico istante $t$, le probabilità composte tra stima e osservazione sono calcolate come prodotto delle relative probabilità di transizione (perchè i due eventi sono indipendenti) e sono riportate in Tabella \ref{tab:prob indice prestazione}.
\begin{figure}[!h]
	\begin{center}
	\includegraphics[width=0.6\textwidth]{pictures/grafo_teoria_indice}
	\end{center}
	\mycaption{Esempio per spiegare l'indice di prestazione.}
	\label{fig:schema indice prestazione}
\end{figure}
\begin{table}[!h]
\centering
\begin{tabular}{c | c | c}
$\hat{y}_{t+1}$ & $y_{t+1}$ & prob. che si verifichi\\
                &           & la combinazione\\
\hline
A & A & $0.3 \cdot 0.3 = 0.09$\\
A & B & $0.3 \cdot 0.2 = 0.06$\\
A & C & $0.3 \cdot 0.5 = 0.15$\\
B & A & $0.2 \cdot 0.3 = 0.06$\\
B & B & $0.2 \cdot 0.2 = 0.04$\\
B & C & $0.2 \cdot 0.5 = 0.10$\\
C & A & $0.5 \cdot 0.3 = 0.15$\\
C & B & $0.5 \cdot 0.2 = 0.10$\\
C & C & $0.5 \cdot 0.5 = 0.25$\\
\end{tabular}
\mycaption{Dati di esempio per spiegare l'indice di prestazione.}
\label{tab:prob indice prestazione}
\end{table}
Di questi valori si sommano quelli che corrispondono alla corretta scelta della stima, cioè gli eventi AA, BB e CC, ottenendo
\begin{equation}
\eta(t+1) = 0.09 + 0.04 + 0.25 = 0.38 \,.
\end{equation}
Si può dimostrare che questo valore è sempre compreso tra $1/N_x$ e 1, dove $N_x$ è il numero di nodi futuri del nodo $x$: il primo caso corrisponde al fatto che tutti gli archi portano lo stesso valore (ed è come scegliere una transizione qualunque); il secondo si ha quando $N_x=1$ cioè comunica con un unico nodo (con probabilità 1).
Il precedente calcolo può anche risultare direttamente considerando la riga della matrice $A$ corrispondente al nodo $x$. Detta questa $a_{x,:}$ si ha cioè 
\begin{equation}
\eta(t+1) = \Vert a_{x,:}\Vert ^2
\end{equation}
(la condizione migliore si ha con $\eta$ elevato).

La prova di ""buona predizione'' può essere fatta sulla stessa traiettoria di creazione del grafo oppure su una diversa. Per capire intanto se le intuizioni sono fondate ci si concentra sulla prima strada. 
Si ha motivo di credere che ad ogni passo di \emph{split} l'indice di qualità aumenti perchè si ha un maggior numero di stati, i quali, per costruzione, descrivono più accuratamente il legame tra la traiettoria e il posizionamento delle telecamere.
Al contrario, provando su una traiettoria diversa si pensa che l'indice aumenti fino a un certo punto ma poi peggiori, come insegna anche la teoria dell'identificazione dei modelli, perchè il grafo è stato modificato da \emph{split} motivati dalla prima.

\begin{figure}[!h]
	\begin{center}
	\includegraphics[width=\textwidth]{pictures/grafico_indiceOk}
	\end{center}
	\mycaption{Ipotesi dell'andamento di $\eta$ in funzione del numero di split.}
	\label{fig:eta_teorico}
\end{figure}



