Rechtfertigung der asymptotischen Worst-Case-Analyse für Wissenschaftler

Ich habe daran gearbeitet, einige Ergebnisse aus der Komplexität von Berechnungen in die theoretische Biologie, insbesondere Evolution und Ökologie , einfließen zu lassen , mit dem Ziel, für Biologen interessant / nützlich zu sein. Eine der größten Schwierigkeiten, mit denen ich konfrontiert war, war die Rechtfertigung des Nutzens einer asymptotischen Worst-Case-Analyse für Untergrenzen. Gibt es Referenzen zur Artikellänge, die eine Untergrenze und eine asymptotische Worst-Case-Analyse für ein wissenschaftliches Publikum rechtfertigen?

Ich bin wirklich auf der Suche nach einer guten Referenz, auf die ich mich in meinem Schreiben verlassen kann, anstatt die Begründungen in dem begrenzten verfügbaren Raum durchgehen zu müssen (da dies nicht der zentrale Punkt des Artikels ist). Ich kenne auch andere Arten und Paradigmen der Analyse, deshalb suche ich keine Referenz, die besagt, dass der schlechteste Fall die "beste" Analyse ist (da es Einstellungen gibt, bei denen es sehr viel weniger gibt), aber das ist es nicht Völlig nutzlos: Es kann uns immer noch theoretisch nützliche Einblicke in das Verhalten tatsächlicher Algorithmen auf tatsächlichen Eingaben geben. Es ist auch wichtig, dass sich das Schreiben an allgemeine Wissenschaftler richtet und nicht nur Ingenieure, Mathematiker oder Informatiker.

Zum Beispiel ist Tim Roughgardens Aufsatz zur Einführung in die Komplexitätstheorie für Ökonomen auf dem richtigen Weg für das, was ich will. Es sind jedoch nur die Abschnitte 1 und 2 relevant (der Rest ist zu wirtschaftsspezifisch), und die angesprochene Zielgruppe ist ein wenig sicherer in Bezug auf Theorem-Lemma-Beweis als die meisten Wissenschaftler ^[1] .

Einzelheiten

Im Kontext der adaptiven Dynamik in der Evolution habe ich zwei spezifische Arten von Widerständen von theoretischen Biologen kennengelernt:

[A] "Warum sollte ich mich für willkürliches interessieren ? Ich weiß bereits, dass das Genom Basenpaare (oder vielleicht Gene) hat und nicht mehr." $n$ $n = 3*10^9$ $n = 2*10^4$

Dies lässt sich relativ leicht mit dem Argument "Wir können uns vorstellen, Sekunden zu warten , aber nicht " abbrechen . Ein komplizierteres Argument könnte jedoch lauten: "Sicher, Sie sagen, Sie interessieren sich nur für ein bestimmtes , aber Ihre Theorien verwenden diese Tatsache nie. Sie verwenden nur, dass es groß, aber endlich ist, und es ist Ihre Theorie, mit der wir uns befassen asymptotische Analyse ". $10^9$ $2^{10^9}$ $n$

[B] "Aber Sie haben nur gezeigt, dass dies schwierig ist, indem Sie diese spezifische Landschaft mit diesen Geräten erstellt haben. Warum sollte ich mich dafür interessieren, anstatt für den Durchschnitt?"

Dies ist eine schwieriger zu behandelnde Kritik, da viele der auf diesem Gebiet gebräuchlichen Werkzeuge aus der statistischen Physik stammen, in der es oft sicher ist, eine einheitliche (oder andere spezifische einfache) Verteilung anzunehmen. Aber Biologie ist "Physik mit Geschichte" und fast alles ist nicht im Gleichgewicht oder "typisch", und empirische Kenntnisse sind unzureichendAnnahmen über Verteilungen über Input zu rechtfertigen. Mit anderen Worten, ich möchte ein ähnliches Argument wie das, das für die Analyse des Gleichverteilungsdurchschnitts bei der Softwareentwicklung verwendet wird: "Wir modellieren den Algorithmus, wir können kein vernünftiges Modell dafür aufbauen, wie der Benutzer mit dem Algorithmus interagiert oder wie seine Verteilung ist von Eingaben werden; das ist für Psychologen oder Endbenutzer, nicht für uns. " Ausgenommen in diesem Fall ist die Wissenschaft nicht in der Lage, das Äquivalent von "Psychologen oder Endbenutzern" zu finden, um die zugrunde liegenden Verteilungen herauszufinden (oder wenn dies überhaupt sinnvoll ist).

Notizen und verwandte Fragen

Der Link behandelt die kognitiven Wissenschaften, aber die Denkweise in der Biologie ist ähnlich. Wenn Sie in Evolution oder Journal of Theoretical Biology stöbern , werden Sie selten Theorem-Lemma-Beweise sehen, und wenn Sie dies tun, handelt es sich in der Regel nur um eine Berechnung, anstatt um einen Existenzbeweis oder eine komplizierte Konstruktion.
Paradigmen zur Komplexitätsanalyse von Algorithmen
Andere Arten der Laufzeitanalyse als Worst-Case, Average-Case usw.?
Ökologie und Evolution durch die algorithmische Linse
Warum sich Ökonomen für die Komplexität ihrer Berechnungen interessieren sollten

cc.complexity-theory reference-request big-picture application-of-theory worst-case Artem Kaznatcheev
quelle

Es ist unmöglich, das Verhalten im schlimmsten Fall zu rechtfertigen. Der Simplex-Algorithmus weist ein exponentielles Verhalten im schlimmsten Fall auf, und die einzigen Personen, die sich jemals darum gekümmert haben, sind die Theoretiker. Was Sie argumentieren müssen, ist (a) das asymptotische Verhalten im Durchschnitt ist wichtig; (b) das asymptotische Verhalten im Durchschnitt und das asymptotische Verhalten im schlimmsten Fall sind ziemlich oft ähnlich; (c) Das asymptotische Verhalten im ungünstigsten Fall ist oft viel einfacher zu berechnen als das asymptotische Verhalten im durchschnittlichen Fall (zumal niemand die relevante Wahrscheinlichkeitsverteilung kennt).

Peter Shor

Asymptotik ist bereits ein problematischer Aspekt. Wir alle kennen die Geschichte über Matrixmultiplikationsalgorithmen (asymptotische Obergrenzen sind in der Praxis bedeutungslos) und vielleicht auch die Geschichte über die Auswahl von Parametern in der Kryptographie (asymptotische Untergrenzen sind in der Praxis bedeutungslos; exponentielle Algorithmen sind manchmal möglich [DES]). Wenn Ihre Analyse tatsächliche Konstanten hat, ist sie überzeugender.

Yuval Filmus

Wenn Sie die Berechnung als ein Spiel (dh als Krieg) zwischen dem Eingabeanbieter und dem Algorithmus betrachten, ist die Worst-Case-Analyse ein standardmäßiger militärischer Ansatz - Sie möchten wissen, wie schlimm es sein kann. Zweitens, und was noch wichtiger ist, die Worst-Case-Analyse erlaubt es Ihnen nicht, intellektuell faul zu sein und Lösungen zu akzeptieren, die für das, was Sie für die Welt halten (und nicht für das, was die Welt wirklich ist), gut sind. Schließlich, und vielleicht am wichtigsten, bietet es eine einheitliche Möglichkeit, Algorithmen auf hoffentlich sinnvolle Weise zu vergleichen. Kurz gesagt, es ist der schlechteste Ansatz, mit Ausnahme aller anderen.

Sariel Har-Peled

Ich denke, eine Untergrenze im schlimmsten Fall sollte so gesehen werden, als würde der Ball zurück ins Spiel gebracht. Sie haben gezeigt, dass es keinen Algorithmus gibt, der das Problem in einem angemessenen Zeitraum auf allen Instanzen lösen kann. Sie mögen vernünftigerweise glauben, dass ihre Instanzen einfach sind - aber Sie haben gerade gezeigt, dass dies keine triviale Tatsache ist. Ihr Modell ist daher unvollständig, es sei denn, sie liefern eine Erklärung, warum dies so ist.

Aaron Roth

(Dies ist der Ansatz, der bei Gesprächen mit Spieltheoretikern zu funktionieren scheint. Er wirft die Frage auf - wenn sich die Märkte wirklich schnell ausgleichen -, welche besonderen Eigenschaften reale Märkte haben, die die Härte im schlimmsten Fall umgehen? Es ist wahrscheinlich möglich, eine plausible zu definieren eine solche Eigenschaft, und die unteren Schranken deuten nur darauf hin, dass dies eine wichtige Forschungsrichtung ist)

Aaron Roth

Antworten:

Mein persönlicher (und voreingenommener) Standpunkt ist, dass die asymptotische Worst-Case-Analyse ein historisches Sprungbrett zu praktischeren Analysearten ist. Es scheint daher schwierig, es den Praktizierenden zu rechtfertigen.

Grenzen für den schlimmsten Fall zu beweisen ist oft einfacher als Grenzen für "nette" Definitionen des Durchschnittsfalls zu beweisen. Die asymptotische Analyse ist oftmals auch viel einfacher als der Nachweis relativ enger Grenzen. Die asymptotische Analyse im schlimmsten Fall ist daher ein guter Ausgangspunkt.

Die Arbeit von Daniel Spielman und Shanghua Teng zur geglätteten Analyse von Simplex scheint mir ein Vorbote dessen zu sein, was passieren kann, wenn wir beginnen, die Form eines Problems besser zu verstehen entwickelt. Wie Aaron Roth in den Kommentaren angedeutet hat, ist das System noch nicht vollständig spezifiziert, wenn sich das "übliche" Verhalten eines Systems erheblich vom schlimmsten unterscheidet, und es sind weitere Arbeiten erforderlich, um das Modell zu verbessern. Über den Worst-Case hinauszugehen, scheint daher als langfristiges Ziel wichtig zu sein.

Bei der asymptotischen Analyse dient sie normalerweise dazu, einen langen und unübersichtlichen Beweis von störenden Details freizuhalten. Leider scheint es derzeit keine Möglichkeit zu geben, die mühsame Arbeit, die Details einzugeben, um die tatsächlichen Konstanten zu erhalten, zu belohnen, so dass dies nur selten getan zu werden scheint. (Seitengrenzen wirken auch dagegen.) Eine sorgfältige Analyse der Details einer asymptotischen Grenze hat zu tatsächlichen Algorithmen mit guten Grenzen für die Konstanten geführt, sodass ich persönlich mehr von dieser Art von Arbeit sehen möchte. Wenn mehr Beweise mit Proof-Assistenten formalisiert würden, könnten die Konstanten möglicherweise mit weniger zusätzlichem Aufwand geschätzt werden. (Oder die Grenzen für die Konstanten, wie sie Gowers für das Szemerédi-Regelmäßigkeits-Lemma festgelegt hat, werden möglicherweise routinemäßiger.) Es gibt auch Möglichkeiten, Untergrenzen zu beweisen, die frei von Konstanten sind. durch Verwendung expliziterer Maschinenmodelle (z. B. deterministischer Automaten mit endlichen Zuständen). Solche (nahezu) genauen Untergrenzen für allgemeinere Berechnungsmodelle können jedoch viel Arbeit erfordern oder außer Reichweite sein. Dies scheint in ~ 1958–73 während der ersten Blütezeit der Automatentheorie verfolgt worden zu sein, aber soweit ich das beurteilen kann, wurde es seitdem weitgehend in Ruhe gelassen.

Kurz gesagt: Ich denke, dass wir in Zukunft die Worst-Case-Analyse nur als ersten Schritt sehen werden, und ich hoffe, dass Ausdrücke wie^* mit galaktischen versteckten Konstanten nur der erste Schritt sind. Ich finde es schwierig, den gegenwärtigen Fokus auf asymptotische Worst-Case-Analysen für Praktiker zu rechtfertigen, aber vielleicht ist es nützlich, dies als den Beginn einer längeren Reise zu betrachten. $O$ $(n^k)$

András Salamon
quelle

Ich teile nicht Ihre Begeisterung, Asymptoten zugunsten präziser Grenzen mit bestimmten Konstanten abzulegen. Asymptotika mögen ungenau sein - aber sie sind nützlicherweise ungenau. Sie abstrahieren über Implementierungsunterschiede für dasselbe Maschinenmodell. Zum Beispiel wird ein Sortieralgorithmus, der auf Hardware der 1950er Jahre quadratisch war, auf heutiger Hardware immer noch quadratisch sein. Darüber hinaus komponieren asymptotische Formeln gut. Beispielsweise werden Linien und Polynome unter Komposition geschlossen. (Beachten Sie, dass das Argumentieren für bessere Grenzen im Durchschnitt im Vergleich zum schlechtesten Fall orthogonal ist, wenn Sie gegen Asymptotika argumentieren.)

brandjon

Sie haben im Allgemeinen recht, aber es gibt einen großen Unterschied zwischen einer kleinen Konstanten und einer Konstanten, die eine nicht-elementare Funktion eines relevanten Parameters ist.

András Salamon

Diese Antwort gefällt mir insgesamt, aber ich stimme @brandjon zu, dass das Ausblenden von Konstanten von entscheidender Bedeutung ist. Der Grund, warum TCS in der Biologie nützlich ist, liegt für mich darin, dass weniger Annahmen über die Mikrodynamik gemacht werden müssen als über die Physik. Wenn Sie jedoch keine Annahmen über die Mikrodynamik treffen (dh die genaue Spezifikation des Berechnungsmodells), können Sie die konstanten Faktoren nicht herausfinden. Das andere nützliche Merkmal von TCS sind strenge qualitative Dichotomien (etwas, das sich leichter mit den qualitativeren Beobachtungen in Bio vergleichen lässt). Um diese zu erhalten, muss man in der Regel auch Konstanten loswerden.

Artem Kaznatcheev

\tilde{O} (n^{\tilde{O} (1 / ϵ)})

$\tilde{O}(n^{\tilde{O}(1/\epsilon)})$

Nebenbei bemerkt gibt es Beispiele, bei denen eine Worst-Case-Analyse sinnvoll ist. Wenn Sie beispielsweise eine Bibliothek mit allgemeinen Unterprogrammen entwickeln und nicht wissen, in welchen Anwendungsbereichen sie nützlich sind, können Sie möglicherweise nicht vorhersehen, wann und warum jemand beispielsweise einen zweigliedrigen Mindestkostenabgleich berechnen möchte. Widersprüchliche Einstellungen wie die Kryptografie sind noch eindeutiger (bei Kryptografie möchten Sie jedoch die Konstanten in Bezug auf die Sicherheitsparameter genau kennen).

Sasho Nikolov

Untere Schranken und Worst-Case-Analyse passen normalerweise nicht zusammen. Sie sagen nicht, dass ein Algorithmus im schlimmsten Fall mindestens exponentielle Zeit benötigt, daher ist er schlecht. Sie sagen, es kann im schlimmsten Fall höchstens eine lineare Zeit dauern und ist daher gut. Ersteres ist nur nützlich, wenn Sie Ihren Algorithmus für alle möglichen Eingaben ausführen und nicht nur für eine durchschnittliche Eingabe.

Wenn Sie zur Demonstration der Bösartigkeit untere Schranken verwenden möchten, möchten Sie eine Best-Case-Analyse oder eine Durchschnittsfallanalyse. Sie können die Dinge vereinfachen, indem Sie sich auf den Punkt von @ PeterShor verlassen, dass Schlimmstes und Durchschnittliches oft sehr ähnlich sind, und eine Liste von Algorithmen angeben, für die dies zutrifft. (Bsp .: alle klassischen Sorten außer Quicksort.)

Um zu demonstrieren, dass Asymptotik im Vergleich zu konstanten Eingaben und konstanten Faktoren eine Rolle spielt, ist mein Lieblingsartikel zu diesem Thema Jon Bentleys "Programming pearls: algorithm design techniques". Er präsentiert vier verschiedene Lösungen für ein einfaches Array-Problem und zeigt, wie der lineare Ansatz den kubischen vernichtet. Er nennt seinen Tisch "The Tyranny of Asymptotics", nach dem Begriff, den die Physiker für die Unlösbarkeit der Raketengleichung verwendeten. Ich benutze dieses Beispiel, um die Suche nach besseren Algorithmen für Studenten vor dem College zu motivieren.

Liest ein Nicht-Informatiker einen Artikel durch, der Code enthält, und weiß, dass er die Details auf niedriger Ebene überspringen muss, um den Überblick zu behalten? Ich weiß es nicht. Vielleicht gibt es anderswo eine bessere Präsentation. Ich halte dies jedoch für eine anständige Ressource.

Und wenn sie argumentieren, dass sie sich nicht für willkürlich große n interessieren, lassen Sie sie rekursive, nicht auswendig gelernte Fibonacci mit 3 * 10 ⁹ Basenpaaren ausführen und sagen, dass es O (1) ist, da die Größe der DNA-Sequenz festgelegt ist. ;)

brandjon
quelle

Ich mag das Fibonacci-Beispiel :)

Suresh Venkat

Betreff: Ihr erster Absatz: Eigentlich ist das fast genau das, was eine Menge Komplexitätstheorie tut. Wenn ein Problem EXP-vollständig ist, bedeutet dies, dass es bei Eingaben im ungünstigsten Fall eine exponentielle Zeit benötigt. Dies wird im Allgemeinen als Hinweis auf die Gesamtschwierigkeit angesehen (was in der Praxis, um fair zu sein, als allgemeiner Indikator oft nicht so schlecht ist). Dies ist der De-facto-Standard, der als "unendlich oft" oder als Untergrenze bezeichnet wird. Es ist ein Ziel, das manchmal angestrebt wird, aber im Vergleich zu den unteren Grenzen oft weit außerhalb der Reichweite liegt, wenn man die unteren Grenzen im Durchschnitt oder fast überall erreicht (d. h. für alle, aber nur für endlich viele Eingaben).

Joshua Grochow

Lassen Sie mich darauf hinweisen, dass Sie nicht nur eine Liste von Algorithmen erstellen können, bei denen die Worst-Case- und die Average-Case-Analyse gleich sind, sondern auch zahlreiche Beispiele, bei denen sie sehr unterschiedlich sind (der Simplex-Algorithmus ist nur der bekannteste) von diesen). Sie müssen wirklich irgendwie argumentieren, dass sie für Ihre spezielle Anwendung gleich sind; Experimentelle Tests sind eine gute Möglichkeit, dies zu tun.

Peter Shor

@ JoshuaGrochow Fair genug. Wie wäre es, wenn wir die Aussage wie folgt überarbeiten: Untere Schranken für Worst-Cases sind wichtig, wenn Sie das Fehlen einer mathematischen Garantie für die Nicht-Schrecklichkeit nachweisen möchten. ;)

Brandjon

-3

Ich war mir einig, dass dies ein wichtiges Thema für die Umfrage / Berichterstattung ist, aber es scheint noch nicht viel gewesen zu sein. Ein paar Refs mit unterschiedlichem Stil / Coverage / Publikum / Formalität, die nicht genau den Anforderungen entsprachen, aber einigermaßen nah beieinander lagen (am besten online bei mittlerer Suche, ich hoffe, weitere davon zu hören; weitere Anmerkungen unten):

Die Komplexität der Atkinson- Algorithmen (leider nur ein einziger Hinweis auf die Biologie in der Veröffentlichung, kann aber unter allgemeineren naturwissenschaftlichen / technischen Begriffen ausreichen)

Die moderne Algorithmentheorie stammt aus den späten 1960er Jahren, als die Methode der asymptotischen Ausführungszeitmessung eingesetzt wurde. Es wird argumentiert, dass das Fach sowohl einen technischen als auch einen wissenschaftlichen Hintergrund hat. Der technische Flügel besteht aus gut verstandenen Entwurfsmethoden, während sich der wissenschaftliche Flügel mit theoretischen Grundlagen befasst. Die Kernthemen beider Flügel werden erhoben. Zum Schluss werden einige persönliche Meinungen dazu geäußert, wohin das Thema als nächstes führen wird.
Komplexität und Algorithmen J. Diaz. 100 Folien. breit; man könnte insbesondere relevante herausgreifen.
Eine sanfte Einführung in die Komplexitätsanalyse von Algorithmen Dionysis "dionyziz" Zindros

Mit anderen Worten, gibt es eine Art Einführung / Übersicht / Überblick über die komplexitätstheoretische Linse in enger Kombination / Verbindung / Begleitung mit der fortschreitenden algorithmischen Linse in der Wissenschaft, so etwas wie "Komplexitätstheorie für Wissenschaftler, Ingenieure und Forscher" ?

Es gibt gute Referenzen für die erstere "algorithmische Linse", die Sie zitiert haben, z. B. Papadimitriou, aber es scheint keine sehr zufriedenstellende Referenz zu sein, die von einem Experten auf diesem Gebiet für die letztere "Komplexitätslinse" geschrieben wurde ... noch (vielleicht eine "Elite") " Mitglied dieser Site wird dies als ihr nächstes Buch - oder Papierprojekt betrachten.

Beachten Sie auch, dass es viele Literaturstellen zur Relevanz P gegen NP außerhalb der Komplexitätstheorie und in anderen wissenschaftlichen Bereichen gibt, die für diesen Zweck verwendet werden könnten. fügt sie bei Interesse in die Kommentare ein.

vzn
quelle

Ich denke, das beantwortet die Frage nicht wirklich.

Huck Bennett

Hast du dir einen der Schiedsrichter angesehen? teil meiner antwort ist, dass es (noch) keine ideale / perfekte antwort gibt:

29.

Sie scheinen asymptotische und Worst-Case-Analysen zu definieren, anstatt sich darauf zu konzentrieren, sie zu rechtfertigen, aber vielleicht habe ich etwas verpasst?

Huck Bennett

Tatsächlich denke ich, dass Forscher außerhalb von TCS den Worst-Case leicht als "künstlich konstruierte Beispiele, die in der Praxis niemals auftreten würden" abtun könnten und (ohne stark davon zu überzeugen) viel mehr am Durchschnittsfall interessiert wären (obwohl es nicht klar ist, dass dies der Fall ist) Der Durchschnittsfall ist derjenige, der den realen Instanzen viel näher kommt.

Joshua Grochow

@vzn: Asymptotisch (zB Big-Oh) und Worst-Case sind etwas orthogonal. Man kann tun asymptotische Worst-Case - Analyse, asymptotisch durchschnittliche Fallanalyse oder sogar asymptotisch einfachste -case Analyse (obwohl ich die letztere scheint etwas perverse zugeben). Man könnte stattdessen eine exakte Worst-Case-Analyse oder eine exakte Average-Case-Analyse usw. durchführen, obwohl diese viel modellabhängiger und weniger robust wären. Die Rechtfertigung der Verwendung von Asymptotika (und das Ausblenden von Dingen wie konstanten Faktoren) unterscheidet sich völlig von der Rechtfertigung von Worst-Case- oder Average-Case- oder Real-Case-Fällen (was auch immer Letzteres bedeuten mag ...).

Joshua Grochow