Statistics For Programmers IV: Ordinary Least Squares

This entry is part of a larger series of entries about statistics and an explanation on how to do basic statistics. You can see the first entry here. Again I will say that I am not an expert statistician, so feel free to pick apart this article and help bring it closer to correctness.

In my last post about statistics, I spoke about how to compare two different averages to see if they are statistically different or not. It was a good introduction to using statistics for hypothesis testing since it was fairly simple yet went over some of the fundamental ideas of statistics - that disturbances could result in us coming to wrong conclusions, and we must do our best to try and detect whether or not differences in results come from the disturbances or from what we believe it to be.

This time we'll address something a bit more complex. In many cases we want to analyze a causal relationship between two variables - that is, variation in one variable is causing variation in another variable.

Note that this post is a bit more theory-oriented, the next one will apply the theory to something programming-related.

In econometrics (something that I've been studying a fair bit over the last year or so), a tool used for this type of analysis is the ordinary least squares (OLS) method. This method assumes that the relationship between the variables can be explained by an equation that looks like this:

y = β0 + β1x + ε

Here, y is the dependent variable, x is the independent variable, β₁ is the effect of a one unit change of x on y, β₀ is the intercept term (basically what y is predicted to be when x is zero), and ε is a random error term. This example only uses a single independent variable, but you can have many more. You can also have functions of independent variables in there, so you could put x² if you like. For OLS, the restriction is that the equation is linear in the β terms (called the parameters) - that is, OLS is a linear estimator.

Once we have formulated our model, we can use data to estimate what the β coefficients are. There are plenty of statistical packages out there that will do OLS on a dataset, R is one that is open-source and available for Ubuntu. It's not as user-friendly as other ones that I've used, but it is easier to get your hands on it.

This paragraph talks about how the estimates are computed, feel free to skip it if you don't care. Otherwise if you want to be hardcore and calculate out the coefficients yourself, the math formula is:

est(β) = (X'X)-1X'y

Here est(β) is the estimator of β, which is a column vector of the parameters in your equation (in the example above we had 2 parameters, so it would be a 2x1 vector). The X is a matrix of your independent variables, for the intercept term you just set one of the columns of your matrix to all 1s. Each independent variable occupies one column of your matrix, so the matrix is nxk for n observations and k independent variables (including an intercept term if you have one). X' is the transpose of X.

So now you know how to get take a bunch of data and infer a causal relationship between them, right? Unfortunately it is not entirely that simple. OLS comes with a whole pile of assumptions in order for you to properly analyze the results that come out:

• The expected value of ε conditional on X is zero. That means that if you hold your independent variables fixed and just keep taking observations, the average error will be zero. It is common for this assumption to be violated, and when it is you usually end up with biased results. It is important to understand how it can be violated and what to do when it is. I'll talk about this more in a later post.
• Random sampling - the different observations of a specific variable are not correlated with one another. This can be violated for dynamic systems where the observations are taken over time.
• No perfect multicollinearity - this basically means that no independent variable is a perfect linear combination of other independent variables (for example if x₅ = 2x₂ - 3.14x₇ you would have a perfect linear combination). You're pretty hosed if this is the case, and you'll probably need to end up removing a variable.
• Homoskedasticity - given any value of X, the spread of your error term is constant. When this is violated you can still use OLS, it's just there will be better estimators.
• No autocorrelation - none of the error terms are correlated with the other error terms. With autocorrelation you can still use OLS, but like heteroskedasticity there will be better estimators.
• Normal errors - your errors must be distributed normally with a constant variance. Note that if this is the case then you will have homooskedasticity and no autocorrelation. If this assumption is violated, then you cannot use the hypothesis tests in the same way.

Assuming all the assumptions are satisfied, we can do hypothesis testing on our estimates of the parameters. Fortunately the hypothesis testing here is even easier, since statistical packages usually spit out the p-value for each parameter. What that p-value measures is the probability that if the actual value of the coefficient were zero, then we would have p-value probability of getting the sample that we did. So if the p-value is very small, you can guess that the actual value for the parameter is not zero.

Anyway like I said before, this post was a bit dry and theoretical. I'll get to something more practical next time.

« Statistics For Programmers III: Differences of Means | Statistics For Programmers V: Performance Analysis »

Why Common Lisp Bothers Me

I've been thinking about a newer project recently (yes, it's that time again) and I was thinking it might be cool to try to do the project using Common Lisp, since I don't know the language all that well and I'd like to try and get to know it better. I've used it a bit in the interpreter, and I used Scheme a bit when I was in university for the principles of programming languages and AI classes, and I find that while the syntax is weird at first, the languages have that neat homoiconicity property that seems to boggle the mind the more I think about it.

What seems to be bothering me about these is not the languages themselves, but how they interact with the real world. The problem started when I wanted to create an executable. You know, those things that you can give to other people that they can actually use to run your program. It took me a while to find anything, and eventually I had to run over to #lisp to find out. Their IRC bot pointed me to a page (apparently lots of newbies to Lisp ask this same question) which told me that Lisp doesn't really use executables. Instead it uses an image (like Smalltalk) which you can dump to an "executable". Except that it isn't really a compiled executable, but a saved state of your REPL session - kinda like if you were working in IRB and decided to hibernate it and when you ran your "program" it would just fire you back into the IRB session with the option of executing a function on its way in.

This brings up another small problem that I had a while back when I was trying to do my code mutation stuff, however a problem I had back then was with finding out how to do things using the standard libraries. I guess I've been spoiled by newer languages like Ruby and Python where the standard libraries seem to come with a large amount of basic functions for string/array (well they were lists, it was Lisp after all) manipulation and it is really easy to figure out how to do that kind of stuff, but when I tried to do some of the same stuff using CL I think I spent more time hunting down docs than I did doing actual coding (in hindsight I probably should have just wrote the functions myself, probably would have saved time that way).

So while I'm sure Lisp is a great language to use for academic stuff or maybe even for a server-side app, I don't think I want to use it for a project that I might want to give to people someday. It seems like the language suffers horribly from neglect, and the people who learn it love it so much that they seem to ignore certain practical matters like this.

Anyway that's the end of my rant. Flame away.

UPDATE: A few Lisp people commented on the post on Hacker News, saying my complaints sum up to things like: "Because I'm used to something else." I'm sorry, but those people have completely missed the point of my argument. It has nothing to do with what I'm used to, it has something to do with what anybody who is not a geek is used to. I want to distribute my application, it either must be executable, or work in runtime platform. The only runtime platforms that are feasible for large scale deployment are either Java-based or browser-based. Otherwise your app is going nowhere, as people won't want to install a whole bunch of crap just to get your app working. That's the point of the argument, it has nothing to do with what I'm used to.
Unfortunately I've probably just wasted the last 5 minutes of my time, because programmers tend to completely blank on reason and logic when it comes to their favourite programming language.

If University were like Real Life

If things had been the same in my university computer science program as software development is in real life, I think the following would be true:

• Assignment Outlines - that paper/PDF you get for your assignment would be horribly vague. The only way to get a clear idea of what the professor wants is to go and ask. Unfortunately when you do that, the answers are also fairly vague, so in the end you'll have to try and guess what they want. (In retrospect, this one actually does happen in university sometimes. I'm leaving it here since in real life this is the norm, not the exception.)
• Assignment Requirements - at some point before the assignment is due, the professor will change what the assignment is about completely. You can either adapt what you have, or start it again from the beginning (although most students procrastinate so it's likely that they won't have anything yet).
• Assignment Review - after showing the professor your assignment, they'll change their mind on what they want. Unlike the previous point, this will only occur after you've shown them the assignment, which heavily penalizes procrastinators.
• Grading - there won't really be any grades in the same sense of the word. Some assignments will have some crazy weighting system, so if you get 90% if the answers right you'll still fail, but your friend who got 20% of them gets a good grade since s/he knew exactly which ones to do. Unfortunately you probably won't figure out this weighting scheme.
  Another possibility is that the grading system is either 0 or 100. The professor doesn't care if you've got the features 90% built, they want to see everything that they asked for.
  Other assignments won't have a grade at all, instead the professor will just accept what you give. 6 months down the road if the assignment was poorly done, you'll be kicked out of university; if it was well done nothing will happen. (An explanation of this one: many times in the real world you're asked to make a judgment call, and the client will just accept your conclusion. After all, you're supposed to be the expert. However after a certain amount of time, evidence might show whether that was a poor decision or not.)
• Competition - your friend does a good job on the assignment and hands it in a week ahead of you. You fail the assignment, regardless of how good it is.
• Other people's work - instead of you starting the assignment from scratch, you'll get the version from last year's class and be told to change it. (it's possible that some professors already do this, which is a good thing!)
• New technologies - you'll start new courses that need you to use a specific programming language or technology that you may or may not have done before. If you don't learn this technology within a few weeks, you fail the course. (there are a few courses like this, especially if you go to a school that teaches Java in first year and then drops C on you at a higher level - this is a good thing!)

There's probably many more things that I could add to this list, if you think of something feel free to add it in the comments!

A little side note: I am not suggesting that computer science programs change in order to create better programmers. A computer science program is not about teaching people how to be better programmers, it is about teaching people computer science. While I do think computer science is a good discipline to study if you want to be a programmer, the actual becoming a good programmer part is your responsibility.

Hello world in 63 bytes

I recently discovered this guide here to making teeny programs in Linux. I thought it was pretty neat, so I've decided to post their Hello world application here:

BITS 32
  org 0x05430000

; ELF header stuff - this stuff is information about the executable that
; Linux uses to see how to execute it. It's stuff like what platform it's
; for, what type of executable it is (object code, executable, shared object),
; how long the program is, where the entry point is, etc.
ehdr:
  ; db means put a byte, dw means put a word (2 bytes)
  ; and dd means put a double-word (4 bytes)
  db 0x7F, "ELF"
  dd 1
  dd 0
  dd $$  ; I'm assuming that $$ means the start of the program
  dw 2
  dw 3
  dd _start
  dw _start - $$

; the program
_start:
  ; send the string to stdout
  ; system call for write is 4, file descriptor for stdout is 1
  ; so set eax = 4, ebx = 1, and ecx = string pointer, edx = string length
  inc   ebx
  add   eax, dword 4
  mov   ecx, msg
  mov   dl, 14
  int   0x80
  ; quit
  and   eax, 0x10020
  xchg  eax, ebx
  int   0x80
  
; Note: The original version doesn't put an ! at the end,
; which makes my version one byte longer. Oh well.
msg:    db 'Hello, world!', 10

You can assemble this using NASM:

sudo apt-get install nasm
nasm -f bin -o a.out helloworld.asm
chmod +x a.out

It's neat because by looking at how this stuff works, you begin to understand how the operating system manages loading programs under the hood. If you're interested in this type of thing, check it out!

I'm not sure how well it would work in Mac or Windows, since a lot of the short-ness of the program comes from exploiting the fact that Linux ignores a lot of the ELF header info, if the ELF header info is too short it will pad the rest with zeroes, and finally Linux clears all registers to zero when loading a program. I'm not sure if the Windows or BSD kernels would do the same, I guess the only way to find out is to try it!

On Challenges

Recently I've been working at redoing a challenge that I failed in the past. It is not really my choice since it is a class required for my degree, but I find I am enjoying being forced into the opportunity and hope that in the future I will force myself to re-attempt past failures in hopes that I can do them better.

The failure was a class called "Real Analysis", and while I didn't actually fail the class, I dropped it halfway through because it was an elective that was kicking my ass. It is a class where you analyze what the real numbers actually are, and how they can be used to build up the fundamental ideas of calculus. After getting my ass kicked on trying to do proofs about limits and continuity, I decided it might be better if I spent my time working on computer science classes instead of this class that, while interesting, had no real impact on what I wanted to do in life (which at the time was graduate and be a programmer).

This was a big regret of mine. At first I was happy to have free time again, but after a while I felt somewhat bad that there was something in a field that I was supposedly good at, yet couldn't do. So here and there I would re-tackle some of the problems in the textbook, with varying degrees of success. Some of them were easy this time around, others were still just as difficult. However now that I'm in a class where I basically have to relearn all this stuff, it isn't as bad as the first time around, and I find I'm actually enjoying it.

So what am I getting at here? Basically what happened to me was I was encountering new challenges. Sure, I've met challenges before in my academic and professional careers, but a lot of the time these challenges were programming or computer related challenges. This is stuff that I know reasonably well, and so the "challenges" aren't really all that challenging when you think about it, since I'm already thinking in the mindset required to solve these problems - although a good programming problem is one where thinking like a programmer isn't really the way to solve it. So if you're one of those programmers who loves to find challenges, why not start looking for challenges beyond your area(s) of expertise? One great thing that could happen is you begin to look at problems from a different perspective, which you can take back to your programming problems and maybe create something great. One thing that I've been thinking about now that I've been writing recipes in Ruby is real-time languages - basically ones where timing is important, even timing that makes your program run slower. A neat idea would be to add a "when" keyword that works like "if" but instead of just skipping when the condition is false, it hangs around until the condition is true. You could do this in Ruby (although you can't use "when", since it is already a Ruby keyword) by just making a function that takes a string of code and a block, evalling the code and sleeping until the evalled code evaluates to true.

Then again, if you want programming problems you can always check out Rosetta Code.

FOOP Presentation

I'll be giving a presentation next Friday, March 12, at Bishop's University (this might be come a semester-ly tradition) on something I'm calling FOOP, which stands for functional object-oriented programming. I'm hoping to talk about what it is and the advantages it has over both functional programming and object-oriented programming. Finally I'll be talking about how Scala accomplishes the combination of the two, and some of the neat features of Scala that I've discovered. I'm not really a Scala expert so I won't be going too much in detail, but hopefully it will be enough to get some people interested in looking into it a bit more.

If you are in the Sherbrooke, Quebec area, feel free to come and check it out! I'll be posting the slides on here afterward for those who can't make it.

Javascript Profiling With Firebug

I realized something today when trying to figure out how to profile my Javascript game jarm. If you go into Firebug and go to the Console tab, there is a button there that says "Profile". For some reason I've never actually noticed it was there! It works just like a regular profiler, click "Profile" and let it do its thing. When you're done click "Profile" again to stop and it will give you a report.