Dans le champ contemporain de l’apprentissage automatique et de la mod\u00e9lisation statistique avanc\u00e9e, l’abondance des donn\u00e9es constitue simultan\u00e9ment une opportunit\u00e9 remarquable et un d\u00e9fi analytique consid\u00e9rable. L’acc\u00e8s banalis\u00e9 \u00e0 des vecteurs de caract\u00e9ristiques de tr\u00e8s grande dimension expose le statisticien et l’ing\u00e9nieur de donn\u00e9es \u00e0 une pathologie bien connue : le fl\u00e9au de la dimensionnalit\u00e9. Lorsqu’un mod\u00e8le int\u00e8gre un nombre disproportionn\u00e9 de variables pr\u00e9dictives par rapport au nombre d’observations empiriques disponibles, les estimations perdent leur stabilit\u00e9, la variance des param\u00e8tres explose et l’interpr\u00e9tabilit\u00e9 ph\u00e9nom\u00e9nologique du syst\u00e8me s’effondre. Face \u00e0 cette prolif\u00e9ration de pr\u00e9dicteurs potentiels, la s\u00e9lection de variables s’impose non pas comme une simple \u00e9tape technique d’ing\u00e9nierie pr\u00e9liminaire, mais comme un imp\u00e9ratif \u00e9pist\u00e9mologique visant \u00e0 isoler le signal fondamental du bruit al\u00e9atoire inh\u00e9rent au monde physique et humain.<\/p>\n
Parmi l’arsenal m\u00e9thodologique d\u00e9di\u00e9 \u00e0 la r\u00e9duction dimensionnelle, la s\u00e9lection du meilleur sous-ensemble \u2014 universellement d\u00e9sign\u00e9e sous l’appellation anglo-saxonne de Best Subset Selection<\/em> \u2014 occupe une position canonique et th\u00e9oriquement pure. Contrairement aux approches heuristiques descendantes, ascendantes ou aux m\u00e9thodes de r\u00e9gularisation continue fond\u00e9es sur des p\u00e9nalit\u00e9s douces, la m\u00e9thode du meilleur sous-ensemble s’attache \u00e0 explorer l’int\u00e9gralit\u00e9 combinatoire des configurations possibles de pr\u00e9dicteurs. Elle r\u00e9sout directement le probl\u00e8me d’optimisation math\u00e9matique sous contrainte de parcimonie stricte, formul\u00e9 au moyen de la norme L0, garantissant ainsi l’identification du mod\u00e8le optimal pour chaque degr\u00e9 de complexit\u00e9 fix\u00e9 a priori. Cette rigueur absolue conf\u00e8re au proc\u00e9d\u00e9 le statut de standard d’or (gold standard<\/em>), servant d’\u00e9talon th\u00e9orique \u00e0 l’aune duquel toutes les m\u00e9thodes approch\u00e9es sont invariablement \u00e9valu\u00e9es.<\/p>\n Ce guide exhaustif se propose d’explorer en profondeur l’ensemble des dimensions conceptuelles, math\u00e9matiques, algorithmiques et appliqu\u00e9es du Best Subset Selection<\/em>. De l’\u00e9lucidation du compromis biais-variance \u00e0 la formalisation des crit\u00e8res d’information p\u00e9nalis\u00e9s tels que l’AIC, le BIC et le Cp de Mallows, en passant par la gestion des co\u00fbts combinatoires exponentiels et l’impl\u00e9mentation industrielle sous les \u00e9cosyst\u00e8mes R et Python, ce trait\u00e9 offre une analyse rigoureuse destin\u00e9e aux chercheurs, psychom\u00e8tres et praticiens de l’apprentissage statistique. Une attention toute particuli\u00e8re sera port\u00e9e \u00e0 la mod\u00e9lisation des sciences cognitives et comportementales, domaine o\u00f9 la n\u00e9cessit\u00e9 d’une parcimonie intelligible rencontre la complexit\u00e9 subtile des mesures psychom\u00e9triques.<\/p>\n La formulation th\u00e9orique de l’apprentissage supervis\u00e9 repose sur l’hypoth\u00e8se de l’existence d’une relation fonctionnelle sous-jacente reliant un vecteur de pr\u00e9dicteurs, not\u00e9 X<\/em> appartenant \u00e0 un espace de dimension p<\/em>, \u00e0 une variable r\u00e9ponse continue ou cat\u00e9gorielle not\u00e9e Y<\/em>, \u00e9voluant dans l’espace unidimensionnel des r\u00e9els. L’objectif fondamental de la d\u00e9marche statistique consiste \u00e0 estimer cette fonction au moyen d’un op\u00e9rateur math\u00e9matique param\u00e9trique ou non param\u00e9trique, capable d’extraire la structure g\u00e9n\u00e9ratrice des donn\u00e9es. Dans cette optique, la d\u00e9finition formelle de l’espace des pr\u00e9dicteurs d\u00e9termine le p\u00e9rim\u00e8tre de l’information accessible \u00e0 l’algorithme. Toutefois, l’inclusion indiscrimin\u00e9e de toutes les covariables disponibles au sein du mod\u00e8le engendre une tension imm\u00e9diate entre la repr\u00e9sentativit\u00e9 descriptive sur l’\u00e9chantillon observ\u00e9 et la capacit\u00e9 de g\u00e9n\u00e9ralisation pr\u00e9dictive sur des donn\u00e9es nouvelles non observ\u00e9es.<\/p>\n L’introduction de covariables non informatives \u2014 c’est-\u00e0-dire de variables al\u00e9atoires orthogonales au signal th\u00e9orique ou ne pr\u00e9sentant que des corr\u00e9lations r\u00e9siduelles fortuites avec la cible \u2014 d\u00e9grade gravement les propri\u00e9t\u00e9s de l’estimateur. En augmentant artificiellement le nombre de degr\u00e9s de libert\u00e9 consomm\u00e9s par la proc\u00e9dure d’ajustement, ces variables parasites gonflent la variance de l’estimation sans apporter de r\u00e9duction correspondante du biais. D’un point de vue g\u00e9om\u00e9trique, l’espace vectoriel engendr\u00e9 par les colonnes de la matrice des donn\u00e9es s’\u00e9largit inutilement, for\u00e7ant la surface de r\u00e9gression \u00e0 s’adapter aux fluctuations stochastiques propres \u00e0 l’\u00e9chantillon d’apprentissage, un ph\u00e9nom\u00e8ne d\u00e9sign\u00e9 sous le terme de surajustement structurel.<\/p>\n Sur le plan \u00e9pist\u00e9mologique, cette qu\u00eate d’\u00e9conomie conceptuelle s’inscrit en droite ligne dans la tradition philosophique du rasoir d’Ockham<\/a> (lex parsimoniae<\/em>), stipulant que la pluralit\u00e9 ne doit pas \u00eatre postul\u00e9e sans n\u00e9cessit\u00e9. Transpos\u00e9 \u00e0 l’apprentissage supervis\u00e9, ce principe dicte qu’entre deux mod\u00e8les offrant une capacit\u00e9 pr\u00e9dictive rigoureusement comparable, l’analyste doit imp\u00e9rativement privil\u00e9gier celui reposant sur le sous-ensemble de pr\u00e9dicteurs le plus restreint. La parcimonie statistique ne constitue donc pas une simple commodit\u00e9 algorithmique, mais une condition sine qua non de la d\u00e9couvrabilit\u00e9 des lois scientifiques sous-jacentes et de la robustesse op\u00e9rationnelle des inf\u00e9rences.<\/p>\n L’arbitrage entre la complexit\u00e9 structurelle d’un mod\u00e8le et sa performance empirique est rigoureusement formalis\u00e9 par la d\u00e9composition de l’erreur quadratique moyenne de pr\u00e9diction (Mean Squared Error<\/em> ou MSE). Pour une observation non incluse dans l’ensemble d’apprentissage, l’erreur quadratique attendue se d\u00e9compose analytiquement en trois termes distincts : le carr\u00e9 du biais de l’estimateur, la variance intrins\u00e8que de l’estimateur induite par les fluctuations d’\u00e9chantillonnage, et la variance du terme d’erreur stochastique, souvent qualifi\u00e9e de bruit irr\u00e9ductible. Math\u00e9matiquement, cette \u00e9galit\u00e9 fondamentale s’\u00e9crit : E[(Y – f\u0302(X))\u00b2] = (Biais[f\u0302(X)])\u00b2 + Var(f\u0302(X)) + \u03c3\u00b2<\/em>, o\u00f9 \u03c3\u00b2<\/em> repr\u00e9sente la variance r\u00e9siduelle incompressible de la nature.<\/p>\n Lorsqu’un mod\u00e8le lin\u00e9aire incorpore l’ensemble des p<\/em> covariables disponibles sans discernement, le biais d’estimation tend vers son minimum th\u00e9orique si la sp\u00e9cification fonctionnelle est correcte, car le syst\u00e8me int\u00e8gre l’ensemble des m\u00e9diateurs et mod\u00e9rateurs potentiels du ph\u00e9nom\u00e8ne. En contrepartie, la variance de l’estimateur cro\u00eet proportionnellement au nombre de param\u00e8tres libres \u00e0 calibrer. Chaque nouveau coefficient estim\u00e9 agit comme un capteur suppl\u00e9mentaire capturant l’al\u00e9a sp\u00e9cifique de l’\u00e9chantillon. La s\u00e9lection de variables op\u00e8re ainsi une r\u00e9duction d\u00e9lib\u00e9r\u00e9e de la complexit\u00e9 structurelle en contraignant certains coefficients \u00e0 z\u00e9ro, acceptant potentiellement une fraction infinit\u00e9simale de biais suppl\u00e9mentaire en \u00e9change d’une r\u00e9duction drastique de la variance d’estimation.<\/p>\n Cette dynamique devient critique en pr\u00e9sence de multicollin\u00e9arit\u00e9, situation o\u00f9 les colonnes de la matrice d’exp\u00e9rience pr\u00e9sentent de fortes interd\u00e9pendances lin\u00e9aires. Dans ce r\u00e9gime, la matrice de Gram s’approche de la singularit\u00e9, provoquant une instabilit\u00e9 num\u00e9rique s\u00e9v\u00e8re de l’inversion matricielle standard des moindres carr\u00e9s. Les variances des coefficients estim\u00e9s deviennent alors exorbitantes, conduisant \u00e0 des intervalles de confiance d\u00e9mesur\u00e9ment larges et \u00e0 des inversions erratiques de signes de param\u00e8tres pourtant \u00e9tablis par la litt\u00e9rature. L’\u00e9limination syst\u00e9matique des coefficients redondants restaure le conditionnement de la matrice d’information et garantit la reproductibilit\u00e9 des inf\u00e9rences pr\u00e9dictives.<\/p>\n Dans le domaine des sciences cognitives, de la neuropsychologie et de la psychiatrie computationnelle, l’enjeu de la s\u00e9lection de variables se double d’une responsabilit\u00e9 \u00e9thique et clinique pr\u00e9pond\u00e9rante. Les protocoles exp\u00e9rimentaux contemporains recueillent couramment des centaines d’indicateurs issus de batteries de tests psychom\u00e9triques, de biomarqueurs neurophysiologiques et de questionnaires auto-rapport\u00e9s \u00e9valuant des dimensions latentes complexes telles que l’anxi\u00e9t\u00e9, la m\u00e9moire de travail ou l’inhibition ex\u00e9cutive. Tenter d’expliquer une alt\u00e9ration fonctionnelle ou un profil psychopathologique \u00e0 l’aide d’un mod\u00e8le contenant des dizaines de dimensions corr\u00e9l\u00e9es compromet l’interpr\u00e9tabilit\u00e9 clinique, privant le praticien de leviers d’intervention th\u00e9rapeutiques intelligibles.<\/p>\n L’utilisation de mod\u00e8les parcimonieux permet de dissocier les v\u00e9ritables pr\u00e9dicteurs causaux des corr\u00e9lations fallacieuses (spurious correlations<\/em>). Dans les grandes cohortes d’\u00e9tudes comportementales, des associations statistiques significatives peuvent \u00e9merger sous l’effet de biais de confusion non contr\u00f4l\u00e9s ou d’erreurs de mesure partag\u00e9es propres aux instruments psychom\u00e9triques. En isolant le sous-ensemble minimal de pr\u00e9dicteurs assurant la quasi-totalit\u00e9 du pouvoir pr\u00e9dictif, l’analyste isole les construits psychologiques qui portent la v\u00e9ritable valeur \u00e9tiologique, limitant les interpr\u00e9tations pseudoscientifiques d\u00e9riv\u00e9es de covariations accidentelles propres \u00e0 un \u00e9chantillon sp\u00e9cifique.<\/p>\n Enfin, l’optimisation des architectures pr\u00e9dictives r\u00e9pond \u00e0 un imp\u00e9ratif pragmatique de r\u00e9duction du fardeau d’\u00e9valuation cognitive impos\u00e9 aux participants ou aux patients. Soumettre un individu souffrant de troubles d\u00e9pressifs s\u00e9v\u00e8res ou d’un d\u00e9clin cognitif d\u00e9butant \u00e0 des batteries d’\u00e9valuation exhaustives durant plusieurs heures engendre fatigue, inattention et d\u00e9sengagement, d\u00e9gradant la fid\u00e9lit\u00e9 m\u00eame des mesures recueillies. L’identification, par des d\u00e9marches de type meilleur sous-ensemble, d’une combinaison restreinte de deux ou trois indices cl\u00e9s permettant un diagnostic pr\u00e9dictif de haute pr\u00e9cision autorise la conception de protocoles de d\u00e9pistage rapides, \u00e9thiques et parfaitement calibr\u00e9s pour la pratique hospitali\u00e8re de routine.<\/p>\n La recherche du meilleur sous-ensemble s’\u00e9nonce rigoureusement comme un probl\u00e8me d’optimisation math\u00e9matique combinatoire sous contrainte de parcimonie, formalis\u00e9e par la pseudo-norme L0<\/em> du vecteur des coefficients de r\u00e9gression. Consid\u00e9rons le mod\u00e8le lin\u00e9aire classique Y = X\u03b2 + \u03b5<\/em>, o\u00f9 Y<\/em> est le vecteur de dimension (n \u00d7 1)<\/em> des observations cibles, X<\/em> est la matrice d’exp\u00e9rience de dimension (n \u00d7 p)<\/em>, \u03b2<\/em> est le vecteur (p \u00d7 1)<\/em> des param\u00e8tres r\u00e9els \u00e0 estimer, et \u03b5<\/em> d\u00e9signe le vecteur des erreurs r\u00e9siduelles ind\u00e9pendantes et identiquement distribu\u00e9es. La pseudo-norme ||\u03b2||\u2080<\/em> compte de fa\u00e7on binaire le nombre de composantes non nulles de \u03b2<\/em>, repr\u00e9sentant la cardinalit\u00e9 exacte du sous-ensemble de pr\u00e9dicteurs mobilis\u00e9s.<\/p>\n Le probl\u00e8me canonique du meilleur sous-ensemble pour une taille k<\/em> donn\u00e9e (avec 0 \u2264 k \u2264 p<\/em>) s’\u00e9crit de la mani\u00e8re suivante : minimiser la somme des carr\u00e9s des r\u00e9sidus ||Y – X\u03b2||\u2082\u00b2<\/em> sous la contrainte structurelle ||\u03b2||\u2080 \u2264 k<\/em>. L’espace des mod\u00e8les candidats explore l’ensemble des sous-ensembles de l’ensemble des indices {1, 2, …, p}<\/em>. La collection totale des configurations possibles pour une taille fix\u00e9e k<\/em> correspond au coefficient binomial C(p, k) = p! \/ (k! (p – k)!)<\/em>. Lorsque l’on somme ces combinaisons pour toutes les cardinalit\u00e9s possibles de k = 0<\/em> jusqu’\u00e0 k = p<\/em>, la dimension globale de l’espace de recherche atteint pr\u00e9cis\u00e9ment 2\u1d56<\/em> mod\u00e8les concurrents.<\/p>\n \u00c0 l’origine de cette s\u00e9quence combinatoire tr\u00f4ne le mod\u00e8le nul, traditionnellement d\u00e9sign\u00e9 par M\u2080<\/em>. Ce mod\u00e8le de r\u00e9f\u00e9rence ne comporte aucun pr\u00e9dicteur dans sa matrice d’exp\u00e9rience et se limite \u00e0 l’ajustement d’un terme constant, l’interception, estim\u00e9e par la moyenne empirique de la variable r\u00e9ponse \u0232<\/em>. Pour toute dimension sup\u00e9rieure, chaque sous-ensemble d’indices d\u00e9finit un sous-espace vectoriel lin\u00e9aire propre au sein de l’espace euclidien de dimension n<\/em>, dans lequel la projection orthogonale du vecteur r\u00e9ponse sera minutieusement calcul\u00e9e et \u00e9valu\u00e9e.<\/p>\n La r\u00e9solution op\u00e9ratoire du Best Subset Selection<\/em> proc\u00e8de selon une m\u00e9thodologie rigoureusement scind\u00e9e en deux phases algorithmiques distinctes, conjuguant l’optimisation intra-dimensionnelle locale et l’arbitrage inter-dimensionnel global. Cette s\u00e9paration conceptuelle est fondamentale pour \u00e9viter la contamination entre l’ajustement m\u00e9canique aux donn\u00e9es d’apprentissage et l’\u00e9valuation de la g\u00e9n\u00e9ralisation statistique :<\/p>\n Cette distinction m\u00e9thodologique garantit que la comparaison finale ne souffre pas de l’optimisme trompeur associ\u00e9 \u00e0 l’augmentation m\u00e9canique de la dimensionnalit\u00e9, prot\u00e9geant l’analyste contre l’illusion de performance pr\u00e9dictive au sein du corpus d’apprentissage.<\/p>\n L’optimalit\u00e9 th\u00e9orique conf\u00e9r\u00e9e aux solutions identifi\u00e9es \u00e0 chaque niveau k<\/em> repose int\u00e9gralement sur la validit\u00e9 des postulats classiques du mod\u00e8le de r\u00e9gression lin\u00e9aire gaussien. Ces hypoth\u00e8ses conditionnent la distribution d’\u00e9chantillonnage des estimateurs des moindres carr\u00e9s et la l\u00e9gitimit\u00e9 probabiliste des crit\u00e8res d’arbitrage. En premier lieu, les perturbations r\u00e9siduelles \u03b5\u1d62<\/em> doivent suivre une distribution normale de moyenne nulle et poss\u00e9der une variance conditionnelle constante \u03c3\u00b2<\/em> sur l’ensemble du domaine des pr\u00e9dicteurs, satisfaisant ainsi l’exigence formelle d’homosc\u00e9dasticit\u00e9. Les \u00e9carts substantiels \u00e0 la normalit\u00e9 ou la pr\u00e9sence d’h\u00e9t\u00e9rosc\u00e9dasticit\u00e9 d\u00e9forment la projection g\u00e9om\u00e9trique et compromettent l’estimation non biais\u00e9e de la variance globale.<\/p>\n En second lieu, l’hypoth\u00e8se d’ind\u00e9pendance conditionnelle des observations garantit que la matrice de covariance du terme d’erreur est purement diagonale : Var(\u03b5 | X) = \u03c3\u00b2 I\u2099<\/em>. En cas d’autocorr\u00e9lation temporelle ou de corr\u00e9lation intra-classe (dans les plans factoriels hi\u00e9rarchiques ou longitudinaux), la somme des carr\u00e9s r\u00e9siduels sous-\u00e9value syst\u00e9matiquement l’incertitude r\u00e9elle, ce qui biaise l’identification du sous-ensemble optimal en favorisant artificiellement des combinaisons de covariables sursp\u00e9cifi\u00e9es.<\/p>\n Enfin, la validit\u00e9 computationnelle de l’algorithme exige que pour chaque sous-ensemble \u00e9valu\u00e9 de taille k<\/em>, la matrice sous-jacente des pr\u00e9dicteurs X\u2096<\/em> soit de rang plein colonne, c’est-\u00e0-dire rang(X\u2096) = k<\/em>, avec imp\u00e9rativement la contrainte g\u00e9om\u00e9trique n > k<\/em>. Si cette condition est respect\u00e9e, la matrice de Gram restreinte (X\u2096\u1d40 X\u2096)<\/em> est strictement d\u00e9finie positive, garantissant l’existence et l’unicit\u00e9 de l’estimateur des moindres carr\u00e9s \u03b2\u0302\u2096 = (X\u2096\u1d40 X\u2096)\u207b\u00b9 X\u2096\u1d40 Y<\/em>. La robustesse statistique de cet estimateur au sein des mod\u00e8les restreints d\u00e9coule directement du th\u00e9or\u00e8me de Gauss-Markov, qui affirme que sous ces hypoth\u00e8ses, l’estimateur ainsi construit demeure le meilleur estimateur lin\u00e9aire non biais\u00e9 (BLUE) pour l’espace vectoriel circonscrit.<\/p>\n L’\u00e9l\u00e9gance conceptuelle du Best Subset Selection<\/em> se heurte imm\u00e9diatement \u00e0 une barri\u00e8re computationnelle insurmontable d\u00e8s que la dimension de l’espace des pr\u00e9dicteurs franchit les standards des donn\u00e9es contemporaines. Pour quantifier rigoureusement cette explosion, appliquons le th\u00e9or\u00e8me du bin\u00f4me de Newton \u00e0 la sommation exhaustive de toutes les combinaisons possibles de taille k<\/em> pr\u00e9lev\u00e9es parmi p<\/em> covariables candidates : \u2211\u2096\u208c\u2080\u1d56 C(p, k) = (1 + 1)\u1d56 = 2\u1d56<\/em>. Le cardinal de l’espace de recherche ob\u00e9it ainsi \u00e0 une trajectoire g\u00e9om\u00e9trique exponentielle pure de base deux.<\/p>\n Cette croissance se traduit par une multiplication vertigineuse des inversions matricielles requises. Si pour p = 10<\/em>, l’espace se limite \u00e0 1 024<\/em> mod\u00e8les \u2014 charge de travail triviale r\u00e9solue en quelques millisecondes par n’importe quel processeur contemporain \u2014, pour p = 20<\/em>, le nombre d’ajustements s’\u00e9l\u00e8ve \u00e0 1 048 576<\/em> mod\u00e8les. \u00c0 p = 30<\/em>, le compteur atteint 1 073 741 824<\/em> \u00e9quations matricielles \u00e0 r\u00e9soudre. Pour p = 50<\/em>, le volume d’op\u00e9rations d\u00e9passe 1,12 \u00d7 10\u00b9\u2075<\/em> mod\u00e8les candidats, ce qui n\u00e9cessiterait des mois d’ex\u00e9cution continue sur des architectures de calcul distribu\u00e9 \u00e0 haute performance.<\/p>\n Le point de rupture computationnel pour une station de travail moderne effectuant des inversions via des d\u00e9compositions QR optimis\u00e9es se situe classiquement autour de p = 30<\/em> \u00e0 p = 40<\/em> variables, \u00e0 condition de recourir \u00e0 des impl\u00e9mentations en langage compil\u00e9 (C ou Fortran). Au-del\u00e0 de ce seuil, le temps n\u00e9cessaire pour simplement \u00e9num\u00e9rer les adresses m\u00e9moire des structures d’indices d\u00e9passe la capacit\u00e9 pratique des syst\u00e8mes d’exploitation conventionnels, rendant la recherche exhaustive mat\u00e9riellement inaccessible.<\/p>\n La barri\u00e8re algorithmique du Best Subset Selection<\/em> ne d\u00e9coule pas seulement d’une limitation technologique passag\u00e8re relative \u00e0 la vitesse des microprocesseurs, mais prend racine dans la th\u00e9orie de la complexit\u00e9 computationnelle. Le probl\u00e8me de la r\u00e9gression sous contrainte de parcimonie L0<\/em> a \u00e9t\u00e9 formellement d\u00e9montr\u00e9 comme appartenant \u00e0 la classe des probl\u00e8mes NP-difficiles<\/a> (NP-hard<\/em>), notamment dans les travaux s\u00e9minales de Natarajan (1995). Cette classification implique qu’il n’existe aucun algorithme d\u00e9terministe connu capable d’identifier la solution globale exacte en un temps polynomial par rapport \u00e0 la dimension p<\/em> dans le cas g\u00e9n\u00e9ral.<\/p>\n Cette r\u00e9alit\u00e9 th\u00e9orique a des cons\u00e9quences fondamentales sur l’analyse de donn\u00e9es modernes \u00e0 haute dimension, telles que les matrices de transcriptomique g\u00e9nomique (comportant fr\u00e9quemment p > 20 000<\/em> g\u00e8nes pour quelques centaines d’\u00e9chantillons) ou l’imagerie par r\u00e9sonance magn\u00e9tique fonctionnelle (contenant des centaines de milliers de voxels). Dans ces contextes o\u00f9 la dimensionnalit\u00e9 exc\u00e8de de plusieurs ordres de grandeur la taille de l’\u00e9chantillon (r\u00e9gime p \u226b n<\/em>), l’application du Best Subset Selection<\/em> brut rel\u00e8ve de l’impossibilit\u00e9 physique absolue.<\/p>\n Cette impasse calculatoire constitue la motivation th\u00e9orique directe ayant conduit la communaut\u00e9 statistique \u00e0 concevoir des alternatives op\u00e9rationnelles. Ces derni\u00e8res se scindent en deux familles majeures : d’une part, les algorithmes gloutons \u00e0 complexit\u00e9 polynomiale qui tronquent l’exploration combinatoire par des choix locaux s\u00e9quentiels, et d’autre part, les m\u00e9thodes de p\u00e9nalisation continue convexe, au premier rang desquelles figure le Lasso, qui remplace la contrainte de norme L0<\/em> discontinue par une enveloppe convexe sous forme de norme L1<\/em>.<\/p>\n Afin de repousser les limites de la faisabilit\u00e9 calculatoire sans renoncer \u00e0 l’exactitude de la solution globale, des informaticiens et statisticiens ont d\u00e9velopp\u00e9 des m\u00e9thodes d’optimisation combinatoire avanc\u00e9es, fond\u00e9es sur le paradigme de s\u00e9paration et \u00e9valuation (Branch-and-Bound<\/em>). L’algorithme le plus embl\u00e9matique de cette cat\u00e9gorie demeure sans conteste celui formul\u00e9 par Furnival et Wilson (1974)<\/a>, connu sous le nom de routine Leaps and Bounds<\/em>. Cette approche permet de d\u00e9couvrir le sous-ensemble minimisant la RSS sans avoir \u00e0 ajuster explicitement la totalit\u00e9 des 2\u1d56<\/em> configurations.<\/p>\n Le principe fondamental repose sur l’organisation des sous-ensembles sous la forme d’un arbre d’exploration arborescent et sur une propri\u00e9t\u00e9 g\u00e9om\u00e9trique stricte de la somme des carr\u00e9s des r\u00e9sidus : l’adjonction d’un pr\u00e9dicteur \u00e0 un sous-ensemble existant ne peut en aucun cas accro\u00eetre sa RSS. Par cons\u00e9quent, la RSS d’un sous-ensemble parent constitue une borne inf\u00e9rieure infranchissable pour l’ensemble des sous-mod\u00e8les d\u00e9riv\u00e9s par expansion de ce n\u0153ud. Si, au cours de la descente de l’arbre, la RSS d’un n\u0153ud interm\u00e9diaire s’av\u00e8re d\u00e9j\u00e0 sup\u00e9rieure \u00e0 la meilleure RSS identifi\u00e9e pour un mod\u00e8le de taille k<\/em> pr\u00e9alablement visit\u00e9, il devient inutile d’explorer les branches filles. La coupure (ou \u00e9lagage) de ce sous-arbre entier permet d’\u00e9conomiser l’\u00e9valuation de millions de combinaisons superflues.<\/p>\n L’efficacit\u00e9 de cette strat\u00e9gie est magnifi\u00e9e par la vectorisation des op\u00e9rations sur les matrices de covariances et l’usage de balayages d’\u00e9limination de Gauss-Jordan (op\u00e9rations de sweep<\/em>). N\u00e9anmoins, cette optimisation rencontre des limites empiriques s\u00e9v\u00e8res en pr\u00e9sence de pr\u00e9dicteurs fortement collin\u00e9aires. Dans une telle configuration, la d\u00e9croissance de la RSS d’un niveau \u00e0 l’autre devient erratique et marginale, emp\u00eachant l’algorithme d’activer pr\u00e9cocement ses crit\u00e8res d’\u00e9lagage. L’arborescence doit alors \u00eatre visit\u00e9e dans sa quasi-totalit\u00e9, ramenant le co\u00fbt de calcul \u00e0 sa borne exponentielle originelle.<\/p>\n Au sein d’une dimensionnalit\u00e9 k<\/em> strictement pr\u00e9d\u00e9termin\u00e9e, le crit\u00e8re universel permettant d’ordonner les C(p, k)<\/em> mod\u00e8les candidats et d’extraire le champion local M\u2096<\/em> est la somme des carr\u00e9s des r\u00e9sidus (Residual Sum of Squares<\/em> ou RSS). Analytiquement, si l’on note y<\/em> le vecteur des observations r\u00e9elles et \u0177 = X\u2096 \u03b2\u0302\u2096<\/em> le vecteur des pr\u00e9dictions g\u00e9n\u00e9r\u00e9es par la sous-matrice X\u2096<\/em>, le r\u00e9sidu d’ajustement est d\u00e9fini par le vecteur d’erreur e = y – \u0177<\/em>. La RSS correspond \u00e0 la norme euclidienne au carr\u00e9 de ce vecteur d’\u00e9carts : RSS = e\u1d40 e = \u2211\u1d62\u208c\u2081\u207f (y\u1d62 – \u0177\u1d62)\u00b2<\/em>.<\/p>\n Sur le plan g\u00e9om\u00e9trique, l’ajustement par les moindres carr\u00e9s \u00e9quivaut rigoureusement \u00e0 projeter orthogonalement le vecteur de donn\u00e9es y<\/em> sur le sous-espace vectoriel de dimension k<\/em> engendr\u00e9 par les colonnes de X\u2096<\/em>. L’op\u00e9rateur de projection orthogonale, commun\u00e9ment qualifi\u00e9 de matrice chapeau (hat matrix<\/em>), s’exprime par la relation matricielle H\u2096 = X\u2096(X\u2096\u1d40 X\u2096)\u207b\u00b9 X\u2096\u1d40<\/em>. Le r\u00e9sidu s’\u00e9crit alors e = (I\u2099 – H\u2096) y<\/em>, o\u00f9 (I\u2099 – H\u2096)<\/em> est le projecteur orthogonal sur l’espace orthogonal \u00e0 l’image de X\u2096<\/em>. La minimisation de la RSS consiste g\u00e9om\u00e9triquement \u00e0 trouver la distance minimale entre le vecteur r\u00e9ponse et le sous-espace consid\u00e9r\u00e9.<\/p>\n Une propri\u00e9t\u00e9 fondamentale r\u00e9git l’\u00e9volution de la RSS : la monotonie d\u00e9croissante par rapport \u00e0 l’inclusion de variables. Tout agrandissement d’un sous-espace vectoriel englobe n\u00e9cessairement l’espace pr\u00e9c\u00e9dent, garantissant que la distance r\u00e9siduelle ne peut qu’\u00eatre r\u00e9duite ou, au pire, demeurer strictement identique. De cette propri\u00e9t\u00e9 d\u00e9coule une cons\u00e9quence capitale : la RSS brute constitue un crit\u00e8re absolu d’arbitrage intra-dimensionnel<\/strong> (pour comparer des mod\u00e8les partageant une m\u00eame taille k<\/em>), mais s’av\u00e8re intrins\u00e8quement incapable d’op\u00e9rer un arbitrage inter-dimensionnel<\/strong> loyal entre mod\u00e8les de dimensions distinctes, favorisant invariablement le mod\u00e8le surparam\u00e9tr\u00e9 complet M\u209a<\/em>.<\/p>\n Directement corr\u00e9l\u00e9 \u00e0 la somme des carr\u00e9s r\u00e9siduels, le coefficient de d\u00e9termination empirique, universellement d\u00e9sign\u00e9 par R\u00b2<\/em>, repr\u00e9sente la proportion de la variance totale de la variable cible expliqu\u00e9e par le mod\u00e8le de r\u00e9gression. Sa formulation alg\u00e9brique s’appuie sur la d\u00e9composition de la somme totale des carr\u00e9s corrig\u00e9e de la moyenne (Total Sum of Squares<\/em> ou TSS) en une composante expliqu\u00e9e par la r\u00e9gression (Explained Sum of Squares<\/em> ou ESS) et la composante r\u00e9siduelle : TSS = ESS + RSS<\/em>, avec TSS = \u2211\u1d62\u208c\u2081\u207f (y\u1d62 – \u0232)\u00b2<\/em>. Le coefficient se formalise alors par le ratio : R\u00b2 = 1 – (RSS \/ TSS)<\/em>.<\/p>\n Dans l’espace euclidien centr\u00e9 des observations, le R\u00b2<\/em> poss\u00e8de une interpr\u00e9tation trigonom\u00e9trique \u00e9l\u00e9gante : il correspond exactement au carr\u00e9 du cosinus de l’angle g\u00e9om\u00e9trique form\u00e9 entre le vecteur centr\u00e9 de la r\u00e9ponse empirique (y – \u0232)<\/em> et le vecteur des pr\u00e9dictions ajust\u00e9es (\u0177 – \u0232)<\/em>. Un R\u00b2<\/em> tendant vers l’unit\u00e9 traduit un alignement vectoriel quasi-parfait, signifiant que la surface de r\u00e9gression capture fid\u00e8lement la variabilit\u00e9 spatiale des points exp\u00e9rimentaux.<\/p>\n Cependant, l’utilisation na\u00efve du R\u00b2<\/em> comme boussole de s\u00e9lection de mod\u00e8les constitue l’un des pi\u00e8ges les plus document\u00e9s de l’inf\u00e9rence statistique. Puisque la TSS est une constante invariante d\u00e9termin\u00e9e exclusivement par la distribution brute de la cible y<\/em>, et que la RSS d\u00e9cro\u00eet m\u00e9caniquement \u00e0 chaque introduction de variable suppl\u00e9mentaire, le R\u00b2<\/em> augmente de mani\u00e8re in\u00e9luctable avec la dimension k<\/em>. L’adjonction d’une variable g\u00e9n\u00e9r\u00e9e par un processus de bruit blanc gaussien sans aucun lien causal avec le ph\u00e9nom\u00e8ne \u00e9l\u00e8vera syst\u00e9matiquement le R\u00b2<\/em> de l’\u00e9chantillon d’apprentissage, cr\u00e9ant une illusion math\u00e9matique d’am\u00e9lioration pr\u00e9dictive qui masque une d\u00e9gradation s\u00e9v\u00e8re des capacit\u00e9s de g\u00e9n\u00e9ralisation du syst\u00e8me.<\/p>\n Lorsque le statisticien restreint d\u00e9lib\u00e9r\u00e9ment l’ajustement \u00e0 un sous-ensemble k<\/em> de pr\u00e9dicteurs issus de la matrice globale, l’estimateur restreint obtenu \u03b2\u0302\u2096<\/em> h\u00e9rite de propri\u00e9t\u00e9s math\u00e9matiques rigoureusement d\u00e9crites par le formalisme de Gauss-Markov. Si le v\u00e9ritable processus g\u00e9n\u00e9rateur de donn\u00e9es ne mobilise effectivement que ce sous-ensemble de variables, l’estimateur des moindres carr\u00e9s restreint est sans biais, c’est-\u00e0-dire E[\u03b2\u0302\u2096] = \u03b2\u2096<\/em>, et sa matrice de variance-covariance s’\u00e9tablit \u00e0 Var(\u03b2\u0302\u2096) = \u03c3\u00b2 (X\u2096\u1d40 X\u2096)\u207b\u00b9<\/em>. L’esp\u00e9rance de cette matrice est \u00e9troitement li\u00e9e au spectre des valeurs propres de la matrice d’information de Fisher restreinte X\u2096\u1d40 X\u2096<\/em>.<\/p>\n Le conditionnement de cette matrice joue un r\u00f4le d\u00e9terminant dans la pr\u00e9cision des estimations. En \u00e9liminant les pr\u00e9dicteurs redondants ou quasi-collin\u00e9aires du jeu global, l’inversion matricielle restreinte devient nettement mieux conditionn\u00e9e : le ratio entre la plus grande et la plus petite valeur propre se stabilise, \u00e9vitant l’amplification artificielle des erreurs de calcul et stabilisant l’estimation des erreurs-types des coefficients r\u00e9siduels.<\/p>\n Il est toutefois imp\u00e9ratif d’analyser le comportement de \u03b2\u0302\u2096<\/em> dans l’\u00e9ventualit\u00e9 o\u00f9 des pr\u00e9dicteurs v\u00e9ritablement informatifs auraient \u00e9t\u00e9 exclus de la s\u00e9lection, ph\u00e9nom\u00e8ne connu sous le nom d’effet de masquage ou de biais de variable omise. Si la matrice des variables omises X\u2092<\/em> pr\u00e9sente une covariance non nulle avec les variables retenues X\u2096<\/em>, l’esp\u00e9rance de l’estimateur restreint devient : E[\u03b2\u0302\u2096] = \u03b2\u2096 + (X\u2096\u1d40 X\u2096)\u207b\u00b9 X\u2096\u1d40 X\u2092 \u03b2\u2092<\/em>. Les coefficients des variables retenues absorbent alors m\u00e9caniquement l’effet marginal des variables manquantes, entra\u00eenant un biais structurel non r\u00e9ductible qui alt\u00e8re l’interpr\u00e9tation causale des estimateurs au profit exclusif de leur capacit\u00e9 d’approximation descriptive locale.<\/p>\n Pour d\u00e9passer l’incapacit\u00e9 structurelle de la RSS \u00e0 arbitrer entre des mod\u00e8les de complexit\u00e9s distinctes, la th\u00e9orie de l’information appliqu\u00e9e \u00e0 la statistique propose des m\u00e9triques d’\u00e9valuation p\u00e9nalis\u00e9e. Parmi elles, le Crit\u00e8re d’Information d’Akaike<\/a> (AIC), introduit par Hirotugu Akaike en 1974, repose sur une fondation \u00e9pist\u00e9mologique particuli\u00e8rement f\u00e9conde : la minimisation de la divergence relative de Kullback-Leibler entre le processus g\u00e9n\u00e9rateur de donn\u00e9es v\u00e9ritable (g\u00e9n\u00e9ralement inaccessible) et le mod\u00e8le probabiliste propos\u00e9.<\/p>\n Dans le cadre de la mod\u00e9lisation lin\u00e9aire sous hypoth\u00e8se de perturbations gaussiennes ind\u00e9pendantes et homosc\u00e9dastiques, l’expression g\u00e9n\u00e9rale de l’AIC, formul\u00e9e \u00e0 partir de la fonction de log-vraisemblance maximale ln(L)<\/em>, prend la forme analytique suivante : AIC = -2 ln(L) + 2k*<\/em>, o\u00f9 k*<\/em> repr\u00e9sente le nombre total de param\u00e8tres libres estim\u00e9s par le mod\u00e8le (incluant les k<\/em> coefficients de r\u00e9gression, le terme d’interception et l’estimateur de la variance r\u00e9siduelle \u03c3\u00b2<\/em>, soit k* = k + 2<\/em>). En exprimant la log-vraisemblance en fonction de la somme des carr\u00e9s r\u00e9siduels, la formule devient : AIC = n ln(RSS \/ n) + 2k + C<\/em>, o\u00f9 C<\/em> est une constante d’\u00e9chelle additive ind\u00e9pendante des mod\u00e8les en comp\u00e9tition.<\/p>\n L’AIC poss\u00e8de la propri\u00e9t\u00e9 th\u00e9orique d’efficacit\u00e9 asymptotique : lorsque la taille de l’\u00e9chantillon tend vers l’infini, l’AIC s\u00e9lectionne le mod\u00e8le dont l’erreur quadratique moyenne de pr\u00e9diction hors \u00e9chantillon est minimale, en supposant que le mod\u00e8le v\u00e9ritable ne figure pas strictement dans l’ensemble candidat ou soit de dimension infinie. Cependant, en contexte d’\u00e9chantillons finis, le terme de p\u00e9nalit\u00e9 lin\u00e9aire 2k<\/em> s’av\u00e8re relativement mod\u00e9r\u00e9, induisant une tendance document\u00e9e \u00e0 la surs\u00e9lection (overfitting<\/em>), ce qui conduit fr\u00e9quemment l’algorithme \u00e0 retenir des pr\u00e9dicteurs superficiels apportant des gains r\u00e9siduels marginaux.<\/p>\n Formul\u00e9 par Gideon Schwarz en 1978, le Crit\u00e8re d’Information Bay\u00e9sien (Bayesian Information Criterion<\/em> ou BIC), \u00e9galement d\u00e9sign\u00e9 sous le nom de crit\u00e8re de Schwarz, adopte une posture m\u00e9thodologique radicalement diff\u00e9rente, enracin\u00e9e dans le paradigme probabiliste de l’inf\u00e9rence bay\u00e9sienne. L’objectif math\u00e9matique du BIC est de maximiser la probabilit\u00e9 a posteriori conditionnelle qu’un mod\u00e8le candidat soit le mod\u00e8le rigoureusement \u00ab vrai \u00bb, sous l’hypoth\u00e8se d’une distribution a priori non informative uniforme sur l’ensemble de l’espace des mod\u00e8les concurrents.<\/p>\n L’\u00e9quation canonique du BIC s’\u00e9nonce selon une structure formellement analogue \u00e0 celle de l’AIC, mais introduit une pond\u00e9ration de p\u00e9nalit\u00e9 d\u00e9pendante de la volum\u00e9trie de l’\u00e9chantillon d’apprentissage : BIC = -2 ln(L) + k ln(n)<\/em>, ce qui, sous l’approximation par la r\u00e9gression lin\u00e9aire aux moindres carr\u00e9s ordinaires, s’exprime par : BIC = n ln(RSS \/ n) + k ln(n)<\/em>. Le multiplicateur de complexit\u00e9 passe ainsi de la constante 2<\/em> dans l’AIC au logarithme naturel de la taille de l’\u00e9chantillon ln(n)<\/em> dans le BIC.<\/p>\n D\u00e8s lors que n \u2265 8<\/em>, la valeur de ln(n)<\/em> surpasse strictement la p\u00e9nalit\u00e9 de 2<\/em> impos\u00e9e par l’AIC (par exemple, pour n = 1 000<\/em>, ln(1 000) \u2248 6,91<\/em>). Le BIC inflige par cons\u00e9quent un co\u00fbt computationnel bien plus s\u00e9v\u00e8re \u00e0 chaque param\u00e8tre additionnel. Cette s\u00e9v\u00e9rit\u00e9 accrue lui conf\u00e8re une propri\u00e9t\u00e9 asymptotique fondamentale : la consistance forte<\/strong>. Si le mod\u00e8le g\u00e9n\u00e9rateur r\u00e9el se trouve inclus dans la famille des sous-ensembles candidats, la probabilit\u00e9 que le BIC s\u00e9lectionne ce mod\u00e8le exact converge vers 1 lorsque n<\/em> tend vers l’infini. En pratique clinique et appliqu\u00e9e, le BIC est syst\u00e9matiquement pr\u00e9f\u00e9r\u00e9 lorsque l’interpr\u00e9tabilit\u00e9 et l’\u00e9limination des faux positifs priment sur la sensibilit\u00e9 pr\u00e9dictive pure.<\/p>\n1. Introduction conceptuelle \u00e0 la s\u00e9lection de variables et au principe de parcimonie<\/h2>\n
1.1 Le r\u00f4le fondamental de la s\u00e9lection d’attributs en mod\u00e9lisation statistique<\/h3>\n
1.2 Le compromis biais-variance face \u00e0 la dimensionnalit\u00e9<\/h3>\n
1.3 Importance de la parcimonie en sciences cognitives et comportementales<\/h3>\n
2. Fondements math\u00e9matiques et algorithmiques du Best Subset Selection<\/h2>\n
2.1 Formulation formelle de l’espace des mod\u00e8les candidats<\/h3>\n
2.2 Le protocole s\u00e9quentiel d’optimisation en deux \u00e9tapes<\/h3>\n
\n
2.3 Hypoth\u00e8ses sous-jacentes du mod\u00e8le lin\u00e9aire classique<\/h3>\n
3. Complexit\u00e9 combinatoire et limites de calculabilit\u00e9<\/h2>\n
3.1 D\u00e9monstration du comportement exponentiel 2 puissance p<\/h3>\n
3.2 La classification NP-difficile de l’optimisation globale<\/h3>\n
3.3 Strat\u00e9gies d’\u00e9lagage d’arbre et branch-and-bound<\/h3>\n
4. Crit\u00e8res d’\u00e9valuation au sein d’une dimension fix\u00e9e<\/h2>\n
4.1 La somme des carr\u00e9s r\u00e9siduels (RSS)<\/h3>\n
4.2 Le coefficient de d\u00e9termination empirique R-deux<\/h3>\n
4.3 Propri\u00e9t\u00e9s statistiques de l’estimateur des moindres carr\u00e9s restreint<\/h3>\n
5. Crit\u00e8res de s\u00e9lection globale p\u00e9nalis\u00e9e pour arbitrer entre tailles de mod\u00e8les<\/h2>\n
5.1 Le crit\u00e8re d’information d’Akaike (AIC)<\/h3>\n
5.2 Le crit\u00e8re d’information bay\u00e9sien (BIC \/ SC)<\/h3>\n
5.3 Le Cp de Mallows et ses relations structurelles<\/h3>\n