Kernel Density Estimation

  • Ersteller Gelöschtes Mitglied 160054
  • Erstellt am

Gelöschtes Mitglied 160054

Guest
Wer Plan von Kernel Density Estimation? Aktuell versuche ich den bedingten Erwartungswert aus einer Zeitreihe zu berechnen. Dazu schätze ich die zwei Dichten (hier beispielhaft für bedingte Erwartung 1. Ordnung) f(x_n,x_n_1) und f(x_n_1) mittels einer Standardmatlabfunktion und berechne dann die bedingte Dichte f(x_n|x_n_1) = f(x_n,x_n_1)/f(x_n_1). Anschließend integriere ich die Dichte numerisch um den bedingten Erwartungswert E(x_n | x_n_1) zu berechnen. Um die sogenannte Bandbreite B zu bestimmen nutze ich einen Optimierungsalgorithmus.
Mit diesem betrachte ich den mittleren quadratischen Fehler der Prädiktion, berechnet mit der Schätzung des bedingten Erwartungswertes gegeben B, und minimiere für einen Teil der Daten den Fehler durch optimale Bestimmung von B.
Ich habe 10k Sample (es sind Sprachsignale) und nutze die ersten 500 derzeit für die Optimierung (d.h. ich schätze die Dichten zwar mittels der 10k Sample, aber für die Anpassung von B wird nur der mittlere quadratische Fehler auf den ersten 500 Samplen berücksichtigt). Kann dieser Ansatz überhaupt overfitten? Sobald ich ein paar Datenpunkte habe sollten eigentlich die Dichten entweder näherungsweise korrekt geschätzt worden sein und die Prädiktion ist "gut", oder die Schätzung der Dichten overfittet, was sich unmittelbar in unsinniger Prädiktion zeigen sollte (mindestens auf den 10k-500 Sample). Auf Grund der relativ komplizierten Berechnung des Erwartungswertes aus den zwei Schätzungen erscheint mir ein anderer Fall unrealistisch. Kann man die Wahrscheinlichkeit noch irgendwie abschätzen, dass das overfittet?

edit: Gestützt wird aktuell die Ansicht das ich nicht overfitte nicht nur durch die Performance auf den Daten mit denen nicht optimiert wurde sowie die Abschätzung des minimalen mittleren quadratischen Fehlers durch einen weiteren Algorithmus (welcher ein anderes Verfahren verwendet). Diese Untergrenze liegt noch deutlich unter dem was ich aktuell mit dem bedingten Erwartungswert erreiche.
 
Zuletzt bearbeitet von einem Moderator:

Benrath

Community-Forum
Mitglied seit
19.05.2003
Beiträge
19.485
Reaktionen
664
Was genau machst du denn da?

Finds gut, dass hier was gepostet wird, kann aber leider nicht helfen. Klingt aber plausibel was du schreibst. Manchmal hilft es einem ja nur, es mal aufzuschreiben. Schon bei Stackexchange gepostet?
 

Gelöschtes Mitglied 160054

Guest
Es geht um die Bestimmung des minimalen quadratischen Fehlers den ein Prädiktor auf speziellen Sprachsignalen haben kann (eigentlich geht es um das Maximum des Prädiktionsgewinns, aber das kommt praktisch auf das Selbe heraus). Für den Prädiktionsgewinn gibt es eine Obergrenze die man durch die sogenannte Transinformation bestimmen kann. Um diesen Weg zu verifizieren - ich erhalte signikant höhere Grenzen als praktische Prädiktoren schaffen - versuche ich auf einen zweiten Weg den maximal möglichen Prädiktionsgewinn zu bestimmen. Da der Optimalprädiktor durch den bedingten Erwartungswert gegeben ist, versuche ich diesen zu bestimmen. Dazu ist die bedingte Wahrscheinlichkeit nötig, welche ich aber nicht direkt schätzen kann, sondern durch die Schätzung von Verbundwahrscheinlichkeiten bestimmen muss. Hier kommt die Kernel Density Estimation ins Spiel. Alle Quellen geben eigentlich an, dass die Bandbreite B über Cross Validation in der Praxis zu bestimmen wäre, da die Faustformeln für die Bestimmung davon für mehr als eine Dimension bzw. Nichtgaussheit nicht viel taugen. Deswegen optimiere ich diese auf Basis eines Teils der Daten.

Stackexchange noch nicht, hab mit einem Kollegen drüber gequatscht. Stack Exchange hat mir bisher noch nie geholfen, sobald eine Frage ab vom üblichen Krams kommt ist da gähnende Leere (hab in diesem Kontext dort auch schon eine Frage stellt, gab natürlich keine Antwort).
Dort hatte ich eine ähnliche Frage gestellt, ob mein Ansatz overfitten kann und hatte damals aber ein Beispiel eines autoregressiven Prozesses gegeben. Das Optimum davon ist ein linearer Prädiktor (wenn man gaußsches Rauschen verwendet). Mein Ansatz hat aber etwas bessere Ergebnisse geliefert. Eine mögliche Erklärung wäre, dass der Ansatz die Pseudozufälligkeit "bemerkt hat" und deswegen noch etwas rausholen konnte. Eine andere, dass es eine von mir nicht erkannte Möglichkeit des Overfittens gibt.
 
Zuletzt bearbeitet von einem Moderator:

FORYOUITERRA

TROLL
Mitglied seit
22.07.2002
Beiträge
4.501
Reaktionen
371
Website
www.frauentag.de
ich hab generell meine probleme dem geschreibsel zu folgen. was ist x_n, was genau ist x_n_1?

(bivariate)-kerndichteschätzer setzen üblicherweise iid samples (x[n], y[n]), n = 1, ..., N voraus.
wenn ich richtig abstrahiere, dann betrachtest du nun die punkte (x[n_1], x[n]). ich gehe davon aus, dass n_1 irgendwie von n abhängt, z.b. n_1 = n - 1,
dann betrachtest du letztlich punkte (x[n-1], x[n]), n = 2,..., N

um zu sehen, ob deine herangehensweise sinnvoll ist, kannst du dich zuerst einmal fragen, ob denn die iid annahme an die beobachtungspunkte erfüllt ist, oder es durch, die aufgrund der zeitreihe implizierte struktur an die sequenz {x[n]} irgendwelche probleme mit dieser grundannahme geben könnte.

wenn du danach immernoch der meinung bist, dass dies ein sinnvolles vorgehen ist, dann brauchst du das rad nicht mehr neu zu erfinden, sondern, dass, was du machen willst, findest du in jedem einführungsbuch der statistik unter dem begriff "Kernregression". Ein bekannter vertreter ist der nadaraya watson kernel estimator, der im (iid) modell

y = f(x) + e

E(y|x) = f(x) schätzt, vorausgesetzt f ist hinreichend glatt (wikilink )
- das ist mit y=x_n und x= x_n_1 also genau das, was du suchst.


wenn du vernünftigerweise jedoch davon ausgehst, dass da doch irgendwas mit der iid annahme verkehrt sein sollte, dann brauchst du auch das rad nicht neu zu erfinden, sondern auch da könnte sich zuerst der blick in ein statistikbuch lohnen. ich empfehle hier als startpunkt kapitel 18 in li und racine's nonparametric econometrics: theory and practice.

ansonsten finde ich das ganze von dir beschriebenes vorgehen merkwürdig. für mich lässt es darauf schließen, dass du mit hoher wahrscheinlichkeit irgendetwas anwendest, was du irgendwie noch nicht gamz verstanden hast. kann mich natürlich auch irren, aber die die standard matlab funktion für das schätzen der dichten wird höchstwahrscheinlich auch ein kerndichteschätzer sein, dieser benötigt schon eine bandbreite durch deine methode schätzt du implizit also bereits mindestens 2 bandbreiten (einmal für f(x,y), einmal für f(x)). wie dann noch eine weitere bandbreite B für die schätzung bei E(Y|X) reinkommen soll, die du nochmal neu kalibrierst, ist mir aktuell schleierhaft, da E(Y|X), wie du richtig schreibst, ja nur von f(x,y) und f(X) abhängen. Also Größen, die du ja bereits geschätzt hast. Unabhängig davon, warum machst du keine cross-validation für die bestimmung der bandbreitenwahl? wenn es mehr als eine illustration ist, dann ist dein vorgehen hier auch ohenhin falsch.
 
Zuletzt bearbeitet:

Gelöschtes Mitglied 160054

Guest
Danke für deine Erläuterungen. Ich habe eine Zeitreihe x. In dieser hängt der Wert zum Zeitpunkt n, geschrieben x[n], stark von vorherigen Werten ab. Ich interessiere mich nun für die Optimalprädiktion, suche als in der Tat den bedingten Erwartungswert E(x[n]|x[n-1]) bzw. auch höhere Ordnungen, also E(x[n]|x[n-1],x[n-2]) usw..
IID nehme ich an, aber kann ich nicht beweisen (zumindest ist x in sehr guter Näherung stationär, das kann ich empirisch belegen).

irgendetwas anwendest, was du irgendwie noch nicht gamz verstanden hast.
Richtig, aber nur Dinge zu nutzen die man vollständig versteht wäre mäßig gut. Learning by Doing.

mindestens 2 bandbreiten
Exakt. Ich nutze auch aktuell exakt zwei was sehr gut zu funktionieren scheint.

aber die die standard matlab funktion für das schätzen der dichten wird höchstwahrscheinlich auch ein kerndichteschätzer sein
Richtig.

wie dann noch eine weitere bandbreite B für die schätzung bei E(Y|X) reinkommen soll, die du nochmal neu kalibrierst, ist mir aktuell schleierhaft, da E(Y|X), wie du richtig schreibst, ja nur von f(x,y) und f(X) abhängen
Gemeint war, dass ich die Bandbreite(n) zum Schätzen von f(x,y) und f(x) optimiere.

Unabhängig davon, warum machst du keine cross-validation für die bestimmung der bandbreitenwahl
Cross-Validation so wie ich es aus der Literatur verstehe dauert viel zu lange. Erste Tests mit einer Pythontoolbox haben ferner keine sinnvollen Werte ergeben (Sowohl via mittels ML als auch LS CV). Meine Herangehensweise liefert bisher plausible Werte (das weiß ich, da ich eine weitere Methode verwende um den minimalen quadratischen Fehler abzuschätzen. Diese Methode ist jedoch i.A. nicht "dicht", also kein Infimum).
Eine weitere (Matlab) Toolbox für die Bandbreitenselektion habe ich auch getestet, aber die würde wenn überhaupt nur bis zum bivariaten Fall funktionieren (d.h. allgemeine Fälle sind nicht eingebaut).

Ein bekannter vertreter ist der nadaraya watson kernel estimator
Danke für das Stichwort, hatte das einmal wo gelesen aber nicht weiterverfolgt, ich schau mal rein.
Nach dem was ich jetzt gelesen habe mache ich genau das was der auch macht, cool.

Bleibt nur die Frage ob mein Ansatz die Bandbreite zu optimieren problematisch ist oder nicht. Er nutzt die Tatsache, dass der minimale quadratische Fehler durch den Erwartungswert erzielt wird. Den kann ich aber nur korrekt berechnen, wenn die bedingte Dichte korrekt ist. Daher nehme ich an, dass die Bandbreitenwahl die zur Minimierung des quadratischen Fehlers führt die beste ist. Entweder liege ich dan mit der geschätzen bedingten Dichte nahe bei der wahren und Erhalte eine gute Lösung, oder eben nicht. Dann sollte der mittlere quadratische Fehler aber höher sein.
Einzig könnte es passieren, dass ich eine Deltafunktion "baue". Oder liege ich da falsch?

edit: Auf dem Weg zum Kiosk ist mir aufgefallen, dass der nadaraya watson kernel estimator schlauer ist, da er sich die Integration spart. Coole Sache, ggf. läuft meine Optimierung dann viel schneller. Ich werde den Teil am WE nochmal testen.
Allerdings würde ich vermuten, dass, da es so aussieht als wäre eine Verallgemeinerung auf beliebige Dimensionen einfach, dass es doch nicht so trivial sein kann, sonst gäbe es das doch überall.
 
Zuletzt bearbeitet von einem Moderator:

FORYOUITERRA

TROLL
Mitglied seit
22.07.2002
Beiträge
4.501
Reaktionen
371
Website
www.frauentag.de
stationär ist ja schonmal gut, dass die werte x[n] stark von vergangenen werten abhängen, bedeutet übersetzt, dass die werte nicht unkorreliert sind, was einer iid annahme sofort widerspricht. ist aber nicht schlimm. was du brauchst ist, dass die abhängigkeitsstruktur in der zeitreiehe nicht zu stark ist und die korrelationen also schnell genug nachlassen (weakly dependent). letztendlich wirst du das so oder so durchboxen müssen - nochmals empfehle ich hier einen blick in das oben genannte buch kapitel 18. dort ist genau der fall, der dich interessiert beschrieben. auch wird ein satz über cross validation bei weakly dependent data im regressionssetting verloren, die ich dir immernoch empfehlen würde.
 

Gelöschtes Mitglied 160054

Guest
stationär ist ja schonmal gut, dass die werte x[n] stark von vergangenen werten abhängen, bedeutet übersetzt, dass die werte nicht unkorreliert sind, was einer iid annahme sofort widerspricht. ist aber nicht schlimm. was du brauchst ist, dass die abhängigkeitsstruktur in der zeitreiehe nicht zu stark ist und die korrelationen also schnell genug nachlassen (weakly dependent). letztendlich wirst du das so oder so durchboxen müssen - nochmals empfehle ich hier einen blick in das oben genannte buch kapitel 18. dort ist genau der fall, der dich interessiert beschrieben. auch wird ein satz über cross validation bei weakly dependent data im regressionssetting verloren, die ich dir immernoch empfehlen würde.

Danke nochmal für den Hinweis auf NW-Estimator, der ergibt in einem Testfall den ich gerade mal berechnet habe praktisch genau die Lösung die ich auf meinem Wege erhalten habe, ist aber minimal schlechter als eine lineare Prädiktion (meine Variante ist minimal besser))

Wichtige Frage an dich:
Siehst du ein nicht triviales Problem bei der Verallgemeinerung des NW-Estimators auf beliebige Dimensionen? Wenn ich den Matlab-Code sehe, dann erscheint es mir unter Annahme eines Produktkernels trivial den beliebig zu verallgemeinern. Aber es gibt bei den paar Implementierungen die ich mir angeguckt habe immer nur den bivariaten Fall.

Zum IDD-Punkt:
Nach meinem Verständnis ist es wie folgt:
Die Daten können in guter Näherung als (vermutlich) streng stationär angenommen werden, hängen also nicht von der absoluten Zeit ab sondern nur von Vorgängern. Mit der Kernel Density Estimation mache ich einen Ansatz für die Verbundswahrscheinlichkeiten. So lange der Prozess streng stationär ist sollte die Schätzung funktionieren. Das Independent sollte nicht notwendig sein. Ansonsten würde ich auch einen Widerspruch zu Marginalverteilungen sehen, wo man Dimensionen rausintegriert.

Meine Sample baue ich wie folgt aus:
(x[n-1], x[n]),(x[n],x[n+1]), usw.

Natürlich ist die Abhängigkeit x[n] und x[n+1] eine andere je nachdem ob davor x[n-1] z.B. 1 oder 2 war, aber deswegen kann ich trotzdem die bivariate Dichte f(x[n],x[n+1]) schätzen. Gegeben hinreichende Daten sollte der Bias den du durch wenig Beispiele für das Tripel (x[n-1], x[n], x[n+1]) irrelevant werden bzw. gegen Null konvergieren.

Im gewissen Sinne würde ich sagen, so lange z.B. f(x) und f(x,y) existieren kann ich die bedingte Dichte durch meinen Ansatz finden, da ich nur die Eigenschaft des bedingten Erwartungswertes als Optimalprädiktor benötige.
Ich kann auch nicht Overfitten, da ich nur auf 5% meiner Daten optimiere. Die Performance auf dem Rest ist die schönerweise die selbe wie auf dem Anfang (+- ~0.1%).

Meine andere Methode schätzt die sogenannte Mutual Information (und leitet daraus eine Untergrenze für den mittleren quadratischen Fehler ab), wobei der Schätzalgorithmus etwas anders als Kernel density estimation funktioniert. Implizit muss da aber auch eine Dichteschätzung drinstecken. Und die Mutual Information Schätzung habe ich bis zum Erbrechen mit allen möglichen stark und schwach korrelierten (bis Dimension 15) Autoregressivenprozessen getestet und sie funktioniert einwandfrei.

Des Weiteren habe ich die KDE auch mit Zufallsprozessen getestet und dort schien sie auch zu funktionieren (wobei ich zugegebenerweise die Optimierung und im Zusammenhang mit höheren Dimensionen damals nicht getestet habe), wobei das jeweils Gaußprozesse waren.
Wie du siehst glaube ich nicht so recht, dass das ein Problem ist.

Das Buch schaue ich mir an, danke!

edit:
Ich habe mal in einen Validierungsordnern geschaut und für den Ansatz den ich beschrieben habe, hat es auch bei einem Prozess mit der Autokorrelation
<a href="https://imgbb.com/"><img src="https://i.ibb.co/Bf7Ktwj/autocorr.png" alt="autocorr" border="0"></a>
funktioniert. Ist die Autokorrelation eines autoregressiven Prozesses 5. Ordnung mit fünffachem Pol bei 0.9.
Minimale Unsicherheit gibt es, da ich nicht 100% verifizieren konnte das die Daten die ich abgelesen habe auch zum aktuellen Skript im Ordner gehören, aber es schien alles plausibel.
Probleme gab es immer dann, wenn ich eine höhere Dimension schätzen sollte als Vorlag, also z.B. E(x[n]|x[n-1], x[n-2]) wenn der Prozess x[n] = ax[n-1] + N(0,1) war, allerdings war da die Bandbreite auch nicht optimiert (normal reference rule) und der quadratische Fehler war immer stark suboptimal.
 
Zuletzt bearbeitet von einem Moderator:

FORYOUITERRA

TROLL
Mitglied seit
22.07.2002
Beiträge
4.501
Reaktionen
371
Website
www.frauentag.de
Buch beschreibt multivariaten Fall.

Man beachte, dass du defakto nur ein gewichtetes mittel der y werte rechnest. Nix mit nummerischer integration bei kernelregression nötig.
Es geht ansonsten auch nicht darum, dass du die Verfahren nicht anwenden kannst. Kannst du natürlich. Es geht einzig darum, sicherzustellen, dass sie sinnvolle Resultate liefern.

Im multivariaten Fall läufst du in den curse of dimensionality, aka langsame konvergenzraten.
 

Gelöschtes Mitglied 160054

Guest
Alles klar, danke dir!
Es geht ansonsten auch nicht darum, dass du die Verfahren nicht anwenden kannst. Kannst du natürlich. Es geht einzig darum, sicherzustellen, dass sie sinnvolle Resultate liefern.
Das erziele ich zum einen durch anlesen von etwas Theorie + Validierung, also Experimenten auf synthetischen Daten.

edit:
Fett, die strenge Definition von weakly dependent hatte ich nicht mehr im Kopf,
Im grenzwert geht die Autokorrelation gegen Null, aber recht langsam. Naja, auf synthetischen Daten habe ich gesehen, dass es geht, mehr kann ich IMO eh nicht machen. Tausend Dank, ich schau dann mal das ich den Multivariante Fall finde, in Kapitel 18 wird der Estimator nicht eingeführt, irgendwo davor, aber ich werde ihn schon finden ;)

edit2:
Tausend Dank, das Stichwort hat mir echt massiv weitergeholfen :) Hab nun auch eine Multivariate Implementierung gefunden, cool (die hat sogar cross-validation drin^^)
 
Zuletzt bearbeitet von einem Moderator:

Gelöschtes Mitglied 160054

Guest
Ok, hab leave one out cross validation implementiert und validiert, scheint zu funktionieren und ist sehr schnell, geil!
Dann kann ich ja bis zur Deadline sogar meine ganzen Daten evaluieren <3

Das einzige das mich jetzt noch stutzig macht ist die leicht vorhandene Prädizierbarkeit von weißem Rauschen.
 
Zuletzt bearbeitet von einem Moderator:
Oben