Module d'appel aux méthodes d'optimisation¶
- Module d'appel aux méthodes d'optimisation
Fonction d'interface pour faciliter l'utilisation de plusieurs libraires d'optimisation¶
Les modules d'analyse de QTLMap font appel à une unique interface afin de rendre modulable l'appel à l'optimisation (quasi-newton, descente de gradient,...) et de ne pas dépendre d'une libraire (NLOPT, NAG,...)
Il existe 4 types d'interface :- la subroutine minimizing_funct pour optimiser n'importe quelle fonction à N variables.
- la subroutine minimizing_funct_family pour optimiser une fonction de vraisemblance utilisant une structure de type MODLIN (--calcul=2)
- la subroutine minimizing_funct_family_sire pour optimiser une fonction de vraisemblance utilisant une structure de famille de pere seulement (--calcul=1)
- la subroutine minimizing_funct_family_multi pour optimiser une fonction de vraisemblance pour du multicaractere
public :: set_optimization public :: minimizing_funct public :: minimizing_funct_family public :: minimizing_funct_family_sire public :: minimizing_funct_family_multi
la subroutine set_optimization permet d'initaliser le type d'optimisation.
Librairies externes¶
Utilisation du quasi newton NAG e04jyf¶
NLOPT¶
LBFGS¶
Optimisation pour les calculs de type MODLIN¶
Indépendances des paramètres à optimiser grâce à la structure familiale¶
On utilise la structure de famille et l'indépendance de certain paramètre dans le calcul des vraisemblances des sous familles pour optimiser la calcul du gradient utilisé par les optimisateurs (quasi newton, gradient conjugués....).
La fonction de vraisamblance est décomposé en somme de fonction des vraisemblances de chaque famille. F(X1,..,Xn) = SUM F ip,jm (X1,...,Xn). Plusieurs paramètres xi correspondent à des paramètres à optimiser pour la vraisamblance d'une sous famille et n'interviennent pas dans le calcul des autres vraisemblances.
Exemples:
- les effets polygéniques
- les effets QTL
- Un niveau d'un effet fixé non représenté dans une famille (Les F2 sont que males pour cette famille par exemple)
Description de l'optimisation sur un exemple¶
Actuellement, on écrit une fonction de vraisemblance prenant comme paramètres :- N : le nombre de paramètre a optimiser
- X : les valeurs des paramètres à tester
- F : le résultat de la vraisemblance globale
Soit 2 familles de père accouplé avec 3 meres (les 2 première mère avec le pere 1 et la dernière avec le pere 2),
On peut décomposer la fonction de vraisemblance ainsi:
F(X1,...,Xn) = F ip=1,jm=1 (X1,...,Xn) + F ip=1,jm=2 (X1,...,Xn) + F ip=2,jm=3 (X1,...,Xn) avec le cout (temps d'exécution) COUT(F)=1 et COUT(F [ip=1,jm=1]) = 1/3,COUT(F [ip=1,jm=2]) = 1/3 ,COUT(F [ip=2,jm=3]) = 1/3
nous avons comme interprétation du vecteur X :
| Sig 1 | Sig 2 | MuGen | PolyPere1 | PolyPere2 | PolyMere1 | PolyMere2 | PolyMere3 |
Les trois sous familles sont influencés par les paramètres en gras (et la variation des autres paramètres
n'influence pas le résultat de la vraisemblance de la famille) :
| ip=*1*, jm=*1* | |||||||||||||||||||||||||||||
| Sig 1 | Sig 2 | MuGen | PolyPere1 | PolyPere2 | PolyMere1 | PolyMere2 | PolyMere3 | |
ip=*1*, jm=*2* | |
Sig 1 | Sig 2 | MuGen | PolyPere1 | PolyPere2 | PolyMere1 | PolyMere2 | PolyMere3 | |
ip=*2*, jm=*3* | |
Sig 1 | Sig 2 | MuGen | PolyPere1 | PolyPere2 | PolyMere1 | PolyMere2 | PolyMere3 |
Le calcul de la dérivé sur un paramètre peut s'écrire :
df/dx = f(..,Xi+h,..)-f(..,xi-h,..)/2*h
L'optimisateur appèle à chaque itération 2 * N la fonction F pour tester les variations de chaque paramètre (X-delta, X+delta) et obtenir la dérivé au point F
cout global = 8 * 2 = 16
Si nous prenons en comptes que les appels effectifs (paramètres en gras). A savoir
cout global = 12 * 2 * 1/3 = 8
sous reserve que le cout des fonctions de vraisemblance des sous familles soit bien la somme du cout globale et qu'elle soit égale entre elle, nous avons donc une optimisation de 50% du temps d'exécution
Implémentation¶
Structure de donnée¶
L'idée est donc de donner à l'optimisateur :- Un filtre de booléen (taille N) pour chaque famille IP,JM indiquant les paramètres de X influençant la vraisemblance de la famille IP,JM
- Une fonction de VRAISEMBLANCE d'une sous famille à optimiser, générique à
l'ensemble des sous famille (FUNCT).
Le calcul du gradient optimisé s 'écrit donc:¶
Construction du filtre¶
La construction du filtre se fait a partir de la matrice d'incidence réduite (l'estimabilité des paramètres via la décomposition de cholesky nous donnes la matrice d'incidence effective utilisée lors de l'optimisation).
Pour chaque colonnes (correspondant au ieme parametre de X), on teste si l'ensemble des valeurs est égale à zéro. Si c'est le cas, le ième paramètres de X n'influence pas la vraissemblance de la sous famille ip,jm.
Benchmark¶
- Compilation en mode optimisé O4 avec gfortran
- 3 exemples sont donnés : marie damon,nicolas deschamp et exemple porc:
Chaque exemple présente :
- la taille du jeu de donnee : np,nm,effet de nuisance => nombre de niveau a estime
- 2 prints d'exécution non optimisé et optimisé , chaque ligne correspond à :
- temps de l'optimisation
- nombre d'appel effectif du calcul de la vraissemblance total
- nombre d'appel au calcul de gradient
- nombre d'appel evité du a la recuperation de la vraisemblance d'une famille
- le taux d'appel optimisé (nb appel evité/ (nb appel + nb appel evite) )
- Le filtre initialisé sous H0 en guise d exemple (ce filtre étant recalculé à chaque position par la suite)
Voici un tableau récapitulatifs des résultats.
| Exemple | Effets de nuisances | Nb niveaux(H1) | Temps cumul non optim | Temps cumul optim | Taux d'optimisation | ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Marie | 0 | 53 | 3,34 | 0,40 | 91,70% | |
Nicolas | 5 | 61 | 8,54 | 3,77 | 58,70% | |
Exemple porc | 0 | 16 | 0.240 | 0,07 | 76,50% |
- Cette optimisation ne peux s appliquer aux méthodes pour les données précalculés puisque le calcul de vraisemblance de la dernière mère à estimer est en fonction des autres mères estimables.
- Pour executer un benchmark, il faut generer le Makefile avec l'option -DBENCHMARK=true
- L'implementation nécéssite d'avoir "la main" sur la calcul du gradient (ce n'est pas le cas pour e04jyf par exemple).
- Le cout des appels de fonctions n'est pas pris en compte (sur une itération, il y a bien plus d'appels aux fonctions de vraisemblance des sous familles qu'a la fonction de vraisemblance globale (sur l'exemple cité plus haut 12*2=24 contre 8*2=16)