Learning Machine Learning – 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!

Advertisements

2 thoughts on “Learning Machine Learning – What does “Closed-form Solution” mean, exactly?

  1. Can I assume that, when non-closed-form appears in closed-form solution, It exist in pair. Somehow they cancel each other.

Leave a Reply

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

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s