Skip to content →

Category: SOCIAL MEDIA & IT

Down-to-earth principal components analysis in 5 steps

Published December 4, 2011 by Jo Jordan

This post is a step-by-step, practical, guide to principal components analysis.  It’s very hands-on and “common sensical”.  If any experts out there spot an egregious error that would horribly mislead a beginner, please do let me know.

I’ll simply work through 4 steps and then sum up as 5 steps in a slightly different order.

#1 Data

I always like to start any data problem by thinking about my data rather concretely.

In a PCA problem, imagine a spreadsheet which has hundreds or even thousands of columns – far too many for comfort.

On each row of the spreadsheet is a case, or ‘training example’ in machine learning parlance.

What we want to do is to find the columns that matter.  Alternatively, we ask “which columns could we bundle together into computed columns so that we have a more manageable number?”

In short, this procedure will tell us which columns we can leave out and which one’s we should bundle together.  The bundles will be the principal components.  And the final answer will tell us how much precision we have lost by bundling scores rather than using original raw data.

So, we begin with data which is laid out in matrix X with m rows and n columns (m x n).

#2 Normalize the data

The data comes in all sizes – little numbers and big numbers, very spread out and bunched together.  First we smooth the data in the same way that tests are normed at college.  Simply, we convert each column to a mean of zero and a standard deviation of one.

To be very clear how this works, we take each cell and adjust the number in the cell depending on the other numbers in the column. If we were working with spreadsheets, we would open another spreadsheet of exactly the same number of rows and columns and add this formula to each cell. So for cell A1 we would have:

= (Sheet1!A1 – mean(ColumnA))/StdDev(ColA)

When we calculate the mean and stddev of the columns in the new spreadsheet, they will all be 0 and 1 respectively.

#3 Principal Component Analysis

Now we find the ‘bundles’ of columns.

In my old days of statistics packages, the program would return a table which listed all the columns down the page and then produced factor loadings or weights for a whole heap of factors (or bundles) in more columns.  The number and the sign would tell you the weight of the original data column in the new ‘bundle’.  The weights varied from -1 through 0 to +1.

In Octave, the free version of Matlab, there is a facility to do PCA in two steps:

Step #3 Part One

  • Compute what is called the covariance matrix.  Simple imagine taking  a copy of the spreadsheet (the second one), multiplying it cell to cell (A1 to A1) and taking the sum of those squares in the new column A, then A1 to B1 and taking the sum of the product in column B, then A1 to C1.. etc until we have new row with N columns each got by multiplying two columns and adding up the product. You’ll have to try it yourself.  I’ll have to get out pen and paper when I read this a year from now.
  • Then we do the same starting with Col B and Col A (that’s a repeat, I know.. stick it in), B to B, B to C  etc.
  • Until we have a new matrix with N columns and N rows.  (Yes – this is what computers are for).
  • And one more sub- step – divide every cell by the original number of cases or training examples (i.e., rows in the very first spreadsheet).

That’s the covariance matrix.  In Octave, which uses linear algebra, it is much easier.  You just tell the machine to multiply the transpose of the normalized data by the normalized data and divide by m – one line of code.

CovarianceMatrix = (X’ * X )/m

(That’s what computers are for!.. the explanation was just so you have a concrete idea of where the data came from and what happened to it).

Step #3 Part One

The second step in PCA is to find the bundles using a function that is built into Octave called the ‘singular value decomposition’ or SVD.

All you do is ask for it and it ‘returns’ three matrices, U, S and V and we are going to use U and S.

U gives us a matrix exactly the same size as the covariance matrix.  Each column now refers to a ‘bundle’. The rows still refer as before to the features (that is the original columns in the data matrix and the normalized data matrix. Have a quick check.  I’ll wait!).

Note we have as many bundles as we had columns right at the start but we don’t want to use all the unbundles (columns in the U matrix) otherwise we will have exactly the same number of columns as when we started – no point, hey?

So we will only use as many, starting from the left, as we need.  We will decide how many to use on the basis of the S matrix.

Let’s do that later and  consider further what U actually tells us.  As we read down column one, cell A1 tells us the loading of original column A, or the 1st feature, on the new bundle 1.  Cell A2 tells us the loading of original column B or the 2nd feature, on new bundle 1. And so on.  Got it?  Try it out.

So what can we do with this?  Two things –

  • We can see which of our original columns were the most important.  They are the ones with the biggest numbers in column on the left and subsequent columns as you move right.   A positive number means the higher the original number the higher would be the bundle score. A negative number in this new table means the higher the number in the original table, the lower would be the bundle score.  Good to know if two of our original columns pull in  the opposite directions. So that is the first use – to understand the original columns and how they hang together.
  • The second use is to create a simplified data set.  Ok, we hate it when bureaucrats create scores for us – like a credit rating. But imagine the rows are just pictures and the columns were the pixels or colors at 10 000 points on page – collapsing 10 000 columns into 1000 columns or 100 columns could be handy for data compression.  (We’ll work out later how much data is lost – or how much blur is added!)  So how do we recreate the scores?  We will come back to this – lets stick with understanding what those numbers in the U matrix mean. All we have to do to get a score for the bundle  is take the number in the U matrix for original column A (now in row 1) and multiple it by the score for the first case in column A  (do it on a bit of paper).  Do that for the whole row for the case times the whole column in U (row of original data times column in the U matrix), add it up, and we get a ‘bundle’ score for the first case.  That will go in cell A1 in a new table. The cell is the score for case 1 on bundle 1.
  • Then we can do the same for the second case, then the third.  And we will make a new column of bundled scores for the whole data set.
  • Then we do the same for the second bundle (it’s OK – that’s what computers are for).
  • Finally we have a matrix with as many rows as we have cases or training examples and as many columns as we have new bundles.  This can be useful when we need compressed data and we don’t mind a bit of blur in the data.

#4 How many bundles do we need?

So now we come back to how many bundles do we need?  Well firstly, a lot fewer than the number of columns that we started with. That’s the whole idea of this exercise – to get that original spreadsheet a lot, lot smaller.

I mentioned before that we use the data for the second matrix, S, that is churned out by the SVD function in Octave, to work out how many bundles to keep.

This S matrix is also exactly the same size as the covariance matrix which was square with the same number of rows and columns as we had columns in the first, first, first data table.

This time, though, we only have data in the diagonal from top left to bottom right.  Every other cell is zero.  So that means there is a number for original row 1 and column A; row 2 and column B; etc.  Gee, couldn’t we have a column?  Yes we could. It’s laid out this way to do with the way machines do arithmetic. It is easier for the machine to pull out the matching diagonal from the U matrix for example.  But that’s not our problem right now.  We just want to know how to use these numbers to work out how many bundles to keep.

Well, these numbers represent how much variance is explained by the bundle.  The very first number (top left) tells us how much variance in the whole original data set is explained by the new bundle.  To work out what % of variance is accounted for by this bundle, we take all the numbers on the diagonal and add them up to give us a number representing all the variance in the whole data set.  Then we take the number for the first bundle (top left) and work it out as a percentage of the whole lot. If the percentage is less than 99% (.99), then we add another bundle (well we add the percentage of another bundle or we add the numbers of the two bundles and divide by sum for all the numbers).  We just keep going until we have enough bundles to account for 99% of the original variance.  (So in plain terms, we have allowed for 1% of blurring).

Oddly, only 1% of blurring might allow us to lose a lot of columns.  Or more precisely, when we compute new scores, one for each bundle in the final solution, we might have far fewer bundles than original number of columns, but still account for 99% of the original amount of detail.

 That’s it…that’s PCA.

#1 Get your data in a spread sheet (cases on rows, features in columns)

#2 Normalize the data so each column has a mean of 0 and an SD of 1

#3 Use a built-in function to return a matrix of eigenvectors (U) and variance (S)

#4 Decide how many ‘bundles’ of features to keep in (account for 99% of variance)

#5 Compute new scores – one score for each case for each bundle (now the columns)

And what do we do with this?

#1 We understand how columns hang together and what we can drop and only lose 1% of detail (or add 1% of blur)

#2 We can use the new scores to do other things like feed them into a prediction program or supervised learning program. The advantage is not to improve on prediction, btw,  but to cut down on computing costs.

That’s all!

CHECK OUT SIMILAR POSTS

3 Comments

10 steps to build a spam catcher

Published November 24, 2011 by Jo Jordan

Here are the ten broad steps to build a spam catcher

  1. Get a sample of emails that are known to be spam or not spam. Split the sample 60:20:20 to provide a “training” set, a “cross-validation” set and a “test” set.
  2. Turn each email into a list of words by
    • Stripping out headers (if not part of the spam test) and other redundancies
    • Running NLP software to record the stem of a word only (for example, record city and cities as cit)
  3. Count the number of times each unique word appears in the sample and order the list so that we can use the top 100 or 10 000 or 50 000 (whatever) to check for spam.  Remember to use stemmed words!
  4. Convert the list of words in each email into a list of look-up numbers by substituting the row number of the word from the dictionary we made in Step 3.
  5. For each email, make another list where row 1 is 1 if the first word in the dictionary is present in the email, where row 2 is the 1 if the second word in the dictionary is present in the email. If the word is not present, leave the value for that row as zero. You should now have as many lists are you have emails each with as many rows as you have words in your spam dictionary.
  6. Run a SVM algorithm to predict whether each email is spam (1) or not spam (0).  The input is the list of 1s and 0s indicating which words are present in the email.
  7. Compare the predictions with the know values and compute the percentage correct.
  8. Compute the predictions on the cross-validation set and tweak the algorithm depending on whether the cross-validation accuracy is too similar to the training accuracy (suggesting the model could be stronger) or too dissimilar (suggesting the model is too strong).
  9. Find the words most associated with spam.
  10. Repeat as required.

CHECK OUT SIMILAR POSTS

Leave a Comment

Learning curves and modelling in machine learning

Published November 15, 2011 by Jo Jordan

In this post, I am going to describe what I have just learned from Andrew Ng at Stanford about “learning curves”.  To computer scientist, a learning curve is what you might expect but describes how well data has been modeled.

I write this as a classically trained psychologist and it is clear that if we are to understand machine learning, we have to watch out for where the thinking of computer scientists differs radically from our own.  This is my commonsensical comparison of the two approaches.  I am writing it down to make sure I have followed what I heard.  It is rough and ready but may help you understand the differences between the two disciplines.

A learning curve in CS

Simply, the CStists take random samples of data where the first sample is very small, let’s say 1 because that is helpful to understanding the logic, and the last sample will be large, let’s say a few thousand.  This is random samples from the same large data set.

Generally, with a sample of 1 up to 3, we can model perfectly.  However, when we try the same model with another sample of the same size, the model will not predict well at all. The amounts of error for the experimental sample and the comparison sample will be hugely different.  So far so good. That’s what we all learned at uni.  Modelling on a small sample is the equivalent of an ‘anecodote’.  Whatever we observed may or may not transfer to other situations.

As we increase our sample size, paradoxically the amount of error in our model increases but the amount of error in our comparison situation decreases.  And ultimately, the error we are making in the two situations converges.  We also know this from uni.

Much of our training goes into getting us to do this and to increasing the sample size so that the error in the hypothetical model goes up, and the error in the comparison model goes down.  Plot this on a piece of paper with error on the y axis and sample size on the x axis.

When the two error rates converge, that is we can explain the future as well as we can explain the present, then we stop and say, “Hey, I have found a scientific law!”

I would say that our willingness to tolerate a more general description of a particular situation so that we can generalize at the same level of accuracy (and inaccuracy) to another situation is one of the hallmarks of uni training. This is so counter-intuitive that many people resist so it takes uni training to get us to do it.

What the computer scientists implicitly point out is that the converse is also true. We are now able to explain the future as badly as we explain the present!  They call this underfitting and suggest that we try another model to see if we can do a better job of explaining the present.  So we will stop increasing the sample size and start playing with the model. We can vary the form of the model, typically moving from a linear to a non-linear model (that is adding more features) and increasing the weights of the parameters (go from a loose floppy kind of model to a stiffer model, if you like).

They do this until the model overfits. That is, until our explanation of the present is very good but the same explanation produces errors in comparison situations.  When they reach this point, they backtrack to a less complicated model (fewer non-linear terms) and decrease the weights of the parameters (take note of a feature but not put too much emphasis on it.)

Once they have found this happy middle ground with a more complicated model, but without the expense of collecting more data, they will try it out on a completely new set of data.

Break with common practice in psychology

For any psychologists reading this

  • This kind of thinking provides us with a possibility of getting away from models that have been stagnant for decades.  Many of these models predict the present so-so and the future so-so.  Here is the opportunity to break away.
  • Note that machine learning specialists use procedures that look like statistics but abandon the central idea of statistics.  They aren’t promising that their original sample was randomly chosen and they aren’t directly interested in the assertion that “if and only if our original sample was random, then what we found in the sample generalizes to other samples that have also been chosen randomly”.  Though they do something similar (taking lots of randomly chosen slices of data from the data they have), they aren’t in the business of asserting the world will never change again.  They have high speed computers to crunch more data when it becomes clear that the world has changed (or that our model of the world is slightly off).
  • Many of the rules-of-thumb that we were once taught fall away. Specifically, get a large sample, keep the number of features below the size of the sample, keep the model simple – these prescriptions are not relevant once we change our starting point.  All we want to find is the model that can generalize from one situation to another with the least error and high speed computers allow us both to use more complicated models and recomputed them when the world they described changes.

I am still to see good working examples outside marketing on the one hand and robotics on the other, but it seemed worth while trying to describe the mental shift that a classically trained psychologist will go through.  Hope this helps

CHECK OUT SIMILAR POSTS

Leave a Comment

Back propagation for the seriously hands-on

Published November 10, 2011 by Jo Jordan

I have just finished the Stanford back propagation exercise, and to put it mildly, it was a ****.

So is back propagation complicated?  And indeed what is it?

These are my notes so that I don’t have to go through all the pain when I do this again.  I am not an expert and the agreement with Stanford is that we don’t give away the answer particularly at the level of code.  So use with care and understand that this can’t tell you everything.  You need to follow some lecture notes too.

Starting from the top: What is back propagation?

Back propagation is a numerical algorithm that allows us to calculate an economical formula for predicting something.

I am going to stick to the example that Stanford uses because the world of robotics seems infinitely more useful than my customary field of psychology. Professor Ng uses an example of handwriting recognition much as the Royal Mail must use for reading postal codes.

We scan a whole lot of digits and save each digit as a row of 1’s and 0’s representing ink being present on any one of 400 (20×20) pixels.  Can you imagine it?

Other problems will always start the same way – with many cases or training examples, one to each row; and each example described by an extraordinary large number of features. Here we have 400 features or columns of X.

The second set of necessary input data is one last column labeling the row.  If we are reading digits, this column will be made up of digits 0-9 (though 0 is written down as 10 for computing reasons).  The digit is still 0 in reality and if we reconstructed the digit by arranging the 400 pixels, it will still be seen to the human eye as 0.

The task is to learn a shorthand way for a computer to see a similar scan of 400 pixels and say, aha, that’s a 1, or that’s a 2 and so on.

Of course the computer will not be 100% accurate but it will get well over 95% correct as we will see.

So that is the input data: a big matrix with examples along the rows of features and with the last column being the correct value – the digit from (10, 1-9) in this case.

How does back propagation work?

Back propagation programs work iteratively without any assumptions about statistics that we are used to in psych.

The computer boffins start by taking a wild guess of the importance of each pixel for a digit, and see what the computer would predict with those weights.  That is called the forward pass.

Then based on what the computer got right or wrong, they work backwards to adjust the weights or importance of each pixel for each digit.

And remembering that computers are pretty fast, the computer can buzz back and forth asking “how’s this?”.

After a set number of trials, it stops improving itself and tells us how well it can read the digits, i.e., compares its answers to the right answers in the last column of our input data.

What is a hidden layer?

Back proagation also has another neat trick.  Instead of using pixels to predict digits, it works with an intermediate or hidden layer.  So the pixels predict some units in the hidden layer and the hidden layer predicts the digits.  Choosing the number of units in the hidden layer is done by trying lots of versions (10 hidden units, 50 hidden units, etc) but I guess computer scientists can pick the range of the right answer as they get experienced with real world problems.

In this example, the solution worked with 25 hidden layers.  That is, 400 pixels were used to make predictions about 25 units which predict which of 10 digits made the data.

The task of the computing scientist is to calculate the weights from the pixels to the hidden layers and from the hidden layers to the digits and then report the answer with a % of “training accuracy” – over 95%, for example.

Steps in back propagation

We have already covered the first four  steps

Step 1: Training data

Get lots of training data with one example on each row and lots of features for each example in the columns.

Make sure the row is labeled correctly in the last column.

Step 2:  Decide on the number of units in the hidden layer

Find out what other people have tried for similar problems and start there (that’s the limit of my knowledge so far).

Step 3: Initialize some weights

I said before, we start with wild guess.  Actually we start with some tiny numbers but the numbers are random.

We need one set of weights linking each pixel to each hidden layer (25 x 400)* and another set linking each hidden layer to each digit (10 x 25)*.

The asterisk means that a bias factor might be added in raising one or the other number by 1.  To keep things simple, I am not going to discuss the bias factor. I’ll just flag where it comes up.  Be careful with them though because I am tired and they might be wrong.

Step 4: Calculate the first wildly inaccurate prediction of the digits

Use the input data and the weights to calculate initial values for the hidden layer.

Our input data of training examples and features (5000 examples by 400 pixels) is crossed with the appropriate initial random weights (25 x 400) to get a new matrix of hidden layer values.  Each training example will have 25 new values (5000 x 25)*.

Then repeat again from the hidden layer to the layer of digits or output layer making another matrix of 5000 x 10.

In the very last step, the calculated value is converted into a probability with the well know sigmoid function.  It would be familiar if you saw it.  I’ll try to patch it in.

The values calculated at the hidden layer are converted into these probability-type values and they are used for the next step and the final answer is converted in the same way.

Now we have a probability type figure for each of 10 digits for each training example (5000 x 10)*.

Step 5: Find out how well we are doing

In this step, we first convert the correct answer (which was a 1, or 5, or 7 or whatever the digit was) into 1’s and 0’s – so we have another matrix (5000 x10).

We compare this with the one we calculated in Step 4 using simple subtraction and make yet another matrix (5000 x 10).

Step 6:  The backward pass begins

So far so good.  All pretty commonsensical. The fun starts when we have to find a way to adjust those guessed weights that we used at the start.

Staying at a commonsensical level, we will take error that we have in that big 5000 x 10 matrix calculated in Step 5 and partition it up so we can ‘track’ the error back to training examples and hidden layers and then from hidden layers to pixels. And this is what the computing scientists do.  T

hey take one training example at a time (one of the 5000 rows), pick out the error for digit 1, and break it up.  And do it again for digit 2 up to digit 0 (which we input as 10).

Step 7: Working with one training example at a time

It might seem odd to work with one training example at a time, and I suspect that is just a convenience for noobes, but stick with the program.  If you don’t, life gets so complicated, you will feel like giving up.

So take example one, which is row 1; and do the stuff. And repeat for row 1, and so on until you are done.

In computing this is done with a loop: for 1: m where m is the number of training examples or rows (5000 in our case).  The machine is happy doing the same thing 5000 times.

So we do everything we did before this step but we start by extracting our row of features:  our X or training data how has 1 row and 400 features (1 x 400)*.

And we still have one label, or correct answer but remember we will turn that into a row of 1’s and 0’s.  So if the right answer is 5, the row will be 0000100000 (1 x10).

And we can recalculate our error, or uplift the right row from matrix of observed values that we calculated in Step 6.  The errors at the ‘output_layer’ will be a row of ten numbers (1 x 10).  They can be positive or negative and the number bit will be less than 1.

Step 8: Now we have to figure out the error in the hidden layer

So we know our starting point of pixels (those never get changed), the correct label (never gets changed) and the error that we calculated for this particular forward pass or iteration.  After we adjust the weights and make another forward pass, our errors change of course and hopefully get smaller.

We now want to work on the hidden layer, which of course is hidden. Actually it doesn’t exist.  It is a mathematical convenience to set up this temporary “tab”.  Nonetheless, we want to partition the errors we saw at the output layer back to the units in the hidden layer (25 in our case)*.

Just like we had at the output layer, where we had one row of errors (1 x 10), we now want a row or column of errors for the hidden layer (1 x25  or 25 x 1)*.

We work out this error by taking the weights we used in the forward pass and multiplying by the observed error and weighting again by another probabilistic value.  This wasn’t explained all that well. I’ve seen other explanations and it makes intuitive sense.  I suspect our version is something to do with computing.

So here goes.  To take the error for hidden layer unit 1, we take the ten weights that we had linking that hidden unit to each digit.  Or we can take the matrix of weights (10 x 25)* and match them against the row of observed errors (1 x 10).  To do this with matrix algebra, then we turn the first matrix on its side (25 x 10) and the second on its side (10 x 1) and we the computer will not only multiply, it will add up as well giving us one column of errors (1 x25).*   Actually we must weight each of these by the probabilistic type function that we called sigmoidGradient.

We put into sigmoidGradient a row for the training example that was calculated earlier on as the original data times the weights between the pixels and the hidden layer ((5000 x 400*)  times  (25 x 400*))– the latter is tipped on its side to perform matrix algebra and produce a matrix of 25* values for each training example (5000 x 25*).

Picking up the column of data that we calculated one paragraph up, we now have two columns (25* x1) which we multiple (in matrix algebra .* so we can do multiplication of columns like we do in Excel).

Now we have a column of errors for the hidden layer for this one particular training example (25* x1).  (Our errors at the output layer for this person was in a row (1 x 10).

Step 9: Figure out how much to adjust the weights

Now we know how much error is in the output layer and the hidden layer, we can work on adjusting the weights.

Remember we have two sets of weights.  Between the output and hidden layer we had (10 x 25*) and between the input layer and the hidden layer, we had (25 x 400*). We deal with each set of weights separately.

Taking the smaller one first (for no particular reason but that we start somewhere), we weight the values of the hidden layer with the amount of error in the output layer.  Disoriented?  I was.  Let’s look again what we did before.  Before we used the errors in the output layer to weight the weights between output and hidden layer and we weighted that with a probabilistic version of input data times the weights coming between input and hidden layers.  That seemingly complicated calculation produced a set of errors – one for each hidden layer – just for this training example because we still working with just one row of data (see Step 8).

Now we are doing something similar but not the same at all. We take the same differences from the output layer (1 x10) and use them to weight the values of the hidden layer that we calculated on the forward pass (1×25*).  This produces (and this is important) a matrix that will have the same proportions as the weights between the hidden and output layer.  So if we have 10 output possibilities (as we do) and 25* units in the hidden layer, then at this stage we are calculating a 10 x 25* matrix.

So for each training example (original row), we have 250 little error scores, one for each combination of output and hidden units (in this case 10×25*).

Eventually we want to find the average of these little errors over all our training examples (all 5000), so we whisk this data out of the for loop into another matrix.  As good programmers, we set this up before and filled it up with zeros (before the for loop started).  As we loop over training examples, we just add in the numbers and we get a total of errors over all training examples (5000) for each of the combos of hidden unit and output unit (10 x25*).

And doing it again

We have a set of errors now for the connections between hidden and output layers. We need to do this again for the connections between the input layer and the hidden layer.

We already have the errors for the hidden layer (25* x1) (see Step 8).  We use these to weight the input values (or maybe we should think of that the other way round – we use the input values to weight the differences).

We take the errors for the hidden layer (25 x1) and multiple by the row of original data ( 1 x 400*) and we will get a matrix of (25 x 400*) – just like our table of weights!  You might notice I did not put an asterisk on the 25 x1 matrix.  This is deliberate.  At this point, we take out the bias factor that we put in before.

We do the same trick of storing the matrix of error codes (25 x 400*) in a blank matrix that we set up earlier and then adding the scores for the next training example, and then the next as we loop through all 5000.

Step 10: Moving on

Now we have got what we want: two matrices, exactly the same size as the matrices for the weights ( 25 x 400* and 10 x 25*).  Inside these matrices are the errors added up over all training examples (5000).

To get the average, we just have to divide by the number of training examples (5000 in this case). In matrix algebra we just say – see that matrix? Divide every cell by m (the number of training examples). Done.

These matrices – one 25 x 400* and the other 10 x 25* are then used to calculate new tables of weights.  And we rinse and repeat.

  1. Forward pass : make a new set of predictions
  2. Back propagation as I described above.
  3. Get two matrices of errors: yay!
  4. Recalculate weights.
  5. Stop when we have done enough.

The next questions are how are the weights recalculated and how do we know if we have done enough?

Recalculating weights

The code for the back propagation algorithm is contained within a function that has two purposes:

  • To calculate the cost of a set of weights (average error in predictions if you like)
  • And the matrices that we calculated to change the weights (also called gradients).

The program works in this order

  • Some random weights
  • Set up the step-size for learning (little or big guesses up or down) and number of iterations (forward/back ward passes)
  • Call a specialized function for ‘advanced optimization’ – we could write a kluxy one but this is the one we are using
  • The advanced optimizer calls our function.
  • And then performs its own magic to update the weights.
  • We get called again, do our thing, rinse and repeat.

How do we know we have done enough?

Mainly the program will stop at the number of iterations we have set.  Then it works out the error rate at that point – how many digits are we getting right and how many not.

Oddly, we don’t want 100% because that would probably just mean we are picking up something quirky about our data.  Mine eventually ran at around 98% meaning there is still human work and management of error to do if we are machine reading postal codes.  At least that is what I am assuming.

 

There you have it.  The outline of the back propagation.  I haven’t taken into account the bias factor but I have stressed the size of the matrices all the way through, because if there is one thing I have learned, that’s how the computing guys make sure they aren’t getting muddled up.  So we should too.

So now I will go through and add an * where the bias factor would come into play.

Hope this helps.  I hope it helps me when I try to do this again.  Good luck!

The regularization parameter

Ah, nearly forgot – the regularization parameter.  Those values – those little bits of error in the two matrices that are the same size as the weights – (25×400*) and (10×25*)?

Each cell in the matrix except for the first column in each which represents the bias factor, must be adjusted slightly by a regularization parameter before we are done and hand the matrices over to the bigger program

The formula is pretty simple.  It is just the theta value for that cell times by the learning rate (set in the main program) and divided by the number of training cases.  Each of the two matrices is adjusted separately.  A relatively trivial bit of arithmetic.

CHECK OUT SIMILAR POSTS

2 Comments

Need to practice first order logic?

Published November 5, 2011 by Jo Jordan

I found this first order logic exercise on Wolfram.

#1 Download Wolfram’s CDF player

-1 The download on their site did not work for me, so I downloaded here from Softpedia.

-2 You will download an .exe file. When it arrives on your personal computer, simply click on the link and it will install as a Program.  It takes a little time to install.  Big beastie to allow you to view interactive documents.

#2 Now read whatever you want on Wolfram’s Demonstrations

-1 Find the demonstration that interests you.  In this case, try this demo for practicing first order logic, also known as predicate calculus..

-2 Click on “Download Demonstration as CDF” at top right and it should open.  If not, try firing up Wolfram first from your Start/Programs.

#3 Practice your first order logic

-1 Choose how many objects to play with,

-2 Start at equation number 1.

-3 Move objects around to change the truth value from true to false and v.v

 

It won’t do your homework for you but it might take the edge off the confusion.

CHECK OUT SIMILAR PPOST

Leave a Comment

Check your propositional logic with a truth table generator

Published November 5, 2011 by Jo Jordan

The Seventh Day Adventist University website has a truth table generator for checking propositional logic.  Instructions for inputting propositional logic symbols are on its page.

My host’s wordpress is borked: so here is the link

http://turner.faculty.swau.edu/mathematics/materialslibrary/truth/

#1 Check you understand each part of the assertion

Basically, you can check that you are using the basic truth table for simple assertions like (A and B).

#2 Generate a truth table for multiple assertions

And you can combine simple assertions to generate a truth table

Caveat

I am not an expert in this, but I am assuming that if a bundle of assertions are always true,whatever the starting values that we put into the bundle, then the bundle resolves to true.

Correspondingly, if the assertions come out as false, no matter what the starting values are, the bundle resolves to be false.

And if the bundle contains a mix of true and false, we are left uncertain what will happen.

Any thoughts?

CHECK OUT SIMILAR POSTS

Leave a Comment

A general algorithm for implementing a neural network

Published November 3, 2011 by Jo Jordan

What is a neural network?

A neural network takes a set of binary (0/1) signals, groups them into a smaller set of hidden units, which are used to work out the probability of something happening.

An example of a neural network?

The example used by Andrew Ng in the Stanford course

  • Converts the image of a handwritten number into 20×20 = 400 pixels, i.e. a row of 400 1’s or 0’s
  • The backward propagator works out how to group the 400 columns of pixels into 25 units (which are ‘hidden’ because the end user doesn’t need to know about them)
  • And then the backward propagator does its magic again to work out weights to match combinations of 25 units onto the ten possibilities of a digit (0-9).

Forward propgation

The forward propagator takes a handwritten number, or rather the row of 400 1’s and 0’s representing the 20×20 pixels for a number, and runs the calculation forwards.  400 1’s and 0’s are multiplied by the weights matching a column to the 25 hidden weights. And 25 new columns are generated.  Each image represented by a row,now has 25 numbers.

The process is repeated with the weights from the 25 columns to the 10 digits and each image now has a probability for each of the 10 digits.   The biggest probability wins!  We have taken a list of pixels and stated what a human thought they were writing down!

Training accuracy

And of course, if we knew what the digit really was, as we do in a ‘training set’ of data, then we can compare the real number with the one that the machine worked out from the set of pixels.  The program run for Stanford students is 97.5% accurate.

Waiting for backward propagation

The real interest is in the backward propagator, of course.  Just how do they work out that there should be 25 units in the hidden layer and how do they work out the weights between the hidden layer and the output layer.

Machine learning vs psychology

In psychology, we have traditionally found the hidden layer with factor analysis or principal components analysis.  We take your scores an intelligence test, for example.  That is simply a row of 1’s and 0’s!  We factor analyse the 1’s and 0’s (for you and hundreds of other people) and arrive at a hidden layer.  And from there we predict an outer layer.

We usually tighten up the inputs to reflect the hidden layer as closely as possible – that is we improve our tests so that 30/50 is meaningful.  And our outer layer is often continuous – that is we predict a range of outcomes which we later carve up into classes.  We might predict your A level exam results by % and then break them into A, B, C, etc.

So it is with great interest that I await the backward propagation.  I am also more interested in unsupervised machine learning which I suspect reflects real world conditions of shifting sands a lot more.

CHECK OUT SIMILAR POSTS

Leave a Comment

Functional dependence in databases: plain language & how-to

Published October 30, 2011 by Jo Jordan

Computer scientists speak a language of their own with long ‘noun phrases’ and complex sentences which are often grammatically incorrect or very difficult to parse.

This post here is a short description of FUNCTIONAL DEPENDENCE IN DATA BASES.  This is a common sense view and an AMATEURISH view – so read it to take off the edge off the unintelligibility of explanations around the web but remember that when you want to solve very hard problems, this explanation will probably be not be sufficient or even accurate.

#1 What is a database?

A database is a set of tables.  A table is just a set of rows and columns like we have in Excel.  A database has lots of tables like the sheets in Excel.

And just as we can in Excel, we can tell the program to toddle off to another table to pick up a value, bring it back and put it in another table.  We call that a Look Up.

#2 Looking up something by tracking from table to table

In a complicated set of tables, the value we want might be in Table 6, for example.  We might also have some information that doesn’t allow us to look up what we want in Table 6, but we can use the information we have to look up something in Table 4 and something else in Table 3 and use those two facts to look up what we need in Table 5 and then go to Table 6 to finish the job.

To take a practical example, if you want to look up someone’s telephone number, you need to know their family name and the town where they live.  If their family name is very common, you might need to know their first name and street name as well, but let’s stick to a simple example.

So if we know our friend lives in Timbuktu, we look up the volume number of the directory for Timbuktu, then we go to the Timbuktu directory/table and we use our friend’s name to lookup their telephone number.

Alternatively, the list might have been laid out in one table and we look in the first two columns for Timbuktu AND our friend’s name.  When we have found both together, the correct telephone number will be in the next column.

#3 What is functional dependence?

In plain language, functional dependence just describes how we look up information.

Because we need our friend’s town to look up their telephone number, then telephone number is functionally dependent on town and the computer scientists write that down as Town àTelephone Number.

Equally ,as we need a name to look up a telephone number, telephone number is functionally dependent on name and that is written as Name à Telephone Number.

What’s more, as we need town and name to look up a telephone number, Telephone Number is functionally dependent on Town AND Name. Computer Scientists write that as Town, Name à Telephone Number.

#4 So why do we care about functional dependence?

Every day we ask questions about functional independence without being conscious that we are using this exalted concept!

We use functional dependence every day

Whenever we look up something like a telephone number, we are asking what information we need to know to look up the number.

When you Googled “functional dependence” and landed up here, you used a look up – or rather you trusted Google to know what look-ups to use!

Tough search problems require us to track from one lookup table to another

At work, we might also say, if I have information A and information B, can I find out Z and how do I find out.

How can I step from table to table to get the information that I seek?

When we design a database or set of spreadsheets, we want to do the least work possible!

When we design a database, or set of Excel spreadsheets, we also want to make as few tables as possible!

We want to make sure we only ever have to type a piece of information into only one table once!

We want to make sure that data that hardly ever changes or we hardly ever look at is still accessible but in tables that we can put out of the way.

That’s it.  That’s the what and why of functional dependence.  So let’s turn to the how and specifically the ‘how’ for students.

#5 So how do you work out functional dependence questions?

With the Stanford experiment in online classes going on, and other computer science students doing homework, you might really want to know how do I do these ***** problems?

This is my way – it is not the official way but it works for me.

When I have a table (R) with columns (A, B, C, D etc), I think of the columns as all the columns in a set of spreadsheets.

Then I turn the functional dependencies (FD) (written AàB) into tables.  AàB is a table with two columns, A and B. In plain language, I use column A to look up column B.

Problem 1

Then, when I am asked, does ABCàD work in that relation and set of FD’s, all I do is ask myself, given the set of tables, if I already  know ABC, can I find the value of D? I have to be careful and methodical, but hey it works.

Problem 2

Then when I am asked if BC, say, is a key, I write down BC and I write down the columns that are left – say a, d.  Then I ask if I can look up a and d with B and C.  If I can, then BC is a key. If not, BC is not a key.

Problem 3

When I am asked if two sets of FD are the same, then all I am being asked is whether a set of tables allows me to look up the same information.  This is more tricky and I found it easiest to draw a matrix with a column for each column (A, B, C, D, etc) and a row for each of those columns.  I scratch out the diagonal (A=A) and see if knowing A (row), I can look up B, C, D etc.  This only works for very simple problems though.

So, this is an amateur’s take on functional dependence. Use it if it works for you and not if it doesn’t.  And remember it is an amateur’s version.  Once problems become more complicated, all that maths is probably useful shorthand and my account is probably concealing some misunderstanding or other!

Good luck.

CHECK OUT SIMILAR POSTS

Leave a Comment

12 steps to running gradient descent in Octave

Published October 16, 2011 by Jo Jordan

This post provides a birds’ eye view of how to calculate linear regression using the numerical programming used by machine-learning people.  It is, of course, easier to do the linear regression in a statistics program but it is good to know and the overall structure probably provide a foundation for other machine-learning programs.

The algorithm works with Octave which is like a free version of MatLab.

I’ve also only given the birds’eye view because the code is part of the Machine Learning course at Stanford and writing it is part of the homework – if we release it, students’ won’t have to write it themselves and they won’t learn how anything.

Example of linear regression

Imagine you want to buy a second hand car and you collect information on prices for a particularly model with the age and mileage of the vehicle.

The following can compute an equation to predict the price of the car from either the age of the vehicle or the mileage.  Using both age and mileage is a multivariate problem which has different algorithms.

#1 Prepare data

~1 Normally, we would input the data into a table in Excel with the first column being age (or mileage) of the vehicle and the second column being price.

~2 Then we would save the file as a csv (comma separated values) text file which we will call for now mydata.txt

#2 Load the data into Octave

~1 Start Octave from your list of Start/Programs

~2 Tell Octave where your data is stored.  For example, cd ‘c:usersmedata’

~3 Confirm you are in the correct directory by typing ‘pwd’

~4 Read in the data using these three commands

data = csvread(‘mydata.txt’);  % reads the data file

X= data(:,1); % reads all the rows of the first column of the data (age in our example) into matrix X

y = data(:, 2); % reads all the rows of the second column of the data (prices in our example) into vector y

m=length(y); % counts the number of training examples, or rows (age, price pairs in our example)

#3 Visualize the data using plot

~1 Find out what the data looks like (inspect the data) by  using the plot function

~2 This was part of the homework so let’s say that the commands for a plot were put in separate file which is called with a simple command plot(X, y)

~3 Calls to a function can be made from the command line within Octave or another function.

#4 Pick out some data to act as a test you have everything correct

~1 Look at the graph and pick two values of X (age of the vehicle in our example)

~2 Estimate by sight the predicted value of Y (the price of the vehicle in our example)

Hang on to these. You will need them at the end!

 #5 Set the ‘settings’ for the gradient descent

~1 Set the number of iterations and type these in at the command line or put them in another function.  For example, iterations=1500

~2 Set the learning rate.  For example, alpha = 0.01

~3 Set up the matrix of theta values (that is, the y intercept and the gradient of the graph. If price= a +b(age), the two theta values are a and b).  Type in theta= [0;0]. That sets the initial values of both parameters as 0.  A line like this predicts every price as 0 no matter the age of the vehicle.  But it is just our starting point!

#6 Calculate the initial cost function

~1 Calculate the errors in prediction if we treat theta as [0;0], or that is if we treat price as a straight line and always 0.  The formula is in essence the sum of the square of the prediction errors divided by twice the number of cases.  I can’t derive this and I am not going to type it in because finding the right formula was probably part of the homework.

~2 Put the code into a function costCompute (X, y, theta) and save as a text file with extension .m (costCompute.m)

~3 This function is called repeatedly later because every time we improve our guess of the parameters (theta or a & b in the regression line), then our prediction errors will decrease.  Basically, we will stop trying to improve our parameters when we can’t reduce our prediction errors any further.

#7 Repeatedly calculate new parameters

~1 The goal now is to iteratively improve our guesses of the parameters (theta – i.e., a & b in the regression line). The machine learning specialists call this ‘learning’ the parameters.  So, we are starting with [0,0] and we will slowly improve them.

~2  The formulas for changing the parametesr amount to calculating a minute change and taking it away from the last value.

~3 There is a different formula for the two parameters (a & b) largely because they start off as differently – as a  constant, a, and as bx. (It’s maths…)

~4 The constant, a, decreases by the alpha (set as low as 0.01 – see above) times the average error in prediction.  Again the formula is part of the homework so I won’t write it down here.

~5 The slope, b, decreases by the alpha times the average error in the prediction itself multiplied by the original x value.  I vaguely intuit this.  Again there is a formula.

~6  A new cost is calculated with the two new parameters and of course, the cost (think of it as the average prediction error) should have gone down.

#8 Iterate lots!

~1 The iteration in this example was set at 1500!

~2 I don’t see how else the program ended. Presumably it could also be coded to end when the improvement in the cost (improvement in prediction errors) falls below an pre-stated, acceptable level.

#9 Print out a linear fit

~1 Overlay a straight line graph on the original plot of the data

~2 Use Octave’s ‘hold on’ command to keep the old plot as the base

~3 To draw our prediction line, either calculate predicted values or simply calculate the predicted values within the plot command.  Plot (X, X*theta, ‘-‘)

#10 Check the answer is reasonable

~1 Find the test data you set up in step 4.

~2 Calculate predicted values using the parameters we have calculated for the two test levels of X (i.e., what prices do we predict for our two ages of vehicle?).

~3 Do they make sense?  My primary school maths teacher told me ALWAYS to write the answer in plain English!

#11 Visualize theta values in a 3D plot

~1 Use Octave’s surf command to visualize the cost (average prediction errors) of each combination of theta values (a & b).

~2 The 3d plot is bowl-shaped and the best combination of (a & b) is at the putative point where the bowl would balance (my rough understanding).

#12 Visualize the contour plot

~1 Use Octave’s contour command to visualize the theta-theta graph (all those a’s plotted against all those b’s).

~2 Our final version of a and b should sit in the inner circle as if it was the highest point on the contour map of a mountain.

This is my record of the 12 steps in using gradient descent to do linear regression for a problem such as predicting of the price of a car from its age.  We need a large data set of recent data and we repeatedly put in values for the y intercept (value of a car when it is brand new) and the slope (the rate the value decreases). (Yeah, I know… a straight line is not necessarily the best model unless we start after the car is a year old).

The program nippily calculates how bad the model is and when it stops getting better, it stops and delivers the parameters for the line.  We can check the parameters graphically (because like all good data scientists we inspected our data at the beginning).

We can also use the contour and surf functions of Octave to plot the improvements in our estimations so that we can see what the program actually did.

I’ve written this to make sure I can do it again. I hope it is useful but the code itself is embargoed because otherwise future students of Stanford will not have to do any work and will not learn anything!

CHECK OUT SIMILAR POSTS

6 Comments

Install Relational Algebra Interpreter on your Windows machine in less than 30 minutes

Published October 13, 2011 by Jo Jordan

This is a quick blog post on how to install and use the Relational Algebra Interpreter on a Windows machine.

#1 What is the Relational Algebra Interpreter?

You only need the Relational Algebra Interpreter if you have a database that you set up through SQLite or MySQL or other database software (not Microsoft Access) and you want a shortcut to writing the SQL commands like SELECT and PROJECT.

The Relational Algebra Interpreter was written Jun Yang, now of Duke Uni.  It is used by many universities, including Stanford, to teach database programming.

#2  Install the Relational Algebra Interpreter?

This notes describe my installation.  I am not an expert and I am jotting down what I did mainly so that I can do it again another day.  If they help you, good; if not, sorry.

#2.1 Do you have Java installed on your machine. I am using Windows 7 on a relatively new machine and I have a Java JRE (runtime environment) installed but not a JDK (development kit).  I didn’t want to rush a notoriously convoluted Java install and make a mess of a new machine, so I fired up my old Windows XP where there is a JDK already installed.

#2.2 Decide where to put your RA interpreter.

The Interpreter comes with everything you need to run on SQLITE databases ( I am not sure on what else) and as I am only using the RA interpreter for a few weeks, I didn’t want to change my PATH statement – so I made a working folder, e.g. C:/A_RA_demo.

I went to Dr Yang’s page and downloaded the RA Interpreter and unzipped it.  I also transferred over from my other machine the test SQLITE3 database that I made earlier (see another post).

#3 Use the Relational Algebra Interpreter

#3.1  The RA Interpreter file runs from your command prompt (Go to Start; type cmd in the box and hit enter; change directory to work in your working directory, e.g., cd c:/A_RA-demo.

#3.2  The RA Interpreter comes with a  sample.db and a sample.properties file.  So to prove everything works, type into your command line, “java –jar ra.jar” and observe the changes on your screen.

#3.3  See what is in the sample.db by typing at the ra> prompt “list;”.

#3.4  Pick any of the “relations” (tables in plain English) and type at the ra> prompt “relationname;”.

#3.5 Type at the ra> prompt “quit;”

#4 Use the Relational Algebra with your own database

#4.1  To use the Relational Algebra with your own database, you must make a corresponding .properties file.

#4.2  Copy the sample.properties file and save it as yourdatabasename.properties.

#4.3  Find the right command line to edit. Most of the file is commentary.

#4.4  I was using a database made in SQLITE3 so I picked the SQLITE command.  You don’t have to add a 3.  You must change the sample.db to the yourdatabasename.extension.  I got held up here for a while because my database was a just a file without an extension.  When I typed in the database-name-only, it worked.

#4.5  Go back to the command line and make sure you are working in the working directory.  If not, look at step #2.2

#4.6 On the command line, type “java –jar ra.jar yourdatabasename.properties”

#4.7 Confirm you have read your database by typing at the >ra prompt “list;”

#4.8  All working?  So quit for now by typing at the >ra prompt “quit;”

#5 Use the Relational Algebra Interpreter with query commands in a file.

#5.1  Put the relational algebra interpreter commands in a text file and save in the working directory (e.g., query1.txt).  [You could test “list;” for now.]

#5.2  Go back to the command prompt and confirm you are in your working directory. Type “java –jar ra.jar yourdatabasename.properties –i query1.txt”

#5.3  You will get an answer, or more likely an error message.  Debug your query, resave query1.txt and rerun the java line.  Conveniently, recall the java line with the up key and enter.

Done!  Now all you have to do is learn the Relational Algebra syntax which you can also find on Professor Yang’s site.  It is a little mind blowing and I found tracking all the brackets quite hard but you get the hang of it with practice.

Make sure you start with a little database so you can check your queries by hand.  And search the Stanford website for class notes to help you on your way.

CHECK OUT SIMILAR POSTS

2 Comments