Was ist die rechnerische Komplexität des EM-Algorithmus?

Im Allgemeinen, und insbesondere für Bernoulli mixture Modell (aka Latent-Class-Analyse).

InformationsquelleAutor Jessica | 2012-12-27
  1. 6

    EM ist so ziemlich das gleiche wie Lloyds Variante von k-means. Also jede iteration dauert O(n*k) Distanz-Berechnungen. Sie sind komplexer Entfernung von Berechnungen, aber am Ende werden Sie eine Variante der Mahalanobis-Distanz.

    Jedoch k-means ist ein ganz netter Kündigung Verhalten. Es gibt nur k^n mögliche cluster-Zuordnungen. Nun, wenn in jedem Schritt wählen Sie eine, die besser ist, es zu kündigen, spätestens nach ausprobieren alle k^n ist. Aber in Wirklichkeit ist es in der Regel endet nach höchstens ein paar Dutzend Schritte.

    Für EM, das ist nicht so einfach. Objekte, die nicht zugeordnet sind, zu einem einzigen cluster, aber wie bei fuzzy-c-Mittel zugeordnet sind, relativ zu allen Clustern. Und das ist, wenn Sie verlieren diese Terminierung garantieren.

    Also ohne anhalten Schwelle, EM würde unendlich Optimierung der cluster-Zuordnungen, bis zu einer unendlichen Genauigkeit (vorausgesetzt, Sie realisieren es mit unendlicher Genauigkeit).

    Als solche, die theoretische Laufzeit der EM ist: unendliche.

    Grenzwert (und wenn es nur hardware-floating-point-Präzision) wird es fertig früher. Aber es wird hart sein, um eine theoretische Grenze hier anders als O(n*k*i) wo i ist die Anzahl der Iterationen (und das kann unendlich sein, aber die können Sie auch 0 wenn Sie nicht wollen, um eine einzelne iteration).

    InformationsquelleAutor Anony-Mousse
  2. 0

    Da der EM-Algorithmus ist von Natur aus iterativ ist, müssen Sie entscheiden, auf einem Abbruchkriterium. Wenn Sie fix eine Obere Schranke für die Anzahl der Schritte, die Laufzeitanalyse ist natürlich einfach. Für andere Kündigung-Kriterien (wie Konvergenz bis auf eine Konstante Differenz), die situation muss analysiert werden, die speziell.

    Lange Geschichte kurz, die Bezeichnung "EM" nicht enthalten ein Abbruchkriterium, so dass die Frage nicht beantwortet werden kann, wie Z.

    • Nichts für ungut, aber diese Antwort ist falsch. Dies ist nicht, wie Sie die Ermittlung eines Algorithmus ist die Komplexität der Berechnung, die Anzahl der Schritte hat das nichts zu tun. Komplexität und Laufzeit-Analyse sind verschiedene Dinge.
    InformationsquelleAutor Dino
  3. 0

    Dies ist, was ich denke:
    Wenn wir davon ausgehen, dass die EM algorithm verwendet linear algebra, was es tut, dann ist seine Komplexität sollte O(m.n^3), wobei m die Anzahl der
    Iterationen und n die Anzahl der Parameter.

    Die Anzahl der Iterationen wird beeinflusst von der Qualität der Startwerte. Gute Startwerte bedeutet kleine m.

    Nicht-so-gute Startwerte größere m oder sogar scheitern, weil der Konvergenz zu einem lokalen Lösung. Lokale Lösungen können existieren, weil EM verwendet wird, auf likelihood-Funktionen, die nonlinear.

    Gute Startwerte bedeutet, dass Sie in die konvexe zone der Anziehung, die Sie umgibt den Ort, der die Global optimale Lösung.

    InformationsquelleAutor user75573
Schreibe einen Kommentar