Sect. 4: further case studies
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Part Number | 5 | |
| Number of Parts | 12 | |
| Author | ||
| License | CC Attribution - ShareAlike 3.0 Germany: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this | |
| Identifiers | 10.5446/45133 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
5
9
11
00:00
Observational studySpeciesSequenceoutputFunction (mathematics)Network topologyTerm (mathematics)SpeciesBoom (sailing)Mathematical modelScientific modellingMathematical modelMathematicsDirection (geometry)BioinformatikPropositional formulaoutputMultitier architectureInformationData miningMachine learningSet (mathematics)HeuristicOrder of magnitudeAlgorithmNP-hardComputer scienceUniverse (mathematics)Computer animation
05:58
Observational studyNumberRankingSequenceNetwork topologyInformationMereologySpeciesSlide ruleSpeciesInequality (mathematics)Direction (geometry)Boom (sailing)Computer animation
07:49
Observational studyEstimationInformationSet (mathematics)Matrix (mathematics)Computer animation
11:03
Observational studyVertex (graph theory)SpeciesElectric currentSpeciesLebendigkeit <Informatik>Boom (sailing)Stress (mechanics)Atomic nucleusData compressionComputer animation
14:32
Observational studyProcess (computing)ChainMarkov chainTheoryBit rateStochasticConstraint (mathematics)Lösung <Mathematik>Linear algebraBerechnungMatrix (mathematics)StatisticsGaussian eliminationZusammenhang <Mathematik>KanteMeasured quantityRow (database)Mathematical modelStochastic processDurchschnitt <Mengenlehre>HöheInformationBoom (sailing)Markov chainDirection (geometry)Complete metric spaceLogical constantComputer animation
19:52
Sample (statistics)SequenceSpeciesObservational studyBit rateData modelSlide ruleTheoryFrequencyProcess (computing)Distribution (mathematics)Mechanism designNetwork topologyDistanceWasserdruckDirection (geometry)SquareSummationEUKLID <Programm>BerechnungForceStochasticProcess (computing)Stochastic processComputer scienceSample (statistics)Durchschnitt <Mengenlehre>Parameter (computer programming)ProzessmodellBus (computing)EstimationBoom (sailing)Computer animation
23:20
Observational studyRankingSlide ruleStochasticVariable (mathematics)Sample (statistics)Network topologySequenceSpeciesPoisson processNumberInformationStochastic processInequality (mathematics)Matrix (mathematics)AlgorithmSet (mathematics)ProteinParameter (computer programming)SpeciesSummationSquareSound effectObservational errorMaximum (disambiguation)StatisticsEstimationStatistikerSymmetry (physics)Probability distributionLogarithmKonvexe FunktionMathematical analysisSystem of linear equationsDerived set (mathematics)PhysikComputer animation
28:37
Observational studyException handlingStochasticNetwork topologyRootProcess (computing)Sample (statistics)Set (mathematics)AlgorithmScientific modellingStochastisches ModellComputer scienceStatisticsInformationComputer animation
29:55
Network topologyObservational studyRoute of administrationAlgorithmComputer scienceInformationInferenceProgrammer (hardware)Computer animation
31:40
Graph coloringObservational studyClassical physicsFunction (mathematics)Graph (mathematics)outputVertex (graph theory)GRABE <Programmiersprache>Physical quantityKanteComputer animation
32:52
Observational studyLatent heatVertex (graph theory)Graph coloringComputer animation
35:02
Observational studyGraph (mathematics)Reduction of orderVertex (graph theory)Computer programKanteMathematicsFile formatEckeWordVierfarbensatzZahlOrder of magnitudeInterface (chemistry)Computer animation
40:39
Observational studyBoundary value problemSlide ruleReduction of orderoutputFunction (mathematics)Task (computing)LengthSet (mathematics)Task (computing)Computer animation
43:00
Observational studyTask (computing)Optimization problemSet (mathematics)Computer animation
44:15
Observational studyBounded variationSet (mathematics)Kapazität <Mathematik>Lotus SametimeComputer animation
45:28
Observational studyFrequencyWorkstation <Musikinstrument>Cellular automatonLatent heatConcentricCircleFrequencyRange (statistics)Computer animation
49:50
FrequencyObservational studyWorkstation <Musikinstrument>Cellular automatonSlide ruleGraph (mathematics)Function (mathematics)SubsetoutputVertex (graph theory)MassKanteFrequencySet (mathematics)Finite setMathematicsComputer animation
52:17
Observational studyRevision controlSlide ruleCellular automatonInformationAlgorithmoutputFunction (mathematics)Identical particlesDecision theoryFrequencyAlgorithmCarry (arithmetic)Decision theoryoutputComputer animation
55:18
Observational studyCovering spaceSubsetInfinityoutputFunction (mathematics)Element (mathematics)Partition (number theory)Physical quantitySet (mathematics)SubsetSpeciesComputer animation
58:11
Observational studyGraph (mathematics)outputSubsetInfinityFunction (mathematics)Vertex (graph theory)Element (mathematics)Canonical ensembleFinite setSubsetSet (mathematics)Computer animation
01:00:25
Observational studyCovering spaceoutputSubsetInfinityFunction (mathematics)Element (mathematics)Partition (number theory)Graph (mathematics)Vertex (graph theory)Wave packetWorkstation <Musikinstrument>AlgorithmUniverse (mathematics)SubsetComputer animation
01:02:07
Observational studyoutputWave packetFunction (mathematics)Workstation <Musikinstrument>Stress (mechanics)Set (mathematics)InformationService (economics)HeuristicSubsetOrbitComputer animation
01:04:48
Observational studyWave packetReduction of orderWorkstation <Musikinstrument>Instance (computer science)Mathematical optimizationFeasibility studyLösung <Mathematik>Order of magnitudeAlgorithmOrbitStress (mechanics)Link (knot theory)Process (computing)Fluktuations-Dissipations-TheoremMachine learningSet (mathematics)Computer scienceComputer animation
01:12:43
Observational studySlide ruleComponent-based software engineeringData compressionZusammenhang <Mathematik>Stress (mechanics)ZugriffOrder of magnitudeProcess (computing)Row (database)Constraint (mathematics)Atomic nucleusComputer animation
01:16:28
Observational studyLösung <Mathematik>BerechnungMatrix (mathematics)Torsion of a curveComputer animation
01:17:54
Observational studyoutputPoint (geometry)InfinityFunction (mathematics)Finitary relationEstimationPlane (geometry)Systems <München>StatisticsLinear regressionPhysical quantityZusammenhang <Mathematik>LinieMeasured quantityWasserdruckSquarePhysical quantityComputer animation
01:20:24
Observational studyProcess modelingData modelApproximationoutputInfinityPoint (geometry)Function (mathematics)EstimationFinitary relationPlane (geometry)Thermodynamic equilibriumStatisticsLinear regressionForceSquareSummationForceComputer animation
01:21:54
Observational studyPoint (geometry)Process modelingDistanceSquareVertical directionDirection (geometry)DistanceTerm (mathematics)EUKLID <Programm>Computer animation
01:23:04
Observational studyProcess modelingSquare numberVertical directionDistancePoint (geometry)SquareSummationObservational errorSound effectComputer animationDiagram
01:24:37
Observational studyProcess modelingVertical directionSquare numberDistancePoint (geometry)EstimatorStatisticsIdentical particlesPhysical lawNichtlineares GleichungssystemMaxima and minimaSymmetry (physics)Random numberError messageSquareSound effectKonvexe FunktionConvex functionEstimatorMaximum (disambiguation)StatisticsMathematical analysisDerived set (mathematics)LiniePhysikComputer animationDiagram
01:27:12
Observational studyPoint (geometry)Process modelingDistanceEstimatorEstimationSquareComputer animationDiagram
01:28:30
Observational studyStatisticsIdentical particlesSquare numberDistancePhysical lawEstimatorNichtlineares GleichungssystemMaxima and minimaSymmetry (physics)Random numberError messageIntegerLinear programmingComputer programSheaf (mathematics)Symmetry (physics)Probability distributionDirection (geometry)Scientific modellingSet (mathematics)Constraint (mathematics)AlgorithmProgrammer (hardware)InternetComputer animation
Transcript: German(auto-generated)
00:04
Okay, so und dafür sehen wir uns jetzt ein konkretes Beispiel an mit einigen, denke ich, überraschenden Erkenntnissen.
00:22
Vielleicht vorneweg alle diese Probleme, sowohl die hier eben Setcover, was Sie da links an der Tafel sehen, als auch das jetzt hier, sind wieder NP-schwer. Ich wiederhole es mal wieder, was das heißt. Für jeden Algorithmus, den man sich nur irgendwie vorstellen kann, egal ob die Menschheit ihn gefunden hat oder nicht,
00:42
kann man Beispiele von moderater Größe basteln, sodass dieser Algorithmus auf diesen Beispielen länger braucht, als das Universum ihm noch Zeit geben wird. So, hier also noch eine ganz kurze Bemerkung. Schauen Sie sich das vielleicht in
01:01
Ruhe nochmal als Verständnisprobe an, dass das Note-Cover-Problem, das wir hier eingeführt haben, dass das verstanden werden kann als ein Spezialfall des Hitting-Sets-Problemen, nämlich wo die ganzen Teilmengen, die überdeckt werden sollen durch Elemente von F, alle Kardinalität 2 haben.
01:24
So, und hier ist die besagte Anwendung, von der ich sprechen möchte. Hat jemand von Ihnen Optimierungsalgorithmen bei mir gehört? Wenn das nicht der Fall ist, dort betrachte ich dasselbe Beispiel unter
01:41
etwas anderen Gesichtspunkten. Falls jemand nächstes Semester bei mir Optimierungsalgorithmen hören wird, seien Sie vorgewarnt, Sie werden dieses Beispiel nochmal wieder sehen. Aber wir reden hier nur von ein paar Minuten Redundanz zwischen zwei Vorlesungen, glaube ich, jetzt nicht so dramatisch. So, worum geht es? Die Grundmenge F ist die Menge aller Bahnhöfe in Deutschland. Und diese Teilmengen, die überdeckt werden sollen, sind Zugläufe.
02:22
Ja, also wenn Sie einen Zug haben, der beispielsweise von Heidelberg nach Frankfurt über Darmstadt fährt, dann entspricht ihr einer gewissen Menge von Bahnhöfen, einer gewissen Teilmenge, der Menge aller Bahnhöfe in Deutschland. Dazu gehören eben Frankfurt, Langen, Darmstadt, je nachdem,
02:44
Darmstadt Süd, Darmstadt Eberstadt, Bickenbach und so weiter und so fort. Bis Heidelberg Hauptbahnhof. Ja, das heißt also, für unsere Zwecke hier wollen wir oder macht es Sinn, jeden Zuglauf als eine Menge von Bahnhöfen zu betrachten.
03:03
Alle weiteren Informationen, wann der Zug fährt, ob er jeden Tag fährt, ob Fahrradmitnahme und so weiter, sind irrelevant an dieser Stelle. So, was wollen wir hier? Wir wollen eine kleinste, möglichst geringe Anzahl von Art-Service-Stationen, sodass jeder Zug
03:20
wenigstens an einer dieser Service-Stationen hält, dass also jeder Zug mindestens an einer dieser Stationen bedient werden kann. So, was Sie hier sehen, ist das ICE-Netz aus dem Jahre, ich glaube 1997. Ich habe mir die Freiheit genommen, dieses Bild nicht jedes Jahr zu aktualisieren.
03:43
Also bleibt es bei 97 oder 98 oder so etwas, aber für die Zielsetzung ist das ja auch egal. Und wenn Sie jetzt hier beim ICE-Netz, die dieses Problem lösen wollen, dann werden Sie feststellen, dass das Ergebnis nicht als überraschend ist.
04:05
Sie können fast von der Geografie her raten, um welche Bahnhöfe es sich handelt. Das ist Berlin, natürlich noch nicht Hauptbahnhof, gab es damals noch nicht. Berlin Zoo oder Berlin Spandau oder so etwas. Berlin Zoo müsste es wohl sein.
04:23
Hannover Hauptbahnhof, Köln Hauptbahnhof, Frankfurt Main Hauptbahnhof, Stuttgart Hauptbahnhof, München Hauptbahnhof. Nicht weit überraschend, hätte man auch per Hand machen können. Ja, mit der einfachen Heuristik. Die bekanntesten, größten Städte sind mit größter Wahrscheinlichkeit auch die zentralsten Punkte im ICE-Netz und sind daher die besten Kandidaten.
04:48
Wenn Sie das Ganze aber für das gesamte Zugnetz betrachten, dann sieht es nicht mehr so ganz einfach aus, die wirklich optimale Lösung hinzukriegen.
05:01
Das hier ist übrigens die wirklich optimale Lösung. Beachten Sie nochmal, was ich eben gesagt habe. Die Problemstellung ist nb schwer. Das heißt, es gibt Beispiele von Moderatorgröße und Moderat heißt um viele Größenordnungen kleiner als dieses reale Beispiel.
05:22
Beispiele von Moderatorgröße. Für jeden Algorithmus gibt es solche Beispiele, an denen dieser Algorithmus sich tot läuft. Und dennoch muss man nicht die Flinte ins Korn werfen, denn diese Optimallösung ist auf überraschend einfache Art und Weise gefunden worden.
05:43
Und zwar etwas, was man, wenn man, wenn man irgendwelche Probleme löst, in der Informatik immer machen sollte, egal ob es klassische Algorithmiken ist oder Data Mining oder irgendwas im maschinellen Lernen oder wo auch immer, Datenbanksysteme, egal wo.
06:06
Schauen Sie, ob Sie einfache Möglichkeiten des Pre-Processings finden, in denen Sie die Datenmenge reduzieren, indem Sie redundante Daten eliminieren. Daten, von denen Sie sagen können, die brauche ich nicht fürs Endergebnis.
06:23
Hier in diesem Beispiel ist das so, nehmen wir zwei Bahnhöfe her. Darmstadt-Hauptbahnhof und Darmstadt-Süd. Ich bin mir nicht sicher, ich weiß es nicht hundertprozentig, aber ich bin mir ziemlich sicher, dass jeder Zug, der in Darmstadt-Süd hält, auch in Darmstadt-Hauptbahnhof fällt.
06:41
Aber nicht umgekehrt. Ja, Züge, die nach Mainz und nach Aschaffenburg fahren, halten zwar in Darmstadt-Hauptbahnhof, aber nicht in Darmstadt-Süd. Aber umgekehrt, es gibt keinen Zug, der in Darmstadt-Süd einsetzt, sondern alle fahren auch durch Darmstadt-Hauptbahnhof durch oder enden da.
07:00
Und das heißt, Sie können Darmstadt-Süd rausschmeißen, weil, wenn es eine Optimallösung gibt, in der Darmstadt-Süd drin ist, ich hoffe, ich trete hier niemanden auf die Füße, der sich Darmstadt-Süd lokal-patriotisch verbunden führt,
07:20
wenn Sie eine Optimallösung mit Darmstadt-Süd drin haben, können Sie aus dieser Optimallösung Darmstadt-Süd rausschmeißen und Darmstadt-Hauptbahnhof stattdessen reintun. Und das ist immer noch eine zulässige Lösung mit genau derselben Anzahl von Bahnhöfen, also optimal. Also können Sie kleine Bahnhöfe rausschmeißen, was ja durchaus, denke ich, plausibel ist.
07:44
Umgekehrt, jetzt betrachten wir zwei Züge, beispielsweise die von Darmstadt nach Frankfurt-Main-Hauptbahnhof fahren. Und der eine Zug ist ein schneller Zug, der hält nur in Darmstadt, Langen und Frankfurt.
08:10
Und der andere Zug, der hält an jeder Milchkanne, die S3 oder sowas. Dann können Sie diesen zweiten Zug, der überall hält, rausschmeißen.
08:25
Warum? Vielleicht auch wieder eine Zeichnung, um das klarzumachen.
09:11
So, Sie haben jetzt einen Zug, der hält wirklich häufig an vielen, vielen Bahnhöfen.
09:30
Sie haben jetzt einen anderen Zug, ich mal das mal so, der jetzt nur an einzelnen wenigen Bahnhöfen hält. Vielleicht gar nicht mal an beiden Endbahnhöfen, der zwischendurch durchfährt.
09:47
Eine nicht untypische Situation, die ich gleich mal auf dem Foto verewigen muss.
10:14
Und wenn Sie eine optimale Lösung haben, oder überhaupt eine Lösung, eine Überdeckung haben,
10:25
dann ist da natürlich einer von den fünf Bahnhöfen des Schnellzugs drin. Irgendeiner von denen, zum Beispiel der zweite oder irgendein anderer. Und damit ist automatisch dann auch der Bummelzug überdeckt.
10:41
Das heißt, um eine Überdeckung zu finden, brauchen Sie den Bummelzug gar nicht. Jede Lösung, die den Schnellzug überdeckt, überdeckt auch den Bummelzug. Das heißt, Sie können den Bummelzug aus der Betrachtung rausschmeißen. An dieser Stelle eine Warnung. Es gibt zu dem Thema eine Übungsaufgabe.
11:02
Und ein gewisser Prozentsatz von Studierenden kommt bei mir mit Problemen an, dass sie es nicht lösen können oder sie haben eine falsche Lösung raus, weil sie an dieser Stelle nicht genau geschaut haben, wie das ist, welchen Zug man rausschmeißt, sondern weil sie intuitiv gedacht haben, dass der Schnellzug rausgeschmissen werden kann.
11:23
Das ist aber nicht so. Das mag vielleicht eher der Intuition entsprechen. Und darauf sind im Laufe der Jahre schon etliche Studierende bei der Bearbeitung dieser Übungsaufgabe hereingefallen, auf ihre Intuition. Aber es ist in Wirklichkeit der Bummelzug, der rausgeschmissen werden kann, nicht der Schnellzug.
11:46
Also achten Sie darauf. So, jetzt kann man also hergehen und alle Bahnhöfe rausschmeißen, wie Darmstadt Süd. Das sind ja schon mal eine ganze Menge, denke ich. Und Sie können auch alle Züge rausschmeißen, nach dieser Regel eben hier an der Tafel.
12:05
Und damit ist die Geschichte noch nicht zu Ende, denn Sie können auch weitermachen. Sie schmeißen erst einen Haufen Bahnhöfe raus, Sie schmeißen einen Haufen Züge raus. Sie werden in der Übungsaufgabe feststellen, dass Sie dann wieder Bahnhöfe möglicherweise rausschmeißen können,
12:21
nachdem Sie Züge rausgeschmissen haben. Und dass Sie dann wieder Züge rausschmeißen können und so weiter und so fort. Also jede Möglichkeit, Züge rauszuschmeißen, liefert potenziell wieder neue Möglichkeiten, Bahnhöfe rauszuschmeißen. Jede Möglichkeit, die Sie verwendet haben, um Bahnhöfe rauszuschmeißen, gibt Ihnen neue Möglichkeiten, Züge rauszuschmeißen.
12:43
Und das Endergebnis der ganzen Sache, wenn Sie das bis zum bitteren Ende durchführen, dieses Pre-Processing, nur Pre-Processing zur Datenreduktion, liefert Ihnen bei den ICEs sechs Bahnhöfe, jeweils mit einem Zug drauf.
13:02
Und hier, bei dem größeren Beispiel, liefert Ihnen dieses Bild. Ich muss Ihnen das erklären, was hier zu sehen ist. Und zwar, Kern der Übungsaufgabe wird sein, dass Sie an einem selbstgebastelten Beispiel einsehen können,
13:21
selbst wenn der Graf ursprünglich zusammenhängt war, kann durch diese Datenreduktion es passieren, dass dieser Graf hochgradig unzusammenhängt wird. Ja, dass beispielsweise Züge rausgeschmissen werden. Also letztendlich läuft es darauf hinaus, dass irgendwann mal ein Zug rausgeschmissen werden kann, der einen Teil des Grafen mit einem anderen Teil verbindet.
13:44
Und das war die letzte Verbindung. Und danach sind diese zwei Teile unzusammenhängt. Das ist auch Teil der Übungsaufgabe anhand dessen Sie das dann letztendlich einsehen können. Das kann bis dahin führen, bis zu einzelnen isolierten Knoten,
14:04
bei denen jeweils ein Zug auch bis zu diesem einen Knoten geschrumpft wurde. Das heißt also, dass Sie Zugläufe haben, die ursprünglich mit 20, 30 Bahnhöfen oder wie auch immer, die Sie anlaufen, begonnen haben. Und durch sukzessive Datenredaktion reduzieren sich dieser Zugläufe auf einen einzigen Bahnhof.
14:25
Und dieser Bahnhof ist isoliert vom Rest des Grafen. Und das Interessante, was mich dazu bewogen hat, erst mal 14 Tage nach dem Fehler zu suchen, weil ich das Ergebnis nicht glauben wollte, das Interessante ist, dass Sie auf die Art und Weise tatsächlich hier in diesem Beispiel mit den ICEs
14:48
diese sechs Bahnhöfe jeweils mit einem zu einem Bahnhof reduzierten Zuglauf herausbekommen. Hier sieht das Bild komplizierter aus. Sie haben schon, wie Sie sehen, im Wesentlichen genau dasselbe,
15:03
nämlich Reduktion auf einzelne isolierte Bahnhöfe, wo dann jeweils ein Zug noch drauf ist, der dann natürlich nicht mehr weiter reduziert werden kann. Sie haben jetzt hier noch so ein paar einfache kleine Zusammenhangskomponenten, die nicht in sich reduziert werden können.
15:24
Aber das ist kein Problem. Sie sehen ja von dem Bild hier, wie klein diese Zusammenhangskomponenten sind. Hier drei Kanten, hier vielleicht vier Kanten und vier Knoten. Sehr kleine Zusammenhangskomponenten. Da können Sie natürlich jeweils mit brute force das beste Ergebnis in jeder dieser kleinen Zusammenhangskomponenten bauen,
15:42
indem Sie einfach alles ausprobieren, was möglich ist. Wir haben das Ganze ausprobiert mit allen möglichen Datensätzen aus Europa, aus allen möglichen Ländern, mit allen möglichen Einschränkungen auf Gattungsklassen, so wie hier ICEs. Und das Größte, was wir mal an übrig gebliebener Zusammenhangskomponenten gefunden haben,
16:06
war in der Tschechi, waren 29 Knoten, von denen fünf Knoten die optimale Überdeckung dieser Zusammenhangskomponenten geliefert haben. Auch das eine Größenordnung, die man noch mit brute force, mit Gewalt, mit dummem Ausprobieren lösen kann.
16:29
Also, eine wichtige Moral. Ich habe lange überlegt, ob ich das Wort Moral hier hinschreiben soll, aber mir ist nichts besseres eingefallen. Also im Englischen kann man das Wort Moral an dieser Stelle genauso verwenden, wie hier die Moral von der Geschichte.
16:48
Nicht die einfachen Dinge, die man tun kann, übersehen. Ja, es ist sehr häufig so. Das ist übrigens auch etwas durchaus, was Sie, das werden Sie nicht sehen können,
17:01
aber was ich Ihnen sagen kann, was bei ILOG sehr wichtig ist, dass ILOG überhaupt eine Chance hat, für große Problemstellungen in adäquater Zeit Lösungen vorzuschlagen,
17:21
Lösungen zu Berechnungen vorzuschlagen, hat sehr viel damit zu tun, dass da sehr aggressive solche Pre-Processing-Sachen passieren. Dinge, die Sie aus der linearen Algebra kennen, Elimination von redundanten Spalten oder Zeilen, Reduktion von Matrizen auf ihren Rang, kommen Ihnen dunkel bekannt vor, diese ganzen Begriffe.
17:43
Die spielen in dem, womit Sie da arbeiten, mit ILOG eine zentrale Rolle. Ja, das ist dieses Thema und das nächste Thema ist dann wieder eines, wo ich weniger von Erfolgen berichten möchte,
18:05
sondern wieder eher etwas kritischer drauf zu sprechen kommen möchte. Das Problem kennen Sie aus der Matte 3, denke ich aus der Statistik. Sie kennen es vielleicht als lineare Regression, sagt Ihnen der Bericht was, oder als Methode der kleinsten Quadrate, als Gaussche Methode, also nicht Gaussche Eliminationsverfahren für lineare Gleichungssysteme,
18:27
sondern als Gaussche Methode in der Statistik, sagt Ihnen das was? Kleinste Quadrate, ok. So, ganz abstrakt gesprochen, was ist das Problem? Sie kennen, Sie haben zwei verschiedene Größen, zum Beispiel physikalische Größen,
18:46
und Sie wissen aus Ihren physikalischen Überlegungen heraus, dass es da eigentlich einen affin-linearen Zusammenhang geben muss, geben sollte, oder Sie vermuten es und wollen es nachprüfen, ob das wirklich so ist.
19:03
Sie kriegen aber Ihre Messergebnisse natürlich durch irgendwelche Einflüsse total verrauscht. Alles, nur kein linearer Zusammenhang, was Sie da rauskriegen. Und jetzt wollen Sie, also was Sie haben sind diese Messpunkte hier.
19:21
Im einfachsten Fall, wir bleiben im zweidimensionalen Fall, weil bei dem worum es mir geht, ist es egal wie viel Dimension. So, und jetzt wollen Sie eine Gerade durchziehen, die diese Messpunkte möglichst genau approximiert. Als die Gerade, die den affin-linearen Zusammenhang zwischen den beiden Messgrößen angeht.
19:42
Affin-linear, denken Sie beispielsweise an den Druck, den man beim Tauchen hat. Ja, das beginnt nicht bei null an der Wasseroberfläche, weil nämlich schon die Tonne pro Quadratmeter von der Luftsäule, von der Atmosphäre schon obendrauf ist.
20:01
Und dann kommt der lineare Zusammenhang, Wassertiefe und Wasserdruck oben noch obendrauf. Deshalb eben nicht unbedingt beginnen am Nullpunkt, sondern etwas versetzt. Da ist eben der Druck, den man beim Tauchen hat, ein Beispiel dafür.
20:24
So, also, hier geht es weniger darum, noch irgendwelche coolen neuen Beispiele zu finden, sondern eher um einen allgemeinen Kritikpunkt nochmal klar zu machen. Denn ich nehme mal an, dass es bei Ihnen auch mehr oder weniger recht kritiklos die Methode der kleinsten Quadrate reingenommen wurde.
20:48
Sozusagen nicht mehr die Zielsetzung, wir wollen eine Gerade durchlegen und müssen uns erstmal überlegen, was das eigentlich heißt, sondern wir wissen, was es heißt, nämlich die Summe der Quadrate minimieren, kleinste Quadrate berechnen.
21:04
So, in meiner bescheidenen Meinung, noch ein zweites Wort für bescheiden, wir hatten vorhin modest, jetzt humble, ist das ein gutes Beispiel für diese Problematik. So, wie kann man sich das jetzt vorstellen?
21:27
Also, auch wieder so ähnlich wie beim Grafenzeichnen, wie wir das letztes Mal hatten, dass wir die Gerade aufhängen, dass jeder Knoten eine Kraft ausübt, eine anziehende Kraft auf die Gerade
21:41
und das Equilibrium dieser einzelnen, verschiedenen Kräfte, die auf die Gerade wirken, ergibt dann tatsächlich die Gerade, die am Ende rauskommt. So, zunächst einmal, ich weiß nicht, ob das thematisiert wurde, aber es ist nicht von vornherein klar,
22:00
dass man die Distanz zu dieser Gerade, wie bei der Methode der kleinsten Quadrate, in vertikaler Richtung misst. Man könnte sie zum Beispiel auch in perpendicular, in orthogonaler Richtung, in senkrechter Richtung zur Gerade messen. Es gibt durchaus mathematische Ansätze, die das tun, ist aber schwieriger, wird ziemlich schnell kompliziert,
22:24
vor allem in mehreren Dimensionen dann. Also, hier ist zunächst einmal, machen Sie sich klar, hier ist zunächst einmal von vornherein eine Entscheidung getroffen worden bei der Methode der kleinsten Quadrate, dass man die Abstände in vertikaler Richtung misst. Warum? Offensichtlich, weil es einfach zu messen ist und einfach dann zu behandeln ist.
22:45
Das sind ja nur Differenzen auf der Y-Koordinate, während es hier natürlich schon ein bisschen komplizierter wird. Die Differenzen in der senkrechter Richtung zur Gerade, da haben Sie schon mal quadratische Thermo- und Wurzeln drin. Euklidische Distanz, Quadrierung, Wurzel, wird schon mathematisch komplizierter.
23:07
Kleinste Quadrate Methode kennen Sie. Das heißt, wir nehmen, nochmal zum Bild zurück, wir nehmen die vertikalen Distanzen zu der Gerade, die wir berechnen wollen, die wir nicht haben, und nehmen das Quadrat jeweils von der Distanz
23:26
und wir wollen die Gerade so durch die Punkte legen, dass die Summe dieser quadrierten Distanzen minimal wird. Ich weiß nicht, ob das 1 zu 1 dementsprech, also ob die Methode der kleinsten Quadrate so eingeführt worden ist,
23:45
aber egal wie sie eingeführt worden ist, ist es letztendlich dasselbe. So, jetzt gibt es aber hier ein kleines Problem. Ich weiß nicht, ob darüber erzählt worden ist in der Matte 3. In früheren Jahren habe ich auch immer gefragt, die Leute haben mir gesagt, dass darüber nicht erzählt worden ist.
24:05
Das Problem ist, wenn Sie die Distanzen quadrieren, dann heißt es, dass Ausreißer einen deutlich überproportionalen Effekt auf das Ergebnis haben. Ausreißer sind aber typischerweise Messungenauigkeiten, Messfehler.
24:23
Muss nicht unbedingt sein, aber sind typischerweise. Damit haben Sie erst mal ein methodisches Problem drin, dass Sie Messfehler überproportional im Ergebnis gewichtet eingehen haben. So, warum zur Hölle also die Quadrate nehmen?
24:46
Eigentlich würde es sich sogar eher anbieten, anstelle einer konvexen Funktion wie die Quadrate, eine koncave Funktion wie etwa den Logarithmus oder die Wurzel zu nehmen, damit eben Ausreißer möglichst wenig Effekt haben.
25:02
Warum Quadrate? Das hat verschiedene Gründe. Ich möchte Sie zunächst mal auf den letzten Punkt hier aufmerksam machen, was wahrscheinlich letztendlich der Hauptgrund ist. Davon haben Sie sicherlich einen Eindruck bekommen in der Matte 3. Nämlich, wenn Sie die Quadrate nehmen, dann lässt sich das Ganze sehr leicht mathematisch behandeln.
25:26
Es lässt sich reduzieren, das haben Sie sicherlich gesehen, auf die Lösung eines Linienangleichungssystems. Was mit anderen Modellierungen, die vielleicht adäquater wären, nicht der Fall ist. Das kommt Ihnen bekannt vor, dass man mit oder der kleinsten Quadrate reduziert das Problem auf die Lösung eines Linienangleichungssystems.
25:49
Was letztendlich im höher Dimensionalen, das ist, was Sie aus der eindimensionalen Analysis kennen, etwas zu minimieren, was quadratisch ist.
26:03
Die Ableitung ist linear und genau das haben Sie im mehr Dimensionalen, ein lineares Gleichungssystem. Es gibt noch mehr Gründe, dass man das aus der Physik begründen kann, was natürlich eine sehr schwache Begründung ist.
26:23
Das ist letztendlich eine ähnliche Begründung wie in der Astrologie, was oben in den Sternen ist, ist unten auf der Welt. Begründung durch Analogie ist keine valide Begründungsform. Man kann sich höchstens dadurch leiten lassen, um Neuerkenntnisse zu gewinnen, aber das nicht als Begründung hernehmen.
26:45
Es gibt durchaus noch einen ernstzunehmenderen Grund, warum man das macht. Vielleicht ist Ihnen in der Matte 3 der Maximum Likelihood Schätzer untergekommen. Das ist ein Fall von Maximum Likelihood Schätzer.
27:03
Das ist das, was man in der Regel in der Statistik macht. Man muss sich klar machen, was ein Maximum Likelihood Schätzer eigentlich ist. Das kann man sich an diesem Beispiel sehr gut klar machen. Das finden Sie laufen. Statistische Ergebnisse sind typischerweise, also analytische Statistische Ergebnisse, nicht nur
27:23
diskriptive Statistische Ergebnisse, sind typischerweise auf einer Maximum Likelihood Schätzung basierend. Es ist nicht die Gerade, die auf Basis dieser einzelnen Punkte die Wahrscheinlichste ist, denn das können wir gar nicht berechnen,
27:44
sondern es ist die Gerade, unter der diese Punkte als Statistisches Ergebnis die höchste Wahrscheinlichkeit haben. Wenn die Gerade hier oben verlaufen würde, im Extrem, dann wären diese Punkte sehr unwahrscheinlich.
28:05
Wenn Sie näher rankommen, wahrscheinlich ja. Wenn Sie die Gerade hier platzieren, aber ein bisschen schräger oder horizontal, wären diese Punkte weiterhin unwahrscheinlich. Und am wahrscheinlichsten werden diese Punkte als Statistisches Ergebnis, wenn
28:25
Sie die Gerade reinsetzen, die die Methode der kleinsten Quadrate liefert. Das ist in vielen Situationen bei perfekter Symmetrie der Wahrscheinlichkeitsverteilung ist das durchaus richtig.
28:44
Darüber hinaus ist das nicht unbedingt richtig, wenn man wirklich die Wahrscheinlichste Gerade haben will. So, damit sind wir an dieser Stelle für heute auch mit der Zeit fertig und wir sind auch mit diesem ganzen Abschnitt fertig.
29:04
Das war jetzt ein schönes Intermezzo. Wir hatten zuerst angefangen mit OBL, haben dann jetzt so ein bisschen mit algorithmischen Problemen rumhandiert. Jetzt kommen wir in eine Richtung, die einiges mit OBL Modellierung zu tun hat, nur eingeschränkter. Wir werden also nicht den gesamten Sprachumfang von OBL verwenden, sondern nur eingeschränkte Modelle betrachten und werden sehen,
29:29
dass es mit dieser eingeschränkten Modellbildungsmöglichkeit immer noch eine ganze Menge überraschender Möglichkeiten gibt, Dinge zu modellieren. Warum betrachten wir diese Einschränkung? Weil sie haben vielleicht auf der DVD das Wort C-Plex gesehen.
29:50
Algorithmen wie dieser C-Plex können genau so etwas lösen, mit dem wir uns ab dem nächsten Mal beschäftigen. Ganz zahlich lineare Programme und sonst können die nichts gut lösen.
30:02
Das ist viel, viel besser algorithmisch handhabbar als das, was OBL insgesamt an Sprachumfang bietet. So, aber das wie gesagt beim nächsten Mal. Für heute mache ich erst mal hier Schluss und würde mich freuen Sie beim nächsten Mal wiederzusehen. Bis dann.