Ali Saad

Of Gravity CPT Conditional Probability Tables CUSUM Cumulative Sum DAG Directed Acyclic Graph DBS Deep Brain Stimulation DCS Dynamic Cumulative Sum EEG Electroencephalography EFA Exploratory Factor Analysis EM Expectation-Maximization EWMA Exponential Weighted Moving Average FFT Fast Fourier Transform FI Freezing Index FoG Freezing of Gait GNN Gaussian Neural Network HLC Hierarchical Latent Class HNR Harmonic to Noise Ratio MPT Maximum Phonation Time PCA Principal Component Analysis PCC Pearson's Correlation Coefficient PCs

Keywords: Parkinson's Disease, Freezing of Gait, Detection, Diagnosis, Multi-sensor system, Gaussian Neural Network, Bayesian Belief Network . Acronyms BBN Bayesian Belief Network BNC Bayesian Naive Classifier COG Center

I would like to give special thanks to the jury members for your brilliant comments and suggestions. I owe a debt of gratitude to Professor Dimitri Lefebvre for your continuous guidance, careful attention to details

Résumé

Détection du risque de chute chez les malades atteints de Parkinson le risque de chute provoqué par le phénomène épisodique de 'Freeze of Gait' (FoG) est un symptôme commun de la maladie de Parkinson. Cette étude concerne la détection et le diagnostic des épisodes de FoG à l'aide d'un prototype multi-capteur. La première contribution est l'introduction de nouveaux capteurs (télém tre et goniomètre) dans le dispositif de mesure pour la détection des épisodes de FoG. Nous montrons que l'information supplémentaire obtenue avec ces capteurs améliore les performances de la détection. La seconde contribution met en oeuvre un algorithme de détection basé sur des réseaux de neurones gaussiens. Les performance de cet algorithme sont discutées et comparées à l'état de l'art. La troisiéme contribution est développement d'une approche de modélisation probabiliste basée sur les réseaux bayésiens pour diagnostiquer le changement du comportement de marche des patients avant, pendant et après un épisode de FoG. La dernière contribution est l'utilisation de réseaux bayésiens arborescents pour construire un modèle global qui lie plusieurs symptômes de la maladie de Parkinson: les épisodes de FoG, la déformation de l'écriture et de la parole. Pour tester et valider cette étude, des donnée cliniques ont été obtenues pour des patients atteints de Parkinson. Les performances en détection, classification et diagnostic sont soigneusement et évaluées.

Framework and context of the thesis

The PhD thesis is prepared within the research group 'Groupe de Recherche en Electrotechnique et Automatique du Havre' (GREAH). It is developed in the framework of academic co-supervision partnership between university of Le Havre 1 and the Islamic University of Lebanon (IUL) 2 . This work has been developed under the supervision of Mr. D.Lefebvre, Professor at GREAH, Mr. F.Guerin, Associate Professor at GREAH, Mr. I.Zaarour, Associate Professor at the faculty of business and economical sciences in the Lebanese University, and Mr. M.Ayache, Associate Professor at the department of Biomedical Instrumentation at IUL. As well as Mr. Paul Bejjani, M.D. at the 'Neuro Science Clinic: Parkinson Memory and Movement Disorder Center' as an expert in the field of neurology.

GREAH -EA 3220 is a research group in the domains of Electrical Engineering (DSPT 8 -SPI), and Automatic Control and Signal Processing (DSPT 9 -STIC). It has two teams: the first is (Electrical systems -ES) that works on actuators and renewable energy systems, the second is (Safe systems -S2) that works on control and diagnosis methods for a large vari-ety of systems. This thesis has been prepared with the S2 team. The mains topics developed in that team are:

-Modeling and simulation, performance evaluation and reliability.

-Diagnosis, faults detection and isolation, monitoring and supervision of industrial systems. -Robust and adaptive control, neural networks, artificial intelligence.

-Hybrid dynamical systems, discrete event systems.

-Sensors and measurements, robotics. The S2 team is with the regional research cluster (TERRA -MRT) and the national research network CNRS -gdr MACS. The team participates to several projects. In particular, it drives the project MADNESS about the measurement, collect and analysis of large stream of data to make the systems safe and secure. This PhD takes part to that project.

List of publications

The obtained results have made the topic of the following publications:

-Journals 1. Ali Saad, Iyad Zaarour, François Guerin, Paul Bejjani

Thesis objective

Parkinson's Disease (PD) is one of the most common progressive neurodegenerative diseases with a higher prevalence in older adults and often having devastating symptoms. One of PD symptoms is freezing, which may occur during gait, speaking or a repetitive movement such as handwriting. Freezing of Gait (FoG) has been defined as 'a brief episodic reduction of forward progression of the feet despite the intention to walk' [Giladi 92]. FoG is one of the most debilitating motor symptoms in patients with PD as it may lead to loss of independence [Fahn 95].

In order to study all the aspects of the FoG phenomena, we are building a system that aims to detect, diagnose and correct FoG in PD patients. This system consists of a multi-sensor device that can be used (1) by PD patients to overcome their FoG difficulties, and (2) by PD experts to diagnose the freezing behavior of patients in order to apply the suitable therapy. Moreover, this system aims to provide effective stimulations for patients to overcome and correct their freezing behavior.

The work done in this thesis is a reliable part to build this FoG prevention system. A new classification algorithm based on new effective sensors is proposed for the detection/diagnosis of FoG. The aim is to design a robust algorithm to detect FoG episodes with maximum detection performance. For this purpose, we developed a multi-sensor device, and conducted a comparison study that highlights the effect of increasing the number of sensors on the FoG detection performance. The detection algorithm that is used in this study is based on the Gaussian Neural Network (GNN) that is adapted for FoG detection. After collecting signals we proposed an approach that extracts unique signature feature vectors from FoG time series. Then due to the complexity of FoG events these heterogeneous feature vectors are combined. This data fusion is applied using the Principal Component Analysis (PCA) technique. Then the combined data are introduced to the GNN detection algorithm. The study proves that the utilization of extra number of sensors, especially the telemeter and the goniometer, can improve the on-line FoG detection performance. The global detection system has been tested and validated first with FoG emulation data and then with real measurements obtained from two groups of patients in the Parkinson Memory and Movement Disorder Center.

Moreover, another approach to detect/diagnose FoG based on the Bayesian Belief Network (BBN) formalism along with multi-sensor device is proposed. The proposed model can also be used for the detection of FoG events, and more importantly for diagnosing and forecasting issues. In particular, using

Ali SAAD c GREAH -2016
the probabilistic inference tool of the BBN, we can infer the probability of a patient having a specific pattern of walking given that this patient is encountering a freezing event. Also, freezing data are used to search for FoG diagnosis and causality in the context of BBN.

Finally, this study introduces the main principle of a global and a reliable methodology for diagnosing multiple PD symptoms based on the BBN formalism. More specifically, the symptoms that we tackled are (1) the FoG phenomena, (2) handwriting disorders, and (3) speech difficulties. The methodology of this modeling approach consists of data acquired from PD patients during their walk using the multi-sensor device. As for handwriting and speech symptoms, we used digitizer tablets and microphone headsets to acquire kinematic and speech features from PD traces and specific vocal activities. A probabilistic inference is applied in an unsupervised classification manner.

Organization of the thesis

The thesis is organized into six chapters describing the different study aspects. Following the general introduction the document is divided as follows:

-Chapter two is subdivided into three parts. Part one is introductory to PD and its main symptoms with emphasis on the FoG phenomena.

Part two focuses on the studied phenomena of FoG and its tremendous impact on the lives of patients. In part three a detailed literature review is established concerning the detection and diagnosis of FoG episodes. This chapter allows making the positioning of our work comparing to existing literature. -Chapter three entitled as multi-sensor design and signal processing provides a detailed description of the multi-sensor system and states the data acquisition techniques used to collect simulation and clinical data. Moreover, this chapter investigates the acquired signals in order to extract informative features that can separate the FoG class from the other modes. The chapter continues with an analysis of the selected features to validate the signal processing part using a windowing approach. Finally the chapter ends with an explanation about the methodology used for combining the selected indicators using PCA technique. -Chapter four examines a new method based on a soft computing technique to detect FoG in PD. The theoretical background of the proposed GNN method is detailed. Moreover the detection performances are highlighted and discussed. In addition, the effect of increasing the number of sensors on the detection performance is investigated. -In chapter five a graphical probabilistic modeling study for FoG is conducted. Part one gives a clear explanation of the modeling approach that is based on the formalism of BBN. Part two describes the utilization of a published data related to FoG. Moreover this part proposed an assessment methodology for finding a causal link between FoG and features of interest. Also, a BBN model is proposed for FoG using the published data that contain data from a single sensor. The third part concentrates on the modeling (using BBN) of FoG using the multi-sensor device. The chapter ends with an exhibition of the results of the proposed BBN classification technique. -Chapter six illustrates how diverse PD syndromes may be combined and integrated into a common global architecture in the framework of modeling and diagnosing PD syndromes. The chapter proposes an experimental and data acquisition system, and gives a clear explanation of the modeling approach based on an unsupervised learning technique (i.e. clustering). The chapter gives a detailed description and interpretation of the obtained results that are considered as local and global prototypes. It states the main principle of a global model that can be used for a better understanding of PD symptoms. -Finally, the document is ended with a conclusion, summarizing the main contributions of this PhD and discussing future derivative works.

Introduction: Parkinson's disease

PD was first described by James Parkinson in 1817. PD is a slowly progressive neurodegenerative disorder [Monti 15]. It is characterized by the loss of dopaminergic and other sub-cortex neurons in the brain (e.g. neurotransmitters that are essential in stabilizing neural functioning and motor movement) [Forno 96]. The etiology of PD is still unclear, but recent studies show that this devastating disorder may be caused by a combination of genetic and environmental factors [Baltazar 14][ Bonifati 14]. In recent studies, the annual incidence per 100,000 is 1 between the ages of 30 and 39 years, 17 between the ages of 50 and 59 years, and 93 between the ages of 70 and 79 years [Bower 99]. On the basis of these incidence rates, the lifetime risks of PD are estimated at 2.0% for men and 1.3% for women [ Elbaz 02]. PD is characterized by a number of motor and non-motor complications and symp-toms with a significant impact on quality of life. PD affects motor control, such as gait, body balance, handwriting, and speech [Morris 96]. The main symptoms of PD are:

-Bradykinesia: Bradykinesia, or slowness of movement, is one of the cardinal manifestations of PD [ The second method which records the handwriting of the patient on a graphical tablet with an electronic pen and analyzing the results For early stage patients, rigidity get improved steadily over the first three months after starting dopamine treatment, but the tremors are more difficult to control [ Lees 09]. Many people are able to improve their handwriting by practicing diligently. They can use wide-ruled paper and concentrate on staying within printed lines. With the aid of medications to control tremors, individuals who have enough willpower and neural functioning to focus on their activities can overcome micrographia symptoms and write legibly [Sullivan 07]. In spite of these advances, there continue to be many complications associated with the long-term management of both motor and non-motor symptoms of PD, and treatment remains a challenge.

Ali

Freezing of Gait in Parkinson's disease

FoG is a unique and well known clinical feature of PD and other higherlevel gait disorders [Nutt 11]. Freezing episodes represent a special form of locomotive disturbance seen only in PD. Freezing may occur during gait, speaking or a repetitive movement such as handwriting. It is one of the most disabling and least understood symptoms in PD, and is usually observed in the advanced stage of the disease [Okuma 06]. FoG does not occur due to muscle weakness, patients are able to freely perform their tasks after overcoming their freezing episode [ Giladi 98]. Parkinsonian freezing is considered as a distinct clinical feature independent of akinesia. Its pathophysiology is poorly understood and is believed to involve abnormalities in dopamine neurotransmission in critical motor control areas in the brain [Sandyk 96]. Over half of patients with PD eventually develop FoG [Nutt 11]. It occurs more frequently in men than in women, especially those who report tremor symptoms [Moore 07]. And usually occurs in patients with long duration and advanced stage of the disease, although mild forms may develop earlier [ Okuma 14]. FoG is one of the most debilitating motor symptoms in patients with PD as it may lead to loss of independence [Fahn 95]. The annual fall incidence rates range from 50% to 70% in patients with PD [Allen 13]. FoG interferes with activities of daily life, reduces mobility, and is an important risk factor for falling with consequent injuries impairing quality of life [Gray 00][ Bloem 04]. FoG episode is defined as an episodic gait impairment whereby there is inability to generate effective forward stepping movements [ Mensink 14]. Patients with FoG experience a brief, sudden and often unexpected episodic reduction of forward progression of the feet despite the intention to walk, and is often described by patients as if their feet are glued to the floor for a short period of time while the COG of their body continues to move forward [Giladi 92]. Freezing episodes have been divided into 3 subtypes: (a) no movement-akinesia (the patient is not making any observed effort to overcome the block), (b) trembling in place (rapid synchronized movement of both legs observed as the patient attempts to overcome the block but no movement forward is seen), and (c) shuffling forward (the patient makes an effort to overcome the block and is partially successful, but the steps are very small and rapid and no real step is taken) [Factor 08][Horak 92]. These phenomena often coexist in the same patient and follow a gradient of severity [Martino 15]. FoG can be provoked while walking in narrow or tight quarters such as a doorway, whilst adjusting one's steps, when reaching a destination, and in stressful situations especially time-limited ones such as walking to answer the telephone or the doorbell ring, entering an elevator, or crossing the street when the light is green. As the disease progresses, FoG can appear spontaneously even in an open runway space [ Bloem 04]. Assessing FoG is further complicated due to the episodic, unpredictable, and variable presentation, as well as the complex relationship with medication [Chen 13]. Its unpredictable occurrence and sensitivity to different factors make it hard to clinically evaluate and quantify FoG [ Giladi 08]. Surprisingly, a visit to Ali SAAD c GREAH -2016 the doctor's office or to a research laboratory improves FoG [Andrews 73], this may happen because of the increased attention made by the patient at the clinic. To evaluate the severity of FoG, during history taking, patients are often asked about the characteristic feeling of 'being glued to the floor'.

To ensure valid and reliable evaluation of FoG, a combined methodology is recommended relying on tests of complex gait during the off-period together with a FoG-questionnaire, addressing severity and impact of freezing on daily life [Nieuwboer 08a]. In PD, FoG is strongly associated with motor fluctuation, dual tasking (cognitive load) aggravates FoG. Treatment of FoG includes medical, behavioral, and surgical approaches [Okuma 06].

-Medical Approach: In general, freezing is resistant to pharmacological therapy such as Levodopa, which is the most effective and commonly used anti-parkinsonian dopaminergic medication, and has significant and long-lasting effects on parkinsonian gait [ Factor 08].

Freezing may happen when the PD patient is due for the next dose of dopaminergic medications. This is called 'off ' freezing, and in this case patient may respond to dopaminergic treatment, and freezing episodes lessen after taking the medicine. In other cases, in which patients take dopamine replacement therapy, they usually report improvement in the PD symptoms, but on the other hand their gait worsens and they encounter freezing episodes. This phenomenon is called 'on' freezing. And sometimes it improves by lowering the dosage of dopaminergic medications [ Factor 08]. Thus, FoG can occur during both on and off medication [ Schroeteler 09]. The first step in medical treatment is to ensure adequate dopaminergic stimulation to reduce the off state [ Okuma 14]. Knowing that the disease progression alone may be responsible for the development of FoG, other studies have suggested that longer duration of dopaminergic treatment may also be associated with FoG [ Okuma 08]. Therefore, it is concluded that FoG is not entirely drug-resistant -Surgical Approach: The majority of patients with PD can be treated with medications. Furthermore, as the disease progresses symptoms evolve and become more resistant to medical therapy. In these cases a surgical intervention is needed. The surgery is called Deep Brain Stimulation (DBS). It is one of the most important solutions proposed to reduce the effects of the severely disabling symptoms of advanced PD (i.e. FoG). This adjustable, reversible therapy uses an implanted device that electrically stimulates areas of the brain, which enables the brain circuits that control movement to function better. The stimulation is done through a neurostimulator device similar to the pacemaker, implanted near the collar bone. The device consists of a c GREAH -2016 Ali SAAD pulse generator connected to electrical stimulation electrodes which deliver electrical stimulation to precisely targeted areas of the brain. DBS is currently targeted to three areas of the brain: the ventral intermediate nucleus of the thalamus, the globus pallidus pars interna, and the subthalamic nucleus. -Behavioral Approach: FoG has been known to respond favourably to sensory 'tricks' and cues. Tricks of all kinds (including external cues) are effective therapeutic approaches. The immediate effects of cues have no consistent impact but longer periods of cued training may be beneficial [Nieuwboer 08b]. In case of patients that encounter FoG during medication, and do not reliably respond to pharmacotherapy or DBS, external cues have been demonstrated that it can influence FoG effectively. They are applied as auditory, visual, tactile, or mental cues [ Schroeteler 09]. Some patients develop their own tricks to overcome freezing attacks (e.g. marching to a command, stepping over inverted cane, walking to music or a beat, and shifting body weight) which all aim to provide sensory-motor drive in order to overcome the freezing [Lim 05]. Evaluating the response to external cues has diagnostic importance, and helps to determine possible therapeutic interventions [Lamberti 97]. Because of the tight interplay between FoG and mental functions, the evaluation must include cognitive testing (mainly frontal executive functions) and judgment of mood. Attention is over-

Ali SAAD c GREAH -2016
loaded, the therapeutic window and the practical applicability of cueing seem more limited. Thus, these evaluation aspects need to be incorporated in the development of future cueing programs designed to alleviate FoG [ Snijders 08].

Detection of Freezing of Gait

Accelerometer approach

Detection of FoG phenomenon has taken an apparent area of interest in research. Several studies were oriented toward using on-body acceleration sensors to measure movements and responses of PD patients. Han et al. [Han 03] use Fast Fourier Transform (FFT) as a signal processing and analysis technique to record movement patterns at different sampling rate. Pre-recorded accelerometer data were utilized, results showed that normal movement frequency was close to 2 Hz while FoG frequencies ranged between 6 and 8 Hz. Moore et al. [ Moore 08] have utilized a single vertical linear accelerometer to detect FoG in PD patients during a predefined walking and standing test. By analyzing the frequency spectrum of the accelerometer, they have found that FoG was accompanied by high-frequency components in the 3-8 Hz band (freeze) with respect to the 0.5-3 Hz band (locomotor). These results allowed calculating a Freezing Index (FI) that was defined as the ratio of power in the freeze band (3-8 Hz) divided by the power in the locomotor band (0.5-3 Hz). They stated that during normal movement the FI will be relatively stable, while the gait freeze will cause it to increase. Thus a threshold was selected such that FI values above this limit have been classified as FoG events. This study was done on seven subjects that experienced a total of 46 FoG events. The method has shown to be up to 78% accurate in detecting FoG before being customized to patients [ Moore 08]. Several researches [Jovanov 09][Bachlin 10] have extended the previous studies to present a wearable computer system which uses on-body acceleration sensors placed on different body parts (ankle, knee and hip) that measure acceleration data of PD patients (figure 2.3). It is claimed that this wearable device automatically detects FoG by calculating the FI inherent in these movements. And once FoG have been detected, a cueing assistant provided a rhythmic auditory signal which stimulated patients to resume walking. Marc Bachlin et al. [Bachlin 10] also introduced an energy threshold to distinguish between standing and other movement states. It was based on the observation that the total energy content of standing is significantly lower than that corresponding to FoG or walking. This system reported on-line FoG detecc GREAH -2016

Ali SAAD tion events with a sensitivity of 73.1% and a specificity of 81.6% with latency 4.5 sec (237 FoG episodes from 8 patients). Although not all patients found that the auditory cueing made a positive effect in overcoming FoG. On the other hand, the results of the prototype done by Jovanov et al. [ Jovanov 09] was represented as improvements in the average latency period. They have recorded signals from five experiments, four from simulated freezing gait events and one from a real patient. They reported 332 ms average latency period with a maximum FoG detection latency period of 580 ms. More advantages were the maximum battery life with minimum system size. Recent research [Mazilu 12] used the collected data from Marc Bachlin et al. [Bachlin 10] to implement a FoG detection method as an application on a smart-phone instead of the wearable computer system. The authors have used supervised machine learning techniques using weka data mining suit to detect FoG. They collected data from different placement of acceleration sensors, and computed four time domain features (mean, variance, standard deviation and entropy), and three frequency domain features (energy, FI [Moore 08] and power [Bachlin 10]). After that they selected the most discriminative features using correlation based feature subset selection as described in [Hall 98]. The selected features were introduced to different classifiers that are trained on features selected from N-1 subjects and ] they defined the index of FoG as the ratio between: the square of the area under the acceleration power spectrum in a freeze band (3-8 Hz), and the square of the area under the acceleration power spectrum in a locomotor band (0-3 Hz). Twenty out of the twenty-five PD patients participants encountered FoG during the study. A total of 298 FoG events were identified by two raters. The two variables that were used to assess their methodology were the width of the sampling window for determining the ratio of freezing, and the threshold above which this ratio indicates a FoG event. Also, they changed the number of included acceleration sensors to evaluate the feasibility of using seven sensors. The stated that the aim of their study is to explore the effects of freeze threshold and window size, as well as the use of multi-segmental sensor placement on the sensitivity and specificity of FoG detection. They combined the detection results of all the seven sensors by using a majority vote algorithm (at least four sensors detected FoG). To evaluate the performance of their methodology they calculated the number of FoG events detected and the percent time frozen (the cumulative duration of all FoG episodes divided by the total duration of the walking task). On the other hand, the two raters also calculated the same evaluation values.

Then their results were presented as a comparison between the findings of their methodology and the findings of the raters. They stated that increasing the number of acceleration sensors gave a the strongest agreement to the raters and thus increased the accuracy of detecting FoG events using a window size of five seconds. Assam et al. [Assam 14] utilized the data which were collected and made public by [Bachlin 10]. They extracted feature vectors that can be used to distinguish FoG time series from normal movement time series by performing multi-resolution wavelet decomposition through wavelet transform. They stated that the FoG sub-band energies of the approximation and detail wavelet coefficients were significantly higher than that of the normal movement time series. Thus they selected coefficients and utilized them as feature vectors for the FoG prediction technique. After that they employed vector quantization to eliminate redundancy using the Linde-Buzo-Gray [START_REF] Linde | An algorithm for vector quantizer design[END_REF] vector quantization algorithm. Then, the calculated dataset was introduced into a conditional random fields data mining technique [Lafferty 01]. They stated that their framework predicts the onset of FoG with best overall performances about of 93% [ Assam 14]. Zach et al. [Zach 15] made use of the FI proposed by [ Moore 08] to evaluate whether accelerometry can detect FoG while executing rapid full turns and while walking with rapid short steps (the two most common provoking circumstances for FoG). They included 23 PD patients that have FoG symptoms. They used a single tri-axial accelerometer mounted on the waist of patients. They stated that during full rapid turns, accelerometry yielded a sensitivity of 78% and specificity of 59%. A sensitivity of 64% and specificity of 69% was observed during walking rapidly with small steps. Combining all tasks rendered a sensitivity of 75% and specificity of 76% [Zach 15]. Furthermore, a recent study [Rezvanian 16] proposed a new method to detect FoG based on the continuous wavelet transform. Their aim was to employ both frequency and time domain information in a smaller sample window size to detect the short-duration of FoG better than FFT method. They analyzed the published data acquired by Bachlin et al. [Bachlin 10] and calculated a FoG index based on the wavelet transform of the data. They used a linear threshold to classify whether a FoG event occurred or not. They selected an optimal decision threshold for discriminating FoG, which was the one that gave the highest accuracy when tested on the published data. They stated that their methodology was able to detect FoG events using a single shank sensor with window size of two seconds and update time of one second and having a 82.1% and 77.1% for the sensitivity and specificity, respectively [Rezvanian 16].

Force sensor approach

For a different approach in detecting FoG, some researches [Hausdorff 03] [Popovic 10] assessed the forces under the feet of PD patients using force sensing resistors. Hausdorff et al. used pressure sensitive insoles that reflect the forces exerted under the feet of patients. They analyzed data from 43 episodes of FoG in 11 patients with advanced PD. Spectral analysis was employed to quantify the frequency content of the acquired data. While detrended fluctuation analysis was used to quantify the temporal structure of the variations in the insole forces. Using spectral analysis they found the presence of low amplitude, complex oscillations during FoG, typically in the

Ali SAAD c GREAH -2016
range of 1-6 Hz. Using detrended fluctuation analysis they reported that FoG is not a random process. During FoG, the legs move with temporal structure and organization [Hausdorff 03]. Another research was based on the belief that during normal gait, the forces under the feet oscillate in an organized pattern, while during FoG episodes this periodicity diminishes.

Electroencephalography approach

Electroencephalography (EEG) is a new approach in detecting FoG events. Handojoseno et al. [Handojoseno 12] presented method for detection of FoG by EEG signals using discrete wavelet transforms. The wavelet transform allowed the decomposition of the EEG signal into five EEG sub-bands with different frequency bandwidth: 0-3.9 Hz, 3.9-7.8 Hz, 7.8-15.6 Hz, 15.6-31.3 Hz and 31.3-62.5 Hz. The sub-bands have been used to extract the sub-band Wavelet Energy and Total Wavelet Entropy. After that a three layer Back Propagation Neural Networks is used for classification purposes. The classifier has the ability to identify the onset of FoG in PD patients during walking with average values of accuracy, sensitivity and specificity are around 75% (ten patients participated in this study).

Multi-sensor approach

Previous researches and implementations have shown considerable effort expended in the development of algorithms for the detection of FoG during predefined activities. Cole et al. [Cole 11] described a two stage FoG detection algorithm during unconstrained and unscripted activities. They used both wireless, wearable, miniaturized tri-axial accelerometer and electromyographic sensor results as input features of a dynamic neural network to detect FoG instances. PD patients would execute these activities while attaching the sensors on different parts of the body (shin, thigh, leg, and forearm) as shown in figure 2.4. The first stage of the algorithm was the application of a linear classifier to determine when the patient is upright (i.e., standing or c GREAH -2016 Ali SAAD walking) using acceleration sensors. The algorithm was applied knowing that when the subject stands or walks, the acceleration due to gravity predominantly registers in the Y-channel of the thigh and shin acceleration sensors, while when the patient sits, the acceleration due to gravity registers in the Z-channel of the thigh acceleration sensor, with unchanging registering in the Y-channel of the shin sensor. The second stage was to apply a dynamic neural network to determine the presence of FoG knowing that the patient was upright. They stated that the Dynamic neural network [Wan 93] was used since it better captures the time varying nature of FoG. The training data included 20 FoG episodes taken from six PD patients, each on the order of two to three seconds long. Upon assessing the effectiveness of this system on experimentally collected datasets, the FoG detector expressed 83% sensitivity and 97% specificity on a per-second basis [Cole 11]. Moreover, Mazilu et al. [Mazilu 13] have designed a multi-modal sensor system using physical and physiological sensors. The integrated sensors were: inertial measurement units, pressure sensors, electrocardiography, galvanic skin response sensors and the functional near infrared sensors. The inertial measurement units were placed on both legs and were used to capture stride frequency and stride length. The pressure sensors were placed on the foot and they used frequency analysis to process the acquired data. Electrocardiography signals were used since they stated that during FoG periods a significantly increased heart rate could be observed. The galvanic skin response sensor which is a method of measuring the electrical conductance of the skin, It was used to spot psychological or physiological arousal.

Ali SAAD c GREAH -2016

The functional near infrared sensor that uses near infrared light to measure concentration of oxygenated and de-oxygenated hemoglobin. The locations of the mentioned sensors are shown in figure 2.5. They acquired data from 18 PD patients. Three of the patients could not perform the entire protocol, due to the disease severity, and seven did not experience any FoG events. They acquired 180 FoG episodes that were labeled by physiotherapists. Upon visual inspection of the acquired data, they have showed preliminary evidence that a multi-modal view can reduce FoG detection latency by considering lower level context (e.g. turning) and physiological data. They stated some drawbacks which is the high sensitivity of the electrocardiography sensors for long term wearing since the electrodes get easily loose. Similarly galvanic skin response sensors lacked robustness, as patients tend to touch the electrodes and consequently corrupt the signal [Mazilu 13].

Conclusion

Throughout this chapter we defined, as possible, PD and highlighted on its main symptoms. We introduced one of the most unpredictable and impairing symptoms of PD which is FoG. We have summarized more than c GREAH -2016

Ali SAAD twelve years of accumulated work in the domain of FoG detection, by presenting the techniques used, and evaluating their results. We traced the development of diverse researches and sensor-based systems (acceleration, force sensitive, electromyography, etc...) to expand and refine the results, pointing out flaws and demonstrating the advantages of each one. The existing studies inspire building advanced FoG detection systems that may utilize their results, and expand it from simple detection of FoG into detection then correction of this phenomena in a more influential and effective way. The main limitations in existing FoG detection methods can be summarized as follows:

-Most of the previously discussed systems that detected FoG used homogeneous data (i.e., data from one type of sensor). In most studies accelerometer was the main sensor that detects FoG. These uni-sensor systems contain limited characteristics to detect and diagnose FoG. -Most systems were developed on rather simplistic and scripted tasks done in the lab, e.g., walking on a treadmill. That leads to potential lack of robustness in daily life, as often clinical settings are not similar with the daily life ones. -Few works that integrated different sensors to detect FoG events used sensors that are hard to be implemented in a daily used wearable system (e.g. EEG, electrocardiography, and more). These types of sensors are difficult to implement for long term wearing since the electrodes get easily loose while performing simple daily life activities. Table 2.1 summarizes the FoG detection methods and their performances using different sensoring approaches and detection methodologies. Their work can be improved by building a prototype that acquires data from different sensor types. The freezing phenomenon is complex, since even for the same patient the behavior of each FoG event is not consistent and it depends on the environmental circumstances. Thus, acquiring data from different kinematic sensors will lead to a better knowledge about the physical behavior of the freezing phenomena. Moreover, combining observations from different sensors will result in an improved detection performance. The wearable device is exposed to human interactions, so there is an increased risk of acquiring incorrect observations due to faulty sensors. In this case, the uni-sensor system cannot compensate the incorrect data of the faulty sensors. On the contrary, the multi-sensor system will show robustness in sensor failure cases because of the diversity of the collected data. Multi-sensor system allows to go beyond just FoG detection, but also to reach diagnosis and prediction of FoG events. In addition, this system can be also extended to detect falls caused by severe freezing episodes. Unlike uni-sensor that will give limited information about the falling behavior of PD patients. By employing different Unlike previous studies, and due to the complexity of FoG episodes, this study aims to detect FoG using the combination of heterogeneous data (i.e., data from different kind of sensors). The classifier decision is based on the data given from a multi-sensors system. We argue that the use of such a multi-sensor device will increase the FoG detection accuracy and also can be used to diagnose and predict freezing episodes. To the best of our knowledge, there is no previous work that integrates telemeters and goniometers in the detection of FoG for PD patients. Our aim is to design a systematic algorithm that will be implemented for on-line detection and may lead to obtain the best sensitivity compared to the existing works that are dealing with FoG detection.

Introduction: Multi-sensor device description

The wearable multi-sensor prototype has been built to acquire heterogeneous data from different types of sensors that are placed on different body parts of PD patients. The integrated sensors are: accelerometers, telemeters and goniometers. The other alternative for a multi-sensor device is the single sensor device, but since freezing affects the whole body of a patient, a single sensor placed on a single position will not be able to assess the behavioral change of patients during FoG. Moreover, fusing multiple sensor technologies to detect the same FoG event will lead to higher reliability and trustworthiness. The accelerometer is selected because of its importance in the previous literature study, that showed a link between the change of acceleration data and FoG. The telemeter is integrated since it gives the ability to measure the variation of the inter-foot distance. This measurement is important since it allows assessing the fact that during FoG, the distance between the legs of PD patients reduces significantly when compared to their normal walk. From the point of view of the PD expert, this measurement defines the FoG phenomenon, since during a FoG episode the inter-foot distance of a patient decreases significantly while maintaining movement. The decrease of the inter-foot distance results in a decrease of the knee angle. This is an another reason to integrate the goniometer. Moreover, the goniometer is introduced so that it can be used in the FoG prevention system to avoid the fall of patients during severe FoG. This can be done by monitoring the knee angle during FoG, and perform specific muscles stimulation if the angle exceeds a predefined threshold. In order to build a preliminary multi-sensor device, all of the above mentioned sensors were connected to a National Instrument Data Acquisition (DAQ) device (NI DAQ PCI 6259). The acquired data are saved as '.dat' files using a Visual-Basic computer program, and then signals were processed off-line by Matlab program.

Acceleration sensor

For the measurement of acceleration during gait, the ADXL330 3-axis acceleration board has been used. Besides precision, the additional advantage of this board is its small size, 28.3 mm x 18.5 mm. There are several accelerometer boards that can be used to serve the same purpose (e.g. triple axis accelerometer LSM303). However the ADXL330 3-axis acceleration board is adopted due to its low noise and power consumption, as well as its small size and weight, in addition to its low cost. Two accelerometers are used in the multi-sensor device, one is fixed on the shin, and the other on the foot. Figure 3.1 shows the acceleration board and the exact placements of the two integrated accelerometers. This accelerometer employs polysilicon surface that allows measuring positive and negative acceleration along one axis. The measurement range of this accelerometer is ±3g. Each sensor consists of a movable center plate between two fixed plates, forming a capacitive divider. In the absence of acceleration the two capacitances are approximately equal. Due to the silicone surface, any applied acceleration causes a mismatch in the plates separation which results in greater capacitive coupling from the closer fixed plate. Thus, a voltage output can be detected on the center plate. It should be noted that for the shin acceleration sensor,

Ali SAAD c GREAH -2016
the y-axis is in same the direction of motion. While for the foot acceleration sensor, the x-axis is in same the direction of motion.

Telemeter sensor

In this study, the used telemeters are the infrared proximity sensors GP2Y0A21YK made by Sharp. This type of sensor detects distances between 10 and 80 cm with voltages between 3.2 and 0.4 V. Two telemeters are integrated, the 'upper telemeter' which is the one far from the foot, and the 'lower telemeter' which is the one near the foot. Figure 3.2 shows the position of the two sensors on the leg. The distance between the two telemeters is about 30 cm. Telemeter sensors were used to measure the variation of the inter-foot distance during walking. Telemeters were placed on the inner part of the lower left leg, so that whenever a step is repeated the sensors will detect the instance that the legs are aligned along each other. This placement is very important for the sake of isolating FoG from normal gait. During normal gait, the expected signal of the telemeter is a short rapid increase of voltage whenever a step occurs. While during a FoG episode, and since the stride length of PD patients decreases significantly, the expected signal of the telemeter is a rapid increase of voltage but with extended time when compared to normal gait. Thus, using the telemeters we can asses the significant decrease in stride length of PD patients. From a PD expert point of view, this assessment is fundamental in the study of FoG detection. Other telemeters that can be used for this purpose are: AN1436 proximity sensor, pololu 38 kHz infrared proximity sensor and many others. This type of sensor is used because its output can be easily converted to distances. In addition, it is characterized with low cost, reduced size and power consumption. Yet, this sensor is good for applications that do not require high precision which is our case. Note that the exact measured distance between the two feet during an exactly defined timing is not required, and that only changes that occur in the signal provided by the telemeter sensors is enough to be used in this study.

Goniometer sensor

The goniometer is employed to the wearable device to measure the angle of the knee during the gait of PD patients. Thus, the variation of this angle during normal gait, and during FoG is observed. The type of goniometer used is the Vishay Spectrol Full 360 • Smart Sensor Model 601 HE. The measurement range of this sensor is 0 • to 360 • with output voltage range not less than 90% of the supply voltage. Therefore, the sensor is calibrated to give 1 v for 0 • , and 2.4 v for 90 • . The advantages of this sensor type are: (1) its self-contained package which provides an analog electrical output over a full 360 • without the need of external electronics. (2) Low power consumption.

(3) Nonvolatile output. These advantages make this sensor more effective

Ali SAAD c GREAH -2016
with less cost over the traditional encoders or potentiometers that measure the angle. The goniometer has been fixed on the leg using two adjustable neoprene supports, one on the thigh and the other on the shin. Figure 3.3 shows the integrated sensor and its placement on the knee. During normal movement patterns of PD patients, the expected signal from the goniometer is a periodic one that increases during each step and then decreases when the step is finished. On the other side, due to the shuffling forward or trembling in place behaviors that happen during FoG, it is expected that this periodicity will change, or it may be totally distorted depending on the severity of the FoG episode.

Simulation and experimental protocol

After studying the gait of PD patients, it is generally observed that they walk with short and hasty steps [Lewis 03] , and during a freezing episode their walk can be described as shuffling forward (the patient makes an effort to overcome the block and is partially successful but the steps are very small and rapid and no real step is taken) [Horak 92]. Consequently, the first use of our acquisition prototype was to acquire data from different gait modes:

(1) walking normally, (2) simulating the short steps of PD patients that is considered as the normal walking for them, and (3) simulating the shuffling forward of PD patients that occurs during their freezing episodes. Table 3.1 summarizes these test modes and their corresponding duration. Each of the below tests is repeated ten times with sampling frequency of 100 Hz. In the last test mode, different gait behaviors are simulated simultaneously c GREAH -2016 Ali SAAD (normal short steps, and FoG). Thus, it is important to label the acquired data points. This is done by observing each run, and selecting manually the five seconds of simulated FoG episode in each run. Therefore, all data points of the FoG episodes are labeled as '1' and the rest of the data points are labeled as '0'. The simulation data are used to conduct a comparative study between signals acquired from the three different gait modes (normal gait, short steps, and FoG). Moreover, the simulation data are used in our study to calibrate and learn our FoG detection algorithm. This is done due to several reasons: (1) The availability of a low number of PD patients, which impose us to save their data for validation. (2) The physical difficulties for PD patients to participate in a quite long and tiring learning phase. (3) Calculating all the required parameters of the detection algorithm from simulation data will generalize our algorithm so that it will not be customized to specific PD patients.

The second use of the multi-sensor device is to acquire data from real patients. Experiments took place in 'Neuro Science Clinic: Parkinson Memory and Movement Disorder Center', Beirut, Lebanon, under the supervision of the PD expert Professor Paul Bejjani and his clinical specialists. Ten patients (seven males and three female) participated voluntary. All patients are diagnosed with PD without evidence of other form of Parkinsonism (dementia, multiple system atrophy, and progressive supranuclear palsy) [Tison 97] and with history of FoG episodes. After understanding the study and the test protocol, all patients agreed to participate anonymously in the tests. We designed a set of scenarios with different types of motor activities that patients are asked to perform. The chosen activities stimulate the occurrence of FoG (e.g. turnings, passing through narrow paths). Since patients will be Table 3.2 summarizes the demographic and clinical characteristics of the population of patients that participated in this study. These information are based on questions asked to the patients and on our personal observations. The total duration of the acquired data are 7,940 seconds (2 hours 12 minutes 20 seconds). Two among the ten patients did not freeze during acquiring their data.

c GREAH -2016

Ali SAAD The total number of freezing episodes that are acquired is 113 for the eight patients. The age of the PD patients varies between 46 and 79 years with average of 69.6 years and standard deviation of 13.5 years. The disease duration of the patients varies between 2 and 17 years with a average of 8.7 years and a standard deviation of 4.2 years. All patients were taking antiparkinsonian medications. The freezing events of most patients occurred as shuffling forward steps. One of the patients (P 7 ) showed freezing as a trembling in place FoG behavior. This patient enriches our dataset with different freezing behaviors, and will allow us to test whether the multisensor device will detect different freezing behaviors or not. During acquiring data, some patients spoke up 'I am freezing now!' during the occurrence of their FoG episodes. And they only overcome their freezing as the clinical expert encourages them verbally to take another step. Thus, we noticed that the freezing phenomena did not occur because of the PD patients muscle weakness, or any motor dysfunction. The acquired data are synchronized with video recordings that are captured during each test. Then with the help of the physiotherapist, FoG data were labeled for each patient as well as the state of the patient (e.g. walking, turning, standing, sitting etc.). Since our aim is to detect freezing during the gait of patients, unrelated data to the walking state have been removed from our datasets. Data are acquired from two groups of five patients, each of them with two sets of sensors. Patients are randomly picked for each group. The two groups undertook the same acquisition protocol and detection algorithm. The main difference is that they have different sensors configuration. The first configuration of sensors consists of 2 sensors (accelerometer and telemeter). For the second configuration of sensors, three additional sensors are added. Thus this set consists of five sensors (goniometer, two telemeters and two accelerometers). The aim is to validate the choice of integrating multi-sensors to detect FoG with better performance. The first five patients of table 3.2 (P 1 till P 5 ) are the group patients that have sensor configuration one. They have an average age of 66 years, and an average disease duration of 9 years. From this group of patients 55 FoG episodes have been recorded. The two patients that did not freeze are from this group. It worth mentioning that both patients encounter freezing event more often in their daily life. On the other hand the last five patients (P 6 till P 10 ) of table 3.2 have sensor configuration two. The average age and disease duration of this group of patients are 73 and 8 years respectively. This group encountered 58 FoG episodes distributed on all five patients. The two groups are randomly obtained and due to the small number of patients a significant difference should be noticed in the average age and number of patients that did not encounter FoG episodes.

c GREAH -2016

Ali SAAD

Feature extraction

In this section, the simulation data are used to conduct a comparative study between signals acquired from the three different gait modes (normal gait, short steps, and FoG). The aim is to extract features that can separate the FoG class from the other modes (one against all). Therefore, each sensor signal is divided into several sub-segments, and time and frequency domain characteristic features have been computed using a sliding window with length of 2 seconds, and step size of 0.2 seconds. Table 3.3 summarizes the extracted characteristic features and their descriptions. The intention is to extract features with minimum complexity, to allow their implementation in a wearable computer for online FoG detection. The most simple and obvious features to be tested in time domain are the mean and standard deviation. Furthermore, we extracted standard frequency based features which are the mean frequency and the frequency power. As for the FI feature, it is extracted due to its importance in previous work. At this stage, test modes have been compared to each other to detect changes in the waveforms of each measured signal. Each sensor was studied separately, in order to extract the optimal features that may lead to detect FoG. These features (table 3.3) are extracted from each analogue output coming from the sensors. And then the most informative features are selected, which are the ones that showed a significant change of the mean of their distribution during FoG.

Raw data analysis

Upon visualizing and comparing the raw signals of the three test modes for each sensor, a change appears in the behavior of the signals during the FoG test mode. For instance, the goniometer signal shows a decreased duration between each step during FoG when compared to normal modes. In other words, the frequency of the variation of the knee angle signal increases during FoG. Moreover, the peak amplitudes of the goniometer signal decrease. This shows that during FoG, patients do not bend their knees in a normal matter. Instead, they make incomplete steps during a small period of time. Figure 3.5c shows a sample of the simulation data that represent the variation of the knee angle during FoG, these changes can be clearly noticed when compared to normal gait modes (figures 3.5a and 3.5b).

As for the signal acquired from the telemeters, FoG episodes are characterized by a deformation of the walking rhythm and step magnitude that leads to specific features in the telemeter sensor voltage measurements. In both short steps and normal walking modes (figures 3.6a and 3.6b) voltage peaks occur shortly, this shows that the patient is walking with complete steps. On the other hand, during FoG (figure 3.6c) the width of the voltage peaks increases while the time between different peaks decreases. This shows that the person is walking with incomplete steps, while legs are close to each other. This significant change in the telemeter signal allows more investigation to extract more features and analyze them. For example, one of the features that may have more accurate discrimination is calculating the duty cycle of each period of the signal which theoretically may lead to evaluate how dominant the high state is in the signal. Moreover, figure 2.7 presents the signals acquired from the accelerometers during the three test modes. These signals show that during FoG, the frequency of the acceleration signal increases due to the shuffling forward behavior patients during FoG. This coincides with the literature review. Figure 3.7c shows a sample of acceleration data during FoG, the increase of frequency is significant when compared to normal gait modes (figures 3.7a and 3.7b). After comparing the raw data of the three sensors, we can conclude that the acceleration data are not the only measurements that contain significant information about the occurrence of FoG. The knee angle and the inter-foot distance, that are measured by the goniometer and the telemeter respectively, also provide important information about FoG.

Features selection

In the previous section, we distinguished the importance of the integrated sensors and the significant change of the behavior of each sensor during FoG. The latter result allowed us to investigate state change detection algorithms that can be applied for the detection of FoG episodes. There are some popular state change detectors, such as the Exponential Weighted Moving Average (EWMA), the Cumulative Sum (CUSUM), and the Dynamic Cumulative Sum (DCS), that can be used for this purpose. The EWMA algorithm is used to detect an increase in the mean of a sequence of random variables. The EWMA estimator is essentially a way of forming a 'recent' estimate of the mean at time t, with older data being progressively down weighted [Ross 12]. The estimated mean will allow to make a decision whether a change occurred or not given a prior knowledge about the mean before the change and after it. The CUSUM is often considered as the best method for the online state change detection [Montgomery 09]. This algorithm is based on a recursive calculation of the logarithm of the likelihood ratios [ Mustapha 09]. At each time t of the signal, the sum of logarithms of the likelihood ratios is computed. The drawback of CUSUM algorithm is that it requires us to have a prior knowledge about the characteristics of the c GREAH -2016

Ali SAAD probability density function of the signal before and after the change. To overcome this drawback the DCS technique can be used. It is based on the local CUSUM of the likelihood ratios between two local segments estimated at the current time t [ Mustapha 09]. The two segments are two windows, situated before and after time t, and an estimation of the characteristics of the probability density function of each segment is calculated before computing the likelihood ratio between them. Although, in this section we do not intend to detect FoG based on the change of one feature. The aim is evaluate the effectiveness of each extracted feature with respect to its change during FoG. This is done by subjecting all features to a change detection test using a linear threshold. The aim is to check the accuracy of a specific threshold in classifying the feature points into freezing data or non-freezing data. This accuracy allows to select the most informative features that show significant change during FoG. Features that are listed in table 3.3 are extracted for each analogue output of the five sensors. We have one analogue output from the goniometer, one from each telemeter (upper and lower), and three (x, y, and z axes) from each accelerometer (shin and foot). In total, we have nine analogue outputs from which features are extracted using a rectangular sliding window of size 2 seconds, with step size of 0.2 seconds. The feature selection methodology is based on three steps.

Visualizing the distribution of features

For visualization purposes, the acquired data from the first three test modes (table 3.1) are concatenated next to each other to form three large vectors for each analogue input. Then, these vectors are transformed into feature vectors using the windowing technique. The total number of extracted features for each test mode is 45 features, which is the number of analogue outputs (9) multiplied by the number of features (5). In this approach, the three test modes are kept separated in order to visualize the change in the distribution of features. Starting by the goniometer signal, it is observed that the most important features that have a significant change in its values during FoG are the FI and mean frequency. Both features show a noticeable increase during FoG mode. Figure 3.8 shows the distribution of both features during the three test modes. For both upper and lower telemeter signals, the main characteristic feature that has a significant change during FoG is the mean.

Figure 3.9 presents the distribution of the mean feature for the upper and lower telemeters. The analysis of the accelerometer signals acquired from the shin shows that features extracted from the frequency components of the Ali SAAD c GREAH -2016 signal are important. Furthermore, on x-axis the FI and mean frequency show a very significant increase during FoG. Moreover, on y-axis the sensor provides only an increase in PSD power during FoG test mode. Finally, the z-axis shows a significant increase of the mean frequency during FoG. Figure 3.10 shows the distribution of informative features of the x-axis acceleration data. Furthermore, standard deviation and PSD power can be considered but with much less significance. The changes of all three indicators in the foot accelerometer during FoG are less than that in the shin accelerometer.

Selection methodology

In this approach, the simulation data of the first three test modes are concatenated next to each other. This step formed one vector that contains both freezing and normal walking data. Then, the windowing technique is applied to the data to extract all features. This approach is used to select the most informative features among the extracted ones. These features are the ones that made an abrupt change during FoG. In other words, we aim to select from the 45 extracted features the ones that make a significant increase or decrease when a sudden freezing episode appears. The flowchart presented in figure 3.11 describes the process in which the 45 set of features are reduced into a subset containing the most informative features. Each feature is treated individually. First, the feature is normalized to the range [0, 1]. Then, a linear threshold is set to classify whether FoG is present or not. This threshold varies from zero to one, and for each value the classification accuracy 1 is calculated. Thus, depending on the threshold value, different accuracies are computed for a single feature. Then, only the maximum classification accuracy for a this feature is saved. The procedure is repeated for all 45 features. As a result, each feature will have a maximum accuracy that reflects the significant change that happened to it during FoG. The last step is to select the top features that yielded classification accuracy greater than 80%. These features are considered to be the most informative features.

Validation of features

In the previous section, a subset of features is selected and considered as the most informative features. In this section, this subset is tested for validity. For this purpose, the fourth test mode (table 3.1) is employed. Figure 3.12 shows the signals of all sensors during one run of the fourth test mode. Only the subset of features are extracted from the signals of this test mode. The aim is to observe the ability of the informative features to detect the appearance of FoG episodes when it is merged with normal gait mode. The threshold of each feature is tested on the new signals, and the one that provides accuracy less than 80% is eliminated from the study. The remaining feature are the ones selected for the FoG detection algorithm. Figure 3.13a shows a significant increase of the mean frequency for the goniometer when an episode of FoG occurred. As for FI, it is noticed that all previous studies applied this feature only on acceleration sensors. But our result shows that this feature can be used to detect FoG using the goniometer also. Signals of both upper and lower telemeter sensors showed a significant change of their mean during FoG episodes (figure 3.13b). This result is very advantageous especially in order to design a system for online detection of FoG, since the mean of the telemeter signal, which is a time domain feature, needs less computational time. Thus, an online detection system can be implemented with minimum latency period. For the shin acceleration data, the features that allow to detect FoG in both x and y axes are the standard deviation (time domain), PSD power and FI (frequency domain). It is worth mentioning that FI has the most significant change during FoG when compared to the other two indicators (figure 3.13c). On the other hand, z-axis of the shin accelerometer shows less significance when compared to the other two axes. With respect to the foot accelerometer (figure 3.13d), FI is the best indicator that can be used to detect FoG. Furthermore, standard deviation and PSD power can be considered but with much less significance. The changes of all three indicators in the foot accelerometer during FoG are less than that in the shin accelerometer. To conclude, positioning the accelerometer on the shin is better than placing it on the foot. Table 3.4 lists the most informative features obtained after following the feature selection steps. As a result, 13 features from the different integrated sensors are qualified and selected to be used in the FoG detection algorithm. These features represents the selected ones using sensor configuration two. For configuration one, this list reduces since all features coming from the goniometer, the upper telemeter and the foot accelerometer are eliminated. As a result, for configuration two the number of features are reduced to 5 features.

Principal Component Analysis

Data combination is an essential task in our study in order to extract the most significant components of the features. The aim of this step is to combine the above mentioned indicators using the PCA technique. This technique is quite old [Pearson 01], but it is still one of the most used multivariate techniques today. The central idea of PCA is to reduce the dimension of a data set consisting of a large number of variables, without losing too much information. As a result, new attributes will be discovered, called the Principal Components (PCs) that will be introduced to the FoG detection algorithm. Other alternatives to PCA are Exploratory Factor Analysis (EFA) and Fischer Discriminant Analysis that could also be used as variable reduction techniques [Ghravian 13] [ Grimm 02]. In our case, PCA is selected since it is not important to determine the correlation among the observed variables, which is done using the other methods. The objective is simple, just combine and reduce multidimensional data to a lower dimensional data while retaining most of the information. Another important advantage for using PCA in our case is the decreased requirements for capacity and memory. This allows the implementation of the algorithm on a wearable computer with minimum complexity. The calculation of PCs is based on the eigenvectors and eigen values of the covariance matrix. Note that there is a drawback that comes with using the PCA method, which is the sensitivity of the PCs to the units of measurement. This drawback may be very important since the extracted attributes are collected from heterogeneous sensors and have different units of measurement. To overcome this drawback it is preferable to use the PCA from the correlation matrix. Thus, avoiding the arrangement of the PCs according to the size of the variances of the original data [ Jolliffe 02]. For correlation matrices, the standardized variables are all dimensionless and can be combined to give suitable PCs scores [Legendre 83].

PCA using simulation data

This section describes the undertook methodology to compute the PCA from the simulation data. It also highlights which parameters are kept to be used in calibrating the clinical data. Let A be a m×n matrix of real numbers where m is the number of variables (13 features in our case) represented by (x 1 , . . . , x m ) and n is the number of realization from these variables.

A =       x 1 . . . x m       (3.1)
To work with PCA properly, it is common to re-center the data so that the mean is zero. This is done by subtracting the mean µ from each of the data dimensions. µ is a vector that contains the mean of all m variables. Let B be the re-centered m × n matrix.

B =       x 1 -µ 1 . . . x m -µ m       (3.2)
The next step is to calculate the covariance matrix C from B. This is accomplished by using equation (3.3). The resulting matrix B is a m × m matrix, in which B T is its transpose. Moreover, the ratio (1/(n -1)) is used for normalization purposes.

C = 1 n -1 BB T (3.3)
As mentioned earlier, we tend to use the correlation matrix since the variables in use are of different scales. First, we should have the variance of each variable. This can be done by using the diagonal values of C that gives a vector (denoted by var) which represents the variances of all variables. Then, we divide each element of the covariance matrix C with the square root of its corresponding values in vector var as shown in equation (3.4). The variables i and j belong to the subset {1, 2, . . . , m}.

R(i, j) = C(i, j) var(i)var(j) (3.4)
The following step is to compute the eigenvectors and eigenvalues from the correlation matrix R. Since R is symmetric (meaning R T = R), then there exist real numbers λ 1 , . . . , λ n (the eigenvalues) and orthogonal, non-zero real vectors (v 1 , . . . , v n ) (the eigenvectors) such that for each i = 1, 2, . . . , n:

R.v i = λ.v i (3.5) Ali SAAD c GREAH -2016
The eigenvectors with the lowest eigenvalues bear the least information about the distribution of the data. Therefore, the first principal component is the eigenvector which has the largest value of λ. The second principal component is the eigenvector which has the second largest value of λ, and so on. Thus, the eigenvectors (denoted by v) should be sorted from highest to lowest corresponding eigenvalue (denoted by λ). Let D be a m × m matrix in which its columns contain the sorted eigenvectors, and e be the array that contains the sorted eigenvalues. In order to decide which eigenvectors(s) should be dropped from matrix D, the percentage of the total variance explained by each principal component (denoted by f ) is calculated. This is done using the using equation (3.6): Figure 3.14 represents the percentage of explained variance in each principal component. It is obvious that the first two PCs that contain about 87% of the information are the most important components. Thus, we will keep the first two components and drop out the rest. These two components are saved and used later to project the clinical data (i.e. data from real PD patients) into the plane (P C 1 , P C 2 ).

f j = e j
The final step in PCA is to the project original data (13 features) using the first two PCs. Let matrix G be a m × 2 matrix consisting of the first two columns of D. Thus, the projected data (denoted by P ) can be computed using equation (3.7):

P = G T × B (3.7)
The resulted matrix P = (p 1 , p 2 ) is a 2 × n matrix, in which each row represents the combination of the 13 features with minimum information loss.

After applying the PCA technique to the FoG simulation dataset, the data are normalized in range [0 : 1] × [0 : 1]. The normalized data (denoted by N ) are computed using equation (3.8) such that i = 1, 2 and j = 1, . . . , n: Using simulation data (test mode four), the 13 extracted features from the second group of PD patients (sensor configuration two) are introduced to the above described PCs computational procedure. Figure 3.15 shows the distribution of the first two PCs in a plane (P C 1 , P C 2 ). On the other hand, for the first group (sensor configuration one) that used a reduced set of sensors, the 5 extracted features from the simulation data are introduced to the PCA computation process. The resulted PCs are shown in figure 3.16.

N (i, j) = P (i, j) -a i b i -a i (3.
It is observed from figure 3.15 that for sensor configuration two, the normal data in both components are distributed near the origin (0, 0). For sensor configuration one(figure 3.26), the normal data are distributed near the point (0, 1). It is also noticed that for configuration one, the distribution of the normal data have an increases standard deviation with respect to the normal data of configuration two. As for the freezing data, in both configurations the first principal component (P C 1 ) increases when a FoG episode occurs. As for the second principal component (P C 2 ), in configuration one the presence of a FoG event leads to a decrease in its values, while in configuration two the FoG event increases the values of (P C 2 ).

After computing the PCA for both sensor configurations, the sorted eigenvectors of the first two PCs are saved. As well as the normalization coefficients of the projected data. These parameters are saved so that they can be used to calibrate the clinical data before introducing it to the detection algorithm.

PCA using clinical data

Feature data from real patients are directly projected into the plane (P C 1 , P C 2 ) using the eigenvectors saved from simulation data. Moreover, the projected data are normalized into the domain [0, 1] × [0, 1] using the normalizing coefficients that are also saved from simulation data. The main purpose of calibrating the clinical data using parameters of simulation data, is to generalize the detection algorithm. In other words, the aim is to build a detection algorithm that is not patient dependent. This is important while studying the FoG phenomena, since every patient has a unique pattern of walking and freezing. The resulting PCs for the different patients will be thoroughly investigated in the next chapter.

Conclusion

In this chapter we have introduced the design of the wearable multi-sensor system that is able to acquire data from PD patients. New sensors in the field of FoG detection are integrated in our system: particularly, the goniometer that measures the angle of the knee and the telemeter that allowed measuring the variation of the inter-foot distance, which is a novel measurement in the evaluation of gait for PD patients. The multi-sensor device is used to extract both simulation and clinical data. The clinical data are acquired from 2 groups of 5 patients each having 2 different sets of sensors. One configuration contains a reduced set of sensors with respect to the other configuration. The importance of the integrated sensors is highlighted by initiating a comparative study between the raw data of each sensor during FoG and normal gait modes. From all the sensors, we have extracted optimal features that made a significant change during FoG. It is shown that at least two features of each of the utilized sensors can be used for detection of FoG. Due to the complexity of FoG episodes, the optimal features are then combined using PCA technique. Using the PCA of simulation data we have saved parameters that are used to calibrate the clinical data. This is done to generalize the detection algorithm. The two PCs explained about 87% of the whole data.

In the next chapter, the combined data via PCA are introduced a new method to detect FoG in PD. The FoG detection algorithm is based on a soft computing technique. Detection performances are highlighted and discussed.

Introduction

After collecting signals from the two groups of patients, the data are subjected to feature extraction, then the extracted features are combined using the PCA technique as discussed in the previous chapter. The aim of collecting data from two different groups having different sensor configurations is to prove that the utilization of extra number of sensors, especially the telemeter and the goniometer, can improve the on-line FoG detection performance. In this study we are interested in detecting FoG using artificial intelligence methods. Thus, we have treated FoG detection as a classification problem, and integrated a soft computing technique to detect FoG, which is the GNN method. The proposed detection algorithm is developed in the previous works by our group [Barakat 12][Sidibe 13] and adapted for FoG detection. This method is a new detection algorithm in the field of FoG detection. The GNNs have some advantages over other artificial neural networks:

-They can automatically adjust the number of neurons to reflect the complexity of the data to be separated. -They generate easily non-linear separators between classes.

-They present a fast learning ability.

-They require fewer weights for obtaining the same accuracy.

-They can build small networks [Vikas 11].

-They have an autonomous adaptation process.

-They are able to take into account new data.

Gaussian Neural Networks

The GNN classifier has one input layer with two linear nodes, one hidden layer composed of N c Gaussian nodes, and one output layer with N c output linear nodes (figure 4.1). The GNN learning algorithm is simplified by fixing the structure instead of adding additional nodes during the learning process. The input data for the GNN are the first two PCs that are extracted from the optimal features of the different sensors after being normalized to the domain

[0 : 1] × [0 : 1]. G 1 G 2 G Nc

Input nodes Hidden nodes Output nodes

Class 1

Class Nc The use of GNN is motivated by the ability to approximate non-linear parametric fields, and because the separations of the Gaussian surfaces are either circular arcs or straight lines depending on the value of the learned Gaussian function parameters [Sidibe 13]. The idea is to use the learning PCs to represent each class (FoG/no-FoG) by a specific Gaussian function. The learning parameters of the GNN method are the Gaussian centers and dispersions. The two components that are calculated from the simulation Ali SAAD c GREAH -2016 data will be introduced as a learning dataset to the GNN in order to learn the centers and dispersions of the Gaussian functions that represent the data. The PCs calculated from the simulation data are saved, and used to project the new data (e.g. data from real PD patients) then introduced to the GNN as a testing dataset. The reasons to use simulation data for calibration and learning are (1) the few number of PD patients, which requires us to save their data for validation, (2) the physical difficulties for PD patients to participate in a long and tiring learning phase. The Gaussian functions are defined by equation ( 4.1):

G j (X (P )) = 1 d j √ 2π e - ||X (P )-c j || 2 2d 2 j , j = 1, . . . , N c (4.1)
where X (P ) is defined as the normalized PCs. N c is the number of activation nodes that correspond to the number of classes. c j and d j are respectively the center and the dispersion of the j t h Gaussian function. The parameters c j and d j are learned iteratively using a supervised learning classification algorithm for the GNN [Sidibe 13]. At each iteration, the misclassification rate of the classifier is evaluated by calculating the mean error of classification which is given by equation ( 4.2)

E m = 1 N c (N c -1) j=1,...,Nc k=1,...,Nc k =j E(j, k) (4.2)
where E(j, k) is defined as the proportion of samples of type j that activate the representative Gaussian function of class k.

Center learning

Initially the Gaussian centers are equal to the COG of the data for each class. The aim is to adjust these centers, so that each center will best represent the data of its class. Let g(X (P )) be defined as the most representative Gaussian function for the data sample X (P ), it is computed using equation (4.3), and thus the position of the center is updated with equation (4.4).

g(X (P )) = arg(max j=1,...,Nc {G j (X (P ))}) (4.3) ∆c g(X (P )) = α. C g(X (P )) -X (P ) N L (g(X (P ))) (4.4)

c GREAH -2016 Ali SAAD
where ∆c g(X (P )) represents the variation of the center C g(X (P )) , and N L (g(X (P ))) is the number of samples in the learning set, that belong to the domain of activation of the function G g(X (P )) , and α is a gain parameter selected by the user. The process stops when the center converges, or when the maximum number of iterations is reached.

Dispersion learning

Initially the dispersions are equal to the standard deviation of the data representing each class. This value is adjusted by using a simple trial and error measurement method because it is really difficult to evaluate the sensitivity of the classifier performance with respect to the standard deviation. The difficulty is that a small variation of the standard deviation for a single node changes the perimeters of all classes. Thus, the dispersion is increased or decreased in order to improve the discrimination between classes, and consequently to minimize the mean error E m . The dispersion is updated with equation (4.5):

∆d j * = γ.β * .d j * (4.5)
where γ is a gain parameter close to 0 selected by the user and the couple (j * , β * ) is defined in equation ( 4

New data classification

For new input X, P rob j (X) which is the probability of belonging to class j is computed using equation (4.7), and X is classified as class(X) = FoG or class(X) = no-FoG according to the maximum of the probability computed for each class.

P rob j (X) = G j (X) Nc k=1 G k (X) , j = 1, . . . , N c (4.7)
Furthermore a classification confidence coefficient is calculated after each decision. Since two classes (FoG and no-FoG) are considered, then there will be two Gaussian activation functions: (1) G 1 (x) having a center c 1 of coordinates (c 1x , c 1y ) and dispersion

d 1 . (2) G 2 (x) having a center c 2 coordinates Ali SAAD c GREAH -2016
(c 2x , c 2y ) and dispersion d 2 .Then the confidence coefficient can be computed using equation (4.8).

conf (x) = |D -R 1 |, if class(x) = FoG d 2 d 1 .|D -R 2 |, if class(x) = no FoG (4.8)
where X is a new classified point, D is the Euclidian distance between this point and the center of the Gaussian function associated to the FoG class. R 1 and R 2 are the radii of the FoG and no-FoG classes respectively. They are calculated using equation (4.9). The confidence coefficient is used to evaluate the belief of the classification for each new input. The ratio d 2 d 1 is multiplied to give a weight for the computed distance relative to the dispersions of each Gaussian function.

R 2 = 2d 2 1 d 2 2 log d 1 d 2 + (c 2 1x + c 2 1y )d 2 2 -(c 2 2x + c 2 2y )d 2 2 d 2 1 -d 2 2 + (c sx ) 2 + (c sy ) 2 (4.9)
where the coordinates c sx and c sy are computed using equations 4.10 and 4.11 respectively.

c sx = - c 1x d 2 2 -c 2x d 2 1 d 2 1 -d 2 2 (4.10) c sy = - c 1y d 2 2 -c 2y d 2 1 d 2 1 -d 2 2 (4.11)

Results with simulation data: Learning phase

The learning phase starts by introducing the normalized PCs that are computed from the simulation data into the GNN learning algorithm. This labeled data (FoG or no-FoG) are divided into two datasets in which one for learning and the other for validation. The 50-50 split sample technique is used, in which half of the data are assigned to the training and calibration sample and the other half is assigned to the validation sample. Yet the assignment of data are not random. It is controlled so that the FoG and no-FoG data points are equivalent in both training and testing samples. Then, using the leaning dataset the centers and dispersions of the two Gaussian functions are calibrated. The learning process is presented in the flow chart To evaluate these terminologies the following fundamental terms are used:

-True positives: equals to the number of true FoG points that are classified correctly. -False positives: equals to the number of true no-FoG points that are classified incorrectly as FoG. -True negatives: equals to the number of true no-FoG points that are classified correctly. -False negatives: equals to the number of true FoG points that are classified incorrectly as no-FoG. These terms are plugged in equations 4.12, 4.13, and 4.14 to compute the desired classification rates. Sensitivity refers to the ability of the classifier to correctly identify FoG data. While specificity refers to the ability of the classifier to correctly identify no-FoG data. Both terminologies are important to evaluate the performance of the detection algorithm. Having only a high sensitivity means that the data of patients will always be classified as FoG, thus the detection algorithm will be useless. On the other hand, accuracy refers to the ability of the classifier to decide correctly among all the cases of FoG and no-FoG. Table 4.1 summarizes the classification rates for each sensor configuration. The GNN classifier is able to detect the occurrence of all FoG episodes of simulation data for both configurations. The performances detailed in this section concern the misclassification rates calculated from the time measurements. It is noticed that using simulation data both sensor configurations yielded high classification rates. Yet, the most significant difference between both results is the increase of specificity when using sensor configuration two (increased number of sensors). In other words, both configurations are able to detect FoG data well. Yet, configuration two is able to identify non-freezing data better.

Results with clinical data: Testing phase

The collected data from the ten PD patients are introduced to the GNN classifier. In order to validate the importance of our multi-sensor system, and the benefit of increasing the number of sensors in FoG detection, we perform two experiments: (1) usage of the data collected from group one of patients and measure the FoG detection performances with sensor configuration one (two sensors); (2) usage of the data collected from group two of patients and compare the FoG detection performance with configurations one and two (with five sensors). Using the clinical data, the GNN detection classifier is also able to detect the occurrence of all FoG episodes for both configurations. Figure 4.5 represents the first two components of a sample of the data acquired from 5 patients with sensor configuration one, while figure 4.6 is for the same patients and the same data with sensor configuration two. The figures also represent the boundaries of the Gaussian functions that are learned from the simulation data. The class separation that appears in figure 4.5 is learned from the simulation data with configuration one, while the class separation in figure 4.6 is learned from the simulation data with configuration two. By comparing the figures of all patients, we notice the poor classification result in terms of false alarm with configuration one, and that increasing the number of sensors and features leads to a decrease in this false alarm and misclassification rates. This improvement occurred for all PD patients, which lead to a significant increase in the detection performance. Using configuration two, it has been noticed that the boundary of Gaussian function can clearly separate the FoG data from normal walking data. This proves that the acquired simulation data can be considered as an acceptable representation of the real patient data. In other words, this proves that the extracted features from the simulated data can be used for the analysis of patient data. Moreover, figure 4.7 shows the change of the classification belief coefficient with respect to time during two consecutive FoG episodes of one of the patients with configuration two. We noticed that in each false classification the confidence coefficient tends to reach the zero value. This information could be very beneficial in the implementation of our system for on-line FoG detection. In addition, the system refuses any short series of decision changes (0 -1 -0 or 1 -0 -1) with low certainty and in such cases maintains the last decision. This post-treatment generally increases the detection accuracy of the on-line system. Table 4.2 summarizes the GNN detection performance for the two groups of patients in the different experiments. Patients (P 1 till P 5 ) do not have performances for sensor configuration two since, as described in section 3.2, data are acquired from these patients using only a set of two sensors. Also, the sensitivity of patients (P 4 and P 5 ) could not be computed since these patients did not encounter any freezing episode during data acquisition. It is shown that most patients had a decreased performance when the selected sensors are reduced (configuration one). Knowing that every patient has different gait behavior and different way of freezing, and besides accuracy improvement, the main improvement while using sensor configuration two is the significant increase of specificity. This means that integrating extra sensors (especially the telemeter and the goniometer) improves the ability of the system to distinguish different normal walking patterns from freezing data. This illustrates the advantages of using a multi-sensor system. The average GNN classification rate is 0.7 for configuration one and 0.9 for configuration two.

Conclusion

We have described a new method to detect FoG in PD patients using a multi-sensor approach. The method is based on the GNN classification algorithm, which is previously implemented by our laboratory and it is adapted to a new field of application, which is FoG detection. The Gaussian activation functions of the detection method are trained using simulation gait patterns and considered as the learning data. Then, the classification algorithm is tested using clinical data (i.e. data from real patients). Moreover, a classification confidence coefficient is computed to reject any decision change having a low confidence. After comparing the detection ability if the GNN using two different sensor configurations, results showed (a) the efficiency of the overall multi-sensor approach in detecting the occurrence of the FoG episodes, since our it is able to detect all FoG events using both sensor configuration; (b) that increasing the number of sensors (sensor configuration two) increases significantly the FoG detection performance in terms of data classification rates. The average GNN classification rate is 0.69 when 2 sensors are used while it is 0.9 when 3 additional sensors are used. Furthermore, table 4.3 presents a comparison between our work and the previous studies that investigated FoG detection. Our detection algorithm is able to detect 100% of the FoG episodes for the ten patients with a significant classification rate c GREAH -2016 Ali SAAD compared to other works. One advantage of our work is that the results are not patient customized, since the learning process is completely separated from the testing process on patients. Thus our system can be generalized to accept new data from new patients.

In the next chapter, the simulation and clinical data are introduced to probabilistic models. Our implemented GNN detection algorithm will be compared to a well-known machine learning algorithm (i.e. Bayesian Belief Network). The aim is to employ a detection algorithm that will be less affected by the fault of sensors. Chapter 5

Freezing of Gait detection using Bayesian Belief Network Contents

Introduction

In this chapter, a graphical probabilistic modeling study for FoG is conducted. This study is based on the BBN formalism. BBNs are high-level representation of probability distributions over a set of variables that are used for building a model of the problem domain. Currently, attractive requests for graphical models, particularly in the form of BBN, can be found in many domains, such as finance (risk evaluation and stress test) [Rebonato 10] [ Meucci 08], network diagnosis [ Khanafar 08], and medical applications [Intan 11] [Sacha 02] [ Gong 09]. Another example of using probabilistic graphical models is integrating data from multiple sensors. This occurs in many applications, one such is integrating data of traffic from sensors placed on roads or bridges, weather information, and incident reports (figure 5.1). Based on the multi-sensor information a graphical model can be built that is trained from historical data and can be used to predict both current and future road speeds including roads where traffic data were not measured. This application is applied on several large cities with very good results [Koller 12]. Bayesian networks have several advantages over the different classification techniques (including the GNN method), stating some of them may point out:

Multiple traffic views

Weather

Incident reports

Learned Model

Road traffic information

-They are a marriage between probability and graph theory [ Murphy 98].

-They provide a natural tool for dealing with two problems that occur throughout applied mathematics and engineering; 'uncertainty and complexity' [Rose 90]. -The graph theoretic side of BBNs provides both an intuitively appealing interface by which humans can model highly-interacting sets of variables as well as a data structure that lends itself naturally to the design of efficient general-purpose algorithms [ Murphy 98]. -They allow replying any query (inference) given certain evidence, not restricted to classification function [ Murphy 98]. -One of the interesting things about BBNs is that they can be used to put discussions about causality on a solid mathematical basis [Huang 96]. -They are a surprising and principled solution for the most sophisticated problem in pattern recognition, which is incomplete or missing data; it estimates referring to probabilistic methods [Huang 96]. -Last but not least, Bayesian networks can incorporate both expert

Ali SAAD c GREAH -2016
and data knowledge into any problem domain [Duda 12]. Using BBN, we have addressed FoG through different approaches. In the first approach, the published data by [Bachlin 10] has been used to make an epidemiological causation study for FoG. Moreover, the published data is used to for FoG detection using BBN. In the second approach, the multisensor device is utilized and the acquired data from sensor configurations one and two are introduced to the BBN methodology for the detection of FoG. The aim is to make a FoG model based on the utilized multi-sensor device that will be less affected by the fault of sensors. Attributes of this model can be adjusted or weighted according to the expert knowledge. Moreover, this model can be used for diagnosing and forecasting issues.

Bayesian Belief Networks

A Bayesian network consists of two components: a qualitative component in the form of a Directed Acyclic Graph (DAG) which is the Bayesian network structure, and a quantitative component in the form conditional probabilities which are the Bayesian network parameters.

Bayesian Network Structure

The structure of a BBN is defined by two sets: the set of nodes (vertices) and the set of directed edges. The structure takes the topological form of a DAG, in which there are no loops [Duda 12]. Figure 5.1 presents an example of a simple BBN structure. The nodes represent random variables (features) that are drawn as circles (labeled by the variable name with upper case bold letters) and its associated states (in lower case). Thus node A has states a 1 , a 2 , . . . , denoted simply a. The edges represent direct dependence among the variables and are drawn by arrows between nodes. In particular, the edge from node X to node A represents a statistical dependence between the corresponding variables. Thus, variable X influences A. In other words, this edge represents the conditional probabilities P (a | x). Node X is then referred to as a parent of A and, similarly, A is referred to as the child of X.

A BBN reflects a simple conditional independence statement, which is that each variable is independent of its non-descendants in the graph given the state of its parents. This property is used to reduce, sometimes significantly, the number of parameters that are required to characterize the joint probability distribution of the variables. This reduction, provides an efficient way to compute the probability of a certain state of nature or a certain class given specific observables or features . In other words,

P (w | x) is c GREAH -2016
Ali SAAD computed such that w denotes the state of nature and x denoted the set of evident features. This probability is called the posterior probability [ Constructing the BBN structure can be done using the knowledge of an expert, data, or the combination of both. Their exists several structure learning techniques that can be used to learn a BBN structure from a given dataset. Several researchers have examined different approached for learning a BBN structure from data. In a special case were each node (variable) has only one parent, the authors of [Chow 68] provide an efficient algorithm that uses this prior knowledge to learn the BBN structure. Other researches like [Cooper 91] [Cooper 92] [Buntine 91] [Spiegelhalter 93] utilized a scoring metric and a search technique. The metric computes a score that is proportional to the posterior probability of a network structure, given the data and an expert prior knowledge. Moreover [Spirtes 93] built a solution method for the general (intractable) case based on independence tests. The most widely used algorithm is provided by [Heckerman 95] and is based on a hill-climbing search. Hill-climbing starts by the initialization of the BBN structure. The initial structure can be constructed from the expert knowledge, randomly built, or even by setting an empty structure. At each search step, it creates all legal variations of the current network obtainable by adding, deleting, or reversing any single arc, and scores these variations. The best variation becomes the new current network, and the process repeats until no variation improves the score[ Grossman 04]. Yet in this study, and based on the expert advice, the FoG phenomena is tackled using a restricted BBN that assumes all attributes are independent given the class node. Thus ,the structure

Ali SAAD c GREAH -2016
would be (as shown in figure 5.2) a root node affecting the rest remaining nodes. This simple form of BBN is called the Bayesian Naive Classifier (BNC) model. It should be noted that naive Bayes easily outperforms many unrestricted Bayesian network classifiers on a large sample of benchmark datasets [Friedman 97].

C

x 1 x 2 x 3 ...

Parameter learning

The simplest approach to learn the parameters (conditional probabilities) of a network is to find the parameter set that maximizes the likelihood that the observed data came from the model.

Likelihood -In essence, a BBN is used to model a probability distribution X. A set of model parameters θ may be learned from the data in such a way that maximizes the likelihood that the data came from X. Given a set of observed training data D = {x 1 , . . . , x N } consisting of N examples, it is useful to consider the likelihood of a model, L(θ) (defined in equation (5.1)), as the likelihood of seeing the data, given a model:

L(θ) = p(D | θ) = N i=1 p(x i | θ) (5.1)
It should be noted here that x i is the i t h training example and that the likelihood of D being generated from model θ is the product of the probabilities of each example, given the model. Maximum likelihood -The learning paradigm which aims to maximize L(θ) is called the maximum likelihood. This approximates the probability of a new example x given the training data D as p(x | D) = p(x | θ M L ) where θ M L is the maximum log-likelihood model which aims to maximize log(L(θ)) and is defined in equation (5.2). Where 'log' here refers to the natural log. And since the natural log is a monotonic increasing function, maximizing c GREAH -2016

Ali SAAD the log-likelihood is the same as maximizing the likelihood. This is done for computational simplicity.

θ M L = arg max θ N i=1 log(p(x i | θ)) (5.2)
This amounts to maximizing the likelihood of the 'data given model'. The maximum likelihood does not assume any prior. Since optimization algorithms typically search for minima rather than maxima. The equivalence of equation ( 5.3) for all x is used.

arg max x (x) = arg min x (-x) (5.3)
This equivalence allows us to look for the minimized negative log-likelihood rather than the maximized log-likelihood as presented in equation (5.4). Moreover, using the negative log-likelihood is equivalent to minimizing an error function.

arg max θ N i=1 log(p(x i | θ)) = arg min θ -N i=1 log(p(x i | θ)) = θ M L (5.4)

Inference

If we define 'knowledge' as relations between the variables that are valid whatever the situation, and 'information' as the facts describing a given situation, then the inference is what allows us to move from a model of knowledge and information to a conclusion [Naim 99]. Once the BBN is built (from the expert knowledge, data, or a combination of both approaches), any calculation of the probability distribution associated with this network is the inference. The calculation methods are more or less complex depending on the complexity of the graph, i.e. depending on the level of factoring of the probability distribution. Some inference methods calculate directly the various probability distributions of interest based on the Bayes theorem and the theorem of independence graph. Researchers [Howard 81] [Olmsted 83] [Shachter 88] developed inference algorithms based on the reversal of the arcs in the network structure. In these algorithms, each reversal of an arc is the application of Bayes theorem. Another famous inference algorithm (Message Passing) in trees and poly-trees is proposed by [Pearl 88]. To work with a graph rather than a poly-tree, [Lauritzen 88] [Jensen 90] [Dawid 92] have created an algorithm that transforms the Bayesian network into a tree (or tree Junction) where each node is a subset of variables in the network. The algorithm then operates several mathematical properties to the obtained tree for computing the inference requested (i.e. simply, using the algorithm of [Pearl 88] to the tree function). The complexity of this algorithm is exponentially depending on the size of a clique (i.e. subsets of adjacent nodes, Ali SAAD c GREAH -2016 also called complete subgraphs). Note that the algorithm of the tree junction is one of the most widespread in the tools of today. Thus, in our problem we use the junction tree engine, which is the mother of all exact inference algorithms. This algorithm gives an exact answer to the exact problem, while other approximated inference algorithms such as Monte-Carlo Markov Chains [ Robert 04], Gibbs sampling [Casella 92] and particle filtering [Gordon 93] give an approximated answer to the exact problem.

Published data analysis

In previous studies, Marc Bachlin et al. [Bachlin 10] developed a wearable assistant for PD patients that detects FoG by analyzing frequency components inherent in the body movements, using measurements from on-body acceleration sensors. The wearable device acquired homogeneous data (i.e. data from one type of sensors) from three acceleration sensors positioned on different body parts (ankle, knee and hip). Each sensor measures three components of acceleration (x: horizontal forward axis, y: the vertical axis and z: the horizontal lateral axis). The used detection algorithm was based on the principle illustrated by Moore et al. [Moore 08] that introduced a FI to evaluate the gait condition of PD patients. The FoG detection is performed by defining a freeze threshold, where values higher than it are considered as FoG events. Several recent studies like [Mazilu 12] [ Assam 14] [ Rezvanian 16] incorporated this published data to implement different FoG detection algorithms. Referring to the data obtained by Marc Bachlin et al. [Bachlin 10] from 10 PD patients, we used the BBN probabilistic model in order to (1) study the causal relationship between FoG and the extracted feature (FI) and (2) to evaluate the ability of the BBN to detect upcoming FoG episodes using this data. The data are composed of separated files for each patient, although some patients have multiple files for each test done. Each file is composed of a matrix that contains measurement data of the three sensors in x, y and z directions. The last column contains the annotation, weather FoG occurred or not. These annotations was labeled by synchronizing the data by a video that recorded each patient run, which allowed to identify the exact start times, durations and end times of FoG episodes. The FI for each acceleration measurement is calculated, using a sliding window that calculates the FI of 256 acceleration samples. Then we calculated the magnitude of the three FIs components for each sensor. Accordingly, all measurements taken are represented in a low dimensional dataset, that is ready to be introduced to our proposed machine learning model.

c GREAH -2016

Ali SAAD

Epidemiology of causality for FoG

Inferring the causal structure of a set of random variables is a challenging task. In the causality domain, the variables of interest are not just statistically associated with each other, yet there is a causal relationship between them. The famous phrase 'correlation does not imply causation' is recognized and seems approved by researchers in empirical and theoretical sciences. For example, in analyzing a demographic database, we may find that the attributes representing the number of hospitals and the number of car thefts in a region are correlated. This does not mean that one causes the other. Both are actually causally linked to a third attribute, namely, population 1 . Formerly, authors in [Spirtes 90] quoted that 'one of the common aims of empirical research in social sciences is to determine the causal relations among a set of variables, and to estimate the relative importance of various causal factors'. Recently, the philosophical wise of this quote is broadly discussed, specifically in the medical and health science, more precisely in the context of symptoms/disease episodes [Russo 07] [Frumkin 06] [Lagiou 05] [ Thagard 98]. In particular, Lagiou et al. [Lagiou 05] (page 565) mentioned that: 'A factor is a cause of a certain disease when alterations in the frequency or intensity of this factor, without concomitant alterations in any other factor, are followed by changes in the frequency of occurrence of the disease, after the passage of a certain time period (incubation, latency, or induction period'. In order to highlight the causal trends of our FoG problem, and from an epidemiological point of view, explicitly we will illustrate the FoG Model by applying what so-called Hill's Criteria of Causation [Hill 65], which is an old approach that outlines the minimal conditions needed to establish a causal relationship between two items. Hill's work has been validated by, Kundi [Kundi 06] as a valuable tool, since both mechanistic and probabilistic aspects were considered. Kundi applied Hill's criteria to the classic case of smoking and lung cancer. The first step for examining our causal proposal was to test if our study is consistent with Hill's criteria.

Table 5.1 summarizes the nine criteria defined by Hill and the resulted observations after applying it to the FoG\FI case. It can be clearly observed that not all of the criteria hold in our case, where the 'plausibility' and 'analgy' criterion weren't applicable. On the other hand, the other criteria weren't as satisfactory as expected. Thus, this methodology did not validate the causality behavior between FI and FoG. Next, we will build a specific BBN, by assuming that a simplest structure exist between variables and FoG, and we will study the FoG episodes via a traditional way of classification using BNC, which is one of the most effective and popular classifiers in data mining techniques [

Criterion

Observation in the FoG\FI case Strength of association During FoG episodes, FI has significant higher values with respect to the normal gait of PD patients Consistency Several studies were applied on different patients, which produced the same results. The relationship also appeared for different genders Specificity in the causes FI is one of the clinical features (not the only one) that can be used to predict FoG

Temporality

FoG in the vast majority of cases occurs when the FI increases

Dose Response Relationship

Extracted data showed that there is a direct relationship between the value of the FI and the occurrence of FoG episodes Theoretical Plausibility

We don't have an explained biological theory stating a theoretical relationship between FI and FoG

Coherence

The conclusion (that accretion of FI causes FoG) made sense given the knowledge about the algorithm for calculating the FI with respect to FoG occurrence Experimental Evidence

The experimental data collected clinically from patients made certain that FoG occurs when the FI increases Analogy In this case, contrasting similar phenomena could not be applied, due to the fact that the approach of detecting causality of FoG is novel.

FoG detection using published data and BBN

The first step of our learning protocol is to split the obtained data, some for training our classifier and others for testing it. For the learning, nine different datasets for nine different patients are chosen in order to build for each patient a BNC model. As for testing, the remaining dataset that corresponds to either for new patients (different from the nine patients used for learning), or to same patients but in a different run of the experiment. Each BNC model (figure 5.4) holds the class node (FoG), which is the parent of the three FI nodes. The nine BNC models differ by their conditional probabilities that are learned from the training sets introduced to the BNC model. The learning experiments were conducted with a random 10-fold To evaluate the performance of the BNC classifier the terminologies (accuracy, sensitivity and specificity) that are defined in section 4.2 are computed. The BNC classifier performance is evaluated using four datasets that were left for testing purposes. The testing results of each dataset can be summarized by calculating the average accuracy, sensitivity and specificity computed from the learned models (table 5.2). We can see that our system's accuracy is about 0.67 with sensitivity 0.59 and specificity 0.69. Because of the different freezing behaviors for patients some testing results were not as good as expected. Yet we argue that given the knowledge that the published data contain measurement from a single type of sensors (accelerometers) the BNC classifier showed promising results and the detection performance may significantly increase when applied to our multi-sensor device. the GNN algorithm. Thus, we also have two groups of patients, the first group of five patients used sensor configuration one (two sensors). While the second group of five patients used sensor configuration two (five sensors).

The BBN model that have been built for FoG detection is shown in figure 5.5. The nodes represents the random variables that are PCs (the linear combination of the 13 extracted features) and the class variable (FoG or no-FoG). While the links, with a specific direction, represent the correlation influences between the nodes. This type of BBN model is the BNC that assumes the attributes (PCs) are independent given the classification node (FoG). This model is used for all ten patients. In the work of section 4, the parameters that were learned using simulation data were the centers and dispersions of the Gaussian functions. In the BBN work, the learned parameters are the conditional probabilities between each node of the BBN model.

PC 1 PC 2

FoG Class

Figure 5.5 -The BNC model that is used for the 10 PD patients using the multi-sensor device.

Figure 5.6 presents the learning process of the simulation data, as well as the testing process of the clinical data using the BBN formalism. The process starts with loading the simulation datasets, then the data entered is discretized from continuous real numbers to histogram integers based on the algorithm proposed by [Colot 94]. This technique is based on Akaike Information Criterion and is successfully implemented in different classification problems [Song 11] [ Gacquer 11]. Then, the DAG is specified, by setting the edges between nodes. The DAG is used to draw the structure of the model. After that, the conditional probabilities between the linked nodes are learned using the parameter learning algorithm discussed in section 5.1.2. The learned parameters from simulation data are saved. The testing process starts by loading the data from each patient. This data are also discretized using the same methodology. Then, we infer the probability of a data point belonging to FoG or no-FoG, where a data point is classified according to the maximum posterior probability obtained. So we decide FoG if P (F oG | evidence) > P (no -F oG | evidence) else we decide no-FoG. Thus, for each patient the BBN classification rates are computed. Table 5.3 presents the FoG detection performances for the ten patients using the BBN model.

Testing process

Learning process

Repeat

Compute classification rates

Figure 5.6 -The learning and testing process of the BBN using the multi-sensor device.

Ali SAAD c GREAH -2016

The BBN classifier is able of detecting all FoG episodes. For sensor configuration one, the average detection accuracy is 0.65 which is approximately similar to the accuracy of GNN classifier (0.7). While for sensor configuration two this average increases to 0.8 which is also nearly equivalent to the GNN classifier (0.9). Thus, the increase of performance is more or less similar to the results accomplished through the GNN method. Thus also by using the BBN algorithm, increasing the number of sensors by utilizing a telemeter and a goniometer yielded an increase in the detection performance significantly. As mentioned in section 4.4 the average classification specificity of the GNN detector significantly increased when introducing extra sensors (from 0.55 using configuration one to 0.82 using configuration two). While the sensitivity remained high in both cases (0.92 for configuration one and 0.94 for configuration two). In the BBN case a different behavior appeared, since both rates (sensitivity and specificity) are equivalent in configuration one (0.68 for sensitivity and 0.67 for specificity), and they both coherently increase when increasing the number of sensors (0.87 for sensitivity and 0.84 for specificity). This shows that the in both configurations the BBN classifier has the ability to distinguish both FoG and no-FoG data equivalently, yet increasing the number of sensor increases both rates. On the other hand, using the GNN classifier, increasing the number of sensors positively influences the ability of the system to distinguish no-FoG patterns from freezing data.

Conclusion

We have described ways for modeling the FoG phenomena of PD patients based on the BBN formalism by following different approaches. We have used a published FoG datasets that contain data acquired from real PD patients while walking and while encountering freezing events. The first approach is to study the causality in the FoG/FI system, this is done by making an epidemiological study for a possible causal model for FoG. This approach resulted in weak or no answers of causality in FoG/FI system. Although, this can be further evaluated in future by applying different causality search model in BBN formalism, this can be combined with an epidemiological study to assess the causation. In this perspective we may construct an influence diagram that fits the expert causal model in the framework of FoG, hence we possibly will generate understandable explanations of the FoG causal structure. In the second approach, and using the published dataset that contains homogeneous data, a BNC model is built for different patients. This approach showed a fluctuating percentage of accuracy, sensitivity and specificity. Using the published data, the BNC classifier had the ability to detect FoG event with an average accuracy of 0.67. The final approach is to utilize the multi-sensor into the BBN algorithm. Results showed that BBN detected all FoG events using heterogeneous data (unlike the homogeneous data of the published datasets). Also, results showed that the FoG classification rate improves when extra telemeter and goniometer are utilized. This meet up with the results of the GNN algorithm. Yet, the BBN model can be extended to take into account more attributes that are related to FoG. One important attribute is the status of the patient during his/her walking (e.g. standing, walking, turning, etc,...). This new attribute is important knowing that different walking behaviors of PD patients may provoke the occurrence of FoG events. Moreover, since each patient freezes in a different pattern, the utilized BBN model can be used beyond FoG detection. For example, using the BBN model we can infer the probability of a patient having a specific pattern of acceleration (telemeter, or goniometer) given that this patient is encountering a freezing event. Thus, we can diagnose for a specific patient what is the most affected sensor during FoG.

In the next chapter, we will present methodologies for the diagnosis of the main behavioral syndromes for PD with BBN and the ways to extend our work and build a global system that is able to embrace new symptoms especially FoG and others for diagnosis purposes.

Introduction

Patients having PD encounter problems with balance, walking (FoG) and speech and more as detailed in section 2.1. These symptoms are collectively known as axial symptoms [ Bejjani 00]. PedunculoPontine Nucleus (PPN) is a brain-stem locomotive center which is involved in the processing of sensory and behavioral information [Hamani 10]. Research work over the past 20 years has indicated that modulation of the activity of this area in the brainstem, the PPN, is beneficial in the treatment of axial symptoms [Mazzone 05] [ Khan 09]. Moreover, the PPN has been highlighted as a DBS target for the treatment of freezing of postural instability and gait disorders in PD and Pro-gressive Supranuclear Palsy [ Factor 08]. Relying on these facts and expert 1 guidance, we assumed that there is a physiological structure related to PPN in the brain that influences these symptoms. This study was initiated by including two symptoms among the rest that are the handwriting and speech symptoms. From a modeling point of view, we used a Graphical Probabilistic Model, more specifically a BBN to represent this physiological structure as a Hidden Variable that links the handwriting and speech skills of PD patients with each other. This methodology is previously is previously used by [Zaarour 04a] for discovering handwriting strategies of primary school children. In this study, the hidden variable is evaluated according to handwriting and speech measured features that are collected from PD patients via a particular experimental protocol. The aim is to identify patterns, by clustering PD patients according to their handwriting and speech skills. The discovered clusters represent a coherent unity that is more easily identifiable and more informative at the level of writing and acoustic features. Hence, this research aims to make an inductive study to discover a hidden prototype for a global structure that includes these skills and is able to embrace new PD symptoms such as FoG. In other words, the aim of this research it to propose a global structure based on the BBN formalism for the diagnosis of PD symptoms. This structure allows the creation of an inference tool to infer for specific characteristic of handwriting, speech, FoG, and more. The discovered prototype can serve as a fundamental reference for future critical assistance, such as a motor diagnostic tool based on different skills of PD patients.

Experimental protocol

A total of ten patients diagnosed with PD (eight males and two females) were recruited. Handwriting and speech data have been collected separately from each patient. Most patients have not performed any voice therapy for at least one month prior to data acquisition. None of the patients undertook surgical implementation of DBS. Table 6.1 summarizes the clinical features of the ten patients that participated in this study. The mean ± standard deviation of the age and duration for the disease were represented respectively: 64.9 ± 12.72 and 6.8 ± 4.96. All patients have taken oral medication before performing the test. The occupation of patients is detailed since it is used in the interpretation of the obtained clusters. The equipment used in the acquisition of the handwriting data is the digitizer tablet (Wacom Intuos2). For measuring the kinematic features of PD patients, four traces are proposed by the neurology expert:

-Trace ( ): An axiomatic trace that should be written fifteen times in a cursive pattern; which requires repetition of a counter clockwise loop progression to the right. The patient should try to write the whole trace with one stroke. -Trace eight (8): This trace obliges patients to make a counter active movement that makes writing this axiomatic trace more complex than trace . It should be written ten times horizontally. Patients should trace each character spaced out such that characters would not be connected. -Trace infinity (∞): It should be written ten times vertically. It is similar to trace eight, but it shows higher level of complexity due to the presence of mental rotation imposed by the patient while writing. -Trace phrase: The phrase is 'the killing bullet is fast'. The patient is being asked to write this phrase five times in a cursive pattern. The fifth phrase was used for the survey. Hence this test is considered as a kind of hand motor physiotherapy. Figure 6.2 shows a handwriting sample of different PD patients taken in the clinic while following our experimental protocol. It can be deduced from figure 6.2a that the hand of the patient was shaking while writing the cursive letter , which is an obvious sign of tremor in PD. While figure 6.2b shows the inability of a patient to continue the axiom loop of number 8. As for figure 6.2c, it is well noticed how the size of each word is decreasing progressively.

c GREAH -2016

Ali SAAD This is a great indication of micrographia in PD.

On the other hand, the acoustic feature measurements of the PD patients have been done by quantifying several vocal phonations. Using a noisecanceling microphone, patients were asked to emit a sustained vowel (a) and a short sentence in Arabic language. Then, they were requested individually to hold steady the frequency of phonation for as long as possible in a quiet room. The captured vowel was repeated five times where the fifth signal was analyzed. As for the phrase, it was repeated three times where the third signal was analyzed. The repeatability of the signals is done because of the fact that the patients show symptoms of fatigue after repetition, thus the acquired parameters will be more observable.

Extraction of handwriting and speech features

The extracted kinematic parameters that fit to the characteristics of different handwriting traces are the mean velocity, fluidity, fluency, mean pressure, pause in duration, and the number of strokes. These features are extracted using a special interface between the tablet and the computer. This program was developed by [Zein 10] using the C Sharp language. As for the acoustic features, four features were extracted from the vowel including the Maximum Phonation Time (MPT), frequency perturbation (jitter), intensity perturbation (shimmer), and Harmonic to Noise Ratio (HNR). While the Standard Deviation of the Intensity (SDI) and the voice breaks were extracted from the phrase. We applied the Praat software package which has been widely and recently used [Rusz 11] [Little 09] as speech features extractor, and specifically as a PD speech diagnostic. Table 6.2 summarizes the description of all the extracted features for both handwriting and speech of PD patients. These features are used later in the clustering and modeling techniques using the BBN formalism.

Feature Description

Handwriting features

Mean velocity

The mean of instantaneous velocities of the patient's trace during the test

Fluidity

The average number of inversions in velocity peak per stroke. This feature represents the movement fluency of the patient during the test

Number of strokes

The number of times the patient writes a complete mark across the tablet, (i.e. the number of times the pen is removed and placed over the tablet)

Pause duration

The average duration of each pause in context done by the patient

Mean pressure

The mean pressure exerted by the patient on the tablet during the test

Acoustic features

Shimmer and Jitter

The frequency and amplitude stability of the patient voice

HNR

The ratio of the energy of the harmonics over the noise energy present in the voice. It can be referred as the degree of hoarseness MPT

The strength of the voice SDI The variation of the patient's voice intensity

Clustering using Bayesian Belief Networks

Based on the BBN framework, we have modeled our problem using the Hierarchical Latent Class (HLC) models anticipated in [ HLC models are tree-structured BBNs where leaf nodes are observed whereas internal nodes are hidden. We represented the physiological brain structure (i.e. the PPN) by a hidden variable that influences both handwriting and speech measuring variables. The fundamental hypothesis published by [Zaarour 03] [Zaarour 04b] assumes that if features of writing (or any other assessed skill) of a set of pupils (PD patients in our case) are similar with respect to a given metric, then these pupils nearly share the same handwriting pattern. Therefore, a part of our work aims at identifying and studying patterns by clustering PD patients according to their different skills that are related to PD symptoms.

We used the Expectation-Maximization (EM) algorithm, which is a broadly applicable approach to the iterative computation of maximum likelihood estimates, useful in a variety of incomplete data problems [McLachlan 09] [Han 06]. Typically, the bottom layer is the visible one, containing the observable data variables, and the top layer is the hidden one, representing latent variables. The EM algorithm is a general method which can be used to obtain maximum likelihood estimates of the parameters of a Bayesian network for a given training dataset. The EM algorithm works even when the dataset is incomplete or has missing values. In other words, The EM algorithm can be used in the context of data re-building. This is beneficial to the domain of diagnosing the fault of sensors in the FoG multi-sensor device. Yet, missing values are not only encountered in problems where there are limitations in the data gathering process, but rather they occur more frequently in situations where there are hidden or unobserved variables in the system. The hidden variable could be the class itself to which these sets of data belong, which is the case in hand (unsupervised classification). There is no justified theoretical selection criteria for BBNs with latent nodes in particular the HLC models [Wang 04] [Zhang 04a]. The challenge is that both the BBN structure and the number of clusters partially depend on the neurologist expert knowledge, and the parameters (i.e., conditional probabilities between children and their parents) are estimated by the EM algorithm. The missing data in this challenge are hidden variables treated as a new unlabeled pattern in the outline of unsupervised learning (i.e., clustering).

EM algorithm steps

P (X = x i ) = N X=x i n j=1 N X=x j (6.1)
Where N X=x j represents the number of training data points in which the variable X assumes the state x j . Note that the denominator of equation (6.1), above, is equal to the total number of data points. So the maximum likelihood estimate for P (X = x i ) is equal to the percentage of data points in which the state of variable X is x i .

Clustering results

The followed modeling procedure consists of two consecutive clustering approaches: (1) clustering patients according to each PD symptom to form local models, (2) clustering patients after connecting each local model to a global structure that contains a new latent class.

Local models

The choice for the speech local model consists of four features: Jitter, HNR, MPT, and SDI. The non-naive structure shown in figure 6.3 is suggested by the expert. The clustering results and the common characteristics of each cluster for the speech local model are summarized in figure 6.4. The expert indicated that patients in cluster one (C 1 ) have more voice strength than in cluster two (C 2 ), since their MPT is longer. Also, from the expert point of view, whether patients have low or high SDI (C 1 ), they are more likely to control their voice levels better than those in C 2 that have medium SDI. Moreover,looking into characteristic features of each cluster, patients in C 1 have less amplitude perturbation (Jitter) than in C 2 . This implies that patients in C 1 have more voice stability. In addition, patients in C 1 have higher HNR, thus lower degree of hoarseness.

According to this clustering, and based on the above interpretation, we can say that patients in C 1 have better physiological parameters compared to C 2 . Under expert guidance, the demographic information of patients were reviewed, and it has been noticed that patients in C 1 are all involved in the teaching domain, which means they perform voice activities as a part of their daily life, as if they are practicing speech therapy. Hence, the results of our speech diagnosis model classified patients according to their ability to control their voice, which is related to the extent that they utilize their voice in their daily activity. As for the handwriting local model, the optimal choice of structure is a naive one (figure 6.4) that integrates all five features: velocity, pause-in duration, fluidity, number of strokes and mean pressure. After presenting the classification results as shown in figure 6.5, we can observe from the characteristic features that all patients that have moderate kinematic parameters are clustered together (C 1 ) while patients that have extreme kinematic parameters are clustered together (C 2 ). The expert states that these results show that traces , 8, infinity, and phrase clustered patients according to their ability of controlling their handwriting of each trace. As mentioned in section 6.2, each patient had to write each trace several times repeatedly. Due to this repetition, and after observing the handwriting traces, we noticed a direct improvement in the tracing ability throughout the tests. Thus, we can state that this protocol can be considered as a kind of hand-motor physiotherapy that is an effective treatment approach for addressing kinematic parameters. Looking back at both speech and handwriting clustering results, it is noticed that (P 3 , P 8 , and P 10 ) and (P 2 , P 4 , P 7 , and P 9 ) are invariant with respect to C 1 and C 2 respectively. Whereas (P 1 , P 5 , and P 6 ) are fluctuating between different clusters. We can conclude that not all cases have coherency with respect to handwriting and speech symptoms.

Similar to these local models of handwriting and speech, the BBN (illustrated in section 5.4) for the FoG phenomena can be considered also a c GREAH -2016

Ali SAAD new local model. The structures and the learned CPTs of the local models are saved and used to make the global model that links all these symptoms together.

Global models

On the way of building our HLC model, we consider the obtained handwriting and speech patterns (local diagnosis models) as leaf nodes for a new latent class that is a source influencing and acting on both types of patterns (pattern of speech and writing). Each local prototype has its own particular motor abilities represented by hidden discrete variables. This model is conceptualized as a global diagnosis model that deals with each local diagnosis model (figure 6.6). The only assumption we make is that these abilities are independent but conditionally dependent on a hidden global class, which is the missing data in this case. For this reason, we used the EM algorithm for calculating the conditional probabilities between local classes and the global class, knowing that the previously calculated conditional probabilities between features (handwriting or speech) and their corresponding class (CPT of the local structures) were predetermined and directly used in the global model. After the modeling and learning phase, the global BBNs were used as an inference tool. For instance, through inference, we can make trade-offs between traces and voice parameters: What is the probability that a PD patient has such difficulty in handwriting, knowing that this person has such After tabulating these groups, it was recognized that C 1 includes two patients (P 3 and P 8 ) (figure 6.7). These patients are found in the local clusters that include patients with better acoustic features, as well as patients that were capable of controlling all their writing abilities upon writing each trace test. Thus, we can conclude that the patients in C 1 are capable of controlling their speech and handwriting motor abilities. Based on the demographic data of the patients, the expert assumes that these results may be because the patients (P 3 and P 8 ) are still in the early stages of the disease (3-4 years). As for C 2 patients, they are also clustered together in the local clusters. They are found in the clusters that have low voice quality with respect to the extracted acoustic features, and a reduced ability to control the proposed traces tests. Hence, C 2 patients of the global model were not able to control their handwriting and acoustic abilities. This may be linked to their belated disease duration (11-15 years). Finally, the third clustering group (C 3 ) is indefinite where patients have a disease duration of 2-6 years, but it still included some common characteristic features such as moderate kinematic and acoustic ones during the hand-motor physiotherapy. Hence, our global methodology diagnoses PD patients by analyzing the clusters with respect to the behavior of patients within the cluster. The PD behavior is represented by a set of features. Each cluster will be simply labeled by experts in the neurology and motor control domain. In the case of handwriting and speech syndromes, characteristics were acquired in the same experiments. To expand this methodology to new PD syndromes, a new experimental protocol must be introduced. For example, the FoG syndrome can be integrated into our methodology by acquiring handwriting and speech data from the same c GREAH -2016 Ali SAAD patients that encounter FoG episodes. Then, by constructing and learning our BBN, we can discover a specific prototype (or cluster) of handwriting and speech linked to the FoG phenomena.

Conclusion

In this chapter, we have described a global methodology for the modeling and diagnosing of the main behavioral syndromes for PD with BBNs. We have described a new way for labeling handwriting and speech prototypes of PD patients. A method based on BBN formalism, combined with a Bayesian clustering algorithm that integrates a prior knowledge provided by experts, has been developed. We modeled the physiological brain structure (i.e. PPN) by a hidden variable that influences both handwriting and speech measuring variables. The results, therefore, should appeal to neurologists and doctors who are interested in the development of axial symptoms in PD.

Depending on the results of the handwriting and speech global diagnosis model, and based on the recent studies that shows a relationship between the frequency of freezing episodes during gait (FoG) and during a bi-manual task (like handwriting) [ Nieuwboer 09], a global probabilistic model for the diagnosis of different PD symptoms can be created. This model utilizes the developed multi-sensor device to integrate the three different symptoms of PD (FoG, handwriting, and speech). By using the inference tool of BBN, the developed model can be used to evaluate different probabilities that link each syndrome to the other. It could be used, for example, to calculate the probability of a patient having a freezing episode if it is known that the patient has a specific behavior of writing. And so it will be possible to predict the harshness staging of PD patients using both motor (i.e., handwriting and FoG) and non-motor (speech) syndromes.

Many new PD syndromes can be integrated into our model to achieve a global assessment for PD, such as swallowing as a neuromuscular activity that influences dysphagia.

Conclusion

Statistically, over 50% of patients with PD eventually develop FoG where patients state experiencing brief and sudden reduction of forward progression of the feet. Even though, it is considered as one of the least understood symptoms in PD, it has been argued that it does not occur due to muscle weakness, and patients are able to freely perform their tasks after overcoming their disabling freezing episode. FoG directly affects the quality of life through different factors, whether by reducing mobility or even injuries due to the important risk of falling. Adding the fact that freezing is generally resistant to pharmacological therapy and its predictability is considered hard due to different transient clinical factors. This has raised the issue to create and find a method for detection and diagnosis of this hindering symptom.

The direct objective of this thesis involves in the detection and diagnosis of the FoG phenomena in PD. Our main contribution in this thesis is that we developed a new FoG detection algorithm based on a multi-sensor device. For this purpose, we started by designing a multi-sensor device that is able to acquire data from five sensors (one goniometer, two telemeters, and two accelerometers). Unlike previous studies, that either used uni-sensor systems or utilized multi-sensor devices but with sensors that are hard to be implemented in the daily life of PD patients, our multi-sensor device is wearable, and consists of non-invasive, non-skin contact sensors that are cheap, small sized, and can be easily handled for long term wearing. One of the main contributions of this thesis is that we introduced two new sensors (telemeters and goniometers) into the field of FoG detection. The telemeter is integrated in a way that allows measuring the variation of the inter-foot distance, which is considered by the expert as the closest measurement that reflects the physiological change of behavior during FoG, which is a novel contribution in the assessment of gait for PD patients. The integrated sensors were introduced to a feature extractor to extract informative time and frequency domain features. One advantage of our work is that due to the complexity and inconsistency of FoG events, these heterogeneous features (i.e. features from different types of sensors) are combined using the PCA technique. The informative features were extracted from both simulation and clinical data. The clinical data were acquired from two groups of five patients each having two different configurations of sensors. Configuration one contains a reduced set of sensors (two sensors) while configuration two contains the full set of sensors (five sensors). Another advantage of our work is that all parameters that are used for the learning and calibration process of the FoG detection algorithm is obtained from simulation data. Whereas, the validation process is done by the clinical data. This method generalizes the detection algorithm and avoids its dependency of the on specific PD patients.

Our main contribution came into sight after introducing the two PCs of the informative features into two different FoG detection approaches (GNN and BBN). Both formalisms were able to detect 100% the appearance of FoG events they encountered from the clinical data. Also, the average classification rate of both approaches is significantly better when using sensor configuration two. For GNN the performance increased from 0.69 (configuration one) to 0.9 (configuration two). While for BBN the performance increased from 0.65 (configuration one) to 0.8 (configuration two). This proved that utilizing additional sensors (especially the telemeter and the goniometer) increases significantly the FoG detection performance. Considering that each patient freezes in a different pattern, an advantage of using the BBN model, is that we moved, beyond FoG detection, into diagnosis for the most affected sensor during FoG. For example, using the BBN model we inferred the probability of a patient having a specific pattern of acceleration (telemeter, or goniometer) given that this patient is encountering a freezing event.

On the way of building a global model for the diagnosis of PD that includes FoG along with other main symptoms of PD, we represented a physiological brain structure (i.e. PPN) by a hidden variable that influences variables that assesses two main symptoms of PD (handwriting and speech). We used the HLC models which are tree-structured BBNs where leaf nodes are observed while internal nodes are hidden. We used the EM algorithm for calculating the conditional probabilities between the leaf nodes and the hidden node. The objective contribution is that we evaluated the performance of PD patients regarding to their handwriting and speech skills. In the clustering and modeling approach, our contribution highlights groups of patients that constitute of a coherent unity, more easily identifiable and more informative at the level of handwriting and speech features. From a cognitive point of view, the behavior of a group could be the function of a specific central representation. Therefore the patients grouped together in the same cluster could share common expertise at the motor program level. In the local approach, the results of our speech local model, classified patients according to their ability to control their voice, which is related to which extent they utilize their voice in their daily activity. Whereas the results of the handwriting local models showed that the proposed traces clustered patients according to their ability of controlling the handwriting that is considered as a hand-motor physiotherapy. The result obtained from this trace, reveals that clinical physiotherapy leads to effective improvements of the motor abilities for PD patients. One benefit on this global model is that it can embrace new symptoms such as FoG to form a global prototype that serves as a helpful assistant as a diagnostic tool based on main symptoms of PD.

The major social challenge is obtaining the acknowledgment of patients to participate in our study. This presents one limitation in our study due to the small number of patients that participated in the experimental protocol. We expect that more patients will participate in future tests. Another limitation in our FoG study is the wired connection between the integrated sensors and the acquisition device. This problem will be solved upon implementing the detection algorithm to a wearable computer. This task will increase the patient comfort during the data acquisition tests.

Perspectives

Although, we believe that the research and contributions conducted in this thesis are essential for the detection and diagnosis of FoG. However, three main points can be considered for future work:

-Improvements in the design and validation of the FoG detection algorithm: This point can be achieved by implementing the FoG detection algorithm in a wearable computer. This will lead to minimizing the wired connections between the sensors and acquisition device. This device will be used for on-line FoG detection, and will increase the comfort of PD patients while acquiring data. Since increas-ing the number of PD patients that participates in our study is very essential for more validation to our obtained results. Furthermore, our implemented BBN model for FoG detection can be adjusted by the integration of the hidden variable in the context of data re-building. This is beneficial to the domain of sensor fault diagnosis and aims is to employ a robust detection algorithm that can compensate any data loss due to the fault of sensors. Also, we will investigate diagnosing FoG using probabilistic models (BBN) by considering the causal factors that would lead to the appearance of FoG episodes. The diagnosis model will combine different useful information from the statistical studies done in this thesis in addition to the knowledge of the PD experts. The aim is to design a model that may predict the appearance of freezing episodes using all information that particularly affect the freezing phenomena. -Introduction of actions to prevent the FoG: The decision given by the detection system will trigger actions that may lead to overcome FoG. In particular we will investigate the stimulation of the tibialis anterior muscle that may be more effective than visual or auditory cueing. However this task needs more extensive effort to study the effect of such action on patients. -Continuation toward a global model that includes several PD symptoms: Depending on the results of the handwriting and speech global diagnosis model. And using the multi-sensor device along with the proposed experimental protocol for acquiring FoG, handwriting, and speech data. The main perspective is to build a global probabilistic model for the diagnosis of different PD symptoms. The developed model can be used to calculate relations between each symptom. For example, the probability of a patient having a freezing episode if it is known that the patient has a specific behavior of writing.

Ali SAAD c GREAH -2016

  Mots clés: Maladie de Parkinson, Freezing of Gait, Détection, Diagnostic, Système multi-capteurs, Réseau de neurones gaussiens, Réseau Bayésien . 3.1 Introduction: Multi-sensor device description . . . . . . . . . . 3.1.1 Acceleration sensor . . . . . . . . . . . . . . . . . . . . 3.1.2 Telemeter sensor . . . . . . . . . . . . . . . . . . . . . 3.1.3 Goniometer sensor . . . . . . . . . . . . . . . . . . . . 3.2 Simulation and experimental protocol . . . . . . . . . . . . . . 3.3 Feature extraction . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Raw data analysis . . . . . . . . . . . . . . . . . . . . . 3.3.2 Features selection . . . . . . . . . . . . . . . . . . . . . 3.4 Principal Component Analysis . . . . . . . . . . . . . . . . . . 3.4.1 PCA using simulation data . . . . . . . . . . . . . . . . 3.4.2 PCA using clinical data . . . . . . . . . . . . . . . . . 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ali SAAD c GREAH -List of Figures 2.1 A sample of the handwriting impairment in PD. . . . . . . . . 2.2 Postoperative coronal brain MRI section illustrating placement of DBS electrodes in the subthalamic nucleus. . . . . . . 2.3 Placement of accelerometers [Bachlin 10]. . . . . . . . . . . . . 2.4 Locations of the accelerometers and surface electromyographic sensors on the PD patients, as well as a sample of the acquired signals [Cole 11]. . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 PD patient wearing the five sensor systems and on-body locations [Mazilu 13]. . . . . . . . . . . . . . . . . . . . . . . . . .3.1 The ADXL330 3-axis acceleration sensor (a) and its placement on the foot (b) and on the shin (c). . . . . . . . . . . . . . . . 3.2 The GP2Y0A21YK telemeter sensor (a) and its placements on the inner part of the lower left leg (b). . . . . . . . . . . . . . 3.3 The Vishay Spectrol Full 360 • goniometer sensor (a) and its placement on the knee part of the left leg (b). . . . . . . . . . 3.4 The patient (left) steps over cones while wearing the prototype as the physiotherapist (right) monitors the patient's gait. . . . 3.5 Goniometer signals during the three test modes. . . . . . . . . 3.6 Telemeter signals during the three test modes. . . . . . . . . . 3.7 Accelerometer signals during the three test modes. . . . . . . . 3.8 Distribution of significant features of the goniometer sensor. . 3.9 Distribution of the mean feature of the telemeter sensors. . . . 3.10 Distribution of significant features of the x-axis shin accelerometer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.11 The process in which the most informative features are selected. 3.12 Signals (Volts) as function of time (seconds) of all sensors during a run of test mode 4, where a FoG episode (shaded red) occurs within normal gait (unshaded blue). . . . . . . . . . . . 3.13 Different features as function of time in which a FoG episode (shaded red) occurs between normal gait (unshaded blue). . . 3.14 The percentage of the total variance explained of the PCs. . . 3.15 Simulation data in plane (P C 1 , P C 2 ) for configuration two. . . 3.16 Simulation data in plane (P C 1 , P C 2 ) for configuration one. . . 4.1 The structure of the GNN classifier. . . . . . . . . . . . . . . . 4.2 The learning phase algorithm of the GNN classifier. . . . . . . 4.3 The learning data in plane (P C 1 , P C 2 ) and boundaries of the GNN classifier for sensor configuration one. . . . . . . . . . . . 4.4 The learning data in plane (P C 1 , P C 2 ) and boundaries of the GNN classifier for sensor configuration two. . . . . . . . . . . . 4.5 Classification with GNN in plane (P C 1 , P C 2 ) with configuration one. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Classification with GNN in plane (P C 1 , P C 2 ) with configuration two. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7 FoG detection function (dotted line) versus the true class (full line) and classification confidence coefficient (dashed line); '0' for no-FoG and '1' for FoG. . . . . . . . . . . . . . . . . . . . 5.1 An example for multi-sensor integration (traffic in this case) using graphical models [Koller 12]. . . . . . . . . . . . . . . . 5.2 An example of a BBN structure. . . . . . . . . . . . . . . . . . 5.3 Structure of a BNC model where node (C) is the root node and nodes (X 1 , . . . , X N ) are the leaf nodes. . . . . . . . . . . . 5.4 The BNC model that is used for the nine PD patients. . . . . 5.5 The BNC model that is used for the 10 PD patients using the multi-sensor device. . . . . . . . . . . . . . . . . . . . . . . . . 5.6 The learning and testing process of the BBN using the multisensor device. . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1 Clinical handwriting samples for PD patients. . . . . . . . . . 6.2 Speech local structure. . . . . . . . . . . . . . . . . . . . . . . 6.3 Clustering results and feature characteristics of speech clusters. 6.4 Handwriting local structure. . . . . . . . . . . . . . . . . . . . 6.5 Clustering results and feature characteristics of handwriting clusters. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6 Handwriting and speech global structure. . . . . . . . . . . . . 6.7 Clustering results for the global structure. . . . . . . . . . . . Ali SAAD c GREAH -List of Tables 2.1 Summary of all FoG detection methods. . . . . . . . . . . . . 3.1 Description and duration of all test modes in FoG episodes simulation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Demographic and clinical characteristics of the ten PD patients from which FoG data are acquired. . . . . . . . . . . . . 3.3 Summary and description of the extracted features. . . . . . . 3.4 The most informative indicators that best detect FoG. . . . . 4.1 The GNN classification rates of for both sensor configurations using the validation data of simulation. . . . . . . . . . . . . . 4.2 The GNN classification rates of for sensor configuration one (P 1 -P 5 ) and sensor configuration two (P 6 -P 10 ) using clinical data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Performance of different FoG detection studies. . . . . . . . . 5.1 Observations based on Hill's criteria for FoG. . . . . . . . . . . 5.2 BNC detection performances for published data. . . . . . . . . 5.3 The BBN classification rates of for sensor configuration one (P 1 -P 5 ) and sensor configuration two (P 6 -P 10 ) using clinical data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1 Demographic and clinical characteristics of the ten PD patients from which handwriting and speech data are acquired. . 6.2 Summary and description of the extracted features. . . . . . . and context of the thesis . . . . . . . 23 1.2 List of publications . . . . . . . . . . . . . . . . . 24 1.3 Thesis objective . . . . . . . . . . . . . . . . . . . 26 1.4 Organization of the thesis . . . . . . . . . . . . . 27

  SAAD c GREAH -2016 obtained [Marquardt 94][Pullmann 98]. Chosen sentences focus on letters with loops which would be slightly deformed by patients with tremor. The deformation can be used as a feature for diagnostics. Bajaj et al. used handwritten samples to differentiate PD patients from patients with other tremors [Bajaj 12]. Normal handwriting is marked by automation, the movements are so fast that normal feedback loop by visual perception and muscle control is disabled. This results in an open loop configuration. For PD patients, the automation is no longer valid, their handwriting depends on the visual closed loop [Unlu 06]. PD patients especially as the disease progresses tend to avoid handwriting tasks because it is stressful and difficult [Phillips 97]. Research describes PD handwriting (in comparison to healthy handwriting) as having variable acceleration peaks, stroke size, or micrographia [Teulings 02]. Boisseau et al. observed that PD handwriting (Fig 2.1) can be characterized by various types of dysfluencies: lack of control, abrupt changes in direction, tremor, slowness, hesitation, rigidity, variability of baseline, and in some cases, micrographia [Boisseau 87]. Not only do instances of micrographia appear in about 10-15% of PD cases, but patients typically are unable to sustain normal-sized writing for more than few letters [Phillips 97]. It was found that PD patients has a harder time writing the more complex movements when required to increase size and speed [Longstaff 03]. It was hypothesized that PD patients choose to write smaller in order to control movement variability. Some researchers have shown that PD patients exhibiting micrographia can consciously alter their handwriting. It was found that external cues or guidelines increased the size and speed of handwriting [Longstaff 03][VanGemmert 01].

Figure 2

 2 Figure 2.1 -A sample of the handwriting impairment in PD.

  Figure 2.2 shows a brain MRI, which is obtained immediately after DBS surgery, to confirm proper electrode placement. Studies have reported that after a DBS surgery significant improvements in the majority of PD symptoms, including FoG occurs [Schupbach 05][Krack 03].

Figure 2 . 2 -

 22 Figure 2.2 -Postoperative coronal brain MRI section illustrating placement of DBS electrodes in the subthalamic nucleus.

Figure 2 . 3 -

 23 Figure 2.3 -Placement of accelerometers [Bachlin 10].

Figure 2 . 4 -

 24 Figure 2.4 -Locations of the accelerometers and surface electromyographic sensors on the PD patients, as well as a sample of the acquired signals [Cole 11].

Figure 2 . 5 -

 25 Figure 2.5 -PD patient wearing the five sensor systems and on-body locations [Mazilu 13].

c

  GREAH -2016 Ali SAAD Table 2.1 -Summary of all FoG detection methods. : Multi-sensor device description . 47 3.1.1 Acceleration sensor . . . . . . . . . . . . . . . . . . 48 3.1.2 Telemeter sensor . . . . . . . . . . . . . . . . . . . 49 3.1.3 Goniometer sensor . . . . . . . . . . . . . . . . . . 50 3.2 Simulation and experimental protocol . . . . . . 51 3.3 Feature extraction . . . . . . . . . . . . . . . . . . 56 3.3.1 Raw data analysis . . . . . . . . . . . . . . . . . . 57 3.3.2 Features selection . . . . . . . . . . . . . . . . . . . 59 3.4 Principal Component Analysis . . . . . . . . . . 67 3.4.1 PCA using simulation data . . . . . . . . . . . . . 67 3.4.2 PCA using clinical data . . . . . . . . . . . . . . . 72 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . 72

Figure 3

 3 Figure 3.1 -The ADXL330 3-axis acceleration sensor (a) and its placement on the foot (b) and on the shin (c).

Figure 3

 3 Figure 3.2 -The GP2Y0A21YK telemeter sensor (a) and its placements on the inner part of the lower left leg (b).

Figure 3

 3 Figure 3.3 -The Vishay Spectrol Full 360 • goniometer sensor (a) and its placement on the knee part of the left leg (b).

  Ali SAAD c GREAH -2016 physically tired throughout the experiments, they were asked to rest between sessions. The different scenarios of the experiments are detailed as follows.-Straight walking with turns: The subject is required to complete 6 m of straight walking, turn, and then walk again in the opposite direction. The performed task is simple. But sometimes, complications are added to the task by adding a cognitive load (holding a ball), narrowing the straight path, or by placing an additional obstacle for patients to turn around it. -Stepping above cones with turns: The subject is required to complete the same tasks as previously mentioned but while stepping over cones placed as barriers as shown in Figure3.4. -Clinic tour: A real-life session that includes random unscripted walking through the hall of the clinic and in the garden with involuntary stops, turns, changes of direction, and walking in narrow spaces.

Figure 3 . 4 -

 34 Figure 3.4 -The patient (left) steps over cones while wearing the prototype as the physiotherapist (right) monitors the patient's gait.

  Characteristic feature Description Mean Mean value of the selected data Standard deviation Standard deviation value of the selected data Power Spectral Density (PSD) Power (S) carried by the wave, per unit frequency (f) Power of the signal a It is calculated using the spectral Moment formula (M r = 2 +∞ 0 f r S x df ) such that M 0 is the signal power Mean frequency a Calculated using the spectral Moment formula such that (M 1 /M 0 ) is the mean frequency FI a Inspired from [Moore 08], and defined as the ratio of power in the freeze band (3-8 Hz) divided by the power in the normal walking band (0.5-3 Hz) a Estimated using PSD Ali SAAD c GREAH -2016

Figure 3 . 5 -

 35 Figure 3.5 -Goniometer signals during the three test modes.

Figure 3 . 6 -

 36 Figure 3.6 -Telemeter signals during the three test modes.

Figure 3 . 7 -

 37 Figure 3.7 -Accelerometer signals during the three test modes.

Figure 3 . 8 -

 38 Figure 3.8 -Distribution of significant features of the goniometer sensor.

Figure 3 . 9 -

 39 Figure 3.9 -Distribution of the mean feature of the telemeter sensors.

Figure 3 .

 3 Figure 3.10 -Distribution of significant features of the x-axis shin accelerometer.

  Figure 3.11 -The process in which the most informative features are selected.

  FI of x-axis shin acceleration data.

  FI of x-axis foot acceleration data.

Figure 3 .

 3 Figure 3.13 -Different features as function of time in which a FoG episode (shaded red) occurs between normal gait (unshaded blue).

Figure 3 . 14 -

 314 Figure 3.14 -The percentage of the total variance explained of the PCs.

  8) where a = [a 1 , a 2 ] and b = [b 1 , b 2 ] are the minimum and maximum values of each principal component respectively. The values of a and b are saved and used later to normalize the data acquired from real PD patients.

Figure 3

 3 Figure 3.15 -Simulation data in plane (P C 1 , P C 2 ) for configuration two.

Figure 3

 3 Figure 3.16 -Simulation data in plane (P C 1 , P C 2 ) for configuration one.

Figure 4 . 1 -

 41 Figure 4.1 -The structure of the GNN classifier.

  .6): (j * , β * ) = arg(min j,β {E m (d j .(1 + β.γ)), β ∈ {0, +1, -1}, j = 1, . . . , N c }) (4.6)

Figure 4 .

 4 Figure 4.2 -The learning phase algorithm of the GNN classifier.

Figure 4 . 3 -

 43 Figure 4.3 -The learning data in plane (P C 1 , P C 2 ) and boundaries of the GNN classifier for sensor configuration one.

Figure 4 . 4 -

 44 Figure 4.4 -The learning data in plane (P C 1 , P C 2 ) and boundaries of the GNN classifier for sensor configuration two.

  Accuracy =T rue positives + T rue negatives T otal cases (4.12) Sensitivity = T rue positives T rue positives + F alse negatives (4.13)Specif icity = T rue negatives T rue negatives + F alse positives(4.14)

  Ali SAADc GREAH -2016

Figure 4 . 5 -

 45 Figure 4.5 -Classification with GNN in plane (P C 1 , P C 2 ) with configuration one.

Figure 4 .

 4 Figure 4.6 -Classification with GNN in plane (P C 1 , P C 2 ) with configuration two.

Figure 4 . 7 -

 47 Figure 4.7 -FoG detection function (dotted line) versus the true class (full line) and classification confidence coefficient (dashed line); '0' for no-FoG and '1' for FoG.

  Ali SAADc GREAH -2016

Figure 5 .

 5 Figure 5.1 -An example for multi-sensor integration (traffic in this case) using graphical models [Koller 12].

Figure 5 . 2 -

 52 Figure 5.2 -An example of a BBN structure.

Figure 5 . 3 -

 53 Figure 5.3 -Structure of a BNC model where node (C) is the root node and nodes (X 1 , . . . , X N ) are the leaf nodes.

  Han 06] [Duda 73].

Figure 5 . 4 -

 54 Figure 5.4 -The BNC model that is used for the nine PD patients.

1.

  The expert in our study is Professor Paul Bejjani, a Neurologist and specialized in the field of PD Ali SAAD c GREAH -2016

Figure 6

 6 Figure 6.1 -Clinical handwriting samples for PD patients.

  Ali SAADc GREAH -2016

  Zhang 04a] [Wang 04], and [Zhang 04b] and used in [Zaarour 04a] [Zaarour 05] [Zaarour 10]. The

Figure 6

 6 Figure 6.2 -Speech local structure.

  Ali SAADc GREAH -2016

Figure 6 . 5 -

 65 Figure 6.4 -Handwriting local structure.

Figure 6 . 6 -

 66 Figure 6.6 -Handwriting and speech global structure.

Figure 6

 6 Figure 6.7 -Clustering results for the global structure.

  . . . . . . . . . . . . . . . . . . . . . . 113 7.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . 115

  Ali SAADc GREAH -2016

  International Journal of Machine Learning and Cybernetics. Springer 2015. 3. Ali Saad, Iyad Zaarour, Abbas Zeinedine, Mohammad Ayache, Paul Bejjani, François Guerin, Dimitri Lefebvre. 'A Preliminary Study of the Causality of Freezing of Gait for Parkinson's Disease Patients: Bayesian Belief Network Approach'. IJCSI International Journal of Computer Science Issues, Vol. 10, Issue 3, No 2, May 2013. 4. Ali Saad, Iyad Zaarour, Paul Bejjani, Mohamad Ayach. 'Handwriting and speech prototypes of Parkinson patients: Belief Network Approach'. IJCSI International Journal of Computer Science Issues, Vol. 9, Issue 3, No. 3, May 2012.

	-Book chapter
	1. Iyad Zaarour, Ali Saad, Abbass Zein Eddine, Mohammad Ayache,
	François Guerin, Paul Bejjani and Dimitri Lefebvre. 'Chapter 26 -
	Methodologies for the Diagnosis of the Main Behavioral Syndromes
	for Parkinsons Disease with Bayesian Belief Networks'. In Emerg-
	ing Trends in Computer Science and Applied Computing, edited
	by Quoc Nam TranHamid Arabnia, Morgan Kaufmann, Boston,
	Pages 467-485, Emerging Trends in Computational Biology, Bioin-
	formatics, and Systems Biology, 2015.
		11th to
	13th September 2013.
	4. Ali Saad, Iyad Zaarour, Abbas Zeinedine, Mohammad Ayache,
	Paul Bejjani, François Guerin, Dimitri Lefebvre. 'A Preliminary
	Study of the Causality of Freezing of Gait for Parkinson's Disease
	Patients: Bayesian Belief Network Approach' İn The 2013 Interna-
	tional Conference on Data Mining (DMIN13), Las Vegas Nevada,
	USA 22th to 25th July 2013.
	5. Iyad Zaarour, Ali Saad, Lilian Sahili, Rani Nassereldine, Moham-
	mad Ayache. 'Handwriting and speech prototypes of Parkinson
	patients: Belief Network Approach'. In the IEEE international
	conference of Sciences of Electronics, Technologies of information
	and Telecommunications (SETIT). Tunisia, 21th to 24th 2012.
	Ali SAAD	c GREAH -2016

, Mohammad Ayache, Dimitri Lefebvre. 'A multi-sensor based method for the detection of Freezing of Gait for Parkinson's disease'. IJICIC International Journal of Innovative Computing, Information and Control. Under Review. 2. Ali Saad, Iyad Zaarour, François Guerin, Paul Bejjani, Mohammad Ayache, Dimitri Lefebvre. 'Detection of Freezing of Gait for Parkinson's disease patients with multi-sensor device and Gaussian neural networks'. -International conferences 1. Ali Saad, Dimitri Lefebvre, Franois Guerin, Paul Bejjani, Mohammad Ayache, Iyad Zaarour. 'A Bayesian network approach for the detection of freezing of gait in Parkinsons disease using a multisensor device'. In the International Conference on Bio-engineering for Smart Technologies (BioSMART 2016), Dubai(UAE), December 4th-7th, 2016. Accepted and on press. 2. Ali Saad, François Guerin, Iyad Zaarour, Mohammad Ayache, Dimitri Lefebvre. 'Sensoring and Features Extraction for the Detection of Freeze of Gait in Parkinson Disease'. In the IEEE 11th International Multi-Conference on Systems, Signals & Devices (SSD), Barcelona, Spain, 11th to 14th February 2014. 3. Ali Saad, Iyad Zaarour, Dimitri Lefebvre, François Guerin, Paul Bejjani, Mohammad Ayache. 'About Detection and Diagnosis of Freezing of Gait'. In the IEEE 2nd International Conference on Advances in Biomedical Engineering. Tripoli, Lebanon, c GREAH -2016 Ali SAAD

  Berardelli 01]. Bradykinesia is the most characteristic symptom of basal ganglia (a group of structures linked to the thalamus in the base of the brain and involved in coordination of movement) dysfunction in PD[Jankovic 99]. The term bradykinesia is often used synonymously with hypokinesia (poverty of movement) and akinesia (absence of movement) (e.g. in facial ex-Hz, which can be observed when the hand is not moving, but shaking, and a higher frequency type II Parkinson tremor of 5-12 Hz which is observed during movement[Baumann 05]. There are two methods known for quantitative analysis of tremors. Classically, the muscle activity is recorded from skin surface electrodes, or steel needles pinned into the muscle through the skin, and printed in the form of electromyography [Merletti 04].

pression or arm swing during walking) [

Wilkinson 08

]. Primary researches concluded that bradykinesia occurs in parkinsonian patients because of their inability to energize sufficiently the appropriate muscles for the initiation and the maintenance of a large and fast movement

[

Wilkinson 08][Hallett 80]. -Tremor: PD leads to a breakdown in the execution of highly practiced skilled movements such as walking and handwriting [Soliveri 92]. The movement dysfunctions in PD influence the fine motor movements necessary to produce smooth and fluent handwriting. Tremor, is the most recognized symptom of PD. It is characterized by an involuntary, rhythmic shaking of a limb, head, or entire body. Pal et al. note that approximately 70% of PD patients notice tremor as the first symptom and it is characterized as having 3-5 Hz with rhythmic movements and varying amplitude [Pal 02]. Symptoms typically start on one side of the body and with progression of the disease, both sides are affected. Moreover, Uitii et al. stated that the dominant hand is typically the side affected with more severity [Uitti 05]. Tremor creates a ragged, shaky line quality, rigidity causes angular movements and bradykinesia produces slow handwriting movement which can lead to small and uncoordinated handwriting or micrographia [Pal 02][Teulings 02]. Clinically, one distinguishes the tremor between type I Parkinson tremor of 4-7

-

  Gait disturbances: PD studies found out that 3% of patients before the age of 40 suffer from gait disturbances symptom. This rate increases with age till it reaches 39% of PD patients after the age of 60 on, compared to medication off [DeLetter 05]. Another form of treatment for the disorder of speech and voice in PD is the Lee Silverman Voice Treatment, which has been reported to be a successful approach in the short and long term[Ramig 88b]. This process stimulates patients to increase vocal effort and improve selfperception to realize that their voice is too soft.

	hoarse voice, and imprecise, hypokinetic articulation [Hartelius 94].
	Along with these perceptual characteristics, measures of short-term
	phonatory instability (e.g., jitter, shimmer, harmonics-to-noise ratio)
	have also been documented in PD. Moreover, Parkinsonian speech
	lacks stability in the long-term phonatory during sustained vowel
	phonation [Ramig 88a]. Researchers reported significant improvement
	in the voice of PD patients with medication (e.g. Requip, Mirapex,
	Levedopa, etc.)
	Consequently, PD limits mobility and increases tendency to falls, this
	predisposes patients to life-threatening complications [Beyer 01]. The
	most disabling gait dysfunction in PD is freezing. Freezing episodes
	during the motion of parkinsonian patients represents a special form of
	locomotive disturbance seen only in parkinsonism. This phenomenon
	is thoroughly described in the next section of this chapter.
	-Speech and voice disorders: Most individuals with PD develop
	voice and speech disorders during the course of their illness [Ho 98].
	Researchers estimate that 89% of people with PD have speech and
	voice disorders [Ramig 08]. The main characteristics of a Parkinso-
	nian speech are the reduced vocal loudness, monotone and breathy or
	Ali SAAD	c GREAH -2016

[Yogev 07

]. The mechanism of gait disturbance in PD is heterogeneous and complex. Failure in initiating gait is one of the main gait disturbances in PD. In order to create a forward momentum, PD patients first tend to shift the Center Of Gravity (COG) laterally and rotate the body before the leading leg swings forward

[Vidailhet 93

]. This start hesitation increases the risk of their fall. The mechanism responsible for start hesitation is not clear, but it has been associated with a complete lack of initiation of postural adjustments

[Breniere 91

]. Another gait disturbance is the abnormal locomotion of parkinsonian patients. Unlike normal human locomotion, parkinsonian gait is slow, with reduced stride length, and decreased steps per minute. It is also characterized by shuffling gait, decreased arm swing while walking, and abnormal posture [

Factor 08

]. Another typical disturbance of locomotion in parkinsonian patients is festinating gait. It consists of rapid small steps taken to keep the COG above the feet while the trunk leans forward involuntarily and shifts the COG forward. To compensate and in an attempt to prevent falling, the patient increases stepping velocity and further shortens the stride

[Brown 96

]. -Other PD symptoms: Most individuals with PD also develop swallowing disorders (dysphagia) during their illness

[Leopold 97

]. Swallowing disorders may develop in as many as 90% of individuals with PD

[Miller 06

]. The swallowing problems include difficulty with lingual motility, bolus formation, and initiation of swallow as well as delayed pharyngeal response and decreased pharyngeal contraction

[Factor 08

][

Sharkawi 02]

. Swallowing treatment has focused on behavioral changes and dietary modifications

[Logemann 98

]. Furthermore, PD patients often suffer from gastrointestinal complications such as nausea, vomiting, dyspepsia, constipation, difficult defecation and others

[

Factor 08][Edwards 91]. As well as sleep disorders such as sleep fragmentation respiratory abnormalities, rapid eye movement sleep disorder and others [Factor 08][Kaynak 05]. Moreover, there are different kinds of symptoms associated with PD that are usually overlooked by physicians due to the fact that similar symptoms are also common in the aging general population. These symptoms are referred to as sensory symptoms. Sensory symptoms are present in the majority of individuals with PD. Studies show that among a series of 388 consecutive Levodopa responsive PD patients, 67% endorsed pain or other sensory symptoms [Giuffrida 05] including coldness sensations, back pain, headache, cramps and many others [Factor 08].

  Popovic et al. analyzed the time series of ground reaction forces by calculating, the Pearson's Correlation Coefficient (PCC), which is the measure of the linear dependence between two signals. They acquired 24 FoG episodes from six patients. After acquiring data from a specific patient, the data were visualized off-line. Then, they select from the sequence of normal locomotion the data that corresponds to a single step. This step was used to compute the correlation coefficient by means of PCC with the entire gait record. They found that during normal gait, PCC values were around ±1, while during a FoG event the PCC diminishes around zero[Popovic 10].

  , more discriminant features can be extracted, and then introduced to an advanced programmed machine learning classifier (Advanced Bayesian Belief Networks, Neural Network or others). The classifier can be projected as a forecasting and prediction tool for FoG prognosis. More advanced is to build a causal model related to FoG and the true causes of it. This model would create a reliable view to predict the effect of a 'change in model' due to an external intervention. Although correcting the FoG episode remains indefinite thus more study must be conducted in this area. Currently, we are interested in detecting FoG using artificial intelligence methods. Soft computing methods are substantially utilized in different real life applications.

	Ali SAAD	c GREAH -2016

sensorsThese applications vary from river forecasting [Cheng 05][Taormina 15], to daily flow prediction [Chau 10][Wu 09] and many others. Therefore, we have treated FoG detection as a classification problem, and integrated a new soft computing technique to detect FoG, which is the Gaussian Neural Network method.

Table 3 .

 3 1 -Description and duration of all test modes in FoG episodes simulation.

	Description	Duration
	Test mode 1 Walking with normal steps	15 s
	Test mode 2 Walking with short steps to simulate the nor-	15 s
	mal gait of PD patients
	Test mode 3 Simulating FoG by imitating the shuffling	15 s
	forward behavior of PD patients during FoG
	episodes
	Test mode 4 Walking with normal short steps for 10 s, and	20 s
	then simulating FoG for 5 s, and finally an-
	other 5 s of normal short steps

Table 3 .

 3 2 -Demographic and clinical characteristics of the ten PD patients from which FoG data are acquired.

	Patient Gender Age Occupation	Disease dura-(years) tion	Number episodes of freezing	Description
						In addition to FoG
	P 1	Male	Health supervisor	2	10	this patients has im-paired balance, word repetition, hesitating
						before speaking
						FoG events appear de-
	P 2	Female	Teacher	17	18	spite that the pa-tient underwent DBS
						surgery 15 years ago
						FoG events appear de-
	P 3	Female Housewife	10	27	spite that the pa-tient underwent DBS
						surgery 10 years ago
						This	patient	can
	P 4	Male	Teacher	7	0	barely walk, yet dur-ing data acquisition
						no freezing occurred
						No FoG events oc-
						curred, although he
	P 5	Male	Accountant	10	0	encounters	freezing
						episodes more often in
						his daily life
	P 6	Male	Doctor	10	14	Severe shuffling for-ward FoG events
	P 7	Male	Trader	4	15	Trembling in place FoG behavior
	P 8	Female Housewife	4	7	Severe shuffling for-ward FoG events
	P 9	Male	Shopkeeper	11	17	Severe shuffling for-ward FoG events
						Severe shuffling for-
	P 10	Male	Shopkeeper	12	5	ward FoG events, Pos-tural instability, im-
						paired balance
	Ali SAAD					c GREAH -2016

Table 3 .

 3 3 -Summary and description of the extracted features.

Table 3 .

 3 4 -The most informative indicators that best detect FoG.

	Sensor	Best indicator
	Goniometer	Mean frequency FI
	Upper and lower telemeter	Mean Standard deviation
		FI (x-axis)
	Shin accelerometer	Standard deviation (x-axis)
		Frequency power (x-axis)
		FI (x and z axes)
	Foot accelerometer	Standard deviation (x-axis)
		Frequency power(x-axis)
	Ali SAAD	c GREAH -2016

  The process continues until the mean error of classification (E m ) converges or the maximum number of iterations is achieved. This algorithm is applied on the two groups of PD patients. As shown in section 3.4, the PCs distributions of freezing and normal data vary between configuration one and two. Thus for each group a specific non-linear boundary is obtained. This boundary best separates FoG from no-FoG according to the learning data. The boundaries are presented in figures 4.3 and 4.4. Besides the different positions of the learned Gaussian functions for each configuration, it is also noticed that the no-FoG area is larger in sensor configuration one (figure4.3). These classification boundaries are tested using the other 50% of the simulation data that are reserved for validation.

	of figure 4.2. Learning dataset
	of the normalized
	PCs
	Initialization of the centers of the
	Nc Gaussian functions
	Calculate Em
	Update the centers and dispersions
	of the Gaussian functions
	Reassessment of Em
	YES
	Em decreases ?
	NO
	Save the previous update of the
	centers and dispersions
	End
	c GREAH -2016	Ali SAAD

Table 4 .

 4 1 -The GNN classification rates of for both sensor configurations using the validation data of simulation.

	Simulation data	Confusion matrix		Accu. Sens. Spec.
			Classified as Classified as
	Config. one	Class FoG	FoG 0.99	no-FoG 0.01	0.85	0.99	0.73
		Class no-FoG	0.26	0.74
			Classified as Classified as
	Config. two	Class FoG	FoG 0.98	no-FoG 0.02	0.96	0.98	0.95
		Class no-FoG	0.05	0.95

Table 4 .

 4 2 -The GNN classification rates of for sensor configuration one (P 1 -P 5 ) and sensor configuration two (P 6 -P 10 ) using clinical data.

		GNN detection per-	GNN detection per-
	Clinical	formance using con-	formance using con-
	data	figuration one		figuration two
		Accu. Sens. Spec. Accu. Sens. Spec.
	P 1	0.85	0.98	0.74	-	-	-
	P 2	0.36	0.91	0.21	-	-	-
	P 3	0.90	0.98	0.68	-	-	-
	P 4	0.52	-	0.52	-	-	-
	P 5	0.44	-	0.44	-	-	-
	P 6	0.74	0.92	0.45	0.96	0.99	0.92
	P 7	0.87	0.97	0.71	0.91	0.99	0.79
	P 8	0.90	0.98	0.68	0.87	0.87	0.87
	P 9	0.90	0.76	1	0.80	0.86	0.78
	P 10	0.54	0.81	0.09	0.91	1	0.77

Table 4 .

 4 3 -Performance of different FoG detection studies.

	Reference Number	Number	Rate of	Rate of
		of	of FoG	FoG	classifica-
		patients	episodes	episode	tion
				detection
	Our work	10	113	100%	88%
	[Moore 08]	7	46	78%	-
	[Bachlin 10]	8	237	-	77%
	[Cole 11]	6	20	-	90%
	[Mazilu 12] Data of [Bachlin 10]	-	99%
	[Handojoseno 12]	10	-	-	75%
	[Tripoliti 13]	5	93	96%	-
	[Assam 14] Data of [Bachlin 10]	93%	-
	[Zach 15]	23	-	-	76%
	[Rezvanian 16]Data of [Bachlin 10]	-	80%

Table 5 .

 5 1 -Observations based on Hill's criteria for FoG.

Table 5 .

 5 2 -BNC detection performances for published data.In this section, the acquired data from the multi-sensor device (simulation and clinical data) are introduced to a Bayesian classifier. The introduced datasets contain the same data (i.e. same PD patients) that are used for

	Testing dataset	Accu. Sens. Spec.
	Dataset one	0.6	0.81	0.59
	Dataset two	0.8	0.5	0.85
	Dataset three	0.65	0.39	0.71
	Dataset four	0.61	0.67	0.61
	Average performances	0.67	0.59	0.69
	5.4 Integration of the multi-sensor device to
	the BBN model
	Ali SAAD			c GREAH -2016

Table 5 .

 5 3 -The BBN classification rates of for sensor configuration one (P 1 -P 5 ) and sensor configuration two (P 6 -P 10 ) using clinical data.

		BBN detection per-	BBN detection per-
	Clinical	formance using con-	formance using con-
	data	figuration one		figuration two
		Accu. Sens. Spec. Accu. Sens. Spec.
	P 1	0.84	0.98	0.71	-	-	-
	P 2	0.65	0.41	0.72	-	-	-
	P 3	0.78	0.73	0.91	-	-	-
	P 4	0.43	-	0.43	-	-	-
	P 5	0.54	-	0.54	-	-	-
	P 6	0.69	0.52	0.97	0.79	0.68	0.97
	P 7	0.51	0.36	0.75	0.89	0.98	0.75
	P 8	0.90	0.77	1	0.84	0.87	0.83
	P 9	0.55	0.86	0.46	0.84	0.81	0.85
	P 10	0.57	0.79	0.21	0.93	1	0.82
	c GREAH -2016						Ali SAAD

  Introduction . . . . . . . . . . . . . . . . . . . . . 101 6.2 Experimental protocol . . . . . . . . . . . . . . . 102 6.2.1 Extraction of handwriting and speech features . . 104 6.3 Clustering using Bayesian Belief Networks . . . 105 6.3.1 EM algorithm steps . . . . . . . . . . . . . . . . . 106 6.4 Clustering results . . . . . . . . . . . . . . . . . . 107 6.4.1 Local models . . . . . . . . . . . . . . . . . . . . . 107 6.4.2 Global models . . . . . . . . . . . . . . . . . . . . 110 6.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . 112

	Chapter 6
	Towards a global model to
	diagnose different Parkinson's
	disease symptoms
	Contents
	6.1
	Ali SAAD	c GREAH -2016

Table 6 .

 6 1 -Demographic and clinical characteristics of the ten PD patients from which handwriting and speech data are acquired.

	Patients Gender	Age (years)	Disease Duration	Occupation
	P 1	Male	40	2	Employee in a restaurant
	P 2	Female	75	15	Tailor
	P 3	Male	71	3	English lecturer
	P 4	Male	76	4	Architecture
	P 5	Male	50	4	Paint contractor
	P 6	Male	81	6	Sales manager
	P 7	Male	66	11	Employee in municipality
	P 8	Male	63	4	Teacher
	P 9	Male	70	15	Cars dealer
	P 10	Female	57	4	Educational guide

Table 6 .

 6 2 -Summary and description of the extracted features.

-

  Initialization: The first step in the EM algorithm is to give some initial values to all the parameters of the Bayesian network model. These parameters are called the Conditional Probability Tables (CPT). The initial values can be random real numbers in the range [0, 1], or can be uniform probabilities giving equal values to all the states. The sum From the predictions of missing data made in the E-step, the completed training data are made available. Using this completed training data, new parameter estimates (CPT) for the Bayesian network are computed in the M-step. The maximum likelihood estimate, in general, for any discrete random variable X that takes n possible states (x 1 , x 2 , . . . , x n ) is given in equation (6.1):

	of values in each row of the CPT must be equal to 1.
	-E-step: The E-step involves inferring the missing/hidden data using
	the observed data and the current parameter values. The missing
	data are predicted using the inference procedure. The estimate of
	missing data is not a discrete value but a probability distribution over
	its possible states.
	-M-step:
	Ali SAAD	c GREAH -2016

Acknowledgements