{"id":3564,"date":"2017-08-03T16:20:02","date_gmt":"2017-08-03T20:20:02","guid":{"rendered":"http:\/\/bioinfo.iric.ca\/?p=3564\/"},"modified":"2017-08-03T16:26:05","modified_gmt":"2017-08-03T20:26:05","slug":"algorithme-du-gradient","status":"publish","type":"post","link":"https:\/\/bioinfo.iric.ca\/fr\/algorithme-du-gradient\/","title":{"rendered":"L’algorithme de descente de gradient"},"content":{"rendered":"

L’algorithme de descente de gradient est un algorithme it\u00e9ratif ayant comme but de trouver les valeurs optimales des param\u00e8tres d’une fonction donn\u00e9e. Il tente d’ajuster ces param\u00e8tres afin de minimiser la sortie d’une fonction de co\u00fbt face \u00e0 un certain jeux de donn\u00e9es. Cet algorithme est souvent utilis\u00e9 en apprentissage machine dans le cadre de r\u00e9gressions non lin\u00e9aires puisqu’il permet de rapidement trouver une solution approximative \u00e0 des probl\u00e8mes tr\u00e8s complexes.<\/p>\n

Mon dernier article, Introduction \u00e0 la r\u00e9gression lin\u00e9aire<\/em><\/a>,\u00a0fait mention de l’algorithme de la descente de gradient comme solution possible pour une r\u00e9gression lin\u00e9aire simple. Bien qu’il existe une\u00a0solution analytique optimale \u00e0 la r\u00e9gression lin\u00e9aire simple, la simplicit\u00e9 de ce probl\u00e8me en fait un excellent candidat pour\u00a0d\u00e9montrer l’application de l’algorithme du gradient.<\/p>\n

Fonction de co\u00fbt<\/h4>\n

Reprenons la fonction de co\u00fbt pour une droite d\u00e9taill\u00e9e dans l’article Introduction \u00e0 la r\u00e9gression lin\u00e9aire<\/em>. La sortie de cette fonction repr\u00e9sente l’erreur et c’est cette erreur que l’on tentera de minimiser : la moyenne de la distance verticale entre nos\u00a0observations et la droite de r\u00e9gression\u00a0au carr\u00e9e (voir\u00a0la m\u00e9thode des moindres carr\u00e9es<\/a>). \u00a0Afin de garder une erreur de taille raisonnable et qui ne sera pas affect\u00e9e par la taille de notre jeu de donn\u00e9es, nous divisions par le nombre d’observations pour r\u00e9cup\u00e9rer la moyenne des erreurs.<\/p>\n

$ Co\u00fbt = \\dfrac{\\sum_{i=1}^n(y_i-(m x_i + b))^2}{N} $<\/p>\n

Gradient<\/h4>\n

Le gradient (la pente de notre fonction de co\u00fbt \u00e0 un point donn\u00e9) repr\u00e9sente la direction et le taux de variation de notre fonction de co\u00fbt. Suivre le gradient n\u00e9gatif de la fonction nous permet donc de la minimiser le plus rapidement possible. Afin d’obtenir le gradient, notre fonction doit \u00eatre diff\u00e9rentiable.\u00a0Prendre le carr\u00e9 de la distance nous assure une erreur positive et ainsi une fonction diff\u00e9rentiable.<\/p>\n

Le gradient de notre fonction de co\u00fbt est obtenu en prenant la d\u00e9riv\u00e9e en fonction de nos param\u00e8tres $m$ et $b$ :<\/p>\n

$ \\dfrac{\\delta}{\\delta m} = \\dfrac{2\\sum_{i=1}^n-x_i(y_i-(m x_i + b))}{N} $<\/p>\n

$ \\dfrac{\\delta}{\\delta b} = \\dfrac{2\\sum_{i=1}^n-(y_i-(m x_i + b))}{N} $<\/p>\n

Deux param\u00e8tres doivent \u00eatres fix\u00e9s dans l’algorithme du gradient, soit le\u00a0pas de gradient<\/em>\u00a0(le taux de changement \u00e0 chaque it\u00e9ration) et le nombre d’it\u00e9rations ou \u00e9poques<\/em>\u00a0pour l’apprentissage. Dans notre exemple, l’algorithme tentera d’ajuster les param\u00e8tres $m$ et $b$ durant 10 000 it\u00e9rations (epochs<\/em>) avec un pas de gradient (lr<\/em>) de 0.001.<\/p>\n

Code<\/h4>\n
import matplotlib.pyplot as plt\r\nimport numpy as np\r\n\r\n# Fonction de co\u00fbt\r\ndef error(m, b, X, Y):\r\n    return sum(((m * x + b) - Y[idx])**2 for idx, x in enumerate(X)) \/ float(len(X))\r\n\r\n# Gradient du param\u00e8tre m\r\ndef m_grad(m, b, X, Y):\r\n    return sum(-2 * x * (Y[idx] - (m * x + b)) for idx, x in enumerate(X)) \/ float(len(X))\r\n\r\n# Gradient du param\u00e8tre b\r\ndef b_grad(m, b, X, Y):\r\n    return sum(-2 * (Y[idx] - (m * x + b)) for idx, x in enumerate(X)) \/ float(len(X))\r\n\r\ndef gradient_descent_LR(X, Y, epochs, lr):\r\n    assert(len(X) == len(Y))\r\n    m = 0\r\n    b = 0\r\n    for e in range(epochs):\r\n        m = m - lr * m_grad(m, b, X, Y)\r\n        b = b - lr * b_grad(m, b, X, Y)\r\n    return m, b\r\n\r\nif __name__ == '__main__':\r\n    # G\u00e9n\u00e9ration du jeu de donn\u00e9es\r\n    X = np.linspace(-1, 1, 100) + np.random.normal(0, 0.25, 100)\r\n    Y = np.linspace(-1, 1, 100) + np.random.normal(0, 0.25, 100)\r\n\r\n    # Ex\u00e9cution de l'algorithme\r\n    m, b = gradient_descent_LR(X, Y, epochs=10000, lr=0.001)\r\n\r\n    # Visualisation de la droite avec les valeurs de m et b trouv\u00e9es par descente de gradient\r\n    line_x = [min(X), max(X)]\r\n    line_y = [(m * i) + b for i in line_x]\r\n    plt.plot(line_x, line_y, 'b')\r\n    plt.plot(X, Y, 'ro')\r\n    plt.show()<\/code><\/pre>\n
Visualisation de l’entra\u00eenement<\/h4>\n
\"\"<\/a>
Visualisation de l’entra\u00eenement par descente de gradient. Notez que les param\u00e8tres convergent de plus en plus lentement lorsqu’ils approchent de leurs valeurs optimales.<\/p><\/div>\n
Un excellent article couvrant le m\u00eame sujet plus en d\u00e9tails peut \u00eatre retrouv\u00e9 \u00e0 l’addresse suivante (en anglais)\u00a0: https:\/\/spin.atomicobject.com\/2014\/06\/24\/gradient-descent-linear-regression\/<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
L’algorithme de descente de gradient est un algorithme it\u00e9ratif ayant comme but de trouver les valeurs optimales des param\u00e8tres d’une fonction donn\u00e9e. Il tente d’ajuster ces param\u00e8tres afin de minimiser la sortie d’une fonction de co\u00fbt face \u00e0 un certain jeux de donn\u00e9es. Cet algorithme est souvent utilis\u00e9 en apprentissage machine dans le cadre de r\u00e9gressions non lin\u00e9aires puisqu’il permet de rapidement trouver une solution approximative \u00e0 des probl\u00e8mes tr\u00e8s complexes. Mon dernier article, Introduction \u00e0 la r\u00e9gression lin\u00e9aire,\u00a0fait mention  […]<\/a><\/p>\n","protected":false},"author":7,"featured_media":3630,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"image","meta":{"jetpack_post_was_ever_published":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[69,85,2,26,70],"tags":[],"class_list":["post-3564","post","type-post","status-publish","format-image","has-post-thumbnail","hentry","category-analyse-de-donnees","category-apprentissage-automatique","category-non-classifiee","category-langage-python","category-scripts","post_format-post-format-image"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"https:\/\/bioinfo.iric.ca\/wpbioinfo\/wp-content\/uploads\/2017\/08\/7899.png","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/posts\/3564","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/comments?post=3564"}],"version-history":[{"count":39,"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/posts\/3564\/revisions"}],"predecessor-version":[{"id":3641,"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/posts\/3564\/revisions\/3641"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/media\/3630"}],"wp:attachment":[{"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/media?parent=3564"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/categories?post=3564"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/tags?post=3564"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}