For a second, I misread this as "Machine Learns Course Materials". Must make this happen - wonder if I can use these machine learning course materials to help.
Machine Learning Course Materials
11–14 of 14 posts
Re: Machine Learning Course Materials
#12Earlier quoted context omitted.
Ooh, Matrix multiplication? Would I get to use Strassen's sub-cubic algorithm? I've been looking for an excuse to use it.
afaik, octave uses blas, which in turn should be using strassen's for it's sgemm, dgemm etc. computations. at least it would be very surprising if it didn't...
Having done a very small amount of research into it I actually think it would be surprising if it did use Strassen's. EDIT: At least frequently, I assume it would use Strassen's for larger matrices much in the same way as introsort works.
Apparently it's becoming irrelevant/unwieldy as computing power increases.
"Practical implementations of Strassen's algorithm switch to standard methods of matrix multiplication for small enough submatrices, for which those algorithms are more efficient. The particular crossover point for which Strassen's algorithm is more efficient depends on the specific implementation and hardware. Earlier authors had estimated that Strassen's algorithm is faster for matrices with widths from 32 to 128 for optimized implementations.[1] However, it has been observed that this crossover point has been increasing in recent years, and a 2010 study found that even a single step of Strassen's algorithm is often not beneficial on current architectures, compared to a highly optimized traditional multiplication, until matrix sizes exceed 1000 or more, and even for matrix sizes of several thousand the benefit is typically marginal at best (around 10% or less)." - http://en.wikipedia.org/wiki/Strassen_algorithm
Coppersmith-Winograd, assuming it is not another Galactic algorithm, looks better - http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_al...
However I do strongly suspect that this is a Galactic algorithm.
In fact, judging from this (http://www-cs.stanford.edu/~virgi/matrixmult-f.pdf), the Big O of time taken for matrix multiplication has been decreasing steadily and without much fuss ever since Strassen.
Again, I suspect these are even more galactic algorithms than strassen's is.
Re: Machine Learning Course Materials
#13Earlier quoted context omitted.
afaik, octave uses blas, which in turn should be using strassen's for it's sgemm, dgemm etc. computations. at least it would be very surprising if it didn't...
Having done a very small amount of research into it I actually think it would be surprising if it did use Strassen's. EDIT: At least frequently, I assume it would use Strassen's for larger matrices much in the same way as introsort works. Apparently it's becoming irrelevant/unwieldy as computing power increases. "Practical implementations of Strassen's algorithm switch to standard methods of matrix multiplication for…
Right. Basically, Strassen's is not friendly to the cache - any improvement you get in the asymptotic behavior is usually swamped by the cost of cache misses.
In that vein, the naive implementation (O(n^3)) implementation is also not cache friendly - if you flip the inner loops you will get far better performance (in row major languages).
But I mainly replied because I love the concept of "galactic algorithms" and Regan&Lipton (orignators of the idea and name).
EDIT: the BLAS routine in question is dgemm.f (double general matrix multiply) and is easily googled so I won't paste it here. No Strassen's in sight.
Re: Machine Learning Course Materials
#14As a reference, you'll want one or two of the Big 6 texts, by Murphy, Koller/Friedman, Bishop, MacKay, and Hastie et al ESL. The first review is good http://www.amazon.com/product-reviews/0262018020/ref=dp_top_...
Also, there are many freely available texts on ML, data mining, stats/prob distributions, linear algebra, optimization etc, incl Barber, Mackay and ESL. See http://www.reddit.com/r/MachineLearning/comments/1jeawf/mach...