Hallo, wenn man eine Funktionsoptimierung durchführt (testen aller möglichen Kombinationen) um die Funktionsparameter für das globale Minimum zu finden, dann kann es leider sein, dass das globale Minimum kein "stabiles" Parameterfeld ist. Ein Beispiel hier nur mit einem Parameter: Parameter -> Wert(Funktions-Output): 1 -> 10 2 -> 8 3 -> 5 4 -> 3 5 -> 5 6 -> 7 7 -> 11 8 -> 20 9 -> 30 10 -> 1 11 -> 25 12 -> 23 Das globale Minimum ist Parameter 10 mit Output 1 aber das ist im Kontext der naheliegend Werte ein Ausreißer also liegt nicht in einem stabilen Parameterfeld. Der gewünschte Parameter wäre natürlich 4 mit dem Output 3 da die Outputs der umliegenden Parameter viel näher sind und so der Parameter 4 in einem stabilen Parameterfeld liegt. Das bedeutet das lokales Minimum ist anhand der Stabilität besser als das globale. Meine Frage ist jetzt, wie finde ich in C++ das möglichst kleinste Minimum mit stabilem Parameterfeld heraus? Das Ganze natürlich nicht nur auf eine Dimension beschränkt sondern höher-dimensional mit zB 10 Input-Parametern. Nach der Funktionsoptimierung bzw dem Durchlaufen aller Kombis liegt eine Tabelle mit allen Parameterkombis und Outputs vor und müsste dann entsprechend untersucht werden. Welche Methoden gibt es denn um das zu machen? Vielleicht hat auch direkt jmd einen Tipp für eine Lib und dem Namen einer entsprechenden Methode? Grüße
Musste den Text mehrmals lesen um zu verstehen was du willst. Spontan würde ich sagen differenzieren und dann das minimum suchen, dessen diff ein gewisses Maß nicht überschreitet.
Sun++ schrieb: > Hallo, > > wenn man eine Funktionsoptimierung durchführt (testen aller möglichen > Kombinationen) um die Funktionsparameter für das globale Minimum zu > finden, dann kann es leider sein, dass das globale Minimum kein > "stabiles" Parameterfeld ist. Du suchst also ein Extremum in einer diskreten Wertemenge, bei der Du glaubst, dass sie einer kontinuierlichen Funktion folgt. Wenn Du die Art der Funktion kennst, dann mach ein Parameterschätzung wie z.B. LMS. Wenn Du gar keine Ahnung von dem funktionalen Zusammenhang hast, wird es schwieriger. Du kannst erstmal Filtern, bei solchen Ausreißern eignen sich Median-Filter.
Mir kommt in den Sinn, die Varianz des Signales mit heran zu ziehen - sie gibt ja ein Maß, wie "bewegt" das Signal ist und damit, ob vermeintliche Ausreißer vielleicht doch, in dessen Natur liegen. Ich seh noch nicht, was die Aufgabe unebdingt mit C++ zu tun hat. Ist erstmal ein mathematisches Problem.
Ich glaube was du suchst nennt sich numerische Optimierung ( https://de.wikipedia.org/wiki/Optimierung_(Mathematik) ). Damit brauchst du nicht mehr den gesamten Funktionsraum samplen. Im Allgemeinen wirst du aber nie zu 100% das globale Minimum sicher finden. Vor allem bei so lästigen Problemen wie bei deinem. Also 2 Minima und dann noch das Globale ganz "schmal". Ich war zwar lange nicht überzeugt, aber in letzter Zeit mache ich sehr viel mit Differential Evolution (https://en.wikipedia.org/wiki/Differential_evolution). 73
Naja, ist doch nicht schwer. Sind doch nur drei Schritte: a.) Alle Kandidaten suchen die Dein lokales Optimum erfüllen. b.) Die gefundenen Kandidaten Bewerten. c.) Den Kandidat mit der besten Bewertung auswählen. Schritt a hast Du ja schon: Lokales Minimum. Für Schritt b musst Du Dir eben was überlegen, was zu Deiner Anwendung passt. Schritt c ist trivial.
Danke für die Antworten. Ich habe eine Idee und zwar könnte man vielleicht die Matrix so neu erstellen, dass jeder Outputwert eines Parametersets auf dem Durchschnitt des eigenen Outputwertes sowie der angrenzenden Parameter-Outputwerte beruht. So würde ein Ausreißer durch die Nachbarn runtergeholt werden und wird somit nicht überbewertet. Sozusagen eine Glättung der Matrix. Ich frage mich noch wie das für eine Mehrdimensionale Matrix dann funktioniert... und die Frage wäre auch wie viele Nachbarn man mit einbezieht von zb 1 bis x, je nachdem führt das dann zu unterschiedlichen Glättungen. Ansonsten stolpere ich immer wieder über KNN also https://de.wikipedia.org/wiki/N%C3%A4chste-Nachbarn-Klassifikation Vielleicht ist das noch besser müsste mich aber weiter einlesen. Im maschninellen Lernen gibts generell einiges aber da steige ich noch nicht so durch. @Hans eine numerische Optimierung ist korrekt aber ein evolutionärer Algo sucht allerdings wohl immer das absolut globale Minimum und nicht ein ein Minimum mit dem stabilsten Parameterraum. Ein evolutionärer Algo folgt meist einem Pfad und erzeugt auch keine gleichverteilte Matrix die man dann auswerten könnte. Daher lasse ich alle Kombinationsmöglichkeiten in definierter Schrittweite durchlaufen so erst gibt es Nachbarn. Ein Optimierer der gezielt die stabilsten Parameterräume sucht kenne ich leider nicht, sowas wäre natürlich prima.
Ich versuche später mal was. Erstmal eine gute Datenstruktur zum auslesen finden evt std::vector oder eine Matrix Lib wie "Eigen". Dann vielleicht per Rekursion ein flexible Sache bauen die auch mit unterschiedlicher Dimensionanzahl zurecht kommt...
Wie wäre es erstmal mit einer genauen Definition eines "Ausreißers"? Häufig ergibt sich dann die Behandlungsstrategie von selbst (z.B. Bandbreitenbegrenzt -> Filter). Btw, bei 10 Dimensionen eine Tabelle der Funktionswerte aller Kombinationen zu erstellen, klingt nur bedingt praktikabel.
Angehängte Dateien:
-
b.png
19 KB
> Btw, bei 10 Dimensionen eine Tabelle der Funktionswerte aller > Kombinationen zu erstellen, klingt nur bedingt praktikabel. Wie soll es sonst gehen? Alternative wäre ja nur ein Optimizer der in der Lage ist nach stabilen Minima zu suchen. Alles was ich kenne sucht das globale Minimum. > Wie wäre es erstmal mit einer genauen Definition eines "Ausreißers"? in etwa wie im Beipiel oben. Angehängt nochmal Grafisch: Parameter 10 mit Output 1 ist hier der Ausreißer ps: ich glaube was ich Suche ist sowas wie im maschine learning um sogenanntes "overfitting" zu vermeiden. Die Parameter wo die Nachbarn ähnlich sind, sind einfach vertrauenswürdiger. Wie gesagt vielleicht tut sowas wie der k-Nearest-Neighbor-Algorithmus die Sache, ich bin allerdings noch nicht durchgestiegen...
>> Btw, bei 10 Dimensionen eine Tabelle der Funktionswerte aller >> Kombinationen zu erstellen, klingt nur bedingt praktikabel. > > Wie soll es sonst gehen? Na ja, wenn jede Dimension wie im Bild z.B. nur 12 diskrete Punkte besitzt, kommen da 12 hoch 10 Werte zusammen ... >> Wie wäre es erstmal mit einer genauen Definition eines "Ausreißers"? > > in etwa wie im Beipiel oben. Wenn du das unter "genaue Definition" verstehst, wird das nichts. Warum ist dieser "Ausreißer" nicht genau das gesuchte/relevante Signal? Du machst unbewußte Annahmen über das Signal - versuch sie zu verifizieren (stimmen die Annahmen überhaupt) und dann zu konkretisieren (ab wann ist es kein Ausreißer mehr; warum?). Kenntnisse über die Art der Daten selbst und die möglichen Fehlerquellen/arten sind dabei hilfreich ;-)
Evtl. ist für sowas, falls hochdimensional, etwas Markov Chain Monte Carlo-mäßiges geeignet. Ich denke das müsste sogar natürlicherweise die Eigenschaft haben, dass es eher die großen, glatten Minima bevorzugt. Die finale Auswahl des globalen Minimums würde ich aber unabhängig vom Algorithmus "von Hand" machen, indem ich auf bestimmte Kriterien prüfe (kleine Ableitung in der Umgebung, etc). Die Optimierungsalgorithmen würde ich nur die Kandidaten dafür finden lassen.
foobar schrieb: > Btw, bei 10 Dimensionen eine Tabelle der Funktionswerte aller > Kombinationen zu erstellen, klingt nur bedingt praktikabel. Das wird er schon noch merken... Hihi... Aber zuerst muss er ja eine "flexible Sache" aus "std::vector" bauen und anschließend noch "maschine learning" machen und "overfitting" vermeiden. Da hat wohl jemand seinen 110V-Föhn an das 230V-Netz angeschlossen...
welch ein wahnsinnig konstruktiver Beitrag... Echter Programmierer schrieb: > Das wird er schon noch merken... Hihi... Bessere Idee? Natürlich könnte der RAM platzen hängt aber von der Stepsize im Parameterraum ab und es müssen sicherlich keine 10 Dimensionen sein. > Aber zuerst muss er ja eine "flexible Sache" aus "std::vector" bauen "aus" einem vector nö eher eine Klasse welche selbigen nutzt. Flexibel ja, mit einem statischen Array wirds nicht klappen. Alternativ eine matrix lib. > und anschließend noch "maschine learning" machen sicher nicht, ggf passt aber ein Werkzeug aus diesem Bereich. > und "overfitting" vermeiden. richtig > Da hat wohl jemand seinen 110V-Föhn an das 230V-Netz angeschlossen... muss ich das kommentieren oder ein psychologisches Profil daraus ableiten, ich lass es mal lieber...
@foobar: Der "Ausreißer" ist nicht genau das gesuchte/relevante Signal weil mit diesem Parameterset die Wahrscheinlichkeit höher ist, dass die Funktion bei unbekannten Daten versagt. Um eine Liste zu vermeiden, könnte man auf die Idee kommen beim iterieren der Kombinationsmöglichkeiten die Glättung schon vornehmen. Allerdings wird das nicht gehen da die Nachbarn in beide Richtungen benötigt werden, man müsste in die Zukunft sehen. Daher denke ich, kommt man um eine Liste nicht herum. @Sven: Markov Chain werd ich mal anschauen. Und "großen, glatten Minima bevorzugt" wäre super. Am liebsten würde ich nichts mehr von Hand auswählen. Ich mach erst mal die Glättungsvariante anhand der Liste. Die Ausreißer werden anhand ihrer Nachbarn normalisiert und minima im Plateau werden bevorzugt. Die Anzahl der Nachbarn 1 bis x kann man gut auf die Steps im Parameterraum abstimmen.
Wilhelm M. schrieb: > Sun++ schrieb: >> Hallo, >> >> wenn man eine Funktionsoptimierung durchführt (testen aller möglichen >> Kombinationen) um die Funktionsparameter für das globale Minimum zu >> finden, dann kann es leider sein, dass das globale Minimum kein >> "stabiles" Parameterfeld ist. > > > Du suchst also ein Extremum in einer diskreten Wertemenge, bei der Du > glaubst, dass sie einer kontinuierlichen Funktion folgt. > > Wenn Du die Art der Funktion kennst, dann mach ein Parameterschätzung > wie z.B. LMS. Wenn Du gar keine Ahnung von dem funktionalen Zusammenhang > hast, wird es schwieriger. Du kannst erstmal Filtern, bei solchen > Ausreißern eignen sich Median-Filter. Nochmal die obige Frage gestellt: kannst Du die beantworten? Andererseits: woher kommen diese "Ausreißer", wenn es denn welche sind? Den gezeigten Ausreißer könntest Du ganz einfach mit einem Median-Filter entfernen.
Evtl. könnte sowas interessant für dich sein: https://de.wikipedia.org/wiki/Evolution%C3%A4rer_Algorithmus
xyz schrieb: > Evtl. könnte sowas interessant für dich sein: > > https://de.wikipedia.org/wiki/Evolution%C3%A4rer_Algorithmus Auch dafür müsste er erstmal eine mathematische Definition seines Suchkriteriums haben. Er bleibt aber lieber bei seinem "stabilen Parameterfeld".
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.