ME-Algorithmen

Eine Einführung in die M(aximum)-E(ntropie)-Algorithmen
mit Beispielen und Animationen

Teil 1 : Der Entropiebegriff
	mit einem kurzen Anhang über die Lagrangesche Multiplikatormethode zur Lösung von Optimierungsproblemen mit Nebenbedingungen

FGCZ-BrownBag, Mittwoch, 02. Juli 2008

Hansruedi Baetschmann
habae@fgcz.ethz.ch

Hansruedi Baetschmann
Interne Presentation Juni 2008

Definitionen der Entropie

Der Begriff Entropie wird in verschiedenen Wissensgebieten verwendet. Er ist in den verschiedenen Wissengebieten unterschiedlich definiert und hat dort je unterschiedliche Bedeutungen.

Entropie in der Physik (Thermodynamik)

Differentielle Entropieänderung dS eines geschlossenen Systems bei der differentiellen (wegabhängigen) Änderung δ𝒬 der Wärmeenergie bei der absoluten Temperatur T :

dS := ((Subscript[δQ, reversibel])/T)  (Dimension von S im MKS-System : [(Joule/Kelvin)])

Entropie in der Informationstheorie (Shannon)

Entropie H(X) eines diskreten gedächtnislosen Senders X, der zufällige und voneinander unabhängige  Zeichen (Subscript[z, i]) eines Alphabets Z mit je bestimmten Wahrscheinlichkeiten (Subscript[p, i]) aussendet :

			H(X):=-(∑_(i=1)^n)(Subscript[p, i])·(Subscript[log, 2])((Subscript[p, i]))    (dimensionslos)

Entropie in der Statistik :

Entropie H(𝒳) einer diskreten Zufallsvariablen 𝒳 mit dem Wertebereich {(Subscript[x, 1]),(Subscript[x, 2]),...,(Subscript[x, n])} und der Wahrscheinlichkeitsverteilung Prob{𝒳=(Subscript[x, i])} = (Subscript[p, i]), i=1...n :

			H(𝒳):=-(∑_(i=1)^n)(Subscript[p, i])·ln((Subscript[p, i]))    (dimensionslos)

Entropie H(𝒳) einer stetigen Zufallsvariablen 𝒳 mit dem Wertebereich [(Subscript[x, min]),(Subscript[x, max])] und der Wahrscheinlichkeits-dichteverteilung f(x) (zur Erinnerung = (d/dx)Prob{𝒳≤x} = (d/dx)F(x)) :

			H(𝒳):=-(∫_(Subscript[x, min])^(Subscript[x, max]))f(x)·ln(f(x))dx   (dimensionslos)

Zum Begriff der Entropie

Auf Grund der Definitionen scheint der Begriff Entropie in der Physik mit dem selben Begriff in der Informationstheorie und der Statistik nichts gemeinsam zu haben.

Auf Grund der Definitionen scheint der Begriff Entropie in der Informationstheorie und der Statistik sehr viel gemeinsam zu haben, bis auf einen Normierungsfaktor sogar derselbe zu sein.

Mittels der statistischen Physik konnte Bolzmann um 1880 herum einen Zusammenhang zwischen dem makroskopischen Entropiebegriff der Thermodynamik (siehe Definition) und dem Entropiebegriff der Informationstheorie und der Statistik herstellen.

Der Zusammenhang ergibt sich daraus, dass thermodynamische makroskopische Zustandsgrössen wie Temperatur etc. statistische Mittelwerte einer Vielzahl von Teilchen sind. Jedes dieser Teilchen befindet sich mit einer bestimmten Wahrscheinlichkeit in einem von vielen Mikrozuständen. (Siehe dazu folgendes Beispiel.)

In der Informationstheorie wird die Entropie meist unter Verwendung des Logarithmus zur Basis 2, in der Physik und Statistik meist unter Verwendung des natürlichen Logarithmus (d.h. zur Basis e) definiert.

Mit Logarithmen zu unterschiedlichen Basen definierte Entropien unterscheiden sich nur um einen konstanten Faktor. Die unterschiedlichen Definitionen sind somit gleichwertig.

Bespiel zur Entropie in der Themodynamik

Entropieänderung bei Volumenverdopplung

Von zwei benachbarten Würfeln mit je dem Volumen (Subscript[V, 0]) sei der linke mit N Teilchen eines idealen Gas gefüllt und der rechte sei leer (Vakuum). Die Temperatur des Gases sei (Subscript[T, 0]) = T und der Druck im rechten Würfel sei (Subscript[p, 0]). Nun werde die gemeinsame Trennwand bei konstanter Temperatur T langsam bis zum Anschlag auf der Gegenseite nach rechts verschoben. Im Endzustand erfüllt das Gas ein Volumen (Subscript[V, 1])=2(Subscript[V, 0]). Die Entropie des Systems im Anfangszustand sei (Subscript[S, 0]) und im Endzustand (Subscript[S, 1]). Wie gross ist die Entropieänderung ΔS=(Subscript[S, 1])-(Subscript[S, 0]) ?

Lösung

Bei einer infinitesimalen Vergrösserung des Volumens um dV ändert sich die Entropie um dS=((δQ)/T) .

Gemäss dem 1.Hauptsatz der Thermodynamik ist δQ=dU-δA, mit dU die infinitesimale Änderung der inneren Energie des Systems und -δA die infinitesimale nach aussen abgegebene Energie in Form von Arbeit.

Im betrachteten System ist dU=0 und -δA=-p·dV.

Aus der Zustandsgleichung p·V=(Subscript[k, Boltzmann])N ·T folgt p=(((Subscript[k, Boltzmann])N·T)/V).

Somit gilt : dS=((δQ)/T)=((dU-δA)/T)=((-δA)/T)=((p·dV)/T)=(((Subscript[k, Boltzmann])N·T)/(V·T))dV=(((Subscript[k, Boltzmann])N)/V)dV

Durch Integration folgt : ΔS=(∫_(Subscript[V, 0])^(Subscript[V, x]))(((Subscript[k, Boltzmann])N)/V)dV=(Subscript[k, Boltzmann])N·ln(((Subscript[V, x])/(Subscript[V, 0])))=(Subscript[k, Boltzmann])N·ln(2)

Damit ergibt sich für (Subscript[V, x])=(Subscript[V, 1])=2(Subscript[V, 0]) :  ΔS=(Subscript[k, Boltzmann])N·ln(((2(Subscript[V, 0]))/(Subscript[V, 0])))=(Subscript[k, Boltzmann])N·ln(2)

Bespiel zur Entropie in der statistischen Physik

Entropieänderung bei Zellenverdopplung

Das System Θ bestehe aus einer würfelförmigen Zelle Ω und N gleichartigen Teilchen. Die Zelle Ω sei in M (=(k^3) für irgend ein k∈ℕ) gleichgrosse, würfelförmige Teilzellen (Subscript[Ω, 1]),(Subscript[Ω, 2])...(Subscript[Ω, M]) aufgeteilt. Die N gleichartigen Teilchen (Subscript[α, 1]),(Subscript[α, 2])...(Subscript[α, N]) befinden sich zufällig im Raum Ω, aber so, dass sich in jeder Teilzelle (Subscript[Ω, i]) gleichviele Teilchen, nämlich (Subscript[n, i])=n Teilchen befinden. Somit gilt : M·n=N.

Die Wahrscheinlichkeit Prob{(Subscript[α, i])ϵ (Subscript[Ω, j])}, das sich ein Teilchen (Subscript[α, i]) in der Teilzelle (Subscript[Ω, j]) befindet, sei für alle Teilchen und alle Teilzellen gleich, nämlich (Subscript[p, i,j])=p . Somit gilt : Prob{(Subscript[α, i])ϵ (Subscript[Ω, j])}=(Subscript[p, i,j])=p=(1/M).

Es gibt unter diesen Bedingungen ((N!)/((Subscript[n, 1])!(Subscript[n, 2])!·...·(Subscript[n, M])!))= ((N!)/(((n!))^M)) = R Möglichkeiten die N Teilchen auf die M Teilzellen zu verteilen. Die Zelle Ω hat also R = ((N!)/(((n!))^M)) verschiedene gleichwahrscheinliche Zustände. Die Wahrscheinlichkeit für jeden dieser Zustände beträgt (1/R)=(1/((((N!)/(((n!))^M)))))=((((n!))^M)/(N!)) = r.

Das System Θ entspricht somit einer gleichverteilten Zufallsvariablen X mit einem Wertebereich, der den R=((N!)/(((n!))^M)) verschiedenen Systemzuständen entspricht. Deshalb lässt sich für das System Θ die statistische Entropie H(Θ) berechnen :

H(Θ) = H(X) = (Underoverscript[-∑, (     i=1), (     R)])(1/R)ln((1/R))=-ln((1/R))=ln(R)=ln(((N!)/(((n!))^M)))=ln(N!)-M·ln(n!)

Entropieänderung bei Zellenverdopplung (Fortsetzung)

H(Θ) = H(X) = (Underoverscript[-∑, (     i=1), (     R)])(1/R)ln((1/R))=-ln((1/R))=ln(R)=ln(((N!)/(((n!))^M)))=ln(N!)-M·ln(n!)

Für x > 1000 gilt :	ln(x!) ≈ x·ln(x)-x 	(mit einem relativen Fehler < 1%)

Mit dieser Approximation gilt nun :

H(Θ)=H(X)=ln(N!)-M·ln(n!)≈(N·ln(N)-N)-M·(n·ln(n)-n)=N·ln(N)-N-N·ln(n)+N= 
       =N·(ln(N)-ln(n))=N·(ln(N)-ln((N/M)))=N·(ln(N)-ln(N)+ln(M))=N·ln(M)=-N·ln((1/M))=-N·ln(p)

Für jedes der Teilchen (Subscript[α, i]) lässt sich ebenfalls die statistische Entropie H((Subscript[α, i]))=H(α) berechnen :

H(α) = (Underoverscript[-∑, (i=1), M])p·ln(p)=(Underoverscript[-∑, (i=1), M])(1/M)·ln(p)=-ln(p)

Es gilt also (approximativ) : H(Θ) = -N·ln(p)= N·H(α)=(∑_(i=1)^N)H((Subscript[α, i]))

Die Entropie des Systems Θ ist die Summe der Entropie seiner N darin befindlichen Teilchen (Subscript[α, i]).

Das heisst mit anderen Worten, dass sich das System Θ, bei welchem die N Teilchen ja nicht völlig unabängig sind, sondern über die Bedingung der homogenen Teilzellenbesetzung voneinander abhängig sind, bereits für relativ kleine Teilchenzahlen (N>1000) wie ein System (Subscript[Θ, unabhängig]) verhält, bei welchem die N Teilchen völlig unabhängig voneinander sind, ihre Verteilung also durch keine Homogenitätsbedingungen mehr eingeschränkt sind. (Für die statistische Entropie gilt die Additivität H(X,Y)=H(X)+H(Y), falls die Zufallsvariabeln X und Y unabhängig sind.)

Die Analogie zum Beispiel Volumenverdopplung aus der Thermodynamik

Die Analogie des Systems Θ zu einer in einem Würfel mit dem Volumen V eingeschlossenen und aus N Teilchen bestehenden Menge eines idealen Gases ist offensichtlich. Der Homogenitätsbedingung für das System Θ entspricht beim idealen Gas die Eigenschaft, dass es im Würfel mit dem Volumen V homogen verteilt ist. Wenn der Würfel in mehrere gleiche Teilwürfel aufgeteilt gedacht wird, dann befindet sich jedes Gasteilchen über die Zeit betrachtet gleich oft (gleich lang) in jedem Teilwürfel. Die Wahrscheinlichkeit, zu einem beliebig gewählten Zeitpunkt ein bestimmes Gasteilchen in einem bestimmten Teilwürfel zu finden, ist für jedes Gasteilchen und jeden Teilwürfel gleich.

Analogie zur Volumenausdehnung

Der würfelförmigen Zelle Ω mit M = (k^3) Teilzellen werden k mal schrittweise neue 1-Teilzelle-dicke Schichten mit (k^2) Teilzellen angefügt bis die Zelle (SuperStar[Ω]) ein Quader der doppelten ursprünglichen Grösse ist und aus  (k^3)+k·(k^2)=2(k^3)=2M Teilzellen besteht.

Für die Wahrscheinlichkeit (Subscript[p, i,j]^( * )) eines Teilchens (Subscript[α, i]) sich in der Teilzelle (Subscript[Ω, j]^( * )), j=1...2M zu befinden gilt somit : (Subscript[p, i,j]^( * ))=(SuperStar[p])=(1/(2M)).

Der Analogie zum therodynamischen Modell entsprechend müsste die Entropie des Systems (SuperStar[Θ]) gegenüber der Entropie des Systems Θ um einen zu N·ln(2) proportionalen Betrag ΔH zugenommen haben.

Analogie zur Volumenausdehnung (Fortsetzung)

Für das System Θ gilt : H(Θ) = N·(Subscript[H, Θ])(α)=-N·ln(p)=-N·ln((1/M))

Für das System (SuperStar[Θ]) gilt : H((SuperStar[Θ])) = N·(Subscript[H, (SuperStar[Θ])])(α)=-N·ln((SuperStar[p]))=-N·ln((1/(2M)))=-N·(ln((1/M))+ln((1/2)))=-N·ln((1/M))+N·ln(2)

Damit ergibt sich :
			 ΔH=H((SuperStar[Θ]))-H(Θ)=(-N·ln((1/M))+N·ln(2))-N·ln((1/M))=N·ln(2)

Für ein System (Subscript[, λ])Θ mit (Subscript[, λ])M = λ·M Teilzellen gilt allgemeiner für ΔH als Funktion von (((Subscript[, λ])M)/M)=((λ·M)/M)=λ :

ΔH(λ)=H((Subscript[, λ])Θ)-H(Θ)=(-N·ln((1/M))-N·ln(λ))-N·ln((1/M))-(-N·ln((1/M))-N·ln(λ))=N·ln(λ)

Weitere Bemerkungen zum Entropiebegriff

Die Entropie kann sowohl in der Physik, wie auch in der Informationstheorie und der Statistik als Mass für die Ungewissheit verstanden werden.

In der Physik ist die Entropie eines Systems ein Mass für die Ungewissheit darüber, in welchem Mikrozustand (also die Gesamtheit der Zustände der einzelnen Atome, Moleküle, etc.) sich das System vor einer Beobachtung befindet.

In der Informationstheorie ist die Entropie eines Senders ein Mass für die Ungewissheit darüber, welches Zeichen der Sender als nächstes Zeichen senden wird.

In der Statistik ist die Entropie einer Zufallsvariablen ein Mass für die Ungewissheit darüber, welchen Wert eine Realisation der Zufallsvariablen annehmen wird, oder anders formuliert, welches Ereignis bei der einmaligen Ausführung eines Zufallsexperiments eintreten wird.

Grundsätzlich gilt für die Entropie ceteris paribus (d.h. unter Konstanthaltung der übrigen Variablen und Beibehaltung oder sinngemässer Anpassung der übrigen Randbedingungen, z.B. 'Form' der Verteilung ) :

In der Physik : Je mehr mögliche Zustände des Gesamtsystems, (z.B. mehr mögliche Zustände der Einzelteilchen, mehr Teilchen), desto höher die Entropie

In der Informationstheorie : Je höher der Zeichenvorrat, desto höher die Entropie

In der Statistik : Je grösser der Wertebereich der Zufallsvariablen, desto höher die Entropie, oder anders formuliert, je mehr mögliche Ereignisse eines Zufallsexperiments, desto höher die Entropie

In allen drei Bereichen : Je 'gleichmässiger' die Wahrscheinlichkeitsverteilung, desto höher die Entropie.

Entropie eines Zustandes oder Ereignisses ?

Es ist falsch, von der Entropie eines einzelnen Zustandes oder eines einzelnen Ereignisses (Subscript[x, i]) zu sprechen. Ein einzelner Zustand oder ein einzelnes Ereignis (Subscript[x, i]) aus einer (endlichen oder unendlichen) Menge {(Subscript[x, 1]),(Subscript[x, 2])...} von möglichen Zuständen oder Ereignissen hat keine Entropie, obwohl sich für einen bestimmten Zustand oder ein bestimmtes Ereignis (Subscript[x, i]), dessen Wahrscheinlichkeit Prob{(Subscript[x, i]) tritt ein} = p((Subscript[x, i])) > 0 bekannt ist, der Ausdruck
Q((Subscript[x, i])) = p((Subscript[x, i]))·ln(p((Subscript[x, i]))) berechnen lässt.

Bei der Betrachtung eines einzelnen zufälligen Zustandes oder eines einzelnen zufälligen Ereignisses (Subscript[x, i]) als Realisation einer Zufallsvariablen 𝒳 ist es nur sinnvoll, von der Entropie E(𝒳) zu sprechen. Gemäss der Definition der Entropie liefert ein einzelner Zustand oder ein einzelnes Ereignis (Subscript[x, i]) einen Beitrag p((Subscript[x, i]))·ln(p((Subscript[x, i]))) zu dieser Entropie.

(Ersetze in den beiden oberen Aussagen, den Begriff 'Entropie' z.B. durch den Begriff 'Erwartungswert', um die Sinnlosigkeit, von der Entropie eines einzelnen zufälligen Zustandes oder Ereignisses zu sprechen, zu verstehen.)

Ein System, welches nur einen einzigen Zustand annehmen kann, oder eine (entartete) Zufallsvariable, welche nur einen einzigen Wert annehmen kann (Experiment mit nur einem möglichen Ausgang, (der sicher eintritt)), haben die Entropie 0.

Masse der Ungewissheit

Die Wahrscheinlichkeit (Subscript[p, i]) = p((Subscript[x, i])) eines einzelnen Wertes (Subscript[x, i]) einer diskreten Zufallsvariablen 𝒳 mit möglichen Werten (Subscript[x, i]), i=1,2...  ist ein Mass für die Ungewissheit, dass diese Zufallsvariable den Wert (Subscript[x, i]) annimmt. (Ein besseres Mass für die Ungewissheit ist eigentlich 1-(Subscript[p, i]), weil mit zunehmendem (Subscript[p, i]) die Ungewissheit für das Annehmen des entsprechenden Wertes (Subscript[x, i]) abnimmt.) Da die Summe  S(𝒳)=(Subscript[p, 1])+(Subscript[p, 2])+...=(∑_i)((Subscript[p, i]))=1 ist, eignet sich S(𝒳) nicht als Mass für die Ungewissheit , welche in der entsprechenden Zufallsvariablen (also in einem gewissen Sinne der Menge aller ihrer möglichen Werte {(Subscript[x, 1]),(Subscript[x, 2]),...} steckt.

Das Produkt P(𝒳)=(Subscript[p, 1])·(Subscript[p, 2])·...=(∏_i)((Subscript[p, i])) eignet sich ebenfalls nicht als Mass der Ungewissheit, welche in der Zufallsvariablen 𝒳 steckt, weil das Produkt P(𝒳) bereits dann gegen 0 strebt, wenn nur ein einzelnes (Subscript[p, i]) gegen 0 strebt.
(Beispiel : Mit dem Produkt P(𝒳) als Mass für die Ungewissheit würde einem Würfel, welcher mit zunehmendem Gebrauch beim Werfen die Augenzahl '6' immer seltener und und die anderen Augenzahlen etwa gleich oft zeigt, eine gegen 0 gehende Ungewissheit (lim_((Subscript[p, i])->(1/5),i=1⃛ 5))((Subscript[p, 1])·(Subscript[p, 2])·(Subscript[p, 3])·(Subscript[p, 4])·(Subscript[p, 5]))·(lim_((Subscript[p, 6])->0))((Subscript[p, 6])) = (1/5)·(1/5)·(1/5)·(1/5)·(1/5)·0=0 zugesprochen, was wenig einleuchtend ist.)

Weil  (lim_(x->0))(-x·ln(x))=0 ist "siehe Graph der Funktion", eignet sich der Ausdruck H(𝒳) = -(∑_i)(Subscript[p, i])·ln((Subscript[p, i])) besonders gut als Mass für die Ungewissheit einer Zufallsvariablen 𝒳.
(Beispiel : Im obigen Fall des Würfels wird diesem eine gegen -ln((1/5)) = ln(5) gehende Ungewissheit -((lim_((Subscript[p, i])->(1/5),i=1⃛ 5))((Subscript[p, 1])·ln((Subscript[p, 1]))+(Subscript[p, 2])·ln((Subscript[p, 2]))+(Subscript[p, 3])·ln((Subscript[p, 3]))+(Subscript[p, 4])·ln((Subscript[p, 4]))+(Subscript[p, 5])·ln((Subscript[p, 5])))+(lim_((Subscript[p, 6])->0))((Subscript[p, 6])·ln((Subscript[p, 6]))))=-(5·((1/5)·ln((1/5)))+0)=-ln((1/5)), was gerade die Entropie eines 5 seitigen, gleichmässigen 'Würfels' ist.)

So wie die Wahrscheinlichkeit (Subscript[p, i]) eines einzelnen Wertes (Subscript[x, i]) einer diskreten Zufallsvariablen 𝒳 ein multiplikatives Mass für die Ungewissheit des Wertes (Subscript[x, i]) ist, ist die Entropie H(𝒳) der Zufallsvariablen 𝒳 ein additives Mass für die Ungewissheit dieser Zufallsvariablen 𝒳.

Denn für zwei unabhängige Zufallsvariabeln 𝒳 und 𝒴 gilt 
	für die Wahrschenlichkeiten : 			Prob{𝒳=(Subscript[x, i]),𝒴=(Subscript[y, j])}	=	Prob{𝒳=(Subscript[x, i])}·Prob{𝒴=(Subscript[y, j])}
	für die Entropien :			       		H(𝒳,𝒴)		=	       H(𝒳)      +     H(𝒴)

"zurück"

Maximum-Entropie-Algorithmen und das Maximum-Entropie-Prinzip

Mit Maximum-Entropie-Algorithmen werden verschiedene problemspezifische Algorithmen, die alle dem selben Maximierungsprinzip genügen, bezeichnet. Ein Beispiel ist der iterative Scaling-Algorithmus.

Gemäss dem Maximum-Entropie-Prinzip wird bei einem statistischen Problem mit einer nicht vollständig bekannten 1-oder mehrdimensionalen Zufallsvariablen 𝔛 in der Menge jene mit dem gegebenen Wissen über 𝔛 verträgliche Lösung (Subscript[𝔛, MaxEntropie]) für diese Zufallsvariable gesucht, welche in unter allen möglichen verträglichen Lösungen {𝔛

Allgemeine Problemstellung

Gegeben ist eine statistische Problemsituation mit einer nicht vollständig bekannten 1-oder mehrdimensionalen Zufallsvariablen 𝔛 und gewissen Rahmenbedingungen ℜ. 𝔛 kann vollständig unbekannt sein. Oder es können gewisse Momente, wie etwa Erwartungswert oder Varianz, der Zufallsvariblen 𝔛 bekannt sein. Es können auch eine Menge von Beobachtungen (Realisationen) (Subscript[(OverHat[x]), 1]),(Subscript[(OverHat[x]), 2]),... ,(Subscript[(OverHat[x]), n ]) von 𝔛 vorliegen. Es kann auch nur der Wertebereich von 𝔛 bekannt sein. Das Wissen über 𝔛 sei mit 𝔚 bezeichnet.

Es sei Ψ die Menge aller mit mit dem gegebenen Wissen 𝔚 und den Rahmenbedingungen ℜ verträglichen Zufallsvariablen. Ψ = { 𝔛 | 𝔛 ist verträglich mit 𝔚 und ℜ}. Gemäss dem Maximum-Entropie-Prinzip wird nun in der Menge Ψ aller mit 𝔚 und ℜ verträglichen Zufallsvariablen 𝔛 jene Zufallsvariable (Subscript[𝔛, MaxEntropie]) gesucht, welche die maximale Entropie hat.

Der Maximum-Entropie-Prinzip liegt die Idee zu Grunde, die Menge der Lösungskandidaten für 𝔛 möglichst gross zu halten und für die Lösung keine Zusatzannahmen zu treffen, welche über das Wissen über 𝔛 hinausgehen. Eine Lösung (Subscript[𝔛, MaxEntropie]) gemäss dem Maximum-Entropie-Prinzip ist also eine Lösung mit der grösst möglichen Zufälligkeit.

Zum Vergleich : Bei einer Lösung gemäss dem Maximum-Likelihood-Prinizip liegt ein statistisches Problem mit einer nicht vollständig bekannten Zufallsvariablen 𝔛 und einer Beobachtung 𝔅 vor. Es wird nun in der Menge Φ aller mit 𝔅 verträglichen Zufallsvariabeln 𝔛 jene Zufallsvariable (Subscript[𝔛, MaxLieklihood]) gesucht, sodass Prob{𝔛=𝔅} maximal ist.

Maximum-Entropie-Algorithmen sind Maximierungsalgorithmen. Sie verwenden Methoden der Differential- und Integralrechnung, speziell die Lagrangesche Multiplikatorenmethode zur Lösung von Optimierungsproblemen mit Nebenbedingungen.

Beispiele von einfachen Problemstellungen

Beispiel 1 : In einer Urne befinden sich ein bestimmte, unbekannte Anzahl n>2 von roten und schwarzen Kugeln. Welches ist das Mischungsverhältnis der Kugeln mit der 'grössten Zufälligkeit' beim Ziehen einer Kugel ?

Dieses Beispiel 1 ist einführend und zeigt, wie eine statistische Problemstellung ohne Beoachtungswerte nach dem Maximum-Entropie-Prinzip dennoch gelöst werden kann.

Beispiel 2 : Die In einer Urne befinden sich ein bestimmte, unbekannte Anzahl n>2 von roten und schwarzen Kugeln. Beim zufälligen Ziehen von total 5 Kugeln werden 2 rote und 3 schwarze Kugeln gezogen. Welches ist das Mischungsverhältnis der Kugeln mit der 'grössten Zufälligkeit' beim Ziehen einer Kugel ?

Dies ist ebenfalls ein einführendes und sehr einfaches Beispiel. Es kann auch nach anderen Prinzipien und mit anderen Methoden gelöst werden (z.B. nach dem Maximum-Likelihood-Prinzip, mit Erwartungswert-Maximierungs-Algorithmen) und ergeben in diesen Fällen das selbe Resultat.

Beispiel 3 : Bei der Kontrolle des Gewichts von Zweipfündern (Brot) wird eine durchschnittliche Abweichung von -4 g und eine Standardabweichung von 7 g festgestellt. Mit welcher Verteilung sollen die Abweichungen beschrieben werden, wenn sie die 'grösst mögliche Zufälligkeit' aufweisen sollen ?

Beispiel 3 ist immer noch verhältnismässig einfach und zeigt, wie eine statistische Problemstellung ohne die urpsrünglichen Beoachtungswerte, sondern nur auf   der Basis von Momenten nach dem Maximum-Entropie-Prinzip gelöst werden kann.

Beispiel 4 : Die Temperatur eines Gases beträgt 300°Kelvin. Mit welcher Vereilung soll die Geschwindigkeit der Gasmoleküle beschrieben werden, wenn diese Verteilung die 'grösst mögliche Zufälligkeit' aufweise soll ?

Diese letzte Beispiel ist von der Problemsituation ähnlich wie Bespiel 3, da die Temperatur eine makroskopische Grösse ist, die sich als Mittelwert mikroskopischer Eigenschaften , nämlich der Molekülgeschwindigkeit (resp. der kinetischen Energie der Gasmoleküle) erklären lässt.

Die Lagrangesche Multiplikatormethode

({{Allgemein

Gegeben
 - Eine Funktion f((Subscript[x, 1]),(Subscript[x, 2]),...,(Subscript[x, n]))
 - Eine Menge {(Subscript[B, 1]),(Subscript[B, 2]),...,(Subscript[B, r])}von r Nebenbedingungen an
     die Variabeln (Subscript[x, 1]),(Subscript[x, 2]),...,(Subscript[x, n]) in Form von Gleichungen:
     (Subscript[B, 1]) : (Subscript[g, 1])((Subscript[x, 1]),(Subscript[x, 2]),...,(Subscript[x, n]))=0
     (Subscript[B, 2]) : (Subscript[g, 2])((Subscript[x, 1]),(Subscript[x, 2]),...,(Subscript[x, n]))=0 
     ...
     (Subscript[B, r]) : (Subscript[g, r])((Subscript[x, 1]),(Subscript[x, 2]),...,(Subscript[x, n]))=0

Gesucht :((Subscript[(OverHat[x]), 1]),(Subscript[(OverHat[x]), 2]),...,(Subscript[(OverHat[x]), n])) so, dass
- f((Subscript[(OverHat[x]), 1]),(Subscript[(OverHat[x]), 2]),...,(Subscript[(OverHat[x]), n]))maximal ist
- die Bedingungen (Subscript[B, 1]),(Subscript[B, 2]),...,(Subscript[B, r]) für ((Subscript[(OverHat[x]), 1]),(Subscript[(OverHat[x]), 2]),...,(Subscript[(OverHat[x]), n])) erfüllt
    sind
Ansatz : Maximiere die neue FunktionL((Overscript[x, ->]),(Overscript[λ, ->])) =
     L((Subscript[x, 1]),(Subscript[x, 2]),...,(Subscript[x, n]),(Subscript[λ, 1]),(Subscript[λ, 2]),...,(Subscript[λ, r])):=
		         f((Subscript[x, 1]),(Subscript[x, 2]),...,(Subscript[x, n])) +
		(Subscript[λ, 1])·(Subscript[g, 1])((Subscript[x, 1]),(Subscript[x, 2]),...,(Subscript[x, n])) +
		(Subscript[λ, 2])·(Subscript[g, 2])((Subscript[x, 1]),(Subscript[x, 2]),...,(Subscript[x, n])) +
		...                                    +
		(Subscript[λ, r])·(Subscript[g, r])((Subscript[x, 1]),(Subscript[x, 2]),...,(Subscript[x, n]))

Lösung : Differenziere die FunktionL((Overscript[p, ->]),(Overscript[λ, ->])) nach allen
     (n+r) Variabeln, setze die (n+r) partiellen Ableitungen
     gleich 0 und löse das so entstandene Gleichungssystem
     nach den (n+r) Unbekannten.
(({{((∂L((Subscript[x, 1]),...,(Subscript[x, n]),(Subscript[λ, 1]),...(Subscript[λ, r])))/(∂(Subscript[x, 1])))=0}, {...}, {((∂L((Subscript[x, 1]),...,(Subscript[x, n]),(Subscript[λ, 1]),...(Subscript[λ, r])))/(∂(Subscript[x, n])))=0}, {((∂L((Subscript[x, 1]),...,(Subscript[x, n]),(Subscript[λ, 1]),...(Subscript[λ, r])))/(∂(Subscript[λ, 1])))=0}, {...}, {((∂L((Subscript[x, 1]),...,(Subscript[x, n]),(Subscript[λ, 1]),...(Subscript[λ, r])))/(∂(Subscript[λ, r])))=0}}))  Gleichungssystem, Beispiel

Gegeben
- die Funktion H((Subscript[p, 1]),(Subscript[p, 2])):=-((Subscript[p, 1])ln((Subscript[p, 1]))+(Subscript[p, 2])ln((Subscript[p, 2])))
- eine Bedingung(Subscript[B, 1]):

     (Subscript[B, 1]) : ((Subscript[p, 1])ln((Subscript[p, 1]))+(Subscript[p, 2])ln((Subscript[p, 2]))-1)=0




Gesucht : ((Subscript[(OverHat[p]), 1]),(Subscript[(OverHat[p]), 2])) so dass
- H((Subscript[(OverHat[p]), 1]),(Subscript[(OverHat[p]), 2])) = -((Subscript[(OverHat[p]), 1])ln((Subscript[(Overscript[(OverHat[p]),  ]), 1]))+(Subscript[(OverHat[p]), 2])ln((Subscript[(OverHat[p]), 2]))) maximal ist
- (Subscript[B, 1]) : ((Subscript[(OverHat[p]), 1])+(Subscript[(OverHat[p]), 2])-1)=0 erfüllt ist

Ansatz : Maximiere die neue Funktion L((Overscript[p, ->]),(Overscript[λ, ->])) =
L((Subscript[p, 1]),(Subscript[p, 2]),(Subscript[λ, 1])):=
	   - ((Subscript[p, 1])ln((Subscript[p, 1]))+(Subscript[p, 2])ln((Subscript[p, 2])))+
	(Subscript[λ, 1])·((Subscript[p, 1])+(Subscript[p, 2])-1)

			"siehe Graph der Lagrange-Hilfsfunktion"
			"siehe Grafik zur Lagrange-Maximierungsmethode"

Lösung :



(({{((∂L((Subscript[p, 1]),(Subscript[p, 2]),(Subscript[λ, 1])))/(∂(Subscript[p, 1])))=0}, {((∂L((Subscript[p, 1]),(Subscript[p, 2]),(Subscript[λ, 1])))/(∂(Subscript[p, 2])))=0}, {((∂L((Subscript[p, 1]),(Subscript[p, 2]),(Subscript[λ, 1])))/(∂(Subscript[λ, 1])))=0}}))=(({{-ln((Subscript[p, 1]))-1+(Subscript[λ, 1])=0}, {-ln((Subscript[p, 2]))-1+(Subscript[λ, 1])=0}, {      (Subscript[p, 1])+(Subscript[p, 2])-1      =0}}))
=>
 ((Subscript[(OverHat[p]), 1]),(Subscript[(OverHat[p]), 2]),(Subscript[(OverHat[λ]), 1]))=((1/2),(1/2),1+ln((1/2)))=((1/2),(1/2),1-ln(2))}})

"zurück"

"zurück"