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.
Wie ist denn die Funktion f konkret definiert? Poste die Definition, wie immer sie aussehen mag, bitte.
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.
Die Problemstellung erscheint mir verwandt zum Rucksackproblem: https://de.wikipedia.org/wiki/Rucksackproblem
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
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.