cbrad

Tuesday, June 29, 2010

QOTD

It's not that people cannot think mathematically. It's that they have enormous trouble doing it in a de-contextualized, abstract setting.

-- Keith Devlin

From In Math You Have to Remember, In Other Subjects You Can Think About It

Tuesday, June 22, 2010

In 2008 I commenced a coursework Masters in mathematics at the University of Queensland. I have downgraded this to a Graduate Diploma and should officially graduate in a few weeks.

My original goal for commencing postgraduate study was to improve my knowledge in programming languages and make the current research more accessible. Unfortunately the local universities teach very little (relevant) theoretical computing science, so I enrolled in mathematics with a focus on discrete mathematics, logic and abstract algebra. After the first year I discovered that there is no real future in programming language research here in Brisbane. I had achieved my goal in the context of the courses available and so switched my study to statistics as data analytics is both interesting and hopefully more viable locally.

To complete the Masters I need to do the equivalent of four courses in research. As I am enrolled in a coursework masters, I pay 2-3 times the standard undergraduate fees. The last course cost $2010. Therefore there is approximately $8000 in fees remaining.

I would enjoy the remaining Masters research component if could find the right supervisor and topic. However employment as a researcher now generally requires a PhD, not a Masters and while a PhD is longer, it also has no fees. So if the circumstances were right to do the Masters research it makes more sense to consider a PhD anyway.

The value proposition for completing the Masters is too low. I have fulfilled the requirements for a Graduate Diploma and so will finish with that.

Tuesday, May 25, 2010

Education is not linear

And we have sold ourselves into a fast food model of education and it's impoverishing our spirits and our energies as much as fast food is depleting our physical bodies.

-- Ken Robinson

Tuesday, May 11, 2010

Brief summary of iPhone Flickr apps

I use Flickr to store my photos. Now that I have an iPhone, I would like to use it as a mobile photo album as well as uploading photos taken from the camera. I don't want the added complexity of using iPhoto as a middleman, so I did a rough survey of iPhone Flickr apps.

Flickr 1.1.3 (free).

Loads photos fast. Caching works well if you have already viewed a photo.

View photos full screen and swipe to navigate.

No zoom.

If you take photos with the inbuilt Camera app and upload them sometime later, it doesn't set the map location and time taken to the original values.

Uploaded photo file size seems larger than with Mobile Fotos or syncing with iPhoto.

Darkslide 1.6.2 (free add-supported version)

Slow load times (even for previously viewed photos).

No swipe to nagivate photos.

No zoom.

Flickit 2.0 (free)

Only does uploading. The Pro app ($5.99) is a full client.

If you take photos with the inbuilt camera app and upload them sometime later, it doesn't set the map location and time taken to original values. Found an explanation from the developer.

Compresses photos significantly. I could only see small differences compared with the same photo uploaded via alternative means. Developer was helpful when I asked about this.

Mobile Fotos ($5.99)

Upload correctly sets the map location and time taken to the original values for photos taken with the inbuilt Camera app.

View photos full screen, swipe to navigate and pinch to zoom.

Slideshow.

Uploaded photos have washed out colours.

Can't select from your tags when uploading, need to type in each time.

Had one case where photos were shown as a blank screen. Cleared cache and problem was resolved.

Developer was responsive when I asked questions.

Reflections ($5.99) and Photo Wallet: Flickr ($3.99) both look interesting in their own right, but neither offer zoom. The developer of Photo Wallet answered my question via twitter quickly to.

In summary, none of the Apps I tried are ideal for uploading to Flickr. This leaves me importing into iPhoto and uploading via the standard web uploader.* Mobile Fotos has the best viewing experience and I would also use it for uploading if the colours and tagging were fixed.

* The iPhone saves GPS information into the EXIF data. I had to set the "Import EXIF location data" privacy setting for the Flickr map location to be set. The privacy implications of this need further investigation.

Tuesday, April 13, 2010

Math is not linear

Math is not linear on Prezi

Sunday, March 21, 2010

Embedding LaTeX in Blogger take 2

After further consideration on Embedding LaTeX in Blogger I have the following concerns in using jsLaTeX.

LaTeX images not rendered in RSS readers

Stability of all the components over (a long) time

jsMath improves on point 2, but looks way too hard to host on Blogger. So I am falling back to using images generated by the CodeCogs online equation editor hosted on Picasa, which is where Blogger uploads images. I put the LaTeX source in the img alt attribute.

Blogger resizing images
After adding a few equations through the standard Blogger mechanism, I noticed that they weren't as clear when previewing. The following two equations are the same image hosted on Picasa, but embedded with different src urls.

$\text{[math]}$

This is using the Blogger generated url in the image tag and has size 400 x 285 pixels.

$\text{[math]}$

This is using the Picasa generated url and has the original size of 415 x 296 pixels.

Notice how the first image is both smaller and blurry. It seems that Blogger is automatically resizing it. Unfortunately this means a little more work for each equation as it requires generating the link in Picasa and replacing the Blogger generated image tag.

Computing variance

Given a list of n numbers $x_1,x_2,...,x_n$ , the variance is defined as

$\frac{1}{n}\sum_{i=1}^n{\left(x_i - \bar{x}\right)^2}\quad\quad\quad\text{(1)}$

where $\bar{x}$ is the arithmetic mean.

$\bar{x} = \frac{1}{n}\sum_{i=1}^n{x_i}$

Expression 1 stated in words is the average squared difference of each data point from the mean. Implemented as an algorithm, this requires two passes over the data set. The first to calculate the mean and the second to sum the squared differences.

Let's derive the more commonly used expression for variance.

$\begin{align*} \frac{1}{n}\sum_{i=1}^n{\left(x_i - \bar{x}\right)^2} & = \frac{1}{n}\sum_{i=1}^n{\left({x_i}^2 - 2x_i\bar{x} + \bar{x}^2\right)} \\ & = \frac{1}{n}\left(\sum_{i=1}^n{x_i}^2 - 2\bar{x}\sum_{i=1}^n{x_i} + n\bar{x}^2\right) \\ & = \frac{1}{n}\sum_{i=1}^n{x_i}^2 - 2\bar{x}^2 + \bar{x}^2 \\ & = \frac{1}{n}\sum_{i=1}^n{x_i}^2 - \bar{x}^2 \\ & = \frac{1}{n}\sum_{i=1}^n{x_i}^2 - \left(\frac{1}{n}\sum_{i=1}^n{x_i}\right)^2 && \text{(2)} \end{align*}$

This only requires a single pass over the data set, computing the incremental sum of the values and the incremental sum of their squares. However, if the terms in the subtraction are large and close enough, catastrophic cancellation can occur. Essentially the precision of the floating point representation is exceeded, yielding unacceptable results. See Algorithms for calculating variance and Theoretical explanation for numerical results for examples (they are calculating the sample variance which is slightly different). More detailed information on catastrophic cancellation can be found in What Every Computer Scientist Should Know About Floating Point Arithmetic (1991).

A more numerically stable (but computationally expensive) single pass algorithm was published by Knuth in The Art of Computer Programming, volume 2. Define $\bar{x}_n$ and $s_n$ as the mean and sum of squared differences of the the first n values respectively.

$\begin{align*} s_0 & = 0\\ \\ s_{n+1} & = \sum_{i=1}^{n+1}\left(x_i-\bar{x}_{n+1}\right)^2\\ & = s_n + \left(x_{n+1}-\bar{x}_n\right)\left(x_{n+1}-\bar{x}_{n+1}\right)\quad\quad\quad(3) \end{align*}$

For m > 0 values, the variance is then $\frac{s_m}{m}$ .

Derivation of Equation 3
This is really just a more verbose version of one-pass algorithm to compute sample variance. First up is the running mean.

$\begin{align*} \bar{x}_0 & = 0\\ \\ \bar{x}_{n+1} & = \frac{n\bar{x}_n + x_{n+1}}{n+1}\\ & = \frac{\left(n+1\right)\bar{x}_n-\bar{x}_n+x_{n+1}}{n+1}\\ & = \bar{x}_n + \frac{x_{n+1}-\bar{x}_n}{n+1} && \quad &&& (4)\\ \end{align*}$

If you think of the mean visually i.e. a horizontal line through the data on a scatter plot, then it is intuitive that the sum of the distances between each point and the mean is zero.

$\sum_{i=1}^n\left(x_i-\bar{x}_n\right) & = \sum_{i=1}^nx_i-n\left(\frac{1}{n}\sum_{i=1}^nx_i\right)=0\quad\quad\quad(5)$

Now define $\gamma$ as the difference of consecutive incremental means, along with a few useful variations.

$\begin{align*} \gamma & = \bar{x}_{n+1} - \bar{x}_n && \quad &&& (6)\\ \\ \gamma & = \bar{x}_n + \frac{x_{n+1}-\bar{x}_n}{n+1} - \bar{x}_n && &&& \text{by (4)}\\ \gamma & = \frac{x_{n+1}-\bar{x}_n}{n+1} \\ \left(n+1\right)\gamma & = x_{n+1}-\bar{x}_n && &&& (7)\\ \\ x_{n+1}-\bar{x}_{n+1} & = x_{n+1}-\bar{x}_n+\bar{x}_n-\bar{x}_{n+1} \\ & = \left(n+1\right)\gamma-\gamma && &&& \text{by (7, 6)} \\ & = n\gamma && &&& (8)\\ \end{align*}$

The pieces are now all in place to derive equation 3.

$\begin{align*} s_{n+1} & = \sum_{i=1}^{n+1}\left(x_i-\bar{x}_{n+1}\right)^2\\ & = \sum_{i=1}^{n}\left(x_i-\bar{x}_{n+1}\right)^2 + \left(x_{n+1}-\bar{x}_{n+1}\right)^2\\ & = \sum_{i=1}^{n}\left(x_i-\bar{x}_n+\bar{x}_n-\bar{x}_{n+1}\right)^2 + \left(n\gamma\right)^2 && \quad &&& \text{by (8)}\\ & = \sum_{i=1}^{n}\left(\left(x_i-\bar{x}_n\right)-\gamma\right)^2+n^2\gamma^2 && &&& \text{by (6)}\\ & = \sum_{i=1}^{n}\left(x_i-\bar{x}_n\right)^2 -2\gamma\sum_{i=1}^{n}\left(x_i-\bar{x}_n\right)+n\gamma^2+n^2\gamma^2\\ & = s_n-0+n\gamma^2\left(1+n\right) && &&& \text{by (5)}\\ & = s_n+\left(x_{n+1}-\bar{x}_n\right)n\gamma && &&& \text{by (7)}\\ & = s_n+\left(x_{n+1}-\bar{x}_n\right)\left(x_{n+1}-\bar{x}_{n+1}\right) && &&& \text{by (8)} \end{align*}$