Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Interpolation mit unbekannter Funktion
Hallo,
ich denke, dass es ganz gut zu AlgoKS passt, deswegen hier eine für mich bedeutende Frage:
Ich habe eine beliebige Anzahl an Funktionswerten und eine Teilmenge der Funktionsparameter gegeben. Leider ist ansonsten über die Funktion wenig bekannt, insbesondere nicht, ob sie linear, quadratisch oder sonst was ist. Wie kann man nun vorgehen, um eine möglichst genaue Interpolation zu erzielen? Desweiteren wäre noch die Wertemenge bekannt. (Die Interpolation ist notwendig, weil die ursprüngliche Funktion nicht (dauerhaft) verwendbar ist.)
Ist sowas hoffnungslos oder kann man da doch was machen?
Vielen Dank!
Gruß
Falls “Möglichst genau” bedeuten soll, dass alle Punkte auf der Kurve liegen bieten sich dir dank fehlender Information beliebige stetige Varianten von gleitenden Durchschnitten an. Polynom- und Splineinterpolation gibt es auch, aber da könntest du den Wertebereich nach oben/unten verlassen.
Danke.
Aber alle Punkte auf der Kurve geht ja nicht, weil es unendlich viele Punkte sind, von denen ich nur endlich viele abfragen kann. Und der Wertebereich darf nicht verlassen werden.
Und ich kann noch Gewichte raten, d.h. ich kenne ungefaehr die Verhaeltnisse der Gewichte. Und wie gesagt kenne ich eine Teilmenge der Parameter und diese ist endlich.
Ich mach es mal konkret :).
Ich schreibe eine Schach-Engine und kann mir moegliche Parameter wie ‘anzahl der besetzten Felder’, ‘Materialwert’, ‘Bauernstruktur’ usw. ausdenken. Nun habe ich als Referenz eine professionelle Schachengine, die deutlich staerker ist als meine. Deswegen moechte ich die Gewichtung der Parameter ‘erraten’. D.h. nicht, dass ich das als alleinige Analysefunktion verwenden wollte, das soll nur ergaenzend sein. Nun kann ich also jede moegliche Stellung bei der starken Engine abfragen und erhalte einen Punktwert in einem bestimmten Intervall. Mir ist bewusst, dass sich die Bewertung einer Stellung auch aus der Bewertung der nachfolgenden Stellungen ergibt.
Das geht stark in Richtung Mustererkennung / Machine Learning. Mit Schach fängst du da nicht gerade mit dem einfachsten Problem an…^^ Aber hier mal ein paar Gedanken (die im Endeffekt auf eine Pseudo-Inverse rauslaufen, also kein Hexenwerk^^):
Zunächst einmal: Die Bewertung der nachfolgenden Stellungen hast du ja quasi implizit in deinen Merkmalen / “Features” (das was du mit besetzte Felder, Materialwert, … beschreibst), das heißt, das beachtest du ja sogar bis zu einem gewissen Grad.
Sei x ein Vektor der einen Spielzustand beschreibt, in seinen Komponenten enthält er die d Merkmale, also in der ersten Dimension die besetzten Felder, in der zweiten den Materialwert, usw. Was du willst, kann man dann einfach als “bewertung = f(x)” hin schreiben, wobei f : R^d → R^1 deinen Merkmalsvektor auf die Bewertung abbildet.
Mit der Referenzsoftware kannst du dir Trainingsdaten erzeugen, quasi Paare der Form: ( referenz_bewertung_1, x_1 ), ( referenz_bewertung_2, x_2 ), …
Jetzt willst du eine Funktion, die den Unterschied, zwischen f(x) und der referenz_bewertung minimiert. etwa error = sum_i ( referenz_bewertung_i - f(x_i) )^2 wenn man den Fehler mit der euklidischen Norm misst.
Was dabei klar wird, weil du andere Features verwendest als die Referenz-Engine und dein f nicht perfekt sein wird, ist, dass du Fehler machst. Daher solltest du approximieren (“einfache” Funktion die möglichst nah an die Trainingswerte kommt) und nicht interpolieren (Werte der Testdaten müssen exakt getroffen werden, erfordert ein sehr hochgradiges Polynom → Overfitting → schnell relativ große Fehler selbst wenn du nah an Trainingsdaten liegst).
Die einfachste (nicht konstante = Mittelwert :D) Approximation wäre eine lineare Approximation. Dann sieht dein f so aus:
f(x) = a_1 * x_1 + a_2 * x_2 + … + a_d * x_d + a_0 * 1
x_1 bis x_d sind wieder die Merkmale deiner aktuellen Spielfeldsituation. Was die Funktion f ausmacht, sind die Konstanten a_0, …, a_d, die du mit Hilfe deiner Trainingsdaten abschätzen musst. Eventuell das, was du als Gewichte bezeichnest(?).
Wie steht hier in Foliensatz 7, Folien 27 - 29 (Linear Regression):
http://www5.cs.fau.de/lectures/ws-1314/pattern-recognition-pr/slides/
X ist eine Matrix, die zeilenweise die Merkmalsvektoren enthält, und hinten noch eine Spalte 1en. Wenn du so eine Zeile mit dem Vektor theta = (a_1, a_2, …, a_d, a_0) multiplizierst, bist du wieder genau bei f(x). Der y-Vektor entspricht deinen referenz_bewertungen. (Auf die Formel zur Berechnung von den Komponenten der theta-Vektoren kommt man, in dem man die Ableitung nach dem jeweiligen a_i auf 0 setzt, denn da liegt ja das Minimum der Funktion. “Pseudo-Inverse”…) Wenn du Probleme mit der Schreibweise hast frag einfach nochmal nach, an die muss man sich erst gewöhnen.
Gegenüber der Anzahl an Parametern, die du abschätzt (“a"s), solltest du ein Vielfaches an Trainingsdaten (”(y_i, x_i)"s) haben. Vielleicht 10, besser 100 mal so viele, dein Suchraum ist ja auch recht groß.
Letztlich kann ich dir nicht sagen, ob bei deinen Features und einer linearen Approximation auch gute Ergebnisse rauskommen - das musst du probieren. Man kann das ganze auf quadratische Funktionen erweitern, indem man alle Komponenten eines x-Vektors paarweise multipliziert und die d^2 Ergebnisse als zusätzliche Features auffasst, das erlaubt die Berücksichtigung von Abhängigkeiten. Je nachdem wie viele Features du hast, steigt der Aufwand zur Berechnung der Parameterabschätzung dann aber recht stark an.
Was den Wertebereich angeht, wirst du wohl entweder abschneiden müssen oder, wenn du die Unterschiede bei großen Werten behalten willst, das Ergebnis noch in eine Art Sigmoid-Funktion stecken. Die sollte innerhalb des Wertebereichs den Funktionswert möglichst wenig ändern ( f(x) ~ x ) und nur den Rand stauchen. Wenn die Funktion den Wertebereich verlässt, heißt das aber ohnehin, dass sie hier wohl nicht gut trainiert ist, es ist also fraglich, ob dir das hilft…
Ich hoffe du hast ein paar neue Anhaltspunkte zum Googeln und ich hab dich nicht zu sehr abgeschreckt 
Wenn dich sowas interessiert, könntest du dir überlegen, IntroPR, PR oder PA zu hören. Da wird zwar nicht direkt künstliche Intelligenz im Hinblick auf Spiele oder so Dinge behandelt, die Prinzipien sind aber immer die selben: Merkmale auf eine Bewertung / Klassenzuordnung abbilden 
1 Like
Recht herzlichen Dank für deine ausführliche Antwort :).
Das Thema interessiert mich sehr und ich werde sicherlich mal genauer nach deinen Stichworten googeln :).
Mich auch. Aber das hast du vielleicht schon gemerkt 