Sinnhaftigkeit von Schranken in der Mathematik?
-
Naja, wenn man z.B. eine numerische Methode analysiert, dann geben die Schranken an, ob eine Methode stabil ist oder nicht. Ist sie es nicht, dann weiß ich, dass ich mir überhaupt nicht die Mühe machen sollte es einzuprogrammieren. Ist sie es, dann kann ich anhand von Schranken auch vorher schon wissen, wie genau die Methode überhaupt ist. Schranken sind ein Maßstab, eine Garantie und deswegen auch in anderen Gebieten der Mathematik ungeheuer wichtig. Wie mein Vorredner schon sagte: Besser man hat Schranken als nichts. Und wenn sich irgendwann rausstellt, dass sie unscharf sind, dann kann sich jemand mit der schärferen Schranke einen Namen machen. Zum Beispiel ist eine untere Schranke für die beste mögliche Komplexität der Matrixmultiplikation noch unbekannt!
-
otze schrieb:
Ein Beispiel dafür sind Laufzeitschranken. Manche Algorithmen sind so kompliziert zu analysieren, dass die Schranken völlig aus den Rundern laufen. Je einfacher ein Algorithmus zu analysieren ist, desto wahrscheinlicher ist es, dass er eine niedrigere Laufzeitschranke als komplizierte Algorithmen hat, unabhängig von der echten Performance. Oder abgeschwächter: Laufzeitschranken einfacherer Algorithmen sind enger, als von komplizierten.
Ja und nein. Normalerweise gibt man ja die Komplexität der Algorithmen eh nur in Landau-Notation an. Und wenn man zwei Algorithmen vergleicht, so ist das meistens ausreichend. Das Problem muss nur groß genug sein. So kannst du ganz leicht zeigen, dass Bubble-Sort langsamer als z.B. Merge-Sort ist.
Wie lange genau der Algorithmus braucht, das sieht man im Zweifelsfall. Aber wenn du entscheiden kannst, welcher der besser der zur Auswahl stehenden Algorithmen ist, ist das doch schonmal was.
otze schrieb:
Ein anderes Beispiel hat ein Prof von mir genannt: Es ging um die obere Schranke einer Wahrscheinlichkeit. Riesiges Paper, seitenweise Herleitungen, kam in ein prominentes theoretisches Journal. Irgendwann hat mal wirklich jemand Werte eingesetzt und es kam raus: unabhängig von den gewählten Parametern war die obere Schranke ≥1. Was bringt so eine Schranke?
Das zeigt nur, dass man beim Berechnen von Schranken so viele Vereinfachungen machen kann, dass am Ende nichts sinnvolles mehr raus kommt.
Auf der Anderen Seite kann es natürlich sein, dass das Problem so böse ist, dass eine Wahrscheinlichkeit von < 1 nicht für alle Eingaben garantiert werden kann...
Schranken sind ja nun auch nichts realitätsfernes. Du willst zum Beispiel immer Wissen, ob eine obere Schranke für den Speicherverbrauch deines Programms existiert...
-
Hi,
anderes Beispiel aus der Optimierung:
bei einem Branch&Bound Algorithmus brauchst du möglichst gute Schranken, um deinen Branching-Baum einzuschränken, so daß der Algorithmus schneller läuft (andersrum: schlechte Schranken bewirken, dass es eher in Richtung "vollständige Iteration" rausläuft).
Gruß,
MJM
-
danke schonmal für eure Antworten
@MJM gegen "gute" Schranken habe ich ja nichts gesagt. Nur zweifel ich an, dass auch nur ein großteil der Schranken deiner Definition von "gut" entspricht.
@ProgChild Ja, ich meinte das auch mit Landau-Notation. Wenn man sich mal die etwas komplexere Algorithmen, wie zum Beispiel Preflow-push Flussalgorithmen anschaut, dann merkt man, dass diese Schranken in keiner Art und Weise eng sind. Da gehts auch nicht um große Unterschiede zwischen verschiedenen Algorithmen, sondern um sowas wie O(sqrt(m)) vs O(n) (n sind die Knoten des Graphen, m die Kanten. Und m<=n^2). Die Komplexitätsbeweise der Algorithmen haben dabei einen so enormen Sicherheitsabstand, dass es schwer bis unmöglich ist abzuschätzen, in welchem Fall welcher Algorithmus besser ist.
Statistische Schranken sind im Allgemeinen noch schlimmer. Ich bringe als Beispiel mal den Union-Bound: P(A1 ν A2 ν ... ν An)<=P(A1)+P(A2)+...+P(An). Ist ein Standardtool bei sowas. Es sorgt dafür, dass viele Bounds sehr schnell sehr schlecht werden (man schätzt die Wahrscheinlichkeit ab, dass in einem Ereignis der Worst-case eintritt und macht dann einen Union-Bound über alle (gleichartigen) Ereignisse).
-
was ist denn eine gute Schranke ?
bevor wie über den Sinn oder Unsinn guter Schranken diskutieren, müssen wir erstmal klären, worüber wir hier reden.
Es gibt Probleme, da gilt "endlich" schon als gute Schranke und erfordert riesigen beweistechnischen Aufwand, bei anderen Problemen ist vielleicht ein Schmutzfaktor von exp(1/n) noch nicht gut genug, wenn man auf exp(1/n^2) verbessern kann.
-
otze schrieb:
@ProgChild Ja, ich meinte das auch mit Landau-Notation. Wenn man sich mal die etwas komplexere Algorithmen, wie zum Beispiel Preflow-push Flussalgorithmen anschaut, dann merkt man, dass diese Schranken in keiner Art und Weise eng sind. Da gehts auch nicht um große Unterschiede zwischen verschiedenen Algorithmen, sondern um sowas wie O(sqrt(m)) vs O(n) (n sind die Knoten des Graphen, m die Kanten. Und m<=n^2). Die Komplexitätsbeweise der Algorithmen haben dabei einen so enormen Sicherheitsabstand, dass es schwer bis unmöglich ist abzuschätzen, in welchem Fall welcher Algorithmus besser ist.
Wenn es zu schwierig wird, bessere Aussagen zu treffen, dass ist das halt so. Aber das ist immer noch besser, - wie hier schon erwähnt - als garnichts in der Hand zu haben.
Wenn du Algorithmen-Vergleiche stichhaltig machen willst, reicht dir eine Abschätzung nach oben natürlich nicht. Du brauchst auch noch eine nach unten...
-
... und Schranken für den average-case.
Der kann nämlich bei manchen Algorithmen erheblich vom worst-case oder best-case abweichen, ist oft sehr praxisrelevant und erheblich schwieriger zu bestimmen (statistische Analyse der Eingabedaten etc) - Beispiel lineare Optimierung mit Simplex.
-
otze schrieb:
@ProgChild Ja, ich meinte das auch mit Landau-Notation. Wenn man sich mal die etwas komplexere Algorithmen, wie zum Beispiel Preflow-push Flussalgorithmen anschaut, dann merkt man, dass diese Schranken in keiner Art und Weise eng sind. Da gehts auch nicht um große Unterschiede zwischen verschiedenen Algorithmen, sondern um sowas wie O(sqrt(m)) vs O(n) (n sind die Knoten des Graphen, m die Kanten. Und m<=n^2). Die Komplexitätsbeweise der Algorithmen haben dabei einen so enormen Sicherheitsabstand, dass es schwer bis unmöglich ist abzuschätzen, in welchem Fall welcher Algorithmus besser ist.
Meines Wissens sind gerade diese Fluß-Beweise aber scharf und es existieren Beispiele, bei denen tatsächlich entsprechend viele Schritte nötig sind. Außerdem gibt einem O(sqrt(m)) und O(n) doch schon nen klaren Hinweis. Der erstere ist nie schlechter und bei dünnen Graphen sogar besser -- zumindest asymptotisch.
Tatsächlich hilft in der Praxis aber wirklich nur das Ausprobieren verschiedener Verfahren, wenn es um maximale Effizienz geht. Oftmals ist in den zu lösenden Probleminstanzen bei Realwelt-Problemen noch mehr Struktur versteckt, auf die die verschiedenen Algorithmen teilweise sehr unterschiedlich reagieren. Gerade die von Dir angesprochenen Flussprobleme können sehr unterschiedlich schwierig sein. Von Problemen, die im wesentlichen darin bestehen eine handvoll disjunkte Wege von a nach b in einem Graphen zu finden bis zu komplexen kombinatorischen Optimierungsproblemen (etwa Finden eines Graphen zu einer gegebenen Gradsequenz) lassen sich sehr viele, sehr unterschiedlich schwierige Probleme als Flußproblem formulieren.
-
Jester schrieb:
Meines Wissens sind gerade diese Fluß-Beweise aber scharf und es existieren Beispiele, bei denen tatsächlich entsprechend viele Schritte nötig sind.
Das hatte ich eigentlich auch so in Erinnerung.
-
Fehlerabschaetzung! Einfache Frage: Ist das numerische Ergebnis, das der Algorithmus liefert, ueberhaupt zu gebrauchen? Da spielen Kondition der Matrix, endliche Genauigkeit des Rechners oder der Messinstrumente eine Rolle und wie sich diese Fehler fortpflanzen.
-
life schrieb:
Das hatte ich eigentlich auch so in Erinnerung.
beim Preflow-Push wäre ich mir da nicht so sicher, zumindest im userem Beweis den wir hatten, wurde an mancher Stelle enorm rumgesaut. Ich finde es zum Beispiel kritisch, für 2 Terme separate Worst-Case Abschätzungen zu machen, aber dabei nicht zu beachten, dass beide Fälle gleichzeitig _niemals_ auftreten können.
Genauso, wie ich es kritisch finde, in der Statistik eine Worstcase Abschätzung zu machen, bei der man annimmt, dass die gefundene Lösung orthogonal(!) zur optimalen Lösung steht. Das kommt nicht vor, insbesondere wenn es eine Abschätzung ist, die nur mit Wahrscheinlichkeit "1-δ" gültig ist. Diese Abschätzung vergleiche ich auch gerne mal mit der Physik, da steht am Ende auch nur : Erwartetes Ergebnis 4+-0.1 . Statistisch gesehen sind aber auch noch Abweichungen von 0,5 oder 0,6 möglich - nur höchst unwahrscheinlich.
@Knivil Aber auch da kann man das Selbe Argument Anwenden: Was ist, wenn das Verfahren ansich numerisch Stabil wäre, aber Mathematisch nicht sinnvoll abgeschätzt werden kann? Dann sagt dir die Schranke "taugt nichts" obwohl dort eigentlich eher "Wissen wir nicht" stehen müsste.
-
otze schrieb:
life schrieb:
Das hatte ich eigentlich auch so in Erinnerung.
beim Preflow-Push wäre ich mir da nicht so sicher, zumindest im userem Beweis den wir hatten, wurde an mancher Stelle enorm rumgesaut. Ich finde es zum Beispiel kritisch, für 2 Terme separate Worst-Case Abschätzungen zu machen, aber dabei nicht zu beachten, dass beide Fälle gleichzeitig _niemals_ auftreten können.
Vielleicht können die Fälle aber asymptotisch gleichzeitig auftreten? Dann kann man asymptotisch nichts besseres zeigen. Zum Beispiel kann ein Graph mit n knoten O(n) Zusammenhangskomponenten haben und trotzdem kann eine konstante Anzahl dieser Komponenten noch lineare Größe aufweisen, also O(n) Größe haben.
Genauso, wie ich es kritisch finde, in der Statistik eine Worstcase Abschätzung zu machen, bei der man annimmt, dass die gefundene Lösung orthogonal(!) zur optimalen Lösung steht. Das kommt nicht vor, insbesondere wenn es eine Abschätzung ist, die nur mit Wahrscheinlichkeit "1-δ" gültig ist. Diese Abschätzung vergleiche ich auch gerne mal mit der Physik, da steht am Ende auch nur : Erwartetes Ergebnis 4+-0.1 . Statistisch gesehen sind aber auch noch Abweichungen von 0,5 oder 0,6 möglich - nur höchst unwahrscheinlich.
Man nutzt das Konfidenzintervall um die Ergebnisse zu validieren. Was sagt Dir denn "erwartet 4, ergebnis 17". Doch wohl deutlich weniger als "erwartet 4+-0.1, ergebnis 17". Ich finde das ziemlich nützlich, schließlich sieht man deutlich, dass da wohl irgendwas schief gelaufen ist. Das einfach wegzulassen ist also keine Lösung.
@Knivil Aber auch da kann man das Selbe Argument Anwenden: Was ist, wenn das Verfahren ansich numerisch Stabil wäre, aber Mathematisch nicht sinnvoll abgeschätzt werden kann? Dann sagt dir die Schranke "taugt nichts" obwohl dort eigentlich eher "Wissen wir nicht" stehen müsste.
Das steht doch bei so einer Schranke quasi immer mit dabei. Dafür probiert man solche Verfahren ja auch aus und sieht dann, ob das Ergebnis mit der Theorie zusammenpasst oder ob es auf einer der beiden Seiten noch Nachbesserungsbedarf gibt. Was schlägst Du alternativ wenn keine gute Schranke verfügbar ist? Die Augen zumachen und hoffen, dass wohl immer alles gutgehen wird?
-
otze schrieb:
[...]
@Knivil Aber auch da kann man das Selbe Argument Anwenden: Was ist, wenn das Verfahren ansich numerisch Stabil wäre, aber Mathematisch nicht sinnvoll abgeschätzt werden kann? Dann sagt dir die Schranke "taugt nichts" obwohl dort eigentlich eher "Wissen wir nicht" stehen müsste.Worauf willst du hinaus? Es gibt eine Menge Dinge, die nützlich sind, die man aber auch total sinnfrei verwenden kann...
Ist dein Argument folgendes? Es gibt Leute, die Fehlerschranken sinnlos einsetzen, also sind jegliche Form von Fehlerschranken sinnlos.
Es sind dir hier eine Menge Motivationen für sinnvolle Beispiele geliefert worden und du wiederholst dauernd deinen zwei negativ Beispiele. Damit kannst du aber die Existenz von sinnvollen Einsatzzwecken nicht eliminieren.
-
Jester schrieb:
Was schlägst Du alternativ wenn keine gute Schranke verfügbar ist?
Das was ich grade tue: Die Sinnhaftigkeit der Schranke anzweifeln und genau analysieren, ob sie wirklich ein sinnvolles Maß zur Bewertung eines Ergebnisses darstellt. Ich hatte einige Beispiele für sinnlose Schranken gebracht, aber das Standardgegenargument, was dann kommt ist: "es ist doch erstmal toll, dass es überhaupt eine Schranke gibt". Nein, ist es nicht. Eine Schranke, die Wahrscheinlichkeiten nach oben mit >1 (immer!) abschätzt, ist nicht sinnvoll. Eine Schranke, die so breit ist, dass man mit ihr überhaupt nichts machen kann, ist nicht sinnvoll (Das ist auch ein Anwendungsfeld für Schranken: wähle die Parameter des Algorithmus so, dass die Schranke möglichst eng wird).
Und wenn man am Ende zum Schluss kommt, dass die Schranke nicht sinnvoll ist, ja was soll man dann machen? Richtig, die Schranke verwerfen und sich selbst überlegen, wie man den Algorithmus bewerten kann. Zum Beispiel kann man in der Numerik ein paar Beispiele nehmen, die dafür bekannt sind, instabile Ergebnisse hervorzubringen. Und schneidet der Algorithmus auf so einem Testfeld gut ab, dann wird er wohl taugen, völlig unabhängig davon, was die Schranke sagt. Ein ähnlicher Fall ist doch auch, wenn die Schranke den worst-case in einem Sonderfall hat, der für einen selbst völlig irrelevant ist. Dann hat die Schranke auch keinerlei Aussagekraft.
Man nutzt das Konfidenzintervall um die Ergebnisse zu validieren. Was sagt Dir denn "erwartet 4, ergebnis 17". Doch wohl deutlich weniger als "erwartet 4+-0.1, ergebnis 17".
Ja, das war aber auch als Beispiel einer Schranke gedacht, die ich als sehr sinnvoll erachte. Das ist eine Schranke, die Aussagt: "mit sehr hoher Wahrscheinlichkeit wirds nicht schlechter als das". Diese Abschätzung ist viel nützlicher als: "Die Abweichung kann unendlich sein, weil die Ergebnisse Gaussverteilt sind". Und eben das ist, was ich anprangere.
-
@Knivil Aber auch da kann man das Selbe Argument Anwenden: Was ist, wenn das Verfahren ansich numerisch Stabil wäre, aber Mathematisch nicht sinnvoll abgeschätzt werden kann? Dann sagt dir die Schranke "taugt nichts" obwohl dort eigentlich eher "Wissen wir nicht" stehen müsste.
Wenn ich ganz praxisnah eine Bruecke baue und die Tragfaehigkeit simuliere ... und das Ergebnis sag: alles super! Aber die Fehlerabschaetzung sagt: sorry, traue dem Ergebnis nicht. Was wuerde ein vernueftiger Brueckenbauer dann machen?
Welchen Sinn hat diese Schranke? Vielleicht den Sinn, Menschenleben zu retten ...
Wenn man sich natuerlich nur auf die Mathematik beschraenkt :), macht es natuerlich keinen Sinn. Wobei ich Feynmann sinngemaess
wiedergeben moechte: Der Sinn hoeherer Mathematik ist nur, sich mit mehr hoeherer Mathematik zu beschaeftigen. Gut, dass ist jetzt aus dem Kontext gegriffen und soll nur zeigen, dass der Sinn von Mathematik nicht in der Mathematik selbst zu finden ist. D.h. deine Frage nach der Sinnhaftigkeit von Schranken in der Mathematik ist eine schlechte Frage.
-
otze schrieb:
Jester schrieb:
Was schlägst Du alternativ wenn keine gute Schranke verfügbar ist?
Das was ich grade tue: Die Sinnhaftigkeit der Schranke anzweifeln und genau analysieren, ob sie wirklich ein sinnvolles Maß zur Bewertung eines Ergebnisses darstellt. Ich hatte einige Beispiele für sinnlose Schranken gebracht, aber das Standardgegenargument, was dann kommt ist: "es ist doch erstmal toll, dass es überhaupt eine Schranke gibt". Nein, ist es nicht. Eine Schranke, die Wahrscheinlichkeiten nach oben mit >1 (immer!) abschätzt, ist nicht sinnvoll. Eine Schranke, die so breit ist, dass man mit ihr überhaupt nichts machen kann, ist nicht sinnvoll (Das ist auch ein Anwendungsfeld für Schranken: wähle die Parameter des Algorithmus so, dass die Schranke möglichst eng wird).
So ganz kann ich dich nicht verstehen. Eine Schranke, die schlechter ist als eine triviale Schranke, zum Beispiel eben die Wahrscheinlichkeit mit einer Zahl größer als 1 abschätzt ist unbrauchbar, keine Frage. Schließlich bekommt man dasselbe Ergebnis, nämlich dass die WK höchstens 1 ist ohne auch nur eine einzige Zeile Beweis zu brauchen. Man kann sich natürlich nun fragen, wie und warum sowas durch einen wissenschaftlichen Begutachtungsprozess gelangen kann. Das ist eine spannende und interessante Frage, aber über die Nützlichkeit von Schranken kann aus so einem Beispiel meiner Meinung nach nichts lernen. Wo also liegt Dein generelles Problem mit Schranken?
Natürlich sollte man bestrebt sein immer möglichst scharfe Schranken zu finden. Aber manchmal ist das einfach unglaublich schwer, trotzdem ist es dann immer noch besser eine scharfe Schranke zu haben als garkeine. Ist man damit noch nicht zufrieden gibt es ja noch eine Reihe von Möglichkeiten, mit denen man weiterkommen kann -- vieles davon wurde ja auch schon genannt. Will man weiter theoretische Garantien haben, kann man versuchen für spezielle Eingaben was besseres zu beweisen als für den allgemeinen Fall, oder man macht eine average-case analyse. Und natürlich ist es auch völlig legitim, eine praktische Auswertung zu machen und die Qualität auf (möglichst realistischen) Eingabeinstanzen bewerten um so Rückschlüsse zu ziehen. Diese Ansätze sind auch nicht prinzipiell gegensätzlich, sondern können sich im Gegenteil sehr gut ergänzen und voneinander profitieren. Keiner sagt, dass man nur eines davon machen darf. Man sollte sich schon darüber im Klaren sein, dass theoretische Aussagen oft wesentlich schlechtere Garantien angeben können, als die praktische Lösungsqualität, einem aber andererseits eine bewiesene Garantie eine Sicherheit bietet, die eine experimentelle Analyse so niemals erreichen kann. Übrigens arbeitet man auch bei der experimentellen Analyse wieder häufig mit Schranken, schließlich möchte man belegen, dass die gemessenen Ergebnisse verlässlich sind und nicht nur zufällig ganz gut waren.
-
otze schrieb:
Zum Beispiel kann man in der Numerik ein paar Beispiele nehmen, die dafür bekannt sind, instabile Ergebnisse hervorzubringen. Und schneidet der Algorithmus auf so einem Testfeld gut ab, dann wird er wohl taugen, völlig unabhängig davon, was die Schranke sagt.
Unter Umständen hast Du kein weiteres Qualitätskriterium für die Ergebnisse. Du kannst die Resultate dann nur anhand einer Schranke beurteilen.