What does “Closed-form Solution” mean, exactly?

“Closed-form solution” is something that I encounter again and again whenever I go a bit deeper into math. It can be a bit frustrating trying to understand what it actually means, because the answer you get either doesn’t help you at all if you’re not a math person, like this one:

An equation is said to be a closed-form solution if it solves a given problem in terms of functions and mathematical operations from a given generally-accepted set. For example, an infinite sum would generally not be considered closed-form. However, the choice of what to call closed-form and what not is rather arbitrary since a new “closed-form” function could simply be defined in terms of the infinite sum.

Right, so it’s arbitrary. Thanks. Or even worse, this one:

A discrete function A(n,k) is called closed form (or sometimes “hypergeometric”) in two variables if the ratiosA(n+1,k)/A(n,k) and A(n,k+1)/A(n,k) are both rational functions. A pair of closed form functions (F,G) is said to be a Wilf-Zeilberger pair if…

Hypergeometric, rational functions, and Wilf-Zeil… let me just stop there. Look, I understand that the above explanations are probably rigorously correct mathematically, I can appreciate it. The thing is that it’s not very useful for me in trying to understand what it actually means!

Instead, let me just attempt to convey the idea using very simple examples, just like the ones used in the Wikipedia page.

The quadratic polynomial

ax^2+bx+c = 0

is closed-form, because its solution

x = \frac{ { - b \pm \sqrt {b^2 - 4ac} }}{{2a}}

can be expressed in finite numbers of elementary operations. By “elementary operations” here we mean subtraction, power, square root, division, and multiplication. Now, in this particular example, I think everyone can agree that the operations are elementary. But for more complex operations/functions, there are no general agreement on when the “elementary” label stops, exactly. This is why they say that the definition of closed-form solution is somewhat arbitrary.

Now, let’s look at an example of non-closed-form expressions. This expression

S = \sum_{i=0}^{\infty} \frac{x}{2^i}

is not in closed form, because even though the operations are simple additions, there’s an infinite number of them. Even the most powerful supercomputer in the universe will never be able to give you the final result of this sum!

But sometimes, a non-closed-form expression can be expressed in the closed form. For example, the infinite sum above can be manipulated into a closed form expression by multiplying the sum by \frac{1}{2} and subtracting the result from the original sum. That is :

S = x + \frac{x}{2} + \frac{x}{4} + \frac{x}{8} + ...

S - \frac{1}{2}S = (x + \frac{x}{2} + \frac{x}{4} + \frac{x}{8} + ...) - (\frac{x}{2} + \frac{x}{4} + \frac{x}{8} + \frac{x}{8} + ...)

\frac{1}{2}S = x

S = 2x , a decidedly closed-form expression.

That’s the value of expressing something in closed-form. Now you don’t even need a calculator to know what the sum is.

The problem is, not every expression has a closed-form equivalent. For example, Galois theory states that unlike quadratic polynomials, fifth (or higher) degree polynomials (that is, quintic, sextic, septic, octic, etc.) have no general closed-form solutions.

That is, we have general formula to find the roots of quadratic polynomials (above), we have the formula for third degree (cubic) polynomials, and we have the formula for fourth degree (quartic) polynomials. But no such thing exists for fifth degree and beyond. So what can we do?

This is where numerical methods come in. Essentially, instead of trying to find the exact solution, numerical methods give us a way to approximate the answer until we’re close enough. As a very simple example, consider the infinite sum we just discussed. How far do you think we have to go to get a result that’s very close to the exact result? Not very far.

Approximating the infinite sum

So, there it is, a post about closed-form solutions. Phew. I think I spent way more time crafting the LaTex expression than I did writing the post!

Learning Machine Learning – Intro & Roadmap

(Last revision: 2014-09-30. Added Foundation Courses section.)

I’ve been having lots of fun with Machine Learning lately. It all started with taking Andrew Ng’s excellent Coursera Machine Learning course. Andrew is a fantastic instructor, with a knack for conveying complex concepts while not getting you bogged in not-yet-relevant details that’d take away from your getting the big picture.

While taking the course, I’ve been creating a lot of draft posts, mostly about digging deeper into topics on which I’m still shaky. Most of the times, this is because of the math involved. Machine Learning requires a lot of math, and it’s on a level that’s way, way deeper than the math you’ll ever see in the CFA curriculum.

(That said, if you’re a CFA candidate or charterholder, don’t let this discourage you! The math you encounter in the CFA curriculum serves as excellent foundation to the math you’ll see in Machine Learning. Here’s a quote from the Preface of Applied Predictive Modeling book: 

For this text, the reader should have some knowledge of basic statistics, including variance, correlation, simple linear regression, and basic hypothesis testing (e.g.: p-values and test statistics).

That’s level 2 all over again, folks! 🙂 )

As part of my learning process, I’d like to create a collection of posts about Machine Learning, with the hope that the process will strengthen my own understanding, and maybe (who knows!) even help someone who’s interested in the topic, but lacking the mathematical tools and a good roadmap to follow to get better at this (i.e.: just like where I am today).

Roadmap

  1. Take Andrew Ng’s Machine Learning Course. (DONE)
  2. Go through Applied Predictive Modeling book, and pick up R language in the process. (ONGOING)
  3. (To be determined)

Math Basics

Resources

Foundation Courses

  • Probabilistic Systems Analysis and Applied Probability. I wish there were something like this when I was still in school/university back then (yes, that was a long time ago). This is an excellent course that you can take at your own pace, and it’s as good as it gets, complete with quizzes, practice problems, and solutions.

Machine Learning Courses

Machine Learning Books

  • Applied Predictive Modeling. I’m currently reading this book. I bought it because it’s (1) an introductory and (2) a very hands-on book (at least the reviews say so).
  • An Introduction to Statistical Learning: 103. A book with equally glowing reviews in Amazon. I picked Applied Predictive Modeling first because (again, from the reviews) it provides a more complete coverage of the entire process.
  • The Elements of Statistical Learning. Available in its entirety in PDF. The math is a bit too advanced for me though. There are just a bit too many foreign words for me to be distracting. I can persevere and look the words up one by one, but I suspect I’d have a more productive time with a gentler book (hence my choice to go with the Applied Predictive Modeling book).
  • Pattern Recognition and Machine Learning. Another book of which many people speak very highly. I did not pick this book because it’s not available in soft copy (unlike the AML book, which has a Kindle version that’s supposedly an exact replica of the printed book), and most importantly, I get the sense that it’s more advanced than the AML book.
  • (To be updated)

Tiny Baby Steps to Good Habits

Installing a new habit is hard. Really hard. Especially, it seems, when it’s a good habit.

Bad habits? Damn, we don’t even have to try, do we? Habits that make you hate yourself after you’ve done it for the millionth time… those are the ones that are the easiest to stick forever.

I don’t know about you, I’ve tried the 18, 21, 28, 30-day program before, and they didn’t work. While I was able to stick to the habit for 18, 21, 28, 30, whatever days… after that I simply stopped doing it.

Some of you (yes, you, one of the 3 or 4 people who are read this blog) know that I’ve put up USD3500 into a stickk.com commitment to blog about CFA level 3 exam material regularly. The idea is that doing this helps ensuring that I’m familiar with the material and I start preparing early.

But it’s hard. It’s hard to make the habit stick. I have the material in my iPad, and when I open my iPad after a hard day of work, what do I do? I open a Marvel comic. Is it a matter of willpower? Is it a matter of motivation? Maybe and maybe.

Which is why I found this approach so interesting. The idea is that you start with such tiny baby steps, that willpower and motivation don’t even come into the picture. If you can’t even take these tiny baby steps, then you might want to ask yourself again whether you really want the habit in the first place!

We will see. I have joined the Sept 10-14 session — let’s see if it works!

Scala and Project Euler

After struggling with Eclipse Scala plugin for so long, FINALLY I managed to get the latest (beta) plugin working with Eclipse Helios (3.6.x).

I’ve got to admit that my expectation was not that high in the beginning, I was expecting yet another episode of WTFs and stupid crashes with this plugin as well. But… the plugin turned out to be pretty good, actually. My very first Scala Hello World actually works! It runs! No crashes (yet)!

So what should one do with a new language to try out? I’m looking for a bunch of bite-sized problems to learn about Scala the language, not a new library, or a new algorithm, and gawd, no web applications! (I especially hate it when a language tutorial starts with a freaking application in a domain that I don’t give a damn about.)

Project Euler comes to the rescue. To quote:

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

The motivation for starting Project Euler, and its continuation, is to provide a platform for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context.

Sounds promising.

The very first problem is very easy, so I don’t think anyone would mind me posting a spoiler here, but SPOILER ALERT anyway if you continue below!

object Test {
  def main(args : Array[String]) : Unit = {
    println(sumMultiplesOfXAndYBelowLimit(3, 5, 1000))
  }

  def sumMultiplesOfXAndYBelowLimit(x: Int, y: Int, limit: Int) = {
    (1 to limit - 1) filter (s => (s % x) == 0 || (s % y) == 0) sum
  }
}

Not a sophisticated solution by any stretch of imagination.

Say instead of doing the modulus stupidly for each number between 1 and 999, one can sum (3, 6, 9…) and (5, 10, 15…) and subtract (15, 30, 45…) (because the numbers in the last group are double counted).

Or if you remember the Gauss anecdote, you can do it even simpler by using a variant of the approach.

But I particularly like how Scala makes it very clear and readable:

    (1 to limit - 1) filter (s => (s % x) == 0 || (s % y) == 0) sum

“From 1 up to but not including the limit, take all the numbers that are not multiples of x or y, and sum them up”

Nice! Maybe I’d get to continue posting actively again after such a long hiatus 🙂

EDIT: as Jem commented below, this solution can be expressed even more cleanly using until, like this

    (1 until limit) filter (s => (s % x) == 0 || (s % y) == 0) sum