Lyric: Linear Regression in Pure Javascript

Lyric is an Open Source implementation of Linear Regression in pure javascript, built on the great javascript matrix library Sylvester by James Coglan and the popular JQuery library. Feel free to use it to implement your own trending and prediction charts or read more below on how it’s built and how to use it. You can download or fork it on Github (Lyric) in the Flurry Github account.

What is Linear Regression?

Given a dataset including a dependent and an explanatory variable, linear regression is a statistical technique used to create a model (equation) that best represents the relationship between the variables. This model can then be used to predict additional values that will follow the same pattern. It is a technique commonly used to add trend lines to charts of time series data and in Machine Learning to predict future values from a given training set of data.

For example, given the following set of noisy timeseries data:

Screen_shot_2012-05-09_at_5

It might be hard to tell from this sample if the values are increasing or decreasing over time. Applying linear regression can yield a trendline to make the pattern clear, such as the following (in green):

Screen_shot_2012-05-09_at_5

Typically, linear regression is implemented using an optimization approach such as Gradient Descent which starts with a rough approximation and improves the accuracy over a large number of iterations. While such an approach will optimize the model, it can be slow based on the number of iterations required. In some cases the problem can be greatly simplified and solved in closed form using a derivation called the Normal Equation

Lyric uses the Normal Equation to make it fast and efficient, as it should work for most applications. 

Using Lyric

First, make sure your data is represented in the form of a 2xN Array comprised of elements with an ‘x’ and ‘y’ value. The x value should be the explanatory and the y the dependent variables.

https://gist.github.com/2797345

Then you need to have Lyric determine the best equation to represent this data. The equation is known as the model and you can build it using the following:

https://gist.github.com/2797461

Now that you have your model, you will want to apply it to a set of inputs. The newInput should be a 1xN array containing only the explanatory variable values you would like to calculate the dependent values. This will result in a new 2xN array which will include the resulting series. 

https://gist.github.com/2797579

The following is a complete example which, given some values for the explanatory values 1 through 5, estimates the values of 6 through 8:

https://gist.github.com/2796914

If you wanted to create a trend line, such as in the example above, you would simply apply the model to the same x values you provided in the input to build the model. 

For more information on using Lyric (and more advanced options) please refer to the Lyric README.

How is Lyric implemented?

Lyric implements the normal equation using a series of matrix operations implemented by Sylvester. However, before the matrix operations can be applied, the input series x (explanatory values) must be modified to represent the degree of polynomial we want to use to fit the data. To do this, we simply take the vector of x values and create a matrix where each row is the values of x raised to a given power. For example, given the power = 3 (for a 3rd degree polynomial) the output O will be of the form:

O[0] = x^0  i.e. all ones

O[1] = x^1  i.e. the same as x

O[2] = x^2  i.e. all elements of x squared

O[3] = x^3  i.e. all elements of x cubed

If you are familiar with linear algebra, you’ll recognize that this represents an equation of the form:

Ax^3+Bx^2+Cx+D

Once the input is in this form, the actual matrix operations are fairly simple, following the normal equation steps. 

https://gist.github.com/2797087

The resulting theta matrix is the values of the constants A, B, C and D from the above equation. Then, by multiplying future values of x by the same theta matrix we can predict y values. 

Learn More

If you’re like to learn more about Linear Regression, the Machine Learning class offered by Coursera reviews it in high detail (as well as many other machine learning topics). 

Standard

3 thoughts on “Lyric: Linear Regression in Pure Javascript

  1. tinybugchild says:

    I get null for the estimated value of any point below 1 when calling applyModel(). Your example trendline seems to be showing the same problem.

  2. sbyrnes says:

    Thanks for pointing this out, this was fixed in an update last week. The problem was that some 1-indexed vectors were being treated as 0-indexed arrays so the 0 value was always empty.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s