$$\\mathcal{M}_{\\theta}(x) = \\hat{y}$$<\/p>\n\n\n\n
Dabei bezeichnet $\\hat{y}$ die Vorhersage des Modells, im Gegensatz zum wahren Wert $y$, der durch den Datensatz vorgegeben ist. Beim Training suchen wir nun den optimalen Parameter<\/p>\n\n\n\n
$$\\theta^*$$<\/p>\n\n\n\n
der daf\u00fcr sorgt, dass die Modellausgabe f\u00fcr alle $x$ aus $\\mathcal{D}$ m\u00f6glichst nah an der wahren Ausgabe $y$ liegt:<\/p>\n\n\n\n
$$\\sum_{(x,y) \\in \\mathcal{D}} d(y,\\mathcal{M}_{\\theta^*}(x))~\\rightarrow ~\\min$$<\/p>\n\n\n\n
Dabei ist $d(\\cdot,\\cdot)$ ein beliebiges Distanzma\u00df, im Fall einer Regression zum Beispiel $$d(y,\\hat{y}) = (y-\\hat{y})^2.$$ Die Summe im obigen Beispiel wird auch als Loss-Funktion $L$ bezeichnet.<\/p>\n\n\n\n
Gradientenverfahren versuchen, diese Funktion zu minimieren, indem sie die Ableitung $$\\mathrm{d}L\/\\mathrm{d}\\theta$$ bilden. Die Berechnung der Ableitung ist h\u00e4ufig rechenaufwendig. Au\u00dferdem kann $L$ viele unterschiedliche lokale Optima besitzen oder sogar \u00fcberhaupt nicht ableitbar sein. In diesem Fall k\u00f6nnen Gradientenverfahren entweder nicht effektiv oder gar nicht zum Einsatz kommen. Abhilfe schafft in diesem Fall die Evolution\u00e4re Optimierung.<\/p>\n\n\n\n
Optimierung durch lokale Suche<\/h2>\n\n\n\n
Nehmen wir eine noch allgemeinere Formulierung eines Optimierungsproblems als Grundlage: Aus einer Menge $\\mathcal{X}$ m\u00f6glicher L\u00f6sungskandidaten soll ein Element<\/p>\n\n\n\n
$$x^* \\in \\mathcal{X}$$<\/p>\n\n\n\n
gefunden werden, das bez\u00fcglich einer festen Loss-Funktion $$L:~\\mathcal{X} \\rightarrow \\mathbb{R}$$ minimal ist:<\/p>\n\n\n\n
$$x^* = \\underset{x \\in \\mathcal{X}}{\\arg\\min} L(x).$$<\/p>\n\n\n\n
Grunds\u00e4tzlich k\u00f6nnte das optimale Element $x^*$ durch Ziehen zuf\u00e4lliger Elemente aus $\\mathcal{X}$ gefunden werden. Dieser Random-Search-Ansatz ist zwar einfach umzusetzen, aber ineffektiv, wenn der Suchraum $\\mathcal{X}$ sehr gro\u00df ist. Er bildet dennoch eine gute Referenz, gegen die andere Verfahren verglichen werden k\u00f6nnen: Liefert ein Optimierungsverfahren schlechtere Ergebnisse als Random Search, ist es nicht geeignet f\u00fcr das vorliegende Problem. Im Gegensatz zum Gradientenverfahren, das sich ausgehend von einem Startpunkt $$x^t$$ in entgegengesetzte Richtung des Gradienten,<\/p>\n\n\n\n
$$-\\eta \\cdot \\mathrm{d}L\/\\mathrm{d}x^t,$$<\/p>\n\n\n\n
mit Schrittweite $\\eta$, bewegt, um sich m\u00f6glichst direkt einem Optimum zu n\u00e4hern, springt Random Search<\/em> wahllos im L\u00f6sungsraum umher und testet zuf\u00e4llige L\u00f6sungskandidaten aus.<\/p>\n\n\n\n Ein Mittelweg besteht darin, von einem Startpunkt $x^0$ auszugehen und sich in der Umgebung dieses Punktes vorzutasten. Beispielsweise werden verschiedene nahegelegene Punkte $\\tilde{x}^0_1, \\dots, \\tilde{x}^0_{\\lambda}$ ausgewertet. Der Punkt mit dem niedrigsten Loss-Wert, welcher folglich n\u00e4her am Optimum zu liegen scheint und daher am vielversprechendsten ist, wird sodann als neuer Ausgangspunkt $x^1$ \u00fcbernommen. Ist keine der nahegelegenen L\u00f6sungen besser als der Ausgangspunkt, wird $x^1 = x^0$ belassen. Wiederholt man diesen Vorgang h\u00e4ufig, so bewegt sich der Punkt $x^t$ f\u00fcr ein immer gr\u00f6\u00dferes $t$ auf ein Optimum zu. Dieses Schema bildet ein Optimierungsverfahren namens (1+\u03bb)-EA. Dabei steht EA f\u00fcr Evolution\u00e4rer Algorithmus.<\/p>\n\n\n\n Die Evolution\u00e4ren Algorithmen bilden eine Klasse von Optimierungsverfahren, die bereits seit den 1950er-Jahren erforscht werden. Das Vorbild ist dabei die erstmals von Charles Darwin formulierte Evolution in der Natur: Bei der Fortpflanzung von Lebewesen werden Gene der Eltern rekombiniert. Zus\u00e4tzlich treten Mutationen auf, wodurch die Nachkommen Eigenschaften der Eltern erben und sich spontan neue Eigenschaften ausbilden k\u00f6nnen. Besser angepasste Nachkommen \u00fcberleben und schaffen es, selbst Nachkommen zu zeugen. Schlechter angepasste Individuen sterben hingegen durch den Selektionsdruck, der zum Beispiel durch Fressfeinde oder begrenztes Nahrungsangebot entsteht. Dieser Vorgang wird bei den Evolution\u00e4ren Algorithmen imitiert: Aus einer Population von $\\mu$ Eltern $[x^t_1, \\dots, x^t_{\\mu}]$ aus $\\mathcal{X}$ werden $\\lambda$ Nachkommen durch Rekombination und Mutation erstellt. Wie diese Operationen genau aussehen, h\u00e4ngt von dem Suchraum $\\mathcal{X}$ ab. Sind die Individuen beispielsweise wie Listen oder Vektoren aufgebaut, $\\mathcal{X} = \\mathbb{Y}^n$, so k\u00f6nnten zwei Vektoren $\\boldsymbol{a}$ und $\\boldsymbol{b}$ rekombiniert werden, indem sie vor einem zuf\u00e4llig gew\u00e4hlten Index $m \\in \\lbrace 1,\\dots,n\\rbrace$ zerteilt werden und je ein Teil von jedem Elternteil \u00fcbernommen wird:<\/p>\n\n\n\n <\/p>\n\n\n\n $$\\tilde{x} = (a_1,\\dots,a_{m-1},b_m,\\dots,b_n)$$<\/p>\n\n\n\n Sind die Individuen reelle Zahlen, $\\mathcal{X} = \\mathbb{R}$, kann eine Mutation durch Addieren eines zuf\u00e4lligen, zum Beispiel normalverteilten Rauschens erfolgen:<\/p>\n\n\n\n $$\\tilde{x} = x + \\epsilon,\\ ~\\epsilon \\sim \\mathcal{N}(0,1)$$<\/p>\n\n\n\n Aus der gesamten Population, bestehend aus den $\\mu$ Eltern und den $\\lambda$ rekombinierten und mutierten Nachkommen, werden nun die $\\mu$ besten Individuen bez\u00fcglich der Loss-Funktion $L$ selektiert. Die Funktion bewertet sozusagen, wie gut angepasst ein Individuum ist. Sie wird daher im Kontext von Evolution\u00e4ren Algorithmen Fitness-Funktion genannt und maximiert statt minimiert. Die $\\mu$ Individuen mit den niedrigsten $L$-Werten (beziehungsweise der h\u00f6chsten Fitness) bilden die n\u00e4chste Elterngeneration; dann beginnt der Prozess von vorn. Erf\u00fcllt der Mutationsoperator bestimmte statistische Eigenschaften, ist es garantiert, dass die Population mit wachsender Zahl Generationen zum globalen Optimum $x^*$ konvergiert (Convergence of evolutionary algorithms in general search spaces<\/a>).<\/p>\n\n\n\n In dem neuen Paper Gradient-free quantum optimization on NISQ devices<\/em><\/a><\/em> nutzen Forscher*innen der Lamarr Institut Evolution\u00e4re Algorithmen, um Schaltkreise von Quantencomputern zu optimieren. Die Schaltkreise sind zusammengesetzt aus verschiedenartigen Gates (Gattern), die auf einzelne oder auf Paare von Qubits wirken und reellwertige Parameter mit Werten zwischen $0$ und $2\\pi$ enthalten. Wird ein solcher Schaltkreis ausgef\u00fchrt, \u00e4ndert er den gemeinsamen Zustand der Qubits und es entstehen Verschr\u00e4nkungen. Diese Verschr\u00e4nkungen f\u00fcr Berechnungen und insbesondere das Maschinelle Lernen nutzbar zu machen ist Gegenstand aktueller Forschung.<\/p>\n\n\n\n Der Suchraum $\\mathcal{X}$ des vorliegenden Optimierungsproblems ist also die Menge aller Quantenschaltkreise, die sich aus allen Kombinationen von Gattern und Parametern ergibt. Potentiell k\u00f6nnen beliebig viele Gatter verwendet werden; daher ist $\\mathcal{X}$ eine unendliche Menge. Die Loss-Funktion $L$ ordnet einem Quantenschaltkreis einen reellen Wert zu und ist definiert als erwartete Kosten bez\u00fcglich einer Hamiltonian (einer Gr\u00f6\u00dfe in der Physik), welche einem Quantenzustand eine Energie zuordnet. Einen Schaltkreis zu finden, der minimal bez\u00fcglich einer gegebenen Hamiltonian ist, ist ein schwieriges Problem der Physik, das von zentraler Bedeutung f\u00fcr die Erforschung von Quantenalgorithmen ist. Es ist eng verwandt mit dem Problem, effizient automatisiert einen Quantenschaltkreis zu finden, der eine bestimmte vorgegebene Funktionalit\u00e4t ausf\u00fchrt.<\/p>\n\n\n\n Sind die Gatter und deren Positionen in einem Quantenschaltkreis fest vorgegeben, k\u00f6nnen mit einem Gradientenverfahren die reellwertigen Gatterparameter optimiert werden. F\u00fcr die Gatterstruktur selbst hingegen ist dies nicht m\u00f6glich, denn das blo\u00dfe Vorhandensein eines Gatters, beziehungsweise dessen Typ und Position, kann man nicht numerisch ableiten. Die Forschenden entschieden sich daher f\u00fcr den Einsatz Evolution\u00e4rer Algorithmen. Diese bieten gro\u00dfe Flexibilit\u00e4t, da es gen\u00fcgt, die Rekombinations- und Mutationsoperatoren festzulegen, um zu garantieren, dass das Verfahren ein gutes Ergebnis findet. Zur Mutation eines Quantenschaltkreises werden hier beispielsweise zuf\u00e4llig Gatter hinzugef\u00fchrt, entfernt, gegen andere Gatter ausgetauscht oder die Parameter leicht ver\u00e4ndert. Durch solche kleinen Ver\u00e4nderungen wird der optimale Schaltkreis nach und nach \u00fcber die Generationen hinweg konstruiert.<\/p>\n\n\n\n In ihrem Paper konnten die Forschenden diesen Prozess nicht nur simulieren, sondern auf echten Quantencomputern mit bis zu 20 Qubits erfolgreich durchf\u00fchren. Sie zeigten somit, dass Evolution\u00e4re Optimierung effektiv anstelle der \u00fcblichen Gradientenverfahren f\u00fcr Probleme des Quantencomputings eingesetzt werden kann. Dadurch k\u00f6nnen nicht nur Parameter fester Gatterstrukturen gelernt, sondern auch kompaktere Quantenschaltkreise gefunden werden, die weniger Gatter ben\u00f6tigen.<\/p>\n\n\n\n Die untenstehende Graphik zeigt den Optimierungsverlauf auf verschiedenen Quantencomputern von IBM und in einer Simulation. In allen F\u00e4llen ist zu beobachten, dass die Energie im Verlauf der Generationen des evolution\u00e4ren Algorithmus\u2019 abnimmt, somit also eine gute L\u00f6sung schrittweise angen\u00e4hert wird.<\/p>\n\n\n\n Auch \u00fcber ein halbes Jahrhundert nach ihrer Entwicklung erweist sich die evolution\u00e4re Optimierung noch immer als flexibles und m\u00e4chtiges Werkzeug f\u00fcr hochaktuelle Anwendungen. So auch im Quantum-Computing, wo gradientenbasierte Verfahren an ihre Grenzen sto\u00dfen.<\/p>\n\n\n\n Weitere Informationen im zugeh\u00f6rigen Paper: Die Evolution\u00e4re Optimierung ist eine echte Alternative zu gradientenbasierten Verfahren, da sie flexibler in verschiedenen Anwendungsszenarien eingesetzt werden kann. ML2R-Forschende nutzten evolution\u00e4re Algorithmen, um Schaltkreise von Quantencomputern zu optimieren.<\/p>\n","protected":false},"author":9,"featured_media":4646,"template":"","meta":{"_acf_changed":true,"footnotes":""},"blog-category":[1416,396],"blog-tag":[1485,1517,1527,1560,1584,1585],"class_list":["post-4641","blog","type-blog","status-publish","has-post-thumbnail","hentry","blog-category-alle-blogbeitraege","blog-category-forschung","blog-tag-evolutionaere-algorithmen","blog-tag-high-performance-computers-hpc-de","blog-tag-ki-in-der-physik","blog-tag-optimierung","blog-tag-quantencomputer","blog-tag-quantum-ml-de"],"acf":[],"publishpress_future_workflow_manual_trigger":{"enabledWorkflows":[]},"_links":{"self":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/blog\/4641","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/blog"}],"about":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/types\/blog"}],"author":[{"embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/users\/9"}],"version-history":[{"count":0,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/blog\/4641\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/media\/4646"}],"wp:attachment":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/media?parent=4641"}],"wp:term":[{"taxonomy":"blog-category","embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/blog-category?post=4641"},{"taxonomy":"blog-tag","embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/blog-tag?post=4641"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}Evolution\u00e4re Algorithmen<\/h2>\n\n\n\n
Evolution\u00e4re Optimierung von Quantenschaltkreisen<\/h2>\n\n\n\n
![\"-](\"https:\/\/lamarr-institute.org\/wp-content\/uploads\/evolution_img1-1-870x1024.jpg\" "\\"\\"")
Schematische Darstellung der Mutation eines Ausgangsquantenschaltkreises (links) und der resultierenden Nachkommen (rechts). Nachkommen entstehen durch Einf\u00fcgen, L\u00f6schen, Austauschen oder Ver\u00e4ndern von Gattern.<\/figcaption><\/figure>\n\n\n\n![\"-](\"https:\/\/lamarr-institute.org\/wp-content\/uploads\/evolution_img2-1-1024x887.jpg\" "\\"\\"")
Performanz des Evolution\u00e4ren Algorithmus\u2019 auf 10 Qubits, ausgef\u00fchrt auf mehreren Quantencomputern (farbige Linien) und simuliert (gestrichelte Linie).<\/figcaption><\/figure>\n\n\n\n
Gradient-free quantum optimization on NISQ devices <\/strong>Lukas Franken, Bogdan Georgiev, Sascha M\u00fccke, Moritz Wolter, Nico Piatkowski, Christian Bauckhage. Arxiv, 2020, PDF<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"