Catégories
Non classé

Système statistique pour la conception de modèles prédictifs

Système statistique pour la conception de modèles prédictifs

lab-logo

Les statisticiens ont changé le monde: non pas en découvrant de nouvelles techniques, mais en changeant la façon dont nous raisonnons, expérimentons et forgeons nos opinions. –Ian Hacking

Les modèles prédictifs constituent la base du machine learning. De ces modèles théoriques ont émergées de nouvelles approches expérimentales afin de correspondre au mieux à ces modèles avec des jeux de données très différents. Dans ce billet, nous vous présentons les systèmes statistiques utilisés à Digigladd pour constituer nos modèles prédictifs.

 

Photo par Chris Liverani @ Unsplash

Nous définissons un modèle sous certaines hypothèses et certains critères.

  • Nous possédons un vecteur de données d’entrées X composé de p paramètres inconnus.
  • Nous possédons une variable Y représentant la sortie de notre modèle sachant X.
  • Il existe une fonction f permettant d’inférer Y sachant X.
  • Afin de trouver le prédicteur optimal f selon un critère précis, nous définissons une fonction de coût Lf selon ce critère.
  • Plus notre prédiction est proche de la réalité, plus Lf sera minimisée.

Comme la qualité du prédicteur est mesurée par la fonction de coût Lf, le meilleur prédicteur f n’est optimal que pour le critère choisi pour définir Lf. Différentes fonctions de coût amènent différentes solutions optimales.

Il n’est généralement pas possible de trouver un prédicteur qui soit optimal selon tous points de vue. A critère fixé, nous étudierons l’espérance de notre fonction de coût afin de déterminer le prédicteur optimal.

Notons la loi de probabilité et E l’espérance.

 

Selon le théorème de Bayes,

 

Puis, en séparant l’intégrale à deux variables :

 

Il est maintenant possible de trouver f en minimisant le taux d’erreur E(Lf) point par point.
Soit c ∈ ℝᵖ, et L_Id la fonction de coût appliqué à la fonction identité de ℝᵖ. 

 

En minimisant l’espérance ci-dessus analytiquement ou numériquement, nous pouvons trouver le meilleur prédicteur f associé.

Une étude de cas nous aidera à clarifier la manière de trouver f sur une fonction de coût précise.

Etude de cas: Erreur quadratique moyenne (MSE)

La fonction de coût la plus répandue en Machine Learning ou Deep Learning est certainement l’erreur quadratique moyenne:

 

Selon la section précédente,

D’où:

 

La solution au critère de minimisation est f(x) = E(Y|X=x), car :

Nous venons de démontrer que quand la fonction de coût est l’erreur quadratique, le meilleur prédicteur Y en tout point X=x est la moyenne conditionnelle:

 

Ce prédicteur est souvent est souvent désigné sous le terme de régression linéaire. Nous pourrions ensuite déterminer β en injectant f(x) dans l’intégrale à deux variable, puis en déterminant les racines du vecteur dérivé de l’intégrale selon β.

Un autre choix possible pour notre fonction de coût est la valeur absolue de l’erreur:

 

Nous pouvons prouver dans ce cas que le prédicteur optimal est la médiane conditionnelle:

 

La médiane conditionnelle est un différent choix de prédicteur, dont les estimations sont généralement plus robuste que l’erreur quadratique. Malheureusement, sa fonction dérivée est discontinue, ce qui handicape plusieurs algorithmes de minimisation.

Lorsque nous voulons prédire une variable Y qui prend des valeurs discrètres c₁, c₂, …, cₖ pouvant être assimilées à différents choix, on parle de classification.

Notre fonction de coût peut alors être représentée sous la forme d’une matrice K×K, avec K le nombre de classes. Lf(ci, cj) est le coût pour une mauvaise classification de ci à la place de cj.

 

 

Nous pouvons à nouveau calculer l’espérance de notre fonction de coût:

 

Il est à nouveau possible de minimiser point par point cette fonction pour déterminer une expression de f:


Un cas très répendu de fonction de coût est la “0-1 loss”. Si la prédiction est juste, le coût est de 0, sinon le coût est de 1.

En notant δ la fonction de Kronecker, l’espérance du coût est la suivante:

 

Le choix optimal pour f qui minimise 1−ℙ(f(X)|X) pour tout x est alors:

 

Ce prédicteur est connu sous le nom de classifieur de Bayes. Comme les probabilités ℙ(c|X)   sont généralement inconnues en pratique, ce prédicteur est plus un concept théorique. En revanche, en appliquant le théorème de Bayes en supposant l’indépendance mutuelle de tous les paramètres:

Ceci est le classifieur de Bayes naïf, qui peut lui être implémenté en pratique.

Tous les prédicteurs que nous avons étudiés dans les sections précédentes présentent des inconvénients importants. Si les données d’entrée X possèdent une structure sous-jacente, une simple régression ne peut pas réduire à la fois le biais et la variance des estimations. En outre, une régression peut entraîner des erreurs de plus en plus importantes proportionnellement au nombre de paramètres d’entrée.

Notre objectif sur ce point consiste à trouver une approximation ˆf (x) de la fonction f (x) qui conserve la relation potentiellement structurée entre les entrées et les sorties, et qui fonctionne  dans des dimensions élevées.

Ce problème peut être résolu par deux approches différentes.

L’approche adoptée en mathématiques appliquées et en statistiques utilise l’approximation et  l’estimation des fonctions.

Les entrées et les sorties sont considérés comme des points dans un espace euclidien, et l’estimateur de prédiction cartographie les paires (X, Y) dans un hyperplan de cet espace. L’estimateur s’exprime désormais comme suit:

 

Ces estimateurs seront choisis en imposant de lourdes restriction sur la classe des modèles appliqués. 

De cette approche mathématique sont nées différentes méthodes de résolution. Les plus connues sont : la roughness penalty, les méthodes des kernels et les basis functions.

Cette approche tente d’apprendre f à l’aide d’un superviseur qui tend à minimiser la fonction de coût. L’objectif du superviseur est de produire des sorties ˆf(xi) en réponse aux différentes entrées. À la fin du processus d’apprentissage, nous voulons que les sorties prédites et réeles soient suffisamment proches pour que le superviseur puisse s’adapter aux nouvelles entrées qu’il rencontrera en pratique.

Le Machine Learning tel que nous le connaissons aujourd’hui est issu de cette approche-ci.

Catégories
Non classé

Résolution d’un problème de logistique avec une IA

Résolution d'un problème de logistique avec l'IA

lab-logo
Le Machine Learning et le Deep Learning ont le vent en poupe dans l’industrie. Cependant, les approches plus conventionnelles ne doivent pas être négligées, car elles permettent de résoudre de nombreux problèmes d’organisation, de planning et de logistique avec peu de données.

Un problème de logistique

Considérons une problématique tout à fait actuelle :

Il y a une pandémie. Les hôpitaux doivent s’organiser rapidement pour soigner les malades.

Il faut un algorithme qui associe les personnes infectées et les hôpitaux en fonction de plusieurs critères tels que la gravité de la maladie, l’âge et l’emplacement du patient, la capacité et l’équipement des hôpitaux, etc.

Carte de la pandémie Fig. 1. Carte de la pandémie, réduite à 4 paramètres : localisation et gravité des patients, localisation et capacité des hôpitaux.

Il est possible de penser qu’un réseau de neurones conviendrait parfaitement à ce problème: des configurations différentes sur beaucoup de paramètres qui doivent être réduits à une solution unique et optimale.

Cependant, certains inconvénients compromettent une telle approche:

  • Le modèle doit être entraîné, il faut de nombreuses données historiques sur les cas précédents,
  • Beaucoup de temps serait perdu à nettoyer et à consolider les données récoltées,
  • Différentes architectures devraient être testées durant de longues sessions d’entraînement.

En revanche, en formulant le problème sous forme de satisfiabilité booléenne, la situation n’aurait aucun des inconvénients susmentionnés tout en donnant une solution sous-optimale en temps polynomial et non déterministe (problème NP-complet), et sans la nécessité de devoir regroupes un jeu de données historiques.

Formulation du problème

La carte de la pandémie (1) illustre les résultats de notre algorithme qui associera les personnes infectées aux hôpitaux. Il existe plusieurs frameworks pour la résolution des contraintes. Google Optimization Tools (a.k.a., OR-Tools) est une suite logicielle open source pour résoudre les problèmes d’optimisation combinatoire. Notre problème sera modélisé en utilisant ce framework en Python.

from ortools.sat.python import cp_model

Un notebook complet pour ce prolbème peut-être trouvé ici.

Paramètres

Pour le moment, simplifions le problème à 4 paramètres:

  • Localisation des personnes infectées
  • Severité de la maladie chez ces personnes
  • Localisation des hôpitaux
  • Nombre de lits dans chaque hôpital

Définissions ces paramètres en python:

# Number of hospitals
n_hospitals = 3
# Number of infected people
n_patients = 200
# Number of beds in every hospital
n_beds_in_hospitals = [30,50,20]
# Location of infected people -- random integer tuple (x,y)
patients_loc = [(randint(0, 100), randint(0, 100)) for _ in range(n_patients)]
# Location of hospitals -- random integer tuple (x,y)
hospitals_loc = [(randint(0, 100), randint(0, 100)) for _ in range(n_hospitals)]
# Illness severity -- 1 = mild -> 5 = severe
patients_severity = [randint(1, 5) for _ in range(n_patients)]

Variables

Un problème de satisfaction des contraintes consiste en un ensemble de variables auxquelles des valeurs doivent être affectées de manière à ce qu’un ensemble de contraintes soit satisfait.

  • Soit I l’ensemble des hôpitaux
  • Soit Jᵢ l’ensemble des lits de l’hôpital i
  • Soit K l’ensemble des patients

Nous pouvons définir notre série de variables:

Si dans l’hôpital i, le lit j est pris par la personne k alors xᵢⱼₖ = 1.

Nous pouvons ajouter ces variables à notre modèle:

model = cp_model.CpModel()
x = {}
for i in range(n_hospitals):
for j in range(n_beds_in_hospitals[i]):
for k in range(n_patients):
x[(i,j,k)] = model.NewBoolVar("x(%d,%d,%d)" % (i,j,k))

Contraintes dures

Les contraintes dures définissent un objectif pour notre modèle. Elles sont essentielless, si elles ne sont pas respectées, le problème ne peut pas être résolu:
 
  • Il doit y avoir au plus une seule personne dans chaque lit,
  • Il doit y avoir au plus un lit  attribué à chaque personne.
     

Concentrons-nous sur la première contrainte. Pour chaque lit j dans chaque hôpital i :

  • Soit il y a un unique patient k,
  • Soit le lit est vide.

Par conséquent, la contrainte est exprimable de la façon suivante:

Notre solveur fait de l’optimisation combinatoire, il ne peut traiter que des contraintes sur des nombres entiers. Par conséquent, l’expression de la contrainte doit être formulée de la façon suivante :

Cette inégalité peut être ajoutée à notre modèle.

# Each bed must host at most one person
for i in range(n_hospitals):
for j in range(n_beds_in_hospitals[i]):
model.Add(sum(x[(i,j,k)] for k in range(n_patients)) <= 1)

Ensuite, traitons la seconde contrainte pour chaque patient k:

  • Soit il est dans un unique lit j dans un hôpital i,
  • Soit il est chez lui.

De la même façon, cette contrainte est exprimable sous la forme d’une inéquation :

Finalement, il est possible de l’ajouter au modèle.

# Each person must be placed in at most one bed
for k in range(n_patients):
inner_sum = []
for i in range(n_hospitals):
inner_sum.append(sum(x[(i,j,k)] for j in range(n_beds_in_hospitals[i])))
model.Add(sum(inner_sum) <= 1)

Contraintes douces

Viennent ensuite les contraintes douces. Notre solution doit essayer de les satisfaire au maximum, mais elles ne sont pas indispensables pour trouver une solution:

  • Chaque personne malade devrait être placée dans un lit,
  • Chaque personne devrait être prise en charge par l’hôpital le plus proche,
  • Les personnes malades dans un état grave devraient être traitées en premier lorsqu’il n’y a pas assez de lits.

Alors que les contraintes dures sont modélisées comme des égalités ou des inégalités, les contraintes souples sont des expressions à minimiser ou maximiser.

Soit Ω l’ensemble de toutes les solutions qui satisfont aux contraintes dures.“Chaque personne malade doit être placée dans un lit” peut être traduit en “maximiser le nombre de lits occupés”.“Chaque personne doit être prise en charge par l’hôpital le plus proche” peut être traduit en “minimiser la distance entre chaque patient et l’hôpital qui lui est affecté”.“Les personnes malades dans un état grave doivent être traitées en premier lorsqu’il n’y a pas suffisamment de lits” peut être traduit en “maximiser la gravité totale de tous les patients pris en charge”. En désignant sev (k) la gravité du patient k :Nous pouvons réduire toutes ces contraintes en un seul objectif :Il faut alors être prudent: ces contraintes souples n’ont pas toutes le même domaine de définition.

  • La contrainte de maximisation des patients va de 0 à n, avec n le nombre de patients,
  • La contrainte de gravité varie de 0 à 5n,
  • La contrainte de distance va de 0 à la distance euclidienne maximale entre i et k.

Étant donné que toutes ces contraintes partagent la même priorité, nous devons définir des facteurs de pénalité pour équilibrer les différentes contraintes.
Voici le code correspondant:

# Integer distance function
idist = lambda xy1, xy2: int(((xy1[0]-xy2[0])**2 + (xy1[1]-xy2[1])**2)**0.5)
# Gain factors (1/penalty factors)
gain_max_patients = 140
gain_severity = int(140/5)
gain_distance = -1
# Maximization objective
soft_csts = []
for i in range(n_hospitals):
for j in range(n_beds_in_hospitals[i]):
for k in range(n_patients):
factor = \
gain_max_patients \
+ gain_distance * idist(hospitals_loc[i], patients_loc[k]) \
+ gain_severity * patients_severity[k]
soft_csts.append(factor * x[(i,j,k)])
model.Maximize(sum(soft_csts))

Solveur

Nous pouvons maintenant lancer le solveur. Il essaiera de trouver la solution optimale dans un délai spécifié. S’il ne parvient pas à trouver la solution optimale, il renverra la solution sous-optimale la plus proche.

solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 60.0
status = solver.Solve(model)

Dans notre cas, le solveur renvoie une solution optimale en 2,5 secondes (2).

 

Fig. 2. Solution retournée par le solveur
 

Conclusion

Cette solution ne demande pas beaucoup de temps afin d’être conçue et implémentée.
Pour une solution équivalente en Deep Learning, le temps de conception est au moins multiplié par 10 avec le tri des données, le choix de l’architecture et l’entraînement du modèle.

De plus, un modèle CP-SAT tel que celui-ci est très robuste s’il est bien modélisé. Voici les résultats avec différents paramètres de simulation (3). Les résultats sont toujours cohérents dans de nombreux cas différents, et en augmentannt les paramètres de simulation (3000 patients, 1000 lits), l’inférence d’une solution a pris un peu moins de 3 minutes.

 

Fig. 3: Différents paramètres de simulation

Bien sûr, les solveurs de contraintes ne s’appliquent guère à des sujets comme la vision par ordinateur et le traîtement du langage, dans lesquels le Deep Learning est souvent la meilleure approche. Cependant, en matière de logistique, d’ordonnancement et de planification, ces solveurs restent dans la plupart des cas la voie à suivre.

Catégories
Non classé

IA, Deep Learning, Data : Trop de battage médiatique ?

IA, Deep Learning, Data : Trop de battage médiatique ?

tech-logo

Un doctorant australien en intelligence artificielle a récemment publié sur LinkedIn ses recherches sur le SARS-CoV-2. Le message a récolté des milliers de vues, de likes et de partages.

Génie inconnu ou sur-médiatisation ?

Un post viral sur le COVID-19

Cette personne a réalisé un modèle d’apprentissage profond capable de prédire si un patient est infecté par le virus COVID-19 à partir de radiographies thoraciques avec une précision annoncée de 97,5%.

En l’état, le projet comprend:

  • Un réseau de neurones entraîné,
  • Du code applicatif conteneurisé,
  • Un dépôt GitHub traduit en 8 langues,
  • Une application web en cours de développement,
  • Une application mobile en cours de développement,
  • Une architecture cloud serverless pour héberger le modèle,
  • De nombreuses percées marketing.

Tout ce qui précède a été construit en une semaine environ.

Deep learning et diagnostic médical

Les réseaux convolutionnels profonds présentent des avantages potentiels pour le diagnostic et le traitement des maladies. De nombreuses publications scientifiques ont été postées ces dernières années [1], en voici quelques-unes:

  • En 2016, un groupe de chercheurs londoniens a publié une méthode pour diagnostiquer la rétinopathie diabétique avec une précision de 86%, le modèle a été entraîné sur 80 000 photographies de fond d’œil [2].
  • La même année, des chercheurs ougandais ont évalué les performances des réseaux convolutionnels sur des frottis sanguins microscopiques à l’aide d’un jeu de données constitué de 10 000 objets [3].
  • Un effort pour classer les nodules pulmonaires a été mené par deux chercheurs japonais sur 550 000 tomodensitogrammes [4].

Ici cependant, un rapide aperçu du dépôt de code dépeint au mieux un manque crucial de compétences dans les domaines du Deep Learning et de l’apprentissage automatique, et au pire une tentative vicieuse d’auto-promotion tout en capitalisant sur la pandémie.

Problèmes inhérents à cette l’étude

Il existe de nombreux problèmes inhérents à cette solution. Premièrement, la représentation neuronale latente sur ce type de réseau est très complexe: elle a besoin de beaucoup de données d’entraînement, comme décrit dans les études susmentionnées.

Mais pour l’instant, ce détecteur de COVID-19 a été entraîné sur…
50 images uniquement !

Fig. 1: Le modèle s’entraîne sur des radiographies X.
Source : NIH Chest X-ray dataset

Pour un réseau qui compte plus de 150 couches et 20 millions de neurones, c’est plus qu’absurde.

De plus, il existe un énorme biais sur le jeu de données. Les 50 images ne sont pas étiquetées en fonction de la présence ou non du virus, elles sont étiquetées en fonction des lésions pulmonaires dans les cas aigus de COVID-19. À moins que des poumons d’une personne ne soient déjà détruits par le virus, le modèle n’a aucun moyen de déceler une infection si cette personne effectue une radiographie.

Dans le cas d’une personne présentant des symptômes de pneumonie, la précision de ce modèle est indéterminée tant que ces symptômes ne sont pas aigus.


Enfin, le modèle utilise le ResNet-50 comme base de réseau pré-entraînté [5]. Bien qu’il s’agisse d’une approche habituelle pour la reconnaissance et la classification d’images, le ResNet a été pré-entraîné à l’aide de photos de différents objets du quotidien. Ainsi, ses couches internes sont usuellement activées avec des formes géométriques et des motifs colorés (2).

Fig. 2: Couches internes du ResNet-50 [6]
 
D’autres problèmes nous frappent lorsque nous examinons de plus près le dépôt de code. Les jeux de données d’entraînement, de validation et de test contiennent des images dupliquées; la majeure partie du programme est tirée d’un didacticiel trouvable sur internet, obscurci avec du code inutile…
 
Pourtant, ce post a récolté plus de 10 000 partages et mentions j’aime sur LinkedIn, de la part de personnes très certainement curieuses et intéressées par les avancées de l’IA. Bien que ce domaine soit en vogue et que de nombreux articles paraissent tous les jours, il est nécessaire de s’interroger sur les compétences que chacun fait miroiter.
 

 
 
La propagande en tant qu’instrument de concurrence commerciale a ouvert des opportunités à l’inventeur et a donné une grande impulsion au chercheur.
 
Edward L. Bernays
 
 
Le Deep Learning n’est pas une solution miracle. De nombreuses entreprises non préparées ont tenté d’internaliser leurs process data, puis ont vu leurs dépenses augmenter alors que rien ne passait en production.
 
Pourtant, les progrès de l’IA sont fulgurants, il est impossible de les ignorer complètement.
 
Cela ne signifie pas plonger directement dans la piscine et se débattre dans l’eau jusqu’à bout de souffle.
Il suffit d’une équipe solide, fiable, avec des compétences transversales en IA / ML, DataOps, architecture et développement.

Références