{"id":37955,"date":"2019-10-31T22:20:47","date_gmt":"2019-10-31T19:20:47","guid":{"rendered":"https:\/\/prohoster.info\/blog\/linejnaya-regressiya-i-metody-eyo-vosstanovleniya\/"},"modified":"2019-10-31T22:20:47","modified_gmt":"2019-10-31T19:20:47","slug":"linejnaya-regressiya-i-metody-eyo-vosstanovleniya","status":"publish","type":"post","link":"https:\/\/prohoster.info\/de\/blog\/administrirovanie\/linejnaya-regressiya-i-metody-eyo-vosstanovleniya","title":{"rendered":"Lineare Regression und Methoden ihrer Wiederherstellung","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Lineare
\nQuelle: xkcd<\/a><\/noindex><\/i><\/p>\n

Lineare Regression ist einer der grundlegenden Algorithmen f\u00fcr viele Bereiche der Datenanalyse. Der Grund daf\u00fcr ist offensichtlich. Es ist ein sehr einfacher und verst\u00e4ndlicher Algorithmus, der seit vielen Jahrzehnten, wenn nicht Jahrhunderten, weit verbreitet ist. Die Idee besteht darin, dass wir eine lineare Abh\u00e4ngigkeit einer Variablen von einer Menge anderer Variablen annehmen und dann versuchen, diese Abh\u00e4ngigkeit zu rekonstruieren.<\/p>\n

Aber dieser Artikel handelt nicht von der Anwendung der linearen Regression zur L\u00f6sung praktischer Probleme. Hier werden interessante Aspekte der Implementierung verteilter Algorithmen zu ihrer Rekonstruktion betrachtet, mit denen wir beim Schreiben des Moduls f\u00fcr maschinelles Lernen in Apache Ignite<\/a><\/noindex>. Ein wenig Grundmathematik, die Grundlagen des maschinellen Lernens und der verteilten Berechnungen helfen zu verstehen, wie man die lineare Regression rekonstruiert, selbst wenn die Daten \u00fcber Tausende von Knoten verteilt sind.
\n<\/a><\/noindex><\/p>\n

Worum geht es?<\/h3>\n

\nVor uns steht die Aufgabe, eine lineare Abh\u00e4ngigkeit zu rekonstruieren. Als Eingabedaten wird eine Menge von Vektoren angeblicher unabh\u00e4ngiger Variablen bereitgestellt, von denen jeder einem bestimmten Wert der abh\u00e4ngigen Variablen zugeordnet wird. Diese Daten k\u00f6nnen in Form von zwei Matrizen dargestellt werden:<\/p>\n

\"Lineare<\/p>\n

\nJetzt, da eine Abh\u00e4ngigkeit angenommen wird, und zudem eine lineare, dr\u00fccken wir unsere Annahme in Form eines Matrizenprodukts aus (zur Vereinfachung der Darstellung wird hier und im Folgenden angenommen, dass das konstante Glied der Gleichung verborgen ist hinter \"Lineare, und die letzte Spalte der Matrix \"Lineare enth\u00e4lt Einsen):<\/p>\n

\"Lineare<\/p>\n

\nSieht sehr nach einem System linearer Gleichungen aus, nicht wahr? Es scheint so, aber f\u00fcr ein solches Gleichungssystem wird es wahrscheinlich keine L\u00f6sungen geben. Der Grund daf\u00fcr sind die St\u00f6rungen, die in praktisch allen realen Daten vorhanden sind. Auch das Fehlen einer linearen Abh\u00e4ngigkeit selbst k\u00f6nnte der Grund sein, gegen die man versuchen kann, durch Einf\u00fchrung zus\u00e4tzlicher Variablen vorzugehen, die nichtlinear von den Urspr\u00fcnglichen abh\u00e4ngen. Betrachten wir das folgende Beispiel:
\n\"Lineare
\nQuelle: Wikipedia<\/a><\/noindex><\/i><\/p>\n

Dies ist ein einfaches Beispiel f\u00fcr lineare Regression, das die Abh\u00e4ngigkeit einer Variablen (auf der Achse \"Lineare) von einer anderen Variablen (auf der Achse \"Lineare). Damit das dem Beispiel entsprechende System linearer Gleichungen eine L\u00f6sung hat, m\u00fcssen alle Punkte genau auf einer Linie liegen. Aber das ist nicht der Fall. Und sie liegen nicht auf einer Linie genau wegen des Rauschens (oder weil die Annahme einer linearen Abh\u00e4ngigkeit fehlerhaft war). Um also die lineare Abh\u00e4ngigkeit aus realen Daten wiederherzustellen, ist es normalerweise erforderlich, eine weitere Annahme einzuf\u00fchren: die Eingabedaten enthalten Rauschen, und dieses Rauschen hat eine normale Verteilung<\/a><\/noindex>. Man kann auch Annahmen \u00fcber andere Arten von Rauschverteilungen treffen, aber in den \u00fcberwiegenden F\u00e4llen wird tats\u00e4chlich die normale Verteilung betrachtet, \u00fcber die wir im Folgenden sprechen werden.<\/p>\n

Die Maximum-Likelihood-Methode<\/h3>\n

\nAlso haben wir das Vorhandensein von zuf\u00e4llig normalverteiltem Rauschen angenommen. Was tun wir in einer solchen Situation? F\u00fcr diesen Fall gibt es in der Mathematik ein weit verbreitetes Konzept. Maximum-Likelihood-Verfahren<\/a><\/noindex>. Kurz gesagt, es besteht darin, Likelihood-Funktion<\/a><\/noindex> und dann diese zu maximieren.<\/p>\n

Kehren wir zur Wiederherstellung der linearen Abh\u00e4ngigkeit bei Daten mit normalem Rauschen zur\u00fcck. Beachten wir, dass die angenommene lineare Abh\u00e4ngigkeit den mathematischen Erwartungswert \"Lineare der vorhandenen normalen Verteilung darstellt. Gleichzeitig ist die Wahrscheinlichkeit, dass \"Lineare einen bestimmten Wert annimmt, unter der Bedingung, dass beobachtbare \"Lineare, sieht folgenderma\u00dfen aus:<\/p>\n

\"Lineare<\/p>\n

\nJetzt setzen wir anstelle von \"Lineare und \"Lineare die ben\u00f6tigten Variablen ein:<\/p>\n

\"Lineare<\/p>\n

\nEs bleibt nur noch, den Vektor \"Linearezu finden, bei dem diese Wahrscheinlichkeit maximal ist. Um eine solche Funktion zu maximieren, ist es praktisch, sie zuerst zu logarithmieren (der Logarithmus der Funktion erreicht sein Maximum an derselben Stelle wie die Funktion selbst):<\/p>\n

\"Lineare<\/p>\n

\nWas wiederum auf die Minimierung der folgenden Funktion hinausl\u00e4uft:<\/p>\n

\"Lineare<\/p>\n

\n\u00dcbrigens wird dies als Methode der kleinsten Quadrate<\/a><\/noindex>bezeichnet. Oft werden alle vorangegangenen \u00dcberlegungen \u00fcbersprungen und es wird einfach diese Methode verwendet.<\/p>\n

QR-Zerlegung<\/h3>\n

\nDas Minimum der oben genannten Funktion kann gefunden werden, wenn der Punkt gefunden wird, an dem der Gradient dieser Funktion gleich null ist. Der Gradient wird wie folgt dargestellt:<\/p>\n

\"Lineare<\/p>\n

\nQR-Zerlegung<\/a><\/noindex> ist eine matrizenbasierte Methode zur L\u00f6sung von Minimierungsproblemen, die in der Methode der kleinsten Quadrate verwendet wird. In diesem Zusammenhang schreiben wir die Gleichung in matrixform um:<\/p>\n

\"Lineare<\/p>\n

\nAlso zerlegen wir die Matrix \"Lineare in Matrizen \"Lineare und \"Lineare und f\u00fchren eine Reihe von Transformationen durch (der Algorithmus der QR-Zerlegung wird hier nicht betrachtet, sondern nur seine Anwendung f\u00fcr die gestellte Aufgabe):<\/p>\n

\"Lineare<\/p>\n

\nDie Matrix \"Lineare ist orthogonal. Das erm\u00f6glicht es uns, das Produkt zu eliminieren \"Lineare:<\/p>\n

\"Lineare<\/p>\n

\nWenn wir ersetzen \"Lineare auf \"Lineare, ergibt sich \"Lineare. Unter Ber\u00fccksichtigung, dass \"Lineare eine obere Dreiecksmatrix ist, sieht das folgenderma\u00dfen aus:<\/p>\n

\"Lineare<\/p>\n

\nDas kann durch das Ersatzverfahren gel\u00f6st werden. Das Element \"Lineare wird gefunden als \"Lineare, das vorhergehende Element \"Lineare wird gefunden als \"Lineare und so weiter.<\/p>\n

Hier sei darauf hingewiesen, dass die Komplexit\u00e4t des erhaltenen Algorithmus durch die Verwendung der QR-Zerlegung gleich ist \"Lineare. Obwohl die Matrixmultiplikation gut parallelisierbar ist, ist es nicht m\u00f6glich, eine effektive verteilte Version dieses Algorithmus zu schreiben.<\/p>\n

Gradientenabstieg<\/h3>\n

\nWenn wir \u00fcber die Minimierung einer bestimmten Funktion sprechen, sollte man immer an die Methode (stochastischer) Gradientabstieg denken. Dies ist eine einfache und effektive Methode zur Minimierung, die auf der iterativen Berechnung des Gradienten der Funktion an einem Punkt und der anschlie\u00dfenden Verschiebung in die entgegengesetzte Richtung des Gradienten basiert. Jeder solche Schritt bringt die L\u00f6sung n\u00e4her an das Minimum. Der Gradient sieht dabei wie folgt aus:<\/p>\n

\"Lineare<\/p>\n

Diese Methode l\u00e4sst sich ebenfalls gut parallelisieren und verteilen aufgrund der linearen Eigenschaften des Gradientenoperators. Beachten Sie, dass in der obigen Formel unter dem Summenzeichen unabh\u00e4ngige Summanden stehen. Mit anderen Worten, wir k\u00f6nnen den Gradient unabh\u00e4ngig f\u00fcr alle Indizes \"Lineare von eins bis \"Lineare, parallel dazu den Gradient f\u00fcr Indizes von \"Lineare bis \"Lineareberechnen. Dann summieren wir die erhaltenen Gradienten. Das Ergebnis dieser Summierung wird dasselbe sein, als h\u00e4tten wir sofort den Gradient f\u00fcr die Indizes von eins bis \"Lineareberechnet. Somit, wenn die Daten auf mehrere Datenteile verteilt sind, kann der Gradient unabh\u00e4ngig auf jedem Teil berechnet werden, und die Ergebnisse dieser Berechnungen k\u00f6nnen dann zusammengefasst werden, um das endg\u00fcltige Ergebnis zu erhalten:<\/p>\n

\"Lineare<\/p>\n

Aus Implementierungssicht passt dies in das Paradigma MapReduce<\/a><\/noindex>. Bei jedem Schritt des Gradientabstiegs wird jedem Dataknoten eine Aufgabe zum Berechnen des Gradienten zugewiesen, dann werden die berechneten Gradienten gesammelt, und das Ergebnis ihrer Summierung wird verwendet, um das Ergebnis zu verbessern.<\/p>\n

Trotz der einfachen Implementierung und der M\u00f6glichkeit der Ausf\u00fchrung im MapReduce-Paradigma hat der Gradientensprung auch seine Nachteile. Insbesondere ist die Anzahl der Schritte, die zur Erreichung der Konvergenz erforderlich sind, im Vergleich zu anderen, spezialisierteren Methoden erheblich h\u00f6her.<\/p>\n

LSQR<\/h3>\n

\nLSQR<\/a><\/noindex> ist eine weitere Methode zur L\u00f6sung der gestellten Aufgabe, die sowohl f\u00fcr die Wiederherstellung der linearen Regression als auch zur L\u00f6sung von linearen Gleichungssystemen geeignet ist. Ihr Hauptmerkmal besteht darin, dass sie die Vorteile von Matrixmethoden und iterativen Ans\u00e4tzen vereint. Implementierungen dieser Methode sind sowohl in Bibliotheken zu finden SciPy<\/a><\/noindex>, als auch in MATLAB<\/a><\/noindex>. Eine Beschreibung dieser Methode wird hier nicht gegeben (sie kann in dem Artikel gefunden werden LSQR: An algorithm for sparse linear equations and sparse least squares<\/a><\/noindex>). Stattdessen wird ein Ansatz demonstriert, der es erm\u00f6glicht, LSQR an die Ausf\u00fchrung in einer verteilten Umgebung anzupassen.<\/p>\n

Die Grundlage der LSQR-Methode bildet ein Bidiagonalierungsverfahren<\/a><\/noindex>. Dies ist ein iteratives Verfahren, bei dem jede Iteration aus den folgenden Schritten besteht:
\n\"Lineare
\n
\nWenn man jedoch davon ausgeht, dass die Matrix \"Lineare horizontal partitioniert ist, kann jede Iteration als zwei MapReduce-Schritte dargestellt werden. Dadurch l\u00e4sst sich der Datenversand w\u00e4hrend jeder Iteration minimieren (nur Vektoren der L\u00e4nge, die der Anzahl der Unbekannten entspricht):<\/p>\n

\"Lineare
\n
\nGenau dieser Ansatz wird bei der Implementierung der linearen Regression in Apache Ignite ML<\/a><\/noindex>.<\/p>\n

Fazit<\/h3>\n

\nverwendet. Es gibt viele Algorithmen zur Wiederherstellung der linearen Regression, aber nicht alle k\u00f6nnen unter allen Bedingungen angewendet werden. So ist die QR-Zerlegung hervorragend f\u00fcr exakte L\u00f6sungen auf kleinen Datenmengen geeignet. Der Gradientensprung l\u00e4sst sich einfach umsetzen und erm\u00f6glicht es, schnell eine N\u00e4herungsl\u00f6sung zu finden. LSQR vereint die besten Eigenschaften der beiden vorherigen Algorithmen, da es verteilt werden kann, schneller konvergiert als der Gradientensprung und auch eine vorzeitige Beendigung des Algorithmus erm\u00f6glicht, im Gegensatz zur QR-Zerlegung zur Suche nach einer N\u00e4herungsl\u00f6sung.
\n
Quelle: habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"

\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a: xkcd \u041b\u0438\u043d\u0435\u0439\u043d\u0430\u044f \u0440\u0435\u0433\u0440\u0435\u0441\u0441\u0438\u044f \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0434\u043d\u0438\u043c \u0438\u0437 \u0431\u0430\u0437\u043e\u0432\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0434\u043b\u044f \u043c\u043d\u043e\u0433\u0438\u0445 \u043e\u0431\u043b\u0430\u0441\u0442\u0435\u0439, \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u044b\u0445 \u0441 \u0430\u043d\u0430\u043b\u0438\u0437\u043e\u043c \u0434\u0430\u043d\u043d\u044b\u0445. \u041f\u0440\u0438\u0447\u0438\u043d\u0430 \u044d\u0442\u043e\u043c\u0443 \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u0430. \u042d\u0442\u043e \u043e\u0447\u0435\u043d\u044c \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0438 \u043f\u043e\u043d\u044f\u0442\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u0447\u0442\u043e \u0441\u043f\u043e\u0441\u043e\u0431\u0441\u0442\u0432\u0443\u0435\u0442 \u0435\u0433\u043e \u0448\u0438\u0440\u043e\u043a\u043e\u043c\u0443 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044e \u0443\u0436\u0435 \u043c\u043d\u043e\u0433\u0438\u0435 \u0434\u0435\u0441\u044f\u0442\u043a\u0438, \u0435\u0441\u043b\u0438 \u043d\u0435 \u0441\u043e\u0442\u043d\u0438, \u043b\u0435\u0442. \u0418\u0434\u0435\u044f \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043c\u044b \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u043c \u043b\u0438\u043d\u0435\u0439\u043d\u0443\u044e \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u043e\u0434\u043d\u043e\u0439 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u043e\u0442 \u043d\u0430\u0431\u043e\u0440\u0430 \u0434\u0440\u0443\u0433\u0438\u0445 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445, \u0430 \u043f\u043e\u0442\u043e\u043c \u043f\u044b\u0442\u0430\u0435\u043c\u0441\u044f […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":28483,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-37955","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"\ud83e\udd47Lineare Regression und Methoden zu ihrer Wiederherstellung | ProHoster","description":"Quelle:","canonical_url":"https:\/\/prohoster.info\/de\/blog\/administrirovanie\/linejnaya-regressiya-i-metody-eyo-vosstanovleniya","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"de_DE","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47\u041b\u0438\u043d\u0435\u0439\u043d\u0430\u044f \u0440\u0435\u0433\u0440\u0435\u0441\u0441\u0438\u044f \u0438 \u043c\u0435\u0442\u043e\u0434\u044b \u0435\u0451 \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u044f | ProHoster","og:description":"\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a:","og:url":"https:\/\/prohoster.info\/de\/blog\/administrirovanie\/linejnaya-regressiya-i-metody-eyo-vosstanovleniya","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-10-31T19:20:47+00:00","article:modified_time":"2019-10-31T19:20:47+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"37955","title":null,"description":null,"keywords":null,"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-23 19:55:19","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-03-01 01:17:23","updated":"2026-01-23 19:55:19","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/posts\/37955","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/comments?post=37955"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/posts\/37955\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/media\/28483"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/media?parent=37955"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/categories?post=37955"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/tags?post=37955"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}