Product Design, Manufacturing & Innovation Resources

Heim » Metropolis-Hastings-Algorithmus

Metropolis-Hastings-Algorithmus

1970

Nicholas Metropolis
Arianna W. Rosenbluth
Marshall N. Rosenbluth
Augusta H. Teller
Edward Teller
W. Keith Hastings

(Abbildung dient nur zur Veranschaulichung)

Der Metropolis-Hastings-Algorithmus ist ein prominenter MCMC Verfahren Das Verfahren dient dazu, eine Folge von Zufallsstichproben aus einer Wahrscheinlichkeitsverteilung zu gewinnen, für die eine direkte Stichprobenziehung schwierig ist. In jeder Iteration wird basierend auf der aktuellen Stichprobe ein Kandidat für die nächste Stichprobe generiert. Dieser Kandidat wird dann mit einer bestimmten Wahrscheinlichkeit akzeptiert oder verworfen, wodurch sichergestellt wird, dass die resultierende Kette gegen die gewünschte Verteilung konvergiert.

The algorithm works by constructing a Markov chain whose stationary distribution is the target distribution [latex]P(x)[/latex]. Let the current state be [latex]x_t[/latex]. First, a candidate state [latex]x'[/latex] is generated from a proposal distribution [latex]Q(x’|x_t)[/latex], which can be any distribution that is easy to sample from (e.g., a Gaussian centered at [latex]x_t[/latex]). Second, an acceptance probability [latex]\alpha(x’, x_t)[/latex] is calculated: [latex]\alpha(x’, x_t) = \min\left(1, \frac{P(x’)Q(x_t|x’)}{P(x_t)Q(x’|x_t)}\right)[/latex]. A random number [latex]u[/latex] is drawn from a uniform distribution on [latex][0, 1][/latex]. If [latex]u \le \alpha[/latex], the candidate is accepted, and the next state is set to [latex]x_{t+1} = x'[/latex]. Otherwise, the candidate is rejected, and the chain remains at the current state, [latex]x_{t+1} = x_t[/latex].

Die Genialität dieses Akzeptanzverhältnisses liegt darin, dass es lediglich die Kenntnis von [latex]P(x)[/latex] bis auf eine Proportionalitätskonstante erfordert, da sich jede Normierungskonstante im Bruch [latex]frac{P(x’)}{P(x_t)}[/latex] aufhebt. Dies ist in der Bayes'schen Statistik von entscheidender Bedeutung, da die A-posteriori-Verteilung oft nur bis auf die schwer zu berechnende Randwahrscheinlichkeit bekannt ist. Der ursprüngliche Metropolis-Algorithmus (1953) ist ein Spezialfall, in dem die Vorschlagsverteilung [latex]Q[/latex] symmetrisch ist, d. h. [latex]Q(x’|x_t) = Q(x_t|x’)[/latex], wodurch sich die Akzeptanzwahrscheinlichkeit zu [latex]minleft(1, frac{P(x’)}{P(x_t)}right)[/latex] vereinfacht. Hastings’ Die Verallgemeinerung von 1970 erlaubte asymmetrische Vorschlagsverteilungen und erweiterte damit die Anwendbarkeit und Effizienz des Algorithmus erheblich.

Algorithmen, Versuchsplanung (Design of Experiments, DOE), Monte-Carlo-Simulation, Qualitätsmanagement, Simulation, Statistische Analyse, Statistische Prozesskontrolle (SPC)

UNESCO Nomenclature: 1209

- Statistik

Typ

Software/Algorithmus

Störung

Wesentliche

Verwendung

Weitverbreitete Verwendung

Vorläufer

Metropolis-Algorithmus (1953)
Theorie des detaillierten Gleichgewichts in Markov-Ketten
Monte-Carlo-Integration
Bayes'sche Wahrscheinlichkeitstheorie

Anwendungen

Simulation der Boltzmann-Verteilung in der statistischen Mechanik
Bayes'sche Inferenz im maschinellen Lernen
Lösung komplexer Optimierungsprobleme mittels simulierter Abkühlung
Computergestützte Finanzmathematik für die Risikomodellierung
Signalverarbeitung und Bildrekonstruktion

Patente:

Potenzielle Innovationsideen

Aufgrund des hohen Datenverkehrs durch Web-Scraping-Bots, der derzeit mehr als 40.000 Anfragen pro Tag umfasst, ist dieser Inhalt ausschließlich Community-Mitgliedern vorbehalten.
> Anmelden < oder > Registrieren < (100% kostenlos) Zugriff darauf sowie auf alle anderen eingeschränkten Inhalte und Tools.

Verwandt mit: Metropolis-Hastings, MCMC, Bayes'sche Statistik, Akzeptanz-Ablehnung, Vorschlagsverteilung, stationäre Verteilung, Markov-Kette, Stichprobenverfahren, statistische Mechanik, simuliertes Ausglühen.

Historischer Kontext

Logistische Regression

Ein Regressionsmodell für eine kategoriale, in der Regel binäre, abhängige Variable. Anstatt das Ergebnis direkt zu modellieren, wird die Wahrscheinlichkeit des Ergebnisses mithilfe der logistischen (sigmoiden) Funktion modelliert. Das Modell sagt die Log-Wahrscheinlichkeit des Ereignisses als lineare Kombination der unabhängigen Variablen voraus: [latex]\ln(\frac{p}{1-p}) = \beta_0 + \beta_1 x_1 + \dots + \beta_p x_p[/latex], wobei p die Wahrscheinlichkeit des Ereignisses ist.

Arbeitsbereich für die Computerprogrammierung, in dem objektorientierte Programmierkonzepte vorgestellt werden.

Das Objekt in OOP (Programmierung)

In der objektorientierten Programmierung (OOP) ist ein Objekt eine grundlegende Einheit, die Daten (Attribute oder Eigenschaften) und die Methoden (Funktionen oder Prozeduren), die diese Daten verarbeiten, bündelt. Objekte sind Instanzen von Klassen, die als Blaupausen fungieren. Dieses Paradigma modelliert reale Entitäten und erleichtert die Verwaltung komplexer Systeme, indem verwandte Zustände und Verhaltensweisen in eigenständigen Einheiten zusammengefasst werden.

Arbeitsbereich für Computerprogrammierung zur Demonstration von Polymorphismus mit Codeschnipseln.

Polymorphismus (Programmierung)

Polymorphismus, griechisch für „viele Formen“, ermöglicht es, Objekte verschiedener Klassen als Objekte einer gemeinsamen Oberklasse zu behandeln. Er ermöglicht die Verwendung einer einzigen Schnittstelle, beispielsweise eines Methodennamens, für eine allgemeine Klasse von Aktionen. Die konkrete Aktion wird zur Laufzeit durch den genauen Typ des Objekts bestimmt. Dies wird häufig durch das Überschreiben von Methoden erreicht.

Metropolis-Hastings-Algorithmus

Softwareentwickler, der abstrakte Klassen in einer modernen IDE-Umgebung programmiert.

Abstraktion (OOP-Programmierung)

Abstraktion in der OOP ist das Konzept, komplexe Implementierungsdetails zu verbergen und nur die wesentlichen Merkmale des Objekts anzuzeigen. Der Fokus liegt auf der Funktion eines Objekts, nicht auf der Art und Weise, wie es diese Funktion ausführt. Dies wird durch abstrakte Klassen und Schnittstellen erreicht, die einen Entwurf für andere Klassen definieren, ohne eine vollständige Implementierung bereitzustellen, wodurch komplexe Systeme vereinfacht werden.

Ingenieure, die die sieben grundlegenden Qualitätswerkzeuge in einem Workshop zur Prozessverbesserung verwenden.

Sieben grundlegende Werkzeuge der Qualität

Die sieben grundlegenden Werkzeuge der Qualität sind eine Reihe grafischer Techniken, die von Kaoru Ishikawa zur Behebung qualitätsrelevanter Probleme entwickelt wurden. Diese Werkzeuge sind: Ursache-Wirkungs-Diagramm (Fischgrätendiagramm), Prüfblatt, Kontrolldiagramm, Histogramm, Pareto-Diagramm, Streudiagramm und Schichtung (oft als Flussdiagramm dargestellt). Sie gelten als „grundlegend“, da sie einfach anzuwenden sind und nur wenig Statistikkenntnisse erfordern.

Softwareentwicklungsbüro, das die Prozessphasen des Wasserfallmodells vorstellt.

Das Wasserfallmodell (Software)

Das Wasserfallmodell ist ein sequenzieller, nicht-iterativer Softwareentwicklungsprozess, bei dem der Fortschritt (wie ein Wasserfall) stetig nach unten fließt und verschiedene Phasen durchläuft: Konzeption, Initiierung, Analyse, Design, Konstruktion, Test, Bereitstellung und Wartung. Jede Phase muss vollständig abgeschlossen sein, bevor mit der nächsten fortgefahren werden kann. Es wird oft iterativen Modellen gegenübergestellt, um deren Flexibilität hervorzuheben.

1960

1967

1970

1970-01-01

1960

1967

1970

1973

CNC-Maschine mit G-Code-Programmierung in einer modernen Werkstattumgebung.

G-Code: Die Standard-CNC-Programmiersprache

G-Code, früher bekannt als RS-274, ist die am weitesten verbreitete Programmiersprache zur Steuerung von CNC-Maschinen. Er besteht aus sequentiellen Befehlen, die der Maschine Anweisungen zu Positionierung, Geschwindigkeit und bestimmten Aktionen geben. Befehle beginnen mit einer Buchstabenadresse; „G“ steht für vorbereitende Befehle für die Bewegung (z. B. G01 für linearen Vorschub), während „M“ für verschiedene Funktionen steht (z. B. M03 für den Spindelstart).

Informatiker bei der automatisierten Theorembeweisführung in einem Büro der 1960er Jahre.

Automatisiertes Theorembeweisen (ATP)

Automatisiertes Beweisen (ATP) ist ein Teilgebiet der Informatik und mathematischen Logik, das sich mit dem Beweisen mathematischer Theoreme mithilfe von Computerprogrammen befasst. ATP-Systeme, auch Beweiser genannt, nutzen logisches Schließen, um neue Theoreme aus Axiomen und Hypothesen abzuleiten. Sie unterscheiden sich von Beweisassistenten, die mehr menschliche Unterstützung benötigen, obwohl es erhebliche Überschneidungen zwischen den beiden Bereichen gibt.

Programmierer, der in einem modernen Büro die Vererbung in der objektorientierten Programmierung kodiert.

Vererbung (OOP-Programmierung)

Vererbung ist ein Mechanismus in der OOP, bei dem eine neue Klasse (Unterklasse oder abgeleitete Klasse) auf einer bestehenden Klasse (Oberklasse oder Basisklasse) basiert und deren Attribute und Methoden erbt. Dies unterstützt die Wiederverwendbarkeit von Code und schafft eine natürliche Hierarchie zwischen Klassen. Die Unterklasse kann das geerbte Verhalten erweitern oder überschreiben, was spezifischere Implementierungen unter Beibehaltung einer gemeinsamen Schnittstelle ermöglicht.

Software-Ingenieur, der statische Überprüfungen mit Code-Analyse-Tools in der Informatik durchführt.

Statische vs. dynamische Verifizierung (IT)

Die Verifizierungstechniken werden allgemein als statisch oder dynamisch klassifiziert. Bei der statischen Überprüfung (oder statischen Analyse) wird der Code oder das Design des Systems untersucht, ohne es auszuführen. Beispiele hierfür sind Code-Reviews, Inspektionen und automatische statische Analysetools. Bei der dynamischen Überprüfung (oder dem Testen) wird das System mit einer Reihe von Eingaben ausgeführt und sein Verhalten beobachtet, um Fehler zu finden. Beide Verfahren ergänzen sich für eine umfassende Qualitätssicherung.

Risikobewertungssitzung mit Ingenieuren, die die Risikoprioritätszahlen in einem professionellen Büro analysieren.

Risikoprioritätsnummer (RPN)

Die Risikoprioritätszahl (RPZ) ist ein quantitatives Maß, das in der FMEA zur Priorisierung von Risiken verwendet wird. Sie wird als das Produkt aus drei Faktoren berechnet: Schwere (S), Auftreten (O) und Entdeckung (D). Die Formel lautet [latex]RPN = S mal O mal D[/latex]. Jeder Faktor wird in der Regel auf einer Skala von 1 bis 10 bewertet, so dass sich die Teams zunächst auf die Risiken mit der höchsten Punktzahl konzentrieren können.

Computer-Workstation mit MATLAB-Schnittstelle zur Veranschaulichung der array-orientierten Syntax in der numerischen Analyse.

MATLABs Array-orientierte Syntax

MATLAB ist eine matrixbasierte Sprache, deren grundlegender Datentyp das Array ist und keine Dimensionierung erfordert. Dies ermöglicht die präzise Darstellung von Matrix- und Vektoroperationen. Beispielsweise ergibt die Multiplikation zweier Matrizen „A“ und „B“ einfach „C = A * B“, und die elementweise Multiplikation ergibt „C = A .* B“, wodurch komplexe Schleifenstrukturen, wie sie in anderen Sprachen vorkommen, abstrahiert werden.

Ingenieure, die in einem modernen Büro an harten und weichen Echtzeitsystemen zusammenarbeiten.

Harte und weiche Echtzeitsysteme

Real-time systems are classified as "hard" or "soft" based on the consequence of missing a deadline. In a hard real-time system, missing a deadline is a total system failure, such as in an anti-lock braking system. In a soft real-time system, missing a deadline leads to degraded performance but not catastrophic failure, such as in live audio-video streaming.

Computerarbeitsplatz in einem Kontrollraum zur Analyse der ratenmonotonen Terminplanung für Echtzeitsysteme.

Rate-Monotonic Scheduling (RMS)

Rate-Monotonic Scheduling (RMS) is a static-priority scheduling algorithm for periodic tasks in a real-time system. It assigns priorities based on task frequency: the shorter a task's period (the higher its rate), the higher its priority. RMS is an optimal static-priority algorithm, meaning if any static-priority algorithm can schedule a task set, RMS can too. Schedulability can be checked using a utilization-based test.

(wenn das Datum unbekannt oder nicht relevant ist, z. B. „Strömungsmechanik“, wird eine gerundete Schätzung seines bemerkenswerten Auftretens bereitgestellt)