<html><head><style type="text/css"><!-- DIV {margin:0px;} --></style></head><body><div style="font-family:garamond, 'new york', times, serif;font-size:18pt"><div style="color: black; "><font class="Apple-style-span" face="'times new roman', 'new york', times, serif" size="2">Hi Brian,</font></div><div style="color: black; "><font class="Apple-style-span" face="'times new roman', 'new york', times, serif" size="2"><br></font></div><div style="color: black; "><font class="Apple-style-span" face="'times new roman', 'new york', times, serif" size="2">Although I'm not familiar with how IterativeRelief works, but, if the complexity has O(T*N^(2*L)) then it might need few hundred years (or maybe much more) to finish since the complexity here is ~ O(2^50,000) ... If L is 40, you'll need roughly 1099511627776 operations, now, suppose each operation takes 1E-7 second ... then, for L =40 our processor will take:</font></div><div style="color: black;
"><font class="Apple-style-span" face="'times new roman', 'new york', times, serif" size="2"><br></font></div><div><font class="Apple-style-span" face="'times new roman', 'new york', times, serif" size="2">1099511627776 *1E-7 /3600 ~= 30.5 hours </font></div><div><font class="Apple-style-span" face="'times new roman', 'new york', times, serif" size="2"><br></font></div><div><font class="Apple-style-span" face="'times new roman', 'new york', times, serif" size="2">Now the problem is that 2^n is neither linear nor polynomial, in fact, it has exponential growth. So my guess is that the</font><font class="Apple-style-span" face="'times new roman', 'new york', times, serif" size="2"> complexity of </font><span class="Apple-style-span" style="font-family: 'times new roman', 'new york', times, serif; font-size: small; ">O(T*N^(2*L)) is the for the direct implementation of the algorithm and without any optimization to speedup the
process.</span></div><div><font class="Apple-style-span" face="'times new roman', 'new york', times, serif" size="2"><br></font></div><div><font class="Apple-style-span" face="'times new roman', 'new york', times, serif" size="2">Regards,</font></div><div><font class="Apple-style-span" face="'times new roman', 'new york', times, serif" size="2">-Rawi</font></div><div><font class="Apple-style-span" face="'times new roman', 'new york', times, serif" size="2"><br></font></div><div style="font-family: garamond, 'new york', times, serif; color: black; "><font class="Apple-style-span" size="2"><br></font><div style="font-family: arial, helvetica, sans-serif; "><font size="2" face="Tahoma"><hr size="1"><b><span style="font-weight: bold;">From:</span></b> Emanuele O<font class="Apple-style-span" size="2">livetti <emanuele@relativita.com></font><br><b style="font-size: 10pt; "><span style="font-weight: bold;">To:</span></b><font class="Apple-style-span"
size="2"> Development and support of PyMVPA <pkg-exppsy-pymvpa@lists.alioth.debian.org></font><br><b style="font-size: 10pt; "><span style="font-weight: bold;">Sent:</span></b><font class="Apple-style-span" size="2"> Wed, January 12, 2011 3:33:31 PM</font><br><b style="font-size: 10pt; "><span style="font-weight: bold;">Subject:</span></b><font class="Apple-style-span" size="2"> Re: [pymvpa] time complexity of IterativeRelief feature selection</font><br></font><br><font class="Apple-style-span" size="2">
On 01/12/2011 01:42 PM, Brian Murphy wrote:</font><br><font class="Apple-style-span" size="2">> </font><br><font class="Apple-style-span" size="2">> I've been running an IterativeRelief feature selection for five days now, and it still hasn't completed. Does anyone have experience to help me get a ball-park estimate of how long it should take? My dataset is ~300 samples by ~25,000 features. I see on the API documentation that the algorithm has complexity "O(T*N^2*I), where T is the number of iterations, N the number of instances, I the number of features". Any idea what the number of iterations should/might be? I don't see a parameter to set this,</font><br><font class="Apple-style-span" size="2">> </font><br><br><font class="Apple-style-span" size="2">Hi Brian,</font><br><br><font class="Apple-style-span" size="2">My guess is that at least one of the following situations occurs:</font><br><font class="Apple-style-span" size="2">- The initial
guess you are starting from is not good for your</font><br><font class="Apple-style-span" size="2">problem. Did you normalize data?</font><br><font class="Apple-style-span" size="2">- The threshold you are using is too low and so it take ages, maybe</font><br><font class="Apple-style-span" size="2">without any real gain. Try to increase it. Again data nomalization</font><br><font class="Apple-style-span" size="2">should play an important role.</font><br><font class="Apple-style-span" size="2">- Your problem is not so friendly towards optimization :-) so a</font><br><font class="Apple-style-span" size="2">stochastic gradient strategy like IterativeReliefOnline might help.</font><br><br><font class="Apple-style-span" size="2">In any case I strongly suggest you to enable the debug mode</font><br><font class="Apple-style-span" size="2">and observe the evolution of the convergence statistics. It will</font><br><font class="Apple-style-span" size="2">tell
you/us more on where is the problem.</font><br><br><font class="Apple-style-span" size="2">Emanuele</font><br><br><br><font class="Apple-style-span" size="2">_______________________________________________</font><br><font class="Apple-style-span" size="2">Pkg-ExpPsy-PyMVPA mailing list</font><br><a ymailto="mailto:Pkg-ExpPsy-PyMVPA@lists.alioth.debian.org" href="mailto:Pkg-ExpPsy-PyMVPA@lists.alioth.debian.org" style="font-size: 10pt; ">Pkg-ExpPsy-PyMVPA@lists.alioth.debian.org</a><br><font class="Apple-style-span" size="2"><span><a target="_blank" href="http://lists.alioth.debian.org/mailman/listinfo/pkg-exppsy-pymvpa">http://lists.alioth.debian.org/mailman/listinfo/pkg-exppsy-pymvpa</a></span></font><br></div></div><div style="position: fixed; font-size: 18pt; font-family: garamond, 'new york', times, serif; color: black; "></div>
</div><br>
</body></html>