Hallo,
ich bin neu hier im Forum. Ich habe schon vergeblich das Forum durchstöbert um Lösungen für mein Problem zu finden. Ich will meinen Code irgendwie effizienter machen, doch habe ich absolut keine Idee. Das Problem ist, dass ich in meiner Matlab Simulation mit ziemlich großen Daten umgehen muss... Bei meinem derzeitigen Stand braucht mein Programm mehrere Stunden bis es komplett duchgelaufen ist, der Grund hierfür liegt in dieser Funktion:
Code:
function[ y_predict ] = kernelregression( x_train,y_train,x_predict, h) % REGRESSION construct regression estimate by using the Nadaraya Watson % kernel estimate % We are using as a kernel function the Gaussian kernel with bandwidth h, % which is choosen datadependent by "Splitting the Sample"
% regression estimate y_predict is a vector in which every entry % represents a value of an estimate of the corresponding entry in % x_predict if(K==0)
y_predict(i)=0;
else
y_predict(i) = sum(K.*y_train)/ K;
end end
Gibt es hier eine Möglichkeit dies schneller zu bekommen, eventuel mit besserer Vektorisierung? Ich weiß leider nicht, wie ich diese for-Schleifen umgehen kann. Da ich leider ein absoluter Anfänger in Matlab bin, brauche ich dringend eure Hilfe...
kannst du einen Beispielaufruf posten? Benötigt ein einzelner Aufruf dieser Funktion so lange, oder wird sie sehr oft aufgerufen?
Mit dem Profiler solltest du zudem innerhalb der Funktion feststellen können, welcher Teil besonders lange dauert.
Ist das "k=0" an der richtigen Stelle, oder sollte das nicht eher innerhalb der i-Schleife sein?
Grüße,
Harald
Christina
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 29.09.2012, 16:11
Titel:
Also K=0 müsste an der richtigen Stelle stehen, da ich es nur am Anfang einmal 0 setzten möchte, damit ich die Aufzählung K=K+... machen kann. Auch ein Beispielauffuf ist eher schwierig, da das ein Teil der Monte Carlo Simulation zur Bewertung von amerikanischen Optionen ist und aus 5 zusätzlichen Funktionen besteht. Die Funktion wird sehr oft aufgerufen. Also es ist schon normal, dass die komplette Auswertung so ca 20 Minuten dauern kann.
Ich kann dir aber gerne mal die Größe der Eingabevariablen geben:
x_predict ist entweder 12000x1 oder 12000x5 groß
x_train 2000x1 oder 2000x5
y_train 2000x1
h Skalar
Meine Frage ist, ob ich die for-Schleifen umgehen kann um das Ganze effizienter zu gestalten. Falls es etwas helfen sollte kann auch mal die anderen Funktionen posten oder dir zukommen lassen.
Christina
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 29.09.2012, 16:14
Titel:
Christina hat Folgendes geschrieben:
Also es ist schon normal, dass die komplette Auswertung so ca 20 Minuten dauern kann.
Im besten Fall, aber so wie es hier ist, dauert es ca 1 stunde für den Fall d=1 (x_train und x_predict eindimensional) und für den Fall das d=5 dauert es mit Sicherheit um die 10Stunden...
Und ich glaube nicht, dass das normal ist und nicht schneller mit einer besseren Implementierung geht
wenn ich nur mal die for-Schleife für d=1 anschaue, versteh ich so einiges nicht:
Code:
% copy every single entry of x_predict into an own vector for easier % handling
x_predict_vector = repmat(x_predict(i,:),SizeOfX,1);
%%% Warum soll x_prefict in einem Vektor stehen, mit einem Skalar läßt
%%% sich doch viel einfacher rechnen
% Kernel Function: Gaussian kernel
K = exp((- norm((x_predict_vector - x_train)/ h).^2)/2);
%%% norm ist schon die Wurzel der Summe aller quadrierten Vektorelemente
%%% h läßt sich auch ausklammern:
x_predict_skalar = x_predict(i);
K = exp(-(0.5/h)*sum((x_predict_skalar - x_train).^2));
% regression estimate y_predict is a vector in which every entry % represents a value of an estimate of the corresponding entry in % x_predict if(K==0)
y_predict(i)=0;
else
y_predict(i) = sum(K.*y_train)/ K;
%%% Wozu das denn nun? K ist ein Skalar. Also läßt sich K wunderbar wegkürzen:
y_predict(i) = sum(y_train);
end
%%% Damit läßt sich die Frage ob K=0 ist viel einfacher beantworten:
%%% Genau dann wenn alle Elemente von x_train==x_predict_skalar sind.
vielen Dank für eure Antworten. Also in dem zweiten Fall, wenn d=5 ist, soll quasi jede Zeile als einzelner Vektor genommen werden, davon dann die euklidische Länge berechnet und diese dann aufaddiert werden. Stimmt das dann damit überein:
Klar müsste es ja eigentlich, denn ^2 hebt die Wurzel auf und somit bleibt nur übrog das jeder Eintrag quadiert wird, richtig?!
so wie es da steht stimmt es, dass k sich weg kürzt, das darf es aber eigentlich nicht, habe mir noch einmal meine ursprüngliche Gleichung angesehen und werde es noch einmal verändern müssen.
Sirius, also ich habe das Skalar deshalb in einen Vektor kopiert, weil ich dachte es macht den Umgang damit in Matlab schneller, und außerdem hatte ich zuerest vor zwischen d=1 und d=5 nicht zu unterscheiden, sondern den Code so zu schereiben, dass er mit beidem umgehen kann. Habe es aber dann doch erst einmal anders gemacht und somit ist das noch ein Überbleibsel.
Wenn ich im zweiten Teil die for Schleife weg lassen kann, dann brauch ich K auch nicht hochzählen und am Anfang Null setzten. Das stimmt doch so oder?
Klar müsste es ja eigentlich, denn ^2 hebt die Wurzel auf und somit bleibt nur übrog das jeder Eintrag quadiert wird, richtig?!
Im Zweifelsfall würde ich das an einem Beispiel testen, ob (zumindest annähernd) das gleiche herauskommt.
Zitat:
ich habe das Skalar deshalb in einen Vektor kopiert, weil ich dachte es macht den Umgang damit in Matlab schneller,
Wäre mir neu
Zitat:
Wenn ich im zweiten Teil die for Schleife weg lassen kann, dann brauch ich K auch nicht hochzählen und am Anfang Null setzten.
Das hängt davon ab, wo K auf 0 gesetzt wird.
So, wie der Code momentan dasteht, brauchst du das weiterhin.
Wenn K nur innerhalb der Schleife auf 0 gesetzt wird, brauchst du es nicht.
habe vorher übersehen, dass k im bruch nciht die summe aller k ist, sondern nur k an der stelle x_i.
jedoch habe ich noch eine Frage,
es wurde ja geschrieben, weil h eine konstante ist, konne man es raus nehmen aus der norm, müsste es aber dann nicht quadiert sein, also müsste dann icht der term:
Code:
K = exp(-(0.5/h)*sum((x_predict_skalar - x_train).^2));
müsste dann icht der term anstatt von (0.5/h) nicht (0.5/h^2) sein?
ja, muss es wohl.
Solche Dinge lassen sich ja aber auch leicht überprüfen, indem man die Funktion für mehrere Code-Varianten durchlaufen lässt und die Ergebnisse vergleicht. Natürlich nicht unbedingt mit h = 1
Falls du noch irgendwo Hilfe brauchst, bitte genau angeben wo.
%consider only the i-th entry (scalar or row vector) of x_predict
x_predict_vector = repmat(x_predict(i,:),SizeOfX,1);
%compute the weights of y_i with the Gaussian Kernel Function
k=sum(exp(-(0.5/h^2)*sum((x_predict_vector - x_train).^2,2)));
if(k==0)
y_predict(i)=0;
break else for j=1:SizeOfX
W(j)= (exp(-(0.5/h^2)*(x_predict_vector - x_train(j,:)).^2))/k;
end end
hierzu noch eine Frage, mit dem Befehl break, beende ich doch jetzt nur den Durchlauf i=1 z.b oder? beende ich damit die for-schleife komplett? Falls dies der Fall sein sollte, wie kann ich dann nur die eine Iteration der for-Schleife beenden?
nur wieder mit aufgenommen, da ich jetzt den Code ohne vorherige if Abfrage geschrieben habe, dass also beide Fälle d=1 und d=5 gleich behandelt werden, da ja das Verfaren das selbe ist und auch in der Abänderung
das richtige rauskommt, auch wenn (x_predict_vector - x_train) nur ein eindimensionaler vektor ist, dass ist zwar sum(...,2) unnötig aber es erlaubt mir die gleiche behandlung beider fälle.
Christina
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 02.10.2012, 18:38
Titel:
Hallo,
ich bin es noch einmal. Ich habe jetzt meinen Code komplett überarbeitet, so dass er sowohl mathematisch korrekt ist, tatsächlich das richtige berechnet und sowohl für den eindimsionalen als auch für den mehrdimensional Fall verwendbar ist. Jetzt ist er nur wirklich ziemlich ziemlich langsam. Er berechnet nun seit 11 Stunden und hat nicht einmal ansatzweise die Hälfte aller Wiederholungen geschafft und es ist der eindimensional Fall...
Könntet ihr vielleicht noch einmal drüber schauen und mir sagen ob ihr auf dem ersten Blick etwas seht um die Laufzeit zu verkürzen?
Code:
function[y_predict] = kregression(x_train,y_train, x_predict, h)
%REGRESSION construct regression estimate by using the Nadaraya Watson
%kernel estimate
% We are using as a kernel function the Gaussian kernel with bandwidth h, % which is choosen data dependent by "Splitting the Sample"
%compute the weights of y_i with the Gaussian Kernel Function:
for j=1:SizeOfX
K=K+ exp(-sum((x_predict(i,:)-x_train(j,:)).^2)/(2*h^2));
end
if(K==0)
y_predict(i)=0;
continue else for j=1:SizeOfX
W(j)=exp(-sum((x_predict(i,:)-x_train(j,:)).^2)/(2*h^2))/K;
end end
y_predict(i)=sum(W.*y_train);
end
%compute regression estimate with learning sample, and use X-values
%of testing sample for the empirical error
y_predict_t(:,:)= kregression(x_learning,y_learning,x_testing,hi);
%compute the empirical error mit Y-values of the testing sample, save
%the result and the corresponding bandwidth in a 2-dim. matrice
y_h(s,1)= (1/(nt))* sum((y_predict_t - y_testing).^2);
y_h(s,2)=hi;
% determine the minimal empirical L2 risk and remember the position [c,i]=min(y_h);
% bandwidth is the value on the position i in the second column
h= y_h(i(1),2);
% now do regression estimate again with the predicted x-values
y_predict=kregression(x_learning,y_learning,x_predict,h);
end
Gibt es hier eine Möglichkeit für eine for Schleife zweit Counter zu verwenden? Oder kann ich mir auf irgendeine Weise den Counter s sparen? Auch hier noch einmal die gleiche Frage, gibt es hier eine Möglichkeit die Laufzeit zu verkürzen?
Vielen Dank schon einmal im Vorraus.
In den for-Schleifen in kregression berechnest du zwei Mal sehr ähnliche Dinge.
Du könntest die W(j) am Anfang berechnen und sie dann in der Schleife verwenden. Der Fall K == 0 wird ja eher die Ausnahme sein, und nur auftreten, wenn im Exponentialterm extrem große Werte vorkommen.
Die Berechnung der W(j) ist für verschiedene h sehr ähnlich. Es wäre also wohl möglich, dass kregression einen Vektor von h's entgegennimmt und das ganze sp effizienter abgearbeitet wird.
Schließlich kann man wohl noch bsxfun verwenden, um x_predict(i,:)-x_train(j,:) für festes i effizienter zu berechnen. Zusammen mit dem Trick von zuvor sollte die for-Schleife dann wegfallen.
Insgesamt würde ich einen Beschleunigungsfaktor von min. 20 erwarten, vermutlich deutlich mehr.
Wichtig: immer wieder (z.B. an kleinen Testfällen) überprüfen, ob nach wie vor das richtige gemacht wird - nicht dass man da irgendwo Fehler einbaut.
Wenn die Parallel Computing Toolbox vorhanden ist und du auf einem Rechner mit mehreren Kernen arbeitest, kann man am Ende noch eine for-Schleife parallelisieren (der Aufwand dazu ist meist sehr gering) und auch so nochmal was rausholen. Am Anfang sollte aber wirklich stehen, den existierenden Code zu optimieren.
Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
RSS