Problemstellung
===============
Angenommen man hat eine Funktion
y = f(x)
Beispielsweise sei diese Funktion zur Linearisierung eines Sensorsignals
x, wobei y das linearisierte Sensorsignal ist. Man betrachtet das
Interval x in [a, z] (a <= x <= z). In diesem Intervall möchte man eine
Näherung der Funktion durch lineare Interpolation zwischen Stützstellen
finden. Diese interpolierte Funktion sei f'.
Man kann davon ausgehen, dass die Funktion hinreichend "wild" ist,
sodass es nicht möglich ist ein passendes Polynom oder einen anderen
funktionalen Zusammenhang zu bestimmen.
Der Speicher für Stützstellen ist begrenzt. Es gibt eine maximale Anzahl
N an Stützstellen (ki), deren Lage auf x aber frei innerhalb von [a, z]
verteilt werden kann. Das Ziel wäre natürlich die Stützstellen so zu
legen, dass insgesamt der Fehler minimiert wird (also die Abweichung der
ursprünglichen Funktion f und der interpolierten Funktion f'). Gesucht
ist also ein (möglichst effizienter) Algorithmus, der die N Stützstellen
innerhalb [a, z] so verteilt, dass der (integrale) Fehler zwischen f und
f' minimal ist.
Ein erster Gedanke
==================
Man könnte zunächst an a und z eine Stützstelle (k0, k1) legen. Die
nächste Stützstelle k2 könnte zwischen k0 und k1 eingebracht werden,
sodass der Fehler minimal ist. Mit k2 kann der Fehler für den linken und
rechten Bereich bestimmt werden. Im Bereich mit dem größten Fehler wird
die nächste Stützstelle eingebracht. Ab hier wiederholt sich der
Vorgang, indem jeweils in die verbleibende Bereiche mit dem größten
Fehler Stützstellen eingebracht werden, bis alle N Stützstellen
festgelegt sind.
Es scheint mir, dass ein solcher Ansatz aber nicht garantiert die beste
Lösung finden wird. Gibt es überhaupt ein Verfahren, dass effizienter
als NP ist und garantiert die beste Lösung findet?
Das Problem kann man als Pathfinding-Problem sehen. Du suchst praktisch
den nächsten optimalen Schritt mit den enstehenden Fehler, die
Überschreitung der maximale Stützstellenanzahl und Schrittrichtung
(Schritte z. B. nur nach rechts zulässig) als Kostenfunktion. Der
A*-Algorithmus garantiert die optimale Lösung wenn die Heuristik die
nötigen Kosten nicht Überschätzt, wird aber ineffizient wenn sie sie
stark unterschätzt. (Eine gute Heuristikfunktion zu finden ist der
schwierige Teil)
Polynom schrieb:> Man kann davon ausgehen, dass die Funktion hinreichend> "wild" ist, sodass es nicht möglich ist ein passendes> Polynom oder einen anderen funktionalen Zusammenhang> zu bestimmen.
Deine Fragestellung ist in sich widersprüchlich.
Einerseits setzt Du eine Funktion y = f(x) als gegeben
voraus; andererseits forderst Du, es solle unmöglich sein,
einen funktionalen Zusammenhang zu bestimmen.
Das geht so nicht.
Egon D. schrieb:> Deine Fragestellung ist in sich widersprüchlich.>> Einerseits setzt Du eine Funktion y = f(x) als gegeben> voraus; andererseits forderst Du, es solle unmöglich sein,> einen funktionalen Zusammenhang zu bestimmen.>> Das geht so nicht.
Im konkreten Fall ist f diskret und besteht also aus (sehr sehr vielen)
Sampling Punkten. Ein funktionaler Zusammenhang zwischen diesen Punkten
(z.B. Polynom n-ten Grades) besteht aber nicht.
Ich hätte es besser und einfacher so ausdrücken können: "für eine
beliebige Funktion f"
Jemand schrieb:> Das Problem kann man als Pathfinding-Problem sehen. Du suchst> praktisch> den nächsten optimalen Schritt mit den enstehenden Fehler, die> Überschreitung der maximale Stützstellenanzahl und Schrittrichtung> (Schritte z. B. nur nach rechts zulässig) als Kostenfunktion. Der> A*-Algorithmus garantiert die optimale Lösung wenn die Heuristik die> nötigen Kosten nicht Überschätzt, wird aber ineffizient wenn sie sie> stark unterschätzt. (Eine gute Heuristikfunktion zu finden ist der> schwierige Teil)
Wenn ich es richtig verstehe, wäre aber das Problem, dass der
Algorithmus keine Limitierung auf N Kanten hat. Er würde mir
Kanten/Segmente quasi von a nach z ziehen und dabei "nur" den Fehler
minimieren.
Polynom schrieb:> Jemand schrieb:>> Das Problem kann man als Pathfinding-Problem sehen. Du suchst>> praktisch>> den nächsten optimalen Schritt mit den enstehenden Fehler, die>> Überschreitung der maximale Stützstellenanzahl und Schrittrichtung>> (Schritte z. B. nur nach rechts zulässig) als Kostenfunktion. Der>> A*-Algorithmus garantiert die optimale Lösung wenn die Heuristik die>> nötigen Kosten nicht Überschätzt, wird aber ineffizient wenn sie sie>> stark unterschätzt. (Eine gute Heuristikfunktion zu finden ist der>> schwierige Teil)>> Wenn ich es richtig verstehe, wäre aber das Problem, dass der> Algorithmus keine Limitierung auf N Kanten hat. Er würde mir> Kanten/Segmente quasi von a nach z ziehen und dabei "nur" den Fehler> minimieren.
Deswegen muss das Teil der Kostenfunktion sein. Wenn das Einfügen einer
>n-ten Stützstelle unbegrenzt hohe Kosten hat (und sonst null), wird
eine andere Lösung gesucht. Wenn man das Einfügen zu weniger
Stützstellen sanktioniert, könnte man sogar eine Mindestanzahl
erzwingen.
Warum sollte es Deiner Meinung nach kein Polynom geben? Hat der
funktionale Zusammenhang aus physikalischer Sicht Unstetigkeitsstellen?
Schau mal den Satz von Weyerstrass nach. Was ist das Modell von dem
Sensor?
Es ist beliebig sinnfrei, eine Abweichung von einer unterpolierten
Funktion zu bewerten.
Perfekt ist, soviel Stützstellen wie Werte.
Je nachdem, wie viel du reduzieren musst, kannst du schauen, welche n
Stellen sich fehlerarm zusammenfassen lassen.
Ein anderer Weg ist von unten, einen Maxi-Fehler festlegen und schauen,
wie weit du kommst.
Für beliebige Funktionen ist das aber beliebig schlecht.
Wenn man die Anzahl N der Stützstellen als fix vorgibt, hat man ein
N-dimensionales Optimierungsproblem. Zu jedem Stützstellen-Vektor (ki)
gibt es eine Fehlersumme, die man minimieren will.
Eine mögliche Heuristik, die ich in der Vergangenheit für
mehrdimensionale Optimierungen gebraucht habe, ist die particle swarm
optimization.
https://en.wikipedia.org/wiki/Particle_swarm_optimization
Ob das hierfür funktioniert, sehe ich grade nicht. Ein Versuch wäre es
wert. Im Netz finden sich diverse Implementierungen in Matlab oder
Python, ich hatte vor längerer Zeit eine Matlab-Version aus dem file
exchange verwendet.
Theor schrieb:> Warum sollte es Deiner Meinung nach kein Polynom geben? Hat der> funktionale Zusammenhang aus physikalischer Sicht Unstetigkeitsstellen?> Schau mal den Satz von Weyerstrass nach. Was ist das Modell von dem> Sensor?
Weil mich das Problem aus rein algorithmischer Sicht für beliebige
Funktionen interessiert.
A. S. schrieb:> Es ist beliebig sinnfrei, eine Abweichung von einer unterpolierten> Funktion zu bewerten.>
(Meinst du interpoliert?) Wieso sollte das sinnfrei sein?
Polynom schrieb:> Theor schrieb:>> Warum sollte es Deiner Meinung nach kein Polynom geben? Hat der>> funktionale Zusammenhang aus physikalischer Sicht Unstetigkeitsstellen?>> Schau mal den Satz von Weyerstrass nach. Was ist das Modell von dem>> Sensor?>> Weil mich das Problem aus rein algorithmischer Sicht für beliebige> Funktionen interessiert.
Ah. Dann ist die Antwort auf Deine Frage: Nein. Es gibt kein Verfahren,
dass effizienter als NP ist und garantiert die beste Lösung findet.
Polynom schrieb:> Im konkreten Fall ist f diskret und besteht also aus> (sehr sehr vielen) Sampling Punkten. Ein funktionaler> Zusammenhang zwischen diesen Punkten (z.B. Polynom> n-ten Grades) besteht aber nicht.>> Ich hätte es besser und einfacher so ausdrücken können:> "für eine beliebige Funktion f"
Einfacher -- ja.
Besser -- nein.
Du siehst nämlich meinen Kritikpunkt immer noch nicht:
Du sprichst von einer Funktion, die keinen funktionalen
Zusammenhang beschreibt.
Das GEHT aber nicht -- von einem funktionalen Zusammenhang
spricht man nämlich genau dann, wenn eine Funktion die
Abhängigkeit der einen von der anderen Größe beschreibt.
Ein funktionaler Zusammenhang ist beispielsweise: "Y sei
0, wenn X rational ist, und 1, wenn X irrational ist."
Egon D. schrieb:> Du siehst nämlich meinen Kritikpunkt immer noch nicht:> Du sprichst von einer Funktion, die keinen funktionalen> Zusammenhang beschreibt.> Das GEHT aber nicht -- von einem funktionalen Zusammenhang> spricht man nämlich genau dann, wenn eine Funktion die> Abhängigkeit der einen von der anderen Größe beschreibt.>> Ein funktionaler Zusammenhang ist beispielsweise: "Y sei> 0, wenn X rational ist, und 1, wenn X irrational ist."
Stell dir das praxisnah vor. Hinter der f(x) steht sowas wie:
return(data[x]);
Und der TE will nicht das ganze Array in sein Programm übernehmen.
Ist es mathematisch wirklich verboten eine Funktion auf Basis von
diskreten Werten aufzubauen?
Zum Algorithmus:
Graphentheorie klingt mir auch nach der vielversprechendsten Methode.
Dass das auf das oben verlinkte Knappsack Problem hinausläuft ist nicht
unwahrscheinlich, aber solche Probleme löst man gerne mit Pfadfindung.
Diese Algorithmen geben nicht die perfekte Lösung, aber meist eine
ziemlich gute.
Alex G. schrieb:> Ist es mathematisch wirklich verboten eine Funktion> auf Basis von diskreten Werten aufzubauen?
Nein, überhaupt nicht.
Es ist aber mathematisch verboten, oben von der
Funktion y=f(x) zu sprechen und drei Zeilen weiter
anzumerken, dass es keinen funktionalen Zusammenhang
zwischen x und y geben soll -- denn die definierte
FUNKTION y = f(x) IST der funktionale Zusammenhang.
Das sind in sich widersprüchliche Aussagen, und die
sind lt. h. M. kein legitimer Bestandteil mathematischer
Theorien.
Egon D. schrieb:> Es ist aber mathematisch verboten, oben von der> Funktion y=f(x) zu sprechen und drei Zeilen weiter> anzumerken, dass es keinen funktionalen Zusammenhang> zwischen x und y geben soll -- denn die definierte> FUNKTION y = f(x) IST der funktionale Zusammenhang.Polynom schrieb:> oder einen *anderen*> funktionalen Zusammenhang
Egon D. schrieb:> Alex G. schrieb:>>> Ist es mathematisch wirklich verboten eine Funktion>> auf Basis von diskreten Werten aufzubauen?>> Nein, überhaupt nicht.>> Es ist aber mathematisch verboten, oben von der> Funktion y=f(x) zu sprechen und drei Zeilen weiter> anzumerken, dass es keinen funktionalen Zusammenhang> zwischen x und y geben soll -- denn die definierte> FUNKTION y = f(x) IST der funktionale Zusammenhang.>> Das sind in sich widersprüchliche Aussagen, und die> sind lt. h. M. kein legitimer Bestandteil mathematischer> Theorien.
Egon, bitte verstehe mich nicht falsch, aber von dir ist hier noch kein
einziger weiterführender Gedanke im Sinne der eigentlichen Frage
gekommen. Trotzdem hast du schon 3 Beiträge verfasst. Also, wenn es dir
hilft, räume ich alles ein was du sagst, wenn wir es dann damit jetzt
bitte abschließen können.
Viele andere konnten gute Gedanken beisteuern und die Problemstellung
trotz der von mir induzierten Widrigkeiten ganz offenbar verstehen.
Also für mich ist es nicht möglich, die "wilde" Funktion in eine
"bekannte" zu überführen! Neuronale Netzwerke (vielleicht) mal aussen
vor, mit einer großen Menge an Randbedinungen kann es natürlich trotzdem
gehen. Mehr Infos ??
Gruß Rainer
Hast Du mal Beispieldaten? Eventuell könnte ein Variationsansatz
funktionieren, bei dem das Integral minimiert wird. Nachteil: Es muß ein
Gleichungssystem mit N+1 Unbekannten gelöst werden, und das eventuell in
doppelter Genauigkeit, weil es nicht unbedingt gut konditioniert ist.
Polynom schrieb:> Egon D. schrieb:>> Alex G. schrieb:>>>>> Ist es mathematisch wirklich verboten eine Funktion>>> auf Basis von diskreten Werten aufzubauen?>>>> Nein, überhaupt nicht.>>>> Es ist aber mathematisch verboten, oben von der>> Funktion y=f(x) zu sprechen und drei Zeilen weiter>> anzumerken, dass es keinen funktionalen Zusammenhang>> zwischen x und y geben soll -- denn die definierte>> FUNKTION y = f(x) IST der funktionale Zusammenhang.>>>> Das sind in sich widersprüchliche Aussagen, und die>> sind lt. h. M. kein legitimer Bestandteil mathematischer>> Theorien.>> Egon, bitte verstehe mich nicht falsch, aber von dir> ist hier noch kein einziger weiterführender Gedanke> im Sinne der eigentlichen Frage gekommen.
Nun ja, ich hatte gehofft, dass Du den Hinweis, dass Deine
Fragestellung in der vorliegenden Form nicht sinnvoll ist,
als weiterführend ansehen würdest.
> Trotzdem hast du schon 3 Beiträge verfasst. Also, wenn> es dir hilft, räume ich alles ein was du sagst, wenn> wir es dann damit jetzt bitte abschließen können.
Nein, ist nicht notwendig. Ich habe dich schon verstanden :)
> Viele andere konnten gute Gedanken beisteuern und die> Problemstellung trotz der von mir induzierten Widrigkeiten> ganz offenbar verstehen.
Ich zitiere Altmeister Goethe: "... denn ein vollkommner
Widerspruch / bleibt gleich geheimnisvoll für Kluge wie
für Toren."
Eine in sich widersprüchliche Fragestellung hat den großen
Vorteil, dass jeder das darunter verstehen kann, was er
darunter verstehen will.
In diesem Sinne: Viel Spaß und einen angenehmen Abend.
Polynom schrieb:> Egon, bitte verstehe mich nicht falsch, aber von dir ist hier noch kein> einziger weiterführender Gedanke im Sinne der eigentlichen Frage> gekommen.
Das siehst du falsch. Von Egon sind genau die Beiträge gekommen die man
von jemanden mit mathematischen Wissen erwarten würde: nämlich die
kritische Hinterfragung der eigentlichen Frage und Offenlegung der
Widersprüchen.
Polynom schrieb:> Man könnte zunächst an a und z eine Stützstelle (k0, k1) legen.
Das ist schon das erste Problem:
Welche Stützstellen y0 = f(k0) und y1 = f(k1) soll man wählen? Selbst
wenn man Meßpunkte an (k0, k1) hätte - wäre es sinnvoll, diese Punkte zu
nehmen? IMHO nein. Denn wie jede Messung sind auch diese Punkte
fehlerbehaftet. Der aus meiner Sicht logische Weg wäre, eine lineare
Regression über alle Meßpunkte zu machen. Die Stützstellen sind dann die
y-Werte der Regressionsgeraden an x = (k0, k1)
> nächste Stützstelle k2 könnte zwischen k0 und k1 eingebracht werden,> sodass der Fehler minimal ist.
Und schon die nächste Frage: welcher Fehler? Die Regressionsgerade aus
dem ersten Schritt minimiert die Summe der quadratischen Abweichungen.
Das wäre ein Fehlermaß. Man könnte aber auch den maximalen Abstand
zwischen Meßwerten und der Geraden nehmen. Das wäre ein weiteres
Fehlermaß. Je nach Anwendung könnte eines geeigneter sein als das
andere.
Aber egal erstmal. Wie geht es weiter?
Vorschlag: wir nehmen den Median der Meßwerte (den mittelsten Punkt) und
betrachen einmal alle Punkte von links bis zum Median. Und einmal alle
Punkte vom Median aus nach rechts (der Medianpunkt ist also in beiden
Mengen).
Für beide Mengen können wir jeweils wieder eine lineare Regression
durchführen. Wir erhalten zwei Geraden, die sich sehr wahrscheinlich [1]
schneiden. Und zwar in der Nähe des Medianpunktes. Das ist unsere dritte
Stützstelle. Die beiden Stützstellen bei (y0, y1) dürften sich übrigens
auch gerade geändert haben.
Auf diese Weise kann man sukzessive neue Stützstellen einfügen. Wenn man
2^N+1 Meßwerte hat, kann man N-mal die Intervalle halbieren. Vermutlich
würde man eine Fehlergrenze festlegen wollen und sobald der Fehler der
linearen Regression für ein Intervall unter diese Grenze fällt, würde
man das Intervall nicht weiter halbieren.
[1] wenn die Regression für beide Halbintervalle Parallelen ausspucken
sollte, dann nicht. Für praktische Fälle dürfte das irrelevant sein.
Ich denke, es ist notwendig die Klasse der Funktionen erst einmal
einzugrenzen. Schon in dieser Hinsicht treten Widersprüche auf. Erst
handelt es sich um Sensordaten, dann um "ALLE" denkbaren Funktionen. Was
denn nun? Das Problem wird komplizierter und nicht einfacher wenn es
generalisiert wird!
Dann wird nach einer "Linearisierung" gefragt obwohl der Kontext der
Frage "Approximation" nahelegt. Dazu fehlt aber das Systemmodell.
Polynome gehen angeblich nicht, obwohl das jeder Theorie widerspricht.
(Jeder der schon mal in einem Test zu einer Zahlenfolge eine Gleichung
finden sollte, könnte das wissen: Es gibt immer mindestens eine und
[fast] immer mehrere Lösungen). Ungeklärt.
Wobei die Herkunft von Sensoren das (die Ablehnung eines Polynoms) in
dem konkreten Fall (falls man sich nun darauf einigen kann) durchaus
begründet erscheinen lässt (ein Polynom mag ja zwischen den Stützstellen
extrem vom Modell abweichende Werte ergeben), anderseits aber für "ALLE"
Funktionen (aus R resp. N oder auch C) durchaus möglich ist - nur halt
keinen praktischen Zweck erfüllt.
Das alles (das allgemeine, nicht NP-schwere Verfahren für alle
existierende Funktionen) ist der feuchte Traum eines mathematisch
Halbgebildeten. Nichts weiter. Entsprechend grenzenlos und sinnlos ist
die Diskussion.
(Man vergebe mir bitte die flapsige Ausdrucksweise. Ein persönlicher
Angriff ist damit nicht beabsichtigt. Ich selbst wei0 zufällig halt
etwas mehr genau auf diesen Punkt bezogen; bin auch kein Überflieger).
So. Und damit ich den TO nun nicht einfach mit leeren Händen dastehen
lasse, meine Leseempfehlung für die Betrachtung des Problems als
Linearisierung (was ich, wie gesagt, für eine sekundäre Option halte):
https://de.wikipedia.org/wiki/Linearisierung
und der entsprechende englische Artikel (den ich persönlich besser
finde)
https://en.wikipedia.org/wiki/Linearization
Polynom schrieb:> Viele andere konnten gute Gedanken beisteuern und die Problemstellung> trotz der von mir induzierten Widrigkeiten ganz offenbar verstehen.
das nenne ich sinnfreie behauptung oder totschlägerargument im sinne von
bitte nur "lösungen und keine probleme" benennen.
es ist eben nicht jedem gegönnt eine sinnlose frage als solche zu
erkennen und dann wird halt "ausgespeichert" sprich einfach
rumgeplappert in der hoffnung irgendwas wird schon passen und wenn nicht
merkt es ja vielleicht keiner, aber dafür waren wir wieder richtig
produktiv/aktiv auch wenns nur blinder aktionismus war.
mt
