Showing posts with label mathematics. Show all posts
Showing posts with label mathematics. Show all posts

Wednesday, March 2, 2011

Non-Hamiltonian Thoughts

A Graph (in computer science terms) is a collection of points and lines (edges) that connect them. Like this:

The points and the lines can symbolize many different things. For instance, points can be cities and lines can be roads. Or points can be people and an edge can mean that the two people it connects are friends.

For the purposes of this post, the points are different thoughts and facts and the line between any two of them means that they are connected.

Now, when I start writing an essay (or a blog post), one of the first things I do is gather up all my thoughts that might be relevant to the topic in my head. I then try to find a narrative that passes through all of them but proceeds smoothly from one thought to the next. This usually means that every new thought has to be connected to the one directly preceding it, which means that the essay turns out to be a "walk" in the Thought graph - you start at one point and then move along the edges until you eventually finish at some other point.

You usually have an idea what thought you want to end up at. And finding a path from the starting thought to the ending one is usually not hard. So, in formal terms, essay writing is in P.

However, imagine a different problem. You have some problem that you want to discuss with a friend. You want to give her all the relevant background information.. and you would prefer to give an essay-like presentation, smoothly moving from one point to the other without repeating yourself. In graph-theoretic terms, this is the problem of finding a Hamiltonian path.

And the sad fact is that for most graphs, this is impossible to do, and, even when it is theoretically possible, it is NP-hard to find such a graph.

So even when you have a fairly good idea about all that you would like to talk about, it is still hard, if not impossible, to formulate them in a linear and coherent way - especially if the graph is not connected enough.

As a corollary: topic jumps and/or repeating yourself are sometimes unavoidable, and should thus be seen as a normal part of conversation. After all, they are the only two solutions that still allow you to cover all of the graph.

Sunday, September 19, 2010

Mathematics as a language

I have been reading a Machine Learning textbook for the past 3 days. It uses a lot of probability theory, something I know the basics of (up to Probability theory II course). I managed to get the gist of what the book was trying to say, but am still somewhat struggling to understand how the proof of the main theorem works and what its implications are.

At some point, my roommate (who is a psychology major and very fond of languages as well) asked me to show her the proof I was reading.. and then instantly turned away when she saw the formulae. So I tried to explain to her what my problem was, in terms she could understand. And then I stumbled upon a pretty interesting and deep analogy:

Mathematics is just a set of symbols used to very precisely say things that would take a lot of plaintext to explain without the special notation. Just a means of precisely expressing yourself. Like the alphabet. However, each branch of mathematics has its own key concepts and terminology (the words) as well as diffent proof techniques (syntax). Different branches of mathematics can, in this sense, be likened to different languages. And different languages can be either very close to eachother (Statistics and Machine learning seem quite like Estonian and Finnish, for instance - they have quite a lot of common ground both in terms of key concepts and proof methods, but they are nevertheless quite distinct, with quite a few things having nearly opposite meaning)

My mother tongue in mathematics is Cryptology, with a slight accent from complexity theory. Reading a Machine Learning textbook for me is akin to reading something in a language I have studied a little (a few years, maybe) but which I am not comfortable in yet - I can make out the meaning of most that is said, but I do not grasp the nuances of the more complex words (ideas) and sometimes get their meaning completely wrong (which happens if you are forced to deduce their meaning just from the context). However, this is a pretty good way of learning the new language, as it forces you into a very deep mode of processing - you have to build up the abstract "big picture" as fast as possible and constantly try to deduce the missing details back from it. Hard, but quite enjoyable, as it makes me feel I am actually learning and very rapidly.

For those who find mathematics courses hard, this analogy might help understand what is going on: you are usually expected to learn the rudiments of a new language, often up to the point where you need to be able to not only understand it but actually "speak" it to a degree by the end. It is not harder than learning normal languages, and as with normal languages, the more different languages you learn, the easier it becomes to acquire a new one.