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.
> 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.
