Régression logistique par morceaux, arbres de décision

Ce qui suit explore une façon fantaisiste de construire des régressions logistiques à mi-chemin entre les arbres de décisions et les réseaux de neurones. Dans un premier temps, on s’intéresse uniquement à une classification binaire.

Parallèle entre un neurone et une régression logistique

Les paragraphes Classification et La classification présente le problème de la classification qui consiste à trouver une fonction f qui maximise la vraisemblance du nuage de points (X_i, y_i)_iX_i \in \R^d et y_i \in \acc{0, 1}.

\ln L(\Theta, X, y) = \sum_{i=1}^n y_i \ln f(\Theta, X_i) + (1-y_i) \ln (1-f(\Theta, X_i))

Dans le cas de la régression logistique, la fonction f est définie comme suit :

f(\Theta, X_i) = \frac{1}{1 + e^{-\sum_{k=1}^d \theta_k x_{ik}}}

Cela ressemble beaucoup à la définition d’un neurone où la fonction d’activation f(x) = \frac{1}{1 + e^{-x}} est une fonction sigmoïde.

Principe d’un arbre de décision

Un arbre de décision se construit peu à peu en répétant toujours la même optimisation sur des sous-ensemble de plus en plus petit. Il faut d’abord un critère qui permette d’évaluer la pertinence de la division effectuée par un noeud de l’arbre. Pour un ensemble (X_i, y_i)_{1 \infegal i \infegal n}, on peut estimer la probabilité p(y_1, ..., y_n) = p(Y) = \frac{1}{n}\sum{i=1}^n y_i. Le critère de Gini G qui évalue la pertinence d’une classification est défini par G(Y) = p(Y) (1 - p(Y)). Un autre critère est le gain d’information ou entropie H : H(Y) = - p(Y) \ln p(Y) - (1-p(Y)) \ln (1 - p(Y)).

On note Y_S l’ensemble des \acc{y_i | i \in S}S est un sous-ensemble. S^C est noté le complémentaire.

Pour le premier noeud de l’arbre de décision, on calcule pour toutes les variables et toutes les observations la diminution du critère choisi :

\begin{array}{rcl}
S_{ik} &=& \acc{ m | x_{mk} \infegal x_{ik}} \\
\Delta_{ik} &=& H(Y) - ( H(Y_{S_{ik}}) + H(Y_{S_{ik}^C} )
\end{array}

On choisit alors la variable k et le seuil x_{ik} qui maximise le gain. Dans le cas d’une régression logistique, la vraisemblance correspond à :

\ln L(\Theta, X, y) = \sum_{i=1}^n y_i \ln f(\Theta, X_i) + (1-y_i) \ln (1-f(\Theta, X_i))

Si on suppose que la fonction f retourne une constante c, cette expression devient :

\ln L(\Theta, X, y) = \sum_{i=1}^n y_i \ln c + (1-y_i) \ln (1-c) = p(Y) \ln c + (1-p(Y)) \ln (1-c)

Or cette expression admet un maximum pour c=p(Y) puisque la dérivée s’annule de façon évidente pour cette valeur :

\frac{\partial \ln L(\Theta, X, y)}{\partial c} = \frac{p(Y)}{c} - \frac{1-p(Y)}{1-c}

On remarque que l’optimisation d’un noeud d’un arbre de décision correspond à l’optimisation de la vraisemblance par une fonction constante. Une régression logistique calculée sur une seule variable est en quelque sorte une généralisation de ce modèle. On apprend un arbre de décision qu’on exporte au format dot.

<<<

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier, export_graphviz
ds = load_iris()
X, y = ds.data, ds.target
y = y % 2
dt = DecisionTreeClassifier(max_depth=3, criterion='entropy')
dt.fit(X, y)
print(dt)
# export_graphviz(dt)

>>>

    DecisionTreeClassifier(criterion='entropy', max_depth=3)

Ce qui donne :

digraph Tree { node [shape=box] ; 0 [label="X[3] <= 0.8\nentropy = 0.918\nsamples = 150\nvalue = [100, 50]"] ; 1 [label="entropy = 0.0\nsamples = 50\nvalue = [50, 0]"] ; 0 -> 1 [labeldistance=2.5, labelangle=45, headlabel="True"] ; 2 [label="X[3] <= 1.75\nentropy = 1.0\nsamples = 100\nvalue = [50, 50]"] ; 0 -> 2 [labeldistance=2.5, labelangle=-45, headlabel="False"] ; 3 [label="X[2] <= 4.95\nentropy = 0.445\nsamples = 54\nvalue = [5, 49]"] ; 2 -> 3 ; 4 [label="entropy = 0.146\nsamples = 48\nvalue = [1, 47]"] ; 3 -> 4 ; 5 [label="entropy = 0.918\nsamples = 6\nvalue = [4, 2]"] ; 3 -> 5 ; 6 [label="X[2] <= 4.85\nentropy = 0.151\nsamples = 46\nvalue = [45, 1]"] ; 2 -> 6 ; 7 [label="entropy = 0.918\nsamples = 3\nvalue = [2, 1]"] ; 6 -> 7 ; 8 [label="entropy = 0.0\nsamples = 43\nvalue = [43, 0]"] ; 6 -> 8 ; }

Construction d’un pseudo arbre

Et si on remplaçait chaque noeud par une régression logistique appris sur les exemples passant par ce noeud… Plutôt que de prendre une décision basée sur une variable donnée et de retourner une probabilité constante, on estime une régression logistique et on retourne la probabilité retournée par la régression.

S’il n’y a théoriquement aucun obstacle, en pratique, certains cas posent quelques problèmes comme le montre l’exemple Arbre d’indécision et repris ci-dessous. La fonction criteria calcule les différents gains selon les points de coupure.

import matplotlib.pyplot as plt
from mlstatpy.ml.logreg import criteria, random_set_1d, plot_ds

X1, y1 = random_set_1d(1000, 2)
X2, y2 = random_set_1d(1000, 3)
X3, y3 = random_set_1d(1000, 4)
df1 = criteria(X1, y1)
df2 = criteria(X2, y2)
df3 = criteria(X3, y3)

fig, ax = plt.subplots(1, 3, figsize=(14, 5), sharey=True)
plot_ds(X1, y1, ax=ax[0], title="easy")
plot_ds(X2, y2, ax=ax[1], title="difficult")
plot_ds(X3, y3, ax=ax[2], title="more difficult")
df1.plot(x='X', y=['Gini', 'Gain', 'p1', 'p2'], ax=ax[0], lw=5.)
df2.plot(x='X', y=['Gini', 'Gain', 'p1', 'p2'], ax=ax[1], lw=5.)
df3.plot(x='X', y=['Gini', 'Gain', 'p1', 'p2'], ax=ax[2], lw=5.)
plt.show()

(png, hires.png, pdf)

../_images/lr_trees-1.png

Le seuil de coupure est évident dans le premier cas et quasiment impossible à trouver de façon numérique dans le second avec les algorithmes tels qu’ils sont implémentés. Les arbres de décision contournent ce problème en imposant que le seuil de coupure laisse au moins quelques exemples de chaque côté ce que la régression logistique ne fait pas. On peut réflechir à d’autres critères. Le suivant explore la log-vraisemblance.

import matplotlib.pyplot as plt
from mlstatpy.ml.logreg import criteria2, random_set_1d, plot_ds

X1, y1 = random_set_1d(1000, 2)
X2, y2 = random_set_1d(1000, 3)
X3, y3 = random_set_1d(1000, 4)
df1 = criteria2(X1, y1)
df2 = criteria2(X2, y2)
df3 = criteria2(X3, y3)
print(df3)

fig, ax = plt.subplots(1, 3, figsize=(14, 5), sharey=True)
plot_ds(X1, y1, ax=ax[0], title="easy")
plot_ds(X2, y2, ax=ax[1], title="difficult")
plot_ds(X3, y3, ax=ax[2], title="more difficult")
df1.plot(x='X', y=['LL', 'LL-10', 'LL-100'], ax=ax[0], lw=5.)
df2.plot(x='X', y=['LL', 'LL-10', 'LL-100'], ax=ax[1], lw=5.)
df3.plot(x='X', y=['LL', 'LL-10', 'LL-100'], ax=ax[2], lw=5.)
plt.show()

(png, hires.png, pdf)

../_images/lr_trees-2.png

La log-vraisemblance dans ce problème à une dimension est assez simple à écrire. Pour avoir une expression qui ne change pas en invertissant les classes, on considère le maxiimum des vraisemblance en considérant deux classifieurs opposés. Le graphe précédent fait varier x_0 avec différents \theta.

System Message: WARNING/2 (LL(x_0, \theta) = \max \left\{ \begin{array}{ll} \frac{1}{1 + \exp((x-x_0) / \theta)} \\ \frac{1}{1+\exp(- (x-x_0) / \theta)} \end{array}\right)

latex exited with error [stdout] This is pdfTeX, Version 3.14159265-2.6-1.40.21 (TeX Live 2020/Debian) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2020-02-02> patch level 5 L3 programming layer <2020-07-17> (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2019/12/20 v1.4l Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsmath.sty For additional information on amsmath, use the `?' option. (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amstext.sty (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsgen.sty)) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsbsy.sty) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsopn.sty)) (/usr/share/texlive/texmf-dist/tex/latex/amscls/amsthm.sty) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amssymb.sty (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amsfonts.sty)) (/usr/share/texlive/texmf-dist/tex/latex/anyfontsize/anyfontsize.sty) (/usr/share/texlive/texmf-dist/tex/latex/tools/bm.sty) (/usr/share/texlive/texmf-dist/tex/latex/etex-pkg/etex.sty) (/usr/share/texlive/texmf-dist/tex/latex/base/fixltx2e.sty Package fixltx2e Warning: fixltx2e is not required with releases after 2015 (fixltx2e) All fixes are now in the LaTeX kernel. (fixltx2e) See the latexrelease package for details. ) (/usr/share/texlive/texmf-dist/tex/latex/cmap/cmap.sty Package cmap Warning: pdftex in DVI mode - exiting. ) (/usr/share/texlive/texmf-dist/tex/latex/fast-diagram/fast-diagram.sty (/usr/share/texlive/texmf-dist/tex/latex/pgf/frontendlayer/tikz.sty (/usr/share/texlive/texmf-dist/tex/latex/pgf/basiclayer/pgf.sty (/usr/share/texlive/texmf-dist/tex/latex/pgf/utilities/pgfrcs.sty (/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgfutil-common.tex (/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgfutil-common-lists.t ex)) (/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgfutil-latex.def (/usr/share/texlive/texmf-dist/tex/latex/ms/everyshi.sty)) (/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgfrcs.code.tex (/usr/share/texlive/texmf-dist/tex/generic/pgf/pgf.revision.tex))) (/usr/share/texlive/texmf-dist/tex/latex/pgf/basiclayer/pgfcore.sty (/usr/share/texlive/texmf-dist/tex/latex/graphics/graphicx.sty (/usr/share/texlive/texmf-dist/tex/latex/graphics/keyval.sty) (/usr/share/texlive/texmf-dist/tex/latex/graphics/graphics.sty (/usr/share/texlive/texmf-dist/tex/latex/graphics/trig.sty) (/usr/share/texlive/texmf-dist/tex/latex/graphics-cfg/graphics.cfg) (/usr/share/texlive/texmf-dist/tex/latex/graphics-def/dvips.def))) (/usr/share/texlive/texmf-dist/tex/latex/pgf/systemlayer/pgfsys.sty (/usr/share/texlive/texmf-dist/tex/generic/pgf/systemlayer/pgfsys.code.tex (/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgfkeys.code.tex (/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgfkeysfiltered.code.t ex)) (/usr/share/texlive/texmf-dist/tex/generic/pgf/systemlayer/pgf.cfg) (/usr/share/texlive/texmf-dist/tex/generic/pgf/systemlayer/pgfsys-dvips.def (/usr/share/texlive/texmf-dist/tex/generic/pgf/systemlayer/pgfsys-common-postsc ript.def))) (/usr/share/texlive/texmf-dist/tex/generic/pgf/systemlayer/pgfsyssoftpath.code. tex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/systemlayer/pgfsysprotocol.code. tex)) (/usr/share/texlive/texmf-dist/tex/latex/xcolor/xcolor.sty (/usr/share/texlive/texmf-dist/tex/latex/graphics-cfg/color.cfg)) (/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcore.code.tex (/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmath.code.tex (/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathcalc.code.tex (/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathutil.code.tex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathparser.code.tex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.code.tex (/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.basic.code .tex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.trigonomet ric.code.tex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.random.cod e.tex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.comparison .code.tex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.base.code. tex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.round.code .tex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.misc.code. tex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.integerari thmetics.code.tex))) (/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfloat.code.tex)) (/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfint.code.tex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepoints.code.te x) (/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepathconstruct. code.tex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepathusage.code .tex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorescopes.code.te x) (/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcoregraphicstate.c ode.tex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcoretransformation s.code.tex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorequick.code.tex ) (/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreobjects.code.t ex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepathprocessing .code.tex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorearrows.code.te x) (/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreshade.code.tex ) (/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreimage.code.tex (/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreexternal.code. tex)) (/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorelayers.code.te x) (/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcoretransparency.c ode.tex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepatterns.code. tex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorerdf.code.tex)) ) (/usr/share/texlive/texmf-dist/tex/generic/pgf/modules/pgfmoduleshapes.code.tex ) (/usr/share/texlive/texmf-dist/tex/generic/pgf/modules/pgfmoduleplot.code.tex ) (/usr/share/texlive/texmf-dist/tex/latex/pgf/compatibility/pgfcomp-version-0-65 .sty) (/usr/share/texlive/texmf-dist/tex/latex/pgf/compatibility/pgfcomp-version-1-18 .sty)) (/usr/share/texlive/texmf-dist/tex/latex/pgf/utilities/pgffor.sty (/usr/share/texlive/texmf-dist/tex/latex/pgf/utilities/pgfkeys.sty (/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgfkeys.code.tex)) (/usr/share/texlive/texmf-dist/tex/latex/pgf/math/pgfmath.sty (/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmath.code.tex)) (/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgffor.code.tex (/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmath.code.tex))) (/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/tikz.code.tex (/usr/share/texlive/texmf-dist/tex/generic/pgf/libraries/pgflibraryplothandlers .code.tex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/modules/pgfmodulematrix.code.tex ) (/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/libraries/tik zlibrarytopaths.code.tex))) (/usr/share/texlive/texmf-dist/tex/latex/base/ifthen.sty) (/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/libraries/tik zlibrarycalc.code.tex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/libraries/tik zlibraryfit.code.tex) (/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/libraries/tik zlibraryshapes.code.tex (/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/libraries/tik zlibraryshapes.geometric.code.tex (/usr/share/texlive/texmf-dist/tex/generic/pgf/libraries/shapes/pgflibraryshape s.geometric.code.tex)) (/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/libraries/tik zlibraryshapes.misc.code.tex (/usr/share/texlive/texmf-dist/tex/generic/pgf/libraries/shapes/pgflibraryshape s.misc.code.tex)) (/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/libraries/tik zlibraryshapes.symbols.code.tex (/usr/share/texlive/texmf-dist/tex/generic/pgf/libraries/shapes/pgflibraryshape s.symbols.code.tex)) (/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/libraries/tik zlibraryshapes.arrows.code.tex (/usr/share/texlive/texmf-dist/tex/generic/pgf/libraries/shapes/pgflibraryshape s.arrows.code.tex)) (/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/libraries/tik zlibraryshapes.callouts.code.tex (/usr/share/texlive/texmf-dist/tex/generic/pgf/libraries/shapes/pgflibraryshape s.callouts.code.tex)) (/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/libraries/tik zlibraryshapes.multipart.code.tex (/usr/share/texlive/texmf-dist/tex/generic/pgf/libraries/shapes/pgflibraryshape s.multipart.code.tex))) (/usr/share/texlive/texmf-dist/tex/latex/relsize/relsize.sty) (/usr/share/texlive/texmf-dist/tex/latex/xargs/xargs.sty (/usr/share/texlive/texmf-dist/tex/latex/xkeyval/xkeyval.sty (/usr/share/texlive/texmf-dist/tex/generic/xkeyval/xkeyval.tex (/usr/share/texlive/texmf-dist/tex/generic/xkeyval/xkvutils.tex))))) (/usr/share/texlive/texmf-dist/tex/latex/titlesec/titlesec.sty) (/usr/share/texlive/texmf-dist/tex/latex/eepic/epic.sty Enhancements to Picture Environment. Version 1.2 - Released June 1, 1986 ) (/usr/share/texlive/texmf-dist/tex/latex/eepic/eepic.sty Extension to Epic and LaTeX. Version 1.1e - Released Dec 21, 1999 ) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xy.sty (/usr/share/texlive/texmf-dist/tex/generic/xypic/xy.tex Bootstrap'ing: catcodes, docmode, (/usr/share/texlive/texmf-dist/tex/generic/xypic/xyrecat.tex ) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xyidioms.tex) Xy-pic version 3.8.9 <2013/10/06> Copyright (c) 1991-2013 by Kristoffer H. Rose <krisrose@tug.org> and others Xy-pic is free software: see the User's Guide for details. Loading kernel: messages; fonts; allocations: state, direction, utility macros; pictures: \xy, positions, objects, decorations; kernel objects: directionals, circles, text; options; algorithms: directions, edges, connections; Xy-pic loaded) (/usr/share/texlive/texmf-dist/tex/generic/iftex/ifpdf.sty (/usr/share/texlive/texmf-dist/tex/generic/iftex/iftex.sty)) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xyall.tex Xy-pic option: All features v.3.8 (/usr/share/texlive/texmf-dist/tex/generic/xypic/xycurve.tex Xy-pic option: Curve and Spline extension v.3.12 curve, circles, loaded) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xyframe.tex Xy-pic option: Frame and Bracket extension v.3.14 loaded) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xycmtip.tex Xy-pic option: Computer Modern tip extension v.3.7 (/usr/share/texlive/texmf-dist/tex/generic/xypic/xytips.tex Xy-pic option: More Tips extension v.3.11 loaded) loaded) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xyline.tex Xy-pic option: Line styles extension v.3.10 loaded) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xyrotate.tex Xy-pic option: Rotate and Scale extension v.3.8 loaded) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xycolor.tex Xy-pic option: Colour extension v.3.11 loaded) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xymatrix.tex Xy-pic option: Matrix feature v.3.14 loaded) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xyarrow.tex Xy-pic option: Arrow and Path feature v.3.9 path, \ar, loaded) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xygraph.tex Xy-pic option: Graph feature v.3.11 loaded) loaded)) (/usr/share/texlive/texmf-dist/tex/latex/l3backend/l3backend-dvips.def) (./math.aux) ABD: EveryShipout initializing macros (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsa.fd) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsb.fd) ! Missing delimiter (. inserted). <to be read again> } l.72 \end{array}\right\end{split} ! Missing delimiter (. inserted). <to be read again> } l.72 \end{array}\right\end{split} [1] (./math.aux) ) (see the transcript file for additional information) Output written on math.dvi (1 page, 9436 bytes). Transcript written on math.log.

Aparté mathématique

La log-vraisemblance d’une régression logistique pour un jeu de données (X_i, y_i) s’exprime comme suit pour une régression logistique de paramètre \beta.

\begin{array}{rcl}
L(\beta, X, y) &=& \sum_{i=1}^n y_i \ln f(\beta, X_i) + (1-y_i) \ln (1-f(\beta, X_i)) \\
\text{avec } f(\beta, X_i) &=& \frac{1}{1 + \exp(- (\beta_0 + \sum_{k=1}^d x_{ik} \beta_k))}
\end{array}

On remarque que :

\begin{array}{rcl}
f(x) &=& \frac{1}{1 + e^{-x}} \\
\Rightarrow f(-x) &=& \frac{1}{1 + e^{x}} = \frac{e^{-x}}{1 + e^{-x}} \\
\Rightarrow f(x) + f(-x) &=& \frac{1}{1 + e^{-x}} + \frac{e^{-x}}{1 + e^{-x}} = 1
\end{array}

Cela explique pour on utilise souvent cette fonction pour transformer une distance en probabilité pour un classifieur binaire. L’apprentissage d’un arbre de décision sklearn.tree.DecisionTreeClassifier propose le paramètre min_samples_leaf. On se propose dans le cadre de la régression logistique de chercher le paramètre \beta_0 qui permet de vérifier la contrainte fixée par min_samples_leaf. Cela revient à trounver un classifieur linéaire parallèle au premier qui vérifie les contraintes.

Approche EM et régression logistique

L’article [Scott2013] explicite un algorithme d’apprentissage EM pour une régression logistique.

../_images/bayes.png

Il faudrait adapter cet agorithme pour apprendre deux régressions logistiques dont la combinaison sur deux parties disjointes serait meilleure qu’une seule régression logistique sur la réunion des deux parties. Cet algorithme devrait trouver à la fois les modèles et la séparation entre les deux parties.

A faire(idée): Arbre de régressions logistiques et EM

Chaque noeud du graphe serait modélisé comme étant la réunion de trois régressions logistiques, une pour diviser l’espace en deux, deux autres apprenant à classifier sur chacune des parties.

issue

Lien vers les réseaux de neurones

En remplaçant chaque noeud par une régression logistique, l’arbre de décision deviendrait un réseau de neurones, avec une structure particulière certes mais un réseau de neurones tout de même. Chaque noeud du graphe serait transformé en un neurone avec une régression logistique impliquant toutes les variables. Il ne resterait plus qu’à continuer l’apprentissage avec des algorithmes à base de gradient stochastique. Cela reviendrait à changer l’initialisation du réseau de neurones. On considère le petit arbre décision suivant, trois features, trois noeuds, deux classes.

On souhaite le transformer en réseau de neurones avec une structure qui serait celle qui suit. On note tout d’abord la fonction sigmoïde f(x, s, h)=\frac{1}{1 + e^{-h(x - s)}}. Elle vaut 1/2 lorsque x vaut s, vaut 1 lorsque x est très grand, et 0 lorsque x est très petit. C’est équivalent à la fonction f(x, s, h)=g(X, S, v_0, h)\frac{1}{1 + e^{h(<X,V> + v_0)}}X=(x_1, x_2, x_3), V=(-1, 0, 0) et v_0=s.

Le problème avec la structure proposée est que chaque noeud final retourne toujours une classe alors que dans un arbre de décision, seule une feuille répond. Un noeud final fait la somme de toutes les feuilles, deux dans cet exemple. L’implémentation de scikit-learn n’est pas la plus facile à manipuler dans le sens où chaque couche ne peut prendre comme entrée que les sorties de la précédente et la fonction d’activation est la même pour tous les neurones. On ne peut pas non plus geler certains coefficients lors de l’apprentissage. C’est à ce moment-là qu’on se demande si ça vaut le coup de se lancer dans une implémentation à la rigueur jolie mais sans doute pas porteuse d’une innovation majeure. Et ce n’est pas la première fois que quelqu’un se lance dans la conversion d’un arbre en réseaux de neurones.

J’ai quand même essayé avec le notebook Un arbre de décision en réseaux de neurones et les classes NeuralTreeNode, NeuralTreeNet. Si l’idée de départ est séduisante, elle requiert une contrainte supplémentaire qui est de créer un réseau de neurones qui ne soit pas un minimum local de la fonction d’erreur auquel cas un apprentissage avec un algorithme à base de gradient ne pourra pas améliorer les performances du réseau de neurones.

../_images/mloc.png

La structure proposée n’est cependant pas la meilleure et elle pourrait être simplifiée. D’autres projets s’appuie des librairies existantes :

Ce dernier package convertit un réseau de neurones en autant de couches que la profondeur de l’arbre. L’image qui suit est tiré de l’article [Nakandalam2020] et qui résume leur idée.

../_images/hb.png

Plan orthogonal

Dans un espace à plusieurs dimensions, la régression logistique divise l’espace à l’aide d’un hyperplan. La fonction de décision reste similaire puisque la probabilité de classification dépend de la distance à cet hyperplan. On suppose qu’il existe une régression logistique binaire apprise sur un nuage de points (X_i, y_i). La probabilité de bonne classification est définie par :

f(\Theta, X_i) = \frac{1}{1 + e^{-\theta_0 + \sum_{k=1}^d \theta_k x_{ik}}}

Le vecteur \Theta définit un hyperplan. On choisit un vecteur \Theta' de telle sorte que <\Theta,\Theta'> = 0. Les deux vecteurs sont orthogonaux. On définit maintenant deux autres vecteurs \Theta_1, \Theta_2 pour deux autres régressions logistiques. Pour classer un point X, on procède comme suit :

  • si <\Theta',X> < 0, on classe le point en appliquant la régression logistique définie par Theta_1,

  • si <\Theta',X> \leqslant 0, on classe le point en appliquant la régression logistique définie par Theta_2.

De manière évidente, les performances en classification sont les mêmes que la première régression logistique. On peut ensuite réestimer les vecteurs \Theta_1, \Theta_2 pour maximiser la vraisemblance sur chacune des parties. Il ne reste plus qu’à montrer que la vraisemblance globale sera supérieur à celle obtenue par la première régression logistique.

A faire(idée): Arbre de régressions logistiques en cascade orthogonale

Implémenter la l’algorithme suivant :

  • Apprendre une régression logistique

  • Choisir un hyperplan perpendiculaire en optimisation un critère Construction d’un pseudo arbre

  • Apprendre une régression logistique sur chacune des parties.

  • Continuer jusqu’à ce l’amélioration soit négligeable

issue

Bibliographie

[Scott2013] Expectation-maximization for logistic regression,

James G. Scott, Liang Sun

[Nakandalam2020] A Tensor-based Approach for One-size-fits-all ML Prediction Serving.

Supun Nakandalam, Karla Saur, Gyeong-In Yu, Konstantinos Karanasos, Carlo Curino, Markus Weimer, Matteo Interlandi. To appear at OSDI 2020.