<figure><img src="image_1.png" /></figure>

HAL
open science

Machine Learning for Brain Disorders

Olivier Colliot

► To cite this version:

Olivier Colliot (Dir.). Machine Learning for Brain Disorders. Olivier Colliot. Springer, 197, 2023, Neuromethods, 978-1-0716-3195-9. 10.1007/978-1-0716-3195-9 hal-04225627

HAL Id: hal-04225627

https://hal.science/hal-04225627v1

Submitted on 3 Oct 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Olivier Colliot Editor

Machine
Learning for
Brain Disorders

OPEN ACCESS

<figure><img src="image_3.png" /></figure>

Humana Press
Series Editor

Wolfgang Walz

University of Saskatchewan

Saskatoon, SK, Canada
*Neuromethods* publishes cutting-edge methods and protocols in all areas of neuroscience as well as translational neurological and mental research. Each volume in the series offers tested laboratory protocols, step-by-step methods for reproducible lab experiments and addresses methodological controversies and pitfalls in order to aid neuroscientists in experimentation. *Neuromethods* focuses on traditional and emerging topics with wide-ranging implications to brain function, such as electrophysiology, neuroimaging, behavioral analysis, genomics, neurodegeneration, translational research and clinical trials. *Neuromethods* provides investigators and trainees with highly useful compendiums of key strategies and approaches for successful research in animal and human brain function including translational “bench to bedside” approaches to mental and neurological diseases.
Machine Learning for Brain Disorders

Edited by

**Olivier Colliot**

CNRS, Paris, France

<figure><img src="image_4.png" /></figure>

Humana Press
Editor

Olivier Colliot

CNRS

Paris, France

ISSN 0893-2336

Neuromethods

ISBN 978-1-0716-3194-2

https://doi.org/10.1007/978-1-0716-3195-9

ISSN 1940-6045 (electronic)

ISBN 978-1-0716-3195-9 (eBook)

© The Editor(s) (if applicable) and The Author(s) 2023

**Open Access** This book is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this book are included in the book's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the book's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use.

The publisher, the authors, and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, expressed or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This Humana imprint is published by the registered company Springer Science+Business Media, LLC part of Springer Nature.

The registered company address is: 1 New York Plaza, New York, NY 10004, U.S.A.
Preface to the Series

Experimental life sciences have two basic foundations: concepts and tools. The Neuro-
methods series focuses on the tools and techniques unique to the investigation of the
nervous system and excitable cells. It will not, however, shortchange the concept side of
things as care has been taken to integrate these tools within the context of the concepts and
questions under investigation. In this way, the series is unique in that it not only collects
protocols but also includes theoretical background information and critiques which led to
the methods and their development. Thus it gives the reader a better understanding of the
origin of the techniques and their potential future development. The Neuromethods pub-
lishing program strikes a balance between recent and exciting developments like those
concerning new animal models of disease, imaging, in vivo methods, and more established
techniques, including, for example, immunocytochemistry and electrophysiological tech-
nologies. New trainees in neurosciences still need a sound footing in these older methods in
order to apply a critical approach to their results.

Under the guidance of its founders, Alan Boulton and Glen Baker, the Neuromethods
series has been a success since its first volume published through Humana Press in 1985. The
series continues to flourish through many changes over the years. It is now published under
the umbrella of Springer Protocols. While methods involving brain research have changed a
lot since the series started, the publishing environment and technology have changed even
more radically. Neuromethods has the distinct layout and style of the Springer Protocols
program, designed specifically for readability and ease of reference in a laboratory setting.

The careful application of methods is potentially the most important step in the process of scientific inquiry. In the past, new methodologies led the way in developing new disciplines in the biological and medical sciences. For example, Physiology emerged out of Anatomy in the nineteenth century by harnessing new methods based on the newly discovered phenomenon of electricity. Nowadays, the relationships between disciplines and methods are more complex. Methods are now widely shared between disciplines and research areas. New developments in electronic publishing make it possible for scientists that encounter new methods to quickly find sources of information electronically. The design of individual volumes and chapters in this series takes this new access technology into account. Springer Protocols makes it possible to download single protocols separately. In addition, Springer makes its print-on-demand technology available globally. A print copy can therefore be acquired quickly and for a competitive price anywhere in the world.

Saskatoon, SK, Canada

Wolfgang Walz
# Preface

Machine learning (ML) is at the core of the tremendous progress in artificial intelligence in the past decade. ML offers exciting promises for medicine. In particular, research on ML for brain disorders is a very active field. Neurological and psychiatric disorders are particularly complex and can be characterized using various types of data. ML has the potential to exploit such rich and complex data for a wide range of benefits including a better understanding of disorders, the discovery of new biomarkers, assisting diagnosis, providing prognostic information, predicting response to treatment and building more effective clinical trials.

Machine learning for brain disorders is an interdisciplinary field, involving concepts from different disciplines such as mathematics, statistics and computer science on the one hand and neurology, psychiatry, neuroscience, pathology and medical imaging on the other hand. It is thus difficult to apprehend for students and researchers who are new to this area. The aim of this book is to provide an up-to-date and comprehensive guide to both methodological and applicative aspects of ML for brain disorders. This book aims to be useful to students and researchers with various backgrounds: engineers, computer scientists, neurologists, psychiatrists, radiologists, neuroscientists, etc.

Part I presents the fundamentals of ML. The book starts with a non-technical introduction to the main concepts underlying ML (Chapter 1). The main classic ML techniques are then presented in Chapter 2. Even though not recent for most of them, these techniques are still useful for various tasks. Chapters 3–6 are devoted to deep learning, a family of techniques which have achieved impressive results in the past decade. Chapter 3 describes the basics of deep learning, starting with simple artificial neural networks and then covering convolutional neural networks (CNN) which are a standard family of approaches that are mainly (but not only) used for imaging data. Those architectures are feed-forward, meaning that information flows only in one direction. On the contrary, recurrent neural networks (RNN), presented in Chapter 4, involve loops. They are particularly adapted to sequential data, including longitudinal data (repeated measurements over time), time series and text. Chapter 5 is dedicated to generative models: models that can generate new data. A large part is devoted to generative adversarial networks (GANs), but other approaches such as diffusion models are also described. Finally, Chapter 6 presents transformers, a recent approach which is now the state-of-the-art for natural language processing and has achieved impressive results for other applications such as imaging.

Part II is devoted to the main types of data used to characterize brain disorders. These include clinical assessments (Chapter 7), neuroimaging (including magnetic resonance imaging—MRI, positron emission tomography—PET, computed tomography—CT, single-photon emission computed tomography—SPECT, Chapter 8), electro- and magnetencephalography (EEG/MEG, Chapter 9), genetic and omics data (including genotyping, transcriptomics, proteomics, metabolomics, Chapter 10), electronic health records (EHR, Chapter 11), mobile devices, connected objects and sensor data (Chapter 12). The emphasis is put on practical aspects rather on an in-depth description of the underlying data acquisition techniques (which can be complex, for instance in the case of neuroimaging or omics data). The corresponding chapters describe which information do these data provide,
how they should be handled and processed and which features can be extracted from
such data.

Part III covers the core methodologies of ML for brain disorders. Each chapter is devoted to a specific medical task that can be addressed with ML, presenting the main state-of-the-art techniques. Chapter 13 deals with image segmentation, a crucial task for extracting information from images. Image segmentation techniques allow delineating anatomical structures and lesions (e.g. tumours, white matter lesions), which can in turn provide biomarkers (e.g. the volume of the structure/lesion or other more sophisticated derived measures). Image registration is presented in Chapter 14. It is also a fundamental image analysis task which allows aligning images from different modalities or different patients and which is a prerequisite for many other ML methods. Chapter 15 describes methods for computer-aided diagnosis and prediction. These include methods to automatically classify patients (for instance to assist diagnosis) as well as to predict their future state. Chapter 16 presents ML methods to discover disease subtypes. Indeed, brain disorders are heterogeneous and patients with a given diagnosis may have different symptoms, a different underlying pathophysiology and a different evolution. Such heterogeneity is a major barrier to the development of new treatments. ML has the potential to help discover more homogeneous disease subtypes. Modelling disease progression is the focus of Chapter 17. The chapter describes a wide range of techniques that allow, in a data-driven manner, to build models of disease progression, which includes finding the ordering by which different biomarkers become abnormal, estimating trajectories of change and uncovering different evolution profiles within a given population. Chapter 18 is devoted to computational pathology which is the automated analysis of histological data (which may come from biopsies or post-mortem samples). Tremendous progresses have been made in this area in the past years. Chapter 19 describes methods for integrating multimodal data including medical imaging, clinical data and genetics (or other omics data). Indeed, characterizing the complexity of brain disorders requires to integrate multiple types of data, but such integration raises computational challenges.

Part IV is dedicated to validation and datasets. These are fundamental issues that are sometimes overlooked by ML researchers. It is indeed crucial that ML models for medicine are thoroughly and rigorously validated. Chapter 20 covers model validation. It introduces the main performance metrics for classification and regression tasks, describes how to estimate these metrics in an unbiased manner and how to obtain confidence intervals. Chapter 21 deals with reproducibility, the ability to reproduce results and findings. It is widely recognized that many fields of science, including ML for medicine, are undergoing a reproducibility crisis. The chapter describes the main types of reproducibility, what they require and why they are important. The topic of Chapter 22 is interpretability of ML methods. In particular, it reviews the main approaches to get insight on how “black-box” models take their decisions and describes their application to brain imaging data. Chapter 23 provides a regulatory science perspective on performance assessment of ML algorithms. It is indeed crucial to understand such perspective because regulation is critical to translate safe and effective technologies to the clinic. Finally, Chapter 24 provides an overview of the main existing datasets accessible to researchers. It can help scientists identify which datasets are most suited to a particular research question and provides hints on how to use them.

Part V presents applications of ML to various neurological and psychiatric disorders. Each chapter is devoted to a specific disorder or family of disorders. It presents some information about the disorder that should, in particular, be useful to researchers who don't have a medical background. It then describes some important applications of ML to
this disorder as well as future challenges. The following disorders are covered: Alzheimer's disease and related dementia (including vascular dementia, frontotemporal dementia and dementia with Lewy bodies) in Chapter 25, Parkinson's disease and related disorders (including multiple system atrophy, progressive supranuclear palsy and dementia with Lewy bodies) in Chapter 26, epilepsy in Chapter 27, multiple sclerosis in Chapter 28, cerebrovascular disorders (including stroke, microbleeds, vascular malformations, aneurysms and small vessel disease) in Chapter 29, brain tumours in Chapter 30, neurodevelopmental disorders (including autism spectrum and attention deficit with hyperactivity disorders) in Chapter 31 and psychiatric disorders (including depression, schizophrenia and bipolar disorder) in Chapter 32.

We hope that this book will serve as a reference for researchers and graduate students who are new to this field of research as well as constitute a useful resource for all scientists working in this exciting scientific area.

Paris, France

Olivier Colliot
**Acknowledgements**

I would like to express my profound gratitude to all authors for their contributions to the book. It is thanks to you that this book has become a reality. I am also extremely grateful to all present and past members of the ARAMIS team. Research is a collective endeavour. It was a privilege (and a pleasure!) to work with you throughout all these years. I learn everyday thanks to you all. More generally, I would like to acknowledge all colleagues with whom I had the chance to work. I warmly thank the reviewers who have kindly reviewed chapters: Maria Gloria Bueno García, Sarah Cohen-Boulakia, Renaud David, Guillaume Dumas, Anton Iftimovici, Hicham Janati, Jochen Klucken, Margy McCullough-Hicks, Paolo Mis-sier, Till Nicke, Sebastian Raschka, Denis Schwartz as well as those who preferred to stay anonymous. Your comments were very useful in improving the book. Finally, I would like to thank my family members for their love and support.

I acknowledge the following funding sources: the French government under manage-
ment of the Centre National de la Recherche Scientifique, the French government under
management of Agence Nationale de la Recherche as part of the “Investissements d’avenir”
program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute) and reference ANR-10-
IAIHU-06 (Agence Nationale de la Recherche-10-IA Institut Hospitalo-Universitaire-6),
the European Union H2020 program (project EuroPOND, grant number 666992), the
Paris Brain Institute under the Big Brain Theory Program (project PredictICD, project
IMAGIN-DEAL in MS), Inria under the Inria Project Lab Program (project Neuromar-
kers), the Abeona Foundation (project Brain@Scale) and the Fondation Vaincre Alzheimer
(grant number FR-18006CB). This book was made Open Access thanks to the support of
the French government under management of Agence Nationale de la Recherche as part of
the “Investissements d’avenir” program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA
Institute).

Paris, France

Olivier Colliot
Abbreviations

<table><tr><td>ABC</td><td>Activities-Specific Balance Confidence</td></tr><tr><td>ABCD</td><td>Adolescent Brain Cognitive Development</td></tr><tr><td>ACR</td><td>American College of Radiology</td></tr><tr><td>AD</td><td>Alzheimer's Disease</td></tr><tr><td>Adagrad</td><td>Adaptive Gradient optimizer</td></tr><tr><td>ADAS</td><td>Alzheimer's Disease Assessment Scale</td></tr><tr><td>ADC</td><td>Apparent Diffusion Coefficient</td></tr><tr><td>ADHD</td><td>Attention Deficit Hyperactivity Disorder</td></tr><tr><td>ADNI</td><td>Alzheimer's Disease Neuroimaging Initiative</td></tr><tr><td>AE</td><td>Autoencoder</td></tr><tr><td>AI</td><td>Artificial Intelligence</td></tr><tr><td>AIBL</td><td>Australian Imaging Biomarkers and Lifestyle Study of Aging</td></tr><tr><td>ALS</td><td>Amyotrophic Lateral Sclerosis</td></tr><tr><td>AP-HP</td><td>Assistance Publique-Hôpitaux de Paris</td></tr><tr><td>ARDM</td><td>Auto-Regressive Diffusion Models</td></tr><tr><td>ASD</td><td>Autism Spectrum Disorder</td></tr><tr><td>ASL</td><td>Arterial Spin Labelling</td></tr><tr><td>ASNR</td><td>American Society of Neuroradiology</td></tr><tr><td>ASPECTS</td><td>The Alberta Stroke Programme Early CT Score</td></tr><tr><td>ASR</td><td>Age-Standardized incidence Rate</td></tr><tr><td>ASSD</td><td>Average Symmetric Surface Distance</td></tr><tr><td>ATP</td><td>Adenosine Triphosphate</td></tr><tr><td>AUC</td><td>Area Under the Curve (can apply to ROC curve or PR curve for instance)</td></tr><tr><td>AVM</td><td>Arteriovenous Malformation</td></tr><tr><td>BA</td><td>Balanced Accuracy</td></tr><tr><td>BAM</td><td>Binary Alignment Map</td></tr><tr><td>BATS</td><td>Brisbane Adolescent Twin Study</td></tr><tr><td>BCI</td><td>Brain Computer Interface</td></tr><tr><td>BD</td><td>Bipolar Disorder</td></tr><tr><td>Bi-LSTM</td><td>Bi-directional Long Short-Term Memory</td></tr><tr><td>BMI</td><td>Body Mass Index</td></tr><tr><td>BOLD</td><td>Blood-Oxygen-Level-Dependent</td></tr><tr><td>BPTT</td><td>Back Propagation Through Time</td></tr><tr><td>BraTS</td><td>Brain Tumour Segmentation Challenge</td></tr><tr><td>BRNN</td><td>Bi-directional Recurrent Neural Network</td></tr><tr><td>CA</td><td>Cornu Ammonis</td></tr><tr><td>CA</td><td>Cross-Attention</td></tr><tr><td>CAD</td><td>Computer-Assisted Diagnosis</td></tr><tr><td>CADASIL</td><td>Cerebral Autosomal Dominant Arteriopathy with Subcortical Infarcts and Leukoencephalopathy</td></tr><tr><td>CAM</td><td>Class Activation Maps</td></tr><tr><td>CAP</td><td>College of American Pathologists</td></tr><tr><td>CARS</td><td>Coherent Anti-Stokes Raman Scattering</td></tr><tr><td>CBD</td><td>Cortico-basal Degeneration</td></tr></table>
<table>
   <tr>
    <td>CBF</td>
    <td>Cerebral Blood Flow</td>
   </tr>
   <tr>
    <td>CBV</td>
    <td>Cerebral Blood Volume</td>
   </tr>
   <tr>
    <td>CC</td>
    <td>Cross-Correlation</td>
   </tr>
   <tr>
    <td>CCA</td>
    <td>Canonical Correlation Analysis</td>
   </tr>
   <tr>
    <td>CDF</td>
    <td>Cumulative Density Function</td>
   </tr>
   <tr>
    <td>CDR</td>
    <td>Clinical Dementia Rating</td>
   </tr>
   <tr>
    <td>CDRH</td>
    <td>Center for Devices and Radiological Health at FDA</td>
   </tr>
   <tr>
    <td>cGAN</td>
    <td>Conditional Generative Adversarial Network</td>
   </tr>
   <tr>
    <td>CIFAR</td>
    <td>Canadian Institute For Advanced Research</td>
   </tr>
   <tr>
    <td>CIS</td>
    <td>Clinically Isolated Syndrome</td>
   </tr>
   <tr>
    <td>CLAIM</td>
    <td>Checklist for Artificial Intelligence in Medical imaging</td>
   </tr>
   <tr>
    <td>CLIP</td>
    <td>Contrastive Language-Image Pretraining</td>
   </tr>
   <tr>
    <td>C-LSTM</td>
    <td>Convolutional Long Short-Term Memory</td>
   </tr>
   <tr>
    <td>CMB</td>
    <td>Cerebral Microbleed</td>
   </tr>
   <tr>
    <td>CN</td>
    <td>Healthy Controls (or Cognitively Normal participants)</td>
   </tr>
   <tr>
    <td>CNN</td>
    <td>Convolutional Neural Network</td>
   </tr>
   <tr>
    <td>CNS</td>
    <td>Central Nervous System</td>
   </tr>
   <tr>
    <td>CNV</td>
    <td>Copy number variant</td>
   </tr>
   <tr>
    <td>CP</td>
    <td>Computational Pathology</td>
   </tr>
   <tr>
    <td>CPAB</td>
    <td>Continuous Piecewise Affine-Based</td>
   </tr>
   <tr>
    <td>CPM</td>
    <td>Computational Precision Medicine</td>
   </tr>
   <tr>
    <td>CPM-RadPath</td>
    <td>CPM Radiology-Pathology Challenge</td>
   </tr>
   <tr>
    <td>CPRD</td>
    <td>Clinical Practice Research Datalink</td>
   </tr>
   <tr>
    <td>CRAM</td>
    <td>Compressed Reference-oriented Alignment Map</td>
   </tr>
   <tr>
    <td>CSF</td>
    <td>Cerebrospinal Fluid</td>
   </tr>
   <tr>
    <td>cSVD</td>
    <td>Cerebral Small Vessel Disease</td>
   </tr>
   <tr>
    <td>CT</td>
    <td>Computed Tomography</td>
   </tr>
   <tr>
    <td>CTA</td>
    <td>Computed Tomography Angiography</td>
   </tr>
   <tr>
    <td>CTSA</td>
    <td>Clinical Translational Science Awards</td>
   </tr>
   <tr>
    <td>CTV-3</td>
    <td>Clinical Terms Version 3</td>
   </tr>
   <tr>
    <td>CV</td>
    <td>Cross-Validation</td>
   </tr>
   <tr>
    <td>D3PM</td>
    <td>Data-Driven Disease Progression Modelling</td>
   </tr>
   <tr>
    <td>DAT</td>
    <td>Dopamine Transporter</td>
   </tr>
   <tr>
    <td>dbGAP</td>
    <td>Database of Genotypes and Phenotypes</td>
   </tr>
   <tr>
    <td>DBS</td>
    <td>Deep Brain Stimulation</td>
   </tr>
   <tr>
    <td>DCGAN</td>
    <td>Deep Convolutional Generative Adversarial Network</td>
   </tr>
   <tr>
    <td>DDPM</td>
    <td>Denoising Diffusion Probabilistic Models</td>
   </tr>
   <tr>
    <td>DEBM</td>
    <td>Discriminative Event-Based Model</td>
   </tr>
   <tr>
    <td>DIAN</td>
    <td>Dominantly Inherited Alzheimer Network</td>
   </tr>
   <tr>
    <td>DICOM</td>
    <td>Digital Imaging and Communications in medicine</td>
   </tr>
   <tr>
    <td>DIR</td>
    <td>Double Inversion Recovery MR sequence</td>
   </tr>
   <tr>
    <td>DL</td>
    <td>Deep Learning</td>
   </tr>
   <tr>
    <td>DLB</td>
    <td>Dementia with Lewy Bodies</td>
   </tr>
   <tr>
    <td>DNA</td>
    <td>Deoxyribonucleic Acid</td>
   </tr>
   <tr>
    <td>dof</td>
    <td>Degrees of Freedom</td>
   </tr>
   <tr>
    <td>DPCE</td>
    <td>Distance map Penalized Cross Entropy loss</td>
   </tr>
   <tr>
    <td>DPS</td>
    <td>Disease Progression Score</td>
   </tr>
   <tr>
    <td>DRAM</td>
    <td>Deep Recurrent Attention Model</td>
   </tr>
   <tr>
    <td>DRNN</td>
    <td>Disconnected Recurrent Neural Network</td>
   </tr>
   <tr>
    <td>DSA</td>
    <td>Digital Subtraction Angiography</td>
   </tr>
   <tr>
    <td>DSC</td>
    <td>Dice Similarity Coefficient</td>
   </tr>
  </table>
<table>
  <tr>
    <td>DSM-5</td>
    <td>5th edition of the Diagnostic and Statistical Manual of Mental Disorders</td>
  </tr>
  <tr>
    <td>DT</td>
    <td>Decision Tree</td>
  </tr>
  <tr>
    <td>DTI</td>
    <td>Diffusion Tensor Imaging</td>
  </tr>
  <tr>
    <td>DWI</td>
    <td>Diffusion-Weighted Imaging</td>
  </tr>
  <tr>
    <td>DXA</td>
    <td>Dual-energy X-ray Absorptiometry</td>
  </tr>
  <tr>
    <td>DZ</td>
    <td>Dizygotic</td>
  </tr>
  <tr>
    <td>EBM</td>
    <td>Event-Based Model</td>
  </tr>
  <tr>
    <td>EDSS</td>
    <td>Expanded Disability Status Scale</td>
  </tr>
  <tr>
    <td>EEA</td>
    <td>European Economic Area</td>
  </tr>
  <tr>
    <td>EEG</td>
    <td>Electroencephalography</td>
  </tr>
  <tr>
    <td>EFA</td>
    <td>Exploratory Factor Analysis</td>
  </tr>
  <tr>
    <td>EHR</td>
    <td>Electronic Health Record</td>
  </tr>
  <tr>
    <td>ELBO</td>
    <td>Evidence Lower Bound</td>
  </tr>
  <tr>
    <td>ELL</td>
    <td>Exponential Logarithmic Loss</td>
  </tr>
  <tr>
    <td>EM</td>
    <td>Expectation-Maximization</td>
  </tr>
  <tr>
    <td>ENIGMA</td>
    <td>Enhancing NeuroImaging Genetics Through Meta-Analysis</td>
  </tr>
  <tr>
    <td>eQTL</td>
    <td>expression Quantitative Trait Loci</td>
  </tr>
  <tr>
    <td>ET</td>
    <td>Enhancing Tumour</td>
  </tr>
  <tr>
    <td>EU</td>
    <td>European Union</td>
  </tr>
  <tr>
    <td>FA</td>
    <td>Fractional Anisotropy</td>
  </tr>
  <tr>
    <td>FAIR</td>
    <td>Findable, Accessible, Interoperable, Reusable</td>
  </tr>
  <tr>
    <td>FASTA</td>
    <td>Fast-All format</td>
  </tr>
  <tr>
    <td>FCD</td>
    <td>Focal Cortical Dysplasia</td>
  </tr>
  <tr>
    <td>FCN</td>
    <td>Fully Connected Network</td>
  </tr>
  <tr>
    <td>FCNN</td>
    <td>Fully Convolutional Neural Network</td>
  </tr>
  <tr>
    <td>FDA</td>
    <td>United States Food and Drug Administration</td>
  </tr>
  <tr>
    <td>FDG-PET</td>
    <td>[18F]-Fluorodeoxyglucose Positron Emission Tomography</td>
  </tr>
  <tr>
    <td>FDR</td>
    <td>False Discovery Rate</td>
  </tr>
  <tr>
    <td>FFPE</td>
    <td>Formalin-Fixed Paraffin-Embedded</td>
  </tr>
  <tr>
    <td>FID</td>
    <td>Fréchet Inception Distance</td>
  </tr>
  <tr>
    <td>FLAIR</td>
    <td>Fluid-Attenuated Inversion Recovery</td>
  </tr>
  <tr>
    <td>FLOP</td>
    <td>Floating Point Operations</td>
  </tr>
  <tr>
    <td>fMRI</td>
    <td>functional Magnetic Resonance Imaging</td>
  </tr>
  <tr>
    <td>FN</td>
    <td>False Negative</td>
  </tr>
  <tr>
    <td>FOG</td>
    <td>Freezing of Gait</td>
  </tr>
  <tr>
    <td>FP</td>
    <td>False Positive</td>
  </tr>
  <tr>
    <td>FROC</td>
    <td>Free-response ROC</td>
  </tr>
  <tr>
    <td>FTLD</td>
    <td>Fronto-temporal Lobar Degeneration</td>
  </tr>
  <tr>
    <td>G2PSR</td>
    <td>Genome-to-Phenome Sparse Regression</td>
  </tr>
  <tr>
    <td>GAN</td>
    <td>Generative Adversarial Network</td>
  </tr>
  <tr>
    <td>GBM</td>
    <td>Glioblastoma</td>
  </tr>
  <tr>
    <td>GD</td>
    <td>Generalized Dice loss</td>
  </tr>
  <tr>
    <td>GDPR</td>
    <td>General Data Protection Regulation</td>
  </tr>
  <tr>
    <td>GENFI</td>
    <td>Genetic FTD Initiative</td>
  </tr>
  <tr>
    <td>GEO</td>
    <td>Gene Expression Omnibus</td>
  </tr>
  <tr>
    <td>GFF</td>
    <td>General Feature Format</td>
  </tr>
  <tr>
    <td>GIS</td>
    <td>Geographic Information Systems</td>
  </tr>
  <tr>
    <td>GM</td>
    <td>Gray Matter</td>
  </tr>
  <tr>
    <td>GMM</td>
    <td>Gaussian Mixture Model</td>
  </tr>
</table>
<table>
   <tr>
    <td>GO</td>
    <td>Gene Ontology</td>
   </tr>
   <tr>
    <td>GPPM</td>
    <td>Gaussian Process Progression Model</td>
   </tr>
   <tr>
    <td>GPS</td>
    <td>Global Positioning System</td>
   </tr>
   <tr>
    <td>GPU</td>
    <td>Graphical Processing Unit</td>
   </tr>
   <tr>
    <td>Grad-CAM</td>
    <td>Gradient-weighted Class Activation Mapping</td>
   </tr>
   <tr>
    <td>GRE</td>
    <td>Gradient-Recalled Echo</td>
   </tr>
   <tr>
    <td>GRU</td>
    <td>Gated Recurrent Unit</td>
   </tr>
   <tr>
    <td>GTEx</td>
    <td>Genotype-Tissue Expression</td>
   </tr>
   <tr>
    <td>GWAS</td>
    <td>Genome-Wide Association Study</td>
   </tr>
   <tr>
    <td>H&amp;E</td>
    <td>Hematoxylin and Eosin</td>
   </tr>
   <tr>
    <td>HAR</td>
    <td>Human Activity Recognition</td>
   </tr>
   <tr>
    <td>HC</td>
    <td>Healthy Controls</td>
   </tr>
   <tr>
    <td>HCP-YA</td>
    <td>Human Connectome Project Young Adult</td>
   </tr>
   <tr>
    <td>HD</td>
    <td>Hausdorff Distance</td>
   </tr>
   <tr>
    <td>HGG</td>
    <td>High-Grade Glioma</td>
   </tr>
   <tr>
    <td>HIPAA</td>
    <td>Health Insurance Portability and Accountability Act</td>
   </tr>
   <tr>
    <td>HS</td>
    <td>Hippocampal Sclerosis</td>
   </tr>
   <tr>
    <td>HUPO</td>
    <td>Human Proteome Organization</td>
   </tr>
   <tr>
    <td>HYDRA</td>
    <td>Heterogeneity through Discriminative Analysis</td>
   </tr>
   <tr>
    <td>i.i.d.</td>
    <td>Independent and Identically Distributed</td>
   </tr>
   <tr>
    <td>IA</td>
    <td>Intracranial Aneurysm</td>
   </tr>
   <tr>
    <td>ICA</td>
    <td>Independent Component Analysis</td>
   </tr>
   <tr>
    <td>ICD</td>
    <td>International Classification of Diseases</td>
   </tr>
   <tr>
    <td>iCDF</td>
    <td>Inverse Cumulative Density Function</td>
   </tr>
   <tr>
    <td>ICF</td>
    <td>International Classification of Functioning, Disability and Health</td>
   </tr>
   <tr>
    <td>ID</td>
    <td>Intelligence Disabilities</td>
   </tr>
   <tr>
    <td>IDH</td>
    <td>Isocitrate Dehydrogenase</td>
   </tr>
   <tr>
    <td>IEEE</td>
    <td>Institute of Electrical and Electronics Engineers</td>
   </tr>
   <tr>
    <td>IHC</td>
    <td>Inmunohistochemistry</td>
   </tr>
   <tr>
    <td>IoU</td>
    <td>Intersection over Union also called JI</td>
   </tr>
   <tr>
    <td>IPMI</td>
    <td>Information Processing in Medical Imaging conference</td>
   </tr>
   <tr>
    <td>IQ</td>
    <td>Intelligence Quotient</td>
   </tr>
   <tr>
    <td>iRANO</td>
    <td>Immune-related Response Assessment in Neuro-Oncology</td>
   </tr>
   <tr>
    <td>iRBD</td>
    <td>Idiopathic Rapid eye movement sleep Behaviour Disorder</td>
   </tr>
   <tr>
    <td>ISBI</td>
    <td>International Symposium on Biomedical Imaging</td>
   </tr>
   <tr>
    <td>ISLES</td>
    <td>The Ischemic Stroke Lesion Segmentation</td>
   </tr>
   <tr>
    <td>JI</td>
    <td>Jaccard index also called IoU</td>
   </tr>
   <tr>
    <td>JS/JSD</td>
    <td>Jensen-Shannon Divergence</td>
   </tr>
   <tr>
    <td>KDE</td>
    <td>Kernel Density Estimate</td>
   </tr>
   <tr>
    <td>KDE-EBM</td>
    <td>Kernel Density Estimation EBM</td>
   </tr>
   <tr>
    <td>KEGG</td>
    <td>Kyoto Encyclopedia of Genes and Genomes</td>
   </tr>
   <tr>
    <td>KL/KLD</td>
    <td>Kullback-Leibler Divergence</td>
   </tr>
   <tr>
    <td>kNN</td>
    <td>k-Nearest Neighbours</td>
   </tr>
   <tr>
    <td>LASSO</td>
    <td>Least Absolute Shrinkage and Selection Operator</td>
   </tr>
   <tr>
    <td>LATE</td>
    <td>Limbic-predominant Age-related TDP-43 Encephalopathy</td>
   </tr>
   <tr>
    <td>LDA</td>
    <td>Linear Discriminant Analysis</td>
   </tr>
   <tr>
    <td>LDDMM</td>
    <td>Large Deformation Diffeomorphic Metric Mapping</td>
   </tr>
   <tr>
    <td>LGG</td>
    <td>Low-Grade Glioma</td>
   </tr>
   <tr>
    <td>LIME</td>
    <td>Local Interpretable Model-agnostic Explanations</td>
   </tr>
  </table>
<table>
  <tr>
    <td>LJTMM</td>
    <td>Latent Time Joint Mixed Model</td>
  </tr>
  <tr>
    <td>LP</td>
    <td>Linear Programming</td>
  </tr>
  <tr>
    <td>LPA</td>
    <td>Logopenic Progressive Aphasia</td>
  </tr>
  <tr>
    <td>LR</td>
    <td>Logistic Regression</td>
  </tr>
  <tr>
    <td>LR-</td>
    <td>Negative Likelihood Ratio</td>
  </tr>
  <tr>
    <td>LR+</td>
    <td>Positive Likelihood Ratio</td>
  </tr>
  <tr>
    <td>LRP</td>
    <td>Layer-wise relevance</td>
  </tr>
  <tr>
    <td>LSTM</td>
    <td>Long Short-Term Memory</td>
  </tr>
  <tr>
    <td>LVO</td>
    <td>Large Vessel Occlusion</td>
  </tr>
  <tr>
    <td>MAE</td>
    <td>Mean Absolute Error</td>
  </tr>
  <tr>
    <td>MAGIC</td>
    <td>Multi-scAle heteroGeneity analysIs and Clustering</td>
  </tr>
  <tr>
    <td>MAGNIMS</td>
    <td>Magnetic Resonance Imaging in Multiple Sclerosis network</td>
  </tr>
  <tr>
    <td>MAP</td>
    <td>Maximum a Posteriori</td>
  </tr>
  <tr>
    <td>MAR</td>
    <td>Missing at Random</td>
  </tr>
  <tr>
    <td>MCA</td>
    <td>Multi-head Cross-Attention</td>
  </tr>
  <tr>
    <td>MCAR</td>
    <td>Missing Completely at Random</td>
  </tr>
  <tr>
    <td>MCMC</td>
    <td>Markov Chain Monte Carlo</td>
  </tr>
  <tr>
    <td>mcVAE</td>
    <td>Multi-Channel Variational Autoencoder</td>
  </tr>
  <tr>
    <td>MD</td>
    <td>Mean Diffusivity</td>
  </tr>
  <tr>
    <td>MDD</td>
    <td>Major Depressive Disorder</td>
  </tr>
  <tr>
    <td>MDE</td>
    <td>Major Depressive Episode</td>
  </tr>
  <tr>
    <td>MDS-UPDRS</td>
    <td>Movement Disorder Society Unified Parkinson's Disease Rating Scale (synonymous: UPDRS)</td>
  </tr>
  <tr>
    <td>MEDA</td>
    <td>Minimal Evidence of Disease Activity</td>
  </tr>
  <tr>
    <td>MEG</td>
    <td>Magnetoencephalography</td>
  </tr>
  <tr>
    <td>MEM</td>
    <td>Micro Electro Mechanical system</td>
  </tr>
  <tr>
    <td>MGMT</td>
    <td>O6-Methylguanine-DNA Methyltransferase</td>
  </tr>
  <tr>
    <td>MI</td>
    <td>Mutual Information</td>
  </tr>
  <tr>
    <td>MICCAI</td>
    <td>The Medical Image Computing and Computer Assisted Intervention Society</td>
  </tr>
  <tr>
    <td>MICE</td>
    <td>Multiple Imputation by Chained Equations</td>
  </tr>
  <tr>
    <td>MIDS</td>
    <td>Medical Imaging Data Structure</td>
  </tr>
  <tr>
    <td>MIP</td>
    <td>Maximal Intensity Projection</td>
  </tr>
  <tr>
    <td>ML</td>
    <td>Machine Learning</td>
  </tr>
  <tr>
    <td>MLE</td>
    <td>Maximum Likelihood Estimation</td>
  </tr>
  <tr>
    <td>MLP</td>
    <td>Multi-Layer Perceptron</td>
  </tr>
  <tr>
    <td>MMSA</td>
    <td>Masked Multi-head Self-Attention</td>
  </tr>
  <tr>
    <td>MMSE</td>
    <td>Mini-Mental state examination</td>
  </tr>
  <tr>
    <td>MNAR</td>
    <td>Missing Not at Random</td>
  </tr>
  <tr>
    <td>MND</td>
    <td>Motor Neuron Disease</td>
  </tr>
  <tr>
    <td>MNI</td>
    <td>Montreal Neurological Institute</td>
  </tr>
  <tr>
    <td>MNIST</td>
    <td>Modified National Institute of Standards and Technology dataset</td>
  </tr>
  <tr>
    <td>MoCA</td>
    <td>Montreal Cognitive Assessment</td>
  </tr>
  <tr>
    <td>MRA</td>
    <td>Magnetic Resonance Angiography</td>
  </tr>
  <tr>
    <td>MRI</td>
    <td>Magnetic Resonance Imaging</td>
  </tr>
  <tr>
    <td>mRNA</td>
    <td>Messenger RNA</td>
  </tr>
  <tr>
    <td>mRS</td>
    <td>modified Rankin Score</td>
  </tr>
  <tr>
    <td>MS</td>
    <td>Multiple Sclerosis</td>
  </tr>
  <tr>
    <td>MSA</td>
    <td>Multi-head Self-Attention</td>
  </tr>
</table>
<table>
   <tr>
    <td>MSA</td>
    <td>Multiple System Atrophy</td>
   </tr>
   <tr>
    <td>MSA-C</td>
    <td>Cerebellar variant of Multiple System Atrophy</td>
   </tr>
   <tr>
    <td>MSA-P</td>
    <td>Parkinsonian variant of Multiple System Atrophy</td>
   </tr>
   <tr>
    <td>MSD</td>
    <td>Medical Segmentation Decathlon</td>
   </tr>
   <tr>
    <td>MSE</td>
    <td>Mean Squared Error</td>
   </tr>
   <tr>
    <td>mTOR</td>
    <td>Mammalian Target of Rapamycin</td>
   </tr>
   <tr>
    <td>MTR</td>
    <td>Magnetization Transfer Ratio</td>
   </tr>
   <tr>
    <td>MZ</td>
    <td>Monozygotic</td>
   </tr>
   <tr>
    <td>mzML</td>
    <td>Mass Spectrometry Markup Language</td>
   </tr>
   <tr>
    <td>NAWM</td>
    <td>Normal Appearing White Matter</td>
   </tr>
   <tr>
    <td>NB</td>
    <td>Naive Bayes</td>
   </tr>
   <tr>
    <td>NCBI</td>
    <td>National Center for Biotechnology Information</td>
   </tr>
   <tr>
    <td>NCC</td>
    <td>Normalized Cross Correlation</td>
   </tr>
   <tr>
    <td>ncRNA</td>
    <td>Non-coding RNA</td>
   </tr>
   <tr>
    <td>NDDs</td>
    <td>Neurodevelopmental Disorders</td>
   </tr>
   <tr>
    <td>NEDA</td>
    <td>No Evidence of Disease Activity</td>
   </tr>
   <tr>
    <td>NeurIPS</td>
    <td>Neuronal Information Processing Systems conference</td>
   </tr>
   <tr>
    <td>NGS</td>
    <td>Next Generation Sequencing</td>
   </tr>
   <tr>
    <td>NifTI</td>
    <td>Neuroimaging Informatics Technology Initiative</td>
   </tr>
   <tr>
    <td>NIH</td>
    <td>National Institutes of Health</td>
   </tr>
   <tr>
    <td>NINCDS-ADRDA</td>
    <td>National Institute of Neurological and Communicative Disorders and Stroke - Alzheimer's Disease and Related Disorders Association</td>
   </tr>
   <tr>
    <td>NIPALS</td>
    <td>Non-linear Iterative Partial Least Squares</td>
   </tr>
   <tr>
    <td>NIVEL</td>
    <td>Netherlands Institute for Health Services Research</td>
   </tr>
   <tr>
    <td>NIVEL-PCD</td>
    <td>NIVEL Primary Care Database</td>
   </tr>
   <tr>
    <td>NLP</td>
    <td>Natural Language Processing</td>
   </tr>
   <tr>
    <td>NMF</td>
    <td>Non-negative Matrix Factorization</td>
   </tr>
   <tr>
    <td>NMI</td>
    <td>Normalized Mutual Information</td>
   </tr>
   <tr>
    <td>NMOSD</td>
    <td>Neuromyelitis Optica Spectrum Disorder</td>
   </tr>
   <tr>
    <td>NMT</td>
    <td>Neural Machine Translation</td>
   </tr>
   <tr>
    <td>NN</td>
    <td>Neural Network</td>
   </tr>
   <tr>
    <td>NPV</td>
    <td>Negative Predictive Value</td>
   </tr>
   <tr>
    <td>OATS</td>
    <td>Older Adult Twin Study</td>
   </tr>
   <tr>
    <td>OCD</td>
    <td>Obsessive Compulsive Disorder</td>
   </tr>
   <tr>
    <td>OCT</td>
    <td>Optimal Cutting Temperature</td>
   </tr>
   <tr>
    <td>OSF</td>
    <td>Open Science Framework</td>
   </tr>
   <tr>
    <td>PACS</td>
    <td>Picture Archiving and Communication System</td>
   </tr>
   <tr>
    <td>PCA</td>
    <td>Posterior Cortical Atrophy</td>
   </tr>
   <tr>
    <td>PCA</td>
    <td>Principal Component Analysis</td>
   </tr>
   <tr>
    <td>PD</td>
    <td>Parkinson's Disease</td>
   </tr>
   <tr>
    <td>PD</td>
    <td>Proton-Density MR sequence</td>
   </tr>
   <tr>
    <td>PDF</td>
    <td>Probability Density Function</td>
   </tr>
   <tr>
    <td>PE</td>
    <td>Positional Encoding</td>
   </tr>
   <tr>
    <td>PET</td>
    <td>Positron Emission Tomography</td>
   </tr>
   <tr>
    <td>PIB-PET</td>
    <td>[11C]-Pittsburgh Compound B Positron Emission Tomography</td>
   </tr>
   <tr>
    <td>PiD</td>
    <td>Pick's Disease</td>
   </tr>
   <tr>
    <td>PLS</td>
    <td>Partial Least Squares</td>
   </tr>
   <tr>
    <td>PLSR</td>
    <td>Partial Least Square Regression</td>
   </tr>
   <tr>
    <td>PML</td>
    <td>Progressive Multifocal Leukoencephalopathy</td>
   </tr>
  </table>
<table>
   <tr>
    <td>PNS</td>
    <td>Peripheral Nervous System</td>
   </tr>
   <tr>
    <td>PPA</td>
    <td>Primary Progressive Aphasia</td>
   </tr>
   <tr>
    <td>PPMI</td>
    <td>Parkinson's Progression Markers Initiative</td>
   </tr>
   <tr>
    <td>PPMS</td>
    <td>Primary Progressive Multiple Sclerosis</td>
   </tr>
   <tr>
    <td>PPV</td>
    <td>Positive Predictive Value</td>
   </tr>
   <tr>
    <td>PRS</td>
    <td>Polygenic Risk Score</td>
   </tr>
   <tr>
    <td>PSI</td>
    <td>HUPO Proteomics Standards Initiative</td>
   </tr>
   <tr>
    <td>PSI</td>
    <td>Proteomics Standards Initiative</td>
   </tr>
   <tr>
    <td>PSP</td>
    <td>Progressive Supranuclear Palsy</td>
   </tr>
   <tr>
    <td>psPD</td>
    <td>pseudoprogression of disease</td>
   </tr>
   <tr>
    <td>PT</td>
    <td>Patient</td>
   </tr>
   <tr>
    <td>PTSD</td>
    <td>Post-Traumatic Stress Disorder</td>
   </tr>
   <tr>
    <td>PVS</td>
    <td>Perivascular Space</td>
   </tr>
   <tr>
    <td>PWI</td>
    <td>Perfusion Weighted Imaging</td>
   </tr>
   <tr>
    <td>QSM</td>
    <td>Quantitative Susceptibility Mapping</td>
   </tr>
   <tr>
    <td>QT</td>
    <td>Quantitative Traits</td>
   </tr>
   <tr>
    <td>QTAB</td>
    <td>Queensland Twin Adolescent Brain</td>
   </tr>
   <tr>
    <td>QTIM</td>
    <td>Queensland Twin IMaging</td>
   </tr>
   <tr>
    <td>rACBF</td>
    <td>relative CBF change</td>
   </tr>
   <tr>
    <td>RANO</td>
    <td>Response Assessment in Neuro-Oncology</td>
   </tr>
   <tr>
    <td>RAVEL</td>
    <td>Removal of Artificial Voxel Effect by Linear regression</td>
   </tr>
   <tr>
    <td>RBF</td>
    <td>Radial Basis Function</td>
   </tr>
   <tr>
    <td>RCNN</td>
    <td>Region Convolutional Neural Network</td>
   </tr>
   <tr>
    <td>RECIST</td>
    <td>Response Evaluation Criteria in Solid Tumours</td>
   </tr>
   <tr>
    <td>ReLU</td>
    <td>Rectified Linear Unit</td>
   </tr>
   <tr>
    <td>REM</td>
    <td>Rapid Eye Movement</td>
   </tr>
   <tr>
    <td>ResNet</td>
    <td>Residual Neural Network</td>
   </tr>
   <tr>
    <td>RF</td>
    <td>Random Forest</td>
   </tr>
   <tr>
    <td>RKHS</td>
    <td>Reproducing Kernel Hilbert Space</td>
   </tr>
   <tr>
    <td>RMSE</td>
    <td>Root Mean Square Error</td>
   </tr>
   <tr>
    <td>RMSProp</td>
    <td>Root Mean Squared Propagation</td>
   </tr>
   <tr>
    <td>RNA</td>
    <td>Ribonucleic Acid</td>
   </tr>
   <tr>
    <td>RNN</td>
    <td>Recurrent Neural Network</td>
   </tr>
   <tr>
    <td>ROC</td>
    <td>Receiver Operating Characteristic curve</td>
   </tr>
   <tr>
    <td>RRMS</td>
    <td>Relapsing Remitting Multiple Sclerosis</td>
   </tr>
   <tr>
    <td>RS-fMRI</td>
    <td>Resting State functional Magnetic Resonance Imaging</td>
   </tr>
   <tr>
    <td>RSNA</td>
    <td>Radiological Society of North America</td>
   </tr>
   <tr>
    <td>SA</td>
    <td>Self-Attention</td>
   </tr>
   <tr>
    <td>SAM</td>
    <td>Sequence Alignment Map</td>
   </tr>
   <tr>
    <td>SD</td>
    <td>Standard Deviation</td>
   </tr>
   <tr>
    <td>SDG</td>
    <td>Stochastic Gradient Descent</td>
   </tr>
   <tr>
    <td>SHAP</td>
    <td>SHapley Additive exPlanations</td>
   </tr>
   <tr>
    <td>Smile-GAN</td>
    <td>Semi-supervised cLustering via GANs</td>
   </tr>
   <tr>
    <td>SNOMED-CT</td>
    <td>Systematized NOmenclature of MEDicine - Clinical Terms</td>
   </tr>
   <tr>
    <td>SNP</td>
    <td>Single Nucleotide Polymorphism</td>
   </tr>
   <tr>
    <td>SPECT</td>
    <td>Single-Photon Emission Computed Tomography</td>
   </tr>
   <tr>
    <td>SPIE</td>
    <td>The Society for Photoelectrical Instrumentation Engineers - The International Society for Optics and Photonics</td>
   </tr>
   <tr>
    <td>SPIRIT-AI</td>
    <td>Standard Protocol Items: Recommendations for Interventional Trials - Artificial Intelligence</td>
   </tr>
  </table>
<table>
  <tr>
    <td>SPMS</td>
    <td>Secondary Progressive Multiple Sclerosis</td>
  </tr>
  <tr>
    <td>SRA</td>
    <td>Sequence Read Archive</td>
  </tr>
  <tr>
    <td>SRH</td>
    <td>Stimulated Raman scattering Histology</td>
  </tr>
  <tr>
    <td>SS</td>
    <td>Sensitivity-Specificity loss</td>
  </tr>
  <tr>
    <td>SSD</td>
    <td>Sum of Square Differences</td>
  </tr>
  <tr>
    <td>SSL</td>
    <td>Semi-Supervised Learning</td>
  </tr>
  <tr>
    <td>STARD-AI</td>
    <td>Standards for Reporting Diagnostic Accuracy Studies - Artificial Intelligence</td>
  </tr>
  <tr>
    <td>STN</td>
    <td>Spatial Transformer Network</td>
  </tr>
  <tr>
    <td>STR</td>
    <td>Swedish Twin Registry</td>
  </tr>
  <tr>
    <td>STRIVE</td>
    <td>the STandards for ReportIng Vascular changes on nEuroimaging</td>
  </tr>
  <tr>
    <td>SUD</td>
    <td>Substance Use Disorder</td>
  </tr>
  <tr>
    <td>SuLign</td>
    <td>Subtyping Alignment</td>
  </tr>
  <tr>
    <td>SuStaIn</td>
    <td>Subtype and Stage Inference</td>
  </tr>
  <tr>
    <td>SVD</td>
    <td>Singular Value Decomposition</td>
  </tr>
  <tr>
    <td>SVM</td>
    <td>Support Vector Machine</td>
  </tr>
  <tr>
    <td>SWI</td>
    <td>Susceptibility-Weighted Images</td>
  </tr>
  <tr>
    <td>TC</td>
    <td>Tumour Core</td>
  </tr>
  <tr>
    <td>TEBM</td>
    <td>Temporal Event-Based Model</td>
  </tr>
  <tr>
    <td>TICI</td>
    <td>Thrombolysis in Cerebral Infarction</td>
  </tr>
  <tr>
    <td>TLE</td>
    <td>Temporal Lobe Epilepsy</td>
  </tr>
  <tr>
    <td>TMZ</td>
    <td>Temozolomide</td>
  </tr>
  <tr>
    <td>TN</td>
    <td>True Negative</td>
  </tr>
  <tr>
    <td>TNR</td>
    <td>True Negative Rate</td>
  </tr>
  <tr>
    <td>TOPMed</td>
    <td>Trans-omics Precision Medicine</td>
  </tr>
  <tr>
    <td>TP</td>
    <td>True Positive</td>
  </tr>
  <tr>
    <td>TPR</td>
    <td>True Positive Rate</td>
  </tr>
  <tr>
    <td>TRIPOD-ML</td>
    <td>Transparent Reporting of a Multivariable Prediction Model for Individual Prognosis or Diagnosis-Machine Learning</td>
  </tr>
  <tr>
    <td>tRNA</td>
    <td>Transfer RNA</td>
  </tr>
  <tr>
    <td>UAD</td>
    <td>Unsupervised Anomaly Detection</td>
  </tr>
  <tr>
    <td>UDA</td>
    <td>Unsupervised Data Augmentation</td>
  </tr>
  <tr>
    <td>UI</td>
    <td>User Interface</td>
  </tr>
  <tr>
    <td>UKB</td>
    <td>UK Biobank</td>
  </tr>
  <tr>
    <td>UMLS</td>
    <td>Unified Medical Language System</td>
  </tr>
  <tr>
    <td>UPDRS</td>
    <td>Unified Parkinson's Disease Rating Scale</td>
  </tr>
  <tr>
    <td>UX</td>
    <td>User Experience</td>
  </tr>
  <tr>
    <td>VaD</td>
    <td>Vascular Dementia</td>
  </tr>
  <tr>
    <td>VAE</td>
    <td>Variational Autoencoder</td>
  </tr>
  <tr>
    <td>VA-GAN</td>
    <td>Visual Attribution Generative Adversarial Network</td>
  </tr>
  <tr>
    <td>VASARI</td>
    <td>Visually Accesible Rembrandt Images</td>
  </tr>
  <tr>
    <td>VCCA</td>
    <td>Deep Variational CCA</td>
  </tr>
  <tr>
    <td>VCI</td>
    <td>Vascular Cognitive Impairment</td>
  </tr>
  <tr>
    <td>VETSA</td>
    <td>Vietnam Era Twin Study of Aging</td>
  </tr>
  <tr>
    <td>ViT</td>
    <td>Vision Transformer</td>
  </tr>
  <tr>
    <td>ViViT</td>
    <td>Video Vision Transformer</td>
  </tr>
  <tr>
    <td>VQGAN</td>
    <td>Vector Quantization Generative Adversarial Network</td>
  </tr>
  <tr>
    <td>VQ-VAE</td>
    <td>Vector Quantization Variational Autoencoder</td>
  </tr>
  <tr>
    <td>WCE</td>
    <td>Weighted Cross Entropy loss</td>
  </tr>
</table>
<table><tr><td>WGAN</td><td>Wasserstein Generative Adversarial Network</td></tr><tr><td>WGS</td><td>Whole Genome Sequence</td></tr><tr><td>WHO</td><td>World Health Organization</td></tr><tr><td>WM</td><td>White Matter</td></tr><tr><td>WMH</td><td>White Matter Hyperintensity</td></tr><tr><td>WSI</td><td>Whole Slide Image</td></tr><tr><td>WT</td><td>Whole Tumour</td></tr><tr><td>WUSTL</td><td>Washington University in Saint Louis</td></tr><tr><td>xAI</td><td>eXplainable AI</td></tr><tr><td>XML</td><td>eXtensible Markup Language</td></tr><tr><td>XNAT</td><td>eXtensible Neuroimaging Archive Toolkit</td></tr></table>
# Contents

<table><tr><td>Preface to the Series</td><td>v</td></tr><tr><td>Preface</td><td>vii</td></tr><tr><td>Acknowledgements</td><td>xi</td></tr><tr><td>Abbreviations</td><td>xiii</td></tr><tr><td>Contributors</td><td>xxvii</td></tr></table>

## PART I MACHINE LEARNING FUNDAMENTALS

<table><tr><td>1</td><td>A Non-technical Introduction to Machine Learning.<br><i>Olivier Colliot</i></td><td>3</td></tr><tr><td>2</td><td>Classic Machine Learning Methods<br><i>Johann Faouzi and Olivier Colliot</i></td><td>25</td></tr><tr><td>3</td><td>Deep Learning: Basics and Convolutional Neural Networks (CNNs)<br><i>Maria Vakalopoulou, Stergios Christodoulidis, Ninon Burgos, Olivier Colliot, and Vincent Lepetit</i></td><td>77</td></tr><tr><td>4</td><td>Recurrent Neural Networks (RNNs): Architectures, Training Tricks, and Introduction to Influential Research.<br><i>Susmita Das, Amara Tariq, Thiago Santos, Sai Sandeep Kantareddy, and Imon Banerjee</i></td><td>117</td></tr><tr><td>5</td><td>Generative Adversarial Networks and Other Generative Models<br><i>Markus Wenzel</i></td><td>139</td></tr><tr><td>6</td><td>Transformers and Visual Transformers.<br><i>Robin Courant, Maika Edberg, Nicolas Dufour, and Vicky Kalogeiton</i></td><td>193</td></tr></table>

## PART II DATA

<table><tr><td>7</td><td>Clinical Assessment of Brain Disorders.<br><i>Stéphane Epelbaum and Federica Cacciamani</i></td><td>233</td></tr><tr><td>8</td><td>Neuroimaging in Machine Learning for Brain Disorders<br><i>Ninon Burgos</i></td><td>253</td></tr><tr><td>9</td><td>Electroencephalography and Magnetoencephalography.<br><i>Marie-Constance Corsi</i></td><td>285</td></tr><tr><td>10</td><td>Working with Omics Data: An Interdisciplinary Challenge at the Crossroads of Biology and Computer Science.<br><i>Thibault Poinsignon, Pierre Poulain, Mélina Gallopin, and Gaëlle Lelandais</i></td><td>313</td></tr><tr><td>11</td><td>Electronic Health Records as Source of Research Data<br><i>Wenjuan Wang, Davide Ferrari, Gabriel Haddon-Hill, and Vasa Curcin</i></td><td>331</td></tr></table>
<table><tr><td>12</td><td>Mobile Devices, Connected Objects, and Sensors. Sirenia Lizbeth Mondragón-González, Eric Burguière, and Karim N'diaye</td><td>355</td></tr></table>

PART III METHODOLOGIES

<table><tr><td>13</td><td>Medical Image Segmentation Using Deep Learning. Han Liu, Dewei Hu, Hao Li, and Ipek Oguz</td><td>391</td></tr></table>

<table><tr><td>14</td><td>Image Registration: Fundamentals and Recent Advances Based on Deep Learning. Min Chen, Nicholas J. Tustison, Rohit Jena, and James C. Gee</td><td>435</td></tr></table>

<table><tr><td>15</td><td>Computer-Aided Diagnosis and Prediction in Brain Disorders. Vikram Venkatraghavan, Sebastian R. van der Voort, Daniel Bos, Marion Smits, Frederik Barkhof, Wiro J. Niessen, Stefan Klein, and Esther E. Bron</td><td>459</td></tr></table>

<table><tr><td>16</td><td>Subtyping Brain Diseases from Imaging Data. Junhao Wen, Erdem Varol, Zhijian Yang, Gyujoon Hwang, Dominique Dwyer, Anahita Fathi Kazerooni, Paris Alexandros Lalousis, and Christos Davatzikos</td><td>491</td></tr></table>

<table><tr><td>17</td><td>Data-Driven Disease Progression Modeling. Neil P. Oxtoby</td><td>511</td></tr></table>

<table><tr><td>18</td><td>Computational Pathology for Brain Disorders. Gabriel Jiménez and Daniel Racoceanu</td><td>533</td></tr></table>

<table><tr><td>19</td><td>Integration of Multimodal Data. Marco Lorenzi, Marie Deprez, Irene Balelli, Ana L. Aguila, and Andre Altmann</td><td>573</td></tr></table>

PART IV VALIDATION AND DATASETS

<table><tr><td>20</td><td>Evaluating Machine Learning Models and Their Diagnostic Value. Gael Varoquaux and Olivier Colliot</td><td>601</td></tr></table>

<table><tr><td>21</td><td>Reproducibility in Machine Learning for Medical Imaging. Olivier Colliot, Elina Thibeau-Sutre, and Ninon Burgos</td><td>631</td></tr></table>

<table><tr><td>22</td><td>Interpretability of Machine Learning Methods Applied to Neuroimaging. Elina Thibeau-Sutre, Sasha Collin, Ninon Burgos, and Olivier Colliot</td><td>655</td></tr></table>

<table><tr><td>23</td><td>A Regulatory Science Perspective on Performance Assessment of Machine Learning Algorithms in Imaging. Weijie Chen, Daniel Krainak, Berkman Sahiner, and Nicholas Petrick</td><td>705</td></tr></table>
<table><tr><td>24</td><td>Main Existing Datasets for Open Brain Research on Humans</td><td>753</td></tr><tr><td></td><td>Baptiste Couvy-Duchesne, Simona Bottani, Etienne Camenen, Fang Fang, Mulusew Fikere, Juliana Gonzalez-Astudillo, Joshua Harvey, Ravi Hassanaly, Irfahan Kassam, Penelope A. Lind, Qianwei Liu, Yi Lu, Marta Nabais, Thibault Rolland, Julia Sidorenko, Lachlan Strike, and Margie Wright</td><td></td></tr></table>

PART V DISORDERS

<table><tr><td>25</td><td>Machine Learning for Alzheimer's Disease and Related Dementia</td><td>807</td></tr><tr><td></td><td>Marc Modat, David M. Cash, Liane Dos Santos Canas, Martina Bocchetta, and Sébastien Ourselin</td><td></td></tr><tr><td>26</td><td>Machine Learning for Parkinson's Disease and Related Disorders</td><td>847</td></tr><tr><td></td><td>Johann Faouzi, Olivier Colliot, and Jean-Christophe Corvol</td><td></td></tr><tr><td>27</td><td>Machine Learning in Neuroimaging of Epilepsy</td><td>879</td></tr><tr><td></td><td>Hyo Min Lee, Ravnoor Singh Gill, Neda Bernasconi, and Andrea Bernasconi</td><td></td></tr><tr><td>28</td><td>Machine Learning in Multiple Sclerosis</td><td>899</td></tr><tr><td></td><td>Bas Jasperse and Frederik Barkhof</td><td></td></tr><tr><td>29</td><td>Machine Learning for Cerebrovascular Disorders</td><td>921</td></tr><tr><td></td><td>Yannan Yu and David Yen-Ting Chen</td><td></td></tr><tr><td>30</td><td>The Role of Artificial Intelligence in Neuro-oncology Imaging</td><td>963</td></tr><tr><td></td><td>Jennifer Soun, Lu-Aung Yosuke Masudathaya, Arabdha Biswas, and Daniel S. Chow</td><td></td></tr><tr><td>31</td><td>Machine Learning for Neurodevelopmental Disorders</td><td>977</td></tr><tr><td></td><td>Clara Moreau, Christine Deruelle, and Guillaume Auzias</td><td></td></tr><tr><td>32</td><td>Machine Learning and Brain Imaging for Psychiatric Disorders: New Perspectives</td><td>1009</td></tr><tr><td></td><td>Ivan Brossollet, Quentin Gallet, Pauline Favre, and Josselin Houenou</td><td></td></tr><tr><td></td><td>Disclosure Statement of the Editor</td><td>1037</td></tr><tr><td></td><td>Index</td><td>1039</td></tr></table>
**Contributors**

ANA L. AGUILA • University College London, Centre for Medical Image Computing,
COMBINE Lab, London, UK

ANDRE ALTMANN • University College London, Centre for Medical Image Computing,
COMBINE Lab, London, UK

GUILLAUME AUZIAS • Aix-Marseille Université, CNRS, Institut de Neurosciences de la
Timone, Marseille, France

IRENE BALELLI • Université Côte d'Azur, Inria Sophia Antipolis, Epione Research Group,
Nice, France

IMON BANERJEE • Mayo Clinic, Phoenix, AZ, USA; Arizona State University, School of
Computing, Informatics, and Decision Systems Engineering, Tempe, AZ, USA

FREDERIK BARKHOF • Department of Radiology and Nuclear Medicine, Amsterdam
University Medical Center, Amsterdam, The Netherlands; Queen Square Institute of
Neurology and Centre for Medical Image Computing, University College, London, UK

ANDREA BERNASCONI • McGill University, Montreal Neurological Institute and Hospital,
Montreal, QC, Canada

NEDA BERNASCONI • McGill University, Montreal Neurological Institute and Hospital,
Montreal, QC, Canada

ARABDHA BISWAS • Department of Radiological Sciences, University of California, Irvine,
Irvine, CA, USA

MARTINA BOCCHETTA • UCL Queen Square Institute of Neurology, Dementia Research
Centre, London, UK; Centre for Cognitive and Clinical Neuroscience, Division of
Psychology, Department of Life Sciences, College of Health, Medicine and Life Sciences,
Brunel University, London, UK

DANIEL BOS • Department of Radiology and Nuclear Medicine, Erasmus MC, Rotterdam,
The Netherlands; Department of Epidemiology, Erasmus MC, Rotterdam, The Netherlands

SIMONA BOTTANI • Sorbonne Université, Institut du Cerveau—Paris Brain Institute—ICM,
CNRS, Inria, Inserm, AP-HP, Hôpital de la Pitié Salpêtrière, Paris, France

ESTHER E. BRON • Biomedical Imaging Group Rotterdam, Department of Radiology and
Nuclear Medicine, Erasmus MC, Rotterdam, The Netherlands

IVAN BROSSOLLET • Neurospin, UNIACT Lab, PsyBrain Team, CEA Saclay, Gif-sur-Yvette,
France

NINON BURGOS • Sorbonne Université, Institut du Cerveau—Paris Brain Institute—ICM,
CNRS, Inria, Inserm, AP-HP, Hôpital de la Pitié Salpêtrière, Paris, France

ERIC BURGUIÈRE • Sorbonne Université, Institut du Cerveau—Paris Brain Institute—ICM,
CNRS, Inserm, AP-HP, Hôpital de la Pitié-Salpêtrière, Paris, France

FEDERICA CACCIAMANI • University of Bordeaux, Inserm, UMR Bordeaux Population
Health, PHARes Team, Bordeaux, France

ETIENNE CAMENEN • Sorbonne Université, Institut du Cerveau—Paris Brain Institute—
ICM, CNRS, Inria, Inserm, AP-HP, Hôpital de la Pitié Salpêtrière, Paris, France

DAVID M. CASH • UCL Queen Square Institute of Neurology, Dementia Research Centre,
London, UK; UK Dementia Research Institute at UCL, London, UK

DAVID YEN-TING CHEN • Department of Medical Imaging, Taipei Medical University –
Shuang Ho Hospital, Zhonghe District, New Taipei City, Taiwan
MIN CHEN • University Pennsylvania, Department of Radiology, Philadelphia, PA, USA

WEIJIE CHEN • Division of Imaging, Diagnostics, and Software Reliability, Office of Science and Engineering Laboratories, Center for Devices and Radiological Health, US Food and Drug Administration, Silver Spring, MD, USA

DANIEL S. CHOW • Department of Radiological Sciences, University of California, Irvine, Irvine, CA, USA

STERGIOS CHRISTODOULIDIS • Université Paris-Saclay, CentraleSupélec, Mathématiques et Informatique pour la Complexité et les Systèmes, Gif-sur-Yvette, France

SASHA COLLIN • Sorbonne Université, Institut du Cerveau – Paris Brain Institute – ICM, CNRS, Inria, Inserm, AP-HP, Hôpital de la Pitié-Salpêtrière, Paris, France

OLIVIER COLLIOT • Sorbonne Université, Institut du Cerveau – Paris Brain Institute – ICM, CNRS, Inria, Inserm, AP-HP, Hôpital de la Pitié-Salpêtrière, Paris, France

MARIE-CONSTANCE CORSI • Sorbonne Université, Institut du Cerveau—Paris Brain Institute—ICM, CNRS, Inria, Inserm, AP-HP, Hôpital de la Pitié Salpêtrière, Paris, France

JEAN-CHRISTOPHE CORVOL • Sorbonne Université, Institut du Cerveau – Paris Brain Institute – ICM, CNRS, Inserm, AP-HP, Hôpital de la Pitié-Salpêtrière, Department of Neurology, Paris, France

ROBIN COURANT • LIX, CNRS, Ecole Polytechnique, IP Paris, Paris, France; CNRS, IRISA, INRIA, Univ. Rennes, Rennes, France

BAPTISTE COUVY-DUCHESNE • Sorbonne Université, Institut du Cerveau—Paris Brain Institute—ICM, CNRS, Inria, Inserm, AP-HP, Hôpital de la Pitié Salpêtrière, Paris, France; Institute for Molecular Bioscience, The University of Queensland, St Lucia, QLD, Australia

VASA CURCIN • Department of Population Health Sciences, King's College London, London, United Kingdom

SUSMITA DAS • Indian Institute of Technology (IIT), Centre of Excellence in Artificial Intelligence, Kharagpur, West Bengal, India

CHRISTOS DAVATZIKOS • Center for Biomedical Image Computing and Analytics, Perelman School of Medicine, University of Pennsylvania, Philadelphia, PA, USA

MARIE DEPREZ • Université Côte d'Azur, Inria Sophia Antipolis, Epione Research Group, Nice, France

CHRISTINE DERUELLE • Aix-Marseille Université, CNRS, Institut de Neurosciences de la Timone, Marseille, France

LIANE DOS SANTOS CANAS • King's College London, School of Biomedical Engineering & Imaging Sciences, London, UK

NICOLAS DUFOUR • LIX, CNRS, Ecole Polytechnique, IP Paris, Paris, France

DOMINIQUE DWYER • Department of Psychiatry and Psychotherapy, Ludwig-Maximilian University, Munich, Germany

MAIKA EDBERG • LIX, CNRS, Ecole Polytechnique, IP Paris, Paris, France

STÉPHANE EPELBAUM • Sorbonne Université, Institut du Cerveau – Paris Brain Institute – ICM, CNRS, Inria, Inserm, AP-HP, Hôpital de la Pitié-Salpêtrière, Paris, France; AP-HP, Hôpital de la Pitié-Salpêtrière, Department of Neurology, Institut de la Mémoire et de la Maladie d'Alzheimer (IM2A), Paris, France

FANG FANG • Karolinska Institutet (KI), Stockholm, Sweden

JOHANN FAOUZI • CREST, ENSAI, Campus de Ker-Lann, Bruz Cedex, France; Sorbonne Université, Institut du Cerveau—Paris Brain Institute—ICM, CNRS, Inria, Inserm, AP-HP, Hôpital de la Pitié Salpêtrière, Paris, France
PAULINE FAVRE • Neurospin, UNIACT Lab, PsyBrain Team, CEA Saclay, Gif-sur-Yvette, France; INSERM U955, Translational Neuropsychiatry Team, Faculté de Santé, Université Paris Est Créteil, Créteil, France

DAVIDE FERRARI • Department of Population Health Sciences, King's College London, London, United Kingdom

MULUSEW FIKERE • Institute for Molecular Bioscience, The University of Queensland, St Lucia, QLD, Australia

QUENTIN GALLET • Neurospin, UNIACT Lab, PsyBrain Team, CEA Saclay, Gif-sur-Yvette, France; INSERM U955, Translational Neuropsychiatry Team, Faculté de Santé, Université Paris Est Créteil, Créteil, France

MÉLINA GALLOPIN • Institute for Integrative Biology of the Cell (I2BC), CEA, CNRS, Université Paris-Saclay, Gif-sur-Yvette, France

JAMES C. GEE • University Pennsylvania, Department of Radiology, Philadelphia, PA, USA

RAVNOOR SINGH GILL • McGill University, Montreal Neurological Institute and Hospital, Montreal, QC, Canada

JULIANA GONZALEZ-ASTUDILLO • Sorbonne Université, Institut du Cerveau—Paris Brain Institute—ICM, CNRS, Inria, Inserm, AP-HP, Hôpital de la Pitié Salpêtrière, Paris, France

GABRIEL HADDON-HILL • Department of Population Health Sciences, King's College London, London, United Kingdom

JOSHUA HARVEY • University of Exeter Medical School, RILD Building, RD&E Hospital Wonford, Exeter, UK

RAVI HASSANALY • Sorbonne Université, Institut du Cerveau—Paris Brain Institute—ICM, CNRS, Inria, Inserm, AP-HP, Hôpital de la Pitié Salpêtrière, Paris, France

JOSSELIN HOUENOU • Neurospin, UNIACT Lab, PsyBrain Team, CEA Saclay, Gif-sur-Yvette, France; INSERM U955, Translational Neuropsychiatry Team, Faculté de Santé, Université Paris Est Créteil, Créteil, France; APHP, Mondor Univ. Hospitals, DMU Impact, Psychiatry Department, Créteil, France

DEWEI HU • Department of Electrical and Computer Engineering, Vanderbilt University, Nashville, TN, USA

GYUJOON HWANG • Center for Biomedical Image Computing and Analytics, Perelman School of Medicine, University of Pennsylvania, Philadelphia, PA, USA

BAS JASPERSE • Department of Radiology and Nuclear Medicine, Amsterdam University Medical Center, Amsterdam, The Netherlands

ROHIT JENA • University Pennsylvania, Department of Radiology, Philadelphia, PA, USA

GABRIEL JIMÉNEZ • Sorbonne Université, Institut du Cerveau—Paris Brain Institute—ICM, CNRS, Inria, Inserm, AP-HP, Hôpital de la Pitié Salpêtrière, Paris, France

VICKY KALOGEITON • LIX, CNRS, Ecole Polytechnique, IP Paris, Paris, France

SAI SANDEEP KANTAREDDY • Arizona State University, School of Computing, Informatics, and Decision Systems Engineering, Tempe, AZ, USA

IRFAHAN KASSAM • Lee Kong Chian School of Medicine, Nanyang Technological University, Singapore, Singapore

ANAHITA FATHI KAZEROONI • Institute for Mental Health and Centre for Human Brain Health, School of Psychology, University of Birmingham, Birmingham, UK

STEFAN KLEIN • Biomedical Imaging Group Rotterdam, Department of Radiology and Nuclear Medicine, Erasmus MC, Rotterdam, The Netherlands
DANIEL KRAINAK • Division of Radiological Health, Office of In Vitro Diagnostics and Radiological Health, Center for Devices and Radiological Health, US Food and Drug Administration, Silver Spring, MD, USA

PARIS ALEXANDROS LALOUSIS • Institute for Mental Health and Centre for Human Brain Health, School of Psychology, University of Birmingham, Birmingham, UK

HYO MIN LEE • McGill University, Montreal Neurological Institute and Hospital, Montreal, QC, Canada

GAËLLE LELANDAIS • Institute for Integrative Biology of the Cell (I2BC), CEA, CNRS, Université Paris-Saclay, Gif-sur-Yvette, France

VINCENT LEPETIT • LIGM, Ecole des Ponts, Univ Gustave Eiffel, CNRS, Marne-la-Vallée, France

HAO LI • Department of Electrical and Computer Engineering, Vanderbilt University, Nashville, TN, USA

PENELOPE A. LIND • Psychiatric Genetics, QIMR Berghofer Medical Research Institute, Herston, QLD, Australia; School of Biomedical Sciences, Queensland University of Technology, Kelvin Grove, QLD, Australia; School of Biomedical Sciences, Faculty of Medicine, University of Queensland, St Lucia, QLD, Australia

HAN LIU • Department of Computer Science, Vanderbilt University, Nashville, TN, USA

QIANWEI LIU • Karolinska Institutet (KI), Stockholm, Sweden

MARCO LORENZI • Université Côte d'Azur, Inria Sophia Antipolis, Epione Research Group, Nice, France

YI LU • Karolinska Institutet (KI), Stockholm, Sweden

LU-AUNG YOSUKE MASUDATHAYA • Department of Radiological Sciences, University of California, Irvine, Irvine, CA, USA

MARC MODAT • King's College London, School of Biomedical Engineering & Imaging Sciences, London, UK

SIRENIA LIZBETH MONDRAGÓN-GONZÁLEZ • Sorbonne Université, Institut du Cerveau—Paris Brain Institute—ICM, CNRS, Inserm, AP-HP, Hôpital de la Pitié-Salpétrière, Paris, France

CLARA MOREAU • Human Genetics and Cognitive Functions, CNRS UMR 3571, Université de Paris, Institut Pasteur, Paris, France

KARIM N'DIAYE • Sorbonne Université, Institut du Cerveau—Paris Brain Institute—ICM, CNRS, Inserm, AP-HP, Hôpital de la Pitié-Salpétrière, Paris, France

MARTA NABAIS • University of Exeter Medical School, RILD Building, RD&E Hospital Wonford, Exeter, UK

WIRO J. NIESSEN • Biomedical Imaging Group Rotterdam, Department of Radiology and Nuclear Medicine, Erasmus MC, Rotterdam, The Netherlands; Quantitative Imaging Group, Department of Imaging Physics, Faculty of Applied Sciences, TU Delft, The Netherlands

IPEK OGUZ • Department of Computer Science, Vanderbilt University, Nashville, TN, USA; Department of Electrical and Computer Engineering, Vanderbilt University, Nashville, TN, USA

SÉBASTIEN OURSELIN • King's College London, School of Biomedical Engineering & Imaging Sciences, London, UK

NEIL P. OXTOBY • UCL Centre for Medical Image Computing, Department of Computer Science, University College London, London, UK

NICHOLAS PETRICK • Division of Imaging, Diagnostics, and Software Reliability, Office of Science and Engineering Laboratories, Center for Devices and Radiological Health, US Food and Drug Administration, Silver Spring, MD, USA
THIBAULT POINSIGNON • *Institute for Integrative Biology of the Cell* (I2BC), CEA, CNRS, Université Paris-Saclay, Gif-sur-Yvette, France

PIERRE POULAIN • Université Paris Cité, CNRS, Institut Jacques Monod, Paris, France

DANIEL RACOCEANU • Sorbonne Université, Institut du Cerveau—Paris Brain Institute—ICM, CNRS, Inria, Inserm, AP-HP, Hôpital de la Pitié Salpêtrière, Paris, France

THIBAULT ROLLAND • Sorbonne Université, Institut du Cerveau—Paris Brain Institute—ICM, CNRS, Inria, Inserm, AP-HP, Hôpital de la Pitié Salpêtrière, Paris, France

BERKMAN SAHINER • Division of Imaging, Diagnostics, and Software Reliability, Office of Science and Engineering Laboratories, Center for Devices and Radiological Health, US Food and Drug Administration, Silver Spring, MD, USA

THIAGO SANTOS • Emory University, Department of Computer Science, Atlanta, GA, USA

JULIA SIDORENKO • Institute for Molecular Bioscience, The University of Queensland, St Lucia, QLD, Australia

MARION SMITS • Department of Radiology and Nuclear Medicine, Erasmus MC, Rotterdam, The Netherlands

JENNIFER SOUN • Department of Radiological Sciences, University of California, Irvine, Irvine, CA, USA

LACHLAN STRIKE • Queensland Brain Institute, the University of Queensland, St Lucia, QLD, Australia

AMARA TARIQ • Mayo Clinic, Phoenix, AZ, USA

ELINA THIBEAU-SUTRE • Department of Applied Mathematics, Technical Medical Centre, University of Twente, Enschede, The Netherlands; Sorbonne Université, Institut du Cerveau – Paris Brain Institute – ICM, CNRS, Inria, Inserm, AP-HP, Hôpital de la Pitié-Salpêtrière, Paris, France

NICHOLAS J. TUSTISON • University of Virginia, Department of Radiology and Medical Imaging, Charlottesville, VA, USA

MARIA VAKALOPOULOU • Université Paris-Saclay, CentraleSupélec, Mathématiques et Informatique pour la Complexité et les Systèmes, Gif-sur-Yvette, France

ERDEM VAROL • Department of Statistics, Center for Theoretical Neuroscience, Zuckerman Institute, Columbia University, New York, NY, USA

GAEL VAROQUAUX • Soda, Inria, Saclay, France

VIKRAM VENKATRAGHAVAN • Alzheimer Center Amsterdam, Neurology, Vrije Universiteit, Amsterdam, The Netherlands; Amsterdam Neuroscience, Neurodegeneration, Amsterdam, The Netherlands

SEBASTIAN R. VAN DER VOORT • Biomedical Imaging Group Rotterdam, Department of Radiology and Nuclear Medicine, Erasmus MC, Rotterdam, The Netherlands

WENJUAN WANG • Department of Population Health Sciences, King's College London, London, United Kingdom

JUNHAO WEN • Center for Biomedical Image Computing and Analytics, Perelman School of Medicine, University of Pennsylvania, Philadelphia, PA, USA

MARKUS WENZEL • Fraunhofer Institute for Digital Medicine MEVIS, Bremen, Germany

MARGIE WRIGHT • Queensland Brain Institute, the University of Queensland, St Lucia, QLD, Australia; Centre for Advanced Imaging, The University of Queensland, St Lucia, QLD, Australia

ZHIJIAN YANG • Center for Biomedical Image Computing and Analytics, Perelman School of Medicine, University of Pennsylvania, Philadelphia, PA, USA

YANNAN YU • Department of Radiology, University of California San Francisco, San Francisco, CA, USA
# Part I

**Machine Learning Fundamentals**
# Chapter 1

# A Non-technical Introduction to Machine Learning

Olivier Colliot

## Abstract

This chapter provides an introduction to machine learning for a non-technical readership. Machine learning is an approach to artificial intelligence. The chapter thus starts with a brief history of artificial intelligence in order to put machine learning into this broader scientific context. We then describe the main general concepts of machine learning. Readers with a background in computer science may skip this chapter.

**Key words** Machine learning, Artificial intelligence, Supervised learning, Unsupervised learning

## 1 Introduction

Machine learning (ML) is a scientific domain which aims at allowing computers to perform tasks without being explicitly programmed to do so [1]. To that purpose, the computer is trained using the examination of examples or experiences. It is part of a broader field of computer science called *artificial intelligence* (AI) which aims at creating computers with abilities that are characteristic of human or animal intelligence. This includes tasks such as perception (the ability to recognize images or sounds), reasoning, decision-making, or creativity. EmbLEMatic tasks which are easy to perform for a human and are inherently difficult for a computer are, for instance, recognizing objects, faces, or animals in photographs or recognizing words in speech. On the other hand, there are also tasks which are inherently easy for a computer and difficult for a human, such as computing with large numbers or memorizing exactly huge amounts of text. Machine learning is the AI technique that has achieved the most impressive successes over the past years. However, it is not the only approach to AI, and conceptually different approaches also exist.

Machine learning also has close ties to other scientific fields. First, it has evident strong links to statistics. Indeed, most machine learning approaches exploit statistical properties of the data. Moreover, some classical approaches used in machine learning were
actually invented in statistics (for instance, linear or logistic regression). Nowadays, there is a constant interplay between progress in statistics and machine learning. ML has also important ties to signal and image processing, ML techniques being efficient for many applications in these domains and signal/image processing concepts being often key to the design or understanding of ML techniques. There are also various links to different branches of mathematics, including optimization and differential geometry. Besides, some inspiration for the design of ML approaches comes from the observation of biological cognitive systems, hence the connections with cognitive science and neuroscience. Finally, the term *data science* has become commonplace to refer to the use of statistical and computational methods for extracting meaningful patterns from data. In practice, machine learning and data science share many concepts, techniques, and tools. Nevertheless, data science puts more emphasis on the discovery of knowledge from the data, while machine learning focuses on solving tasks.

This chapter starts by providing a few historical landmarks regarding artificial intelligence and machine learning (Subheading 2). It then proceeds with the main concepts of ML which are foundational to understand other chapters of this book.

## 2 A Bit of History

As a scientific endeavor, artificial intelligence is at least 80 years old. Here, we provide a very brief overview of this history. For more details, the reader may refer to [2]. A non-exhaustive timeline of AI is shown in Fig. 1.

<figure><img src="image_5.png" /><figcaption>Fig. 1 A brief timeline of AI with some of the landmark advances</figcaption></figure>
Even if this is debatable, one often considers AI to emerge in the 1940s–1950s with a series of important concepts and events. In 1943, the neurophysiologist Warren McCulloch and the logician Walter Pitts proposed an artificial neuron model, which is a mathematical abstraction of a biological neuron [3], and showed that sets of neurons can compute logical operations. In 1948, the mathematician and philosopher Norbert Wiener coined the term “cybernetics” [4] to designate the scientific study of control and communication in humans, animals, and machines. This idea that such processes can be studied within the same framework in both humans/animals and machines is a conceptual revolution. In 1949, the psychologist Donald Hebb [5] described a theory of learning for biological neurons which was later influential in the modification of the weights of artificial neurons.

In 1950, Alan Turing, one of the founders of computer science, introduced a test (the famous “Turing test”) for deciding if a machine can think [6]. Actually, since the question *can a machine think?* is ill-posed and depends on the definition of thinking, Turing proposed to replace it with a practical test. The idea is that of a game in which an interrogator is given the task of determining which of two players A and B is a computer and which is a human (by using only responses to written questions). In 1956, the mathematician John McCarthy organized what remained as the famous Dartmouth workshop and which united ten prominent scientists for 2 months (among which were Marvin Minsky, Claude Shannon, Arthur Samuel, and others). This workshop is more important by its scientific program than by its outputs. Let us reproduce here the first sentences of the proposal written by McCarthy et al. [7] as we believe that they are particularly enlightening on the prospects of artificial intelligence:

> We propose that a 2 month, 10 man study of artificial intelligence be carried out during the summer of 1956 at Dartmouth College in Hanover, New Hampshire. The study is to proceed on the basis of the conjecture that every aspect of learning or any other feature of intelligence can in principle be so precisely described that a machine can be made to simulate it. An attempt will be made to find how to make machines use language, form abstractions and concepts, solve kinds of problems now reserved for humans, and improve themselves. We think that a significant advance can be made in one or more of these problems if a carefully selected group of scientists work on it together for a summer.

There was no major advance made at the workshop, although a reasoning program, able to prove theorems, was presented by Allen Newell and Herbert Simon [8] at this occasion. This can be considered as the start of symbolic AI (we will come back later on the two main families of AI: symbolic and connexionist). Let us end the 1950s with the invention, in 1958, of the perceptron by Frank Rosenblatt [9], whose work was built upon the ideas of McCulloch, Pitts, and Hebb. The perceptron was the first actual artificial
neuron. It was able to recognize images. This is an important landmark for several reasons. The perceptron, with some modifications, is still the building block of modern deep learning algorithms. To mimic an artificial neuron (Fig. 2), it is composed of a set of inputs (which correspond to the information entering the synapses) $x_i$, which are linearly combined and then go through a non-linear function $g$ to produce an output $y$. This was an important advance at the time, but it had strong limitations, in particular its inability to discriminate patterns which are not linearly separable. More generally, in the field of AI as a whole, unreasonable promises had been made, and they were not delivered: newspapers were writing about upcoming machines that could talk, see, write, and think; the US government funded huge programs to design automatic translation programs, etc. This led to a dramatic drop in research funding and, more generally, in interest in AI. This is often referred to as the first AI winter (Fig. 3).

Even though research in AI continued, it was not before the early 1980s that real-world applications were once again considered possible. This wave was that of expert systems [10], which are a type of symbolic AI approach but with domain-specific knowledge. Expert systems led to commercial applications and to a real boom in the industry. A specific programming language, called LISP [11], became dominant for the implementation of expert systems. Companies started building LISP machines, which were dedicated computers with specific architecture tailored to execute LISP efficiently. One cannot help thinking of a parallel with current hardware dedicated to deep learning. However, once again, expectations were not met. Expert systems were very large and complex sets of rules. They were difficult to maintain and update. They also had poor performances in perception tasks such as image and speech recognition. Academic and industrial funding subsequently dropped. This was the second AI winter.

At this stage, it is probably useful to come back to the two main families of AI: symbolic and connexionist (Fig. 4). They had important links at the beginning (see, e.g., the work of McCulloch and Pitt aiming to perform logical operations using artificial neurons), but they subsequently developed separately. In short, these two families can be described as follows. The first operates on symbols through sets of logical rules. It has strong ties to the domain of predicate logic. Connexionism aims at training networks of artificial neurons. This is done through the examination of training examples. More generally, it is acceptable to put most machine learning methods within the connexionist family, even though they don't rely on artificial neuron models, because their underlying principle is also to exploit statistical similarities in the training data. For a more detailed perspective on the two families of AI, the reader can refer to the very interesting (and even entertaining!) paper of Cardon et al. [12].
<figure><img src="image_6.png" /><figcaption>(b)</figcaption></figure>

<figure><img src="image_7.png" /></figure>

Inputs Weights Sum Non-Linearity Output

**Fig. 2 (a)** Biological neuron. The synapses form the input of the neuron. Their signals are combined, and if the result exceeds a given threshold, the neuron is activated and produces an output signal which is sent through the axon. (b) The perceptron: an artificial neuron which is inspired by biology. It is composed of the set of inputs (which correspond to the information entering the synapses) $x_i$, which are linearly combined with weights $w_i$ and then go through a non-linear function $g$ to produce an output $y$. Image in panel (a) is courtesy of Thibault Rolland
<figure><img src="image_8.png" /><figcaption>**Fig. 3** Summers and winters of AI</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>**Fig. 4** Two families of AI. The symbolic approach operates on symbols through logical rules. The connexionist family actually not only encompasses artificial neural networks but more generally machine learning approaches</figcaption></figure>

Let us come back to our historical timeline. The 1980s saw a rebirth of connexionism and, more generally, the start of the rise of machine learning. Interestingly, it is at that time that two of the main conferences on machine learning started: the International Conference on Machine Learning (ICML) in 1980 and Neural Information Processing Systems (NeurIPS, formerly NIPS) in 1987. It had been known for a long time that neural networks with multiple layers (as opposed to the original perceptron with a single layer) (Fig. 5) could solve non-linearly separable problems, but their training remained difficult. The back-propagation algorithm for training multilayer neural networks was described by David Rumelhart, Geoffrey Hinton, and Ronald Williams [13] in 1986, as well as by Yann LeCun in 1985 [14], who also refined the procedure in his PhD thesis published in 1987. This idea had actually been explored since the 1960s, but it was only in the 1980s that it was efficiently used for training multilayer neural networks. Finally, in 1989, Yann LeCun proposed the convolutional neural network [15], an architecture inspired by the organization of the visual cortex, whose principle is still at the core of
<figure><img src="image_10.png" /><figcaption>**Fig. 5** A multilayer perceptron model (here with only one hidden layer, but there can be many more)</figcaption></figure>

state-of-the-art algorithms for many image processing and recognition tasks. Multilayer neural networks demonstrated their utility in several real-world applications such as digit recognition on checks and ZIP codes [16]. Nevertheless, they would not become the dominant machine learning approach until the 2010s. Indeed, at the time, they required considerable computing power for training, and there was often not enough training data.

During the 1980s and 1990s, machine learning methods continued to develop. Interestingly, connections between machine learning and statistics increased. We are not going to provide an overview of the history of statistics, but one should note that many statistical methods such as linear regression [17], principal component analysis [18], discriminant analysis [19], or decision trees [20] can actually be used to solve machine learning tasks such as automatic categorization of objects or prediction. In the 1980s, decision trees witnessed important developments (see, e.g., the ID3 [21] and CART [21] algorithms). In the 1990s, there were important advances in the statistical theory of learning (in particular, the works of Vladimir Vapnik [22]). A landmark algorithm developed at that time was the support vector machine (SVM) [23] which worked well with small training datasets and could handle non-linearities through the use of kernels. The machine learning field continued to expand through the 2000s and 2010s, with new approaches but also more mature software packages such as scikit-learn [24]. More generally, it is actually important to have in mind that what is currently called AI owes more to statistics (and other mathematical fields such as optimization in particular) than to modeling of brain circuitry and that even approaches that take inspiration from neurobiology can actually be viewed as complex statistical machineries.
2012 saw the revival of neural networks and the beginning of the era of deep learning. It was undoubtedly propelled by the considerable improvement obtained on the ImageNet recognition challenge which contains 14 million natural images belonging to 20,000 categories. The solution, proposed by Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton [25], was a convolutional neural network with a large number of layers, hence the term deep learning. The building blocks of this solution were already present in the 1980s, but there was not enough computing power nor large training datasets for them to work properly. In the interval, things had changed. Computers had become exponentially more powerful, and, in particular, the use of graphical processing units (GPU) considerably sped up computations. The expansion of the Internet had provided massive amounts of data of various sorts such as texts and images. In the subsequent years, deep learning [26] approaches became increasingly sophisticated. In parallel, efficient and mature software packages including TensorFlow [27], PyTorch [28], or Keras [29], whose development is supported by major companies such as Google and Facebook, enable deep learning to be used more easily by scientists and engineers.

Artificial intelligence in medicine as a research field is about 50 years old. In 1975, an expert system, called MYCIN, was proposed to identify bacteria causing various infectious diseases [30]. More generally, there was a growing interest in expert systems for medical applications. Medical image processing also quickly became a growing field. The first conference on Information Processing in Medical Imaging (IPMI) was held in 1977 (it existed under a different name since 1969). The first SPIE Medical Image Processing conference took place in 1986, and the Medical Image Computing and Computer-Assisted Intervention (MICCAI) conference started in 1998. Image perception tasks, such as segmentation or classification, soon became among the key topics of this field, even though the methods came in majority from traditional image processing and not from machine learning. In the 2010s, machine learning approaches became dominant for medical image processing and more generally in artificial intelligence in medicine.

To conclude this part, it is important to be clear about the different terms, in particular those of artificial intelligence, machine learning, and deep learning (Fig. 6). Machine learning is *one* approach to artificial intelligence, and other radically different approaches exist. Deep learning is a specific type of machine learning approach. It has recently obtained impressive results on some types of data (in particular, images and text), but this does not mean that it is the universal solution to all problems. As we will see in this book, there are tasks for which other types of approaches perform best.
<figure><img src="image_11.png" /><figcaption>**Fig. 6** Artificial intelligence, machine learning, and deep learning are not synonymous. Deep learning is a type of machine learning which involves neural networks with a large number of hidden layers. Machine learning is one approach to artificial intelligence, but other approaches exist</figcaption></figure>

# 3 Main Machine Learning Concepts

As aforementioned, machine learning aims at making a computer capable of performing a task without explicitly being programmed for that task. More precisely, it means that one will not write a sequence of instructions that will directly perform the considered task. Instead, one will write a program that allows the computer to learn how to perform the task by examining examples or experiences. The output of this learning process is a computer program itself that performs the desired task, but this program was not explicitly written. Instead, it has been learned automatically by the computer.

In 1997, Tom Mitchell gave a more precise definition of a **well-posed machine learning problem** [31]:

> A computer program is said to learn from **experience E** with respect to some **task T** and some **performance measure P**, if its performance at task T, as measured by P, improves with experience E.

He then provides the example of a computer that learns to play checkers: task T is playing checkers, performance measure P is the proportion of games won, and the training experience E is playing checker games against itself. Very often, the experience E will not be an actual action but the observation of a set of examples, for instance, a set of images belonging to different categories, such as photographs of cats and dogs, or medical images containing tumors or without lesions. Please refer to Box 1 for a summary.

**Box 1: Definition of machine learning**

Machine learning definition [31]:

> a computer program is said to learn from **experience E** with respect to some **task T** and some **performance measure P**, if its performance at task T, as measured by P, improves with experience E.

(continued)
**Box 1 (continued)**

Example: learning to detect tumors from medical images

* **Task T:** detect tumors from medical image

* **Performance measure P:** proportion of tumors correctly identified

* **Experience E:** examining a dataset of medical images where the presence of tumors has been annotated

**3.1 Types of Learning**

One usually considers three main types of learning: supervised learning, unsupervised learning, and reinforcement learning (Box 2). In both supervised and unsupervised learning, the experience E is actually the inspection of a set of examples, which we will refer to as *training examples* or *training set*.

**Box 2: Supervised, Unsupervised, and Reinforcement learning**

* **Supervised learning.** Learns from labeled examples, i.e., examples for which the output that we are trying to learn is known

- Example 1. The task is computer-aided diagnosis (a classification problem), and the label can be the diagnosis of each patient, as defined by an expert physician.

- Example 2. The task is the prediction of the age of a person from a set of biological variables (e.g., a brain MRI). This is a regression problem. The label is the true age of a given person in the training set.

* **Unsupervised learning.** Learns from unlabeled examples

- Example 1. Given a large set of newspaper articles, automatically cluster them into groups dealing with the same topic based only on the text of the article. The topics can, for example, be economics, politics, or international affairs. The topics are not known a priori.

- Example 2. Given a set of patients with autism spectrum disorders, the aim is to discover a cluster of patients that share the same characteristics. The clusters are not known a priori. Examples 1 and 2 will be referred to as clustering tasks.

- Example 3. Given a large set of medical characteristics (various biological measurements, clinical and cognitive tests, medical images), find a small set of variables that best explain the variability of the dataset. This is a dimensionality reduction problem.

(continued)
**Box 2 (continued)**

* **Reinforcement learning.** Learns by iteratively performing actions to maximize some reward

- Classical approach used for learning to play games (chess, go, etc.) or in the domain of robotics

- Currently few applications in the domain of brain diseases

### 3.1.1 Supervised Learning

In supervised learning, the machine learns to perform a task by examining a set of examples for which the output is known (i.e., the examples have been labeled). The two most common tasks in supervised learning are classification and regression (Fig. 7). Classification aims at assigning a category for each sample. The examples can, for instance, be different patients, and the categories are the different possible diagnoses. The outputs are thus discrete. Examples of common classification algorithms include logistic regression (in spite of its name, it is a classification method), linear discriminant analysis, support vector machines, random forest classifiers, and deep learning models for classification. In regression, the output is a continuous number. This can be, for example, the future clinical score of a patient that we are trying to predict. Examples of common regression methods include simple or multiple linear regression, penalized regression, and random forest regression. Finally, there are many other tasks that can be framed as a supervised learning problem, including, for example, data synthesis, image segmentation, and many others which will be described in other chapters of this book.

### 3.1.2 Unsupervised Learning

In unsupervised learning, the examples are not labeled. The two most common tasks in unsupervised learning are clustering and dimensionality reduction (Fig. 8). Clustering aims at discovering groups within the training set, but these groups are not known a priori. The objective is to find groups such that members of the same group are similar, while members of different groups are dissimilar. For example, one can aim to discover disease subtypes which are not known a priori. Some classical clustering methods are k-means or spectral clustering, for instance. Dimensionality reduction aims at finding a space of variables (of lower dimension than the input space) that best explain the variability of the training data, given a larger set of input variables. This produces a new set of variables that, in general, are not among the input variables but are combinations of them. Examples of such methods include principal component analysis, Laplacian eigenmaps, or variational autoencoders.
<figure><img src="image_12.png" /><figcaption>**Fig. 7** Two of the main supervised learning tasks: classification and regression. The upper panel presents a classification task which aims at linearly separating the orange and the blue class. Each sample is described by two variables. The lower panel presents a linear regression task in which the aim is to predict the body mass index from the age of a person. *Figure courtesy of Johann Faouzi*</figcaption></figure>

**3.1.3 Reinforcement**
**Learning**

In reinforcement learning, the machine will take a series of actions in order to maximize a reward. This can, for example, be the case of a machine learning to play chess, which will play games against itself in order to maximize the number of victories. These methods are widely used for learning to play games or in the domain of robotics. So far, they have had few applications to brain diseases and will not be covered in the rest of this book.

**3.1.4 Discussion**

Unsupervised learning is obviously attractive because it does not require labels. Indeed, acquiring labels for a training set is usually time-consuming and expensive because the labels need to be assigned by a human. This is even more problematic in medicine because the labels must be provided by experts in the field. It is thus in principle attractive to adopt unsupervised strategies, even for
Clustering

<figure><img src="image_13.png" /><figcaption>**Fig. 8** Clustering task. The algorithm automatically identifies three groups (corresponding to the red circles) from unlabeled examples (the blue dots). The groups are not known a priori. *Figure courtesy of Johann Faouzi*</figcaption></figure>

tasks which could be framed as supervised learning problems. Nevertheless, up to now, the performances of supervised approaches are often vastly superior in many applications. However, in the past years, an alternative strategy called self-supervised learning, where the machine itself provides its own supervision, has emerged. This is a promising approach which has already led to impressive results in different fields such as natural language processing in particular [32–34].

## 3.2 Overview of the Learning Process

In this section, we aim at formalizing the main concepts underlying most supervised learning methods. Some of these concepts, with modifications, also extend to unsupervised cases.

The task that we will consider will be to provide an output, denoted as $y$, from an input given to the computer, denoted as $x$. At this moment, the nature of $x$ does not matter. It can, for example, be any possible photograph as in the example presented in Fig. 9. It could also be a single number, a series of numbers, a text, etc. For now, the nature of $y$ can also be varied. Typically, in the case of regression, it can be a number. In the case of classification, it corresponds to a label (for instance, the label “cat” in our example). For now, you do not need to bother about how these data (images, labels, etc.) are represented in a computer. For those without a background in computer science, this will be briefly covered in Subheading 3.3.

Learning will aim at finding a function $f$ that can transform $x$ into $y$, that is, such that $y=f(x)$. For now, $f$ can be of any type—
<figure><img src="image_14.png" /><figcaption>**Fig. 9** Main concepts underlying supervised learning, here in the case of classification. The aim is to be able to recognize the content of a photograph (the input x) which amounts to assigning it a label (the output y). In other words, we would like to have a function f that transforms x into y. In order to find the function f, we will make use of a training set (x(1), y(1), ..., x(n), y(n)) (which in our case is a set of photographs which have been labeled). All images come from https://commons.wikimedia.org/ and have no usage restriction</figcaption></figure>

just imagine it as an operation that can associate a given x with a given y. In Chap. 3, the functions f will be artificial neural networks. Learning aims at finding a function f which will provide the correct output for each given input. Let us call the loss function and denote ℓ a function that measures the error that is made by the function f. The loss function takes two arguments: the true output y and the predicted output f(x). The lower the loss function value, the closer the predicted output is to the true output. An example of loss function is the classical least squares loss $ℓ(y, f(x)) = (y - f(x))²$, but many others exist. Ideally, the best function f would be the one that produces the minimal error for any possible input x and associated output y, not only those which we have at our disposal, but any other possible new data. Of course, we do not have any possible data at our disposal. Thus, we are going to use a set of data called the training set. In supervised learning, this set is labeled, i.e., for each example in this set, we know the value of both x and y. Let us denote as (x(1), y(1), ..., x(n), y(n)) the n examples of the training
set which are *n* pairs of inputs and outputs. We are now going to search for the function *f* that makes the minimum error over the *n* samples of the training set. In other words, we are looking for the function which minimizes the average error over the training set. Let us call this average error the cost function:

$$J(f) = \frac{1}{n} \sum_{i=1}^{n} \ell(y^{(i)}, f(x^{(i)}))$$

Learning will then aim at finding the function $\hat{f}$ which minimizes the cost function:

$$\hat{f} = \arg \min_{f \in \mathcal{F}} \frac{1}{n} \sum_{i=1}^{n} \ell(y^{(i)}, f(x^{(i)}))$$

In the above equation, *argmin* indicates that we are interested in the function *f* that minimizes the cost $J(f)$ and not in the value of the cost itself. *F* is the space that contains all admissible functions. *F* can, for instance, be the set of linear functions or the set of neural networks with a given architecture.

The procedure that will aim at finding *f* that minimizes the cost is called an *optimization procedure*. Sometimes, the minimum can be found analytically (i.e., by directly solving an equation for *f*), but this will rarely be the case. In other cases, one will resort to an iterative procedure (i.e., an algorithm): the function *f* is iteratively modified until we find the function which minimizes the cost. There are cases where we will have an algorithm that is guaranteed to find the global minimum and others where one will only find a local minimum.

Minimizing the errors on the training set does not guarantee that the trained computer will perform well on new examples which were not part of the training set. A first reason may be that the training set is too different from the general population (for instance, we have trained a model on a dataset of young males, and we would like to apply it to patients of any gender and age). Another reason is that, even if the training set characteristics follow those of the general population, the learned function *f* may be too specific to the training set. In other words, it has learned the training set “by heart” but has not discovered a more general rule that would work for other examples. This phenomenon is called *overfitting* and often arises when the dimensionality of the data is too high (there are many variables to represent an input), when the training set is too small, or when the function *f* is too flexible. A way to prevent overfitting will be to modify the cost function so that it not only represents the average error across training samples but also constrains the function *f* to have some specific properties.
<table><caption>**Table 1**

**Example where the input is a series of number. Here each patient is characterized by several variables**</caption><thead><tr><th></th><th>Age (years)</th><th>Height (cm)</th><th>Weight (kg)</th></tr></thead><tbody><tr><td>Patient 1</td><td>52.5</td><td>172</td><td>52</td></tr><tr><td>Patient 2</td><td>75.1</td><td>182</td><td>78</td></tr><tr><td>Patient 3</td><td>32.7</td><td>161</td><td>47</td></tr><tr><td>Patient 4</td><td>45</td><td>190</td><td>92</td></tr></tbody></table>

### 3.3 Inputs and Features

In the previous section, we made no assumption on the nature of the input $x$. It could be an image, a number, a text, etc.

The simplest form of input that one can consider is when $x$ is a single number. Examples include age, clinical scores, etc. However, for most problems, characterization of a patient cannot be done with a single number but requires a large set of measurements (Table 1). In such a case, the input can be a series of numbers $x_1, \dots, x_p$ which can be arranged into a vector:

$$ \boldsymbol{x} = \begin{bmatrix} x_1 \\ \vdots \\ x_p \end{bmatrix} $$

However, there are cases where the input is not a vector of numbers. This is the case when the input is a medical image, a text, or a DNA sequence, for instance. Of course, in a computer, everything is stored as numbers. An image is an array of values representing the grayscale intensity of each pixel (Fig. 10). A text is a sequence of characters which are each coded as a number. However, unlike in the example presented in Table 1, these numbers are not meaningful by themselves. For this reason, a common approach is to extract features, which will be series of numbers that meaningfully represent the input. For example, if the input is a brain magnetic resonance image (MRI), relevant features could be the volumes of different anatomical regions of the brain (this specific process is done using a technique called image segmentation which is covered in another chapter). This would result in a series of numbers that would form an input vector. The development of efficient methods for extracting meaningful features from raw data is important in machine learning. Such an approach is often called *feature engineering*. Deep learning methods allow for avoiding extracting features by providing an end-to-end approach from the raw data to the output. In some areas, this has made feature engineering less important, but there are still applications where the so-called handcrafted features are competitive with deep learning methods.
<figure><img src="image_15.png" /><figcaption>**Fig. 10** In a computer, an image is represented as an array of numbers. Each number corresponds to the gray level of a given pixel. Here the example is a slice of an anatomical MRI which has been severely undersampled so that the different pixels are clearly visible. Note that an anatomical MRI is actually a 3D image and would thus be represented by a 3D array rather than by a 2D array. Image courtesy of Ninon Burgos</figcaption></figure>

**3.4 Illustration in a Simple Case**

We will now illustrate step by step the above concepts in a very simple case: univariate linear regression. Univariate means that the input is a single number as in the example shown in Fig. 7. Linear means that the model $f$ will be a simple line. The input is a number $x$ and the output is a number $y$. The loss will be the least squares loss: $\ell(y, f(x)) = (y - f(x))^2$. The model $f$ will be a linear function of $x$ that is $f(x) = w_1x + w_0$ and corresponds to the equation of a line, $w_1$ being the slope of the line and $w_0$ the intercept. To further simplify things, we will consider the case where there is no intercept, i.e., the line passes through the origin. Different values of $w_1$ correspond to different lines (and thus to different functions $f$) and to different values of the cost function $J(f)$, which can be in our case rewritten as $J(w_1)$ since $f$ only depends on the parameter $w_1$ (Fig. 11). The best model is the one for which $J(w_1)$ is minimal.

How can we find $w_1$ such that $J(w_1)$ is minimal? We are going to use the derivative of $J$: $\frac{dJ}{dw_1}$. A minimum of $J(w_1)$ is necessarily such that $\frac{dJ}{dw_1} = 0$ (in our specific case, the converse is also true). In our case, it is possible to directly solve $\frac{dJ}{dw_1} = 0$. This will nevertheless not be the case in general. Very often, it will not be possible to solve this analytically. We will thus resort to an iterative algorithm. One classical iterative method is *gradient descent*. In the general case, $f$ depends not on only one parameter $w_1$ but on a set of parameters ($w_1, \dots, w_p$) which can be assembled into a vector $w$. Thus, instead of working with the derivative $\frac{dJ}{dw_1}$, we will work with the gradient $\nabla_w J$. The gradient is a vector that indicates the direction that one should follow to climb along $J$. We will thus follow the opposite of the gradient, hence the name gradient descent. This process is illustrated in Fig. 12, together with the corresponding algorithm.
<figure><img src="image_16.png" /><figcaption>**Fig. 11** We illustrate the concepts of supervised learning on a very simple case: univariate linear regression with no intercept. Training samples correspond to the black circles. The different models $f(x) = w_1x$ correspond to the different lines. Each model (and thus each value of the parameter $w_1$) corresponds to a value of the cost $J(w_1)$. The best model (the blue line) is the one which minimizes $J(w_1)$; here it corresponds to the line with a slope $w_1 = 1$.</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>**Fig. 12** Upper panel: Illustration of the concept of gradient descent in a simple case where the model $f$ is defined using only one parameter $w_1$. The value of $w_1$ is iteratively updated by following the opposite of the gradient. Lower panel: Gradient descent algorithm where $\eta$ is the learning rate, i.e., the speed at which $w_1$ will be updated.</figcaption></figure>
# 4 Conclusion

This chapter provided an introduction to machine learning (ML) for a non-technical readership (e.g., physicians, neuroscientists, etc.). ML is an approach to artificial intelligence and thus needs to be put into this larger context. We introduced the main concepts underlying ML that will be further expanded in Chaps. 2–6. The reader can find a summary of these main concepts, as well as notations, in Box 3.

## Box 3: Summary of main concepts

* The input $x$

* The output $y$

* The training samples $(x^{(1)}, y^{(1)}), \dots, (x^{(n)}, y^{(n)})$

* The model: transforms the input into the output

$$f \text{ such that } y = f(x)$$

* The set of possible models $\mathcal{F}$

* The loss: measures the error between the predicted and the true output, for a given sample

$$\ell(y, f(x))$$

* The cost function: measures the average error across the training samples

$$J(f) = \frac{1}{n} \sum_{i=1}^{n} \ell(y^{(i)}, f(x^{(i)}))$$

* Learning process: finding the model which minimizes the cost function

$$\hat{f} = \arg \min_{f \in \mathcal{F}} J(f)$$

# Acknowledgements

The author would like to thank Johann Faouzi for his insightful comments. This work was supported by the French government under management of Agence Nationale de la Recherche as part of the “Investissements d’avenir” program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute) and reference ANR-10-IAIHU-06 (Institut Hospitalo-Universitaire ICM).
## References

1. Samuel AL (1959) Some studies in machine learning using the game of checkers. IBM J Res Dev 3(3):210-229

2. Russell S, Norvig P (2002) Artificial intelligence: a modern approach. Pearson, London

3. McCulloch WS, Pitts W (1943) A logical calculus of the ideas immanent in nervous activity. Bull Math Biophys 5(4):115-133

4. Wiener N (1948) Cybernetics or control and communication in the animal and the machine. MIT Press, Cambridge

5. Hebb DO (1949) The organization of behavior. Wiley, New York

6. Turing AM (1950) Computing machinery and intelligence. Mind 59(236):433-360

7. McCarthy J, Minsky ML, Rochester N, Shanon CE (1955) A proposal for the Dartmouth summer research project on artificial intelligence. Research Report. http://raysolomonoff.com/dartmouth/boxa/dart564props.pdf

8. Newell A, Simon H (1956) The logic theory machine-a complex information processing system. IRE Trans Inf Theory 2(3):61-79

9. Rosenblatt F (1958) The perceptron: a probabilistic model for information storage and organization in the brain. Psychol Rev 65(6): 386

10. Buchanan BG, Shortliffe EH (1984) Rule-based expert systems: the MYCIN experiments of the Stanford Heuristic Programming Project. Addison-Wesley, Boston

11. McCarthy J (1960) Recursive functions of symbolic expressions and their computation by machine, part I. Commun ACM 3(4): 184-195

12. Cardon D, Cointet JP, Mazières A, Libbrecht E (2018) Neurons spike back. Reseaux 5:173-220. https://neurovenge.antonomase.fr/RevengeNeurons_Reseaux.pdf

13. Rumelhart DE, Hinton GE, Williams RJ (1986) Learning representations by back-propagating errors. Nature 323(6088): 533-536

14. Le Cun Y (1985) Une procédure d'apprentissage pour réseau à seuil assymétrique. Cognitiva 85:599-604

15. LeCun Y, Boser B, Denker JS, Henderson D, Howard RE, Hubbard W, Jackel LD (1989) Backpropagation applied to handwritten zip

code recognition. Neural Comput 1(4): 541-551

16. Matan O, Baird HS, Bromley J, Burges CJC, Denker JS, Jackel LD, Le Cun Y, Pednault EPD, Satterfield WD, Stenard CE et al (1992) Reading handwritten digits: a zip code recognition system. Computer 25(7):59-63

17. Legendre AM (1806) Nouvelles méthodes pour la détermination des orbites des comètes. Firmin Didot

18. Pearson K (1901) On lines and planes of closest fit to systems of points in space. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science 2(11):559-572

19. Fisher RA (1936) The use of multiple measurements in taxonomic problems. Ann Eugenics 7(2):179-188

20. Loh WY (2014) Fifty years of classification and regression trees. Int Stat Rev 82(3):329-348

21. Quinlan JR (1986) Induction of decision trees. Mach Learn 1(1):81-106

22. Vapnik V (1999) The nature of statistical learning theory. Springer, Berlin

23. Boser BE, Guyon IM, Vapnik VN (1992) A training algorithm for optimal margin classifiers. In: Proceedings of the fifth annual workshop on computational learning theory, pp 144-152

24. Pedregosa F, Varoquaux G, Gramfort A, Michel V, Thirion B et al (2011) Scikit-learn: Machine learning in python. J Mach Learn Res 12:2825-2830

25. Krizhevsky A, Sutskever I, Hinton GE (2012) ImageNet classification with deep convolutional neural networks. In: Advances in neural information processing systems, vol 25, pp 1097-1105

26. LeCun Y, Bengio Y, Hinton G (2015) Deep learning. Nature 521(7553):436-444

27. Abadi M, Agarwal A et al (2015) TensorFlow: Large-scale machine learning on heterogeneous systems. https://www.tensorflow.org/, software available from tensorflow.org

28. Paszke A, Gross S, Massa F, Lerer A, Bradbury J, Chanan G, Killeen T, Lin Z, Gimelshein N, Antiga L et al (2019) PyTorch: An imperative style, high-performance deep learning library. In: Advances in neural information processing systems, vol 32, pp 8026-8037
29. Chollet F et al (2015) Keras. https://github.com/fchollet/keras

30. Shortliffe E (1976) Computer-based medical consultations: MYCIN. Elsevier, Amsterdam

31. Mitchell T (1997) Machine learning. McGraw Hill, New York

32. Mikolov T, Chen K, Corrado G, Dean J (2013) Efficient estimation of word representations in vector space. arXiv preprint arXiv:13013781

33. Radford A, Narasimhan K, Salimans T, Sutskever I (2018) Improving language understanding by generative pre-training. https://doi.org/10.7455/EN.00000000-0000-0000-0000-0000-0000
34. Devlin J, Chang MW, Lee K, Toutanova K (2018) Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:181004805

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

<figure><img src="image_18.png" /></figure>
**Classic Machine Learning Methods**

Johann Faouzi and Olivier Colliot

**Abstract**

In this chapter, we present the main classic machine learning methods. A large part of the chapter is devoted to supervised learning techniques for classification and regression, including nearest neighbor methods, linear and logistic regressions, support vector machines, and tree-based algorithms. We also describe the problem of overfitting as well as strategies to overcome it. We finally provide a brief overview of unsupervised learning methods, namely, for clustering and dimensionality reduction. The chapter does not cover neural networks and deep learning as these will be presented in Chaps. 3, 4, 5, and 6.

**Key words** Machine learning, Classification, Regression, Clustering, Dimensionality reduction

# 1 Introduction

This chapter presents the main classic machine learning (ML) methods. There is a focus on supervised learning methods for classification and regression, but we also describe some unsupervised approaches. The chapter is meant to be readable by someone with no background in machine learning. It is nevertheless necessary to have some basic notions of linear algebra, probabilities, and statistics. If this is not the case, we refer the reader to Chapters 2 and 3 of [1].

The rest of this chapter is organized as follows. Rather than grouping methods by categories (for instance, classification or regression methods), we chose to present methods by increasing order of complexity. We first provide the notations in Subheading 2. We then describe a very intuitive family of methods, that of nearest neighbors (Subheading 3). We continue with linear regression (Subheading 4) and logistic regression (Subheading 5), the latter being a classification technique. We subsequently introduce the problem of overfitting (Subheading 6) as well as strategies to mitigate it (Subheading 7). Subheading 8 describes support vector machines (SVM). Subheading 9 explains how binary classification methods can be extended to a multi-class setting. We then describe
methods which are specifically adapted to the case of normal distributions (Subheading 10). Decision trees and random forests are described in Subheading 11. We then briefly describe some unsupervised learning techniques, namely, for clustering (Subheading 12) and dimensionality reduction (Subheading 13). The chapter ends with a description of kernel methods which can be used to extend linear techniques to non-linear cases (Subheading 14). Box 1 summarizes the methods presented in this chapter, grouped by categories and then sorted in order of appearance.

## Box 1: Main Classic ML Methods

* **Supervised learning**

- **Classification**: nearest neighbors, logistic regression, support vector machine (SVM), naive Bayes, linear discriminant analysis (LDA), quadratic discriminant analysis, tree-based models (decision tree, random forest, extremely randomized trees)

- **Regression**: nearest neighbors, linear regression, support vector machine regression, tree-based models (decision tree, random forest, extremely randomized trees), kernel ridge regression

* **Unsupervised learning**

- **Clustering**: k-means, Gaussian mixture model

- **Dimensionality reduction**: principal component analysis (PCA), linear discriminant analysis (LDA), kernel principal component analysis

## 2 Notations

Let $n$ be the number of samples and $p$ be the number of features. An input sample is thus a $p$-dimensional vector:

$$ \mathbf{x} = \begin{bmatrix} x_1 \\ \vdots \\ x_p \end{bmatrix} $$

An output sample is denoted by $\mathbf{y}$. Thus, a sample is $(\mathbf{x}, \mathbf{y})$. The dataset of $n$ samples can then be summarized as an $n \times p$ matrix $\mathbf{X}$ representing the input data and an $n$-dimensional vector $\mathbf{y}$ representing the target data:
$$X = \begin{bmatrix} \mathbf{x}^{(1)} \\ \vdots \\ \mathbf{x}^{(n)} \end{bmatrix} = \begin{bmatrix} x_1^{(1)} & \dots & x_p^{(1)} \\ \vdots & \ddots & \vdots \\ x_1^{(n)} & \dots & x_p^{(n)} \end{bmatrix}, \quad y = \begin{bmatrix} y_1 \\ \vdots \\ y_n \end{bmatrix}$$

The input space is denoted by $I$, and the set of training samples is denoted by $\mathbf{x}$.

In the case of regression, $y$ is a real number. In the case of classification, $y$ is a single label. More precisely, $y$ can only take one of a finite set of values called labels. The set of possible classes (i.e., labels) is denoted by $C = \{C_1, \dots, C_q\}$, with $q$ being the number of classes. As the values of the classes are not meaningful, when there are only two classes, the classes are often called the positive and negative classes. In this case and also for mathematical reasons, without loss of generality, we assume the values of the classes to be +1 and -1.

## 3 Nearest Neighbor Methods

One of the most intuitive approaches to machine learning is nearest neighbors. It is based on the following intuition: for a given input, its corresponding output is likely to be similar to the outputs of similar inputs. A real-life metaphor would be that if a subject has similar characteristics than other subjects who were diagnosed with a given disease, then this subject is likely to also be suffering from this disease.

More formally, nearest neighbor methods use the training samples from the neighborhood of a given point $\mathbf{x}$, denoted by $N(\mathbf{x})$, to perform prediction [2].

For regression tasks, the prediction is computed as a weighted mean of the target values in $N(\mathbf{x})$:

$$\hat{y} = \sum_{\mathbf{x}^{(i)} \in N(\mathbf{x})} w_i^{(\mathbf{x})} y^{(i)}$$

where $w_i^{(\mathbf{x})}$ is the weight associated with $\mathbf{x}^{(i)}$ to predict the output of $\mathbf{x}$, with $w_i^{(\mathbf{x})} \ge 0 \forall i$ and $\sum_i w_i^{(\mathbf{x})} = 1$.

For classification tasks, the predicted label corresponds to the label with the largest weighted sum of occurrences of each label:

$$\hat{y} = \arg \max_{C} \sum_{\mathbf{x}^{(i)} \in N(\mathbf{x})} w_i^{(\mathbf{x})} \mathbf{1}_{y^{(i)} = C_k}$$

A key parameter of nearest neighbor methods is the *metric*, denoted by $d$, that is, a mathematical function that defines dissimilarity. The metric is used to define the neighborhood of any point and can also be used to compute the weights.
**3.1 Metrics**

Many metrics have been defined for various types of input data such as vectors of real numbers, integers, or booleans. Among these different types, vectors of real numbers are one of the most common types of input data, for which the most commonly used metric is the Euclidean distance, defined as:

$$ \forall \mathbf{x}, \mathbf{x}' \in I, \|\mathbf{x} - \mathbf{x}'\|_2 = \sqrt{\sum_{j=1}^{p} (x_j - x'_j)^2} $$

The Euclidean distance is sometimes referred to as the “ordinary” distance since it is the one based on the Pythagorean theorem and that everyone uses in their everyday lives.

**3.2 Neighborhood**

The two most common definitions of the neighborhood rely on either the number of neighbors or the radius around the given point. Figure 1 illustrates the differences between both definitions.

The k-nearest neighbor method defines the neighborhood of a given point x as the set of the k closest points to x:

$$ N(\mathbf{x}) = \{\mathbf{x}^{(i)}\}_{i=1}^{k} \quad \text{with} \quad d(\mathbf{x}, \mathbf{x}^{(1)}) \le \dots \le d(\mathbf{x}, \mathbf{x}^{(n)}) $$

The radius neighbor method defines the neighborhood of a given point x as the set of points whose dissimilarity to x is smaller than the given radius, denoted by r:

$$ N(\mathbf{x}) = \{\mathbf{x}^{(i)} \in X \mid d(\mathbf{x}, \mathbf{x}^{(i)}) < r\} $$

<figure><img src="image_19.png" /><figcaption>**Fig. 1** Different definitions of the neighborhood. On the left, the neighborhood of a given point is the set of its five nearest neighbors. On the right, the neighborhood of a given point is the set of points whose dissimilarity is lower than the radius. For a given input, its neighborhood may be different depending on the definition used. The Euclidean distance is used as the metric in both examples</figcaption></figure>
**3.3 Weights**

The two most common approaches to compute the weights are to use:

* Uniform weights (all the weights are equal):

$$ \forall i, w_i^{(x)} = \frac{1}{|N(\boldsymbol{x})|} $$

* Weights inversely proportional to the dissimilarity:

$$ \forall i, w_i^{(x)} = \frac{\frac{1}{d(\boldsymbol{x}^{(i)}, \boldsymbol{x})}}{\sum_j \frac{1}{d(\boldsymbol{x}^{(j)}, \boldsymbol{x})}} = \frac{1}{d(\boldsymbol{x}^{(i)}, \boldsymbol{x}) \sum_j \frac{1}{d(\boldsymbol{x}^{(j)}, \boldsymbol{x})}} $$

With uniform weights, every point in the neighborhood equally contributes to the prediction. With weights inversely proportional to the dissimilarity, closer points contribute more to the prediction than further points. Figure 2 illustrates the different decision functions obtained with uniform weights and weights inversely proportional to the dissimilarity for a 3-nearest neighbor classification model.

**3.4 Neighbor Search**

The brute-force method to compute the neighborhood for n points with p features is to compute the metric for each pair of inputs, which has a $O(n^2p)$ algorithmic complexity (assuming that evaluating the metric for a pair of inputs has a complexity of $O(p)$, which is the case for most metrics). However, it is possible to decrease this algorithmic complexity if the metric is a *distance*, that is, if the metric *d* satisfies the following properties:

1. Non-negativity: $\forall \boldsymbol{a}, \boldsymbol{b}, d(\boldsymbol{a}, \boldsymbol{b}) \ge 0$

2. Identity: $\forall \boldsymbol{a}, \boldsymbol{b}, d(\boldsymbol{a}, \boldsymbol{b}) = 0$ if and only if $\boldsymbol{a} = \boldsymbol{b}$

<figure><img src="image_20.png" /><figcaption>**Fig. 2** Impact of the definition of the weights on the prediction function of a 3-nearest neighbor classification model. When the weights are inversely proportional to the dissimilarity, the classifier is more subject to outliers since the predictions in the close neighborhood of any input are mostly dedicated by the label of this input, independently of the number of neighbors used. With uniform weights, the prediction function tends to be smoother</figcaption></figure>
3. Symmetry: $\forall \mathbf{a}, \mathbf{b}, d(\mathbf{a}, \mathbf{b}) = d(\mathbf{b}, \mathbf{a})$

4. Triangle inequality: $\forall \mathbf{a}, \mathbf{b}, \mathbf{c}, d(\mathbf{a}, \mathbf{b}) + d(\mathbf{b}, \mathbf{c}) \ge d(\mathbf{a}, \mathbf{c})$

The key property is the *triangle inequality*, which has a simple interpretation: the shortest path between two points is a straight line. Mathematically, if $\mathbf{a}$ is far from $\mathbf{c}$ and $\mathbf{c}$ is close to $\mathbf{b}$ (i.e., $d(\mathbf{a}, \mathbf{c})$ is large and $d(\mathbf{b}, \mathbf{c})$ is small), then $\mathbf{a}$ is far from $\mathbf{b}$ (i.e., $d(\mathbf{a}, \mathbf{b})$ is large). This is obtained by rewriting the triangle inequality as follows:

$$ \forall \mathbf{a}, \mathbf{b}, \mathbf{c}, d(\mathbf{a}, \mathbf{b}) \ge d(\mathbf{a}, \mathbf{c}) - d(\mathbf{b}, \mathbf{c}) $$

This means that it is not necessary to compute $d(\mathbf{a}, \mathbf{b})$ in this case. Therefore, the computational cost of a nearest neighbor search can be reduced to $O(n\log(n)p)$ or better, which is a substantial improvement over the brute-force method for large $n$. Two popular methods that take advantage of this property are the *K-dimensional tree structure* [3] and the *ball tree structure* [4].

# 4 Linear Regression

Linear regression is a regression model that linearly combines the features. Each feature is associated with a coefficient that represents the relative weight of this feature compared to the other features. A real-life metaphor would be to see the coefficients as the ingredients of a recipe: the key is to find the best balance (i.e., proportions) between all the ingredients in order to make the best cake.

Mathematically, a linear model is a model that linearly combines the features [5]:

$$ f(\mathbf{x}) = w_0 + \sum_{j=1}^{p} w_j x_j $$

A common notation consists in including a 1 in $\mathbf{x}$ so that $f(\mathbf{x})$ can be written as the *dot product* between the vector $\mathbf{x}$ and the vector $\mathbf{w}$:

$$ f(\mathbf{x}) = w_0 \times 1 + \sum_{j=1}^{p} w_j x_j = \mathbf{x}^{\top} \mathbf{w} $$

where the vector $\mathbf{w}$ consists of:

* The intercept (also known as bias) $w_0$

* The coefficients ($w_1, \dots, w_p$), where each coefficient $w_j$ is associated with the corresponding feature $x_j$

In the case of linear regression, $f(\mathbf{x})$ is the predicted output:

$$ \hat{y} = f(\mathbf{x}) = \mathbf{x}^{\top} \mathbf{w} $$
<figure><img src="image_21.png" /><figcaption>**Fig. 3** Ordinary least squares regression. The coefficients (i.e., the intercept and the slope with a single predictor) are estimated by minimizing the sum of the squared errors</figcaption></figure>

There are several methods to estimate the *w* coefficients. In this section, we present the oldest one which is known as ordinary least squares regression.

In the case of ordinary least squares regression, the cost function *J* is the sum of the squared errors on the training data (see Fig. 3):

$$J(\mathbf{w}) = \sum_{i=1}^{n} (y^{(i)} - \hat{y}^{(i)})^2 = \sum_{i=1}^{n} (y^{(i)} - \mathbf{x}^{(i)\top} \mathbf{w})^2 = \|\mathbf{y} - \mathbf{X}\mathbf{w}\|_2^2$$

One wants to find the optimal parameters $\mathbf{w}^*$ that minimize the cost function:

$$\mathbf{w}^* = \arg\min_{\mathbf{w}} J(\mathbf{w})$$

This optimization problem is *convex*, implying that any local minimum is a global minimum, and *differentiable*, implying that every local minimum has a null gradient. One therefore aims to find null gradients of the cost function:

$$\begin{align*}
\nabla_{\mathbf{w}^*} J &= 0 \\
\Rightarrow \quad 2\mathbf{X}^\top \mathbf{X} \mathbf{w}^* - 2\mathbf{X}^\top \mathbf{y} &= 0 \\
\Rightarrow \quad \mathbf{X}^\top \mathbf{X} \mathbf{w}^* &= \mathbf{X}^\top \mathbf{y} \\
\Rightarrow \quad \mathbf{w}^* &= (\mathbf{X}^\top \mathbf{X})^{-1} \mathbf{X}^\top \mathbf{y}
\end{align*}$$

Ordinary least squares regression is one of the few machine learning optimization problems for which there exists a closed formula, i.e., the optimal solution can be computed using a finite number of standard operations such as addition, multiplication,
and evaluations of well-known functions. A summary of linear regression can be found in Box 2.

Box 2: Linear Regression

• Main idea: best hyperplane (i.e., line when $p=1$, plane when $p=2$) mapping the inputs and to the outputs.

• Mathematical formulation: linear relationship between the predicted output $\hat{y}$ and the input $x$ that minimizes the sum of squared errors:

$$ \hat{y} = w_0^* + \sum_{j=1}^{n} w_j^* x_j \quad \text{with} \quad w^* = \arg \min_{w} \sum_{i=1}^{n} (y^{(i)} - x^{(i)\top} w)^2 $$

• Regularization: can be penalized to avoid overfitting (ridge), to perform feature selection (lasso), or both (elastic-net). See Subheading 7.

5 Logistic Regression

Intuitively, linear regression consists in finding the line that best fits the data: the true output should be as close to the line as possible. For binary classification, one wants the line to separate both classes as well as possible: the samples from one class should all be in one subspace, and the samples from the other class should all be in the other subspace, with the inputs being as far as possible from the line.

Mathematically, for binary classification tasks, a linear model is defined by a hyperplane splitting the input space into two subspaces such that each subspace is characteristic of one class. For instance, a line splits a plane into two subspaces in the two-dimensional case, while a plane splits a three-dimensional space into two subspaces. A hyperplane is defined by a vector $w = (w_0, w_1, \dots, w_p)$, and $f(x) = x^\top w$ corresponds to the signed distance between the input $x$ and the hyperplane $w$: in one subspace, the distance with any input is always positive, whereas in the other subspace, the distance with any input is always negative. Figure 4 illustrates the decision function in the two-dimensional case where both classes are linearly separable.

The sign of the signed distance corresponds to the decision function of a linear binary classification model:

$$ \hat{y} = \mathrm{sign}(f(\boldsymbol{x})) = \begin{cases} +1 & \text{if } f(\boldsymbol{x}) > 0 \\ -1 & \text{if } f(\boldsymbol{x}) < 0 \end{cases} $$
<figure><img src="image_22.png" /><figcaption>**Fig. 4** Decision function of a logistic regression model. A logistic regression is a linear model, that is, its decision function is linear. In the two-dimensional case, it separates a plane with a line</figcaption></figure>

The logistic regression model is a probabilistic linear model that transforms the signed distance to the hyperplane into a probability using the sigmoid function [6], denoted by $\sigma(u) = \frac{1}{1+\exp(-u)}$. Consider the linear model:

$$f(\boldsymbol{x}) = \boldsymbol{x}^{\top} \boldsymbol{w} = w_0 + \sum_{j=1}^{p} w_j x_j$$

Then the probability of belonging to the positive class is:

$$P(y = +1 | \mathbf{x} = \boldsymbol{x}) = \sigma(f(\boldsymbol{x})) = \frac{1}{1 + \exp(-f(\boldsymbol{x}))}$$

and that of belonging to the negative class is:

$$\begin{aligned} P(y = -1 | \mathbf{x} = \boldsymbol{x}) &= 1 - P(y = +1 | \mathbf{x} = \boldsymbol{x}) \\ &= \frac{\exp(-f(\boldsymbol{x}))}{1 + \exp(-f(\boldsymbol{x}))} \\ &= \frac{1}{1 + \exp(f(\boldsymbol{x}))} \\ P(y = -1 | \mathbf{x} = \boldsymbol{x}) &= \sigma(-f(\boldsymbol{x})) \end{aligned}$$

By applying the inverse of the sigmoid function, which is known as the logit function, one can see that the logarithm of the *odds ratio* is modeled as a linear combination of the features:

$$\log\left(\frac{P(y = +1 | \mathbf{x} = \boldsymbol{x})}{P(y = -1 | \mathbf{x} = \boldsymbol{x})}\right) = \log\left(\frac{P(y = +1 | \mathbf{x} = \boldsymbol{x})}{1 - P(y = +1 | \mathbf{x} = \boldsymbol{x})}\right) = f(\boldsymbol{x})$$
The w coefficients are estimated by maximizing the likelihood function, that is, the function measuring the goodness of fit of the model to the training data:

$$L(\mathbf{w}) = \prod_{i=1}^{n} P(y = y^{(i)} | \mathbf{x} = \mathbf{x}^{(i)}; \mathbf{w})$$

For computational reasons, it is easier to maximize the log-likelihood, which is simply the logarithm of the likelihood:

$$\begin{align*}
\log(L(\mathbf{w})) &= \sum_{i=1}^{n} \log(P(y = y^{(i)} | \mathbf{x} = \mathbf{x}^{(i)}; \mathbf{w})) \\
&= \sum_{i=1}^{n} \log(\sigma(y^{(i)} f(\mathbf{x}^{(i)}; \mathbf{w}))) \\
&= \sum_{i=1}^{n} -\log(1 + \exp(y^{(i)} \mathbf{x}^{(i)\top} \mathbf{w})) \\
\log(L(\mathbf{w})) &= -\sum_{i=1}^{n} \log(1 + \exp(y^{(i)} \mathbf{x}^{(i)\top} \mathbf{w}))
\end{align*}$$

Finally, we can rewrite this maximization problem as a minimization problem by noticing that $\max_{\mathbf{w}} \log(L(\mathbf{w})) = - \min_{\mathbf{w}} \log(L(\mathbf{w}))$:

$$\max_{\mathbf{w}} \log(L(\mathbf{w})) = - \min_{\mathbf{w}} \sum_{i=1}^{n} \log(1 + \exp(y^{(i)} \mathbf{x}^{(i)\top} \mathbf{w}))$$

We can see that the w coefficients that maximize the likelihood are also the coefficients that minimize the sum of the logistic loss values, with the logistic loss being defined as:

$$\ell_{\text{logistic}}(y, f(\mathbf{x})) = \log(1 + \exp(yf(\mathbf{x}))) / \log(2)$$

Unlike for linear regression, there is no closed formula for this minimization. One thus needs to use an optimization method such as gradient descent which was presented in Subheading 3 of Chap. 1. In practice, more sophisticated approaches such as quasi-Newton methods and variants of stochastic gradient descent are often used. The main concepts underlying logistic regression can be found in Box 3.

### Box 3: Logistic Regression

* **Main idea:** best hyperplane (i.e., line) that separates two classes.

* **Mathematical formulation:** the signed distance to the hyperplane is mapped into the probability to belong to the positive class using the sigmoid function:

(continued)
**Box 3 (continued)**

$$f(\mathbf{x}) = w_0 + \sum_{j=1}^{n} w_j x_j$$
$$P(y = +1 | \mathbf{x} = \mathbf{x}_0) = \sigma(f(\mathbf{x})) = \frac{1}{1 + \exp(-f(\mathbf{x}))}$$

* **Estimation**: likelihood maximization.

* **Regularization**: can be penalized to avoid overfitting ($\ell_2$ penalty), to perform feature selection ($\ell_1$ penalty), or both (elastic-net penalty).

# 6 Overfitting and Regularization

The original formulations of ordinary least squares regression and logistic regression are *unregularized* models, that is, the model is trained to fit the training data as much as possible. Let us consider a real-life example as it is very similar to human learning. If a person learns by heart the content of a book, they are able to solve the exercises in the book, but unable to apply the theoretical concepts to new exercises or real-life situations. If a person only quickly reads through the book, they are probably unable to solve neither the exercises in the book nor new exercises.

The corresponding concepts are known as *overfitting* and *underfitting* in machine learning. Overfitting occurs when a model fits too well the training data and generalizes poorly to new data. Oppositely, underfitting occurs when a model does not capture well enough the characteristics of the training data and thus also generalizes poorly to new data.

Overfitting and underfitting are related to frequently used terms in machine learning: *bias* and *variance*. Bias is defined as the expected (i.e., mean) difference between the true output and the predicted output. Variance is defined as the variability of the predicted output. For instance, let us consider a model predicting the age of a person from a picture. If the model *always* underestimates or overestimates the age, then the model is biased. If the model makes *both large and small errors*, then the model has a high variance.

Ideally, one would like to have a model with a small bias and a small variance. However, the bias of a model tends to increase when decreasing its variance, and the variance of the model tends to increase when decreasing its bias. This phenomenon is known as the *bias-variance trade-off*. Figure 5 illustrates this phenomenon. One can also notice it by computing the squared error between the true output $y$ (fixed) and the predicted output $\hat{y}$ (random variable): its expected value is the sum of the squared bias of $\hat{y}$ and the variance of $\hat{y}$:
<figure><img src="image_23.png" /><figcaption>**Fig. 5** Illustration of underfitting and overfitting. Underfitting occurs when a model is too simple and does not capture well enough the characteristics of the training data, leading to high bias and low variance. Oppositely, overfitting occurs when a model is too complex and learns the noise in the training data, leading to low bias and high variance.</figcaption></figure>
$$
\begin{align*}
\mathbb{E}[(y - \hat{y})^2] &= \mathbb{E}[y^2 - 2y\hat{y} + \hat{y}^2] \\
&= y^2 - 2y\mathbb{E}[\hat{y}] + \mathbb{E}[\hat{y}^2] \\
&= y^2 - 2y\mathbb{E}[\hat{y}] + \mathbb{E}[\hat{y}^2] + \mathbb{E}[\hat{y}]^2 - \mathbb{E}[\hat{y}]^2 \\
&= (\mathbb{E}[\hat{y}] - y)^2 + \mathbb{E}[\hat{y}^2] - \mathbb{E}[\hat{y}]^2 \\
&= (\mathbb{E}[\hat{y}] - y)^2 + \mathbb{E}[\hat{y}^2 - \mathbb{E}[\hat{y}]^2] \\
&= (\mathbb{E}[\hat{y}] - y)^2 + \mathbb{E}[\hat{y}^2 - 2\mathbb{E}[\hat{y}]^2 + \mathbb{E}[\hat{y}]^2] \\
&= (\mathbb{E}[\hat{y}] - y)^2 + \mathbb{E}[\hat{y}^2 - 2\hat{y}\mathbb{E}[\hat{y}] + \mathbb{E}[\hat{y}]^2] \\
&= (\mathbb{E}[\hat{y}] - y)^2 + \mathbb{E}[(\hat{y} - \mathbb{E}[\hat{y}])^2]
\end{align*}
$$

$$
\mathbb{E}[(y - \hat{y})^2] = \underbrace{(\mathbb{E}[\hat{y}] - y)^2}_{\text{bias}^2} + \underbrace{\text{Var}[\hat{y}]}_{\text{variance}}
$$

7 Penalized Models

Depending on the class of methods, there exist different strategies
to tackle overfitting.

For neighbor methods, the number of neighbors used to define
the neighborhood of any input and the strategy to compute the
weights are the key hyperparameters to control the bias-variance
trade-off. For models that are presented in the remaining sections
of this chapter, we mention strategies to address the bias-variance
trade-off in their respective sections. In this section, we present the
most commonly used strategies for models whose parameters are
optimized by minimizing a cost function defined as the mean loss
values over all the training samples:

$$
\min_{\mathbf{w}} J(\mathbf{w}) \quad \text{with} \quad J(\mathbf{w}) = \frac{1}{n} \sum_{i=1}^{n} \ell(y^{(i)}, f(\mathbf{x}^{(i)}; \mathbf{w}))
$$

This is, for instance, the case of the linear and logistic regression
methods presented in the previous sections.

7.1 Penalties

The main idea is to introduce a *penalty term* Pen(*w*) that will
constraint the parameters *w* to have some desired properties. The
most common penalties are the *ℓ*₂ penalty, the *ℓ*₁ penalty, and the
elastic-net penalty.

7.1.1 ℓ₂ Penalty

The ℓ₂ penalty is defined as the squared ℓ₂ norm of the
w coefficients:
$$ \ell_2(\mathbf{w}) = \|\mathbf{w}\|_2^2 = \sum_{j=1}^{p} w_j^2 $$

The $\ell_2$ penalty forces each coefficient $w_i$ not to be too large and makes the coefficients more robust to collinearity (i.e., when some features are approximately linear combinations of the other features).

### 7.1.2 $\ell_1$ Penalty

The $\ell_2$ penalty forces the values of the parameters not to be too large, but does not incentivize to make small values tend to zero. Indeed, the square of a small value is even smaller. When the number of features is large, or when interpretability is important, it can be useful to make the model select the most important features. The corresponding metric is the $\ell_0$ “norm” (which is not a proper norm in the mathematical sense), defined as the number of nonzero elements:

$$ \ell_0(\mathbf{w}) = \|\mathbf{w}\|_0 = \sum_{j=1}^{p} \mathbf{1}_{w_j \neq 0} $$

However, the $\ell_0$ “norm” is neither differentiable nor convex (which are useful properties to solve an optimization problem, but this is not further detailed for the sake of conciseness). The best convex differentiable approximation of the $\ell_0$ “norm” is the $\ell_1$ norm (see Fig. 6), defined as the sum of the absolute values of each element:

$$ \ell_1(\mathbf{w}) = \|\mathbf{w}\|_1 = \sum_{j=1}^{p} |w_j| $$

### 7.1.3 Elastic-Net Penalty

Both the $\ell_2$ and $\ell_1$ penalties have their upsides and downsides. In order to try to obtain the best of penalties, one can add both penalties in the objective function. The combination of both penalties is known as the elastic-net penalty:

$$ \mathrm{EN}(\mathbf{w}, \alpha) = \alpha \|\mathbf{w}\|_1 + (1 - \alpha) \|\mathbf{w}\|_2^2 $$

where $\alpha \in [0, 1]$ is a hyperparameter representing the proportion of the $\ell_1$ penalty compared to the $\ell_2$ penalty.

## 7.2 New Optimization Problem

A natural approach would be to add a constraint to the minimization problem:

$$ \min_{\mathbf{w}} J(\mathbf{w}) \quad \text{subject to} \quad \mathrm{Pen}(\mathbf{w}) < c \quad (1) $$

which reads as “Find the optimal parameters that minimize the cost function $J$ among all the parameters $\mathbf{w}$ that satisfy $\mathrm{Pen}(\mathbf{w}) < c$” for a positive real number $c$. Figure 7 illustrates the optimal solution of a simple linear regression task with different constraints. This figure
<figure><img src="image_24.png" /><figcaption>**Fig. 6** Unit balls of the $l_0$, $l_1$, and $l_2$ norms. For each norm, the set of points in $\mathbb{R}^2$ whose norm is equal to 1 is plotted. The $l_1$ norm is the best convex approximation to the $l_0$ norm. Note that the lines for the $l_0$ norm extend to $-\infty$ and $+\infty$ but are cut for plotting reasons</figcaption></figure>

also highlights the sparsity property of the $l_1$ penalty (the optimal parameter for the horizontal axis is set to zero) that the $l_2$ penalty does not have (the optimal parameter for the horizontal axis is small but different from zero).

Although this approach is appealing due to its intuitiveness and the possibility to set the maximum possible penalty on the parameters $w$, it leads to a minimization problem that is not trivial to solve. A similar approach consists in adding the regularization term in the cost function:

$$ \min_{w} J(w) + \lambda \times \text{Pen}(w) \qquad (2) $$

where $\lambda > 0$ is a hyperparameter that controls the weights of the penalty term compared to the mean loss values over all the training samples. This formulation is related to the Lagrangian function of the minimization problem with the penalty constraint.

This formulation leads to a minimization problem with no constraint which is much easier to solve. One can actually show that Eqs. 1 and 2 are related: solving Eq. 2 for a given $\lambda$, whose optimal solution is denoted by $w_\lambda^*$, is equivalent to solving Eq. 1 for $c = \text{Pen}(w_\lambda^*)$. In other words, solving Eq. 2 for a given $\lambda$ is equivalent to solving Eq. 1 for $c$ whose value is only known after finding the optimal solution of Eq. 2.

Figure 8 illustrates the impact of the regularization term $\lambda \times \text{Pen}(w)$ on the prediction function of a kernel ridge regression algorithm (see Subheading 14 for more details) for different values of $\lambda$. For high values of $\lambda$, the regularization term is dominating the mean loss value, making the prediction function not fitting well enough the training data (underfitting). For small values of $\lambda$, the
<figure><img src="image_25.png" /><figcaption>**Fig. 7** Illustration of the minimization problem with a constraint on the penalty term. The plot represents the value of the loss function for different values of the two coefficients for a linear regression task. The black star indicates the optimal solution with no constraint. The green and orange stars indicate the optimal solutions when imposing a constraint on the $ℓ_2$ and $ℓ_1$ norms of the parameters $w$, respectively</figcaption></figure>

mean loss value is dominating the regularization term, making the prediction function fitting too well the training data (overfitting). A good balance between the mean loss value and the regularization term is required to learn the best function.

Since linear regression is one of the oldest and best-known models, the aforementioned penalties were originally introduced for linear regression:

* Linear regression with the $ℓ_2$ penalty is also known as ridge [7]:

$$ \min_w \|y - Xw\|_2^2 + \lambda \|w\|_2^2 $$
<figure><img src="image_26.png" /><figcaption>**Fig. 8** Illustration of regularization. A kernel ridge regression algorithm is fitted on the training data (blue points) with different values of $\lambda$, which is the weight of the regularization in the cost function. The smaller the values of $\lambda$, the smaller the weight of the $\ell_2$ regularization. The algorithm underfits (respectively, overfits) the data when the value of $\lambda$ is too large (respectively, low)</figcaption></figure>
As in ordinary least squares regression, there exists a closed formula for the optimal solution:

$$ \boldsymbol{w}^* = (\boldsymbol{X}^\top \boldsymbol{X} + \lambda \boldsymbol{I})^{-1} \boldsymbol{X}^\top \boldsymbol{y} $$

* Linear regression with the $\ell_1$ penalty is also known as lasso [8]:

$$ \min_{\boldsymbol{w}} \|\boldsymbol{y} - \boldsymbol{X}\boldsymbol{w}\|_2^2 + \lambda \|\boldsymbol{w}\|_1 $$

* Linear regression with the elastic-net penalty is also known as elastic-net [9]:

$$ \min_{\boldsymbol{w}} \|\boldsymbol{y} - \boldsymbol{X}\boldsymbol{w}\|_2^2 + \lambda\alpha\|\boldsymbol{w}\|_1 + \lambda(1 - \alpha)\|\boldsymbol{w}\|_2^2 $$

The penalties can also be added in other models such as logistic regression, support vector machines, artificial neural networks, etc.

# 8 Support Vector Machine

Linear and logistic regression take into account every training sample in order to find the best line, which is due to their corresponding loss functions: the squared error is zero only if the true and predicted outputs are equal, and the logistic loss is always positive. One could argue that the training samples whose outputs are “easily” well predicted are not relevant: only the training samples whose outputs are not “easily” well predicted or are wrongly predicted should be taken into account. The support vector machine (SVM) is based on this principle (please see Box 4 for an overview of the SVM).

## Box 4: Support Vector Machine

* **Main idea:** hyperplane (i.e., line) that maximizes the margin (i.e., the distance between the hyperplane and the closest inputs to the hyperplane).

* **Support vectors:** only the misclassified inputs and the inputs well classified but with low confidence are taken into account.

* **Non-linearity:** decision function can be non-linear with the use of non-linear kernels.

* **Regularization:** $\ell_2$ penalty.

## 8.1 Original Formulation

The original support vector machine was invented in 1963 and was a linear binary classification method [10]. Figure 9 illustrates the main concept of its original version. When both classes are linearly
<figure><img src="image_27.png" /><figcaption>Fig. 9 Support vector machine classifier with linearly separable classes. When two classes are linearly separable, there exist an infinite number of hyperplanes separating them (left). The decision function of the support vector machine classifier is the hyperplane that maximizes the margin, that is, the distance between the hyperplane and the closest points to the hyperplane (right). Support vectors are highlighted with a black circle surrounding them</figcaption></figure>

separable, there exist an infinite number of hyperplanes that separate both classes. The SVM finds the hyperplane that maximizes the margin, that is, the distance between the hyperplane and the closest points of both classes to the hyperplane, while linearly separating both classes.

The SVM was later updated to non-separable classes [11]. Figure 10 illustrates the role of the margin in this case. The dashed lines correspond to the hyperplanes defined by the equations $x^\top w = +1$ and $x^\top w = -1$. The margin is the distance between both hyperplanes and is equal to $2/\|w\|_2^2$. It defines which samples are included in the decision function of the model: a sample is included if and only if it is inside the margin or outside the margin and misclassified. Such samples are called *support vectors* and are illustrated in Fig. 10 with a black circle surrounding them. In this case, the margin can be seen a regularization term: the larger the margin is, the more support vectors are included in the decision function, the more regularized the model is.

The loss function for the SVM is called the *hinge loss* and is defined as:

$$ \ell_{\text{hinge}}(y, f(\mathbf{x})) = \max(0, 1 - yf(\mathbf{x})) $$

Figure 11 illustrates the curves of the logistic and hinge losses. The logistic loss is always positive, even when the point is accurately classified with high confidence (i.e., when $yf(\mathbf{x}) \gg 0$), whereas the hinge loss is equal to zero when the point is accurately classified with good confidence (i.e., when $yf(\mathbf{x}) \ge 1$). One can see that a sample $(\mathbf{x}, y)$ is a support vector if and only if $yf(\mathbf{x}) \ge 1$, that is, if and only if $\ell_{\text{hinge}}(y, f(\mathbf{x})) = 0$.
<figure><img src="image_28.png" /><figcaption>**Fig. 10** Decision function of a support vector machine classifier with a linear kernel when both classes are not strictly linearly separable. The support vectors are the training points within the margin of the decision function and the misclassified training points. The support vectors are highlighted with a black circle surrounding them</figcaption></figure>

<figure><img src="image_29.png" /><figcaption>**Fig. 11** Binary classification losses. The logistic loss is always positive, even when the point is accurately classified with high confidence (i.e., when $yf(x) \gg 0$), whereas the hinge loss is equal to zero when the point is accurately classified with good confidence (i.e., when $yf(x) \ge 1$)</figcaption></figure>
## 8.2 General Formulation with Kernels

The optimal $\boldsymbol{w}$ coefficients for the original version are estimated by minimizing an objective function consisting of the sum of the hinge loss values and a $\ell_2$ penalty term (which is inversely proportional to the margin):

$$ \min_{\boldsymbol{w}} \sum_{i=1}^{n} \max(0, 1 - y^{(i)} \boldsymbol{x}^{(i)\top} \boldsymbol{w}) + \frac{1}{2C} \|\boldsymbol{w}\|_2^2 $$

The SVM was later updated to non-linear decision functions with the use of kernels [12].

In order to have a non-linear decision function, one could map the input space $I$ into another space (often called the feature space), denoted by $G$, using a function denoted by $\phi$:

$$ \phi: \mathcal{I} \rightarrow G \\ \boldsymbol{x} \mapsto \phi(\boldsymbol{x}) $$

The decision function would still be linear (with a dot product), but in the feature space:

$$ f(\boldsymbol{x}) = \phi(\boldsymbol{x})^{\top} \boldsymbol{w} $$

Unfortunately, solving the corresponding minimization problem is not trivial:

$$ \min_{\boldsymbol{w}} \sum_{i=1}^{n} \max(0, 1 - y^{(i)} \phi(\boldsymbol{x}^{(i)})^{\top} \boldsymbol{w}) + \frac{1}{2C} \|\boldsymbol{w}\|_2^2 \quad (3) $$

Nonetheless, two mathematical properties make the use of non-linear transformations in the feature space possible: the kernel trick and the representer theorem.

The kernel trick asserts that the dot product in the feature space can be computed using only the points from the input space and a kernel function, denoted by $K$:

$$ \forall \boldsymbol{x}, \boldsymbol{x}' \in I, \phi(\boldsymbol{x})^{\top} \phi(\boldsymbol{x}') = K(\boldsymbol{x}, \boldsymbol{x}') $$

The representer theorem [13, 14] asserts that, under certain conditions on the kernel $K$ and the feature space $G$ associated with the function $\phi$, any minimizer of Eq. 3 admits the following form:

$$ f = \sum_{i=1}^{n} \alpha_i K(\cdot, \boldsymbol{x}^{(i)}) $$

where $\alpha$ solves:

$$ \min_{\boldsymbol{\alpha}} \sum_{i=1}^{n} \max(0, 1 - y^{(i)}[\boldsymbol{K}\boldsymbol{\alpha}]_i) + \frac{1}{2C} \boldsymbol{\alpha}^{\top} \boldsymbol{K} \boldsymbol{\alpha} $$
where $K$ is the $n \times n$ matrix consisting of the evaluations of the kernel on all the pairs of training samples: $\forall i, j \in \{1, \dots, n\}$, $K_{ij} = K(\mathbf{x}^{(i)}, \mathbf{x}^{(j)})$.

Because the hinge loss is equal to zero if and only if $y_i f(\mathbf{x})$ is greater than or equal to 1, only the training samples $(\mathbf{x}^{(i)}, y^{(i)})$ such that $y^{(i)} f(\mathbf{x}^{(i)}) < 1$ have a nonzero $\alpha_i$ coefficient. These points are the so-called support vectors, and this is why they are the only training samples contributing to the decision function of the model:

$$ SV = \{i \in \{1, \dots, n\} \mid \alpha_i \neq 0\} \\ f(\mathbf{x}) = \sum_{i=1}^{n} \alpha_i K(\mathbf{x}, \mathbf{x}^{(i)}) = \sum_{i \in SV} \alpha_i K(\mathbf{x}, \mathbf{x}^{(i)}) $$

The kernel trick and the representer theorem show that it is more practical to work with the kernel $K$ instead of the mapping function $\phi$. Popular kernel functions include:

* The linear kernel:

$$ K(\mathbf{x}, \mathbf{x}') = \mathbf{x}^{\top} \mathbf{x}' $$

* The polynomial kernel:

$$ K(\mathbf{x}, \mathbf{x}') = (\gamma \mathbf{x}^{\top} \mathbf{x}' + c_0)^d \quad \text{with} \quad \gamma > 0, c_0 \ge 0, d \in \mathbb{N}^* $$

* The sigmoid kernel:

$$ K(\mathbf{x}, \mathbf{x}') = \tanh(\gamma \mathbf{x}^{\top} \mathbf{x}' + c_0) \quad \text{with} \quad \gamma > 0, c_0 \ge 0 $$

* The radial basis function (RBF) kernel:

$$ K(\mathbf{x}, \mathbf{x}') = \exp\left(-\gamma \|\mathbf{x} - \mathbf{x}'\|_2^2\right) \quad \text{with} \quad \gamma > 0 $$

The linear kernel yields a linear decision function and is actually identical to the original formulation of the SVM (one can show that there is a mapping between the $\alpha$ and $\mathbf{w}$ coefficients). Non-linear kernels allow for non-linear, more complex, decision functions. This is particularly useful when the data is not linearly separable, which is the most common use case. Figure 12 illustrates the decision function and the margin of a SVM classification model for four different kernels.

The SVM was also extended to regression tasks with the use of the $\epsilon$-insensitive loss. Similar to the hinge loss, which is equal to zero for points that are correctly classified and outside the margin, the $\epsilon$-insensitive loss is equal to zero when the error between the true target value and the predicted value is not greater than $\epsilon$:

$$ \ell_{\epsilon-\text{insensitive}}(y, f(\mathbf{x})) = \max(0, |y - f(\mathbf{x})| - \epsilon) $$
<figure><img src="image_30.png" /><figcaption>Fig. 12 Impact of the kernel on the decision function of a support vector machine classifier. A non-linear kernel allows for a non-linear decision function</figcaption></figure>

The objective function for the SVM regression method combines the values of ε-insensitive loss of the training points and the ℓ₂ penalty:

$$ \min_{\boldsymbol{w}} \sum_{i=1}^{n} \max \left( 0, \left| y^{(i)} - \phi(\boldsymbol{x}^{(i)})^{\top} \boldsymbol{w} \right| - \varepsilon \right) + \frac{1}{2C} \|\boldsymbol{w}\|_{2}^{2} $$

Figure 13 illustrates the curves of three regression losses. The squared error loss takes very small values for small errors and very high values for high errors, whereas the absolute error loss takes small values for small errors and high values for high errors. Both losses take small but nonzero values when the error is small. On the contrary, the ε-insensitive loss is null when the error is small and otherwise equal to the absolute error loss minus ε.
<figure><img src="image_31.png" /><figcaption>**Fig. 13** Regression losses. The squared error loss takes very small values for small errors and very large values for large errors, whereas the absolute error loss takes small values for small errors and large values for large errors. Both losses take small but nonzero values when the error is small. On the contrary, the ε-insensitive loss is null when the error is small and otherwise equal the absolute error loss minus ε. When computed over several samples, the squared and absolute error losses are often referred to as mean squared error (MSE) and mean absolute error (MAE), respectively</figcaption></figure>

# 9 Multiclass Classification

The classification methods that we presented so far, logistic regression and support vector machines, are binary classifiers: they can only be used when there are only two possible outcomes. However, in practice, it is common to have more than two possible outcomes. For instance, differential diagnosis of brain disorders is often between several, and not only two, diseases.

Several strategies have been proposed to extend any binary classification method to multiclass classification tasks. They all rely on transforming the multiclass classification task into several binary classification tasks. In this section, we present the most commonly used strategies: *one-vs-rest*, *one-vs-one*, and *error correcting output code* [15]. Figure 14 illustrates the main ideas of these approaches. But first, we present a natural extension of logistic regression to multiclass classification tasks which is often referred to as *multinomial logistic regression* [5].
<figure><img src="image_32.png" /><figcaption>**Fig. 14** Main approaches to convert a multiclass classification task into several binary classification tasks. In the one-vs-rest approach, each class is associated with a binary classification model that is trained to separate this class from all the other classes. In the one-vs-one approach, a binary classifier is trained on each pair of classes. In the error correcting output code approach, the classes are (randomly) split into two groups, and a binary classifier is trained for each split</figcaption></figure>

## 9.1 Multinomial Logistic Regression

For binary classification, logistic regression is characterized by a hyperplane: the signed distance to the hyperplane is mapped into the probability of belonging to the positive class using the sigmoid function. However, for multiclass classification, a single hyperplane is not enough to characterize all the classes. Instead, each class $C_k$ is characterized by a hyperplane $w_k$, and, for any input $\mathbf{x}$, one can compute the signed distance $\mathbf{x}^\top w_k$ between the input $\mathbf{x}$ and the hyperplane $w_k$. The signed distances are mapped into probabilities using the softmax function, defined as
$$ \text{softmax}(\mathbf{x}_1, \dots, \mathbf{x}_q) = \left( \frac{\exp(\mathbf{x}_1)}{\sum_{j=1}^q \exp(\mathbf{x}_j)}, \dots, \frac{\exp(\mathbf{x}_q)}{\sum_{j=1}^q \exp(\mathbf{x}_j)} \right), \text{ as follows:} $$

$$ \forall k \in \{1, \dots, q\}, \quad P(y = C_k | \mathbf{x} = \mathbf{x}) = \frac{\exp(\mathbf{x}^\top \mathbf{w}_k)}{\sum_{j=1}^q \exp(\mathbf{x}^\top \mathbf{w}_j)} $$

The coefficients $(w_k)_{1 \le k \le q}$ are still estimated by maximizing the likelihood function:

$$ L(\mathbf{w}_1, \dots, \mathbf{w}_q) = \prod_{i=1}^{n} \prod_{k=1}^{q} P(y = C_k | \mathbf{x} = \mathbf{x}^{(i)})^{1_{y^{(i)} = c_k}} $$

which is equivalent to minimizing the negative log-likelihood:
$$
\begin{align*}
& - \log(L(\mathbf{w}_1, \dots, \mathbf{w}_q)) \\
&= - \sum_{i=1}^{n} \sum_{k=1}^{q} \mathbf{1}_{y^{(i)} = c_k} \log(P(y = c_k | \mathbf{x} = \mathbf{x}^{(i)})) \\
&= \sum_{i=1}^{n} - \sum_{k=1}^{q} \mathbf{1}_{y^{(i)} = c_k} \log \left( \frac{\exp(\mathbf{x}^{(i)\top} \mathbf{w}_k)}{\sum_{j=1}^{q} \exp(\mathbf{x}^{(i)\top} \mathbf{w}_j)} \right) \\
&= \sum_{i=1}^{n} \ell_{\text{cross-entropy}}(y^{(i)}, \text{softmax}(\mathbf{x}^{(i)\top} \mathbf{w}_1, \dots, \mathbf{x}^{(i)\top} \mathbf{w}_q))
\end{align*}
$$

where $\ell_{\text{cross-entropy}}$ is known as the *cross-entropy loss* and is defined, for any label $y$ and any vector of probabilities $(\pi_1, \dots, \pi_q)$, as:

$$ \ell_{\text{cross-entropy}}(y, (\pi_1, \dots, \pi_q)) = - \sum_{k=1}^{q} \mathbf{1}_{y=c_k} \log \pi_k $$

This loss is commonly used to train artificial neural networks on classification tasks and is equivalent to the logistic loss in the binary case.

Figure 15 illustrates the impact of the strategy used to handle a multiclass classification task on the decision function.

## 9.2 One-vs-Rest

A strategy to transform a multiclass classification task into several binary classification tasks is to fit a binary classifier for each class: the positive class is the given class, and the negative class consists of all the other classes merged into a single class. This strategy is known as *one-vs-rest*. The advantage of this strategy is that each class is characterized by a single model, so that it is possible to gain deeper knowledge about the class by inspecting its corresponding model. A consequence is that the predictions for new samples take into account the confidence of the models: the predicted class for a new input is the class for which the corresponding model is the most confident that this input belongs to its class. The one-vs-rest strategy is the most commonly used strategy and usually a good default choice.

## 9.3 One-vs-One

Another strategy is to fit a binary classifier for each pair of classes: this strategy is known as *one-vs-one*. The advantage of this strategy is that the classes in each binary classification task are “pure”, in the sense that different classes are never merged into a single class. However, the number of binary classifiers that needs to be trained is larger for the one-vs-one strategy ($\frac{1}{2}q(q-1)$) than for the one-vs-rest strategy ($q$). Nonetheless, for the one-vs-one strategy, the number of training samples in each binary classification task is smaller than the total number of samples, which makes training each binary classifier usually faster. Another drawback is that this strategy is less interpretable compared to the one-vs-rest strategy, as the predicted class corresponds to the class obtaining the most
<figure><img src="image_33.png" /><figcaption>**Fig. 15** Illustration of the impact of the strategy used to handle a multiclass classification task on the decision function of a logistic regression model</figcaption></figure>

votes (i.e., winning the most one-vs-one matchups), which does not take into account the confidence in winning each matchup.<fnref n="1" /> For instance, winning a one-vs-one matchup with 0.99 probability gives the same result as winning the same matchup with 0.51 probability, i.e., one vote.

## 9.4 Error Correcting Output Code

A substantially different strategy, inspired by the theory of error correction code, consists in merging a subset of classes into one class and the other subset into the other class, for each binary classification task. This data is often called the code book and can be represented as a matrix whose rows correspond to the classes and whose columns correspond to the binary classification tasks. The matrix consists only of -1 and +1 values that represent the corresponding label for each class and for each binary task.<fnref n="2" /> For

<footnote n="1">¹ The confidences are actually taken into account but only in the event of a tie.</footnote>

<footnote n="2">² The values are 0 and 1 when the classifier does not return scores but only probabilities.</footnote>
any input, each binary classifier returns the score (or probability) associated with the positive class. The predicted class for this input is the class whose corresponding vector is the most similar to the vector of scores, with similarity being assessed with the Euclidean distance (the lower, the more similar). There exist advanced strategies to define the code book, but it has been argued than a random code book usually gives as good results as a sophisticated one [16].

# 10 Decision Functions with Normal Distributions

Normal distributions are popular distributions because they are commonly found in nature. For instance, the distribution of heights and birth weights of human beings can be approximated using normal distributions. Moreover, normal distributions are particularly easy to work with from a mathematical point of view. For these reasons, a common model consists in assuming that the training input vectors are independently sampled from normal distributions.

A possible classification model consists in assuming that, for each class, all the corresponding inputs are sampled from a normal distribution with mean vector $\boldsymbol{\mu}_k$ and covariance matrix $\boldsymbol{\Sigma}_k$:

$$ \forall i \text{ such that } y^{(i)} = C_k, \boldsymbol{x}^{(i)} \sim \mathcal{N}(\boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k) $$

Using the probability density function of a normal distribution, one can compute the probability density of any input $\boldsymbol{x}$ associated with the distribution $\mathcal{N}(\boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k)$ of class $C_k$:

$$ p_{\boldsymbol{x}|y=C_k}(\boldsymbol{x}) = \frac{1}{\sqrt{(2\pi)^p |\boldsymbol{\Sigma}_k|}} \exp\left(-\frac{1}{2} [\boldsymbol{x} - \boldsymbol{\mu}_k]^\top \boldsymbol{\Sigma}_k^{-1} [\boldsymbol{x} - \boldsymbol{\mu}_k]\right) $$

With such a probabilistic model, it is easy to compute the probability that a sample belongs to class $C_k$ using Bayes rule:

$$ P(y=C_k | \boldsymbol{x}=\boldsymbol{x}) = \frac{p_{\boldsymbol{x}|y=C_k}(\boldsymbol{x}) P(y=C_k)}{p_{\boldsymbol{x}}(\boldsymbol{x})} $$

With normal distributions, it is mathematically easier to work with log-probabilities:
$$
\begin{align*}
\log P(y = C_k | \mathbf{x} = \mathbf{x})
&= \log p_{x|y=C_k}(\mathbf{x}) + \log P(y = C_k) - \log p_x(\mathbf{x}) \\
&= -\frac{1}{2} [\mathbf{x} - \boldsymbol{\mu}_k]^\top \boldsymbol{\Sigma}_k^{-1} [\mathbf{x} - \boldsymbol{\mu}_k] - \frac{1}{2} \log |\boldsymbol{\Sigma}_k| + \log P(y = C_k) \\
&\quad - \frac{p}{2} \log(2\pi) - \log p_x(\mathbf{x}) \\
&= -\frac{1}{2} \mathbf{x}^\top \boldsymbol{\Sigma}_k^{-1} \mathbf{x} + \mathbf{x}^\top \boldsymbol{\Sigma}_k^{-1} \boldsymbol{\mu}_k \\
&\quad -\frac{1}{2} \boldsymbol{\mu}_k^\top \boldsymbol{\Sigma}_k^{-1} \boldsymbol{\mu}_k - \frac{1}{2} \log |\boldsymbol{\Sigma}_k| + \log P(y = C_k) \\
&\quad - \frac{p}{2} \log(2\pi) - \log p_x(\mathbf{x}) \tag{4}
\end{align*}
$$

It is also possible to make further assumptions on the covariance matrices that lead to different models. In this section, we present the most commonly used ones: naive Bayes, linear discriminant analysis, and quadratic discriminant analysis. Figure 16 illustrates the covariance matrices and the decision functions for these models in the two-dimensional case.

**10.1 Naive Bayes**

The naive Bayes model assumes that, conditionally to each class $C_k$, the features are independent and have the same variance $\sigma_k^2$:

$$ \forall k, \quad \mathbf{\Sigma}_k = \sigma_k^2 \mathbf{I}_p $$

Equation 4 can thus be further simplified:

$$
\begin{align*}
\log P(y = C_k | \mathbf{x} = \mathbf{x})
&= - \frac{1}{2\sigma_k^2} \mathbf{x}^\top \mathbf{x} + \frac{1}{\sigma_k^2} \mathbf{x}^\top \boldsymbol{\mu}_k - \frac{1}{2\sigma_k^2} \boldsymbol{\mu}_k^\top \boldsymbol{\mu}_k - \log \sigma_k + \log P(y = C_k) \\
&\quad - \frac{p}{2} \log(2\pi) - \log p_x(\mathbf{x}) \\
&= \mathbf{x}^\top \mathbf{W}_k \mathbf{x} + \mathbf{x}^\top \mathbf{w}_k + w_{0k} + s
\end{align*}
$$

where:

* $\mathbf{W}_k = -\frac{1}{2\sigma_k^2} \mathbf{I}_p$ is the matrix of the quadratic term for class $C_k$.

* $\mathbf{w}_k = \frac{1}{\sigma_k^2} \boldsymbol{\mu}_k$ is the vector of the linear term for class $C_k$.

* $w_{0k} = -\frac{1}{2\sigma_k^2} \boldsymbol{\mu}_k^\top \boldsymbol{\mu}_k - \log \sigma_k + \log P(y = C_k)$ is the intercept for class $C_k$.

* $s = -\frac{p}{2} \log(2\pi) - \log p_x(\mathbf{x})$ is a term that does not depend on class $C_k$.

Therefore, naive Bayes is a quadratic model. The probabilities for input $\mathbf{x}$ to belong to each class $C_k$ can then easily be computed:

$$ P(y = C_k | \mathbf{x} = \mathbf{x}) = \frac{\exp(\mathbf{x}^\top \mathbf{W}_k \mathbf{x} + \mathbf{x}^\top \mathbf{w}_k + w_{0k})}{\sum_{j=1}^k \exp(\mathbf{x}^\top \mathbf{W}_j \mathbf{x} + \mathbf{x}^\top \mathbf{w}_j + w_{0j})} $$
<figure><img src="image_34.png" /><figcaption>**Fig. 16** Illustration of decision functions with normal distributions. A two-dimensional covariance matrix can be represented as an ellipse. In the naive Bayes model, the features are assumed to be independent and to have the same variance conditionally to the class, leading to covariance matrices being represented as circles. When the covariance matrices are assumed to be identical, the decision functions are linear instead of quadratic</figcaption></figure>

With the naive Bayes model, it is relatively common to have the conditional variances $\sigma_k^2$ to all be equal:

$$ \forall k, \Sigma_k = \sigma_k^2 I_p = \sigma^2 I_p $$

In this case, Eq. 4 can be even further simplified:

$$ \begin{align*} \log P(y = C_k | \mathbf{x} = \mathbf{x}) \\ &= -\frac{1}{2\sigma^2} \mathbf{x}^\top \mathbf{x} + \frac{1}{\sigma^2} \mathbf{x}^\top \boldsymbol{\mu}_k - \frac{1}{2\sigma^2} \boldsymbol{\mu}_k^\top \boldsymbol{\mu}_k - \log \sigma_k + \log P(y = C_k) \\ &\quad - \frac{p}{2} \log(2\pi) - \log p_x(\mathbf{x}) \\ &= \mathbf{x}^\top \mathbf{w}_k + w_{0k} + s \end{align*} $$
where:

* $\mathbf{w}_k = \frac{1}{\sigma^2} \boldsymbol{\mu}_k$ is the vector of the linear term for class $C_k$.

* $w_{0k} = -\frac{1}{2\sigma^2} \boldsymbol{\mu}_k^\top \boldsymbol{\mu}_k + \log P(y = C_k)$ is the intercept for class $C_k$.

* $s = -\frac{1}{2\sigma^2} \mathbf{x}^\top \mathbf{x} - \log \sigma - \frac{\ell}{2} \log(2\pi) - \log p_x(\mathbf{x})$ is a term that does not depend on class $C_k$.

In this case, naive Bayes becomes a linear model.

**10.2 Linear Discriminant Analysis**

Linear discriminant analysis (LDA) makes the assumption that all the covariance matrices are identical but otherwise arbitrary:

$$ \forall k, \mathbf{\Sigma}_k = \mathbf{\Sigma} $$

Therefore, Eq. 4 can be further simplified:

$$
\begin{align*}
\log P(y = C_k | \mathbf{x} = \mathbf{x})
&= -\frac{1}{2} [\mathbf{x} - \boldsymbol{\mu}_k]^\top \boldsymbol{\Sigma}^{-1} [\mathbf{x} - \boldsymbol{\mu}_k] - \frac{1}{2} \log |\boldsymbol{\Sigma}| + \log P(y = C_k) \\
&\quad - \frac{\ell}{2} \log(2\pi) - \log p_x(\mathbf{x}) \\
&= -\frac{1}{2} (\mathbf{x}^\top \boldsymbol{\Sigma}^{-1} \mathbf{x} - \mathbf{x}^\top \boldsymbol{\Sigma}^{-1} \boldsymbol{\mu}_k - \boldsymbol{\mu}_k^\top \boldsymbol{\Sigma}^{-1} \mathbf{x} + \boldsymbol{\mu}_k^\top \boldsymbol{\Sigma}^{-1} \boldsymbol{\mu}_k) \\
&\quad - \frac{1}{2} \log |\boldsymbol{\Sigma}| + \log P(y = C_k) - \frac{\ell}{2} \log(2\pi) - \log p_x(\mathbf{x}) \\
&= -\mathbf{x}^\top \boldsymbol{\Sigma}^{-1} \boldsymbol{\mu}_k - \frac{1}{2} \mathbf{x}^\top \boldsymbol{\Sigma}^{-1} \mathbf{x} - \frac{1}{2} \boldsymbol{\mu}_k^\top \boldsymbol{\Sigma}^{-1} \boldsymbol{\mu}_k + \log P(y = C_k) - \frac{1}{2} \log |\boldsymbol{\Sigma}| \\
&\quad - \frac{\ell}{2} \log(2\pi) - \log p_x(\mathbf{x}) \\
&= \mathbf{x}^\top \mathbf{w}_k + w_{0k} + s
\end{align*}
$$

where:

* $\mathbf{w}_k = \mathbf{\Sigma}^{-1} \boldsymbol{\mu}_k$ is the vector of coefficients for class $C_k$.

* $w_{0k} = -\frac{1}{2} \boldsymbol{\mu}_k^\top \boldsymbol{\Sigma}^{-1} \boldsymbol{\mu}_k + \log P(y = C_k)$ is the intercept for class $C_k$.

* $s = -\frac{1}{2} \mathbf{x}^\top \boldsymbol{\Sigma}^{-1} \mathbf{x} - \frac{1}{2} \log |\boldsymbol{\Sigma}| - \frac{\ell}{2} \log(2\pi) - \log p_x(\mathbf{x})$ is a term that does not depend on class $C_k$.

Therefore, linear discriminant analysis is a linear model. When $\boldsymbol{\Sigma}$ is diagonal, linear discriminant analysis is identical to naive Bayes with identical conditional variances.

The probabilities for input $\mathbf{x}$ to belong to each class $C_k$ can then easily be computed:

$$ P(y = C_k | \mathbf{x} = \mathbf{x}) = \frac{\exp(\mathbf{x}^\top \mathbf{w}_k + w_{0k})}{\sum_{j=1}^{k} \exp(\mathbf{x}^\top \mathbf{w}_j + w_{0j})} $$

**10.3 Quadratic Discriminant Analysis**

Quadratic discriminant analysis makes no assumption on the covariance matrices $\mathbf{\Sigma}_k$ that can all be arbitrary. Equation 4 can be written as:
$$
\begin{align*}
\log P(y = C_k | \mathbf{x} = \mathbf{x})
&= -\frac{1}{2} \mathbf{x}^\top \mathbf{\Sigma}_k^{-1} \mathbf{x} + \mathbf{x}^\top \mathbf{\Sigma}_k^{-1} \boldsymbol{\mu}_k - \frac{1}{2} \boldsymbol{\mu}_k^\top \mathbf{\Sigma}_k^{-1} \boldsymbol{\mu}_k - \frac{1}{2} \log |\mathbf{\Sigma}_k| \\
&\quad + \log P(y = C_k) - \frac{p}{2} \log(2\pi) - \log p_x(\mathbf{x}) \\
&= \mathbf{x}^\top \mathbf{W}_k \mathbf{x} + \mathbf{x}^\top \mathbf{w}_k + w_{0k} + s
\end{align*}
$$

where:

• $\mathbf{W}_k = -\frac{1}{2}\mathbf{\Sigma}_k^{-1}$ is the matrix of the quadratic term for class $C_k$.

• $\mathbf{w}_k = \mathbf{\Sigma}_k^{-1}\boldsymbol{\mu}_k$ is the vector of the linear term for class $C_k$.

• $w_{0k} = -\frac{1}{2}\boldsymbol{\mu}_k^\top\mathbf{\Sigma}_k^{-1}\boldsymbol{\mu}_k - \frac{1}{2}\log|\mathbf{\Sigma}_k| + \log P(y = C_k)$ is the intercept for class $C_k$.

• $s = -\frac{p}{2}\log(2\pi) - \log p_x(\mathbf{x})$ is a term that does not depend on class $C_k$.

Therefore, quadratic discriminant analysis is a quadratic model.

The probabilities for input $\mathbf{x}$ to belong to each class $C_k$ can then easily be computed:

$$P(y = C_k | \mathbf{x} = \mathbf{x}) = \frac{\exp(\mathbf{x}^\top \mathbf{W}_k \mathbf{x} + \mathbf{x}^\top \mathbf{w}_k + w_{0k})}{\sum_{j=1}^k \exp(\mathbf{x}^\top \mathbf{W}_j \mathbf{x} + \mathbf{x}^\top \mathbf{w}_j + w_{0j})}$$

# 11 Tree-Based Methods

## 11.1 Decision Tree

Binary decisions based on conditional statements are frequently used in everyday life because they are intuitive and easy to understand. Figure 17 illustrates a general approach when someone is ill. Depending on conditional statements (severity of symptoms, ability to quickly consult a specialist), the decision (consult your general practitioner or a specialist, or call for emergency services) is different. Models with such an architecture are often used in machine learning and are called *decision trees*.

A decision tree is an algorithm containing only conditional statements and can be represented with a tree [17]. This graph consists of:

• Decision nodes for all the conditional statements

• Branches for the potential outcomes of each decision node

• Leaf nodes for the final decision

Figure 18 illustrates a decision tree and its corresponding decision function. For a given sample, the final decision is obtained by following its corresponding path, starting at the root node.

A decision tree recursively partitions the feature space in order to group samples with the same labels or similar target values. At each node, the objective is to find the best (feature, threshold) pair so that both subsets obtained with this split are the most *pure*, that
<figure><img src="image_35.png" /><figcaption>**Fig. 17** A general thought process when being ill. Depending on conditional statements (severity of symptoms, ability to quickly consult a specialist), the decision (consult your general practitioner or a specialist, or call for emergency services) is different</figcaption></figure>

<figure><img src="image_36.png" /><figcaption>**Fig. 18** A decision tree: (left) the rules learned by the decision tree and (right) the corresponding decision function</figcaption></figure>

is, homogeneous. To do so, the best (feature, threshold) pair is defined as the pair that minimizes an *impurity* criterion.

Let $S \subseteq X$ be a subset of training samples. For classification tasks, the distribution of the classes, that is, the proportion of each class, is used to measure the purity of the subset. Let $p_k$ be the proportion of samples from class $C_k$ in a given partition:

$$p_k = \frac{1}{|S|} \sum_{y \in S} 1_{y = C_k}$$

Popular impurity criteria for classification tasks include:

* Gini index: $\sum k p_k(1 - p_k)$

* Entropy: $-\sum p_k \log(p_k)$

* Misclassification: $1 - \max_k p_k$
<figure><img src="image_37.png" /><figcaption>**Fig. 19** Illustration of Gini index and entropy. The entropy function takes larger values than the Gini index, especially for $p_k < 0.8$, which thus is more discriminative against heterogeneous subsets (when most classes only represent only a small proportion of the samples) than Gini index</figcaption></figure>

Figure 19 illustrates the values of the Gini index and the entropy for a single class $C_k$ and for different proportions of samples $p_k$. One can see that the entropy function takes larger values than the Gini index, especially for $p_k < 0.8$. Since the sum of the proportions is equal to 1, most classes only represent a small proportion of the samples. Therefore, a simple interpretation is that entropy is more discriminative against heterogeneous subsets than the Gini index. Misclassification only takes into account the proportion of the most common class and tends to be even less discriminative against heterogeneous subsets than both entropy and Gini index.

For regression tasks, the mean error from a reference value (such as the mean or the median) is often used as the impurity criterion:

* Mean squared error: $\frac{1}{|S|} \sum_{y \in S} (y - \bar{y})^2$ with $\bar{y} = \frac{1}{|S|} \sum_{y \in S} y$

* Mean absolute error: $\frac{1}{|S|} \sum_{y \in S} |y - \text{median}_S(y)|$

Theoretically, a tree can grow until every leaf node is perfectly pure. However, such a tree would have a lot of branches and would be very complex, making it prone to overfitting. Several strategies are commonly used to limit the size of the tree. One approach consists in growing the tree with no restriction and then *pruning* the tree, that is, replacing subtrees with nodes [17]. Other popular strategies to limit the complexity of the tree are usually applied while the tree is grown and include setting:

* A maximum depth for the tree

* A minimum number of samples required to be at an internal node
* A minimum number of samples required to split a given partition

* A maximum number of leaf nodes

* A maximum number of features considered (instead of all the features) to find the best split

* A minimum impurity decrease to split an internal node

## 11.2 Random Forest
One limitation of decision trees is their simplicity. Decision trees tend to use a small fraction of the features in their decision function. In order to use more features in the decision tree, growing a larger tree is required, but large trees tend to suffer from overfitting, that is, having a low bias but a high variance. One solution to decrease the variance without much increasing the bias is to build an ensemble of trees with randomness, hence the name *random forest* [18]. An overview of random forests can be found in Box 5.

In a bid to have trees that are not perfectly correlated (thus building actually different trees), each tree is built using only a subset of the training samples obtained with random sampling. Moreover, for each decision node of each tree, only a subset of the features are considered to find the best split.

The final prediction is obtained by averaging the predictions of each tree. For classification tasks, the predicted class is either the most commonly predicted class (hard-voting) or the one with the highest mean probability estimate (soft-voting) across the trees. For regression tasks, the predicted value is usually the mean of the predicted values across the trees.

### Box 5: Random Forest

* **Random forest:** ensemble of decision trees with randomness introduced to build different trees

* **Decision tree:** algorithm containing only conditional statements and represented with a tree

* **Regularization:** maximum depth for each tree, minimum number of samples required to split a given partition, etc.

## 11.3 Extremely Randomized Trees
Even though random forests involve randomness in sampling both the samples and the features, trees inside a random forest tend to be correlated, thus limiting the variance decrease. In order to decrease even more the variance of the model (while possibly increasing its bias) by growing less correlated trees, *extremely randomized trees* introduce more randomness [19]. Instead of looking for the best split among all the candidate (feature,
threshold) pairs, one threshold is drawn at random for each
candidate feature, and the best of these randomly generated
thresholds is chosen as the splitting rule.

**12 Clustering**

So far, we have presented classic machine learning methods for classification and regression, which are the main components of supervised learning. Each input **x**<sup>(i)</sup> had an associated output **y**<sup>(i)</sup>. In this section, we present clustering, which is an unsupervised machine learning task. In unsupervised learning, only the inputs **x**<sup>(i)</sup> are available, with no associated outputs. As the ground truth is not available, the objective is to extract information from the input data without supervising the learning process with the output data.

Clustering consists in finding groups of samples such that:

* Samples from the same group are similar.

* Samples from different groups are different.

For instance, clustering can be used to identify disease subtypes for heterogeneous diseases such as Alzheimer's disease and Parkinson's disease.

In this section, we present two of the most common clustering methods: the *k*-means algorithm and the Gaussian mixture model.

**12.1 k-means**
The *k*-means algorithm divides a set of *n* samples, denoted by *X*, into a set of *k* disjoint clusters, each denoted by *X*<sub>j</sub>, such that
*X* = {*X*<sub>1</sub>, ..., *X*<sub>k</sub>}.

Figure 20 illustrates the concept of this algorithm. Each cluster $X_j$ is characterized by its *centroid*, denoted by $\mu_j$, that is, the mean of the samples in this cluster:

<figure><img src="image_38.png" /><figcaption>**Fig. 20** Illustration of the *k*-means algorithm. The objective of the algorithm is to find the centroids that minimize the within-cluster sum-of-squares criterion. In this example, the inertia is approximately equal to 184.80 and is the lowest possible inertia, meaning that the represented centroids are optimal</figcaption></figure>
$$ \mu_j = \frac{1}{|\mathcal{X}_j|} \sum_{\mathbf{x}^{(i)} \in \mathcal{X}_j} \mathbf{x}^{(i)} $$

The centroids fully define the set of clusters because each sample is assigned to the cluster whose centroid is the closest.

The k-means algorithm aims at finding centroids that minimize the inertia, also known as within-cluster sum-of-squares criterion:

$$ \min_{\{\mu_1, \dots, \mu_k\}} \sum_{j=1}^{k} \sum_{\mathbf{x}^{(i)} \in \mathcal{X}_j} \|\mathbf{x}^{(i)} - \mu_j\|_2^2 $$

The original algorithm used to find the centroids is often referred to as *Lloyd's algorithm* [20] and is presented in Algorithm 1. After initializing the centroids, a two-step loop is repeated until convergence (when the centroids are identical for two consecutive iterations) consisting of:

1. The assignment step, where the clusters are updated based on the current centroids

2. The update step, where the centroids are updated based on the current clusters

When clusters are well-defined, a point from a given cluster is likely to stay in this cluster. Therefore, the assignment step can be sped up thanks to the triangle inequality by keeping track of lower and upper bounds for distances between points and centers, at the cost of higher memory usage [21].

## Algorithm 1 Lloyd's algorithm (aka naive k-means algorithm)

**Result:** Centroids {$\mu_1, \dots, \mu_k$}

Initialize the centroids {$\mu_1, \dots, \mu_k$};

while not converged do

**Assignment step:** Compute the clusters (i.e., assign each sample to its nearest centroid):

$$ \forall j \in \{1, \dots, k\}, \quad \mathcal{X}_j = \{\mathbf{x}^{(i)} \in \mathcal{X} \mid \|\mathbf{x}^{(i)} - \mu_j\|_2^2 = \min_l \|\mathbf{x}^{(i)} - \mu_l\|_2^2\} $$

**Update step:** Compute the centroids of the updated clusters:

$$ \forall j \in \{1, \dots, k\}, \quad \mu_j = \frac{1}{|\mathcal{X}_j|} \sum_{\mathbf{x}^{(i)} \in \mathcal{X}_j} \mathbf{x}^{(i)} $$
Even though the *k*-means algorithm is one of the simplest and most used clustering methods, it has several downsides that should be kept in mind.

First, the number of clusters *k* is a hyperparameter. Setting a value much different from the actual number of clusters may yield poor clusters.

Second, the inertia is not a convex function. Although Lloyd's algorithm is guaranteed to converge, it may converge to a local minimum that is not a global minimum. Figure 21 illustrates the convergence to such centroids. Several strategies are often applied to address this issue, including sophisticated centroid initialization [22] and running the algorithm numerous times and keeping the best run (i.e., the one yielding the lowest inertia).

<figure><img src="image_39.png" /><figcaption>**Fig. 21** Illustration of the convergence of the *k*-means algorithm to bad local minima. In the upper figure, the algorithm converged to a global minimum because the inertia is equal to the minimum possible value (184.80); thus, the obtained clusters are optimal. In the four other figures, the algorithm converged to a local minima that are not global minima because the inertias are higher than the minimum possible value; thus, the obtained clusters are suboptimal</figcaption></figure>
Third, inertia makes the assumption that the clusters are convex and isotropic. The k-means algorithm may yield poor results when this assumption does not hold, such as with elongated clusters or manifolds with irregular shapes.

Fourth, the Euclidean distance tends to be inflated (i.e., the ratio of the distances of the nearest and farthest neighbors to a given target is close to 1) in high-dimensional spaces, making inertia a poor criterion in such spaces [23]. One can alleviate this issue by running a dimensionality reduction method such as principal component analysis prior to the k-means algorithm.

**12.2 Gaussian Mixture Model**

A mixture model makes the assumption that each sample is generated from a mixture of several independent distributions.

Let $k$ be the number of distributions. Each distribution $F_j$ is characterized by its probability of being picked, denoted by $\pi_j$, and its density $p_j$ with parameters $\theta_j$, denoted by $p_j(\cdot; \theta_j)$. Let $\Delta = (\Delta_1, \dots, \Delta_k)$ be a vector-valued random variable such that:

$$ \sum_{j=1}^{k} \Delta_{j} = 1 \quad \text{and} \quad \forall j \in \{1, \dots, k\}, \ P(\Delta_{j} = 1) = 1 - P(\Delta_{j} = 0) = \pi_{j} $$

and $(x_1, \dots, x_k)$ be independent random variables such that $x_j \sim F_j$. The samples are assumed to be generated from a random variable $x$ with density $p_x$ such that:

$$ x = \sum_{j=1}^{k} \Delta_{j} x_{j} \\ \forall x \in X, \ p_{x}(x, \theta) = \sum_{j=1}^{k} \pi_{j} p_{j}(x; \theta_{j}) $$

A Gaussian mixture model is a particular case of a mixture model in which each distribution $F_j$ is a Gaussian distribution with mean vector $\mu_j$ and covariance matrix $\Sigma_j$:

$$ \forall j \in \{1, \dots, k\}, \ F_j = \mathcal{N}(\mu_j, \Sigma_j) $$

Figure 22 illustrates the learned distributions from a Gaussian mixture model.

The objective is to find the parameters $\theta$ that maximize the likelihood, with $\theta = (\{\mu_j\}_{j=1}^k, \{\Sigma_j\}_{j=1}^k, \{\pi_j\}_{j=1}^k)$:

$$ L(\theta) = \prod_{i=1}^{n} p_{X}(x^{(i)}; \theta) $$

For computational reasons, it is easier to maximize the log-likelihood:
<figure><img src="image_40.png" /><figcaption>Fig. 22 Gaussian mixture model. For each estimated distribution, the mean vector and the ellipsis consisting of all the points within one standard deviation of the mean are plotted</figcaption></figure>

$$ \log(L(\boldsymbol{\theta})) = \sum_{i=1}^{n} \log(p_X(\boldsymbol{x}^{(i)}; \boldsymbol{\theta})) = \sum_{i=1}^{n} \log\left(\sum_{j=1}^{k} \pi_j p_j(\boldsymbol{x}; \boldsymbol{\theta}_j)\right) $$

Because the density $p_X(\cdot; \boldsymbol{\theta})$ is a weighted sum of Gaussian densities, the expression cannot be further simplified.

In order to solve this maximization problem, an algorithm called *expectation-maximization* (EM) is often applied [24]. Algorithm 2 describes the main concepts of this algorithm. After initializing the parameters of each distribution, a two-step loop is repeated until convergence (when the parameters are stable over consecutive loops):

* The *expectation step*, in which the probability for each sample $\boldsymbol{x}^{(i)}$ to have been generated from distribution $F_j$ is computed

* The *maximization step*, in which the probability and the parameters of each distribution are updated

Because it is impossible to know which samples have been generated by each distribution, it is also impossible to directly maximize the log-likelihood, which is why we compute its *expected value* using the posterior probabilities, hence the name *expectation step*. The second step simply consists in maximizing the expected log-likelihood, hence the name *maximization step*.
## Algorithm 2 Expectation-maximization algorithm for Gaussian mixture models

**Result:** Mean vectors {$\mu_j$}$_{j=1}^k$, covariance matrices {$\Sigma_j$}$_{j=1}^k$ and probabilities {$\pi_j$}$_{j=1}^k$

Initialize the mean vectors {$\mu_j$}$_{j=1}^k$, covariance matrices {$\Sigma_j$}$_{j=1}^k$ and probabilities {$\pi_j$}$_{j=1}^k$;

while not converged do

**E-step:** Compute the posterior probability $\gamma_i(j)$ for each sample $\mathbf{x}^{(i)}$ to have been generated from distribution $F_j$:

$$ \forall i \in \{1, \dots, n\}, \forall j \in \{1, \dots, k\}, \gamma_i(j) = \frac{\pi_j p_j(\mathbf{x}^{(i)}; \theta_j, \Sigma_j)}{\sum_{l=1}^{k} \pi_l p_l(\mathbf{x}^{(i)}; \theta_l, \Sigma_l)} $$

**M-step:** Update the parameters of each distribution $F_j$:

$$ \forall j \in \{1, \dots, k\}, \quad \boldsymbol{\mu}_j = \frac{\sum_{i=1}^{n} \gamma_i(j) \mathbf{x}^{(i)}}{\sum_{i=1}^{n} \gamma_i(j)} $$

$$ \forall j \in \{1, \dots, k\}, \quad \boldsymbol{\Sigma}_j = \frac{\sum_{i=1}^{n} \gamma_i(j) [\mathbf{x}^{(i)} - \boldsymbol{\mu}_j] [\mathbf{x}^{(i)} - \boldsymbol{\mu}_j]^\top}{\sum_{i=1}^{n} \gamma_i(j)} $$

$$ \forall j \in \{1, \dots, k\}, \quad \pi_j = \frac{1}{n} \sum_{i=1}^{n} \gamma_i(j) $$

Lloyd's and EM algorithms have a lot of similarities. In the first step, the assignment step assigns each sample to its closest cluster, whereas the expectation step computes the probability for each sample to have been generated from each distribution. In the second step, the update step computes the centroid of each cluster as the mean of the samples in a given cluster, while the maximization step updates the probability and the parameters of each distribution as a weighted average over all the samples. For these reasons, the k-means algorithm is often referred to as a *hard-voting* clustering method, as opposed to the Gaussian mixture model which is referred to as a *soft-voting* clustering method.

The Gaussian mixture model has several advantages over the k-means algorithm.

First, the use of normal distribution densities instead of Euclidean distances dwindles the inflation issue in high-dimensional spaces. Second, the Gaussian mixture model includes covariance matrices, allowing for clusters with elliptical shapes, while the k-means algorithm only includes centroids, forcing clusters to have circular shapes.
Nonetheless, the Gaussian mixture model also has several drawbacks, sharing a few with the *k*-means algorithm.

First, the number of distributions *k* is a hyperparameter. Setting a value much different from the actual number of clusters may yield poor clusters. Second, the log-likelihood is not a concave function. Like Lloyd's algorithm, the EM algorithm is guaranteed to converge, but it may converge to a local maximum that is not a global maximum. Several strategies are often applied to address this issue, including sophisticated centroid initialization [22] and running the algorithm numerous times and keeping the best run (i.e., the one yielding the highest log-likelihood). Third, the Gaussian mixture model has more parameters than the *k*-means algorithm. Therefore, it usually requires more samples to accurately estimate its parameters (in particular the covariance matrices) than the *k*-means algorithm.

# 13 Dimensionality Reduction

Dimensionality reduction consists in finding a good mapping from the input space into a space of lower dimension. Dimensionality reduction can either be unsupervised or supervised.

## 13.1 Principal Component Analysis

For exploratory data analysis, it may be interesting to investigate the variances of the *p* features and the $\frac{1}{2}p(p-1)$ covariances or correlations. However, as the value of *p* increases, this process becomes growingly tedious. Moreover, each feature may explain a small proportion of the total variance. It may be more desirable to have another representation of the data where a small number of features explain most of the total variance, in other words to have a coordinate system adapted to the input data.

Principal component analysis (PCA) consists in finding a representation of the data through *principal components* [25]. The principal components are a sequence of unit vectors such that the *i*-th vector is the best approximation of the data (i.e., maximizing the explained variance) while being orthogonal to the first *i* − 1 vectors.

Figure 23 illustrates principal component analysis when the input space is two-dimensional. On the upper figure, the training data in the original space is plotted. Both features explain about the same amount of the total variance, although one can clearly see that both features are strongly correlated. Principal component analysis identifies a new Cartesian coordinate system based on the input data. On the lower figure, the training data in the new coordinate system is plotted. The first dimension explains much more variance than the second dimension.
<figure><img src="image_41.png" /><figcaption>**Fig. 23** Illustration of principal component analysis. On the upper figure, the training data in the original space (blue points with black axes) is plotted. Both features explain about the same amount of the total variance, although one can clearly see a linear pattern. Principal component analysis learns a new Cartesian coordinate system based on the input data (red axes). On the lower figure, the training data in the new coordinate system is plotted (green points with red axes). The first dimension explains much more variance than the second dimension</figcaption></figure>

### 13.1.1 Full Decomposition

Mathematically, given an input matrix $X \in \mathbb{R}^{n \times p}$ that is centered (i.e., the mean value of each column $X_{:,j}$ is equal to zero), the objective is to find a matrix $W \in \mathbb{R}^{p \times p}$ such that:

* $W$ is an orthogonal matrix, i.e., its columns are unit vectors and orthogonal to each other.

* The new representation of the input data, denoted by $T$, consists of the coordinates in the Cartesian coordinate system induced by $W$ (whose columns form an orthogonal basis of $\mathbb{R}^p$ with the Euclidean dot product):

$$T = XW$$

* Each column of $W$ maximizes the explained variance.
Each column $w_i = W_{:,i}$ is a principal component. Each input vector $x$ is transformed into another vector $t$ using a linear combination of each feature with the weights from the $W$ matrix:

$$t = x^{\top} W$$

The first principal component $w^{(1)}$ is the unit vector that maximizes the explained variance:

$$ \begin{aligned} w_1 &= \arg \max \left\{ \sum_{i=1}^{n} x^{(i)\top} w \right\} \\ &= \arg \max \left\{ \| X w \| \right\} \\ &= \arg \max \left\{ w^{\top} X^{\top} X w \right\} \\ w_1 &= \arg \max_{w \in \mathbb{R}^p} \left\{ \frac{w^{\top} X^{\top} X w}{w^{\top} w} \right\} \end{aligned} $$

As $X^\top X$ is a positive semi-definite matrix, a well-known result from linear algebra is that $w^{(1)}$ is the eigenvector associated with the largest eigenvalue of $X^\top X$.

The $k$th component is found by subtracting the first $k-1$ principal components from $X$:

$$\hat{X}_k = X - \sum_{s=1}^{k-1} X w^{(s)} w^{(s)\top}$$

and then finding the unit vector that explains the maximum variance from this new data matrix:

$$w_k = \arg \max_{\|w\|=1} \{\|\hat{X}_k w\|\} = \arg \max_{w \in \mathbb{R}^p} \left\{ \frac{w^\top \hat{X}_k^\top \hat{X}_k w}{w^\top w} \right\}$$

One can show that the eigenvector associated with the $k$th largest eigenvalue of the $X^\top X$ matrix maximizes the quantity to be maximized.

Therefore, the matrix $W$ is the matrix whose columns are the eigenvectors of the $X^\top X$ matrix, sorted by descending order of their associated eigenvalues.

Since each principal component iteratively maximizes the remaining variance, the first principal components explain most of the total variance, while the last ones explain a tiny proportion of the total variance. Therefore, keeping only a subset of the ordered principal components usually gives a good representation of the input data.

Mathematically, given a number of dimensions $l$, the new representation is obtained by truncating the matrix of principal components $W$ to only keep the first $l$ columns, resulting in the submatrix $W_{:,l}$: