mikrocontroller.net

Forum: PC-Programmierung C++ stabile Parameter bei F-Optimierung


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
Autor: Sun++ (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Keiner N. (nichtgast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Wilhelm M. (wimalopaan)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Mr. Meeseeks look at me (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Hans (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Echter Programmierer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Sun++ (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Sun++ (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: TP (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Gau?-Tiefpass drüber und dann Minium suchen

Autor: foobar (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Sun++ (Gast)
Datum:
Angehängte Dateien:
  • preview image for b.png
    b.png
    19,2 KB, 34 Downloads

Bewertung
0 lesenswert
nicht lesenswert
> 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...

Autor: foobar (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>> 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 ;-)

Autor: Sven B. (scummos)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Echter Programmierer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Sun++ (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Sun++ (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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.

Autor: Wilhelm M. (wimalopaan)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: xyz (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Evtl. könnte sowas interessant für dich sein:

https://de.wikipedia.org/wiki/Evolution%C3%A4rer_Algorithmus

Autor: mh (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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".

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.