Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Performing Linear Regression Using Ruby

sharethrough.com

Post reply on HN
Print view View original

31–40 of 44 posts

Re: Performing Linear Regression Using Ruby

#31

Post by east2west »

rohitarondekar wrote: post #18
sciboy wrote: post #2

B = (X^TX)^(-1)X^TY anyone?

In computing (X^TX)^(-1) if the number of features is large then it can be slow as computing the inverse of a matrix is slow. Also unless you use pseudo inverse (pinv in octave) you need to take care of degenerate cases. However if you use Regularization i.e replace the (X^TX)^(-1) with (X^TX + lambda*W)^(-1), where lambda is the regularization parameter and W is a matrix of the form: |0 0 0| |0 1 0| |0 0 1| i.e iden…

DO NOT EVER use Penrose pseudoinverse in numerical computation. It is guaranteed to diverge.

Re: Performing Linear Regression Using Ruby

#32

Post by beagle3 »

rohitarondekar wrote: post #18
sciboy wrote: post #2

B = (X^TX)^(-1)X^TY anyone?

In computing (X^TX)^(-1) if the number of features is large then it can be slow as computing the inverse of a matrix is slow. Also unless you use pseudo inverse (pinv in octave) you need to take care of degenerate cases. However if you use Regularization i.e replace the (X^TX)^(-1) with (X^TX + lambda*W)^(-1), where lambda is the regularization parameter and W is a matrix of the form: |0 0 0| |0 1 0| |0 0 1| i.e iden…

All regularization work I'm aware of uses W=I (an identity matrix). Where did you find this zero origin matrix?

Note that your W does not guarantee invertability - e.g., if your original (0,0) is already 0.

Re: Performing Linear Regression Using Ruby

#33

Post by beagle3 »

rohitarondekar wrote: post #26
crntaylor wrote: post #22

Earlier quoted context omitted.

Implementation tip - you don't need to invert that matrix! [1]. Whenever you see an equation of the form Ab = c and you want to find b, you should use a function equivalent to lu_solve (in the GNU Scientific Library) or the left-divide operator in Octave/Matlab (b = A\c), which will use the LU factorization algorithm [2] without ever computing A^(-1). This is normally faster, more numerically stable and more space ef…

According to Wikipedia[1]Matrix Inversion is also O(n^3) and according to the note can be even better by inverting smaller matrices within and multiplying[2]. My linear algebra isn't very good so I'll have to look into LU Factorization but is there vast difference between the computational performance of the two operations? (Assuming you don't need solve Ab=c for different values of b and c) Also is LU Factorization…

The reason you want to avoid matrix inversion is not computational performance - it is precision.

You can generally "multiply by the inverse" without actually computing the inverse, in a way that needs less intermediate floating point precision.

If your matrices have a large spread of eigenvalues, it makes a lot of difference - double precision often doesn't have enough precision for direct inversion in the real world.

(And even if you do want to invert, it is more numerically stable to do that as a solution of Ax=e, for each 'e' a basis element, as long as you compute A^-1 \* e indirectly using a numerically stable method)

Re: Performing Linear Regression Using Ruby

#34

Post by ucsd_surfNerd »

gammarator wrote: post #12

...and at the end he shows you how to do the same thing with two lines of R. It's very useful to code basic statistical algorithms yourself so you understand how they work, but for any serious analysis you'll get more reliable and performant results with a library.

That is exactly what I was going for. Basic algorithm yourself to help people understand the math but you wouldn't want to use this code in a production system.

In fact I perform the vast majority of my statistical analysis in R.

Ruby is just a fun language to implement basic statistical algorithms in and it the Ruby community as a whole doesn't hasn't put a lot of emphasis on stats.

Re: Performing Linear Regression Using Ruby

#35

Post by ucsd_surfNerd »

cheald wrote: post #10

We do regressions with rb-gsl. require 'gsl' x = GSL::Vector.alloc(array_of_x_values) y = GSL::Vector.alloc(array_of_y_values) c0, c1, cov00, cov01, cov11, chisq, status = GSL::Fit::linear(x, y) It's not nearly as much work, and it's much faster than doing it in pure Ruby. :) (It also does weighted regressions and exponential fitting, among a host of other things. That wheel's gone done been invented already.)

I did look at GSL :). I decided to write it by hand because I wanted to help people understand the underlying math. I find that too many people use libraries without understand the math which can become problematic especially when performing statistical analysis.

Thanks for pointing out GSL. I appreciate the feedback.

Re: Performing Linear Regression Using Ruby

#36

Post by ucsd_surfNerd »

EzGraphs wrote: post #3

Ruby is great for data prep, basic calculations, web app development, and scraping aggregating data and R for visualization. I find them to be a joyful combination. Great for small data sets, quick estimations, and various small projects. Larger data sets and performance intensive operations are better handled in Python (or Java, C++, etc). Lots of statistical analysis is way below the threshold of Hadoop and company…

I totally agree that Ruby + R makes a great data toolbox. I use Ruby + R for almost all of my day to day exploratory data analysis work.

As far as python goes I think python has become more popular simply because it has more community around data applications. Unfortunately a lot of people view ruby as just Rails. I think academia's adoption of python has also helped it grow into a data analysis language.

Really any MR you do with python you could do with Ruby as it all uses hadoop streaming.

Re: Performing Linear Regression Using Ruby

#37

Post by cheald »

ucsd_surfNerd wrote: post #35
cheald wrote: post #10

We do regressions with rb-gsl. require 'gsl' x = GSL::Vector.alloc(array_of_x_values) y = GSL::Vector.alloc(array_of_y_values) c0, c1, cov00, cov01, cov11, chisq, status = GSL::Fit::linear(x, y) It's not nearly as much work, and it's much faster than doing it in pure Ruby. :) (It also does weighted regressions and exponential fitting, among a host of other things. That wheel's gone done been invented already.)

I did look at GSL :). I decided to write it by hand because I wanted to help people understand the underlying math. I find that too many people use libraries without understand the math which can become problematic especially when performing statistical analysis. Thanks for pointing out GSL. I appreciate the feedback.

It's definitely good to understand the underlying math, and it's a good article on "this is how to translate a formula into Ruby code", but given that the article is positioned as "We needed to solve this problem, and this is how we solved it", it seems like it'd make more sense to focus on solving it with the least work and the best performance, which is why I mentioned GSL.

It's great to see other people doing statistical work in Ruby, though, so please don't let my criticism keep you from continuing to do it! :)

Re: Performing Linear Regression Using Ruby

#38

Post by rohitarondekar »

beagle3 wrote: post #33
rohitarondekar wrote: post #26

Earlier quoted context omitted.

According to Wikipedia[1]Matrix Inversion is also O(n^3) and according to the note can be even better by inverting smaller matrices within and multiplying[2]. My linear algebra isn't very good so I'll have to look into LU Factorization but is there vast difference between the computational performance of the two operations? (Assuming you don't need solve Ab=c for different values of b and c) Also is LU Factorization…

The reason you want to avoid matrix inversion is not computational performance - it is precision. You can generally "multiply by the inverse" without actually computing the inverse, in a way that needs less intermediate floating point precision. If your matrices have a large spread of eigenvalues, it makes a lot of difference - double precision often doesn't have enough precision for direct inversion in the real worl…

Thank you for explaining, I think I get it now. The ML course on Coursera is a little light on the Maths. As in the professor only explains as much is needed to perform the techniques. So I think I'll be watching Strangs Linear Algebra lectures on OCW soon. :)

Re: Performing Linear Regression Using Ruby

#39

Post by rohitarondekar »

beagle3 wrote: post #32
rohitarondekar wrote: post #18

Earlier quoted context omitted.

In computing (X^TX)^(-1) if the number of features is large then it can be slow as computing the inverse of a matrix is slow. Also unless you use pseudo inverse (pinv in octave) you need to take care of degenerate cases. However if you use Regularization i.e replace the (X^TX)^(-1) with (X^TX + lambda*W)^(-1), where lambda is the regularization parameter and W is a matrix of the form: |0 0 0| |0 1 0| |0 0 1| i.e iden…

All regularization work I'm aware of uses W=I (an identity matrix). Where did you find this zero origin matrix? Note that your W does not guarantee invertability - e.g., if your original (0,0) is already 0.

This was shown by Professor Andrew in the Coursera ML class that's happening right now.

Given n features x1 to xn we introduce x0 feature which is always set to 1. During the Regularization lectures the professor said that we don't need to control (or regularize) the theta0 (the parameter for x0) because it doesn't make a difference. I believe this is the reason W(0,0) is set to 0.

The lectures are a little light on the maths, i.e the professor explains only enough maths to explain the techniques so I'm not aware of more details. I'm planning on watching some Linear Algebra lectures to fill in the gaps. :)

Re: Invertability, according to the professor, if lambda is > 0 then the matrix will be invertable. Again I'm not 100% sure if this is true or not.

Re: Performing Linear Regression Using Ruby

#40

Post by rohitarondekar »

east2west wrote: post #31
rohitarondekar wrote: post #18

Earlier quoted context omitted.

In computing (X^TX)^(-1) if the number of features is large then it can be slow as computing the inverse of a matrix is slow. Also unless you use pseudo inverse (pinv in octave) you need to take care of degenerate cases. However if you use Regularization i.e replace the (X^TX)^(-1) with (X^TX + lambda*W)^(-1), where lambda is the regularization parameter and W is a matrix of the form: |0 0 0| |0 1 0| |0 0 1| i.e iden…

DO NOT EVER use Penrose pseudoinverse in numerical computation. It is guaranteed to diverge.

Can you please explain why this is? Or maybe point to an explanation somewhere? Thanks.
Post reply on HN